Distributed query engine pipeline method and system

• US 7,472,112 B2
• Filed: 06/23/2003
• Issued: 12/30/2008
• Est. Priority Date: 06/23/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kimball, Andrew E., Desai, Arpan A., Pfleiger, Todd F.
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Darno; Patrick A
• Application Number:
  US10/601,730
• Publication Number:
  US 20040260685A1
• Time in Patent Office: 2,017 Days
• Field of Search: 707/3, 707/4, 707/104.1, 707/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8358 Query translation
• CPC Class Codes: G06F 16/84 Mapping; Conversion
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A distributed query engine pipeline architecture comprises cascaded analysis engines that accept an input query and each identifies a portion of the input query that it can pass on to an execution engine. Each stage rewrites the input query to remove the portion identified and replaces it with a placeholder. The rewritten query is forwarded to the next analysis engine in the cascade. Each engine compiles the portion it identified so that an execution engine may process that portion. Execution preferably proceeds from the portion of the query compiled by the last analysis engine. The execution engine corresponding to the last analysis engine executes the query and makes a call to the next higher execution engine in the cascade for data from the preceding portion. The process continues until the results from the input query are fully assembled.

Claims

1. A method of distributing portions of a query over two or more execution engines, the method comprising:

receiving an input query into a first analysis engine of serially cascaded analysis engines, each cascaded analysis engine serving to identify and extract portions of the input query to be compiled and executed on a particular execution engine serially cascaded with other search engines;

identifying with the first analysis engine, a portion of the input query that can be processed by a first execution engine;

compiling the identified portion of the input query forming a first compiled portion;

rewriting the input query to form a first rewritten query wherein the identified portion of the input query is removed from the input query and replaced by a first placeholder;

passing an entire portion of the first rewritten query including the first placeholder to a second analysis engine of the serially cascaded analysis engines;

identifying with the second analysis engine, a portion of the first rewritten query that can be processed by a second execution engine; and

compiling the identified portion of the first rewritten query generating a second compiled portion wherein the input query is distributed over the first execution engine and the second execution engine for sequential execution, wherein the sequential execution is performed using serially cascaded execution engines that call to one another as a source for information.

2. The method of claim 1, further comprising:

rewriting the first rewritten query to form a second rewritten query wherein the identified portion of the first rewritten query is removed from the first rewritten query and replaced by a second placeholder.

3. The method of claim 1, wherein the rewriting act further comprises wrapping the second compiled portion into the first compiled portion of the input query to produce a nested query for sequential execution.

4. The method of claim 1, wherein the first compiled portion and the second compiled portion may be executed over different data sources.

5. The method of claim 1, wherein a first analysis engine is a structured query language based engine and a second analysis engine is an extensible markup language based engine.

6. The method of claim 1, further comprising:

executing partially the second compiled portion using the second execution engine forming the combination of second interim results and the first placeholder, wherein the first placeholder remains an unexecuted part of the second compiled portion;

generating a call from the second execution engine to the first execution engine requesting the data corresponding to the first placeholder;

executing the first compiled portion using the first execution engine to form first interim results corresponding to the first placeholder and satisfying the call;

providing the first interim results to the second execution engine; and

substituting the first interim results for the first placeholder forming the combination of second interim results and first interim results comprising combined input query results.

7. The method of claim 6, wherein the first execution engine and the second execution engine operate on queries comprising different data models.

8. The method of claim 1, further comprising:

executing partially the first compiled portion using the first execution engine forming first interim results;

generating a call from the first execution engine to the second execution engine requesting the data corresponding to an unidentified portion of the input query;

executing the second compiled portion using the second execution engine to form second interim results and satisfying the call;

providing the second interim results to the first execution engine; and

combining the first interim results with the second interim results to form combined input query results.

9. The method of claim 8, wherein the first execution engine and the second execution engine operate on queries comprising different data models.

10. A system for distributive processing of an input query, the system comprising:

a computer comprising;

two or more serially cascaded analysis engines for separating out portions of the input query that can be compiled and executed, wherein each cascaded analysis engine serves to identify and extract portions of the input query to be compiled and executed on a particular execution engine serially cascaded with other search engines;

two or more serially cascaded execution engines for operation on the input query; and

access to one or more data sources, wherein the two or more analysis engines operate to independently identify and compile one or more portions of the input query wherein;

at least one of the two or more analysis engines rewrites the input query to remove the portion of the input query that corresponds to an execution engine and replaces the portion with a placeholder,

the rewritten query, including the placeholder is input to a subsequent analysis engine in the two or more serially cascaded analysis engines; and

the two or more execution engines sequentially process the one or more compiled portions of the input query such that partial query results from one execution engine are passed to a subsequent execution engine using calls between execution engines and combined to form overall input query results.

11. A computer-readable storage media containing instructions, which when run on a computer, execute a method of distributing portions of a query over two or more execution engines, the method comprising:

receiving an input query into a first analysis engine of a serial cascade of analysis engines, each cascaded analysis engine serving to identify and extract portions of the input query to be compiled and executed on a particular execution engine serially cascaded with other search engines;

identifying with the first analysis engine, a portion of the input query that can be processed by a first execution engine;

compiling the identified portion of the input query forming a first compiled portion;

rewriting the input query to form a first rewritten query wherein the identified portion of the input query is removed from the input query and replaced by a first placeholder;

passing an entire portion of the first rewritten query including the first placeholder to a second analysis engine of the serial cascade of analysis engines;

identifying with the second analysis engine, a portion of the first rewritten query that can be processed by a second execution engine; and

compiling the identified portion of the first rewritten query generating a second compiled portion wherein the input query is distributed over the first execution engine and the second execution engine; and

wherein the rewriting act further comprises wrapping the second compiled portion into the first compiled portion to produce a nested query for sequential execution, wherein calls are used between the first execution engine and the second execution engine to retrieve information.

12. The computer-readable storage medium of claim 11, further comprising:

executing partially the second compiled portion using the second execution engine forming the combination of second interim results and the first placeholder, wherein the first placeholder remains an unexecuted part of the second compiled portion;

generating a call from the second execution engine to the first execution engine requesting the data corresponding to the first placeholder;

executing the first compiled portion using the first execution engine to form first interim results corresponding to the first placeholder and satisfying the call;

providing the first interim results to the second execution engine; and

substituting the first interim results for the first placeholder forming the combination of second interim results and first interim results comprising combined input query results.

13. The computer readable storage medium of claim 12, wherein the first execution engine and the second execution engine operate on queries comprising different data models.

14. The computer readable storage medium of claim 12, wherein the first compiled portion and the second compiled portion are executed over different data sources.

15. The computer readable storage medium of claim 11, further comprising:

executing partially the first compiled portion using the first execution engine forming first interim results;

generating a call from the first execution engine to the second execution engine requesting the data corresponding to an unidentified portion of the input query;

executing the second compiled portion using the second execution engine to form second interim results and satisfying the call;

providing the second interim results to the first execution engine; and

combining the first interim results with the second interim results to form combined input query results.

16. The computer readable storage medium of claim 15, wherein a first analysis engine is a structured query language based engine and a second analysis engine is an extensible markup language based engine.