Join Algorithms

Jr Codex DBMS Notes

Level: Intermediate–Advanced Prerequisites: Chapter 1: The Life of a Query Time to complete: ~20 minutes

Table of Contents

1. Three Ways to Join
2. Nested Loop Join
3. Hash Join
4. Sort-Merge Join
5. Choosing Between Them
6. Join Order
7. Summary & Next Steps

1. Three Ways to Join

Module 2, Chapter 3 defined a join as a Cartesian product followed by a selection. No database does that literally. There are three real algorithms, and knowing which one a plan chose explains most join performance.

The Three
─────────────────────────────────────────
  NESTED LOOP   for each row of A, find matches
                in B
  HASH JOIN     build a hash table on one side,
                probe with the other
  SORT-MERGE    sort both sides, then walk them
                together

  Each wins in a different situation. The optimiser
  picks per join, not per query.
─────────────────────────────────────────

2. Nested Loop Join

def nested_loop(outer, inner, match):
    for o in outer:                      # for EVERY outer row
        for i in inner:                  # scan the ENTIRE inner side
            if match(o, i):
                yield (o, i)
# Cost: |outer| × |inner|.  1,000 × 1,000 = 1,000,000 comparisons.

The Version That Is Actually Fast
─────────────────────────────────────────
  INDEXED NESTED LOOP — the inner side has an index
  on the join column.

    for each outer row:
        seek the index ──► ~3 page reads

  Cost: |outer| × log(|inner|), not |outer| × |inner|.

  1,000 outer rows × 3 reads = 3,000 reads instead
  of a million comparisons.
─────────────────────────────────────────

def indexed_nested_loop(outer, inner_index, key):
    for o in outer:
        for i in inner_index.lookup(key(o)):      # B+ tree seek — Module 5, Ch.2
            yield (o, i)

When It Wins
─────────────────────────────────────────
  ✓ the OUTER side is SMALL (few rows)
  ✓ the INNER side has an index on the join column
  ✓ you need the first rows quickly — it STREAMS
    (Chapter 1), so LIMIT can stop it early

  ✗ both sides large and no index ──► catastrophic.
    A nested loop over two large tables in a plan is
    almost always a bug (Chapter 4).
─────────────────────────────────────────

3. Hash Join

def hash_join(build_side, probe_side, build_key, probe_key):
    table = {}
    for row in build_side:                     # BUILD phase — blocking
        table.setdefault(build_key(row), []).append(row)
 
    for row in probe_side:                     # PROBE phase — streaming
        for match in table.get(probe_key(row), ()):
            yield (match, row)
# Cost: |build| + |probe|. LINEAR — each side read once.

The Properties
─────────────────────────────────────────
  Build the hash table on the SMALLER side, so it
  is more likely to fit in memory.

  BLOCKING on the build side (Chapter 1) — no rows
  emerge until the build finishes. Then it streams.

  EQUALITY ONLY. A hash table cannot answer
  a.x < b.y. This is the same limitation as hash
  indexes (Module 5, Chapter 3).
─────────────────────────────────────────

When Memory Runs Out
─────────────────────────────────────────
  If the build side exceeds work_mem, the database
  uses a GRACE HASH JOIN: partition both sides by
  hash into disk files, then join partition by
  partition.

  Correct, and much slower. In EXPLAIN ANALYZE it
  appears as "Batches: 8" rather than "Batches: 1".
  More than one batch means it spilled.
─────────────────────────────────────────

When It Wins
─────────────────────────────────────────
  ✓ large tables, equality join, no useful index
  ✓ the smaller side fits in memory
  ✓ the default for big analytical joins

  ✗ non-equality conditions
  ✗ when you need the first row fast
─────────────────────────────────────────

4. Sort-Merge Join

