use fv_value::Value;
use crate::{Agg, AggOp};
#[derive(Debug, Clone)]
pub(crate) struct Acc {
pub count: u64,
pub slots: Box<[Option<f64>]>,
pub sets: Option<Box<[Option<std::collections::BTreeSet<String>>]>>,
pub welford: Option<Box<[Welford]>>,
}
#[derive(Debug, Clone, Copy, Default, PartialEq)]
pub(crate) struct Welford {
pub n: u64,
pub mean: f64,
pub m2: f64,
}
impl Welford {
fn add(&mut self, x: f64) {
self.n += 1;
let delta = x - self.mean;
self.mean += delta / self.n as f64;
self.m2 += delta * (x - self.mean);
}
fn merge(&mut self, o: &Welford) {
if o.n == 0 {
return;
}
if self.n == 0 {
*self = *o;
return;
}
let (na, nb) = (self.n as f64, o.n as f64);
let delta = o.mean - self.mean;
let total = na + nb;
self.m2 += o.m2 + delta * delta * na * nb / total;
self.mean += delta * nb / total;
self.n += o.n;
}
}
pub(crate) fn needs_sets(aggs: &[Agg]) -> bool {
aggs.iter().any(|a| a.op == AggOp::CountDistinct)
}
pub(crate) fn needs_welford(aggs: &[Agg]) -> bool {
aggs.iter().any(|a| a.op.is_variance())
}
impl Acc {
pub fn new(n_aggs: usize, with_sets: bool, with_welford: bool) -> Self {
Self {
count: 0,
slots: vec![None; n_aggs].into_boxed_slice(),
sets: if with_sets {
Some(vec![None; n_aggs].into_boxed_slice())
} else {
None
},
welford: if with_welford {
Some(vec![Welford::default(); n_aggs].into_boxed_slice())
} else {
None
},
}
}
pub fn add(&mut self, aggs: &[Agg], row: &[(String, Value)]) {
self.count += 1;
for (i, a) in aggs.iter().enumerate() {
match a.op {
AggOp::Count => {}
AggOp::CountDistinct => {
let v = row.iter().find(|(k, _)| k == &a.column).map(|(_, v)| v);
if let (Some(v), Some(sets)) = (v, self.sets.as_mut()) {
if !matches!(v, Value::Null) {
sets[i].get_or_insert_with(Default::default).insert(value_key(Some(v)));
}
}
}
op if op.is_variance() => {
let Some(v) = row.iter().find(|(k, _)| k == &a.column).and_then(|(_, v)| as_num(v)) else {
continue;
};
if let Some(w) = self.welford.as_mut() {
w[i].add(v);
}
}
AggOp::BoolAnd | AggOp::BoolOr => {
let Some(b) = row
.iter()
.find(|(k, _)| k == &a.column)
.and_then(|(_, v)| as_bool_num(v))
else {
continue;
};
self.slots[i] = Some(combine_scalar(a.op, self.slots[i], b));
}
AggOp::BitAnd | AggOp::BitOr | AggOp::BitXor => {
let Some(n) = row.iter().find(|(k, _)| k == &a.column).and_then(|(_, v)| as_int(v)) else {
continue;
};
self.slots[i] = Some(combine_scalar(a.op, self.slots[i], n));
}
_ => {
let Some(v) = row.iter().find(|(k, _)| k == &a.column).and_then(|(_, v)| as_num(v)) else {
continue;
};
self.slots[i] = Some(combine_scalar(a.op, self.slots[i], v));
}
}
}
}
pub fn merge(&mut self, aggs: &[Agg], other: &Acc) {
self.count += other.count;
for (i, a) in aggs.iter().enumerate() {
if a.op == AggOp::CountDistinct {
if let (Some(mine), Some(theirs)) = (self.sets.as_mut(), other.sets.as_ref()) {
if let Some(t) = &theirs[i] {
mine[i].get_or_insert_with(Default::default).extend(t.iter().cloned());
}
}
continue;
}
if a.op.is_variance() {
if let (Some(mine), Some(theirs)) = (self.welford.as_mut(), other.welford.as_ref()) {
let o = theirs[i];
mine[i].merge(&o);
}
continue;
}
self.slots[i] = match (self.slots[i], other.slots[i]) {
(x, None) => x,
(None, y) => y,
(Some(x), Some(y)) => Some(combine_scalar(a.op, Some(x), y)),
};
}
}
pub fn finalize_aggs(&self, aggs: &[Agg]) -> Vec<(String, Value)> {
aggs.iter()
.enumerate()
.map(|(i, a)| {
(
a.alias.clone(),
finalize(
a.op,
self.count,
self.slots[i],
self.sets.as_ref().and_then(|s| s[i].as_ref()),
self.welford.as_ref().map(|w| w[i]),
),
)
})
.collect()
}
}
fn combine_scalar(op: AggOp, cur: Option<f64>, v: f64) -> f64 {
match (op, cur) {
(AggOp::Sum | AggOp::Avg, Some(s)) => s + v,
(AggOp::Min, Some(m)) => m.min(v),
(AggOp::Max, Some(m)) => m.max(v),
(AggOp::BoolAnd, Some(a)) => ((a != 0.0) && (v != 0.0)) as i64 as f64,
(AggOp::BoolOr, Some(a)) => ((a != 0.0) || (v != 0.0)) as i64 as f64,
(AggOp::BitAnd, Some(a)) => ((a as i64) & (v as i64)) as f64,
(AggOp::BitOr, Some(a)) => ((a as i64) | (v as i64)) as f64,
(AggOp::BitXor, Some(a)) => ((a as i64) ^ (v as i64)) as f64,
_ => v, }
}
pub(crate) fn finalize(
op: AggOp,
count: u64,
slot: Option<f64>,
set: Option<&std::collections::BTreeSet<String>>,
w: Option<Welford>,
) -> Value {
match op {
AggOp::Count => Value::Num(count as f64),
AggOp::CountDistinct => Value::Num(set.map(|s| s.len()).unwrap_or(0) as f64),
AggOp::Sum => Value::Num(slot.unwrap_or(0.0)),
AggOp::Avg => Value::Num(
slot.map(|s| if count > 0 { s / count as f64 } else { 0.0 })
.unwrap_or(0.0),
),
AggOp::Min | AggOp::Max => slot.map(Value::Num).unwrap_or(Value::Null),
AggOp::BoolAnd | AggOp::BoolOr => slot.map(|x| Value::Bool(x != 0.0)).unwrap_or(Value::Null),
AggOp::BitAnd | AggOp::BitOr | AggOp::BitXor => {
slot.map(|x| Value::Num((x as i64) as f64)).unwrap_or(Value::Null)
}
AggOp::VarPop | AggOp::VarSamp | AggOp::StddevPop | AggOp::StddevSamp => {
let w = w.unwrap_or_default();
let var = match op {
_ if w.n == 0 => return Value::Null,
AggOp::VarPop | AggOp::StddevPop => w.m2 / w.n as f64,
_ if w.n < 2 => return Value::Null, _ => w.m2 / (w.n - 1) as f64,
};
Value::Num(if matches!(op, AggOp::StddevPop | AggOp::StddevSamp) {
var.sqrt()
} else {
var
})
}
}
}
pub(crate) fn as_bool_num(v: &Value) -> Option<f64> {
match v {
Value::Bool(b) => Some(*b as i64 as f64),
_ => None,
}
}
pub(crate) fn as_int(v: &Value) -> Option<f64> {
match v {
Value::Num(n) if n.fract() == 0.0 => Some(*n),
_ => None,
}
}
pub(crate) fn as_num(v: &Value) -> Option<f64> {
match v {
Value::Num(n) => Some(*n),
_ => None,
}
}
pub(crate) fn composite_of(row: &[(String, Value)], group_by: &[String]) -> String {
let mut s = String::new();
for (i, g) in group_by.iter().enumerate() {
if i > 0 {
s.push('\u{1}');
}
s.push_str(&value_key(row.iter().find(|(k, _)| k == g).map(|(_, v)| v)));
}
s
}
pub(crate) fn vals_of(row: &[(String, Value)], group_by: &[String]) -> Vec<Value> {
group_by
.iter()
.map(|g| {
row.iter()
.find(|(k, _)| k == g)
.map(|(_, v)| v.clone())
.unwrap_or(Value::Null)
})
.collect()
}
pub(crate) fn value_key(v: Option<&Value>) -> String {
match v {
None | Some(Value::Null) => "\u{0}null".into(),
Some(Value::Bool(b)) => format!("b{b}"),
Some(Value::Num(n)) => format!("n{n}"),
Some(Value::Str(s)) => format!("s{s}"),
Some(other) => format!("x{other:?}"),
}
}
#[cfg(test)]
mod tests {
use super::*;
fn row(pairs: &[(&str, Value)]) -> Vec<(String, Value)> {
pairs.iter().map(|(k, v)| (k.to_string(), v.clone())).collect()
}
fn aggs() -> Vec<Agg> {
vec![
Agg::count("n"),
Agg::of(AggOp::Sum, "amount", "total"),
Agg::of(AggOp::Avg, "amount", "mean"),
Agg::of(AggOp::Min, "amount", "lo"),
Agg::of(AggOp::Max, "amount", "hi"),
]
}
fn val(out: &[(String, Value)], alias: &str) -> Value {
out.iter().find(|(a, _)| a == alias).unwrap().1.clone()
}
#[test]
fn add_accumulates_every_op() {
let ag = aggs();
let mut acc = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
for a in [2.0, 4.0, 6.0] {
acc.add(&ag, &row(&[("amount", Value::Num(a))]));
}
let out = acc.finalize_aggs(&ag);
assert_eq!(val(&out, "n"), Value::Num(3.0));
assert_eq!(val(&out, "total"), Value::Num(12.0));
assert_eq!(val(&out, "mean"), Value::Num(4.0));
assert_eq!(val(&out, "lo"), Value::Num(2.0));
assert_eq!(val(&out, "hi"), Value::Num(6.0));
}
#[test]
fn merge_combines_two_accumulators() {
let ag = aggs();
let mut a = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
let mut b = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
a.add(&ag, &row(&[("amount", Value::Num(2.0))])); a.add(&ag, &row(&[("amount", Value::Num(10.0))])); b.add(&ag, &row(&[("amount", Value::Num(1.0))])); a.merge(&ag, &b);
let out = a.finalize_aggs(&ag);
assert_eq!(val(&out, "n"), Value::Num(3.0));
assert_eq!(val(&out, "total"), Value::Num(13.0));
assert_eq!(val(&out, "mean"), Value::Num(13.0 / 3.0));
assert_eq!(val(&out, "lo"), Value::Num(1.0));
assert_eq!(val(&out, "hi"), Value::Num(10.0));
}
#[test]
fn merge_with_empty_slot_is_a_no_op_side() {
let ag = vec![Agg::of(AggOp::Max, "amount", "hi")];
let mut a = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
let b = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag)); a.add(&ag, &row(&[("amount", Value::Num(5.0))]));
a.merge(&ag, &b);
assert_eq!(val(&a.finalize_aggs(&ag), "hi"), Value::Num(5.0));
let mut c = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
c.merge(&ag, &a);
assert_eq!(val(&c.finalize_aggs(&ag), "hi"), Value::Num(5.0));
}
#[test]
fn finalize_of_no_events() {
assert_eq!(finalize(AggOp::Count, 0, None, None, None), Value::Num(0.0));
assert_eq!(finalize(AggOp::Sum, 0, None, None, None), Value::Num(0.0));
assert_eq!(finalize(AggOp::Avg, 0, None, None, None), Value::Num(0.0));
assert_eq!(finalize(AggOp::Min, 0, None, None, None), Value::Null);
assert_eq!(finalize(AggOp::Max, 0, None, None, None), Value::Null);
assert_eq!(finalize(AggOp::CountDistinct, 0, None, None, None), Value::Num(0.0));
}
#[test]
fn non_numeric_values_do_not_aggregate() {
let ag = vec![Agg::count("n"), Agg::of(AggOp::Sum, "amount", "total")];
let mut acc = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
acc.add(&ag, &row(&[("amount", Value::Str("nope".into()))])); acc.add(&ag, &row(&[("amount", Value::Num(3.0))]));
let out = acc.finalize_aggs(&ag);
assert_eq!(val(&out, "n"), Value::Num(2.0));
assert_eq!(val(&out, "total"), Value::Num(3.0));
}
#[test]
fn count_distinct_counts_unique_non_null_values_and_merges_as_union() {
let ag = vec![Agg::of(AggOp::CountDistinct, "bidder", "uniq"), Agg::count("n")];
let mut a = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
for b in ["b1", "b2", "b1"] {
a.add(&ag, &row(&[("bidder", Value::Str(b.into()))]));
}
a.add(&ag, &row(&[("bidder", Value::Null)])); a.add(&ag, &row(&[("other", Value::Num(1.0))])); let out = a.finalize_aggs(&ag);
assert_eq!(val(&out, "uniq"), Value::Num(2.0));
assert_eq!(val(&out, "n"), Value::Num(5.0)); a.add(&ag, &row(&[("bidder", Value::Num(1.0))]));
a.add(&ag, &row(&[("bidder", Value::Str("1".into()))]));
assert_eq!(val(&a.finalize_aggs(&ag), "uniq"), Value::Num(4.0));
let mut b = Acc::new(ag.len(), needs_sets(&ag), needs_welford(&ag));
b.add(&ag, &row(&[("bidder", Value::Str("b2".into()))])); b.add(&ag, &row(&[("bidder", Value::Str("b9".into()))])); a.merge(&ag, &b);
assert_eq!(val(&a.finalize_aggs(&ag), "uniq"), Value::Num(5.0));
}
#[test]
fn value_key_distinguishes_types_and_null() {
assert_eq!(value_key(None), value_key(Some(&Value::Null)));
assert_ne!(
value_key(Some(&Value::Num(1.0))),
value_key(Some(&Value::Str("1".into())))
);
assert_ne!(
value_key(Some(&Value::Bool(true))),
value_key(Some(&Value::Str("true".into())))
);
}
}
#[cfg(test)]
mod func2_tests {
use super::*;
fn agg(op: AggOp, col: &str) -> Agg {
Agg::of(op, col, "r")
}
fn feed(aggs: &[Agg], col: &str, vals: &[Value]) -> Acc {
let mut a = Acc::new(aggs.len(), needs_sets(aggs), needs_welford(aggs));
for v in vals {
a.add(aggs, &[(col.to_string(), v.clone())]);
}
a
}
fn out(a: &Acc, aggs: &[Agg]) -> Value {
a.finalize_aggs(aggs)[0].1.clone()
}
fn n(v: Value) -> f64 {
match v {
Value::Num(x) => x,
o => panic!("not num: {o:?}"),
}
}
#[test]
fn variance_and_stddev_match_known_values() {
let d: Vec<Value> = [2., 4., 4., 4., 5., 5., 7., 9.]
.iter()
.map(|x| Value::Num(*x))
.collect();
for (op, expect) in [
(AggOp::VarPop, 4.0),
(AggOp::StddevPop, 2.0),
(AggOp::VarSamp, 32.0 / 7.0), (AggOp::StddevSamp, (32.0f64 / 7.0).sqrt()),
] {
let ag = vec![agg(op, "x")];
assert!((n(out(&feed(&ag, "x", &d), &ag)) - expect).abs() < 1e-9, "{op:?}");
}
}
#[test]
fn samp_needs_two_values_pop_needs_one() {
let one = vec![Value::Num(5.0)];
assert_eq!(
out(&feed(&[agg(AggOp::VarPop, "x")], "x", &one), &[agg(AggOp::VarPop, "x")]),
Value::Num(0.0)
);
assert_eq!(
out(
&feed(&[agg(AggOp::VarSamp, "x")], "x", &one),
&[agg(AggOp::VarSamp, "x")]
),
Value::Null
);
assert_eq!(
out(&feed(&[agg(AggOp::VarPop, "x")], "x", &[]), &[agg(AggOp::VarPop, "x")]),
Value::Null
);
let mixed = vec![Value::Num(1.0), Value::Str("nope".into()), Value::Num(3.0)];
assert_eq!(
n(out(
&feed(&[agg(AggOp::VarPop, "x")], "x", &mixed),
&[agg(AggOp::VarPop, "x")]
)),
1.0
); }
#[test]
fn welford_merge_equals_single_pass() {
let ag = vec![agg(AggOp::VarPop, "x")];
let all: Vec<Value> = (1..=10).map(|i| Value::Num(i as f64)).collect();
let single = feed(&ag, "x", &all);
let mut left = feed(&ag, "x", &all[..3]);
let right = feed(&ag, "x", &all[3..]);
left.merge(&ag, &right);
assert!(
(n(out(&left, &ag)) - n(out(&single, &ag))).abs() < 1e-9,
"merge != single-pass"
);
}
#[test]
fn bool_and_or_fold() {
let t = Value::Bool(true);
let f = Value::Bool(false);
assert_eq!(
out(
&feed(&[agg(AggOp::BoolAnd, "b")], "b", &[t.clone(), t.clone()]),
&[agg(AggOp::BoolAnd, "b")]
),
Value::Bool(true)
);
assert_eq!(
out(
&feed(&[agg(AggOp::BoolAnd, "b")], "b", &[t.clone(), f.clone()]),
&[agg(AggOp::BoolAnd, "b")]
),
Value::Bool(false)
);
assert_eq!(
out(
&feed(&[agg(AggOp::BoolOr, "b")], "b", &[f.clone(), t.clone()]),
&[agg(AggOp::BoolOr, "b")]
),
Value::Bool(true)
);
assert_eq!(
out(
&feed(&[agg(AggOp::BoolOr, "b")], "b", &[f.clone(), f.clone()]),
&[agg(AggOp::BoolOr, "b")]
),
Value::Bool(false)
);
assert_eq!(
out(
&feed(&[agg(AggOp::BoolAnd, "b")], "b", &[Value::Num(1.0)]),
&[agg(AggOp::BoolAnd, "b")]
),
Value::Null
);
}
#[test]
fn bit_and_or_xor_fold() {
let v: Vec<Value> = [12.0, 10.0, 6.0].iter().map(|x| Value::Num(*x)).collect();
assert_eq!(
out(&feed(&[agg(AggOp::BitAnd, "n")], "n", &v), &[agg(AggOp::BitAnd, "n")]),
Value::Num((12 & 10 & 6) as f64)
);
assert_eq!(
out(&feed(&[agg(AggOp::BitOr, "n")], "n", &v), &[agg(AggOp::BitOr, "n")]),
Value::Num((12 | 10 | 6) as f64)
);
assert_eq!(
out(&feed(&[agg(AggOp::BitXor, "n")], "n", &v), &[agg(AggOp::BitXor, "n")]),
Value::Num((12 ^ 10 ^ 6) as f64)
);
assert_eq!(
out(
&feed(&[agg(AggOp::BitAnd, "n")], "n", &[Value::Num(1.5)]),
&[agg(AggOp::BitAnd, "n")]
),
Value::Null
);
}
#[test]
fn welford_survives_snapshot_round_trip() {
let ag = vec![agg(AggOp::VarSamp, "x")];
let a = feed(&ag, "x", &[Value::Num(2.0), Value::Num(4.0), Value::Num(6.0)]);
let j = crate::snapshot::acc_to_json_v2(&a);
let b = crate::snapshot::acc_from_json_v2(&j).unwrap();
assert_eq!(a.welford, b.welford);
assert_eq!(out(&a, &ag), out(&b, &ag));
}
}