Skip to content

CONCEPT Cited by 1 source

Runnable plan at every step

Definition

Runnable plan at every step is a query-planner architectural invariant: every intermediate state of the optimisation pipeline — not just the final output — is a complete, executable plan. Between any two pipeline phases, the current plan tree can be handed to the execution engine and produce the same result set as the final, fully-optimised plan would produce, only slower (and possibly much more expensive).

Andrés Taylor's canonical framing (Source: sources/2026-04-21-planetscale-optimizing-query-planning-in-vitess-a-step-by-step-approach): "In this new query planning model, every step in the optimization pipeline results in a runnable plan. This means that developers working on the planner can inspect the plan at any stage, allowing for a better understanding of the optimization process at each step. By having runnable plans at every step, it becomes easier to identify potential issues, inefficiencies, or areas where further optimization is possible."

What it contrasts with

Opaque-intermediate planners, where the bulk of the work lives in function arguments, local variables, and the call stack — not in an addressable tree structure. Taylor's description of Vitess's old model is the canonical example: "In the old model, we performed the optimization more in a top-down approach — we planned the full aggregation, and all ordering needed to support it, in one go. We would start with the join order tree, and do a lot of logic, and then output a new tree that performed the correct aggregations. In between the two, most of the current state was kept in arguments, local variables, and in the stack." The article's own diagram represents this as "Horizon Planning a little blurred, to show that it's difficult to inspect". The output is a runnable plan; the intermediate states are not.

Properties the invariant enables

1. Inspectability

Developers can print or visualise the plan at any phase boundary and see the full operator tree, not a partial structure + a Go stack frame. Phase-by- phase plan-tree evolution becomes a debugging artefact (see the article's four progressive snapshots of the worked example SELECT u.foo, ue.bar FROM user u JOIN user_extra ue ON u.uid = ue.uid ORDER BY u.baz).

2. Differential testability

Because every intermediate plan is runnable, the unoptimised plan and the fully optimised plan can both be executed on the same input and their outputs compared. Taylor: "Another benefit of this model is the possibility of running both the unoptimized plan and the optimized version and comparing their results. It should not matter if we have to evaluate a WHERE predicate on the VTGate side with our excellent evalengine support for most MySQL expressions, or if we can delegate it to the underlying database. The result should be the same." Divergence is a planner bug.

3. Incremental rewriter composition

A rewriter operates on a runnable-plan input and produces a runnable-plan output. Rewriter composition becomes function composition over a single type (operator tree), which supports fixed-point tree rewriting and phase ordering without each rewriter having to care about global pipeline state.

4. Cheap incremental evolution

New optimisations can be added as new rewriters without restructuring the pipeline. The pipeline diagram (Parse → Join Order → Horizon Planning → Offset Planning → Executable Plan) is stable under new optimisations because new rules plug into the existing horizon or offset phases as additional rewriters. Contrast with the old model where new optimisations meant carving new call-stack state + reasoning about interleaving with existing state.

Relationship to tree transformation granularity

The runnable-plan invariant is most cleanly achievable when each rewriter is a local tree transformation: takes two adjacent operators (parent + child) as input, produces a new subtree, splices it in. Taylor's canonical framing: "Each step is also simpler — it's a tree transformation taking two operators as input, one being the input of the other, and producing a new subtree that replaces the two inputs." Large, global rewrites (e.g. "plan the entire aggregation in one go") can also preserve the invariant, but they impose a correctness-proof burden on the rewriter author.

Why it matters beyond Vitess

The runnable-plan invariant is not Vitess-specific — it's the architectural stance behind Spark Catalyst's rule-based optimiser, Calcite's Hep planner, Snowflake's Datasketches-style planner. What's distinctive about Vitess's application is the pushdown boundary it has to model: every intermediate plan must be runnable both "locally at VTGate" and "across the shard fanout", and the runnable-plan property makes it possible to test both paths against each other. Engines without a pushdown boundary (single-node planners) benefit from the invariant, but the differential- testing lever is less dramatic.

Relationship to

Seen in

Last updated · 550 distilled / 1,221 read