Join algorithms

A JOIN in SQL says which rows belong together, not how to find them. The planner chooses one of three physical algorithms for each join. You'll see the choice in EXPLAIN output.

#Nested loop

For each row on the outer side, find matching rows on the inner side.

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

With an index on the inner join key, each lookup is a quick B-tree probe, so this is the best plan when the outer side is small, for example "this user's 20 orders, joined to products." Without an index, it scans the inner table once per outer row. That's O(N × M), and it's the classic cause of a query that's fast in development and slow in production.

#Hash join

Build a hash table from the smaller input, keyed on the join column. Then stream the larger input and probe the table.

• About O(N + M). This is the usual winner for joining two large, unsorted inputs.
• Works only for equality joins (a.id = b.a_id).
• Needs memory for the hash table. In PostgreSQL that's bounded by work_mem, and if the table doesn't fit, the join spills to disk in batches. EXPLAIN ANALYZE reports Batches: N, and more than 1 means it spilled.

#Merge join

Sort both inputs on the join key, then walk them together like the merge step of merge sort.

• Cheap when both inputs already arrive sorted, for example from an index on the key or an earlier ORDER BY.
• Handles range conditions as well as equality, and produces sorted output for free.
• When the inputs aren't already sorted, the sort costs more than a hash join would.

#Reading a plan

Hash Join  (cost=... rows=48210)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on orders o
  ->  Hash
        ->  Seq Scan on customers c

When a join is slow, look at three things:

• The row estimate against the actual count. A planner that expects 10 rows and gets 100,000 picks a nested loop when it should have picked a hash join. Run ANALYZE and check the table statistics.
• Whether the inner side of a nested loop has an index. If it doesn't, either add one (composite indexes) or make the join a hash join.
• Whether a hash join spilled to disk.

Don't force a join algorithm. Fix the estimate or the index and let the planner choose. The query plans lesson walks through real EXPLAIN ANALYZE output.