Inside the Query Engine
A SELECT is a request, not a program. Seven stages turn it into one: parser, binder, planner, optimizer, executor and storage — each with its own data structure and its own way of failing.
Why this exists
The mechanism as the answer to a problem — read this before the name.
- Problem
The caller says
SELECT name FROM users WHERE id = 42and expects one row. The engine has 8 KB pages, B+ trees and a buffer pool — nothing that understands the word SELECT.↓ - Naive solution
Hard-code a procedure per query shape: a function that scans users and compares id. Every new query is new code in the engine.
↓ - Why it breaks
There are infinitely many queries, and the best procedure for one of them changes as the data grows: at 900 rows a scan is right, at 9 million an index descent is. The procedure cannot be fixed at write time.
↓ - Better idea
Separate the *what* from the *how*: parse the text into a structure, then let the engine invent a procedure for it at run time, choosing among alternatives by estimated cost.
↓ - Internal mechanism
A pipeline. Lexer and parser build an AST; the binder resolves names against the catalog; the planner enumerates candidate plans; the optimizer costs them and keeps the cheapest; the executor runs the plan as a tree of iterators pulling rows with
next(); the storage engine serves pages.↓ - Trade-offs
Planning costs time on every execution — microseconds for simple statements, milliseconds for ten-table joins — and the plan is only as good as the statistics. Prepared statements and plan caches trade freshness for that time.
↓ - Real database
PostgreSQL: parser → analyzer → rewriter → planner/optimizer → executor, in
src/backend/parser,optimizerandexecutor. This platform’s engine insrc/db/sqlhas the same shape with the rewriter folded into the planner.
Choose your depth
The same mechanism at four altitudes. Start where you are; come back deeper.
SQL describes the result you want; it says nothing about how to get it. The query engine is the part of the database that invents the how: it checks the text, works out which tables and columns you mean, considers several ways of computing the answer, picks the one it estimates to be cheapest, and runs it.
That is why the same query can be fast on Monday and slow on Friday without a line of code changing: the data changed, the estimates changed, and the engine invented a different procedure.
The seven stages
A statement passes through seven stages, and every one of them has a data structure of its own. The parser turns text into tokens and tokens into an abstract syntax tree. Semantic analysis — the binder — resolves every name in that tree against the catalog: users becomes a table object with a row count and a column list, id becomes column 0 of type int, and id = 42 is type-checked. The planner enumerates ways of computing the result: for each table its access paths (sequential scan, each usable index), for each join its order and method. The optimizer attaches an estimated cost to each candidate and keeps the cheapest. The execution engine turns the chosen plan into a tree of operators and pulls rows through it. The storage engine serves the 8 KB pages the leaves ask for.
The stages are ordered by how cheaply they fail. A syntax error is caught in microseconds by the parser; an unknown column costs a catalog lookup; a bad plan costs the whole execution. Which is also why an unknown column is *not* a syntax error: SELECT nmae FROM users is perfectly grammatical, and only the binder — with the catalog in hand — can reject it.
stage in out can fail with ------------------ ---------------------- -------------------------- ------------------------------- 1 SQL text bytes on the wire string (transport only) 2 Parser string tokens → AST syntax error at position n 3 Semantic analysis AST + catalog bound tree (oids, types) unknown relation / column, type 4 Planner bound tree + stats candidate plan trees (always produces something) 5 Optimizer candidates + constants one plan wrong plan from stale statistics 6 Execution engine plan rows, one next() at a time work_mem exceeded, timeout 7 Storage engine page requests 8 KB pages via buffer pool I/O error, cache miss latency
The executor: a tree of iterators
The chosen plan is a tree — Limit above Sort above HashAggregate above Hash Join above two scans — and the executor runs it as a tree of iterators. Every operator implements the same three calls: open(), next() and close(). The client asks the root for a row; the root asks its child; the request descends to a leaf, which reads a page and returns the first row; the row climbs back up, transformed by each operator on the way. This is the Volcano model (Graefe, 1994), and it is why the executor can be built from a dozen small operators that know nothing about each other.
The model has one consequence that shows up in every EXPLAIN: some operators are pipelined and some are pipeline breakers. Filter, Projection, Limit and Nested Loop pass rows through as they arrive, so a LIMIT 10 above them stops the whole plan after ten rows. Sort, HashAggregate and the build side of a Hash Join must consume *everything* before they can emit anything, so a LIMIT 10 above a Sort still sorts the full input. Whether the plan puts the breaker below or above the cheap operators is the difference between a millisecond and a minute.
The price of Volcano is a virtual call per row per operator — at ten operators and ten million rows, a hundred million function calls that do almost nothing each. Vectorised executors pass batches of a few thousand column values between operators instead, so the work happens in tight loops over arrays that stay in the CPU cache. Analytical engines (DuckDB, ClickHouse, Velox) are vectorised; PostgreSQL is row-at-a-time with JIT compilation of expressions as a partial answer.
1interface Operator {2 open() // acquire resources, open children3 next(): Row|null // pull one row from children, transform, return it4 close()5}6 7// Filter: pipelined — passes rows as they arrive8Filter.next():9 loop:10 row = child.next()11 if row == null: return null12 if predicate(row): return row13 14// Sort: pipeline breaker — must see everything first15Sort.next():16 if not sorted:17 rows = []; while (r = child.next()) rows.push(r)18 rows.sort(byKey); sorted = true; i = 019 return i < rows.length ? rows[i++] : nullWhere prepared statements and plan caching sit
Stages 2 to 5 are pure functions of the text, the catalog and the statistics. If the same statement runs a thousand times per second with different parameter values, doing that work a thousand times is waste. A prepared statement (PREPARE, or the extended protocol every driver uses under the hood) keeps the output of parsing and binding — the bound tree — and re-runs only planning and execution with the new parameter values.
A plan cache goes one step further and keeps the plan. The catch is the parameter: a plan chosen for WHERE status = 'refunded' (0.5% of rows, index scan) is wrong for WHERE status = 'paid' (62%, sequential scan). PostgreSQL resolves this with a heuristic: the first five executions of a prepared statement get a *custom plan* built for the actual value; after that, if a *generic plan* that ignores the value is not estimated to be worse, it is cached and reused. On skewed data that switch is a classic source of "the query got slow on the sixth call". plan_cache_mode = force_custom_plan turns it off per session.
The storage boundary
Nothing above the leaves of the plan knows about pages. A Seq Scan asks the storage engine for page 0, page 1, page 2 of the heap file; an Index Scan asks for the root page of a B+ tree, then a branch, then a leaf, then heap pages by tuple id. Every request goes through the The Buffer Pool: a hit costs a hash lookup and a pin, a miss costs a real read and an eviction. This is why the cost model bothers to distinguish a sequential page (1.0) from a random one (4.0), and why EXPLAIN (BUFFERS) reports shared hits and reads separately.
The boundary runs the other way too. The executor never rewrites a page; an UPDATE produces a new tuple version through the same operator tree (a ModifyTable node above a scan), and the storage layer appends to the Write-Ahead Logging before the page changes. Reads and writes share the pipeline; only the leaves differ.
Key points
- SQL is declarative; the query engine is a compiler that invents a procedure for each statement at run time, using statistics to choose among alternatives.
- Seven stages, each with its own artefact: string → tokens → AST → bound tree → candidate plans → chosen plan → rows. A stage can only report the errors its artefact can express — the parser cannot know that a column is missing.
- The executor runs the plan as a tree of iterators (Volcano): each operator pulls rows from its children with next(). Pipelined operators stream; Sort, HashAggregate and hash builds block.
- Vectorised executors pass batches instead of rows to amortise the per-row overhead; that is the main architectural difference between an OLTP engine and an analytical one.
- Prepared statements skip parsing and binding; plan caches also skip planning, at the risk of a generic plan that ignores parameter skew.
- Leaves talk to storage only in pages, through the buffer pool. Every cost the optimizer counts is ultimately a page read or a row handled.
SQL → parser → planner → executor → storage
SELECT name FROM users WHERE id = 42
- ↓
- ↓
- ↓
- ↓
- ↓
- ↓
The lexer cuts the string into tokens; a recursive-descent parser consumes them according to the grammar and builds an abstract syntax tree. Precedence (`AND` below `=`, `*` above `+`) is decided here and never revisited.
8 tokens: SELECT · name · FROM · users · WHERE · id · = · 42
6 AST nodes
select
└── core
├── columns[1]
│ └── item
│ └── expr: col name="name"
├── from: table name="users"
└── where: bin op="="
├── l: col name="id"
└── r: lit v=42Try it in the playground
EXPLAIN ANALYZE SELECT id, name FROM users WHERE email = 'jonas.olsen7@example.com';
EXPLAIN ANALYZE SELECT id, total FROM orders ORDER BY created_at DESC LIMIT 5;
When to use — and when not
- This architecture fits when queries are ad hoc and data sizes change — the cost of planning is repaid by not hard-coding the procedure.
- The iterator model fits transactional workloads: low latency to the first row, LIMIT stops early, memory stays bounded per operator.
- Vectorised or compiled execution fits better when scans touch billions of rows and the per-row call overhead dominates — analytical engines.
- A key-value store that needs only
get(key)has no use for a planner; the procedure is always the same.
Failure modes
- A plan cached from early executions (generic plan) applied to a skewed parameter value — the sixth call is 100× slower than the first five.
- A pipeline breaker placed below a LIMIT: the whole input is sorted or hashed to return ten rows.
- Treating parse-time success as correctness: the statement parsed, the binder rejected it, the application retried in a loop.
- Reading estimated cost as milliseconds. Cost units rank alternatives within one plan; they do not predict wall-clock time.
Where you meet this
Back up to the practical layer, and across to the rest of Engineer Atlas.
- CompilersFront end / middle end / back end → Parser + binder / planner + optimizer / executorA query engine is a compiler whose target language is a tree of iterators, compiled anew on every execution.
- DSATree traversal → Iterator model (pull-based next())