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::{
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/// Direction of one field in an explicit result order.
29#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30pub enum SortDirection {
31    /// Smaller values first; absence precedes present values.
32    Ascending,
33    /// Larger values first; absence follows present values.
34    Descending,
35}
36
37/// Exact comparison. Equality distinguishes absent values; ranges and pattern matches require presence.
38#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39#[repr(u8)]
40pub enum Comparison {
41    /// Equal, including two absent values.
42    Eq = 0,
43    /// Not equal, including absent versus present.
44    Ne = 1,
45    /// Present and less than the present operand.
46    Lt = 2,
47    /// Present and less than or equal to the present operand.
48    Le = 3,
49    /// Present and greater than the present operand.
50    Gt = 4,
51    /// Present and greater than or equal to the present operand.
52    Ge = 5,
53    /// Present Text or Blob starts with an exact operand of the same type.
54    /// Text uses UTF-8 bytes without normalization; Blob uses raw bytes.
55    /// Empty prefixes match all present values, including empty values; other types refuse.
56    StartsWith = 6,
57    /// Present Text or Blob ends with an exact operand of the same type.
58    /// Empty suffixes match all present values; text is not normalized.
59    EndsWith = 7,
60    /// A present list or set contains an equal scalar member, or a present Text
61    /// or Blob contains the exact byte sequence of the same type.
62    /// Empty substring needles match every present Text/Blob. Text uses UTF-8 without normalization.
63    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                // Compare escaped content, never the presence byte or terminator.
102                // In particular, optional empty text must not match suffix U+0001.
103                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                        // Prefixes start at a component boundary: escaping each
111                        // byte preserves prefix identity for Text and Blob alike.
112                        Self::StartsWith => actual.starts_with(operand),
113                        // A suffix starting after 00 starts inside an escaped zero
114                        // (00 FF), not at a raw-byte boundary. This matters for Blob
115                        // operands beginning FF; valid UTF-8 cannot begin there.
116                        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    // One side is absent. Equality/inequality are symmetric; execution,
131    // presence-only filters and sparse membership share this rule.
132    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
141// Both slices are validated component contents with presence/terminator removed.
142fn 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    // Only a Blob needle starting FF can match inside an escaped zero (00 FF).
150    // A valid overlapping match may follow. One raw search avoids repeatedly
151    // scanning long prefixes. Each temporary is bounded by the row byte limit.
152    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/// A bounded logical position, bound to database, schema, query and direction.
167/// It is not an authorization token or a snapshot. Callers may choose positions;
168/// the database revalidates all claims and retains no trusted progress counters.
169#[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    /// Encode the bounded continuation for an application's transport.
179    #[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    /// Decode framing; execution additionally checks query identity and key shape.
188    /// # Errors
189    /// Refuses unsupported versions, flags and oversized or incomplete frames.
190    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/// A bounded page. Empty rows do not mean completion when `next` is present.
203/// Ordinary queries are live; maintenance source pages read frozen input.
204#[derive(Debug)]
205pub struct QueryPage<T> {
206    /// Matching results in the selected total order.
207    pub rows: Vec<T>,
208    /// Resume position; only None establishes completion.
209    pub next: Option<QueryCursor>,
210    /// Examined primary/index candidates, including residual nonmatches and retries.
211    pub examined: usize,
212    /// Rows fetched; tracked separately from index candidates.
213    pub fetched: usize,
214    /// Sum of returned encoded entity/projected-record bytes, excluding transport overhead.
215    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                    // Output records replace the entity root, not an extra nested value.
243                    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/// A literal, row field or length threshold in a fluent predicate.
257#[derive(Clone, Copy, Debug, PartialEq, Eq)]
258pub enum QueryOperand<'a> {
259    /// Compare with this exact typed value.
260    Literal(IndexValue<'a>),
261    /// Compare the field's byte length (Text/Blob) or item count (list/set/map).
262    Length(u32),
263    /// Compare with another top-level field on the same row.
264    Field(&'a str),
265}
266
267struct Predicate<'a> {
268    field: &'a str,
269    comparison: Comparison,
270    operand: QueryOperand<'a>,
271    // Consecutive alternatives form one clause; clauses are ANDed.
272    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
308// Request construction depends on operand shapes, not the entity's Rust type.
309// Keep allocation and clause loops out of every typed builder instantiation.
310impl<'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(
347        &mut self,
348        field: &'a str,
349        values: impl ExactSizeIterator<Item = IndexValue<'a>>,
350    ) {
351        if values.len() == 0 || values.len() > MAX_TERMS - self.predicates.len() {
352            self.over_limit = true;
353            return;
354        }
355        for value in values {
356            self.filter(field, Comparison::Ne, QueryOperand::Literal(value));
357        }
358    }
359
360    #[inline(never)]
361    fn using_index(&mut self, name: &'a str, values: &[IndexValue<'a>]) {
362        if values.len() > 4 {
363            self.over_limit = true;
364        } else {
365            self.index = Some((name, values.to_vec()));
366        }
367    }
368
369    #[inline(never)]
370    fn order_by(&mut self, fields: &[&'a str]) {
371        self.order_descending = 0;
372        if fields.len() > 4 {
373            self.over_limit = true;
374        } else {
375            self.order = Some(fields.to_vec());
376        }
377    }
378
379    #[inline(never)]
380    fn order_by_each(&mut self, fields: &[(&'a str, SortDirection)]) {
381        if fields.len() > 4 {
382            self.over_limit = true;
383            return;
384        }
385        self.order = Some(Vec::with_capacity(fields.len()));
386        self.order_descending = 0;
387        for &(field, direction) in fields {
388            self.append_order(field, direction);
389        }
390    }
391
392    fn append_order(&mut self, field: &'a str, direction: SortDirection) {
393        let fields = self.order.get_or_insert_with(Vec::new);
394        if fields.len() == 4 {
395            self.over_limit = true;
396            return;
397        }
398        if direction == SortDirection::Descending {
399            self.order_descending |= 1 << fields.len();
400        }
401        fields.push(field);
402    }
403
404    fn primary_descending(&self, entity: &EntitySchema) -> bool {
405        self.order_descending != 0
406            && self.order.as_ref().is_some_and(|fields| {
407                fields.last() == Some(&entity.primary_key)
408                    && self.order_descending & (1 << (fields.len() - 1)) != 0
409            })
410    }
411}
412
413// Maintenance gets only bounded primary traversal, not a second query frontend.
414pub(super) fn source_page<M: Memory>(
415    map: &Map<M>,
416    entity: &EntitySchema,
417    binding: [u8; 32],
418    incarnation: [u8; 16],
419    cursor: Option<&QueryCursor>,
420    rows: usize,
421    bytes: usize,
422) -> Result<QueryPage<Vec<u8>>, Error> {
423    let request = Request {
424        rows,
425        work: rows,
426        bytes,
427        cursor,
428        ..Request::default()
429    };
430    let plan = Plan::admit(
431        entity,
432        &request,
433        binding,
434        incarnation,
435        None,
436        PlanOutput::Rows,
437    )?;
438    execute(map, entity, &request, &plan, None)
439}
440
441/// Fluent exact predicates over one entity. No callback executor is generated.
442/// Ordering uses primary order, an explicit index, a proven automatic path or
443/// bounded complete sorting. Work exhaustion never returns a sorted prefix.
444pub struct Query<'a, E, M: Memory> {
445    db: &'a Database<M>,
446    request: Request<'a>,
447    entity: PhantomData<E>,
448}
449impl<M: Memory> Database<M> {
450    /// Begin a live primary-key-ordered query. Admission occurs on `fetch`.
451    #[must_use]
452    pub fn query<E: Entity>(&self) -> Query<'_, E, M> {
453        Query {
454            db: self,
455            entity: PhantomData,
456            request: Request::default(),
457        }
458    }
459}
460impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
461    /// Remove duplicate output records. Proven leading index tuples use live
462    /// pages; identity projections need no duplicate tracking. Other projections scan to
463    /// completion in one call, retaining at most 32 tuples within 128 KiB.
464    /// That fallback preserves first-match traversal order, refuses cursors and
465    /// returns `Limit` if work, result count or combined bytes cannot fit; it
466    /// never returns a partial result. An individually oversized row returns
467    /// `RowTooLarge`. Comparison keys are bounded to 4096 bytes.
468    /// Non-identity sorted DISTINCT retains the best `limit` distinct tuples. Its order
469    /// must lead with all varying projected fields. A mandatory literal equality
470    /// fixes a field. Remove duplicates before applying `limit` and output bytes.
471    #[must_use]
472    pub fn distinct(mut self) -> Self {
473        self.request.distinct = true;
474        self
475    }
476
477    /// Add an AND term over a top-level field. Lists and sets support exact scalar membership with `Contains`.
478    /// Eq/Ne with `IndexValue::Absent` also accept any optional stored field,
479    /// including blobs and containers. Empty values are present, not absent.
480    /// All operands are admitted before storage reads, including contradictory terms.
481    /// On a primary traversal, mandatory Eq/Lt/Le/Gt/Ge primary-key comparisons
482    /// narrow the scanned range. On an index path, those comparisons can narrow
483    /// its first field after the admitted fixed prefix. Only examined rows
484    /// undergo integrity checks; oversized derived bounds remain residual filters.
485    /// Indexed StartsWith can seek that field's exact encoded Text/Blob prefix too.
486    #[must_use]
487    pub fn filter(
488        mut self,
489        field: &'a str,
490        comparison: Comparison,
491        value: impl Into<IndexValue<'a>>,
492    ) -> Self {
493        self.request
494            .filter(field, comparison, QueryOperand::Literal(value.into()));
495        self
496    }
497
498    /// Require an exact field value. Equivalent to `filter(field, Comparison::Eq, value)`.
499    #[must_use]
500    pub fn eq(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
501        self.filter(field, Comparison::Eq, value)
502    }
503
504    /// Require a different value, including absent versus present.
505    #[must_use]
506    pub fn ne(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
507        self.filter(field, Comparison::Ne, value)
508    }
509
510    /// Require a present field strictly below the supplied value.
511    #[must_use]
512    pub fn lt(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
513        self.filter(field, Comparison::Lt, value)
514    }
515
516    /// Require a present field at or below the supplied value.
517    #[must_use]
518    pub fn lte(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
519        self.filter(field, Comparison::Le, value)
520    }
521
522    /// Require a present field strictly above the supplied value.
523    #[must_use]
524    pub fn gt(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
525        self.filter(field, Comparison::Gt, value)
526    }
527
528    /// Require a present field at or above the supplied value.
529    #[must_use]
530    pub fn gte(self, field: &'a str, value: impl Into<IndexValue<'a>>) -> Self {
531        self.filter(field, Comparison::Ge, value)
532    }
533
534    /// Compare two top-level fields on the same row. Lists and sets support Contains
535    /// with a present scalar field of the element type. Text and Blob also
536    /// support StartsWith, EndsWith and Contains with a present right-hand field.
537    /// Types must match; Text and Blob bounds may differ within their respective families.
538    /// Two absent values are equal. An ordered comparison requires two present values.
539    #[must_use]
540    pub fn filter_fields(mut self, left: &'a str, comparison: Comparison, right: &'a str) -> Self {
541        self.request
542            .filter(left, comparison, QueryOperand::Field(right));
543        self
544    }
545
546    /// Compare UTF-8 bytes for Text, raw bytes for Blob, or the item count for a
547    /// list, set or map. Accepts Eq, Ne, Lt, Le, Gt and Ge. An absent field
548    /// matches Ne only; use Gt(0) for a present, nonempty value.
549    #[must_use]
550    pub fn filter_length(mut self, field: &'a str, comparison: Comparison, length: u32) -> Self {
551        self.request
552            .filter(field, comparison, QueryOperand::Length(length));
553        self
554    }
555
556    /// Match rows whose optional field has a value, including an empty value.
557    /// Required and unknown fields return `InvalidQuery` at admission.
558    #[must_use]
559    pub fn filter_present(self, field: &'a str) -> Self {
560        self.filter(field, Comparison::Ne, IndexValue::Absent)
561    }
562
563    /// Match rows whose optional field has no value.
564    /// Required and unknown fields return `InvalidQuery` at admission.
565    #[must_use]
566    pub fn filter_absent(self, field: &'a str) -> Self {
567        self.filter(field, Comparison::Eq, IndexValue::Absent)
568    }
569
570    /// Match a present field inside an inclusive range, ANDed with other filters.
571    /// Equivalent to `filter(field, Comparison::Ge, lower)` followed by
572    /// `filter(field, Comparison::Le, upper)`, including cursor/job identity.
573    /// Both exact operands are admitted and consume two of the eight comparisons.
574    /// Absent operands refuse; absent fields never match. Reversed bounds produce
575    /// no matches, without skipping admission of either operand or other filters.
576    #[must_use]
577    pub fn filter_between(
578        self,
579        field: &'a str,
580        lower: impl Into<IndexValue<'a>>,
581        upper: impl Into<IndexValue<'a>>,
582    ) -> Self {
583        self.filter(field, Comparison::Ge, lower)
584            .filter(field, Comparison::Le, upper)
585    }
586
587    /// Match a present field strictly outside an inclusive range.
588    /// Equivalent to one `filter_any` clause containing `Lt lower` then `Gt upper`,
589    /// including cursor/job identity. Both exact operands consume filter terms.
590    /// Absent operands refuse and absent fields never match; this is not a general
591    /// negation of `filter_between`. Equal bounds exclude that value; reversed
592    /// bounds match every present value, once. Uses the existing single traversal
593    /// and work budget, without seeking separate ranges for the two alternatives.
594    #[must_use]
595    pub fn filter_not_between(
596        self,
597        field: &'a str,
598        lower: impl Into<IndexValue<'a>>,
599        upper: impl Into<IndexValue<'a>>,
600    ) -> Self {
601        self.filter_any(&[
602            (field, Comparison::Lt, lower.into()),
603            (field, Comparison::Gt, upper.into()),
604        ])
605    }
606
607    /// Match `lower <= field && field <= upper` using three top-level fields of the row.
608    /// Both comparisons require present values of compatible types. Equal endpoints
609    /// are inclusive. Uses the same two comparison terms and continuation as the
610    /// equivalent chained `filter_fields` calls.
611    #[must_use]
612    pub fn filter_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
613        self.filter_fields(field, Comparison::Ge, lower)
614            .filter_fields(field, Comparison::Le, upper)
615    }
616
617    /// Match `field < lower || field > upper` using fields of the same row.
618    /// A missing bound makes only its own comparison false. A missing tested field
619    /// never matches. Uses one OR clause and the same two comparison terms and
620    /// continuation as the equivalent `filter_any_operands` call.
621    #[must_use]
622    pub fn filter_not_between_fields(self, field: &'a str, lower: &'a str, upper: &'a str) -> Self {
623        self.filter_any_operands(&[
624            (field, Comparison::Lt, QueryOperand::Field(lower)),
625            (field, Comparison::Gt, QueryOperand::Field(upper)),
626        ])
627    }
628
629    /// Add an OR clause of exact top-level comparisons, ANDed with other filters.
630    /// Each clause must contain at least one comparison; all filters together
631    /// may contain at most eight. Empty/oversized clauses refuse with `Error::Limit`
632    /// at execution. Every operand is admitted, even if another alternative matches.
633    /// Uses one ordered traversal, without union scans or duplicate rows. Alternatives
634    /// do not establish fixed index prefixes; a one-term clause behaves like `filter`.
635    #[must_use]
636    pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
637        self.request.or_clause(
638            alternatives
639                .iter()
640                .map(|&(field, op, value)| (field, op, QueryOperand::Literal(value))),
641        );
642        self
643    }
644
645    /// Add one OR clause of literal, field-to-field or length comparisons.
646    /// Each alternative follows its corresponding single-filter admission rules.
647    /// All alternatives share the eight-comparison budget with the other filters.
648    /// Literal-only clauses have the same cursor and job identity as `filter_any`.
649    #[must_use]
650    pub fn filter_any_operands(
651        mut self,
652        alternatives: &[(&'a str, Comparison, QueryOperand<'a>)],
653    ) -> Self {
654        self.request.or_clause(alternatives.iter().copied());
655        self
656    }
657
658    /// Match a field against any supplied exact value, ANDed with other filters.
659    /// Equivalent to `filter_any` with equality comparisons in the supplied order.
660    /// Include `None` in a slice of optional values to match an absent field.
661    /// When the field is the next traversal key component, seek between the smallest
662    /// and largest member, including all tied owners. Interior candidates still consume work.
663    /// Repeated members never repeat rows, but each counts toward the shared
664    /// eight-comparison limit. Empty or oversized lists refuse with `Error::Limit`.
665    /// Every member is admitted before reading; there is no coercion, sorting or
666    /// deduplication of operands. Reordering members changes cursor/job identity.
667    #[must_use]
668    pub fn filter_in(
669        mut self,
670        field: &'a str,
671        values: &[impl Copy + Into<IndexValue<'a>>],
672    ) -> Self {
673        self.request.or_clause(
674            values
675                .iter()
676                .copied()
677                .map(|value| (field, Comparison::Eq, QueryOperand::Literal(value.into()))),
678        );
679        self
680    }
681
682    /// Exclude every supplied exact value, ANDed with other filters.
683    /// Equivalent to consecutive `filter(field, Comparison::Ne, value)` calls
684    /// in the supplied order. Absent fields match unless absence is explicitly
685    /// excluded. Empty lists refuse; all members, including duplicates, count
686    /// toward the shared eight-comparison budget. Every operand is admitted.
687    /// The equivalent inequality chain shares cursor/job identity; reordering
688    /// the list changes that identity. No coercion or deduplication is performed.
689    #[must_use]
690    pub fn filter_not_in(
691        mut self,
692        field: &'a str,
693        values: &[impl Copy + Into<IndexValue<'a>>],
694    ) -> Self {
695        self.request
696            .filter_not_in(field, values.iter().copied().map(Into::into));
697        self
698    }
699
700    /// Select index order and exact leading components (at most four).
701    /// All rows matching this prefix are considered. Sparse indexes require
702    /// every optional indexed component to be proven present by the prefix or
703    /// filters. Every alternative in a proving OR clause must reject absence.
704    #[must_use]
705    pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
706        self.request.using_index(name, values);
707        self
708    }
709
710    /// Append an ascending sort field. Earlier fields take precedence.
711    /// The same field, work and continuation rules as [`Self::order_by_each`] apply.
712    #[must_use]
713    pub fn order_asc(mut self, field: &'a str) -> Self {
714        self.request.append_order(field, SortDirection::Ascending);
715        self
716    }
717
718    /// Append a descending sort field. An implicit primary-key tie-breaker
719    /// stays ascending; append the primary key explicitly to choose its direction.
720    #[must_use]
721    pub fn order_desc(mut self, field: &'a str) -> Self {
722        self.request.append_order(field, SortDirection::Descending);
723        self
724    }
725
726    /// Replace the current order with 1..=4 distinct top-level ordered fields, then the primary key.
727    /// An explicitly listed primary key must be last. All fields share one
728    /// direction, reversed by `descending`. Prefer a complete ordered path.
729    /// Otherwise scan to completion while retaining the best `limit` rows within
730    /// 128 KiB of key/output buffers, then sort them. Non-identity DISTINCT retains
731    /// the best `limit` distinct tuples. Work exhaustion refuses; no
732    /// cursor is supported by this fallback. DISTINCT requires an identity result
733    /// or an order led by all varying projected fields. Equality terms may fix
734    /// leading index components. With `using_index`, require that path's order.
735    #[must_use]
736    pub fn order_by(mut self, fields: &[&'a str]) -> Self {
737        self.request.order_by(fields);
738        self
739    }
740
741    /// Replace the order with 1..=4 fields and their individual directions.
742    /// An explicit primary key must be last; otherwise append it ascending.
743    /// `descending()` reverses every direction, including that tie-breaker.
744    /// The same path proof and complete-sort bounds as `order_by` apply.
745    #[must_use]
746    pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
747        self.request.order_by_each(fields);
748        self
749    }
750
751    /// Reverse the complete result order, including its unique tie-breaker.
752    #[must_use]
753    pub fn descending(mut self) -> Self {
754        self.request.descending = true;
755        self
756    }
757
758    /// Return at most 1..=32 matching rows in this page.
759    /// Complete-collection DISTINCT refuses if the full result exceeds this cap.
760    /// Complete sorting applies this cap after examining the entire input; it
761    /// never relaxes the separate 32-matching-row retention bound.
762    /// For grouped aggregates, cap the complete selected result instead; use
763    /// `group_page` to set a retained grouped response's page size separately.
764    #[must_use]
765    pub fn limit(mut self, rows: usize) -> Self {
766        self.request.rows = rows;
767        self
768    }
769
770    /// Examine at most 1..=512 candidates, independently of the returned row limit.
771    #[must_use]
772    pub fn work_limit(mut self, candidates: usize) -> Self {
773        self.request.work = candidates;
774        self
775    }
776
777    /// Exercise output exhaustion with a small response in qualification fixtures.
778    #[cfg(feature = "test-support")]
779    #[doc(hidden)]
780    #[must_use]
781    pub fn test_output_limit(mut self, bytes: usize) -> Self {
782        self.request.bytes = bytes;
783        self
784    }
785
786    /// Continue this query; page resource limits may change between calls.
787    #[must_use]
788    pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
789        self.request.cursor = Some(cursor);
790        self
791    }
792
793    /// Admit and execute one page, then decode only its matching output rows.
794    /// # Errors
795    /// Refuses unsupported shapes, inexact operands, limits, invalid cursors and corruption.
796    /// A selected output row larger than the whole byte allowance returns `RowTooLarge`.
797    /// # Panics
798    /// Supplier corruption traps without repair, as for direct record reads.
799    pub fn fetch(self) -> Result<QueryPage<E>, Error> {
800        fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
801    }
802
803    /// Return the first matching entity in query order, or `None` on a proven miss.
804    /// Uses a one-row page. For partial pages with resumable progress use `fetch`.
805    /// # Errors
806    /// Returns the same admission and storage errors as `fetch`. Returns `Limit`
807    /// if the work budget ends before a match or exhaustion is established.
808    pub fn first(self) -> Result<Option<E>, Error> {
809        let mut page = self.probe_matches(1)?;
810        match page.rows.pop() {
811            None if page.next.is_some() => Err(Error::Limit),
812            result => Ok(result),
813        }
814    }
815
816    /// Return the only match, or `None` when the query is exhausted without one.
817    /// A valid row limit is overridden to probe for two matches. Applies to the
818    /// whole query, so a continuation is refused.
819    /// # Errors
820    /// Returns `MultipleMatches` on a second match and `Limit` if the page is
821    /// incomplete before cardinality is known. Ordinary fetch errors apply.
822    pub fn try_one(self) -> Result<Option<E>, Error> {
823        if self.request.cursor.is_some() {
824            return Err(Error::InvalidQuery);
825        }
826        let mut page = self.probe_matches(2)?;
827        if page.rows.len() == 2 {
828            return Err(Error::MultipleMatches);
829        }
830        if page.next.is_some() {
831            return Err(Error::Limit);
832        }
833        Ok(page.rows.pop())
834    }
835
836    fn probe_matches(self, rows: usize) -> Result<QueryPage<E>, Error> {
837        if !(1..=32).contains(&self.request.rows) {
838            return Err(Error::Limit);
839        }
840        self.limit(rows).fetch()
841    }
842
843    /// Project matching top-level fields into an existing `#[record]` type.
844    /// Names, optionality and complete value definitions must match exactly.
845    /// The record is an output shape, not a new stored entity or schema entry.
846    /// Byte limits count projected bytes; all source fields still undergo validation.
847    /// # Errors
848    /// Refuses non-record/empty or incompatible output shapes, and the same failures
849    /// as `fetch`. A continuation must use the same selected field shape.
850    /// # Panics
851    /// Supplier corruption traps without repair, as for direct record reads.
852    pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
853        let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
854        raw.decode_projection()
855    }
856}
857
858// Reuse named-record metadata/codecs rather than a second value tree or a
859// generic executor per output shape. The full transitive graph matters: named
860// links compare by identity, which alone cannot establish codec compatibility.
861fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
862    let TypeBody::Record(fields) = &output.body else {
863        return Err(Error::InvalidQuery);
864    };
865    if fields.is_empty()
866        || fields.len() > crate::schema::MAX_FIELDS
867        || fields.windows(2).any(|w| w[0].name >= w[1].name)
868    {
869        return Err(Error::InvalidQuery);
870    }
871    let mut source = TypeGraph::default();
872    let mut target = TypeGraph::default();
873    let mut mask = 0;
874    for field in *fields {
875        let position = entity
876            .fields
877            .iter()
878            .position(|f| f.name == field.name)
879            .ok_or(Error::InvalidQuery)?;
880        let stored = &entity.fields[position];
881        if stored.value != field.value || stored.optional != field.optional {
882            return Err(Error::InvalidQuery);
883        }
884        source
885            .include(stored.value)
886            .map_err(|_| Error::InvalidQuery)?;
887        target
888            .include(field.value)
889            .map_err(|_| Error::InvalidQuery)?;
890        mask |= 1 << position;
891    }
892    if !source.contains(&target) {
893        return Err(Error::InvalidQuery);
894    }
895    Ok(mask)
896}
897
898struct Term {
899    position: usize,
900    comparison: Comparison,
901    operand: TermOperand,
902    or_next: bool,
903}
904
905enum TermOperand {
906    Literal {
907        bytes: Vec<u8>,
908        absent: bool,
909    },
910    Member {
911        item: FieldType,
912        needle: MemberNeedle,
913    },
914    Field(usize),
915    Length(u32),
916}
917
918enum MemberNeedle {
919    Literal(Vec<u8>),
920    Field(usize),
921}
922
923fn member_type(field: FieldType) -> Option<FieldType> {
924    match key::operand_type(field) {
925        FieldType::List { item, .. } => Some(*item),
926        FieldType::Named(link) => match (link.definition)().body {
927            TypeBody::Set { item, .. } => Some(item),
928            _ => None,
929        },
930        _ => None,
931    }
932}
933
934// inspect_fields has already validated every item, including the tail after a match.
935fn contains_member(
936    span: &[u8],
937    optional: bool,
938    item: FieldType,
939    needle: &[u8],
940    scratch: &mut Vec<u8>,
941) -> Result<bool, Error> {
942    let mut reader = Decoder::new(span)?;
943    if optional && !reader.boolean()? {
944        return Ok(false);
945    }
946    for _ in 0..reader.nat32()? {
947        scratch.clear();
948        IndexValue::read(&mut reader, item)?.append_component(false, scratch);
949        if scratch.as_slice() == needle {
950            return Ok(true);
951        }
952    }
953    Ok(false)
954}
955
956fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
957    for (i, field) in entity.fields.iter().enumerate() {
958        if mask & (1 << i) != 0 && !key::supports(field.value) {
959            return Err(Error::InvalidQuery);
960        }
961    }
962    Ok(())
963}
964
965// Grouping, distinct counts and collected DISTINCT share exact tuple equality.
966fn comparison_key(
967    entity: &EntitySchema,
968    mask: u16,
969    values: &[IndexValue<'_>],
970) -> Result<Vec<u8>, Error> {
971    let mut key = Vec::new();
972    for (i, field) in entity.fields.iter().enumerate() {
973        if mask & (1 << i) != 0 {
974            values[i].append_component(field.optional, &mut key);
975            if key.len() > MAX_COMPARISON_KEY {
976                return Err(Error::Limit);
977            }
978        }
979    }
980    Ok(key)
981}
982
983fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
984    if size > limit {
985        return Err(Error::RowTooLarge);
986    }
987    if size > limit - *used {
988        return Err(Error::Limit);
989    }
990    *used += size;
991    Ok(())
992}
993
994// Size and copy already validated projection spans using the same field mask.
995fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
996    spans
997        .iter()
998        .enumerate()
999        .filter(|(i, _)| mask & (1 << i) != 0)
1000        .map(|(_, (start, end))| usize::from(end - start))
1001        .sum()
1002}
1003
1004fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
1005    let mut output = Vec::with_capacity(size);
1006    for (i, &(start, end)) in spans.iter().enumerate() {
1007        if mask & (1 << i) != 0 {
1008            output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
1009        }
1010    }
1011    output
1012}
1013#[derive(Clone, Copy)]
1014enum PlanOutput {
1015    Rows,
1016    Aggregate { grouped: bool },
1017}
1018
1019struct Plan<'a> {
1020    primary: usize,
1021    index: Option<&'a IndexSchema>,
1022    prefix: Vec<u8>,
1023    fixed_components: usize,
1024    terms: Vec<Term>,
1025    selected: u16,
1026    // Non-orderable fields need only their validated optional tags, never key slots.
1027    span_fields: u16,
1028    binding: [u8; 32],
1029    projection: Option<u16>,
1030    distinct: distinct::Strategy,
1031    sort: Option<Vec<(usize, bool)>>,
1032    descending: bool,
1033}
1034impl<'a> Plan<'a> {
1035    fn use_index(&mut self, entity: &EntitySchema, path: order::IndexPath<'a>) {
1036        self.index = Some(path.index);
1037        self.prefix = path.prefix;
1038        self.fixed_components = path.fixed;
1039        self.selected |= entity.key_fields();
1040    }
1041
1042    fn admit(
1043        entity: &'a EntitySchema,
1044        request: &Request<'_>,
1045        schema: [u8; 32],
1046        incarnation: [u8; 16],
1047        projection: Option<&TypeSchema>,
1048        output: PlanOutput,
1049    ) -> Result<Self, Error> {
1050        if request.over_limit
1051            || !(1..=32).contains(&request.rows)
1052            || !(1..=MAX_WORK).contains(&request.work)
1053            || !(1..=MAX_OUTPUT).contains(&request.bytes)
1054        {
1055            return Err(Error::Limit);
1056        }
1057        if !matches!(output, PlanOutput::Aggregate { grouped: true }) && !request.groups.is_empty()
1058        {
1059            return Err(Error::InvalidQuery);
1060        }
1061        // Bound literal encoding even when a declaration's maximum exceeds one row.
1062        for value in request
1063            .predicates
1064            .iter()
1065            .filter_map(|p| match &p.operand {
1066                QueryOperand::Literal(value) => Some(value),
1067                QueryOperand::Field(_) | QueryOperand::Length(_) => None,
1068            })
1069            .chain(request.index.iter().flat_map(|(_, values)| values.iter()))
1070        {
1071            if match value {
1072                IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
1073                IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
1074                _ => false,
1075            } {
1076                return Err(Error::Limit);
1077            }
1078        }
1079        let primary = entity
1080            .fields
1081            .iter()
1082            .position(|f| f.name == entity.primary_key && !f.optional)
1083            .ok_or(Error::InvalidQuery)?;
1084        let mut plan = Self {
1085            primary,
1086            index: None,
1087            prefix: prefix(2, entity.id),
1088            fixed_components: 0,
1089            terms: Vec::new(),
1090            selected: 1 << primary,
1091            span_fields: 0,
1092            binding: [0; 32],
1093            projection: projection
1094                .map(|output| admit_projection(entity, output))
1095                .transpose()?,
1096            distinct: distinct::Strategy::Identity,
1097            sort: None,
1098            descending: request.descending ^ request.primary_descending(entity),
1099        };
1100        for predicate in &request.predicates {
1101            let position = entity
1102                .fields
1103                .iter()
1104                .position(|f| f.name == predicate.field)
1105                .ok_or(Error::InvalidQuery)?;
1106            let field = &entity.fields[position];
1107            let member = if predicate.comparison == Comparison::Contains {
1108                member_type(field.value)
1109            } else {
1110                None
1111            };
1112            let operand = match predicate.operand {
1113                QueryOperand::Length(length) => {
1114                    let supported = match key::operand_type(field.value) {
1115                        FieldType::Text { .. }
1116                        | FieldType::Blob { .. }
1117                        | FieldType::List { .. } => true,
1118                        FieldType::Named(link) => matches!(
1119                            (link.definition)().body,
1120                            TypeBody::Map { .. } | TypeBody::Set { .. }
1121                        ),
1122                        _ => false,
1123                    };
1124                    if !supported || !predicate.comparison.is_relational() {
1125                        return Err(Error::InvalidQuery);
1126                    }
1127                    plan.span_fields |= 1 << position;
1128                    TermOperand::Length(length)
1129                }
1130                QueryOperand::Field(name) => {
1131                    let right = entity
1132                        .fields
1133                        .iter()
1134                        .position(|f| f.name == name)
1135                        .ok_or(Error::InvalidQuery)?;
1136                    let right_type = entity.fields[right].value;
1137                    let left_type = member.unwrap_or(field.value);
1138                    let compatible = left_type == right_type
1139                        || matches!(
1140                            (left_type, right_type),
1141                            (FieldType::Text { .. }, FieldType::Text { .. })
1142                                | (FieldType::Blob { .. }, FieldType::Blob { .. })
1143                        );
1144                    if !compatible
1145                        || !key::supports(left_type)
1146                        || (member.is_none() && !predicate.comparison.supports_scalar(left_type))
1147                    {
1148                        return Err(Error::InvalidQuery);
1149                    }
1150                    plan.selected |= 1 << right;
1151                    if let Some(item) = member {
1152                        plan.span_fields |= 1 << position;
1153                        TermOperand::Member {
1154                            item,
1155                            needle: MemberNeedle::Field(right),
1156                        }
1157                    } else {
1158                        plan.selected |= 1 << position;
1159                        TermOperand::Field(right)
1160                    }
1161                }
1162                QueryOperand::Literal(value) => {
1163                    if let Some(item) = member {
1164                        if !key::supports(item) {
1165                            return Err(Error::InvalidQuery);
1166                        }
1167                        value.admit(item, false)?;
1168                        let mut bytes = Vec::new();
1169                        value.append_component(false, &mut bytes);
1170                        plan.span_fields |= 1 << position;
1171                        TermOperand::Member {
1172                            item,
1173                            needle: MemberNeedle::Literal(bytes),
1174                        }
1175                    } else {
1176                        let absent = value == IndexValue::Absent;
1177                        if key::supports(field.value) {
1178                            plan.selected |= 1 << position;
1179                        } else if absent
1180                            && matches!(predicate.comparison, Comparison::Eq | Comparison::Ne)
1181                        {
1182                            plan.span_fields |= 1 << position;
1183                        } else {
1184                            return Err(Error::InvalidQuery);
1185                        }
1186                        predicate
1187                            .comparison
1188                            .admit(field.value, field.optional, value)?;
1189                        let mut bytes = Vec::new();
1190                        value.append_component(field.optional, &mut bytes);
1191                        TermOperand::Literal { bytes, absent }
1192                    }
1193                }
1194            };
1195            plan.terms.push(Term {
1196                position,
1197                comparison: predicate.comparison,
1198                operand,
1199                or_next: predicate.or_next,
1200            });
1201        }
1202        // Admit every operand before selecting a path, even for empty or
1203        // contradictory queries. The scanner consumes this one proven choice.
1204        match order::select(entity, request, output)? {
1205            order::Path::Primary => {}
1206            order::Path::Index(path) => plan.use_index(entity, path),
1207            order::Path::Sort(fields) => {
1208                for &(position, _) in &fields {
1209                    plan.selected |= 1 << position;
1210                }
1211                plan.sort = Some(fields);
1212            }
1213        }
1214        if request.distinct {
1215            plan.distinct = distinct::admit(
1216                entity,
1217                request,
1218                plan.projection,
1219                plan.index,
1220                plan.fixed_components,
1221                plan.sort.is_some(),
1222            )?;
1223            if plan.distinct == distinct::Strategy::Complete {
1224                plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
1225            }
1226        }
1227        let mut hash = Sha256::new();
1228        hash.update(b"ic-db:query:v1\0");
1229        hash.update(schema);
1230        hash.update(incarnation);
1231        hash.update([u8::from(request.descending)]);
1232        hash.update((plan.prefix.len() as u32).to_le_bytes());
1233        hash.update(&plan.prefix);
1234        for term in &plan.terms {
1235            hash.update([term.position as u8, term.comparison as u8]);
1236            match &term.operand {
1237                TermOperand::Literal { bytes, .. }
1238                | TermOperand::Member {
1239                    needle: MemberNeedle::Literal(bytes),
1240                    ..
1241                } => {
1242                    hash.update((bytes.len() as u32).to_le_bytes());
1243                    hash.update(bytes);
1244                }
1245                TermOperand::Length(length) => {
1246                    hash.update((u32::MAX - 1).to_le_bytes());
1247                    hash.update(length.to_le_bytes());
1248                }
1249                TermOperand::Field(right)
1250                | TermOperand::Member {
1251                    needle: MemberNeedle::Field(right),
1252                    ..
1253                } => {
1254                    // Outside the bounded literal length domain.
1255                    hash.update(u32::MAX.to_le_bytes());
1256                    hash.update([*right as u8]);
1257                }
1258            }
1259        }
1260        // Keep existing conjunction identities unchanged. A bounded clause mask
1261        // distinguishes OR grouping without persisting another predicate model.
1262        let clauses = plan
1263            .terms
1264            .iter()
1265            .enumerate()
1266            .fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
1267        if clauses != 0 {
1268            hash.update(b"or-clauses\0");
1269            hash.update([clauses]);
1270        }
1271        if let Some(order) = &request.order {
1272            hash.update(b"order\0");
1273            hash.update([order.len() as u8]);
1274            for name in order {
1275                // Field names were admitted by order selection above.
1276                hash.update([entity
1277                    .fields
1278                    .iter()
1279                    .position(|f| f.name == *name)
1280                    .ok_or(Error::InvalidQuery)? as u8]);
1281            }
1282        }
1283        if request.order_descending != 0 {
1284            hash.update(b"order-directions\0");
1285            hash.update([request.order_descending]);
1286        }
1287        // Preserve existing entity-result cursors. Projected shapes add a
1288        // domain-separated suffix; output Rust names do not change semantics.
1289        if let Some(mask) = plan.projection {
1290            hash.update(b"projection\0");
1291            hash.update(mask.to_le_bytes());
1292        }
1293        if request.distinct {
1294            hash.update(b"distinct\0");
1295        }
1296        plan.binding = hash.finalize().into();
1297        if let Some(cursor) = request.cursor {
1298            if cursor.binding != plan.binding {
1299                return Err(Error::InvalidCursor);
1300            }
1301            plan.validate_position(entity, &cursor.position)
1302                .map_err(|_| Error::InvalidCursor)?;
1303        }
1304        Ok(plan)
1305    }
1306
1307    fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
1308        if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
1309            return Err(Error::InvalidCursor);
1310        }
1311        if let Some(index) = self.index {
1312            let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
1313            for name in index.fields {
1314                consume_index_component(entity, index, name, &mut remaining)?;
1315            }
1316            if !index.unique {
1317                key::consume(&mut remaining, entity.key_type()?)?;
1318            }
1319            if !remaining.is_empty() {
1320                return Err(Error::InvalidCursor);
1321            }
1322        } else {
1323            RowKey::decode(
1324                bytes.get(5..).ok_or(Error::InvalidCursor)?,
1325                entity.key_type()?,
1326            )?;
1327        }
1328        Ok(())
1329    }
1330
1331    fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
1332        QueryCursor {
1333            binding: self.binding,
1334            position: position.to_vec(),
1335            inclusive,
1336        }
1337    }
1338}
1339
1340// Cursor framing and DISTINCT equivalence boundaries use the same key decoder.
1341fn consume_index_component(
1342    entity: &EntitySchema,
1343    index: &IndexSchema,
1344    name: &str,
1345    remaining: &mut &[u8],
1346) -> Result<(), Error> {
1347    let field = entity
1348        .fields
1349        .iter()
1350        .find(|f| f.name == name)
1351        .ok_or(Error::InvalidQuery)?;
1352    if field.optional {
1353        let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
1354        *remaining = rest;
1355        match presence {
1356            0 if !index.present_only => return Ok(()),
1357            1 => {}
1358            _ => return Err(Error::InvalidCursor),
1359        }
1360    }
1361    key::consume(remaining, field.value)
1362}
1363
1364// Admission, execution and request cleanup share one entity-independent boundary.
1365// Only conversion of the returned bytes remains in the typed public terminals.
1366#[inline(never)]
1367#[expect(
1368    clippy::needless_pass_by_value,
1369    reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
1370)]
1371fn fetch_rows<M: Memory>(
1372    db: &Database<M>,
1373    entity: &EntitySchema,
1374    request: Request<'_>,
1375    projection: Option<&TypeSchema>,
1376) -> Result<QueryPage<Vec<u8>>, Error> {
1377    db.schema.admits(entity)?;
1378    let plan = Plan::admit(
1379        entity,
1380        &request,
1381        db.schema.fingerprint(),
1382        db.incarnation,
1383        projection,
1384        PlanOutput::Rows,
1385    )?;
1386    execute(&db.map, entity, &request, &plan, None)
1387}
1388
1389fn execute<M: Memory>(
1390    map: &Map<M>,
1391    entity: &EntitySchema,
1392    request: &Request<'_>,
1393    plan: &Plan<'_>,
1394    mut aggregate: Option<aggregate::Accumulator<'_>>,
1395) -> Result<QueryPage<Vec<u8>>, Error> {
1396    execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
1397}
1398
1399// Retained aggregates use the same traversal, but checkpoint at a work boundary.
1400// Reserve a maximum candidate before the next fetch, including index/owner keys.
1401const STEP_INPUT_BYTES: usize = 64 * 1024;
1402const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
1403
1404fn execute_inner<M: Memory>(
1405    map: &Map<M>,
1406    entity: &EntitySchema,
1407    request: &Request<'_>,
1408    plan: &Plan<'_>,
1409    mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
1410    mut input_bytes: Option<&mut usize>,
1411) -> Result<QueryPage<Vec<u8>>, Error> {
1412    let mut page = QueryPage {
1413        rows: Vec::new(),
1414        next: None,
1415        examined: 0,
1416        fetched: 0,
1417        output_bytes: 0,
1418    };
1419    let Some(bounds) = range::bounds(entity, request, plan)? else {
1420        return Ok(page);
1421    };
1422    let terminal = range::terminal_key(&bounds, plan.descending);
1423    let mut entries = map.range((bounds.0.as_ref(), bounds.1.as_ref()));
1424    let mut collected = if plan.distinct == distinct::Strategy::Complete {
1425        Some(distinct::Collection::new(
1426            plan.projection.ok_or(Error::InvalidQuery)?,
1427        ))
1428    } else {
1429        None
1430    };
1431    let mut sorted = plan
1432        .sort
1433        .as_ref()
1434        .map(|_| sort::Collection::new(request, plan.distinct));
1435    let mut component = Vec::new();
1436    let mut right_component = Vec::new();
1437    // Each processed equivalence class is either wholly rejected or already
1438    // emitted. Inclusive byte retries point at an unreturned class instead.
1439    let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
1440        distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
1441    } else {
1442        None
1443    };
1444    let primary_type = entity.fields[plan.primary].value;
1445    while let Some(entry) = if plan.descending {
1446        entries.next_back()
1447    } else {
1448        entries.next()
1449    } {
1450        // Retained jobs may have consumed their lifetime candidate allowance.
1451        // An empty range can still establish completion; refuse a next candidate
1452        // before reading its value or touching the accumulator.
1453        if request.work == 0 {
1454            return Err(Error::Limit);
1455        }
1456        page.examined += 1;
1457        let stored_key = entry.key();
1458        let mut read_bytes = stored_key.len();
1459        let (owner, bytes) = if plan.index.is_some() {
1460            let owner_bytes = entry.value();
1461            read_bytes += owner_bytes.len();
1462            let owner = RowKey::decode(&owner_bytes, primary_type)?;
1463            let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
1464            (owner, bytes)
1465        } else {
1466            (
1467                RowKey::decode(&stored_key[5..], primary_type)?,
1468                entry.value(),
1469            )
1470        };
1471        if let Some(used) = input_bytes.as_deref_mut() {
1472            read_bytes += bytes.len();
1473            if read_bytes > CANDIDATE_BYTES {
1474                return Err(Error::Corrupt);
1475            }
1476            *used += read_bytes;
1477        }
1478        page.fetched += 1;
1479        let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
1480        let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
1481        entity.inspect_fields(
1482            &bytes,
1483            plan.selected,
1484            &mut values,
1485            (plan.span_fields != 0
1486                || plan.projection.is_some()
1487                || aggregate.as_ref().is_some_and(|a| a.needs_spans()))
1488            .then_some(&mut spans),
1489        )?;
1490        if RowKey::from_index(values[plan.primary])? != owner {
1491            return Err(Error::Corrupt);
1492        }
1493        if plan.index.is_some() {
1494            validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
1495        }
1496        let mut accepts = |term: &Term| -> Result<bool, Error> {
1497            let value = values[term.position];
1498            component.clear();
1499            let (operand, optional) = match &term.operand {
1500                TermOperand::Literal { absent: true, .. }
1501                    if plan.span_fields & (1 << term.position) != 0 =>
1502                {
1503                    let absent = bytes[usize::from(spans[term.position].0)] == 0;
1504                    return Ok(term.comparison.accepts_absent(absent));
1505                }
1506                TermOperand::Member { item, needle } => {
1507                    let needle = match needle {
1508                        MemberNeedle::Literal(bytes) => bytes.as_slice(),
1509                        MemberNeedle::Field(right) => {
1510                            let value = values[*right];
1511                            if value == IndexValue::Absent {
1512                                return Ok(false);
1513                            }
1514                            right_component.clear();
1515                            value.append_component(false, &mut right_component);
1516                            &right_component
1517                        }
1518                    };
1519                    let (start, end) = spans[term.position];
1520                    return contains_member(
1521                        &bytes[usize::from(start)..usize::from(end)],
1522                        entity.fields[term.position].optional,
1523                        *item,
1524                        needle,
1525                        &mut component,
1526                    );
1527                }
1528                TermOperand::Length(length) => {
1529                    let (start, end) = spans[term.position];
1530                    let span = &bytes[usize::from(start)..usize::from(end)];
1531                    let actual =
1532                        crate::codec::validated_length(span, entity.fields[term.position].optional)
1533                            .map(u32::to_be_bytes);
1534                    return Ok(term.comparison.accepts(
1535                        actual.as_ref().map(|v| v.as_slice()),
1536                        Some(&length.to_be_bytes()),
1537                        false,
1538                    ));
1539                }
1540                TermOperand::Literal { bytes, absent } => (
1541                    (!absent).then_some(bytes.as_slice()),
1542                    entity.fields[term.position].optional,
1543                ),
1544                TermOperand::Field(right) => {
1545                    let rhs = values[*right];
1546                    right_component.clear();
1547                    rhs.append_component(false, &mut right_component);
1548                    (
1549                        (rhs != IndexValue::Absent).then_some(right_component.as_slice()),
1550                        false,
1551                    )
1552                }
1553            };
1554            value.append_component(optional, &mut component);
1555            Ok(term.comparison.accepts(
1556                (value != IndexValue::Absent).then_some(component.as_slice()),
1557                operand,
1558                optional,
1559            ))
1560        };
1561        let matches = 'matches: {
1562            'clause: for clause in plan.terms.split_inclusive(|term| !term.or_next) {
1563                for term in clause {
1564                    if accepts(term)? {
1565                        continue 'clause;
1566                    }
1567                }
1568                break 'matches false;
1569            }
1570            true
1571        };
1572        let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
1573        let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
1574        if matches && let Some(accumulator) = aggregate.as_mut() {
1575            accumulator.push(entity, &values, &bytes, &spans)?;
1576            if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
1577                // One validated match proves existence, even at the work boundary.
1578                return Ok(page);
1579            }
1580        } else if matches && let Some(collection) = collected.as_mut() {
1581            collection.push(entity, request, &values, &bytes, &spans)?;
1582        } else if matches && let Some(collection) = sorted.as_mut() {
1583            collection.push(entity, plan, &values, &bytes, &spans)?;
1584        } else if matches && !duplicate {
1585            let size = plan
1586                .projection
1587                .map_or(bytes.len(), |mask| projection_size(&spans, mask));
1588            if size > request.bytes {
1589                return Err(Error::RowTooLarge);
1590            }
1591            if size > request.bytes - page.output_bytes {
1592                page.next = Some(plan.cursor(stored_key, true));
1593                return Ok(page);
1594            }
1595            page.output_bytes += size;
1596            if let Some(mask) = plan.projection {
1597                page.rows.push(copy_projection(&bytes, &spans, mask, size));
1598            } else {
1599                page.rows.push(bytes);
1600            }
1601            if let Some(boundary) = boundary {
1602                previous = Some(boundary.to_vec());
1603            }
1604        }
1605        if page.rows.len() == request.rows
1606            || page.examined == request.work
1607            || input_bytes
1608                .as_deref()
1609                .is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
1610        {
1611            if terminal == Some(stored_key) {
1612                break;
1613            }
1614            if (aggregate.is_some() && input_bytes.is_none())
1615                || collected.is_some()
1616                || sorted.is_some()
1617            {
1618                // Completion has not been observed. Never expose partial reductions;
1619                // an exact-boundary scan may conservatively require more budget.
1620                return Err(Error::Limit);
1621            }
1622            page.next = Some(plan.cursor(stored_key, false));
1623            return Ok(page);
1624        }
1625    }
1626    if let Some(collection) = collected {
1627        page.output_bytes = collection.output_bytes;
1628        page.rows = collection.rows;
1629    }
1630    if let Some(collection) = sorted {
1631        collection.finish(request.bytes, &mut page)?;
1632    }
1633    Ok(page)
1634}