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