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