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.

[2] Worst-case optimal join algorithms have been implemented in commercial database systems, including the LogicBlox system.

[3][4] Worst-case optimal joins have been applied to build a worst-case optimal algorithm for e-matching.

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. [ 1 ]