Generating a hierarchical plain-text execution plan from a database query

• US 7,167,848 B2
• Filed: 11/07/2003
• Issued: 01/23/2007
• Est. Priority Date: 11/07/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kollar, Lubor J., Boukouvalas, Alexios, Liu, Jinghao, Marathe, Arunprasad P.
• Primary Examiner(s): Hirl; Joseph P
• Application Number:
  US10/704,480
• Publication Number:
  US 20050102613A1
• Time in Patent Office: 1,173 Days
• Field of Search: 707/4, 706/14, 706/45, 706/46
• US Class Current: 706/14
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A system, method and computer-readable medium containing computer-executable instructions for tuning queries is provided. A query processor converts a query into an execution plan in a hierarchical format that conforms to a standardized schema. In one embodiment of the invention, the hierarchical format employed is XML.

Claims

1. A system for generating a hierarchical plain-text execution plan comprising:

an execution plan creator, the execution plan creator receiving a physical operator tree representing a plan to execute a query and generating from the physical operator tree a hierarchical plain-text execution plan from a compiled query plan to create a compile-time execution plan and updating the compile-time execution plan with execution information available when the compile-time execution plan is executed to create and store an execution-time execution plan.

2. The system of claim 1, wherein the hierarchical plain-text execution plan is an XML document.

3. The system of claim 2, wherein the XML document adheres to a specified XML schema.

4. The system of claim 1, wherein the physical operator tree is modified to create a transformed physical operator tree associated with a query, the transformed physical operator tree shared by a plurality of instances of the query.

5. The system of claim 4, wherein the transformed physical operator tree is read-only.

6. The system of claim 1, wherein the physical operator tree is modified to create a transformed physical operator tree associated with a particular instance of a query.

7. The system of claim 1, wherein the execution plan creator generates a first physical operator tree and a second physical operator tree, the first physical operator tree associated with the query and the second physical operator tree associated with a particular instance of the query.

8. The system of claim 1, further comprising a query parser, wherein the query parser receives a database query, parses the database query for correct syntax and builds a relational operator tree representing the database query.

9. The system of claim 8, wherein the database query is a SQL query.

10. The system of claim 1, further comprising a query optimizer that generates at least one physical operator tree from the relational operator tree representing the database query.

11. The system of claim 10, wherein the query optimizer transforms the relational operator tree into a plurality of physical operator trees using a plurality of tree transformation rules.

12. The system of claim 11, wherein the plurality of physical operator trees are logically equivalent.

13. The system of claim 12, wherein the query optimizer selects a one of the plurality of physical operator trees to execute.

14. The system of claim 13, wherein the query optimizer selects the one of the plurality of physical operator trees to execute based on an estimated cost of execution.

15. The system of claim 13, wherein the query executor executes the one of the plurality of physical operator trees to execute.

16. A method for generating a hierarchical plain-text execution plan for a query, the method comprising:

in response to receiving a database query, separating the database query into non-query language constructs and language constructs;

generating from the non-query language constructs a first hierarchical plain-text execution plan;

generating from the query language constructs a second hierarchical plain-text execution plan;

merging the first and second hierarchical plain-text execution plan into a composite compile-time execution plan;

updating the composite compile-time execution plan with information available when the composite compile-time execution plan is executed to create and store an execution-time execution plan.

17. The method of claim 16, wherein the composite execution plan is an XML document.

18. The method of claim 17, wherein the XML document conforms to an XML schema comprising the following elements:

EstimateCPU, EstimateIO, EstimateRebinds, EstimateRewinds, and Estimate Rows.

19. A tangible computer-readable medium including computer-readable instructions for:

in response to receiving a database query, separating the database query into non-query language constructs and language constructs and generating from the non-query language constructs a first compile-time hierarchical plain-text execution plan and generating from the query language constructs a second compile-time hierarchical plain-text execution plan;

merging the first and second plans together to create a composite compile-time execution plan; and

updating the composite compile-time execution plan with information available when the composite compile-time execution plan is executed to create and store an execution-time execution plan.