Sort Vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs

Join is an important database operation. As computer architectures evolve, the best join algorithm may change hand. This paper reexamines two popular join algorithms - hash join and sort-merge join - to determine if the latest computer architecture trends shift the tide that has favored hash join for many years. For a fair comparison, the authors implemented the most optimized parallel version of both algorithms on the latest Intel Core i7 platform. Both implementations scale well with the number of cores in the system and take advantages of latest processor features for performance. The authors' hash-based implementation achieves more than 100M tuples per second which is 17X faster than the best reported performance on CPUs and 8X faster than that reported for GPUs.