Worst-case optimal join algorithm: Difference between revisions

Revision as of 15:44, 4 March 2023

Latest revision as of 13:02, 25 August 2025

(10 intermediate revisions by 4 users not shown)

Line 1:

{{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 arXiv |last1=Wang |first1=Yisu Remy |last2=Willsey |first2=Max |last3=Suciu |first3=Dan |date=2023-01-27 |title=Free Join: Unifying Worst-Case Optimal and Traditional Joins |class=cs.DB |eprint=2301.10841 }}</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>

== References ==

Line 7 ⟶ 10:

{{Reflist}}

=== Sources ===

*{{Cite journal |lastlast1=Ngo |firstfirst1=Hung Q. |last2=Porat |first2=Ely |last3=Ré |first3=Christopher |last4=Rudra |first4=Atri |date=2018-03-13 |title=Worst-case Optimal Join Algorithms |url=https://doi.org/10.1145/3180143 |journal=Journal of the ACM |volume=65 |issue=3 |pages=16:1–16:40 |doi=10.1145/3180143 |issn=0004-5411|arxiv=1203.1952 }}

*{{Cite journal |last1=Ngo |first1=Hung Q |last2=Ré |first2=Christopher |last3=Rudra |first3=Atri |date=2014-02-28 |title=Skew strikes back: new developments in the theory of join algorithms |url=https://doi.org/10.1145/2590989.2590991 |journal=ACM SIGMOD Record |volume=42 |issue=4 |pages=5–16 |doi=10.1145/2590989.2590991 |s2cid=6384477 |issn=0163-5808|url-access=subscription }}

== External links ==