Skip to main content

ic_db/store/query/
mod.rs

1//! Bounded fluent traversal. Typed result construction stays outside shared execution.
2mod 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/// Direction of one field in an explicit result order.
27#[derive(Clone, Copy, Debug, PartialEq, Eq)]
28pub enum SortDirection {
29    /// Smaller values first; absence precedes present values.
30    Ascending,
31    /// Larger values first; absence follows present values.
32    Descending,
33}
34
35/// Exact comparison. Equality distinguishes absent values; ranges and pattern matches require presence.
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37#[repr(u8)]
38pub enum Comparison {
39    /// Equal, including two absent values.
40    Eq = 0,
41    /// Not equal, including absent versus present.
42    Ne = 1,
43    /// Present and less than the present operand.
44    Lt = 2,
45    /// Present and less than or equal to the present operand.
46    Le = 3,
47    /// Present and greater than the present operand.
48    Gt = 4,
49    /// Present and greater than or equal to the present operand.
50    Ge = 5,
51    /// Present Text or Blob starts with an exact operand of the same type.
52    /// Text uses UTF-8 bytes without normalization; Blob uses raw bytes.
53    /// Empty prefixes match all present values, including empty values; other types refuse.
54    StartsWith = 6,
55    /// Present Text or Blob ends with an exact operand of the same type.
56    /// Empty suffixes match all present values; text is not normalized.
57    EndsWith = 7,
58    /// Present text contains the exact UTF-8 operand, without normalization.
59    /// Empty needles match all present text; this is not collection membership.
60    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                // Compare escaped content, never the presence byte or terminator.
88                // In particular, optional empty text must not match suffix U+0001.
89                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                        // Prefixes start at a component boundary: escaping each
97                        // byte preserves prefix identity for Text and Blob alike.
98                        Self::StartsWith => actual.starts_with(operand),
99                        // A suffix starting after 00 starts inside an escaped zero
100                        // (00 FF), not at a raw-byte boundary. This matters for Blob
101                        // operands beginning FF; valid UTF-8 cannot begin there.
102                        Self::EndsWith => actual
103                            .strip_suffix(operand)
104                            .is_some_and(|prefix| prefix.last() != Some(&0)),
105                        // Valid UTF-8 needles cannot start within an escaped NUL
106                        // (00 FF) or a multibyte character. Search is linear and
107                        // constant-space even for repetitive bounded operands.
108                        _ => 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    // One side is absent. Equality/inequality are symmetric; execution,
120    // presence-only filters and sparse membership share this rule.
121    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/// A bounded logical position, bound to database, schema, query and direction.
131/// It is not an authorization token or a snapshot. Callers may choose positions;
132/// the database revalidates all claims and retains no trusted progress counters.
133#[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    /// Encode the bounded continuation for an application's transport.
143    #[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    /// Decode framing; execution additionally checks query identity and key shape.
151    /// # Errors
152    /// Refuses unsupported versions, flags and oversized or incomplete frames.
153    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/// A bounded page. Empty rows do not mean completion when `next` is present.
166/// Ordinary queries are live; maintenance source pages read frozen input.
167#[derive(Debug)]
168pub struct QueryPage<T> {
169    /// Matching results in the selected total order.
170    pub rows: Vec<T>,
171    /// Resume position; only None establishes completion.
172    pub next: Option<QueryCursor>,
173    /// Examined primary/index candidates, including residual nonmatches and retries.
174    pub examined: usize,
175    /// Rows fetched; tracked separately from index candidates.
176    pub fetched: usize,
177    /// Sum of returned encoded entity/projected-record bytes, excluding transport overhead.
178    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                    // Output records replace the entity root, not an extra nested value.
206                    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    // Consecutive alternatives form one clause; clauses are ANDed.
224    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
260// Request construction depends on operand shapes, not the entity's Rust type.
261// Keep allocation and clause loops out of every typed builder instantiation.
262impl<'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
351// Maintenance gets only bounded primary traversal, not a second query frontend.
352pub(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
372/// Fluent exact predicates over one entity. No callback executor is generated.
373/// Ordering uses primary order, an explicit index, a proven automatic path or
374/// bounded complete sorting. Work exhaustion never returns a sorted prefix.
375pub 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    /// Begin a live primary-key-ordered query. Admission occurs on `fetch`.
382    #[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    /// Remove duplicate output records. Proven leading index tuples use live
393    /// pages; identity projections need no duplicate tracking. Other projections scan to
394    /// completion in one call, retaining at most 32 tuples within 128 KiB.
395    /// That fallback preserves first-match traversal order, refuses cursors and
396    /// returns `Limit` if work, result count or combined bytes cannot fit; it
397    /// never returns a partial result. An individually oversized row returns
398    /// `RowTooLarge`. Comparison keys are bounded to 4096 bytes.
399    /// Non-identity sorted DISTINCT retains at most 32 distinct tuples. Its order
400    /// must cover exactly the projected fields (unless the result is inherently
401    /// unique); remove duplicates before applying `limit` and output bytes.
402    #[must_use]
403    pub fn distinct(mut self) -> Self {
404        self.request.distinct = true;
405        self
406    }
407    /// Add an AND term over an exact top-level ordered scalar/unit-enum field.
408    /// Eq/Ne with `IndexValue::Absent` also accept any optional stored field,
409    /// including blobs and containers. Empty values are present, not absent.
410    /// All operands are admitted before storage reads, including contradictory terms.
411    /// On a primary traversal, mandatory Eq/Lt/Le/Gt/Ge primary-key comparisons
412    /// narrow the scanned range. On an index path, those comparisons can narrow
413    /// its first field after the admitted fixed prefix. Only examined rows
414    /// undergo integrity checks; oversized derived bounds remain residual filters.
415    /// Indexed StartsWith can seek that field's exact encoded Text/Blob prefix too.
416    #[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    /// Match a present field inside an inclusive range, ANDed with other filters.
427    /// Equivalent to `filter(field, Comparison::Ge, lower)` followed by
428    /// `filter(field, Comparison::Le, upper)`, including cursor/job identity.
429    /// Both exact operands are admitted and consume two of the eight comparisons.
430    /// Absent operands refuse; absent fields never match. Reversed bounds produce
431    /// no matches, without skipping admission of either operand or other filters.
432    #[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    /// Match a present field strictly outside an inclusive range.
443    /// Equivalent to one `filter_any` clause containing `Lt lower` then `Gt upper`,
444    /// including cursor/job identity. Both exact operands consume filter terms.
445    /// Absent operands refuse and absent fields never match; this is not a general
446    /// negation of `filter_between`. Equal bounds exclude that value; reversed
447    /// bounds match every present value, once. Uses the existing single traversal
448    /// and work budget, without seeking separate ranges for the two alternatives.
449    #[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    /// Add an OR clause of exact top-level comparisons, ANDed with other filters.
462    /// Each clause must contain at least one comparison; all filters together
463    /// may contain at most eight. Empty/oversized clauses refuse with `Error::Limit`
464    /// at execution. Every operand is admitted, even if another alternative matches.
465    /// Uses one ordered traversal, without union scans or duplicate rows. Alternatives
466    /// do not establish fixed index prefixes; a one-term clause behaves like `filter`.
467    #[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    /// Match a field against any supplied exact value, ANDed with other filters.
473    /// Equivalent to `filter_any` with equality comparisons in the supplied order.
474    /// Absence matches only an explicit `IndexValue::Absent` member on an optional field.
475    /// Repeated members never repeat rows, but each counts toward the shared
476    /// eight-comparison limit. Empty or oversized lists refuse with `Error::Limit`.
477    /// Every member is admitted before reading; there is no coercion, sorting or
478    /// deduplication of operands. Reordering members changes cursor/job identity.
479    #[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    /// Exclude every supplied exact value, ANDed with other filters.
491    /// Equivalent to consecutive `filter(field, Comparison::Ne, value)` calls
492    /// in the supplied order. Absent fields match unless absence is explicitly
493    /// excluded. Empty lists refuse; all members, including duplicates, count
494    /// toward the shared eight-comparison budget. Every operand is admitted.
495    /// The equivalent inequality chain shares cursor/job identity; reordering
496    /// the list changes that identity. No coercion or deduplication is performed.
497    #[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    /// Select index order and exact leading components (at most four).
503    /// All rows matching this prefix are considered. Sparse indexes require
504    /// every optional indexed component to be proven present by the prefix or
505    /// filters. Every alternative in a proving OR clause must reject absence.
506    #[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    /// Order by 1..=4 distinct top-level ordered fields, then the primary key.
512    /// An explicitly listed primary key must be last. All fields share one
513    /// direction, reversed by `descending`. Prefer a complete ordered path.
514    /// Otherwise scan to completion while retaining the best `limit` rows within
515    /// 128 KiB of key/output buffers, then sort them. Non-identity DISTINCT retains
516    /// at most 32 distinct tuples before output selection. Work exhaustion refuses; no
517    /// cursor is supported by this fallback. DISTINCT requires an identity result
518    /// or an order covering exactly the projected fields. Equality terms may fix
519    /// leading index components. With `using_index`, require that path's order.
520    #[must_use]
521    pub fn order_by(mut self, fields: &[&'a str]) -> Self {
522        self.request.order_by(fields);
523        self
524    }
525    /// Replace the order with 1..=4 fields and their individual directions.
526    /// An explicit primary key must be last; otherwise append it ascending.
527    /// `descending()` reverses every direction, including that tie-breaker.
528    /// The same path proof and complete-sort bounds as `order_by` apply.
529    #[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    /// Reverse the complete result order, including its unique tie-breaker.
535    #[must_use]
536    pub fn descending(mut self) -> Self {
537        self.request.descending = true;
538        self
539    }
540    /// Return at most 1..=32 matching rows in this page.
541    /// Complete-collection DISTINCT refuses if the full result exceeds this cap.
542    /// Complete sorting applies this cap after examining the entire input; it
543    /// never relaxes the separate 32-matching-row retention bound.
544    /// For grouped aggregates, cap the complete selected result instead; use
545    /// `group_page` to set a retained grouped response's page size separately.
546    #[must_use]
547    pub fn limit(mut self, rows: usize) -> Self {
548        self.request.rows = rows;
549        self
550    }
551    /// Examine at most 1..=512 candidates, independently of the returned row limit.
552    #[must_use]
553    pub fn work_limit(mut self, candidates: usize) -> Self {
554        self.request.work = candidates;
555        self
556    }
557    /// Allow 1..=131072 encoded result-row bytes. Transport framing is host-owned.
558    #[must_use]
559    pub fn byte_limit(mut self, bytes: usize) -> Self {
560        self.request.bytes = bytes;
561        self
562    }
563    /// Continue this query; page resource limits may change between calls.
564    #[must_use]
565    pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
566        self.request.cursor = Some(cursor);
567        self
568    }
569    /// Admit and execute one page, then decode only its matching output rows.
570    /// # Errors
571    /// Refuses unsupported shapes, inexact operands, limits, invalid cursors and corruption.
572    /// A selected output row larger than the whole byte allowance returns `RowTooLarge`.
573    /// # Panics
574    /// Supplier corruption traps without repair, as for direct record reads.
575    pub fn fetch(self) -> Result<QueryPage<E>, Error> {
576        fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
577    }
578    /// Project matching top-level fields into an existing `#[record]` type.
579    /// Names, optionality and complete value definitions must match exactly.
580    /// The record is an output shape, not a new stored entity or schema entry.
581    /// Byte limits count projected bytes; all source fields still undergo validation.
582    /// # Errors
583    /// Refuses non-record/empty or incompatible output shapes, and the same failures
584    /// as `fetch`. A continuation must use the same selected field shape.
585    /// # Panics
586    /// Supplier corruption traps without repair, as for direct record reads.
587    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
593// Reuse named-record metadata/codecs rather than a second value tree or a
594// generic executor per output shape. The full transitive graph matters: named
595// links compare by identity, which alone cannot establish codec compatibility.
596fn 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
650// Grouping, distinct counts and collected DISTINCT share exact tuple equality.
651fn 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
679// Size and copy already validated projection spans using the same field mask.
680fn 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    // Non-orderable fields need only their validated optional tags, never key slots.
705    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        // Bound literal encoding even when a declaration's maximum exceeds one row.
732        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        // Admit every operand before selecting a path, even for empty or
802        // contradictory queries. The scanner consumes this one proven choice.
803        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        // Keep existing conjunction identities unchanged. A bounded clause mask
844        // distinguishes OR grouping without persisting another predicate model.
845        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                // Field names were admitted by order selection above.
859                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        // Preserve existing entity-result cursors. Projected shapes add a
871        // domain-separated suffix; output Rust names do not change semantics.
872        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
921// Cursor framing and DISTINCT equivalence boundaries use the same key decoder.
922fn 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// Admission, execution and request cleanup share one entity-independent boundary.
946// Only conversion of the returned bytes remains in the typed public terminals.
947#[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
980// Retained aggregates use the same traversal, but checkpoint at a work boundary.
981// Reserve a maximum candidate before the next fetch, including index/owner keys.
982const 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    // Each processed equivalence class is either wholly rejected or already
1017    // emitted. Inclusive byte retries point at an unreturned class instead.
1018    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        // Retained jobs may have consumed their lifetime candidate allowance.
1029        // An empty range can still establish completion; refuse a next candidate
1030        // before reading its value or touching the accumulator.
1031        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                        // Admission permits only Eq/Ne(Absent) here. Full decoding
1086                        // validated this optional tag and the entire present value.
1087                        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                // One validated match proves existence, even at the work boundary.
1106                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                // Completion has not been observed. Never expose partial reductions;
1144                // an exact-boundary scan may conservatively require more budget.
1145                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}