US6807546B2 — Database system with methodology for distributing…

Claim 1

Independent Claim 129 words

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.

Claim 2

Dependent Claim 129 words

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.

Claim 3

Dependent Claim 17 words

The method of claim 1 , wherein said query requests data from a plurality of database tables.

Claim 4

Dependent Claim 17 words

The method of claim 2 , wherein said enumerating step includes enumerating a plurality of join strategies.

Claim 5

Dependent Claim 16 words

The method of claim 1 , wherein said enumerating step includes using a depth first search.

Claim 6

Dependent Claim 15 words

The method of claim 1 , wherein nodes of said search tree include join methods.

Claim 7

Dependent Claim 15 words

The method of claim 1 , wherein nodes of said search tree include available indexes.

Claim 8

Dependent Claim 17 words

The method of claim 1 , wherein nodes of said search tree include tables to be joined.

Claim 9

Dependent Claim 20 words

The method of claim 1 , wherein said selecting step includes selecting nodes in different portions of the search tree.

Claim 10

Dependent Claim 33 words

The method of claim 8 , wherein said selecting step includes adjusting the number of nodes of the search tree for evaluation when a complete plan for execution of the query is determined.

Claim 11

Dependent Claim 19 words

The method of claim 1 , wherein said evaluating step includes comparing estimated execution costs of the selected nodes.

Claim 12

Dependent Claim 19 words

The method of claim 1 , wherein said evaluating step includes evaluating nodes until a complete plan is determined.

Claim 13

Dependent Claim 22 words

The method of claim 1 , wherein said evaluating step includes evaluating nodes until the limited number of nodes have been evaluated.

Claim 14

Dependent Claim 35 words

The method of claim 1 , further comprising: 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.

Claim 15

Dependent Claim 14 words

A computer-readable medium having computer-executable instructions for performing the method of claim 1 .

Claim 16

Dependent Claim 14 words

A downloadable set of computer-executable instructions for performing the method of claim 1 .

Claim 17

Dependent Claim 107 words

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.

Claim 18

Dependent Claim 107 words

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.

Claim 19

Dependent Claim 17 words

The method of claim 16 , wherein the query requests data from a plurality of database tables.

Claim 20

Dependent Claim 21 words

The method of claim 17 , wherein the sub-plans include join methods for joining data from said plurality of database tables.

Claim 21

Dependent Claim 17 words

The method of claim 17 , wherein the sub-plans include indexes available for providing access to data.

Claim 22

Dependent Claim 15 words

The method of claim 16 , wherein said determining step includes using a depth-first search.

Claim 23

Dependent Claim 19 words

The method of claim 16 , wherein said quota comprises an upper limit on the sub-plans to be considered.

Claim 24

Dependent Claim 17 words

The method of claim 16 , wherein said quota is adjusted if an overall plan is determined.

Claim 25

Dependent Claim 19 words

The method of claim 22 , wherein said quota is reduced if the overall plan has favorable execution costs.

Claim 26

Dependent Claim 25 words

The method of claim 22 , wherein said quota is adjusted to equal a fixed fraction of the estimated execution costs of the overall plan.

Claim 27

Dependent Claim 28 words

The method of claim 16 , further comprising: distributing the quota over a search space comprising available sub-plans to consider sub-plans in various areas of the search space.

Claim 28

Dependent Claim 16 words

The method of claim 25 , wherein said quota is recursively distributed over the search space.

Claim 29

Dependent Claim 22 words

The method of claim 16 , further comprising: when quota is exhausted, selecting the most favorable overall plan that has been generated.

Claim 30

Dependent Claim 25 words

The method of claim 16 , further comprising: using the most favorable overall plan that is generated to provide data in response to the query.

Claim 31

Dependent Claim 29 words

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.

Claim 32

Dependent Claim 106 words

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.

Claim 33

Dependent Claim 106 words

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.

Claim 34

Dependent Claim 25 words

The method of claim 30 , wherein said alternative join strategies comprise a selected one of join method, available indexes, and tables to be joined.

Claim 35

Dependent Claim 22 words

The method of claim 30 , wherein said distributing step includes allocating sufficient quota to reach a leaf of said tree representation.

Claim 36

Dependent Claim 19 words

The method of claim 30 , wherein said distributing step includes distributing the quota recursively over the tree representation.

Claim 37

Dependent Claim 20 words

The method of claim 30 , wherein said quota is reduced if a plan having favorable execution costs is generated.

Claim 38

Dependent Claim 23 words

The method of claim 34 , wherein said quota is reduced to a fixed fraction of the estimated execution costs of a plan.

Claim 39

Dependent Claim 32 words

The method of claim 30 , further comprising: comparing a plan generated for execution of the query with a plan previously determined and retaining the plan having more favorable estimated execution costs.

Claim 40

Dependent Claim 28 words

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.

Claim 41

Dependent Claim 25 words

The method of claim 30 , further comprising: using the plan for creating a physical access plan for returning the data requested by the query.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2007-10-19	2008-04-19	2008-10-19	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2011-10-19	2012-04-19	2012-10-19	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2015-10-19	2016-04-19	2016-10-19	$7700.00	Window Closed / Lapsed

Database system with methodology for distributing query optimization effort over large search spaces

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag