Skip to main content

vortex_array/aggregate_fn/
accumulator_grouped.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::mem;
5
6use arrow_buffer::ArrowNativeType;
7use vortex_buffer::Buffer;
8use vortex_error::VortexExpect;
9use vortex_error::VortexResult;
10use vortex_error::vortex_bail;
11use vortex_error::vortex_ensure_eq;
12use vortex_error::vortex_panic;
13use vortex_mask::Mask;
14
15use crate::ArrayRef;
16use crate::Canonical;
17use crate::Columnar;
18use crate::ExecutionCtx;
19use crate::IntoArray;
20use crate::aggregate_fn::Accumulator;
21use crate::aggregate_fn::AggregateDTypes;
22use crate::aggregate_fn::AggregateFn;
23use crate::aggregate_fn::AggregateFnRef;
24use crate::aggregate_fn::AggregateFnVTable;
25use crate::aggregate_fn::DynAccumulator;
26use crate::arrays::ChunkedArray;
27use crate::arrays::FixedSizeListArray;
28use crate::arrays::ListViewArray;
29use crate::arrays::fixed_size_list::FixedSizeListArrayExt;
30use crate::arrays::fixed_size_list::FixedSizeListArraySlotsExt;
31use crate::arrays::listview::ListViewArraySlotsExt;
32use crate::builders::builder_with_capacity_in;
33use crate::builtins::ArrayBuiltins;
34use crate::columnar::AnyColumnar;
35use crate::dtype::DType;
36use crate::executor::max_iterations;
37use crate::match_each_integer_ptype;
38
39/// Reference-counted type-erased grouped accumulator.
40pub type GroupedAccumulatorRef = Box<dyn DynGroupedAccumulator>;
41
42/// A batch of grouped values to aggregate.
43///
44/// Each outer list value is one group, and the inner element array is shared by all groups.
45/// Aggregate implementations can inspect the concrete grouped representation directly, or ask for
46/// derived ranges when their algorithm is expressed in terms of `(offset, size)` pairs.
47pub enum GroupedArray {
48    /// Groups represented as a list-view array with per-group offsets and sizes.
49    ListView(ListViewArray),
50    /// Groups represented as a fixed-size list array.
51    FixedSizeList(FixedSizeListArray),
52}
53
54impl From<ListViewArray> for GroupedArray {
55    fn from(groups: ListViewArray) -> Self {
56        Self::ListView(groups)
57    }
58}
59
60impl From<FixedSizeListArray> for GroupedArray {
61    fn from(groups: FixedSizeListArray) -> Self {
62        Self::FixedSizeList(groups)
63    }
64}
65
66impl GroupedArray {
67    /// The inner element array shared by all groups.
68    pub fn elements(&self) -> &ArrayRef {
69        match self {
70            Self::ListView(groups) => groups.elements(),
71            Self::FixedSizeList(groups) => groups.elements(),
72        }
73    }
74
75    /// Return the `(offset, size)` ranges describing each group in `elements`.
76    pub fn group_ranges(&self, ctx: &mut ExecutionCtx) -> VortexResult<GroupRanges> {
77        match self {
78            Self::ListView(groups) => list_view_group_ranges(groups, ctx),
79            Self::FixedSizeList(groups) => Ok(fixed_size_list_group_ranges(groups)),
80        }
81    }
82
83    /// Return the per-group validity mask.
84    pub fn group_validity(&self, ctx: &mut ExecutionCtx) -> VortexResult<Mask> {
85        match self {
86            Self::ListView(groups) => groups.validity()?.execute_mask(groups.len(), ctx),
87            Self::FixedSizeList(groups) => groups.validity()?.execute_mask(groups.len(), ctx),
88        }
89    }
90
91    /// The number of groups in this batch.
92    pub fn len(&self) -> usize {
93        match self {
94            Self::ListView(groups) => groups.len(),
95            Self::FixedSizeList(groups) => groups.len(),
96        }
97    }
98
99    /// Returns true when this batch contains no groups.
100    pub fn is_empty(&self) -> bool {
101        self.len() == 0
102    }
103
104    /// Returns true when every group is valid.
105    pub fn all_groups_valid(&self, ctx: &mut ExecutionCtx) -> VortexResult<bool> {
106        Ok(self.group_validity(ctx)?.all_true())
107    }
108
109    unsafe fn with_elements_unchecked(&self, elements: ArrayRef) -> VortexResult<Self> {
110        Ok(match self {
111            Self::ListView(groups) => unsafe {
112                ListViewArray::new_unchecked(
113                    elements,
114                    groups.offsets().clone(),
115                    groups.sizes().clone(),
116                    groups.validity()?,
117                )
118            }
119            .into(),
120            Self::FixedSizeList(groups) => unsafe {
121                FixedSizeListArray::new_unchecked(
122                    elements,
123                    groups.list_size(),
124                    groups.validity()?,
125                    groups.len(),
126                )
127            }
128            .into(),
129        })
130    }
131}
132
133/// The physical ranges of a grouped array.
134pub enum GroupRanges {
135    /// Explicit ranges extracted from a list-view array.
136    ListView {
137        /// The `(offset, size)` ranges.
138        ranges: Vec<(usize, usize)>,
139    },
140    /// Uniform ranges derived from a fixed-size list array.
141    FixedSizeList {
142        /// The number of groups.
143        len: usize,
144        /// The number of elements in each group.
145        size: usize,
146    },
147}
148
149impl GroupRanges {
150    /// The number of groups described by these ranges.
151    pub fn len(&self) -> usize {
152        match self {
153            Self::ListView { ranges } => ranges.len(),
154            Self::FixedSizeList { len, .. } => *len,
155        }
156    }
157
158    /// Returns true when there are no groups.
159    pub fn is_empty(&self) -> bool {
160        self.len() == 0
161    }
162
163    /// Return the `(offset, size)` range for the group at `index`.
164    fn range(&self, index: usize) -> (usize, usize) {
165        match self {
166            Self::ListView { ranges } => ranges[index],
167            Self::FixedSizeList { len, size } => {
168                assert!(index < *len, "range index out of bounds");
169                (index * size, *size)
170            }
171        }
172    }
173
174    /// Iterate over all `(offset, size)` group ranges.
175    pub fn iter(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
176        (0..self.len()).map(|index| self.range(index))
177    }
178}
179
180/// An accumulator used for computing grouped aggregates.
181///
182/// Note that the groups must be processed in order, and the accumulator does not support random
183/// access to groups.
184pub struct GroupedAccumulator<V: AggregateFnVTable> {
185    /// The vtable of the aggregate function.
186    vtable: V,
187    /// The options of the aggregate function.
188    options: V::Options,
189    /// Type-erased aggregate function used for kernel dispatch.
190    aggregate_fn: AggregateFnRef,
191    /// The input, partial, and result dtypes lent to every vtable call.
192    dtypes: AggregateDTypes,
193    /// The accumulated state for prior batches of groups.
194    partials: Vec<ArrayRef>,
195}
196
197impl<V: AggregateFnVTable> GroupedAccumulator<V> {
198    pub fn try_new(vtable: V, options: V::Options, dtype: DType) -> VortexResult<Self> {
199        let dtypes = AggregateDTypes::try_new(&vtable, &options, dtype)?;
200
201        Ok(Self::from_dtypes(vtable, options, dtypes))
202    }
203
204    /// Build a grouped accumulator over dtypes that are already resolved.
205    pub(super) fn from_dtypes(vtable: V, options: V::Options, dtypes: AggregateDTypes) -> Self {
206        let aggregate_fn = AggregateFn::new(vtable.clone(), options.clone()).erased();
207
208        Self {
209            vtable,
210            options,
211            aggregate_fn,
212            dtypes,
213            partials: vec![],
214        }
215    }
216}
217
218/// A trait object for type-erased grouped accumulators, used for dynamic dispatch when the aggregate
219/// function is not known at compile time.
220pub trait DynGroupedAccumulator: 'static + Send {
221    /// Accumulate a list of groups into the accumulator.
222    fn accumulate_list(&mut self, groups: &ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<()>;
223
224    /// Finish the accumulation and return the partial aggregate results for all groups.
225    /// Resets the accumulator state for the next round of accumulation.
226    fn flush(&mut self) -> VortexResult<ArrayRef>;
227
228    /// Finish the accumulation and return the final aggregate results for all groups.
229    /// Resets the accumulator state for the next round of accumulation.
230    fn finish(&mut self) -> VortexResult<ArrayRef>;
231}
232
233impl<V: AggregateFnVTable> DynGroupedAccumulator for GroupedAccumulator<V> {
234    fn accumulate_list(&mut self, groups: &ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<()> {
235        let elements_dtype = match groups.dtype() {
236            DType::List(elem, _) => elem,
237            DType::FixedSizeList(elem, ..) => elem,
238            _ => vortex_bail!(
239                "Input DType mismatch: expected List or FixedSizeList, got {}",
240                groups.dtype()
241            ),
242        };
243        vortex_ensure_eq!(
244            elements_dtype.as_ref(),
245            &self.dtypes.dtype,
246            "Input DType mismatch"
247        );
248
249        // We first execute the groups until it is a ListView or FixedSizeList, since we only
250        // dispatch the aggregate kernel over the elements of these arrays.
251        let canonical = match groups.clone().execute::<Columnar>(ctx)? {
252            Columnar::Canonical(c) => c,
253            Columnar::Constant(c) => c.into_array().execute::<Canonical>(ctx)?,
254        };
255        match canonical {
256            Canonical::List(groups) => self.accumulate_grouped_array(groups.into(), ctx),
257            Canonical::FixedSizeList(groups) => self.accumulate_grouped_array(groups.into(), ctx),
258            _ => {
259                vortex_panic!("We checked the DType above, so this should never happen")
260            }
261        }
262    }
263
264    fn flush(&mut self) -> VortexResult<ArrayRef> {
265        if self.partials.len() == 1 {
266            return Ok(self.partials.pop().vortex_expect("checked one partial"));
267        }
268        // Pass the `Vec` itself so that this shares the `try_new` instance of other callers.
269        Ok(ChunkedArray::try_new(
270            mem::take(&mut self.partials),
271            self.dtypes.partial_dtype.clone(),
272        )?
273        .into_array())
274    }
275
276    fn finish(&mut self) -> VortexResult<ArrayRef> {
277        let states = self.flush()?;
278        let results = self
279            .vtable
280            .finalize(self.dtypes.args(&self.options), states)?;
281
282        vortex_ensure_eq!(
283            results.dtype(),
284            &self.dtypes.return_dtype,
285            "Return DType mismatch"
286        );
287
288        Ok(results)
289    }
290}
291
292impl<V: AggregateFnVTable> GroupedAccumulator<V> {
293    fn accumulate_grouped_array(
294        &mut self,
295        groups: GroupedArray,
296        ctx: &mut ExecutionCtx,
297    ) -> VortexResult<()> {
298        let mut elements = groups.elements().clone();
299        for _ in 0..max_iterations() {
300            // Try a registered grouped kernel for the current element encoding.
301            if let Some(kernel) = ctx
302                .aggregate_kernels()
303                .find_grouped_encoding_kernel(elements.encoding_id(), self.aggregate_fn.id())
304            {
305                // SAFETY: we assume that elements execution is safe
306                let kernel_groups = unsafe { groups.with_elements_unchecked(elements.clone())? };
307                if let Some(result) =
308                    kernel.grouped_aggregate(&self.aggregate_fn, &kernel_groups, ctx)?
309                {
310                    return self.push_result(result);
311                }
312            }
313
314            // Try a grouped kernel for the current aggregate regardless of element encoding.
315            if let Some(kernel) = ctx
316                .aggregate_kernels()
317                .find_grouped_kernel(self.aggregate_fn.id())
318            {
319                // SAFETY: we preserve the grouped shape and validity while replacing the
320                // elements with another representation of the same logical array.
321                let kernel_groups = unsafe { groups.with_elements_unchecked(elements.clone())? };
322                if let Some(result) =
323                    kernel.grouped_aggregate(&self.aggregate_fn, &kernel_groups, ctx)?
324                {
325                    return self.push_result(result);
326                }
327            }
328
329            if elements.is::<AnyColumnar>() {
330                break;
331            }
332
333            // Execute one step and try again
334            elements = elements.execute(ctx)?;
335        }
336
337        let elements = elements.execute::<Columnar>(ctx)?.into_array();
338        // SAFETY: we preserve the grouped shape and validity while replacing the elements with an
339        // executed form of the same logical array.
340        let grouped = unsafe { groups.with_elements_unchecked(elements)? };
341
342        // Otherwise, we iterate the offsets and sizes and accumulate each group one by one.
343        self.accumulate_grouped_fallback(&grouped, ctx)
344    }
345
346    fn accumulate_grouped_fallback(
347        &mut self,
348        grouped: &GroupedArray,
349        ctx: &mut ExecutionCtx,
350    ) -> VortexResult<()> {
351        let mut accumulator = Accumulator::try_new(
352            self.vtable.clone(),
353            self.options.clone(),
354            self.dtypes.dtype.clone(),
355        )?;
356        let mut states =
357            builder_with_capacity_in(&self.dtypes.partial_dtype, grouped.len(), ctx.allocator());
358        let group_ranges = grouped.group_ranges(ctx)?;
359        let group_validity = grouped.group_validity(ctx)?;
360
361        for ((offset, size), valid) in group_ranges.iter().zip(group_validity.iter()) {
362            if valid {
363                let group = grouped.elements().slice(offset..offset + size)?;
364                accumulator.accumulate(&group, ctx)?;
365                states.append_scalar(&accumulator.flush()?)?;
366            } else {
367                states.append_null()
368            }
369        }
370
371        self.push_result(states.finish())
372    }
373
374    fn push_result(&mut self, state: ArrayRef) -> VortexResult<()> {
375        vortex_ensure_eq!(
376            state.dtype(),
377            &self.dtypes.partial_dtype,
378            "State DType mismatch"
379        );
380        self.partials.push(state);
381        Ok(())
382    }
383}
384fn list_view_group_ranges(
385    groups: &ListViewArray,
386    ctx: &mut ExecutionCtx,
387) -> VortexResult<GroupRanges> {
388    let offsets = groups.offsets();
389    let sizes = groups.sizes().cast(offsets.dtype().clone())?;
390
391    let ranges = match_each_integer_ptype!(offsets.dtype().as_ptype(), |O| {
392        let offsets = offsets.clone().execute::<Buffer<O>>(ctx)?;
393        let sizes = sizes.execute::<Buffer<O>>(ctx)?;
394        offsets
395            .as_ref()
396            .iter()
397            .zip(sizes.as_ref().iter())
398            .map(|(offset, size)| {
399                (
400                    offset.to_usize().vortex_expect("Offset value is not usize"),
401                    size.to_usize().vortex_expect("Size value is not usize"),
402                )
403            })
404            .collect::<Vec<_>>()
405    });
406
407    Ok(GroupRanges::ListView { ranges })
408}
409
410fn fixed_size_list_group_ranges(groups: &FixedSizeListArray) -> GroupRanges {
411    GroupRanges::FixedSizeList {
412        len: groups.len(),
413        size: groups.list_size() as usize,
414    }
415}
416
417#[cfg(test)]
418mod tests {
419    use std::sync::LazyLock;
420
421    use vortex_error::VortexResult;
422    use vortex_session::VortexSession;
423
424    use crate::ArrayRef;
425    use crate::IntoArray;
426    use crate::VortexSessionExecute;
427    use crate::aggregate_fn::DynGroupedAccumulator;
428    use crate::aggregate_fn::GroupedAccumulator;
429    use crate::aggregate_fn::NumericalAggregateOpts;
430    use crate::aggregate_fn::fns::count::Count;
431    use crate::arrays::Chunked;
432    use crate::arrays::PrimitiveArray;
433    use crate::assert_arrays_eq;
434    use crate::dtype::DType;
435    use crate::dtype::Nullability::NonNullable;
436    use crate::dtype::PType;
437
438    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
439
440    fn accumulator() -> VortexResult<GroupedAccumulator<Count>> {
441        GroupedAccumulator::try_new(
442            Count,
443            NumericalAggregateOpts::default(),
444            DType::Primitive(PType::I32, NonNullable),
445        )
446    }
447
448    fn state(values: impl IntoIterator<Item = u64>) -> ArrayRef {
449        PrimitiveArray::from_iter(values).into_array()
450    }
451
452    #[test]
453    fn test_flush_single_partial_returns_original_array() -> VortexResult<()> {
454        let mut accumulator = accumulator()?;
455        let state = state([1, 2, 3]);
456        accumulator.push_result(state.clone())?;
457
458        let flushed = accumulator.flush()?;
459
460        assert!(ArrayRef::ptr_eq(&flushed, &state));
461        Ok(())
462    }
463
464    #[test]
465    fn test_flush_multiple_partials_returns_chunked_array() -> VortexResult<()> {
466        let mut accumulator = accumulator()?;
467        accumulator.push_result(state([1, 2]))?;
468        accumulator.push_result(state([3, 4]))?;
469
470        let flushed = accumulator.flush()?;
471
472        assert!(flushed.is::<Chunked>());
473        assert_eq!(flushed.len(), 4);
474        assert_arrays_eq!(
475            &flushed,
476            &state([1, 2, 3, 4]),
477            &mut SESSION.create_execution_ctx()
478        );
479        assert!(accumulator.flush()?.is_empty());
480        Ok(())
481    }
482
483    #[test]
484    fn test_flush_without_partials_returns_empty_chunked_array() -> VortexResult<()> {
485        let mut accumulator = accumulator()?;
486
487        let flushed = accumulator.flush()?;
488
489        assert!(flushed.is::<Chunked>());
490        assert!(flushed.is_empty());
491        assert_eq!(flushed.dtype(), &DType::Primitive(PType::U64, NonNullable));
492        Ok(())
493    }
494}