Physical Planning of Database Queries Using Partial Solutions

• US 20150154256A1
• Filed: 10/24/2014
• Published: 06/04/2015
• 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.
• Granted Patent: US 10,628,417 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 for limiting the number of partial solutions considered for processing a query, the method comprising:

receiving a request for generating an execution plan for a database query;

determining a partial solutions limit on the number of partial solutions to be evaluated for determining the execution plan of the query;

determining a plurality of partial solutions, each partial solution corresponding to a portion of the execution plan for processing the database query, each partial solution determined by evaluating a number of candidate partial solutions, the number of candidate partial solutions determined based on the partial solutions limit;

combining the plurality of partial solutions to obtain an execution plan for the database query; 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 solutions processed for a goal; and

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

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

for each of the plurality of partial solutions;

identifying a set of candidate partial solutions; and

selecting a subset of the set of candidate partial solutions, the size of the subset determined based on the partial solutions limit.

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

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

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

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

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

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

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

determining a measure of complexity of the database query; and

determining the partial solutions limit based on the complexity of the query

7. The computer-implemented method of claim 6, wherein the partial solutions limit is determined based on a function that is inversely proportionate to the measure of complexity of the database query.

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

determining the measure of complexity of the database query based on an estimate of the number of feasible joins of the database query.

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

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

10. The computer-implemented method of claim 6, wherein the number of feasible joins of a database query is determined by join enumeration.

11. The computer-implemented method of claim 10, wherein the join enumeration is performed by performing an ordered traversal of 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.

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

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

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

15. The computer-implemented method of claim 12, further comprising:

determining cost measures of partial solutions 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.

16. The computer-implemented method of claim 12, 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 query.

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

maintaining a mapping from ranges of measures of query complexity to partial solution limits; and

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

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

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

maintaining a mapping from ranges of number of feasible joins of database queries to partial solution limits; and

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

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

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

receiving a request for generating an execution plan for a database query;

determining a partial solutions limit on the number of partial solutions to be evaluated for determining the execution plan of the query;

determining a plurality of partial solutions, each partial solution corresponding to a portion of the execution plan for processing the database query, each partial solution determined by evaluating a number of candidate partial solutions, the number of candidate partial solutions determined based on the partial solutions limit;

combining the plurality of partial solutions to obtain an execution plan for the database query; and

executing the database query by executing the execution plan.

20. A computer-implemented system for limiting the number of partial solutions considered for processing a query, the system comprising:

a computer processor; and

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

receiving a request for generating an execution plan for a database query;

determining a partial solutions limit on the number of partial solutions to be evaluated for determining the execution plan of the query;

determining a plurality of partial solutions, each partial solution corresponding to a portion of the execution plan for processing the database query, each partial solution determined by evaluating a number of candidate partial solutions, the number of candidate partial solutions determined based on the partial solutions limit;

combining the plurality of partial solutions to obtain an execution plan for the database query; and

executing the database query by executing the execution plan.