Join Algorithm Race: Nested-Loop vs Hash vs Sort-Merge

Join Algorithm

Relations

|R| rows 16

|S| rows 16

Key domain size 8

Speed 10/s

Execution Stats

Progress0%

Comparisons

Matches found

Est. complexity

O(n·m)

Phase

scan

How it works

A query planner must join relation R (|R| rows) with relation S (|S| rows) on a key. The three classic physical join algorithms trade comparisons for setup work:

Nested-Loop:  for r in R: for s in S: if r.key==s.key -> emit
              cost ≈ O(|R|·|S|) comparisons

Hash Join:    build a hash table on R's key (one pass, O(|R|))
              probe with each s in S, only checking r's in
              the same bucket -> O(|R|+|S|) average

Sort-Merge:   sort R and S by key (O(n log n) each), then
              walk both with two pointers, advancing whichever
              key is smaller -> O(|R|+|S|) after sorting

Nested-Loop — always correct, needs no extra memory, but degrades badly as both relations grow; the visualization scans every S row for every R row.
Hash Join — builds buckets from R first (build phase), then probes each S row against only its bucket (probe phase); far fewer comparisons when the key domain is large enough to spread rows across buckets.
Sort-Merge Join — reorders both rows by key, then a single left-to-right sweep finds all matches; efficient when the data is already sorted (e.g. arrives off a B-tree index) or memory forces an external sort anyway.

A real optimizer picks between these using cost estimates from table statistics — this is exactly the decision behind an EXPLAIN plan's "Nested Loop" / "Hash Join" / "Merge Join" node.

Nested-Loop · scanning

R (outer relation, cubes) S (inner relation, spheres)

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.