{{Short description|Algorithm for computing relational joins}}
[[Image:Comparison of join algorithms.png|thumb|An illustration of properties of join algorithms. When performing a join between more than two relations on more than two attributes, binary join algorithms such as [[hash join]] operate over two relations at a time, and join them on all attributes in the join condition; worst-case optimal algorithms such as generic join operate on a single attribute at a time but join all the relations on this attribute.<ref>{{Cite journalarXiv |lastlast1=Wang |firstfirst1=Yisu Remy |last2=Willsey |first2=Max |last3=Suciu |first3=Dan |date=2023-01-27 |title=Free Join: Unifying Worst-Case Optimal and Traditional Joins |urlclass=http://arxivcs.org/abs/2301.10841DB |journaleprint=arXiv:2301.10841 [cs]}}</ref>]]
A '''worst-case optimal join algorithm''' is an [[algorithm]] for computing [[Join (SQL)|relational joins]] with a runtime that is bounded by the [[Worst-case complexity|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.<ref>{{Cite journalarXiv |lastlast1=Ngo |firstfirst1=Hung Q. |last2=Porat |first2=Ely |last3=Ré |first3=Christopher |last4=Rudra |first4=Atri |date=2012-03-08 |title=Worst-case Optimal Join Algorithms |urlclass=http://arxivcs.org/abs/1203.1952DB |journaleprint=arXiv:1203.1952 [cs, math]}}</ref> Worst-case optimal join algorithms have been implemented in commercial database systems, including the [[LogicBlox|LogicBlox system]].<ref>{{Cite journalarXiv |last=Veldhuizen |first=Todd L. |date=2013-12-20 |title=Leapfrog Triejoin: a worst-case optimal join algorithm |class=cs.DB |eprint=1210.0481 }}</ref><ref>{{Cite journal |last1=Freitag |first1=Michael |last2=Bandle |first2=Maximilian |last3=Schmidt |first3=Tobias |last4=Kemper |first4=Alfons |last5=Neumann |first5=Thomas |date=2020-07-01 |title=Adopting worst-case optimal joins in relational database systems |url=httphttps://arxivdoi.org/abs10.14778/12103407790.04813407797 |journal=arXiv:1210Proceedings of the VLDB Endowment |volume=13 |issue=12 |pages=1891–1904 |doi=10.048114778/3407790.3407797 |s2cid=221115321 |issn=2150-8097|url-access=subscription [cs]}}</ref> Worst-case optimal joins have been applied to build a worst-case optimal algorithm for [[e-matching]].<ref>{{Cite journal |lastlast1=Zhang |firstfirst1=Yihong |last2=Wang |first2=Yisu Remy |last3=Willsey |first3=Max |last4=Tatlock |first4=Zachary |date=2022-01-12 |title=Relational e-matching |url=https://doi.org/10.1145/3498696 |journal=Proceedings of the ACM on Programming Languages |volume=6 |issue=POPL |pages=35:1–35:22 |doi=10.1145/3498696|s2cid=236924583 |doi-access=free |arxiv=2108.02290 }}</ref>
