Skip to main content

ic_db/store/query/
mod.rs

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