1mod aggregate;
3mod distinct;
4mod order;
5mod range;
6mod sort;
7pub use aggregate::{
8 Aggregate, GroupCount, GroupOrder, GroupValue,
9 jobs::{AggregateJobs, GroupCursor, GroupPage, JobHandle, JobOutcome, JobStep},
10};
11
12use super::{Database, Map, prefix, row_key, validate_index_entry};
13use crate::{
14 Entity, EntitySchema, Error, FieldType, IndexSchema, IndexValue, TypeBody, TypeSchema, Value,
15 codec::Decoder, key, primary::RowKey, types::TypeGraph,
16};
17use ic_storage::Memory;
18use sha2::{Digest, Sha256};
19use std::marker::PhantomData;
20
21const MAX_TERMS: usize = 8;
22const MAX_WORK: usize = 512;
23const MAX_OUTPUT: usize = 128 * 1024;
24const MAX_COMPARISON_KEY: usize = 4096;
25const MAX_DISTINCT_VALUES: usize = 32;
26const MAX_STATE_BYTES: usize = 128 * 1024;
27
28#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30pub enum SortDirection {
31 Ascending,
33 Descending,
35}
36
37#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39#[repr(u8)]
40pub enum Comparison {
41 Eq = 0,
43 Ne = 1,
45 Lt = 2,
47 Le = 3,
49 Gt = 4,
51 Ge = 5,
53 StartsWith = 6,
57 EndsWith = 7,
60 Contains = 8,
64}
65
66impl Comparison {
67 fn is_relational(self) -> bool {
68 matches!(
69 self,
70 Self::Eq | Self::Ne | Self::Lt | Self::Le | Self::Gt | Self::Ge
71 )
72 }
73
74 fn supports_scalar(self, field: FieldType) -> bool {
75 self.is_relational()
76 || matches!(
77 key::operand_type(field),
78 FieldType::Text { .. } | FieldType::Blob { .. }
79 )
80 }
81
82 fn admit(self, field: FieldType, optional: bool, value: IndexValue<'_>) -> Result<(), Error> {
83 value.admit(field, optional)?;
84 if !self.supports_scalar(field) {
85 return Err(Error::InvalidQuery);
86 }
87 if value == IndexValue::Absent && !matches!(self, Self::Eq | Self::Ne) {
88 return Err(Error::InvalidOperand);
89 }
90 Ok(())
91 }
92
93 fn accepts(self, actual: Option<&[u8]>, operand: Option<&[u8]>, optional: bool) -> bool {
94 if actual.is_none() {
95 return self.accepts_absent(operand.is_none());
96 }
97 match self {
98 Self::Eq => actual == operand,
99 Self::Ne => actual != operand,
100 Self::StartsWith | Self::EndsWith | Self::Contains => {
101 fn content(key: &[u8], optional: bool) -> Option<&[u8]> {
104 key.get(usize::from(optional)..)?.strip_suffix(&[0, 0])
105 }
106 actual
107 .and_then(|key| content(key, optional))
108 .zip(operand.and_then(|key| content(key, optional)))
109 .is_some_and(|(actual, operand)| match self {
110 Self::StartsWith => actual.starts_with(operand),
113 Self::EndsWith => actual
117 .strip_suffix(operand)
118 .is_some_and(|prefix| prefix.last() != Some(&0)),
119 _ => contains_component(actual, operand),
120 })
121 }
122 _ if actual.is_none() || operand.is_none() => false,
123 Self::Lt => actual < operand,
124 Self::Le => actual <= operand,
125 Self::Gt => actual > operand,
126 Self::Ge => actual >= operand,
127 }
128 }
129
130 fn accepts_absent(self, other_absent: bool) -> bool {
133 match self {
134 Self::Eq => other_absent,
135 Self::Ne => !other_absent,
136 _ => false,
137 }
138 }
139}
140
141fn contains_component(actual: &[u8], needle: &[u8]) -> bool {
143 let Some(start) = memchr::memmem::find(actual, needle) else {
144 return false;
145 };
146 if start == 0 || actual[start - 1] != 0 {
147 return true;
148 }
149 fn raw(content: &[u8]) -> Vec<u8> {
153 let mut bytes = Vec::with_capacity(content.len().min(crate::codec::MAX_ROW_BYTES));
154 let mut encoded = content.iter();
155 while let Some(&byte) = encoded.next() {
156 bytes.push(byte);
157 if byte == 0 {
158 encoded.next();
159 }
160 }
161 bytes
162 }
163 memchr::memmem::find(&raw(actual), &raw(needle)).is_some()
164}
165
166#[derive(Clone, Debug, PartialEq, Eq)]
170pub struct QueryCursor {
171 binding: [u8; 32],
172 position: Vec<u8>,
173 inclusive: bool,
174}
175impl QueryCursor {
176 pub(super) const MAX_ENCODED_BYTES: usize = 34 + crate::MAX_INDEX_KEY_BYTES;
177
178 #[must_use]
180 pub fn to_bytes(&self) -> Vec<u8> {
181 let mut bytes = vec![1, u8::from(self.inclusive)];
182 bytes.extend(self.binding);
183 bytes.extend(&self.position);
184 bytes
185 }
186
187 pub fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
191 if !(35..=Self::MAX_ENCODED_BYTES).contains(&bytes.len()) || bytes[0] != 1 || bytes[1] > 1 {
192 return Err(Error::InvalidCursor);
193 }
194 Ok(Self {
195 binding: bytes[2..34].try_into().map_err(|_| Error::InvalidCursor)?,
196 position: bytes[34..].to_vec(),
197 inclusive: bytes[1] == 1,
198 })
199 }
200}
201
202#[derive(Debug)]
205pub struct QueryPage<T> {
206 pub rows: Vec<T>,
208 pub next: Option<QueryCursor>,
210 pub examined: usize,
212 pub fetched: usize,
214 pub output_bytes: usize,
216}
217
218impl QueryPage<Vec<u8>> {
219 #[inline(never)]
220 pub(super) fn decode_entities<E: Entity>(self) -> Result<QueryPage<E>, Error> {
221 Ok(QueryPage {
222 rows: self
223 .rows
224 .iter()
225 .map(|bytes| E::decode(bytes))
226 .collect::<Result<_, _>>()?,
227 next: self.next,
228 examined: self.examined,
229 fetched: self.fetched,
230 output_bytes: self.output_bytes,
231 })
232 }
233
234 #[inline(never)]
235 fn decode_projection<R: Value>(self) -> Result<QueryPage<R>, Error> {
236 Ok(QueryPage {
237 rows: self
238 .rows
239 .iter()
240 .map(|bytes| {
241 let mut reader = Decoder::new(bytes)?;
242 let row = R::decode_from(&mut reader)?;
244 reader.finish()?;
245 Ok(row)
246 })
247 .collect::<Result<_, Error>>()?,
248 next: self.next,
249 examined: self.examined,
250 fetched: self.fetched,
251 output_bytes: self.output_bytes,
252 })
253 }
254}
255
256#[derive(Clone, Copy, Debug, PartialEq, Eq)]
258pub enum QueryOperand<'a> {
259 Literal(IndexValue<'a>),
261 Length(u32),
263 Field(&'a str),
265}
266
267struct Predicate<'a> {
268 field: &'a str,
269 comparison: Comparison,
270 operand: QueryOperand<'a>,
271 or_next: bool,
273}
274struct Request<'a> {
275 groups: aggregate::GroupRequest<'a>,
276 predicates: Vec<Predicate<'a>>,
277 index: Option<(&'a str, Vec<IndexValue<'a>>)>,
278 order: Option<Vec<&'a str>>,
279 order_descending: u8,
280 descending: bool,
281 distinct: bool,
282 rows: usize,
283 work: usize,
284 bytes: usize,
285 cursor: Option<&'a QueryCursor>,
286 over_limit: bool,
287}
288
289impl Default for Request<'_> {
290 fn default() -> Self {
291 Self {
292 groups: aggregate::GroupRequest::default(),
293 predicates: Vec::new(),
294 index: None,
295 order: None,
296 order_descending: 0,
297 descending: false,
298 distinct: false,
299 rows: 32,
300 work: 128,
301 bytes: MAX_OUTPUT,
302 cursor: None,
303 over_limit: false,
304 }
305 }
306}
307
308impl<'a> Request<'a> {
311 #[inline(never)]
312 fn filter(&mut self, field: &'a str, comparison: Comparison, operand: QueryOperand<'a>) {
313 if self.predicates.len() == MAX_TERMS {
314 self.over_limit = true;
315 } else {
316 self.predicates.push(Predicate {
317 field,
318 comparison,
319 operand,
320 or_next: false,
321 });
322 }
323 }
324
325 #[inline(never)]
326 fn or_clause(
327 &mut self,
328 alternatives: impl ExactSizeIterator<Item = (&'a str, Comparison, QueryOperand<'a>)>,
329 ) {
330 let count = alternatives.len();
331 if count == 0 || count > MAX_TERMS - self.predicates.len() {
332 self.over_limit = true;
333 } else {
334 self.predicates.extend(alternatives.enumerate().map(
335 |(i, (field, comparison, operand))| Predicate {
336 field,
337 comparison,
338 operand,
339 or_next: i + 1 < count,
340 },
341 ));
342 }
343 }
344
345 #[inline(never)]
346 fn filter_not_in(&mut self, field: &'a str, values: &[IndexValue<'a>]) {
347 if values.is_empty() || values.len() > MAX_TERMS - self.predicates.len() {
348 self.over_limit = true;
349 return;
350 }
351 for &value in values {
352 self.filter(field, Comparison::Ne, QueryOperand::Literal(value));
353 }
354 }
355
356 #[inline(never)]
357 fn using_index(&mut self, name: &'a str, values: &[IndexValue<'a>]) {
358 if values.len() > 4 {
359 self.over_limit = true;
360 } else {
361 self.index = Some((name, values.to_vec()));
362 }
363 }
364
365 #[inline(never)]
366 fn order_by(&mut self, fields: &[&'a str]) {
367 self.order_descending = 0;
368 if fields.len() > 4 {
369 self.over_limit = true;
370 } else {
371 self.order = Some(fields.to_vec());
372 }
373 }
374
375 #[inline(never)]
376 fn order_by_each(&mut self, fields: &[(&'a str, SortDirection)]) {
377 if fields.len() > 4 {
378 self.over_limit = true;
379 return;
380 }
381 self.order = Some(fields.iter().map(|(name, _)| *name).collect());
382 self.order_descending = fields
383 .iter()
384 .enumerate()
385 .fold(0, |mask, (i, (_, direction))| {
386 mask | (u8::from(*direction == SortDirection::Descending) << i)
387 });
388 }
389
390 fn primary_descending(&self, entity: &EntitySchema) -> bool {
391 self.order_descending != 0
392 && self.order.as_ref().is_some_and(|fields| {
393 fields.last() == Some(&entity.primary_key)
394 && self.order_descending & (1 << (fields.len() - 1)) != 0
395 })
396 }
397}
398
399pub(super) fn source_page<M: Memory>(
401 map: &Map<M>,
402 entity: &EntitySchema,
403 binding: [u8; 32],
404 incarnation: [u8; 16],
405 cursor: Option<&QueryCursor>,
406 rows: usize,
407 bytes: usize,
408) -> Result<QueryPage<Vec<u8>>, Error> {
409 let request = Request {
410 rows,
411 work: rows,
412 bytes,
413 cursor,
414 ..Request::default()
415 };
416 let plan = Plan::admit(entity, &request, binding, incarnation, None, false)?;
417 execute(map, entity, &request, &plan, None)
418}
419
420pub struct Query<'a, E, M: Memory> {
424 db: &'a Database<M>,
425 request: Request<'a>,
426 entity: PhantomData<E>,
427}
428impl<M: Memory> Database<M> {
429 #[must_use]
431 pub fn query<E: Entity>(&self) -> Query<'_, E, M> {
432 Query {
433 db: self,
434 entity: PhantomData,
435 request: Request::default(),
436 }
437 }
438}
439impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
440 #[must_use]
451 pub fn distinct(mut self) -> Self {
452 self.request.distinct = true;
453 self
454 }
455
456 #[must_use]
466 pub fn filter(
467 mut self,
468 field: &'a str,
469 comparison: Comparison,
470 value: impl Into<IndexValue<'a>>,
471 ) -> Self {
472 self.request
473 .filter(field, comparison, QueryOperand::Literal(value.into()));
474 self
475 }
476
477 #[must_use]
483 pub fn filter_fields(mut self, left: &'a str, comparison: Comparison, right: &'a str) -> Self {
484 self.request
485 .filter(left, comparison, QueryOperand::Field(right));
486 self
487 }
488
489 #[must_use]
493 pub fn filter_length(mut self, field: &'a str, comparison: Comparison, length: u32) -> Self {
494 self.request
495 .filter(field, comparison, QueryOperand::Length(length));
496 self
497 }
498
499 #[must_use]
502 pub fn filter_present(self, field: &'a str) -> Self {
503 self.filter(field, Comparison::Ne, IndexValue::Absent)
504 }
505
506 #[must_use]
509 pub fn filter_absent(self, field: &'a str) -> Self {
510 self.filter(field, Comparison::Eq, IndexValue::Absent)
511 }
512
513 #[must_use]
520 pub fn filter_between(
521 self,
522 field: &'a str,
523 lower: impl Into<IndexValue<'a>>,
524 upper: impl Into<IndexValue<'a>>,
525 ) -> Self {
526 self.filter(field, Comparison::Ge, lower)
527 .filter(field, Comparison::Le, upper)
528 }
529
530 #[must_use]
538 pub fn filter_not_between(
539 self,
540 field: &'a str,
541 lower: impl Into<IndexValue<'a>>,
542 upper: impl Into<IndexValue<'a>>,
543 ) -> Self {
544 self.filter_any(&[
545 (field, Comparison::Lt, lower.into()),
546 (field, Comparison::Gt, upper.into()),
547 ])
548 }
549
550 #[must_use]
555 pub fn filter_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
556 self.filter_fields(field, Comparison::Ge, lower)
557 .filter_fields(field, Comparison::Le, upper)
558 }
559
560 #[must_use]
565 pub fn filter_not_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
566 self.filter_any_operands(&[
567 (field, Comparison::Lt, QueryOperand::Field(lower)),
568 (field, Comparison::Gt, QueryOperand::Field(upper)),
569 ])
570 }
571
572 #[must_use]
579 pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
580 self.request.or_clause(
581 alternatives
582 .iter()
583 .map(|&(field, op, value)| (field, op, QueryOperand::Literal(value))),
584 );
585 self
586 }
587
588 #[must_use]
593 pub fn filter_any_operands(
594 mut self,
595 alternatives: &[(&'a str, Comparison, QueryOperand<'a>)],
596 ) -> Self {
597 self.request.or_clause(alternatives.iter().copied());
598 self
599 }
600
601 #[must_use]
609 pub fn filter_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
610 self.request.or_clause(
611 values
612 .iter()
613 .copied()
614 .map(|value| (field, Comparison::Eq, QueryOperand::Literal(value))),
615 );
616 self
617 }
618
619 #[must_use]
627 pub fn filter_not_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
628 self.request.filter_not_in(field, values);
629 self
630 }
631
632 #[must_use]
637 pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
638 self.request.using_index(name, values);
639 self
640 }
641
642 #[must_use]
652 pub fn order_by(mut self, fields: &[&'a str]) -> Self {
653 self.request.order_by(fields);
654 self
655 }
656
657 #[must_use]
662 pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
663 self.request.order_by_each(fields);
664 self
665 }
666
667 #[must_use]
669 pub fn descending(mut self) -> Self {
670 self.request.descending = true;
671 self
672 }
673
674 #[must_use]
681 pub fn limit(mut self, rows: usize) -> Self {
682 self.request.rows = rows;
683 self
684 }
685
686 #[must_use]
688 pub fn work_limit(mut self, candidates: usize) -> Self {
689 self.request.work = candidates;
690 self
691 }
692
693 #[cfg(feature = "test-support")]
695 #[doc(hidden)]
696 #[must_use]
697 pub fn test_output_limit(mut self, bytes: usize) -> Self {
698 self.request.bytes = bytes;
699 self
700 }
701
702 #[must_use]
704 pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
705 self.request.cursor = Some(cursor);
706 self
707 }
708
709 pub fn fetch(self) -> Result<QueryPage<E>, Error> {
716 fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
717 }
718
719 pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
729 let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
730 raw.decode_projection()
731 }
732}
733
734fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
738 let TypeBody::Record(fields) = &output.body else {
739 return Err(Error::InvalidQuery);
740 };
741 if fields.is_empty()
742 || fields.len() > crate::schema::MAX_FIELDS
743 || fields.windows(2).any(|w| w[0].name >= w[1].name)
744 {
745 return Err(Error::InvalidQuery);
746 }
747 let mut source = TypeGraph::default();
748 let mut target = TypeGraph::default();
749 let mut mask = 0;
750 for field in *fields {
751 let position = entity
752 .fields
753 .iter()
754 .position(|f| f.name == field.name)
755 .ok_or(Error::InvalidQuery)?;
756 let stored = &entity.fields[position];
757 if stored.value != field.value || stored.optional != field.optional {
758 return Err(Error::InvalidQuery);
759 }
760 source
761 .include(stored.value)
762 .map_err(|_| Error::InvalidQuery)?;
763 target
764 .include(field.value)
765 .map_err(|_| Error::InvalidQuery)?;
766 mask |= 1 << position;
767 }
768 if !source.contains(&target) {
769 return Err(Error::InvalidQuery);
770 }
771 Ok(mask)
772}
773
774struct Term {
775 position: usize,
776 comparison: Comparison,
777 operand: TermOperand,
778 or_next: bool,
779}
780
781enum TermOperand {
782 Literal {
783 bytes: Vec<u8>,
784 absent: bool,
785 },
786 Member {
787 item: FieldType,
788 needle: MemberNeedle,
789 },
790 Field(usize),
791 Length(u32),
792}
793
794enum MemberNeedle {
795 Literal(Vec<u8>),
796 Field(usize),
797}
798
799fn member_type(field: FieldType) -> Option<FieldType> {
800 match key::operand_type(field) {
801 FieldType::List { item, .. } => Some(*item),
802 FieldType::Named(link) => match (link.definition)().body {
803 TypeBody::Set { item, .. } => Some(item),
804 _ => None,
805 },
806 _ => None,
807 }
808}
809
810fn contains_member(
812 span: &[u8],
813 optional: bool,
814 item: FieldType,
815 needle: &[u8],
816 scratch: &mut Vec<u8>,
817) -> Result<bool, Error> {
818 let mut reader = Decoder::new(span)?;
819 if optional && !reader.boolean()? {
820 return Ok(false);
821 }
822 for _ in 0..reader.nat32()? {
823 scratch.clear();
824 IndexValue::read(&mut reader, item)?.append_component(false, scratch);
825 if scratch.as_slice() == needle {
826 return Ok(true);
827 }
828 }
829 Ok(false)
830}
831
832fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
833 for (i, field) in entity.fields.iter().enumerate() {
834 if mask & (1 << i) != 0 && !key::supports(field.value) {
835 return Err(Error::InvalidQuery);
836 }
837 }
838 Ok(())
839}
840
841fn comparison_key(
843 entity: &EntitySchema,
844 mask: u16,
845 values: &[IndexValue<'_>],
846) -> Result<Vec<u8>, Error> {
847 let mut key = Vec::new();
848 for (i, field) in entity.fields.iter().enumerate() {
849 if mask & (1 << i) != 0 {
850 values[i].append_component(field.optional, &mut key);
851 if key.len() > MAX_COMPARISON_KEY {
852 return Err(Error::Limit);
853 }
854 }
855 }
856 Ok(key)
857}
858
859fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
860 if size > limit {
861 return Err(Error::RowTooLarge);
862 }
863 if size > limit - *used {
864 return Err(Error::Limit);
865 }
866 *used += size;
867 Ok(())
868}
869
870fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
872 spans
873 .iter()
874 .enumerate()
875 .filter(|(i, _)| mask & (1 << i) != 0)
876 .map(|(_, (start, end))| usize::from(end - start))
877 .sum()
878}
879
880fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
881 let mut output = Vec::with_capacity(size);
882 for (i, &(start, end)) in spans.iter().enumerate() {
883 if mask & (1 << i) != 0 {
884 output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
885 }
886 }
887 output
888}
889struct Plan<'a> {
890 primary: usize,
891 index: Option<&'a IndexSchema>,
892 prefix: Vec<u8>,
893 fixed_components: usize,
894 terms: Vec<Term>,
895 selected: u16,
896 span_fields: u16,
898 binding: [u8; 32],
899 projection: Option<u16>,
900 distinct: distinct::Strategy,
901 sort: Option<Vec<(usize, bool)>>,
902 descending: bool,
903}
904impl<'a> Plan<'a> {
905 fn use_index(&mut self, entity: &EntitySchema, path: order::IndexPath<'a>) {
906 self.index = Some(path.index);
907 self.prefix = path.prefix;
908 self.fixed_components = path.fixed;
909 self.selected |= entity.key_fields();
910 }
911
912 fn admit(
913 entity: &'a EntitySchema,
914 request: &Request<'_>,
915 schema: [u8; 32],
916 incarnation: [u8; 16],
917 projection: Option<&TypeSchema>,
918 group_output: bool,
919 ) -> Result<Self, Error> {
920 if request.over_limit
921 || !(1..=32).contains(&request.rows)
922 || !(1..=MAX_WORK).contains(&request.work)
923 || !(1..=MAX_OUTPUT).contains(&request.bytes)
924 {
925 return Err(Error::Limit);
926 }
927 if !group_output && !request.groups.is_empty() {
928 return Err(Error::InvalidQuery);
929 }
930 for value in request
932 .predicates
933 .iter()
934 .filter_map(|p| match &p.operand {
935 QueryOperand::Literal(value) => Some(value),
936 QueryOperand::Field(_) | QueryOperand::Length(_) => None,
937 })
938 .chain(request.index.iter().flat_map(|(_, values)| values.iter()))
939 {
940 if match value {
941 IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
942 IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
943 _ => false,
944 } {
945 return Err(Error::Limit);
946 }
947 }
948 let primary = entity
949 .fields
950 .iter()
951 .position(|f| f.name == entity.primary_key && !f.optional)
952 .ok_or(Error::InvalidQuery)?;
953 let mut plan = Self {
954 primary,
955 index: None,
956 prefix: prefix(2, entity.id),
957 fixed_components: 0,
958 terms: Vec::new(),
959 selected: 1 << primary,
960 span_fields: 0,
961 binding: [0; 32],
962 projection: projection
963 .map(|output| admit_projection(entity, output))
964 .transpose()?,
965 distinct: distinct::Strategy::Identity,
966 sort: None,
967 descending: request.descending ^ request.primary_descending(entity),
968 };
969 for predicate in &request.predicates {
970 let position = entity
971 .fields
972 .iter()
973 .position(|f| f.name == predicate.field)
974 .ok_or(Error::InvalidQuery)?;
975 let field = &entity.fields[position];
976 let member = if predicate.comparison == Comparison::Contains {
977 member_type(field.value)
978 } else {
979 None
980 };
981 let operand = match predicate.operand {
982 QueryOperand::Length(length) => {
983 let supported = match key::operand_type(field.value) {
984 FieldType::Text { .. }
985 | FieldType::Blob { .. }
986 | FieldType::List { .. } => true,
987 FieldType::Named(link) => matches!(
988 (link.definition)().body,
989 TypeBody::Map { .. } | TypeBody::Set { .. }
990 ),
991 _ => false,
992 };
993 if !supported || !predicate.comparison.is_relational() {
994 return Err(Error::InvalidQuery);
995 }
996 plan.span_fields |= 1 << position;
997 TermOperand::Length(length)
998 }
999 QueryOperand::Field(name) => {
1000 let right = entity
1001 .fields
1002 .iter()
1003 .position(|f| f.name == name)
1004 .ok_or(Error::InvalidQuery)?;
1005 let right_type = entity.fields[right].value;
1006 let left_type = member.unwrap_or(field.value);
1007 let compatible = left_type == right_type
1008 || matches!(
1009 (left_type, right_type),
1010 (FieldType::Text { .. }, FieldType::Text { .. })
1011 | (FieldType::Blob { .. }, FieldType::Blob { .. })
1012 );
1013 if !compatible
1014 || !key::supports(left_type)
1015 || (member.is_none() && !predicate.comparison.supports_scalar(left_type))
1016 {
1017 return Err(Error::InvalidQuery);
1018 }
1019 plan.selected |= 1 << right;
1020 if let Some(item) = member {
1021 plan.span_fields |= 1 << position;
1022 TermOperand::Member {
1023 item,
1024 needle: MemberNeedle::Field(right),
1025 }
1026 } else {
1027 plan.selected |= 1 << position;
1028 TermOperand::Field(right)
1029 }
1030 }
1031 QueryOperand::Literal(value) => {
1032 if let Some(item) = member {
1033 if !key::supports(item) {
1034 return Err(Error::InvalidQuery);
1035 }
1036 value.admit(item, false)?;
1037 let mut bytes = Vec::new();
1038 value.append_component(false, &mut bytes);
1039 plan.span_fields |= 1 << position;
1040 TermOperand::Member {
1041 item,
1042 needle: MemberNeedle::Literal(bytes),
1043 }
1044 } else {
1045 let absent = value == IndexValue::Absent;
1046 if key::supports(field.value) {
1047 plan.selected |= 1 << position;
1048 } else if absent
1049 && matches!(predicate.comparison, Comparison::Eq | Comparison::Ne)
1050 {
1051 plan.span_fields |= 1 << position;
1052 } else {
1053 return Err(Error::InvalidQuery);
1054 }
1055 predicate
1056 .comparison
1057 .admit(field.value, field.optional, value)?;
1058 let mut bytes = Vec::new();
1059 value.append_component(field.optional, &mut bytes);
1060 TermOperand::Literal { bytes, absent }
1061 }
1062 }
1063 };
1064 plan.terms.push(Term {
1065 position,
1066 comparison: predicate.comparison,
1067 operand,
1068 or_next: predicate.or_next,
1069 });
1070 }
1071 match order::select(entity, request)? {
1074 order::Path::Primary => {}
1075 order::Path::Index(path) => plan.use_index(entity, path),
1076 order::Path::Sort(fields) => {
1077 for &(position, _) in &fields {
1078 plan.selected |= 1 << position;
1079 }
1080 plan.sort = Some(fields);
1081 }
1082 }
1083 if request.distinct {
1084 plan.distinct = distinct::admit(
1085 entity,
1086 request,
1087 plan.projection,
1088 plan.index,
1089 plan.fixed_components,
1090 plan.sort.is_some(),
1091 )?;
1092 if plan.distinct == distinct::Strategy::Complete {
1093 plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
1094 }
1095 }
1096 let mut hash = Sha256::new();
1097 hash.update(b"ic-db:query:v1\0");
1098 hash.update(schema);
1099 hash.update(incarnation);
1100 hash.update([u8::from(request.descending)]);
1101 hash.update((plan.prefix.len() as u32).to_le_bytes());
1102 hash.update(&plan.prefix);
1103 for term in &plan.terms {
1104 hash.update([term.position as u8, term.comparison as u8]);
1105 match &term.operand {
1106 TermOperand::Literal { bytes, .. }
1107 | TermOperand::Member {
1108 needle: MemberNeedle::Literal(bytes),
1109 ..
1110 } => {
1111 hash.update((bytes.len() as u32).to_le_bytes());
1112 hash.update(bytes);
1113 }
1114 TermOperand::Length(length) => {
1115 hash.update((u32::MAX - 1).to_le_bytes());
1116 hash.update(length.to_le_bytes());
1117 }
1118 TermOperand::Field(right)
1119 | TermOperand::Member {
1120 needle: MemberNeedle::Field(right),
1121 ..
1122 } => {
1123 hash.update(u32::MAX.to_le_bytes());
1125 hash.update([*right as u8]);
1126 }
1127 }
1128 }
1129 let clauses = plan
1132 .terms
1133 .iter()
1134 .enumerate()
1135 .fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
1136 if clauses != 0 {
1137 hash.update(b"or-clauses\0");
1138 hash.update([clauses]);
1139 }
1140 if let Some(order) = &request.order {
1141 hash.update(b"order\0");
1142 hash.update([order.len() as u8]);
1143 for name in order {
1144 hash.update([entity
1146 .fields
1147 .iter()
1148 .position(|f| f.name == *name)
1149 .ok_or(Error::InvalidQuery)? as u8]);
1150 }
1151 }
1152 if request.order_descending != 0 {
1153 hash.update(b"order-directions\0");
1154 hash.update([request.order_descending]);
1155 }
1156 if let Some(mask) = plan.projection {
1159 hash.update(b"projection\0");
1160 hash.update(mask.to_le_bytes());
1161 }
1162 if request.distinct {
1163 hash.update(b"distinct\0");
1164 }
1165 plan.binding = hash.finalize().into();
1166 if let Some(cursor) = request.cursor {
1167 if cursor.binding != plan.binding {
1168 return Err(Error::InvalidCursor);
1169 }
1170 plan.validate_position(entity, &cursor.position)
1171 .map_err(|_| Error::InvalidCursor)?;
1172 }
1173 Ok(plan)
1174 }
1175
1176 fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
1177 if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
1178 return Err(Error::InvalidCursor);
1179 }
1180 if let Some(index) = self.index {
1181 let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
1182 for name in index.fields {
1183 consume_index_component(entity, index, name, &mut remaining)?;
1184 }
1185 if !index.unique {
1186 key::consume(&mut remaining, entity.key_type()?)?;
1187 }
1188 if !remaining.is_empty() {
1189 return Err(Error::InvalidCursor);
1190 }
1191 } else {
1192 RowKey::decode(
1193 bytes.get(5..).ok_or(Error::InvalidCursor)?,
1194 entity.key_type()?,
1195 )?;
1196 }
1197 Ok(())
1198 }
1199
1200 fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
1201 QueryCursor {
1202 binding: self.binding,
1203 position: position.to_vec(),
1204 inclusive,
1205 }
1206 }
1207}
1208
1209fn consume_index_component(
1211 entity: &EntitySchema,
1212 index: &IndexSchema,
1213 name: &str,
1214 remaining: &mut &[u8],
1215) -> Result<(), Error> {
1216 let field = entity
1217 .fields
1218 .iter()
1219 .find(|f| f.name == name)
1220 .ok_or(Error::InvalidQuery)?;
1221 if field.optional {
1222 let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
1223 *remaining = rest;
1224 match presence {
1225 0 if !index.present_only => return Ok(()),
1226 1 => {}
1227 _ => return Err(Error::InvalidCursor),
1228 }
1229 }
1230 key::consume(remaining, field.value)
1231}
1232
1233#[inline(never)]
1236#[expect(
1237 clippy::needless_pass_by_value,
1238 reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
1239)]
1240fn fetch_rows<M: Memory>(
1241 db: &Database<M>,
1242 entity: &EntitySchema,
1243 request: Request<'_>,
1244 projection: Option<&TypeSchema>,
1245) -> Result<QueryPage<Vec<u8>>, Error> {
1246 db.schema.admits(entity)?;
1247 let plan = Plan::admit(
1248 entity,
1249 &request,
1250 db.schema.fingerprint(),
1251 db.incarnation,
1252 projection,
1253 false,
1254 )?;
1255 execute(&db.map, entity, &request, &plan, None)
1256}
1257
1258fn execute<M: Memory>(
1259 map: &Map<M>,
1260 entity: &EntitySchema,
1261 request: &Request<'_>,
1262 plan: &Plan<'_>,
1263 mut aggregate: Option<aggregate::Accumulator<'_>>,
1264) -> Result<QueryPage<Vec<u8>>, Error> {
1265 execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
1266}
1267
1268const STEP_INPUT_BYTES: usize = 64 * 1024;
1271const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
1272
1273fn execute_inner<M: Memory>(
1274 map: &Map<M>,
1275 entity: &EntitySchema,
1276 request: &Request<'_>,
1277 plan: &Plan<'_>,
1278 mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
1279 mut input_bytes: Option<&mut usize>,
1280) -> Result<QueryPage<Vec<u8>>, Error> {
1281 let mut page = QueryPage {
1282 rows: Vec::new(),
1283 next: None,
1284 examined: 0,
1285 fetched: 0,
1286 output_bytes: 0,
1287 };
1288 let Some(bounds) = range::bounds(entity, request, plan)? else {
1289 return Ok(page);
1290 };
1291 let terminal = range::terminal_key(&bounds, plan.descending);
1292 let mut entries = map.range((bounds.0.as_ref(), bounds.1.as_ref()));
1293 let mut collected = if plan.distinct == distinct::Strategy::Complete {
1294 Some(distinct::Collection::new(
1295 plan.projection.ok_or(Error::InvalidQuery)?,
1296 ))
1297 } else {
1298 None
1299 };
1300 let mut sorted = plan
1301 .sort
1302 .as_ref()
1303 .map(|_| sort::Collection::new(request, plan.distinct));
1304 let mut component = Vec::new();
1305 let mut right_component = Vec::new();
1306 let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
1309 distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
1310 } else {
1311 None
1312 };
1313 let primary_type = entity.fields[plan.primary].value;
1314 while let Some(entry) = if plan.descending {
1315 entries.next_back()
1316 } else {
1317 entries.next()
1318 } {
1319 if request.work == 0 {
1323 return Err(Error::Limit);
1324 }
1325 page.examined += 1;
1326 let stored_key = entry.key();
1327 let mut read_bytes = stored_key.len();
1328 let (owner, bytes) = if plan.index.is_some() {
1329 let owner_bytes = entry.value();
1330 read_bytes += owner_bytes.len();
1331 let owner = RowKey::decode(&owner_bytes, primary_type)?;
1332 let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
1333 (owner, bytes)
1334 } else {
1335 (
1336 RowKey::decode(&stored_key[5..], primary_type)?,
1337 entry.value(),
1338 )
1339 };
1340 if let Some(used) = input_bytes.as_deref_mut() {
1341 read_bytes += bytes.len();
1342 if read_bytes > CANDIDATE_BYTES {
1343 return Err(Error::Corrupt);
1344 }
1345 *used += read_bytes;
1346 }
1347 page.fetched += 1;
1348 let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
1349 let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
1350 entity.inspect_fields(
1351 &bytes,
1352 plan.selected,
1353 &mut values,
1354 (plan.span_fields != 0
1355 || plan.projection.is_some()
1356 || aggregate.as_ref().is_some_and(|a| a.needs_spans()))
1357 .then_some(&mut spans),
1358 )?;
1359 if RowKey::from_index(values[plan.primary])? != owner {
1360 return Err(Error::Corrupt);
1361 }
1362 if plan.index.is_some() {
1363 validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
1364 }
1365 let mut accepts = |term: &Term| -> Result<bool, Error> {
1366 let value = values[term.position];
1367 component.clear();
1368 let (operand, optional) = match &term.operand {
1369 TermOperand::Literal { absent: true, .. }
1370 if plan.span_fields & (1 << term.position) != 0 =>
1371 {
1372 let absent = bytes[usize::from(spans[term.position].0)] == 0;
1373 return Ok(term.comparison.accepts_absent(absent));
1374 }
1375 TermOperand::Member { item, needle } => {
1376 let needle = match needle {
1377 MemberNeedle::Literal(bytes) => bytes.as_slice(),
1378 MemberNeedle::Field(right) => {
1379 let value = values[*right];
1380 if value == IndexValue::Absent {
1381 return Ok(false);
1382 }
1383 right_component.clear();
1384 value.append_component(false, &mut right_component);
1385 &right_component
1386 }
1387 };
1388 let (start, end) = spans[term.position];
1389 return contains_member(
1390 &bytes[usize::from(start)..usize::from(end)],
1391 entity.fields[term.position].optional,
1392 *item,
1393 needle,
1394 &mut component,
1395 );
1396 }
1397 TermOperand::Length(length) => {
1398 let (start, end) = spans[term.position];
1399 let span = &bytes[usize::from(start)..usize::from(end)];
1400 let actual =
1401 crate::codec::validated_length(span, entity.fields[term.position].optional)
1402 .map(u32::to_be_bytes);
1403 return Ok(term.comparison.accepts(
1404 actual.as_ref().map(|v| v.as_slice()),
1405 Some(&length.to_be_bytes()),
1406 false,
1407 ));
1408 }
1409 TermOperand::Literal { bytes, absent } => (
1410 (!absent).then_some(bytes.as_slice()),
1411 entity.fields[term.position].optional,
1412 ),
1413 TermOperand::Field(right) => {
1414 let rhs = values[*right];
1415 right_component.clear();
1416 rhs.append_component(false, &mut right_component);
1417 (
1418 (rhs != IndexValue::Absent).then_some(right_component.as_slice()),
1419 false,
1420 )
1421 }
1422 };
1423 value.append_component(optional, &mut component);
1424 Ok(term.comparison.accepts(
1425 (value != IndexValue::Absent).then_some(component.as_slice()),
1426 operand,
1427 optional,
1428 ))
1429 };
1430 let matches = 'matches: {
1431 'clause: for clause in plan.terms.split_inclusive(|term| !term.or_next) {
1432 for term in clause {
1433 if accepts(term)? {
1434 continue 'clause;
1435 }
1436 }
1437 break 'matches false;
1438 }
1439 true
1440 };
1441 let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
1442 let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
1443 if matches && let Some(accumulator) = aggregate.as_mut() {
1444 accumulator.push(entity, &values, &bytes, &spans)?;
1445 if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
1446 return Ok(page);
1448 }
1449 } else if matches && let Some(collection) = collected.as_mut() {
1450 collection.push(entity, request, &values, &bytes, &spans)?;
1451 } else if matches && let Some(collection) = sorted.as_mut() {
1452 collection.push(entity, plan, &values, &bytes, &spans)?;
1453 } else if matches && !duplicate {
1454 let size = plan
1455 .projection
1456 .map_or(bytes.len(), |mask| projection_size(&spans, mask));
1457 if size > request.bytes {
1458 return Err(Error::RowTooLarge);
1459 }
1460 if size > request.bytes - page.output_bytes {
1461 page.next = Some(plan.cursor(stored_key, true));
1462 return Ok(page);
1463 }
1464 page.output_bytes += size;
1465 if let Some(mask) = plan.projection {
1466 page.rows.push(copy_projection(&bytes, &spans, mask, size));
1467 } else {
1468 page.rows.push(bytes);
1469 }
1470 if let Some(boundary) = boundary {
1471 previous = Some(boundary.to_vec());
1472 }
1473 }
1474 if page.rows.len() == request.rows
1475 || page.examined == request.work
1476 || input_bytes
1477 .as_deref()
1478 .is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
1479 {
1480 if terminal == Some(stored_key) {
1481 break;
1482 }
1483 if (aggregate.is_some() && input_bytes.is_none())
1484 || collected.is_some()
1485 || sorted.is_some()
1486 {
1487 return Err(Error::Limit);
1490 }
1491 page.next = Some(plan.cursor(stored_key, false));
1492 return Ok(page);
1493 }
1494 }
1495 if let Some(collection) = collected {
1496 page.output_bytes = collection.output_bytes;
1497 page.rows = collection.rows;
1498 }
1499 if let Some(collection) = sorted {
1500 collection.finish(request.bytes, &mut page)?;
1501 }
1502 Ok(page)
1503}