vortex_array/aggregate_fn/
accumulator_grouped.rs1use 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
39pub type GroupedAccumulatorRef = Box<dyn DynGroupedAccumulator>;
41
42pub enum GroupedArray {
48 ListView(ListViewArray),
50 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 pub fn elements(&self) -> &ArrayRef {
69 match self {
70 Self::ListView(groups) => groups.elements(),
71 Self::FixedSizeList(groups) => groups.elements(),
72 }
73 }
74
75 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 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 pub fn len(&self) -> usize {
93 match self {
94 Self::ListView(groups) => groups.len(),
95 Self::FixedSizeList(groups) => groups.len(),
96 }
97 }
98
99 pub fn is_empty(&self) -> bool {
101 self.len() == 0
102 }
103
104 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
133pub enum GroupRanges {
135 ListView {
137 ranges: Vec<(usize, usize)>,
139 },
140 FixedSizeList {
142 len: usize,
144 size: usize,
146 },
147}
148
149impl GroupRanges {
150 pub fn len(&self) -> usize {
152 match self {
153 Self::ListView { ranges } => ranges.len(),
154 Self::FixedSizeList { len, .. } => *len,
155 }
156 }
157
158 pub fn is_empty(&self) -> bool {
160 self.len() == 0
161 }
162
163 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 pub fn iter(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
176 (0..self.len()).map(|index| self.range(index))
177 }
178}
179
180pub struct GroupedAccumulator<V: AggregateFnVTable> {
185 vtable: V,
187 options: V::Options,
189 aggregate_fn: AggregateFnRef,
191 dtypes: AggregateDTypes,
193 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 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
218pub trait DynGroupedAccumulator: 'static + Send {
221 fn accumulate_list(&mut self, groups: &ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<()>;
223
224 fn flush(&mut self) -> VortexResult<ArrayRef>;
227
228 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 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 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 if let Some(kernel) = ctx
302 .aggregate_kernels()
303 .find_grouped_encoding_kernel(elements.encoding_id(), self.aggregate_fn.id())
304 {
305 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 if let Some(kernel) = ctx
316 .aggregate_kernels()
317 .find_grouped_kernel(self.aggregate_fn.id())
318 {
319 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 elements = elements.execute(ctx)?;
335 }
336
337 let elements = elements.execute::<Columnar>(ctx)?.into_array();
338 let grouped = unsafe { groups.with_elements_unchecked(elements)? };
341
342 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}