From SQL to execution plans
A declarative SQL query says what you want. The database must decide how to get it, translating the query into an executable plan of physical operators.
The pipeline
Query processing runs in stages. The parser checks syntax and builds a parse tree. The binder or analyser resolves table and column names against the catalogue and checks types and permissions. The rewriter expands views and simplifies expressions. The optimiser chooses an efficient execution plan, and the executor runs it and returns rows.
Logical and physical plans
A logical plan expresses the query in relational algebra: selections, projections, joins, and aggregations, with no decisions about method. A physical plan chooses specific algorithms for each operator, such as an index scan or sequential scan for a table, and hash join or merge join for a join, plus the order in which to join tables.
Access paths
To read a table, the executor can perform a sequential scan, reading every page in order; an index scan, walking an index and fetching matching rows; an index-only scan, answering from the index alone; or a bitmap scan, collecting matching row locations from one or more indexes, sorting them by page, and fetching each page once. The best choice depends on selectivity and data layout.
The iterator model
Many executors use the iterator or Volcano model, described by Goetz Graefe in the early 1990s: every operator offers open, next, and close. The top operator repeatedly calls next on its children, pulling rows up the plan one at a time. Operators such as filters and projections pipeline rows without storing them; others, such as sorts, must consume all input before producing output.
Vectorised and compiled execution
Pulling one row at a time incurs overhead per row. Vectorised executors, common in analytical systems, process batches of thousands of values at once, using CPU caches and vector instructions efficiently. Other systems compile query plans into machine code, removing interpretation overhead. Both approaches can be many times faster for large scans.
Reading a plan
EXPLAIN prints the chosen plan as a tree, with estimated costs and row counts for each node; EXPLAIN ANALYZE also runs it and reports actual times and rows. Large gaps between estimated and actual row counts often explain bad plans. Reading plans from the innermost, most indented nodes outwards follows the flow of data.
Prepared statements and plan caching
Parsing and optimising a query takes time, so applications can prepare a statement once and execute it many times with different parameters. The database may cache a plan for reuse. A cached generic plan can be poor for unusual parameter values, such as a very common versus a very rare customer, so some systems re-plan based on actual parameters.
Worked example
SELECT name FROM customers WHERE city = 'Lima' ORDER BY name. The parser builds a tree; the binder confirms customers has city and name; the optimiser estimates that 0.2% of 2,000,000 rows, about 4,000, match, and chooses an index scan on city followed by a sort of 4,000 rows, rather than scanning all 2,000,000 rows. EXPLAIN ANALYZE would show the actual matching row count to confirm the estimate.
Key takeaways
Queries pass through parsing, binding, rewriting, optimisation, and execution. Logical plans state relational operations; physical plans pick algorithms and join orders. Access paths include sequential, index, index-only, and bitmap scans. The Volcano iterator model pulls rows through open, next, and close; pipelined operators stream rows, while sorts block. Vectorised and compiled execution reduce per-row overhead. EXPLAIN and EXPLAIN ANALYZE reveal plans and estimation errors. Prepared statements reuse plans but may suit some parameters poorly.
Flashcard
Checks syntax and builds a parse tree
Check your understanding
In EXPLAIN ANALYZE output, the optimiser estimated 10 rows for a scan but 500,000 were returned. What does this suggest?