# EGA: An Efficient GPU Accelerated Groupby Aggregation Algorithm
## 3 Background and Motivation
### Single Pass Hash-Based GPU-Accelerated SOTA Method  
In previous works, many different groupby aggregation algorithms have been proposed. Our research indicates that the single pass hash-based GPU-accelerated SOTA GA algorithm is a linear probing GA algorithm with parameter tuning based on GPU architecture [12]. We will hereafter refer to this algorithm as LPHGA. LPHGA first initializes a hash table \(HT\) of size \(S\) in GPU memory. The hash table can be viewed as two arrays: \(HTK\) and \(HTV\), where \(HTK\) stores keys and \(HTV\) stores values. Each GPU thread is responsible for processing one or more key-value pairs (k-v). During execution, each thread computes the hash value of its assigned key using a specific hash function to determine the appropriate position for inserting the k-v pair into the hash table. Since multiple threads may attempt to insert into the same position, a synchronization mechanism is required to handle this contention. In CPU implementations, locks are typically used for synchronization; in GPU implementations, atomic operations are employed to ensure thread safety. Once all k-v pairs are inserted into \(HT\), they need to be collected into contiguous GPU memory. To this end, LPHGA defines a collection key array and a collection value array to store the final results. Additionally, a helper array, referred to as the indicator array \(I\), is used to track the occupancy of each slot in \(HT\). During the hash insertion process, the indicator array \(I\) marks whether each slot contains a k-v pair. After the insertion process is complete, LPHGA computes the prefix sum of \(I\) in place to determine the appropriate positions for each k-v pair in the collection array. Regarding the size \(S\) of the hash table \(HT\), previous research suggests that \(S\) should be twice the number of groups in the key array \(K\), meaning that the load factor of \(HT\) should ideally be maintained around 0.5 [1]. However, in practical applications, the cardinality of \(K\) (the number of distinct groups) is unknown. To ensure that the load factor does not exceed 0.5, it is common to set \(S\) to \(2L\). We present an example to clarify the process of this method. The flow of the algorithm is illustrated in Figure 1.  
In this example, each thread is responsible for managing a single key-value (k-v) pair. All threads concurrently insert k-v pairs into the hash table. For instance, consider thread \(T_{0}\), which attempts to insert the key '15' into the hash table \(HT\). Initially, \(T_{0}\) targets the third slot in \(HT\) for insertion. However, upon discovering that the slot already contains the key '3', it employs linear probing to check the next slot: the fourth slot. This slot also results in a collision with the key '2', prompting \(T_{0}\) to continue probing for an available slot. Eventually, it locates an empty slot, successfully inserting the key '15' and updating the indicator array from '0' to '1' to signify that this slot is now occupied. Once all threads have completed their insertion tasks, the subsequent step involves scanning the indicator array to ascertain the locations where each k-v pair should be collected. Following this scan, the next phase is to gather the k-v pairs into a designated collection array. Each thread first verifies whether its designated slot is empty; if it is occupied, the thread collects the corresponding key into the collection array based on the results obtained from the indicator scan. From the algorithm flow of LPHGA, we can see a significant issue with this algorithm: when there are relatively few empty slots in the hash table, a GPU thread attempting to insert a key/value pair into the hash table may need to probe through many non-empty slots. To address this issue, our approach is to perform group aggregation in multiple stages. First, we perform group aggregation on a subset of key/value pairs. The selection criterion  
Figure 1: An example of LPHGA. for this subset is that the key/value pairs can be inserted into the hash table in a single probe.