Skip to main content

vortex_array/aggregate_fn/
storage_pushdown.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Opt-in pushdown of an aggregate into the storage of one extension type.
5//!
6//! See [`ExtensionStoragePushdown`] for when such a pushdown is correct.
7
8use std::mem;
9
10use vortex_error::VortexResult;
11use vortex_error::vortex_bail;
12use vortex_error::vortex_err;
13use vortex_session::VortexSession;
14
15use crate::ArrayRef;
16use crate::Canonical;
17use crate::Columnar;
18use crate::ExecutionCtx;
19use crate::aggregate_fn::Accumulator;
20use crate::aggregate_fn::AggregateArgs;
21use crate::aggregate_fn::AggregateDTypes;
22use crate::aggregate_fn::AggregateFnId;
23use crate::aggregate_fn::AggregateFnVTable;
24use crate::aggregate_fn::DynAccumulator;
25use crate::arrays::ConstantArray;
26use crate::arrays::Extension;
27use crate::arrays::extension::ExtensionArrayExt;
28use crate::dtype::DType;
29use crate::dtype::extension::ExtVTable;
30use crate::scalar::Scalar;
31
32/// Runs aggregate `A` on the storage values of extension type `E`.
33///
34/// The input must have extension type `E`, and `A` must support its storage dtype. Binding fails
35/// for any other input. The wrapper has a separate aggregate ID, `<A>[<E>]`, formed from the IDs
36/// of `A` and `E`. Registering it does not replace `A`.
37///
38/// Aggregates that already support extension dtypes directly do not need this wrapper.
39///
40/// # Correctness
41///
42/// A registration **must** satisfy both conditions:
43///
44/// - The aggregation is defined for logical values of `E`.
45/// - For every valid input, aggregating the storage values produces the storage representation
46///   of the logical aggregate result. This requires storage to preserve whichever properties `A`
47///   relies on, such as ordering, equality, arithmetic, or NaN classification.
48///
49/// For example, minimum is defined for timestamps, and their integer storage preserves their
50/// ordering, so both conditions hold. Summing timestamps fails the first condition even though
51/// their storage supports addition.
52///
53/// These conditions are not checked. An invalid registration can silently return incorrect results.
54///
55/// # Results and partials
56///
57/// Results and partial states are those of `A` over the storage dtype. Results are not converted
58/// back to `E`. For example, the minimum and maximum of a timestamp column are raw `i64` values
59/// in the column's time unit.
60///
61/// Partial states can only be combined when the aggregate, options, and full input dtype match.
62/// This includes extension metadata, so timestamp partials with different time units must not be
63/// combined even if their storage dtypes match.
64///
65/// # Example
66///
67/// Timestamps compare like their `i64` storage, so `is_sorted` can be pushed down. Register the
68/// pair once on the session, then bind it like any other aggregate:
69///
70/// ```
71/// # use vortex_array::IntoArray;
72/// # use vortex_session::VortexSession;
73/// # use vortex_array::VortexSessionExecute;
74/// # use vortex_array::aggregate_fn::Accumulator;
75/// # use vortex_array::aggregate_fn::DynAccumulator;
76/// # use vortex_array::aggregate_fn::ExtensionStoragePushdown;
77/// # use vortex_array::aggregate_fn::fns::is_sorted::IsSorted;
78/// # use vortex_array::aggregate_fn::fns::is_sorted::IsSortedOptions;
79/// # use vortex_array::aggregate_fn::session::AggregateFnSessionExt;
80/// # use vortex_array::arrays::ExtensionArray;
81/// # use vortex_array::arrays::PrimitiveArray;
82/// # use vortex_array::dtype::DType;
83/// # use vortex_array::dtype::Nullability;
84/// # use vortex_array::extension::datetime::TimeUnit;
85/// # use vortex_array::extension::datetime::Timestamp;
86/// # fn main() -> vortex_error::VortexResult<()> {
87/// let session = VortexSession::empty();
88///
89/// // Register `vortex.is_sorted[vortex.timestamp]`.
90/// let is_sorted = ExtensionStoragePushdown::new(IsSorted, Timestamp);
91/// session.aggregate_fns().register(is_sorted.clone());
92///
93/// // Aggregate a timestamp column through its storage.
94/// let ext_dtype = Timestamp::new(TimeUnit::Milliseconds, Nullability::NonNullable).erased();
95/// let column = ExtensionArray::new(
96///     ext_dtype.clone(),
97///     PrimitiveArray::from_iter([1_000i64, 2_000, 3_000]).into_array(),
98/// )
99/// .into_array();
100///
101/// let mut acc = Accumulator::try_new(
102///     is_sorted,
103///     IsSortedOptions { strict: true },
104///     DType::Extension(ext_dtype),
105/// )?;
106/// acc.accumulate(&column, &mut session.create_execution_ctx())?;
107/// assert!(bool::try_from(&acc.finish()?)?);
108/// # Ok(())
109/// # }
110/// ```
111#[derive(Clone, Debug)]
112pub struct ExtensionStoragePushdown<A: AggregateFnVTable, E: ExtVTable> {
113    aggregate: A,
114    ext: E,
115    id: AggregateFnId,
116}
117
118impl<A: AggregateFnVTable, E: ExtVTable> ExtensionStoragePushdown<A, E> {
119    /// Push `aggregate` down into the storage of extension type `ext`.
120    ///
121    /// Only do this when `aggregate` over the storage is correct for `ext`; see
122    /// [`ExtensionStoragePushdown`] for how to check.
123    pub fn new(aggregate: A, ext: E) -> Self {
124        #[expect(clippy::disallowed_methods, reason = "interning a dynamic id")]
125        let id = AggregateFnId::new(&format!("{}[{}]", aggregate.id(), ext.id()));
126        Self { aggregate, ext, id }
127    }
128
129    /// The storage dtype of `dtype`, if it is an extension dtype of type `E`.
130    fn storage_dtype<'a>(&self, dtype: &'a DType) -> Option<&'a DType> {
131        dtype
132            .as_extension_opt()
133            .filter(|ext_dtype| ext_dtype.is::<E>())
134            .map(|ext_dtype| ext_dtype.storage_dtype())
135    }
136
137    /// The arguments of the storage aggregate `A`.
138    ///
139    /// `A` shares this aggregate's options, return and partial dtypes, and its input dtype is
140    /// borrowed from the extension dtype, so this allocates nothing.
141    fn storage_args<'a>(
142        &self,
143        args: AggregateArgs<'a, A::Options>,
144    ) -> VortexResult<AggregateArgs<'a, A::Options>> {
145        let dtype = self.storage_dtype(args.dtype).ok_or_else(|| {
146            vortex_err!(
147                "Aggregate function {} expects extension type {}, got {}",
148                self.id,
149                self.ext.id(),
150                args.dtype
151            )
152        })?;
153        Ok(AggregateArgs { dtype, ..args })
154    }
155
156    /// Accumulate a storage batch into `state` through an [`Accumulator`] of `A`, so that the
157    /// kernels and cached statistics of `A` on the storage encoding still apply.
158    fn accumulate_storage(
159        &self,
160        args: AggregateArgs<'_, A::Options>,
161        state: &mut A::Partial,
162        storage: &ArrayRef,
163        ctx: &mut ExecutionCtx,
164    ) -> VortexResult<()> {
165        let mut accumulator = Accumulator::from_dtypes(
166            self.aggregate.clone(),
167            args.options.clone(),
168            AggregateDTypes::new(
169                args.dtype.clone(),
170                args.return_dtype.clone(),
171                args.partial_dtype.clone(),
172            ),
173        );
174        accumulator.accumulate(storage, ctx)?;
175        let Some(batch) = accumulator.take_partial() else {
176            return Ok(());
177        };
178        let running = mem::replace(state, self.aggregate.empty_partial(args)?);
179        *state = self.aggregate.merge_partials(args, running, batch)?;
180        Ok(())
181    }
182}
183
184impl<A: AggregateFnVTable, E: ExtVTable> AggregateFnVTable for ExtensionStoragePushdown<A, E> {
185    type Options = A::Options;
186    type Partial = A::Partial;
187
188    fn id(&self) -> AggregateFnId {
189        self.id
190    }
191
192    fn serialize(&self, options: &Self::Options) -> VortexResult<Option<Vec<u8>>> {
193        self.aggregate.serialize(options)
194    }
195
196    fn deserialize(&self, metadata: &[u8], session: &VortexSession) -> VortexResult<Self::Options> {
197        self.aggregate.deserialize(metadata, session)
198    }
199
200    fn return_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
201        self.aggregate
202            .return_dtype(options, self.storage_dtype(input_dtype)?)
203    }
204
205    fn partial_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
206        self.aggregate
207            .partial_dtype(options, self.storage_dtype(input_dtype)?)
208    }
209
210    fn empty_partial(&self, args: AggregateArgs<'_, Self::Options>) -> VortexResult<Self::Partial> {
211        self.aggregate.empty_partial(self.storage_args(args)?)
212    }
213
214    fn partial_from_scalar(
215        &self,
216        args: AggregateArgs<'_, Self::Options>,
217        scalar: &Scalar,
218    ) -> VortexResult<Self::Partial> {
219        self.aggregate
220            .partial_from_scalar(self.storage_args(args)?, scalar)
221    }
222
223    fn merge_partials(
224        &self,
225        args: AggregateArgs<'_, Self::Options>,
226        first: Self::Partial,
227        second: Self::Partial,
228    ) -> VortexResult<Self::Partial> {
229        self.aggregate
230            .merge_partials(self.storage_args(args)?, first, second)
231    }
232
233    fn to_scalar(
234        &self,
235        args: AggregateArgs<'_, Self::Options>,
236        partial: &Self::Partial,
237    ) -> VortexResult<Scalar> {
238        self.aggregate.to_scalar(self.storage_args(args)?, partial)
239    }
240
241    fn is_saturated(
242        &self,
243        args: AggregateArgs<'_, Self::Options>,
244        partial: &Self::Partial,
245    ) -> bool {
246        self.storage_args(args)
247            .is_ok_and(|args| self.aggregate.is_saturated(args, partial))
248    }
249
250    /// Unwrap extension arrays to their storage before decoding, so the storage accumulator sees
251    /// the storage encoding.
252    fn try_accumulate(
253        &self,
254        args: AggregateArgs<'_, Self::Options>,
255        state: &mut Self::Partial,
256        batch: &ArrayRef,
257        ctx: &mut ExecutionCtx,
258    ) -> VortexResult<bool> {
259        let Some(array) = batch.as_opt::<Extension>() else {
260            return Ok(false);
261        };
262        self.accumulate_storage(self.storage_args(args)?, state, array.storage_array(), ctx)?;
263        Ok(true)
264    }
265
266    fn accumulate(
267        &self,
268        args: AggregateArgs<'_, Self::Options>,
269        state: &mut Self::Partial,
270        batch: &Columnar,
271        ctx: &mut ExecutionCtx,
272    ) -> VortexResult<()> {
273        let args = self.storage_args(args)?;
274        match batch {
275            Columnar::Canonical(Canonical::Extension(array)) => {
276                self.accumulate_storage(args, state, array.storage_array(), ctx)
277            }
278            // A constant storage array has no encoding to dispatch on and no statistics worth
279            // caching, so it goes straight to `A` rather than through a nested accumulator.
280            Columnar::Constant(constant) => {
281                let storage = constant.scalar().as_extension().to_storage_scalar();
282                self.aggregate.accumulate(
283                    args,
284                    state,
285                    &Columnar::Constant(ConstantArray::new(storage, constant.len())),
286                    ctx,
287                )
288            }
289            Columnar::Canonical(_) => {
290                vortex_bail!(
291                    "Aggregate function {} expects an extension array, got {}",
292                    self.id,
293                    batch.dtype()
294                )
295            }
296        }
297    }
298
299    fn finalize(
300        &self,
301        args: AggregateArgs<'_, Self::Options>,
302        states: ArrayRef,
303    ) -> VortexResult<ArrayRef> {
304        self.aggregate.finalize(self.storage_args(args)?, states)
305    }
306
307    fn finalize_scalar(
308        &self,
309        args: AggregateArgs<'_, Self::Options>,
310        partial: &Self::Partial,
311    ) -> VortexResult<Scalar> {
312        self.aggregate
313            .finalize_scalar(self.storage_args(args)?, partial)
314    }
315}
316
317#[cfg(test)]
318mod tests {
319    use std::sync::LazyLock;
320
321    use rstest::rstest;
322    use vortex_error::VortexResult;
323    use vortex_session::VortexSession;
324
325    use super::ExtensionStoragePushdown;
326    use crate::IntoArray;
327    use crate::VortexSessionExecute;
328    use crate::aggregate_fn::Accumulator;
329    use crate::aggregate_fn::AggregateFnVTable;
330    use crate::aggregate_fn::DynAccumulator;
331    use crate::aggregate_fn::NumericalAggregateOpts;
332    use crate::aggregate_fn::fns::is_sorted::IsSorted;
333    use crate::aggregate_fn::fns::is_sorted::IsSortedOptions;
334    use crate::aggregate_fn::fns::min_max::MinMax;
335    use crate::aggregate_fn::session::AggregateFnSessionExt;
336    use crate::arrays::ConstantArray;
337    use crate::arrays::ExtensionArray;
338    use crate::arrays::PrimitiveArray;
339    use crate::dtype::DType;
340    use crate::dtype::Nullability;
341    use crate::extension::datetime::Date;
342    use crate::extension::datetime::Time;
343    use crate::extension::datetime::TimeUnit;
344    use crate::extension::datetime::Timestamp;
345    use crate::scalar::Scalar;
346
347    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
348
349    #[test]
350    fn pushes_down_into_storage() -> VortexResult<()> {
351        let session = VortexSession::empty();
352        let aggregate = ExtensionStoragePushdown::new(MinMax, Timestamp);
353        session.aggregate_fns().register(aggregate.clone());
354        assert!(
355            session
356                .aggregate_fns()
357                .find_plugin(&aggregate.id())
358                .is_some()
359        );
360
361        let ext_dtype = Timestamp::new(TimeUnit::Milliseconds, Nullability::Nullable).erased();
362        let storage =
363            PrimitiveArray::from_option_iter([Some(3_000i64), None, Some(1_000)]).into_array();
364        let array = ExtensionArray::new(ext_dtype.clone(), storage.clone()).into_array();
365
366        let mut ctx = session.create_execution_ctx();
367        let mut acc = Accumulator::try_new(
368            aggregate,
369            NumericalAggregateOpts::default(),
370            DType::Extension(ext_dtype),
371        )?;
372        acc.accumulate(&array, &mut ctx)?;
373
374        let mut expected = Accumulator::try_new(
375            MinMax,
376            NumericalAggregateOpts::default(),
377            storage.dtype().clone(),
378        )?;
379        expected.accumulate(&storage, &mut ctx)?;
380
381        assert_eq!(acc.finish()?, expected.finish()?);
382        Ok(())
383    }
384
385    #[test]
386    fn combines_flushed_partials() -> VortexResult<()> {
387        let mut ctx = SESSION.create_execution_ctx();
388        let ext_dtype = Timestamp::new(TimeUnit::Milliseconds, Nullability::Nullable).erased();
389        let batch = |values: [Option<i64>; 2]| {
390            ExtensionArray::new(
391                ext_dtype.clone(),
392                PrimitiveArray::from_option_iter(values).into_array(),
393            )
394            .into_array()
395        };
396        let accumulator = || {
397            Accumulator::try_new(
398                ExtensionStoragePushdown::new(MinMax, Timestamp),
399                NumericalAggregateOpts::default(),
400                DType::Extension(ext_dtype.clone()),
401            )
402        };
403
404        let mut first = accumulator()?;
405        first.accumulate(&batch([Some(3_000), None]), &mut ctx)?;
406        let mut second = accumulator()?;
407        second.accumulate(&batch([Some(1_000), Some(500)]), &mut ctx)?;
408        first.combine_partials(&second.flush()?)?;
409
410        let mut expected = accumulator()?;
411        expected.accumulate(&batch([Some(3_000), None]), &mut ctx)?;
412        expected.accumulate(&batch([Some(1_000), Some(500)]), &mut ctx)?;
413
414        assert_eq!(first.finish()?, expected.finish()?);
415        Ok(())
416    }
417
418    #[test]
419    fn accumulates_constant_batches() -> VortexResult<()> {
420        let mut ctx = SESSION.create_execution_ctx();
421        let ext_dtype = Timestamp::new(TimeUnit::Milliseconds, Nullability::Nullable).erased();
422        let constant = |value: i64| {
423            ConstantArray::new(
424                Scalar::extension_ref(
425                    ext_dtype.clone(),
426                    Scalar::primitive(value, Nullability::Nullable),
427                ),
428                3,
429            )
430            .into_array()
431        };
432
433        let mut acc = Accumulator::try_new(
434            ExtensionStoragePushdown::new(MinMax, Timestamp),
435            NumericalAggregateOpts::default(),
436            DType::Extension(ext_dtype.clone()),
437        )?;
438        acc.accumulate(&constant(2_000), &mut ctx)?;
439        acc.accumulate(&constant(1_000), &mut ctx)?;
440
441        let mut expected = Accumulator::try_new(
442            MinMax,
443            NumericalAggregateOpts::default(),
444            ext_dtype.storage_dtype().clone(),
445        )?;
446        expected.accumulate(
447            &PrimitiveArray::from_option_iter([Some(2_000i64), Some(1_000)]).into_array(),
448            &mut ctx,
449        )?;
450
451        assert_eq!(acc.finish()?, expected.finish()?);
452        Ok(())
453    }
454
455    #[test]
456    fn rejects_other_extension_types() {
457        let date = DType::Extension(Date::new(TimeUnit::Days, Nullability::Nullable).erased());
458        assert!(
459            ExtensionStoragePushdown::new(MinMax, Timestamp)
460                .return_dtype(&NumericalAggregateOpts::default(), &date)
461                .is_none()
462        );
463    }
464
465    #[test]
466    fn default_session_registers_temporal_order_aggregates() {
467        let session = VortexSession::empty();
468        let aggregate_fns = session.aggregate_fns();
469        for id in [
470            ExtensionStoragePushdown::new(IsSorted, Date).id(),
471            ExtensionStoragePushdown::new(IsSorted, Time).id(),
472            ExtensionStoragePushdown::new(IsSorted, Timestamp).id(),
473            ExtensionStoragePushdown::new(MinMax, Date).id(),
474            ExtensionStoragePushdown::new(MinMax, Time).id(),
475            ExtensionStoragePushdown::new(MinMax, Timestamp).id(),
476        ] {
477            assert!(
478                aggregate_fns.find_plugin(&id).is_some(),
479                "{id} is not registered"
480            );
481        }
482    }
483
484    #[rstest]
485    // Nulls sort first.
486    #[case::sorted([None, Some(1_000), Some(2_000), Some(2_000)], false, true)]
487    #[case::unsorted([Some(2_000), Some(1_000), None, Some(3_000)], false, false)]
488    #[case::strict_with_duplicates([None, Some(1_000), Some(2_000), Some(2_000)], true, false)]
489    fn is_sorted_over_timestamps(
490        #[case] values: [Option<i64>; 4],
491        #[case] strict: bool,
492        #[case] expected: bool,
493    ) -> VortexResult<()> {
494        let mut ctx = SESSION.create_execution_ctx();
495        let ext_dtype = Timestamp::new(TimeUnit::Milliseconds, Nullability::Nullable).erased();
496        let array = ExtensionArray::new(
497            ext_dtype.clone(),
498            PrimitiveArray::from_option_iter(values).into_array(),
499        )
500        .into_array();
501
502        let mut acc = Accumulator::try_new(
503            ExtensionStoragePushdown::new(IsSorted, Timestamp),
504            IsSortedOptions { strict },
505            DType::Extension(ext_dtype),
506        )?;
507        acc.accumulate(&array, &mut ctx)?;
508
509        assert_eq!(bool::try_from(&acc.finish()?)?, expected);
510        Ok(())
511    }
512
513    #[test]
514    fn min_max_over_dates_matches_storage() -> VortexResult<()> {
515        let mut ctx = SESSION.create_execution_ctx();
516        let ext_dtype = Date::new(TimeUnit::Days, Nullability::Nullable).erased();
517        let storage =
518            PrimitiveArray::from_option_iter([Some(20i32), None, Some(-3), Some(7)]).into_array();
519        let array = ExtensionArray::new(ext_dtype.clone(), storage.clone()).into_array();
520
521        let mut acc = Accumulator::try_new(
522            ExtensionStoragePushdown::new(MinMax, Date),
523            NumericalAggregateOpts::default(),
524            DType::Extension(ext_dtype),
525        )?;
526        acc.accumulate(&array, &mut ctx)?;
527
528        let mut expected = Accumulator::try_new(
529            MinMax,
530            NumericalAggregateOpts::default(),
531            storage.dtype().clone(),
532        )?;
533        expected.accumulate(&storage, &mut ctx)?;
534
535        assert_eq!(acc.finish()?, expected.finish()?);
536        Ok(())
537    }
538}