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) = group_output(
328 groups,
329 self.request.rows,
330 self.request.bytes,
331 decode_group_value,
332 )?;
333 Ok(Aggregate {
334 value,
335 examined: page.examined,
336 fetched: page.fetched,
337 output_bytes,
338 })
339 }
340
341 pub fn exists(self) -> Result<Aggregate<bool>, Error> {
354 let mut plan = self.aggregate_plan(None, false)?;
355 self.select_aggregate_row_path(&mut plan)?;
356 let mut found = false;
357 let page = execute(
358 &self.db.map,
359 E::SCHEMA,
360 &self.request,
361 &plan,
362 Some(Accumulator::Exists(&mut found)),
363 )?;
364 Ok(Aggregate {
365 value: found,
366 examined: page.examined,
367 fetched: page.fetched,
368 output_bytes: 1,
369 })
370 }
371
372 pub fn count(self) -> Result<Aggregate<u64>, Error> {
387 if self.request.bytes < 8 {
388 return Err(Error::RowTooLarge);
389 }
390 let mut plan = self.aggregate_plan(None, false)?;
391 if self.request.predicates.is_empty() && self.request.index.is_none() {
392 return Ok(Aggregate {
393 value: self.db.cardinality::<E>()?,
394 examined: 0,
395 fetched: 0,
396 output_bytes: 8,
397 });
398 }
399 if super::range::covers_primary(&plan)
400 || super::order::select_aggregate_prefix(E::SCHEMA, &self.request, &mut plan)?
401 {
402 return self.count_keys(&plan);
403 }
404 let reducer = self.count_reducer(None)?;
405 self.scalar_count_value(&plan, reducer)
406 }
407
408 pub fn count_validated(self) -> Result<Aggregate<u64>, Error> {
413 self.scalar_count(None)
414 }
415
416 pub fn count_index_entries(self) -> Result<Aggregate<u64>, Error> {
428 if self.request.index.is_none() || !self.request.predicates.is_empty() {
429 return Err(Error::InvalidQuery);
430 }
431 if self.request.bytes < 8 {
432 return Err(Error::RowTooLarge);
433 }
434 let plan = self.aggregate_plan(None, false)?;
435 self.count_keys(&plan)
436 }
437
438 fn count_keys(&self, plan: &Plan<'_>) -> Result<Aggregate<u64>, Error> {
439 let bounds = super::range::bounds(E::SCHEMA, &self.request, plan)?;
440 let mut examined = 0;
441 if let Some(range) = bounds {
442 let terminal = super::range::terminal_key(&range, false);
443 let entries = self.db.map.range((range.0.as_ref(), range.1.as_ref()));
444 for entry in entries.take(self.request.work) {
445 examined += 1;
446 if examined == self.request.work && terminal.is_none_or(|end| end != entry.key()) {
447 return Err(Error::Limit);
448 }
449 }
450 }
451 Ok(Aggregate {
452 value: examined as u64,
453 examined,
454 fetched: 0,
455 output_bytes: 8,
456 })
457 }
458
459 pub fn count_field(self, field: &str) -> Result<Aggregate<u64>, Error> {
467 self.scalar_count(Some(field))
468 }
469
470 pub fn count_distinct<K: Value>(self) -> Result<Aggregate<u64>, Error> {
479 if self.request.bytes < 8 {
480 return Err(Error::RowTooLarge);
481 }
482 let (mut plan, reducer) = self.distinct_plan::<K>()?;
483 self.select_aggregate_row_path(&mut plan)?;
484 self.scalar_count_value(&plan, reducer)
485 }
486
487 fn distinct_plan<K: Value>(&self) -> Result<(Plan<'static>, Reducer), Error> {
488 let plan = self.aggregate_plan(Some(K::definition()), false)?;
489 let reducer = Reducer::distinct(plan.projection.ok_or(Error::InvalidQuery)?);
490 Ok((plan, reducer))
491 }
492
493 fn select_aggregate_row_path(&self, plan: &mut Plan<'static>) -> Result<(), Error> {
494 if plan.index.is_none() && !super::range::covers_primary(plan) {
495 super::order::select_aggregate_prefix(E::SCHEMA, &self.request, plan)?;
496 }
497 Ok(())
498 }
499
500 fn scalar_count(self, field: Option<&str>) -> Result<Aggregate<u64>, Error> {
501 if self.request.bytes < 8 {
502 return Err(Error::RowTooLarge);
503 }
504 let mut plan = self.aggregate_plan(None, false)?;
505 self.select_aggregate_row_path(&mut plan)?;
506 let reducer = self.count_reducer(field)?;
507 self.scalar_count_value(&plan, reducer)
508 }
509
510 fn scalar_count_value(
511 self,
512 plan: &Plan<'_>,
513 mut reducer: Reducer,
514 ) -> Result<Aggregate<u64>, Error> {
515 let page = execute(
516 &self.db.map,
517 E::SCHEMA,
518 &self.request,
519 plan,
520 Some(Accumulator::Scalar(&mut reducer)),
521 )?;
522 Ok(Aggregate {
523 value: reducer.finish()?.into_count()?,
524 examined: page.examined,
525 fetched: page.fetched,
526 output_bytes: 8,
527 })
528 }
529
530 pub fn group_count<K: Value>(self) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
547 self.group_counts(None)
548 }
549
550 pub fn group_count_field<K: Value>(
559 self,
560 field: &str,
561 ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
562 self.group_counts(Some(field))
563 }
564
565 pub fn group_count_distinct<K: Value, R: Value>(
578 self,
579 ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
580 let (plan, reducer) = self.group_distinct_plan::<K, R>()?;
581 self.group_count_values(plan, reducer)
582 }
583
584 fn group_distinct_plan<K: Value, R: Value>(&self) -> Result<(Plan<'static>, Reducer), Error> {
585 let mut plan = self.aggregate_plan(Some(K::definition()), true)?;
586 let operand = admit_projection(E::SCHEMA, R::definition())?;
587 admit_ordered_fields(E::SCHEMA, operand)?;
588 plan.selected |= operand;
589 Ok((plan, Reducer::distinct(operand)))
590 }
591
592 fn group_counts<K: Value>(
593 self,
594 field: Option<&str>,
595 ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
596 let plan = self.aggregate_plan(Some(K::definition()), true)?;
597 let reducer = self.count_reducer(field)?;
598 self.group_count_values(plan, reducer)
599 }
600
601 fn group_count_values<K: Value>(
602 self,
603 mut plan: Plan<'static>,
604 reducer: Reducer,
605 ) -> Result<Aggregate<Vec<GroupCount<K>>>, Error> {
606 self.select_aggregate_row_path(&mut plan)?;
607 let (groups, page) = self.grouped(&plan, reducer)?;
608 let (value, output_bytes) = group_output(
609 groups,
610 self.request.rows,
611 self.request.bytes,
612 decode_group_count,
613 )?;
614 Ok(Aggregate {
615 value,
616 examined: page.examined,
617 fetched: page.fetched,
618 output_bytes,
619 })
620 }
621
622 fn count_reducer(&self, field: Option<&str>) -> Result<Reducer, Error> {
623 let presence = field
625 .map(|name| E::SCHEMA.field_position(name).ok_or(Error::InvalidQuery))
626 .transpose()?
627 .filter(|&i| E::SCHEMA.fields[i].optional);
628 Ok(Reducer::Count { presence, total: 0 })
629 }
630
631 fn grouped(
632 &self,
633 plan: &Plan<'_>,
634 initial: Reducer,
635 ) -> Result<(Groups, QueryPage<Vec<u8>>), Error> {
636 if self.request.groups.page.is_some() {
637 return Err(Error::InvalidQuery);
638 }
639 let mut groups = self.admit_groups(plan, initial)?;
640 let page = execute(
641 &self.db.map,
642 E::SCHEMA,
643 &self.request,
644 plan,
645 Some(Accumulator::Groups(&mut groups)),
646 )?;
647 Ok((groups, page))
648 }
649
650 fn admit_groups(&self, plan: &Plan<'_>, initial: Reducer) -> Result<Groups, Error> {
651 Ok(Groups {
652 selection: self.request.groups.admit(E::SCHEMA, &initial)?,
653 mask: plan.projection.ok_or(Error::InvalidQuery)?,
654 initial,
655 rows: BTreeMap::new(),
656 state_bytes: 0,
657 })
658 }
659
660 fn aggregate_plan(
661 &self,
662 output: Option<&TypeSchema>,
663 group_output: bool,
664 ) -> Result<Plan<'static>, Error> {
665 if self.request.cursor.is_some()
666 || self.request.distinct
667 || self.request.order.is_some()
668 || self.request.descending
669 {
670 return Err(Error::InvalidQuery);
671 }
672 self.db.schema.admits(E::SCHEMA)?;
673 let mut plan = Plan::admit(
674 E::SCHEMA,
675 &self.request,
676 self.db.schema.fingerprint(),
677 self.db.incarnation,
678 output,
679 super::PlanOutput::Aggregate {
680 grouped: group_output,
681 },
682 )?;
683 if let Some(mask) = plan.projection {
684 admit_ordered_fields(E::SCHEMA, mask)?;
685 plan.selected |= mask;
686 }
687 Ok(plan)
688 }
689}
690
691fn group_output<T>(
692 groups: Groups,
693 rows: usize,
694 bytes: usize,
695 decode: fn(&[u8], Completed) -> Result<T, Error>,
696) -> Result<(Vec<T>, usize), Error> {
697 let mut output_bytes = 0;
698 let value = groups
699 .into_output()?
700 .into_iter()
701 .take(rows)
702 .map(|(key, result)| {
703 admit_output(key.len() + result.encoded_len(), bytes, &mut output_bytes)?;
704 decode(&key, result)
705 })
706 .collect::<Result<_, Error>>()?;
707 Ok((value, output_bytes))
708}
709
710fn decode_group_count<K: Value>(key: &[u8], result: Completed) -> Result<GroupCount<K>, Error> {
711 Ok(GroupCount {
712 key: decode_record(key)?,
713 count: result.into_count()?,
714 })
715}
716
717fn decode_group_value<K: Value, R: Value>(
718 key: &[u8],
719 result: Completed,
720) -> Result<GroupValue<K, R>, Error> {
721 let value = result.into_value()?;
722 Ok(GroupValue {
723 key: decode_record(key)?,
724 value: value.as_deref().map(decode_record).transpose()?,
725 })
726}
727
728fn decode_record<R: Value>(bytes: &[u8]) -> Result<R, Error> {
729 let mut reader = Decoder::new(bytes)?;
730 let value = R::decode_from(&mut reader)?;
731 reader.finish()?;
732 Ok(value)
733}
734
735pub(super) enum Accumulator<'a> {
737 Exists(&'a mut bool),
739 Scalar(&'a mut Reducer),
740 Groups(&'a mut Groups),
741}
742impl Accumulator<'_> {
743 pub(super) fn needs_spans(&self) -> bool {
744 !matches!(
745 self,
746 Self::Exists(_)
747 | Self::Scalar(
748 Reducer::Numeric(_)
749 | Reducer::Count { presence: None, .. }
750 | Reducer::Distinct { .. }
751 )
752 )
753 }
754
755 pub(super) fn push(
756 &mut self,
757 entity: &EntitySchema,
758 values: &[IndexValue<'_>],
759 bytes: &[u8],
760 spans: &[(u16, u16)],
761 ) -> Result<(), Error> {
762 match self {
763 Self::Exists(found) => {
764 **found = true;
765 Ok(())
766 }
767 Self::Scalar(state) => state.push(entity, values, bytes, spans, MAX_STATE_BYTES),
768 Self::Groups(state) => state.push(entity, values, bytes, spans),
769 }
770 }
771}
772
773#[derive(Clone)]
774pub(super) enum Reducer {
775 Numeric(numeric::NumericAggregate),
776 Distinct {
777 mask: u16,
778 seen: BTreeSet<Vec<u8>>,
779 },
780 Count {
781 presence: Option<usize>,
782 total: u64,
783 },
784 Extremum {
785 position: usize,
786 maximum: bool,
787 selected: Option<(Vec<u8>, Vec<u8>)>,
788 },
789}
790impl Reducer {
791 fn distinct(mask: u16) -> Self {
792 Self::Distinct {
793 mask,
794 seen: BTreeSet::new(),
795 }
796 }
797
798 fn extremum(entity: &EntitySchema, mask: u16, maximum: bool) -> Result<Self, Error> {
799 if mask.count_ones() != 1 {
800 return Err(Error::InvalidQuery);
801 }
802 let position = mask.trailing_zeros() as usize;
803 if !key::supports(entity.fields[position].value) {
804 return Err(Error::InvalidQuery);
805 }
806 Ok(Self::Extremum {
807 position,
808 maximum,
809 selected: None,
810 })
811 }
812
813 fn retained_bytes(&self) -> usize {
814 match self {
815 Self::Numeric(state) => state.retained_bytes(),
816 Self::Count { .. } => 8,
817 Self::Distinct { seen, .. } => 8 + seen.iter().map(Vec::capacity).sum::<usize>(),
818 Self::Extremum { selected, .. } => selected
819 .as_ref()
820 .map_or(0, |(key, bytes)| key.capacity() + bytes.capacity()),
821 }
822 }
823
824 fn finish(self) -> Result<Completed, Error> {
825 match self {
826 Self::Count { total, .. } => Ok(Completed::Count(total)),
827 Self::Distinct { seen, .. } => Ok(Completed::Count(seen.len() as u64)),
828 Self::Extremum { selected, .. } => Ok(Completed::Value(selected)),
829 Self::Numeric(state) => state.finish(),
830 }
831 }
832
833 fn push(
834 &mut self,
835 entity: &EntitySchema,
836 values: &[IndexValue<'_>],
837 bytes: &[u8],
838 spans: &[(u16, u16)],
839 allowance: usize,
840 ) -> Result<(), Error> {
841 match self {
842 Self::Numeric(state) => state.push(values)?,
843 Self::Distinct { mask, seen } => {
844 let key = comparison_key(entity, *mask, values)?;
845 if !seen.contains(&key) {
846 if seen.len() == MAX_DISTINCT_VALUES
847 || 8 + seen.iter().map(Vec::capacity).sum::<usize>() + key.capacity()
848 > allowance
849 {
850 return Err(Error::Limit);
851 }
852 seen.insert(key);
853 }
854 }
855 Self::Count { presence, total } => {
856 *total += u64::from(presence.is_none_or(|i| bytes[usize::from(spans[i].0)] != 0));
857 }
858 Self::Extremum {
859 position,
860 maximum,
861 selected,
862 } => {
863 let value = values[*position];
864 if value == IndexValue::Absent {
865 return Ok(());
866 }
867 let mut key = Vec::new();
868 value.append_component(entity.fields[*position].optional, &mut key);
869 if key.len() > MAX_COMPARISON_KEY {
870 return Err(Error::Limit);
871 }
872 if selected
873 .as_ref()
874 .is_none_or(|(old, _)| if *maximum { key > *old } else { key < *old })
875 {
876 let (start, end) = spans[*position];
877 if key.capacity() + usize::from(end - start) > allowance {
878 return Err(Error::Limit);
879 }
880 let output = bytes[usize::from(start)..usize::from(end)].to_vec();
882 if key.capacity() + output.capacity() > allowance {
883 return Err(Error::Limit);
884 }
885 *selected = Some((key, output));
886 }
887 }
888 }
889 Ok(())
890 }
891}
892
893enum Completed {
895 Count(u64),
896 Value(Option<(Vec<u8>, Vec<u8>)>),
897}
898impl Completed {
899 fn encoded_len(&self) -> usize {
900 match self {
901 Self::Count(_) => 8,
902 Self::Value(value) => value.as_ref().map_or(0, |(_, bytes)| bytes.len()),
903 }
904 }
905 fn result_key<'a>(&'a self, scratch: &'a mut [u8; 8]) -> Option<&'a [u8]> {
907 match self {
908 Self::Count(total) => {
909 *scratch = total.to_be_bytes();
910 Some(scratch)
911 }
912 Self::Value(selected) => selected.as_ref().map(|(key, _)| key.as_slice()),
913 }
914 }
915
916 fn retained_bytes(&self) -> usize {
917 match self {
918 Self::Count(_) => 8,
919 Self::Value(value) => value
920 .as_ref()
921 .map_or(0, |(key, bytes)| key.capacity() + bytes.capacity()),
922 }
923 }
924
925 fn into_count(self) -> Result<u64, Error> {
926 match self {
927 Self::Count(count) => Ok(count),
928 _ => Err(Error::Corrupt),
929 }
930 }
931
932 fn into_value(self) -> Result<Option<Vec<u8>>, Error> {
933 match self {
934 Self::Value(value) => Ok(value.map(|(_, bytes)| bytes)),
935 _ => Err(Error::Corrupt),
936 }
937 }
938}
939
940pub(super) struct Groups {
941 selection: Selection,
942 mask: u16,
943 initial: Reducer,
945 rows: BTreeMap<Vec<u8>, (Vec<u8>, Reducer)>,
946 state_bytes: usize,
947}
948impl Groups {
949 fn into_output(self) -> Result<Vec<(Vec<u8>, Completed)>, Error> {
950 let mut state_bytes = self.state_bytes;
952 let mut rows = self
953 .rows
954 .into_iter()
955 .map(|(key, (record, reducer))| {
956 let previous = reducer.retained_bytes();
957 let result = reducer.finish()?;
958 state_bytes = state_bytes - previous + result.retained_bytes();
959 if state_bytes > MAX_STATE_BYTES {
960 return Err(Error::Limit);
961 }
962 Ok((key, (record, result)))
963 })
964 .collect::<Result<Vec<_>, Error>>()?;
965 rows.retain(|(_, (_, result))| {
966 let mut scratch = [0; 8];
967 let actual = result.result_key(&mut scratch);
968 self.selection
969 .predicates
970 .split_inclusive(|(_, _, or_next)| !or_next)
971 .all(|clause| {
972 clause.iter().any(|(comparison, operand, _)| {
973 comparison.accepts(actual, operand.as_deref(), self.selection.optional)
974 })
975 })
976 });
977 if self.selection.order == GroupOrder::KeyDescending {
978 rows.reverse();
981 } else if self.selection.order != GroupOrder::Key {
982 rows.sort_unstable_by(|(ka, (_, a)), (kb, (_, b))| {
983 let (mut sa, mut sb) = ([0; 8], [0; 8]);
984 let order = a.result_key(&mut sa).cmp(&b.result_key(&mut sb));
985 let order = if self.selection.order == GroupOrder::AggregateDescending {
986 order.reverse()
987 } else {
988 order
989 };
990 order.then_with(|| ka.cmp(kb))
991 });
992 }
993 Ok(rows.into_iter().map(|(_, row)| row).collect())
994 }
995
996 fn push(
997 &mut self,
998 entity: &EntitySchema,
999 values: &[IndexValue<'_>],
1000 bytes: &[u8],
1001 spans: &[(u16, u16)],
1002 ) -> Result<(), Error> {
1003 let key = comparison_key(entity, self.mask, values)?;
1004 let size = projection_size(spans, self.mask);
1005 if let Some((_, reducer)) = self.rows.get_mut(&key) {
1006 let previous = reducer.retained_bytes();
1007 reducer.push(
1008 entity,
1009 values,
1010 bytes,
1011 spans,
1012 MAX_STATE_BYTES - self.state_bytes + previous,
1013 )?;
1014 self.state_bytes = self.state_bytes - previous + reducer.retained_bytes();
1015 return Ok(());
1016 }
1017 let base = key.capacity() + size;
1018 let available = MAX_STATE_BYTES - self.state_bytes;
1019 if self.rows.len() == MAX_GROUPS || base + self.initial.retained_bytes() > available {
1020 return Err(Error::Limit);
1021 }
1022 let mut reducer = self.initial.clone();
1023 reducer.push(entity, values, bytes, spans, available - base)?;
1024 let output = copy_projection(bytes, spans, self.mask, size);
1025 let retained = key.capacity() + output.capacity() + reducer.retained_bytes();
1028 if retained > available {
1029 return Err(Error::Limit);
1030 }
1031 self.state_bytes += retained;
1032 self.rows.insert(key, (output, reducer));
1033 Ok(())
1034 }
1035}