A worst-case optimal join algorithm is an algorithm for computing relational joins with a runtime that is bounded by the worst-case output size of the join. Traditional binary join algorithms such as hash join operate over two relations at a time; joins between more than two relations are implemented by repeatedly applying binary joins. Worst-case optimal join algorithms are asymptotically faster in worst case than any join algorithm based on such iterated binary joins.

The first worst-case optimal join algorithm, generic join, was published in 2012. Worst-case optimal join algorithms have been implemented in commercial database systems, including the LogicBlox system. Worst-case optimal joins have been applied to build a worst-case optimal algorithm for e-matching.

Notes

Sources

• Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri (2018-03-13). "Worst-case Optimal Join Algorithms". Journal of the ACM. 65 (3): 16:1–16:40. arXiv:1203.1952. doi:10.1145/3180143. ISSN 0004-5411.
• Ngo, Hung Q; Ré, Christopher; Rudra, Atri (2014-02-28). "Skew strikes back: new developments in the theory of join algorithms". ACM SIGMOD Record. 42 (4): 5–16. doi:10.1145/2590989.2590991. ISSN 0163-5808. S2CID 6384477.