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