Database system with methodology for distributing query optimization effort over large search spaces
AssigneeSybase, Inc.
InventorMatthew Young-Lai
Life of this patent
Estimating the term…
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.
Claims38
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.
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.
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.
Dependencies are inferred from the claim text.