Joins

Description

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

Parameters

$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

Space Complexity Graph

Time-Space Tradeoff