An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory

• DOI: 10.1145/2882903.2882917
• Publication Date: 2016-06-16T19:01:52Z
• Authors: Stefan Schuh; Xiao Chen; Jens Dittrich
• Keywords: Join (topology); Hash join; Sort-merge join

Relational equi-joins are at the heart of almost every query plan. They have been studied, improved, and reexamined on a regular basis since existence database community. In past four years several new join algorithms proposed experimentally evaluated. Some those papers contradict each other in their experimental findings. This makes it surprisingly hard to answer very simple question: what is fastest algorithm 2015? this paper we will try develop an answer. We start with end-to-end black box comparison most important methods. Afterwards, inspect internals these white comparison. derive improved variants state-of-the-art by applying optimizations like~software-write combine buffers, various hash table implementations, as well NUMA-awareness terms data placement scheduling. also radix partitioning strategies. Eventually, position perform comprehensive thirteen different algorithms. factor scaling effects size input datasets, number threads, page sizes, distributions. Furthermore, analyze impact joins (unchanged) TPC-H query. Finally, conclude list major lessons learned from our study guideline for practitioners implementing massive main-memory joins. As case all databases, learn that there no single best algorithm. Each has its strength weaknesses shines areas parameter space.