Scheduling of query pipeline execution

Patent metadata

Field	Value
Publication number	US-11874835-B2
Application number	US-202217674313-A
Country	US
Kind code	B2
Filing date	Feb 17, 2022
Priority date	Nov 8, 2021
Publication date	Jan 16, 2024
Grant date	Jan 16, 2024

Abstract

A system includes reception of a query execution plan associated with a plurality of query execution pipelines, estimated execution costs and estimated intermediate result cardinalities, determination of one or more precedence relationships of the plurality of query execution pipelines, determination of an execution order of the plurality of query execution pipelines based on the estimated execution costs, the estimated intermediate result cardinalities, and the one or more precedence relationships, and providing of the execution order of the plurality of query execution pipelines and the query execution plan to a query execution engine.

First claim

What is claimed is:

1. A system comprising:
a memory storing processor-executable program code; and
a processing unit to execute the processor-executable program code in order to cause the system to:
receive a query execution plan associated with a plurality of query execution pipelines, estimated execution costs and estimated intermediate result cardinalities;
determine one or more precedence relationships of the plurality of query execution pipelines;
determine a plurality of execution orders of the plurality of query execution pipelines based on the one or more precedence relationships;
for each of the plurality of execution orders, determine a memory size and lifetime of intermediate results of each pipeline based on the estimated execution costs and the estimated intermediate result cardinalities;
determine an execution order from the plurality of query execution orders based on the memory size and lifetime of intermediate results of each pipeline determined for each of the plurality of execution orders; and
provide the execution order of the plurality of query execution pipelines and the query execution plan to a query execution engine.

2. A system according to claim 1 , wherein determination of the execution order comprises:
determination of a memory cost of each of the plurality of execution orders based on the memory size and lifetime of intermediate results of each pipeline determined for each of the plurality of execution orders; and
determination of the execution order from the plurality of execution orders based on the memory costs determined for each of the plurality of execution orders.

3. A system according to claim 2 , wherein determination of the execution order from the plurality of execution orders comprises determination of one of the plurality of execution orders having a lowest memory cost.

4. A system according to claim 2 , wherein determination of the plurality of execution orders of the plurality of query execution pipelines based on the one or more precedence relationships comprises:
determination of one of the plurality of query execution pipelines having a memory cost below a threshold,
wherein the determined plurality of execution orders do not include the one of the plurality of query execution pipelines having a memory cost below a threshold.

5. A system according to claim 1 , wherein determination of the execution order comprises:
determination of a longest pipeline path to which each of the plurality of query execution pipelines belongs, and based on the one or more precedence relationships; and
determination of the execution order based on the longest pipeline path to which each of the plurality of query execution pipelines belongs.

6. A system according to claim 5 , wherein determination of the execution order comprises:
determination of a first execution order based on the longest pipeline path to which each of the plurality of query execution pipelines belongs;
determination of a plurality of execution orders of the plurality of query execution pipelines based on the one or more precedence relationships;
determination of a memory cost of the first execution order based on the memory size and lifetime of intermediate results of each pipeline determined for the first execution order;
determination of a memory cost of each of the plurality of execution orders based on the memory size and lifetime of intermediate results of each pipeline determined for each of the plurality of execution orders, wherein determination of a memory cost of one of the plurality of execution orders terminates if the memory cost of the one of the plurality of execution orders will exceed the memory cost of the first execution order; and
determination of the execution order from the plurality of execution orders based on the memory cost determined for each of the plurality of execution orders.

7. A system according to claim 6 , wherein determination of the plurality of execution orders of the plurality of query execution pipelines based on the one or more precedence relationships comprises:
determination of one of the plurality of query execution pipelines having a memory cost below a threshold,
wherein the determined plurality of execution orders do not include the one of the plurality of query execution pipelines having a memory cost below a threshold.

8. A computer-implemented method comprising:
receiving a query execution plan associated with a plurality of query execution pipelines, estimated execution costs and estimated intermediate result cardinalities;
determining one or more precedence relationships of the plurality of query execution pipelines;
determining a plurality of execution orders of the plurality of query execution pipelines based on the one or more precedence relationships;
for each of the plurality of execution orders, determining a memory size and lifetime of intermediate results of each pipeline based on the estimated execution costs and the estimated intermediate result cardinalities;
determining an execution order from the plurality of query execution orders based on the memory size and lifetime of intermediate results of each pipeline determined for each of the plurality of execution order; and
providing the execution order of the plurality of query execution pipelines and the query execution plan to a query execution engine.

9. A method according to claim 8 , wherein determining the execution order comprises:
determining a memory cost of each of the plurality of execution orders based on the memory size and lifetime of intermediate results of each pipeline determined for each of the plurality of execution orders; and
determining the execution order from the plurality of execution orders based on the memory cost determined for each of the plurality of execution orders.

10. A method according to claim 9 , wherein determining the execution order from the plurality of execution orders comprises determining one of the plurality of execution orders having a lowest memory cost.

11. A method according to claim 9 , wherein determining the plurality of execution orders of the plurality of query execution pipelines based on the one or more precedence relationships comprises:
determining one of the plurality of query execution pipelines having a memory cost below a threshold,
wherein the determined plurality of execution orders do not include the one of the plurality of query execution pipelines having a memory cost below a threshold.

12. A method according to claim 8 , wherein determining the execution order comprises:
determining a longest pipeline path to which each of the plurality of query execution pipelines belongs, based on the one or more precedence relationships; and
determining the execution order based on the longest pipeline path to which each of the plurality of query execution pipelines belongs.

13. A method according to claim 12 , wherein determining the execution order comprises:
determining a first execution order based on the longest pipeline path to which each of the plurality of query execution pipelines belongs;
determining a plurality of execution orders of the plurality of query execution pipelines based on the one or more precedence relationships;
determining a memory cost of the first execution order based on the memory size and lifetime of intermediate results of each pipeline determined for the first execution order;
determining a memory cost of each of the plurality of execution orders based on the memory size and lifetime of intermediate results of each pipeline determined for each of the plurality of execution orders, wherein determination of a memory c

Assignees

• Sap Se

Inventors

• Wolf Florian
• Landgraf Lukas
• Boehm Alexander

Classifications

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F11/3409

  for performance assessment · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/24539

  using cached or materialised query results · CPC title

• G06F16/2474 Primary

  Sequence data queries, e.g. querying versioned data · CPC title