System and methodology for cost-based subquery optimization using a left-deep tree join enumeration algorithm

• US 20040220923A1
• Filed: 04/28/2004
• Published: 11/04/2004
• Est. Priority Date: 06/29/2002
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Nica, Anisoara
• Granted Patent: US 7,617,179 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A system providing methodology for cost-based enumeration of subqueries using a left-deep tree join enumeration algorithm is described. In one embodiment, for example, in a database system, a method of the present invention is described for optimizing a database query, the method comprises steps of: receiving a database query including at least one subquery; building a query optimization graph for each query block of the database query, the query optimization graph including plan nodes representing subqueries of each query block; generating a set of access methods and join methods for each plan node, including generating at least one access method for a subquery quantifier based on subquery type and semantic properties of the database query; determining an optimal access plan for each query block based upon selecting access methods, join methods, and join order for plan nodes of the query optimization graph having favorable execution costs; and constructing a detailed access plan for execution of the database query based upon the optimal access plan determined for each query block.

Claims

1. In a database system, a method for optimizing a database query, the method comprising:

receiving a database query including at least one subquery;

building a query optimization graph for each query block of the database query, the query optimization graph including plan nodes representing subqueries of each query block;

generating a set of access methods and join methods for each plan node, including generating at least one access method for a subquery quantifier based on subquery type and semantic properties of the database query;

determining an optimal access plan for each query block based upon selecting access methods, join methods, and join order for plan nodes of said query optimization graph having favorable execution costs; and

constructing a detailed access plan for execution of the database query based upon the optimal access plan determined for each query block.

2. The method of claim 1, wherein said building step includes identifying each query block in the database query.

3. The method of claim 1, wherein said building step includes building a query optimization graph including plan nodes representing subplans and quantifiers of each query block.

4. The method of claim 1, wherein said generating step includes costing each access method and join method.

5. The method of claim 1, wherein said determining step includes starting with most nested plan nodes.

6. The method of claim 1, wherein said step of generating at least one access method for a subquery includes computing a property vector for said at least one access method.

7. The method of claim 6, wherein said step of computing a property vector includes computing a property vector of an access method by optimizing the subquery'"'"'s Derived Table Block (DTB) specifically for that access method without transforming the DTB for a subquery execution strategy corresponding to that access method.

8. The method of claim 1, wherein said step of generating at least one access method includes generating an access method based on subquery execution strategies appropriate for subquery type and semantic properties of the database query.

9. The method of claim 1, wherein said step of generating at least one access method includes generating an uncorrelated derived table with hash filters access method for a qualifying subquery.

10. The method of claim 1, wherein said step of generating at least one access method includes generating an access method corresponding to evaluation of a subquery in the subquery'"'"'s original form.

11. The method of claim 1, wherein said step of generating at least one access method includes generating an access method using an aggregate and then join subquery execution strategy for a qualifying subquery.

12. The method of claim 1, wherein said step of generating at least one access method includes generating an access method using a filter, aggregate and then join subquery execution strategy for a qualifying subquery.

13. The method of claim 1, wherein said determining step includes evaluating execution costs of a candidate plan segment to be added to an access plan being constructed.

14. The method of claim 13, wherein said candidate plan segment comprises a selected plan node together with an access method and a join method generated for the selected plan node.

15. The method of claim 14, wherein said determining step includes evaluating execution costs of partial access plans enabling earlier pruning of unfavorable access plans.

16. The method of claim 1, wherein said determining step includes substeps of:

placing a candidate plan segment in a next position in an access plan being constructed, the candidate plan segment comprising a plan node, access method and join method valid at the next position; and

evaluating the access plan including the candidate plan segment.

17. The method of claim 16, wherein said determining step further comprises substeps of:

if the access plan is less favorable than an access plan previously identified, replacing the candidate plan segment with another available candidate plan segment and repeating said evaluating substep.

18. The method of claim 16, wherein said determining step further comprises substeps of:

if the access plan is more favorable than an access plan previously identified but is not a complete plan, placing an additional candidate plan segment in a next position of the access plan; and

repeating said evaluating substep.

19. The method of claim 16, wherein said determining step further comprises substeps of:

if the access plan is more favorable than an access plan previously identified and is a complete plan, considering alternative plans by repeating the placing and evaluating substeps until all alternatives are considered.

20. The method of claim 16, wherein said determining step further comprises substeps of:

if the access plan is more favorable than an access plan previously identified and is a complete plan, considering alternative access plans by repeating the placing and evaluating substeps until reaching a pre-selected limitation on consideration of alternative access plans.

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

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