use std::hash::Hash;
use std::hash::Hasher;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering;
use smallvec::SmallVec;
use vortex_error::VortexResult;
use vortex_error::vortex_bail;
use vortex_session::VortexSession;
use vortex_utils::aliases::hash_map::HashMap;
use crate::ArrayRef;
use crate::optimizer::kernels::ArrayKernels;
use crate::optimizer::kernels::ArrayKernelsExt;
use crate::trace_op;
pub mod kernels;
pub mod rules;
const MAX_OPTIMIZER_REWRITE_PASS: usize = 100;
#[derive(Debug, Default)]
pub(crate) struct OptimizedState(pub(crate) AtomicBool);
impl OptimizedState {
fn is_optimized(&self) -> bool {
self.0.load(Ordering::Relaxed)
}
fn mark_optimized(&self) {
self.0.store(true, Ordering::Relaxed);
}
}
pub(crate) fn mark_decoded_optimized(array: &ArrayRef) {
array.optimized_state().mark_optimized();
}
pub trait ArrayOptimizer {
fn optimize(&self) -> VortexResult<ArrayRef>;
fn optimize_ctx(&self, session: &VortexSession) -> VortexResult<ArrayRef>;
fn optimize_recursive(&self, session: &VortexSession) -> VortexResult<ArrayRef>;
}
impl ArrayOptimizer for ArrayRef {
fn optimize(&self) -> VortexResult<ArrayRef> {
if self.optimized_state().is_optimized() {
return Ok(self.clone());
}
Optimizer::new(None).optimize_root(self.clone())
}
fn optimize_ctx(&self, session: &VortexSession) -> VortexResult<ArrayRef> {
if self.optimized_state().is_optimized() {
return Ok(self.clone());
}
let session_kernels = session.kernels();
let session_kernels: &ArrayKernels = &session_kernels;
Optimizer::new(Some(session_kernels)).optimize_array(self)
}
fn optimize_recursive(&self, session: &VortexSession) -> VortexResult<ArrayRef> {
self.optimize_ctx(session)
}
}
struct ArrayByPtr(ArrayRef);
impl PartialEq for ArrayByPtr {
fn eq(&self, other: &Self) -> bool {
ArrayRef::ptr_eq(&self.0, &other.0)
}
}
impl Eq for ArrayByPtr {}
impl Hash for ArrayByPtr {
fn hash<H: Hasher>(&self, state: &mut H) {
self.0.addr().hash(state);
}
}
pub(crate) struct Optimizer<'a> {
session_kernels: Option<&'a ArrayKernels>,
rewritten_shared: HashMap<ArrayByPtr, ArrayRef>,
}
impl<'a> Optimizer<'a> {
pub(crate) fn new(session_kernels: Option<&'a ArrayKernels>) -> Self {
Self {
session_kernels,
rewritten_shared: HashMap::new(),
}
}
pub(crate) fn optimize_array(&mut self, array: &ArrayRef) -> VortexResult<ArrayRef> {
if !array.is_shared() {
return self.optimize(array.clone());
}
let key = ArrayByPtr(array.clone());
if let Some(rewritten) = self.rewritten_shared.get(&key) {
return Ok(rewritten.clone());
}
let optimized = self.optimize(array.clone())?;
if !ArrayRef::ptr_eq(&optimized, array) {
self.rewritten_shared.insert(key, optimized.clone());
}
Ok(optimized)
}
fn optimize(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {
if array.optimized_state().is_optimized() {
return Ok(array);
}
let mut optimized = self.optimize_root(array.clone())?;
for _ in 0..=MAX_OPTIMIZER_REWRITE_PASS {
let with_children = self.optimize_new_nodes(optimized.clone())?;
if ArrayRef::ptr_eq(&with_children, &optimized) {
break;
}
optimized = self.optimize_root(with_children)?;
}
if !ArrayRef::ptr_eq(&optimized, &array) {
optimized.statistics().inherit_from(array.statistics());
}
optimized.optimized_state().mark_optimized();
Ok(optimized)
}
fn optimize_root(&mut self, mut current_array: ArrayRef) -> VortexResult<ArrayRef> {
let mut any_optimizations = false;
trace_op!(record_optimize_start(
¤t_array,
self.session_kernels.is_some()
));
for _ in 0..=MAX_OPTIMIZER_REWRITE_PASS {
trace_op!(record_optimize_loop_start(¤t_array));
if let Some(new_array) = current_array.reduce()? {
current_array = self.optimize_rewritten(new_array)?;
any_optimizations = true;
trace_op!(record_optimize_loop_end());
continue;
}
trace_op!(record_optimize_reduce_none(¤t_array));
let mut reduced_parent = None;
for (slot_idx, slot) in current_array.slots().iter().enumerate() {
let Some(child) = slot else {
continue;
};
if let Some(session_kernels) = self.session_kernels
&& let Some(new_array) =
try_session_parent_reduce(session_kernels, ¤t_array, child, slot_idx)?
{
reduced_parent = Some(new_array);
break;
}
if let Some(new_array) = child.reduce_parent(¤t_array, slot_idx)? {
reduced_parent = Some(new_array);
break;
}
}
if let Some(new_array) = reduced_parent {
current_array = self.optimize_rewritten(new_array)?;
any_optimizations = true;
trace_op!(record_optimize_loop_end());
continue;
}
trace_op!(record_optimize_parent_reduce_none(¤t_array));
trace_op!(record_optimize_loop_end());
trace_op!(record_optimize_done(¤t_array, any_optimizations));
return Ok(current_array);
}
vortex_bail!("Exceeded maximum optimization iterations (possible infinite loop)");
}
fn optimize_rewritten(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {
if self.session_kernels.is_none() {
return Ok(array);
}
self.optimize_new_nodes(array)
}
fn optimize_new_nodes(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {
let mut new_slots: Option<SmallVec<_>> = None;
for (slot_idx, slot) in array.slots().iter().enumerate() {
let optimized = match slot {
Some(child) if !child.optimized_state().is_optimized() => {
let optimized = self.optimize_array(child)?;
(!ArrayRef::ptr_eq(&optimized, child)).then_some(optimized)
}
_ => None,
};
match optimized {
Some(optimized) => new_slots
.get_or_insert_with(|| {
let mut slots = SmallVec::with_capacity(array.slots().len());
slots.extend(array.slots()[..slot_idx].iter().cloned());
slots
})
.push(Some(optimized)),
None => {
if let Some(new_slots) = &mut new_slots {
new_slots.push(slot.clone());
}
}
}
}
let Some(new_slots) = new_slots else {
return Ok(array);
};
unsafe { array.with_slots(new_slots) }
}
}
fn try_session_parent_reduce(
kernels: &ArrayKernels,
parent: &ArrayRef,
child: &ArrayRef,
slot_idx: usize,
) -> VortexResult<Option<ArrayRef>> {
let Some(reduce_parent_fns) =
kernels.find_reduce_parent(parent.encoding_id(), child.encoding_id())
else {
return Ok(None);
};
#[allow(clippy::unused_enumerate_index)]
for (_kernel_idx, reduce_parent) in reduce_parent_fns.iter().enumerate() {
if let Some(new_array) = reduce_parent(child, parent, slot_idx)? {
trace_op!(record_session_parent_reduce_applied(
parent,
child,
slot_idx,
_kernel_idx,
&new_array,
));
return Ok(Some(new_array));
}
trace_op!(record_session_parent_reduce_declined(
parent,
child,
slot_idx,
_kernel_idx,
));
}
Ok(None)
}
#[cfg(test)]
mod tests {
use std::sync::LazyLock;
use vortex_buffer::buffer;
use vortex_error::VortexResult;
use vortex_mask::Mask;
use vortex_session::VortexSession;
use crate::ArrayRef;
use crate::IntoArray;
use crate::arrays::FilterArray;
use crate::arrays::Primitive;
use crate::arrays::SliceArray;
use crate::arrays::StructArray;
use crate::expr::stats::Precision;
use crate::expr::stats::Stat;
use crate::expr::stats::StatsProviderExt;
use crate::optimizer::ArrayOptimizer;
use crate::scalar::ScalarValue;
static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
fn lazy_slice(array: ArrayRef, range: std::ops::Range<usize>) -> VortexResult<ArrayRef> {
Ok(SliceArray::try_new(array, range)?.into_array())
}
#[test]
fn optimize_marks_result_and_skips_it_after() -> VortexResult<()> {
let sliced = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..3)?;
assert!(!sliced.optimized_state().is_optimized());
let optimized = sliced.optimize_ctx(&SESSION)?;
assert!(optimized.is::<Primitive>());
assert!(optimized.optimized_state().is_optimized());
assert!(ArrayRef::ptr_eq(
&optimized.optimize_ctx(&SESSION)?,
&optimized
));
assert!(
!lazy_slice(optimized, 0..1)?
.optimized_state()
.is_optimized()
);
Ok(())
}
#[test]
fn optimize_without_session_does_not_mark() -> VortexResult<()> {
let sliced = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..3)?;
let optimized = sliced.optimize()?;
assert!(optimized.is::<Primitive>());
assert!(!optimized.optimized_state().is_optimized());
Ok(())
}
#[test]
fn optimize_rewrites_a_shared_node_once() -> VortexResult<()> {
let shared = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..3)?;
let parent =
StructArray::from_fields(&[("a", shared.clone()), ("b", shared)])?.into_array();
let optimized = parent.optimize_ctx(&SESSION)?;
let fields = optimized.slots().iter().flatten().collect::<Vec<_>>();
assert_eq!(fields.len(), 2);
assert!(fields[0].is::<Primitive>());
assert!(ArrayRef::ptr_eq(fields[0], fields[1]));
Ok(())
}
#[test]
fn optimize_marks_every_descendant() -> VortexResult<()> {
let sliced = lazy_slice(buffer![1i32, 2, 3, 4].into_array(), 1..4)?;
let filtered =
FilterArray::try_new(sliced, Mask::from_iter([true, false, true]))?.into_array();
let optimized = filtered.optimize_ctx(&SESSION)?;
assert!(
optimized
.depth_first_traversal()
.all(|node| node.optimized_state().is_optimized())
);
assert!(ArrayRef::ptr_eq(
&optimized.optimize_recursive(&SESSION)?,
&optimized
));
Ok(())
}
#[test]
fn optimize_keeps_stats_of_rewritten_array() -> VortexResult<()> {
let array = buffer![1i32, 2, 3, 4].into_array();
array
.statistics()
.set(Stat::IsSorted, Precision::exact(ScalarValue::Bool(true)));
let sliced = lazy_slice(array, 1..3)?;
sliced
.statistics()
.set(Stat::IsSorted, Precision::exact(ScalarValue::Bool(true)));
let optimized = sliced.optimize_ctx(&SESSION)?;
assert!(optimized.is::<Primitive>());
assert_eq!(
optimized.statistics().get_as::<bool>(Stat::IsSorted),
Precision::exact(true)
);
Ok(())
}
}