Skip to main content

vortex_array/scalar_fn/fns/
dynamic_expression.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Predicates with fixed inputs and a body that changes during execution.
5
6use std::fmt::Debug;
7use std::fmt::Display;
8use std::fmt::Formatter;
9use std::hash::Hash;
10use std::hash::Hasher;
11use std::sync::Arc;
12
13use parking_lot::RwLock;
14use vortex_error::VortexResult;
15use vortex_error::vortex_ensure;
16use vortex_session::registry::CachedId;
17
18use crate::ArrayRef;
19use crate::ExecutionCtx;
20use crate::IntoArray;
21use crate::arrays::StructArray;
22use crate::builtins::ArrayBuiltins;
23use crate::dtype::DType;
24use crate::dtype::FieldName;
25use crate::dtype::FieldNames;
26use crate::dtype::Nullability;
27use crate::expr::BoundExpression;
28use crate::expr::display::ExprDisplay;
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::validity::Validity;
35
36/// A source of a predicate that can change while a query runs, such as the build-side bounds of
37/// a hash join or the threshold of a top-N operator in a compute engine.
38pub trait DynamicExpressionSource: Debug + Display + Send + Sync + 'static {
39    /// A monotonically increasing counter, incremented whenever [`Self::current`] can return a
40    /// different predicate, including a bound becoming available or a filter completing.
41    /// A generation must not be reused for another predicate.
42    fn generation(&self) -> u64;
43
44    /// The current predicate, bound against `scope`.
45    ///
46    /// The scope is a struct whose field `i`, named by [`input_field_name`], holds the child `i`
47    /// of the dynamic expression. The predicate must return a boolean.
48    fn current(&self, scope: &DType) -> VortexResult<BoundExpression>;
49}
50
51/// The name of the scope field that holds child `idx` of a dynamic expression.
52pub fn input_field_name(idx: usize) -> FieldName {
53    FieldName::from(idx.to_string())
54}
55
56/// A predicate that a [`DynamicExpressionSource`] can replace while a query runs.
57///
58/// The children of the expression are the inputs that every predicate of the source can read, so
59/// the columns a scan must read are known before the source has its first predicate. Each
60/// evaluation reads the current predicate of the source. This process-local expression is not
61/// serializable.
62#[derive(Clone)]
63pub struct DynamicExpression;
64
65impl ScalarFnVTable for DynamicExpression {
66    type Options = DynamicExpressionOptions;
67
68    fn id(&self) -> ScalarFnId {
69        static ID: CachedId = CachedId::new("vortex.dynamic_expression");
70        *ID
71    }
72
73    fn arity(&self, _options: &Self::Options) -> Arity {
74        Arity::Variadic { min: 0, max: None }
75    }
76
77    fn child_name(&self, _options: &Self::Options, child_idx: usize) -> ChildName {
78        ChildName::from(Arc::from(input_field_name(child_idx).as_ref()))
79    }
80
81    fn fmt_sql(
82        &self,
83        options: &Self::Options,
84        expr: &dyn ExprDisplay,
85        f: &mut Formatter<'_>,
86    ) -> std::fmt::Result {
87        write!(f, "dynamic({}", options.source)?;
88        for idx in 0..expr.display_children_count() {
89            write!(f, ", ")?;
90            Display::fmt(expr.display_child(idx), f)?;
91        }
92        write!(f, ")")
93    }
94
95    fn return_dtype(&self, _options: &Self::Options, _arg_dtypes: &[DType]) -> VortexResult<DType> {
96        // The predicate can change, so the dtype must cover every predicate of the source.
97        Ok(DType::Bool(Nullability::Nullable))
98    }
99
100    fn execute(
101        &self,
102        options: &Self::Options,
103        args: &dyn ExecutionArgs,
104        ctx: &mut ExecutionCtx,
105    ) -> VortexResult<ArrayRef> {
106        let inputs = (0..args.num_inputs())
107            .map(|idx| args.get(idx))
108            .collect::<VortexResult<Vec<_>>>()?;
109        let names = (0..inputs.len())
110            .map(input_field_name)
111            .collect::<FieldNames>();
112        let scope = StructArray::try_new(names, inputs, args.row_count(), Validity::NonNullable)?
113            .into_array();
114
115        let predicate = options.current(scope.dtype())?;
116        scope
117            .apply_bound(&predicate)?
118            .cast(DType::Bool(Nullability::Nullable))?
119            .execute(ctx)
120    }
121}
122
123/// The options of a [`DynamicExpression`]: its source, and the predicate last bound from it.
124#[derive(Clone)]
125pub struct DynamicExpressionOptions {
126    source: Arc<dyn DynamicExpressionSource>,
127    bound: Arc<RwLock<BoundPredicates>>,
128}
129
130/// The predicate of the source as of a generation, bound against each scope it was read with.
131///
132/// A scan reads the predicate with the dtypes of the bound inputs and executes it with the dtypes
133/// of the input arrays, which can differ, so each scope keeps its own binding.
134#[derive(Default)]
135struct BoundPredicates {
136    generation: u64,
137    by_scope: Vec<(DType, BoundExpression)>,
138}
139
140impl DynamicExpressionOptions {
141    /// Create options that read predicates from `source`.
142    pub fn new(source: Arc<dyn DynamicExpressionSource>) -> Self {
143        Self {
144            source,
145            bound: Arc::new(RwLock::new(BoundPredicates::default())),
146        }
147    }
148
149    /// The source of the predicates.
150    pub fn source(&self) -> &Arc<dyn DynamicExpressionSource> {
151        &self.source
152    }
153
154    /// The current predicate of the source, bound against `scope`.
155    ///
156    /// A predicate is bound once for each generation of the source and scope.
157    pub fn current(&self, scope: &DType) -> VortexResult<BoundExpression> {
158        let generation = self.source.generation();
159        {
160            let bound = self.bound.read();
161            if bound.generation == generation
162                && let Some((_, predicate)) = bound
163                    .by_scope
164                    .iter()
165                    .find(|(bound_scope, _)| bound_scope == scope)
166            {
167                return Ok(predicate.clone());
168            }
169        }
170
171        let mut bound = self.bound.write();
172        if bound.generation != generation {
173            bound.generation = generation;
174            bound.by_scope.clear();
175        }
176        if let Some((_, predicate)) = bound
177            .by_scope
178            .iter()
179            .find(|(bound_scope, _)| bound_scope == scope)
180        {
181            return Ok(predicate.clone());
182        }
183
184        let predicate = self.source.current(scope)?;
185        vortex_ensure!(
186            matches!(predicate.dtype(), DType::Bool(_)),
187            "Dynamic expression {} must return a boolean, got {}",
188            self.source,
189            predicate.dtype()
190        );
191        bound.by_scope.push((scope.clone(), predicate.clone()));
192        Ok(predicate)
193    }
194}
195
196impl Debug for DynamicExpressionOptions {
197    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
198        f.debug_struct("DynamicExpressionOptions")
199            .field("source", &self.source)
200            .finish()
201    }
202}
203
204impl Display for DynamicExpressionOptions {
205    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
206        Display::fmt(&self.source, f)
207    }
208}
209
210/// Equality and hashing use the identity of the source, so a new predicate of the source does not
211/// change the identity of the expression tree.
212impl PartialEq for DynamicExpressionOptions {
213    fn eq(&self, other: &Self) -> bool {
214        Arc::ptr_eq(&self.source, &other.source)
215    }
216}
217
218impl Eq for DynamicExpressionOptions {}
219
220impl Hash for DynamicExpressionOptions {
221    fn hash<H: Hasher>(&self, state: &mut H) {
222        Arc::as_ptr(&self.source).cast::<()>().hash(state);
223    }
224}
225
226#[cfg(test)]
227mod tests {
228    use std::sync::atomic::AtomicU64;
229    use std::sync::atomic::Ordering;
230
231    use vortex_buffer::buffer;
232    use vortex_session::VortexSession;
233
234    use super::*;
235    use crate::VortexSessionExecute;
236    use crate::arrays::BoolArray;
237    use crate::assert_arrays_eq;
238    use crate::expr::col;
239    use crate::expr::dynamic_expression;
240    use crate::expr::get_item;
241    use crate::expr::lit;
242    use crate::expr::lt;
243    use crate::expr::root;
244    use crate::scalar_fn::fns::dynamic::DynamicExprUpdates;
245
246    #[derive(Debug, Default)]
247    struct Threshold(AtomicU64);
248
249    impl Display for Threshold {
250        fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
251            write!(f, "threshold")
252        }
253    }
254
255    impl DynamicExpressionSource for Threshold {
256        fn generation(&self) -> u64 {
257            self.0.load(Ordering::SeqCst)
258        }
259
260        fn current(&self, scope: &DType) -> VortexResult<BoundExpression> {
261            match self.generation() {
262                0 => lit(true).bind(scope),
263                value => lt(get_item(input_field_name(0), root()), lit(value)).bind(scope),
264            }
265        }
266    }
267
268    #[test]
269    fn execution_and_update_tracking_follow_current_predicates() -> VortexResult<()> {
270        let threshold = Arc::new(Threshold::default());
271        let expression = dynamic_expression(
272            Arc::clone(&threshold) as Arc<dyn DynamicExpressionSource>,
273            [col("a")],
274        );
275        let input =
276            StructArray::from_fields(&[("a", buffer![1u64, 5, 10].into_array())])?.into_array();
277        let expression = expression.bind(input.dtype())?.optimize_recursive()?;
278        let updates = DynamicExprUpdates::new(&expression).unwrap();
279        let mut ctx = VortexSession::empty().create_execution_ctx();
280        for (value, version, expected) in [
281            (0, 0, [true, true, true]),
282            (6, 1, [true, true, false]),
283            (12, 2, [true, true, true]),
284        ] {
285            threshold.0.store(value, Ordering::SeqCst);
286            assert_eq!(updates.version(), version);
287            assert_eq!(updates.version(), version);
288            assert_arrays_eq!(
289                input.clone().apply_bound(&expression)?,
290                BoolArray::from_iter(expected.map(Some)),
291                &mut ctx
292            );
293        }
294        Ok(())
295    }
296}