def merge_join(left_sorted, right_sorted, lkey, rkey):
    i = j = 0
    while i < len(left_sorted) and j < len(right_sorted):
        a, b = lkey(left_sorted[i]), rkey(right_sorted[j])
        if   a < b: i += 1
        elif a > b: j += 1
        else:
            # handle the group of equal keys on both sides
            for l, r in equal_group(left_sorted, right_sorted, i, j):
                yield (l, r)
            i, j = advance_past(left_sorted, right_sorted, i, j)
# Cost: sorting both sides, then ONE linear pass.

The Key Question
─────────────────────────────────────────
  Is the input ALREADY SORTED?

  If yes — because both sides are read via a B+
  tree index on the join column — the sort cost
  disappears and merge join is extremely fast.

  If no, it must sort both sides first, and hash
  join usually beats it.

  So merge join's competitiveness depends entirely
  on whether indexes supply the ordering for free
  (Module 5, Chapter 2).
─────────────────────────────────────────

When It Wins
─────────────────────────────────────────
  ✓ both inputs already sorted on the join key
  ✓ the output needs to be sorted anyway (the
    ORDER BY is then free too)
  ✓ INEQUALITY joins — the only one of the three
    that handles a.x < b.y efficiently
  ✓ very large inputs that will not fit in memory,
    since external sort is well-behaved
─────────────────────────────────────────

5. Choosing Between Them

The Practical Reading
─────────────────────────────────────────
  Seeing NESTED LOOP over two big tables
      ──► a missing index, or a bad row estimate.
          Investigate (Chapter 4).

  Seeing HASH JOIN on large tables
      ──► normal and usually correct.

  Seeing MERGE JOIN
      ──► usually means indexes provided the
          ordering. Generally a good sign.

  Seeing HASH JOIN with many BATCHES
      ──► it spilled. Raise work_mem, or reduce the
          rows reaching the join.
─────────────────────────────────────────

6. Join Order

With several tables, the order of joins usually matters more than the algorithm.

Why Order Dominates
─────────────────────────────────────────
  A ⋈ B ⋈ C, joined two at a time.

  If A ⋈ B produces 10 rows and those join to C:
      cheap.

  If A ⋈ C produces 10,000,000 intermediate rows
  and those join to B:
      expensive, even though the final answer is
      identical.

  The goal is to keep INTERMEDIATE results small —
  join the most restrictive pair first.
─────────────────────────────────────────

The Search Space
─────────────────────────────────────────
  n tables have roughly n! join orders, times the
  algorithm choice at each step.

    3 tables ──► manageable
    6 tables ──► thousands of plans
   12 tables ──► astronomically many

  So optimisers use DYNAMIC PROGRAMMING (build up
  the best plan for each subset of tables) up to a
  threshold, then switch to a GENETIC or heuristic
  search beyond it.

  PostgreSQL's threshold is geqo_threshold,
  default 12 tables.
─────────────────────────────────────────

What This Means for You
─────────────────────────────────────────
  BELOW the threshold, the optimiser searches
  exhaustively and your written join order is
  irrelevant.

  ABOVE it, the search is heuristic and may miss
  the best plan. Very large joins are where plans
  become unpredictable — one more reason to keep
  queries to a manageable number of tables, or to
  break them up with CTEs.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

• Indexed nested loop turns a quadratic join into |outer| × log|inner|, and is the right choice when the outer side is small and the inner is indexed.
• Hash join is linear and is the default for large equality joins, but blocks on its build side and cannot handle inequalities.
• Sort-merge join is competitive only when indexes supply the ordering for free, and is the only algorithm that handles inequality joins well.
• Join order matters more than algorithm choice because it determines intermediate result sizes; optimisers search exhaustively only below a table-count threshold.

Concept Check

1. Why is a nested loop join over two large unindexed tables almost always a sign of a problem?
2. What does "Batches: 8" in a hash join's plan tell you, and what are the two fixes?
3. Why can join order matter more than which join algorithm is used?

Next Chapter

→ Chapter 3: Cost-Based Optimization

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index