Multi-Core Scheduling for Parallel Queries

• US 20100312762A1
• Filed: 04/12/2010
• Published: 12/09/2010
• Est. Priority Date: 06/05/2009
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Li, Wen-Syan, Xu, Jian, Yan, Jianfeng
• Granted Patent: US 8,219,546 B2
• Time in Patent Office: Days
• US Class Current: 707/716
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 9/505 considering the load

Abstract

An operator manager may be configured to determine a number of available cores and to assign the cores among a plurality of operators of a query, the operators including a running set of operators through which a plurality of query paths exist. The operator manager may include a status monitor configured to determine the number of available cores and to determine the running set of operators, a critical path selector configured to determine a critical path of the query from among the query paths and the running set of operators, and a workload manager configured to assign a first core of the available cores to a running operator of the running set and of the critical path, and to thereafter receive a new critical path from the critical path selector and to assign a second core of the available cores to the running operator of the new critical path.

Claims

1. A system including instructions recorded on a computer-readable medium, the system comprising:

an operator manager configured to determine a number of available cores and to assign the cores among a plurality of operators of a query, the operators including a running set of operators through which a plurality of query paths exist, the operator manager including

a status monitor configured to determine the number of available cores and to determine the running set of operators,

a critical path selector configured to determine a critical path of the query from among the query paths and the running set of operators, and

a workload manager configured to assign a first core of the available cores to a running operator of the running set and of the critical path, and to thereafter receive a new critical path from the critical path selector and to assign a second core of the available cores to the running operator of the new critical path.

2. The system of claim 1, wherein the critical path selector is configured to determine the critical path including summing operator execution times of operators of each query path, and thereafter selecting the critical path as having a largest summed execution time of the query paths.

3. The system of claim 2, wherein the critical path selector is configured to determine the new critical path by re-calculating summed operator execution times for each query path after the assignment of the first core to the running operator of the running set and of the critical path, and selecting the new critical path as having the largest summed execution time of the query paths.

4. The system of claim 1, wherein the critical path selector is configured to determine the new critical path including:

calculating summed operator execution times for each query path after the assignment of the first core to the running operator of the running set and of the critical path;

determining a potential critical path for assignment of the second core to a running operator of the running set and of the potential critical path, the potential critical path having the largest summed execution time of the query paths;

determining from the workload manager that the assignment of the second core to the running operator of the running set and of the potential critical path would not provide a net benefit in the execution time thereof; and

determining the new critical path as having the second-largest summed execution time of the query paths.

5. The system of claim 1, wherein the workload manager is configured to assign the first core including determining from a reduction function of the running operator of the running set and of the critical path that the assignment of the first core will result in a net reduction in execution time thereof.

6. The system of claim 1 wherein the operator manager is configured to continue to assign the available cores to the running operators of the query paths until the workload manager determines that, according to reduction functions of the running operators, assignment of any available core to any of the running operators would not result in a decrease in the execution times thereof.

7. The system of claim 1, wherein the status monitor is configured to detect a state change including a newly-available or unavailable core, a start or completion of a running operator of the query, and configured to stop or start operations of the operator manager based on the state change.

8. The system of claim 1, comprising:

a query manager configured to determine a plurality of queries, including the query, wherein the query manager includes

a query selector configured to determine a total number of available cores and configured to assign the available cores of the total number of available cores to the operator manager for parallel processing of the query therewith; and

a query monitor configured to monitor the plurality of queries to determine a state thereof.

9. The system of claim 8, wherein the query selector is configured to determine a tree shape associated with the plurality of queries and to determine a multi-query processing algorithm based thereon and on the total number of available cores.

10. The system of claim 9, wherein the query selector is configured to implement the multi-query processing algorithm including a Shortest Remaining Job First (SRJF) algorithm, according to which the query monitor selects the query from the plurality of queries as having the shortest remaining time to finish, and the query selector assigns the available cores to the query for use by the operator manager in parallel processing thereof.

11. The system of claim 9, wherein the query selector is configured to implement the multi-query processing algorithm including a Benefits Driven Balanced Critical Path (BD-BCP) algorithm, according to which a loop is executed in which the query monitor selects the query from the plurality of queries as having the largest benefit experienced from assigning a core thereto, and the query selector assigns a first core to the query, whereupon the loop continues with selection by the query monitor of a next query having the next largest benefit experienced from assigning a core thereto from the plurality of available cores.

12. The system of claim 1, wherein the running set of operators include each running operator of the query within each parallel thread of the query, wherein a path from each such running operator to the end of the query is included in the plurality of query paths.

13. A computer-implemented method comprising:

determining a query including a plurality of operators, the operators including a running set of operators through which a plurality of query paths exist;

determining a number of available cores;

determining a critical path of the plurality of query paths, based on a total execution time of each of the plurality of query paths;

assigning a first one of the available cores to a first operator within the running set and within the critical path;

determining a new critical path through the plurality of query paths, based on the assigning; and

assigning a second one of the available cores to a second operator within the running set and the new critical path.

14. The method of claim 13, wherein determining the critical path comprises:

summing operator execution times of operators of each query path; and

selecting the critical path as having a largest summed execution time of the query paths.

15. The method of claim 13 wherein assigning the first one of the available cores comprises determining from a reduction function associated with the first operator within the running set and within the critical path that assignment of the first one of the available cores thereto will result in a reduced execution time thereof.

16. The method of claim 13, wherein determining the new critical path comprises:

calculating summed operator execution times for each query path after the assignment of the first one of the available cores to the first operator within the running set and within the critical path;

determining a potential critical path for assignment of the second one of the available cores to a running operator of the running set and of the potential critical path, the potential critical path having the largest summed execution time of the query paths;

determining that the assignment of the second one of the available cores to the running operator of the running set and of the potential critical path would not provide a net benefit in the execution time thereof; and

determining the new critical path as having a next-largest summed execution time of the query paths.

17. The method of claim 13, wherein determining the query comprises:

determining the query from a plurality of queries;

determining a total number of cores; and

determining that the query has the shortest remaining time to finish of the plurality of queries; and

assigning the available cores of the total number of cores to the query, based on the determining that the query has the shortest remaining time to finish.

18. The method of claim 13, wherein determining the query comprises:

determining the query from a plurality of queries;

determining a total number of cores;

projecting, for each of the plurality of queries, a benefit length associated with a reduction in query execution time as caused by the assignment of at least one core of the total number of cores to each query for processing therewith;

assigning at least one core of the total number of cores to the query, based on the projecting;

re-projecting the benefit length for each of the plurality of queries, based on the assigning; and

assigning at least a second core of the total number of cores to the query, based on the re-projecting, the first and second cores of the total number of cores thus forming the available cores for the query.

19. A computer program product, the computer program product being tangibly embodied on a computer-readable medium and comprising instructions that, when executed, are configured to:

determine a query including a plurality of operators, the operators including a running set of operators through which a plurality of query paths exist;

determine a number of available cores;

determine a critical path of the plurality of query paths, based on a total execution time of each of the plurality of query paths;

assign a first one of the available cores to a first operator within the running set and within the critical path;

determine a new critical path through the plurality of query paths, based on the assigning; and

assign a second one of the available cores to a second operator within the running set and the new critical path.

20. The computer program product of claim 19, wherein the critical path is determined by:

summing operator execution times of operators of each query path; and

selecting the critical path as having a largest summed execution time of the query paths.

21. The computer program product of claim 19, wherein the first one of the available cores is assigned by determining from a reduction function associated with the first operator within the running set and within the critical path that assignment of the first one of the available cores thereto will result in a reduced execution time thereof.