1mod aggregate;
3mod distinct;
4mod order;
5mod range;
6mod sort;
7pub use aggregate::jobs::{AggregateJobs, GroupCursor, GroupPage, JobHandle, JobOutcome, JobStep};
8pub use aggregate::{Aggregate, GroupCount, GroupOrder, GroupValue};
9
10use super::{Database, Map, prefix, row_key, validate_index_entry};
11use crate::{
12 Entity, EntitySchema, Error, FieldType, IndexSchema, IndexValue, TypeBody, TypeSchema, Value,
13 codec::Decoder, key, primary::RowKey, types::TypeGraph,
14};
15use ic_storage::Memory;
16use sha2::{Digest, Sha256};
17use std::marker::PhantomData;
18
19const MAX_TERMS: usize = 8;
20const MAX_WORK: usize = 512;
21const MAX_OUTPUT: usize = 128 * 1024;
22const MAX_COMPARISON_KEY: usize = 4096;
23const MAX_DISTINCT_VALUES: usize = 32;
24const MAX_STATE_BYTES: usize = 128 * 1024;
25
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
28pub enum SortDirection {
29 Ascending,
31 Descending,
33}
34
35#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37#[repr(u8)]
38pub enum Comparison {
39 Eq = 0,
41 Ne = 1,
43 Lt = 2,
45 Le = 3,
47 Gt = 4,
49 Ge = 5,
51 StartsWith = 6,
55 EndsWith = 7,
58 Contains = 8,
61}
62
63impl Comparison {
64 fn admit(self, field: FieldType, optional: bool, value: IndexValue<'_>) -> Result<(), Error> {
65 value.admit(field, optional)?;
66 let field = key::operand_type(field);
67 if (matches!(self, Self::StartsWith | Self::EndsWith)
68 && !matches!(field, FieldType::Text { .. } | FieldType::Blob { .. }))
69 || (self == Self::Contains && !matches!(field, FieldType::Text { .. }))
70 {
71 return Err(Error::InvalidQuery);
72 }
73 if value == IndexValue::Absent && !matches!(self, Self::Eq | Self::Ne) {
74 return Err(Error::InvalidOperand);
75 }
76 Ok(())
77 }
78
79 fn accepts(self, actual: Option<&[u8]>, operand: Option<&[u8]>, optional: bool) -> bool {
80 if actual.is_none() {
81 return self.accepts_absent(operand.is_none());
82 }
83 match self {
84 Self::Eq => actual == operand,
85 Self::Ne => actual != operand,
86 Self::StartsWith | Self::EndsWith | Self::Contains => {
87 fn content(key: &[u8], optional: bool) -> Option<&[u8]> {
90 key.get(usize::from(optional)..)?.strip_suffix(&[0, 0])
91 }
92 actual
93 .and_then(|key| content(key, optional))
94 .zip(operand.and_then(|key| content(key, optional)))
95 .is_some_and(|(actual, operand)| match self {
96 Self::StartsWith => actual.starts_with(operand),
99 Self::EndsWith => actual
103 .strip_suffix(operand)
104 .is_some_and(|prefix| prefix.last() != Some(&0)),
105 _ => memchr::memmem::find(actual, operand).is_some(),
109 })
110 }
111 _ if actual.is_none() || operand.is_none() => false,
112 Self::Lt => actual < operand,
113 Self::Le => actual <= operand,
114 Self::Gt => actual > operand,
115 Self::Ge => actual >= operand,
116 }
117 }
118
119 fn accepts_absent(self, other_absent: bool) -> bool {
122 match self {
123 Self::Eq => other_absent,
124 Self::Ne => !other_absent,
125 _ => false,
126 }
127 }
128}
129
130#[derive(Clone, Debug, PartialEq, Eq)]
134pub struct QueryCursor {
135 binding: [u8; 32],
136 position: Vec<u8>,
137 inclusive: bool,
138}
139impl QueryCursor {
140 pub(super) const MAX_ENCODED_BYTES: usize = 34 + crate::MAX_INDEX_KEY_BYTES;
141
142 #[must_use]
144 pub fn to_bytes(&self) -> Vec<u8> {
145 let mut bytes = vec![1, u8::from(self.inclusive)];
146 bytes.extend(self.binding);
147 bytes.extend(&self.position);
148 bytes
149 }
150 pub fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
154 if !(35..=Self::MAX_ENCODED_BYTES).contains(&bytes.len()) || bytes[0] != 1 || bytes[1] > 1 {
155 return Err(Error::InvalidCursor);
156 }
157 Ok(Self {
158 binding: bytes[2..34].try_into().map_err(|_| Error::InvalidCursor)?,
159 position: bytes[34..].to_vec(),
160 inclusive: bytes[1] == 1,
161 })
162 }
163}
164
165#[derive(Debug)]
168pub struct QueryPage<T> {
169 pub rows: Vec<T>,
171 pub next: Option<QueryCursor>,
173 pub examined: usize,
175 pub fetched: usize,
177 pub output_bytes: usize,
179}
180
181impl QueryPage<Vec<u8>> {
182 #[inline(never)]
183 pub(super) fn decode_entities<E: Entity>(self) -> Result<QueryPage<E>, Error> {
184 Ok(QueryPage {
185 rows: self
186 .rows
187 .iter()
188 .map(|bytes| E::decode(bytes))
189 .collect::<Result<_, _>>()?,
190 next: self.next,
191 examined: self.examined,
192 fetched: self.fetched,
193 output_bytes: self.output_bytes,
194 })
195 }
196
197 #[inline(never)]
198 fn decode_projection<R: Value>(self) -> Result<QueryPage<R>, Error> {
199 Ok(QueryPage {
200 rows: self
201 .rows
202 .iter()
203 .map(|bytes| {
204 let mut reader = Decoder::new(bytes)?;
205 let row = R::decode_from(&mut reader)?;
207 reader.finish()?;
208 Ok(row)
209 })
210 .collect::<Result<_, Error>>()?,
211 next: self.next,
212 examined: self.examined,
213 fetched: self.fetched,
214 output_bytes: self.output_bytes,
215 })
216 }
217}
218
219struct Predicate<'a> {
220 field: &'a str,
221 comparison: Comparison,
222 value: IndexValue<'a>,
223 or_next: bool,
225}
226struct Request<'a> {
227 groups: aggregate::GroupRequest<'a>,
228 predicates: Vec<Predicate<'a>>,
229 index: Option<(&'a str, Vec<IndexValue<'a>>)>,
230 order: Option<Vec<&'a str>>,
231 order_descending: u8,
232 descending: bool,
233 distinct: bool,
234 rows: usize,
235 work: usize,
236 bytes: usize,
237 cursor: Option<&'a QueryCursor>,
238 over_limit: bool,
239}
240
241impl Default for Request<'_> {
242 fn default() -> Self {
243 Self {
244 groups: aggregate::GroupRequest::default(),
245 predicates: Vec::new(),
246 index: None,
247 order: None,
248 order_descending: 0,
249 descending: false,
250 distinct: false,
251 rows: 32,
252 work: 128,
253 bytes: MAX_OUTPUT,
254 cursor: None,
255 over_limit: false,
256 }
257 }
258}
259
260impl<'a> Request<'a> {
263 #[inline(never)]
264 fn filter(&mut self, field: &'a str, comparison: Comparison, value: impl Into<IndexValue<'a>>) {
265 if self.predicates.len() == MAX_TERMS {
266 self.over_limit = true;
267 } else {
268 self.predicates.push(Predicate {
269 field,
270 comparison,
271 value: value.into(),
272 or_next: false,
273 });
274 }
275 }
276
277 #[inline(never)]
278 fn or_clause(
279 &mut self,
280 alternatives: impl ExactSizeIterator<Item = (&'a str, Comparison, IndexValue<'a>)>,
281 ) {
282 let count = alternatives.len();
283 if count == 0 || count > MAX_TERMS - self.predicates.len() {
284 self.over_limit = true;
285 } else {
286 self.predicates.extend(alternatives.enumerate().map(
287 |(i, (field, comparison, value))| Predicate {
288 field,
289 comparison,
290 value,
291 or_next: i + 1 < count,
292 },
293 ));
294 }
295 }
296
297 #[inline(never)]
298 fn filter_not_in(&mut self, field: &'a str, values: &[IndexValue<'a>]) {
299 if values.is_empty() || values.len() > MAX_TERMS - self.predicates.len() {
300 self.over_limit = true;
301 return;
302 }
303 for &value in values {
304 self.filter(field, Comparison::Ne, value);
305 }
306 }
307
308 #[inline(never)]
309 fn using_index(&mut self, name: &'a str, values: &[IndexValue<'a>]) {
310 if values.len() > 4 {
311 self.over_limit = true;
312 } else {
313 self.index = Some((name, values.to_vec()));
314 }
315 }
316
317 #[inline(never)]
318 fn order_by(&mut self, fields: &[&'a str]) {
319 self.order_descending = 0;
320 if fields.len() > 4 {
321 self.over_limit = true;
322 } else {
323 self.order = Some(fields.to_vec());
324 }
325 }
326
327 #[inline(never)]
328 fn order_by_each(&mut self, fields: &[(&'a str, SortDirection)]) {
329 if fields.len() > 4 {
330 self.over_limit = true;
331 return;
332 }
333 self.order = Some(fields.iter().map(|(name, _)| *name).collect());
334 self.order_descending = fields
335 .iter()
336 .enumerate()
337 .fold(0, |mask, (i, (_, direction))| {
338 mask | (u8::from(*direction == SortDirection::Descending) << i)
339 });
340 }
341
342 fn primary_descending(&self, entity: &EntitySchema) -> bool {
343 self.order_descending != 0
344 && self.order.as_ref().is_some_and(|fields| {
345 fields.last() == Some(&entity.primary_key)
346 && self.order_descending & (1 << (fields.len() - 1)) != 0
347 })
348 }
349}
350
351pub(super) fn source_page<M: Memory>(
353 map: &Map<M>,
354 entity: &EntitySchema,
355 binding: [u8; 32],
356 incarnation: [u8; 16],
357 cursor: Option<&QueryCursor>,
358 rows: usize,
359 bytes: usize,
360) -> Result<QueryPage<Vec<u8>>, Error> {
361 let request = Request {
362 rows,
363 work: rows,
364 bytes,
365 cursor,
366 ..Request::default()
367 };
368 let plan = Plan::admit(entity, &request, binding, incarnation, None, false)?;
369 execute(map, entity, &request, &plan, None)
370}
371
372pub struct Query<'a, E, M: Memory = ic_storage::DefaultMemoryImpl> {
376 db: &'a Database<M>,
377 request: Request<'a>,
378 entity: PhantomData<E>,
379}
380impl<M: Memory> Database<M> {
381 #[must_use]
383 pub fn query<E: Entity>(&self) -> Query<'_, E, M> {
384 Query {
385 db: self,
386 entity: PhantomData,
387 request: Request::default(),
388 }
389 }
390}
391impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
392 #[must_use]
403 pub fn distinct(mut self) -> Self {
404 self.request.distinct = true;
405 self
406 }
407 #[must_use]
417 pub fn filter(
418 mut self,
419 field: &'a str,
420 comparison: Comparison,
421 value: impl Into<IndexValue<'a>>,
422 ) -> Self {
423 self.request.filter(field, comparison, value);
424 self
425 }
426 #[must_use]
433 pub fn filter_between(
434 self,
435 field: &'a str,
436 lower: impl Into<IndexValue<'a>>,
437 upper: impl Into<IndexValue<'a>>,
438 ) -> Self {
439 self.filter(field, Comparison::Ge, lower)
440 .filter(field, Comparison::Le, upper)
441 }
442 #[must_use]
450 pub fn filter_not_between(
451 self,
452 field: &'a str,
453 lower: impl Into<IndexValue<'a>>,
454 upper: impl Into<IndexValue<'a>>,
455 ) -> Self {
456 self.filter_any(&[
457 (field, Comparison::Lt, lower.into()),
458 (field, Comparison::Gt, upper.into()),
459 ])
460 }
461 #[must_use]
468 pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
469 self.request.or_clause(alternatives.iter().copied());
470 self
471 }
472 #[must_use]
480 pub fn filter_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
481 self.request.or_clause(
482 values
483 .iter()
484 .copied()
485 .map(|value| (field, Comparison::Eq, value)),
486 );
487 self
488 }
489
490 #[must_use]
498 pub fn filter_not_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
499 self.request.filter_not_in(field, values);
500 self
501 }
502 #[must_use]
507 pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
508 self.request.using_index(name, values);
509 self
510 }
511 #[must_use]
521 pub fn order_by(mut self, fields: &[&'a str]) -> Self {
522 self.request.order_by(fields);
523 self
524 }
525 #[must_use]
530 pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
531 self.request.order_by_each(fields);
532 self
533 }
534 #[must_use]
536 pub fn descending(mut self) -> Self {
537 self.request.descending = true;
538 self
539 }
540 #[must_use]
547 pub fn limit(mut self, rows: usize) -> Self {
548 self.request.rows = rows;
549 self
550 }
551 #[must_use]
553 pub fn work_limit(mut self, candidates: usize) -> Self {
554 self.request.work = candidates;
555 self
556 }
557 #[must_use]
559 pub fn byte_limit(mut self, bytes: usize) -> Self {
560 self.request.bytes = bytes;
561 self
562 }
563 #[must_use]
565 pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
566 self.request.cursor = Some(cursor);
567 self
568 }
569 pub fn fetch(self) -> Result<QueryPage<E>, Error> {
576 fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
577 }
578 pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
588 let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
589 raw.decode_projection()
590 }
591}
592
593fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
597 let TypeBody::Record(fields) = &output.body else {
598 return Err(Error::InvalidQuery);
599 };
600 if fields.is_empty()
601 || fields.len() > crate::schema::MAX_FIELDS
602 || fields.windows(2).any(|w| w[0].name >= w[1].name)
603 {
604 return Err(Error::InvalidQuery);
605 }
606 let mut source = TypeGraph::default();
607 let mut target = TypeGraph::default();
608 let mut mask = 0;
609 for field in *fields {
610 let position = entity
611 .fields
612 .iter()
613 .position(|f| f.name == field.name)
614 .ok_or(Error::InvalidQuery)?;
615 let stored = &entity.fields[position];
616 if stored.value != field.value || stored.optional != field.optional {
617 return Err(Error::InvalidQuery);
618 }
619 source
620 .include(stored.value)
621 .map_err(|_| Error::InvalidQuery)?;
622 target
623 .include(field.value)
624 .map_err(|_| Error::InvalidQuery)?;
625 mask |= 1 << position;
626 }
627 if !source.contains(&target) {
628 return Err(Error::InvalidQuery);
629 }
630 Ok(mask)
631}
632
633struct Term {
634 position: usize,
635 comparison: Comparison,
636 operand: Vec<u8>,
637 absent: bool,
638 or_next: bool,
639}
640
641fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
642 for (i, field) in entity.fields.iter().enumerate() {
643 if mask & (1 << i) != 0 && !key::supports(field.value) {
644 return Err(Error::InvalidQuery);
645 }
646 }
647 Ok(())
648}
649
650fn comparison_key(
652 entity: &EntitySchema,
653 mask: u16,
654 values: &[IndexValue<'_>],
655) -> Result<Vec<u8>, Error> {
656 let mut key = Vec::new();
657 for (i, field) in entity.fields.iter().enumerate() {
658 if mask & (1 << i) != 0 {
659 values[i].append_component(field.optional, &mut key);
660 if key.len() > MAX_COMPARISON_KEY {
661 return Err(Error::Limit);
662 }
663 }
664 }
665 Ok(key)
666}
667
668fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
669 if size > limit {
670 return Err(Error::RowTooLarge);
671 }
672 if size > limit - *used {
673 return Err(Error::Limit);
674 }
675 *used += size;
676 Ok(())
677}
678
679fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
681 spans
682 .iter()
683 .enumerate()
684 .filter(|(i, _)| mask & (1 << i) != 0)
685 .map(|(_, (start, end))| usize::from(end - start))
686 .sum()
687}
688
689fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
690 let mut output = Vec::with_capacity(size);
691 for (i, &(start, end)) in spans.iter().enumerate() {
692 if mask & (1 << i) != 0 {
693 output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
694 }
695 }
696 output
697}
698struct Plan<'a> {
699 index: Option<&'a IndexSchema>,
700 prefix: Vec<u8>,
701 fixed_components: usize,
702 terms: Vec<Term>,
703 selected: u16,
704 presence: u16,
706 binding: [u8; 32],
707 projection: Option<u16>,
708 distinct: distinct::Strategy,
709 sort: Option<Vec<(usize, bool)>>,
710 descending: bool,
711}
712impl<'a> Plan<'a> {
713 fn admit(
714 entity: &'a EntitySchema,
715 request: &Request<'_>,
716 schema: [u8; 32],
717 incarnation: [u8; 16],
718 projection: Option<&TypeSchema>,
719 group_output: bool,
720 ) -> Result<Self, Error> {
721 if request.over_limit
722 || !(1..=32).contains(&request.rows)
723 || !(1..=MAX_WORK).contains(&request.work)
724 || !(1..=MAX_OUTPUT).contains(&request.bytes)
725 {
726 return Err(Error::Limit);
727 }
728 if !group_output && !request.groups.is_empty() {
729 return Err(Error::InvalidQuery);
730 }
731 for value in request
733 .predicates
734 .iter()
735 .map(|p| &p.value)
736 .chain(request.index.iter().flat_map(|(_, values)| values.iter()))
737 {
738 if match value {
739 IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
740 IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
741 _ => false,
742 } {
743 return Err(Error::Limit);
744 }
745 }
746 let primary = entity
747 .fields
748 .iter()
749 .position(|f| f.name == entity.primary_key)
750 .ok_or(Error::InvalidQuery)?;
751 let mut plan = Self {
752 index: None,
753 prefix: prefix(2, entity.id),
754 fixed_components: 0,
755 terms: Vec::new(),
756 selected: 1 << primary,
757 presence: 0,
758 binding: [0; 32],
759 projection: projection
760 .map(|output| admit_projection(entity, output))
761 .transpose()?,
762 distinct: distinct::Strategy::Identity,
763 sort: None,
764 descending: request.descending ^ request.primary_descending(entity),
765 };
766 for predicate in &request.predicates {
767 let position = entity
768 .fields
769 .iter()
770 .position(|f| f.name == predicate.field)
771 .ok_or(Error::InvalidQuery)?;
772 let field = &entity.fields[position];
773 let ordered = key::supports(field.value);
774 if !ordered
775 && !(predicate.value == IndexValue::Absent
776 && matches!(predicate.comparison, Comparison::Eq | Comparison::Ne))
777 {
778 return Err(Error::InvalidQuery);
779 }
780 predicate
781 .comparison
782 .admit(field.value, field.optional, predicate.value)?;
783 let absent = predicate.value == IndexValue::Absent;
784 let mut operand = Vec::new();
785 predicate
786 .value
787 .append_component(field.optional, &mut operand);
788 plan.terms.push(Term {
789 position,
790 comparison: predicate.comparison,
791 operand,
792 absent,
793 or_next: predicate.or_next,
794 });
795 if ordered {
796 plan.selected |= 1 << position;
797 } else {
798 plan.presence |= 1 << position;
799 }
800 }
801 match order::select(entity, request)? {
804 order::Path::Primary => {}
805 order::Path::Index(path) => {
806 plan.index = Some(path.index);
807 plan.prefix = path.prefix;
808 plan.selected |= entity.key_fields();
809 plan.fixed_components = path.fixed;
810 }
811 order::Path::Sort(fields) => {
812 for &(position, _) in &fields {
813 plan.selected |= 1 << position;
814 }
815 plan.sort = Some(fields);
816 }
817 }
818 if request.distinct {
819 plan.distinct = distinct::admit(
820 entity,
821 request,
822 plan.projection,
823 plan.index,
824 plan.fixed_components,
825 plan.sort.is_some(),
826 )?;
827 if plan.distinct == distinct::Strategy::Complete {
828 plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
829 }
830 }
831 let mut hash = Sha256::new();
832 hash.update(b"ic-db:query:v1\0");
833 hash.update(schema);
834 hash.update(incarnation);
835 hash.update([u8::from(request.descending)]);
836 hash.update((plan.prefix.len() as u32).to_le_bytes());
837 hash.update(&plan.prefix);
838 for term in &plan.terms {
839 hash.update([term.position as u8, term.comparison as u8]);
840 hash.update((term.operand.len() as u32).to_le_bytes());
841 hash.update(&term.operand);
842 }
843 let clauses = plan
846 .terms
847 .iter()
848 .enumerate()
849 .fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
850 if clauses != 0 {
851 hash.update(b"or-clauses\0");
852 hash.update([clauses]);
853 }
854 if let Some(order) = &request.order {
855 hash.update(b"order\0");
856 hash.update([order.len() as u8]);
857 for name in order {
858 hash.update([entity
860 .fields
861 .iter()
862 .position(|f| f.name == *name)
863 .ok_or(Error::InvalidQuery)? as u8]);
864 }
865 }
866 if request.order_descending != 0 {
867 hash.update(b"order-directions\0");
868 hash.update([request.order_descending]);
869 }
870 if let Some(mask) = plan.projection {
873 hash.update(b"projection\0");
874 hash.update(mask.to_le_bytes());
875 }
876 if request.distinct {
877 hash.update(b"distinct\0");
878 }
879 plan.binding = hash.finalize().into();
880 if let Some(cursor) = request.cursor {
881 if cursor.binding != plan.binding {
882 return Err(Error::InvalidCursor);
883 }
884 plan.validate_position(entity, &cursor.position)
885 .map_err(|_| Error::InvalidCursor)?;
886 }
887 Ok(plan)
888 }
889 fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
890 if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
891 return Err(Error::InvalidCursor);
892 }
893 if let Some(index) = self.index {
894 let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
895 for name in index.fields {
896 consume_index_component(entity, index, name, &mut remaining)?;
897 }
898 if !index.unique {
899 key::consume(&mut remaining, entity.key_type()?)?;
900 }
901 if !remaining.is_empty() {
902 return Err(Error::InvalidCursor);
903 }
904 } else {
905 RowKey::decode(
906 bytes.get(5..).ok_or(Error::InvalidCursor)?,
907 entity.key_type()?,
908 )?;
909 }
910 Ok(())
911 }
912 fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
913 QueryCursor {
914 binding: self.binding,
915 position: position.to_vec(),
916 inclusive,
917 }
918 }
919}
920
921fn consume_index_component(
923 entity: &EntitySchema,
924 index: &IndexSchema,
925 name: &str,
926 remaining: &mut &[u8],
927) -> Result<(), Error> {
928 let field = entity
929 .fields
930 .iter()
931 .find(|f| f.name == name)
932 .ok_or(Error::InvalidQuery)?;
933 if field.optional {
934 let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
935 *remaining = rest;
936 match presence {
937 0 if !index.present_only => return Ok(()),
938 1 => {}
939 _ => return Err(Error::InvalidCursor),
940 }
941 }
942 key::consume(remaining, field.value)
943}
944
945#[inline(never)]
948#[expect(
949 clippy::needless_pass_by_value,
950 reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
951)]
952fn fetch_rows<M: Memory>(
953 db: &Database<M>,
954 entity: &EntitySchema,
955 request: Request<'_>,
956 projection: Option<&TypeSchema>,
957) -> Result<QueryPage<Vec<u8>>, Error> {
958 db.schema.admits(entity)?;
959 let plan = Plan::admit(
960 entity,
961 &request,
962 db.schema.fingerprint(),
963 db.incarnation,
964 projection,
965 false,
966 )?;
967 execute(&db.map, entity, &request, &plan, None)
968}
969
970fn execute<M: Memory>(
971 map: &Map<M>,
972 entity: &EntitySchema,
973 request: &Request<'_>,
974 plan: &Plan<'_>,
975 mut aggregate: Option<aggregate::Accumulator<'_>>,
976) -> Result<QueryPage<Vec<u8>>, Error> {
977 execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
978}
979
980const STEP_INPUT_BYTES: usize = 64 * 1024;
983const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
984
985fn execute_inner<M: Memory>(
986 map: &Map<M>,
987 entity: &EntitySchema,
988 request: &Request<'_>,
989 plan: &Plan<'_>,
990 mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
991 mut input_bytes: Option<&mut usize>,
992) -> Result<QueryPage<Vec<u8>>, Error> {
993 let mut page = QueryPage {
994 rows: Vec::new(),
995 next: None,
996 examined: 0,
997 fetched: 0,
998 output_bytes: 0,
999 };
1000 let Some(bounds) = range::bounds(entity, request, plan)? else {
1001 return Ok(page);
1002 };
1003 let mut entries = map.range(bounds);
1004 let mut collected = if plan.distinct == distinct::Strategy::Complete {
1005 Some(distinct::Collection::new(
1006 plan.projection.ok_or(Error::InvalidQuery)?,
1007 ))
1008 } else {
1009 None
1010 };
1011 let mut sorted = plan
1012 .sort
1013 .as_ref()
1014 .map(|_| sort::Collection::new(request, plan.distinct == distinct::Strategy::Sorted));
1015 let mut component = Vec::new();
1016 let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
1019 distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
1020 } else {
1021 None
1022 };
1023 while let Some(entry) = if plan.descending {
1024 entries.next_back()
1025 } else {
1026 entries.next()
1027 } {
1028 if request.work == 0 {
1032 return Err(Error::Limit);
1033 }
1034 page.examined += 1;
1035 let stored_key = entry.key();
1036 let mut read_bytes = stored_key.len();
1037 let (owner, bytes) = if plan.index.is_some() {
1038 let owner_bytes = entry.value();
1039 read_bytes += owner_bytes.len();
1040 let owner = RowKey::decode(&owner_bytes, entity.key_type()?)?;
1041 let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
1042 (owner, bytes)
1043 } else {
1044 (
1045 RowKey::decode(&stored_key[5..], entity.key_type()?)?,
1046 entry.value(),
1047 )
1048 };
1049 if let Some(used) = input_bytes.as_deref_mut() {
1050 read_bytes += bytes.len();
1051 if read_bytes > CANDIDATE_BYTES {
1052 return Err(Error::Corrupt);
1053 }
1054 *used += read_bytes;
1055 }
1056 page.fetched += 1;
1057 let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
1058 let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
1059 entity.inspect_fields(
1060 &bytes,
1061 plan.selected,
1062 &mut values,
1063 (plan.presence != 0
1064 || plan.projection.is_some()
1065 || aggregate.as_ref().is_some_and(|a| a.needs_spans()))
1066 .then_some(&mut spans),
1067 )?;
1068 let primary = entity
1069 .fields
1070 .iter()
1071 .position(|f| f.name == entity.primary_key)
1072 .ok_or(Error::Corrupt)?;
1073 if RowKey::from_index(values[primary])? != owner {
1074 return Err(Error::Corrupt);
1075 }
1076 if plan.index.is_some() {
1077 validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
1078 }
1079 let matches = plan
1080 .terms
1081 .split_inclusive(|term| !term.or_next)
1082 .all(|clause| {
1083 clause.iter().any(|term| {
1084 if plan.presence & (1 << term.position) != 0 {
1085 let absent = bytes[usize::from(spans[term.position].0)] == 0;
1088 return term.comparison.accepts_absent(absent);
1089 }
1090 let value = values[term.position];
1091 component.clear();
1092 value.append_component(entity.fields[term.position].optional, &mut component);
1093 term.comparison.accepts(
1094 (value != IndexValue::Absent).then_some(component.as_slice()),
1095 (!term.absent).then_some(term.operand.as_slice()),
1096 entity.fields[term.position].optional,
1097 )
1098 })
1099 });
1100 let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
1101 let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
1102 if matches && let Some(accumulator) = aggregate.as_mut() {
1103 accumulator.push(entity, &values, &bytes, &spans)?;
1104 if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
1105 return Ok(page);
1107 }
1108 } else if matches && let Some(collection) = collected.as_mut() {
1109 collection.push(entity, request, &values, &bytes, &spans)?;
1110 } else if matches && let Some(collection) = sorted.as_mut() {
1111 collection.push(entity, plan, &values, &bytes, &spans)?;
1112 } else if matches && !duplicate {
1113 let size = plan
1114 .projection
1115 .map_or(bytes.len(), |mask| projection_size(&spans, mask));
1116 if size > request.bytes {
1117 return Err(Error::RowTooLarge);
1118 }
1119 if size > request.bytes - page.output_bytes {
1120 page.next = Some(plan.cursor(stored_key, true));
1121 return Ok(page);
1122 }
1123 page.output_bytes += size;
1124 if let Some(mask) = plan.projection {
1125 page.rows.push(copy_projection(&bytes, &spans, mask, size));
1126 } else {
1127 page.rows.push(bytes);
1128 }
1129 if let Some(boundary) = boundary {
1130 previous = Some(boundary.to_vec());
1131 }
1132 }
1133 if page.rows.len() == request.rows
1134 || page.examined == request.work
1135 || input_bytes
1136 .as_deref()
1137 .is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
1138 {
1139 if (aggregate.is_some() && input_bytes.is_none())
1140 || collected.is_some()
1141 || sorted.is_some()
1142 {
1143 return Err(Error::Limit);
1146 }
1147 page.next = Some(plan.cursor(stored_key, false));
1148 return Ok(page);
1149 }
1150 }
1151 if let Some(collection) = collected {
1152 page.output_bytes = collection.output_bytes;
1153 page.rows = collection.rows;
1154 }
1155 if let Some(collection) = sorted {
1156 collection.finish(request.bytes, &mut page)?;
1157 }
1158 Ok(page)
1159}