Skip to main content

uqa_execution/
physical.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Volcano `PhysicalOperator` trait shared by every operator in this crate.
8
9use thiserror::Error;
10
11use crate::batch::{Batch, RowSchema};
12
13/// A leading physical row-order property carried between operators.
14///
15/// `position` is a logical position in the operator's output schema. Positional tracking keeps duplicate labels and structured qualified identities distinct. `nulls_first` is irrelevant when `nullable` is false, which lets a primary-key scan satisfy either explicit NULLS placement without adding a redundant sort.
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct PhysicalOrder {
18    pub position: usize,
19    pub descending: bool,
20    pub nulls_first: Option<bool>,
21    pub nullable: bool,
22}
23
24/// Operator-pipeline error type. Wraps SQL evaluation errors so call
25/// sites do not need to juggle two error enums.
26#[derive(Debug, Error)]
27pub enum ExecError {
28    #[error("execution error: {0}")]
29    Other(String),
30    #[error("SQL error: {0}")]
31    SQL(#[from] uqa_sql::SQLError),
32}
33
34impl From<uqa_sql::schema::SchemaLayoutError> for ExecError {
35    fn from(error: uqa_sql::schema::SchemaLayoutError) -> Self {
36        Self::Other(error.to_string())
37    }
38}
39
40pub type ExecResult<T> = std::result::Result<T, ExecError>;
41
42/// Direction requested by a scrollable query consumer.
43#[derive(Debug, Clone, Copy, PartialEq, Eq)]
44pub enum PhysicalScanDirection {
45    Forward,
46    Backward,
47}
48
49/// How an operator participates in a backwards-capable pipeline.
50#[derive(Debug, Clone, Copy, PartialEq, Eq)]
51pub enum BackwardScanSupport {
52    /// The operator cannot preserve `PostgreSQL` backwards-scan semantics. A scrollable cursor must materialize the completed plan above it.
53    Unsupported,
54    /// The operator's output is a semantic materialization boundary and may be placed in a directional spool before parent expressions run.
55    Materialize,
56    /// The operator natively accepts [`PhysicalScanDirection`] and can rewind without rebuilding its semantic state.
57    Native,
58}
59
60/// Preserve the primary execution result while still surfacing a cleanup
61/// failure. `Result::and` discards the cleanup error whenever both operations
62/// fail, which makes file/child-close failures disappear behind the original
63/// operator error.
64pub(crate) fn with_cleanup<T>(
65    primary: ExecResult<T>,
66    cleanup: ExecResult<()>,
67    cleanup_context: &str,
68) -> ExecResult<T> {
69    match (primary, cleanup) {
70        (Ok(value), Ok(())) => Ok(value),
71        (Ok(_), Err(cleanup_error)) => Err(cleanup_error),
72        (Err(primary_error), Ok(())) => Err(primary_error),
73        (Err(primary_error), Err(cleanup_error)) => Err(ExecError::Other(format!(
74            "{primary_error}; {cleanup_context}: {cleanup_error}"
75        ))),
76    }
77}
78
79/// Volcano-style streaming operator. Operators form a tree; each
80/// operator pulls from its children inside `next` and emits a
81/// [`Batch`] until the input is exhausted.
82///
83/// Pipeline lifecycle:
84///
85/// 1. `open` -- bind state, open child operators, allocate buffers.
86/// 2. `next` -- pull the next [`Batch`]; return `None` to terminate.
87/// 3. `close` -- release buffers and close child operators.
88///
89/// Blocking operators (sort / hash-aggregate) materialise their input
90/// during `open`; pipelined operators (filter / project / limit) emit
91/// batches as they arrive.
92pub trait PhysicalOperator: Send {
93    /// Complete logical-to-physical row layout emitted by this operator. Every [`Batch`] returned by [`Self::next`] must carry this exact schema; operators must reject a child that violates that invariant.
94    fn row_schema(&self) -> &RowSchema;
95
96    /// Schema column names in logical output order.
97    fn schema(&self) -> &[String] {
98        self.row_schema().columns()
99    }
100
101    /// Planner/runtime cardinality estimate for choosing physical strategies.
102    /// `None` means the operator cannot provide a useful estimate. The value
103    /// is advisory rather than a correctness bound.
104    fn estimated_cardinality(&self) -> Option<u64> {
105        None
106    }
107
108    /// Leading output ordering known to be preserved by this operator.
109    fn output_ordering(&self) -> &[PhysicalOrder] {
110        &[]
111    }
112
113    /// Let a leaf consume its native projected rows directly into an
114    /// aggregate executor. Returning `false` promises that no input was
115    /// consumed, so the caller can fall back to ordinary `Batch` pulls.
116    fn consume_into_aggregate(
117        &mut self,
118        _executor: &mut dyn crate::relational::AggregateExecutor,
119    ) -> ExecResult<bool> {
120        Ok(false)
121    }
122
123    /// Describe backwards-scan support without changing the operator tree. The default is deliberately conservative so a scrollable cursor freezes the complete output of unclassified plans.
124    fn backward_scan_support(&self) -> BackwardScanSupport {
125        BackwardScanSupport::Unsupported
126    }
127
128    fn open(&mut self) -> ExecResult<()>;
129    fn next(&mut self) -> ExecResult<Option<Batch>>;
130    /// Pull one directional batch. Native backwards-capable pipelines keep batches to one row so a consumer can reverse direction between adjacent fetches.
131    fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
132        match direction {
133            PhysicalScanDirection::Forward => self.next(),
134            PhysicalScanDirection::Backward => Err(ExecError::Other(
135                "physical operator does not support backwards scanning".into(),
136            )),
137        }
138    }
139    /// Rewind a native backwards-capable pipeline without recomputing rows held by semantic materialization boundaries.
140    fn rewind(&mut self) -> ExecResult<()> {
141        Err(ExecError::Other(
142            "physical operator does not support rewind".into(),
143        ))
144    }
145    fn close(&mut self) -> ExecResult<()>;
146}
147
148/// Return whether `actual` has `required` as an ordering prefix.
149pub fn ordering_satisfies(actual: &[PhysicalOrder], required: &[PhysicalOrder]) -> bool {
150    actual.len() >= required.len()
151        && actual.iter().zip(required).all(|(actual, required)| {
152            actual.position == required.position
153                && actual.descending == required.descending
154                && (!actual.nullable
155                    || actual.nulls_first == required.nulls_first
156                    || required.nulls_first.is_none())
157        })
158}
159
160/// Resolve a simple ordering expression to one logical position without collapsing duplicate or qualified SQL identities into a display label.
161pub fn order_expression_position(
162    schema: &RowSchema,
163    expression: &crate::ScalarExpr,
164) -> Option<usize> {
165    match expression {
166        crate::ScalarExpr::Column(column) => schema.unqualified_position(column),
167        crate::ScalarExpr::Position(position) => (*position < schema.len()).then_some(*position),
168        crate::ScalarExpr::QualifiedColumn { qualifier, column } => {
169            schema.qualified_position(qualifier, column)
170        }
171        _ => None,
172    }
173}
174
175/// Borrowing iterator over a physical operator. Construction opens the
176/// pipeline; exhaustion and execution errors close it exactly once. Dropping
177/// an unfinished cursor performs best-effort cleanup.
178pub struct OperatorBatchCursor<'operator> {
179    operator: &'operator mut dyn PhysicalOperator,
180    finished: bool,
181}
182
183impl<'operator> OperatorBatchCursor<'operator> {
184    pub fn open(operator: &'operator mut dyn PhysicalOperator) -> ExecResult<Self> {
185        if let Err(open_error) = operator.open() {
186            return match operator.close() {
187                Ok(()) => Err(open_error),
188                Err(close_error) => Err(ExecError::Other(format!(
189                    "{open_error}; operator close after open failure also failed: {close_error}"
190                ))),
191            };
192        }
193        Ok(Self {
194            operator,
195            finished: false,
196        })
197    }
198
199    fn finish(&mut self) -> ExecResult<()> {
200        if self.finished {
201            return Ok(());
202        }
203        self.finished = true;
204        self.operator.close()
205    }
206}
207
208impl Iterator for OperatorBatchCursor<'_> {
209    type Item = ExecResult<Batch>;
210
211    fn next(&mut self) -> Option<Self::Item> {
212        if self.finished {
213            return None;
214        }
215        match self.operator.next() {
216            Ok(Some(batch)) => Some(Ok(batch)),
217            Ok(None) => match self.finish() {
218                Ok(()) => None,
219                Err(error) => Some(Err(error)),
220            },
221            Err(next_error) => {
222                let close = self.finish();
223                Some(with_cleanup(
224                    Err(next_error),
225                    close,
226                    "operator close after execution failure also failed",
227                ))
228            }
229        }
230    }
231}
232
233impl Drop for OperatorBatchCursor<'_> {
234    fn drop(&mut self) {
235        let _ = self.finish();
236    }
237}
238
239/// Convenience: collect every batch from `op` until exhaustion. The
240/// operator is `open`ed and `close`d for the caller. Useful for tests
241/// and for callers that do not need streaming behaviour.
242pub fn run_to_batches(op: &mut dyn PhysicalOperator) -> ExecResult<Vec<Batch>> {
243    OperatorBatchCursor::open(op)?.collect()
244}
245
246/// Run the operator and concatenate all output batches into a single
247/// flat row vector. The schema of the first batch is the result schema.
248pub fn run_to_rows(
249    op: &mut dyn PhysicalOperator,
250) -> ExecResult<(Vec<String>, Vec<uqa_sql::ResultRow>)> {
251    let schema = op.schema().to_vec();
252    let mut rows: Vec<uqa_sql::ResultRow> = Vec::new();
253    for batch in OperatorBatchCursor::open(op)? {
254        let batch = batch?;
255        rows.extend(batch.into_result_rows());
256    }
257    Ok((schema, rows))
258}
259
260/// Preserve the SQL error reported by a physical operator.
261pub fn physical_exec_error(error: crate::ExecError) -> uqa_sql::SQLError {
262    match error {
263        crate::ExecError::SQL(error) => error,
264        crate::ExecError::Other(message) => uqa_sql::SQLError::Internal(message),
265    }
266}
267
268#[cfg(test)]
269mod tests {
270    use super::*;
271
272    struct FailingOperator {
273        fail_open: bool,
274        fail_close: bool,
275        closed: bool,
276    }
277
278    impl PhysicalOperator for FailingOperator {
279        fn row_schema(&self) -> &RowSchema {
280            static SCHEMA: std::sync::OnceLock<RowSchema> = std::sync::OnceLock::new();
281            SCHEMA.get_or_init(RowSchema::default)
282        }
283
284        fn open(&mut self) -> ExecResult<()> {
285            if self.fail_open {
286                Err(ExecError::Other("open failed".into()))
287            } else {
288                Ok(())
289            }
290        }
291
292        fn next(&mut self) -> ExecResult<Option<Batch>> {
293            Err(ExecError::Other("next failed".into()))
294        }
295
296        fn close(&mut self) -> ExecResult<()> {
297            self.closed = true;
298            if self.fail_close {
299                Err(ExecError::Other("close failed".into()))
300            } else {
301                Ok(())
302            }
303        }
304    }
305
306    #[test]
307    fn runner_closes_after_open_and_next_failures() {
308        let mut open = FailingOperator {
309            fail_open: true,
310            fail_close: false,
311            closed: false,
312        };
313        assert!(run_to_batches(&mut open)
314            .unwrap_err()
315            .to_string()
316            .contains("open failed"));
317        assert!(open.closed);
318
319        let mut next = FailingOperator {
320            fail_open: false,
321            fail_close: false,
322            closed: false,
323        };
324        assert!(run_to_batches(&mut next)
325            .unwrap_err()
326            .to_string()
327            .contains("next failed"));
328        assert!(next.closed);
329    }
330
331    #[test]
332    fn runner_reports_execution_and_cleanup_failures() {
333        let mut operator = FailingOperator {
334            fail_open: false,
335            fail_close: true,
336            closed: false,
337        };
338        let error = run_to_batches(&mut operator).unwrap_err().to_string();
339        assert!(error.contains("next failed"), "{error}");
340        assert!(error.contains("close failed"), "{error}");
341        assert!(operator.closed);
342    }
343
344    #[test]
345    fn cleanup_combiner_preserves_both_errors() {
346        let error = with_cleanup::<()>(
347            Err(ExecError::Other("primary".into())),
348            Err(ExecError::Other("cleanup".into())),
349            "cleanup failed",
350        )
351        .unwrap_err()
352        .to_string();
353        assert!(error.contains("primary"), "{error}");
354        assert!(error.contains("cleanup"), "{error}");
355    }
356
357    #[test]
358    fn dropping_cursor_closes_an_unfinished_pipeline() {
359        let mut operator = FailingOperator {
360            fail_open: false,
361            fail_close: false,
362            closed: false,
363        };
364        {
365            let _cursor = OperatorBatchCursor::open(&mut operator).unwrap();
366        }
367        assert!(operator.closed);
368    }
369
370    #[test]
371    fn ordering_positions_keep_duplicate_structured_identities_distinct() {
372        let schema = RowSchema::with_identities(
373            vec!["id".into(), "id".into()],
374            vec![
375                crate::ColumnIdentity::qualified("left", "id"),
376                crate::ColumnIdentity::qualified("right", "id"),
377            ],
378            vec![None, None],
379        );
380        assert_eq!(
381            order_expression_position(&schema, &crate::ScalarExpr::qualified_column("left", "id")),
382            Some(0)
383        );
384        assert_eq!(
385            order_expression_position(&schema, &crate::ScalarExpr::qualified_column("right", "id")),
386            Some(1)
387        );
388        assert_eq!(
389            order_expression_position(&schema, &crate::ScalarExpr::Column("id".into())),
390            None
391        );
392        let actual = [PhysicalOrder {
393            position: 0,
394            descending: false,
395            nulls_first: None,
396            nullable: false,
397        }];
398        let required = [PhysicalOrder {
399            position: 1,
400            descending: false,
401            nulls_first: Some(false),
402            nullable: true,
403        }];
404        assert!(!ordering_satisfies(&actual, &required));
405    }
406}