Sliding window execution: support multi-window merge/subtract in query engine

[milindsrivastava1997]

Problem

Sliding windows in the query engine today are not "tumbling with
configurable overlap" — they're a fundamentally narrower serving model. Per
asap_types::capability_matching::window_compatible
(capability_matching.rs:63-77):

match config.window_type {
    WindowType::Sliding => data_range_ms == window_ms,
    WindowType::Tumbling => data_range_ms.is_multiple_of(window_ms),
}

A sliding-window aggregation can only serve a query whose requested time
range matches the window's width exactly — no merge, no subtract, across
multiple stored overlapping windows. This is enforced live, on every query,
via find_compatible_aggregation() (called from both
simple_engine/promql.rs:1062 and simple_engine/sql.rs:503). Tumbling
windows have had multi-bucket merge support all along
(simple_engine/mod.rs's do_merge path); sliding never got the equivalent.

Concretely: rate(http_requests_total[5m]) refreshed every 60s has
data_range_ms = 300,000 but window_size_ms = 60,000 (derived from
t_repeat_ms, unrelated to the query's own range). Under sliding this is
rejected outright — not wrong data, just "no compatible aggregation," always.
The only naturally-compatible case today is a spatial-only query with no
range literal at all, which is also the least interesting case to slide.

This blocks #555 (a manual config override to choose tumbling vs.
sliding per experiment) from being safely shippable — enabling it today
would produce plans that fail at query time for almost any real workload
query.

Relationship to #405

#405 ("Optimization-based sketch/streaming config selection") already
documents Sliding: W < range_a → Infeasible as a deliberate v1 modeling
assumption in its own feasibility table and cost formulas — not an
unimplemented case. This issue is effectively a proposal to extend that
formulation (and the corresponding query-engine implementation) to support
W < range_a for sliding windows via merge/subtract, the same way tumbling
already works. #405 remains the design/tracking issue for automatic
optimizer-driven selection generally; this issue is scoped specifically to
making sliding-window execution correct, independent of who chooses to use
one (the optimizer, or the manual override in #555).

What's already correct (not part of this issue)

The ingestion side already works and is tested:
precompute_engine/window_manager.rs's WindowManager correctly produces a
dense, Unix-epoch-aligned grid of overlapping window buckets, one every
slide_interval_ms, forever (closed_windows(), panes_for_window()).
The gap is entirely on the query-serving side.

Scope

Split into two sub-issues (linked below):

1. Generating different sliding window candidates.
2. Supporting sliding window candidates in the query engine (execution).

Also in scope, surfaced during design but not yet resolved:

• planner/cleanup.rs's WindowType::Sliding branch (cleanup.rs:31-38)
  hardcodes a single-window read assumption (read_count_threshold = 1) and
  needs to become window-count-aware once multi-window sliding queries
  exist. It also skips the CleanupPolicy::NoCleanup check the Tumbling
  branch has — worth fixing alongside.
• An unverified epoch/phase-alignment dependency for exact-match lookups:
  simple_engine/mod.rs:419-423 looks up a bucket at
  [end_timestamp - window_size_ms, end_timestamp] exactly, but
  align_end_timestamp_promql() (promql.rs:44-56) only aligns
  end_timestamp to the scrape interval, not to the aggregation's
  slide_interval_ms. Needs resolving as part of this work (either
  per-aggregation alignment, or changing exact-match to "nearest available
  window").

Definition of done

• Sliding-window queries where data_range_ms is a multiple of
  window_size_ms (mirroring tumbling's existing rule) return correct data,
  via merge (mergeable sketch types) or subtract (subtractable types) across
  multiple stored buckets.
• End-to-end correctness test: plan → run → query a sliding-window
  aggregation → assert correct results. (This is the test Manual windowing override (tumbling/sliding) in config.yaml #555
  explicitly defers to this issue.)

Related

Full technical trace (code locations, worked example, alignment analysis)
attached as a comment on this issue.

[milindsrivastava1997]

Blocker: sliding windows need multi-window merge before the manual override is usable

Written up from a /grilling session scoping "add a manual tumbling/sliding
override to config.yaml" (see [[sliding-window-manual-override-plan]] once
that's written up). This doc captures what got discovered about the query
engine's current sliding-window support — the reason the override work is
blocked — so it can seed its own issue/design session. Not a design for the
fix; just the findings.

The headline finding

Sliding windows, as implemented today, are not "tumbling with configurable
overlap." They're a fundamentally narrower serving model: exactly one
precomputed window per query, and the query's own requested time range must
match that window's width exactly. There is no merge/subtract path for
sliding windows at query-serving time, even though tumbling has had one all
along. This means a global "use sliding windows" toggle would silently break
almost every genuinely temporal query (anything with a PromQL range literal
or SQL WHERE-clause duration that doesn't happen to equal its own refresh
interval) — not with wrong data, but with an outright "no compatible
aggregation" failure, deterministically, every time.

Where this is enforced

asap-common/dependencies/rs/asap_types/src/capability_matching.rs:63-77,
window_compatible():

match config.window_type {
    WindowType::Sliding => data_range_ms == window_ms,
    WindowType::Tumbling => data_range_ms.is_multiple_of(window_ms),
}

The doc comment says it outright: "a sliding window precomputes one fixed
range per timestamp; overlapping windows cannot be merged."

This function is called from find_compatible_aggregation()
(capability_matching.rs:154), which is the hot-path query-serving
lookup — called from both simple_engine/promql.rs:1062 and
simple_engine/sql.rs:503 on every query. So this isn't a planning-time
guard that could be relaxed later without touching serving code — it's live
today, and it's the actual reason a sliding-window query with a mismatched
range would fail.

Concrete example that fails today

Query: rate(http_requests_total[5m]), in a query group with
repetition_delay_ms: 60000.

• data_range_ms = 300,000ms — comes straight from the [5m] literal in the
  query text (query_requirements.rs:68-78; SQL's equivalent is
  TimeInfo::get_duration() via sql.rs:255, compute_sql_window()).
• window_size_ms = 60,000ms — comes from t_repeat_ms via
  get_effective_repeat() (planner/window.rs:69), not from
  data_range_ms. data_range_ms only participates as a floor check
  (data_range_ms >= t_repeat_ms, window.rs:64-68).

Tumbling handles this fine: at query time it's a range query over
[start, end), merging however many 60,000ms buckets fall inside
(simple_engine/mod.rs:416,426, do_merge); 300000 % 60000 == 0 passes
window_compatible.

Sliding cannot: 300000 != 60000 → window_compatible returns false →
find_compatible_aggregation finds no candidate for this statistic → the
query fails to be served, always, regardless of workload timing.

The only query shape that's naturally compatible with sliding today is a
spatial-only query with no range literal at all (e.g. sum(x)), because
data_range_ms defaults to one scrape interval and set_window_parameters's
spatial relaxation branch (window.rs:61-63) forces window_size_ms to
match it. That's also the least interesting case to slide — the window is
already the system's smallest granularity, so there's nothing meaningful left
to overlap.

What already works (ingestion side) vs. what doesn't (query side)

The ingestion side is actually already correct and tested:
precompute_engine/window_manager.rs's WindowManager produces a dense,
Unix-epoch-aligned grid of completed sliding-window buckets — one every
slide_interval_ms, forever (closed_windows(), panes_for_window(),
covered by existing unit tests at the bottom of that file). The worker really
does emit overlapping windows on schedule.

The gap is entirely on the query-serving side: nothing merges or
subtracts across multiple stored sliding-window buckets to answer a query
whose range spans more than one window. simple_engine/mod.rs's
create_store_query_plan (:413-427) and execute_and_merge_store_queries
(:544-576) both branch unconditionally on window_type == Sliding →
single exact-match lookup, explicitly skipping the merge path that Tumbling
uses ("Sliding window mode: Skipping merge (expecting 1 precompute per key)", mod.rs:553).

optimizer/candidate_gen.rs already has a conceptual design for this in
the cost-model/candidate-generation space — window_candidates()
(:104-151) enumerates sliding (W, S, k) triples where k = range_a / W
windows would need to be combined, and determine_query_method()
(:155-173) picks Direct / Subtract / Merge based on whether the
underlying sketch type supports subtraction or merging. None of that is
wired into the live query-serving path — it's only used by the offline
candidate_gen_dump/optimizer_cli cost simulators. It's a reasonable
starting point for (b)'s design, not a ready-to-use implementation.

Secondary, smaller findings also relevant to (b)

• cleanup.rs's WindowType::Sliding branch is single-window-shaped
  too (planner/cleanup.rs:31-38): it hardcodes a read_count_threshold
  of 1 (or num_steps for range queries), matching "a sliding query only
  ever reads one window." Once multi-window merge exists, this needs to
  become window-count-aware, like Tumbling's lookback_buckets calculation
  just above it. It also skips the CleanupPolicy::NoCleanup check that the
  Tumbling branch has — a minor inconsistency worth fixing at the same time,
  not urgent on its own.

• Exact-match queries also have an unverified epoch/phase-alignment
  dependency, independent of the merge gap: simple_engine/mod.rs:419-423
  looks up a bucket at [end_timestamp - window_size_ms, end_timestamp]
  exactly. The worker's buckets sit on a slide_interval_ms-aligned grid
  from Unix epoch 0, but the query's own end_timestamp is only floor-aligned
  to data_ingestion_interval_ms (the scrape interval) —
  promql.rs:44-56, align_end_timestamp_promql() — which knows nothing
  about the aggregation's slide_interval_ms. For queries fired on an
  arbitrary wall-clock schedule, whether end_timestamp lands on a
  slide-interval boundary is essentially down to when the experiment
  happened to start, not something deliberately guaranteed. This matters
  even in today's single-window-only case, and needs to be resolved as part
  of (b)'s design (either by aligning to slide_interval_ms per-aggregation,
  or by changing exact-match to "nearest available window").

What "done" looks like for (b) (not designed yet)

A sliding-window query whose data_range_ms is a multiple of window_size_ms
(mirroring Tumbling's already-working rule) should be served correctly by
combining multiple stored sliding-window buckets — merge for mergeable
sketch types, subtract for subtractable ones (per
optimizer/sketch_properties.rs's existing mergeable/subtractable
classification) — the same way Tumbling already merges multiple non-overlapping
buckets today, but accounting for the overlap between sliding windows so
values aren't double-counted.

This needs its own /grilling session — deliberately not designed further
here.

Why this blocks the manual-override work

The windowing: {type, slide_divisor} config override (see
[[sliding-window-manual-override-plan]]) is otherwise ready to scope in
detail — global-only for now (with a separate tracked gap for per-
aggregation-id overrides, covering both this and the existing
sketch_parameters global-only limitation), slide_divisor-based slide
sizing, PromQL + SQL paths, loud errors on non-exact division. But shipping
it before (b) lands means windowing.type: sliding would silently produce
plans that fail at query-serving time for almost any real workload query —
a footgun, not a feature. Building the override is being held until (b)
ships.

[milindsrivastava1997]

554's execution is largely already done on main, via a different route than the #557 stack (#562/#568) planned.

#557's PR B (#568) proposed building sliding-multi-bucket merge as new work (extracting merge_window_at_timestamp, reusing it for instant+range). Independently, five merged PRs already got both instant and range queries to correctly walk/merge multiple Sliding buckets by fixing adjacent bugs one at a time:

• fix(query-engine): merge all sliding-window buckets per key instead of taking first #570 — instant path: merge all sliding buckets per key instead of taking the first
• fix(query-engine): range queries expand keys_query and merge same-timestamp buckets #582 — range path: stopped collapsing same-timestamp buckets into a HashMap (which silently dropped Sliding's legitimate multi-bucket case)
• fix(query-engine): expand self-keyed accumulators in range queries #587, fix(query-engine): range queries expand keys_query per output step #595 — range path: keys_query expansion per step, self-keyed accumulator expansion
• Range query scan_window steps by window_size_ms, not slide_interval_ms, for Sliding aggregations #600/fix(query-engine): range query bucket scan steps by slide_interval_ms, not window_size_ms (#600) #603 — range path: bucket scan steps by slide_interval_ms, not window_size_ms (the grid buckets actually live on)

So "implement merge across multiple stored sliding-window buckets" is now substantially satisfied on main already, as fallout from general range-query bug fixes, not via the #557 stack. The #557-B (#568) approach should be re-verified against current main before reuse — it's likely obsolete, not just conflicting.

What's still actually missing from 554's:

• capability_matching.rs's window_compatible() — still hard data_range_ms == window_size_ms exact-match on main (capability_matching.rs:74). This is the literal gate keeping all of the above unreachable from real queries — nothing above changes 554's status until this is relaxed.
• cleanup.rs's read_count_threshold = 1 hardcoding — untouched.
• The epoch/slide-interval alignment question for exact-match lookups — untouched (Range query scan_window steps by window_size_ms, not slide_interval_ms, for Sliding aggregations #600/fix(query-engine): range query bucket scan steps by slide_interval_ms, not window_size_ms (#600) #603 only fixed the scan-step half of this, for range queries).
• The end-to-end plan→run→query correctness test — doesn't exist yet.

Also worth folding into scope: #588 (DeltaSetAggregator restricted to tumbling) requires the merge path above to special-case DeltaSetAggregator as tumbling-only even when co-located with sliding-capable accumulators in the same query — none of 554/557/588 currently assigns ownership of wiring that exception in.