A Simple Query Planner: Choosing an Index and a Join Strategy

Building a Database Engine: Transactions & Concurrency

Chapter 9 · A Simple Query Planner: Choosing an Index and a Join Strategy

Every chapter so far has left a choice to the caller: use an index or scan (Course 1, Chapter 9), nested-loop or hash join (Chapter 8, this course). A real planner makes that choice automatically, from real, measurable properties of the data — and, as this chapter finds out the hard way, the obvious way to estimate "which is cheaper" doesn't actually match reality until it's calibrated against real measurements.

The Obvious Cost Formula

def choose_join_strategy(n, m):
    nl_cost = n * m       # nested-loop: one comparison per (n, m) pair
    hj_cost = n + m       # hash join: one step per row, on each side
    return 'nested_loop' if nl_cost <= hj_cost else 'hash_join'
    

This predicts hash join wins as soon as n=m=3 (9 > 6). Real measurement says otherwise.

Finding 1: The Naive Formula Is Wrong at Small Scale

Verified directly — real, averaged timing (2,000 repetitions per size, to cut through microsecond-scale noise)

At n=m=3: nested-loop averages 0.47μs, hash join 0.60μs — nested-loop is actually faster, despite the formula predicting hash join. At n=m=5: the same mismatch. Pinpointing the real crossover precisely: nested-loop stays faster through n=m=6, and hash join only pulls ahead starting at n=m=7. The naive formula's own predicted crossover (n=m=3) misses the real one by a factor of more than 2×.

The reason: constructing a Python dict, hashing keys into it, and looking them up all carry real, non-trivial constant overhead the pure "count the operations" formula never accounts for. A handful of plain comparisons can genuinely be cheaper than building a hash table at all.

Finding 2: A Corrected, Empirically-Calibrated Formula

HASH_JOIN_OVERHEAD = 8   # calibrated against the real crossover measured above

def choose_join_strategy_corrected(n, m):
    nl_cost = n * m
    hj_cost = n + m + HASH_JOIN_OVERHEAD
    return 'nested_loop' if nl_cost <= hj_cost else 'hash_join'
    

Verified directly — every size, from n=m=2 through n=m=600, now matches real behavior

Re-checking every size tested — 2 through 600 — against the corrected formula: every single prediction matches the real, measured winner. A flat, real, measured constant folded into the cost estimate is enough to fix the small-scale mismatch entirely — for equal-sized inputs.

Finding 3: A Unified Planner, Measured Against a Naive Baseline

Combining Course 1's own index-vs-scan choice with this chapter's corrected join-strategy choice into one planner, and running it against a baseline that always scans and always uses nested-loop — on 1,500 customers and 3,000 orders.

Verified directly — a real, measured ≈110× aggregate speedup

300 point lookups: 0.71ms with the index vs. 37.53ms always scanning. One join: the planner correctly chose hash_join, running in 0.91ms vs. 140.96ms for the naive always-nested-loop baseline. Identical results both ways. Total: 1.62ms vs. 178.49ms — ≈110× faster overall, with the planner never once choosing wrong.

An Honest Limitation: No Predicate Pushdown

"Find customer 42's own orders" can be answered two ways: join everything, then filter for customer 42 — or filter customers down to just that one row first, then join only that row against orders.

Verified directly — filtering first is dramatically faster, and the planner never considers it

Join-then-filter on the full 1,500×3,000 tables (correctly using hash_join): ≈1ms. Filter-then-join, using the index to find customer 42 first, then joining just that one row against orders: ≈0.1-0.2ms — 5–9× faster for this specific, highly selective query. This chapter's own planner never considers this option at all: join_smart() always joins the full tables and estimates cost purely from their sizes, with no concept of checking whether a WHERE clause could shrink one side down before the join even starts. Real query optimizers call this predicate pushdown — a genuinely bigger, harder optimization than choosing an algorithm for a fixed order of operations, and a deliberate, honest scope boundary for this course's own simple planner.

Where This Connects

This chapter's finding	What it connects to
Naive operation-count formula wrong at small scale	Maths for Programmers: Numerical Methods & Floating-Point Computation — the same lesson that a clean theoretical model and real measured behavior can diverge, and only measurement resolves which is right
Choosing index vs. scan	Building a Database Engine: Storage & Query Fundamentals Chapter 9 (Course 1) — `choose_where_plan()` is that exact function, reused unchanged
No predicate pushdown	An honest, deliberate scope boundary — a genuinely bigger project than this "simple" planner, matching Course 1's own honest "no cost-based optimizer beyond simple heuristics" scope statement from Chapter 1

Hands-On Exercises

Exercise 1

Test the corrected formula against a genuinely asymmetric shape — a tiny table (2 rows) joined against a much larger one (2,000, then 20,000, then 100,000 rows) — rather than the equal-sized pairs this chapter calibrated against. Confirm whether the formula's own prediction still matches real, measured behavior, and explain what you find.

📄 View solution

Exercise 2

Run the same WHERE id = 777 lookup through both select() (index-aware) and select_naive() (always scans) against the chapter's own 1,500-row customers table. Confirm both return the exact same single row, and explain why an index changing HOW an answer is found should never change WHAT the answer is.

📄 View solution

Exercise 3

Run a range query (WHERE id > 1495) against the indexed customers table and confirm choose_where_plan() falls back to a full scan rather than using the index at all — even though the column has a real index built on it. Explain why, and what this planner would need to do differently to support it.

📄 View solution

Chapter 9 Quick Reference

The naive formula: n*m vs. n+m — reasonable in shape, wrong at small scale, verified reproducibly
Verified Finding 1: real crossover is at n=m≈7, not n=m=3 as the naive formula predicts — dict construction has real constant overhead
Verified Finding 2: a real, calibrated +8 overhead term matches every equal-sized test from 2 to 600 rows
Verified Finding 3: a unified index+join planner is ≈110× faster in aggregate than a naive always-scan/always-nested-loop baseline
Honest limitation: no predicate pushdown — the planner is blind to filtering one side down before a join, missing a real 5–9× win for selective queries
Next chapter: Capstone — a transactional, multi-table engine, bringing every chapter of this course together for the first time