AGGREGATION IN PARALLEL COMPUTATION ENVIRONMENTS WITH SHARED MEMORY
According to some embodiments, a data structure may be provided by separating an input table into a plurality of partitions; generating, by each of a first plurality of execution threads operating concurrently, a local hash table for each of the threads, each local hash table storing key—index pairs; and merging the local hash tables, by a second plurality of execution threads operating concurrently, to produce a set of disjoint result hash tables. An overall result may be obtained from the result set of disjoint result hash tables. The data structure may used in a parallel computing environment to determine an aggregation.
1 . A computer implemented method, comprising:
separating an input table into a plurality of partitions;
generating, by each of a first plurality of execution threads operating concurrently, a local hash table for each of the partitions, each local hash table storing key—index pairs; and
merging the local hash tables, by a second plurality of execution threads operating concurrently, to produce a set of disjoint result hash tables.
2 . The method of claim 1 , wherein each distinct key is mapped to a unique integer.
3 . The method of claim 1 , wherein the local hash table generated by each of the first plurality of execution threads is private to the execution thread that generated it and is independent of other local hash tables.
4 . The method of claim 1 , wherein each of the second plurality of execution threads processes a dedicated range of hash values of all of the local hash tables.
5 . The method of claim 1 , wherein the local hash tables are of a fixed size.
6 . The method of claim 1 , further comprising concatenating the set of disjoint result hash tables to obtain an overall result.
7 . A computer implemented method, comprising:
retrieving, by concurrently executing a first plurality of execution threads, disjoint partitions of an input table;
aggregating, by each of the first plurality of execution threads, values of each partition into a respective local hash table, each local hash table storing key—index pairs; and
merging the local hash tables, by a second plurality of execution threads operating concurrently, to produce a set of disjoint result hash tables, each of the second plurality of execution threads responsible for a dedicated range of hash values of all of the local hash tables.
8 . The method of claim 7 , wherein each distinct key is mapped to a unique integer.
9 . The method of claim 7 , wherein the local hash table generated by each of the first plurality of execution threads is private to the execution thread that generated it and is independent of other local hash tables.
10 . The method of claim 7 , wherein the plurality of first execution threads further:
retrieves another partition of the input table when a previously retrieved partition is consumed by the plurality of first execution threads; and
moves the local hash tables to a buffer when a hash table becomes a threshold size, initializes a new local hash table, and proceeds to retrieve another partition of the input table.
11 . The method of claim 7 , further comprising concatenating the set of disjoint result hash tables to obtain an overall result.
12 . The method of claim 1 , wherein the second plurality of execution threads are further responsible for another dedicated range of hash values of all of the local hash tables in an instance the second plurality of execution threads have processed all of the local hash tables and other ranges of hash values remain unprocessed.
13 . A system, comprising:
a plurality of processing units;
a shared memory accessible by all of the plurality of processing units;
a database to store an input table; and
a query engine to execute an query comprising:
separating the input table into a plurality of partitions;
generating, by each of a first plurality of execution threads executing concurrently by the plurality of processing units, a local hash table for each of the partitions, each local hash table storing key—index pairs; and
merging the local hash tables, by a second plurality of execution threads executing concurrently by the plurality of processing units, to produce a set of disjoint result hash tables.
14 . The system of claim 13 , wherein each distinct key is mapped to a unique integer.
15 . The system of claim 13 , wherein the local hash table generated by each of the first plurality of execution threads is private to the execution thread that generated it and is independent of other local hash tables.
16 . The system of claim 13 , wherein each of the second plurality of execution threads processes a dedicated range of hash values of all of the local hash tables.
17 . The system of claim 13 , wherein the local hash tables are of a fixed size.
18 . The system of claim 13 , further comprising concatenating the set of disjoint result hash tables to obtain an overall result.
19 . A system, comprising:
a plurality of processing units;
a shared memory accessible by all of the plurality of processing units;
a database to store an input table; and
a query engine to execute an aggregation query comprising:
retrieving, by concurrently executing a first plurality of execution threads by the plurality of processing units, disjoint partitions of an input table;
aggregating, by each of the first plurality of execution threads, values of each partition into a respective local hash table, each local hash table storing key—index pairs; and
merging the local hash tables, by a second plurality of execution threads executing concurrently by the plurality of processing units, to produce a set of disjoint result hash tables, each of the second plurality of execution threads responsible for a dedicated range of hash values of all of the local hash tables.
20 . The system of claim 19 , wherein each distinct key is mapped to a unique integer.
21 . The system of claim 19 , wherein the local hash table generated by each of the first plurality of execution threads is private to the execution thread that generated it and is independent of other local hash tables.
22 . The system of claim 19 , wherein the plurality of first execution threads further:
retrieve another partition of the input table when a previously retrieved partition is consumed by the plurality of first execution threads;
move the local hash tables to a buffer when a hash table becomes a threshold size, initializes a new local hash table, and proceeds to retrieve another partition of the input table.
23 . The system of claim 19 , further comprising concatenating the set of disjoint result hash tables to obtain an overall result.