Zero-overhead Instance-optimal Join Algorithms

The optimal algorithm for computing acyclic joins was discovered by Yannakakis some 50 years ago. Despite its age, virtually no modern databases implement this algorithm. This is because the classic version of the algorithm has high constant overhead, and is incompatible with known query optimization techniques. In this talk, we present several new algorithms that are not only instance-optimal, but also provably efficient in absolute terms. More precisely, given the same query plan, our algorithms guarantee to run at least as fast as the binary hash join, and often much faster.