Validating multiple execution plans for database queries

• US 20040167891A1
• Filed: 02/24/2004
• Published: 08/26/2004
• Est. Priority Date: 03/31/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Waas, Florian
• Granted Patent: US 7,010,524 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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.

2. A medium bearing representations of instructions and data for causing a suitably programmed computer to perform the method of claim 1.

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

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

5. The method of claim 4 further comprising producing a global rank for at least one of the alternative execution programs from the rank data.

6. The method of claim 5 where the global rank uniquely identifies the one execution plans from all of the other alternative execution plans.

7. The method of claim 6 where the ranks of all alternative execution plans are dense.

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

organizing the alternative plans into a plurality of groups at least some of which include multiple operators associated with operators in the 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;

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

9. A medium bearing representations of instructions and data for causing a suitably programmed computer to perform the method of claim 8.

10. The method of claim 8 where one of the groups is a root group.

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

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

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

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

15. The method of claim 8 wherein unranking one of the global rank designations comprises:

receiving a representation of the one global rank designations;

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

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

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

17. The method of claim 15 where the received one global rank designation is randomly selected from a collection of global rank designations.

18. A method 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 step until reaching those of the operators not having pointers to another one of the groups,

repeating the above steps, selecting at least one different operator for each of the constructed plans.

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

20. The method of claim 19 where the directory includes a rank for each operator representing a number of alternative plans associated with that operator.

21. The method of claim 20 further including adjusting the rank of one of the selected operators after it has been selected.

22. The method of claim 19 where the directory includes a rank for each group representing a number of alternative plans associated with that group.

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

24. The method of claim 23 where the respective operators are selected such that the global rank designation uniquely identifies a single one of the alternative execution plans.

25. The method of claim 23 where the specification contains a plurality of global rank designations.

26. The method of claim 25 further comprising deriving the plurality of global rank designations from the specification.

27. The method of claim 18 where the operators and pointers form a tree structure.

28. The method of claim 27 where each operator is selected in each repetition in a manner such that all of the possible alternative plans has approximately the same probability of being unranked.

29. The method of claim 27 where the probability of selecting each operator in each group is related to the number of operators in the subtree of the each operator.

30. A medium bearing representations of instructions and data for causing a suitably programmed computer to perform the method 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 step until reaching those of the operators not having pointers to another one of the groups,

repeating the above steps, selecting at least one different operator for each of the constructed plans.

31. The method of claim 30 where the medium is a storage medium.

32. The method of claim 30 where the medium is a signal transmitted on a network of computers.

33. A system for validating multiple alternative execution plans for a single database query, comprising:

a search engine responsive to the query for constructing a data structure containing a plurality of groups each including a number of alternative operators, at least some of the operators having pointers to one or more different ones of the groups;

a ranking module for ranking the operators in the groups and for unranking them so as to construct a plurality of different execution plans for the query;

a validation module for validating the execution plans from the ranking module.

34. The system of claim 33 where the data structure is a table.

35. The system of claim 33 further including a specification for specifying a number of different plans to be constructed.

36. The system of claim 33 further including a directory containing locations of the groups and operators within the data structure containing the groups.

38. The directory of claim 36 where the directory includes rank data for each group representing a number of alternative plans associated with that group.

37. A directory for a data structure having a plurality of groups of alternative operators for carrying out a database query, at least some of the operators having pointers to one or more different ones of the groups, the directory including

indicia representing locations of the operators within the data structure;

rank data for each operator representing a number of alternative plans associated with that operator.