Skip to content

Query-Plan Lowering and Optimization

Optimizing lowering method — instantiates Specification-to-Execution Lowering

Lowers a declarative query into a physical execution plan, letting a cost model choose freely among result-equivalent plans — not just a correct plan, the cheap one.

A query states what rows are wanted; it says nothing about how to get them. Query-Plan Lowering and Optimization is the level shift that turns that declarative statement into a concrete physical plan — which join algorithm, which index, in what order — and its defining feature is that the lowering is deliberately non-deterministic: for one query there are many result-equivalent plans, and the mechanism's job is to search that space and pick a cheap one, not merely a correct one. Correctness is a floor every candidate already meets; all the value is in the freedom above that floor. That is what separates it from the archetype's other lowerings, which labour to produce a faithful implementation — here fidelity is guaranteed across the whole plan space by construction, and the effort goes into choosing well within it.

Example

An analytics query joins a 500-million-row orders table to a small customers table and filters on a date range. Written naively it reads as "join everything, then filter." The optimizer lowers it through a ladder of representations: parse to a logical algebra tree, then explore equivalent forms — push the date filter below the join so it runs first, reorder the join so the small table drives, and choose between a hash join and an index-nested-loop depending on whether a usable index exists. Every rewrite is drawn from a set of equivalence-preserving transformations, so all candidates return identical rows. A cost model then scores plans using the engine's own statistics — table sizes, index selectivity, memory — and picks the cheapest: filter-then-hash-join here, estimated to touch a few million rows instead of five hundred million. The author wrote none of this and does not need to; they stated the what, and the optimizer chose the how.

How it works

  • Lower through a representation ladder. Parse the query to a logical plan (relational algebra), then to a space of physical plans; the levels cleanly separate what is computed from how.
  • Generate equivalent alternatives. Apply equivalence-preserving rewrites — predicate pushdown, join reordering, operator selection — to enumerate (or sample) the plan space.
  • Cost against the substrate. Score candidates with a cost model driven by the engine's statistics and available operators; correctness is invariant across them, cost is not.
  • Emit the chosen plan. Hand the lowest-cost physical plan to the execution engine.

Tuning parameters

  • Search budget — exhaustive vs. heuristic, pruned enumeration. More search finds cheaper plans but costs planning time; for a short query the search can cost more than it saves.
  • Cost-model fidelity — simple cardinality heuristics vs. detailed statistics and histograms. Better models pick better plans, but only if the statistics they read are fresh and accurate.
  • Optimization freedom — how many transformations the optimizer may apply (join reordering on/off, which operators are in play). Wider freedom finds faster plans and enlarges the space where a bad estimate can mislead it.
  • Re-planning policy — plan once and cache vs. re-optimize as data and statistics change. Caching saves planning cost; a cached plan degrades as the data shifts underneath it.

When it helps, and when it misleads

Its strength is that it lets people write intent and still get performance, adapts one query to different data shapes and hardware without a rewrite, and captures decades of execution expertise in a reusable optimizer that most users never think about.

Its failure modes rest on the cost estimates, and estimates come from statistics that go stale. A wrong row-count guess can pick a plan orders of magnitude worse than the naive one, and the failure is silent — the answer is right, just slow.[1] The plan space grows combinatorially, so the optimizer trades true optimality for tractable search and can miss the best plan entirely. The classic misuse is over-trusting the optimizer as a black box, then hand-forcing plan hints to rescue one bad query — hints that quietly rot as the data changes. The discipline is to keep statistics fresh and to treat a pathological plan as a signal to fix the cost inputs, not as a reason to override the mechanism.

How it implements the components

  • intermediate_representation_ladder — the logical-plan → physical-plan levels that separate what is computed from how, the staging on which all optimization operates.
  • optimization_freedom_budget — its signature: the space of result-equivalent plans the optimizer is licensed to choose among, and how much of that space to search.
  • target_substrate_profile — the engine's physical operators, indexes, and statistics, which the cost model reads to score plans for this substrate rather than an abstract one.

It does not prove each rewrite meaning-preserving with a shipped certificate (semantic_correspondence_contract, proof_and_test_obligation_set — that's Proof-Carrying Transformation); the equivalence of its transformation rules is assumed by construction, and its effort goes to cost, not to proof.

Notes

The mechanism assumes its rewrite rules are equivalence-preserving; if a transformation rule is buggy, the optimizer will happily pick a fast plan that returns the wrong rows, and nothing in the cost model would catch it. Validating the rule set itself is a separate concern that belongs to Translation-Validation Harness or Proof-Carrying Transformation — this mechanism optimizes given a trusted set of equivalences.

References

[1] Cardinality estimation — predicting how many rows each operator produces — is the well-known weak point of cost-based optimization: errors compound up the plan tree and are the usual reason a "good" optimizer chooses a catastrophically slow plan. It is why keeping table statistics current matters more than any single tuning knob. ↩