# EGA: An Efficient GPU Accelerated Groupby Aggregation Algorithm
## 1 Introduction  
With the rapid development of information technology, the generation and application of big data have become significant characteristics of contemporary society. Traditional data processing methods, especially in distributed environments, struggle with data's rapid growth and diversification. The efficient analysis of massive datasets remains a critical research challenge [1]. In this context, Group By Aggregation (GA) has demonstrated considerable for application potential in the field of large-scale data analysis. GA is primarily utilized to extract valuable information from vast datasets; by grouping and aggregating data, GA enables organizations to identify trends, optimize decision-making, and enhance efficiency. This method proves essential for log analysis, social media, finance, and healthcare applications [2, 3, 4, 5]. Currently, many big data processing tasks rely on Massively Parallel Processing (MPP) platforms, such as Dremel, Apache Spark (v3.4.4), and Redshift (v3.5.11) [6,7]. These platforms achieve efficient data processing by distributing computational tasks across multiple computing nodes. However, existing MPP platforms exhibit several notable characteristics in practical applications. First, the low density of computing cores results in insufficient computational throughput, making it difficult to meet the demands of real-time data processing. Second, the dispersed storage of data significantly increases the overhead of dataexchange, thereby reducing the overall performance of the system. Furthermore, many computational tasks often undergo multiple stages, akin to the Map/Reduce computation process, which adds latency and affects the ability to perform real-time computations. When dealing with operators that require substantial computational resources such as GA, achieving near-real-time computation becomes challenging. To address this challenge, the application of Graphics Processing Units (GPUs) in the field of big data analysis has garnered increasing attention [8; 9; 10]. For instance, platforms like Apache Spark and NVIDIA RAPIDS (v25.02) leverage the GPU acceleration for data analysis, significantly enhancing computational efficiency. Apache Spark supports the allocation of computational tasks to GPUs, thereby accelerating data processing and machine learning tasks, while NVIDIA RAPIDS provides a comprehensive suite of GPU-accelerated libraries that optimize data science and analytical workflows. GPUs have been widely used in the acceleration of GA. Existing GPU GA algorithms are either hash-based or sort-based. Some previous studies have shown that hash-based GA methods are superior to sort-based GA methods [11]. However, existing hash-based GA algorithms that utilize GPU acceleration exhibit certain limitations [1; 12]. Hash-based algorithms require a hash table. In the following two scenarios, hash-based algorithms will face performance degradation: first, when the load factor of hash table is excessively high, the computational efficiency of the platform significantly declines, failing to fully exploit the advantages of GPUs; second, when the data volume exceeds the GPU's memory capacity, there are no platforms available that can make full use of the GPU for GA acceleration. To address the aforementioned challenges, this paper proposes EGA, an efficient GPU-accelerated groupby aggregation algorithm. In this paper, our main contributions are as follows: In the situation that data could fit in GPU memory, single-pass EGA (SP-EGA) is designed to maintain high computational efficiency even when the load factor of the hash table is 1.0. SP-EGA achieves acceleration factors ranging from 1.16 to 5.39 times compared to the state-of-the-art (SOTA) hash-based GA algorithm on the GPU when the load factor exceeds 0.90 and achieves acceleration factors ranging from 1.30 to 2.48 times compared to the SOTA sort-based GA algorithm on the GPU. In situations where data could not fit in GPU memory, multi-pass EGA (MP-EGA) is designed to support data GA that exceeds GPU memory capacity.