1use vortex_error::VortexResult;
5
6use crate::expr::BoundExpression;
7use crate::scalar_fn::ExpressionReduceNode;
8
9impl BoundExpression {
10 pub fn optimize(&self) -> VortexResult<BoundExpression> {
16 Ok(self.try_optimize()?.unwrap_or_else(|| self.clone()))
17 }
18
19 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 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 fn try_optimize(&self) -> VortexResult<Option<BoundExpression>> {
42 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 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 pub fn optimize_recursive(&self) -> VortexResult<BoundExpression> {
87 Ok(self
88 .try_optimize_recursive()?
89 .unwrap_or_else(|| self.clone()))
90 }
91
92 pub fn try_optimize_recursive(&self) -> VortexResult<Option<BoundExpression>> {
94 let mut current = self.try_optimize()?;
96
97 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 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 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 #[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 #[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}