Worst Case Optimal Join Algorithms:
Techniques, Results, and Open Problems

                             Hung Q Ngo

                        Relational AI Inc. (US)



Abstract. Worst case optimal join algorithms are the class of join al-
gorithms whose runtime match the worst-case output size of a given join
query. While the first provably worse case optimal join algorithm was dis-
covered relatively recently, the techniques and results surrounding these
algorithms grow out of decades of research from a wide range of areas,
intimately connecting graph theory, algorithms, information theory, con-
straint satisfaction, database theory, and geometric inequalities. These
ideas are not just paper ware, one such algorithms was the work-horse
join algorithm of a successful commercial database and data analytics
engine.
This talks aims to be a gentle introduction to worst case optimal algo-
rithms, the intuition behind them, historical and recent developments,
and connections to information theory, and several fundamental open
problems.