Task scheduling for highly concurrent analytical and transaction workloads

• US 10,545,789 B2
• Filed: 04/25/2018
• Issued: 01/28/2020
• Est. Priority Date: 06/24/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Ailamaki, Anastasia, Scheuer, Tobias, Psaroudakis, Iraklis, May, Norman
• Primary Examiner(s): Wu, Benjamin C
• Application Number:
  US15/963,060
• Publication Number:
  US 20180246755A1
• Time in Patent Office: 643 Days
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 2209/504 Resource capping
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Systems and method for a task scheduler with dynamic adjustment of concurrency levels and task granularity are disclosed for improved execution of highly concurrent analytical and transactional systems. The task scheduler can avoid both over commitment and underutilization of computing resources by monitoring and controlling the number of active worker threads. The number of active worker threads can be adapted to avoid underutilization of computing resources by giving the OS control of additional worker threads processing blocked application tasks. The task scheduler can dynamically determine a number of parallel operations for a particular task based on the number of available threads. The number of available worker threads can be determined based on the average availability of worker threads in the recent history of the application. Based on the number of available worker threads, the partitionable operation can be partitioned into a number of sub operations and executed in parallel.

Claims

1. A method, executable by a computer system, comprising:

processing, by a database management system (DBMS) operating on the computer system, a query in a first thread in a plurality of worker threads to generate a parsing task associated with the query;

parsing, by a parser of the DBMS operating on the computer system, the query based on the parsing task to generate an execution plan comprising a plurality of ordered operations for answering the query;

generating, by the parser of the DBMS operating on the computer system, a task graph based on the execution plan, the task graph comprising a plurality of task nodes corresponding to the plurality of ordered operations;

identifying, by the DBMS operating on the computer system, a first task node in the plurality of task nodes corresponding to a first ordered operation in the plurality of ordered operations determined to be partitionable into sub operations for execution in parallel; and

generating, by an optimizer of the DBMS operating on the computer system, a plurality of partitioned tasks for execution in parallel based on the first task node and a number of available worker threads in the plurality of worker threads.

2. The method of claim 1 further comprising:

executing, by the DBMS operating on the computer system, the plurality of partitioned tasks in the plurality of worker threads;

executing, by the DBMS operating on the computer system, the plurality of task nodes in the plurality of worker threads; and

tracking, by the DBMS operating on the computer system, the availability of worker threads while the plurality of partitioned tasks and the plurality of task nodes are executing.

3. The method of claim 1, wherein processing the query is performed in response to receiving the query from a client, the method further comprising sending results of the query to the client.

4. The method of claim 1, wherein generating the plurality of partitioned tasks is further based on a state of the query.

5. The method of claim 1, wherein the query is an SQL query for information contained in a database.

6. The method of claim 1, wherein the number of available worker threads in the plurality of worker threads is a first number of available worker threads in the plurality of worker threads, wherein the plurality of partitioned tasks is a first plurality of partitioned tasks, wherein the method further comprises:

identifying, by the DBMS operating on the computer system, a second task node in the plurality of task nodes corresponding to a second ordered operation in the plurality of ordered operations determined to be partitionable into sub operations for execution in parallel; and

generating, by the optimizer of the DBMS operating on the computer system, a second plurality of partitioned tasks for execution in parallel based on the second task node and a second number of available worker threads in the plurality of worker threads.

7. The method of claim 6 further comprising:

executing, by the DBMS operating on the computer system, the second plurality of partitioned tasks in the plurality of worker threads; and

tracking, by the DBMS operating on the computer system, the availability of worker threads while the second plurality of partitioned tasks are executing.

8. A non-transitory computer readable medium storing a program executable by at least one processing unit of a computing system, the program comprising sets of instructions for:

processing, by a database management system (DBMS) operating on the computing system, a query in a first thread in a plurality of worker threads to generate a parsing task associated with the query;

parsing, by a parser of the DBMS operating on the computing system, the query based on the parsing task to generate an execution plan comprising a plurality of ordered operations for answering the query;

generating, by the parser of the DBMS operating on the computing system, a task graph based on the execution plan, the task graph comprising a plurality of task nodes corresponding to the plurality of ordered operations;

identifying, by the DBMS operating on the computing system, a first task node in the plurality of task nodes corresponding to a first ordered operation in the plurality of ordered operations determined to be partitionable into sub operations for execution in parallel; and

generating, by a optimizer of the DBMS operating on the computing system, a plurality of partitioned tasks for execution in parallel based on the first task node and the concurrency level value.

