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    /// Native batch reads preserve the SQL evaluation and first-error order of consecutive single-row reads when the caller consumes the complete input. Custom sources must establish this before opting in.
31    fn supports_batched_consumption(&self) -> bool {
32        false
33    }
34
35    /// Optional non-identity schema used by positional sources. This carries
36    /// hidden lookup aliases and slot remaps that cannot be represented by the
37    /// legacy column-name slice.
38    fn physical_schema(&self) -> Option<&RowSchema> {
39        None
40    }
41
42    /// Estimated total rows available from this source.
43    fn estimated_cardinality(&self) -> Option<u64> {
44        None
45    }
46
47    /// Leading row order guaranteed by the source.
48    fn output_ordering(&self) -> &[PhysicalOrder] {
49        &[]
50    }
51
52    /// Pull the next row. Returns `None` when the source is exhausted.
53    fn next_row(&mut self) -> ExecResult<Option<ResultRow>>;
54
55    /// Pull up to `max_rows` without forcing batch-capable sources through a
56    /// row-at-a-time lock or backend call. The default preserves compatibility
57    /// for iterator-like sources.
58    fn next_batch(&mut self, max_rows: usize) -> ExecResult<Vec<ResultRow>> {
59        let mut rows = Vec::with_capacity(max_rows);
60        while rows.len() < max_rows {
61            match self.next_row()? {
62                Some(row) => rows.push(row),
63                None => break,
64            }
65        }
66        Ok(rows)
67    }
68
69    /// Pull a positional batch directly. Backend-native sources override this
70    /// to avoid constructing named maps at the scan boundary; compatibility
71    /// sources are converted exactly once here.
72    fn next_physical_batch(&mut self, max_rows: usize) -> ExecResult<Vec<PhysicalRow>> {
73        let schema = RowSchema::new(self.schema().to_vec());
74        self.next_batch(max_rows).map(|rows| {
75            rows.into_iter()
76                .map(|row| PhysicalRow::from_result_row(&schema, row))
77                .collect()
78        })
79    }
80
81    /// Feed backend-native projected rows directly to an aggregate. Sources
82    /// that cannot preserve their normal filter and virtual-column semantics
83    /// return `false` without advancing their cursor.
84    fn consume_into_aggregate(
85        &mut self,
86        _executor: &mut dyn crate::relational::AggregateExecutor,
87    ) -> ExecResult<bool> {
88        Ok(false)
89    }
90
91    /// Consume the complete source into the native public accumulator without transferring temporary row ownership. Unsupported sources decline before advancing their cursor.
92    fn collect_materialized(
93        &mut self,
94        _sink: &mut crate::query::output::MaterializedResultSink<'_>,
95    ) -> ExecResult<bool> {
96        Ok(false)
97    }
98}
99
100/// In-memory source from a precomputed `Vec<ResultRow>`. Useful for
101/// tests and for materialising CTE bodies.
102pub struct VecSource {
103    schema: Vec<String>,
104    physical_schema: RowSchema,
105    rows: std::vec::IntoIter<ResultRow>,
106}
107
108/// In-memory positional source that preserves a structured [`RowSchema`] and shared physical row fragments without round-tripping through named maps.
109pub struct PhysicalVecSource {
110    schema: RowSchema,
111    rows: std::vec::IntoIter<PhysicalRow>,
112}
113
114/// Physical scan over a fallible row iterator. Unlike [`VecSource`], this
115/// adapter preserves producer backpressure and late errors without requiring a
116/// cardinality-sized staging vector.
117pub struct RowIteratorScan<'a> {
118    schema: RowSchema,
119    rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
120    exhausted: bool,
121}
122
123/// Physical scan over a fallible positional-row iterator. This is the native
124/// adapter for producers whose output can contain duplicate or unnamed SQL
125/// columns and therefore cannot be represented by [`ResultRow`].
126pub struct PhysicalRowIteratorScan<'a> {
127    schema: RowSchema,
128    rows: crate::SQLRowStream<'a, PhysicalRow>,
129    batch_size: std::num::NonZeroUsize,
130    exhausted: bool,
131}
132
133impl<'a> RowIteratorScan<'a> {
134    pub fn new(
135        schema: Vec<String>,
136        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
137    ) -> Self {
138        Self {
139            schema: RowSchema::new(schema),
140            rows,
141            exhausted: false,
142        }
143    }
144
145    pub fn with_types(
146        schema: Vec<String>,
147        types: Vec<Option<ColumnType>>,
148        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
149    ) -> Self {
150        Self {
151            schema: RowSchema::with_types(schema, types),
152            rows,
153            exhausted: false,
154        }
155    }
156
157    pub fn with_row_schema(
158        schema: RowSchema,
159        rows: Box<dyn Iterator<Item = ExecResult<ResultRow>> + Send + 'a>,
160    ) -> Self {
161        Self {
162            schema,
163            rows,
164            exhausted: false,
165        }
166    }
167}
168
169impl PhysicalOperator for RowIteratorScan<'_> {
170    fn row_schema(&self) -> &RowSchema {
171        &self.schema
172    }
173
174    fn supports_batched_consumption(&self) -> bool {
175        true
176    }
177
178    fn open(&mut self) -> ExecResult<()> {
179        self.exhausted = false;
180        Ok(())
181    }
182
183    fn next(&mut self) -> ExecResult<Option<Batch>> {
184        self.next_with_demand(
185            std::num::NonZeroUsize::new(DEFAULT_BATCH_SIZE).expect("nonempty scan batch"),
186        )
187    }
188
189    fn next_with_demand(&mut self, demand: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
190        if self.exhausted {
191            return Ok(None);
192        }
193        let mut batch = Vec::with_capacity(DEFAULT_BATCH_SIZE.min(demand.get()));
194        while batch.len() < DEFAULT_BATCH_SIZE.min(demand.get()) {
195            match self.rows.next() {
196                Some(Ok(row)) => batch.push(row),
197                Some(Err(error)) => return Err(error),
198                None => {
199                    self.exhausted = true;
200                    break;
201                }
202            }
203        }
204        if batch.is_empty() {
205            Ok(None)
206        } else {
207            Ok(Some(Batch::new(self.schema.clone(), batch)))
208        }
209    }
210
211    fn close(&mut self) -> ExecResult<()> {
212        self.exhausted = true;
213        Ok(())
214    }
215}
216
217impl<'a> PhysicalRowIteratorScan<'a> {
218    pub fn new(
219        schema: RowSchema,
220        rows: Box<dyn Iterator<Item = ExecResult<PhysicalRow>> + Send + 'a>,
221    ) -> Self {
222        Self::from_stream(
223            schema,
224            crate::SQLRowStream::new(
225                rows.map(|row| row.map_err(crate::physical::physical_exec_error)),
226            ),
227        )
228    }
229
230    pub fn from_stream(schema: RowSchema, rows: crate::SQLRowStream<'a, PhysicalRow>) -> Self {
231        Self {
232            schema,
233            rows,
234            batch_size: std::num::NonZeroUsize::new(DEFAULT_BATCH_SIZE)
235                .expect("default scan batch is nonempty"),
236            exhausted: false,
237        }
238    }
239
240    /// Limit retained producer values when individual rows may exceed the consumer's work allowance.
241    pub fn with_batch_size(mut self, size: std::num::NonZeroUsize) -> Self {
242        self.batch_size = size;
243        self
244    }
245}
246
247impl PhysicalOperator for PhysicalRowIteratorScan<'_> {
248    fn row_schema(&self) -> &RowSchema {
249        &self.schema
250    }
251
252    fn supports_batched_consumption(&self) -> bool {
253        true
254    }
255
256    fn backward_scan_support(&self) -> BackwardScanSupport {
257        BackwardScanSupport::Materialize
258    }
259
260    fn open(&mut self) -> ExecResult<()> {
261        self.exhausted = false;
262        Ok(())
263    }
264
265    fn next(&mut self) -> ExecResult<Option<Batch>> {
266        self.next_with_demand(
267            std::num::NonZeroUsize::new(self.batch_size.get()).expect("nonempty scan batch"),
268        )
269    }
270
271    fn next_with_demand(&mut self, demand: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
272        if self.exhausted {
273            return Ok(None);
274        }
275        let mut batch = Vec::with_capacity(self.batch_size.get().min(demand.get()));
276        while batch.len() < self.batch_size.get().min(demand.get()) {
277            match self.rows.next() {
278                Some(Ok(row)) => batch.push(row),
279                Some(Err(error)) => return Err(error.into()),
280                None => {
281                    self.exhausted = true;
282                    break;
283                }
284            }
285        }
286        if batch.is_empty() {
287            Ok(None)
288        } else {
289            Ok(Some(Batch::from_physical_rows(self.schema.clone(), batch)))
290        }
291    }
292
293    fn close(&mut self) -> ExecResult<()> {
294        self.exhausted = true;
295        self.rows.close().map_err(Into::into)
296    }
297}
298
299impl VecSource {
300    pub fn new(schema: Vec<String>, rows: Vec<ResultRow>) -> Self {
301        let physical_schema = RowSchema::from_named_columns(schema.clone());
302        Self {
303            schema,
304            physical_schema,
305            rows: rows.into_iter(),
306        }
307    }
308
309    pub fn with_row_schema(physical_schema: RowSchema, rows: Vec<ResultRow>) -> Self {
310        Self {
311            schema: physical_schema.columns().to_vec(),
312            physical_schema,
313            rows: rows.into_iter(),
314        }
315    }
316
317    pub fn with_types(
318        schema: Vec<String>,
319        types: Vec<Option<ColumnType>>,
320        rows: Vec<ResultRow>,
321    ) -> Self {
322        let physical_schema = RowSchema::with_types(schema.clone(), types);
323        Self {
324            schema,
325            physical_schema,
326            rows: rows.into_iter(),
327        }
328    }
329}
330
331impl RowSource for VecSource {
332    fn schema(&self) -> &[String] {
333        &self.schema
334    }
335
336    fn supports_batched_consumption(&self) -> bool {
337        true
338    }
339
340    fn physical_schema(&self) -> Option<&RowSchema> {
341        Some(&self.physical_schema)
342    }
343
344    fn estimated_cardinality(&self) -> Option<u64> {
345        u64::try_from(self.rows.len()).ok()
346    }
347
348    fn next_row(&mut self) -> ExecResult<Option<ResultRow>> {
349        Ok(self.rows.next())
350    }
351}
352
353impl PhysicalVecSource {
354    pub fn new(schema: RowSchema, rows: Vec<PhysicalRow>) -> Self {
355        Self {
356            schema,
357            rows: rows.into_iter(),
358        }
359    }
360}
361
362impl RowSource for PhysicalVecSource {
363    fn schema(&self) -> &[String] {
364        self.schema.columns()
365    }
366
367    fn supports_batched_consumption(&self) -> bool {
368        true
369    }
370
371    fn physical_schema(&self) -> Option<&RowSchema> {
372        Some(&self.schema)
373    }
374
375    fn estimated_cardinality(&self) -> Option<u64> {
376        u64::try_from(self.rows.len()).ok()
377    }
378
379    fn next_row(&mut self) -> ExecResult<Option<ResultRow>> {
380        Ok(self
381            .rows
382            .next()
383            .map(|row| self.schema.view(&row).to_result_row()))
384    }
385
386    fn next_physical_batch(&mut self, max_rows: usize) -> ExecResult<Vec<PhysicalRow>> {
387        Ok(self.rows.by_ref().take(max_rows).collect())
388    }
389}
390
391/// `TableScan`: a leaf operator that drains its [`RowSource`].
392///
393/// Emits batches of at most [`DEFAULT_BATCH_SIZE`] rows. Idempotent
394/// `open` / `close` so the operator can be re-opened in tests.
395pub struct TableScan {
396    source: Option<Box<dyn RowSource>>,
397    schema: RowSchema,
398    ordering: Vec<PhysicalOrder>,
399    estimated_cardinality: Option<u64>,
400    exhausted: bool,
401    _memory: Option<uqa_core::memory::MemoryReservation>,
402}
403
404impl TableScan {
405    pub(crate) fn boxed_with_control(
406        source: Box<dyn RowSource>,
407        control: &uqa_core::memory::ProductionControl<'_>,
408    ) -> Result<Box<Self>, uqa_sql::SQLError> {
409        use uqa_core::memory::ProductionVec;
410        control.check()?;
411        let schema = match source.physical_schema() {
412            Some(schema) => schema.clone(),
413            None => {
414                let mut columns = ProductionVec::new(*control);
415                for column in source.schema() {
416                    columns.push_produced(control.copy_text(column)?)?;
417                }
418                RowSchema::new_with_control(columns.finish()?, control)?
419            }
420        };
421        let mut ordering = ProductionVec::new(*control);
422        for order in source.output_ordering() {
423            ordering.push_produced(control.finish(order.clone(), control.empty_reservation())?)?;
424        }
425        let (ordering, memory) = ordering.finish()?.into_parts();
426        let memory = control.combine(memory, control.reserve(size_of::<Self>())?);
427        let estimated_cardinality = source.estimated_cardinality();
428        Ok(Box::new(Self {
429            source: Some(source),
430            schema,
431            ordering,
432            estimated_cardinality,
433            exhausted: false,
434            _memory: memory,
435        }))
436    }
437
438    pub fn new(source: Box<dyn RowSource>) -> Self {
439        let schema = source
440            .physical_schema()
441            .cloned()
442            .unwrap_or_else(|| RowSchema::new(source.schema().to_vec()));
443        let ordering = source.output_ordering().to_vec();
444        let estimated_cardinality = source.estimated_cardinality();
445        Self {
446            source: Some(source),
447            schema,
448            ordering,
449            estimated_cardinality,
450            exhausted: false,
451            _memory: None,
452        }
453    }
454
455    pub fn from_rows(schema: Vec<String>, rows: Vec<ResultRow>) -> Self {
456        Self::new(Box::new(VecSource::new(schema, rows)))
457    }
458
459    pub fn from_typed_rows(
460        schema: Vec<String>,
461        types: Vec<Option<ColumnType>>,
462        rows: Vec<ResultRow>,
463    ) -> Self {
464        Self::new(Box::new(VecSource::with_types(schema, types, rows)))
465    }
466
467    pub fn from_rows_with_schema(schema: RowSchema, rows: Vec<ResultRow>) -> Self {
468        Self::new(Box::new(VecSource::with_row_schema(schema, rows)))
469    }
470
471    pub fn from_physical_rows(schema: RowSchema, rows: Vec<PhysicalRow>) -> Self {
472        Self::new(Box::new(PhysicalVecSource::new(schema, rows)))
473    }
474}
475
476impl PhysicalOperator for TableScan {
477    fn row_schema(&self) -> &RowSchema {
478        &self.schema
479    }
480
481    fn supports_batched_consumption(&self) -> bool {
482        self.source
483            .as_ref()
484            .is_some_and(|source| source.supports_batched_consumption())
485    }
486
487    fn estimated_cardinality(&self) -> Option<u64> {
488        self.estimated_cardinality
489    }
490
491    fn output_ordering(&self) -> &[PhysicalOrder] {
492        &self.ordering
493    }
494
495    fn backward_scan_support(&self) -> BackwardScanSupport {
496        BackwardScanSupport::Materialize
497    }
498
499    fn consume_into_aggregate(
500        &mut self,
501        executor: &mut dyn crate::relational::AggregateExecutor,
502    ) -> ExecResult<bool> {
503        let Some(source) = self.source.as_mut() else {
504            return Ok(false);
505        };
506        source.consume_into_aggregate(executor)
507    }
508
509    fn collect_materialized(
510        &mut self,
511        sink: &mut crate::query::output::MaterializedResultSink<'_>,
512    ) -> ExecResult<bool> {
513        let Some(source) = self.source.as_mut() else {
514            return Ok(false);
515        };
516        let complete = source.collect_materialized(sink)?;
517        self.exhausted |= complete;
518        Ok(complete)
519    }
520
521    fn open(&mut self) -> ExecResult<()> {
522        self.exhausted = false;
523        Ok(())
524    }
525
526    fn next(&mut self) -> ExecResult<Option<Batch>> {
527        self.next_with_demand(
528            std::num::NonZeroUsize::new(DEFAULT_BATCH_SIZE).expect("nonempty scan batch"),
529        )
530    }
531
532    fn next_with_demand(&mut self, demand: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
533        if self.exhausted {
534            return Ok(None);
535        }
536        let Some(src) = self.source.as_mut() else {
537            return Ok(None);
538        };
539        let buf = src.next_physical_batch(DEFAULT_BATCH_SIZE.min(demand.get()))?;
540        if buf.is_empty() {
541            self.exhausted = true;
542            return Ok(None);
543        }
544        Ok(Some(Batch::from_physical_rows(self.schema.clone(), buf)))
545    }
546
547    fn close(&mut self) -> ExecResult<()> {
548        self.source = None;
549        self.exhausted = true;
550        Ok(())
551    }
552}
553
554#[cfg(test)]
555mod tests {
556    use super::*;
557    use crate::physical::run_to_rows;
558    use uqa_core::Value;
559
560    fn row<const N: usize>(pairs: [(&str, Value); N]) -> ResultRow {
561        pairs.into_iter().map(|(k, v)| (k.to_string(), v)).collect()
562    }
563
564    #[test]
565    fn table_scan_drains_source() {
566        let rows = vec![
567            row([("id", Value::Int(1)), ("name", Value::Str("a".into()))]),
568            row([("id", Value::Int(2)), ("name", Value::Str("b".into()))]),
569        ];
570        let mut scan = TableScan::from_rows(vec!["id".into(), "name".into()], rows);
571        let (cols, rows) = run_to_rows(&mut scan).unwrap();
572        assert_eq!(cols, vec!["id", "name"]);
573        assert_eq!(rows.len(), 2);
574    }
575
576    #[test]
577    fn table_scan_empty_source_returns_no_batch() {
578        let mut scan = TableScan::from_rows(vec!["id".into()], Vec::new());
579        let (_cols, rows) = run_to_rows(&mut scan).unwrap();
580        assert_eq!(rows.len(), 0);
581    }
582
583    #[test]
584    fn iterator_scan_propagates_a_late_producer_error() {
585        let rows = vec![
586            Ok(row([("id", Value::Int(1))])),
587            Err(crate::ExecError::Other("late producer failure".into())),
588        ];
589        let mut scan = RowIteratorScan::new(vec!["id".into()], Box::new(rows.into_iter()));
590        let error = run_to_rows(&mut scan).unwrap_err();
591        assert!(error.to_string().contains("late producer failure"));
592    }
593}