Pipelineable and parallelizable streaming parsers for querying structured data-interchange information

Patent metadata

Field	Value
Publication number	US-11537620-B2
Application number	US-202117443610-A
Country	US
Kind code	B2
Filing date	Jul 27, 2021
Priority date	Oct 2, 2019
Publication date	Dec 27, 2022
Grant date	Dec 27, 2022

Abstract

A computing system includes a processor and memory. The memory includes instruction code that causes the processor to generate first and second parser instances and associate the first parser and the second parser with respective first and second search queries. The processor controls the first parser to repeatedly obtain data from the data stream in blocks until the first parser finishes identifying elements in the data stream associated with its search path. The processor controls the second parser to repeatedly obtain blocks from the first parser when the blocks obtained by the first parser have not been searched by the second parser, and controls the second parser to obtain blocks from the data stream when the blocks obtained by the first parser have been searched by the second parser and the first parser has finished searching.

First claim

What is claimed is:

1. A system, comprising:
a processor; and
a memory, accessible by the processor, storing instructions that, when executed by the processor, cause the processor to perform operations comprising:
associating a first parser with a first search query;
associating a second parser with a second search query;
controlling the first parser to obtain first data from a data stream and to search the obtained first data for a first set of elements associated with the first search query;
associating a read-from-stream flag (RS flag) with the second parser, wherein the RS flag defines a false state and a true state;
controlling, in response to the RS flag being in the false state, the second parser to receive the obtained first data from the first parser and search the obtained first data for a second set of elements associated with the second search query;
controlling, in response to the RS flag being in the true state, the second parser to obtain second data from the data stream and search the obtained second data for the second set of elements associated with the second search query;
outputting the first set of elements found by the first parser as a first result of the searching; and
outputting the second set of elements found by the second parser as a second result of the searching.

2. The system of claim 1 , wherein the operations comprise:
receiving the first search query and the second search query; and
in response to receiving the first search query and the second search query:
generating the first parser; and
generating the second parser.

3. The system of claim 1 , wherein the second search query is different from the first search query, and wherein the second set of elements found by the second parser occur in the data stream before the first set of elements found by the first parser.

4. The system of claim 1 , wherein the operations comprise:
generating a third parser;
associating the third parser with a third search query;
associating a second RS flag with the third parser; and
controlling, in response to the second RS flag being in the false state, the third parser to receive third data from the second parser and search the third data for a third set of elements associated with the third search query.

5. The system of claim 4 , wherein when the first parser is not finished searching and the second parser is finished searching, the second parser is controlled by the processor to continue to receive the obtained first data from the first parser and provide the obtained first data to the third parser.

6. The system of claim 1 , wherein receiving, by the second parser, the obtained first data from the first parser comprises: obtaining a copy of a particular portion of the first data from the first parser, obtaining a reference to a memory location of the particular portion of the first data, or any combination thereof.

7. The system of claim 1 , wherein the first and second parsers are controlled by the processor to search a particular block of data simultaneously.

8. A computer-implemented method comprising:
associating a first parser with a first search query;
associating a second parser with a second search query;
controlling the first parser to obtain first data from a data stream and to search the obtained first data for a first set of elements associated with the first search query;
associating a read-from-stream flag (RS flag) with the second parser, wherein the RS flag defines either a false state or a true state;
controlling, in response to the RS flag being in the false state, the second parser to receive the obtained first data from the first parser and search the obtained first data for a second set of elements associated with the second search query;
controlling, in response to the RS flag being in the true state, the second parser to obtain second data from the data stream and search the obtained second data for the second set of elements associated with the second search query;
outputting the first set of elements found by the first parser as a first result of the searching; or
outputting the second set of elements found by the second parser as a second result of the searching.

9. The computer-implemented method of claim 8 , comprising:
generating a third parser;
associating the third parser with a third search query; and
associating a second RS flag with the third parser; and
controlling, in response to the second RS flag being in the false state, the third parser to receive third data from the second parser and search the third data for a third set of elements associated with the third search query.

10. The computer-implemented method of claim 9 , wherein when the first parser is not finished searching and the second parser is finished searching, the method comprises:
continuing to receive the obtained first data from the first parser and provide the obtained first data to the third parser.

11. The computer-implemented method of claim 8 , comprising:
receiving the first search query and the second search query; and
wherein the first parser is associated with the first search query in response to receiving the first search query and the second parser is associated with second search query in response to receiving the second search query.

12. The computer-implemented method of claim 8 , wherein the second search query is different from the first search query, and wherein the second set of elements found by the second parser occur in the data stream before the first set of elements found by the first parser.

13. The computer-implemented method of claim 8 , wherein receiving, by the second parser, the obtained first data from the first parser comprises: obtaining a copy of a particular portion of the first data from the first parser, obtaining a reference to a memory location of the particular portion of the first data, or any combination thereof.

14. The computer-implemented method of claim 8 , wherein the first parser and the second parser are configured to search a particular block of data simultaneously.

15. An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions that, when executed by a processor, cause the processor to perform operations comprising:
associating a first parser with a first search query;
associating a second parser with a second search query;
controlling the first parser to obtain first data from a data stream and to search the obtained first data for a first set of elements associated with the first search query;
associating a read-from-stream flag (RS flag) with the second parser, wherein the RS flag defines a false state and a true state;
controlling, in response to the RS flag being in the false state, the second parser to receive the obtained first data from the first parser and search the obtained first data for a second set of elements associated with the second search query;
controlling, in response to the RS flag being in the true state, the second parser to obtain second data from the data stream and search the obtained second data for the second set of elements associated with the second search query;
outputting the first set of elements found by the first parser as a first result of the searching; and
outputting the second set of elements found by the second parser as a second result of the searching.

16. The article of manufacture of claim 15 , wherein the second search query is different from the first search query, and wherein the second set of elements found by the second parser occur in the data stream before

Assignees

• Servicenow Inc

Inventors

• Motamedi Khosrow Jian

Classifications

• G06F16/24568 Primary

  Data stream processing; Continuous queries · CPC title

• G06F16/248

  Presentation of query results · CPC title