1mod aggregate;
3mod distinct;
4mod order;
5mod range;
6mod sort;
7pub use aggregate::jobs::{AggregateJobs, GroupCursor, GroupPage, JobHandle, JobOutcome, JobStep};
8pub use aggregate::{Aggregate, GroupCount, GroupOrder, GroupValue};
9
10use super::{Database, Map, prefix, row_key, validate_index_entry};
11use crate::{
12 Entity, EntitySchema, Error, FieldType, IndexSchema, IndexValue, TypeBody, TypeSchema, Value,
13 codec::Decoder, key, primary::RowKey, types::TypeGraph,
14};
15use ic_storage::Memory;
16use sha2::{Digest, Sha256};
17use std::marker::PhantomData;
18
19const MAX_TERMS: usize = 8;
20const MAX_WORK: usize = 512;
21const MAX_OUTPUT: usize = 128 * 1024;
22const MAX_COMPARISON_KEY: usize = 4096;
23const MAX_DISTINCT_VALUES: usize = 32;
24const MAX_STATE_BYTES: usize = 128 * 1024;
25
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
28pub enum SortDirection {
29 Ascending,
31 Descending,
33}
34
35#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37#[repr(u8)]
38pub enum Comparison {
39 Eq = 0,
41 Ne = 1,
43 Lt = 2,
45 Le = 3,
47 Gt = 4,
49 Ge = 5,
51 StartsWith = 6,
55 EndsWith = 7,
58 Contains = 8,
61}
62
63impl Comparison {
64 fn is_relational(self) -> bool {
65 matches!(
66 self,
67 Self::Eq | Self::Ne | Self::Lt | Self::Le | Self::Gt | Self::Ge
68 )
69 }
70
71 fn admit(self, field: FieldType, optional: bool, value: IndexValue<'_>) -> Result<(), Error> {
72 value.admit(field, optional)?;
73 let field = key::operand_type(field);
74 if matches!(self, Self::StartsWith | Self::EndsWith | Self::Contains)
75 && !matches!(field, FieldType::Text { .. } | FieldType::Blob { .. })
76 {
77 return Err(Error::InvalidQuery);
78 }
79 if value == IndexValue::Absent && !matches!(self, Self::Eq | Self::Ne) {
80 return Err(Error::InvalidOperand);
81 }
82 Ok(())
83 }
84
85 fn accepts(self, actual: Option<&[u8]>, operand: Option<&[u8]>, optional: bool) -> bool {
86 if actual.is_none() {
87 return self.accepts_absent(operand.is_none());
88 }
89 match self {
90 Self::Eq => actual == operand,
91 Self::Ne => actual != operand,
92 Self::StartsWith | Self::EndsWith | Self::Contains => {
93 fn content(key: &[u8], optional: bool) -> Option<&[u8]> {
96 key.get(usize::from(optional)..)?.strip_suffix(&[0, 0])
97 }
98 actual
99 .and_then(|key| content(key, optional))
100 .zip(operand.and_then(|key| content(key, optional)))
101 .is_some_and(|(actual, operand)| match self {
102 Self::StartsWith => actual.starts_with(operand),
105 Self::EndsWith => actual
109 .strip_suffix(operand)
110 .is_some_and(|prefix| prefix.last() != Some(&0)),
111 _ => contains_component(actual, operand),
112 })
113 }
114 _ if actual.is_none() || operand.is_none() => false,
115 Self::Lt => actual < operand,
116 Self::Le => actual <= operand,
117 Self::Gt => actual > operand,
118 Self::Ge => actual >= operand,
119 }
120 }
121
122 fn accepts_absent(self, other_absent: bool) -> bool {
125 match self {
126 Self::Eq => other_absent,
127 Self::Ne => !other_absent,
128 _ => false,
129 }
130 }
131}
132
133fn contains_component(actual: &[u8], needle: &[u8]) -> bool {
135 let Some(start) = memchr::memmem::find(actual, needle) else {
136 return false;
137 };
138 if start == 0 || actual[start - 1] != 0 {
139 return true;
140 }
141 fn raw(content: &[u8]) -> Vec<u8> {
145 let mut bytes = Vec::with_capacity(content.len().min(crate::codec::MAX_ROW_BYTES));
146 let mut encoded = content.iter();
147 while let Some(&byte) = encoded.next() {
148 bytes.push(byte);
149 if byte == 0 {
150 encoded.next();
151 }
152 }
153 bytes
154 }
155 memchr::memmem::find(&raw(actual), &raw(needle)).is_some()
156}
157
158#[derive(Clone, Debug, PartialEq, Eq)]
162pub struct QueryCursor {
163 binding: [u8; 32],
164 position: Vec<u8>,
165 inclusive: bool,
166}
167impl QueryCursor {
168 pub(super) const MAX_ENCODED_BYTES: usize = 34 + crate::MAX_INDEX_KEY_BYTES;
169
170 #[must_use]
172 pub fn to_bytes(&self) -> Vec<u8> {
173 let mut bytes = vec![1, u8::from(self.inclusive)];
174 bytes.extend(self.binding);
175 bytes.extend(&self.position);
176 bytes
177 }
178 pub fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
182 if !(35..=Self::MAX_ENCODED_BYTES).contains(&bytes.len()) || bytes[0] != 1 || bytes[1] > 1 {
183 return Err(Error::InvalidCursor);
184 }
185 Ok(Self {
186 binding: bytes[2..34].try_into().map_err(|_| Error::InvalidCursor)?,
187 position: bytes[34..].to_vec(),
188 inclusive: bytes[1] == 1,
189 })
190 }
191}
192
193#[derive(Debug)]
196pub struct QueryPage<T> {
197 pub rows: Vec<T>,
199 pub next: Option<QueryCursor>,
201 pub examined: usize,
203 pub fetched: usize,
205 pub output_bytes: usize,
207}
208
209impl QueryPage<Vec<u8>> {
210 #[inline(never)]
211 pub(super) fn decode_entities<E: Entity>(self) -> Result<QueryPage<E>, Error> {
212 Ok(QueryPage {
213 rows: self
214 .rows
215 .iter()
216 .map(|bytes| E::decode(bytes))
217 .collect::<Result<_, _>>()?,
218 next: self.next,
219 examined: self.examined,
220 fetched: self.fetched,
221 output_bytes: self.output_bytes,
222 })
223 }
224
225 #[inline(never)]
226 fn decode_projection<R: Value>(self) -> Result<QueryPage<R>, Error> {
227 Ok(QueryPage {
228 rows: self
229 .rows
230 .iter()
231 .map(|bytes| {
232 let mut reader = Decoder::new(bytes)?;
233 let row = R::decode_from(&mut reader)?;
235 reader.finish()?;
236 Ok(row)
237 })
238 .collect::<Result<_, Error>>()?,
239 next: self.next,
240 examined: self.examined,
241 fetched: self.fetched,
242 output_bytes: self.output_bytes,
243 })
244 }
245}
246
247#[derive(Clone, Copy, Debug, PartialEq, Eq)]
249pub enum QueryOperand<'a> {
250 Literal(IndexValue<'a>),
252 Length(u32),
254 Field(&'a str),
256}
257
258struct Predicate<'a> {
259 field: &'a str,
260 comparison: Comparison,
261 operand: QueryOperand<'a>,
262 or_next: bool,
264}
265struct Request<'a> {
266 groups: aggregate::GroupRequest<'a>,
267 predicates: Vec<Predicate<'a>>,
268 index: Option<(&'a str, Vec<IndexValue<'a>>)>,
269 order: Option<Vec<&'a str>>,
270 order_descending: u8,
271 descending: bool,
272 distinct: bool,
273 rows: usize,
274 work: usize,
275 bytes: usize,
276 cursor: Option<&'a QueryCursor>,
277 over_limit: bool,
278}
279
280impl Default for Request<'_> {
281 fn default() -> Self {
282 Self {
283 groups: aggregate::GroupRequest::default(),
284 predicates: Vec::new(),
285 index: None,
286 order: None,
287 order_descending: 0,
288 descending: false,
289 distinct: false,
290 rows: 32,
291 work: 128,
292 bytes: MAX_OUTPUT,
293 cursor: None,
294 over_limit: false,
295 }
296 }
297}
298
299impl<'a> Request<'a> {
302 #[inline(never)]
303 fn filter(&mut self, field: &'a str, comparison: Comparison, operand: QueryOperand<'a>) {
304 if self.predicates.len() == MAX_TERMS {
305 self.over_limit = true;
306 } else {
307 self.predicates.push(Predicate {
308 field,
309 comparison,
310 operand,
311 or_next: false,
312 });
313 }
314 }
315
316 #[inline(never)]
317 fn or_clause(
318 &mut self,
319 alternatives: impl ExactSizeIterator<Item = (&'a str, Comparison, QueryOperand<'a>)>,
320 ) {
321 let count = alternatives.len();
322 if count == 0 || count > MAX_TERMS - self.predicates.len() {
323 self.over_limit = true;
324 } else {
325 self.predicates.extend(alternatives.enumerate().map(
326 |(i, (field, comparison, operand))| Predicate {
327 field,
328 comparison,
329 operand,
330 or_next: i + 1 < count,
331 },
332 ));
333 }
334 }
335
336 #[inline(never)]
337 fn filter_not_in(&mut self, field: &'a str, values: &[IndexValue<'a>]) {
338 if values.is_empty() || values.len() > MAX_TERMS - self.predicates.len() {
339 self.over_limit = true;
340 return;
341 }
342 for &value in values {
343 self.filter(field, Comparison::Ne, QueryOperand::Literal(value));
344 }
345 }
346
347 #[inline(never)]
348 fn using_index(&mut self, name: &'a str, values: &[IndexValue<'a>]) {
349 if values.len() > 4 {
350 self.over_limit = true;
351 } else {
352 self.index = Some((name, values.to_vec()));
353 }
354 }
355
356 #[inline(never)]
357 fn order_by(&mut self, fields: &[&'a str]) {
358 self.order_descending = 0;
359 if fields.len() > 4 {
360 self.over_limit = true;
361 } else {
362 self.order = Some(fields.to_vec());
363 }
364 }
365
366 #[inline(never)]
367 fn order_by_each(&mut self, fields: &[(&'a str, SortDirection)]) {
368 if fields.len() > 4 {
369 self.over_limit = true;
370 return;
371 }
372 self.order = Some(fields.iter().map(|(name, _)| *name).collect());
373 self.order_descending = fields
374 .iter()
375 .enumerate()
376 .fold(0, |mask, (i, (_, direction))| {
377 mask | (u8::from(*direction == SortDirection::Descending) << i)
378 });
379 }
380
381 fn primary_descending(&self, entity: &EntitySchema) -> bool {
382 self.order_descending != 0
383 && self.order.as_ref().is_some_and(|fields| {
384 fields.last() == Some(&entity.primary_key)
385 && self.order_descending & (1 << (fields.len() - 1)) != 0
386 })
387 }
388}
389
390pub(super) fn source_page<M: Memory>(
392 map: &Map<M>,
393 entity: &EntitySchema,
394 binding: [u8; 32],
395 incarnation: [u8; 16],
396 cursor: Option<&QueryCursor>,
397 rows: usize,
398 bytes: usize,
399) -> Result<QueryPage<Vec<u8>>, Error> {
400 let request = Request {
401 rows,
402 work: rows,
403 bytes,
404 cursor,
405 ..Request::default()
406 };
407 let plan = Plan::admit(entity, &request, binding, incarnation, None, false)?;
408 execute(map, entity, &request, &plan, None)
409}
410
411pub struct Query<'a, E, M: Memory = ic_storage::DefaultMemoryImpl> {
415 db: &'a Database<M>,
416 request: Request<'a>,
417 entity: PhantomData<E>,
418}
419impl<M: Memory> Database<M> {
420 #[must_use]
422 pub fn query<E: Entity>(&self) -> Query<'_, E, M> {
423 Query {
424 db: self,
425 entity: PhantomData,
426 request: Request::default(),
427 }
428 }
429}
430impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
431 #[must_use]
442 pub fn distinct(mut self) -> Self {
443 self.request.distinct = true;
444 self
445 }
446 #[must_use]
456 pub fn filter(
457 mut self,
458 field: &'a str,
459 comparison: Comparison,
460 value: impl Into<IndexValue<'a>>,
461 ) -> Self {
462 self.request
463 .filter(field, comparison, QueryOperand::Literal(value.into()));
464 self
465 }
466 #[must_use]
470 pub fn filter_fields(mut self, left: &'a str, comparison: Comparison, right: &'a str) -> Self {
471 self.request
472 .filter(left, comparison, QueryOperand::Field(right));
473 self
474 }
475 #[must_use]
479 pub fn filter_length(mut self, field: &'a str, comparison: Comparison, length: u32) -> Self {
480 self.request
481 .filter(field, comparison, QueryOperand::Length(length));
482 self
483 }
484 #[must_use]
487 pub fn filter_present(self, field: &'a str) -> Self {
488 self.filter(field, Comparison::Ne, IndexValue::Absent)
489 }
490 #[must_use]
493 pub fn filter_absent(self, field: &'a str) -> Self {
494 self.filter(field, Comparison::Eq, IndexValue::Absent)
495 }
496 #[must_use]
503 pub fn filter_between(
504 self,
505 field: &'a str,
506 lower: impl Into<IndexValue<'a>>,
507 upper: impl Into<IndexValue<'a>>,
508 ) -> Self {
509 self.filter(field, Comparison::Ge, lower)
510 .filter(field, Comparison::Le, upper)
511 }
512 #[must_use]
520 pub fn filter_not_between(
521 self,
522 field: &'a str,
523 lower: impl Into<IndexValue<'a>>,
524 upper: impl Into<IndexValue<'a>>,
525 ) -> Self {
526 self.filter_any(&[
527 (field, Comparison::Lt, lower.into()),
528 (field, Comparison::Gt, upper.into()),
529 ])
530 }
531 #[must_use]
538 pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
539 self.request.or_clause(
540 alternatives
541 .iter()
542 .map(|&(field, op, value)| (field, op, QueryOperand::Literal(value))),
543 );
544 self
545 }
546 #[must_use]
551 pub fn filter_any_operands(
552 mut self,
553 alternatives: &[(&'a str, Comparison, QueryOperand<'a>)],
554 ) -> Self {
555 self.request.or_clause(alternatives.iter().copied());
556 self
557 }
558
559 #[must_use]
567 pub fn filter_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
568 self.request.or_clause(
569 values
570 .iter()
571 .copied()
572 .map(|value| (field, Comparison::Eq, QueryOperand::Literal(value))),
573 );
574 self
575 }
576
577 #[must_use]
585 pub fn filter_not_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
586 self.request.filter_not_in(field, values);
587 self
588 }
589 #[must_use]
594 pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
595 self.request.using_index(name, values);
596 self
597 }
598 #[must_use]
608 pub fn order_by(mut self, fields: &[&'a str]) -> Self {
609 self.request.order_by(fields);
610 self
611 }
612 #[must_use]
617 pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
618 self.request.order_by_each(fields);
619 self
620 }
621 #[must_use]
623 pub fn descending(mut self) -> Self {
624 self.request.descending = true;
625 self
626 }
627 #[must_use]
634 pub fn limit(mut self, rows: usize) -> Self {
635 self.request.rows = rows;
636 self
637 }
638 #[must_use]
640 pub fn work_limit(mut self, candidates: usize) -> Self {
641 self.request.work = candidates;
642 self
643 }
644 #[must_use]
646 pub fn byte_limit(mut self, bytes: usize) -> Self {
647 self.request.bytes = bytes;
648 self
649 }
650 #[must_use]
652 pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
653 self.request.cursor = Some(cursor);
654 self
655 }
656 pub fn fetch(self) -> Result<QueryPage<E>, Error> {
663 fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
664 }
665 pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
675 let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
676 raw.decode_projection()
677 }
678}
679
680fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
684 let TypeBody::Record(fields) = &output.body else {
685 return Err(Error::InvalidQuery);
686 };
687 if fields.is_empty()
688 || fields.len() > crate::schema::MAX_FIELDS
689 || fields.windows(2).any(|w| w[0].name >= w[1].name)
690 {
691 return Err(Error::InvalidQuery);
692 }
693 let mut source = TypeGraph::default();
694 let mut target = TypeGraph::default();
695 let mut mask = 0;
696 for field in *fields {
697 let position = entity
698 .fields
699 .iter()
700 .position(|f| f.name == field.name)
701 .ok_or(Error::InvalidQuery)?;
702 let stored = &entity.fields[position];
703 if stored.value != field.value || stored.optional != field.optional {
704 return Err(Error::InvalidQuery);
705 }
706 source
707 .include(stored.value)
708 .map_err(|_| Error::InvalidQuery)?;
709 target
710 .include(field.value)
711 .map_err(|_| Error::InvalidQuery)?;
712 mask |= 1 << position;
713 }
714 if !source.contains(&target) {
715 return Err(Error::InvalidQuery);
716 }
717 Ok(mask)
718}
719
720struct Term {
721 position: usize,
722 comparison: Comparison,
723 operand: TermOperand,
724 or_next: bool,
725}
726
727enum TermOperand {
728 Literal { bytes: Vec<u8>, absent: bool },
729 Field(usize),
730 Length(u32),
731}
732
733fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
734 for (i, field) in entity.fields.iter().enumerate() {
735 if mask & (1 << i) != 0 && !key::supports(field.value) {
736 return Err(Error::InvalidQuery);
737 }
738 }
739 Ok(())
740}
741
742fn comparison_key(
744 entity: &EntitySchema,
745 mask: u16,
746 values: &[IndexValue<'_>],
747) -> Result<Vec<u8>, Error> {
748 let mut key = Vec::new();
749 for (i, field) in entity.fields.iter().enumerate() {
750 if mask & (1 << i) != 0 {
751 values[i].append_component(field.optional, &mut key);
752 if key.len() > MAX_COMPARISON_KEY {
753 return Err(Error::Limit);
754 }
755 }
756 }
757 Ok(key)
758}
759
760fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
761 if size > limit {
762 return Err(Error::RowTooLarge);
763 }
764 if size > limit - *used {
765 return Err(Error::Limit);
766 }
767 *used += size;
768 Ok(())
769}
770
771fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
773 spans
774 .iter()
775 .enumerate()
776 .filter(|(i, _)| mask & (1 << i) != 0)
777 .map(|(_, (start, end))| usize::from(end - start))
778 .sum()
779}
780
781fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
782 let mut output = Vec::with_capacity(size);
783 for (i, &(start, end)) in spans.iter().enumerate() {
784 if mask & (1 << i) != 0 {
785 output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
786 }
787 }
788 output
789}
790struct Plan<'a> {
791 index: Option<&'a IndexSchema>,
792 prefix: Vec<u8>,
793 fixed_components: usize,
794 terms: Vec<Term>,
795 selected: u16,
796 span_fields: u16,
798 binding: [u8; 32],
799 projection: Option<u16>,
800 distinct: distinct::Strategy,
801 sort: Option<Vec<(usize, bool)>>,
802 descending: bool,
803}
804impl<'a> Plan<'a> {
805 fn admit(
806 entity: &'a EntitySchema,
807 request: &Request<'_>,
808 schema: [u8; 32],
809 incarnation: [u8; 16],
810 projection: Option<&TypeSchema>,
811 group_output: bool,
812 ) -> Result<Self, Error> {
813 if request.over_limit
814 || !(1..=32).contains(&request.rows)
815 || !(1..=MAX_WORK).contains(&request.work)
816 || !(1..=MAX_OUTPUT).contains(&request.bytes)
817 {
818 return Err(Error::Limit);
819 }
820 if !group_output && !request.groups.is_empty() {
821 return Err(Error::InvalidQuery);
822 }
823 for value in request
825 .predicates
826 .iter()
827 .filter_map(|p| match &p.operand {
828 QueryOperand::Literal(value) => Some(value),
829 QueryOperand::Field(_) | QueryOperand::Length(_) => None,
830 })
831 .chain(request.index.iter().flat_map(|(_, values)| values.iter()))
832 {
833 if match value {
834 IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
835 IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
836 _ => false,
837 } {
838 return Err(Error::Limit);
839 }
840 }
841 let primary = entity
842 .fields
843 .iter()
844 .position(|f| f.name == entity.primary_key)
845 .ok_or(Error::InvalidQuery)?;
846 let mut plan = Self {
847 index: None,
848 prefix: prefix(2, entity.id),
849 fixed_components: 0,
850 terms: Vec::new(),
851 selected: 1 << primary,
852 span_fields: 0,
853 binding: [0; 32],
854 projection: projection
855 .map(|output| admit_projection(entity, output))
856 .transpose()?,
857 distinct: distinct::Strategy::Identity,
858 sort: None,
859 descending: request.descending ^ request.primary_descending(entity),
860 };
861 for predicate in &request.predicates {
862 let position = entity
863 .fields
864 .iter()
865 .position(|f| f.name == predicate.field)
866 .ok_or(Error::InvalidQuery)?;
867 let field = &entity.fields[position];
868 let operand = match predicate.operand {
869 QueryOperand::Length(length) => {
870 let supported = match key::operand_type(field.value) {
871 FieldType::Text { .. }
872 | FieldType::Blob { .. }
873 | FieldType::List { .. } => true,
874 FieldType::Named(link) => matches!(
875 (link.definition)().body,
876 TypeBody::Map { .. } | TypeBody::Set { .. }
877 ),
878 _ => false,
879 };
880 if !supported || !predicate.comparison.is_relational() {
881 return Err(Error::InvalidQuery);
882 }
883 plan.span_fields |= 1 << position;
884 TermOperand::Length(length)
885 }
886 QueryOperand::Field(name) => {
887 let right = entity
888 .fields
889 .iter()
890 .position(|f| f.name == name)
891 .ok_or(Error::InvalidQuery)?;
892 let right_type = entity.fields[right].value;
893 let compatible = field.value == right_type
894 || matches!(
895 (field.value, right_type),
896 (FieldType::Text { .. }, FieldType::Text { .. })
897 | (FieldType::Blob { .. }, FieldType::Blob { .. })
898 );
899 if !compatible
900 || !key::supports(field.value)
901 || !predicate.comparison.is_relational()
902 {
903 return Err(Error::InvalidQuery);
904 }
905 plan.selected |= (1 << position) | (1 << right);
906 TermOperand::Field(right)
907 }
908 QueryOperand::Literal(value) => {
909 let absent = value == IndexValue::Absent;
910 if key::supports(field.value) {
911 plan.selected |= 1 << position;
912 } else if absent
913 && matches!(predicate.comparison, Comparison::Eq | Comparison::Ne)
914 {
915 plan.span_fields |= 1 << position;
916 } else {
917 return Err(Error::InvalidQuery);
918 }
919 predicate
920 .comparison
921 .admit(field.value, field.optional, value)?;
922 let mut bytes = Vec::new();
923 value.append_component(field.optional, &mut bytes);
924 TermOperand::Literal { bytes, absent }
925 }
926 };
927 plan.terms.push(Term {
928 position,
929 comparison: predicate.comparison,
930 operand,
931 or_next: predicate.or_next,
932 });
933 }
934 match order::select(entity, request)? {
937 order::Path::Primary => {}
938 order::Path::Index(path) => {
939 plan.index = Some(path.index);
940 plan.prefix = path.prefix;
941 plan.selected |= entity.key_fields();
942 plan.fixed_components = path.fixed;
943 }
944 order::Path::Sort(fields) => {
945 for &(position, _) in &fields {
946 plan.selected |= 1 << position;
947 }
948 plan.sort = Some(fields);
949 }
950 }
951 if request.distinct {
952 plan.distinct = distinct::admit(
953 entity,
954 request,
955 plan.projection,
956 plan.index,
957 plan.fixed_components,
958 plan.sort.is_some(),
959 )?;
960 if plan.distinct == distinct::Strategy::Complete {
961 plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
962 }
963 }
964 let mut hash = Sha256::new();
965 hash.update(b"ic-db:query:v1\0");
966 hash.update(schema);
967 hash.update(incarnation);
968 hash.update([u8::from(request.descending)]);
969 hash.update((plan.prefix.len() as u32).to_le_bytes());
970 hash.update(&plan.prefix);
971 for term in &plan.terms {
972 hash.update([term.position as u8, term.comparison as u8]);
973 match &term.operand {
974 TermOperand::Literal { bytes, .. } => {
975 hash.update((bytes.len() as u32).to_le_bytes());
976 hash.update(bytes);
977 }
978 TermOperand::Length(length) => {
979 hash.update((u32::MAX - 1).to_le_bytes());
980 hash.update(length.to_le_bytes());
981 }
982 TermOperand::Field(right) => {
983 hash.update(u32::MAX.to_le_bytes());
985 hash.update([*right as u8]);
986 }
987 }
988 }
989 let clauses = plan
992 .terms
993 .iter()
994 .enumerate()
995 .fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
996 if clauses != 0 {
997 hash.update(b"or-clauses\0");
998 hash.update([clauses]);
999 }
1000 if let Some(order) = &request.order {
1001 hash.update(b"order\0");
1002 hash.update([order.len() as u8]);
1003 for name in order {
1004 hash.update([entity
1006 .fields
1007 .iter()
1008 .position(|f| f.name == *name)
1009 .ok_or(Error::InvalidQuery)? as u8]);
1010 }
1011 }
1012 if request.order_descending != 0 {
1013 hash.update(b"order-directions\0");
1014 hash.update([request.order_descending]);
1015 }
1016 if let Some(mask) = plan.projection {
1019 hash.update(b"projection\0");
1020 hash.update(mask.to_le_bytes());
1021 }
1022 if request.distinct {
1023 hash.update(b"distinct\0");
1024 }
1025 plan.binding = hash.finalize().into();
1026 if let Some(cursor) = request.cursor {
1027 if cursor.binding != plan.binding {
1028 return Err(Error::InvalidCursor);
1029 }
1030 plan.validate_position(entity, &cursor.position)
1031 .map_err(|_| Error::InvalidCursor)?;
1032 }
1033 Ok(plan)
1034 }
1035 fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
1036 if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
1037 return Err(Error::InvalidCursor);
1038 }
1039 if let Some(index) = self.index {
1040 let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
1041 for name in index.fields {
1042 consume_index_component(entity, index, name, &mut remaining)?;
1043 }
1044 if !index.unique {
1045 key::consume(&mut remaining, entity.key_type()?)?;
1046 }
1047 if !remaining.is_empty() {
1048 return Err(Error::InvalidCursor);
1049 }
1050 } else {
1051 RowKey::decode(
1052 bytes.get(5..).ok_or(Error::InvalidCursor)?,
1053 entity.key_type()?,
1054 )?;
1055 }
1056 Ok(())
1057 }
1058 fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
1059 QueryCursor {
1060 binding: self.binding,
1061 position: position.to_vec(),
1062 inclusive,
1063 }
1064 }
1065}
1066
1067fn consume_index_component(
1069 entity: &EntitySchema,
1070 index: &IndexSchema,
1071 name: &str,
1072 remaining: &mut &[u8],
1073) -> Result<(), Error> {
1074 let field = entity
1075 .fields
1076 .iter()
1077 .find(|f| f.name == name)
1078 .ok_or(Error::InvalidQuery)?;
1079 if field.optional {
1080 let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
1081 *remaining = rest;
1082 match presence {
1083 0 if !index.present_only => return Ok(()),
1084 1 => {}
1085 _ => return Err(Error::InvalidCursor),
1086 }
1087 }
1088 key::consume(remaining, field.value)
1089}
1090
1091#[inline(never)]
1094#[expect(
1095 clippy::needless_pass_by_value,
1096 reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
1097)]
1098fn fetch_rows<M: Memory>(
1099 db: &Database<M>,
1100 entity: &EntitySchema,
1101 request: Request<'_>,
1102 projection: Option<&TypeSchema>,
1103) -> Result<QueryPage<Vec<u8>>, Error> {
1104 db.schema.admits(entity)?;
1105 let plan = Plan::admit(
1106 entity,
1107 &request,
1108 db.schema.fingerprint(),
1109 db.incarnation,
1110 projection,
1111 false,
1112 )?;
1113 execute(&db.map, entity, &request, &plan, None)
1114}
1115
1116fn execute<M: Memory>(
1117 map: &Map<M>,
1118 entity: &EntitySchema,
1119 request: &Request<'_>,
1120 plan: &Plan<'_>,
1121 mut aggregate: Option<aggregate::Accumulator<'_>>,
1122) -> Result<QueryPage<Vec<u8>>, Error> {
1123 execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
1124}
1125
1126const STEP_INPUT_BYTES: usize = 64 * 1024;
1129const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
1130
1131fn execute_inner<M: Memory>(
1132 map: &Map<M>,
1133 entity: &EntitySchema,
1134 request: &Request<'_>,
1135 plan: &Plan<'_>,
1136 mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
1137 mut input_bytes: Option<&mut usize>,
1138) -> Result<QueryPage<Vec<u8>>, Error> {
1139 let mut page = QueryPage {
1140 rows: Vec::new(),
1141 next: None,
1142 examined: 0,
1143 fetched: 0,
1144 output_bytes: 0,
1145 };
1146 let Some(bounds) = range::bounds(entity, request, plan)? else {
1147 return Ok(page);
1148 };
1149 let mut entries = map.range(bounds);
1150 let mut collected = if plan.distinct == distinct::Strategy::Complete {
1151 Some(distinct::Collection::new(
1152 plan.projection.ok_or(Error::InvalidQuery)?,
1153 ))
1154 } else {
1155 None
1156 };
1157 let mut sorted = plan
1158 .sort
1159 .as_ref()
1160 .map(|_| sort::Collection::new(request, plan.distinct == distinct::Strategy::Sorted));
1161 let mut component = Vec::new();
1162 let mut right_component = Vec::new();
1163 let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
1166 distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
1167 } else {
1168 None
1169 };
1170 while let Some(entry) = if plan.descending {
1171 entries.next_back()
1172 } else {
1173 entries.next()
1174 } {
1175 if request.work == 0 {
1179 return Err(Error::Limit);
1180 }
1181 page.examined += 1;
1182 let stored_key = entry.key();
1183 let mut read_bytes = stored_key.len();
1184 let (owner, bytes) = if plan.index.is_some() {
1185 let owner_bytes = entry.value();
1186 read_bytes += owner_bytes.len();
1187 let owner = RowKey::decode(&owner_bytes, entity.key_type()?)?;
1188 let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
1189 (owner, bytes)
1190 } else {
1191 (
1192 RowKey::decode(&stored_key[5..], entity.key_type()?)?,
1193 entry.value(),
1194 )
1195 };
1196 if let Some(used) = input_bytes.as_deref_mut() {
1197 read_bytes += bytes.len();
1198 if read_bytes > CANDIDATE_BYTES {
1199 return Err(Error::Corrupt);
1200 }
1201 *used += read_bytes;
1202 }
1203 page.fetched += 1;
1204 let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
1205 let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
1206 entity.inspect_fields(
1207 &bytes,
1208 plan.selected,
1209 &mut values,
1210 (plan.span_fields != 0
1211 || plan.projection.is_some()
1212 || aggregate.as_ref().is_some_and(|a| a.needs_spans()))
1213 .then_some(&mut spans),
1214 )?;
1215 let primary = entity
1216 .fields
1217 .iter()
1218 .position(|f| f.name == entity.primary_key)
1219 .ok_or(Error::Corrupt)?;
1220 if RowKey::from_index(values[primary])? != owner {
1221 return Err(Error::Corrupt);
1222 }
1223 if plan.index.is_some() {
1224 validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
1225 }
1226 let matches = plan
1227 .terms
1228 .split_inclusive(|term| !term.or_next)
1229 .all(|clause| {
1230 clause.iter().any(|term| {
1231 let value = values[term.position];
1232 component.clear();
1233 let (operand, optional) = match &term.operand {
1234 TermOperand::Literal { absent: true, .. }
1235 if plan.span_fields & (1 << term.position) != 0 =>
1236 {
1237 let absent = bytes[usize::from(spans[term.position].0)] == 0;
1238 return term.comparison.accepts_absent(absent);
1239 }
1240 TermOperand::Length(length) => {
1241 let (start, end) = spans[term.position];
1242 let span = &bytes[usize::from(start)..usize::from(end)];
1243 let actual = crate::codec::validated_length(
1244 span,
1245 entity.fields[term.position].optional,
1246 )
1247 .map(u32::to_be_bytes);
1248 return term.comparison.accepts(
1249 actual.as_ref().map(|v| v.as_slice()),
1250 Some(&length.to_be_bytes()),
1251 false,
1252 );
1253 }
1254 TermOperand::Literal { bytes, absent } => (
1255 (!absent).then_some(bytes.as_slice()),
1256 entity.fields[term.position].optional,
1257 ),
1258 TermOperand::Field(right) => {
1259 let rhs = values[*right];
1260 right_component.clear();
1261 rhs.append_component(false, &mut right_component);
1262 (
1263 (rhs != IndexValue::Absent).then_some(right_component.as_slice()),
1264 false,
1265 )
1266 }
1267 };
1268 value.append_component(optional, &mut component);
1269 term.comparison.accepts(
1270 (value != IndexValue::Absent).then_some(component.as_slice()),
1271 operand,
1272 optional,
1273 )
1274 })
1275 });
1276 let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
1277 let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
1278 if matches && let Some(accumulator) = aggregate.as_mut() {
1279 accumulator.push(entity, &values, &bytes, &spans)?;
1280 if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
1281 return Ok(page);
1283 }
1284 } else if matches && let Some(collection) = collected.as_mut() {
1285 collection.push(entity, request, &values, &bytes, &spans)?;
1286 } else if matches && let Some(collection) = sorted.as_mut() {
1287 collection.push(entity, plan, &values, &bytes, &spans)?;
1288 } else if matches && !duplicate {
1289 let size = plan
1290 .projection
1291 .map_or(bytes.len(), |mask| projection_size(&spans, mask));
1292 if size > request.bytes {
1293 return Err(Error::RowTooLarge);
1294 }
1295 if size > request.bytes - page.output_bytes {
1296 page.next = Some(plan.cursor(stored_key, true));
1297 return Ok(page);
1298 }
1299 page.output_bytes += size;
1300 if let Some(mask) = plan.projection {
1301 page.rows.push(copy_projection(&bytes, &spans, mask, size));
1302 } else {
1303 page.rows.push(bytes);
1304 }
1305 if let Some(boundary) = boundary {
1306 previous = Some(boundary.to_vec());
1307 }
1308 }
1309 if page.rows.len() == request.rows
1310 || page.examined == request.work
1311 || input_bytes
1312 .as_deref()
1313 .is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
1314 {
1315 if (aggregate.is_some() && input_bytes.is_none())
1316 || collected.is_some()
1317 || sorted.is_some()
1318 {
1319 return Err(Error::Limit);
1322 }
1323 page.next = Some(plan.cursor(stored_key, false));
1324 return Ok(page);
1325 }
1326 }
1327 if let Some(collection) = collected {
1328 page.output_bytes = collection.output_bytes;
1329 page.rows = collection.rows;
1330 }
1331 if let Some(collection) = sorted {
1332 collection.finish(request.bytes, &mut page)?;
1333 }
1334 Ok(page)
1335}