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