9. The non-transitory computer readable medium of claim 8, wherein the program further comprises sets of instructions for:

executing, by the DBMS operating on the computing system, the plurality of partitioned tasks in the plurality of worker threads;

executing, by the DBMS operating on the computing system, the plurality of task nodes in the plurality of worker threads; and

tracking, by the DBMS operating on the computing system, the availability of worker threads while the plurality of partitioned tasks and the plurality of task nodes are executing.

10. The non-transitory computer readable medium of claim 8, wherein the set of instructions for processing the query is performed in response to receiving the query from a client, wherein the program further comprises a set of instructions for sending results of the query to the client.

11. The non-transitory computer readable medium of claim 8, wherein generating the plurality of partitioned tasks is further based on a state of the query.

12. The non-transitory computer readable medium of claim 8, wherein the query is an SQL query for information contained in a database.

13. The non-transitory computer readable medium of claim 8, wherein the number of available worker threads in the plurality of worker threads is a first number of available worker threads in the plurality of worker threads, wherein the plurality of partitioned tasks is a first plurality of partitioned tasks, wherein the program further comprises sets of instructions for:

identifying, by the DBMS operating on the computer system, a second task node in the plurality of task nodes corresponding to a second ordered operation in the plurality of ordered operations determined to be partitionable into sub operations for execution in parallel; and

generating, by the optimizer of the DBMS operating on the computer system, a second plurality of partitioned tasks for execution in parallel based on the second task node and the a second number of available worker threads in the plurality of worker threads.

14. The non-transitory computer readable medium of claim 13, wherein the program further comprises sets of instructions for:

executing, by the DBMS operating on the computer system, the second plurality of partitioned tasks in the plurality of worker threads; and

tracking, by the DBMS operating on the computer system, the availability of worker threads while the second plurality of partitioned tasks are executing.

15. A system comprising:

a set of processing units;

a non-transitory computer readable medium coupled to the set of processing units and comprising instructions, that when executed by at least one processing unit cause the at least one processing unit to be configured to;

process, by a database management system (DBMS) operating on the system, a query in a first thread in a plurality of worker threads to generate a parsing task associated with the query;

parse, by a parser of the DBMS operating on the system, the query based on the parsing task to generate an execution plan comprising a plurality of ordered operations for answering the query;

generate, by the parser of the DBMS operating on the system, a task graph based on the execution plan, the task graph comprising a plurality of task nodes corresponding to the plurality of ordered operations;

identify, by the DBMS operating on the system, a first task node in the plurality of task nodes corresponding to a first ordered operation in the plurality of ordered operations determined to be partitionable into sub operations for execution in parallel; and

generate, by an optimizer of the DBMS operating on the system, a plurality of partitioned tasks for execution in parallel based on the first task node and a number of available worker threads in the plurality of worker threads.

16. The system of claim 15, wherein the instructions further cause the at least one processing unit to be configured to:

execute, by the DBMS operating on the system, the plurality of partitioned tasks in the plurality of worker threads;

execute, by the DBMS operating on the system, the plurality of task nodes in the plurality of task nodes; and

track, by the DBMS operating on the system, the availability of worker threads while the plurality of partitioned tasks and the plurality of task nodes execute.

17. The system of claim 15, wherein processing the query is performed in response to receiving the query from a client, wherein the instructions further cause the at least one processing unit to be configured to send results of the query to the client.

18. The system of claim 15, wherein the plurality of partitioned tasks is further based on a state of the query.

19. The system of claim 15, wherein the number of available worker threads in the plurality of worker threads is a first number of available worker threads in the plurality of worker threads, wherein the plurality of partitioned tasks is a first plurality of partitioned tasks, wherein the instructions further cause the at least one processing unit to be configured to:

identify, by the DBMS operating on the system, a second task node in the plurality of task nodes corresponding to a second ordered operation in the plurality of ordered operations determined to be partitionable into sub operations for execution in parallel; and

generate, by the optimizer of the DBMS operating on the system, a second plurality of partitioned tasks for execution in parallel based on the second task node and a second number of available worker threads in the plurality of worker threads.

20. The system of claim 15, wherein the instructions further cause the at least one processing unit to be configured to:

execute, by the DBMS operating on the system, the second plurality of partitioned tasks in the plurality of worker threads; and

track, by the DBMS operating on the system, the availability of worker threads while the second plurality of partitioned tasks are executing.