Jump label

Service navigation

Main navigation

You are here:

Main content

Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited


Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited


Cagri Balkesen, Jens Teubner, Gustavo Alonso, and M. Tamer Özsu


Proceedings of the VLDB Endowment; vol. 7, no 1; pages 85-96


paper (PDF)


In this paper we experimentally study the performance of main-memory, parallel, multi-core join algorithms, focusing on sort-merge and (radix-)hash join. The relative performance of these two join approaches have been a topic of discussion for a long time. With the advent of modern multi-core architectures, it has been argued that sort-merge join is now a better choice than radix-hash join. This claim is justified based on the width of SIMD instructions (sort-merge outperforms radix-hash join once SIMD is sufficiently wide), and NUMA awareness (sort-merge is superior to hash join in NUMA architectures). We conduct extensive experiments on the original and optimized versions of these algorithms. The experiments show that, contrary to these claims, radix-hash join is still clearly superior, and sort-merge approaches to performance of radix only when very large amounts of data are involved. The paper also provides the fastest implementations of these algorithms, and covers many aspects of modern hardware architectures relevant not only for joins but for any parallel data processing operator.

Sub content


Prof. Dr. Jens Teubner
Tel.: 0231 755-6481