Join Algorithms — Nested-Loop, Hash, Sort-Merge

A join combines rows from two tables based on a predicate. Every database supports the same SQL syntax — but the cost difference between picking the right algorithm and the wrong one can be 10,000×.

The Three Workhorses

1. Nested-Loop Join — O(M × N)

The simplest. For every row of the outer table, scan the inner table and emit pairs where the predicate matches.

for o in outer:
    for i in inner:
        if predicate(o, i):
            emit (o, i)

Cost: |outer| * |inner| comparisons. Quadratic and brutal at scale.

Wins when: one side is tiny (a few rows), or when the inner side has an index on the join column (index-nested-loop). With an index, the cost drops to |outer| * log(inner).

2. Hash Join — O(M + N)

Build a hash table on the smaller side keyed by the join column. Probe with the other side.

build := hash_map<join_key, []row>
for r in smaller:
    build[r.key].append(r)
for r in larger:
    for match in build[r.key]:
        emit (match, r)

Cost: |smaller| + |larger| (linear). Wins when neither side is sorted and both fit in memory.

Limitation: only works for equi-joins (=). Range predicates like a.x < b.y can't hash. When the build side spills memory, hybrid hash join partitions both inputs to disk on hash buckets and joins each pair of partitions independently.

3. Sort-Merge Join — O(M log M + N log N), or O(M + N) if pre-sorted

Sort both inputs on the join column. Walk the two sorted streams with a merge cursor.

ls := sort(left,  by join_key)
rs := sort(right, by join_key)
i = 0; j = 0
while i < |ls| and j < |rs|:
    if ls[i].key < rs[j].key: i += 1
    elif ls[i].key > rs[j].key: j += 1
    else:
        # collect runs of equal keys on both sides, emit cross-product
        ...

Cost: dominated by sorting. Once sorted, the merge is linear.

Wins when: inputs are already sorted (from an index scan, or because the previous operator was a sort), or when output must be sorted anyway (ORDER BY follows).

Picking the Right Algorithm

The optimizer chooses based on cost estimates from statistics:

You can force one in Postgres with SET enable_hashjoin = off, run EXPLAIN ANALYZE, and watch the runtime explode. That's the lesson real-world DBAs internalize.

In this lesson you'll build all three algorithms and see firsthand how their output and cost differ.