Skip to main content

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            &current_array,
284            self.session_kernels.is_some()
285        ));
286
287        for _ in 0..=MAX_OPTIMIZER_REWRITE_PASS {
288            trace_op!(record_optimize_loop_start(&current_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(&current_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, &current_array, child, slot_idx)?
310                {
311                    reduced_parent = Some(new_array);
312                    break;
313                }
314
315                if let Some(new_array) = child.reduce_parent(&current_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(&current_array));
329            trace_op!(record_optimize_loop_end());
330
331            trace_op!(record_optimize_done(&current_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}