Free Your Hash Join From Slow Synchronizations: A Fast Hash Join Implementation on GPU

Non-partitioned hash join on GPU suffers from significant overhead from two types of synchronizations, i.e., (i) synchronizing concurrent writes in build phase and (ii) memory stall of synchronous random memory access in probe phase. To address these problems, we introduce a synchronization-free hash join implementation. The hash table is constructed in a lock-free way in build phase and searched with asynchronous memory access in probe phase. Through these innovations, we demonstrate a substantial improvement in hash join performance on GPUs, achieving up to a 1.19x speedup compared to traditional approaches.