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