Overview of the main idea (3 sentences)

This paper is a fantastic introduction to the various hash join algorithm implementations for relational database management systems. The authors start by giving a very detailed overview of all the existing algorithms (excluding sort-merge since the literature has basically already showed that these should only be used when the data is pre-sorted already). Then, they benchmark everything and in doing so, augment and improve the underlying algorithms quite a bit.

Key findings / takeaways from the paper (2-3 sentences)

• Smaller joins don’t benefit from pre-partitioning, but larger joins probably do.
• When in doubt, fallback to something simpler.
• Huge pages seem to benefit hash join algorithms.
• Benchmarking is hard!

System used in evaluation and how it was modified/extended (1 sentence)

A real system is not used for this paper, probably because that would make it too hard for the authors to implement all the algorithms. They take a query plan that was generated by Hyper and just roll some C code for it.

Workload Evaluated (1 sentence)

TPC-H Query 19.