Skip to main content

uqa_execution/
scan.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Scan operators.
8//!
9//! [`TableScan`] pulls rows from any [`RowSource`] in fixed-size
10//! batches. The trait is the integration seam: the engine implements
11//! it over its in-memory and SQLite-backed table state, the FDW layer
12//! implements it over `MemoryHandler` / `DuckDBHandler` /
13//! `ArrowHandler`, and tests can implement it directly over an
14//! in-memory `Vec<ResultRow>`.
15
16use crate::batch::{Batch, PhysicalRow, RowSchema, DEFAULT_BATCH_SIZE};
17use crate::physical::{BackwardScanSupport, ExecResult, PhysicalOperator, PhysicalOrder};
18use crate::RowSchemaExecution;
19use uqa_sql::ast::ColumnType;
20use uqa_sql::ResultRow;
21
22/// Source of rows feeding a [`TableScan`]. Implementors typically own
23/// a snapshot of the underlying table or external relation; the scan
24/// operator holds the source as a boxed trait object so callers can
25/// mix and match implementations across one query.
26pub trait RowSource: Send {
27    /// Stable column order for the rows produced by [`Self::next_row`].
28    fn schema(&self) -> &[String];
29
30    /// Optional non-identity schema used by positional sources. This carries
31    /// hidden lookup aliases and slot remaps that cannot be represented by the
32    /// legacy column-name slice.
33    fn physical_schema(&self) -> Option<&RowSchema> {
34        None
35    }
36
37    /// Estimated total rows available from this source.
38    fn estimated_cardinality(&self) -> Option<u64> {
39        None
40    }
41
42    /// Leading row order guaranteed by the source.
43    fn output_ordering(&self) -> &[PhysicalOrder] {
44        &[]
45    }
46
47    /// Pull the next row. Returns `None` when the source is exhausted.
48    fn next_row(&mut self) -> ExecResult<Option<ResultRow>>;
49
50    /// Pull up to `max_rows` without forcing batch-capable sources through a
51    /// row-at-a-time lock or backend call. The default preserves compatibility
52    /// for iterator-like sources.
53    fn next_batch(&mut self, max_rows: usize) -> ExecResult<Vec<ResultRow>> {
54        let mut rows = Vec::with_capacity(max_rows);
55        while rows.len() < max_rows {
56            match self.next_row()? {
57                Some(row) => rows.push(row),
58                None => break,
59            }
60        }
61        Ok(rows)
62    }
63
64    /// Pull a positional batch directly. Backend-native sources override this
65    /// to avoid constructing named maps at the scan boundary; compatibility
66    /// sources are converted exactly once here.
67    fn next_physical_batch(&mut self, max_rows: usize) -> ExecResult<Vec<PhysicalRow>> {
68        let schema = RowSchema::new(self.schema().to_vec());
69        self.next_batch(max_rows).map(|rows| {
70            rows.into_iter()
71                .map(|row| PhysicalRow::from_result_row(&schema, row))
72                .collect()
73        })
74    }
75
76    /// Feed backend-native projected rows directly to an aggregate. Sources
77    /// that cannot preserve their normal filter and virtual-column semantics
78    /// return `false` without advancing their cursor.
79    fn consume_into_aggregate(
80        &mut self,
81        _executor: &mut dyn crate::relational::AggregateExecutor,
82    ) -> ExecResult<bool> {
83        Ok(false)
84    }
85}
86
87/// In-memory source from a precomputed `Vec<ResultRow>`. Useful for
88/// tests and for materialising CTE bodies.
89pub struct VecSource {
90    schema: Vec<String>,
91    physical_schema: RowSchema,
92    rows: std::vec::IntoIter<ResultRow>,
93}
94
95/// In-memory positional source that preserves a structured [`RowSchema`] and shared physical row fragments without round-tripping through named maps.
96pub struct PhysicalVecSource {
97    schema: RowSchema,
98    rows: std::vec::IntoIter<PhysicalRow>,
99}
100
101/// Physical scan over a fallible row iterator. Unlike [`VecSource`], this
102/// adapter preserves producer backpressure and late errors without requiring a
103/// cardinality-sized staging vector.
104pub struct RowIteratorScan<'a> {
105    schema: RowSchema,
106    rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
107    exhausted: bool,
108}
109
110/// Physical scan over a fallible positional-row iterator. This is the native
111/// adapter for producers whose output can contain duplicate or unnamed SQL
112/// columns and therefore cannot be represented by [`ResultRow`].
113pub struct PhysicalRowIteratorScan<'a> {
114    schema: RowSchema,
115    rows: Box<dyn Iterator<Item = ExecResult<PhysicalRow>> + Send + 'a>,
116    batch_size: std::num::NonZeroUsize,
117    exhausted: bool,
118}
119
120impl<'a> RowIteratorScan<'a> {
121    pub fn new(
122        schema: Vec<String>,
123        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
124    ) -> Self {
125        Self {
126            schema: RowSchema::new(schema),
127            rows,
128            exhausted: false,
129        }
130    }
131
132    pub fn with_types(
133        schema: Vec<String>,
134        types: Vec<Option<ColumnType>>,
135        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
136    ) -> Self {
137        Self {
138            schema: RowSchema::with_types(schema, types),
139            rows,
140            exhausted: false,
141        }
142    }
143
144    pub fn with_row_schema(
145        schema: RowSchema,
146        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
147    ) -> Self {
148        Self {
149            schema,
150            rows,
151            exhausted: false,
152        }
153    }
154}
155
156impl PhysicalOperator for RowIteratorScan<'_> {
157    fn row_schema(&self) -> &RowSchema {
158        &self.schema
159    }
160
161    fn open(&mut self) -> ExecResult<()> {
162        self.exhausted = false;
163        Ok(())
164    }
165
166    fn next(&mut self) -> ExecResult<Option<Batch>> {
167        if self.exhausted {
168            return Ok(None);
169        }
170        let mut batch = Vec::with_capacity(DEFAULT_BATCH_SIZE);
171        while batch.len() < DEFAULT_BATCH_SIZE {
172            match self.rows.next() {
173                Some(Ok(row)) => batch.push(row),
174                Some(Err(error)) => return Err(error),
175                None => {
176                    self.exhausted = true;
177                    break;
178                }
179            }
180        }
181        if batch.is_empty() {
182            Ok(None)
183        } else {
184            Ok(Some(Batch::new(self.schema.clone(), batch)))
185        }
186    }
187
188    fn close(&mut self) -> ExecResult<()> {
189        self.exhausted = true;
190        Ok(())
191    }
192}
193
194impl<'a> PhysicalRowIteratorScan<'a> {
195    pub fn new(
196        schema: RowSchema,
197        rows: Box<dyn Iterator<Item = ExecResult<PhysicalRow>> + Send + 'a>,
198    ) -> Self {
199        Self {
200            schema,
201            rows,
202            batch_size: std::num::NonZeroUsize::new(DEFAULT_BATCH_SIZE)
203                .expect("default scan batch is nonempty"),
204            exhausted: false,
205        }
206    }
207
208    /// Limit retained producer values when individual rows may exceed the consumer's work allowance.
209    pub fn with_batch_size(mut self, size: std::num::NonZeroUsize) -> Self {
210        self.batch_size = size;
211        self
212    }
213}
214
215impl PhysicalOperator for PhysicalRowIteratorScan<'_> {
216    fn row_schema(&self) -> &RowSchema {
217        &self.schema
218    }
219
220    fn backward_scan_support(&self) -> BackwardScanSupport {
221        BackwardScanSupport::Materialize
222    }
223
224    fn open(&mut self) -> ExecResult<()> {
225        self.exhausted = false;
226        Ok(())
227    }
228
229    fn next(&mut self) -> ExecResult<Option<Batch>> {
230        if self.exhausted {
231            return Ok(None);
232        }
233        let mut batch = Vec::with_capacity(self.batch_size.get());
234        while batch.len() < self.batch_size.get() {
235            match self.rows.next() {
236                Some(Ok(row)) => batch.push(row),
237                Some(Err(error)) => return Err(error),
238                None => {
239                    self.exhausted = true;
240                    break;
241                }
242            }
243        }
244        if batch.is_empty() {
245            Ok(None)
246        } else {
247            Ok(Some(Batch::from_physical_rows(self.schema.clone(), batch)))
248        }
249    }
250
251    fn close(&mut self) -> ExecResult<()> {
252        self.exhausted = true;
253        Ok(())
254    }
255}
256
257impl VecSource {
258    pub fn new(schema: Vec<String>, rows: Vec<ResultRow>) -> Self {
259        let physical_schema = RowSchema::from_named_columns(schema.clone());
260        Self {
261            schema,
262            physical_schema,
263            rows: rows.into_iter(),
264        }
265    }
266
267    pub fn with_row_schema(physical_schema: RowSchema, rows: Vec<ResultRow>) -> Self {
268        Self {
269            schema: physical_schema.columns().to_vec(),
270            physical_schema,
271            rows: rows.into_iter(),
272        }
273    }
274
275    pub fn with_types(
276        schema: Vec<String>,
277        types: Vec<Option<ColumnType>>,
278        rows: Vec<ResultRow>,
279    ) -> Self {
280        let physical_schema = RowSchema::with_types(schema.clone(), types);
281        Self {
282            schema,
283            physical_schema,
284            rows: rows.into_iter(),
285        }
286    }
287}
288
289impl RowSource for VecSource {
290    fn schema(&self) -> &[String] {
291        &self.schema
292    }
293
294    fn physical_schema(&self) -> Option<&RowSchema> {
295        Some(&self.physical_schema)
296    }
297
298    fn estimated_cardinality(&self) -> Option<u64> {
299        u64::try_from(self.rows.len()).ok()
300    }
301
302    fn next_row(&mut self) -> ExecResult<Option<ResultRow>> {
303        Ok(self.rows.next())
304    }
305}
306
307impl PhysicalVecSource {
308    pub fn new(schema: RowSchema, rows: Vec<PhysicalRow>) -> Self {
309        Self {
310            schema,
311            rows: rows.into_iter(),
312        }
313    }
314}
315
316impl RowSource for PhysicalVecSource {
317    fn schema(&self) -> &[String] {
318        self.schema.columns()
319    }
320
321    fn physical_schema(&self) -> Option<&RowSchema> {
322        Some(&self.schema)
323    }
324
325    fn estimated_cardinality(&self) -> Option<u64> {
326        u64::try_from(self.rows.len()).ok()
327    }
328
329    fn next_row(&mut self) -> ExecResult<Option<ResultRow>> {
330        Ok(self
331            .rows
332            .next()
333            .map(|row| self.schema.view(&row).to_result_row()))
334    }
335
336    fn next_physical_batch(&mut self, max_rows: usize) -> ExecResult<Vec<PhysicalRow>> {
337        Ok(self.rows.by_ref().take(max_rows).collect())
338    }
339}
340
341/// `TableScan`: a leaf operator that drains its [`RowSource`].
342///
343/// Emits batches of at most [`DEFAULT_BATCH_SIZE`] rows. Idempotent
344/// `open` / `close` so the operator can be re-opened in tests.
345pub struct TableScan {
346    source: Option<Box<dyn RowSource>>,
347    schema: RowSchema,
348    ordering: Vec<PhysicalOrder>,
349    estimated_cardinality: Option<u64>,
350    exhausted: bool,
351}
352
353impl TableScan {
354    pub fn new(source: Box<dyn RowSource>) -> Self {
355        let schema = source
356            .physical_schema()
357            .cloned()
358            .unwrap_or_else(|| RowSchema::new(source.schema().to_vec()));
359        let ordering = source.output_ordering().to_vec();
360        let estimated_cardinality = source.estimated_cardinality();
361        Self {
362            source: Some(source),
363            schema,
364            ordering,
365            estimated_cardinality,
366            exhausted: false,
367        }
368    }
369
370    pub fn from_rows(schema: Vec<String>, rows: Vec<ResultRow>) -> Self {
371        Self::new(Box::new(VecSource::new(schema, rows)))
372    }
373
374    pub fn from_typed_rows(
375        schema: Vec<String>,
376        types: Vec<Option<ColumnType>>,
377        rows: Vec<ResultRow>,
378    ) -> Self {
379        Self::new(Box::new(VecSource::with_types(schema, types, rows)))
380    }
381
382    pub fn from_rows_with_schema(schema: RowSchema, rows: Vec<ResultRow>) -> Self {
383        Self::new(Box::new(VecSource::with_row_schema(schema, rows)))
384    }
385
386    pub fn from_physical_rows(schema: RowSchema, rows: Vec<PhysicalRow>) -> Self {
387        Self::new(Box::new(PhysicalVecSource::new(schema, rows)))
388    }
389}
390
391impl PhysicalOperator for TableScan {
392    fn row_schema(&self) -> &RowSchema {
393        &self.schema
394    }
395
396    fn estimated_cardinality(&self) -> Option<u64> {
397        self.estimated_cardinality
398    }
399
400    fn output_ordering(&self) -> &[PhysicalOrder] {
401        &self.ordering
402    }
403
404    fn backward_scan_support(&self) -> BackwardScanSupport {
405        BackwardScanSupport::Materialize
406    }
407
408    fn consume_into_aggregate(
409        &mut self,
410        executor: &mut dyn crate::relational::AggregateExecutor,
411    ) -> ExecResult<bool> {
412        let Some(source) = self.source.as_mut() else {
413            return Ok(false);
414        };
415        source.consume_into_aggregate(executor)
416    }
417
418    fn open(&mut self) -> ExecResult<()> {
419        self.exhausted = false;
420        Ok(())
421    }
422
423    fn next(&mut self) -> ExecResult<Option<Batch>> {
424        if self.exhausted {
425            return Ok(None);
426        }
427        let Some(src) = self.source.as_mut() else {
428            return Ok(None);
429        };
430        let buf = src.next_physical_batch(DEFAULT_BATCH_SIZE)?;
431        if buf.is_empty() {
432            self.exhausted = true;
433            return Ok(None);
434        }
435        Ok(Some(Batch::from_physical_rows(self.schema.clone(), buf)))
436    }
437
438    fn close(&mut self) -> ExecResult<()> {
439        self.source = None;
440        self.exhausted = true;
441        Ok(())
442    }
443}
444
445#[cfg(test)]
446mod tests {
447    use super::*;
448    use crate::physical::run_to_rows;
449    use uqa_core::Value;
450
451    fn row<const N: usize>(pairs: [(&str, Value); N]) -> ResultRow {
452        pairs.into_iter().map(|(k, v)| (k.to_string(), v)).collect()
453    }
454
455    #[test]
456    fn table_scan_drains_source() {
457        let rows = vec![
458            row([("id", Value::Int(1)), ("name", Value::Str("a".into()))]),
459            row([("id", Value::Int(2)), ("name", Value::Str("b".into()))]),
460        ];
461        let mut scan = TableScan::from_rows(vec!["id".into(), "name".into()], rows);
462        let (cols, rows) = run_to_rows(&mut scan).unwrap();
463        assert_eq!(cols, vec!["id", "name"]);
464        assert_eq!(rows.len(), 2);
465    }
466
467    #[test]
468    fn table_scan_empty_source_returns_no_batch() {
469        let mut scan = TableScan::from_rows(vec!["id".into()], Vec::new());
470        let (_cols, rows) = run_to_rows(&mut scan).unwrap();
471        assert_eq!(rows.len(), 0);
472    }
473
474    #[test]
475    fn iterator_scan_propagates_a_late_producer_error() {
476        let rows = vec![
477            Ok(row([("id", Value::Int(1))])),
478            Err(crate::ExecError::Other("late producer failure".into())),
479        ];
480        let mut scan = RowIteratorScan::new(vec!["id".into()], Box::new(rows.into_iter()));
481        let error = run_to_rows(&mut scan).unwrap_err();
482        assert!(error.to_string().contains("late producer failure"));
483    }
484}