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