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,
62}
63
64impl Comparison {
65 fn is_relational(self) -> bool {
66 matches!(
67 self,
68 Self::Eq | Self::Ne | Self::Lt | Self::Le | Self::Gt | Self::Ge
69 )
70 }
71
72 fn supports_scalar(self, field: FieldType) -> bool {
73 self.is_relational()
74 || matches!(
75 key::operand_type(field),
76 FieldType::Text { .. } | FieldType::Blob { .. }
77 )
78 }
79
80 fn admit(self, field: FieldType, optional: bool, value: IndexValue<'_>) -> Result<(), Error> {
81 value.admit(field, optional)?;
82 if !self.supports_scalar(field) {
83 return Err(Error::InvalidQuery);
84 }
85 if value == IndexValue::Absent && !matches!(self, Self::Eq | Self::Ne) {
86 return Err(Error::InvalidOperand);
87 }
88 Ok(())
89 }
90
91 fn accepts(self, actual: Option<&[u8]>, operand: Option<&[u8]>, optional: bool) -> bool {
92 if actual.is_none() {
93 return self.accepts_absent(operand.is_none());
94 }
95 match self {
96 Self::Eq => actual == operand,
97 Self::Ne => actual != operand,
98 Self::StartsWith | Self::EndsWith | Self::Contains => {
99 fn content(key: &[u8], optional: bool) -> Option<&[u8]> {
102 key.get(usize::from(optional)..)?.strip_suffix(&[0, 0])
103 }
104 actual
105 .and_then(|key| content(key, optional))
106 .zip(operand.and_then(|key| content(key, optional)))
107 .is_some_and(|(actual, operand)| match self {
108 Self::StartsWith => actual.starts_with(operand),
111 Self::EndsWith => actual
115 .strip_suffix(operand)
116 .is_some_and(|prefix| prefix.last() != Some(&0)),
117 _ => contains_component(actual, operand),
118 })
119 }
120 _ if actual.is_none() || operand.is_none() => false,
121 Self::Lt => actual < operand,
122 Self::Le => actual <= operand,
123 Self::Gt => actual > operand,
124 Self::Ge => actual >= operand,
125 }
126 }
127
128 fn accepts_absent(self, other_absent: bool) -> bool {
131 match self {
132 Self::Eq => other_absent,
133 Self::Ne => !other_absent,
134 _ => false,
135 }
136 }
137}
138
139fn contains_component(actual: &[u8], needle: &[u8]) -> bool {
141 let Some(start) = memchr::memmem::find(actual, needle) else {
142 return false;
143 };
144 if start == 0 || actual[start - 1] != 0 {
145 return true;
146 }
147 fn raw(content: &[u8]) -> Vec<u8> {
151 let mut bytes = Vec::with_capacity(content.len().min(crate::codec::MAX_ROW_BYTES));
152 let mut encoded = content.iter();
153 while let Some(&byte) = encoded.next() {
154 bytes.push(byte);
155 if byte == 0 {
156 encoded.next();
157 }
158 }
159 bytes
160 }
161 memchr::memmem::find(&raw(actual), &raw(needle)).is_some()
162}
163
164#[derive(Clone, Debug, PartialEq, Eq)]
168pub struct QueryCursor {
169 binding: [u8; 32],
170 position: Vec<u8>,
171 inclusive: bool,
172}
173impl QueryCursor {
174 pub(super) const MAX_ENCODED_BYTES: usize = 34 + crate::MAX_INDEX_KEY_BYTES;
175
176 #[must_use]
178 pub fn to_bytes(&self) -> Vec<u8> {
179 let mut bytes = vec![1, u8::from(self.inclusive)];
180 bytes.extend(self.binding);
181 bytes.extend(&self.position);
182 bytes
183 }
184 pub fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
188 if !(35..=Self::MAX_ENCODED_BYTES).contains(&bytes.len()) || bytes[0] != 1 || bytes[1] > 1 {
189 return Err(Error::InvalidCursor);
190 }
191 Ok(Self {
192 binding: bytes[2..34].try_into().map_err(|_| Error::InvalidCursor)?,
193 position: bytes[34..].to_vec(),
194 inclusive: bytes[1] == 1,
195 })
196 }
197}
198
199#[derive(Debug)]
202pub struct QueryPage<T> {
203 pub rows: Vec<T>,
205 pub next: Option<QueryCursor>,
207 pub examined: usize,
209 pub fetched: usize,
211 pub output_bytes: usize,
213}
214
215impl QueryPage<Vec<u8>> {
216 #[inline(never)]
217 pub(super) fn decode_entities<E: Entity>(self) -> Result<QueryPage<E>, Error> {
218 Ok(QueryPage {
219 rows: self
220 .rows
221 .iter()
222 .map(|bytes| E::decode(bytes))
223 .collect::<Result<_, _>>()?,
224 next: self.next,
225 examined: self.examined,
226 fetched: self.fetched,
227 output_bytes: self.output_bytes,
228 })
229 }
230
231 #[inline(never)]
232 fn decode_projection<R: Value>(self) -> Result<QueryPage<R>, Error> {
233 Ok(QueryPage {
234 rows: self
235 .rows
236 .iter()
237 .map(|bytes| {
238 let mut reader = Decoder::new(bytes)?;
239 let row = R::decode_from(&mut reader)?;
241 reader.finish()?;
242 Ok(row)
243 })
244 .collect::<Result<_, Error>>()?,
245 next: self.next,
246 examined: self.examined,
247 fetched: self.fetched,
248 output_bytes: self.output_bytes,
249 })
250 }
251}
252
253#[derive(Clone, Copy, Debug, PartialEq, Eq)]
255pub enum QueryOperand<'a> {
256 Literal(IndexValue<'a>),
258 Length(u32),
260 Field(&'a str),
262}
263
264struct Predicate<'a> {
265 field: &'a str,
266 comparison: Comparison,
267 operand: QueryOperand<'a>,
268 or_next: bool,
270}
271struct Request<'a> {
272 groups: aggregate::GroupRequest<'a>,
273 predicates: Vec<Predicate<'a>>,
274 index: Option<(&'a str, Vec<IndexValue<'a>>)>,
275 order: Option<Vec<&'a str>>,
276 order_descending: u8,
277 descending: bool,
278 distinct: bool,
279 rows: usize,
280 work: usize,
281 bytes: usize,
282 cursor: Option<&'a QueryCursor>,
283 over_limit: bool,
284}
285
286impl Default for Request<'_> {
287 fn default() -> Self {
288 Self {
289 groups: aggregate::GroupRequest::default(),
290 predicates: Vec::new(),
291 index: None,
292 order: None,
293 order_descending: 0,
294 descending: false,
295 distinct: false,
296 rows: 32,
297 work: 128,
298 bytes: MAX_OUTPUT,
299 cursor: None,
300 over_limit: false,
301 }
302 }
303}
304
305impl<'a> Request<'a> {
308 #[inline(never)]
309 fn filter(&mut self, field: &'a str, comparison: Comparison, operand: QueryOperand<'a>) {
310 if self.predicates.len() == MAX_TERMS {
311 self.over_limit = true;
312 } else {
313 self.predicates.push(Predicate {
314 field,
315 comparison,
316 operand,
317 or_next: false,
318 });
319 }
320 }
321
322 #[inline(never)]
323 fn or_clause(
324 &mut self,
325 alternatives: impl ExactSizeIterator<Item = (&'a str, Comparison, QueryOperand<'a>)>,
326 ) {
327 let count = alternatives.len();
328 if count == 0 || count > MAX_TERMS - self.predicates.len() {
329 self.over_limit = true;
330 } else {
331 self.predicates.extend(alternatives.enumerate().map(
332 |(i, (field, comparison, operand))| Predicate {
333 field,
334 comparison,
335 operand,
336 or_next: i + 1 < count,
337 },
338 ));
339 }
340 }
341
342 #[inline(never)]
343 fn filter_not_in(&mut self, field: &'a str, values: &[IndexValue<'a>]) {
344 if values.is_empty() || values.len() > MAX_TERMS - self.predicates.len() {
345 self.over_limit = true;
346 return;
347 }
348 for &value in values {
349 self.filter(field, Comparison::Ne, QueryOperand::Literal(value));
350 }
351 }
352
353 #[inline(never)]
354 fn using_index(&mut self, name: &'a str, values: &[IndexValue<'a>]) {
355 if values.len() > 4 {
356 self.over_limit = true;
357 } else {
358 self.index = Some((name, values.to_vec()));
359 }
360 }
361
362 #[inline(never)]
363 fn order_by(&mut self, fields: &[&'a str]) {
364 self.order_descending = 0;
365 if fields.len() > 4 {
366 self.over_limit = true;
367 } else {
368 self.order = Some(fields.to_vec());
369 }
370 }
371
372 #[inline(never)]
373 fn order_by_each(&mut self, fields: &[(&'a str, SortDirection)]) {
374 if fields.len() > 4 {
375 self.over_limit = true;
376 return;
377 }
378 self.order = Some(fields.iter().map(|(name, _)| *name).collect());
379 self.order_descending = fields
380 .iter()
381 .enumerate()
382 .fold(0, |mask, (i, (_, direction))| {
383 mask | (u8::from(*direction == SortDirection::Descending) << i)
384 });
385 }
386
387 fn primary_descending(&self, entity: &EntitySchema) -> bool {
388 self.order_descending != 0
389 && self.order.as_ref().is_some_and(|fields| {
390 fields.last() == Some(&entity.primary_key)
391 && self.order_descending & (1 << (fields.len() - 1)) != 0
392 })
393 }
394}
395
396pub(super) fn source_page<M: Memory>(
398 map: &Map<M>,
399 entity: &EntitySchema,
400 binding: [u8; 32],
401 incarnation: [u8; 16],
402 cursor: Option<&QueryCursor>,
403 rows: usize,
404 bytes: usize,
405) -> Result<QueryPage<Vec<u8>>, Error> {
406 let request = Request {
407 rows,
408 work: rows,
409 bytes,
410 cursor,
411 ..Request::default()
412 };
413 let plan = Plan::admit(entity, &request, binding, incarnation, None, false)?;
414 execute(map, entity, &request, &plan, None)
415}
416
417pub struct Query<'a, E, M: Memory = ic_storage::DefaultMemoryImpl> {
421 db: &'a Database<M>,
422 request: Request<'a>,
423 entity: PhantomData<E>,
424}
425impl<M: Memory> Database<M> {
426 #[must_use]
428 pub fn query<E: Entity>(&self) -> Query<'_, E, M> {
429 Query {
430 db: self,
431 entity: PhantomData,
432 request: Request::default(),
433 }
434 }
435}
436impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
437 #[must_use]
448 pub fn distinct(mut self) -> Self {
449 self.request.distinct = true;
450 self
451 }
452 #[must_use]
462 pub fn filter(
463 mut self,
464 field: &'a str,
465 comparison: Comparison,
466 value: impl Into<IndexValue<'a>>,
467 ) -> Self {
468 self.request
469 .filter(field, comparison, QueryOperand::Literal(value.into()));
470 self
471 }
472 #[must_use]
478 pub fn filter_fields(mut self, left: &'a str, comparison: Comparison, right: &'a str) -> Self {
479 self.request
480 .filter(left, comparison, QueryOperand::Field(right));
481 self
482 }
483 #[must_use]
487 pub fn filter_length(mut self, field: &'a str, comparison: Comparison, length: u32) -> Self {
488 self.request
489 .filter(field, comparison, QueryOperand::Length(length));
490 self
491 }
492 #[must_use]
495 pub fn filter_present(self, field: &'a str) -> Self {
496 self.filter(field, Comparison::Ne, IndexValue::Absent)
497 }
498 #[must_use]
501 pub fn filter_absent(self, field: &'a str) -> Self {
502 self.filter(field, Comparison::Eq, IndexValue::Absent)
503 }
504 #[must_use]
511 pub fn filter_between(
512 self,
513 field: &'a str,
514 lower: impl Into<IndexValue<'a>>,
515 upper: impl Into<IndexValue<'a>>,
516 ) -> Self {
517 self.filter(field, Comparison::Ge, lower)
518 .filter(field, Comparison::Le, upper)
519 }
520 #[must_use]
528 pub fn filter_not_between(
529 self,
530 field: &'a str,
531 lower: impl Into<IndexValue<'a>>,
532 upper: impl Into<IndexValue<'a>>,
533 ) -> Self {
534 self.filter_any(&[
535 (field, Comparison::Lt, lower.into()),
536 (field, Comparison::Gt, upper.into()),
537 ])
538 }
539 #[must_use]
546 pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
547 self.request.or_clause(
548 alternatives
549 .iter()
550 .map(|&(field, op, value)| (field, op, QueryOperand::Literal(value))),
551 );
552 self
553 }
554 #[must_use]
559 pub fn filter_any_operands(
560 mut self,
561 alternatives: &[(&'a str, Comparison, QueryOperand<'a>)],
562 ) -> Self {
563 self.request.or_clause(alternatives.iter().copied());
564 self
565 }
566
567 #[must_use]
575 pub fn filter_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
576 self.request.or_clause(
577 values
578 .iter()
579 .copied()
580 .map(|value| (field, Comparison::Eq, QueryOperand::Literal(value))),
581 );
582 self
583 }
584
585 #[must_use]
593 pub fn filter_not_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
594 self.request.filter_not_in(field, values);
595 self
596 }
597 #[must_use]
602 pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
603 self.request.using_index(name, values);
604 self
605 }
606 #[must_use]
616 pub fn order_by(mut self, fields: &[&'a str]) -> Self {
617 self.request.order_by(fields);
618 self
619 }
620 #[must_use]
625 pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
626 self.request.order_by_each(fields);
627 self
628 }
629 #[must_use]
631 pub fn descending(mut self) -> Self {
632 self.request.descending = true;
633 self
634 }
635 #[must_use]
642 pub fn limit(mut self, rows: usize) -> Self {
643 self.request.rows = rows;
644 self
645 }
646 #[must_use]
648 pub fn work_limit(mut self, candidates: usize) -> Self {
649 self.request.work = candidates;
650 self
651 }
652 #[must_use]
654 pub fn byte_limit(mut self, bytes: usize) -> Self {
655 self.request.bytes = bytes;
656 self
657 }
658 #[must_use]
660 pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
661 self.request.cursor = Some(cursor);
662 self
663 }
664 pub fn fetch(self) -> Result<QueryPage<E>, Error> {
671 fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
672 }
673 pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
683 let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
684 raw.decode_projection()
685 }
686}
687
688fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
692 let TypeBody::Record(fields) = &output.body else {
693 return Err(Error::InvalidQuery);
694 };
695 if fields.is_empty()
696 || fields.len() > crate::schema::MAX_FIELDS
697 || fields.windows(2).any(|w| w[0].name >= w[1].name)
698 {
699 return Err(Error::InvalidQuery);
700 }
701 let mut source = TypeGraph::default();
702 let mut target = TypeGraph::default();
703 let mut mask = 0;
704 for field in *fields {
705 let position = entity
706 .fields
707 .iter()
708 .position(|f| f.name == field.name)
709 .ok_or(Error::InvalidQuery)?;
710 let stored = &entity.fields[position];
711 if stored.value != field.value || stored.optional != field.optional {
712 return Err(Error::InvalidQuery);
713 }
714 source
715 .include(stored.value)
716 .map_err(|_| Error::InvalidQuery)?;
717 target
718 .include(field.value)
719 .map_err(|_| Error::InvalidQuery)?;
720 mask |= 1 << position;
721 }
722 if !source.contains(&target) {
723 return Err(Error::InvalidQuery);
724 }
725 Ok(mask)
726}
727
728struct Term {
729 position: usize,
730 comparison: Comparison,
731 operand: TermOperand,
732 or_next: bool,
733}
734
735enum TermOperand {
736 Literal {
737 bytes: Vec<u8>,
738 absent: bool,
739 },
740 Member {
741 item: FieldType,
742 needle: MemberNeedle,
743 },
744 Field(usize),
745 Length(u32),
746}
747
748enum MemberNeedle {
749 Literal(Vec<u8>),
750 Field(usize),
751}
752
753fn member_type(field: FieldType) -> Option<FieldType> {
754 match key::operand_type(field) {
755 FieldType::List { item, .. } => Some(*item),
756 FieldType::Named(link) => match (link.definition)().body {
757 TypeBody::Set { item, .. } => Some(item),
758 _ => None,
759 },
760 _ => None,
761 }
762}
763
764fn contains_member(
766 span: &[u8],
767 optional: bool,
768 item: FieldType,
769 needle: &[u8],
770 scratch: &mut Vec<u8>,
771) -> Result<bool, Error> {
772 let mut reader = Decoder::new(span)?;
773 if optional && !reader.boolean()? {
774 return Ok(false);
775 }
776 for _ in 0..reader.nat32()? {
777 scratch.clear();
778 IndexValue::read(&mut reader, item)?.append_component(false, scratch);
779 if scratch.as_slice() == needle {
780 return Ok(true);
781 }
782 }
783 Ok(false)
784}
785
786fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
787 for (i, field) in entity.fields.iter().enumerate() {
788 if mask & (1 << i) != 0 && !key::supports(field.value) {
789 return Err(Error::InvalidQuery);
790 }
791 }
792 Ok(())
793}
794
795fn comparison_key(
797 entity: &EntitySchema,
798 mask: u16,
799 values: &[IndexValue<'_>],
800) -> Result<Vec<u8>, Error> {
801 let mut key = Vec::new();
802 for (i, field) in entity.fields.iter().enumerate() {
803 if mask & (1 << i) != 0 {
804 values[i].append_component(field.optional, &mut key);
805 if key.len() > MAX_COMPARISON_KEY {
806 return Err(Error::Limit);
807 }
808 }
809 }
810 Ok(key)
811}
812
813fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
814 if size > limit {
815 return Err(Error::RowTooLarge);
816 }
817 if size > limit - *used {
818 return Err(Error::Limit);
819 }
820 *used += size;
821 Ok(())
822}
823
824fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
826 spans
827 .iter()
828 .enumerate()
829 .filter(|(i, _)| mask & (1 << i) != 0)
830 .map(|(_, (start, end))| usize::from(end - start))
831 .sum()
832}
833
834fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
835 let mut output = Vec::with_capacity(size);
836 for (i, &(start, end)) in spans.iter().enumerate() {
837 if mask & (1 << i) != 0 {
838 output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
839 }
840 }
841 output
842}
843struct Plan<'a> {
844 primary: usize,
845 index: Option<&'a IndexSchema>,
846 prefix: Vec<u8>,
847 fixed_components: usize,
848 terms: Vec<Term>,
849 selected: u16,
850 span_fields: u16,
852 binding: [u8; 32],
853 projection: Option<u16>,
854 distinct: distinct::Strategy,
855 sort: Option<Vec<(usize, bool)>>,
856 descending: bool,
857}
858impl<'a> Plan<'a> {
859 fn admit(
860 entity: &'a EntitySchema,
861 request: &Request<'_>,
862 schema: [u8; 32],
863 incarnation: [u8; 16],
864 projection: Option<&TypeSchema>,
865 group_output: bool,
866 ) -> Result<Self, Error> {
867 if request.over_limit
868 || !(1..=32).contains(&request.rows)
869 || !(1..=MAX_WORK).contains(&request.work)
870 || !(1..=MAX_OUTPUT).contains(&request.bytes)
871 {
872 return Err(Error::Limit);
873 }
874 if !group_output && !request.groups.is_empty() {
875 return Err(Error::InvalidQuery);
876 }
877 for value in request
879 .predicates
880 .iter()
881 .filter_map(|p| match &p.operand {
882 QueryOperand::Literal(value) => Some(value),
883 QueryOperand::Field(_) | QueryOperand::Length(_) => None,
884 })
885 .chain(request.index.iter().flat_map(|(_, values)| values.iter()))
886 {
887 if match value {
888 IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
889 IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
890 _ => false,
891 } {
892 return Err(Error::Limit);
893 }
894 }
895 let primary = entity
896 .fields
897 .iter()
898 .position(|f| f.name == entity.primary_key && !f.optional)
899 .ok_or(Error::InvalidQuery)?;
900 let mut plan = Self {
901 primary,
902 index: None,
903 prefix: prefix(2, entity.id),
904 fixed_components: 0,
905 terms: Vec::new(),
906 selected: 1 << primary,
907 span_fields: 0,
908 binding: [0; 32],
909 projection: projection
910 .map(|output| admit_projection(entity, output))
911 .transpose()?,
912 distinct: distinct::Strategy::Identity,
913 sort: None,
914 descending: request.descending ^ request.primary_descending(entity),
915 };
916 for predicate in &request.predicates {
917 let position = entity
918 .fields
919 .iter()
920 .position(|f| f.name == predicate.field)
921 .ok_or(Error::InvalidQuery)?;
922 let field = &entity.fields[position];
923 let member = if predicate.comparison == Comparison::Contains {
924 member_type(field.value)
925 } else {
926 None
927 };
928 let operand = match predicate.operand {
929 QueryOperand::Length(length) => {
930 let supported = match key::operand_type(field.value) {
931 FieldType::Text { .. }
932 | FieldType::Blob { .. }
933 | FieldType::List { .. } => true,
934 FieldType::Named(link) => matches!(
935 (link.definition)().body,
936 TypeBody::Map { .. } | TypeBody::Set { .. }
937 ),
938 _ => false,
939 };
940 if !supported || !predicate.comparison.is_relational() {
941 return Err(Error::InvalidQuery);
942 }
943 plan.span_fields |= 1 << position;
944 TermOperand::Length(length)
945 }
946 QueryOperand::Field(name) => {
947 let right = entity
948 .fields
949 .iter()
950 .position(|f| f.name == name)
951 .ok_or(Error::InvalidQuery)?;
952 let right_type = entity.fields[right].value;
953 let left_type = member.unwrap_or(field.value);
954 let compatible = left_type == right_type
955 || matches!(
956 (left_type, right_type),
957 (FieldType::Text { .. }, FieldType::Text { .. })
958 | (FieldType::Blob { .. }, FieldType::Blob { .. })
959 );
960 if !compatible
961 || !key::supports(left_type)
962 || (member.is_none() && !predicate.comparison.supports_scalar(left_type))
963 {
964 return Err(Error::InvalidQuery);
965 }
966 plan.selected |= 1 << right;
967 if let Some(item) = member {
968 plan.span_fields |= 1 << position;
969 TermOperand::Member {
970 item,
971 needle: MemberNeedle::Field(right),
972 }
973 } else {
974 plan.selected |= 1 << position;
975 TermOperand::Field(right)
976 }
977 }
978 QueryOperand::Literal(value) => {
979 if let Some(item) = member {
980 if !key::supports(item) {
981 return Err(Error::InvalidQuery);
982 }
983 value.admit(item, false)?;
984 let mut bytes = Vec::new();
985 value.append_component(false, &mut bytes);
986 plan.span_fields |= 1 << position;
987 TermOperand::Member {
988 item,
989 needle: MemberNeedle::Literal(bytes),
990 }
991 } else {
992 let absent = value == IndexValue::Absent;
993 if key::supports(field.value) {
994 plan.selected |= 1 << position;
995 } else if absent
996 && matches!(predicate.comparison, Comparison::Eq | Comparison::Ne)
997 {
998 plan.span_fields |= 1 << position;
999 } else {
1000 return Err(Error::InvalidQuery);
1001 }
1002 predicate
1003 .comparison
1004 .admit(field.value, field.optional, value)?;
1005 let mut bytes = Vec::new();
1006 value.append_component(field.optional, &mut bytes);
1007 TermOperand::Literal { bytes, absent }
1008 }
1009 }
1010 };
1011 plan.terms.push(Term {
1012 position,
1013 comparison: predicate.comparison,
1014 operand,
1015 or_next: predicate.or_next,
1016 });
1017 }
1018 match order::select(entity, request)? {
1021 order::Path::Primary => {}
1022 order::Path::Index(path) => {
1023 plan.index = Some(path.index);
1024 plan.prefix = path.prefix;
1025 plan.selected |= entity.key_fields();
1026 plan.fixed_components = path.fixed;
1027 }
1028 order::Path::Sort(fields) => {
1029 for &(position, _) in &fields {
1030 plan.selected |= 1 << position;
1031 }
1032 plan.sort = Some(fields);
1033 }
1034 }
1035 if request.distinct {
1036 plan.distinct = distinct::admit(
1037 entity,
1038 request,
1039 plan.projection,
1040 plan.index,
1041 plan.fixed_components,
1042 plan.sort.is_some(),
1043 )?;
1044 if plan.distinct == distinct::Strategy::Complete {
1045 plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
1046 }
1047 }
1048 let mut hash = Sha256::new();
1049 hash.update(b"ic-db:query:v1\0");
1050 hash.update(schema);
1051 hash.update(incarnation);
1052 hash.update([u8::from(request.descending)]);
1053 hash.update((plan.prefix.len() as u32).to_le_bytes());
1054 hash.update(&plan.prefix);
1055 for term in &plan.terms {
1056 hash.update([term.position as u8, term.comparison as u8]);
1057 match &term.operand {
1058 TermOperand::Literal { bytes, .. }
1059 | TermOperand::Member {
1060 needle: MemberNeedle::Literal(bytes),
1061 ..
1062 } => {
1063 hash.update((bytes.len() as u32).to_le_bytes());
1064 hash.update(bytes);
1065 }
1066 TermOperand::Length(length) => {
1067 hash.update((u32::MAX - 1).to_le_bytes());
1068 hash.update(length.to_le_bytes());
1069 }
1070 TermOperand::Field(right)
1071 | TermOperand::Member {
1072 needle: MemberNeedle::Field(right),
1073 ..
1074 } => {
1075 hash.update(u32::MAX.to_le_bytes());
1077 hash.update([*right as u8]);
1078 }
1079 }
1080 }
1081 let clauses = plan
1084 .terms
1085 .iter()
1086 .enumerate()
1087 .fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
1088 if clauses != 0 {
1089 hash.update(b"or-clauses\0");
1090 hash.update([clauses]);
1091 }
1092 if let Some(order) = &request.order {
1093 hash.update(b"order\0");
1094 hash.update([order.len() as u8]);
1095 for name in order {
1096 hash.update([entity
1098 .fields
1099 .iter()
1100 .position(|f| f.name == *name)
1101 .ok_or(Error::InvalidQuery)? as u8]);
1102 }
1103 }
1104 if request.order_descending != 0 {
1105 hash.update(b"order-directions\0");
1106 hash.update([request.order_descending]);
1107 }
1108 if let Some(mask) = plan.projection {
1111 hash.update(b"projection\0");
1112 hash.update(mask.to_le_bytes());
1113 }
1114 if request.distinct {
1115 hash.update(b"distinct\0");
1116 }
1117 plan.binding = hash.finalize().into();
1118 if let Some(cursor) = request.cursor {
1119 if cursor.binding != plan.binding {
1120 return Err(Error::InvalidCursor);
1121 }
1122 plan.validate_position(entity, &cursor.position)
1123 .map_err(|_| Error::InvalidCursor)?;
1124 }
1125 Ok(plan)
1126 }
1127 fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
1128 if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
1129 return Err(Error::InvalidCursor);
1130 }
1131 if let Some(index) = self.index {
1132 let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
1133 for name in index.fields {
1134 consume_index_component(entity, index, name, &mut remaining)?;
1135 }
1136 if !index.unique {
1137 key::consume(&mut remaining, entity.key_type()?)?;
1138 }
1139 if !remaining.is_empty() {
1140 return Err(Error::InvalidCursor);
1141 }
1142 } else {
1143 RowKey::decode(
1144 bytes.get(5..).ok_or(Error::InvalidCursor)?,
1145 entity.key_type()?,
1146 )?;
1147 }
1148 Ok(())
1149 }
1150 fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
1151 QueryCursor {
1152 binding: self.binding,
1153 position: position.to_vec(),
1154 inclusive,
1155 }
1156 }
1157}
1158
1159fn consume_index_component(
1161 entity: &EntitySchema,
1162 index: &IndexSchema,
1163 name: &str,
1164 remaining: &mut &[u8],
1165) -> Result<(), Error> {
1166 let field = entity
1167 .fields
1168 .iter()
1169 .find(|f| f.name == name)
1170 .ok_or(Error::InvalidQuery)?;
1171 if field.optional {
1172 let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
1173 *remaining = rest;
1174 match presence {
1175 0 if !index.present_only => return Ok(()),
1176 1 => {}
1177 _ => return Err(Error::InvalidCursor),
1178 }
1179 }
1180 key::consume(remaining, field.value)
1181}
1182
1183#[inline(never)]
1186#[expect(
1187 clippy::needless_pass_by_value,
1188 reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
1189)]
1190fn fetch_rows<M: Memory>(
1191 db: &Database<M>,
1192 entity: &EntitySchema,
1193 request: Request<'_>,
1194 projection: Option<&TypeSchema>,
1195) -> Result<QueryPage<Vec<u8>>, Error> {
1196 db.schema.admits(entity)?;
1197 let plan = Plan::admit(
1198 entity,
1199 &request,
1200 db.schema.fingerprint(),
1201 db.incarnation,
1202 projection,
1203 false,
1204 )?;
1205 execute(&db.map, entity, &request, &plan, None)
1206}
1207
1208fn execute<M: Memory>(
1209 map: &Map<M>,
1210 entity: &EntitySchema,
1211 request: &Request<'_>,
1212 plan: &Plan<'_>,
1213 mut aggregate: Option<aggregate::Accumulator<'_>>,
1214) -> Result<QueryPage<Vec<u8>>, Error> {
1215 execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
1216}
1217
1218const STEP_INPUT_BYTES: usize = 64 * 1024;
1221const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
1222
1223fn execute_inner<M: Memory>(
1224 map: &Map<M>,
1225 entity: &EntitySchema,
1226 request: &Request<'_>,
1227 plan: &Plan<'_>,
1228 mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
1229 mut input_bytes: Option<&mut usize>,
1230) -> Result<QueryPage<Vec<u8>>, Error> {
1231 let mut page = QueryPage {
1232 rows: Vec::new(),
1233 next: None,
1234 examined: 0,
1235 fetched: 0,
1236 output_bytes: 0,
1237 };
1238 let Some(bounds) = range::bounds(entity, request, plan)? else {
1239 return Ok(page);
1240 };
1241 let mut entries = map.range(bounds);
1242 let mut collected = if plan.distinct == distinct::Strategy::Complete {
1243 Some(distinct::Collection::new(
1244 plan.projection.ok_or(Error::InvalidQuery)?,
1245 ))
1246 } else {
1247 None
1248 };
1249 let mut sorted = plan
1250 .sort
1251 .as_ref()
1252 .map(|_| sort::Collection::new(request, plan.distinct == distinct::Strategy::Sorted));
1253 let mut component = Vec::new();
1254 let mut right_component = Vec::new();
1255 let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
1258 distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
1259 } else {
1260 None
1261 };
1262 let primary_type = entity.fields[plan.primary].value;
1263 while let Some(entry) = if plan.descending {
1264 entries.next_back()
1265 } else {
1266 entries.next()
1267 } {
1268 if request.work == 0 {
1272 return Err(Error::Limit);
1273 }
1274 page.examined += 1;
1275 let stored_key = entry.key();
1276 let mut read_bytes = stored_key.len();
1277 let (owner, bytes) = if plan.index.is_some() {
1278 let owner_bytes = entry.value();
1279 read_bytes += owner_bytes.len();
1280 let owner = RowKey::decode(&owner_bytes, primary_type)?;
1281 let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
1282 (owner, bytes)
1283 } else {
1284 (
1285 RowKey::decode(&stored_key[5..], primary_type)?,
1286 entry.value(),
1287 )
1288 };
1289 if let Some(used) = input_bytes.as_deref_mut() {
1290 read_bytes += bytes.len();
1291 if read_bytes > CANDIDATE_BYTES {
1292 return Err(Error::Corrupt);
1293 }
1294 *used += read_bytes;
1295 }
1296 page.fetched += 1;
1297 let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
1298 let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
1299 entity.inspect_fields(
1300 &bytes,
1301 plan.selected,
1302 &mut values,
1303 (plan.span_fields != 0
1304 || plan.projection.is_some()
1305 || aggregate.as_ref().is_some_and(|a| a.needs_spans()))
1306 .then_some(&mut spans),
1307 )?;
1308 if RowKey::from_index(values[plan.primary])? != owner {
1309 return Err(Error::Corrupt);
1310 }
1311 if plan.index.is_some() {
1312 validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
1313 }
1314 let mut accepts = |term: &Term| -> Result<bool, Error> {
1315 let value = values[term.position];
1316 component.clear();
1317 let (operand, optional) = match &term.operand {
1318 TermOperand::Literal { absent: true, .. }
1319 if plan.span_fields & (1 << term.position) != 0 =>
1320 {
1321 let absent = bytes[usize::from(spans[term.position].0)] == 0;
1322 return Ok(term.comparison.accepts_absent(absent));
1323 }
1324 TermOperand::Member { item, needle } => {
1325 let needle = match needle {
1326 MemberNeedle::Literal(bytes) => bytes.as_slice(),
1327 MemberNeedle::Field(right) => {
1328 let value = values[*right];
1329 if value == IndexValue::Absent {
1330 return Ok(false);
1331 }
1332 right_component.clear();
1333 value.append_component(false, &mut right_component);
1334 &right_component
1335 }
1336 };
1337 let (start, end) = spans[term.position];
1338 return contains_member(
1339 &bytes[usize::from(start)..usize::from(end)],
1340 entity.fields[term.position].optional,
1341 *item,
1342 needle,
1343 &mut component,
1344 );
1345 }
1346 TermOperand::Length(length) => {
1347 let (start, end) = spans[term.position];
1348 let span = &bytes[usize::from(start)..usize::from(end)];
1349 let actual =
1350 crate::codec::validated_length(span, entity.fields[term.position].optional)
1351 .map(u32::to_be_bytes);
1352 return Ok(term.comparison.accepts(
1353 actual.as_ref().map(|v| v.as_slice()),
1354 Some(&length.to_be_bytes()),
1355 false,
1356 ));
1357 }
1358 TermOperand::Literal { bytes, absent } => (
1359 (!absent).then_some(bytes.as_slice()),
1360 entity.fields[term.position].optional,
1361 ),
1362 TermOperand::Field(right) => {
1363 let rhs = values[*right];
1364 right_component.clear();
1365 rhs.append_component(false, &mut right_component);
1366 (
1367 (rhs != IndexValue::Absent).then_some(right_component.as_slice()),
1368 false,
1369 )
1370 }
1371 };
1372 value.append_component(optional, &mut component);
1373 Ok(term.comparison.accepts(
1374 (value != IndexValue::Absent).then_some(component.as_slice()),
1375 operand,
1376 optional,
1377 ))
1378 };
1379 let matches = 'matches: {
1380 'clause: for clause in plan.terms.split_inclusive(|term| !term.or_next) {
1381 for term in clause {
1382 if accepts(term)? {
1383 continue 'clause;
1384 }
1385 }
1386 break 'matches false;
1387 }
1388 true
1389 };
1390 let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
1391 let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
1392 if matches && let Some(accumulator) = aggregate.as_mut() {
1393 accumulator.push(entity, &values, &bytes, &spans)?;
1394 if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
1395 return Ok(page);
1397 }
1398 } else if matches && let Some(collection) = collected.as_mut() {
1399 collection.push(entity, request, &values, &bytes, &spans)?;
1400 } else if matches && let Some(collection) = sorted.as_mut() {
1401 collection.push(entity, plan, &values, &bytes, &spans)?;
1402 } else if matches && !duplicate {
1403 let size = plan
1404 .projection
1405 .map_or(bytes.len(), |mask| projection_size(&spans, mask));
1406 if size > request.bytes {
1407 return Err(Error::RowTooLarge);
1408 }
1409 if size > request.bytes - page.output_bytes {
1410 page.next = Some(plan.cursor(stored_key, true));
1411 return Ok(page);
1412 }
1413 page.output_bytes += size;
1414 if let Some(mask) = plan.projection {
1415 page.rows.push(copy_projection(&bytes, &spans, mask, size));
1416 } else {
1417 page.rows.push(bytes);
1418 }
1419 if let Some(boundary) = boundary {
1420 previous = Some(boundary.to_vec());
1421 }
1422 }
1423 if page.rows.len() == request.rows
1424 || page.examined == request.work
1425 || input_bytes
1426 .as_deref()
1427 .is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
1428 {
1429 if (aggregate.is_some() && input_bytes.is_none())
1430 || collected.is_some()
1431 || sorted.is_some()
1432 {
1433 return Err(Error::Limit);
1436 }
1437 page.next = Some(plan.cursor(stored_key, false));
1438 return Ok(page);
1439 }
1440 }
1441 if let Some(collection) = collected {
1442 page.output_bytes = collection.output_bytes;
1443 page.rows = collection.rows;
1444 }
1445 if let Some(collection) = sorted {
1446 collection.finish(request.bytes, &mut page)?;
1447 }
1448 Ok(page)
1449}