Query Plan Rewriter¶
Cost-based optimizer tool — instantiates Equivalence-Preserving Rewrite Optimization
Rewrites a declarative query into one of many result-equivalent execution plans, then emits the plan a cost model estimates will be cheapest to run.
A SQL query says what rows you want, never how to get them — and the "how" can differ in cost by orders of magnitude. The Query Plan Rewriter (the optimizer at the heart of a database engine) closes that gap: it takes one declarative query and rewrites it into a space of result-equivalent execution plans — different join orders, join algorithms, index-versus-scan choices, where each filter is applied — then uses a cost model built on table statistics to estimate which plan is cheapest, and emits that one. Its defining trait, and what separates it from every other rewriter here, is that selection is driven by estimated cost over data it has only summarised: cardinalities, histograms, index selectivity. It does not run the candidates to find out; it predicts, and commits to the prediction.
Example¶
A reporting query joins orders, customers, and line_items, filters to one region and the last 30 days, and aggregates revenue. As written it reads as: join all three tables, then filter, then group — which, executed literally, materialises tens of millions of joined rows before throwing almost all of them away.
The rewriter explores equivalent plans instead. Predicate pushdown moves the region and date filters below the joins, so each table is cut down before it is joined. Join reordering starts from customers in the chosen region (an estimated few thousand rows) rather than from the giant line_items. Access-path selection switches the date filter to an index range-scan because statistics say it selects under 1% of rows. The cost model scores each candidate from estimated row counts and picks the cheapest; the emitted plan returns the identical result set having estimated it will touch a thousandth of the data. Same rows out, a fraction of the work — provided the estimates were right.
How it works¶
The rewriter enumerates plans provably result-equivalent under relational algebra — commuting and reassociating joins, pushing selections and projections down, swapping physical operators (hash join versus index nested-loop) — so every candidate returns the same rows. Over that space it runs a cost model: from cached statistics it estimates the cardinality flowing through each operator and converts that to an abstract cost (I/O plus CPU). Then a selection rule — usually cheapest-estimated-cost, under a search budget because the space explodes combinatorially — picks the winner. The engine acts on an estimate, which is the source of both its power and its fragility: the emitted plan is only as good as the cardinality guesses that ranked it.
Tuning parameters¶
- Statistics freshness — how current the histograms and row counts are. Stale statistics feed the cost model bad cardinalities and produce confidently-wrong plans; refreshing them costs maintenance time.
- Search budget — how much of the plan space the optimizer explores before committing. A wider search finds better plans but spends more planning time — a real cost for short queries.
- Cost-model weights — how I/O, CPU, and memory are priced relative to each other and to the hardware. Mis-weighting optimises for the wrong bottleneck.
- Plan stability versus freedom — whether to pin a known-good plan (hints, plan baselines) or let the optimizer re-choose as statistics drift. Pinning avoids surprise regressions; freedom adapts to new data.
- Estimation depth — single-column versus multi-column/correlated statistics. Modelling correlation improves multi-predicate estimates at the cost of far more statistics to maintain.
When it helps, and when it misleads¶
Its strength is that it makes declarative querying practical: humans write intent, the optimizer finds an efficient execution, and re-finds it automatically as data grows — delivering speed-ups no hand-tuning would sustain across changing tables.
Its fragility is that everything rests on estimated cardinalities, and estimation error compounds through a multi-join plan, so a single bad guess (a skewed column, correlated predicates the model assumes independent) can select a catastrophically slow plan with total confidence.[n1] The estimates are only as good as the statistics behind them, so stale stats silently degrade every plan. The classic misuse is trusting the chosen plan on faith and never checking realised cost; the corrective is to measure — with a Benchmark Harness or the engine's own runtime feedback — and to correct the statistics or pin a plan when estimate and reality diverge.
How it implements the components¶
Query Plan Rewriter fills the search-and-select components a cost-based optimizer owns:
candidate_rewrite_space— the space of result-equivalent execution plans (join orders, physical operators, access paths) it enumerates for a single query.orthogonal_cost_criterion— its cost model defines "cheaper" as estimated resource use (I/O plus CPU from cardinality estimates), the axis it optimises, held separate from whether the result is correct.selection_and_acceptance_rule— it accepts the minimum-estimated-cost plan found within its search budget and emits that one.
It does not author the relational-equivalence rules that make two plans return the same rows (Algebraic Simplification Rulebook is the catalogue analogue), it does not verify the chosen plan actually returns identical rows (Property-Based Equivalence Test, Golden-Output Regression Test), and it does not *measure realised runtime — its cost is an estimate, where Benchmark Harness measures.*
Related¶
- Instantiates: Equivalence-Preserving Rewrite Optimization — it is the automated, cost-driven rewriter specialised to declarative queries.
- Sibling mechanisms: Compiler Optimization Pass · Benchmark Harness · Algebraic Simplification Rulebook · Golden-Output Regression Test · Property-Based Equivalence Test
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Query Plan Rewriter operates as an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution because it rewrites a declarative query into one of many result-equivalent execution plans, then emits the plan a cost model estimates will be cheapest to run.
Independent corroboration: The frozen evidence defines Query Plan Rewriter as 'Rewrites a declarative query into one of many result-equivalent execution plans, then emits the plan a cost model estimates will be cheapest to run', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Specialized
Rationale: Equivalence-preserving query rewriting is a database and compiler optimization technique.
Related originating lineages:
- Mathematics — Relational algebra supplied formal equivalence laws.
- Operations Research — Cost minimization supplied selection among equivalent execution plans.
Review resolution: Both blind reviewers agree on computer_science as the primary origin. Explicit reconciliation resolves alternate_origin_disagreement, origin_mode_disagreement. The merged alternate lineages retain only domains the reviewers identified as materially formative; domain_reach=specialized records later applicability separately from origin breadth.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
The Query Plan Rewriter and the Compiler Optimization Pass are the archetype's two automated, cost-driven rewriters, and the contrast is instructive. The compiler rewrites imperative IR and can often prove legality by static analysis, but must model a complex machine; the query optimizer rewrites declarative relational algebra, where equivalence is comparatively easy, but must guess cost from statistics it cannot fully see. The compiler's hard problem is legality; the optimizer's hard problem is estimation.
[n1] Cardinality estimation — predicting how many rows flow through each operator — is the well-documented soft spot of cost-based query optimization: errors grow through successive joins and are the usual root cause when an optimizer picks a badly slow plan. It is why measured runtime feedback is the standard corrective. ↩