A worst-case optimal join algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for computing
relational joins with a runtime that is bounded by the
worst-case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
output size of the join. Traditional ''binary join'' algorithms such as
hash join
The hash join is an example of a join algorithm and is used in the implementation of a relational database management system. All variants of hash join algorithms involve building hash tables from the tuples of one or both of the joined relations ...
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.
References
Notes
Sources
*
*{{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
A Gentle(-ish) Introduction to Worst-Case Optimal Joins
Join algorithms