query-optimizer

How it is built

Architecture overview

A query optimizer takes a declarative query and decides how to run it: which indexes to read, in which order to join the tables, with which join algorithm. It cannot execute the candidates to compare them, so it scores each one with a cost model fed by estimated row counts, which come from statistics sampled earlier. The PostgreSQL planner is the running example. It builds a set of scan paths per table, joins them bottom-up by dynamic programming, keeps the cheapest path per set of tables and turns the winner into the plan tree the executor runs (source: PostgreSQL docs, planner/optimizer; optimizer README).

The classic split is cardinality estimation, cost model and plan enumeration. The best end-to-end measurement of the three is Leis et al. (VLDB 2015) on 113 multi-join queries: all tested estimators routinely produce large errors, the cost model matters much less than the estimates, and exhaustive enumeration still beats heuristics despite the bad estimates. That ordering sets this page's shape: most of the engineering goes into statistics, into plan choices that stay safe when estimates are wrong, and into a feedback loop that shows when they were.

Parts:

• Rewrites — normalise the query, push filters down, flatten subqueries before any costing — relational-algebra (no page yet), subquery-decorrelation (no page yet)
• Statistics — per-column samples: null fraction, distinct count, most common values, histogram — HyperLogLog, cardinality-estimation (no page yet)
• Cost model — page and CPU constants turn row counts into a number per path (no block in the graph; see gaps)
• Plan search — which join orders and shapes to consider — join-order-dynamic-programming (no page yet), cascades-query-optimization (no page yet)
• Physical operators — the choices the search costs — Hash join, Sort-merge join, B+ tree, External merge sort, Top-k selection, Bloom filter
• Execution style — what the chosen plan compiles to — Vectorized execution, query-compilation (no page yet), Columnar storage
• Feedback loop — plan capture, estimate-error metrics, regression tests — sibling systems metrics, logging, experimentation, continuous benchmarking

                                       ┌─ planner ────────────────────────┐          ┌──────────┐
 SQL ─► parse ─► analyze ─► rewrite ─► │ base paths ─► join search ─►     ├─ plan ──►│ executor │
                                       │ aggregate · sort · limit         │          └────┬─────┘
                                       └───────┬─────────────────┬────────┘               │ actual rows,
                                               ▲ row estimates   ▲                        ▼ time, I/O
 tables ─► ANALYZE (sample) ─► statistics ─────┘           cost constants             logs · metrics

The executor is a separate system (the query engine); the optimizer's contract with it is the plan tree and the estimates attached to each node, which EXPLAIN prints next to the actual numbers.

How the parts fit together

Rewrites

Rewrites are cost-agnostic: they are always worth doing, so they run before the search and shrink it. The PostgreSQL pull_up_sublinks turns ANY and EXISTS sub-selects into semijoins or anti-semijoins, which makes them ordinary join-order citizens (source: PostgreSQL source, prepjointree.c). Other sub-selects stay SubPlan nodes that the executor evaluates against the outer row (source: subselect.c), which is slow when the outer side is large. DuckDB takes the general route: a dedicated dependent-join flattening pass in src/planner/subquery/flatten_dependent_join.cpp, one of a long ordered list of passes (expression rewriting, filter pushdown, join order, top-N, statistics propagation) in its optimizer.cpp. CockroachDB makes the split explicit: Prep and Rewrite are cost-agnostic transforms, Search is the costed phase (source: CockroachDB pkg/sql/opt/doc.go). relational-algebra (no page yet) holds the equivalences these passes use.

The contract with the search: a list of base relations, restriction quals (a = 1) split from join quals (b = c), and a bounded problem size. PostgreSQL merges sub-queries and explicit joins into one flat list only up to from_collapse_limit and join_collapse_limit, both 8 by default; setting join_collapse_limit to 1 pins the written join order (source: PostgreSQL docs, runtime-config-query).

Statistics and cardinality estimates

ANALYZE samples 300 × the statistics target rows per column (source: PostgreSQL source, analyze.c), 30,000 rows at the default target of 100 (arithmetic), picking blocks first and then rows by Vitter's algorithm. From the sample it stores per column the null fraction, n_distinct, a most-common-values list with frequencies, and equal-frequency histogram bounds for the rest.

The PostgreSQL docs work these through on a 10,000-row table (source: PostgreSQL docs, row estimation examples):

• Range unique1 < 1000: the value falls into the second of 10 buckets, selectivity (1 + (1000 − 993)/(1997 − 993))/10 = 0.100697, rows 10000 × 0.100697 ≈ 1007.
• Equality on a most-common value: the stored frequency, 0.003, gives 30 rows. For a value not in the list: (1 − sum of MCV frequencies)/(676 − 10) = 0.0014559, 15 rows.
• Two conditions: the planner assumes independence and multiplies, 0.100697 × 0.0014559 gives 1 row.
• Equi-join: (1 − null_frac1) × (1 − null_frac2)/max(rows1, rows2) = 0.0001; with 50 outer rows, 50 × 10000 × 0.0001 = 50 rows.

