Skip to main content

zero_client/ivm/
aggregate.rs

1//! The aggregate operators' helpers and the `Aggregate` operator
2//! (`packages/zql/src/ivm/aggregate.ts`).
3
4use super::*;
5use crate::ast::{
6    Aggregate as AggregateSpec, AggregateFunction, Direction, OrderPart, json_value_at,
7};
8use crate::compare;
9use crate::json::{self, Object, Value};
10use crate::keys::aggregate_columns as cols;
11use crate::map::OrderedMap;
12use crate::schema::{Column, ValueType};
13use std::cell::RefCell;
14use std::cmp::Ordering;
15use std::collections::HashMap;
16use std::rc::{Rc, Weak};
17
18/// `isSyntheticColumn`: the columns the aggregate operators add to a row.
19pub fn is_synthetic_column(column: &str) -> bool {
20    column == cols::KEY || cols::PAYLOAD.contains(&column)
21}
22
23/// `carriesComponents`: whether `fn_`'s rows carry the sum and count.
24pub fn carries_components(fn_: AggregateFunction) -> bool {
25    matches!(fn_, AggregateFunction::Sum | AggregateFunction::Avg)
26}
27
28/// `isInvertible`: a change to one row moves the result by a fixed delta.
29pub fn is_invertible(fn_: AggregateFunction) -> bool {
30    matches!(
31        fn_,
32        AggregateFunction::Count | AggregateFunction::Sum | AggregateFunction::Avg
33    )
34}
35
36/// `aggregateValue`: the value `row` contributes to `aggregate`: its field,
37/// or the JSON leaf at the path when it is one the function takes (a number
38/// for sum and avg, a number or string for min and max), else null.
39pub fn aggregate_value(aggregate: &AggregateSpec, row: &Row) -> Value {
40    let v = row.get(aggregate.field.as_deref().unwrap_or(""));
41    let Some(path) = &aggregate.path else {
42        return v.cloned().unwrap_or(Value::Null);
43    };
44    match json_value_at(path, v) {
45        leaf @ Value::Number(_) => leaf.clone(),
46        leaf @ Value::String(_)
47            if matches!(
48                aggregate.fn_,
49                AggregateFunction::Min | AggregateFunction::Max
50            ) =>
51        {
52            leaf.clone()
53        }
54        _ => Value::Null,
55    }
56}
57
58fn column(type_: ValueType, optional: bool) -> Column {
59    Column {
60        type_,
61        optional,
62        server_name: None,
63    }
64}
65
66/// `aggregateSourceSchema`: the columns and primary key of the rows an
67/// aggregate emits, from its input's columns and its group key. A
68/// top-level aggregate has no group key, so its one row is keyed by
69/// `_0_key`.
70pub fn aggregate_source_schema(
71    input_columns: &OrderedMap<Column>,
72    group_key: &[String],
73    aggregate: &AggregateSpec,
74) -> Result<(OrderedMap<Column>, Vec<String>), PipelineError> {
75    let mut columns = OrderedMap::new();
76    for c in group_key {
77        assert_not_synthetic_column(c)?;
78        let Some(schema) = input_columns.get(c) else {
79            return Err(PipelineError::new(format!(
80                "Aggregate: group key column \"{c}\" missing"
81            )));
82        };
83        columns.insert(c.clone(), schema.clone());
84    }
85    if group_key.is_empty() {
86        columns.insert(cols::KEY, column(ValueType::Number, false));
87    }
88    let value = match aggregate.fn_ {
89        AggregateFunction::Count => column(ValueType::Number, false),
90        AggregateFunction::Sum | AggregateFunction::Avg => column(ValueType::Number, true),
91        AggregateFunction::Min | AggregateFunction::Max => {
92            if aggregate.path.is_some() {
93                column(ValueType::Json, true)
94            } else {
95                let field = aggregate.field.as_deref();
96                let Some(schema) = field.and_then(|f| input_columns.get(f)) else {
97                    return Err(PipelineError::new(format!(
98                        "Aggregate: {} field \"{}\" missing",
99                        aggregate.fn_.as_str(),
100                        field.unwrap_or("")
101                    )));
102                };
103                Column {
104                    optional: true,
105                    ..schema.clone()
106                }
107            }
108        }
109    };
110    columns.insert(cols::VALUE, value);
111    if carries_components(aggregate.fn_) {
112        columns.insert(cols::SUM, column(ValueType::Number, false));
113        columns.insert(cols::COUNT, column(ValueType::Number, false));
114    }
115    let primary_key = if group_key.is_empty() {
116        vec![cols::KEY.to_owned()]
117    } else {
118        group_key.to_vec()
119    };
120    Ok((columns, primary_key))
121}
122
123/// `assertNotSyntheticColumn`.
124pub fn assert_not_synthetic_column(column: &str) -> Result<(), PipelineError> {
125    if is_synthetic_column(column) {
126        return Err(PipelineError::new(format!(
127            "Aggregate: group key column \"{column}\" collides with the synthetic aggregate column of the same name"
128        )));
129    }
130    Ok(())
131}
132
133/// A group's running state (`AggState`).
134#[derive(Clone, Debug, PartialEq, Default)]
135pub(crate) struct AggState {
136    /// count(*): every row.
137    pub(crate) count: i64,
138    /// The sum of the non-null values.
139    pub(crate) sum: f64,
140    /// How many values are non-null.
141    pub(crate) non_null: i64,
142    /// The min or max of the non-null values; null when there are none.
143    pub(crate) extreme: Value,
144}
145
146/// How an aggregate function reduces a group's rows (`Reducer`).
147pub(crate) struct Reducer {
148    pub(crate) aggregate: AggregateSpec,
149}
150
151impl Reducer {
152    pub(crate) fn new(aggregate: AggregateSpec) -> Result<Self, PipelineError> {
153        let fn_ = aggregate.fn_;
154        let is_count = fn_ == AggregateFunction::Count;
155        if is_count != aggregate.field.is_none() {
156            return Err(PipelineError::new(format!(
157                "Aggregate: {} {} field",
158                fn_.as_str(),
159                if is_count { "takes no" } else { "requires a" }
160            )));
161        }
162        if aggregate.path.is_some() && aggregate.field.is_none() {
163            return Err(PipelineError::new(
164                "Aggregate: a JSON path requires a field",
165            ));
166        }
167        Ok(Reducer { aggregate })
168    }
169
170    pub(crate) fn fn_(&self) -> AggregateFunction {
171        self.aggregate.fn_
172    }
173
174    /// The result for a state.
175    pub(crate) fn value(&self, s: &AggState) -> Value {
176        match self.fn_() {
177            AggregateFunction::Count => Value::Number(s.count as f64),
178            AggregateFunction::Sum if s.non_null == 0 => Value::Null,
179            AggregateFunction::Sum => Value::Number(s.sum),
180            AggregateFunction::Avg if s.non_null == 0 => Value::Null,
181            AggregateFunction::Avg => Value::Number(s.sum / s.non_null as f64),
182            AggregateFunction::Min | AggregateFunction::Max => s.extreme.clone(),
183        }
184    }
185
186    pub(crate) fn beats(&self, v: &Value, current: &Value) -> bool {
187        let c = compare_aggregate_values(v, current);
188        if self.fn_() == AggregateFunction::Max {
189            c == Ordering::Greater
190        } else {
191            c == Ordering::Less
192        }
193    }
194
195    /// The value `row` contributes, null when none.
196    pub(crate) fn read(&self, row: &Row) -> Value {
197        aggregate_value(&self.aggregate, row)
198    }
199
200    /// Whether an edit from `old` to `new` leaves the value reduced as it
201    /// was.
202    pub(crate) fn same_value(&self, old: &Row, new: &Row) -> bool {
203        self.aggregate.field.is_none()
204            || compare_aggregate_values(&self.read(old), &self.read(new)) == Ordering::Equal
205    }
206
207    /// Adds a row to a state being accumulated.
208    pub(crate) fn contribute(&self, s: &mut AggState, row: &Row) {
209        s.count += 1;
210        if self.aggregate.field.is_none() {
211            return;
212        }
213        let v = self.read(row);
214        if v.is_null() {
215            return;
216        }
217        s.non_null += 1;
218        match self.fn_() {
219            AggregateFunction::Sum | AggregateFunction::Avg => match v {
220                Value::Number(n) => s.sum += n,
221                _ => report(format!("Aggregate: {} needs a number", self.fn_().as_str())),
222            },
223            AggregateFunction::Min | AggregateFunction::Max => {
224                if s.extreme.is_null() || self.beats(&v, &s.extreme) {
225                    s.extreme = v;
226                }
227            }
228            AggregateFunction::Count => {}
229        }
230    }
231
232    /// The invertible delta of count, sum and avg.
233    pub(crate) fn apply_invertible(
234        &self,
235        s: &mut AggState,
236        row: &Row,
237        sign: i64,
238        field_only: bool,
239    ) {
240        if !field_only {
241            s.count += sign;
242        }
243        let Some(field) = &self.aggregate.field else {
244            return;
245        };
246        match self.read(row) {
247            Value::Null => {}
248            Value::Number(n) => {
249                s.sum += sign as f64 * n;
250                s.non_null += sign;
251            }
252            _ => report(format!(
253                "Aggregate: {}({field}) requires a number",
254                self.fn_().as_str()
255            )),
256        }
257    }
258
259    /// Min and max maintenance. Returns false when the extreme was removed
260    /// or edited away: the group must be read again.
261    pub(crate) fn push_extreme(&self, s: &mut AggState, change: &Change) -> bool {
262        match change {
263            Change::Add(node) => {
264                self.contribute(s, &node.row);
265                true
266            }
267            Change::Remove(node) => {
268                let v = self.read(&node.row);
269                s.count -= 1;
270                if v.is_null() {
271                    return true;
272                }
273                if !s.extreme.is_null()
274                    && compare_aggregate_values(&v, &s.extreme) == Ordering::Equal
275                {
276                    return false;
277                }
278                s.non_null -= 1;
279                true
280            }
281            Change::Edit { node, old_node } => self.same_value(&old_node.row, &node.row),
282            Change::Child(..) => true,
283        }
284    }
285
286    /// Whether a group's row changes from `stored` to `state`: its value,
287    /// or a sum or average's components.
288    pub(crate) fn changed(&self, stored: &AggState, state: &AggState) -> bool {
289        !identical(Some(&self.value(stored)), Some(&self.value(state)))
290            || (carries_components(self.fn_())
291                && (stored.sum != state.sum || stored.non_null != state.non_null))
292    }
293
294    /// Writes the result, and a sum or average's components, into `row`.
295    pub(crate) fn write_payload(&self, row: &mut Object, s: &AggState) {
296        row.insert(cols::VALUE, self.value(s));
297        if carries_components(self.fn_()) {
298            row.insert(cols::SUM, Value::Number(s.sum));
299            row.insert(cols::COUNT, Value::Number(s.non_null as f64));
300        }
301    }
302}
303
304/// `compareAggregateValues`: numbers before strings, as in JS and SQLite,
305/// for the leaves of a JSON path; otherwise `compareValues`. Values JS can't
306/// compare, such as the objects of a json column without a path, fail the
307/// query as JS's throw does. Equal values compare equal first, as JS's
308/// `a === b` does for one row's own value.
309pub fn compare_aggregate_values(a: &Value, b: &Value) -> Ordering {
310    match (a, b) {
311        (Value::Number(_), Value::String(_)) => Ordering::Less,
312        (Value::String(_), Value::Number(_)) => Ordering::Greater,
313        _ => match compare::compare_checked(a, b) {
314            Ok(o) => o,
315            Err(_) if a == b => Ordering::Equal,
316            Err(e) => {
317                report(e.to_string());
318                compare::compare(a, b)
319            }
320        },
321    }
322}
323
324/// `valueToKey`: a string without surrogates (in UTF-16) is `s` and the
325/// string, any other value its JSON.
326pub fn value_to_key(v: &Value) -> String {
327    match v {
328        Value::String(s) if s.chars().all(|c| (c as u32) <= 0xFFFF) => format!("s{s}"),
329        v => json::stringify(v),
330    }
331}
332
333/// Reduces the rows of a relationship per parent, or of a whole query, to
334/// an aggregate: one row per group key, `{...groupKey, _0_value}`, so a
335/// `Join` routes it as it would the child rows.
336///
337/// count, sum and avg are kept in O(1) per change. min and max are too,
338/// unless the extreme leaves; then the group is read again in `reconcile`.
339pub struct Aggregate {
340    me: Weak<Aggregate>,
341    input: Rc<dyn Input>,
342    group_key: Vec<String>,
343    reducer: Reducer,
344    schema: Rc<SourceSchema>,
345    storage: RefCell<HashMap<String, AggState>>,
346    /// min and max groups whose extreme a push removed, in insertion order,
347    /// to read again in `reconcile`. Their storage keeps the state last
348    /// sent.
349    dirty_groups: RefCell<Vec<(String, Vec<Value>)>>,
350    output: RefCell<Weak<dyn Output>>,
351}
352
353impl Aggregate {
354    pub fn new(
355        input: Rc<dyn Input>,
356        group_key: Vec<String>,
357        aggregate: AggregateSpec,
358        table_name: Option<String>,
359    ) -> Result<Rc<Self>, PipelineError> {
360        let reducer = Reducer::new(aggregate)?;
361        let input_schema = input.get_schema();
362        let (columns, primary_key) =
363            aggregate_source_schema(&input_schema.columns, &group_key, &reducer.aggregate)?;
364        let sort: Vec<OrderPart> = primary_key
365            .iter()
366            .map(|k| OrderPart {
367                field: k.clone(),
368                direction: Direction::Asc,
369            })
370            .collect();
371        let schema = Rc::new(SourceSchema {
372            table_name: table_name.unwrap_or_else(|| input_schema.table_name.clone()),
373            columns,
374            primary_key,
375            relationships: Vec::new(),
376            is_hidden: false,
377            system: input_schema.system,
378            compare_rows: make_comparator(&sort, false),
379            sort: Some(sort),
380        });
381        let op = Rc::new_cyclic(|me| Aggregate {
382            me: me.clone(),
383            input: input.clone(),
384            group_key,
385            reducer,
386            schema,
387            storage: RefCell::default(),
388            dirty_groups: RefCell::default(),
389            output: RefCell::new(no_output()),
390        });
391        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
392        Ok(op)
393    }
394
395    fn compute(&self, constraint: Option<Constraint>) -> AggState {
396        let mut s = AggState::default();
397        for node in self.input.fetch(&FetchRequest {
398            constraint,
399            ..FetchRequest::default()
400        }) {
401            self.reducer.contribute(&mut s, &node.row);
402        }
403        s
404    }
405
406    fn emit_if_changed(&self, values: &[Value], stored: &AggState, state: &AggState) {
407        if !self.reducer.changed(stored, state) {
408            return;
409        }
410        let out = self.output.borrow().upgrade();
411        if let Some(out) = out {
412            out.push(
413                Change::Edit {
414                    node: self.make_node(values, state),
415                    old_node: self.make_node(values, stored),
416                },
417                self,
418            );
419        }
420    }
421
422    fn make_node(&self, values: &[Value], state: &AggState) -> Node {
423        let mut row = Object::new();
424        for (c, v) in self.group_key.iter().zip(values) {
425            row.insert(c.clone(), v.clone());
426        }
427        if self.group_key.is_empty() {
428            row.insert(cols::KEY, Value::Number(0.0));
429        }
430        self.reducer.write_payload(&mut row, state);
431        Node::new(Rc::new(row))
432    }
433
434    fn constraint(&self, values: &[Value]) -> Constraint {
435        Constraint::new(
436            self.group_key
437                .iter()
438                .zip(values)
439                .map(|(k, v)| (k.clone(), Some(v.clone())))
440                .collect(),
441        )
442    }
443
444    /// The group a fetch is for, or `None` when its constraint lacks the
445    /// group key, which JS asserts.
446    fn group_values(&self, constraint: Option<&Constraint>) -> Option<Vec<Value>> {
447        if self.group_key.is_empty() {
448            return Some(Vec::new());
449        }
450        let Some(constraint) = constraint else {
451            report(
452                "Aggregate requires a constraint on the group key (relationship aggregate only)",
453            );
454            return None;
455        };
456        let mut values = Vec::new();
457        for c in &self.group_key {
458            if !constraint.has(c) {
459                report(format!(
460                    "Aggregate: constraint missing group key column \"{c}\""
461                ));
462                return None;
463            }
464            values.push(constraint.get(c).cloned().unwrap_or(Value::Null));
465        }
466        Some(values)
467    }
468
469    /// `stateKey`.
470    fn state_key(values: &[Value]) -> String {
471        if values.len() == 1 {
472            value_to_key(&values[0])
473        } else {
474            json::stringify(&Value::Array(values.to_vec()))
475        }
476    }
477
478    fn fetch_now(&self, req: &FetchRequest) -> NodeStream {
479        let Some(values) = self.group_values(req.constraint.as_ref()) else {
480            return empty();
481        };
482        let key = Self::state_key(&values);
483        let stored = self.storage.borrow().get(&key).cloned();
484        let state = match stored {
485            Some(s) => s,
486            None => {
487                let s = self.compute(req.constraint.clone());
488                self.storage.borrow_mut().insert(key, s.clone());
489                s
490            }
491        };
492        from_vec(vec![self.make_node(&values, &state)])
493    }
494
495    fn is_dirty(&self, key: &str) -> bool {
496        self.dirty_groups.borrow().iter().any(|(k, _)| k == key)
497    }
498}
499
500impl InputBase for Aggregate {
501    fn get_schema(&self) -> Rc<SourceSchema> {
502        self.schema.clone()
503    }
504    fn destroy(&self) {
505        self.input.destroy()
506    }
507}
508
509impl Input for Aggregate {
510    fn set_output(&self, output: Weak<dyn Output>) {
511        *self.output.borrow_mut() = output;
512    }
513
514    fn fetch(&self, req: &FetchRequest) -> NodeStream {
515        let me = self.me.clone();
516        let req = req.clone();
517        lazy(move || -> NodeStream {
518            match me.upgrade() {
519                Some(me) => me.fetch_now(&req),
520                None => empty(),
521            }
522        })
523    }
524}
525
526impl Output for Aggregate {
527    fn push(&self, change: Change, _pusher: &dyn InputBase) {
528        let row = &change.node().row;
529        let values: Vec<Value> = self
530            .group_key
531            .iter()
532            .map(|k| row.get(k).cloned().unwrap_or(Value::Null))
533            .collect();
534        let key = Self::state_key(&values);
535        // Nothing downstream has fetched the group: a later fetch computes
536        // it.
537        let Some(stored) = self.storage.borrow().get(&key).cloned() else {
538            return;
539        };
540        let mut state = stored.clone();
541        let r = &self.reducer;
542        if is_invertible(r.fn_()) {
543            match &change {
544                Change::Add(n) => r.apply_invertible(&mut state, &n.row, 1, false),
545                Change::Remove(n) => r.apply_invertible(&mut state, &n.row, -1, false),
546                Change::Edit { node, old_node } => {
547                    // Subtracting and adding again a value that didn't change
548                    // would only add rounding error.
549                    if r.same_value(&old_node.row, &node.row) {
550                        return;
551                    }
552                    r.apply_invertible(&mut state, &old_node.row, -1, true);
553                    r.apply_invertible(&mut state, &node.row, 1, true);
554                }
555                Change::Child(..) => return,
556            }
557        } else if self.is_dirty(&key) || !r.push_extreme(&mut state, &change) {
558            if !self.is_dirty(&key) {
559                self.dirty_groups.borrow_mut().push((key, values));
560            }
561            return;
562        }
563        if state.count < 0 {
564            report("Aggregate: removed a row from an empty group");
565            return;
566        }
567        self.storage.borrow_mut().insert(key, state.clone());
568        self.emit_if_changed(&values, &stored, &state);
569    }
570
571    fn reconcile(&self, _pusher: &dyn InputBase) {
572        let dirty = std::mem::take(&mut *self.dirty_groups.borrow_mut());
573        for (key, values) in dirty {
574            let Some(stored) = self.storage.borrow().get(&key).cloned() else {
575                continue;
576            };
577            let state = self.compute(Some(self.constraint(&values)));
578            self.storage.borrow_mut().insert(key, state.clone());
579            self.emit_if_changed(&values, &stored, &state);
580        }
581        let out = self.output.borrow().upgrade();
582        if let Some(out) = out {
583            out.reconcile(self);
584        }
585    }
586}