Validating multiple execution plans for database queries
First Claim
Patent Images
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 Assignments
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.
68 Citations
28 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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.- View Dependent Claims (8, 9, 10)
-
-
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. - View Dependent Claims (12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22)
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. - View Dependent Claims (25, 26)
-
-
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.
-
Specification