Query optimization by sub-plan memoization

• US 6,850,925 B2
• Filed: 05/15/2001
• Issued: 02/01/2005
• Est. Priority Date: 05/15/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aboulnaga, Ashraf I., Chaudhuri, Surajit
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): RAYYAN, SUSAN F
• Application Number:
  US09/858,206
• Publication Number:
  US 20030055813A1
• Time in Patent Office: 1,358 Days
• Field of Search: 707/2, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Database system query optimizers use several techniques such as histograms and sampling to estimate the result sizes of operators and sub-plans (operator trees) and the number of distinct values in their outputs. Instead of estimates, the invention uses the exact actual values of the result sizes and the number of distinct values in the outputs of sub-plans encountered by the optimizer. This is achieved by optimizing the query in phases. In each phase, newly encountered sub-plans are recorded for which result size and/or distinct value estimates are required. These sub-plans are executed at the end of the phase to determine their actual result sizes and the actual number of distinct values in their outputs. In subsequent phases, the optimizer uses these actual values when it encounters the same sub-plan again.

Claims

1. An iterative process for optimizing a query to produce an optimized query execution plan for a database comprising the steps of:

a) initializing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans;

b) optimizing an input query to produce a first set of sub-plans, which when executed produce result record sets from the database;

c) forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans;

d) executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure for use in producing a final query execution plan for answering the input query; and

e) creating a different set of query sub-plans using a result stored in the sub-plan memo data structure and using said query sub-plans to create one or more additional sub-plan query statements which are then executed over the database.

2. The process of claim 1 wherein executing a sub-plan query statement produces a count of the number of data records and a count of the number of distinct data record values as a result which are stored in the sub-plan memo data structure.

3. The process of claim 1 wherein additional sub-plans are added to said first set of sub-plans in a sequence of optimization iterations until no sub-plans are added that do not have corresponding sub-plan query statements that have been executed over the database.

4. The process of claim 3 wherein a decision to add a new sub-plan during said sequence of optimization iterations uses results stored in the sub-plan memo data structure to produce one or more additional query execution sub-plans.

5. The method of claim 1 wherein the first set of sub-plans is derived from data in a catalog containing statistics regarding the contents of the database.

6. The method of claim 5 wherein data from the catalog is used to produce a sub-plan execution solution for each of the sub-plans in said first set of sub-plans.

7. The method of claim 5 wherein an optimizer component does not execute sub-plan query statements nor store results in the sub-plan memo data structure for certain input queries but instead uses the contents of said catalog to create the final query execution plan.

8. Computer apparatus for executing a query comprising:

a) a computer input for receiving a user query;

b) a computer memory containing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans for answering the user query;

c) an optimizer component for evaluating an input query to produce a first set of sub-plans, which when executed produce result record sets from the database;

d) said optimizer component including means for forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans;

e) a query execution component for executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure for use in producing a final query execution plan for answering the input query; and

f) said optimizer component including means to create a different set of query sub-plans using the results stored in the sub-plan memo data structure.

9. The apparatus of claim 8 wherein said optimizer component executes a sub-plan query statement and produces a count of the number of data records and a count of the number of distinct data records as results which are stored in the sub-plan memo data structure.

10. The apparatus of claim 8 wherein the optimizer component adds additional sub-plans to said first set of sub-plans in a sequence of optimization iterations until no sub-plans are added that do not have corresponding sub-plan query statements that have been executed over the database.

11. The apparatus of claim 10 wherein the optimizer bases a decision to add a new sub-plan during said sequence of optimization iterations on using results stored in the sub-plan memo data structure to produce one or more additional query execution sub-plans.

12. The apparatus of claim 8 wherein the optimizer adds sub-plans to said first set of query execution sub-plans in a sequence of optimization iterations until the number of optimization iterations reaches a specified number or until no sub-plan query statements are added to the sub-plan memo data structure.

13. The apparatus of claim 8 wherein the optimizer maintains a catalog containing statistics regarding the contents of the database and derives the first set of sub-plans from data in said catalog.

