Skip to main content

vortex_array/scalar_fn/fns/
dynamic.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Debug;
5use std::fmt::Display;
6use std::fmt::Formatter;
7use std::hash::Hash;
8use std::hash::Hasher;
9use std::sync::Arc;
10
11use parking_lot::Mutex;
12use vortex_error::VortexExpect;
13use vortex_error::VortexResult;
14use vortex_error::vortex_bail;
15use vortex_session::registry::CachedId;
16
17use crate::ArrayRef;
18use crate::ExecutionCtx;
19use crate::IntoArray;
20use crate::arrays::ConstantArray;
21use crate::dtype::DType;
22use crate::expr::BoundExpression;
23use crate::expr::display::ExprDisplay;
24use crate::expr::traversal::NodeExt;
25use crate::expr::traversal::NodeVisitor;
26use crate::expr::traversal::TraversalOrder;
27use crate::scalar::Scalar;
28use crate::scalar::ScalarValue;
29use crate::scalar_fn::Arity;
30use crate::scalar_fn::ChildName;
31use crate::scalar_fn::ExecutionArgs;
32use crate::scalar_fn::ScalarFnId;
33use crate::scalar_fn::ScalarFnVTable;
34use crate::scalar_fn::ScalarFnVTableExt;
35use crate::scalar_fn::VecExecutionArgs;
36use crate::scalar_fn::fns::binary::Binary;
37use crate::scalar_fn::fns::dynamic_expression::DynamicExpression;
38use crate::scalar_fn::fns::dynamic_expression::DynamicExpressionSource;
39use crate::scalar_fn::fns::operators::CompareOperator;
40use crate::scalar_fn::fns::operators::Operator;
41
42/// A dynamic comparison expression can be used to capture a comparison to a value that can change
43/// during the execution of a query, such as when a compute engine pushes down an ORDER BY + LIMIT
44/// operation and is able to progressively tighten the bounds of the filter.
45#[derive(Clone)]
46pub struct DynamicComparison;
47
48impl ScalarFnVTable for DynamicComparison {
49    type Options = DynamicComparisonExpr;
50
51    fn id(&self) -> ScalarFnId {
52        static ID: CachedId = CachedId::new("vortex.dynamic");
53        *ID
54    }
55
56    fn arity(&self, _options: &Self::Options) -> Arity {
57        Arity::Exact(1)
58    }
59
60    fn child_name(&self, _instance: &Self::Options, child_idx: usize) -> ChildName {
61        match child_idx {
62            0 => ChildName::from("lhs"),
63            _ => unreachable!(),
64        }
65    }
66
67    fn fmt_sql(
68        &self,
69        dynamic: &DynamicComparisonExpr,
70        expr: &dyn ExprDisplay,
71        f: &mut Formatter<'_>,
72    ) -> std::fmt::Result {
73        Display::fmt(expr.display_child(0), f)?;
74        write!(f, " {} dynamic(", dynamic.operator)?;
75        match dynamic.scalar() {
76            None => write!(f, "scalar=<none>")?,
77            Some(scalar) => write!(f, "scalar={scalar}")?,
78        }
79        write!(f, ")")
80    }
81
82    fn return_dtype(
83        &self,
84        dynamic: &DynamicComparisonExpr,
85        arg_dtypes: &[DType],
86    ) -> VortexResult<DType> {
87        let lhs = &arg_dtypes[0];
88        if !dynamic.rhs.dtype.eq_ignore_nullability(lhs) {
89            vortex_bail!(
90                "Incompatible dtypes for dynamic comparison: expected {} (ignore nullability) but got {}",
91                &dynamic.rhs.dtype,
92                lhs
93            );
94        }
95        Ok(DType::Bool(
96            lhs.nullability() | dynamic.rhs.dtype.nullability(),
97        ))
98    }
99
100    fn execute(
101        &self,
102        data: &Self::Options,
103        args: &dyn ExecutionArgs,
104        ctx: &mut ExecutionCtx,
105    ) -> VortexResult<ArrayRef> {
106        if let Some(scalar) = data.rhs.scalar() {
107            let lhs = args.get(0)?;
108            let rhs = ConstantArray::new(scalar, args.row_count()).into_array();
109
110            let delegate_args = VecExecutionArgs::new(vec![lhs, rhs], args.row_count());
111            return Binary
112                .bind(Operator::from(data.operator))
113                .execute(&delegate_args, ctx);
114        }
115        let ret_dtype =
116            DType::Bool(args.get(0)?.dtype().nullability() | data.rhs.dtype.nullability());
117
118        Ok(ConstantArray::new(
119            Scalar::try_new(ret_dtype, Some(data.default.into()))?,
120            args.row_count(),
121        )
122        .into_array())
123    }
124
125    fn is_strict(&self, _options: &Self::Options) -> bool {
126        false
127    }
128
129    /// A dynamic comparison is a comparison, or a constant while it has no value to compare
130    /// against, and neither can fail.
131    fn is_infallible(&self, _options: &Self::Options) -> bool {
132        true
133    }
134}
135
136#[derive(Clone, Debug)]
137pub struct DynamicComparisonExpr {
138    pub(crate) operator: CompareOperator,
139    pub(crate) rhs: Arc<Rhs>,
140    // Default value for the dynamic comparison.
141    pub(crate) default: bool,
142}
143
144impl DynamicComparisonExpr {
145    /// The comparison applied between the input and the dynamic value.
146    pub fn operator(&self) -> CompareOperator {
147        self.operator
148    }
149
150    /// The result used while the dynamic value is not yet known.
151    pub fn default(&self) -> bool {
152        self.default
153    }
154
155    /// A comparison against the same dynamic value with a different operator and default.
156    pub fn with_operator(&self, operator: CompareOperator, default: bool) -> Self {
157        Self {
158            operator,
159            rhs: Arc::clone(&self.rhs),
160            default,
161        }
162    }
163
164    pub fn scalar(&self) -> Option<Scalar> {
165        (self.rhs.value)().map(|v| {
166            Scalar::try_new(self.rhs.dtype.clone(), Some(v))
167                .vortex_expect("`DynamicComparisonExpr` was invalid")
168        })
169    }
170}
171
172impl Display for DynamicComparisonExpr {
173    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
174        write!(
175            f,
176            "{} {}",
177            self.operator,
178            self.scalar()
179                .map_or_else(|| "<none>".to_string(), |v| v.to_string())
180        )
181    }
182}
183
184impl PartialEq for DynamicComparisonExpr {
185    fn eq(&self, other: &Self) -> bool {
186        self.operator == other.operator
187            && Arc::ptr_eq(&self.rhs, &other.rhs)
188            && self.default == other.default
189    }
190}
191impl Eq for DynamicComparisonExpr {}
192
193impl Hash for DynamicComparisonExpr {
194    fn hash<H: Hasher>(&self, state: &mut H) {
195        self.operator.hash(state);
196        Arc::as_ptr(&self.rhs).hash(state);
197        self.default.hash(state);
198    }
199}
200
201/// Hash and PartialEq are implemented based on the ptr of the value function, such that the
202/// internal value doesn't impact the hash of an expression tree.
203pub(crate) struct Rhs {
204    // The right-hand side value is a function that returns an `Option<ScalarValue>`.
205    pub(crate) value: Arc<dyn Fn() -> Option<ScalarValue> + Send + Sync>,
206    // The data type of the right-hand side value.
207    pub(crate) dtype: DType,
208}
209
210impl Rhs {
211    pub fn scalar(&self) -> Option<Scalar> {
212        (self.value)().map(|v| {
213            Scalar::try_new(self.dtype.clone(), Some(v)).vortex_expect("`Rhs` was invalid")
214        })
215    }
216}
217
218impl Debug for Rhs {
219    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
220        f.debug_struct("Rhs")
221            .field("value", &"<dyn Fn() -> Option<ScalarValue> + Send + Sync>")
222            .field("dtype", &self.dtype)
223            .finish()
224    }
225}
226
227/// A utility for checking whether any dynamic expressions have been updated.
228pub struct DynamicExprUpdates {
229    exprs: Box<[DynamicComparisonExpr]>,
230    sources: Box<[Arc<dyn DynamicExpressionSource>]>,
231    // Track the latest observed versions of each dynamic expression, along with a version counter.
232    prev_versions: Mutex<ObservedVersions>,
233}
234
235struct ObservedVersions {
236    version: u64,
237    scalars: Vec<Option<Scalar>>,
238    generations: Vec<u64>,
239}
240
241impl DynamicExprUpdates {
242    /// Track dynamic scalar functions contained in a bound expression tree.
243    pub fn new(expr: &BoundExpression) -> Option<Self> {
244        #[derive(Default)]
245        struct Visitor {
246            exprs: Vec<DynamicComparisonExpr>,
247            sources: Vec<Arc<dyn DynamicExpressionSource>>,
248        }
249
250        impl NodeVisitor<'_> for Visitor {
251            type NodeTy = BoundExpression;
252
253            fn visit_down(&mut self, node: &'_ Self::NodeTy) -> VortexResult<TraversalOrder> {
254                if let Some(dynamic) = node.as_opt::<DynamicComparison>() {
255                    self.exprs.push(dynamic.clone());
256                }
257                if let Some(dynamic) = node.as_opt::<DynamicExpression>() {
258                    self.sources.push(Arc::clone(dynamic.source()));
259                }
260                Ok(TraversalOrder::Continue)
261            }
262        }
263
264        let mut visitor = Visitor::default();
265        expr.accept(&mut visitor).vortex_expect("Infallible");
266
267        if visitor.exprs.is_empty() && visitor.sources.is_empty() {
268            return None;
269        }
270
271        let exprs = visitor.exprs.into_boxed_slice();
272        let sources = visitor.sources.into_boxed_slice();
273        let scalars = exprs
274            .iter()
275            .map(|expr| {
276                (expr.rhs.value)().map(|v| {
277                    Scalar::try_new(expr.rhs.dtype.clone(), Some(v))
278                        .vortex_expect("`DynamicExprUpdates` was invalid")
279                })
280            })
281            .collect();
282        let generations = sources.iter().map(|source| source.generation()).collect();
283
284        Some(Self {
285            exprs,
286            sources,
287            prev_versions: Mutex::new(ObservedVersions {
288                version: 0,
289                scalars,
290                generations,
291            }),
292        })
293    }
294
295    pub fn version(&self) -> u64 {
296        let mut guard = self.prev_versions.lock();
297
298        let mut updated = false;
299        for (i, expr) in self.exprs.iter().enumerate() {
300            let current = expr.scalar();
301            if current != guard.scalars[i] {
302                // At least one expression has been updated.
303                // We don't bail out early in order to avoid false positives for future calls
304                // to `is_updated`.
305                updated = true;
306                guard.scalars[i] = current;
307            }
308        }
309        for (i, source) in self.sources.iter().enumerate() {
310            let current = source.generation();
311            if current != guard.generations[i] {
312                updated = true;
313                guard.generations[i] = current;
314            }
315        }
316
317        if updated {
318            guard.version += 1;
319        }
320
321        guard.version
322    }
323}
324
325#[cfg(test)]
326mod tests {
327    use std::sync::LazyLock;
328    use std::sync::atomic::AtomicI32;
329    use std::sync::atomic::Ordering;
330
331    use vortex_buffer::buffer;
332    use vortex_error::VortexResult;
333    use vortex_session::VortexSession;
334
335    use super::*;
336    use crate::IntoArray;
337    use crate::VortexSessionExecute;
338    use crate::arrays::BoolArray;
339    use crate::assert_arrays_eq;
340    use crate::dtype::DType;
341    use crate::dtype::Nullability;
342    use crate::dtype::PType;
343    use crate::expr::dynamic;
344    use crate::expr::root;
345
346    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
347
348    #[test]
349    fn is_not_strict() {
350        let expr = dynamic(
351            CompareOperator::Lt,
352            || None,
353            DType::Primitive(PType::I32, Nullability::NonNullable),
354            true,
355            root(),
356        );
357
358        assert!(!expr.as_scalar().is_some_and(|f| f.signature().is_strict()));
359    }
360
361    #[test]
362    fn return_dtype_bool() -> VortexResult<()> {
363        let expr = dynamic(
364            CompareOperator::Lt,
365            || Some(5i32.into()),
366            DType::Primitive(PType::I32, Nullability::NonNullable),
367            true,
368            root(),
369        );
370        let input_dtype = DType::Primitive(PType::I32, Nullability::NonNullable);
371        assert_eq!(
372            expr.return_dtype(&input_dtype)?,
373            DType::Bool(Nullability::NonNullable)
374        );
375        Ok(())
376    }
377
378    #[test]
379    fn execute_with_value() -> VortexResult<()> {
380        let mut ctx = SESSION.create_execution_ctx();
381        let input = buffer![1i32, 5, 10].into_array();
382        let expr = dynamic(
383            CompareOperator::Lt,
384            || Some(5i32.into()),
385            DType::Primitive(PType::I32, Nullability::NonNullable),
386            true,
387            root(),
388        );
389        let result = input.apply(&expr)?;
390        assert_arrays_eq!(result, BoolArray::from_iter([true, false, false]), &mut ctx);
391        Ok(())
392    }
393
394    #[test]
395    fn execute_without_value_default_true() -> VortexResult<()> {
396        let mut ctx = SESSION.create_execution_ctx();
397        let input = buffer![1i32, 5, 10].into_array();
398        let expr = dynamic(
399            CompareOperator::Lt,
400            || None,
401            DType::Primitive(PType::I32, Nullability::NonNullable),
402            true,
403            root(),
404        );
405        let result = input.apply(&expr)?;
406        assert_arrays_eq!(result, BoolArray::from_iter([true, true, true]), &mut ctx);
407        Ok(())
408    }
409
410    #[test]
411    fn execute_without_value_default_false() -> VortexResult<()> {
412        let mut ctx = SESSION.create_execution_ctx();
413        let input = buffer![1i32, 5, 10].into_array();
414        let expr = dynamic(
415            CompareOperator::Lt,
416            || None,
417            DType::Primitive(PType::I32, Nullability::NonNullable),
418            false,
419            root(),
420        );
421        let result = input.apply(&expr)?;
422        assert_arrays_eq!(
423            result,
424            BoolArray::from_iter([false, false, false]),
425            &mut ctx
426        );
427        Ok(())
428    }
429
430    #[test]
431    fn execute_value_flips() -> VortexResult<()> {
432        let mut ctx = SESSION.create_execution_ctx();
433        let threshold = Arc::new(AtomicI32::new(5));
434        let threshold_clone = Arc::clone(&threshold);
435        let expr = dynamic(
436            CompareOperator::Lt,
437            move || Some(threshold_clone.load(Ordering::SeqCst).into()),
438            DType::Primitive(PType::I32, Nullability::NonNullable),
439            true,
440            root(),
441        );
442        let input = buffer![1i32, 5, 10].into_array();
443
444        let result = input.clone().apply(&expr)?;
445        assert_arrays_eq!(result, BoolArray::from_iter([true, false, false]), &mut ctx);
446
447        threshold.store(10, Ordering::SeqCst);
448        let result = input.apply(&expr)?;
449        assert_arrays_eq!(result, BoolArray::from_iter([true, true, false]), &mut ctx);
450
451        Ok(())
452    }
453}