[future work] Stage 1: window candidates with properties — tumbling window, sliding window with merge, sliding window with subtraction #1206

Future work. Not scheduled. It depends on #1160 (state groups) and #1203 (candidate properties).

Example

sum_over_time(http_requests_total[5m]), exact, every 1 min. Three window summaries can answer it (planner-layering.md, Appendix: Windows and window summaries):

• Today: only the first exists. The window-composition rule (extend_local_window_composition) and Pass 2's TumblingWindows rule build SummaryMerge ← SummaryTumblingWindowChain.
• Sliding windows: no operator.
• Subtraction: SummarySubtract is declared in the IR but reserved and unimplemented (crates/types/src/ir/operator/asap.rs:110).
• Properties: the tumbling-window width and count are operator arguments, not properties a reader can require.

Representation, rules, enumeration

• (a) Representation.

  • A window state group $G^W$ per aggregate and window.
  • Its candidates carry a window layout $\omega$ (tumbling, sliding, subtractive) in $p^{\log}$.
  • A reader's $r^{\log}$ states its window and evaluation grid.

• (b) Rules. One Pass 2 rule per layout adds window candidates to $G^W$:

  • tumbling (today's, 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);
  • sliding with merge;
  • sliding with subtraction, gated by invertibility.

  Each rule adds candidates to the group. It does not copy readers.

• (c) Enumeration. No new mechanism. Each reader's edge picks one window candidate that satisfies $\alpha^{\log}$ (layout valid for its window and grid). One tumbling chain can serve readers with different windows.

Formulation

A window state group $G^{W}$ is the state of an aggregate over the query's window $W$ (e.g. 5 min, aligned to the evaluation grid). Its candidates are window summaries, each $v = (e_v, p_v)$, where $p^{\log}_v$ extends $\theta_v$ with a window layout $\omega_v$:

• Requirement. A reader of $G^W$ states $r^{\log} = (W, \text{evaluation grid}, \text{accuracy})$. Then $\alpha^{\log}_{u,c,i} = 1$ iff $\omega_u$ is valid for $(W, \text{grid})$ and $\theta_u$ meets the accuracy.
• Reuse. One tumbling chain of width $w$ can serve readers with different $W$ (merge newest $n$): one producer, several edges in $\mathcal E$ (Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201).
• Physical properties. A sliding or subtractive state with $\ell$ = AcrossEvaluations is kept between evaluations (Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200), the way a tumbling chain is.

Data structures and interfaces per stage

IR (crates/types/src/ir/operator/asap.rs):

• SummarySlidingWindowChain { child, family, …, window_length_ms, slide_ms }, new;
• SummarySubtract { left, right }, implemented: executor support and cost;
• each node's guarantees and costs from formulas, like SummaryTumblingWindowChain.

Properties (#1203):

pub enum WindowLayout {
    Tumbling { width_ms: u64 },
    Sliding { length_ms: u64, slide_ms: u64 },
    Subtractive { slide_ms: u64 },
}
// `LogicalProperties.window_layout` (#1203, a dimension of p^log) gains the
// Sliding and Subtractive variants; `LogicalRequirement.window` (the reader's
// window and evaluation grid) already exists. No new flat enum of combinations.

Stage 1:

• Pass 1: creates $G^W$ as a state group (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).
• Pass 2: one rule per layout adds candidates to $G^W$:
  • the tumbling rule (today's);
  • a sliding rule;
  • a subtraction rule, gated by an invertibility capability per summary family.
• Domain. Which widths and slides are offered stays a domain rule (Pass 2: offer only gcd tumbling-window widths; finer divisors are dominated #1171).

Stage 2: timing and lifetime per window candidate (#1200), like today's chains.

Cost (asap-cost):

• sliding: ingestion work × active windows, and memory per window;
• subtraction: two updates per slide and one running state.

Executor: sliding chains and SummarySubtract.

Current vs proposed

Scope and acceptance

Now: the design-doc section in planner-layering.md (windows appendix and Pass 2 rules) with the table above.

Later:

• the IR nodes, rules, cost and executor support, one layout per PR;
• acceptance: for the example, $G^W$ lists all three layouts, and Stage 3 picks the cheapest under the cost model.

Related

• Tracking: Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207.

• 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: state groups and the two window orders.

• 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 width domain and its bug.

• Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203: properties; Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200: lifetime.

• 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).