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: merge is order-insensitive, store returns buckets out of order, and get_keys() drops all keys on any removal #586
Three independent, pre-existing bugs in DeltaSetAggregatorAccumulator (delta_set_aggregator_accumulator.rs), found while investigating PR #582's review thread. All three need fixing together — fixing any subset still leaves multi-toggle, multi-epoch key histories wrong.
1. merge_accumulators (lines 291-319) is order-insensitive and collapses toggle counts. It unions every bucket's added/removed into two HashSets, then treats any key present in both as a "conflict" and strips it from both, regardless of which bucket contributed which side or in what order. This is wrong for any key that toggles more than once across the merged buckets — e.g. base window adds K, window A removes K, window B re-adds K, window C removes K again: chronologically K should end up absent, but the algorithm dedups removed={K} (from A and C) against added={K} (from B), calls it a conflict, and strips both — so K survives as present. Wrong regardless of input order, since the algorithm never looks at order at all.
2. The store returns buckets out of chronological order once epoch rotation has occurred.query_precomputed_output (per_key.rs:550-567) — the path DeltaSetAggregator key queries always use, since create_keys_query_params always queries [0, end_timestamp] — checks the current (newest, still-open) epoch first, then sealed epochs oldest-to-newest. The resulting Vec<TimestampedBucket> order is [newest] [oldest sealed] [next-oldest] ... [newest sealed], not sorted, and nothing downstream (merge_precomputed_outputs/merge_accumulators in simple_engine/mod.rs) re-sorts by timestamp before the sequential merge fold.
3. get_keys() (lines 251-258) returns None for the entire accumulator whenever removed is non-empty, instead of returning added.difference(&removed) (the actual current key set). Since removed is non-empty as soon as any key has ever been removed across the metric's full history, this fires on ordinary label churn, not just corrupted state — every currently-active key is hidden just because some unrelated key was removed at some point. This is independent of bugs #1/#2: even with a fully correct, order-sensitive merge producing exactly correct added/removed sets, get_keys() would still wrongly return None here.
No existing test catches any of these: the only multi-bucket DeltaSetAggregator merge test with real toggling covers a single flip across 2 non-overlapping buckets (passes by accident); the only test that forces epoch rotation only asserts a bucket count, never merge correctness or order; no test exercises get_keys() after any removal.
Affects both instant and range queries — not specific to #580/#582, though #582's new hard-fail-on-missing-keys behavior surfaces bug #3 more visibly (turns routine label churn into a full range-query failure instead of a silent skip).
changed the title [-]DeltaSetAggregator merge is order-insensitive and count-collapsing; store also returns buckets out of chronological order[/-][+]DeltaSetAggregator: merge is order-insensitive, store returns buckets out of order, and get_keys() drops all keys on any removal[/+]on Aug 23, 2026
Note on bug #2 (store returns buckets out of order after epoch rotation): this is not currently reachable for DeltaSetAggregator specifically. insert_for_store_key (per_key.rs, and the same logic in global.rs) unconditionally skips maybe_rotate_epoch() whenever aggregation_type == DeltaSetAggregator, and always has (since PR #175/#279) — it needs to retain full history, so it never seals an epoch. So sealed_epochs stays empty for this type, and the current/sealed concatenation order never matters for it today.
The bug is still real in query_precomputed_output's general contract though: any other accumulator type that does rotate (e.g. Sum, under CircularBuffer with a small capacity) can be returned out of chronological order today. It just doesn't corrupt anything for those types since their merges are commutative. Confirmed this with a test using Sum forcing 3 epoch seals — the newest (still-open current epoch) bucket comes back first, ahead of 3 older sealed epochs.
Fixing the store's ordering is still worth doing as part of this issue — it's the correct contract for the method regardless, and it's what stands between today's harmless-for-everyone-else bug and a real corruption the moment DeltaSetAggregator's rotation exemption is ever relaxed, or a future order-sensitive accumulator doesn't get the same exemption.
Activity
[-]DeltaSetAggregator merge is order-insensitive and count-collapsing; store also returns buckets out of chronological order[/-][+]DeltaSetAggregator: merge is order-insensitive, store returns buckets out of order, and get_keys() drops all keys on any removal[/+]milindsrivastava1997 commentedon Aug 25, 2026
Note on bug #2 (store returns buckets out of order after epoch rotation): this is not currently reachable for DeltaSetAggregator specifically. insert_for_store_key (per_key.rs, and the same logic in global.rs) unconditionally skips maybe_rotate_epoch() whenever aggregation_type == DeltaSetAggregator, and always has (since PR #175/#279) — it needs to retain full history, so it never seals an epoch. So sealed_epochs stays empty for this type, and the current/sealed concatenation order never matters for it today.
The bug is still real in query_precomputed_output's general contract though: any other accumulator type that does rotate (e.g. Sum, under CircularBuffer with a small capacity) can be returned out of chronological order today. It just doesn't corrupt anything for those types since their merges are commutative. Confirmed this with a test using Sum forcing 3 epoch seals — the newest (still-open current epoch) bucket comes back first, ahead of 3 older sealed epochs.
Fixing the store's ordering is still worth doing as part of this issue — it's the correct contract for the method regardless, and it's what stands between today's harmless-for-everyone-else bug and a real corruption the moment DeltaSetAggregator's rotation exemption is ever relaxed, or a future order-sensitive accumulator doesn't get the same exemption.
fix(query-engine): address code review findings on #586's fix
fix(query-engine): consistent hard-fail semantics across #586's invar…
fix(query-engine): DeltaSetAggregator merge ordering, non-commutative…
refactor(query-engine): collapse execute_query_pipeline into a thin w…
refactor(query-engine): unify range pipeline onto output_timestamps +…