Validating multiple execution plans for database queries

• US 7,337,169 B2
• Filed: 09/23/2005
• Issued: 02/26/2008
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Waas, Florian, Galindo-Legaria, Cesar A.
• Primary Examiner(s): Gaffin; Jeffrey
• Assistant Examiner(s): Veillard; Jacques
• Application Number:
  US11/234,467
• Publication Number:
  US 20060020573A1
• Time in Patent Office: 886 Days
• Field of Search: 707 1- 7, 707/10, 707100-102, 707/104.1, 707/201, 709/203, 709/204, 709/206, 709/213
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/959 Network
• 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/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Validation of large numbers of alternative execution plans for a database query, either an exhaustive enumeration of the complete space of alternatives, or else an unbiased random sample, is performed by efficiently constructing execution trees from a data structure having groups alternative operators that are ranked in a directory. Each global rank of a plan identifies that plan uniquely among all the alternative plans. The operators are unranked from the directory according to a specification that characterizes the desired plans.

Claims

1. A method implemented at least in part by a computing device for organizing multiple execution plans for database query, the method comprising the steps of:

arranging a plurality of execution plans into a plurality of groups, each group having at least one operator associated with at least one operator in another of the groups;

determining identification data for each operator related to other operators in the other of the groups;

determining identification data for each execution plan based on the identification data for each operator, whereby the identification data for each execution plan uniquely identifies the respective execution plan from all other execution plans; and

storing the identification data.

2. The method of claim 1, wherein the identification data for each execution plan represents a combination of operator choices within the groups used to obtain the respective execution plan.

3. The method of claim 1, wherein the identification data for the execution plans is represented by consecutive designations.

4. The method of claim 1, further comprising adjusting the identification data of an operator after selection of the operator in a construction of an execution plan.

5. The method of claim 1, further comprising selecting an execution plan having a lowest estimated cost, in relation to all other execution plans, for obtaining data responsive to the database query.

6. The method of claim 1, further comprising recording the execution plans according to the identification data for each execution plan.

7. The method of claim 1, further comprising recording locations of the operators associated with each execution plan according to respective identification data.

8. The method of claim 1, further comprising validating one or more of the execution plans and accordingly adjusting the identification data for each validated execution plan.

9. The method of claim 8, further comprising listing the execution plans according to the adjusted identification data for each execution plan, whereby the execution plans are listed in an order of relative performance during validation.

10. The method of claim 3, further comprising generating an execution plan for a designation selected at random.

11. The method of claim 1, further comprising listing the execution plans according to the identification data for each execution plan, resulting in each execution plan being randomly selectable for testing.

12. A method implemented at least in part by a computing device for generating a plan for executing a database query, the method comprising:

developing groups of operators representing alternative execution plans for a query;

ranking the operators;

assigning unique identifiers to the alternative execution plans based on the ranking of the operators; and

storing the unique identifiers.

13. The method of claim 12, further comprising assembling an execution tree for a selected execution plan by unranking the selected execution plan, wherein unranking the selected execution plan involves selecting one of the operators from each group associated with the identifier of the selected execution plan.

14. The method of claim 12, further comprising testing each execution plan to determine an execution plan having a lowest estimated cost, in relation to all other execution plans, for obtaining data responsive to the database query.

15. The method of claim 14, further comprising listing each execution plan according to the respective unique identifier and the respectively determined cost associated with the execution plan for later use in construction of alternative plans other than a single optimum plan.

16. A computer-readable medium comprising a directory for a data structure having a plurality of groups of alternative operators for carrying out a database query in accordance with an execution plan, the directory comprising:

rank data for each operator in relation to the alternative operators; and

unique rank data for each execution plan based on respective operator rank data, said unique rank data suitable to facilitate organization of execution plans.

17. The computer-readable medium of claim 16, wherein the data structure is a table.

18. The computer-readable medium of claim 16, wherein the directory further includes locations of the groups and the operators including the groups.

19. The computer-readable medium of claim 18, wherein operators of an execution plan are selected by accessing operator locations in the data structure.

20. The computer-readable medium of claim 19, further including rank data for each group representing a number of alternative execution plans associated with that group.