Validating multiple execution plans for database queries
AssigneeMicrosoft Corporation
InventorsCesar A. Galindo-Legaria, Florian Waas
Life of this patent
Estimating the term…
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.
Claims38
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.