Skip to content

CONCEPT Cited by 1 source

Fixed-point tree rewriting

Definition

Fixed-point tree rewriting is a convergence discipline used by query planners (and compilers) in which a set of rewrite rules is applied to a plan tree repeatedly, in a full-tree pass, until a complete pass produces no changes. The state where no rule fires is the fixed point — the tree is stable under the active rewriter set.

Andres Taylor's canonical wiki framing (Source: sources/2026-04-21-planetscale-optimizing-aggregation-in-the-vitess-query-planner): "During the planning phase, we perform extensive tree rewriting to push as much work down under Routes as possible. This involves repeatedly rewriting the tree until no further changes occur during a full pass of the tree, a state known as the fixed-point."

Why fixed-point

A single pass is insufficient when rewrites compose:

  • Rewrite A transforms node X → Y, exposing a new shape that matches rewrite B's precondition.
  • Rewrite B fires on the new Y, producing Z.
  • Z may expose a new shape matching rewrite A again.

Orchestrating this manually (chaining rules in the right order) is fragile and brittle to new rule additions. The fixed-point loop abstracts the orchestration: you specify the rules, the loop runs them until convergence, and any correct-individually rule set produces a correct plan if the loop terminates.

Why it terminates

Fixed-point termination requires a well-founded order — each rewrite makes progress on some metric that can only decrease finitely. For Vitess-style pushdown rewriters, the metric is typically "depth at which operations live relative to the leaves" — pushing operations further down the tree is monotonic in a specific direction, so a rewriter that fires eventually exhausts its opportunities.

For rewriters that might loop (A followed by a reverse-A), the loop diverges. Planner authors must ensure the rewriter set has a common termination metric — a design discipline, not an automatic property.

Composition with phases

A planner using phase ordering runs fixed-point convergence per phase. Taylor: "After completing a phase, we run the push-down rewriters, then move to the next phase, and so on" (Source: sources/2026-04-21-planetscale-optimizing-aggregation-in-the-vitess-query-planner).

  • Within a phase: loop until fixed-point over that phase's active rewriter set.
  • Across phases: proceed sequentially; each phase can enable a new rule that the previous phase had gated off.

The two layers together form a two-level fixed-point: phase-level loop until fixed-point under the full (union-of-phases) rewriter set, achieved by composing per-phase fixed-point loops in sequence.

Diagnostic value

Fixed-point semantics are helpful for debugging planner bugs because any intermediate tree during the loop is a valid (if unoptimised) plan. Printing tree snapshots at each loop iteration (the "plan trace") lets the author trace exactly which rewrite introduced a pathological shape. Taylor's 2024-07-22 post shows this technique — three snapshots of the plan tree, progressing from initial expansion → post-first-rewriter-pass → final (after phase-ordering fix).

Alternative architectures

  • Single-pass top-down — fast but requires manually-ordered rules. Fragile to new rule additions.
  • Volcano / Cascades memo-based search — cost-based, explores alternative plans via a memo structure. Much more expressive for cost-based planning; much more expensive to implement and debug. Calcite, SQL Server, Spark Catalyst use Cascades-style.
  • Heuristic cost-based over fixed-point-rewriting — Vitess's approach. Fixed-point loop for structural rewrites; heuristic rules (rather than a full cost model) to decide which of multiple valid plans to pick. Trade-off: simpler to implement, harder to extend to cost-based decisions.

Seen in

  • sources/2026-04-21-planetscale-optimizing-aggregation-in-the-vitess-query-planner — canonical wiki introduction. Andres Taylor (PlanetScale / Vitess core, 2024-07-22) canonicalises fixed-point tree rewriting as the convergence discipline the VTGate planner uses within each phase. The 2024 OOM incident demonstrates that fixed-point within one phase is insufficient when two rewrites interfere — the fix composes fixed-point per phase with phase ordering to break the interference.
Last updated · 378 distilled / 1,213 read