Module 19 · Storage, indexing and recovery · Lesson 3 of 4
Query processing and join algorithms
What happens between SQL text and results: parsing, logical and physical plans, the iterator execution model, scans, external sorting, nested-loop, hash and sort-merge joins with their costs.
Why it matters
Two logically identical queries can differ in runtime by a factor of a thousand depending on the plan the database chooses. Understanding how plans are built and executed lets you read EXPLAIN output, predict when a hash join beats a nested loop, and see why bad row estimates produce disastrous plans. The System Design track's query optimization lesson covers the practical method; this lesson covers the machinery it relies on.
The idea
A query goes through a pipeline before any data moves.
- 1
Parse and bind
Check syntax, resolve tables and columns against the catalogue, check permissions. - 2
Rewrite
Apply rules that are always beneficial: expand views, flatten subqueries into joins, push selections and projections down, remove redundant conditions. - 3
Optimize
Enumerate alternative physical plans (join orders, join algorithms, access paths) and estimate each one's cost from table statistics; keep the cheapest. - 4
Execute
Run the chosen plan, a tree of physical operators.
The iterator model
Most engines execute plans as a tree of operators that each implement open, next and close (the Volcano or iterator model). The root asks its child for the next row, which asks its children, and rows flow up one at a time. Operators that can produce rows as they consume them (scans, filters, nested-loop joins) pipeline; operators that must see all input first (sort, the build side of a hash join, aggregation) are blocking. Analytical engines process batches of rows per call (vectorised execution) or compile plans into machine code to cut per-row overhead.
Access paths
| Access path | Reads | Best when |
|---|---|---|
| Sequential (full) scan | Every page of the table, in order | A large fraction of rows qualifies, or there is no useful index |
| Index scan | Index pages plus a table page per matching row (random I/O) | Few rows qualify (high selectivity) |
| Index-only scan | Index pages only | The index covers every needed column |
| Bitmap index scan | Collect matching row ids, sort by page, then read pages in order | Moderate selectivity, or combining several indexes |
Sorting data larger than memory
ORDER BY, DISTINCT, GROUP BY and sort-merge joins may need to sort more data than fits in memory. External merge sort reads memory-sized chunks, sorts each and writes them as sorted runs, then merges runs in passes. With B pages of memory and N pages of data, there are about N/B initial runs, and each merge pass combines B − 1 runs, so a few passes suffice even for huge inputs. This is why raising sort memory (work_mem, sort_buffer_size) can turn a multi-pass disk sort into an in-memory one.
Join algorithms
Let R be the outer table with M pages and S the inner with N pages.
| Algorithm | How it works | Approximate cost (page I/Os) | Best when |
|---|---|---|---|
| Simple nested loop | For each row of R, scan all of S | M + rows(R) × N | Never, except tiny tables |
| Block nested loop | For each memory-sized block of R, scan S once | M + ⌈M / (B − 2)⌉ × N | No index and no equality condition |
| Index nested loop | For each row of R, look up matches in an index on S | M + rows(R) × (index lookup cost) | Small outer input and an index on the inner join key |
| Sort-merge join | Sort both on the join key, then merge in one pass | Sort costs + M + N | Inputs already sorted, or output must be sorted; equality or range joins |
| Hash join | Build a hash table on the smaller input, probe it with the larger | About 3 × (M + N) with partitioning if the build side spills, M + N if it fits | Large equality joins with no useful order |
Choosing a plan
The optimizer estimates cardinalities (how many rows each operator produces) from statistics: row counts, distinct values, histograms and most-common values per column. From cardinalities it estimates I/O and CPU cost. For joins it must pick an order: with n tables there are factorially many orders, so optimizers use dynamic programming over subsets (System R style) for moderate n, usually restricted to left-deep trees, and heuristics or genetic search beyond that. Estimation errors compound across joins: assuming two filters are independent when they are correlated can underestimate rows by orders of magnitude, leading to a nested loop where a hash join was needed. Fresh statistics, extended statistics for correlated columns, and checking estimated versus actual rows in EXPLAIN ANALYZE are the practical defences.
Trade-offs
Nested loops start returning rows immediately and excel with small outer inputs and indexes; hash joins dominate large equality joins but need memory and block on the build side; sort-merge joins win when inputs are already ordered. Cost-based optimization usually finds good plans quickly, at the risk of terrible plans when statistics mislead it. Pipelined execution saves memory; blocking operators are sometimes unavoidable.
In an interview
Explain a plan choice with numbers: "Joining a 50-row filtered department set to a 10-million-row employee table with an index on dept_id: an index nested loop does 50 index lookups, effectively instant. Joining two unfiltered 10-million-row tables on a non-indexed key: a hash join building on the smaller one, a few full scans. If the optimizer picked a nested loop for the second, I would check its row estimates, because it probably thought one side was tiny."
Check yourself
A query joins two large tables on an equality condition, neither input is sorted, and there is no index on either join column. Which join algorithm will a good optimizer usually choose?