1pub(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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
21pub enum GroupOrder {
22 #[default]
24 Key,
25 AggregateAscending,
27 AggregateDescending,
29 KeyDescending,
31}
32
33#[derive(Default)]
34pub(super) struct GroupRequest<'a> {
35 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 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 optional: bool,
106}
107
108#[derive(Debug)]
110pub struct Aggregate<T> {
111 pub value: T,
113 pub examined: usize,
115 pub fetched: usize,
117 pub output_bytes: usize,
119}
120
121#[derive(Debug)]
123pub struct GroupCount<K> {
124 pub key: K,
126 pub count: u64,
128}
129
130#[derive(Debug)]
132pub struct GroupValue<K, R> {
133 pub key: K,
135 pub value: Option<R>,
137}
138
139impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
140 #[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 #[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 #[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 #[must_use]
198 pub fn order_groups(mut self, order: GroupOrder) -> Self {
199 self.request.groups.order = Some(order);
200 self
201 }
202
203 pub fn min<R: Value>(self) -> Result<Aggregate<Option<R>>, Error> {
216 self.extremum(false)
217 }
218
219 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 pub fn group_min<K: Value, R: Value>(self) -> Result<Aggregate<Vec<GroupValue<K, R>>>, Error> {
290 self.group_extrema(false)
291 }
292
293 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 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 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 pub fn count_validated(self) -> Result<Aggregate<u64>, Error> {
408 self.scalar_count(None)
409 }
410
411 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 pub fn count_field(self, field: &str) -> Result<Aggregate<u64>, Error> {
461 self.scalar_count(Some(field))
462 }
463
464 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 pub fn group_count<K: Value>(self) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
541 self.group_counts(None)
542 }
543
544 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 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 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
749pub(super) enum Accumulator<'a> {
751 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 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
907enum 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 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 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 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 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 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}