Joins: Nested-Loop & Hash Join

Building a Database Engine: Transactions & Concurrency

Chapter 8 · Joins: Nested-Loop & Hash Join

Chapter 7's own capstone joined customers to orders by hand — build a Python dict once, look each order up in it. That was already a hash join, just not named as one. This chapter builds two real join algorithms properly, verifies they agree with each other exactly, measures a real speed difference at scale, and finds a genuine correctness bug hiding in the "obvious" way to build a hash table.

Two Real Join Algorithms

def nested_loop_join(left_rows, left_key_idx, right_rows, right_key_idx):
    results = []
    for l in left_rows:
        for r in right_rows:          # a full inner scan for EVERY outer row
            if l[left_key_idx] == r[right_key_idx]:
                results.append((l, r))
    return results

def hash_join(build_rows, build_key_idx, probe_rows, probe_key_idx):
    hash_table = {}
    for row in build_rows:
        hash_table.setdefault(row[build_key_idx], []).append(row)   # a LIST per key
    results = []
    for probe_row in probe_rows:
        key = probe_row[probe_key_idx]
        for build_row in hash_table.get(key, []):
            results.append((build_row, probe_row))
    return results
    

Finding 1: The Two Algorithms Agree Exactly

Verified directly — identical result sets, real data

Three real customers, four real orders (Alice has two, Bob and Carol have one each), joined via nested_loop_join and hash_join: both find exactly 4 pairs, and as sets they're identical. Two structurally very different algorithms produce the same answer, as they must.

Finding 2: A Real, Measured 44× Speedup

Verified directly — real timing at 800 × 800 rows

Nested-loop join: 0.0147s. Hash join: 0.0003s — ≈44× faster, with identical result sets confirmed by set comparison. Nested-loop does a full 800-row inner scan for every one of 800 outer rows — ≈640,000 comparisons. Hash join builds one dict in 800 steps, then does 800 O(1) lookups — ≈1,600 steps total.

Finding 3: A Real, Silent Correctness Bug — Building on the Wrong Side

customers.id is unique — one row per id. orders.customer_id is not — Alice alone has two orders sharing the same key. The most natural first version of a hash join's own build step just assigns a key to a row, without thinking about what happens if that key shows up twice:

def hash_join_naive_overwrite(build_rows, build_key_idx, probe_rows, probe_key_idx):
    hash_table = {}
    for row in build_rows:
        hash_table[row[build_key_idx]] = row      # BUG: overwrites on a key collision
    # ...
    

Verified directly — one of Alice's two real orders silently vanishes

Building the hash table on orders (the duplicate-key side), keyed by customer_id: the naive version finds only 3 pairs, not 4. Order 100 ($50, one of Alice's own two real orders) is completely missing — silently overwritten in the dict by order 101, the last one inserted for customer_id=1. No error, no warning — just one fewer row in the final result than the true join actually has. Extending this with a customer who has three orders (Exercise 3) confirms the pattern generalizes: every duplicate past the first is silently dropped, not just one.

The fix is the same one shown in this chapter's own hash_join from the start: hash_table.setdefault(key, []).append(row) instead of a bare assignment. Every key maps to a list of rows, so a collision means "append," never "overwrite."

Finding 4: Once Fixed, Either Side Is Safe to Build On

Verified directly — correctness no longer depends on which side you pick

Building the correct, list-based hash table on customers (the unique-key side) and on orders (the duplicate-key side) both produce the exact same 4-pair result, confirmed by set comparison. The real-world advice to build a hash join on the smaller table is about performance and memory — not correctness. Correctness only depends on never assuming a key is unique on the build side unless it genuinely, provably is.

Where This Connects

This chapter's finding	What it connects to
Nested-loop's O(n×m) vs. hash join's O(n+m)	Maths for Programmers: Algorithms & Complexity — the exact same growth-rate reasoning, this time measured on a real join instead of an abstract example
A real customer, real orders, joined by real code	Chapter 7 (this course) — the manual dictionary-based join in that chapter's own capstone was already an unnamed hash join; this chapter names it, generalizes it, and finds the bug hiding in the shortcut version
"Confidently wrong is worse than a crash"	This site's own recurring theme — the naive hash join doesn't error, doesn't warn, just quietly returns fewer rows than the true answer

Hands-On Exercises

Exercise 1

Join a table of one customer against a table of one order whose customer_id doesn't match that customer's own id at all. Confirm both nested_loop_join and hash_join correctly return an empty result, with no error and no special-case handling needed in either.

📄 View solution

Exercise 2

Instrument both join functions to count real operations — every comparison for nested-loop, every build-plus-probe step for hash join — and run them against this chapter's own 3-customer, 4-order data. Confirm the counts match rows_left × rows_right and rows_left + rows_right exactly, not just approximately.

📄 View solution

Exercise 3

Give one customer three orders instead of two, and run the naive overwrite hash join built on the orders side. Confirm it now finds only 1 pair instead of the true 3, and explain why the number of silently dropped rows scales with the number of duplicates for that key, not capped at just one.

📄 View solution

Chapter 8 Quick Reference

Nested-loop join: a full inner scan for every outer row — O(n×m), correct by construction, no assumptions about key uniqueness needed
Hash join: build a dict from one side, probe from the other — O(n+m), but only correct if the dict maps each key to a list of rows
Verified Finding 1: both algorithms agree exactly on real customer/order data
Verified Finding 2: a real, measured ≈44× speedup at 800×800 rows, with identical results
Verified Finding 3: a naive overwrite-based hash join silently drops every duplicate-key row but the last one seen — no error, just fewer results
Verified Finding 4: once the hash table is list-based, either side is safe to build on — the "build on the smaller table" rule is about performance, not correctness
Next chapter: A Simple Query Planner — choosing an index and a join strategy automatically, verified against a naive always-scan baseline