Pass 2: offer only gcd tumbling-window widths; finer divisors are dominated #1171

Problem, by example

One dashboard panel, every 10 s, over a gauge with 10,000 series at 200,000 rows/s (crates/devtools/tests/sketch_plan_snapshots/workloads/quantile-single.json):

quantile_over_time(0.99, data[5m])      max_error 0.05, failure_probability 0.3

This issue uses the names from #1163 (SummaryTumblingWindowChain for today's PaneChain, tumbling_window_* for today's pane_*, TumblingWindows for the Panes origin, TumblingWindowWidthDomain for PaneWidthDomain). The outputs quoted from today's planner keep the old names.

Running stage_pipeline --workload quantile-single.json --text (#1159, at 0e8c928) prints this group after Pass 2:

G2:  Aggregate quantile(q=0.99)  <- G1
    [0]   Pass1  Aggregate quantile(q=0.99)                                                            inputs=[G1]
    [1]   Pass1  Project ← SummaryEstimate Quantile(q=0.99) ← SummaryAgg Kll(… k=86)                   inputs=[G1]
    [2]   Pass1  Project ← SummaryEstimate Quantile(q=0.99) ← SummaryAgg DDSketch(alpha=0.05)          inputs=[G1]
    [3]   Panes  … ← SummaryMerge ← PaneChain Kll(… k=86) pane_count=30 pane_width_ms=10000            inputs=[G0]
    [4]   Panes  … ← SummaryMerge ← PaneChain DDSketch(alpha=0.05) pane_count=30 pane_width_ms=10000   inputs=[G0]
    [5]   Panes  … ← SummaryMerge ← PaneChain Kll(… k=86) pane_count=120 pane_width_ms=2500            inputs=[G0]
    …
          (25 widths × 2 sketches = 50 tumbling-window candidates: every divisor of 10000 ms, down to 1 ms)

Stage 2 then builds 209 operator nodes and 260 physical candidates; Stage 3's MILP has 3125 variables and 7519 constraints.

A cheapest plan can only select the 10000 ms width. A SummaryTumblingWindowChain at 2500 ms keeps 120 tumbling windows per series instead of 30, and SummaryMerge merges 120 states per evaluation instead of 30. Each row still goes into exactly one tumbling window, so ingestion work is the same. The result is the same (exact accumulators) or no more accurate (sketches). Every width finer than 10000 ms costs more and buys nothing.

With two queries the same happens per sharing set. For sum_over_time(data[1m]) and sum_over_time(data[5m]), both every 10 s, Pass 2 adds 23 shared chain groups, from PaneChain pane_count=30 pane_width_ms=10000 down to pane_count=75000 pane_width_ms=4. Stage 3 hits its deadline (DeadlineReached, 29474 MILP variables, 72726 constraints), and the selected plan uses the 10000 ms chain.

What should happen instead: each sketch gets one SummaryTumblingWindowChain candidate, at tumbling_window_width_ms=10000. The two-query example gets one shared chain group, SummaryTumblingWindowChain tumbling_window_count=30 tumbling_window_width_ms=10000.

Why it happens

• The width domain. TumblingWindowWidthDomain (crates/logical-asap-optimization/src/pass2/memo/shared_configurations.rs) chooses which tumbling-window widths Pass 2 offers. Each query contributes its evaluation grid, evaluation_grid_ms(): the fixed interval, taken by gcd with a range query's step and with the evaluation phase.

  • SeedGrids: each query's grid, plus the gcd of every pair of widths in the set, repeated until no new width appears. For queries every 10 s and every 15 s, this is {5000, 10000, 15000}.
  • Expanding { max_parts }: SeedGrids plus each grid divided into at most max_parts equal parts.
  • Complete: every integer-millisecond divisor of every grid (tumbling_window_width_divisors_before). For a 10000 ms grid, that is 25 widths.

• The rule then intersects with the query window. tumbling_window_candidates (pass2/asap_aware_cse.rs) sets a build's width to the gcd of its query window and every reader's offered width. A 5 m window over a 10 s grid therefore gets 10000 ms.

• The planner ends with Complete. crates/planner/src/run.rs plans in rounds, each re-running Stage 1 to Stage 3 under the deadline:

  • one SeedGrids round;
  • then Expanding rounds from TumblingWindowWidthFrontier::next_domain, with max_parts 4, 8, 16, …;
  • then a final Complete round.

  The type's comment states the assumption: "Seed grids are only a feasible-plan heuristic; optimality must use the complete domain." stage_pipeline plans through the same rounds and prints the memo of the round whose plan was selected; for the example above that was the Complete round. Several tests (e.g. plan-selection/src/search/candidates/inventory.rs) call the rules with Complete directly.

Proposal

SeedGrids is the complete domain for tumbling-window widths. A tumbling-window chain serves a set of readers. Its width must divide each reader's query window and grid, and the largest width that does is their gcd. SeedGrids already contains that gcd, because its gcd closure covers every subset of readers that may share a chain. A width finer than that gcd is dominated:

• Same ingestion work: at any width, each row is inserted into one tumbling window.
• More state: query window / width tumbling windows per series.
• More query-time merging: query window / width states per evaluation.
• No accuracy gain: exact accumulators are exact at any width, and the planner's sketch error bounds do not improve with more merged tumbling windows.

The same argument holds for #1160's order (b), RawDataMerge ← RawDataTumblingWindowChain: a finer raw-data chain keeps the same rows in more tumbling windows.

Changes:

1. The planner plans once, with SeedGrids. In run.rs, delete the Expanding and Complete rounds. Also delete TumblingWindowWidthFrontier, TumblingWindowWidthDomain::Expanding, TumblingWindowWidthDomain::Complete and tumbling_window_width_divisors_before. With one variant left, TumblingWindowWidthDomain itself can go, and tumbling_window_width_domain_before becomes the gcd closure of the readers' grids.
2. Tests that pass Complete directly use the gcd domain, so they cover what the planner selects from.
3. Remove report.tumbling_window_widths_pending (today pane_widths_pending). It only reports that the Complete round did not finish. Its readers go with it: tools/dag-viewer/stages.js (and its README) and the corpus_snapshots / sketch_plan_snapshots tests.
4. Update the docs. The domain type's comment calls seed grids a heuristic, and docs/develop_docs/pane-search-compression-evaluation.md describes the round structure.

Open question: does the planner model any cost that falls as tumbling windows get finer? If one exists, it breaks the dominance argument, and that width family must stay. I found none in the cost model: per-window costs scale with the tumbling-window count, and ingestion costs do not depend on width.

Readers with different grids

One producer can have readers whose grids differ, e.g. rate(x[1m]) hash-consed from a copy every 10 s and a copy every 15 s. Each subset of readers that shares one chain needs its own gcd. The design treats alignment as a required property, the same way #1160 treats sketch size:

• The property. A query q requires grid g_q, its evaluation grid. A node that serves query set S requires gcd(S).
• Who delivers it.
  • A SummaryTumblingWindowChain of width w built at ingestion time delivers g if w divides g.
  • A chain built at query time is computed over the window ending at the evaluation time, so it delivers every g.

The work splits into three layers:

1. Stage 1 (this issue): offer the gcd closure of the group's reader grids. The closure is closed under pairwise gcd, so it contains gcd(S) for every reader subset S. That is the largest, cheapest width that serves all of S, so no per-subset enumeration is needed. For {10 s, 15 s} it is {5 s, 10 s, 15 s}.
2. Stage 2 (Stage 2: an ingestion-time tumbling-window chain serves a reader whose interval its width does not divide (wrong answers) #1173): one AllowedOutputs constraint per chain candidate. At ingestion time a chain of width w gets AllowedOutputs { outputs: { q : w divides g_q } }. Alignment to the epoch grid is a per-reader condition: a chain that serves each of q0 and q1 alone also serves both together. So no pairwise IncompatibleOutputs is needed.
3. Stage 3 (no new constraint type). AllowedOutputs is all Stage 3 needs. What it gives depends on the engine:

   • Today's engine (search/milp/model.rs) enforces AllowedOutputs through the per-output reachability reach[q][c].

   • The group MILP of [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 (draft feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144) enforces it through forbid_reach(q, c) (constraint 9), which covers the shareable reach a[q,c] and each query context's choices. Each query evaluation is its own execution context with one candidate per group (O4), and only shareable candidates (ingestion-time chains, materialized results) are shared across contexts, charged once on x[m]. So for q0 every 10 s and q1 every 15 s it chooses between:

     • one shared chain: a 5 s chain that both query contexts read;
     • one chain per query: q0's context reads a 10 s chain and q1's a 15 s chain, two shareable candidates.

     It picks whichever is cheaper.

   • A shared materialized result m read by both queries runs in its own context at the schedule group's evaluations. Its chain is reached by both queries (a[q0,·] = a[q1,·] = 1), so AllowedOutputs correctly forces a chain that both allow.

Today's engine only: no split below a shared consumer. In today's engine a consumer's physical candidate binds one producer per input. So two queries that reach a chain through one shared NotMaterialized consumer must share the chain, and only the 5 s chain is offered. The #1095 group MILP removes this limit, because query-time consumers are chosen per query context. No per-requirement copies are needed in either engine. Splitting is rarely cheaper anyway:

• with a shared 5 s chain, each row is inserted once into 12 tumbling windows per series;
• with 10 s and 15 s chains, each row is inserted twice, into 6 + 4 tumbling windows.

Scope and acceptance

In scope: the width domain and the round structure in run.rs, for both SummaryTumblingWindowChain and, once #1160 adds it, RawDataTumblingWindowChain.

Out of scope:

• the Rename PaneChain to SummaryTumblingWindowChain, and every pane name to the tumbling-window wording #1163 rename itself;
• Pass 2: tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows (window-specific; memo representation is #1203) #1160's state groups. This issue removes width copies and Pass 2: tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows (window-specific; memo representation is #1203) #1160 removes reader copies; the two compose.
• sketch-size pruning.

Acceptance:

• Single query. For quantile-single.json, stage_pipeline --text offers each sketch exactly one SummaryTumblingWindowChain candidate, at tumbling_window_width_ms=10000. Before Pass 2: tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows (window-specific; memo representation is #1203) #1160 these candidates are in G2, which then has 5 candidates: 3 Pass1 and 2 TumblingWindows. After Pass 2: tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows (window-specific; memo representation is #1203) #1160 they are in the KLL and DDSketch state groups.
• Two queries. For sum_over_time(data[1m]) and sum_over_time(data[5m]) every 10 s, Pass 2 adds exactly one shared chain group, SummaryTumblingWindowChain tumbling_window_count=30 tumbling_window_width_ms=10000. Stage 3's MILP is smaller than today's 29474 variables.
• Mixed grids. For rate(x[1m]) every 10 s and rate(x[1m]) every 15 s, hash-consed into one group, the offered widths are 5000, 10000 and 15000 ms (today: 21 widths in the selected Expanding { max_parts: 64 } round). A chain read by both queries must use 5000 ms: a 15000 ms chain does not end on the 10 s query's evaluation times. Today's planner selects a 15000 ms chain for both, which gives wrong answers (Stage 2: an ingestion-time tumbling-window chain serves a reader whose interval its width does not divide (wrong answers) #1173).
• No cost regressions. corpus_snapshots and sketch_plan_snapshots keep every selected plan's cost or lower it, and the PR lists each changed plan.
• Tests. asap-plan-selection --lib, the stage_pipeline tests and the planner run tests pass.

Status and related work

• Decided (2026-11-02): offer only gcd widths; finer divisors are dominated.
• Decided (2026-11-02): readers with different grids, handled in three layers. Stage 1 offers the gcd closure (this issue). Stage 2 sets per-reader AllowedOutputs (Stage 2: an ingestion-time tumbling-window chain serves a reader whose interval its width does not divide (wrong answers) #1173). Stage 3 enforces AllowedOutputs, through reach in today's engine and through forbid_reach in the [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095/feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 group MILP; there is no new constraint type. Per-requirement consumer copies are not needed, because [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095's per-query contexts already let readers take different chains.
• Rename PaneChain to SummaryTumblingWindowChain, and every pane name to the tumbling-window wording #1163 renames PaneChain and every pane name to the tumbling-window wording used here. This issue's code lands after it.
• Pass 2: tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows (window-specific; memo representation is #1203) #1160:
  • It moves summary tumbling-window builds into state groups and adds order (b), RawDataMerge ← RawDataTumblingWindowChain, with one candidate per width in the query window's input group. With this issue, that is one candidate per gcd width, not one per divisor.
  • Pass 2: tumbling-window builds as candidates of the state group, and merge-then-aggregate over raw tumbling windows (window-specific; memo representation is #1203) #1160 lists "pane-width domain pruning" as out of scope; this issue is that work.
• Stage 2: an ingestion-time tumbling-window chain serves a reader whose interval its width does not divide (wrong answers) #1173: a tumbling-window chain built at ingestion time serves a reader whose interval its width does not divide; found from this issue's mixed-grids case.
• feat(devtools): stage_pipeline --text prints every planner stage's output as text #1159 adds stage_pipeline --text, which produced the outputs above.