Skip to main content

uqa_execution/query/index_candidates/
ids.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Freeze complete candidate support in identity order before any row evaluation.
8
9use crate::{
10    mutation::PhysicalRowBuffer,
11    physical::physical_exec_error,
12    spill::{SharedSpillReader, SpillBatchWriter, SpillRows},
13    PhysicalRow, RowSchema, SharedSpill, SpillBuffer,
14};
15use std::sync::Arc;
16use uqa_core::{CancellationToken, DocId, Value};
17use uqa_sql::SQLError;
18
19#[derive(Clone)]
20enum IdentityStorage {
21    Memory(Arc<[DocId]>),
22    Spill(SharedSpill),
23}
24
25/// An immutable, ascending, duplicate-free candidate set. Independent cursors share its captured source, with bounded resident state.
26#[derive(Clone)]
27pub struct SelectedIds {
28    storage: IdentityStorage,
29    cancellation: CancellationToken,
30}
31
32impl SelectedIds {
33    /// Classify the complete ordered input once before either output is read. `true` goes to the first set, `false` to the second, and `None` omits the identity.
34    pub(crate) fn partition(
35        &self,
36        bytes: usize,
37        mut select: impl FnMut(DocId) -> Result<Option<bool>, SQLError>,
38    ) -> Result<(Self, Self), SQLError> {
39        let mut first = IdentityBuilder::new(bytes / 2, &self.cancellation);
40        let mut second = IdentityBuilder::new(bytes / 2, &self.cancellation);
41        for id in self.cursor() {
42            let id = id?;
43            match select(id)? {
44                Some(true) => first.push(id)?,
45                Some(false) => second.push(id)?,
46                None => {}
47            }
48        }
49        Ok((first.finish(false)?, second.finish(false)?))
50    }
51
52    /// Freeze a callback-based producer before any consumer reads its identities.
53    pub(crate) fn capture_visit(
54        bytes: usize,
55        cancellation: &CancellationToken,
56        produce: impl FnOnce(&mut dyn FnMut(DocId) -> Result<(), SQLError>) -> Result<(), SQLError>,
57    ) -> Result<Self, SQLError> {
58        let mut builder = IdentityBuilder::new(bytes, cancellation);
59        produce(&mut |id| builder.push(id))?;
60        builder.finish(true)
61    }
62
63    /// Capture all identities before consumption, using bounded memory and ascending, duplicate-free output.
64    pub fn capture(
65        ids: impl IntoIterator<Item = Result<DocId, SQLError>>,
66        bytes: usize,
67        cancellation: &CancellationToken,
68    ) -> Result<Self, SQLError> {
69        let mut builder = IdentityBuilder::new(bytes, cancellation);
70        for id in ids {
71            builder.push(id?)?;
72        }
73        builder.finish(true)
74    }
75
76    pub(crate) fn from_sorted(
77        ids: Vec<DocId>,
78        bytes: usize,
79        cancellation: &CancellationToken,
80    ) -> Result<Self, SQLError> {
81        cancellation.check()?;
82        if ids.len() <= bytes / size_of::<DocId>() {
83            return Ok(Self {
84                storage: IdentityStorage::Memory(ids.into()),
85                cancellation: cancellation.clone(),
86            });
87        }
88        let mut builder = IdentityBuilder::new(bytes, cancellation);
89        for id in ids {
90            builder.push(id)?;
91        }
92        builder.finish(false)
93    }
94
95    pub fn len(&self) -> usize {
96        match &self.storage {
97            IdentityStorage::Memory(ids) => ids.len(),
98            IdentityStorage::Spill(rows) => rows.rows(),
99        }
100    }
101
102    pub fn is_empty(&self) -> bool {
103        self.len() == 0
104    }
105
106    pub fn cursor(&self) -> SelectedIdCursor {
107        SelectedIdCursor {
108            source: self.clone(),
109            position: 0,
110            rows: None,
111            failed: false,
112        }
113    }
114}
115
116pub struct SelectedIdCursor {
117    source: SelectedIds,
118    position: usize,
119    rows: Option<SpillRows<SharedSpillReader>>,
120    failed: bool,
121}
122
123impl SelectedIdCursor {
124    fn read(&mut self) -> Result<Option<DocId>, SQLError> {
125        self.source.cancellation.check()?;
126        let id = match &self.source.storage {
127            IdentityStorage::Memory(ids) => ids.get(self.position).copied(),
128            IdentityStorage::Spill(source) => {
129                if self.rows.is_none() {
130                    self.rows = Some(source.read_rows().map_err(physical_exec_error)?);
131                }
132                self.rows
133                    .as_mut()
134                    .expect("opened candidate cursor")
135                    .next()
136                    .map(|row| decode(row.map_err(physical_exec_error)?.row))
137                    .transpose()?
138            }
139        };
140        self.position += usize::from(id.is_some());
141        Ok(id)
142    }
143}
144
145impl Iterator for SelectedIdCursor {
146    type Item = Result<DocId, SQLError>;
147
148    fn next(&mut self) -> Option<Self::Item> {
149        if self.failed || self.position == self.source.len() {
150            return None;
151        }
152        match self.read() {
153            Ok(Some(id)) => Some(Ok(id)),
154            Ok(None) => {
155                self.failed = true;
156                Some(Err(SQLError::Internal(
157                    "truncated candidate identities".into(),
158                )))
159            }
160            Err(error) => {
161                self.failed = true;
162                Some(Err(error))
163            }
164        }
165    }
166}
167
168struct SpilledIds {
169    rows: SpillBuffer,
170    writer: SpillBatchWriter,
171    schema: RowSchema,
172}
173
174enum CapturedIds {
175    Memory(Vec<DocId>),
176    Spill(Box<SpilledIds>),
177}
178
179pub(super) struct IdentityBuilder {
180    records: CapturedIds,
181    bytes: usize,
182    cancellation: CancellationToken,
183    previous: Option<DocId>,
184    ascending: bool,
185}
186
187impl IdentityBuilder {
188    pub(super) fn new(bytes: usize, cancellation: &CancellationToken) -> Self {
189        Self {
190            records: CapturedIds::Memory(Vec::new()),
191            bytes,
192            cancellation: cancellation.clone(),
193            previous: None,
194            ascending: true,
195        }
196    }
197
198    pub(super) fn push(&mut self, id: DocId) -> Result<(), SQLError> {
199        self.cancellation.check()?;
200        self.ascending &= self.previous.is_none_or(|previous| previous < id);
201        self.previous = Some(id);
202        if let CapturedIds::Memory(ids) = &mut self.records {
203            let limit = self.bytes / 4 / size_of::<DocId>();
204            if ids.len() < limit {
205                if ids.len() == ids.capacity() {
206                    let capacity = ids.capacity().saturating_mul(2).max(4).min(limit);
207                    ids.reserve_exact(capacity - ids.len());
208                }
209                ids.push(id);
210                return Ok(());
211            }
212            let schema = RowSchema::with_internal_relation_types(
213                uqa_sql::ast::InternalRelationId::allocate(),
214                vec![None],
215            );
216            let mut spilled = SpilledIds {
217                rows: SpillBuffer::new(self.bytes / 4),
218                writer: SpillBatchWriter::new(schema.clone()).map_err(physical_exec_error)?,
219                schema,
220            };
221            for &id in ids.iter() {
222                self.cancellation.check()?;
223                spilled.push(id)?;
224            }
225            self.records = CapturedIds::Spill(Box::new(spilled));
226        }
227        let CapturedIds::Spill(records) = &mut self.records else {
228            unreachable!("spilled candidate identities")
229        };
230        records.push(id)
231    }
232
233    pub(super) fn finish(self, sort: bool) -> Result<SelectedIds, SQLError> {
234        self.cancellation.check()?;
235        let SpilledIds {
236            mut rows,
237            writer,
238            schema,
239        } = match self.records {
240            CapturedIds::Memory(mut ids) => {
241                if sort && !self.ascending {
242                    ids.sort_unstable();
243                    ids.dedup();
244                }
245                return Ok(SelectedIds {
246                    storage: IdentityStorage::Memory(ids.into()),
247                    cancellation: self.cancellation,
248                });
249            }
250            CapturedIds::Spill(records) => *records,
251        };
252        writer.finish(&mut rows).map_err(physical_exec_error)?;
253        if !sort || self.ascending {
254            return Ok(SelectedIds {
255                storage: IdentityStorage::Spill(
256                    rows.into_shared(schema).map_err(physical_exec_error)?,
257                ),
258                cancellation: self.cancellation,
259            });
260        }
261        // The existing storage-backed physical key set sorts identities directly, without decorating each ID as a SQL sort row.
262        let mut ordered = PhysicalRowBuffer::new(
263            self.bytes / 4,
264            self.cancellation.clone(),
265            "sort indexed candidates",
266        );
267        for row in rows.drain_rows().map_err(physical_exec_error)? {
268            ordered.insert("", decode(row.map_err(physical_exec_error)?.row)?)?;
269        }
270        let ordered = ordered.finish()?;
271        let mut output = Self::new(self.bytes, &self.cancellation);
272        ordered.visit(&mut |_, id| {
273            output.push(id)?;
274            Ok(true)
275        })?;
276        output.finish(false)
277    }
278}
279
280impl SpilledIds {
281    fn push(&mut self, id: DocId) -> Result<(), SQLError> {
282        self.writer
283            .push(
284                &mut self.rows,
285                PhysicalRow::from_values(vec![Value::Bytes(id.to_be_bytes().to_vec())]),
286            )
287            .map_err(physical_exec_error)
288    }
289}
290
291fn decode(row: PhysicalRow) -> Result<DocId, SQLError> {
292    let Some(Value::Bytes(bytes)) = row.value(0) else {
293        return Err(SQLError::Internal("invalid candidate identity".into()));
294    };
295    Ok(u64::from_be_bytes(bytes.as_slice().try_into().map_err(
296        |_| SQLError::Internal("invalid candidate identity width".into()),
297    )?))
298}