No type-level distinction between order-sensitive and order-insensitive accumulator merges #604

Activity

1. milindsrivastava1997 commented on Aug 25, 2026

   

   milindsrivastava1997

   on Aug 25, 2026

   ContributorAuthor

   More actions

   Idea worth considering later: use two separate types, one for a raw unmerged delta and one for a merged/combined delta. Right now nothing stops added/removed from overlapping except convention. If the raw type enforced "no overlap" at compile time, that class of bug couldn't happen. Not proposing this as the fix, just flagging it as an option to weigh, since it would add real cost (a second type to plumb through serialization and storage) and would need to work for future accumulators with this same problem.
2. milindsrivastava1997 commented on Aug 25, 2026

   

   milindsrivastava1997

   on Aug 25, 2026

   ContributorAuthor

   More actions

   Two design options for making order-sensitive vs. order-insensitive merges distinguishable. Both work within the current Box<dyn AggregateCore> architecture, but with opposite trade-offs.

   Option A: capability trait

   Add a second, narrower trait that only order-sensitive accumulators implement, plus one accessor on the base trait to reach it:

   pub trait OrderedMerge: AggregateCore {
       fn merge_ordered(&self, ordered: &[(i64, &dyn AggregateCore)]) -> Result<Box<dyn AggregateCore>, ...>;
   }
   
   pub trait AggregateCore: SerializableToSink + Send + Sync {
       // ...existing methods...
       fn as_ordered_merge(&self) -> Option<&dyn OrderedMerge> { None } // default: not order-sensitive
   }

   DeltaSetAggregatorAccumulator overrides as_ordered_merge to return Some(self) and implements merge_ordered. The one merge call site (simple_engine::merge_precomputed_outputs) branches: if let Some(om) = acc.as_ordered_merge() { om.merge_ordered(&sorted_with_timestamps) } else { self.merge_accumulators(...) }.

   Before/after: nothing else changes. window_merger.rs's NaiveMerger (currently Vec<Box<dyn AggregateCore>>, folds via merge_with) stays exactly as-is — it never needs to know the split exists.

   Pros: small, scoped diff (one trait, one default method, one override, one call-site branch). Every other accumulator (Sum, KLL, HLL, CountMinSketch, ...) is untouched. merge_ordered's signature forces timestamps to be supplied wherever it's actually called.
   Cons: still a runtime check — a future order-sensitive accumulator that forgets to override as_ordered_merge compiles fine and silently takes the unordered path. Two parallel merge code paths to maintain.

   Option B: replace Box<dyn AggregateCore> with a closed enum

   AggregationType already enumerates all ~13 accumulator kinds, so this isn't a new axis — just making the type system reflect it:

   pub enum Accumulator {
       OrderInsensitive(OrderInsensitiveAccumulator),
       OrderSensitive(OrderSensitiveAccumulator),
   }
   pub enum OrderInsensitiveAccumulator { Sum(SumAccumulator), Hll(HllAccumulator), CountMinSketch(CountMinSketchAccumulator), /* ... */ }
   pub enum OrderSensitiveAccumulator { DeltaSetAggregator(DeltaSetAggregatorAccumulator) /* future order-sensitive types go here */ }

   Before (today, sum_accumulator.rs:92-112, repeated near-identically in all ~13 accumulator files):

   fn merge_with(&self, other: &dyn AggregateCore) -> Result<Box<dyn AggregateCore>, ...> {
       if other.get_accumulator_type() != self.get_accumulator_type() {
           return Err(format!("Cannot merge SumAccumulator with {}", other.get_accumulator_type()).into());
       }
       let other_sum = other.as_any().downcast_ref::<SumAccumulator>()
           .ok_or("Failed to downcast to SumAccumulator")?;
       let merged = Self::merge_accumulators(vec![self.clone(), other_sum.clone()])?;
       ...
   }

   After:

   fn merge_with(a: &Accumulator, b: &Accumulator) -> Result<Accumulator, MergeError> {
       match (a, b) {
           (Accumulator::Sum(x), Accumulator::Sum(y)) => Ok(Accumulator::Sum(SumAccumulator::merge_accumulators(vec![x.clone(), y.clone()])?)),
           (Accumulator::Hll(x), Accumulator::Hll(y)) => Ok(Accumulator::Hll(HllAccumulator::merge_accumulators(vec![x.clone(), y.clone()])?)),
           // ... one line per type
           (a, b) => Err(MergeError::TypeMismatch(a.type_name(), b.type_name())), // one shared mismatch arm, not 13 copies
       }
   }

   But the reverse also holds — window_merger.rs's NaiveMerger, which today is fully generic over accumulator type (Vec<Box<dyn AggregateCore>>, folds via merge_with, never touched when a new accumulator type is added), now has to branch on OrderInsensitive vs. OrderSensitive and gains a "mixed kinds in one window" error case that couldn't previously be expressed.

   Pros: real compiler-enforced exhaustiveness — add a 14th accumulator type and every non-wildcard match on Accumulator fails to compile until you place it in OrderInsensitive or OrderSensitive. Also deletes a large amount of existing as_any()/downcast_ref() boilerplate (165 call sites in the crate today, merge_with being the dominant repeated pattern) and the runtime "Cannot merge X with Y" checks that go with it.
   Cons: touches every place currently built around dyn AggregateCore/dyn SingleSubpopulationAggregate/dyn MultipleSubpopulationAggregate polymorphism (precompute operators, WindowMerger, the two *Factory traits, accumulator_serde.rs) — a crate-wide refactor, not a scoped fix. Loses open extension (adding a type today = "new struct + impl the traits"; with the enum it's "new struct + new variant + touch every exhaustive match on it").

   Recommendation

   Option A for a scoped fix to this specific bug class. Option B is worth it only if the codebase is already heading away from trait-object-based accumulators for other reasons — it's a genuine net win on the downcast-boilerplate side, but it's a much bigger change than #604 alone justifies.
3. milindsrivastava1997

   added a commit that references this issue on Aug 25, 2026

   fix(query-engine): DeltaSetAggregator merge ordering, non-commutative…

   ...

   8bd1ab8