# US 10,628,417 B2 · Physical planning of database queries using partial solutions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,628,417 B2 - Document ID: US10628417B2 - Status: Granted - Kind: B2 - Application number: 14/522,876 - Filed: 2014-10-24 - Published: 2015-06-04 - Granted: 2020-04-21 - Earliest claimed: 2013-12-01 - Assignees: ParAccel LLC - Applicants: ParAccel LLC - Inventors: William J. McKenna; Richard L. Cole - Web page: https://patentgrep.com/patent/US10628417B2 ## CPC - G06F 16/24542: {Plan optimisation} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 3) 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. ### Claim 5 (depends on 3) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 9) 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. ### Claim 11 (depends on 8) 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. ### Claim 12 (depends on 8) 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. ### Claim 13 (depends on 1) 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. ### Claim 14 (depends on 1) 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. ### Claim 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 15) 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. ### Claim 19 (depends on 15) 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. ### Claim 20 (depends on 19) 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. ### Claim 21 (depends on 20) 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. ### Claim 22 (depends on 19) 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. ### Claim 23 (depends on 19) 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. ### Claim 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. ### Claim 25 (depends on 16) 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.