This paper aims to be a brief introduction to the design and analysis of
worst-case optimal join algorithms. We discuss the key techniques for proving
runtime and output size bounds.

Author: Hung Q. Ngo. 2018.

In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems (SIGMOD/PODS ‘18).

Worst-case optimal join algorithms are the class of join algorithms whose
runtime match the worst-case output size of a given join query. While the first
provably worst-case optimal join algorithm was discovered 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, constraint satisfaction, database theory, and
geometric inequalities. These ideas are not just paperware: in addition to
academic project implementations, two variations of such algorithms are the
work-horse join algorithms of commercial database and data analytics engines.

Read the PDF:
Worst-Case Optimal Join Algorithms: Techniques, Results and Open Problems