vortex_array/optimizer/mod.rs
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! The optimizer applies metadata-only rewrite rules (`reduce` and `reduce_parent`) in a
5//! fixpoint loop until no more transformations are possible.
6//!
7//! Optimization runs between execution steps, which is what enables cross-step optimizations:
8//! after a child is decoded, new `reduce_parent` rules may match that were previously blocked.
9//!
10//! There are three public entry points on [`ArrayOptimizer`]:
11//!
12//! - [`ArrayOptimizer::optimize`] uses only static rules registered on encoding vtables, and only
13//! rewrites the root node.
14//! - [`ArrayOptimizer::optimize_ctx`] also consults the session's active
15//! [`kernels::ArrayKernels`] registry before static parent-reduce rules, so this is the entry
16//! point used by execution. It optimizes the root, then the descendants below it that were
17//! never optimized, then the root again if a child changed.
18//! - [`ArrayOptimizer::optimize_recursive`] is the same as [`ArrayOptimizer::optimize_ctx`].
19//!
20//! With a session, the optimizer works top down. It first tries the rules of a node on its children
21//! as they are, so a rule that drops or replaces a child does not optimize that child first. Then
22//! it optimizes the children that were never optimized, and if any child changed, it tries the
23//! rules of the node again. Thus a parent rule or kernel keyed on a child's encoding still sees
24//! that encoding rather than a lazy wrapper around it, such as a slice of an FSST array under a
25//! `LIKE`. Children already optimized are left without visiting their subtrees.
26//!
27//! Whenever a rule rewrites a node, the nodes the rule built are optimized bottom up before the
28//! next pass on the node. Otherwise two rules that are inverses of each other, such as
29//! `slice(get_item(s))` and `get_item(slice(s))`, could rewrite the node back and forth.
30//!
31//! Each array records whether the optimizer has taken it to its fixpoint. A new array starts
32//! unoptimized, and optimizing with a session marks the arrays it returns, so optimizing an array
33//! again returns it without trying any rule. The optimizer marks a node only after it optimized
34//! the children of the node, so the descendants of a marked node are marked too. The mark does not
35//! record the session: an array optimized with one session is not optimized again with a session
36//! that registers more kernels.
37
38use std::hash::Hash;
39use std::hash::Hasher;
40use std::sync::atomic::AtomicBool;
41use std::sync::atomic::Ordering;
42
43use smallvec::SmallVec;
44use vortex_error::VortexResult;
45use vortex_error::vortex_bail;
46use vortex_session::VortexSession;
47use vortex_utils::aliases::hash_map::HashMap;
48
49use crate::ArrayRef;
50use crate::optimizer::kernels::ArrayKernels;
51use crate::optimizer::kernels::ArrayKernelsExt;
52use crate::trace_op;
53
54pub mod kernels;
55pub mod rules;
56
57/// Last zero-based fixpoint pass attempted before treating continued rewrites as an infinite loop.
58/// Increasing this value permits longer rewrite chains but delays detection of cyclic rules.
59const MAX_OPTIMIZER_REWRITE_PASS: usize = 100;
60
61/// Records whether the optimizer has already optimized an array node and all of its descendants.
62///
63/// A shared array never changes, so a node that the optimizer took to its fixpoint stays there.
64/// Every new array starts unoptimized, and changing a uniquely owned array in place clears the
65/// state.
66///
67/// # What the mark promises
68///
69/// The mark promises only that no reduce or parent-reduce rule applies to the node or its
70/// descendants, given their encodings, dtypes, slots and data. These do not change while the
71/// array is shared. A thread that sees the mark skips the optimizer for the whole subtree, so a
72/// rule that could apply later is never tried.
73///
74/// # When an array stays unoptimized
75///
76/// An array must stay unmarked, or clear its mark, when the decision of a rule depends on
77/// something that can change after the optimizer pass:
78///
79/// - The array changes in place. [`ArrayRef::inner_mut`] clears the mark, because the caller holds
80/// the only reference and can replace slots or data.
81/// - A rule reads state that can be set on a shared array after the pass, such as statistics.
82/// For example, a rule that reduces an array to a constant when [`Stat::IsConstant`] is known
83/// does not run if the statistic is computed after the array was marked. A shared array cannot
84/// clear its mark, because that needs the only reference. Thus such a rule must not depend on
85/// the mark, or the optimizer must not mark the arrays that it can apply to.
86/// - The session changes. The mark does not record the kernels it was optimized with, so an
87/// array optimized with one session is not optimized again with a session that registers more
88/// kernels.
89///
90/// # Memory ordering
91///
92/// The flag uses [`Ordering::Relaxed`]. This is correct because the mark only promises things that
93/// a thread can already see through its reference to the array. If the mark comes to promise
94/// state that another thread writes, such as statistics that a rule reads, store it with
95/// [`Ordering::Release`] and load it with [`Ordering::Acquire`]. Then a thread that sees the mark
96/// also sees that state.
97///
98/// [`ArrayRef::inner_mut`]: crate::ArrayRef::inner_mut
99/// [`Stat::IsConstant`]: crate::expr::stats::Stat::IsConstant
100#[derive(Debug, Default)]
101pub(crate) struct OptimizedState(pub(crate) AtomicBool);
102
103impl OptimizedState {
104 fn is_optimized(&self) -> bool {
105 self.0.load(Ordering::Relaxed)
106 }
107
108 fn mark_optimized(&self) {
109 self.0.store(true, Ordering::Relaxed);
110 }
111}
112
113/// Marks an array decoded from its serialized form as optimized.
114///
115/// Decoding calls this for each node it decodes, and it decodes the children of a node before the
116/// node. Thus every decoded node is marked, and the optimizer does not try reduce or
117/// parent-reduce rules on any of them. Only the nodes that an encoding's deserializer builds itself
118/// around its decoded children stay unmarked. Arrays are usually written as the compressor built
119/// them, so this skips rules on decoded arrays without the guarantee that none applies.
120pub(crate) fn mark_decoded_optimized(array: &ArrayRef) {
121 array.optimized_state().mark_optimized();
122}
123
124/// Extension trait for optimizing array trees using reduce/reduce_parent rules.
125pub trait ArrayOptimizer {
126 /// Optimize the root array node by running reduce and reduce_parent rules to fixpoint.
127 ///
128 /// This uses only static rules registered on encoding vtables. Use [`Self::optimize_ctx`]
129 /// when a session-scoped [`kernels::ArrayKernels`] registry should participate.
130 fn optimize(&self) -> VortexResult<ArrayRef>;
131
132 /// Optimize the array tree using static rules and the active [`kernels::ArrayKernels`]
133 /// registry on `session`, if any.
134 ///
135 /// The descendants that were never optimized are optimized before the root. Session kernels
136 /// are checked for each `(parent_encoding_id, child_encoding_id)` pair before the child's
137 /// static `PARENT_RULES`. The registry comes from the [`kernels::KernelSession`] on `session`,
138 /// if any. If `session` does not contain a [`kernels::KernelSession`], this behaves like
139 /// [`Self::optimize`] on the root and its never optimized descendants.
140 fn optimize_ctx(&self, session: &VortexSession) -> VortexResult<ArrayRef>;
141
142 /// Optimize the entire array tree recursively (root and all descendants).
143 ///
144 /// This is the same as [`Self::optimize_ctx`]: optimizing a node first optimizes every
145 /// descendant that was never optimized.
146 fn optimize_recursive(&self, session: &VortexSession) -> VortexResult<ArrayRef>;
147}
148
149impl ArrayOptimizer for ArrayRef {
150 fn optimize(&self) -> VortexResult<ArrayRef> {
151 if self.optimized_state().is_optimized() {
152 return Ok(self.clone());
153 }
154
155 Optimizer::new(None).optimize_root(self.clone())
156 }
157
158 fn optimize_ctx(&self, session: &VortexSession) -> VortexResult<ArrayRef> {
159 if self.optimized_state().is_optimized() {
160 return Ok(self.clone());
161 }
162
163 let session_kernels = session.kernels();
164 let session_kernels: &ArrayKernels = &session_kernels;
165 Optimizer::new(Some(session_kernels)).optimize_array(self)
166 }
167
168 fn optimize_recursive(&self, session: &VortexSession) -> VortexResult<ArrayRef> {
169 self.optimize_ctx(session)
170 }
171}
172
173/// An array keyed by identity: two keys are equal only when they hold the same array, as
174/// [`ArrayRef::ptr_eq`] decides.
175///
176/// The key holds the array, so its address cannot be freed and reused by another array while the
177/// key exists.
178struct ArrayByPtr(ArrayRef);
179
180impl PartialEq for ArrayByPtr {
181 fn eq(&self, other: &Self) -> bool {
182 ArrayRef::ptr_eq(&self.0, &other.0)
183 }
184}
185
186impl Eq for ArrayByPtr {}
187
188impl Hash for ArrayByPtr {
189 fn hash<H: Hasher>(&self, state: &mut H) {
190 self.0.addr().hash(state);
191 }
192}
193
194/// The optimizer state, which can be kept for many optimize calls.
195///
196/// Execution keeps one optimizer for all of [`ArrayRef::execute_until`], so a shared node that one
197/// step rewrote is not rewritten again when a later step reaches it through another parent.
198pub(crate) struct Optimizer<'a> {
199 /// The session kernels, tried before the static parent-reduce rules.
200 ///
201 /// Without them, the optimizer rewrites only the root node and does not mark the result, so
202 /// optimizing it later with a session still tries the session kernels.
203 session_kernels: Option<&'a ArrayKernels>,
204 /// The shared nodes this optimizer rewrote, each with the array it was rewritten into.
205 ///
206 /// Many parents can hold the same unoptimized node, such as the struct below every field of a
207 /// projection. A rewrite returns a new array and does not mark the node, so without this each
208 /// parent would rewrite the node and its whole subtree again. The key keeps the node alive
209 /// for the life of the optimizer.
210 rewritten_shared: HashMap<ArrayByPtr, ArrayRef>,
211}
212
213impl<'a> Optimizer<'a> {
214 /// Creates an optimizer that tries `session_kernels` before the static parent-reduce rules.
215 pub(crate) fn new(session_kernels: Option<&'a ArrayKernels>) -> Self {
216 Self {
217 session_kernels,
218 rewritten_shared: HashMap::new(),
219 }
220 }
221
222 /// Optimizes `array` and the descendants below it that were never optimized, and marks the
223 /// result.
224 ///
225 /// If another owner holds `array` too, the rewrite is remembered, and a later call with the
226 /// same array returns it.
227 pub(crate) fn optimize_array(&mut self, array: &ArrayRef) -> VortexResult<ArrayRef> {
228 if !array.is_shared() {
229 return self.optimize(array.clone());
230 }
231
232 let key = ArrayByPtr(array.clone());
233 if let Some(rewritten) = self.rewritten_shared.get(&key) {
234 return Ok(rewritten.clone());
235 }
236
237 let optimized = self.optimize(array.clone())?;
238 if !ArrayRef::ptr_eq(&optimized, array) {
239 self.rewritten_shared.insert(key, optimized.clone());
240 }
241
242 Ok(optimized)
243 }
244
245 /// Optimizes the root of `array` top down: first the root, then the descendants below it that
246 /// were never optimized, then the root again while its children change. Marks the result.
247 fn optimize(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {
248 if array.optimized_state().is_optimized() {
249 return Ok(array);
250 }
251
252 // The rules of the root get the first try, on children that can still be lazy, so a rule
253 // that drops or replaces a child does not pay to optimize that child's subtree first.
254 let mut optimized = self.optimize_root(array.clone())?;
255
256 for _ in 0..=MAX_OPTIMIZER_REWRITE_PASS {
257 let with_children = self.optimize_new_nodes(optimized.clone())?;
258 if ArrayRef::ptr_eq(&with_children, &optimized) {
259 break;
260 }
261
262 // A child changed its encoding, so a parent rule keyed on that encoding can apply now.
263 optimized = self.optimize_root(with_children)?;
264 }
265
266 // A rewrite keeps the logical values, so every statistic of the input stays valid. Lazy
267 // constructors such as `slice` put the statistics they carry over on the lazy node.
268 if !ArrayRef::ptr_eq(&optimized, &array) {
269 optimized.statistics().inherit_from(array.statistics());
270 }
271
272 optimized.optimized_state().mark_optimized();
273 Ok(optimized)
274 }
275
276 /// Runs the reduce and parent-reduce rules on the root of `current_array` to fixpoint.
277 ///
278 /// With session kernels, the nodes each rewrite built are optimized before the next pass.
279 fn optimize_root(&mut self, mut current_array: ArrayRef) -> VortexResult<ArrayRef> {
280 let mut any_optimizations = false;
281
282 trace_op!(record_optimize_start(
283 ¤t_array,
284 self.session_kernels.is_some()
285 ));
286
287 for _ in 0..=MAX_OPTIMIZER_REWRITE_PASS {
288 trace_op!(record_optimize_loop_start(¤t_array));
289
290 if let Some(new_array) = current_array.reduce()? {
291 current_array = self.optimize_rewritten(new_array)?;
292 any_optimizations = true;
293 trace_op!(record_optimize_loop_end());
294 continue;
295 }
296
297 trace_op!(record_optimize_reduce_none(¤t_array));
298
299 // Try children in order; the first parent rewrite restarts the fixpoint loop.
300 let mut reduced_parent = None;
301 for (slot_idx, slot) in current_array.slots().iter().enumerate() {
302 let Some(child) = slot else {
303 continue;
304 };
305
306 // Session kernels take precedence over the child's static parent-reduce rules.
307 if let Some(session_kernels) = self.session_kernels
308 && let Some(new_array) =
309 try_session_parent_reduce(session_kernels, ¤t_array, child, slot_idx)?
310 {
311 reduced_parent = Some(new_array);
312 break;
313 }
314
315 if let Some(new_array) = child.reduce_parent(¤t_array, slot_idx)? {
316 reduced_parent = Some(new_array);
317 break;
318 }
319 }
320
321 if let Some(new_array) = reduced_parent {
322 current_array = self.optimize_rewritten(new_array)?;
323 any_optimizations = true;
324 trace_op!(record_optimize_loop_end());
325 continue;
326 }
327
328 trace_op!(record_optimize_parent_reduce_none(¤t_array));
329 trace_op!(record_optimize_loop_end());
330
331 trace_op!(record_optimize_done(¤t_array, any_optimizations));
332
333 return Ok(current_array);
334 }
335
336 vortex_bail!("Exceeded maximum optimization iterations (possible infinite loop)");
337 }
338
339 /// Optimizes the nodes that a rule built below the array it returned, if the optimizer has
340 /// session kernels.
341 fn optimize_rewritten(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {
342 if self.session_kernels.is_none() {
343 return Ok(array);
344 }
345
346 self.optimize_new_nodes(array)
347 }
348
349 /// Optimizes the nodes below `array` that were never optimized, such as those a rule built
350 /// below its result.
351 ///
352 /// Rules and constructors build lazy arrays, so these nodes are not yet optimized, at any
353 /// depth. Optimizing them as each rewrite happens keeps the optimizer from undoing one rule
354 /// with its inverse: `slice(get_item(s))` and `get_item(slice(s))` rewrite into each other
355 /// until the inner `slice(s)` collapses into `s`'s own encoding.
356 ///
357 /// A child that is already optimized is left as it is without visiting its subtree, which
358 /// skips the subtrees a rule carries over from the array it rewrote.
359 fn optimize_new_nodes(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {
360 let mut new_slots: Option<SmallVec<_>> = None;
361 for (slot_idx, slot) in array.slots().iter().enumerate() {
362 let optimized = match slot {
363 Some(child) if !child.optimized_state().is_optimized() => {
364 let optimized = self.optimize_array(child)?;
365 (!ArrayRef::ptr_eq(&optimized, child)).then_some(optimized)
366 }
367 _ => None,
368 };
369
370 match optimized {
371 Some(optimized) => new_slots
372 .get_or_insert_with(|| {
373 let mut slots = SmallVec::with_capacity(array.slots().len());
374 slots.extend(array.slots()[..slot_idx].iter().cloned());
375 slots
376 })
377 .push(Some(optimized)),
378 None => {
379 if let Some(new_slots) = &mut new_slots {
380 new_slots.push(slot.clone());
381 }
382 }
383 }
384 }
385
386 let Some(new_slots) = new_slots else {
387 return Ok(array);
388 };
389
390 // SAFETY: optimizer rules only replace child slots with logically equivalent arrays, so
391 // the parent's logical values and statistics remain valid.
392 unsafe { array.with_slots(new_slots) }
393 }
394}
395
396fn try_session_parent_reduce(
397 kernels: &ArrayKernels,
398 parent: &ArrayRef,
399 child: &ArrayRef,
400 slot_idx: usize,
401) -> VortexResult<Option<ArrayRef>> {
402 let Some(reduce_parent_fns) =
403 kernels.find_reduce_parent(parent.encoding_id(), child.encoding_id())
404 else {
405 return Ok(None);
406 };
407
408 #[allow(clippy::unused_enumerate_index)]
409 for (_kernel_idx, reduce_parent) in reduce_parent_fns.iter().enumerate() {
410 if let Some(new_array) = reduce_parent(child, parent, slot_idx)? {
411 trace_op!(record_session_parent_reduce_applied(
412 parent,
413 child,
414 slot_idx,
415 _kernel_idx,
416 &new_array,
417 ));
418
419 return Ok(Some(new_array));
420 }
421
422 trace_op!(record_session_parent_reduce_declined(
423 parent,
424 child,
425 slot_idx,
426 _kernel_idx,
427 ));
428 }
429
430 Ok(None)
431}
432
433#[cfg(test)]
434mod tests {
435 use std::sync::LazyLock;
436
437 use vortex_buffer::buffer;
438 use vortex_error::VortexResult;
439 use vortex_mask::Mask;
440 use vortex_session::VortexSession;
441
442 use crate::ArrayRef;
443 use crate::IntoArray;
444 use crate::arrays::FilterArray;
445 use crate::arrays::Primitive;
446 use crate::arrays::SliceArray;
447 use crate::arrays::StructArray;
448 use crate::expr::stats::Precision;
449 use crate::expr::stats::Stat;
450 use crate::expr::stats::StatsProviderExt;
451 use crate::optimizer::ArrayOptimizer;
452 use crate::scalar::ScalarValue;
453
454 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
455
456 fn lazy_slice(array: ArrayRef, range: std::ops::Range<usize>) -> VortexResult<ArrayRef> {
457 Ok(SliceArray::try_new(array, range)?.into_array())
458 }
459
460 #[test]
461 fn optimize_marks_result_and_skips_it_after() -> VortexResult<()> {
462 let sliced = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..3)?;
463 assert!(!sliced.optimized_state().is_optimized());
464
465 let optimized = sliced.optimize_ctx(&SESSION)?;
466 assert!(optimized.is::<Primitive>());
467 assert!(optimized.optimized_state().is_optimized());
468 assert!(ArrayRef::ptr_eq(
469 &optimized.optimize_ctx(&SESSION)?,
470 &optimized
471 ));
472
473 // A new array built over an optimized one starts unoptimized.
474 assert!(
475 !lazy_slice(optimized, 0..1)?
476 .optimized_state()
477 .is_optimized()
478 );
479 Ok(())
480 }
481
482 #[test]
483 fn optimize_without_session_does_not_mark() -> VortexResult<()> {
484 let sliced = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..3)?;
485
486 let optimized = sliced.optimize()?;
487 assert!(optimized.is::<Primitive>());
488 assert!(!optimized.optimized_state().is_optimized());
489 Ok(())
490 }
491
492 #[test]
493 fn optimize_rewrites_a_shared_node_once() -> VortexResult<()> {
494 // Both fields hold the same unoptimized slice. The second field reuses the rewrite of the
495 // first, so the optimizer does not rewrite the slice and its subtree again.
496 let shared = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..3)?;
497 let parent =
498 StructArray::from_fields(&[("a", shared.clone()), ("b", shared)])?.into_array();
499
500 let optimized = parent.optimize_ctx(&SESSION)?;
501 let fields = optimized.slots().iter().flatten().collect::<Vec<_>>();
502 assert_eq!(fields.len(), 2);
503 assert!(fields[0].is::<Primitive>());
504 assert!(ArrayRef::ptr_eq(fields[0], fields[1]));
505 Ok(())
506 }
507
508 #[test]
509 fn optimize_marks_every_descendant() -> VortexResult<()> {
510 let sliced = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..4)?;
511 let filtered =
512 FilterArray::try_new(sliced, Mask::from_iter([true, false, true]))?.into_array();
513
514 let optimized = filtered.optimize_ctx(&SESSION)?;
515 assert!(
516 optimized
517 .depth_first_traversal()
518 .all(|node| node.optimized_state().is_optimized())
519 );
520 assert!(ArrayRef::ptr_eq(
521 &optimized.optimize_recursive(&SESSION)?,
522 &optimized
523 ));
524 Ok(())
525 }
526
527 #[test]
528 fn optimize_keeps_stats_of_rewritten_array() -> VortexResult<()> {
529 let array = buffer![1i32, 2, 3, 4].into_array();
530 array
531 .statistics()
532 .set(Stat::IsSorted, Precision::exact(ScalarValue::Bool(true)));
533
534 let sliced = lazy_slice(array, 1..3)?;
535 sliced
536 .statistics()
537 .set(Stat::IsSorted, Precision::exact(ScalarValue::Bool(true)));
538
539 let optimized = sliced.optimize_ctx(&SESSION)?;
540 assert!(optimized.is::<Primitive>());
541 assert_eq!(
542 optimized.statistics().get_as::<bool>(Stat::IsSorted),
543 Precision::exact(true)
544 );
545 Ok(())
546 }
547}