Database system with methodology for distributing query optimization effort over large search spaces
First Claim
1. In a database system, a method for optimization of a query, the method comprising:
- receiving a query requesting data from a database;
enumerating a plurality of plans which can be used for obtaining data requested by the query;
creating a search tree based on said plurality of plans, the search tree having nodes representing segments of said plurality of plans;
selecting a limited number of nodes of the search tree for evaluation to limit effort spent on query optimization; and
generating a complete plan for execution of the query by performing the substeps of;
evaluating the selected nodes of the search tree; and
if the evaluation determines that a given node is more favorable than comparable nodes previously evaluated, retaining the given node as part of the complete plan.
2 Assignments
0 Petitions
Accused Products
Abstract
In a database system, a method for optimization of a query is described. When a query is received which requests data from a database, a plurality of plans which can be used for obtaining data requested by the query are enumerated. A search tree is created based upon these plans, with nodes of the search tree representing segments of the plans. A limited number of nodes of the search tree are selected for evaluation to limit the effort spent on query optimization. A complete plan for execution of the query is generated by evaluating the selected nodes of the search tree and, if the evaluation determines that a given node is more favorable than comparable nodes previously evaluated, retaining the given node as part of the complete plan.
-
Citations
38 Claims
-
1. In a database system, a method for optimization of a query, the method comprising:
-
receiving a query requesting data from a database;
enumerating a plurality of plans which can be used for obtaining data requested by the query;
creating a search tree based on said plurality of plans, the search tree having nodes representing segments of said plurality of plans;
selecting a limited number of nodes of the search tree for evaluation to limit effort spent on query optimization; and
generating a complete plan for execution of the query by performing the substeps of;
evaluating the selected nodes of the search tree; and
if the evaluation determines that a given node is more favorable than comparable nodes previously evaluated, retaining the given node as part of the complete plan. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
comparing a complete plan generated for execution of the query with a complete plan previously determined and retaining the complete plan having more favorable estimated execution costs.
-
-
14. A computer-readable medium having computer-executable instructions for performing the method of claim 1.
-
15. A downloadable set of computer-executable instructions for performing the method of claim 1.
-
16. In a database system, a method for optimizing execution of a query, the method comprising:
-
receiving a query requesting data from a database;
determining available sub-plans for obtaining data requested by the query, each sub-plan comprising a portion of an overall plan for obtaining the requested data;
selecting a quota, said quota comprising a limitation on the sub-plans to be considered for purposes of generating the overall plan;
while quota is available, generating the overall plan by performing the substeps of;
estimating execution costs of available sub-plans;
retaining sub-plans having lower estimated execution costs than other sub-plans; and
forming an overall plan based on the retained sub-plans. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
distributing the quota over a search space comprising available sub-plans to consider sub-plans in various areas of the search space.
-
-
26. The method of claim 25, wherein said quota is recursively distributed over the search space.
-
27. The method of claim 16, further comprising:
when quota is exhausted, selecting the most favorable overall plan that has been generated.
-
28. The method of claim 16, further comprising:
using the most favorable overall plan that is generated to provide data in response to the query.
-
29. The method of claim 16, further comprising:
using the overall plan for creating a physical access plan for obtaining the data requested by the query from the database.
-
30. In a database system, a method for join enumeration, the method comprising:
-
receiving a request for data from a plurality of database tables;
enumerating alternative join strategies for obtaining the requested data;
creating a tree representation of said alternative join strategies;
selecting a quota comprising a number of said alternative join strategies to be considered for obtaining the requested data;
distributing the quota over the tree representation to select alternative join strategies in various areas of the tree representation; and
generating a plan for obtaining the requested data based on comparing the selected alternative join strategies and using alternative join strategies having more favorable execution costs. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38)
comparing a plan generated for execution of the query with a plan previously determined and retaining the plan having more favorable estimated execution costs.
-
-
37. The method of claim 36, further comprising:
when the quota is exhausted, using the plan that has been retained for obtaining the data requested by the query.
-
38. The method of claim 30, further comprising:
using the plan for creating a physical access plan for returning the data requested by the query.
Specification