Skip to main content

zero_client/ivm/
group_by.rs

1//! `GroupBy`, `GroupProjection` and their helpers
2//! (`packages/zql/src/ivm/group-by.ts`).
3
4use super::*;
5use crate::ast::{Aggregate as AggregateSpec, Ast, Direction, OrderPart};
6use crate::json::{self, Object, Value};
7use crate::keys::aggregate_columns as cols;
8use crate::map::OrderedMap;
9use crate::schema::{Column, ValueType};
10use std::cell::{Cell, RefCell};
11use std::collections::HashMap;
12use std::rc::{Rc, Weak};
13
14/// The columns, primary key and sort of a grouped operator's rows.
15pub type GroupSchema = (OrderedMap<Column>, Vec<String>, Vec<OrderPart>);
16
17/// `groupSourceSchema`: the columns, primary key and sort of the rows
18/// `GroupBy` emits: the group columns, the group's key (`_0_key`) and the
19/// aggregate's payload, with a sum or average's row count (`_0_rows`).
20///
21/// The key is the group's values in one string, since a synced row key
22/// can't hold a `null`, which is a value like any other here.
23pub fn group_source_schema(
24    input_columns: &OrderedMap<Column>,
25    ordering: &[OrderPart],
26    aggregate: &AggregateSpec,
27) -> Result<GroupSchema, PipelineError> {
28    let group_key: Vec<String> = ordering.iter().map(|p| p.field.clone()).collect();
29    let (mut columns, _) = aggregate_source_schema(input_columns, &group_key, aggregate)?;
30    let string = Column {
31        type_: ValueType::String,
32        optional: false,
33        server_name: None,
34    };
35    columns.insert(cols::KEY, string);
36    if carries_components(aggregate.fn_) {
37        columns.insert(
38            cols::ROWS,
39            Column {
40                type_: ValueType::Number,
41                optional: false,
42                server_name: None,
43            },
44        );
45    }
46    // The key is unique and follows from the columns: it only makes the
47    // order total.
48    let mut sort = ordering.to_vec();
49    sort.push(OrderPart {
50        field: cols::KEY.to_owned(),
51        direction: Direction::Asc,
52    });
53    Ok((columns, vec![cols::KEY.to_owned()], sort))
54}
55
56/// `groupKey`: a group's `_0_key`, which also keys its state: `valueToKey`
57/// of the value for one column, the values JSON encoded for several.
58pub fn group_key(values: &[Value]) -> String {
59    if values.len() == 1 {
60        value_to_key(&values[0])
61    } else {
62        json::stringify(&Value::Array(values.to_vec()))
63    }
64}
65
66/// `groupOrdering`: the order of a grouped query's rows: its `orderBy`
67/// restricted to the group columns (its `groupBy`, or the columns a count
68/// of distinct combinations groups by), then the rest of them ascending.
69pub fn group_ordering(ast: &Ast) -> Vec<OrderPart> {
70    let columns: &[String] = ast
71        .group_by
72        .as_deref()
73        .or_else(|| ast.aggregate.as_ref().and_then(|a| a.distinct.as_deref()))
74        .unwrap_or_default();
75    let mut ordering: Vec<OrderPart> = Vec::new();
76    for part in ast.order_by.as_deref().unwrap_or_default() {
77        if columns.contains(&part.field) && !ordering.iter().any(|p| p.field == part.field) {
78            ordering.push(part.clone());
79        }
80    }
81    for column in columns {
82        if !ordering.iter().any(|p| &p.field == column) {
83            ordering.push(OrderPart {
84                field: column.clone(),
85                direction: Direction::Asc,
86            });
87        }
88    }
89    ordering
90}
91
92/// Groups its input by columns and reduces each group, as `GROUP BY` does:
93/// one row per combination of the columns' values,
94/// `{...columns, _0_key, _0_value}`, with a sum or average's components. A
95/// distinct is a GroupBy with a count, whose value a view doesn't show.
96///
97/// The input is sorted by the group columns first, so a fetch folds each
98/// run of a group in one pass. Every group's state is kept: a push adds a
99/// group with its first row, removes it with its last, and otherwise edits
100/// it when its value changes. A min or max whose extreme leaves is read
101/// again in `reconcile`, as in `Aggregate`.
102pub struct GroupBy {
103    me: Weak<GroupBy>,
104    input: Rc<dyn Input>,
105    columns: Vec<String>,
106    reducer: Reducer,
107    /// A sum or average row carries its group's row count.
108    carries_rows: bool,
109    schema: Rc<SourceSchema>,
110    storage: RefCell<HashMap<String, AggState>>,
111    /// Set by the first fetch: until then nothing downstream has the rows.
112    hydrated: Cell<bool>,
113    /// min and max groups whose extreme a push removed, with a row of the
114    /// group, in insertion order. Their storage keeps the value last sent,
115    /// with the current count.
116    dirty_groups: RefCell<Vec<(String, Row)>>,
117    output: RefCell<Weak<dyn Output>>,
118}
119
120impl GroupBy {
121    /// `ordering` names each group column once; the input must be sorted by
122    /// it first.
123    pub fn new(
124        input: Rc<dyn Input>,
125        ordering: &[OrderPart],
126        table_name: impl Into<String>,
127        aggregate: AggregateSpec,
128    ) -> Result<Rc<Self>, PipelineError> {
129        let reducer = Reducer::new(aggregate)?;
130        if ordering.is_empty() {
131            return Err(PipelineError::new("GroupBy: needs at least one column"));
132        }
133        let input_schema = input.get_schema();
134        let input_sort = input_schema.sort.as_deref().unwrap_or_default();
135        let sorted = ordering.iter().enumerate().all(|(i, part)| {
136            input_sort
137                .get(i)
138                .is_some_and(|s| s.field == part.field && s.direction == part.direction)
139        });
140        if !sorted {
141            return Err(PipelineError::new(
142                "GroupBy: the input must be sorted by the group columns first",
143            ));
144        }
145        let (columns, primary_key, sort) =
146            group_source_schema(&input_schema.columns, ordering, &reducer.aggregate)?;
147        let schema = Rc::new(SourceSchema {
148            table_name: table_name.into(),
149            columns,
150            primary_key,
151            relationships: Vec::new(),
152            is_hidden: false,
153            system: input_schema.system,
154            compare_rows: make_comparator(&sort, false),
155            sort: Some(sort),
156        });
157        let carries_rows = carries_components(reducer.fn_());
158        let op = Rc::new_cyclic(|me| GroupBy {
159            me: me.clone(),
160            input: input.clone(),
161            columns: ordering.iter().map(|p| p.field.clone()).collect(),
162            reducer,
163            carries_rows,
164            schema,
165            storage: RefCell::default(),
166            hydrated: Cell::new(false),
167            dirty_groups: RefCell::default(),
168            output: RefCell::new(no_output()),
169        });
170        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
171        Ok(op)
172    }
173
174    fn emit(&self, change: Change) {
175        let out = self.output.borrow().upgrade();
176        if let Some(out) = out {
177            out.push(change, self);
178        }
179    }
180
181    fn group_values(&self, row: &Row) -> Vec<Value> {
182        self.columns
183            .iter()
184            .map(|c| row.get(c).cloned().unwrap_or(Value::Null))
185            .collect()
186    }
187
188    fn stored(&self, key: &str) -> Option<AggState> {
189        self.storage.borrow().get(key).cloned()
190    }
191
192    /// Records `state` for the group and returns its row.
193    fn store(&self, values: &[Value], state: AggState) -> Node {
194        let node = self.make_node(values, &state);
195        self.storage.borrow_mut().insert(group_key(values), state);
196        node
197    }
198
199    fn make_node(&self, values: &[Value], state: &AggState) -> Node {
200        let mut row = Object::new();
201        for (c, v) in self.columns.iter().zip(values) {
202            row.insert(c.clone(), v.clone());
203        }
204        row.insert(cols::KEY, Value::String(group_key(values)));
205        self.reducer.write_payload(&mut row, state);
206        if self.carries_rows {
207            row.insert(cols::ROWS, Value::Number(state.count as f64));
208        }
209        Node::new(Rc::new(row))
210    }
211
212    fn is_dirty(&self, key: &str) -> bool {
213        self.dirty_groups.borrow().iter().any(|(k, _)| k == key)
214    }
215
216    /// `Map.set`: a group already dirty keeps its place.
217    fn mark_dirty(&self, key: &str, row: &Row) {
218        let mut dirty = self.dirty_groups.borrow_mut();
219        match dirty.iter_mut().find(|(k, _)| k == key) {
220            Some(entry) => entry.1 = row.clone(),
221            None => dirty.push((key.to_owned(), row.clone())),
222        }
223    }
224
225    /// Stores `state` and sends the move from `stored` downstream, if any.
226    fn emit_if_changed(&self, values: &[Value], stored: &AggState, state: AggState) {
227        let changed = self.reducer.changed(stored, &state)
228            || (self.carries_rows && stored.count != state.count);
229        let node = self.make_node(values, &state);
230        self.storage.borrow_mut().insert(group_key(values), state);
231        // A row whose field is null moves only a sum or average's row count.
232        if changed {
233            self.emit(Change::Edit {
234                node,
235                old_node: self.make_node(values, stored),
236            });
237        }
238    }
239
240    fn add(&self, row: &Row) {
241        let values = self.group_values(row);
242        let key = group_key(&values);
243        let Some(stored) = self.stored(&key) else {
244            let mut state = AggState::default();
245            self.reducer.contribute(&mut state, row);
246            let node = self.store(&values, state);
247            return self.emit(Change::Add(node));
248        };
249        let mut state = stored.clone();
250        if self.is_dirty(&key) {
251            // Read again in reconcile; only the count is kept up to date.
252            state.count += 1;
253            self.storage.borrow_mut().insert(key, state);
254            return;
255        }
256        self.reducer.contribute(&mut state, row);
257        self.emit_if_changed(&values, &stored, state);
258    }
259
260    fn remove(&self, row: &Row) {
261        let values = self.group_values(row);
262        let key = group_key(&values);
263        let Some(stored) = self.stored(&key) else {
264            return report("GroupBy: removed a row of a group it lacks");
265        };
266        if stored.count == 1 {
267            self.storage.borrow_mut().remove(&key);
268            self.dirty_groups.borrow_mut().retain(|(k, _)| *k != key);
269            return self.emit(Change::Remove(self.make_node(&values, &stored)));
270        }
271        let mut state = stored.clone();
272        if is_invertible(self.reducer.fn_()) {
273            self.reducer.apply_invertible(&mut state, row, -1, false);
274        } else if self.is_dirty(&key)
275            || !self
276                .reducer
277                .push_extreme(&mut state, &Change::Remove(Node::new(row.clone())))
278        {
279            // Keep what was last sent downstream, with the count down by one.
280            self.mark_dirty(&key, row);
281            let mut kept = stored;
282            kept.count -= 1;
283            self.storage.borrow_mut().insert(key, kept);
284            return;
285        }
286        self.emit_if_changed(&values, &stored, state);
287    }
288
289    /// An edit within a group.
290    fn update(&self, old_row: &Row, row: &Row) {
291        let values = self.group_values(row);
292        let key = group_key(&values);
293        let Some(stored) = self.stored(&key) else {
294            return;
295        };
296        if self.is_dirty(&key) || self.reducer.same_value(old_row, row) {
297            return;
298        }
299        if !is_invertible(self.reducer.fn_()) {
300            // The extreme may have moved either way.
301            return self.mark_dirty(&key, row);
302        }
303        let mut state = stored.clone();
304        self.reducer.apply_invertible(&mut state, old_row, -1, true);
305        self.reducer.apply_invertible(&mut state, row, 1, true);
306        self.emit_if_changed(&values, &stored, state);
307    }
308
309    /// Reads the rows of `row`'s group. It leaves out the null values, which
310    /// a constraint never matches, so it can read rows of other groups too,
311    /// which the caller skips.
312    fn constraint(&self, row: &Row) -> Option<Constraint> {
313        let mut constraint: Option<Constraint> = None;
314        for c in &self.columns {
315            match row.get(c) {
316                None | Some(Value::Null) => {}
317                Some(v) => constraint
318                    .get_or_insert_with(Constraint::default)
319                    .set(c, Some(v.clone())),
320            }
321        }
322        constraint
323    }
324
325    fn fetch_now(self: &Rc<Self>, req: &FetchRequest) -> NodeStream {
326        // A top-level query without a bound: the view reads every row once.
327        if req.constraint.is_some() || req.start.is_some() || req.reverse {
328            report("GroupBy: fetch takes no constraint, start or reverse");
329            return empty();
330        }
331        self.hydrated.set(true);
332        let me = self.clone();
333        // The first row of the current run, and its group's state.
334        let mut first: Option<Row> = None;
335        let mut state = AggState::default();
336        let mut it = self.input.fetch(&FetchRequest::default());
337        let mut done = false;
338        Box::new(std::iter::from_fn(move || {
339            while !done {
340                let Some(node) = it.next() else {
341                    done = true;
342                    let first = first.take()?;
343                    let values = me.group_values(&first);
344                    return Some(me.store(&values, std::mem::take(&mut state)));
345                };
346                if let Some(current) = &first
347                    && row_equals_for_compound_key(current, &node.row, &me.columns)
348                {
349                    me.reducer.contribute(&mut state, &node.row);
350                    continue;
351                }
352                let finished = first.take().map(|f| {
353                    let values = me.group_values(&f);
354                    me.store(&values, std::mem::take(&mut state))
355                });
356                first = Some(node.row.clone());
357                me.reducer.contribute(&mut state, &node.row);
358                if finished.is_some() {
359                    return finished;
360                }
361            }
362            None
363        }))
364    }
365}
366
367impl InputBase for GroupBy {
368    fn get_schema(&self) -> Rc<SourceSchema> {
369        self.schema.clone()
370    }
371    fn destroy(&self) {
372        self.input.destroy()
373    }
374}
375
376impl Input for GroupBy {
377    fn set_output(&self, output: Weak<dyn Output>) {
378        *self.output.borrow_mut() = output;
379    }
380
381    fn fetch(&self, req: &FetchRequest) -> NodeStream {
382        let me = self.me.clone();
383        let req = req.clone();
384        lazy(move || -> NodeStream {
385            match me.upgrade() {
386                Some(me) => me.fetch_now(&req),
387                None => empty(),
388            }
389        })
390    }
391}
392
393impl Output for GroupBy {
394    fn push(&self, change: Change, _pusher: &dyn InputBase) {
395        if !self.hydrated.get() {
396            return;
397        }
398        match change {
399            Change::Add(node) => self.add(&node.row),
400            Change::Remove(node) => self.remove(&node.row),
401            Change::Edit { node, old_node } => {
402                if row_equals_for_compound_key(&old_node.row, &node.row, &self.columns) {
403                    self.update(&old_node.row, &node.row);
404                } else {
405                    self.remove(&old_node.row);
406                    self.add(&node.row);
407                }
408            }
409            // The input has no relationships the group rows show.
410            Change::Child(..) => {}
411        }
412    }
413
414    fn reconcile(&self, _pusher: &dyn InputBase) {
415        let dirty = std::mem::take(&mut *self.dirty_groups.borrow_mut());
416        for (key, group_row) in dirty {
417            // Its last row may have gone in the meantime.
418            let Some(stored) = self.stored(&key) else {
419                continue;
420            };
421            let mut state = AggState::default();
422            for node in self.input.fetch(&FetchRequest {
423                constraint: self.constraint(&group_row),
424                ..FetchRequest::default()
425            }) {
426                if row_equals_for_compound_key(&node.row, &group_row, &self.columns) {
427                    self.reducer.contribute(&mut state, &node.row);
428                }
429            }
430            self.emit_if_changed(&self.group_values(&group_row), &stored, state);
431        }
432        let out = self.output.borrow().upgrade();
433        if let Some(out) = out {
434            out.reconcile(self);
435        }
436    }
437}
438
439/// A group column as a view shows it: its name in the view and in the
440/// input.
441#[derive(Clone, Debug)]
442pub struct ProjectedColumn {
443    pub out: String,
444    pub from: String,
445}
446
447/// Turns the rows of a `GroupBy`, or of the source a synced client reads
448/// them from, into the rows a view shows: the group columns under the
449/// query's names and, for a `groupBy()` with an aggregate, its value under
450/// `value_name` (`count`, `sum`, …). A `distinct()` shows no value, so an
451/// edit, which only moves its count, doesn't reach the view.
452pub struct GroupProjection {
453    input: Rc<dyn Input>,
454    projection: Rc<(Vec<ProjectedColumn>, Option<String>)>,
455    schema: Rc<SourceSchema>,
456    output: RefCell<Weak<dyn Output>>,
457}
458
459fn project(projection: &(Vec<ProjectedColumn>, Option<String>), node: &Node) -> Node {
460    let (columns, value_name) = projection;
461    let mut row = Object::new();
462    for c in columns {
463        if let Some(v) = node.row.get(&c.from) {
464            row.insert(c.out.clone(), v.clone());
465        }
466    }
467    if let Some(name) = value_name
468        && let Some(v) = node.row.get(cols::VALUE)
469    {
470        row.insert(name.clone(), v.clone());
471    }
472    Node::new(Rc::new(row))
473}
474
475impl GroupProjection {
476    pub fn new(
477        input: Rc<dyn Input>,
478        columns: Vec<ProjectedColumn>,
479        value_name: Option<String>,
480    ) -> Result<Rc<Self>, PipelineError> {
481        // The value would overwrite the group column. The query builder
482        // rejects that; a hand-built AST can still name one.
483        if let Some(name) = &value_name
484            && columns.iter().any(|c| &c.out == name)
485        {
486            return Err(PipelineError::new(format!(
487                "groupBy(): the column \"{name}\" has the same name as the {name}() value"
488            )));
489        }
490        let input_schema = input.get_schema();
491        let view_name = |field: &str| columns.iter().find(|c| c.from == field).map(|c| &c.out);
492        let sort: Vec<OrderPart> = input_schema
493            .sort
494            .as_deref()
495            .unwrap_or_default()
496            .iter()
497            .filter_map(|p| {
498                view_name(&p.field).map(|out| OrderPart {
499                    field: out.clone(),
500                    direction: p.direction,
501                })
502            })
503            .collect();
504        let mut view_columns = OrderedMap::new();
505        for c in &columns {
506            if let Some(col) = input_schema.columns.get(&c.from) {
507                view_columns.insert(c.out.clone(), col.clone());
508            }
509        }
510        if let Some(name) = &value_name
511            && let Some(col) = input_schema.columns.get(cols::VALUE)
512        {
513            view_columns.insert(name.clone(), col.clone());
514        }
515        let schema = Rc::new(SourceSchema {
516            table_name: input_schema.table_name.clone(),
517            columns: view_columns,
518            primary_key: columns.iter().map(|c| c.out.clone()).collect(),
519            relationships: Vec::new(),
520            is_hidden: false,
521            system: input_schema.system,
522            compare_rows: make_comparator(&sort, false),
523            sort: Some(sort),
524        });
525        let op = Rc::new(GroupProjection {
526            input: input.clone(),
527            projection: Rc::new((columns, value_name)),
528            schema,
529            output: RefCell::new(no_output()),
530        });
531        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
532        Ok(op)
533    }
534
535    fn emit(&self, change: Change) {
536        let out = self.output.borrow().upgrade();
537        if let Some(out) = out {
538            out.push(change, self);
539        }
540    }
541}
542
543impl InputBase for GroupProjection {
544    fn get_schema(&self) -> Rc<SourceSchema> {
545        self.schema.clone()
546    }
547    fn destroy(&self) {
548        self.input.destroy()
549    }
550}
551
552impl Input for GroupProjection {
553    fn set_output(&self, output: Weak<dyn Output>) {
554        *self.output.borrow_mut() = output;
555    }
556
557    fn fetch(&self, req: &FetchRequest) -> NodeStream {
558        let projection = self.projection.clone();
559        Box::new(self.input.fetch(req).map(move |n| project(&projection, &n)))
560    }
561}
562
563impl Output for GroupProjection {
564    fn push(&self, change: Change, _pusher: &dyn InputBase) {
565        let p = &self.projection;
566        match change {
567            Change::Add(n) => self.emit(Change::Add(project(p, &n))),
568            Change::Remove(n) => self.emit(Change::Remove(project(p, &n))),
569            Change::Edit { node, old_node } => {
570                // A row's key is its group's values, so an edit only moves
571                // its value, which a distinct doesn't show.
572                if p.1.is_none()
573                    || identical(node.row.get(cols::VALUE), old_node.row.get(cols::VALUE))
574                {
575                    return;
576                }
577                self.emit(Change::Edit {
578                    node: project(p, &node),
579                    old_node: project(p, &old_node),
580                });
581            }
582            Change::Child(..) => {}
583        }
584    }
585
586    fn reconcile(&self, _pusher: &dyn InputBase) {
587        let out = self.output.borrow().upgrade();
588        if let Some(out) = out {
589            out.reconcile(self);
590        }
591    }
592}