Validating multiple execution plans for database queries
First Claim
Patent Images
1. A computer-executable medium having computer-executable instructions for validation by a programmed digital computer, the computer-executable instructions performing:
- 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.
1 Assignment
0 Petitions
Accused Products
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.
45 Citations
3 Claims
-
1. A computer-executable medium having computer-executable instructions for validation by a programmed digital computer, the computer-executable instructions performing:
-
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. - View Dependent Claims (2, 3)
-
Specification