Systems and methods for determining peak memory requirements in SQL processing engines with concurrent subtasks

1. A method for estimating peak memory requirements of a specific database query scheduled to execute on one or more worker nodes in a Structured Query Language (SQL) processing engine, the method comprising:

determining or obtaining a query execution plan;

gathering statistics associated with each database table;

breaking the query execution plan into one or more subtasks and determining any dependencies between subtasks and which subtasks may execute in parallel;

calculating an estimated memory usage for each subtask using the statistics;

determining or obtaining a directed acyclic dependency graph of the one or more subtasks;

based at least in part on the directed acyclic dependency graph, determining any dependencies between subtasks and which subtasks can execute concurrently on a single worker node, wherein

each node in the directed acyclic graph represents an operator, and wherein each operator can be categorized by its function and general memory cost, the operators comprising:

one or more accumulating operators that accumulate data in underlying data structures, process the data, and return results only after processing all of the input data, accumulating operators having a high memory cost;

one or more partially accumulating operators that accumulate data from one of the input sides and stream data from a second input side, partially accumulating operators having a medium memory cost; and

one or more pipelining operators that operate on one page at a time and has a low memory cost;

totaling the amount of estimated memory for each subtask on a single worker node and setting this amount of estimated memory as the estimated peak memory requirement for the specific database query.

2. The method of claim 1 , wherein the statistics associated with each database table includes the size of the table.

3. The method of claim 1 , wherein the estimated memory usage for each subtask is determined at least in part based on the type of task and the quantity of data to be processed.

4. The method of claim 1 , wherein the step of determining which subtasks can execute concurrently on a single worker node comprises determining which nodes require a completed input from other nodes before beginning a task.

5. A method for estimating peak memory requirements of a specific database query scheduled to execute on one or more worker nodes, the method comprising:

determining or obtaining a query execution plan;

gathering statistics associated with each database table, the statistics comprising the size of the table;

breaking the query execution plan into one or more subtasks;

calculating an estimated memory usage for each subtask using the statistics, wherein the estimated memory usage for each subtask is determined at least in part based on the type of task and the quantity of data to be processed;

determining or obtaining a directed acyclic dependency graph of the one or more subtasks, wherein the directed acyclic dependency graph may identify nodes as being pipelining operators, accumulating operators, or partially accumulating operators;

based at least in part on the directed acyclic dependency graph, determining which subtasks can execute concurrently on a single worker node, at least in part by determining which nodes require a completed input from other nodes before beginning a task, wherein

each node in the directed acyclic graph represents an operator, and wherein each operator can be categorized by its function and general memory cost, the operators comprising:

one or more accumulating operators that accumulate data in underlying data structures, process the data, and return results only after processing all of the input data, accumulating operators having a high memory cost;

one or more partially accumulating operators that accumulate data from one of the input sides and stream data from a second input side, partially accumulating operators having a medium memory cost; and

one or more pipelining operators that operate on one page at a time and has a low memory cost; and

totaling the amount of estimated memory for each subtask that can execute concurrently on a single worker node and setting this amount of estimated memory as the estimated peak memory requirement for the specific database query, where accumulating operators and partially accumulating operators are assigned a greater memory cost than pipelining operators.

6. A method for estimating peak memory requirements of a specific database query scheduled to execute on one or more worker nodes, the method comprising:

determining or obtaining a query execution plan;

gathering statistics associated with each database table;

breaking the query execution plan into one or more subtasks;

calculating an estimated memory usage for each subtask using the statistics;

determining or obtaining a directed acyclic dependency graph of the one or more subtasks, the dependency graph identifying nodes as being pipelining operators, accumulating operators, or partially accumulating operators;

based at least in part on the directed acyclic dependency graph, determining which subtasks can execute concurrently on a single worker node, wherein

each node in the directed acyclic graph represents an operator, and wherein each operator can be categorized by its function and general memory cost, the operators comprising:

one or more accumulating operators that accumulate data in underlying data structures, process the data, and return results only after processing all of the input data, accumulating operators having a high memory cost;

one or more partially accumulating operators that accumulate data from one of the input sides and stream data from a second input side, partially accumulating operators having a medium memory cost; and

one or more pipelining operators that operate on one page at a time and has a low memory cost; and

totaling the amount of estimated memory for each subtask that can execute concurrently on a single worker node and setting this amount of estimated memory as the estimated peak memory requirement for the specific database query, where accumulating operators and partially accumulating operators are assigned a greater memory cost than pipelining operators.