Query optimizer system and method

• US 7,146,352 B2
• Filed: 06/23/2003
• Issued: 12/05/2006
• 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., Brundage, Michael L.
• Primary Examiner(s): Vo, Tim
• Assistant Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US10/601,480
• Publication Number:
  US 20050004892A1
• Time in Patent Office: 1,261 Days
• Field of Search: 707/2, 707/3, 707/4, 707/100, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8365 Query optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An optimizer/normalizer is used to generate optimized intermediate language representation of an input query, such as an XML input query. A method of optimization of an input query in intermediate language form includes receiving the input query, examining the nodes in a left-depth first manner to identify code patterns and node types which are subjects for optimization, tagging the identified code patterns until the intermediate language representation of the input query has been examined in its entirety, searching from the top of the intermediate language representation for tagged code patterns, and adjusting the tagged code patterns with improved code patterns to form an optimal representation for an input query. The input to the optimizer/normalizer is assumed to be an input query transformed into an intermediate language representation containing code patterns and nodes, each node having a respective node type.

Claims

1. A method for constructing an optimal representation for an input query, the method comprising:

receiving the input query, wherein the input query is an intermediate language representation comprising nodes, each node having a respective node type;

examining the nodes in a left-depth first manner to identify node types for optimization;

tagging nodes corresponding to the identified node types;

moving upward to the next node until the intermediate language representation of the input query has been examined in its entirety;

searching from the top of the intermediate language representation for tagged nodes and identifying code patterns to be optimized; and

adjusting the identified code patterns with improved code patterns to form an optimal representation for the input query,

wherein the improved code patterns are generated using one or more translations comprising at least one of constant folding, logical rewrites, path rewrites, loop-invariant code rewrites, tuple rewrites, position rewrites, commutations. inlining and sort elimination.

2. The method of claim 1, wherein the receiving step comprises receiving a semantic intermediate language representation.

3. The method of claim 2, wherein the semantic representation comprises a graph structure containing nodes.

4. A computer-readable medium having computer-executable instructions executed by a processor for performing a method for constructing an optimal representation for an input query, the method comprising:

receiving the input query, wherein the input query is an intermediate language representation containing code patterns and nodes, each node having a respective node type;

examining the nodes in a left-depth first manner to identify code patterns and node types which are subjects for optimization;

tagging the identified code patterns until the intermediate language representation of the input query has been examined in its entirety;

searching from the top of the intermediate language representation for tagged code patterns; and

adjusting the tagged code patterns with improved code patterns to form an optimal representation for an input query,

wherein the improved code patterns are generated using one or more translations comprising at least one of constant folding, logical rewrites, path rewrites, loop-invariant code rewrites, tuple rewrites, position rewrites, commutations, inlining and sort elimination.

5. A computer system for generating an optimized representation of an XML intermediate language representation of one or more of input queries comprising:

one or more of input devices for receiving the one or more input queries;

one or more intermediate language compilers wherein each compiler generates an intermediate language representation of an input query;

an expression accumulator which combines each intermediate language representation into a single XML intermediate language representation; and

an optimizer performing the acts of;

receiving the input query, wherein the input query is an intermediate language representation containing code patterns and nodes, each node having a respective node type;

examining the nodes in a left-depth first manner to identify code patterns and node types which are subjects for optimization;

tagging the identified code patterns until the intermediate language representation of the input query has been examined in its entirety;

searching from the top of the intermediate language representation for tagged code patterns; and

adjusting the tagged code patterns with improved code patterns to form an optimal representation for an input query,

wherein the improved code patterns are generated using one or more translations comprising at least one of constant folding, logical rewrites, path rewrites, loop-invariant code rewrites. tuple rewrites, position rewrites, commutations, inlining and sort elimination.

6. The system of claim 5, wherein the one or more input queries comprise one or more of an XML query and an XML view.

7. The system of claim 5, further containing a post-optimization process portion forming query results, the system comprising:

one or more target generators wherein the optimized representation is transformed into one or more target representations forming target queries;

one or more data sources for querying over; and

one or more execution engines wherein the target queries are executed over the one or more data sources to produce query results.

8. A method for constructing an optimal representation for an input query, the method comprising:

receiving the input query, wherein the input query is an intermediate language representation containing nodes, each node having a respective node type;

examining the nodes to inspect code patterns associated with respective node types;

comparing the inspected code patterns using a pattern match algorithm to detect non-optimized code patterns; and

adjusting one or more of the non-optimized code patterns and the inspected code patterns with improved code patterns to form an optimal representation for an input query,

wherein the improved code patterns are generated using one or more translations comprising at least one of constant folding, logical rewrites, path rewrites, loop-invariant code rewrites, tuple rewrites, position rewrites, commutations, inlining and sort elimination.

9. The method of claim 8, wherein the receiving step comprises receiving a semantic intermediate language representation.

10. The method of claim 9, wherein the semantic representation comprises a graph structure containing nodes.

11. A computer-readable medium having computer-executable instructions executed by a processor for performing a method for constructing an optimal representation for an input query, the method comprising:

receiving the input query, wherein the input query is an intermediate language representation containing nodes, each node having a respective node type;

examining the nodes to inspect code patterns associated with respective node types;

comparing the inspected code patterns using a pattern match algorithm to detect non-optimized code patterns; and

adjusting one or more of the non-optimized code patterns and the inspected code patterns with improved code patterns to form an optimal representation for an input query,

wherein the improved code patterns are generated using one or more translations comprising at least one of constant folding, logical rewrites, path rewrites, loop-invariant code, tuple rewrites, position rewrites, commutations, inlining and sort elimination.

12. A computer system for generating an optimized representation of an XML intermediate language representation of one or more of input queries comprising:

one or more of input devices for receiving the one or more input queries;

one or more intermediate language compilers wherein each compiler generates an intermediate language representation of an input query;

an expression accumulator which combines each intermediate language representation into a single XML intermediate language representation; and

an optimizer performing the acts of;

receiving the input query, wherein the input query is an intermediate language representation containing nodes, each node having a respective node type;

examining the nodes to inspect code patterns associated with respective node types;

comparing the inspected code patterns using a pattern match algorithm to detect non-optimized code patterns; and

adjusting one or more of the non-optimized code patterns and the inspected code patterns with improved code patterns to form an optimal representation for an input query, wherein the improved code patterns are generated using one or more translations comprising at least one of constant folding, logical rewrites, path rewrites, loop-invariant code, tuple rewrites, position rewrites, commutations, inlining and sort elimination.