Physical planning of database queries using partial solutions

• US 10,628,417 B2
• Filed: 10/24/2014
• Issued: 04/21/2020
• Est. Priority Date: 12/01/2013
• Status: Active Grant

• Current Assignee: Paraccel Incorporated (Actian Corporation)
• Original Assignee: Paraccel Incorporated (Actian Corporation)
• Inventors: McKenna, William J., Cole, Richard L.
• Primary Examiner(s): Singh, Amresh
• Application Number:
  US14/522,876
• Publication Number:
  US 20150154256A1
• Time in Patent Office: 2,006 Days
• Field of Search: 707718, 707803, 707722, 707759, 382305, 714 49, 705 5
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A database system determines execution plans for database queries by evaluating a number of partial solutions for each database query. The database system determines a partial solutions limit on the number of partial solutions to be evaluated for determining the execution plan of the query. The database system determines a plurality of partial solutions, each partial solution corresponding to a portion of the execution plan for processing the database query. The database system evaluates a number of candidate partial solutions for determining a partial solution. The number of candidate partial solutions evaluated is determined based on the partial solutions limit. The database system combines the plurality of partial solutions to obtain an execution plan for the database query. The database system executes the database query by executing the execution plan.

Claims

1. A computer-implemented method of physical planning of database queries, comprising:

receiving a database query including a plurality of portions;

receiving a request for generating an execution plan for the database query including the plurality of portions;

generating the execution plan for execution of the database query, comprising;

identifying the plurality of portions of the database query, wherein each portion of the database query is associated with one or more partial execution plans, each partial execution plan represents an execution plan for the portion of the database query and comprises one or more physical operators, and wherein each physical operator implements a database operation for producing an output data set from one or more input data sets;

determining a threshold number of partial execution plans for the database query based on a measure of complexity of the database query, the measure of complexity of the query representing an estimate of a number of feasible joins of the database query, the estimate determined based on at least one of;

(1) a structure of the database query or (2) a join enumeration performed using an ordered traversal of a graph representation of the database query, the threshold number limiting a number of candidate partial execution plans evaluated to determine a partial execution plan for each portion of the database query, the threshold number determined to be a value inversely proportionate to the measure of complexity of the database query;

determining a plurality of partial execution plans for execution of the database query by evaluating the number of candidate partial execution plans for each portion of the database query, each partial execution plan corresponding to a portion of the database query; and

combining the plurality of partial execution plans to generate the execution plan;

and

executing the database query by executing the execution plan.

2. The computer-implemented method of claim 1, further comprising:

maintaining an estimate of cost based on partial execution plans processed for a goal; and

responsive to encountering a new partial execution plan having a cost greater than a cost of a partial execution plan previously processed for the goal, determining not to process the new partial execution plan.

3. The computer-implemented method of claim 1, wherein determining the plurality of partial execution plans comprises:

for each of the plurality of partial execution plans;

identifying a set of candidate partial execution plans; and

selecting a subset of the set of candidate partial execution plans, the size of the subset determined based on the threshold number.

4. The computer-implemented method of claim 3, wherein selecting a subset of the set of candidate partial execution plans comprises:

ranking the set of candidate partial execution plans based on a cost estimate for each candidate partial execution plans; and

selecting a subset of highest ranked candidate partial execution plans from the set of partial execution plans.

5. The computer-implemented method of claim 3, wherein selecting a subset of the set of candidate partial execution plans comprises:

ranking the set of partial execution plans based on a cost estimate for each candidate partial execution plans; and

selecting a plurality of subsets of partial execution plans from the set of partial execution plans, each subset corresponding to a physical operator wherein each subset comprises the highest ranked partial execution plans corresponding to the physical operator.

6. The computer-implemented method of claim 1, further comprising:

determining the measure of complexity of the database query to be higher for database queries with higher number of feasible joins.

7. The computer-implemented method of claim 1, wherein the graph representation of the database query comprises a join graph of the database query, wherein the join graph of the database query comprises nodes corresponding to tables of the database query and edges corresponding to pairs of tables, each pair corresponding to tables joined by the database query.

8. The computer-implemented method of claim 1, further comprising:

maintaining a goal comprising a logical expression from the database query and a cost bound for the goal.

9. The computer-implemented method of claim 8, wherein the goal further comprises one or more constraints, wherein the sub-goals are selected so as to satisfy the constraints of the goal.

10. The computer-implemented method of claim 9, wherein a constraint specifies a distribution of data across a plurality of processors for a table processed by the database query or an intermediate result generated by the database query.

11. The computer-implemented method of claim 8, further comprising:

determining cost measures of partial execution plans corresponding to sub-goals for the goal; and

eliminating a sub-goal responsive to determining that the sum of cost measures of the sub-goals determined so far exceeds the cost bound of the goal.

12. The computer-implemented method of claim 8, wherein the goal further comprises one or more physical properties of data sets processed by the database query, the data sets comprising one of a table processed by the goal, an intermediate result, or a result returned by the database query.

13. The computer-implemented method of claim 1, further comprising:

maintaining a mapping from ranges of measures of query complexity to threshold numbers; and

determining a measure of query complexity for a new database query; and

