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.
83 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)
-
-
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)
-
-
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)
-
Specification