Worst-case optimal join algorithm
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.[2] Worst-case optimal join algorithms have been implemented in commercial database systems, including the LogicBlox system.[3] Worst-case optimal joins have been applied to build a worst-case optimal algorithm for e-matching.[4]
References
Notes
- ^ Wang, Yisu Remy; Willsey, Max; Suciu, Dan (2023-01-27). "Free Join: Unifying Worst-Case Optimal and Traditional Joins". arXiv:2301.10841 [cs].
- ^ Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri (2012-03-08). "Worst-case Optimal Join Algorithms". arXiv:1203.1952 [cs, math].
- ^ Veldhuizen, Todd L. (2013-12-20). "Leapfrog Triejoin: a worst-case optimal join algorithm". arXiv:1210.0481 [cs].
- ^ Zhang, Yihong; Wang, Yisu Remy; Willsey, Max; Tatlock, Zachary (2022-01-12). "Relational e-matching". Proceedings of the ACM on Programming Languages. 6 (POPL): 35:1–35:22. doi:10.1145/3498696.
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. 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.