🔗Join algorithms

Same INNER/LEFT semantics, different physics

Logical joins describe which tuples survive; physical operators decide CPU, memory, and I/O. Nested loops, hash joins, and merge joins are the three workhorses, each wins under different sizes, indexes, and sort orders.

🏗️Hash Join: The Memory Build

EQUIs are fast when one side fits in RAM.

Build vs Probe

The engine picks the smaller table to Build an in-memory Hash Table. It then scans the larger table (Probe), hashing each join key to find matches in the build table. This is O(N+M) and avoids nested looping.

Smaller Table → [Hash Function] → Hash Map ← Larger Table

Memory Grant

The optimizer estimates row sizes to request a "Memory Grant." If the grant is too small, the Hash Table spills to disk (temp files), multiplying I/O costs.

Skew Problem

A "heavy" join key (e.g., tenant_id=1 having 90% of rows) creates deep buckets in the hash table, turning O(1) lookups into slow linear scans.

🌪️Sort-Merge: The External Spill

When memory fails, sorting wins.

If both tables are massive, the engine uses External Merge Sort. It sorts chunks of data, saves them to disk, and then merges them. Once sorted, the join is a simple single-pass walk (O(N log N)).

Algorithm	Memory Usage	Disk I/O	Ideal For
Nested Loop	Minimal	High (Random)	Small result sets; Index-heavy probes.
Hash Join	High (Build set)	Zero (if fits)	Large equi-joins with no indexes.
Sort-Merge	Medium (Sort buffers)	High (Sequential)	Inequality joins; already sorted data.

SQL

Plan snippet labels

EXPLAIN
SELECT *
FROM orders o
JOIN customers c ON c.customer_id = o.customer_id;

✓Illustrative result set

operator
Hash Join
Seq Scan on orders o
Hash
Seq Scan on customers c

Misread join shapes

Forcing nested loops with hints while the inner side explodes in cardinality.
Assuming merge join is cheap when large explicit sorts sit underneath.
Ignoring join order effects on memory grants and spills on hash builds.

Skew, memory, order

Profile join keys for skew before blaming “bad optimizer day.”
Add supporting indexes to enable loop or merge paths where they truly fit.
Revisit plans after statistics updates, hash vs loop flips are common after data shifts.

Outer joins

Optimizers cannot freely reorder outer joins like inner joins, NULL-padding and predicate placement change semantics. When cardinality looks wrong, confirm you are not fighting an outer-join reshape.

TL;DR

Physical join algorithms implement relational joins: nested loop (good for tiny inner sides + index lookups), hash join (builds a hash table, great for large equi-joins), and merge join (walks two sorted inputs, great when both sides are ordered on join keys). The optimizer picks based on cardinality estimates, available memory, and indexes, not your syntax order.