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(
347 &mut self,
348 field: &'a str,
349 values: impl ExactSizeIterator<Item = IndexValue<'a>>,
350 ) {
351 if values.len() == 0 || values.len() > MAX_TERMS - self.predicates.len() {
352 self.over_limit = true;
353 return;
354 }
355 for value in values {
356 self.filter(field, Comparison::Ne, QueryOperand::Literal(value));
357 }
358 }
359
360 #[inline(never)]
361 fn using_index(&mut self, name: &'a str, values: &[IndexValue<'a>]) {
362 if values.len() > 4 {
363 self.over_limit = true;
364 } else {
365 self.index = Some((name, values.to_vec()));
366 }
367 }
368
369 #[inline(never)]
370 fn order_by(&mut self, fields: &[&'a str]) {
371 self.order_descending = 0;
372 if fields.len() > 4 {
373 self.over_limit = true;
374 } else {
375 self.order = Some(fields.to_vec());
376 }
377 }
378
379 #[inline(never)]
380 fn order_by_each(&mut self, fields: &[(&'a str, SortDirection)]) {
381 if fields.len() > 4 {
382 self.over_limit = true;
383 return;
384 }
385 self.order = Some(Vec::with_capacity(fields.len()));
386 self.order_descending = 0;
387 for &(field, direction) in fields {
388 self.append_order(field, direction);
389 }
390 }
391
392 fn append_order(&mut self, field: &'a str, direction: SortDirection) {
393 let fields = self.order.get_or_insert_with(Vec::new);
394 if fields.len() == 4 {
395 self.over_limit = true;
396 return;
397 }
398 if direction == SortDirection::Descending {
399 self.order_descending |= 1 << fields.len();
400 }
401 fields.push(field);
402 }
403
404 fn primary_descending(&self, entity: &EntitySchema) -> bool {
405 self.order_descending != 0
406 && self.order.as_ref().is_some_and(|fields| {
407 fields.last() == Some(&entity.primary_key)
408 && self.order_descending & (1 << (fields.len() - 1)) != 0
409 })
410 }
411}
412
413pub(super) fn source_page<M: Memory>(
415 map: &Map<M>,
416 entity: &EntitySchema,
417 binding: [u8; 32],
418 incarnation: [u8; 16],
419 cursor: Option<&QueryCursor>,
420 rows: usize,
421 bytes: usize,
422) -> Result<QueryPage<Vec<u8>>, Error> {
423 let request = Request {
424 rows,
425 work: rows,
426 bytes,
427 cursor,
428 ..Request::default()
429 };
430 let plan = Plan::admit(
431 entity,
432 &request,
433 binding,
434 incarnation,
435 None,
436 PlanOutput::Rows,
437 )?;
438 execute(map, entity, &request, &plan, None)
439}
440
441pub struct Query<'a, E, M: Memory> {
445 db: &'a Database<M>,
446 request: Request<'a>,
447 entity: PhantomData<E>,
448}
449impl<M: Memory> Database<M> {
450 #[must_use]
452 pub fn query<E: Entity>(&self) -> Query<'_, E, M> {
453 Query {
454 db: self,
455 entity: PhantomData,
456 request: Request::default(),
457 }
458 }
459}
460impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
461 #[must_use]
472 pub fn distinct(mut self) -> Self {
473 self.request.distinct = true;
474 self
475 }
476
477 #[must_use]
487 pub fn filter(
488 mut self,
489 field: &'a str,
490 comparison: Comparison,
491 value: impl Into<IndexValue<'a>>,
492 ) -> Self {
493 self.request
494 .filter(field, comparison, QueryOperand::Literal(value.into()));
495 self
496 }
497
498 #[must_use]
500 pub fn eq(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
501 self.filter(field, Comparison::Eq, value)
502 }
503
504 #[must_use]
506 pub fn ne(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
507 self.filter(field, Comparison::Ne, value)
508 }
509
510 #[must_use]
512 pub fn lt(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
513 self.filter(field, Comparison::Lt, value)
514 }
515
516 #[must_use]
518 pub fn lte(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
519 self.filter(field, Comparison::Le, value)
520 }
521
522 #[must_use]
524 pub fn gt(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
525 self.filter(field, Comparison::Gt, value)
526 }
527
528 #[must_use]
530 pub fn gte(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
531 self.filter(field, Comparison::Ge, value)
532 }
533
534 #[must_use]
540 pub fn filter_fields(mut self, left: &'a str, comparison: Comparison, right: &'a str) -> Self {
541 self.request
542 .filter(left, comparison, QueryOperand::Field(right));
543 self
544 }
545
546 #[must_use]
550 pub fn filter_length(mut self, field: &'a str, comparison: Comparison, length: u32) -> Self {
551 self.request
552 .filter(field, comparison, QueryOperand::Length(length));
553 self
554 }
555
556 #[must_use]
559 pub fn filter_present(self, field: &'a str) -> Self {
560 self.filter(field, Comparison::Ne, IndexValue::Absent)
561 }
562
563 #[must_use]
566 pub fn filter_absent(self, field: &'a str) -> Self {
567 self.filter(field, Comparison::Eq, IndexValue::Absent)
568 }
569
570 #[must_use]
577 pub fn filter_between(
578 self,
579 field: &'a str,
580 lower: impl Into<IndexValue<'a>>,
581 upper: impl Into<IndexValue<'a>>,
582 ) -> Self {
583 self.filter(field, Comparison::Ge, lower)
584 .filter(field, Comparison::Le, upper)
585 }
586
587 #[must_use]
595 pub fn filter_not_between(
596 self,
597 field: &'a str,
598 lower: impl Into<IndexValue<'a>>,
599 upper: impl Into<IndexValue<'a>>,
600 ) -> Self {
601 self.filter_any(&[
602 (field, Comparison::Lt, lower.into()),
603 (field, Comparison::Gt, upper.into()),
604 ])
605 }
606
607 #[must_use]
612 pub fn filter_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
613 self.filter_fields(field, Comparison::Ge, lower)
614 .filter_fields(field, Comparison::Le, upper)
615 }
616
617 #[must_use]
622 pub fn filter_not_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
623 self.filter_any_operands(&[
624 (field, Comparison::Lt, QueryOperand::Field(lower)),
625 (field, Comparison::Gt, QueryOperand::Field(upper)),
626 ])
627 }
628
629 #[must_use]
636 pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
637 self.request.or_clause(
638 alternatives
639 .iter()
640 .map(|&(field, op, value)| (field, op, QueryOperand::Literal(value))),
641 );
642 self
643 }
644
645 #[must_use]
650 pub fn filter_any_operands(
651 mut self,
652 alternatives: &[(&'a str, Comparison, QueryOperand<'a>)],
653 ) -> Self {
654 self.request.or_clause(alternatives.iter().copied());
655 self
656 }
657
658 #[must_use]
668 pub fn filter_in(
669 mut self,
670 field: &'a str,
671 values: &[impl Copy + Into<IndexValue<'a>>],
672 ) -> Self {
673 self.request.or_clause(
674 values
675 .iter()
676 .copied()
677 .map(|value| (field, Comparison::Eq, QueryOperand::Literal(value.into()))),
678 );
679 self
680 }
681
682 #[must_use]
690 pub fn filter_not_in(
691 mut self,
692 field: &'a str,
693 values: &[impl Copy + Into<IndexValue<'a>>],
694 ) -> Self {
695 self.request
696 .filter_not_in(field, values.iter().copied().map(Into::into));
697 self
698 }
699
700 #[must_use]
705 pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
706 self.request.using_index(name, values);
707 self
708 }
709
710 #[must_use]
713 pub fn order_asc(mut self, field: &'a str) -> Self {
714 self.request.append_order(field, SortDirection::Ascending);
715 self
716 }
717
718 #[must_use]
721 pub fn order_desc(mut self, field: &'a str) -> Self {
722 self.request.append_order(field, SortDirection::Descending);
723 self
724 }
725
726 #[must_use]
736 pub fn order_by(mut self, fields: &[&'a str]) -> Self {
737 self.request.order_by(fields);
738 self
739 }
740
741 #[must_use]
746 pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
747 self.request.order_by_each(fields);
748 self
749 }
750
751 #[must_use]
753 pub fn descending(mut self) -> Self {
754 self.request.descending = true;
755 self
756 }
757
758 #[must_use]
765 pub fn limit(mut self, rows: usize) -> Self {
766 self.request.rows = rows;
767 self
768 }
769
770 #[must_use]
772 pub fn work_limit(mut self, candidates: usize) -> Self {
773 self.request.work = candidates;
774 self
775 }
776
777 #[cfg(feature = "test-support")]
779 #[doc(hidden)]
780 #[must_use]
781 pub fn test_output_limit(mut self, bytes: usize) -> Self {
782 self.request.bytes = bytes;
783 self
784 }
785
786 #[must_use]
788 pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
789 self.request.cursor = Some(cursor);
790 self
791 }
792
793 pub fn fetch(self) -> Result<QueryPage<E>, Error> {
800 fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
801 }
802
803 pub fn first(self) -> Result<Option<E>, Error> {
809 let mut page = self.probe_matches(1)?;
810 match page.rows.pop() {
811 None if page.next.is_some() => Err(Error::Limit),
812 result => Ok(result),
813 }
814 }
815
816 pub fn try_one(self) -> Result<Option<E>, Error> {
823 if self.request.cursor.is_some() {
824 return Err(Error::InvalidQuery);
825 }
826 let mut page = self.probe_matches(2)?;
827 if page.rows.len() == 2 {
828 return Err(Error::MultipleMatches);
829 }
830 if page.next.is_some() {
831 return Err(Error::Limit);
832 }
833 Ok(page.rows.pop())
834 }
835
836 fn probe_matches(self, rows: usize) -> Result<QueryPage<E>, Error> {
837 if !(1..=32).contains(&self.request.rows) {
838 return Err(Error::Limit);
839 }
840 self.limit(rows).fetch()
841 }
842
843 pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
853 let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
854 raw.decode_projection()
855 }
856}
857
858fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
862 let TypeBody::Record(fields) = &output.body else {
863 return Err(Error::InvalidQuery);
864 };
865 if fields.is_empty()
866 || fields.len() > crate::schema::MAX_FIELDS
867 || fields.windows(2).any(|w| w[0].name >= w[1].name)
868 {
869 return Err(Error::InvalidQuery);
870 }
871 let mut source = TypeGraph::default();
872 let mut target = TypeGraph::default();
873 let mut mask = 0;
874 for field in *fields {
875 let position = entity
876 .fields
877 .iter()
878 .position(|f| f.name == field.name)
879 .ok_or(Error::InvalidQuery)?;
880 let stored = &entity.fields[position];
881 if stored.value != field.value || stored.optional != field.optional {
882 return Err(Error::InvalidQuery);
883 }
884 source
885 .include(stored.value)
886 .map_err(|_| Error::InvalidQuery)?;
887 target
888 .include(field.value)
889 .map_err(|_| Error::InvalidQuery)?;
890 mask |= 1 << position;
891 }
892 if !source.contains(&target) {
893 return Err(Error::InvalidQuery);
894 }
895 Ok(mask)
896}
897
898struct Term {
899 position: usize,
900 comparison: Comparison,
901 operand: TermOperand,
902 or_next: bool,
903}
904
905enum TermOperand {
906 Literal {
907 bytes: Vec<u8>,
908 absent: bool,
909 },
910 Member {
911 item: FieldType,
912 needle: MemberNeedle,
913 },
914 Field(usize),
915 Length(u32),
916}
917
918enum MemberNeedle {
919 Literal(Vec<u8>),
920 Field(usize),
921}
922
923fn member_type(field: FieldType) -> Option<FieldType> {
924 match key::operand_type(field) {
925 FieldType::List { item, .. } => Some(*item),
926 FieldType::Named(link) => match (link.definition)().body {
927 TypeBody::Set { item, .. } => Some(item),
928 _ => None,
929 },
930 _ => None,
931 }
932}
933
934fn contains_member(
936 span: &[u8],
937 optional: bool,
938 item: FieldType,
939 needle: &[u8],
940 scratch: &mut Vec<u8>,
941) -> Result<bool, Error> {
942 let mut reader = Decoder::new(span)?;
943 if optional && !reader.boolean()? {
944 return Ok(false);
945 }
946 for _ in 0..reader.nat32()? {
947 scratch.clear();
948 IndexValue::read(&mut reader, item)?.append_component(false, scratch);
949 if scratch.as_slice() == needle {
950 return Ok(true);
951 }
952 }
953 Ok(false)
954}
955
956fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
957 for (i, field) in entity.fields.iter().enumerate() {
958 if mask & (1 << i) != 0 && !key::supports(field.value) {
959 return Err(Error::InvalidQuery);
960 }
961 }
962 Ok(())
963}
964
965fn comparison_key(
967 entity: &EntitySchema,
968 mask: u16,
969 values: &[IndexValue<'_>],
970) -> Result<Vec<u8>, Error> {
971 let mut key = Vec::new();
972 for (i, field) in entity.fields.iter().enumerate() {
973 if mask & (1 << i) != 0 {
974 values[i].append_component(field.optional, &mut key);
975 if key.len() > MAX_COMPARISON_KEY {
976 return Err(Error::Limit);
977 }
978 }
979 }
980 Ok(key)
981}
982
983fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
984 if size > limit {
985 return Err(Error::RowTooLarge);
986 }
987 if size > limit - *used {
988 return Err(Error::Limit);
989 }
990 *used += size;
991 Ok(())
992}
993
994fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
996 spans
997 .iter()
998 .enumerate()
999 .filter(|(i, _)| mask & (1 << i) != 0)
1000 .map(|(_, (start, end))| usize::from(end - start))
1001 .sum()
1002}
1003
1004fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
1005 let mut output = Vec::with_capacity(size);
1006 for (i, &(start, end)) in spans.iter().enumerate() {
1007 if mask & (1 << i) != 0 {
1008 output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
1009 }
1010 }
1011 output
1012}
1013#[derive(Clone, Copy)]
1014enum PlanOutput {
1015 Rows,
1016 Aggregate { grouped: bool },
1017}
1018
1019struct Plan<'a> {
1020 primary: usize,
1021 index: Option<&'a IndexSchema>,
1022 prefix: Vec<u8>,
1023 fixed_components: usize,
1024 terms: Vec<Term>,
1025 selected: u16,
1026 span_fields: u16,
1028 binding: [u8; 32],
1029 projection: Option<u16>,
1030 distinct: distinct::Strategy,
1031 sort: Option<Vec<(usize, bool)>>,
1032 descending: bool,
1033}
1034impl<'a> Plan<'a> {
1035 fn use_index(&mut self, entity: &EntitySchema, path: order::IndexPath<'a>) {
1036 self.index = Some(path.index);
1037 self.prefix = path.prefix;
1038 self.fixed_components = path.fixed;
1039 self.selected |= entity.key_fields();
1040 }
1041
1042 fn admit(
1043 entity: &'a EntitySchema,
1044 request: &Request<'_>,
1045 schema: [u8; 32],
1046 incarnation: [u8; 16],
1047 projection: Option<&TypeSchema>,
1048 output: PlanOutput,
1049 ) -> Result<Self, Error> {
1050 if request.over_limit
1051 || !(1..=32).contains(&request.rows)
1052 || !(1..=MAX_WORK).contains(&request.work)
1053 || !(1..=MAX_OUTPUT).contains(&request.bytes)
1054 {
1055 return Err(Error::Limit);
1056 }
1057 if !matches!(output, PlanOutput::Aggregate { grouped: true }) && !request.groups.is_empty()
1058 {
1059 return Err(Error::InvalidQuery);
1060 }
1061 for value in request
1063 .predicates
1064 .iter()
1065 .filter_map(|p| match &p.operand {
1066 QueryOperand::Literal(value) => Some(value),
1067 QueryOperand::Field(_) | QueryOperand::Length(_) => None,
1068 })
1069 .chain(request.index.iter().flat_map(|(_, values)| values.iter()))
1070 {
1071 if match value {
1072 IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
1073 IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
1074 _ => false,
1075 } {
1076 return Err(Error::Limit);
1077 }
1078 }
1079 let primary = entity
1080 .fields
1081 .iter()
1082 .position(|f| f.name == entity.primary_key && !f.optional)
1083 .ok_or(Error::InvalidQuery)?;
1084 let mut plan = Self {
1085 primary,
1086 index: None,
1087 prefix: prefix(2, entity.id),
1088 fixed_components: 0,
1089 terms: Vec::new(),
1090 selected: 1 << primary,
1091 span_fields: 0,
1092 binding: [0; 32],
1093 projection: projection
1094 .map(|output| admit_projection(entity, output))
1095 .transpose()?,
1096 distinct: distinct::Strategy::Identity,
1097 sort: None,
1098 descending: request.descending ^ request.primary_descending(entity),
1099 };
1100 for predicate in &request.predicates {
1101 let position = entity
1102 .fields
1103 .iter()
1104 .position(|f| f.name == predicate.field)
1105 .ok_or(Error::InvalidQuery)?;
1106 let field = &entity.fields[position];
1107 let member = if predicate.comparison == Comparison::Contains {
1108 member_type(field.value)
1109 } else {
1110 None
1111 };
1112 let operand = match predicate.operand {
1113 QueryOperand::Length(length) => {
1114 let supported = match key::operand_type(field.value) {
1115 FieldType::Text { .. }
1116 | FieldType::Blob { .. }
1117 | FieldType::List { .. } => true,
1118 FieldType::Named(link) => matches!(
1119 (link.definition)().body,
1120 TypeBody::Map { .. } | TypeBody::Set { .. }
1121 ),
1122 _ => false,
1123 };
1124 if !supported || !predicate.comparison.is_relational() {
1125 return Err(Error::InvalidQuery);
1126 }
1127 plan.span_fields |= 1 << position;
1128 TermOperand::Length(length)
1129 }
1130 QueryOperand::Field(name) => {
1131 let right = entity
1132 .fields
1133 .iter()
1134 .position(|f| f.name == name)
1135 .ok_or(Error::InvalidQuery)?;
1136 let right_type = entity.fields[right].value;
1137 let left_type = member.unwrap_or(field.value);
1138 let compatible = left_type == right_type
1139 || matches!(
1140 (left_type, right_type),
1141 (FieldType::Text { .. }, FieldType::Text { .. })
1142 | (FieldType::Blob { .. }, FieldType::Blob { .. })
1143 );
1144 if !compatible
1145 || !key::supports(left_type)
1146 || (member.is_none() && !predicate.comparison.supports_scalar(left_type))
1147 {
1148 return Err(Error::InvalidQuery);
1149 }
1150 plan.selected |= 1 << right;
1151 if let Some(item) = member {
1152 plan.span_fields |= 1 << position;
1153 TermOperand::Member {
1154 item,
1155 needle: MemberNeedle::Field(right),
1156 }
1157 } else {
1158 plan.selected |= 1 << position;
1159 TermOperand::Field(right)
1160 }
1161 }
1162 QueryOperand::Literal(value) => {
1163 if let Some(item) = member {
1164 if !key::supports(item) {
1165 return Err(Error::InvalidQuery);
1166 }
1167 value.admit(item, false)?;
1168 let mut bytes = Vec::new();
1169 value.append_component(false, &mut bytes);
1170 plan.span_fields |= 1 << position;
1171 TermOperand::Member {
1172 item,
1173 needle: MemberNeedle::Literal(bytes),
1174 }
1175 } else {
1176 let absent = value == IndexValue::Absent;
1177 if key::supports(field.value) {
1178 plan.selected |= 1 << position;
1179 } else if absent
1180 && matches!(predicate.comparison, Comparison::Eq | Comparison::Ne)
1181 {
1182 plan.span_fields |= 1 << position;
1183 } else {
1184 return Err(Error::InvalidQuery);
1185 }
1186 predicate
1187 .comparison
1188 .admit(field.value, field.optional, value)?;
1189 let mut bytes = Vec::new();
1190 value.append_component(field.optional, &mut bytes);
1191 TermOperand::Literal { bytes, absent }
1192 }
1193 }
1194 };
1195 plan.terms.push(Term {
1196 position,
1197 comparison: predicate.comparison,
1198 operand,
1199 or_next: predicate.or_next,
1200 });
1201 }
1202 match order::select(entity, request, output)? {
1205 order::Path::Primary => {}
1206 order::Path::Index(path) => plan.use_index(entity, path),
1207 order::Path::Sort(fields) => {
1208 for &(position, _) in &fields {
1209 plan.selected |= 1 << position;
1210 }
1211 plan.sort = Some(fields);
1212 }
1213 }
1214 if request.distinct {
1215 plan.distinct = distinct::admit(
1216 entity,
1217 request,
1218 plan.projection,
1219 plan.index,
1220 plan.fixed_components,
1221 plan.sort.is_some(),
1222 )?;
1223 if plan.distinct == distinct::Strategy::Complete {
1224 plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
1225 }
1226 }
1227 let mut hash = Sha256::new();
1228 hash.update(b"ic-db:query:v1\0");
1229 hash.update(schema);
1230 hash.update(incarnation);
1231 hash.update([u8::from(request.descending)]);
1232 hash.update((plan.prefix.len() as u32).to_le_bytes());
1233 hash.update(&plan.prefix);
1234 for term in &plan.terms {
1235 hash.update([term.position as u8, term.comparison as u8]);
1236 match &term.operand {
1237 TermOperand::Literal { bytes, .. }
1238 | TermOperand::Member {
1239 needle: MemberNeedle::Literal(bytes),
1240 ..
1241 } => {
1242 hash.update((bytes.len() as u32).to_le_bytes());
1243 hash.update(bytes);
1244 }
1245 TermOperand::Length(length) => {
1246 hash.update((u32::MAX - 1).to_le_bytes());
1247 hash.update(length.to_le_bytes());
1248 }
1249 TermOperand::Field(right)
1250 | TermOperand::Member {
1251 needle: MemberNeedle::Field(right),
1252 ..
1253 } => {
1254 hash.update(u32::MAX.to_le_bytes());
1256 hash.update([*right as u8]);
1257 }
1258 }
1259 }
1260 let clauses = plan
1263 .terms
1264 .iter()
1265 .enumerate()
1266 .fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
1267 if clauses != 0 {
1268 hash.update(b"or-clauses\0");
1269 hash.update([clauses]);
1270 }
1271 if let Some(order) = &request.order {
1272 hash.update(b"order\0");
1273 hash.update([order.len() as u8]);
1274 for name in order {
1275 hash.update([entity
1277 .fields
1278 .iter()
1279 .position(|f| f.name == *name)
1280 .ok_or(Error::InvalidQuery)? as u8]);
1281 }
1282 }
1283 if request.order_descending != 0 {
1284 hash.update(b"order-directions\0");
1285 hash.update([request.order_descending]);
1286 }
1287 if let Some(mask) = plan.projection {
1290 hash.update(b"projection\0");
1291 hash.update(mask.to_le_bytes());
1292 }
1293 if request.distinct {
1294 hash.update(b"distinct\0");
1295 }
1296 plan.binding = hash.finalize().into();
1297 if let Some(cursor) = request.cursor {
1298 if cursor.binding != plan.binding {
1299 return Err(Error::InvalidCursor);
1300 }
1301 plan.validate_position(entity, &cursor.position)
1302 .map_err(|_| Error::InvalidCursor)?;
1303 }
1304 Ok(plan)
1305 }
1306
1307 fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
1308 if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
1309 return Err(Error::InvalidCursor);
1310 }
1311 if let Some(index) = self.index {
1312 let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
1313 for name in index.fields {
1314 consume_index_component(entity, index, name, &mut remaining)?;
1315 }
1316 if !index.unique {
1317 key::consume(&mut remaining, entity.key_type()?)?;
1318 }
1319 if !remaining.is_empty() {
1320 return Err(Error::InvalidCursor);
1321 }
1322 } else {
1323 RowKey::decode(
1324 bytes.get(5..).ok_or(Error::InvalidCursor)?,
1325 entity.key_type()?,
1326 )?;
1327 }
1328 Ok(())
1329 }
1330
1331 fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
1332 QueryCursor {
1333 binding: self.binding,
1334 position: position.to_vec(),
1335 inclusive,
1336 }
1337 }
1338}
1339
1340fn consume_index_component(
1342 entity: &EntitySchema,
1343 index: &IndexSchema,
1344 name: &str,
1345 remaining: &mut &[u8],
1346) -> Result<(), Error> {
1347 let field = entity
1348 .fields
1349 .iter()
1350 .find(|f| f.name == name)
1351 .ok_or(Error::InvalidQuery)?;
1352 if field.optional {
1353 let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
1354 *remaining = rest;
1355 match presence {
1356 0 if !index.present_only => return Ok(()),
1357 1 => {}
1358 _ => return Err(Error::InvalidCursor),
1359 }
1360 }
1361 key::consume(remaining, field.value)
1362}
1363
1364#[inline(never)]
1367#[expect(
1368 clippy::needless_pass_by_value,
1369 reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
1370)]
1371fn fetch_rows<M: Memory>(
1372 db: &Database<M>,
1373 entity: &EntitySchema,
1374 request: Request<'_>,
1375 projection: Option<&TypeSchema>,
1376) -> Result<QueryPage<Vec<u8>>, Error> {
1377 db.schema.admits(entity)?;
1378 let plan = Plan::admit(
1379 entity,
1380 &request,
1381 db.schema.fingerprint(),
1382 db.incarnation,
1383 projection,
1384 PlanOutput::Rows,
1385 )?;
1386 execute(&db.map, entity, &request, &plan, None)
1387}
1388
1389fn execute<M: Memory>(
1390 map: &Map<M>,
1391 entity: &EntitySchema,
1392 request: &Request<'_>,
1393 plan: &Plan<'_>,
1394 mut aggregate: Option<aggregate::Accumulator<'_>>,
1395) -> Result<QueryPage<Vec<u8>>, Error> {
1396 execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
1397}
1398
1399const STEP_INPUT_BYTES: usize = 64 * 1024;
1402const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
1403
1404fn execute_inner<M: Memory>(
1405 map: &Map<M>,
1406 entity: &EntitySchema,
1407 request: &Request<'_>,
1408 plan: &Plan<'_>,
1409 mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
1410 mut input_bytes: Option<&mut usize>,
1411) -> Result<QueryPage<Vec<u8>>, Error> {
1412 let mut page = QueryPage {
1413 rows: Vec::new(),
1414 next: None,
1415 examined: 0,
1416 fetched: 0,
1417 output_bytes: 0,
1418 };
1419 let Some(bounds) = range::bounds(entity, request, plan)? else {
1420 return Ok(page);
1421 };
1422 let terminal = range::terminal_key(&bounds, plan.descending);
1423 let mut entries = map.range((bounds.0.as_ref(), bounds.1.as_ref()));
1424 let mut collected = if plan.distinct == distinct::Strategy::Complete {
1425 Some(distinct::Collection::new(
1426 plan.projection.ok_or(Error::InvalidQuery)?,
1427 ))
1428 } else {
1429 None
1430 };
1431 let mut sorted = plan
1432 .sort
1433 .as_ref()
1434 .map(|_| sort::Collection::new(request, plan.distinct));
1435 let mut component = Vec::new();
1436 let mut right_component = Vec::new();
1437 let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
1440 distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
1441 } else {
1442 None
1443 };
1444 let primary_type = entity.fields[plan.primary].value;
1445 while let Some(entry) = if plan.descending {
1446 entries.next_back()
1447 } else {
1448 entries.next()
1449 } {
1450 if request.work == 0 {
1454 return Err(Error::Limit);
1455 }
1456 page.examined += 1;
1457 let stored_key = entry.key();
1458 let mut read_bytes = stored_key.len();
1459 let (owner, bytes) = if plan.index.is_some() {
1460 let owner_bytes = entry.value();
1461 read_bytes += owner_bytes.len();
1462 let owner = RowKey::decode(&owner_bytes, primary_type)?;
1463 let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
1464 (owner, bytes)
1465 } else {
1466 (
1467 RowKey::decode(&stored_key[5..], primary_type)?,
1468 entry.value(),
1469 )
1470 };
1471 if let Some(used) = input_bytes.as_deref_mut() {
1472 read_bytes += bytes.len();
1473 if read_bytes > CANDIDATE_BYTES {
1474 return Err(Error::Corrupt);
1475 }
1476 *used += read_bytes;
1477 }
1478 page.fetched += 1;
1479 let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
1480 let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
1481 entity.inspect_fields(
1482 &bytes,
1483 plan.selected,
1484 &mut values,
1485 (plan.span_fields != 0
1486 || plan.projection.is_some()
1487 || aggregate.as_ref().is_some_and(|a| a.needs_spans()))
1488 .then_some(&mut spans),
1489 )?;
1490 if RowKey::from_index(values[plan.primary])? != owner {
1491 return Err(Error::Corrupt);
1492 }
1493 if plan.index.is_some() {
1494 validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
1495 }
1496 let mut accepts = |term: &Term| -> Result<bool, Error> {
1497 let value = values[term.position];
1498 component.clear();
1499 let (operand, optional) = match &term.operand {
1500 TermOperand::Literal { absent: true, .. }
1501 if plan.span_fields & (1 << term.position) != 0 =>
1502 {
1503 let absent = bytes[usize::from(spans[term.position].0)] == 0;
1504 return Ok(term.comparison.accepts_absent(absent));
1505 }
1506 TermOperand::Member { item, needle } => {
1507 let needle = match needle {
1508 MemberNeedle::Literal(bytes) => bytes.as_slice(),
1509 MemberNeedle::Field(right) => {
1510 let value = values[*right];
1511 if value == IndexValue::Absent {
1512 return Ok(false);
1513 }
1514 right_component.clear();
1515 value.append_component(false, &mut right_component);
1516 &right_component
1517 }
1518 };
1519 let (start, end) = spans[term.position];
1520 return contains_member(
1521 &bytes[usize::from(start)..usize::from(end)],
1522 entity.fields[term.position].optional,
1523 *item,
1524 needle,
1525 &mut component,
1526 );
1527 }
1528 TermOperand::Length(length) => {
1529 let (start, end) = spans[term.position];
1530 let span = &bytes[usize::from(start)..usize::from(end)];
1531 let actual =
1532 crate::codec::validated_length(span, entity.fields[term.position].optional)
1533 .map(u32::to_be_bytes);
1534 return Ok(term.comparison.accepts(
1535 actual.as_ref().map(|v| v.as_slice()),
1536 Some(&length.to_be_bytes()),
1537 false,
1538 ));
1539 }
1540 TermOperand::Literal { bytes, absent } => (
1541 (!absent).then_some(bytes.as_slice()),
1542 entity.fields[term.position].optional,
1543 ),
1544 TermOperand::Field(right) => {
1545 let rhs = values[*right];
1546 right_component.clear();
1547 rhs.append_component(false, &mut right_component);
1548 (
1549 (rhs != IndexValue::Absent).then_some(right_component.as_slice()),
1550 false,
1551 )
1552 }
1553 };
1554 value.append_component(optional, &mut component);
1555 Ok(term.comparison.accepts(
1556 (value != IndexValue::Absent).then_some(component.as_slice()),
1557 operand,
1558 optional,
1559 ))
1560 };
1561 let matches = 'matches: {
1562 'clause: for clause in plan.terms.split_inclusive(|term| !term.or_next) {
1563 for term in clause {
1564 if accepts(term)? {
1565 continue 'clause;
1566 }
1567 }
1568 break 'matches false;
1569 }
1570 true
1571 };
1572 let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
1573 let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
1574 if matches && let Some(accumulator) = aggregate.as_mut() {
1575 accumulator.push(entity, &values, &bytes, &spans)?;
1576 if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
1577 return Ok(page);
1579 }
1580 } else if matches && let Some(collection) = collected.as_mut() {
1581 collection.push(entity, request, &values, &bytes, &spans)?;
1582 } else if matches && let Some(collection) = sorted.as_mut() {
1583 collection.push(entity, plan, &values, &bytes, &spans)?;
1584 } else if matches && !duplicate {
1585 let size = plan
1586 .projection
1587 .map_or(bytes.len(), |mask| projection_size(&spans, mask));
1588 if size > request.bytes {
1589 return Err(Error::RowTooLarge);
1590 }
1591 if size > request.bytes - page.output_bytes {
1592 page.next = Some(plan.cursor(stored_key, true));
1593 return Ok(page);
1594 }
1595 page.output_bytes += size;
1596 if let Some(mask) = plan.projection {
1597 page.rows.push(copy_projection(&bytes, &spans, mask, size));
1598 } else {
1599 page.rows.push(bytes);
1600 }
1601 if let Some(boundary) = boundary {
1602 previous = Some(boundary.to_vec());
1603 }
1604 }
1605 if page.rows.len() == request.rows
1606 || page.examined == request.work
1607 || input_bytes
1608 .as_deref()
1609 .is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
1610 {
1611 if terminal == Some(stored_key) {
1612 break;
1613 }
1614 if (aggregate.is_some() && input_bytes.is_none())
1615 || collected.is_some()
1616 || sorted.is_some()
1617 {
1618 return Err(Error::Limit);
1621 }
1622 page.next = Some(plan.cursor(stored_key, false));
1623 return Ok(page);
1624 }
1625 }
1626 if let Some(collection) = collected {
1627 page.output_bytes = collection.output_bytes;
1628 page.rows = collection.rows;
1629 }
1630 if let Some(collection) = sorted {
1631 collection.finish(request.bytes, &mut page)?;
1632 }
1633 Ok(page)
1634}