====================================================================
Published: 22 February 2023
Tags: algorithms, database, math, sql
Semih Salihoğlu dives into what Worst-case Optimal Join (wcoj) algorithms are, how they can be useful in databases management systems, and how they're implemented in the Kùzu database.
Some highlights:
- Wcoj algorithms propose that queries involving complex “cyclic joins” over many-to-many relationships should be evaluated column at a time instead of table at a time
- "Worst-case optimal" means that the worst-case runtime of these algorithms meets a known lower bound for the worst-case runtime of any join algorithm
- Kùzu generates plans that mix binary joins and wcoj-style multiway intersections