Hybrid query execution plan

Patent metadata

Field	Value
Publication number	US-9418108-B2
Application number	US-201313740143-A
Country	US
Kind code	B2
Filing date	Jan 11, 2013
Priority date	Oct 7, 2010
Publication date	Aug 16, 2016
Grant date	Aug 16, 2016

Abstract

A procedural pattern in a received query execution plan can be matched to a stored pattern for which an equivalent declarative operator has been pre-defined. The query execution plan can describe a query for accessing data. A hybrid execution plan can be generated by replacing the procedural pattern with the equivalent declarative operator. A hybrid execution plan processing cost can be assigned to execution of the hybrid execution plan and a query execution plan processing cost can be assigned to execution of the query execution plan. The assigning can include evaluating a cost model for the hybrid execution plan and the query execution plan. The query can be executed using the hybrid execution plan if the hybrid execution plan processing cost is less than the query execution plan processing cost or the query execution plan if the hybrid execution plan processing cost is greater than the query execution plan processing cost. Related systems, methods, and articles of manufacture are disclosed.

First claim

What is claimed is:

1. A computer program product comprising a machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
receiving a query execution plan describing a query for accessing data and comprising a first procedural construct;
generating a hybrid execution plan based on at least the query execution plan, the generating comprising replacing the first procedural construct in the query execution plan with a pre-defined equivalent declarative operator such that the hybrid query execution plan comprises a combination of at least one other procedural construct of the query execution plan and the predefined equivalent declarative operator, the pre-defined equivalent declarative operator comprising a conversion of procedural logic within the first procedural construct, the conversion comprising implicitly unrolling loops within the procedural logic and independently calculating an expression for each tuple within the procedural logic;
assigning a hybrid execution plan processing cost to execution of the hybrid execution plan and a query execution plan processing cost to execution of the query execution plan, the assigning comprising evaluating a cost model for the hybrid execution plan and the query execution plan; and
executing the query using the hybrid execution plan after determining that the hybrid execution plan processing cost is less than the query execution plan processing cost or the query execution plan after determining that the hybrid execution plan processing cost is greater than the query execution plan processing cost.

2. A computer program product as in claim 1 , wherein the matching further comprises applying tuple calculus to identify the procedural statement for replacement by the pre-defined equivalent declarative statement.

3. A computer program product as in claim 1 , wherein evaluating the cost model comprises determining the hybrid execution plan processing cost and the query execution plan processing cost using functions comprising:
Cost=Σ k N O −N P C decl +Σ m N P C m proc +Σ C parop /min( P C ,P P )

where Σ k N O −N p C decl represents a first sum of costs for all declarative statements,
Σ m N p C m proc represents a second sum of costs for all procedural statements, and
Σ C parop /min(P C ,P P ) represents a third sum of costs for all procedural and/or declarative operators that are calculated in parallel as divided by a minimum number of available parallel processors (P C ) and parallel operators (P P ).

4. A computer program product as in claim 1 , wherein the equivalent declarative operator comprises at least one of a selection declarative operator, a join declarative operator, a leftouter-join declarative operator, a projection declarative operator, an aggregation declarative operator, and an assign declarative operator.

5. A computer program product as in claim 1 , wherein the operations further comprise: translating a second procedural construct in the query plan to a second equivalent declarative operator in the hybrid execution plan, the translating comprising identifying a borderline procedural construct associated with a side effect when the borderline procedural construct is executed.

6. A computer program product as in claim 5 , wherein the side effect enables a condition that when a first tuple element value is changed during a loop iteration of the borderline procedural construct, the changed tuple element value is accessed in a subsequent loop iteration such that access of the changed tuple element value rather than access of the first tuple element value prevents the borderline procedural construct to be translated to an equivalent declarative operator.

7. A computer program product as in claim 1 , further comprising:
generating a second hybrid execution plan by replacing a different procedural construct with a second equivalent declarative operator;
assigning a second hybrid execution plan processing cost to execution of the second hybrid execution plan by evaluating a cost model for the second hybrid execution plan; and
executing the query using the second hybrid execution plan if the second hybrid execution plan processing cost is less than both of the query execution plan processing cost and the hybrid execution plan processing cost.

8. A system comprising:
at least one programmable processor; and
at least one machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
receiving a query execution plan describing a query for accessing data and comprising a first procedural construct;
generating a hybrid execution plan based on at least the query execution plan, the generating comprising replacing the first procedural construct in the query execution plan with a pre-defined equivalent declarative operator such that the hybrid query execution plan comprises a combination of at least one other procedural construct of the query execution plan and the predefined equivalent declarative operator, the pre-defined equivalent declarative operator comprising a conversion of procedural logic within the first procedural construct, the conversion comprising implicitly unrolling loops within the procedural logic and independently calculating an expression for each tuple within the procedural logic;
assigning a hybrid execution plan processing cost to execution of the hybrid execution plan and a query execution plan processing cost to execution of the query execution plan, the assigning comprising evaluating a cost model for the hybrid execution plan and the query execution plan; and
executing the query using the hybrid execution plan after determining that the hybrid execution plan processing cost is less than the query execution plan processing cost or the query execution plan after determining that the hybrid execution plan processing cost is greater than the query execution plan processing cost.

9. A system as in claim 8 , wherein the matching further comprises applying tuple calculus to identify the procedural statement for replacement by the pre-defined equivalent declarative statement.

10. A system as in claim 8 , wherein evaluating the cost model comprises determining the hybrid execution plan processing cost and the query execution plan processing cost using functions comprising:
Cost=Σ k N O −N P C decl +Σ m N P C m proc +Σ C parop /min( P C ,P P )

where Σ k N O −N p C decl represents a first sum of costs for all declarative statements,
Σ m N p C m proc represents a second sum of costs for all procedural statements, and
Σ C parop /min(P C ,P P ) represents a third sum of costs for all procedural and/or declarative operators that are calculated in parallel as divided by a minimum number of available parallel processors (P C ) and parallel operators (P P ).

11. A system as in claim 8 , wherein the equivalent declarative operator comprises at least one of a selection declarative operator, a join declarative operator, a leftouter-join declarative operator, a projection declarative operator, an aggregation declarative operator, and an assign declarative operator.

12. A system as in claim 8 , wherein the operations further comprise: translating a second procedural construct in the query plan to a second equivalent declarative operator in the hybrid execution plan, the translating comprising identifying a borde

Assignees

• Sap Se

Inventors

• Jaecksch Bernhard
• Faerber Franz

Classifications

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F16/2456

  Join operations · CPC title

• G06F16/2454

  Optimisation of common expressions · CPC title

• G06F16/2453

  Query optimisation · CPC title