Skew strikes back: New developments in the theory of join algorithms

An overview of recent developments that establish non-trivial bounds for all join queries and algorithms that meet these bounds, which are called as worst-case optimal join algorithms, is presented. The study describes recent results on join algorithms that have provable worst-case optimality runtime guarantees. Much of this progress can be understood by thinking about a simple join evaluation problem that we illustrate with the so-called triangle query. The run time of join algorithms in terms of the input data is measured, assuming the input query has constant size; this is known as the data complexity measure, which is standard in database theory.