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

• US 6,807,546 B2
• Filed: 05/08/2003
• Issued: 10/19/2004
• Est. Priority Date: 08/12/2002
• Status: Active Grant

• Current Assignee: iAnywhere Solutions Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Young-Lai, Matthew
• Primary Examiner(s): Mizrahi, Diane D
• Application Number:
  US10/249,791
• Publication Number:
  US 20040030677A1
• Time in Patent Office: 530 Days
• Field of Search: 707/3, 707/2, 707/100, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

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.

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

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

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

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

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

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

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

9. 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.

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

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

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

13. 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.

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.

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

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

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

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

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

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

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

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

25. 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.

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.

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

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

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

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

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

36. 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.

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.