Patent US6598044B1 successfully refreshed from Google Patents.
US6598044B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for choosing optimal query execution plan for multiple defined equivalent query expressions
Assignee: Microsoft Technology Licensing LLC
•
Filing: 2002-06-25
•
Granted: 2003-07-22
•
Expires: 2022-06-25
Abstract
Abstract A query formulates choices of multiple equivalent forms. A choice is represented by a CHOOSE operator having multiple arguments representing the equivalent forms. A lookup table is generated to include a group for each node other than CHOOSE arguments. For CHOOSE arguments, the generated table includes a single equivalence group having all choose arguments as members. The enumeration algorithm of the optimizer is applied to generate additional members and/or groups, whereby for each group, every member thereof is an equivalent. A cost value is assigned to each member of each group and a member of each group is selected as a lowest cost value member. The lowest cost value members of the groups define an optimized tree and optimization of the query.
Inventors
- 👤 Florian Waas
- 👤 Cesar Galindo-Legaria
- 👤 Goetz Graefe
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:36
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
313 words
A method of optimizing a query including therein at least one choice of at least a pair of equivalent forms, the query comprising operators and arguments relating to the operators, each choice being represented by a CHOOSE operator having at least a pair of CHOOSE arguments representing the corresponding pair of equivalent forms, an initial tree representation of the query including a node for each operator and each argument, each argument relating to an operator being represented in the tree as a child node of the node representing such operator, the method comprising: generating an initial version of a lookup table, the generated lookup table including a group for each node of the initial tree other than the nodes for each CHOOSE operator and the CHOOSE arguments thereof, the generated lookup table including with regard to each CHOOSE operator node and the CHOOSE argument nodes thereof a single group having both CHOOSE argument nodes as members thereof, each operator being represented as a member within a group thereof as the operator and a reference to a group of each argument associated therewith; generating any available equivalents for each group based on the initial version of the table, including generating at least one of: an additional member of a group; a new member of a new group; and combinations thereof; whereby for each group, every member thereof is an equivalent; and assigning a cost value to each member of each group and selecting a member of each group as a lowest cost value member of the group, the assigned cost value of each member reflecting a cost of such member and if the member implies one or more other groups a cost of the lowest cost value member of each implied group, the lowest cost value members of the groups defining an optimized tree for the query and thereby an optimization of the query.
Claim 2
Independent Claim
313 words
A method of optimizing a query including therein at least one choice of at least a pair of equivalent forms, the query comprising operators and arguments relating to the operators, each choice being represented by a CHOOSE operator having at least a pair of CHOOSE arguments representing the corresponding pair of equivalent forms, an initial tree representation of the query including a node for each operator and each argument, each argument relating to an operator being represented in the tree as a child node of the node representing such operator, the method comprising: generating an initial version of a lookup table, the generated lookup table including a group for each node of the initial tree other than the nodes for each CHOOSE operator and the CHOOSE arguments thereof, the generated lookup table including with regard to each CHOOSE operator node and the CHOOSE argument nodes thereof a single group having both CHOOSE argument nodes as members thereof, each operator being represented as a member within a group thereof as the operator and a reference to a group of each argument associated therewith; generating any available equivalents for each group based on the initial version of the table, including generating at least one of: an additional member of a group; a new member of a new group; and combinations thereof; whereby for each group, every member thereof is an equivalent; and assigning a cost value to each member of each group and selecting a member of each group as a lowest cost value member of the group, the assigned cost value of each member reflecting a cost of such member and if the member implies one or more other groups a cost of the lowest cost value member of each implied group, the lowest cost value members of the groups defining an optimized tree for the query and thereby an optimization of the query.
Claim 3
Dependent Claim
17 words
The method of claim 1 further comprising executing the optimization of the query to produce query results.
Claim 4
Dependent Claim
72 words
The method of claim 1 wherein generating the initial version of the table comprises with regard to each CHOOSE operator node in the tree: determining the CHOOSE argument nodes of the CHOOSE operator node; defining a group in the table to include the determined CHOOSE argument nodes; and adjusting any other group that would refer to the CHOOSE operator to instead refer to the defined group with the determined CHOOSE argument nodes.
Claim 5
Dependent Claim
318 words
A computer-readable medium having computer-executable instructions thereon for performing a method of optimizing a query including therein at least one choice of a pair of equivalent forms, the query comprising operators and arguments relating to the operators, each choice being represented by a CHOOSE operator having a pair of CHOOSE arguments representing the corresponding pair of equivalent forms, an initial tree representation of the query including a node for each operator and each argument, each argument relating to an operator being represented in the tree as a child node of the node representing such operator, the method comprising: generating an initial version of a lookup table, the generated lookup table including a group for each node of the initial tree other than the nodes for each CHOOSE operator and the CHOOSE arguments thereof, the generated lookup table including with regard to each CHOOSE operator node and the CHOOSE argument nodes thereof a single group having both CHOOSE argument nodes as members thereof, each operator being represented as a member within a group thereof as the operator and a reference to a group of each argument associated therewith; generating any available equivalents for each group based on the initial version of the table, including generating at least one of: an additional member of a group; a new member of a new group; and combinations thereof; whereby for each group, every member thereof is an equivalent; and assigning a cost value to each member of each group and selecting a member of each group as a lowest cost value member of the group, the assigned cost value of each member reflecting a cost of such member and if the member implies one or more other groups a cost of the lowest cost value member of each implied group, the lowest cost value members of the groups defining an optimized tree for the query and thereby an optimization of the query.
Claim 6
Dependent Claim
318 words
A computer-readable medium having computer-executable instructions thereon for performing a method of optimizing a query including therein at least one choice of a pair of equivalent forms, the query comprising operators and arguments relating to the operators, each choice being represented by a CHOOSE operator having a pair of CHOOSE arguments representing the corresponding pair of equivalent forms, an initial tree representation of the query including a node for each operator and each argument, each argument relating to an operator being represented in the tree as a child node of the node representing such operator, the method comprising: generating an initial version of a lookup table, the generated lookup table including a group for each node of the initial tree other than the nodes for each CHOOSE operator and the CHOOSE arguments thereof, the generated lookup table including with regard to each CHOOSE operator node and the CHOOSE argument nodes thereof a single group having both CHOOSE argument nodes as members thereof, each operator being represented as a member within a group thereof as the operator and a reference to a group of each argument associated therewith; generating any available equivalents for each group based on the initial version of the table, including generating at least one of: an additional member of a group; a new member of a new group; and combinations thereof; whereby for each group, every member thereof is an equivalent; and assigning a cost value to each member of each group and selecting a member of each group as a lowest cost value member of the group, the assigned cost value of each member reflecting a cost of such member and if the member implies one or more other groups a cost of the lowest cost value member of each implied group, the lowest cost value members of the groups defining an optimized tree for the query and thereby an optimization of the query.
Claim 7
Dependent Claim
20 words
The medium of claim 4 wherein the method further comprises executing the optimization of the query to produce query results.
Claim 8
Dependent Claim
72 words
The medium of claim 4 wherein generating the initial version of the table comprises with regard to each CHOOSE operator node in the tree: determining the CHOOSE argument nodes of the CHOOSE operator node; defining a group in the table to include the determined CHOOSE argument nodes; and adjusting any other group that would refer to the CHOOSE operator to instead refer to the defined group with the determined CHOOSE argument nodes.
Claim 9
Dependent Claim
312 words
A computer performing a method of optimizing a query including therein at least one choice of a pair of equivalent forms, the query comprising operators and arguments relating to the operators, each choice being represented by a CHOOSE operator having a pair of CHOOSE arguments representing the corresponding pair of equivalent forms, an initial tree representation of the query including a node for each operator and each argument, each argument relating to an operator being represented in the tree as a child node of the node representing such operator, the method comprising: generating an initial version of a lookup table, the generated lookup table including a group for each node of the initial tree other than the nodes for each CHOOSE operator and the CHOOSE arguments thereof, the generated lookup table including with regard to each CHOOSE operator node and the CHOOSE argument nodes thereof a single group having both CHOOSE argument nodes as members thereof, each operator being represented as a member within a group thereof as the operator and a reference to a group of each argument associated therewith; generating any available equivalents for each group based on the initial version of the table, including generating at least one of: an additional member of a group; a new member of a new group; and combinations thereof; whereby for each group, every member thereof is an equivalent; and assigning a cost value to each member of each group and selecting a member of each group as a lowest cost value member of the group, the assigned cost value of each member reflecting a cost of such member and if the member implies one or more other groups a cost of the lowest cost value member of each implied group, the lowest cost value members of the groups defining an optimized tree for the query and thereby an optimization of the query.
Claim 10
Dependent Claim
312 words
A computer performing a method of optimizing a query including therein at least one choice of a pair of equivalent forms, the query comprising operators and arguments relating to the operators, each choice being represented by a CHOOSE operator having a pair of CHOOSE arguments representing the corresponding pair of equivalent forms, an initial tree representation of the query including a node for each operator and each argument, each argument relating to an operator being represented in the tree as a child node of the node representing such operator, the method comprising: generating an initial version of a lookup table, the generated lookup table including a group for each node of the initial tree other than the nodes for each CHOOSE operator and the CHOOSE arguments thereof, the generated lookup table including with regard to each CHOOSE operator node and the CHOOSE argument nodes thereof a single group having both CHOOSE argument nodes as members thereof, each operator being represented as a member within a group thereof as the operator and a reference to a group of each argument associated therewith; generating any available equivalents for each group based on the initial version of the table, including generating at least one of: an additional member of a group; a new member of a new group; and combinations thereof; whereby for each group, every member thereof is an equivalent; and assigning a cost value to each member of each group and selecting a member of each group as a lowest cost value member of the group, the assigned cost value of each member reflecting a cost of such member and if the member implies one or more other groups a cost of the lowest cost value member of each implied group, the lowest cost value members of the groups defining an optimized tree for the query and thereby an optimization of the query.
Claim 11
Dependent Claim
20 words
The computer of claim 7 wherein the method further comprises executing the optimization of the query to produce query results.
Claim 12
Dependent Claim
72 words
The computer of claim 7 wherein generating the initial version of the table comprises with regard to each CHOOSE operator node in the tree: determining the CHOOSE argument nodes of the CHOOSE operator node; defining a group in the table to include the determined CHOOSE argument nodes; and adjusting any other group that would refer to the CHOOSE operator to instead refer to the defined group with the determined CHOOSE argument nodes.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-07-21 | 2007-01-20 | 2007-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-07-21 | 2011-01-20 | 2011-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-07-21 | 2015-01-20 | 2015-07-22 | $7700.00 | Window Closed / Lapsed |