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]
544 pub fn filter_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
545 self.filter_fields(field, Comparison::Ge, lower)
546 .filter_fields(field, Comparison::Le, upper)
547 }
548
549 #[must_use]
554 pub fn filter_not_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
555 self.filter_any_operands(&[
556 (field, Comparison::Lt, QueryOperand::Field(lower)),
557 (field, Comparison::Gt, QueryOperand::Field(upper)),
558 ])
559 }
560
561 #[must_use]
568 pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
569 self.request.or_clause(
570 alternatives
571 .iter()
572 .map(|&(field, op, value)| (field, op, QueryOperand::Literal(value))),
573 );
574 self
575 }
576 #[must_use]
581 pub fn filter_any_operands(
582 mut self,
583 alternatives: &[(&'a str, Comparison, QueryOperand<'a>)],
584 ) -> Self {
585 self.request.or_clause(alternatives.iter().copied());
586 self
587 }
588
589 #[must_use]
597 pub fn filter_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
598 self.request.or_clause(
599 values
600 .iter()
601 .copied()
602 .map(|value| (field, Comparison::Eq, QueryOperand::Literal(value))),
603 );
604 self
605 }
606
607 #[must_use]
615 pub fn filter_not_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
616 self.request.filter_not_in(field, values);
617 self
618 }
619 #[must_use]
624 pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
625 self.request.using_index(name, values);
626 self
627 }
628 #[must_use]
638 pub fn order_by(mut self, fields: &[&'a str]) -> Self {
639 self.request.order_by(fields);
640 self
641 }
642 #[must_use]
647 pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
648 self.request.order_by_each(fields);
649 self
650 }
651 #[must_use]
653 pub fn descending(mut self) -> Self {
654 self.request.descending = true;
655 self
656 }
657 #[must_use]
664 pub fn limit(mut self, rows: usize) -> Self {
665 self.request.rows = rows;
666 self
667 }
668 #[must_use]
670 pub fn work_limit(mut self, candidates: usize) -> Self {
671 self.request.work = candidates;
672 self
673 }
674 #[must_use]
676 pub fn byte_limit(mut self, bytes: usize) -> Self {
677 self.request.bytes = bytes;
678 self
679 }
680 #[must_use]
682 pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
683 self.request.cursor = Some(cursor);
684 self
685 }
686 pub fn fetch(self) -> Result<QueryPage<E>, Error> {
693 fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
694 }
695 pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
705 let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
706 raw.decode_projection()
707 }
708}
709
710fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
714 let TypeBody::Record(fields) = &output.body else {
715 return Err(Error::InvalidQuery);
716 };
717 if fields.is_empty()
718 || fields.len() > crate::schema::MAX_FIELDS
719 || fields.windows(2).any(|w| w[0].name >= w[1].name)
720 {
721 return Err(Error::InvalidQuery);
722 }
723 let mut source = TypeGraph::default();
724 let mut target = TypeGraph::default();
725 let mut mask = 0;
726 for field in *fields {
727 let position = entity
728 .fields
729 .iter()
730 .position(|f| f.name == field.name)
731 .ok_or(Error::InvalidQuery)?;
732 let stored = &entity.fields[position];
733 if stored.value != field.value || stored.optional != field.optional {
734 return Err(Error::InvalidQuery);
735 }
736 source
737 .include(stored.value)
738 .map_err(|_| Error::InvalidQuery)?;
739 target
740 .include(field.value)
741 .map_err(|_| Error::InvalidQuery)?;
742 mask |= 1 << position;
743 }
744 if !source.contains(&target) {
745 return Err(Error::InvalidQuery);
746 }
747 Ok(mask)
748}
749
750struct Term {
751 position: usize,
752 comparison: Comparison,
753 operand: TermOperand,
754 or_next: bool,
755}
756
757enum TermOperand {
758 Literal {
759 bytes: Vec<u8>,
760 absent: bool,
761 },
762 Member {
763 item: FieldType,
764 needle: MemberNeedle,
765 },
766 Field(usize),
767 Length(u32),
768}
769
770enum MemberNeedle {
771 Literal(Vec<u8>),
772 Field(usize),
773}
774
775fn member_type(field: FieldType) -> Option<FieldType> {
776 match key::operand_type(field) {
777 FieldType::List { item, .. } => Some(*item),
778 FieldType::Named(link) => match (link.definition)().body {
779 TypeBody::Set { item, .. } => Some(item),
780 _ => None,
781 },
782 _ => None,
783 }
784}
785
786fn contains_member(
788 span: &[u8],
789 optional: bool,
790 item: FieldType,
791 needle: &[u8],
792 scratch: &mut Vec<u8>,
793) -> Result<bool, Error> {
794 let mut reader = Decoder::new(span)?;
795 if optional && !reader.boolean()? {
796 return Ok(false);
797 }
798 for _ in 0..reader.nat32()? {
799 scratch.clear();
800 IndexValue::read(&mut reader, item)?.append_component(false, scratch);
801 if scratch.as_slice() == needle {
802 return Ok(true);
803 }
804 }
805 Ok(false)
806}
807
808fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
809 for (i, field) in entity.fields.iter().enumerate() {
810 if mask & (1 << i) != 0 && !key::supports(field.value) {
811 return Err(Error::InvalidQuery);
812 }
813 }
814 Ok(())
815}
816
817fn comparison_key(
819 entity: &EntitySchema,
820 mask: u16,
821 values: &[IndexValue<'_>],
822) -> Result<Vec<u8>, Error> {
823 let mut key = Vec::new();
824 for (i, field) in entity.fields.iter().enumerate() {
825 if mask & (1 << i) != 0 {
826 values[i].append_component(field.optional, &mut key);
827 if key.len() > MAX_COMPARISON_KEY {
828 return Err(Error::Limit);
829 }
830 }
831 }
832 Ok(key)
833}
834
835fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
836 if size > limit {
837 return Err(Error::RowTooLarge);
838 }
839 if size > limit - *used {
840 return Err(Error::Limit);
841 }
842 *used += size;
843 Ok(())
844}
845
846fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
848 spans
849 .iter()
850 .enumerate()
851 .filter(|(i, _)| mask & (1 << i) != 0)
852 .map(|(_, (start, end))| usize::from(end - start))
853 .sum()
854}
855
856fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
857 let mut output = Vec::with_capacity(size);
858 for (i, &(start, end)) in spans.iter().enumerate() {
859 if mask & (1 << i) != 0 {
860 output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
861 }
862 }
863 output
864}
865struct Plan<'a> {
866 primary: usize,
867 index: Option<&'a IndexSchema>,
868 prefix: Vec<u8>,
869 fixed_components: usize,
870 terms: Vec<Term>,
871 selected: u16,
872 span_fields: u16,
874 binding: [u8; 32],
875 projection: Option<u16>,
876 distinct: distinct::Strategy,
877 sort: Option<Vec<(usize, bool)>>,
878 descending: bool,
879}
880impl<'a> Plan<'a> {
881 fn use_index(&mut self, entity: &EntitySchema, path: order::IndexPath<'a>) {
882 self.index = Some(path.index);
883 self.prefix = path.prefix;
884 self.fixed_components = path.fixed;
885 self.selected |= entity.key_fields();
886 }
887
888 fn admit(
889 entity: &'a EntitySchema,
890 request: &Request<'_>,
891 schema: [u8; 32],
892 incarnation: [u8; 16],
893 projection: Option<&TypeSchema>,
894 group_output: bool,
895 ) -> Result<Self, Error> {
896 if request.over_limit
897 || !(1..=32).contains(&request.rows)
898 || !(1..=MAX_WORK).contains(&request.work)
899 || !(1..=MAX_OUTPUT).contains(&request.bytes)
900 {
901 return Err(Error::Limit);
902 }
903 if !group_output && !request.groups.is_empty() {
904 return Err(Error::InvalidQuery);
905 }
906 for value in request
908 .predicates
909 .iter()
910 .filter_map(|p| match &p.operand {
911 QueryOperand::Literal(value) => Some(value),
912 QueryOperand::Field(_) | QueryOperand::Length(_) => None,
913 })
914 .chain(request.index.iter().flat_map(|(_, values)| values.iter()))
915 {
916 if match value {
917 IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
918 IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
919 _ => false,
920 } {
921 return Err(Error::Limit);
922 }
923 }
924 let primary = entity
925 .fields
926 .iter()
927 .position(|f| f.name == entity.primary_key && !f.optional)
928 .ok_or(Error::InvalidQuery)?;
929 let mut plan = Self {
930 primary,
931 index: None,
932 prefix: prefix(2, entity.id),
933 fixed_components: 0,
934 terms: Vec::new(),
935 selected: 1 << primary,
936 span_fields: 0,
937 binding: [0; 32],
938 projection: projection
939 .map(|output| admit_projection(entity, output))
940 .transpose()?,
941 distinct: distinct::Strategy::Identity,
942 sort: None,
943 descending: request.descending ^ request.primary_descending(entity),
944 };
945 for predicate in &request.predicates {
946 let position = entity
947 .fields
948 .iter()
949 .position(|f| f.name == predicate.field)
950 .ok_or(Error::InvalidQuery)?;
951 let field = &entity.fields[position];
952 let member = if predicate.comparison == Comparison::Contains {
953 member_type(field.value)
954 } else {
955 None
956 };
957 let operand = match predicate.operand {
958 QueryOperand::Length(length) => {
959 let supported = match key::operand_type(field.value) {
960 FieldType::Text { .. }
961 | FieldType::Blob { .. }
962 | FieldType::List { .. } => true,
963 FieldType::Named(link) => matches!(
964 (link.definition)().body,
965 TypeBody::Map { .. } | TypeBody::Set { .. }
966 ),
967 _ => false,
968 };
969 if !supported || !predicate.comparison.is_relational() {
970 return Err(Error::InvalidQuery);
971 }
972 plan.span_fields |= 1 << position;
973 TermOperand::Length(length)
974 }
975 QueryOperand::Field(name) => {
976 let right = entity
977 .fields
978 .iter()
979 .position(|f| f.name == name)
980 .ok_or(Error::InvalidQuery)?;
981 let right_type = entity.fields[right].value;
982 let left_type = member.unwrap_or(field.value);
983 let compatible = left_type == right_type
984 || matches!(
985 (left_type, right_type),
986 (FieldType::Text { .. }, FieldType::Text { .. })
987 | (FieldType::Blob { .. }, FieldType::Blob { .. })
988 );
989 if !compatible
990 || !key::supports(left_type)
991 || (member.is_none() && !predicate.comparison.supports_scalar(left_type))
992 {
993 return Err(Error::InvalidQuery);
994 }
995 plan.selected |= 1 << right;
996 if let Some(item) = member {
997 plan.span_fields |= 1 << position;
998 TermOperand::Member {
999 item,
1000 needle: MemberNeedle::Field(right),
1001 }
1002 } else {
1003 plan.selected |= 1 << position;
1004 TermOperand::Field(right)
1005 }
1006 }
1007 QueryOperand::Literal(value) => {
1008 if let Some(item) = member {
1009 if !key::supports(item) {
1010 return Err(Error::InvalidQuery);
1011 }
1012 value.admit(item, false)?;
1013 let mut bytes = Vec::new();
1014 value.append_component(false, &mut bytes);
1015 plan.span_fields |= 1 << position;
1016 TermOperand::Member {
1017 item,
1018 needle: MemberNeedle::Literal(bytes),
1019 }
1020 } else {
1021 let absent = value == IndexValue::Absent;
1022 if key::supports(field.value) {
1023 plan.selected |= 1 << position;
1024 } else if absent
1025 && matches!(predicate.comparison, Comparison::Eq | Comparison::Ne)
1026 {
1027 plan.span_fields |= 1 << position;
1028 } else {
1029 return Err(Error::InvalidQuery);
1030 }
1031 predicate
1032 .comparison
1033 .admit(field.value, field.optional, value)?;
1034 let mut bytes = Vec::new();
1035 value.append_component(field.optional, &mut bytes);
1036 TermOperand::Literal { bytes, absent }
1037 }
1038 }
1039 };
1040 plan.terms.push(Term {
1041 position,
1042 comparison: predicate.comparison,
1043 operand,
1044 or_next: predicate.or_next,
1045 });
1046 }
1047 match order::select(entity, request)? {
1050 order::Path::Primary => {}
1051 order::Path::Index(path) => plan.use_index(entity, path),
1052 order::Path::Sort(fields) => {
1053 for &(position, _) in &fields {
1054 plan.selected |= 1 << position;
1055 }
1056 plan.sort = Some(fields);
1057 }
1058 }
1059 if request.distinct {
1060 plan.distinct = distinct::admit(
1061 entity,
1062 request,
1063 plan.projection,
1064 plan.index,
1065 plan.fixed_components,
1066 plan.sort.is_some(),
1067 )?;
1068 if plan.distinct == distinct::Strategy::Complete {
1069 plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
1070 }
1071 }
1072 let mut hash = Sha256::new();
1073 hash.update(b"ic-db:query:v1\0");
1074 hash.update(schema);
1075 hash.update(incarnation);
1076 hash.update([u8::from(request.descending)]);
1077 hash.update((plan.prefix.len() as u32).to_le_bytes());
1078 hash.update(&plan.prefix);
1079 for term in &plan.terms {
1080 hash.update([term.position as u8, term.comparison as u8]);
1081 match &term.operand {
1082 TermOperand::Literal { bytes, .. }
1083 | TermOperand::Member {
1084 needle: MemberNeedle::Literal(bytes),
1085 ..
1086 } => {
1087 hash.update((bytes.len() as u32).to_le_bytes());
1088 hash.update(bytes);
1089 }
1090 TermOperand::Length(length) => {
1091 hash.update((u32::MAX - 1).to_le_bytes());
1092 hash.update(length.to_le_bytes());
1093 }
1094 TermOperand::Field(right)
1095 | TermOperand::Member {
1096 needle: MemberNeedle::Field(right),
1097 ..
1098 } => {
1099 hash.update(u32::MAX.to_le_bytes());
1101 hash.update([*right as u8]);
1102 }
1103 }
1104 }
1105 let clauses = plan
1108 .terms
1109 .iter()
1110 .enumerate()
1111 .fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
1112 if clauses != 0 {
1113 hash.update(b"or-clauses\0");
1114 hash.update([clauses]);
1115 }
1116 if let Some(order) = &request.order {
1117 hash.update(b"order\0");
1118 hash.update([order.len() as u8]);
1119 for name in order {
1120 hash.update([entity
1122 .fields
1123 .iter()
1124 .position(|f| f.name == *name)
1125 .ok_or(Error::InvalidQuery)? as u8]);
1126 }
1127 }
1128 if request.order_descending != 0 {
1129 hash.update(b"order-directions\0");
1130 hash.update([request.order_descending]);
1131 }
1132 if let Some(mask) = plan.projection {
1135 hash.update(b"projection\0");
1136 hash.update(mask.to_le_bytes());
1137 }
1138 if request.distinct {
1139 hash.update(b"distinct\0");
1140 }
1141 plan.binding = hash.finalize().into();
1142 if let Some(cursor) = request.cursor {
1143 if cursor.binding != plan.binding {
1144 return Err(Error::InvalidCursor);
1145 }
1146 plan.validate_position(entity, &cursor.position)
1147 .map_err(|_| Error::InvalidCursor)?;
1148 }
1149 Ok(plan)
1150 }
1151 fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
1152 if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
1153 return Err(Error::InvalidCursor);
1154 }
1155 if let Some(index) = self.index {
1156 let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
1157 for name in index.fields {
1158 consume_index_component(entity, index, name, &mut remaining)?;
1159 }
1160 if !index.unique {
1161 key::consume(&mut remaining, entity.key_type()?)?;
1162 }
1163 if !remaining.is_empty() {
1164 return Err(Error::InvalidCursor);
1165 }
1166 } else {
1167 RowKey::decode(
1168 bytes.get(5..).ok_or(Error::InvalidCursor)?,
1169 entity.key_type()?,
1170 )?;
1171 }
1172 Ok(())
1173 }
1174 fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
1175 QueryCursor {
1176 binding: self.binding,
1177 position: position.to_vec(),
1178 inclusive,
1179 }
1180 }
1181}
1182
1183fn consume_index_component(
1185 entity: &EntitySchema,
1186 index: &IndexSchema,
1187 name: &str,
1188 remaining: &mut &[u8],
1189) -> Result<(), Error> {
1190 let field = entity
1191 .fields
1192 .iter()
1193 .find(|f| f.name == name)
1194 .ok_or(Error::InvalidQuery)?;
1195 if field.optional {
1196 let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
1197 *remaining = rest;
1198 match presence {
1199 0 if !index.present_only => return Ok(()),
1200 1 => {}
1201 _ => return Err(Error::InvalidCursor),
1202 }
1203 }
1204 key::consume(remaining, field.value)
1205}
1206
1207#[inline(never)]
1210#[expect(
1211 clippy::needless_pass_by_value,
1212 reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
1213)]
1214fn fetch_rows<M: Memory>(
1215 db: &Database<M>,
1216 entity: &EntitySchema,
1217 request: Request<'_>,
1218 projection: Option<&TypeSchema>,
1219) -> Result<QueryPage<Vec<u8>>, Error> {
1220 db.schema.admits(entity)?;
1221 let plan = Plan::admit(
1222 entity,
1223 &request,
1224 db.schema.fingerprint(),
1225 db.incarnation,
1226 projection,
1227 false,
1228 )?;
1229 execute(&db.map, entity, &request, &plan, None)
1230}
1231
1232fn execute<M: Memory>(
1233 map: &Map<M>,
1234 entity: &EntitySchema,
1235 request: &Request<'_>,
1236 plan: &Plan<'_>,
1237 mut aggregate: Option<aggregate::Accumulator<'_>>,
1238) -> Result<QueryPage<Vec<u8>>, Error> {
1239 execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
1240}
1241
1242const STEP_INPUT_BYTES: usize = 64 * 1024;
1245const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
1246
1247fn execute_inner<M: Memory>(
1248 map: &Map<M>,
1249 entity: &EntitySchema,
1250 request: &Request<'_>,
1251 plan: &Plan<'_>,
1252 mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
1253 mut input_bytes: Option<&mut usize>,
1254) -> Result<QueryPage<Vec<u8>>, Error> {
1255 let mut page = QueryPage {
1256 rows: Vec::new(),
1257 next: None,
1258 examined: 0,
1259 fetched: 0,
1260 output_bytes: 0,
1261 };
1262 let Some(bounds) = range::bounds(entity, request, plan)? else {
1263 return Ok(page);
1264 };
1265 let terminal = range::terminal_key(&bounds, plan.descending);
1266 let mut entries = map.range((bounds.0.as_ref(), bounds.1.as_ref()));
1267 let mut collected = if plan.distinct == distinct::Strategy::Complete {
1268 Some(distinct::Collection::new(
1269 plan.projection.ok_or(Error::InvalidQuery)?,
1270 ))
1271 } else {
1272 None
1273 };
1274 let mut sorted = plan
1275 .sort
1276 .as_ref()
1277 .map(|_| sort::Collection::new(request, plan.distinct == distinct::Strategy::Sorted));
1278 let mut component = Vec::new();
1279 let mut right_component = Vec::new();
1280 let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
1283 distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
1284 } else {
1285 None
1286 };
1287 let primary_type = entity.fields[plan.primary].value;
1288 while let Some(entry) = if plan.descending {
1289 entries.next_back()
1290 } else {
1291 entries.next()
1292 } {
1293 if request.work == 0 {
1297 return Err(Error::Limit);
1298 }
1299 page.examined += 1;
1300 let stored_key = entry.key();
1301 let mut read_bytes = stored_key.len();
1302 let (owner, bytes) = if plan.index.is_some() {
1303 let owner_bytes = entry.value();
1304 read_bytes += owner_bytes.len();
1305 let owner = RowKey::decode(&owner_bytes, primary_type)?;
1306 let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
1307 (owner, bytes)
1308 } else {
1309 (
1310 RowKey::decode(&stored_key[5..], primary_type)?,
1311 entry.value(),
1312 )
1313 };
1314 if let Some(used) = input_bytes.as_deref_mut() {
1315 read_bytes += bytes.len();
1316 if read_bytes > CANDIDATE_BYTES {
1317 return Err(Error::Corrupt);
1318 }
1319 *used += read_bytes;
1320 }
1321 page.fetched += 1;
1322 let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
1323 let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
1324 entity.inspect_fields(
1325 &bytes,
1326 plan.selected,
1327 &mut values,
1328 (plan.span_fields != 0
1329 || plan.projection.is_some()
1330 || aggregate.as_ref().is_some_and(|a| a.needs_spans()))
1331 .then_some(&mut spans),
1332 )?;
1333 if RowKey::from_index(values[plan.primary])? != owner {
1334 return Err(Error::Corrupt);
1335 }
1336 if plan.index.is_some() {
1337 validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
1338 }
1339 let mut accepts = |term: &Term| -> Result<bool, Error> {
1340 let value = values[term.position];
1341 component.clear();
1342 let (operand, optional) = match &term.operand {
1343 TermOperand::Literal { absent: true, .. }
1344 if plan.span_fields & (1 << term.position) != 0 =>
1345 {
1346 let absent = bytes[usize::from(spans[term.position].0)] == 0;
1347 return Ok(term.comparison.accepts_absent(absent));
1348 }
1349 TermOperand::Member { item, needle } => {
1350 let needle = match needle {
1351 MemberNeedle::Literal(bytes) => bytes.as_slice(),
1352 MemberNeedle::Field(right) => {
1353 let value = values[*right];
1354 if value == IndexValue::Absent {
1355 return Ok(false);
1356 }
1357 right_component.clear();
1358 value.append_component(false, &mut right_component);
1359 &right_component
1360 }
1361 };
1362 let (start, end) = spans[term.position];
1363 return contains_member(
1364 &bytes[usize::from(start)..usize::from(end)],
1365 entity.fields[term.position].optional,
1366 *item,
1367 needle,
1368 &mut component,
1369 );
1370 }
1371 TermOperand::Length(length) => {
1372 let (start, end) = spans[term.position];
1373 let span = &bytes[usize::from(start)..usize::from(end)];
1374 let actual =
1375 crate::codec::validated_length(span, entity.fields[term.position].optional)
1376 .map(u32::to_be_bytes);
1377 return Ok(term.comparison.accepts(
1378 actual.as_ref().map(|v| v.as_slice()),
1379 Some(&length.to_be_bytes()),
1380 false,
1381 ));
1382 }
1383 TermOperand::Literal { bytes, absent } => (
1384 (!absent).then_some(bytes.as_slice()),
1385 entity.fields[term.position].optional,
1386 ),
1387 TermOperand::Field(right) => {
1388 let rhs = values[*right];
1389 right_component.clear();
1390 rhs.append_component(false, &mut right_component);
1391 (
1392 (rhs != IndexValue::Absent).then_some(right_component.as_slice()),
1393 false,
1394 )
1395 }
1396 };
1397 value.append_component(optional, &mut component);
1398 Ok(term.comparison.accepts(
1399 (value != IndexValue::Absent).then_some(component.as_slice()),
1400 operand,
1401 optional,
1402 ))
1403 };
1404 let matches = 'matches: {
1405 'clause: for clause in plan.terms.split_inclusive(|term| !term.or_next) {
1406 for term in clause {
1407 if accepts(term)? {
1408 continue 'clause;
1409 }
1410 }
1411 break 'matches false;
1412 }
1413 true
1414 };
1415 let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
1416 let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
1417 if matches && let Some(accumulator) = aggregate.as_mut() {
1418 accumulator.push(entity, &values, &bytes, &spans)?;
1419 if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
1420 return Ok(page);
1422 }
1423 } else if matches && let Some(collection) = collected.as_mut() {
1424 collection.push(entity, request, &values, &bytes, &spans)?;
1425 } else if matches && let Some(collection) = sorted.as_mut() {
1426 collection.push(entity, plan, &values, &bytes, &spans)?;
1427 } else if matches && !duplicate {
1428 let size = plan
1429 .projection
1430 .map_or(bytes.len(), |mask| projection_size(&spans, mask));
1431 if size > request.bytes {
1432 return Err(Error::RowTooLarge);
1433 }
1434 if size > request.bytes - page.output_bytes {
1435 page.next = Some(plan.cursor(stored_key, true));
1436 return Ok(page);
1437 }
1438 page.output_bytes += size;
1439 if let Some(mask) = plan.projection {
1440 page.rows.push(copy_projection(&bytes, &spans, mask, size));
1441 } else {
1442 page.rows.push(bytes);
1443 }
1444 if let Some(boundary) = boundary {
1445 previous = Some(boundary.to_vec());
1446 }
1447 }
1448 if page.rows.len() == request.rows
1449 || page.examined == request.work
1450 || input_bytes
1451 .as_deref()
1452 .is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
1453 {
1454 if terminal == Some(stored_key) {
1455 break;
1456 }
1457 if (aggregate.is_some() && input_bytes.is_none())
1458 || collected.is_some()
1459 || sorted.is_some()
1460 {
1461 return Err(Error::Limit);
1464 }
1465 page.next = Some(plan.cursor(stored_key, false));
1466 return Ok(page);
1467 }
1468 }
1469 if let Some(collection) = collected {
1470 page.output_bytes = collection.output_bytes;
1471 page.rows = collection.rows;
1472 }
1473 if let Some(collection) = sorted {
1474 collection.finish(request.bytes, &mut page)?;
1475 }
1476 Ok(page)
1477}