Skip to main content

vortex_array/arrays/dict/
take.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use smallvec::SmallVec;
5use vortex_error::VortexResult;
6
7use super::Dict;
8use crate::ArrayRef;
9use crate::Canonical;
10use crate::ExecutionCtx;
11use crate::IntoArray;
12use crate::array::ArrayView;
13use crate::array::VTable;
14use crate::arrays::Constant;
15use crate::arrays::ConstantArray;
16use crate::arrays::dict::DictArraySlotsExt;
17use crate::expr::stats::Precision;
18use crate::expr::stats::Stat;
19use crate::expr::stats::StatsProvider;
20use crate::expr::stats::StatsProviderExt;
21use crate::kernel::ExecuteParentKernel;
22use crate::matcher::Matcher;
23use crate::optimizer::rules::ArrayParentReduceRule;
24use crate::scalar::Scalar;
25use crate::stats::StatsSet;
26use crate::validity::Validity;
27
28pub trait TakeReduce: VTable {
29    /// Take elements from an array at the given indices without reading buffers.
30    ///
31    /// This trait is for take implementations that can operate purely on array metadata and
32    /// structure without needing to read or execute on the underlying buffers. Implementations
33    /// should return `None` if taking requires buffer access.
34    ///
35    /// # Preconditions
36    ///
37    /// The indices are guaranteed to be non-empty.
38    fn take(array: ArrayView<'_, Self>, indices: &ArrayRef) -> VortexResult<Option<ArrayRef>>;
39}
40
41pub trait TakeExecute: VTable {
42    /// Take elements from an array at the given indices, potentially reading buffers.
43    ///
44    /// Unlike [`TakeReduce`], this trait is for take implementations that may need to read
45    /// and execute on the underlying buffers to produce the result.
46    ///
47    /// # Preconditions
48    ///
49    /// The indices are guaranteed to be non-empty.
50    fn take(
51        array: ArrayView<'_, Self>,
52        indices: &ArrayRef,
53        ctx: &mut ExecutionCtx,
54    ) -> VortexResult<Option<ArrayRef>>;
55}
56
57/// Short-circuits take for the inputs that need no encoding-specific work.
58///
59/// Returns `Some(result)` when the answer is already known, or `None` when take must proceed
60/// normally.
61fn short_circuit<V: VTable>(array: ArrayView<'_, V>, indices: &ArrayRef) -> Option<ArrayRef> {
62    // Fast-path for empty indices.
63    if indices.is_empty() {
64        let result_dtype = array
65            .dtype()
66            .clone()
67            .union_nullability(indices.dtype().nullability());
68        return Some(Canonical::empty(&result_dtype).into_array());
69    }
70
71    // Fast-path for empty arrays: all indices must be null, return all-invalid result.
72    if array.is_empty() {
73        return Some(
74            ConstantArray::new(Scalar::null(array.dtype().as_nullable()), indices.len())
75                .into_array(),
76        );
77    }
78
79    None
80}
81
82#[derive(Default, Debug)]
83pub struct TakeReduceAdaptor<V>(pub V);
84
85impl<V> ArrayParentReduceRule<V> for TakeReduceAdaptor<V>
86where
87    V: TakeReduce,
88{
89    type Parent = Dict;
90
91    fn reduce_parent(
92        &self,
93        array: ArrayView<'_, V>,
94        parent: ArrayView<'_, Dict>,
95        child_idx: usize,
96    ) -> VortexResult<Option<ArrayRef>> {
97        // Only handle the values child (index 1), not the codes child (index 0).
98        if child_idx != 1 {
99            return Ok(None);
100        }
101        if let Some(result) = short_circuit::<V>(array, parent.codes()) {
102            return Ok(Some(result));
103        }
104        let result = <V as TakeReduce>::take(array, parent.codes())?;
105        if let Some(taken) = &result {
106            propagate_take_stats(array.array(), taken, parent.codes())?;
107        }
108        Ok(result)
109    }
110}
111
112#[derive(Default, Debug)]
113pub struct TakeExecuteAdaptor<V>(pub V);
114
115impl<V> ExecuteParentKernel<V> for TakeExecuteAdaptor<V>
116where
117    V: TakeExecute,
118{
119    type Parent = Dict;
120
121    fn execute_parent(
122        &self,
123        array: ArrayView<'_, V>,
124        parent: <Self::Parent as Matcher>::Match<'_>,
125        child_idx: usize,
126        ctx: &mut ExecutionCtx,
127    ) -> VortexResult<Option<ArrayRef>> {
128        // Only handle the values child (index 1), not the codes child (index 0).
129        if child_idx != 1 {
130            return Ok(None);
131        }
132        if let Some(result) = short_circuit::<V>(array, parent.codes()) {
133            return Ok(Some(result));
134        }
135        let result = <V as TakeExecute>::take(array, parent.codes(), ctx)?;
136        if let Some(taken) = &result {
137            propagate_take_stats(array.array(), taken, parent.codes())?;
138        }
139        Ok(result)
140    }
141}
142
143pub(crate) fn propagate_take_stats(
144    source: &ArrayRef,
145    target: &ArrayRef,
146    indices: &ArrayRef,
147) -> VortexResult<()> {
148    let indices_all_valid = matches!(
149        indices.validity()?,
150        Validity::NonNullable | Validity::AllValid
151    );
152    target.statistics().with_mut_typed_stats_set(|mut st| {
153        if indices_all_valid {
154            let is_constant = source.statistics().get_as::<bool>(Stat::IsConstant);
155            if matches!(is_constant, Precision::Exact(true)) {
156                // Any combination of elements from a constant array is still const
157                st.set(Stat::IsConstant, Precision::exact(true));
158            }
159        }
160        let inexact_min_max = [Stat::Min, Stat::Max]
161            .into_iter()
162            .filter_map(|stat| match source.statistics().get(stat).into_inexact() {
163                Precision::Exact(scalar) | Precision::Inexact(scalar) => {
164                    scalar.into_value().map(|sv| (stat, Precision::Inexact(sv)))
165                }
166                Precision::Absent => None,
167            })
168            .collect::<SmallVec<_>>();
169        st.combine_sets(
170            &(unsafe { StatsSet::new_unchecked(inexact_min_max) }).as_typed_ref(source.dtype()),
171        )
172    })
173}
174
175/// Executes a dictionary whose codes are constant by expanding the one value they select, rather
176/// than materializing the codes and gathering through them.
177///
178/// The executor offers the codes child to its parent's kernels before the values child, so this
179/// runs ahead of the values' take kernel, whatever their encoding.
180#[derive(Debug)]
181pub(crate) struct DictConstantCodesKernel;
182
183impl ExecuteParentKernel<Constant> for DictConstantCodesKernel {
184    type Parent = Dict;
185
186    fn execute_parent(
187        &self,
188        array: ArrayView<'_, Constant>,
189        parent: <Self::Parent as Matcher>::Match<'_>,
190        child_idx: usize,
191        ctx: &mut ExecutionCtx,
192    ) -> VortexResult<Option<ArrayRef>> {
193        if child_idx != 0 || parent.is_empty() {
194            return Ok(None);
195        }
196        let value = match array.scalar().as_primitive().as_::<usize>() {
197            Some(code) => parent
198                .values()
199                .execute_scalar(code, ctx)?
200                .cast(parent.dtype())?,
201            None => Scalar::null(parent.dtype().as_nullable()),
202        };
203        Ok(Some(ConstantArray::new(value, parent.len()).into_array()))
204    }
205}