The independence step is where estimates break. In the docs' multivariate example, two columns that determine each other give an estimate of 1 row where 100 come back; CREATE STATISTICS … (dependencies) fixes it (source: PostgreSQL docs, multivariate statistics examples). Leis et al. measure the general effect: PostgreSQL's base-table estimates are good (q-error median 1.00, 90th percentile 2.08, 95th 6.10, maximum 207), but across joins all systems underestimate result sizes more as the number of joins grows (source: Leis et al. 2015, Table 1 and Figure 3). Distinct counts are the other estimate that can be kept differently: HyperLogLog holds a distinct count in kilobytes, can be updated while data loads and merged across partitions, and DuckDB keeps one in its column distinct statistics (source: DuckDB distinct_statistics.cpp). cardinality-estimation (no page yet) covers the sketch and sampling options in general.

Cost model

Each path gets a startup cost and a total cost in arbitrary units, scaled to a sequential page fetch of 1.0. The PostgreSQL defaults: random_page_cost 4.0, cpu_tuple_cost 0.01, cpu_index_tuple_cost 0.005, cpu_operator_cost 0.0025 (source: PostgreSQL docs, runtime-config-query). A sequential scan of 345 pages and 10,000 rows costs 345 × 1.0 + 10,000 × 0.01 = 445 (source: PostgreSQL docs, using EXPLAIN). The docs say the constants are best treated as averages over the whole workload, and that changing them from a few experiments is very risky. The default 4.0 for random pages is justified by an assumption that most random reads hit cache.

Leis et al. found the cost model matters less than cardinalities: with true cardinalities injected, a tuned PostgreSQL model gave 41 % lower geometric-mean runtime and even a simple tuples-processed function 34 %, small next to what estimation errors cost. Hence the usual advice: fix statistics first, tune constants last.

Plan search

PostgreSQL builds one RelOptInfo per set of base relations and generates join sets level by level, pairs, then triples, and so on, so all paths for a set exist before any set containing it is built; paths for the same set compete by cost and sort order (pathkeys), and left-deep, right-deep and bushy shapes are all considered (source: optimizer README). Pairs with a join clause are preferred over cross products. Below geqo_threshold (default 12 FROM items) the search is near-exhaustive; above it a genetic search takes over and returns a reasonable, not necessarily optimal, plan (source: PostgreSQL docs, planner/optimizer and GEQO). For 12 tables there are 12! = 479,001,600 left-deep orders (arithmetic) but only 2^12 = 4,096 table subsets for the dynamic program to fill, which is why DP, not enumeration, is feasible. join-order-dynamic-programming (no page yet) covers DPccp and DPhyp.

DuckDB implements DPhyp ("Dynamic Programming Strikes Back", Moerkotte and Neumann 2008) with a work budget: after 10,000 emitted pairs it abandons exact search and falls back to greedy operator ordering (source: DuckDB plan_enumerator.cpp). That is the same compromise as GEQO with a deterministic fallback.

The alternative is a Cascades-style memo: groups of logically equivalent expressions, transformation and implementation rules, and top-down search that interleaves exploring and costing to prune (source: CockroachDB doc.go). cascades-query-optimization (no page yet) is the choice when the rule set is large and physical properties such as distribution matter; Apache Calcite, which applies planner rules guided by a cost model, and CockroachDB use it. For a pure join-order problem, DP is simpler. Tree shape matters less than one might fear in Leis et al.: with primary- and foreign-key indexes, left-deep-only search had a 95th-percentile slowdown of 2.49 over full search, right-deep-only 30,931 (Table 2).

Physical operators

The search costs a small menu of operators, each with a block page behind it:

• Hash join: the default for equi-joins, whose cost hinges on the build side's estimated size.
• Sort-merge join: wins when inputs arrive sorted, because pathkeys let an index scan provide the order for free.
• B+ tree index scans: priced with random_page_cost, so a bad row estimate flips scan versus index.
• External merge sort and Top-k selection: a Sort below a known LIMIT becomes a bounded heap (source: PostgreSQL tuplesort.c, bounded sort state).
• Bloom filter: a runtime filter built from the join's build side and applied to the probe-side scan; the optimizer decides when it pays. DuckDB's join-filter pushdown builds min/max filters from the build keys (source: DuckDB join_filter_pushdown_optimizer.cpp).

