Skip to main content

ic_db/store/query/aggregate/
mod.rs

1//! Bounded aggregates over the shared scanner and exact reducers, without row history.
2pub(super) mod jobs;
3mod numeric;
4
5use super::{
6    Comparison, MAX_COMPARISON_KEY, MAX_DISTINCT_VALUES, MAX_STATE_BYTES, MAX_TERMS, Plan, Query,
7    QueryPage, admit_ordered_fields, admit_output, admit_projection, comparison_key,
8    copy_projection, execute, projection_size,
9};
10use crate::{
11    Entity, EntitySchema, Error, FieldType, IndexValue, TypeSchema, Value, ValueSchema,
12    codec::Decoder, key,
13};
14use ic_storage::Memory;
15use std::collections::{BTreeMap, BTreeSet};
16
17const MAX_GROUPS: usize = 32;
18
19/// Completed-group ordering. Aggregate ties always use ascending canonical keys.
20#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
21pub enum GroupOrder {
22    /// Ascending group-key tuple, in canonical field-name order (the default).
23    #[default]
24    Key,
25    /// Ascending aggregate value; absent values precede present values.
26    AggregateAscending,
27    /// Descending aggregate value; absent values follow present values.
28    AggregateDescending,
29    /// Descending group-key tuple, in canonical field-name order; absence sorts last.
30    KeyDescending,
31}
32
33#[derive(Default)]
34pub(super) struct GroupRequest<'a> {
35    // The final bool joins this term to the next alternative in one OR clause.
36    predicates: Vec<(Comparison, IndexValue<'a>, bool)>,
37    order: Option<GroupOrder>,
38    page: Option<jobs::pages::PageRequest<'a>>,
39}
40impl GroupRequest<'_> {
41    pub(super) fn is_empty(&self) -> bool {
42        self.predicates.is_empty() && self.order.is_none() && self.page.is_none()
43    }
44
45    fn admit(&self, entity: &EntitySchema, reducer: &Reducer) -> Result<Selection, Error> {
46        if self
47            .page
48            .is_some_and(|page| !(1..=MAX_GROUPS).contains(&page.size))
49        {
50            return Err(Error::Limit);
51        }
52        let field = match reducer {
53            Reducer::Count { .. } | Reducer::Distinct { .. } => ValueSchema {
54                value: FieldType::Nat64,
55                optional: false,
56            },
57            Reducer::Extremum { position, .. } => {
58                let field = &entity.fields[*position];
59                ValueSchema {
60                    value: field.value,
61                    optional: field.optional,
62                }
63            }
64            Reducer::Numeric(state) => state.output(),
65        };
66        // Extrema/numeric results may be absent even with required input fields.
67        let absent_result = !matches!(reducer, Reducer::Count { .. } | Reducer::Distinct { .. });
68        let predicates = self
69            .predicates
70            .iter()
71            .map(|&(comparison, value, or_next)| {
72                if match value {
73                    IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
74                    IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
75                    _ => false,
76                } {
77                    return Err(Error::Limit);
78                }
79                comparison.admit(field.value, absent_result, value)?;
80                let key = if value == IndexValue::Absent {
81                    None
82                } else {
83                    let mut key = Vec::new();
84                    value.append_component(field.optional, &mut key);
85                    if key.len() > MAX_COMPARISON_KEY {
86                        return Err(Error::Limit);
87                    }
88                    Some(key)
89                };
90                Ok((comparison, key, or_next))
91            })
92            .collect::<Result<_, Error>>()?;
93        Ok(Selection {
94            predicates,
95            order: self.order.unwrap_or_default(),
96            optional: field.optional,
97        })
98    }
99}
100
101struct Selection {
102    predicates: Vec<(Comparison, Option<Vec<u8>>, bool)>,
103    order: GroupOrder,
104    // Physical comparison-key framing, distinct from an absent aggregate result.
105    optional: bool,
106}
107
108/// A completed aggregate and its execution costs. No partial result or cursor.
109#[derive(Debug)]
110pub struct Aggregate<T> {
111    /// Completed value over all matching input rows.
112    pub value: T,
113    /// Examined primary/index candidates, including residual nonmatches.
114    pub examined: usize,
115    /// Fetched and validated source rows.
116    pub fetched: usize,
117    /// Encoded result bytes, excluding transport framing.
118    pub output_bytes: usize,
119}
120
121/// One complete group. Absent optional key values belong to a group too.
122#[derive(Debug)]
123pub struct GroupCount<K> {
124    /// Projected grouping tuple in an ordinary named record.
125    pub key: K,
126    /// Matching rows, or present operand values for `group_count_field`.
127    pub count: u64,
128}
129
130/// One complete group's aggregate value, preserving all-absent groups.
131#[derive(Debug)]
132pub struct GroupValue<K, R> {
133    /// Projected grouping tuple, including optional absent keys.
134    pub key: K,
135    /// Single-field result record, or `None` when the group has no present operand.
136    pub value: Option<R>,
137}
138
139impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
140    /// Page completed retained groups, returning at most 1..=32 rows per response.
141    /// `limit` still caps the complete selected result and binds the job. Page size
142    /// and byte allowance may change. Supply None for the first page; continuation
143    /// is valid only for a completed job. Only grouped resume terminals accept this.
144    #[must_use]
145    pub fn group_page(mut self, size: usize, after: Option<&'a jobs::GroupCursor>) -> Self {
146        self.request.groups.page = Some(jobs::pages::PageRequest { size, after });
147        self
148    }
149
150    /// Add an AND predicate on the completed aggregate value, before group ordering
151    /// and output limits. At most eight terms. Counts require Nat64 operands;
152    /// extrema require the source type; sums require the declared result type.
153    /// Absent values support Eq/Ne only. Text and Blob extrema also accept StartsWith,
154    /// EndsWith and Contains.
155    /// Only grouped terminals accept this modifier, even for empty input.
156    #[must_use]
157    pub fn filter_groups(
158        mut self,
159        comparison: Comparison,
160        value: impl Into<IndexValue<'a>>,
161    ) -> Self {
162        if self.request.groups.predicates.len() == MAX_TERMS {
163            self.request.over_limit = true;
164        } else {
165            self.request
166                .groups
167                .predicates
168                .push((comparison, value.into(), false));
169        }
170        self
171    }
172
173    /// Add an OR clause on completed aggregate values, ANDed with other group
174    /// filters. The clause must be nonempty; all group filters together permit
175    /// eight comparisons. Every operand is admitted before reading any rows.
176    /// Uses `filter_groups`' exact type and absence rules. All groups must finish
177    /// and validate before selection, ordering and output limits. Clause boundaries
178    /// bind retained jobs; a singleton clause is equivalent to `filter_groups`.
179    #[must_use]
180    pub fn filter_groups_any(mut self, alternatives: &[(Comparison, IndexValue<'a>)]) -> Self {
181        let count = alternatives.len();
182        if count == 0 || count > MAX_TERMS - self.request.groups.predicates.len() {
183            self.request.over_limit = true;
184        } else {
185            self.request.groups.predicates.extend(
186                alternatives
187                    .iter()
188                    .enumerate()
189                    .map(|(i, &(comparison, value))| (comparison, value, i + 1 != count)),
190            );
191        }
192        self
193    }
194
195    /// Order completed groups before applying output limits. Only grouped
196    /// terminals accept this modifier. The last call selects the order.
197    #[must_use]
198    pub fn order_groups(mut self, order: GroupOrder) -> Self {
199        self.request.groups.order = Some(order);
200        self
201    }
202
203    /// Minimum present value of an exact single-field record projection.
204    /// Supports ordered scalars/unit enums without requiring an index. The result
205    /// preserves the declared type and optionality; empty/all-absent input returns
206    /// `None`. `limit` never truncates input. Only the winning record's bytes count
207    /// toward the engine output bound; an absent result occupies zero payload bytes.
208    /// # Errors
209    /// Refuses multi-field projections, unsupported types, cursors, DISTINCT and
210    /// explicit ordering. Work exhaustion or a comparison key beyond 4096 bytes
211    /// returns `Limit`; an oversized winning result returns `RowTooLarge`.
212    /// Ordinary projection/query errors apply. Completion must precede `work_limit`.
213    /// # Panics
214    /// Supplier corruption traps without repair.
215    pub fn min<R: Value>(self) -> Result<Aggregate<Option<R>>, Error> {
216        self.extremum(false)
217    }
218
219    /// Maximum present value, with the same types, bounds and empty-input behavior
220    /// as [`Self::min`]. Equal operands retain the first encountered value.
221    /// # Errors
222    /// The same projection, resource and query errors as [`Self::min`].
223    /// # Panics
224    /// Supplier corruption traps without repair.
225    pub fn max<R: Value>(self) -> Result<Aggregate<Option<R>>, Error> {
226        self.extremum(true)
227    }
228
229    fn extremum<R: Value>(self, maximum: bool) -> Result<Aggregate<Option<R>>, Error> {
230        let (plan, reducer) = self.extremum_plan::<R>(maximum)?;
231        self.scalar_value(&plan, reducer)
232    }
233
234    fn extremum_plan<R: Value>(&self, maximum: bool) -> Result<(Plan<'a>, Reducer), Error> {
235        let plan = self.aggregate_plan(Some(R::definition()), false)?;
236        let reducer = Reducer::extremum(
237            E::SCHEMA,
238            plan.projection.ok_or(Error::InvalidQuery)?,
239            maximum,
240        )?;
241        Ok((plan, reducer))
242    }
243
244    fn scalar_value<R: Value>(
245        self,
246        plan: &Plan<'_>,
247        mut reducer: Reducer,
248    ) -> Result<Aggregate<Option<R>>, Error> {
249        let page = execute(
250            &self.db.map,
251            E::SCHEMA,
252            &self.request,
253            plan,
254            Some(Accumulator::Scalar(&mut reducer)),
255        )?;
256        let mut output_bytes = 0;
257        let value = reducer
258            .finish()?
259            .into_value()?
260            .map(|bytes| {
261                admit_output(bytes.len(), self.request.bytes, &mut output_bytes)?;
262                decode_record(&bytes)
263            })
264            .transpose()?;
265        Ok(Aggregate {
266            value,
267            examined: page.examined,
268            fetched: page.fetched,
269            output_bytes,
270        })
271    }
272
273    /// Minimum present operand per group. `K` is an exact grouping record; `R`
274    /// is an exact single-field operand record. They may overlap. All-absent
275    /// groups retain `None`; empty input yields no groups. No index is required.
276    /// Groups default to ascending canonical field-name tuple order;
277    /// `filter_groups` and `order_groups` select completed results. `limit` selects
278    /// completed groups, never input rows. Output bytes are the key record plus
279    /// the present winning record; transport option framing is excluded.
280    /// At most 32 groups and 128 KiB of retained keys, records and reducer payloads
281    /// are admitted. Every comparison key is bounded to 4096 bytes. Winner growth
282    /// is charged, and replacement releases the previous winner's charge.
283    /// # Errors
284    /// The projection, work and shape refusals of [`Self::min`] apply. Group or
285    /// retained-state exhaustion returns `Limit`. An oversized output group
286    /// returns `RowTooLarge`; combined output exhaustion returns `Limit`.
287    /// # Panics
288    /// Supplier corruption traps without repair.
289    pub fn group_min<K: Value, R: Value>(self) -> Result<Aggregate<Vec<GroupValue<K, R>>>, Error> {
290        self.group_extrema(false)
291    }
292
293    /// Maximum present operand per group, with the contract of [`Self::group_min`].
294    /// # Errors
295    /// The same projection, work, state, shape and output refusals as grouped minimum.
296    /// # Panics
297    /// Supplier corruption traps without repair.
298    pub fn group_max<K: Value, R: Value>(self) -> Result<Aggregate<Vec<GroupValue<K, R>>>, Error> {
299        self.group_extrema(true)
300    }
301
302    fn group_extrema<K: Value, R: Value>(
303        self,
304        maximum: bool,
305    ) -> Result<Aggregate<Vec<GroupValue<K, R>>>, Error> {
306        let (plan, initial) = self.group_extremum_plan::<K, R>(maximum)?;
307        self.group_values(&plan, initial)
308    }
309
310    fn group_extremum_plan<K: Value, R: Value>(
311        &self,
312        maximum: bool,
313    ) -> Result<(Plan<'a>, Reducer), Error> {
314        let mut plan = self.aggregate_plan(Some(K::definition()), true)?;
315        let operand = admit_projection(E::SCHEMA, R::definition())?;
316        let initial = Reducer::extremum(E::SCHEMA, operand, maximum)?;
317        plan.selected |= operand;
318        Ok((plan, initial))
319    }
320
321    fn group_values<K: Value, R: Value>(
322        self,
323        plan: &Plan<'_>,
324        initial: Reducer,
325    ) -> Result<Aggregate<Vec<GroupValue<K, R>>>, Error> {
326        let (groups, page) = self.grouped(plan, initial)?;
327        let (value, output_bytes) = value_output(groups, self.request.rows, self.request.bytes)?;
328        Ok(Aggregate {
329            value,
330            examined: page.examined,
331            fetched: page.fetched,
332            output_bytes,
333        })
334    }
335
336    /// Whether at least one row matches, without materializing an entity.
337    /// Can seek a mandatory equality prefix and evaluate remaining filters on its owner rows.
338    /// Stops after validating the first matching row; later rows are not inspected.
339    /// Returns false only after observing the end of the selected input.
340    /// `limit` does not truncate input. The boolean result occupies one byte.
341    /// # Errors
342    /// Refuses cursors, DISTINCT, explicit ordering and group modifiers, as for
343    /// `count`. Exhausting `work_limit` without a match returns `Limit`, never
344    /// false; an exact-boundary no-match scan can conservatively refuse.
345    /// Ordinary admission and examined-row integrity errors still apply.
346    /// # Panics
347    /// Supplier corruption traps without repair, as for ordinary query execution.
348    pub fn exists(self) -> Result<Aggregate<bool>, Error> {
349        let mut plan = self.aggregate_plan(None, false)?;
350        self.select_aggregate_row_path(&mut plan)?;
351        let mut found = false;
352        let page = execute(
353            &self.db.map,
354            E::SCHEMA,
355            &self.request,
356            &plan,
357            Some(Accumulator::Exists(&mut found)),
358        )?;
359        Ok(Aggregate {
360            value: found,
361            examined: page.examined,
362            fetched: page.fetched,
363            output_bytes: 1,
364        })
365    }
366
367    /// Count all matching rows in one synchronous execution. Empty input yields zero.
368    /// Uses maintained cardinality for unfiltered input and physical index keys for
369    /// fully covered index ranges or primary-key comparison ranges. A partially covered
370    /// equality prefix narrows the owner rows checked by the remaining predicates. Use
371    /// [`Self::count_validated`] to check each visited row and selected index owner.
372    /// `limit` does not limit input; the scalar output occupies eight bytes.
373    /// Completion must be established within `work_limit`; an exact-boundary
374    /// scan can conservatively refuse. Use `start_count`/`resume_count` for retained work.
375    /// # Errors
376    /// Refuses cursors, DISTINCT, explicit ordering and the ordinary query failures.
377    /// Work exhaustion returns `Limit`, never a partial count. Too few output bytes
378    /// returns `RowTooLarge`.
379    /// # Panics
380    /// Supplier corruption traps without repair, as for ordinary query execution.
381    pub fn count(self) -> Result<Aggregate<u64>, Error> {
382        if self.request.bytes < 8 {
383            return Err(Error::RowTooLarge);
384        }
385        let mut plan = self.aggregate_plan(None, false)?;
386        if self.request.predicates.is_empty() && self.request.index.is_none() {
387            return Ok(Aggregate {
388                value: self.db.cardinality::<E>()?,
389                examined: 0,
390                fetched: 0,
391                output_bytes: 8,
392            });
393        }
394        if super::range::covers_primary(&plan)
395            || super::order::select_aggregate_prefix(E::SCHEMA, &self.request, &mut plan)?
396        {
397            return self.count_keys(&plan);
398        }
399        let reducer = self.count_reducer(None)?;
400        self.scalar_count_value(&plan, reducer)
401    }
402
403    /// Count by validating each visited row, including its selected index entry.
404    /// # Errors
405    /// Returns the same admission and resource errors as [`Self::count`], and
406    /// reports corruption encountered during traversal.
407    pub fn count_validated(self) -> Result<Aggregate<u64>, Error> {
408        self.scalar_count(None)
409    }
410
411    /// Count physical entries in the range selected by `using_index` and its
412    /// leading operands. This reads neither index values nor owner rows. A
413    /// dangling index entry counts as one. Use [`Self::count_validated`] to validate rows.
414    /// Like other scalar counts, the row limit does not truncate the input.
415    /// # Errors
416    /// Requires an explicit index. Row predicates, ordering, cursors, grouping
417    /// and DISTINCT refuse. Reaching the work limit before observing completion
418    /// returns `Limit`; fewer than eight output bytes returns `RowTooLarge`.
419    /// # Panics
420    /// Malformed supplier storage can trap during traversal.
421    pub fn count_index_entries(self) -> Result<Aggregate<u64>, Error> {
422        if self.request.index.is_none() || !self.request.predicates.is_empty() {
423            return Err(Error::InvalidQuery);
424        }
425        if self.request.bytes < 8 {
426            return Err(Error::RowTooLarge);
427        }
428        let plan = self.aggregate_plan(None, false)?;
429        self.count_keys(&plan)
430    }
431
432    fn count_keys(&self, plan: &Plan<'_>) -> Result<Aggregate<u64>, Error> {
433        let bounds = super::range::bounds(E::SCHEMA, &self.request, plan)?;
434        let mut examined = 0;
435        if let Some(range) = bounds {
436            let terminal = super::range::terminal_key(&range, false);
437            let entries = self.db.map.range((range.0.as_ref(), range.1.as_ref()));
438            for entry in entries.take(self.request.work) {
439                examined += 1;
440                if examined == self.request.work && terminal.is_none_or(|end| end != entry.key()) {
441                    return Err(Error::Limit);
442                }
443            }
444        }
445        Ok(Aggregate {
446            value: examined as u64,
447            examined,
448            fetched: 0,
449            output_bytes: 8,
450        })
451    }
452
453    /// Count present values of a top-level field, including non-scalar fields.
454    /// Empty input and all-absent input yield zero; present empty values count.
455    /// Limits, refusals and corruption traps are the same as [`Self::count`].
456    /// # Errors
457    /// Unknown fields refuse even for empty input. Ordinary count errors apply.
458    /// # Panics
459    /// Supplier corruption traps without repair.
460    pub fn count_field(self, field: &str) -> Result<Aggregate<u64>, Error> {
461        self.scalar_count(Some(field))
462    }
463
464    /// Count distinct projected tuples, including absent values. An indexed filter can narrow the input.
465    /// Retain at most 32 distinct comparison keys, each at most 4096 bytes, within
466    /// the shared 128-KiB state bound. No projected records are retained. `limit`
467    /// never truncates this count. The scalar result occupies eight bytes.
468    /// # Errors
469    /// Ordinary count/projection errors and distinct-state exhaustion refuse.
470    /// # Panics
471    /// Supplier corruption traps without repair.
472    pub fn count_distinct<K: Value>(self) -> Result<Aggregate<u64>, Error> {
473        if self.request.bytes < 8 {
474            return Err(Error::RowTooLarge);
475        }
476        let (mut plan, reducer) = self.distinct_plan::<K>()?;
477        self.select_aggregate_row_path(&mut plan)?;
478        self.scalar_count_value(&plan, reducer)
479    }
480
481    fn distinct_plan<K: Value>(&self) -> Result<(Plan<'static>, Reducer), Error> {
482        let plan = self.aggregate_plan(Some(K::definition()), false)?;
483        let reducer = Reducer::distinct(plan.projection.ok_or(Error::InvalidQuery)?);
484        Ok((plan, reducer))
485    }
486
487    fn select_aggregate_row_path(&self, plan: &mut Plan<'static>) -> Result<(), Error> {
488        if plan.index.is_none() && !super::range::covers_primary(plan) {
489            super::order::select_aggregate_prefix(E::SCHEMA, &self.request, plan)?;
490        }
491        Ok(())
492    }
493
494    fn scalar_count(self, field: Option<&str>) -> Result<Aggregate<u64>, Error> {
495        if self.request.bytes < 8 {
496            return Err(Error::RowTooLarge);
497        }
498        let mut plan = self.aggregate_plan(None, false)?;
499        self.select_aggregate_row_path(&mut plan)?;
500        let reducer = self.count_reducer(field)?;
501        self.scalar_count_value(&plan, reducer)
502    }
503
504    fn scalar_count_value(
505        self,
506        plan: &Plan<'_>,
507        mut reducer: Reducer,
508    ) -> Result<Aggregate<u64>, Error> {
509        let page = execute(
510            &self.db.map,
511            E::SCHEMA,
512            &self.request,
513            plan,
514            Some(Accumulator::Scalar(&mut reducer)),
515        )?;
516        Ok(Aggregate {
517            value: reducer.finish()?.into_count()?,
518            examined: page.examined,
519            fetched: page.fetched,
520            output_bytes: 8,
521        })
522    }
523
524    /// Count matching rows grouped by an exact named-record projection.
525    /// Keys support ordered scalars/unit enums, including optional absence; no index
526    /// is required. Results default to ascending tuple order in canonical field-name order.
527    /// `filter_groups` and `order_groups` select completed results before output limits.
528    /// `limit` selects the first completed groups (1..=32), never input rows.
529    /// The engine output allowance bounds key-record bytes plus eight count bytes per group.
530    /// Empty input yields no groups. At most 32 groups and 128 KiB of key/output
531    /// state may be retained, independently of the requested output limit;
532    /// each comparison key is capped at 4096 bytes, independently of index-key limits.
533    /// # Errors
534    /// Refuses unsupported key types, cursors, DISTINCT and explicit ordering.
535    /// Work, group or retained-state exhaustion returns `Limit`, never partial groups.
536    /// Completion must be established within `work_limit`; a boundary scan can refuse.
537    /// Ordinary projection/query integrity and byte-limit errors also apply.
538    /// # Panics
539    /// Supplier corruption traps without repair, as for ordinary query execution.
540    pub fn group_count<K: Value>(self) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
541        self.group_counts(None)
542    }
543
544    /// Count present operand values within each projected group. Groups whose
545    /// operands are all absent remain in the output with count zero. The operand
546    /// may be any top-level stored field and need not belong to the group key.
547    /// Bounds and ordering are the same as [`Self::group_count`].
548    /// # Errors
549    /// Unknown operands and ordinary grouped-count errors refuse.
550    /// # Panics
551    /// Supplier corruption traps without repair.
552    pub fn group_count_field<K: Value>(
553        self,
554        field: &str,
555    ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
556        self.group_counts(Some(field))
557    }
558
559    /// Count distinct projected `R` tuples within each projected `K` group.
560    /// Absence is a tuple component, as for [`Self::count_distinct`]; an all-absent
561    /// group has one distinct tuple, not zero. Projections may overlap. No index
562    /// is required. Complete input before group filtering/order and output limits.
563    /// Retain at most 32 groups and 32 distinct tuples per group, with one shared
564    /// 128-KiB state allowance and a 4096-byte cap per comparison key.
565    /// # Errors
566    /// Refuses unsupported projections, cursors, DISTINCT and explicit input order.
567    /// Work, cardinality or byte exhaustion returns `Limit`, never partial counts.
568    /// Ordinary grouped-count output and integrity errors apply.
569    /// # Panics
570    /// Supplier corruption traps without repair.
571    pub fn group_count_distinct<K: Value, R: Value>(
572        self,
573    ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
574        let (plan, reducer) = self.group_distinct_plan::<K, R>()?;
575        self.group_count_values(plan, reducer)
576    }
577
578    fn group_distinct_plan<K: Value, R: Value>(&self) -> Result<(Plan<'static>, Reducer), Error> {
579        let mut plan = self.aggregate_plan(Some(K::definition()), true)?;
580        let operand = admit_projection(E::SCHEMA, R::definition())?;
581        admit_ordered_fields(E::SCHEMA, operand)?;
582        plan.selected |= operand;
583        Ok((plan, Reducer::distinct(operand)))
584    }
585
586    fn group_counts<K: Value>(
587        self,
588        field: Option<&str>,
589    ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
590        let plan = self.aggregate_plan(Some(K::definition()), true)?;
591        let reducer = self.count_reducer(field)?;
592        self.group_count_values(plan, reducer)
593    }
594
595    fn group_count_values<K: Value>(
596        self,
597        mut plan: Plan<'static>,
598        reducer: Reducer,
599    ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
600        self.select_aggregate_row_path(&mut plan)?;
601        let (groups, page) = self.grouped(&plan, reducer)?;
602        let (value, output_bytes) = count_output(groups, self.request.rows, self.request.bytes)?;
603        Ok(Aggregate {
604            value,
605            examined: page.examined,
606            fetched: page.fetched,
607            output_bytes,
608        })
609    }
610
611    fn count_reducer(&self, field: Option<&str>) -> Result<Reducer, Error> {
612        // Presence needs only the validated tag, not an ordered scalar slot.
613        let presence = field
614            .map(|name| {
615                E::SCHEMA
616                    .fields
617                    .iter()
618                    .enumerate()
619                    .find(|(_, f)| f.name == name)
620                    .map(|(i, f)| f.optional.then_some(i))
621                    .ok_or(Error::InvalidQuery)
622            })
623            .transpose()?
624            .flatten();
625        Ok(Reducer::Count { presence, total: 0 })
626    }
627
628    fn grouped(
629        &self,
630        plan: &Plan<'_>,
631        initial: Reducer,
632    ) -> Result<(Groups, QueryPage<Vec<u8>>), Error> {
633        if self.request.groups.page.is_some() {
634            return Err(Error::InvalidQuery);
635        }
636        let mut groups = self.admit_groups(plan, initial)?;
637        let page = execute(
638            &self.db.map,
639            E::SCHEMA,
640            &self.request,
641            plan,
642            Some(Accumulator::Groups(&mut groups)),
643        )?;
644        Ok((groups, page))
645    }
646
647    fn admit_groups(&self, plan: &Plan<'_>, initial: Reducer) -> Result<Groups, Error> {
648        Ok(Groups {
649            selection: self.request.groups.admit(E::SCHEMA, &initial)?,
650            mask: plan.projection.ok_or(Error::InvalidQuery)?,
651            initial,
652            rows: BTreeMap::new(),
653            state_bytes: 0,
654        })
655    }
656
657    fn aggregate_plan(
658        &self,
659        output: Option<&TypeSchema>,
660        group_output: bool,
661    ) -> Result<Plan<'static>, Error> {
662        if self.request.cursor.is_some()
663            || self.request.distinct
664            || self.request.order.is_some()
665            || self.request.descending
666        {
667            return Err(Error::InvalidQuery);
668        }
669        self.db.schema.admits(E::SCHEMA)?;
670        let mut plan = Plan::admit(
671            E::SCHEMA,
672            &self.request,
673            self.db.schema.fingerprint(),
674            self.db.incarnation,
675            output,
676            super::PlanOutput::Aggregate {
677                grouped: group_output,
678            },
679        )?;
680        if let Some(mask) = plan.projection {
681            admit_ordered_fields(E::SCHEMA, mask)?;
682            plan.selected |= mask;
683        }
684        Ok(plan)
685    }
686}
687
688fn value_output<K: Value, R: Value>(
689    groups: Groups,
690    rows: usize,
691    bytes: usize,
692) -> Result<(Vec<GroupValue<K, R>>, usize), Error> {
693    let mut output_bytes = 0;
694    let value = groups
695        .into_output()?
696        .into_iter()
697        .take(rows)
698        .map(|(key, reducer)| {
699            admit_output(key.len() + reducer.encoded_len(), bytes, &mut output_bytes)?;
700            decode_group_value(&key, reducer)
701        })
702        .collect::<Result<_, Error>>()?;
703    Ok((value, output_bytes))
704}
705
706fn count_output<K: Value>(
707    groups: Groups,
708    rows: usize,
709    bytes: usize,
710) -> Result<(Vec<GroupCount<K>>, usize), Error> {
711    let mut output_bytes = 0;
712    let value = groups
713        .into_output()?
714        .into_iter()
715        .take(rows)
716        .map(|(key, reducer)| {
717            admit_output(key.len() + 8, bytes, &mut output_bytes)?;
718            decode_group_count(&key, reducer)
719        })
720        .collect::<Result<_, Error>>()?;
721    Ok((value, output_bytes))
722}
723
724fn decode_group_count<K: Value>(key: &[u8], result: Completed) -> Result<GroupCount<K>, Error> {
725    Ok(GroupCount {
726        key: decode_record(key)?,
727        count: result.into_count()?,
728    })
729}
730
731fn decode_group_value<K: Value, R: Value>(
732    key: &[u8],
733    result: Completed,
734) -> Result<GroupValue<K, R>, Error> {
735    let value = result.into_value()?;
736    Ok(GroupValue {
737        key: decode_record(key)?,
738        value: value.as_deref().map(decode_record).transpose()?,
739    })
740}
741
742fn decode_record<R: Value>(bytes: &[u8]) -> Result<R, Error> {
743    let mut reader = Decoder::new(bytes)?;
744    let value = R::decode_from(&mut reader)?;
745    reader.finish()?;
746    Ok(value)
747}
748
749// Closed choices over delivered reducers and one grouping table, not user extensions.
750pub(super) enum Accumulator<'a> {
751    // Synchronous existence can complete on the first matching row; no job state.
752    Exists(&'a mut bool),
753    Scalar(&'a mut Reducer),
754    Groups(&'a mut Groups),
755}
756impl Accumulator<'_> {
757    pub(super) fn needs_spans(&self) -> bool {
758        !matches!(
759            self,
760            Self::Exists(_)
761                | Self::Scalar(
762                    Reducer::Numeric(_)
763                        | Reducer::Count { presence: None, .. }
764                        | Reducer::Distinct { .. }
765                )
766        )
767    }
768
769    pub(super) fn push(
770        &mut self,
771        entity: &EntitySchema,
772        values: &[IndexValue<'_>],
773        bytes: &[u8],
774        spans: &[(u16, u16)],
775    ) -> Result<(), Error> {
776        match self {
777            Self::Exists(found) => {
778                **found = true;
779                Ok(())
780            }
781            Self::Scalar(state) => state.push(entity, values, bytes, spans, MAX_STATE_BYTES),
782            Self::Groups(state) => state.push(entity, values, bytes, spans),
783        }
784    }
785}
786
787#[derive(Clone)]
788pub(super) enum Reducer {
789    Numeric(numeric::NumericAggregate),
790    Distinct {
791        mask: u16,
792        seen: BTreeSet<Vec<u8>>,
793    },
794    Count {
795        presence: Option<usize>,
796        total: u64,
797    },
798    Extremum {
799        position: usize,
800        maximum: bool,
801        selected: Option<(Vec<u8>, Vec<u8>)>,
802    },
803}
804impl Reducer {
805    fn distinct(mask: u16) -> Self {
806        Self::Distinct {
807            mask,
808            seen: BTreeSet::new(),
809        }
810    }
811
812    fn extremum(entity: &EntitySchema, mask: u16, maximum: bool) -> Result<Self, Error> {
813        if mask.count_ones() != 1 {
814            return Err(Error::InvalidQuery);
815        }
816        let position = mask.trailing_zeros() as usize;
817        if !key::supports(entity.fields[position].value) {
818            return Err(Error::InvalidQuery);
819        }
820        Ok(Self::Extremum {
821            position,
822            maximum,
823            selected: None,
824        })
825    }
826
827    fn retained_bytes(&self) -> usize {
828        match self {
829            Self::Numeric(state) => state.retained_bytes(),
830            Self::Count { .. } => 8,
831            Self::Distinct { seen, .. } => 8 + seen.iter().map(Vec::capacity).sum::<usize>(),
832            Self::Extremum { selected, .. } => selected
833                .as_ref()
834                .map_or(0, |(key, bytes)| key.capacity() + bytes.capacity()),
835        }
836    }
837
838    fn finish(self) -> Result<Completed, Error> {
839        match self {
840            Self::Count { total, .. } => Ok(Completed::Count(total)),
841            Self::Distinct { seen, .. } => Ok(Completed::Count(seen.len() as u64)),
842            Self::Extremum { selected, .. } => Ok(Completed::Value(selected)),
843            Self::Numeric(state) => state.finish(),
844        }
845    }
846
847    fn push(
848        &mut self,
849        entity: &EntitySchema,
850        values: &[IndexValue<'_>],
851        bytes: &[u8],
852        spans: &[(u16, u16)],
853        allowance: usize,
854    ) -> Result<(), Error> {
855        match self {
856            Self::Numeric(state) => state.push(values)?,
857            Self::Distinct { mask, seen } => {
858                let key = comparison_key(entity, *mask, values)?;
859                if !seen.contains(&key) {
860                    if seen.len() == MAX_DISTINCT_VALUES
861                        || 8 + seen.iter().map(Vec::capacity).sum::<usize>() + key.capacity()
862                            > allowance
863                    {
864                        return Err(Error::Limit);
865                    }
866                    seen.insert(key);
867                }
868            }
869            Self::Count { presence, total } => {
870                *total += u64::from(presence.is_none_or(|i| bytes[usize::from(spans[i].0)] != 0));
871            }
872            Self::Extremum {
873                position,
874                maximum,
875                selected,
876            } => {
877                let value = values[*position];
878                if value == IndexValue::Absent {
879                    return Ok(());
880                }
881                let mut key = Vec::new();
882                value.append_component(entity.fields[*position].optional, &mut key);
883                if key.len() > MAX_COMPARISON_KEY {
884                    return Err(Error::Limit);
885                }
886                if selected
887                    .as_ref()
888                    .is_none_or(|(old, _)| if *maximum { key > *old } else { key < *old })
889                {
890                    let (start, end) = spans[*position];
891                    if key.capacity() + usize::from(end - start) > allowance {
892                        return Err(Error::Limit);
893                    }
894                    // Copy only a winner, after admitting its replacement charge.
895                    let output = bytes[usize::from(start)..usize::from(end)].to_vec();
896                    if key.capacity() + output.capacity() > allowance {
897                        return Err(Error::Limit);
898                    }
899                    *selected = Some((key, output));
900                }
901            }
902        }
903        Ok(())
904    }
905}
906
907// Completed results cannot be advanced. All numeric range checks precede selection.
908enum Completed {
909    Count(u64),
910    Value(Option<(Vec<u8>, Vec<u8>)>),
911}
912impl Completed {
913    fn encoded_len(&self) -> usize {
914        match self {
915            Self::Count(_) => 8,
916            Self::Value(value) => value.as_ref().map_or(0, |(_, bytes)| bytes.len()),
917        }
918    }
919    // Counts need only eight stack bytes; extrema borrow their retained ordered key.
920    fn result_key<'a>(&'a self, scratch: &'a mut [u8; 8]) -> Option<&'a [u8]> {
921        match self {
922            Self::Count(total) => {
923                *scratch = total.to_be_bytes();
924                Some(scratch)
925            }
926            Self::Value(selected) => selected.as_ref().map(|(key, _)| key.as_slice()),
927        }
928    }
929
930    fn retained_bytes(&self) -> usize {
931        match self {
932            Self::Count(_) => 8,
933            Self::Value(value) => value
934                .as_ref()
935                .map_or(0, |(key, bytes)| key.capacity() + bytes.capacity()),
936        }
937    }
938
939    fn into_count(self) -> Result<u64, Error> {
940        match self {
941            Self::Count(count) => Ok(count),
942            _ => Err(Error::Corrupt),
943        }
944    }
945
946    fn into_value(self) -> Result<Option<Vec<u8>>, Error> {
947        match self {
948            Self::Value(value) => Ok(value.map(|(_, bytes)| bytes)),
949            _ => Err(Error::Corrupt),
950        }
951    }
952}
953
954pub(super) struct Groups {
955    selection: Selection,
956    mask: u16,
957    // Never advanced: each new group receives its own empty reducer state.
958    initial: Reducer,
959    rows: BTreeMap<Vec<u8>, (Vec<u8>, Reducer)>,
960    state_bytes: usize,
961}
962impl Groups {
963    fn into_output(self) -> Result<Vec<(Vec<u8>, Completed)>, Error> {
964        // Accumulation has completed. Output filtering cannot relax input/state bounds.
965        let mut state_bytes = self.state_bytes;
966        let mut rows = self
967            .rows
968            .into_iter()
969            .map(|(key, (record, reducer))| {
970                let previous = reducer.retained_bytes();
971                let result = reducer.finish()?;
972                state_bytes = state_bytes - previous + result.retained_bytes();
973                if state_bytes > MAX_STATE_BYTES {
974                    return Err(Error::Limit);
975                }
976                Ok((key, (record, result)))
977            })
978            .collect::<Result<Vec<_>, Error>>()?;
979        rows.retain(|(_, (_, result))| {
980            let mut scratch = [0; 8];
981            let actual = result.result_key(&mut scratch);
982            self.selection
983                .predicates
984                .split_inclusive(|(_, _, or_next)| !or_next)
985                .all(|clause| {
986                    clause.iter().any(|(comparison, operand, _)| {
987                        comparison.accepts(actual, operand.as_deref(), self.selection.optional)
988                    })
989                })
990        });
991        if self.selection.order == GroupOrder::KeyDescending {
992            // BTreeMap supplied ascending canonical keys; reverse the completed,
993            // filtered rows before any output limit or page is selected.
994            rows.reverse();
995        } else if self.selection.order != GroupOrder::Key {
996            rows.sort_unstable_by(|(ka, (_, a)), (kb, (_, b))| {
997                let (mut sa, mut sb) = ([0; 8], [0; 8]);
998                let order = a.result_key(&mut sa).cmp(&b.result_key(&mut sb));
999                let order = if self.selection.order == GroupOrder::AggregateDescending {
1000                    order.reverse()
1001                } else {
1002                    order
1003                };
1004                order.then_with(|| ka.cmp(kb))
1005            });
1006        }
1007        Ok(rows.into_iter().map(|(_, row)| row).collect())
1008    }
1009
1010    fn push(
1011        &mut self,
1012        entity: &EntitySchema,
1013        values: &[IndexValue<'_>],
1014        bytes: &[u8],
1015        spans: &[(u16, u16)],
1016    ) -> Result<(), Error> {
1017        let key = comparison_key(entity, self.mask, values)?;
1018        let size = projection_size(spans, self.mask);
1019        if let Some((_, reducer)) = self.rows.get_mut(&key) {
1020            let previous = reducer.retained_bytes();
1021            reducer.push(
1022                entity,
1023                values,
1024                bytes,
1025                spans,
1026                MAX_STATE_BYTES - self.state_bytes + previous,
1027            )?;
1028            self.state_bytes = self.state_bytes - previous + reducer.retained_bytes();
1029            return Ok(());
1030        }
1031        let base = key.capacity() + size;
1032        let available = MAX_STATE_BYTES - self.state_bytes;
1033        if self.rows.len() == MAX_GROUPS || base + self.initial.retained_bytes() > available {
1034            return Err(Error::Limit);
1035        }
1036        let mut reducer = self.initial.clone();
1037        reducer.push(entity, values, bytes, spans, available - base)?;
1038        let output = copy_projection(bytes, spans, self.mask, size);
1039        // Map/set nodes and fixed bookkeeping are independently bounded by the
1040        // group and per-group distinct cardinality caps.
1041        let retained = key.capacity() + output.capacity() + reducer.retained_bytes();
1042        if retained > available {
1043            return Err(Error::Limit);
1044        }
1045        self.state_bytes += retained;
1046        self.rows.insert(key, (output, reducer));
1047        Ok(())
1048    }
1049}