You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
DeltaSetAggregator per-step keys replay is O(range_length^2), unbounded by lookback #599
`execute_range_query_pipeline`'s per-step keys merge (#583) recomputes each output step's key set from scratch, scanning `[0, current_time)` for `DeltaSetAggregator` (since its window is unbounded, replaying from the beginning by design — see `docs/583-range-keys-per-step-design.md`, Q2/Q3). For `N` output steps, total keys-merge work is `O(N^2)` bucket-merges (step 1 processes ~1 bucket, step 2 processes ~2, ..., step N processes ~N).
This was a deliberate, documented tradeoff in #583's design discussion: ship the simple recompute-from-scratch version first (easiest to verify correct, matches the existing values-loop pattern exactly), and only build incremental carry-forward merging (an `O(N)` alternative — persist a running merged accumulator across the `current_time` loop, folding in only new buckets since the last step) if this is ever a measured problem in practice. `SetAggregator`'s window is bounded by its own `window_size_ms` regardless of range length, so it never has this blowup — only `DeltaSetAggregator` does.
Filing this so the tradeoff is trackable outside the design doc/PR discussion, not because it's known to be a current problem. No action needed unless/until it's measured to matter for some real range/step combination.
Activity
fix(query-engine): warn on unresolved keys merge, guard zero keys window
fix(query-engine): range queries expand keys_query per output step (#595