Robustness metrics for optimization of query execution plans

Patent metadata

Field	Value
Publication number	US-11580106-B2
Application number	US-202117528608-A
Country	US
Kind code	B2
Filing date	Nov 17, 2021
Priority date	Jun 1, 2018
Publication date	Feb 14, 2023
Grant date	Feb 14, 2023

Abstract

A method may include responding to a query to retrieve data from a database by identifying a plurality of query execution plans. An overall robustness value may be determined for each query execution plan. The overall robustness value of a query execution plan may correspond to a sum of individual robustness values for each operator included in the query execution plan. Each operator may have an individual robustness value that corresponds to a first change in a total cost of a query execution plan including the operator relative to a second change in an output cardinality of the operator. One of the plurality of query execution plans may be selected based on the overall robustness value of each of the plurality of query execution plans. The query may be executed by performing a sequence of operators included in the selected one of the plurality of query execution plan.

First claim

What is claimed is:

1. A system, comprising:
at least one data processor; and
at least one memory storing instructions which, when executed by the at least one data processor, result in operators comprising:
responding to a query to retrieve data from a database by at least identifying a plurality of query execution plans;
determining, for each of the plurality of query execution plans, an overall robustness value corresponding to a sum of an individual robustness value associated with each operator included in the query execution plan;
selecting, based at least on the overall robustness value of each of the plurality of query execution plans, one of the plurality of query execution plan for executing the query; and
executing the query in accordance with the selected one of the plurality of query execution plan, the query being executed by at least performing a sequence of operators included in the selected one of the plurality of query execution plan.

2. The system of claim 1 , wherein the individual robustness value comprises a cardinality-slope robustness value, and wherein the cardinality-slope robustness value of each operator corresponds to a slope of a parametric cost function modeling a total cost of the query execution plan including the operator relative to an output cardinality of the operator.

3. The system of claim 1 , wherein the individual robustness value comprises a selectivity-slope robustness value, wherein the selectivity-slope robustness value of each operator corresponds to a slope of a parametric cost function modeling a total cost of the query execution plan including the operator relative to a selectivity of the operator, and wherein the selectivity of the operator corresponds to an output size of the operator relative to a maximum output size of the operator.

4. The system of claim 1 , wherein the individual robustness value comprises a cardinality-integral robustness value, wherein the cardinality-integral robustness value of the each operator corresponds to an integral of a parametric cost function modeling the total cost of a query execution plan including the operator relative to an output cardinality of the operator, and wherein the integral is bound between a lower cardinality bound and an upper cardinality bound.

5. The system of claim 1 , wherein the overall robustness value of the query execution plan comprises a weighted sum of the individual robustness value associated with each operator included in the query execution plan, and wherein a first operator included in the query execution plan is assigned a higher weight than a second operator included in the query execution plan based at least on the first operator being more prone to a cardinality estimation error than the second operator.

6. The system of claim 1 , wherein the one of the plurality of query execution plans is selected based at least on the one of the plurality of query execution plans having a lowest overall robustness value.

7. The system of claim 1 , wherein the one of the plurality of query execution plans is selected based at least on the one of the plurality of query execution plans being associated with an overall robustness value that does not exceed a threshold value.

8. The system of claim 1 , wherein the query execution plan is associated with a total cost corresponding to a sum of a quantity of time and/or a quantity of computational resources required to perform each operator included in the query execution plan.

9. The system of claim 1 , wherein each operator included in the query execution plan is associated with an output cardinality corresponding to an output size of the operator.

10. The system of claim 1 , wherein the plurality of query execution plans are identified based at least on a cost of each of the plurality of query execution plans.

11. The system of claim 1 , wherein the plurality of query execution plans comprise a threshold quantity of query execution plans having a lowest cost.

12. The system of claim 1 , wherein a query execution plan is identified to be part of the plurality of query execution plans based at least on a cost of the query execution plan not exceeding a cost of a lowest cost query execution plan by a threshold value.

13. A computer-implemented method, comprising:
responding to a query to retrieve data from a database by at least identifying a plurality of query execution plans;
determining, for each of the plurality of query execution plans, an overall robustness value corresponding to a sum of an individual robustness value associated with each operator included in the query execution plan;
selecting, based at least on the overall robustness value of each of the plurality of query execution plans, one of the plurality of query execution plan for executing the query; and
executing the query in accordance with the selected one of the plurality of query execution plan, the query being executed by at least performing a sequence of operators included in the selected one of the plurality of query execution plan.

14. The method of claim 13 , wherein the individual robustness value comprises a cardinality-slope robustness value, and wherein the cardinality-slope robustness value of each operator corresponds to a slope of a parametric cost function modeling a total cost of the query execution plan including the operator relative to an output cardinality of the operator.

15. The method of claim 13 , wherein the individual robustness value comprises a selectivity-slope robustness value, wherein the selectivity-slope robustness value of each operator corresponds to a slope of a parametric cost function modeling a total cost of the query execution plan including the operator relative to a selectivity of the operator, and wherein the selectivity of the operator corresponds to an output size of the operator relative to a maximum output size of the operator.

16. The method of claim 13 , wherein the individual robustness value comprises a cardinality-integral robustness value, wherein the cardinality-integral robustness value of the each operator corresponds to an integral of a parametric cost function modeling the total cost of a query execution plan including the operator relative to an output cardinality of the operator, and wherein the integral is bound between a lower cardinality bound and an upper cardinality bound.

17. The method of claim 13 , wherein the overall robustness value of the query execution plan comprises a weighted sum of the individual robustness value associated with each operator included in the query execution plan, and wherein a first operator included in the query execution plan is assigned a higher weight than a second operator included in the query execution plan based at least on the first operator being more prone to a cardinality estimation error than the second operator.

18. The method of claim 13 , wherein the one of the plurality of query execution plans is selected based at least on the one of the plurality of query execution plans having a lowest overall robustness value and/or an overall robustness value that does not exceed a threshold value.

19. The method of claim 13 , wherein the plurality of query execution plans comprise a threshold quantity of query execution plans having a lowest cost and/or a plurality of query execution plans whose costs do not exceed a cost of a lowest cost query execution plan by a threshold value.

20. A non-transitory computer readable medium storing instructions, which when executed by at least one data processor, result in

Assignees

• Sap Se

Inventors

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

Classifications

• G06F16/24537 Primary

  of operators · CPC title

• G06F16/24545 Primary

  Selectivity estimation or determination · CPC title