Publication
Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects
Clemens Lutz; Sebastian Breß; Steffen Zeuch; Tilmann Rabl; Volker Markl
In: SIGMOD '22: Proceedings of the 2022 International Conference on Management of Data. ACM SIGMOD International Conference on Management of Data (SIGMOD-2022), June 12-17, Philadelphia, PA, USA, Pages 1017-1032, ISBN 978-1-4503-9249-5, ACM, 2022.
Abstract
Database management systems are facing growing data volumes. Previous research suggests that GPUs are well-equipped to quickly process joins and similar stateful operators, as GPUs feature high-bandwidth on-board memory. However, GPUs cannot scale joins to large data volumes due to two limiting factors: (1)~large state does not fit into the on-board memory, and (2)~spilling state to main memory is constrained by the interconnect bandwidth. Thus, CPUs are often the better choice for scalable data processing.
In this paper, we propose a new join algorithm that scales to large data volumes by taking advantage of fast interconnects. Fast interconnects such as NVLink~2.0 are a new technology that connect the GPU to main memory at a high bandwidth, and thus enable us to design our join to efficiently spill its state. Our evaluation shows that our Triton join outperforms a no-partitioning hash join by more than 100× on the same GPU, and a radix-partitioned join on the CPU by up to 2.5×. As a result, GPU-enabled DBMSs are able to scale beyond the GPU memory capacity.