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