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

Problem, by example

One dashboard panel, exact, every 10 s, over the counter http_requests_total (#509 Example 1's data facts):

sum by (job) (rate(http_requests_total[1m]))

Running stage_pipeline --text (#1159) on main 91d874f prints this memo after Pass 2:

G0: Scan
G1: TimeRange 60s          <- G0
G2: Aggregate rate()       <- G1
    [0]  Pass1  FinalizeExactAccumulator ← SummaryAgg                                       inputs=[G1]
    [1]  TumblingWindows  FinalizeExactAccumulator ← SummaryMerge ← SummaryTumblingWindowChain tumbling_window_count=6 tumbling_window_width_ms=10000   inputs=[G0]
    [2]  TumblingWindows  FinalizeExactAccumulator ← SummaryMerge ← SummaryTumblingWindowChain tumbling_window_count=24 tumbling_window_width_ms=2500   inputs=[G0]
    …
    [25] TumblingWindows  FinalizeExactAccumulator ← SummaryMerge ← SummaryTumblingWindowChain tumbling_window_count=60000 tumbling_window_width_ms=1    inputs=[G0]
G3: Aggregate sum()        <- G2
    [0]  Pass1  FinalizeExactAccumulator ← SummaryAgg                                       inputs=[G2]

All 26 candidates of G2 end in the same FinalizeExactAccumulator of the same rate state. They differ only in how that state is built: one SummaryAgg over the raw window, or merging one of 25 tumbling-window layouts. Because the state is not a group, the shared Finalize is copied into every candidate. Stage 2 then builds 81 operator nodes and 107 physical candidates:

O2:  FinalizeExactAccumulator   implements=[G2[0]]
O3:  FinalizeExactAccumulator   implements=[G2[1]]
…
O27: FinalizeExactAccumulator   implements=[G2[25]]      ← 26 identical Finalize nodes
C106: O80 SummaryAgg (sum)      producers per input: [{C3,C4,…,C28}]   ← 26 producers, one per copy

What should happen instead: the tumbling-window builds are candidates of the rate state group, and the aggregate reads that group once:

G1: TimeRange 60s                   <- G0
Gs: rate state over G1 (60s)        <- G1, G0
    [0]  SummaryAgg                           inputs=[G1]       (from #1203 PR 1)
    [1]  SummaryMerge ← SummaryTumblingWindowChain(10000ms × 6) inputs=[G0]   (this issue)
    …
    [25] SummaryMerge ← SummaryTumblingWindowChain(1ms × 60000) inputs=[G0]   (this issue)
G2: Aggregate rate()                <- G1
    [0]  FinalizeExactAccumulator             inputs=[Gs]

This has one Finalize for G2, and the tumbling-window-width choice lives only in Gs. In this example Stage 2's operator nodes would drop from 81 to about 56: 25 Finalize copies fewer. That figure is counted by hand from the run above, not measured.

Scope: window-specific (re-scoped 2026-11-04)

This issue does not change the memo group representation. That belongs to tracking issue #1207, and specifically to #1203 PR 1:

• each mergeable state is its own group, because θ is a candidate property and not part of the group's identity;
• one operator per candidate;
• fused builds;
• shared builds as plain group identity;
• memo choice per consumer input.

After #1203 PR 1, Gs exists and holds SummaryAgg(G1).

This issue adds only the window candidates, which hash-consing cannot find because a merge of a tumbling-window chain is a different operator tree from SummaryAgg:

1. Tumbling-window builds join the state group (order a).
2. Merge-then-aggregate over raw sub-windows (order b).

Sizes, accuracy, edges and the MILP are #1203 PR 2, #1201 and #1204.

Why it happens

• Tumbling-window candidates copy the reader. extend_local_window_composition (pass2/memo/window_candidates.rs) adds each tumbling-window layout as a whole new candidate of the aggregate's group, Finalize ← SummaryMerge ← SummaryTumblingWindowChain, copying the reader. Even once Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203 PR 1 makes Gs a group, nothing says that SummaryMerge ← SummaryTumblingWindowChain computes the same state as SummaryAgg(G1), so the copies stay.
• Shared chains get their own group only at the end of Pass 2. add_shared_summary_state_groups creates a group for a tumbling-window chain only when two or more candidates build it identically. For example, with sum_over_time(http_requests_total[1m]) and sum_over_time(http_requests_total[5m]), it adds G25: SummaryTumblingWindowChain tumbling_window_count=30 tumbling_window_width_ms=10000, and both readers merge the newest tumbling windows of it.
• Order (b) does not exist. There is no operator that keeps raw rows in tumbling windows.

Formulation

In #1207's terms: the state group $G^s$ is one intermediate state family. A tumbling-window build is another candidate $v = (e_v, p_v)$ of it, with
$$e_v = \texttt{SummaryMerge}\bigl(\texttt{SummaryTumblingWindowChain}{w \times N}(G_0)\bigr),$$
and the width $w$ and count $N$ are operator arguments of $e_v$. The reader Finalize keeps one input edge into $G^s$, and Stage 3 chooses among its producers ($y{u,c,i}$, #1201). Adding a candidate to $G^s$ is a Stage 1 Pass 2 rule, declared by measure: "this chain merge computes the state of this measure over this window".

Proposal

1. Pass 2's TumblingWindows rule adds tumbling-window builds to the state group, not to readers.

• extend_local_window_composition adds SummaryMerge ← SummaryTumblingWindowChain ← <scan group> as a candidate of Gs, once per offered width.
• add_shared_summary_state_groups shrinks to the case hash-consing does not cover: one tumbling-window chain read by different windows, e.g. the 1m reader merging the newest 6 of a chain of 30 tumbling windows.

2. A windowed aggregate over sub-windows has two orders, each a candidate of a different group. Take rate(http_requests_total[1m]) split into six 10 s sub-windows. Names follow #1163 (merged): SummaryTumblingWindowChain and tumbling_window_* fields.

• Today only (a) exists, and only as a copy of the reader in G2.
• (b) works without a mergeable state. It also applies when the aggregate has no mergeable state (plain Exact), where (a) cannot.
• (b) can share raw sub-windows. Windows of different lengths could share the same raw sub-windows, and keep them across evaluations, the way (a) shares tumbling-window chains.
• Choosing a sub-window grid is then a choice inside G1 (order b) or inside the state group (order a), not a copy of every group above them.

Order (b)'s operators (decided): RawDataTumblingWindowChain and RawDataMerge. They are the raw-data counterparts of SummaryTumblingWindowChain and SummaryMerge. Each name says what it holds: summary states or raw data, kept as a chain of tumbling windows.

• RawDataTumblingWindowChain { tumbling_window_width_ms, tumbling_window_count, child } keeps the child's rows in tumbling_window_count tumbling windows of tumbling_window_width_ms, aligned to absolute time. Each evaluation builds the newest tumbling window and keeps the older ones, like SummaryTumblingWindowChain keeps states. It is one node however many tumbling windows it holds.

• RawDataMerge { skip_newest_tumbling_windows, tumbling_window_count, child } outputs the rows of the tumbling windows it names: skip the newest skip_newest_tumbling_windows, then take the next tumbling_window_count. Naming the range, not only "the newest n", lets readers of one RawDataTumblingWindowChain read different query windows from it. With one RawDataTumblingWindowChain(10000ms × 36):

  • rate(x[1m]) reads RawDataMerge(skip 0, 6 tumbling windows);
  • rate(x[5m]) reads RawDataMerge(skip 0, 30 tumbling windows);
  • rate(x[1m] offset 5m) reads RawDataMerge(skip 30, 6 tumbling windows).

  The tumbling-window edges follow PromQL's left-open window, (t - 60 s, t].

So G1 gets candidate [1] RawDataMerge(skip 0, 6 tumbling windows) ← RawDataTumblingWindowChain(10000ms × 6) inputs=[G0], one per tumbling-window width.

Rejected alternative: Concat of TimeShift ← TimeRange slices. It needs no new operator, but each slice is relative to the evaluation time. The slice at offset 10 s holds different rows ten seconds later, so slices can't be kept across evaluations. It also needs one node per slice: 60,000 at the 1 ms grid.

What order (b) needs besides the operators:

• Executor support for RawDataTumblingWindowChain and RawDataMerge.
• Cost model. Price holding raw rows: e.g. 66,667 rows/s × 60 s ≈ 4M rows, against order (a)'s per-series states. Stage 3 picks between them.
• Deployment capability. A capability says whether the deployment keeps raw tumbling windows, next to Stage 2's RawDataNotRetained pruning; without it there is no order-(b) candidate.

Data structures and interfaces per stage

• IR: RawDataTumblingWindowChain, RawDataMerge (new), with executor support.
• Stage 1, Pass 2 (pass2/memo/window_candidates.rs, pass2/memo/state_groups.rs):
  • the TumblingWindows rule targets the state group;
  • order (b) adds RawDataMerge ← RawDataTumblingWindowChain to the window's input group;
  • add_shared_summary_state_groups is reduced.
• Stage 2:
  • physical properties of the new chain, through Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200's timing and lifetime;
  • the deployment capability for keeping raw tumbling windows, next to RawDataNotRetained.
• Cost (asap-cost): prices raw rows held by RawDataTumblingWindowChain.
• Stage 3: no change.

Current vs proposed

Scope and acceptance

In scope:

• the TumblingWindows rule over state groups;
• the reduced add_shared_summary_state_groups;
• order (b): operators, executor, cost, capability;
• planner-layering.md for these.

Out of scope:

• the memo group representation: state groups, one operator per candidate, fused and shared builds, memo choice (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203 PR 1, Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207);
• sizes and accuracy (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203 PR 2, Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204);
• tumbling-window-width domain pruning (Pass 2: offer only gcd tumbling-window widths; finer divisors are dominated #1171).

Depends on: #1203 PR 1 (#1207 step 2).

Acceptance:

• Deletes what it replaces in the same PR, with no dead code, fallback, flag, shim or reuse of an old abstraction; the PR body lists what it deleted (Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, Policy).
• Group structure. For the example above, asap-planner --output text shows one rate state group with 26 candidates, and G2 has a single FinalizeExactAccumulator candidate reading it.
• Stage 2 count. Stage 2 has one FinalizeExactAccumulator operator node for G2, where today it has 26.
• Both orders. G1 has an order-(b) candidate RawDataMerge(skip 0, 6 tumbling windows) ← RawDataTumblingWindowChain(10000ms × 6), and the state group has the order-(a) tumbling-window candidates.
• Shared raw tumbling windows. For rate(x[1m]) and rate(x[5m]) on one grid, the selected plan can have both read one RawDataTumblingWindowChain, through RawDataMerge(skip 0, 6 tumbling windows) and RawDataMerge(skip 0, 30 tumbling windows).
• Plans. Each plan or cost change is listed in the PR, for a manual check with asap-planner --output text.

Status and related work

• Re-scoped (2026-11-04): window-specific only. The memo group representation moved to Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203 PR 1 under Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207. docs(planner-layering): state groups from Pass 1, size as a candidate property, two window orders #1183 (the earlier design doc) was closed.
• Decided (2026-11-02):
  • order (b) uses RawDataTumblingWindowChain and RawDataMerge; the Concat-of-shifted-TimeRange alternative was rejected;
  • a windowed aggregate over sub-windows has two orders, (a) and (b), each a candidate of its group.
• Related:
  • Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 (tracking), Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203 (memo representation), Pass 2: offer only gcd tumbling-window widths; finer divisors are dominated #1171 / Stage 2: an ingestion-time tumbling-window chain serves a reader whose interval its width does not divide (wrong answers) #1173 (tumbling-window widths), [future work] Stage 1: window candidates with properties — tumbling window, sliding window with merge, sliding window with subtraction #1206 (sliding windows, future);
  • Rename PaneChain to SummaryTumblingWindowChain, and every pane name to the tumbling-window wording #1163 (pane → tumbling-window names, merged);
  • feat(devtools): stage_pipeline --text prints every planner stage's output as text #1159 (stage_pipeline --text).