Skip to main content

uqa_execution/relational/
filter.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Pipelined WHERE filtering.
8
9use super::{
10    truthy, BackwardScanSupport, Batch, DefaultExpressionEvaluator, ExecError, ExecResult,
11    PhysicalOperator, PhysicalScanDirection, RowSchema, SQLParam, ScalarExpr,
12    SharedExpressionEvaluator, SharedRowPredicate,
13};
14
15use uqa_core::memory::{Produced, ProductionControl};
16use uqa_sql::{plan::OwnedScalarExpr, SQLError};
17
18/// Pipelined `WHERE` operator. Drops rows whose predicate evaluates
19/// to `false` or `NULL`; truthy rows pass through unchanged.
20pub struct Filter<'a> {
21    child: Box<dyn PhysicalOperator + 'a>,
22    input_pending: crate::physical::demand::PendingRows,
23    condition: FilterCondition<'a>,
24    schema: RowSchema,
25    _memory: Option<uqa_core::memory::MemoryReservation>,
26}
27
28enum FilterCondition<'a> {
29    Expression {
30        predicate: crate::scalar::PreparedExpressions<Produced<ScalarExpr>>,
31        evaluator: SharedExpressionEvaluator<'a>,
32    },
33    Row(SharedRowPredicate<'a>),
34    /// A predicate that names a column its input does not produce. Reading that column would yield NULL for every row, so the first input row reports the defect instead.
35    Unresolved(Produced<String>),
36}
37
38impl Filter<'static> {
39    pub fn new(
40        child: Box<dyn PhysicalOperator>,
41        predicate: ScalarExpr,
42        params: Vec<SQLParam>,
43    ) -> Self {
44        Self::with_evaluator(child, predicate, DefaultExpressionEvaluator::shared(params))
45    }
46}
47
48impl<'a> Filter<'a> {
49    pub fn with_evaluator(
50        child: Box<dyn PhysicalOperator + 'a>,
51        predicate: ScalarExpr,
52        evaluator: SharedExpressionEvaluator<'a>,
53    ) -> Self {
54        let schema = child.row_schema().clone();
55        let predicate = evaluator.bind_type_introspection(predicate, &schema);
56        Self {
57            child,
58            input_pending: crate::physical::demand::PendingRows::default(),
59            condition: FilterCondition::Expression {
60                predicate: crate::scalar::PreparedExpressions::produced_scalar(
61                    ProductionControl::uncontrolled()
62                        .finish(predicate, None)
63                        .expect("ordinary predicate"),
64                    &ProductionControl::uncontrolled(),
65                )
66                .expect("ordinary predicate preparation"),
67                evaluator,
68            },
69            schema,
70            _memory: None,
71        }
72    }
73
74    pub fn with_row_predicate(
75        child: Box<dyn PhysicalOperator + 'a>,
76        predicate: SharedRowPredicate<'a>,
77    ) -> Self {
78        let schema = child.row_schema().clone();
79        Self {
80            child,
81            input_pending: crate::physical::demand::PendingRows::default(),
82            condition: FilterCondition::Row(predicate),
83            schema,
84            _memory: None,
85        }
86    }
87
88    /// A filter whose predicate reads `column`, which `child` does not produce. Statement validation reports a user's unknown column before execution, so a row reaching this filter exposes a predicate that was placed on the wrong input; it fails with an internal error instead of reading NULL.
89    pub fn unresolved(child: Box<dyn PhysicalOperator + 'a>, column: String) -> Self {
90        let schema = child.row_schema().clone();
91        Self {
92            child,
93            input_pending: crate::physical::demand::PendingRows::default(),
94            condition: FilterCondition::Unresolved(
95                ProductionControl::uncontrolled()
96                    .finish(column, None)
97                    .expect("ordinary unresolved column"),
98            ),
99            schema,
100            _memory: None,
101        }
102    }
103
104    /// Prepare the admitted predicate while retaining its original child on every failure.
105    pub fn with_owned_predicate(
106        child: Box<dyn PhysicalOperator + 'a>,
107        predicate: OwnedScalarExpr,
108        evaluator: SharedExpressionEvaluator<'a>,
109        control: &ProductionControl<'_>,
110    ) -> Result<Self, SQLError> {
111        let (child, (schema, predicate)) =
112            crate::physical::construction::OperatorBuild::run(child, |child| {
113                let schema = child.row_schema().clone();
114                let predicate =
115                    evaluator.bind_type_introspection_owned(predicate, &schema, control)?;
116                let predicate = crate::scalar::PreparedExpressions::produced_scalar(
117                    predicate.finish(control)?,
118                    control,
119                )?;
120                Ok((schema, predicate))
121            })?;
122        Ok(Self {
123            child,
124            input_pending: crate::physical::demand::PendingRows::default(),
125            condition: FilterCondition::Expression {
126                predicate,
127                evaluator,
128            },
129            schema,
130            _memory: None,
131        })
132    }
133
134    /// Keep a placed-column diagnostic deferred until its input actually produces a row.
135    pub fn with_unresolved_column(
136        child: Box<dyn PhysicalOperator + 'a>,
137        column: Produced<String>,
138    ) -> Self {
139        let schema = child.row_schema().clone();
140        Self {
141            child,
142            input_pending: crate::physical::demand::PendingRows::default(),
143            condition: FilterCondition::Unresolved(column),
144            schema,
145            _memory: None,
146        }
147    }
148
149    pub fn into_boxed(
150        self,
151        control: &ProductionControl<'_>,
152    ) -> Result<Box<dyn PhysicalOperator + 'a>, SQLError> {
153        let Self {
154            child,
155            input_pending,
156            condition,
157            schema,
158            _memory: _,
159        } = self;
160        crate::physical::construction::OperatorBuild::build(child, |owner| {
161            let memory = control.reserve(size_of::<Self>())?;
162            owner.wrap(|child| {
163                Box::new(Self {
164                    child,
165                    input_pending,
166                    condition,
167                    schema,
168                    _memory: memory,
169                })
170            });
171            Ok(())
172        })
173    }
174
175    fn filter_batch(&self, batch: Batch) -> ExecResult<Option<Batch>> {
176        let mut kept = Vec::with_capacity(batch.rows.len());
177        for row in batch.rows {
178            let keep = match &self.condition {
179                FilterCondition::Expression {
180                    predicate,
181                    evaluator,
182                } => truthy(&evaluator.evaluate_physical_with_function_states(
183                    predicate,
184                    &batch.schema,
185                    &row,
186                    predicate.calls(),
187                )?),
188                FilterCondition::Row(predicate) => predicate.keep_physical(&batch.schema, &row)?,
189                FilterCondition::Unresolved(column) => {
190                    return Err(ExecError::SQL(uqa_sql::SQLError::Internal(format!(
191                        "a predicate placed on its input reads {}, which the input does not produce", column.as_str()
192                    ))));
193                }
194            };
195            if keep {
196                kept.push(row);
197            }
198        }
199        Ok((!kept.is_empty()).then(|| Batch::from_physical_rows(self.schema.clone(), kept)))
200    }
201}
202
203impl Filter<'_> {
204    fn pull(&mut self, demand: Option<std::num::NonZeroUsize>) -> ExecResult<Option<Batch>> {
205        let Some(demand) = demand else {
206            loop {
207                let Some(batch) = self.input_pending.pull(self.child.as_mut(), None)? else {
208                    return Ok(None);
209                };
210                if let Some(batch) = self.filter_batch(batch)? {
211                    return Ok(Some(batch));
212                }
213            }
214        };
215        let mut kept = Vec::new();
216        while kept.len() < demand.get() {
217            let Some(batch) = self
218                .input_pending
219                .pull(self.child.as_mut(), Some(crate::physical::demand::ONE))?
220            else {
221                break;
222            };
223            if let Some(batch) = self.filter_batch(batch)? {
224                kept.extend(batch.rows);
225            }
226        }
227        Ok((!kept.is_empty()).then(|| Batch::from_physical_rows(self.schema.clone(), kept)))
228    }
229}
230
231impl PhysicalOperator for Filter<'_> {
232    fn row_schema(&self) -> &RowSchema {
233        &self.schema
234    }
235
236    fn estimated_cardinality(&self) -> Option<u64> {
237        self.child.estimated_cardinality()
238    }
239
240    fn output_ordering(&self) -> &[crate::PhysicalOrder] {
241        self.child.output_ordering()
242    }
243
244    fn backward_scan_support(&self) -> BackwardScanSupport {
245        if self.child.backward_scan_support() == BackwardScanSupport::Native {
246            BackwardScanSupport::Native
247        } else {
248            BackwardScanSupport::Unsupported
249        }
250    }
251
252    fn open(&mut self) -> ExecResult<()> {
253        self.input_pending.clear();
254        self.child.open()
255    }
256
257    fn next(&mut self) -> ExecResult<Option<Batch>> {
258        self.pull(None)
259    }
260
261    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
262        self.pull(Some(rows))
263    }
264
265    fn next_direction(&mut self, direction: PhysicalScanDirection) -> ExecResult<Option<Batch>> {
266        loop {
267            let Some(batch) = self.child.next_direction(direction)? else {
268                return Ok(None);
269            };
270            if let Some(batch) = self.filter_batch(batch)? {
271                return Ok(Some(batch));
272            }
273        }
274    }
275
276    fn rewind(&mut self) -> ExecResult<()> {
277        self.input_pending.clear();
278        self.child.rewind()
279    }
280
281    fn close(&mut self) -> ExecResult<()> {
282        self.input_pending.clear();
283        self.child.close()
284    }
285}
286
287#[cfg(test)]
288mod production_tests;