# EGA: An Efficient GPU Accelerated Groupby Aggregation Algorithm
## 2 Related Work  
Early work investigated multi-core CPUs for groupby acceleration. [PERSON] et al. observed that, in multi-core CPU architectures, groupby operations using hash-based methods and sorting-based methods share significant similarities [13]. [PERSON] et al. proposed several parameter recommendations for data structures to optimize groupby operations in multi-core CPU environments [14]. In recent years, with the rapid development of GPU technology, researchers have increasingly focused on implementing groupby operations on GPUs. Research on GPU acceleration algorithms for GA can be mainly divided into the following two categories: hash-based methods and sorting-based methods. In the sorting-based approach, [PERSON] et al. were among the first to utilize GPU-based sorting to enhance groupby aggregation algorithms [15]. Additionally, [PERSON] et al. implemented a sorting-based groupby aggregation in SQLite, showcasing its effectiveness in database operations [16]. [PERSON] et al. proposed a sorting algorithm with adaptive capabilities that integrates the advantages of traditional sorting and hashing algorithms, eliminating the need for users to select different algorithms based on conditions such as data size and data distribution characteristics [17]. [PERSON] et al. found that current sorting solutions cannot fully utilize modern GPUs' parallel processing capabilities due to the need for synchronizing threads accessing shared memory [18]. To address this, they propose a novel method to reduce the overhead of accessing aggregate memory locations through atomic operations. The advantage of sorting-based methods is that their performance is relatively stable and can maintain good performance across various data group sizes. However, previous research has indicated that hash-based methods outperform sorting-based methods when the data group size is medium or small [1]. Therefore, in order to achieve better performance when the number of data groups is moderate or small, there are also studies on hash-based data grouping and aggregation algorithms. In the hash-based approach, [PERSON] et al. implemented a set of parallel hash table techniques, including open addressing, chaining, and cuckoo hashing, and evaluated their performance in terms of memory usage, construction time, and retrieval efficiency under different scenarios [19]. This study preliminarily confirms the possibility of accelerating hashing with GPUs, but it has not yet been applied to data analysis applications such as group aggregation of data. [PERSON] et al. proposed a hash table-based groupby aggregation algorithm that employs linear probing to resolve conflicts [1]. However, they noted that the hash table design must align with the constraints of the GPU global memory (GM), with a recommended load factor of approximately 0.5. That is to say, in this study, half of the hash table will be empty, which will result in significant space wastage. [PERSON] et al. proposed using hash tables of different granularities in different scenarios: when the data volume is small, the hash table can be placed in shared memory or even registers; when the data volume is large, the hash table can be placed in global memory. However, this division requires the ability to estimate the number of data groups in advance to determine whether to place the hash table in faster storage (such as GPU L2 or shared memory), thus limiting the applicability of this method. [PERSON] et al. systematically analyzed the impact of GPU architectures (covering four NVIDIA generations and two AMD GCN) on hash aggregation performance, revealing that hardware dependency fundamentally limits the generalizability of prior heuristic methods (NVIDIA Corporation, Santa Clara, CA, USA; Advanced Micro Devices, Inc., Santa Clara, CA, USA). They proposed a dynamic tuning algorithm leveraging the convexity of configuration space, achieving less than 1% performance loss in 90% cases within 1% of full search time, establishing a new paradigm for operator optimization in heterogeneous computing [20].