Paper on efficient processing of joins and grouped aggregations on GPUs accepted at SIGMOD’25

The paper "Efficiently Processing Joins and Grouped Aggregations on GPUs" by Bowen Wu, Dimitris Koutsoukos and Gustavo Alonso was accepted at SIGMOD'25.


Abstract: The increasing use of Graphics Processing Units (GPUs) in data centers has sparked interest in leveraging GPUs for tasks beyond ML, especially in database systems. Despite the existing extensive work on GPU-based database operators, several questions are still open. For instance, the performance of almost all operators suffers from random accesses, which can account for up to 75% of the runtime. In addition, the group-by operator, widely used and expensive, has not been fully explored for GPU acceleration. Furthermore, existing work often uses limited and unrepresentative workloads for evaluation and does not explore the query optimization aspect, i.e., how to choose the most efficient implementation based on the workload.
In this paper, we revisit the state-of-the-art GPU-based join and group-by implementations. We identify their inefficiencies and propose several optimizations. We introduce GFTR, a novel technique to reduce random accesses, leading to speedups of up to 2.3x. We further optimize existing hash-based and sort-based group-by implementations, achieving significant speedups (13x and 1.7x, respectively). We also present a new partition-based group-by algorithm ideal for high group cardinalities. We analyze the optimizations with cost models, allowing us to predict the speedup. Finally, we conduct an extensive performance evaluation to reveal the strengths and weaknesses of each implementation. We conclude by providing practical decision trees to guide query optimizers in selecting the most efficient implementation for a given workload.