Executing database queries for grouping data using channel based flow control
A database system generates an execution plan including multiple operators for processing a database query, for example, a join query or a group by query. The database system allocates a set of threads. Threads communicate with other threads via blocking channels. A blocking channel includes a buffer of a fixed capacity. The database system processes the database query by streaming data through operators of the execution plan. A thread sends data generated by an operator to another thread via the blocking channel if the buffer of the blocking channel has available capacity to store the data, or else the thread blocks until the buffer has capacity to store the data. Similarly, a thread receives data generated by an operator of another thread via the blocking channel if the buffer of the blocking channel has available data, or else the thread blocks until the buffer has data.
1. A computer-implemented method for executing a database query for grouping data stored in an input table, the computer-implemented method comprising:
receiving, by a database system executing on a cluster of servers, the database query including a grouping clause for aggregating data stored in the input table;
generating an execution plan for executing the database query, the execution plan comprising a plurality of operators, the execution plan storing partial aggregation results in a data structure, the execution plan including instructions for a plurality of data distribution strategies for distributing the data structure over the cluster of servers, the plurality of data distribution strategies including a first data distribution strategy and a second data distribution strategy;
allocating a set of threads for executing operators of the execution plan, each thread processing one or more operators, the set of threads comprising at least a first thread and a second thread, wherein the first thread communicates with the second thread via a blocking channel comprising a buffer of fixed capacity for storing data, wherein the blocking channel blocks the first thread if the buffer is full, wherein the second thread processes an operator with a plurality of inputs. wherein a blocking channel is allocated to each of the plurality of inputs; and
processing the database query by streaming data through the operators of the execution plan, comprising:
determining at execution time of the database query, characteristics of input data processed by the database query, the characteristics comprising one or more of: a size of data of the input table, or a number of unique keys in the input table,
selecting at execution time of the database query, the first data distribution strategy from the plurality of data distribution strategies included in the execution plan of the database query based on the characteristics of input data processed by the database query,
monitoring characteristics of input data during execution of the database query,
responsive to detecting a change in characteristics of input data during execution of the database query, changing the distribution strategy from the first distribution strategy to the second distribution strategy, and
communicating data by the first thread via the blocking channel to the second thread.
2. The computer-implemented method of claim 1 , wherein the blocking channel allows a thread to perform one or more of:
a push operation that pushes data to the buffer of the blocking channel, wherein the push operation causes the thread to block if the buffer of the blocking channel is full; and
a pull operation that pulls data from the buffer of the blocking channel, wherein the pull operation causes the thread to block if the buffer of the blocking channel is empty.
3. The computer-implemented method of claim 1 , wherein the data structure is a hashmap that maps keys representing columns for grouping the data to partial results of aggregation of data of the input table.
4. The computer-implemented method of claim 1 , wherein one of the first data distribution strategy or the second data distribution strategy stores the data structure in each server of the cluster of servers if the size of the data structure is below a threshold value.
5. The computer-implemented method of claim 1 , wherein one of the first data distribution strategy or the second data distribution strategy partitions the data structure across a plurality of servers of the cluster of servers if the size of the data structure exceeds a threshold value.
6. The computer-implemented method of claim 1 , wherein the blocking channel is introduced between the first thread and the second thread, wherein the first thread executes an operator of the execution plan that shuffles data stored in the input table across the cluster of servers.
7. The computer-implemented method of claim 1 , wherein the blocking channel is introduced between the first thread and the second thread, wherein the first thread executes an operator for broadcasting data of the data structure to each server of the cluster of servers.
8. The computer-implemented method of claim 1 , wherein the blocking channel is introduced between the first thread and the second thread responsive to determining that a second operator performed by the second thread performs an aggregation of data stored in a table.
9. A non-transitory computer readable storage medium storing instructions that when executed by one or more computer processors, cause the one or more computer processors to perform steps comprising:
receiving, by a database system executing on a cluster of servers, a database query including a grouping clause for aggregating data stored in an input table;
generating an execution plan for executing the database query, the execution plan comprising a plurality of operators, the execution plan storing partial aggregation results in a data structure, the execution plan including instructions for a plurality of data distribution strategies for distributing the data structure over the cluster of servers, the plurality of data distribution strategies including a first data distribution strategy and a second data distribution strategy;
allocating a set of threads for executing operators of the execution plan, each thread processing one or more operators, the set of threads comprising at least a first thread and a second thread, wherein the first thread communicates with the second thread via a blocking channel comprising a buffer of fixed capacity for storing data, wherein the blocking channel blocks the first thread if the buffer is full, wherein the second thread processes an operator with a plurality of inputs. wherein a blocking channel is allocated to each of the plurality of inputs; and
processing the database query by streaming data through the operators of the execution plan, comprising:
determining at execution time of the database query, characteristics of input data processed by the database query, the characteristics comprising one or more of: a size of data of the input table, or a number of unique keys in the input table,
selecting at execution time of the database query, the first data distribution strategy from the plurality of data distribution strategies included in the execution plan of the database query based on the characteristics of input data processed by the database query,
monitoring characteristics of input data during execution of the database query,
responsive to detecting a change in characteristics of input data during execution of the database query, changing the distribution strategy from the first distribution strategy to the second distribution strategy, and
communicating data by the first thread via the blocking channel to the second thread.
10. The non-transitory computer readable storage medium of claim 9 , wherein the blocking channel allows a thread to perform one or more of:
a push operation that pushes data to the buffer of the blocking channel, wherein the push operation causes the thread to block if the buffer of the blocking channel is full; and
a pull operation that pulls data from the buffer of the blocking channel, wherein the pull operation causes the thread to block if the buffer of the blocking channel is empty.
11. The non-transitory computer readable storage medium of claim 9 , wherein the data structure is a hashmap that maps keys representing columns for grouping the data to partial results of aggregation of data of the input table.
12. The non-transitory computer readable storage medium of claim 9 , wherein one of the first data distribution strategy or the second data distribution strategy stores the data structure in each server of the cluster of servers if the size of the data structure is below a threshold value.
13. The non-transitory computer readable storage medium of claim 9 , wherein one of the first data distribution strategy or the second data distribution strategy partitions the data structure across a plurality of servers of the cluster of servers if the size of the data structure exceeds a threshold value.
14. The non-transitory computer readable storage medium of claim 9 , wherein the blocking channel is introduced between the first thread and the second thread, wherein the first thread executes an operator of the execution plan that shuffles data stored in the input table across the cluster of servers.
15. The non-transitory computer readable storage medium of claim 9 , wherein the blocking channel is introduced between the first thread and the second thread, wherein the first thread executes an operator for broadcasting data of the data structure to each server of the cluster of servers.
16. The non-transitory computer readable storage medium of claim 9 , wherein the blocking channel is introduced between the first thread and the second thread responsive to determining that a second operator performed by the second thread performs an aggregation of data stored in a table.
17. A computer system comprising:
one or more computer processors; and
a non-transitory computer readable storage medium storing instructions that when executed by the one or more computer processors, cause the one or more computer processors to perform steps comprising:
receiving, by a database system executing on a cluster of servers, a database query including a grouping clause for aggregating data stored in an input table;
generating an execution plan for executing the database query, the execution plan comprising a plurality of operators, the execution plan storing partial aggregation results in a data structure, the execution plan including instructions for a plurality of data distribution strategies for distributing the data structure over the cluster of servers, the plurality of data distribution strategies including a first data distribution strategy and a second data distribution strategy;
allocating a set of threads for executing operators of the execution plan, each thread processing one or more operators, the set of threads comprising at least a first thread and a second thread, wherein the first thread communicates with the second thread via a blocking channel comprising a buffer of fixed capacity for storing data, wherein the blocking channel blocks the first thread if the buffer is full, wherein the second thread processes an operator with a plurality of inputs. wherein a blocking channel is allocated to each of the plurality of inputs; and
processing the database query by streaming data through the operators of the execution plan, comprising:
determining at execution time of the database query, characteristics of input data processed by the database query, the characteristics comprising one or more of: a size of data of the input table, or a number of unique keys in the input table,
selecting at execution time of the database query, the first data distribution strategy from the plurality of data distribution strategies included in the execution plan of the database query based on the characteristics of input data processed by the database query,
monitoring characteristics of input data during execution of the database query,
responsive to detecting a change in characteristics of input data during execution of the database query, changing the distribution strategy from the first distribution strategy to the second distribution strategy, and
communicating data by the first thread via the blocking channel to the second thread.
18. The computer system of claim 17 , wherein the blocking channel allows a thread to perform one or more of:
a push operation that pushes data to the buffer of the blocking channel, wherein the push operation causes the thread to block if the buffer of the blocking channel is full; and
a pull operation that pulls data from the buffer of the blocking channel, wherein the pull operation causes the thread to block if the buffer of the blocking channel is empty.
19. The computer system of claim 17 , wherein the blocking channel is introduced between the first thread and the second thread, wherein the first thread executes an operator of the execution plan that shuffles data stored in the input table across the cluster of servers.
20. The computer system of claim 17 , wherein the blocking channel is introduced between the first thread and the second thread, wherein the first thread executes an operator for broadcasting data of the data structure to each server of the cluster of servers.