OPTIMIZATION OF PARALLELIZATION OF USER-DEFINED FUNCTIONS WITH FLEXIBLE PARTITIONING

• US 20150379077A1
• Filed: 06/26/2014
• Published: 12/31/2015
• Est. Priority Date: 06/26/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Grosse, Philipp, Lehner, Wolfgang, May, Norman
• Granted Patent: US 9,454,571 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Technologies are disclosed for generating query execution plans optimized for parallel execution for programs having both core database relational functions and user-defined functions. A variety of optimization strategies can be employed to improve performance in a parallel execution scenarios. A flexible range of permitted partition arrangements can be specified as acceptable to parallelized instances of the user-defined function. The optimizer can leverage such information when constructing an optimized query execution plan. Partitioning arrangements or other properties can be leveraged to avoid additional or unnecessary processing.

Claims

1. A query execution plan optimization system comprising:

one or more processors;

memory coupled to the one or more processors;

a stored representation of a software program, wherein the representation of the software program comprises both one or more user-defined functions and one or more other operations, and the representation of the software program indicates at least one property for a user-defined function out of the user-defined functions and at least one property for an operation out of the other operations, wherein the operation comprises another user-defined function or a core relational database operation; and

an optimizer configured to transform the representation of the software program into an optimized query execution plan optimized for parallel execution according to the user-defined function property and the operation property.

2. The query execution plan optimization system of claim 1 wherein:

the user-defined function property comprises a permitted range of partition arrangements as an input pre-condition when the user-defined function is executed in parallel; and

the optimizer considers a plurality of partition arrangements in the range.

3. The optimization system of claim 2 wherein:

the optimizer is configured to leverage partitioning already performed when within the permitted range of partition arrangements.

4. The optimization system of claim 1 wherein:

the operation property comprises a global structural property comprising a post-condition partition arrangement of an output of the operation;

the user-defined function property comprises a global structural property comprising an expected pre-condition partition arrangement for an input of the user-defined function when the user-defined function is executed in parallel; and

the optimizer is configured to introduce an exchange operation at a detected property mismatch at an input-output coupling in the stored representation of the software program.

5. The optimization system of claim 1 wherein:

the optimizer supports optimization over of a range of pre-condition properties.

6. The optimization system of claim 1 wherein:

the stored representation of the software program represents a full merge and initial partitioning operation; and

the optimizer is configured to rewrite the full merge and initial partitioning operation into one or more rewritten operations.

7. The optimization system of claim 6 wherein:

the full merge and initial partitioning operation of the stored representation of the query execution plan appears between a first operation with an output having an output property and a second operation with an input having an input property and coupled to the output of the first operation, wherein the input property specifies a range of permitted partition arrangements; and

the one or more rewritten operations are selected based on the output property and the input property.

8. The optimization system of claim 1 wherein:

the optimizer selects from a plurality of alternative re-writes based on number of cores, number of nodes, processing cost, and processing size.

9. The optimization system of claim 1 wherein:

the optimizer implements a cost-based decision making process to choose a degree of parallelism.

10. The optimization system of claim 1 wherein:

the stored representation specifies a merge technique for parallelized instances of the user-defined function; and

the optimizer is configured to apply the merge technique when generating the optimized query execution plan optimized for parallel execution.

11. The optimization system of claim 10 wherein:

the merge technique comprises user-defined merge operations; and

the optimizer applies the user-defined merge operations when generating the optimized query execution plan optimized for parallel execution.

12. The optimization system of claim 1 wherein:

the stored representation indicates an expected sorting condition for input to parallelized instances of the user-defined function; and

the optimizer is configured to enforce the expected sorting condition when generating the optimized query execution plan optimized for parallel execution.

13. The optimization system of claim 1 wherein:

the stored representation indicates an ensured sorting condition for output of parallelized instances of the user-defined function; and

the optimizer is configured to leverage the ensured sorting condition when generating the optimized query execution plan optimized for parallel execution.

14. The optimization system of claim 1 wherein:

for the user-defined function, the stored representation indicates an expected size of an output relation in terms of size of an input relation; and

the optimizer is configured to consider the expected size when generating the optimized query execution plan optimized for parallel execution.

15. The optimization system of claim 1 wherein:

for the user-defined function, the stored representation indicates an expected run time in terms of size of an input relation; and

the optimizer is configured to consider the expected run time when generating the optimized query execution plan optimized for parallel execution.

16. The optimization system of claim 1 wherein:

the query execution plan represents a loop or nested operations.

17. A method implemented at least in part by a computing system, the method comprising:

receiving a representation of one or more user-defined functions and one or more core database relational operations, wherein the representation comprises at least one property for at least one of the user-defined functions and at least one property for at least one of the core database relational operations; and

generating a query execution plan optimized for parallel execution of the one or more user-defined functions and the one or more core database relational operations according to the user-defined function property and the core database relational operation property.

18. The method of claim 17 wherein generating the optimized query execution plan comprises:

traversing the representation wherein the traversing comprises comparing properties of a child plan with permitted properties of a current operation, and, in case of a mismatch, introducing an exchange operation.

19. The method of claim 18 wherein introducing an exchange operation comprises:

considering alternatives, and selecting an alternative out of the alternatives based on estimated costs and an explicitly specified range of permitted partition arrangements.

20. One or more computer-readable media comprising computer-executable instructions causing a computing system to perform a method comprising:

receiving a representation of a program comprising a core database relational operation and a user-defined function coupled to the at least one core database relational operation, wherein the representation comprises an input property specifying a range of permitted partition arrangements as an input pre-condition for parallelized instances of the user-defined function, and the representation comprises an output property specifying a partition arrangement post-condition for the core database relational operation;

detecting a mismatch between the pre-condition and the post-condition in the representation of the program;

responsive to detecting the mismatch between the pre-condition and the post-condition, considering a plurality of possible exchange operations remedying the mismatch that satisfy the input pre-condition for parallelized instances of the user-defined function; and

incorporating the exchange operation into an optimized query execution plan implementing the program, whereby the optimized query execution plan avoids a full merge and initial partitioning operation to remedy the mismatch.