Risk matters more than average cost here. Leis et al. found most timeouts under PostgreSQL's estimates were nested-loop joins chosen because a join result was underestimated; disabling plain nested-loop joins (index nested loops kept) removed all timeouts and made no query slower. Prefer the operator whose worst case is bounded.

Execution style

Whether the plan then runs through vectorized operators over columnar batches or through compiled code (query-compilation, no page yet; Neumann, VLDB 2011, compiles pipelines with LLVM) is partly the optimizer's call. PostgreSQL decides on JIT from the plan's estimated cost: jit_above_cost 100,000, with inlining and expensive optimisation above 500,000 (source: PostgreSQL docs, runtime-config-query). Compilation adds start-up time, so an overestimated cost can lead to compiling a short query.

Feedback loop

The planner never learns by itself, so the surrounding system must. EXPLAIN ANALYZE prints estimated and actual rows per node; the ratio is the q-error, the quantity Leis et al. report. auto_explain logs plans of statements slower than auto_explain.log_min_duration (off by default), and pg_stat_statements keeps per-query counters keyed by a normalized-query id (source: PostgreSQL docs). Estimation error per node goes to a metrics system, plan text to the logs, constants and statistics-target changes to experiments, and a benchmark such as JOB (Leis et al.) to the CI gate. The sibling systems metrics, logging, experimentation and continuous benchmarking provide these parts.

Data and control flow

Planning one query

The docs' example: SELECT * FROM tenk1 t1, tenk2 t2 WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2.

1. Parse and analyze give a query tree; rewrites change nothing here.
2. Base-relation paths: for tenk1, a sequential scan and a bitmap index scan on unique1 < 50; selectivity 0.005035 from the histogram, 50 rows. For tenk2, scans and an index scan on unique2.
3. Join sizing: 50 × 10,000 × 0.0001 = 50 rows, estimated once for the pair, independent of the join method.
4. The join search costs nested-loop, merge and hash join in both directions; with 50 outer rows an index probe per row wins, giving a nested loop with an inner index scan (source: PostgreSQL docs, row estimation examples).
5. The cheapest path becomes the plan, and EXPLAIN prints each node's estimate beside its cost.

Statistics refresh changes a plan

1. A bulk load adds rows; reltuples is stale, but the planner scales it by the current page count.
2. Histograms and MCVs still describe the old data until ANALYZE (manual or automatic) re-samples.
3. After it, selectivities change, a join flips from nested loop to hash join, and the plan hash recorded by logging changes.
4. The feedback loop flags the changed plan; the metric to compare is runtime and q-error before and after.

Plan regression caught in CI

1. The benchmark suite runs queries against a fixed dataset and captures EXPLAIN text and runtimes.
2. A change to statistics code, a cost constant or a rule produces a different join order for one query.
3. The suite compares runtime against the stored baseline and reports the plan diff next to it.
4. The author either accepts the new plan with its numbers or fixes the estimate.

Scaling

In the order you would pull the levers:

1. Estimate quality. Raise the statistics target for the skewed columns, add extended statistics for correlated column groups; both cost ANALYZE time, which grows with the sample (300 × target rows).
2. Planning time. It grows with the number of joined tables; geqo_threshold, the collapse limits and DuckDB's pair budget bound it. Cache prepared plans where parameters allow it (plan_cache_mode picks between custom and generic plans).
3. Plan safety. Prefer operators with bounded worst cases; pin a join order with join_collapse_limit = 1 for a known-bad query; hints are a last resort.
4. Parallelism and JIT. Both are gated by cost thresholds (parallel_setup_cost 1000, parallel_tuple_cost 0.1, JIT 100,000); a better estimate improves both decisions.
5. Fleet scale. Per-query plan capture is too large to keep forever; keep plan hashes and the worst offenders by q-error.

Failure modes

Real implementations

Sources

• Selinger et al., Access path selection in a relational database management system, SIGMOD 1979 (the System R DP the PostgreSQL docs refer to)
• Moerkotte and Neumann, Dynamic programming strikes back, SIGMOD 2008
• Leis et al., How good are query optimizers, really?, PVLDB 2015 (DOI)
• Neumann, Efficiently compiling efficient query plans for modern hardware, PVLDB 2011 (DOI)
• PostgreSQL docs: Planner/Optimizer, Row estimation examples, Multivariate statistics examples, Using EXPLAIN, Planner method configuration, GEQO, auto_explain, pg_stat_statements
• PostgreSQL source: optimizer README, prepjointree.c, subselect.c, analyze.c, tuplesort.c
• DuckDB source: optimizer.cpp, plan_enumerator.cpp, flatten_dependent_join.cpp, distinct_statistics.cpp, join_filter_pushdown_optimizer.cpp
• CockroachDB optimizer design (doc.go), Apache Calcite algebra, DataFusion query optimizer guide