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    exhausted: bool,
117}
118
119impl<'a> RowIteratorScan<'a> {
120    pub fn new(
121        schema: Vec<String>,
122        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
123    ) -> Self {
124        Self {
125            schema: RowSchema::new(schema),
126            rows,
127            exhausted: false,
128        }
129    }
130
131    pub fn with_types(
132        schema: Vec<String>,
133        types: Vec<Option<ColumnType>>,
134        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
135    ) -> Self {
136        Self {
137            schema: RowSchema::with_types(schema, types),
138            rows,
139            exhausted: false,
140        }
141    }
142
143    pub fn with_row_schema(
144        schema: RowSchema,
145        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
146    ) -> Self {
147        Self {
148            schema,
149            rows,
150            exhausted: false,
151        }
152    }
153}
154
155impl PhysicalOperator for RowIteratorScan<'_> {
156    fn row_schema(&self) -> &RowSchema {
157        &self.schema
158    }
159
160    fn open(&mut self) -> ExecResult<()> {
161        self.exhausted = false;
162        Ok(())
163    }
164
165    fn next(&mut self) -> ExecResult<Option<Batch>> {
166        if self.exhausted {
167            return Ok(None);
168        }
169        let mut batch = Vec::with_capacity(DEFAULT_BATCH_SIZE);
170        while batch.len() < DEFAULT_BATCH_SIZE {
171            match self.rows.next() {
172                Some(Ok(row)) => batch.push(row),
173                Some(Err(error)) => return Err(error),
174                None => {
175                    self.exhausted = true;
176                    break;
177                }
178            }
179        }
180        if batch.is_empty() {
181            Ok(None)
182        } else {
183            Ok(Some(Batch::new(self.schema.clone(), batch)))
184        }
185    }
186
187    fn close(&mut self) -> ExecResult<()> {
188        self.exhausted = true;
189        Ok(())
190    }
191}
192
193impl<'a> PhysicalRowIteratorScan<'a> {
194    pub fn new(
195        schema: RowSchema,
196        rows: Box<dyn Iterator<Item = ExecResult<PhysicalRow>> + Send + 'a>,
197    ) -> Self {
198        Self {
199            schema,
200            rows,
201            exhausted: false,
202        }
203    }
204}
205
206impl PhysicalOperator for PhysicalRowIteratorScan<'_> {
207    fn row_schema(&self) -> &RowSchema {
208        &self.schema
209    }
210
211    fn backward_scan_support(&self) -> BackwardScanSupport {
212        BackwardScanSupport::Materialize
213    }
214
215    fn open(&mut self) -> ExecResult<()> {
216        self.exhausted = false;
217        Ok(())
218    }
219
220    fn next(&mut self) -> ExecResult<Option<Batch>> {
221        if self.exhausted {
222            return Ok(None);
223        }
224        let mut batch = Vec::with_capacity(DEFAULT_BATCH_SIZE);
225        while batch.len() < DEFAULT_BATCH_SIZE {
226            match self.rows.next() {
227                Some(Ok(row)) => batch.push(row),
228                Some(Err(error)) => return Err(error),
229                None => {
230                    self.exhausted = true;
231                    break;
232                }
233            }
234        }
235        if batch.is_empty() {
236            Ok(None)
237        } else {
238            Ok(Some(Batch::from_physical_rows(self.schema.clone(), batch)))
239        }
240    }
241
242    fn close(&mut self) -> ExecResult<()> {
243        self.exhausted = true;
244        Ok(())
245    }
246}
247
248impl VecSource {
249    pub fn new(schema: Vec<String>, rows: Vec<ResultRow>) -> Self {
250        let physical_schema = RowSchema::from_named_columns(schema.clone());
251        Self {
252            schema,
253            physical_schema,
254            rows: rows.into_iter(),
255        }
256    }
257
258    pub fn with_row_schema(physical_schema: RowSchema, rows: Vec<ResultRow>) -> Self {
259        Self {
260            schema: physical_schema.columns().to_vec(),
261            physical_schema,
262            rows: rows.into_iter(),
263        }
264    }
265
266    pub fn with_types(
267        schema: Vec<String>,
268        types: Vec<Option<ColumnType>>,
269        rows: Vec<ResultRow>,
270    ) -> Self {
271        let physical_schema = RowSchema::with_types(schema.clone(), types);
272        Self {
273            schema,
274            physical_schema,
275            rows: rows.into_iter(),
276        }
277    }
278}
279
280impl RowSource for VecSource {
281    fn schema(&self) -> &[String] {
282        &self.schema
283    }
284
285    fn physical_schema(&self) -> Option<&RowSchema> {
286        Some(&self.physical_schema)
287    }
288
289    fn estimated_cardinality(&self) -> Option<u64> {
290        u64::try_from(self.rows.len()).ok()
291    }
292
293    fn next_row(&mut self) -> ExecResult<Option<ResultRow>> {
294        Ok(self.rows.next())
295    }
296}
297
298impl PhysicalVecSource {
299    pub fn new(schema: RowSchema, rows: Vec<PhysicalRow>) -> Self {
300        Self {
301            schema,
302            rows: rows.into_iter(),
303        }
304    }
305}
306
307impl RowSource for PhysicalVecSource {
308    fn schema(&self) -> &[String] {
309        self.schema.columns()
310    }
311
312    fn physical_schema(&self) -> Option<&RowSchema> {
313        Some(&self.schema)
314    }
315
316    fn estimated_cardinality(&self) -> Option<u64> {
317        u64::try_from(self.rows.len()).ok()
318    }
319
320    fn next_row(&mut self) -> ExecResult<Option<ResultRow>> {
321        Ok(self
322            .rows
323            .next()
324            .map(|row| self.schema.view(&row).to_result_row()))
325    }
326
327    fn next_physical_batch(&mut self, max_rows: usize) -> ExecResult<Vec<PhysicalRow>> {
328        Ok(self.rows.by_ref().take(max_rows).collect())
329    }
330}
331
332/// `TableScan`: a leaf operator that drains its [`RowSource`].
333///
334/// Emits batches of at most [`DEFAULT_BATCH_SIZE`] rows. Idempotent
335/// `open` / `close` so the operator can be re-opened in tests.
336pub struct TableScan {
337    source: Option<Box<dyn RowSource>>,
338    schema: RowSchema,
339    ordering: Vec<PhysicalOrder>,
340    estimated_cardinality: Option<u64>,
341    exhausted: bool,
342}
343
344impl TableScan {
345    pub fn new(source: Box<dyn RowSource>) -> Self {
346        let schema = source
347            .physical_schema()
348            .cloned()
349            .unwrap_or_else(|| RowSchema::new(source.schema().to_vec()));
350        let ordering = source.output_ordering().to_vec();
351        let estimated_cardinality = source.estimated_cardinality();
352        Self {
353            source: Some(source),
354            schema,
355            ordering,
356            estimated_cardinality,
357            exhausted: false,
358        }
359    }
360
361    pub fn from_rows(schema: Vec<String>, rows: Vec<ResultRow>) -> Self {
362        Self::new(Box::new(VecSource::new(schema, rows)))
363    }
364
365    pub fn from_typed_rows(
366        schema: Vec<String>,
367        types: Vec<Option<ColumnType>>,
368        rows: Vec<ResultRow>,
369    ) -> Self {
370        Self::new(Box::new(VecSource::with_types(schema, types, rows)))
371    }
372
373    pub fn from_rows_with_schema(schema: RowSchema, rows: Vec<ResultRow>) -> Self {
374        Self::new(Box::new(VecSource::with_row_schema(schema, rows)))
375    }
376
377    pub fn from_physical_rows(schema: RowSchema, rows: Vec<PhysicalRow>) -> Self {
378        Self::new(Box::new(PhysicalVecSource::new(schema, rows)))
379    }
380}
381
382impl PhysicalOperator for TableScan {
383    fn row_schema(&self) -> &RowSchema {
384        &self.schema
385    }
386
387    fn estimated_cardinality(&self) -> Option<u64> {
388        self.estimated_cardinality
389    }
390
391    fn output_ordering(&self) -> &[PhysicalOrder] {
392        &self.ordering
393    }
394
395    fn backward_scan_support(&self) -> BackwardScanSupport {
396        BackwardScanSupport::Materialize
397    }
398
399    fn consume_into_aggregate(
400        &mut self,
401        executor: &mut dyn crate::relational::AggregateExecutor,
402    ) -> ExecResult<bool> {
403        let Some(source) = self.source.as_mut() else {
404            return Ok(false);
405        };
406        source.consume_into_aggregate(executor)
407    }
408
409    fn open(&mut self) -> ExecResult<()> {
410        self.exhausted = false;
411        Ok(())
412    }
413
414    fn next(&mut self) -> ExecResult<Option<Batch>> {
415        if self.exhausted {
416            return Ok(None);
417        }
418        let Some(src) = self.source.as_mut() else {
419            return Ok(None);
420        };
421        let buf = src.next_physical_batch(DEFAULT_BATCH_SIZE)?;
422        if buf.is_empty() {
423            self.exhausted = true;
424            return Ok(None);
425        }
426        Ok(Some(Batch::from_physical_rows(self.schema.clone(), buf)))
427    }
428
429    fn close(&mut self) -> ExecResult<()> {
430        self.source = None;
431        self.exhausted = true;
432        Ok(())
433    }
434}
435
436#[cfg(test)]
437mod tests {
438    use super::*;
439    use crate::physical::run_to_rows;
440    use uqa_core::Value;
441
442    fn row<const N: usize>(pairs: [(&str, Value); N]) -> ResultRow {
443        pairs.into_iter().map(|(k, v)| (k.to_string(), v)).collect()
444    }
445
446    #[test]
447    fn table_scan_drains_source() {
448        let rows = vec![
449            row([("id", Value::Int(1)), ("name", Value::Str("a".into()))]),
450            row([("id", Value::Int(2)), ("name", Value::Str("b".into()))]),
451        ];
452        let mut scan = TableScan::from_rows(vec!["id".into(), "name".into()], rows);
453        let (cols, rows) = run_to_rows(&mut scan).unwrap();
454        assert_eq!(cols, vec!["id", "name"]);
455        assert_eq!(rows.len(), 2);
456    }
457
458    #[test]
459    fn table_scan_empty_source_returns_no_batch() {
460        let mut scan = TableScan::from_rows(vec!["id".into()], Vec::new());
461        let (_cols, rows) = run_to_rows(&mut scan).unwrap();
462        assert_eq!(rows.len(), 0);
463    }
464
465    #[test]
466    fn iterator_scan_propagates_a_late_producer_error() {
467        let rows = vec![
468            Ok(row([("id", Value::Int(1))])),
469            Err(crate::ExecError::Other("late producer failure".into())),
470        ];
471        let mut scan = RowIteratorScan::new(vec!["id".into()], Box::new(rows.into_iter()));
472        let error = run_to_rows(&mut scan).unwrap_err();
473        assert!(error.to_string().contains("late producer failure"));
474    }
475}