Joins¶

What a join is¶

A join combines rows from two tables according to a condition — usually equality between a foreign key and a primary key. Logically, every join is "the Cartesian product of both tables, filtered by the condition"; physically, no database computes it that way. This page covers both halves: the semantics (which rows come out, including the NULL traps) and the algorithms (how the engine produces them, and what each costs). Measurements are from PostgreSQL 16.2.

Semantics¶

Trap 1: filtering an outer join in WHERE¶

ON decides which rows match; WHERE filters the result. For an outer join, putting a condition on the right table in WHERE discards the NULL-padded rows and silently turns it into an inner join. Measured (customers an, binh, chi; an has a paid order, binh a cancelled one):

-- "all customers, with their paid order if any"
SELECT cu.name, od.status FROM cu
LEFT JOIN od ON od.cid = cu.id AND od.status = 'paid';
-- an | paid,   binh | NULL,   chi | NULL          ← what was meant

SELECT cu.name, od.status FROM cu
LEFT JOIN od ON od.cid = cu.id
WHERE od.status = 'paid';
-- an | paid                                       ← binh and chi gone

Trap 2: NOT IN with a NULL¶

-- a1 = {1, 2, 3},  b1 = {1, NULL}
SELECT x FROM a1 WHERE x NOT IN (SELECT y FROM b1);        -- measured: no rows
SELECT x FROM a1 WHERE NOT EXISTS
  (SELECT 1 FROM b1 WHERE b1.y = a1.x);                    -- measured: 2, 3

x NOT IN (1, NULL) means x <> 1 AND x <> NULL; x <> NULL is unknown, so the whole condition is never true and no row passes. One NULL in the subquery's result empties the answer. Use NOT EXISTS for anti joins; it also optimizes better (PostgreSQL can't turn NOT IN into an anti join because of these semantics).

Trap 3: join fan-out¶

Joining orders to order_items and payments in one query multiplies rows: an order with 3 items and 2 payments produces 6 rows, so sum(payment.amount) counts each payment 3 times. Aggregate each child table in a subquery first, then join the aggregates.

The three algorithms¶

Nested loop¶

for each row r in outer:
    for each row s in inner where s.key = r.key:     ← an index lookup, ideally
        emit (r, s)

The only algorithm that supports arbitrary join conditions (<, LIKE, function calls), and the only one with no startup cost: it returns the first row immediately, which makes it ideal under LIMIT. Measured: joining the 29 orders of one customer to customers used a nested loop, 0.03–0.11 ms.

Hash join¶

build:  H = hash table of inner rows keyed by join key     ← smaller input
probe:  for each outer row r: for each s in H[r.key]: emit (r, s)

O(n + m) time; memory proportional to the build side. Equality conditions only. It must finish building before emitting anything (startup cost), so it is poor under small LIMITs.

When the build side doesn't fit in work_mem, the hash join partitions both inputs by hash into batches, writes all but the first to temporary files, and processes them one batch at a time (grace / hybrid hash join). Measured on the 2M × 100k join:

Each batched row is written to and read back from disk once. With a skewed key (one value in a large fraction of rows), a single batch can still be too big — a classic cause of hash joins using far more memory or time than estimated.

Merge join¶

sort both inputs by key (unless already sorted by an index)
advance a cursor on each; when keys match, emit all combinations of the equal-key groups

O(n + m) after sorting; tiny memory. Best when both sides arrive already sorted — from B-tree indexes on the join keys, or from an earlier merge join or ORDER BY that needs the same order. Equality (and some range) conditions.

Measured comparison¶

Joining all 2,000,000 orders to 100,000 customers and aggregating (warm cache, no parallelism, median of 3 runs):

With all data in memory, the index-based plans won; the planner, which assumes random page reads cost 4x sequential ones, predicted the opposite. See Query Optimization.

When each wins¶

Join order¶

For A ⋈ B ⋈ C, the result is the same in any order, but intermediate sizes differ enormously. Joining the two tables that filter each other most first keeps intermediate results small. The planner chooses the order using row estimates — so a bad estimate for one table's filter (see correlated columns in Query Optimization) can produce a join order whose intermediate result is millions of rows instead of hundreds.

Distributed joins¶

When tables are partitioned across machines (Partitioning vs. Sharding):

Network transfer dominates, which is why distributed databases (Citus, Vitess, Spark) push so hard for co-location.

Real-world usage: In Proxel's analytics queries, joining jobs with results with proxy_stats — adding indexes on foreign keys and re-ordering joins from smallest to largest table reduced query time from 8 s to 200 ms.

Common pitfall¶

Missing indexes on foreign key columns. PostgreSQL creates an index for a primary key automatically but not for the referencing column (orders.customer_id). Without it, the planner cannot use an index nested loop from customer to orders, and — less obviously — every DELETE from customers must scan the whole orders table to check the foreign key constraint, holding locks while it does. Index every foreign key column that is used in joins or whose parent rows get deleted or updated.