determining the threshold number for the database query by selecting the value of limit from the range corresponding to the measure of query complexity for the new database query.

14. The computer-implemented method of claim 1, further comprising:

maintaining a mapping from ranges of number of feasible joins of database queries to threshold numbers; and

determining a number of feasible joins for a new database query; and

determining the threshold number for the database query by selecting the value of threshold number from the range corresponding to the number of feasible joins for the new database query.

15. A non-transitory computer readable storage medium storing instructions thereon, the instructions comprising, instructions for:

receiving a database query including a plurality of portions;

receiving a request for generating an execution plan for the database query including the plurality of portions;

generating the execution plan for execution of the database query, comprising;

identifying the plurality of portions of the database query, wherein each portion of the database query is associated with one or more partial execution plans, each partial execution plan represents an execution plan for the portion of the database query and comprises one or more physical operators, and wherein each physical operator implements a database operation for producing an output data set from one or more input data sets;

determining a threshold number of partial execution plans for the database query based on a measure of complexity of the database query, the measure of complexity of the query representing an estimate of a number of feasible joins of the database query, the estimate determined based on at least one of;

(1) a structure of the database query or (2) a join enumeration performed using an ordered traversal of a graph representation of the database query, the threshold number limiting a number of candidate partial execution plans evaluated to determine a partial execution plan for each portion of the database query, the threshold number determined to be a value inversely proportionate to the measure of complexity of the database query;

determining a plurality of partial execution plans for execution of the database query by evaluating the number of candidate partial execution plans for each portion of the database query, each partial execution plan corresponding to a portion of the database query; and

combining the plurality of partial execution plans to generate the execution plan;

and

executing the database query by executing the execution plan.

16. The non-transitory computer readable storage medium of claim 15, wherein instructions for determining the plurality of partial execution plans comprise instructions for:

for each of the plurality of partial execution plans;

identifying a set of candidate partial execution plans; and

selecting a subset of the set of candidate partial execution plans, the size of the subset determined based on the threshold number.

17. The non-transitory computer readable storage medium of claim 15, wherein the stored instructions further comprise instructions for:

determining the measure of complexity of the database query.

18. The non-transitory computer readable storage medium of claim 15, wherein the stored instructions further comprise instructions for:

maintaining a mapping from ranges of measures of query complexity to threshold numbers; and

determining a measure of query complexity for a new database query; and

determining the threshold number for the database query by selecting the value of limit from the range corresponding to the measure of query complexity for the new database query.

19. The non-transitory computer readable storage medium of claim 15, wherein the stored instructions further comprise instructions for:

maintaining a goal comprising a logical expression from the database query and a cost bound for the goal.

20. The non-transitory computer readable storage medium of claim 19, wherein the goal further comprises one or more constraints, wherein the sub-goals are selected so as to satisfy the constraints of the goal.

21. The non-transitory computer readable storage medium of claim 20, wherein a constraint specifies a distribution of data across a plurality of processors for a table processed by the database query or an intermediate result generated by the database query.

22. The non-transitory computer readable storage medium of claim 19, further comprising:

determining cost measures of partial execution plans corresponding to sub-goals for the goal; and

eliminating a sub-goal responsive to determining that the sum of cost measures of the sub-goals determined so far exceeds the cost bound of the goal.

23. The non-transitory computer readable storage medium of claim 19, wherein the goal further comprises one or more physical properties of data sets processed by the database query, the data sets comprising one of a table processed by the goal, an intermediate result, or a result returned by the database query.

25. The non-transitory computer readable storage medium of claim 16, wherein instructions for selecting a subset of the set of candidate execution plans comprise instructions for:

ranking the set of candidate partial execution plans based on a cost estimate for each candidate partial execution plans; and

selecting a plurality of subsets of partial execution plans from the set of partial execution plans, each subset corresponding to a physical operator wherein each subset comprises the highest ranked partial execution plans corresponding to the physical operator.

24. A computer-implemented system for physical planning of database queries, the system comprising:

a computer processor; and

a non-transitory computer-readable storage medium storing instructions thereon, the instructions comprising;

receiving a database query including a plurality of portions;

receiving a request for generating an execution plan for the database query including the plurality of portions;

generating the execution plan for execution of the database query, comprising;

identifying the plurality of portions of the database query, wherein each portion of the database query is associated with one or more partial execution plans, each partial execution plan represents an execution plan for the portion of the database query and comprises one or more physical operators, and wherein each physical operator implements a database operation for producing an output data set from one or more input data sets;

determining a threshold number of partial execution plans for the database query based on a measure of complexity of the database query, the measure of complexity of the query representing an estimate of a number of feasible joins of the database query, the estimate determined based on at least one of;

(1) a structure of the database query or (2) a join enumeration performed using an ordered traversal of a graph representation of the database query, the threshold number limiting a number of candidate partial execution plans evaluated to determine a partial execution plan for each portion of the database query, the threshold number determined to be a value inversely proportionate to the measure of complexity of the database query;

determining a plurality of partial execution plans for execution of the database query by evaluating the number of candidate partial execution plans for each portion of the database query, each partial execution plan corresponding to a portion of the database query; and

combining the plurality of partial execution plans to generate the execution plan;

and

executing the database query by executing the execution plan.