Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Worst-case optimal join algorithm
open-in-new
<p>A worst-case optimal join algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for computing <a href="/facts/Join_(SQL)/Cxl5lxcR">relational joins</a> with a runtime that is bounded by the <a href="/facts/Worst-case_complexity/kqzQkwIc">worst-case</a> output size of the join. Traditional <i>binary join</i> algorithms such as <a href="/facts/Hash_join/WryEJk9d">hash join</a> 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. </p><p>The first worst-case optimal join algorithm, <i>generic join</i>, was published in 2012. Worst-case optimal join algorithms have been implemented in commercial database systems, including the <a href="/facts/LogicBlox/e7qjT6d7">LogicBlox system</a>. Worst-case optimal joins have been applied to build a worst-case optimal algorithm for <a href="/facts/E-matching/tLSvoyLM">e-matching</a>. </p> <h3>Notes</h3> <h3>Sources</h3> <ul><li>Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri (2018-03-13). <a href="https://doi.org/10.1145/3180143">"Worst-case Optimal Join Algorithms"</a>. <i>Journal of the ACM</i>. 65 (3): 16:1–16:40. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1203.1952">1203.1952</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F3180143">10.1145/3180143</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>.</li> <li>Ngo, Hung Q; Ré, Christopher; Rudra, Atri (2014-02-28). <a href="https://doi.org/10.1145/2590989.2590991">"Skew strikes back: new developments in the theory of join algorithms"</a>. <i>ACM SIGMOD Record</i>. 42 (4): 5–16. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2590989.2590991">10.1145/2590989.2590991</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0163-5808">0163-5808</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6384477">6384477</a>.</li></ul>