Optimal ranges for relational query execution plans

Patent metadata

Field	Value
Publication number	US-11080276-B2
Application number	US-201815904192-A
Country	US
Kind code	B2
Filing date	Feb 23, 2018
Priority date	Feb 23, 2018
Publication date	Aug 3, 2021
Grant date	Aug 3, 2021

Abstract

In some implementations, there is provided an apparatus having at least one data processor and at least one memory storing instructions which, when executed by the at least one data processor, cause executing at least a portion of a query execution plan; determining, at an edge including an intermediate result, a cardinality; proceeding with the execution of the query execution plan, when the determined cardinality is within an optimality range associated with the edge; and selecting an alternative query execution plan for execution, when the determined cardinality is outside the optimality range associated with the edge. Related systems and articles of manufacture are also provided.

First claim

What is claimed is:

1. An apparatus, comprising:
at least one data processor; and
at least one memory storing instructions which, when executed by the at least one data processor, cause operations comprising:
executing at least a portion of a query execution plan including an edge node, a first node providing a first input to the edge node, and a second node providing a second input to the edge node, the executing providing, at the edge node, an intermediate result based on the first input provided by the first node and the second input provided by the second node;
determining a cardinality for the intermediate result at the edge node, rather than determining cardinalities for the first node and the second node;
proceeding with the execution of the query execution plan, when the determined cardinality is within an optimality range associated with the edge node including the intermediate result; and
selecting an alternative query execution plan for execution, when the determined cardinality is outside the optimality range associated with the edge node including the intermediate result.

2. The apparatus of claim 1 further comprising:
receiving, at a query optimizer, a query from an application; and
determining, at the query optimizer, the query execution plan for execution at a database.

3. The apparatus of claim 1 further comprising:
estimating, before the executing, the optimality range associated with the edge node.

4. The apparatus of claim 3 , wherein the optimality range includes a lower cardinality bound and a higher cardinality bound, wherein the lower cardinality bound and the higher cardinality bound form a range, within which query execution plan remains optimal.

5. The apparatus of claim 4 , wherein the lower cardinality bound is mapped to a first alternative query execution plan and the higher cardinality bound is mapped to the second alternative query execution plan, and wherein when the determined cardinality is less than the lower cardinality bound, the query optimizer selects the first alternative query execution plan for execution as an optimal plan, and wherein when the determined cardinality is higher than the higher cardinality bound, the query optimizer selects the second alternative query execution plan for execution as the optimal plan.

6. The apparatus of claim 1 , wherein the determined cardinality represents the actual cardinality obtained from execution of at least the edge node that provides the intermediate result, and wherein the optimality range is determined based on a parametric cost function.

7. The apparatus of claim 1 , wherein the optimality range and the alternative query execution plan are cached in a table, wherein the determining further comprising calculating a plurality of query execution plans, and wherein a plurality of optimality ranges are determined for a corresponding plurality of edge nodes of the query execution plan.

8. A method comprising:
executing at least a portion of a query execution plan including an edge node, a first node providing a first input to the edge node, and a second node providing a second input to the edge node, the executing providing, at the edge node, an intermediate result based on the first input provided by the first node and the second input provided by the second node;
determining a cardinality for the intermediate result at the edge node, rather than determining cardinalities for the first node and the second node;
proceeding with the execution of the query execution plan, when the determined cardinality is within an optimality range associated with the edge node including the intermediate result; and
selecting an alternative query execution plan for execution, when the determined cardinality is outside the optimality range associated with the edge node including the intermediate result.

9. The method of claim 8 further comprising:
receiving, at a query optimizer, a query from an application; and
determining, at the query optimizer, the query execution plan for execution at a database.

10. The method of claim 8 further comprising:
estimating, before the executing, the optimality range associated with the edge node.

11. The method of claim 10 , wherein the optimality range includes a lower cardinality bound and a higher cardinality bound, wherein the lower cardinality bound and the higher cardinality bound form a range, within which query execution plan remains optimal.

12. The method of claim 11 , wherein the lower cardinality bound is mapped to a first alternative query execution plan and the higher cardinality bound is mapped to the second alternative query execution plan, and wherein when the determined cardinality is less than the lower cardinality bound, the query optimizer selects the first alternative query execution plan for execution as an optimal plan, and wherein when the determined cardinality is higher than the higher cardinality bound, the query optimizer selects the second alternative query execution plan for execution as the optimal plan.

13. The method of claim 8 , wherein the determined cardinality represents the actual cardinality obtained from execution of at least the edge node that provides the intermediate result, and wherein the optimality range is determined based on a parametric cost function.

14. The method of claim 8 , wherein the optimality range and the alternative query execution plan are cached in a table, wherein the determining further comprising calculating a plurality of query execution plans, and wherein a plurality of optimality ranges are determined for a corresponding plurality of edge nodes of the query execution plan.

15. A non-transitory computer-readable storage medium including program code which, when executed by the at least one data processor, cause operations comprising:
executing at least a portion of a query execution plan including an edge node, a first node providing a first input to the edge node, and a second node providing a second input to the edge node, the executing providing, at the edge node, an intermediate result based on the first input provided by the first node and the second input provided by the second node;
determining a cardinality for the intermediate result at the edge node, rather than determining cardinalities for the first node and the second node;
proceeding with the execution of the query execution plan, when the determined cardinality is within an optimality range associated with the edge node including the intermediate result; and
selecting an alternative query execution plan for execution, when the determined cardinality is outside the optimality range associated with the edge node including the intermediate result.

16. The non-transitory computer-readable storage medium of claim 15 further causing operations comprising:
receiving, at a query optimizer, a query from an application; and
determining, at the query optimizer, the query execution plan for execution at a database.

17. The non-transitory computer-readable storage medium of claim 15 further causing operations comprising:
estimating, before the executing, the optimality range associated with the edge node.

18. The non-transitory computer-readable storage medium of claim 17 , wherein the optimality range includes a lower cardinality bound and a higher cardinality bound, wherein the lower cardinality bound and the higher cardinality bound form a range, within which query execution plan remains optimal.

19. The non-transitory computer-readable storage medium of claim 18 , wherein the lower car

Assignees

• Sap Se

Inventors

• Wolf Florian
• May Norman
• Willems Paul
• Sattler Kai-Uwe

Classifications

• G06F16/24549 Primary

  Run-time optimisation · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title