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

Patent metadata

Field	Value
Publication number	US-11086879-B2
Application number	US-201916591334-A
Country	US
Kind code	B2
Filing date	Oct 2, 2019
Priority date	Oct 2, 2019
Publication date	Aug 10, 2021
Grant date	Aug 10, 2021

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 computing system for processing information communicated via a data stream that contains one or more elements, the computing system comprising:
a processor; and
memory in communication with the processor, storing instruction code executable by the processor to cause the processor to perform operations that include:
generating instances of a first parser and a second parser;
associating the first parser with a first search query and the second parser with a second search query;
controlling the first parser to obtain data from the data stream in blocks and to search the blocks for one or more elements that are associated with the first search query;
controlling the second parser to search the obtained blocks for one or more elements that are associated with the second search query;
controlling the first parser to repeatedly obtain data from the data stream in blocks until the first parser finishes searching;
controlling the second parser to: (i) repeatedly obtain the blocks from the first parser when the blocks obtained by the first parser have not been searched by the second parser, and (ii) repeatedly obtain blocks from the data stream when the first parser has finished searching and all of the blocks obtained by the first parser have been searched by the second parser; and

outputting a first set of elements found by the first parser as a first result of searching and a second set of elements found by the second parser as a second result of the searching to a database, file, or calling process implemented by the processor.

2. The computing system of claim 1 , wherein the instruction code causes the processor to perform operations that include:
receiving the first search query and the second search query from one or more users; and
wherein in response to receiving the first search query and the second search query, the first parser is generated and associated with the first search query and the second parser is generated and associated with second search query.

3. The computing system of claim 1 , wherein the second search query is different from the first search query, and wherein the one or more elements associated with the second search query occur in the data stream before the one or more elements associated with the first search query.

4. The computing system of claim 1 , wherein the instruction code causes the processor to perform operations that include:
generating an instance of a third parser;
associating the third parser with a third search query;
controlling the third parser to search the blocks for one or more elements that are associated with third search query; and
controlling the third parser to: (i) repeatedly obtain the blocks from the second parser when the blocks obtained by the second parser have not been searched by the third parser, and (ii) repeatedly obtain the blocks from the data stream when the first parser and the second parser have finished searching and all of the blocks obtained by the second parser have been searched by the third parser.

5. The computing 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 obtain the blocks from the first parser and provide the blocks obtained to the third parser.

6. The computing system of claim 1 , wherein obtaining, by the second parser, a particular block from the first parser comprises one of: obtaining a copy of the particular block from the first parser, or obtaining a reference to a memory location of the particular block from the first parser.

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

8. A computer-implemented method for processing information, wherein the information is represented by a data stream that contains one or more elements, the computer-implemented method comprising:
generating instances of a first parser and a second parser;
associating the first parser with a first search query and the second parser with a second search query;
obtaining, by the first parser, data from the data stream in blocks;
searching, by the first parser, the blocks for one or more elements that are associated with the first search query;
searching, by the second parser, the obtained blocks for one or more elements that are associated with the second search query; and
repeatedly obtaining, by the first parser, data from the data stream in blocks until the first parser finishes searching;
repeatedly obtaining, by the second parser, the blocks from (i) the first parser when the blocks obtained by the first parser have not been searched by the second parser, and (ii) the data stream when the first parser has finished searching and the blocks obtained by the first parser have been searched by the second parser; and
outputting a first set of elements found by the first parser as a first result of searching and a second set of elements found by the second parser as a second result of the searching to a database, file, or calling process implemented by a processor.

9. The computer-implemented method of claim 8 , comprising:
receiving the first search query and the second search query from one or more users; and
wherein in response to receiving the first search query and the second search query, the first parser is generated and associated with the first search query and the second parser is generated and associated with second search query.

10. 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 associated with the second search query occur in the data stream before the first set of elements associated with the first search query.

11. The computer-implemented method of claim 8 , comprising:
generating an instance of a third parser;
associating the third parser with a third search query;
repeatedly obtaining, by the third parser, blocks from: (i) the second parser when the blocks obtained by the second parser have not been searched by the third parser, and (ii) the data stream when the first parser and the second parser have finished searching and all of the blocks obtained by the second parser have been searched by the third parser; and
searching, by the third parser, the obtained blocks for one or more elements within each block that are associated with third search query.

12. The computer-implemented method of claim 11 , wherein the first parser is not finished searching and the second parser is finished searching, the method comprises:
continuing to repeatedly obtain, by the second parser, the blocks from the first parser and provide the blocks obtained to the third parser.

13. The computer-implemented method of claim 8 , wherein obtaining, by the second parser, a particular block from the first parser comprises one of: obtaining a copy of the particular block from the first parser, or obtaining a reference to a memory location of the particular block from the first parser.

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

15. An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions for processing information communicated via a data stream that contains one or more elements, wherein the program instructions are executable by a computing system to cause the computing system to perform operatio

Assignees

• Servicenow Inc

Inventors

• Motamedi Khosrow Jian

Classifications

• G06F16/248

  Presentation of query results · CPC title

• G06F16/24568 Primary

  Data stream processing; Continuous queries · CPC title