Validating multiple execution plans for database queries

• US 6,721,724 B1
• Filed: 03/31/2000
• Issued: 04/13/2004
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Waas, Florian
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US09/539,824
• Time in Patent Office: 1,474 Days
• Field of Search: 707/2-7, 707/10, 707/101, 707/102, 707/201, 709/104, 705/8, 705/9, 705/10, 705/28, 705/29
• 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 for validation by a programmed digital computer, comprising:

organizing a plurality of alternative execution plans for carrying out a database query into a plurality of groups each having at least one operator associated with at least one operator in another of the groups;

determining rank data for each operator related to a number of alternative operators in the other of the groups;

determining rank data for each group;

assigning a local rank related to a number of alternative operators associated with that operator in another one of the groups; and

producing a global rank for at least one of the alternative execution plans from the rank data.

2. The method of claim 1 where each of the execution plans is a tree of the operators.

3. The method of claim 2 where each of the alternative execution plans includes operators taken from different ones of the groups.

4. The method of claim 1, further comprising the step of validating one or more of the execution plans.

5. The method of claim 1, further comprising the step of recording the alternative execution plans according to the rank data.

6. The method of claim 1, further comprising the steps of recording locations of the operators and groups associated with each alternative execution plan, according to respective rank data, whereby a total number of possible execution plans is tracked.

7. A computer readable medium that configures a computer system to perform a method, the method comprising the steps of:

organizing a plurality of alternative execution plans for carrying out a database query into a plurality of groups each having at least one operator associated with at least one operator in another of the groups;

determining rank data for each operator related to a number of alternative operators in the other of the groups;

determining rank data for each group;

assigning a local rank related to a number of alternative operators associated with that operator in another one of the groups; and

producing a global rank for at least one of the alternative execution plans from the rank data.

8. The computer readable medium of claim 7 wherein the method further comprises the step of validating one or more of the execution plans.

9. The computer readable medium of claim 7, wherein the method further comprises the step of recording the alternative execution plans according to the rank data.

10. The computer readable medium of claim 7, wherein the method further comprises the step of recording locations of the operators and groups associated with each alternative execution plan, according to respective rank data, whereby a total number of possible execution plans is tracked.

11. A method for validation by a programmed digital computer, comprising:

organizing a plurality of alternative execution plans for carrying out a database query into a plurality of groups each having at least one operator associated with at least one operator in another of the groups, where each of the execution plans is a tree of the operators and includes operators taken from different ones of the groups;

determining rank data for each operator related to a number of alternative operators in the other of the groups;

determining rank data for each group; and

producing a global rank for at least one of the alternative execution plans from the rank data.

12. The method of claim 11 where a respective global rank uniquely identifies one execution plan from all other alternative execution plans.

13. The method of claim 12 where the ranks of all alternative execution plans are dense.

14. A method for validating multiple execution plans for a single database query, comprising:

organizing alternative plans into a plurality of groups at least some of which include multiple operators associated with operators in others of the groups;

for each operator, assigning a local rank related to a number of alternative operators associated with that operator in another one of the groups; and

for each of a plurality of global rank designations, unrunking a unique one of the alternative plans corresponding to the global rank.

15. The method of claim 14 where one of the groups is a root group.

16. The method of claim 15 where some of the operators are associated with operators in only one other group.

17. The method of claim 14 where the local rank for an operator is related to a number of alternative operators in a tree containing the operator.

18. The method of claim 14 where each global rank is a number uniquely identifying one of the totality of alternative plans.

19. The method of claim 14 further comprising executing each of the plans specified by the global ranks.

20. The method of claim 14 wherein unranking one of the global rank designations comprises:

receiving a representation of the one global rank designations;

selecting one of the operators from a root group associated with the one global rank designation; and

repeating the preceding step for the other groups, always selecting one of the operators in response to the one global rank designation.

21. The method of claim 20 where the global rank designation is adjusted during each repetition of the selecting step.

22. The method of claim 20 where the received representation of the one global rank designation is randomly selected from a collection of global rank designations.

23. A computer readable medium that configures a computer system to perform a method, the method comprising the steps of:

organizing alternative plans into a plurality of groups at least some of which include multiple operators associated with operators in others of the groups;

for each operator, assigning a local rank related to a number of alternative operators associated with that operator in another one of the groups; and

for each of a plurality of global rank designations, unranking a unique one of the alternative plans corresponding to the global rank.

24. A method for validating alternative execution plans for a 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; and

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.

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

26. The method of claim 24, wherein the rank data for the execution plans is represented by consecutive designations, whereby a valid execution plan can be generated for any designation selected at random, and that different designations will produce different execution plans.

27. A method for validating alternative execution plans for a database query, the method comprising the steps of:

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

ranking the operators;

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

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; and

validating the execution tree.

28. A computer readable medium that configures a computer system to perform a method, the method comprising the steps of:

organizing a plurality of alternative execution plans for carrying out a database query into a plurality of groups each having at least one operator associated with at least one operator in another of the groups;

determining rank data for each operator related to a number of alternative operators in the other of the groups;

determining rank data for each group; and

producing a global rank for at least one of the alternative execution plans from the rank data.