=Paper=
{{Paper
|id=Vol-2100/keynote2
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-2100/keynote2.pdf
|volume=Vol-2100
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-2100/keynote2.pdf</pdf>
<pre>
 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.

</pre>