Joins (Joins)

From Algorithm Wiki
Jump to navigation Jump to search


An SQL join clause - corresponding to a join operation in relational algebra - combines columns from one or more tables in a relational database.


$m,n$: sizes of input tables

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Nested loop join 1960 $O(nm)$ $O({1})$ Exact Deterministic
Sort merge join 1960 $O(nlogn + mlogm)$ $O(n+m)$? Exact Deterministic
Hash join 1960 $O(n+m)$ $O(n+m)$? Exact Deterministic

Time Complexity Graph

Joins - Time.png