14. The apparatus of claim wherein the optimizer uses data from the catalog to produce a sub-plan execution solution for at least some of the sub-plans in said first set of sub-plans.

15. A computer readable medium containing instructions for optimizing a query execution plan for a database comprising instructions for:

a) initializing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans;

b) evaluating an input query to produce a first set of sub-plans, which when executed produce result record sets from the database;

c) forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans;

d) executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure for use in producing a final query execution plan for answering the input query; and

e) creating a different set of query sub-plans using a result stored in the sub-plan memo data structure and using said query sub-plans to create one or more additional sub-plan query statements which are then executed over the database.

16. The computer readable medium of claim 15 wherein instructions for executing a sub-plan query statement produce a count of the number of data records and a count of the number of distinct data record values as results which are stored in the sub-plan memo data structure.

17. The computer readable medium of claim 15 wherein said instructions add sub-plans to said first set of sub-plans in a sequence of optimization iterations until no sub-plans are added that do not have corresponding sub-plan query statements that have been executed over the database.

18. The computer readable medium of claim 17 wherein the instructions implement a decision to add a new sub-plan during said sequence of optimization iterations based on results stored in the sub-plan memo data structure to produce one or more additional query execution sub-plans.

19. The computer readable medium of claim 15 wherein the instructions add sub-plans to said first set of query execution sub-plans in a sequence of optimization iterations until the number of optimization iterations reaches a specified number or until no sub-plan query statements are added to the sub-plan memo data structure.

20. The computer readable medium of claim 15 wherein the instructions construct the first set of sub-plans from data in a catalog containing statistics regarding the contents of the database.

21. The computer readable medium of claim 20 wherein the instructions use data from the catalog to produce a sub-plan execution solution for each of the sub-plans in said first set of sub-plans.

22. The computer readable medium of claim 21 wherein the instructions implement a decision which determines whether or not to execute sub-plan query statements and store results in the sub-plan memo data structure for certain input queries and when the sub-plan query statements are not executed said instructions use the contents of said catalog to create the final query execution plan.

23. An iterative process for optimizing a query to produce an optimized query execution plan for a database comprising the steps of:

a) initializing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans;

b) optimizing an input query to produce a first set of sub-plans, which when executed produce result record sets from the database;

c) forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans;

d) executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure for use in producing a final query execution plan for answering the input query; and

e) performing a series of optimization iterations in which additional sub-plans are added to the first set of query execution sub-plans until the number of optimization iterations reaches a specified number or until no sub-plan query statements are added to the sub-plan memo data structure.

24. A computer readable medium having instructions for optimizing a query to produce an optimized query execution plan for a database comprising instructions for:

a) initializing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans;

b) optimizing an input query to produce a first set of sub-plans, which when executed produce result record sets from the database;

c) forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans;

d) executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure for use in producing a final query execution plan for answering the input query; and

e) performing a series of optimization iterations in which additional sub-plans are added to the first set of query execution sub-plans until the number of optimization iterations reaches a specified number or until no sub-plan query statements are added to the sub-plan memo data structure.

25. A process for optimizing a query to produce a query execution plan for a database comprising the steps of:

a) initializing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans;

b) optimizing an input query to produce a first set of sub-plans, which when executed produce result record sets from the database;

c) forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans; and

d) executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure including a hash table wherein the query for a given sub-plan is a key for accessing contents of said hash table relating to result size and number of distinct values from execution of the query for said sub-plan for use in producing a final query execution plan for answering the input query.

26. A computer readable medium having instructions for optimizing a query to produce a query execution plan for a database comprising instructions for:

a) initializing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans;

b) optimizing an input query to produce a first set of sub-plans, which when executed produce result record sets from the database;

c) forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans; and

d) executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure including a hash table wherein the query for a given sub-plan is a key for accessing contents of said hash table relating to result size and number of distinct values from execution of the query for said sub-plan for use in producing a final query execution plan for answering the input query.