Validating multiple execution plans for database queries

• US 7,158,963 B2
• Filed: 03/24/2005
• Issued: 01/02/2007
• 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): Robinson; Greta
• Assistant Examiner(s): Veillard; Jacques
• Application Number:
  US11/089,235
• Publication Number:
  US 20050267874A1
• Time in Patent Office: 649 Days
• Field of Search: 707100-102, 707200-201, 707 1- 10, 707/104.1, 709/104, 709/219
• US Class Current: 707/718
• 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 constructing multiple alternative execution plans for a single database query, comprising:

constructing one of the execution plans by

selecting one of a plurality of operators from a root group of a data structure having a plurality of groups of alternative operators, certain of the operators having pointers to one or more different ones of the groups,

selecting one of a plurality of the operators in at least one of the different groups,

repeating the preceding act of selecting one of a plurality of the operators in at least one of the different groups until reaching an operator not having a pointer to another one of the groups,

repeating the above acts, selecting at least one different operator for each of the constructed plans, where rank data is determined for each operator that distinguishes that operator from alternative operators in other groups, the rank data facilitating construction of the multiple alternative execution plans.

2. The method of claim 1, where the operators are selected by accessing a directory containing their locations in the data structure.

3. The method of claim 1, further comprising the act of adjusting the rank of one of the selected operators after it has been selected.

4. The method of claim 1, further comprising the act of receiving a specification containing at least one global rank designation, and where the selecting acts select their respective operators in response to the global rank designation.

5. The method of claim 4, where the respective operators are selected to result in the global rank designation uniquely identifying a single one of the alternative execution plans.

6. The method of claim 4, where the specification contains a plurality of global rank designations.

7. The method of claim 6, further comprising the act of deriving the plurality of global rank designations from the specification.

8. The method of claim 1, where the operators and pointers form a tree structure.

9. The method of claim 8, where each operator is selected in each repetition in a manner resulting in all of the possible alternative plans having approximately the same probability of being unranked.

10. The method of claim 8, where the probability of selecting an operator in each group is proportional to the number of possible subtrees of the respective operator in relation to the total number of subtrees of all operators in the respective group.

11. The method of claim 1, wherein determining rank data for each operator further includes assigning a local rank for each operator related to a number of alternative operators associated with that operator in other of the groups and wherein a unique global rank is produced for each of the alternative execution plans from the operator rank data.

12. The method of claim 1, where the rank data determined for each operator is based upon a number of alternative execution plans occurring through use of the respective operator.

13. The method of claim 12, where a global rank designation is determined for each alternative execution plan based upon respective ranks determined for each operator in the respective execution plan.

14. A computer-readable medium having a tangible component and having computer-executable instructions for performing a method for constructing multiple alternative execution plans for a single database query, the method comprising the acts of:

constructing one of the execution plans by

selecting one of a plurality of operators from a root group of a data structure having a plurality of groups of alternative operators, certain of the operators having pointers to one or more different ones of the groups,

selecting one of a plurality of the operators in at least one of the different groups,

repeating the preceding act of selecting one of a plurality of the operators in at least one of the different groups until reaching an operator not having a pointer to another one of the groups,

repeating the above acts, selecting at least one different operator for each of the constructed plans;

where rank data is determined for each operator related to a combination

of operator choices in a plan tree occurring from the respective operator.

15. The method of claim 14, where the medium is a storage medium.

16. The method of claim 14, where the medium is a signal transmitted on a network of computers.

17. The method of claim 14, where a global rank is determined for at least one of the execution plans based on operator rank data of operators used in the respective plan.

18. The method of claim 17, where a global rank is determined for each execution plan based on operator rank data of operators used in each execution plan.

19. The method of claim 18, where a total number of global ranks determined is based on a total combination of operator choices occurring within the plurality of groups, and each global rank uniquely identifies a single one of the execution plans from all other execution plans.

20. A computer readable medium having at least one physical media and encoded with a computer program code for constructing multiple alternative execution plans for a single database query, the medium having stored thereon data structure having a plurality of groups of alternative operators for carrying out the database query, at least some of the operators having pointers to one or more different ones of the groups, the data structure including:

a first data field including indicia representing locations of the operators within the data structure;

a second data field including rank data for each operator related to alternative operators in other of the groups; and

a third data field including a global rank based on the operator rank data for each query execution plan, the global rank uniquely identifying each execution plan relative to every other execution plan, the global rank data facilitating organization and validation of the multiple alternative execution plans.