Skip to main content

vortex_array/expr/
optimize.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use vortex_error::VortexResult;
5
6use crate::expr::BoundExpression;
7use crate::scalar_fn::ExpressionReduceNode;
8
9impl BoundExpression {
10    /// Optimize the root expression node only, iterating to convergence.
11    ///
12    /// This applies optimization rules repeatedly until no more changes occur:
13    /// 1. `simplify` - scalar-function simplifications over the bound node
14    /// 2. `reduce` - abstract reduction rules via `ReduceNode`
15    pub fn optimize(&self) -> VortexResult<BoundExpression> {
16        Ok(self.try_optimize()?.unwrap_or_else(|| self.clone()))
17    }
18
19    /// Apply this node's own simplification rule, if it has one.
20    ///
21    /// Non-scalar nodes carry no rules, so they never simplify.
22    fn simplify_node(&self) -> VortexResult<Option<BoundExpression>> {
23        match self {
24            BoundExpression::Scalar { scalar_fn, .. } => scalar_fn.simplify(self),
25            BoundExpression::Root { .. } => Ok(None),
26        }
27    }
28
29    /// Apply this node's own abstract reduction rule, if it has one.
30    fn reduce_node<'a>(
31        &self,
32        node: &ExpressionReduceNode<'a>,
33    ) -> VortexResult<Option<ExpressionReduceNode<'a>>> {
34        match self {
35            BoundExpression::Scalar { scalar_fn, .. } => scalar_fn.reduce_expression(node),
36            BoundExpression::Root { .. } => Ok(None),
37        }
38    }
39
40    /// Try to optimize the root expression node only, returning None if no optimizations applied.
41    fn try_optimize(&self) -> VortexResult<Option<BoundExpression>> {
42        // Copy-on-write: `current` stays None until a rule fires, so unchanged nodes (the common
43        // case) are never cloned.
44        let mut current: Option<BoundExpression> = None;
45        let mut loop_counter = 0;
46
47        loop {
48            if loop_counter > 100 {
49                vortex_error::vortex_bail!(
50                    "Exceeded maximum optimization iterations (possible infinite loop)"
51                );
52            }
53            loop_counter += 1;
54
55            let expr = current.as_ref().unwrap_or(self);
56            let mut changed = false;
57
58            if let Some(simplified) = expr.simplify_node()? {
59                current = Some(simplified);
60                changed = true;
61            }
62
63            // Try reduce via ReduceNode. The node borrows the expression, so constructing it is
64            // free; the block scopes the borrow so `current` can be updated.
65            let reduced = {
66                let expr = current.as_ref().unwrap_or(self);
67                expr.reduce_node(&ExpressionReduceNode::new(expr))?
68                    .map(ExpressionReduceNode::into_expression)
69            };
70            if let Some(reduced_expr) = reduced {
71                current = Some(reduced_expr);
72                changed = true;
73            }
74
75            if !changed {
76                break;
77            }
78        }
79
80        Ok(current)
81    }
82
83    /// Optimize the entire expression tree recursively.
84    ///
85    /// Optimizes children first (bottom-up), then optimizes the root.
86    pub fn optimize_recursive(&self) -> VortexResult<BoundExpression> {
87        Ok(self
88            .try_optimize_recursive()?
89            .unwrap_or_else(|| self.clone()))
90    }
91
92    /// Try to optimize the entire expression tree recursively.
93    pub fn try_optimize_recursive(&self) -> VortexResult<Option<BoundExpression>> {
94        // First optimize the root
95        let mut current = self.try_optimize()?;
96
97        // Then recursively optimize children. The new children vector is only allocated once a
98        // child actually changes, so fully-optimized subtrees cost no allocations.
99        let expr = current.as_ref().unwrap_or(self);
100        let children = expr.children();
101        let mut new_children: Option<Vec<BoundExpression>> = None;
102        for (idx, child) in children.iter().enumerate() {
103            if let Some(optimized) = child.try_optimize_recursive()? {
104                new_children
105                    .get_or_insert_with(|| children[..idx].to_vec())
106                    .push(optimized);
107            } else if let Some(new_children) = new_children.as_mut() {
108                new_children.push(child.clone());
109            }
110        }
111
112        if let Some(new_children) = new_children {
113            let updated = expr.clone().with_children(new_children)?;
114
115            // After updating children, try to optimize root again
116            current = Some(updated.try_optimize()?.unwrap_or(updated));
117        }
118
119        Ok(current)
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use std::sync::LazyLock;
126
127    use rstest::rstest;
128    use vortex_buffer::buffer;
129    use vortex_error::VortexResult;
130    use vortex_error::vortex_err;
131    use vortex_session::VortexSession;
132
133    use crate::IntoArray;
134    use crate::VortexSessionExecute;
135    use crate::arrays::BoolArray;
136    use crate::arrays::StructArray;
137    use crate::assert_arrays_eq;
138    use crate::dtype::DType;
139    use crate::dtype::FieldName;
140    use crate::dtype::Nullability;
141    use crate::dtype::PType;
142    use crate::dtype::StructFields;
143    use crate::expr::Expression;
144    use crate::expr::and;
145    use crate::expr::cast;
146    use crate::expr::eq;
147    use crate::expr::get_item;
148    use crate::expr::lit;
149    use crate::expr::lt_eq;
150    use crate::expr::merge;
151    use crate::expr::or;
152    use crate::expr::pack;
153    use crate::expr::root;
154    use crate::expr::select;
155    use crate::expr::zip_expr;
156    use crate::scalar::Scalar;
157    use crate::scalar_fn::fns::literal::Literal;
158
159    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
160
161    #[test]
162    fn optimize_or_chain_correctness() -> VortexResult<()> {
163        let expr = or(
164            eq(get_item("x", root()), lit(1i32)),
165            eq(get_item("x", root()), lit(2i32)),
166        );
167        let scope = DType::Struct(
168            StructFields::new(
169                ["x"].into(),
170                vec![DType::Primitive(PType::I32, Nullability::NonNullable)],
171            ),
172            Nullability::NonNullable,
173        );
174        let optimized = expr.bind(&scope)?.optimize_recursive()?;
175
176        let data =
177            StructArray::from_fields(&[("x", buffer![0i32, 1, 2, 3].into_array())])?.into_array();
178        let actual = data.apply_bound(&optimized)?;
179        assert_arrays_eq!(
180            actual,
181            BoolArray::from_iter([false, true, true, false]),
182            &mut SESSION.create_execution_ctx()
183        );
184        Ok(())
185    }
186
187    #[test]
188    fn optimize_folds_cast_of_literal_in_comparison() -> VortexResult<()> {
189        let expr = lt_eq(
190            get_item("x", root()),
191            cast(
192                lit(3i32),
193                DType::Primitive(PType::F64, Nullability::NonNullable),
194            ),
195        );
196        let scope = DType::Struct(
197            StructFields::new(
198                ["x"].into(),
199                vec![DType::Primitive(PType::F64, Nullability::NonNullable)],
200            ),
201            Nullability::NonNullable,
202        );
203        let optimized = expr.bind(&scope)?.optimize_recursive()?;
204
205        // Prune rules pattern-match a bare Literal on the comparison RHS; a cast wrapper
206        // silently disables pruning.
207        let rhs = optimized
208            .child(1)
209            .as_opt::<Literal>()
210            .ok_or_else(|| vortex_err!("expected a bare literal RHS, got {optimized}"))?;
211        assert_eq!(rhs, &Scalar::primitive(3.0f64, Nullability::NonNullable));
212        Ok(())
213    }
214
215    #[rstest]
216    #[case::and_annihilator(and(root(), lit(false)), DType::Bool(Nullability::Nullable))]
217    #[case::or_annihilator(or(root(), lit(true)), DType::Bool(Nullability::Nullable))]
218    #[case::and_nullable_identity(
219        and(root(), lit(Scalar::from(Some(true)))),
220        DType::Bool(Nullability::NonNullable)
221    )]
222    #[case::or_nullable_identity(
223        or(root(), lit(Scalar::from(Some(false)))),
224        DType::Bool(Nullability::NonNullable)
225    )]
226    #[case::zip_true(
227        zip_expr(lit(true), lit(1i32), root()),
228        DType::Primitive(PType::I32, Nullability::Nullable)
229    )]
230    #[case::zip_false(
231        zip_expr(lit(false), root(), lit(1i32)),
232        DType::Primitive(PType::I32, Nullability::Nullable)
233    )]
234    fn literal_simplification_preserves_result_dtype(
235        #[case] expr: Expression,
236        #[case] scope: DType,
237    ) -> VortexResult<()> {
238        let original = expr.bind(&scope)?;
239        let optimized = expr.bind(&scope)?.optimize_recursive()?;
240        assert_eq!(optimized.dtype(), original.dtype());
241
242        Ok(())
243    }
244
245    /// `Select` over a `pack` rewrites to a `pack` of the selected child fields. It must read
246    /// those fields out of the child `pack` itself, because the optimizer visits children before
247    /// their parent and so never revisits the children a rule introduces.
248    #[test]
249    fn optimize_select_of_pack_reads_pack_fields() -> VortexResult<()> {
250        let field_names = (0..4)
251            .map(|idx| FieldName::from(format!("field_{idx}")))
252            .collect::<Vec<_>>();
253        let fields = StructFields::new(
254            field_names.clone().into(),
255            vec![DType::Primitive(PType::U64, Nullability::NonNullable); field_names.len()],
256        );
257        let scope = DType::Struct(fields, Nullability::NonNullable);
258
259        let root_pack = pack(
260            field_names
261                .iter()
262                .map(|name| (name.clone(), get_item(name.clone(), root())))
263                .collect::<Vec<_>>(),
264            Nullability::NonNullable,
265        );
266        let expr = select(
267            field_names
268                .iter()
269                .cloned()
270                .chain(["input_row_idx".into(), "input_file_idx".into()])
271                .collect::<Vec<_>>(),
272            merge([
273                root_pack,
274                pack(
275                    [
276                        ("input_row_idx", lit(0_u64)),
277                        ("input_file_idx", lit(1_u64)),
278                    ],
279                    Nullability::NonNullable,
280                ),
281            ]),
282        );
283
284        let expected = pack(
285            field_names
286                .into_iter()
287                .map(|name| (name.clone(), get_item(name, root())))
288                .chain([
289                    ("input_row_idx".into(), lit(0_u64)),
290                    ("input_file_idx".into(), lit(1_u64)),
291                ])
292                .collect::<Vec<_>>(),
293            Nullability::NonNullable,
294        );
295
296        let expected = expected.bind(&scope)?;
297
298        let optimized = expr.bind(&scope)?.optimize_recursive()?;
299        assert_eq!(optimized, expected, "got {optimized}");
300        assert_eq!(optimized.optimize_recursive()?, expected);
301
302        Ok(())
303    }
304
305    /// `Merge` reduces to a `pack` that reads each field out of its children, so it must also
306    /// read straight out of a `pack` child.
307    #[test]
308    fn optimize_merge_of_packs_reads_pack_fields() -> VortexResult<()> {
309        let scope = DType::Struct(StructFields::empty(), Nullability::NonNullable);
310        let expr = merge([
311            pack([("a", lit(0_u64))], Nullability::NonNullable),
312            pack([("b", lit(1_u64))], Nullability::NonNullable),
313        ]);
314
315        let expected = pack(
316            [("a", lit(0_u64)), ("b", lit(1_u64))],
317            Nullability::NonNullable,
318        );
319
320        let expected = expected.bind(&scope)?;
321
322        let optimized = expr.bind(&scope)?.optimize_recursive()?;
323        assert_eq!(optimized, expected, "got {optimized}");
324        assert_eq!(optimized.optimize_recursive()?, expected);
325
326        Ok(())
327    }
328}