Skip to main content

vortex_array/aggregate_fn/fns/bounded_max/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Display;
5use std::fmt::Formatter;
6use std::num::NonZeroUsize;
7use std::sync::LazyLock;
8
9use vortex_buffer::BufferString;
10use vortex_buffer::ByteBuffer;
11use vortex_error::VortexExpect;
12use vortex_error::VortexResult;
13use vortex_error::vortex_bail;
14use vortex_error::vortex_ensure;
15use vortex_error::vortex_ensure_eq;
16use vortex_session::VortexSession;
17use vortex_session::registry::CachedId;
18
19use crate::ArrayRef;
20use crate::Columnar;
21use crate::ExecutionCtx;
22use crate::aggregate_fn::AggregateArgs;
23use crate::aggregate_fn::AggregateFnId;
24use crate::aggregate_fn::AggregateFnRef;
25use crate::aggregate_fn::AggregateFnSatisfaction;
26use crate::aggregate_fn::AggregateFnVTable;
27use crate::aggregate_fn::NumericalAggregateOpts;
28use crate::aggregate_fn::fns::max::Max;
29use crate::aggregate_fn::fns::min_max::MinMax;
30use crate::aggregate_fn::fns::min_max::columnar_min_max;
31use crate::aggregate_fn::fns::min_max::min_max;
32use crate::builtins::ArrayBuiltins;
33use crate::dtype::DType;
34use crate::dtype::FieldNames;
35use crate::dtype::Nullability;
36use crate::dtype::StructFields;
37use crate::partial_ord::partial_max;
38use crate::scalar::Scalar;
39use crate::scalar::ScalarTruncation;
40use crate::scalar::upper_bound;
41
42/// Field name for the bounded maximum upper-bound value in the partial state.
43pub const BOUNDED_MAX_BOUND: &str = "bound";
44/// Field name for whether the partial state represents an unknown upper bound.
45pub const BOUNDED_MAX_UNKNOWN: &str = "unknown";
46
47static NAMES: LazyLock<FieldNames> =
48    LazyLock::new(|| FieldNames::from([BOUNDED_MAX_BOUND, BOUNDED_MAX_UNKNOWN]));
49
50/// Options for [`BoundedMax`].
51#[derive(Clone, Debug, PartialEq, Eq, Hash)]
52pub struct BoundedMaxOptions {
53    /// Maximum byte length for UTF8/Binary bounds.
54    pub max_bytes: NonZeroUsize,
55}
56
57impl Display for BoundedMaxOptions {
58    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
59        write!(f, "{}", self.max_bytes.get())
60    }
61}
62
63/// Compute a byte-bounded upper bound for the maximum non-null value of a UTF8/Binary array.
64#[derive(Clone, Debug)]
65pub struct BoundedMax;
66
67enum BoundedMaxState {
68    Empty,
69    Value(Scalar),
70    Unknown,
71}
72
73/// Partial accumulator state for the bounded maximum aggregate.
74pub struct BoundedMaxPartial {
75    state: BoundedMaxState,
76}
77
78impl BoundedMaxPartial {
79    fn merge_bound(&mut self, max: Scalar) {
80        if max.is_null() {
81            return;
82        }
83
84        self.state = match std::mem::replace(&mut self.state, BoundedMaxState::Empty) {
85            BoundedMaxState::Empty => BoundedMaxState::Value(max),
86            BoundedMaxState::Value(current) => BoundedMaxState::Value(
87                partial_max(max, current).vortex_expect("incomparable bounded max scalars"),
88            ),
89            BoundedMaxState::Unknown => BoundedMaxState::Unknown,
90        };
91    }
92
93    fn unknown(&mut self) {
94        self.state = BoundedMaxState::Unknown;
95    }
96
97    fn final_scalar(&self, args: AggregateArgs<'_, BoundedMaxOptions>) -> VortexResult<Scalar> {
98        let dtype = args.return_dtype.clone();
99        match &self.state {
100            BoundedMaxState::Value(max) => max.cast(&dtype),
101            BoundedMaxState::Empty | BoundedMaxState::Unknown => Ok(Scalar::null(dtype)),
102        }
103    }
104}
105
106/// Return the serialized partial-state dtype for [`BoundedMax`].
107///
108/// A null struct means the partial is empty. A non-null struct with a null `bound` and
109/// `unknown = true` means the input has a non-null maximum but no finite upper bound could be
110/// represented within the configured byte limit.
111pub fn make_bounded_max_partial_dtype(element_dtype: &DType) -> DType {
112    DType::Struct(
113        StructFields::new(
114            NAMES.clone(),
115            vec![
116                element_dtype.as_nullable(),
117                DType::Bool(Nullability::NonNullable),
118            ],
119        ),
120        Nullability::Nullable,
121    )
122}
123
124impl AggregateFnVTable for BoundedMax {
125    type Options = BoundedMaxOptions;
126    type Partial = BoundedMaxPartial;
127
128    fn id(&self) -> AggregateFnId {
129        static ID: CachedId = CachedId::new("vortex.bounded_max");
130        *ID
131    }
132
133    fn serialize(&self, options: &Self::Options) -> VortexResult<Option<Vec<u8>>> {
134        let max_bytes = u64::try_from(options.max_bytes.get())?;
135        Ok(Some(max_bytes.to_le_bytes().to_vec()))
136    }
137
138    fn deserialize(
139        &self,
140        metadata: &[u8],
141        _session: &VortexSession,
142    ) -> VortexResult<Self::Options> {
143        vortex_ensure_eq!(
144            metadata.len(),
145            size_of::<u64>(),
146            "BoundedMax options have the wrong byte length"
147        );
148        let mut bytes = [0u8; size_of::<u64>()];
149        bytes.copy_from_slice(metadata);
150        let max_bytes = usize::try_from(u64::from_le_bytes(bytes))?;
151        vortex_ensure!(max_bytes > 0, "BoundedMax requires max_bytes > 0");
152        Ok(BoundedMaxOptions {
153            max_bytes: NonZeroUsize::new(max_bytes).vortex_expect("checked non-zero max_bytes"),
154        })
155    }
156
157    fn return_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
158        supported_dtype(options, input_dtype).map(DType::as_nullable)
159    }
160
161    fn can_satisfy(
162        &self,
163        options: &Self::Options,
164        requested: &AggregateFnRef,
165    ) -> AggregateFnSatisfaction {
166        if let Some(other) = requested.as_opt::<Self>() {
167            return if other == options {
168                AggregateFnSatisfaction::Exact
169            } else if options.max_bytes >= other.max_bytes {
170                AggregateFnSatisfaction::Approximate
171            } else {
172                AggregateFnSatisfaction::No
173            };
174        }
175
176        // The stored bound skips NaNs, so it cannot stand in for a NaN-including maximum.
177        if requested
178            .as_opt::<Max>()
179            .is_some_and(|options| options.skip_nans)
180        {
181            AggregateFnSatisfaction::Approximate
182        } else {
183            AggregateFnSatisfaction::No
184        }
185    }
186
187    fn partial_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
188        supported_dtype(options, input_dtype).map(make_bounded_max_partial_dtype)
189    }
190
191    fn empty_partial(
192        &self,
193        _args: AggregateArgs<'_, Self::Options>,
194    ) -> VortexResult<Self::Partial> {
195        Ok(BoundedMaxPartial {
196            state: BoundedMaxState::Empty,
197        })
198    }
199
200    fn partial_from_scalar(
201        &self,
202        _args: AggregateArgs<'_, Self::Options>,
203        scalar: &Scalar,
204    ) -> VortexResult<Self::Partial> {
205        // A null partial means the producing accumulator saw nothing valid.
206        let state = if scalar.is_null() {
207            BoundedMaxState::Empty
208        } else {
209            let Some(fields) = scalar.as_struct_opt() else {
210                vortex_bail!(
211                    "BoundedMax partial must be a struct, got {}",
212                    scalar.dtype()
213                );
214            };
215            let Some(bound) = fields.field_by_idx(0) else {
216                vortex_bail!("BoundedMax partial is missing its bound field");
217            };
218            let Some(unknown) = fields
219                .field_by_idx(1)
220                .and_then(|unknown| unknown.as_bool().value())
221            else {
222                vortex_bail!("BoundedMax partial is missing its non-null unknown field");
223            };
224
225            if unknown {
226                BoundedMaxState::Unknown
227            } else if bound.is_null() {
228                BoundedMaxState::Empty
229            } else {
230                BoundedMaxState::Value(bound)
231            }
232        };
233        Ok(BoundedMaxPartial { state })
234    }
235
236    fn merge_partials(
237        &self,
238        _args: AggregateArgs<'_, Self::Options>,
239        mut first: Self::Partial,
240        second: Self::Partial,
241    ) -> VortexResult<Self::Partial> {
242        match second.state {
243            BoundedMaxState::Empty => {}
244            BoundedMaxState::Value(max) => first.merge_bound(max),
245            BoundedMaxState::Unknown => first.unknown(),
246        }
247        Ok(first)
248    }
249
250    fn to_scalar(
251        &self,
252        args: AggregateArgs<'_, Self::Options>,
253        partial: &Self::Partial,
254    ) -> VortexResult<Scalar> {
255        let dtype = args.partial_dtype.clone();
256        let bound_dtype = args.dtype.as_nullable();
257        match &partial.state {
258            BoundedMaxState::Empty => Ok(Scalar::null(dtype)),
259            BoundedMaxState::Value(max) => Ok(Scalar::struct_(
260                dtype,
261                vec![
262                    max.cast(&bound_dtype)?,
263                    Scalar::bool(false, Nullability::NonNullable),
264                ],
265            )),
266            BoundedMaxState::Unknown => Ok(Scalar::struct_(
267                dtype,
268                vec![
269                    Scalar::null(bound_dtype),
270                    Scalar::bool(true, Nullability::NonNullable),
271                ],
272            )),
273        }
274    }
275
276    fn is_saturated(
277        &self,
278        _args: AggregateArgs<'_, Self::Options>,
279        partial: &Self::Partial,
280    ) -> bool {
281        matches!(partial.state, BoundedMaxState::Unknown)
282    }
283
284    fn try_accumulate(
285        &self,
286        args: AggregateArgs<'_, Self::Options>,
287        partial: &mut Self::Partial,
288        batch: &ArrayRef,
289        ctx: &mut ExecutionCtx,
290    ) -> VortexResult<bool> {
291        // `min_max` computes both extrema in one pass and caches both on `batch`, so a
292        // `BoundedMin` over the same batch reads the cached value instead of a second scan.
293        if let Some(result) = min_max(batch, ctx, NumericalAggregateOpts::default())? {
294            merge_max(partial, result.max, args.options.max_bytes.get())?;
295        }
296        Ok(true)
297    }
298
299    fn accumulate(
300        &self,
301        args: AggregateArgs<'_, Self::Options>,
302        partial: &mut Self::Partial,
303        batch: &Columnar,
304        ctx: &mut ExecutionCtx,
305    ) -> VortexResult<()> {
306        // Delegate to the existing min_max implementation for now. A dedicated bounded-max
307        // aggregate would avoid computing min when only max is needed.
308        let Some(result) = columnar_min_max(batch, NumericalAggregateOpts::default(), ctx)? else {
309            return Ok(());
310        };
311        merge_max(partial, result.max, args.options.max_bytes.get())
312    }
313
314    fn finalize(
315        &self,
316        _args: AggregateArgs<'_, Self::Options>,
317        partials: ArrayRef,
318    ) -> VortexResult<ArrayRef> {
319        partials.get_item(BOUNDED_MAX_BOUND)
320    }
321
322    fn finalize_scalar(
323        &self,
324        args: AggregateArgs<'_, Self::Options>,
325        partial: &Self::Partial,
326    ) -> VortexResult<Scalar> {
327        partial.final_scalar(args)
328    }
329}
330
331/// Merge the byte-bounded upper bound of `max` into `partial`.
332fn merge_max(partial: &mut BoundedMaxPartial, max: Scalar, max_bytes: usize) -> VortexResult<()> {
333    match truncate_max(max, max_bytes)? {
334        Some(bound) => partial.merge_bound(bound),
335        None => partial.unknown(),
336    }
337    Ok(())
338}
339
340fn supported_dtype<'a>(_options: &BoundedMaxOptions, input_dtype: &'a DType) -> Option<&'a DType> {
341    MinMax
342        .return_dtype(&NumericalAggregateOpts::default(), input_dtype)
343        .map(|_| input_dtype)
344}
345
346fn truncate_max(value: Scalar, max_bytes: usize) -> VortexResult<Option<Scalar>> {
347    let nullability = value.dtype().nullability();
348    match value.dtype() {
349        DType::Utf8(_) => {
350            Ok(
351                upper_bound(BufferString::from_scalar(value)?, max_bytes, nullability)
352                    .map(|(bound, _)| bound),
353            )
354        }
355        DType::Binary(_) => {
356            Ok(
357                upper_bound(ByteBuffer::from_scalar(value)?, max_bytes, nullability)
358                    .map(|(bound, _)| bound),
359            )
360        }
361        _ => Ok(Some(value)),
362    }
363}
364
365#[cfg(test)]
366mod tests {
367    use std::num::NonZeroUsize;
368    use std::sync::LazyLock;
369
370    use vortex_buffer::buffer;
371    use vortex_error::VortexExpect;
372    use vortex_error::VortexResult;
373    use vortex_session::VortexSession;
374
375    use crate::IntoArray;
376    use crate::VortexSessionExecute;
377    use crate::aggregate_fn::Accumulator;
378    use crate::aggregate_fn::AggregateFnSatisfaction;
379    use crate::aggregate_fn::AggregateFnVTable;
380    use crate::aggregate_fn::AggregateFnVTableExt;
381    use crate::aggregate_fn::DynAccumulator;
382    use crate::aggregate_fn::NumericalAggregateOpts;
383    use crate::aggregate_fn::fns::bounded_max::BoundedMax;
384    use crate::aggregate_fn::fns::bounded_max::BoundedMaxOptions;
385    use crate::aggregate_fn::fns::bounded_max::BoundedMaxPartial;
386    use crate::aggregate_fn::fns::bounded_max::BoundedMaxState;
387    use crate::aggregate_fn::fns::max::Max;
388    use crate::aggregate_fn::fns::min::Min;
389    use crate::arrays::PrimitiveArray;
390    use crate::arrays::VarBinViewArray;
391    use crate::dtype::Nullability;
392    use crate::scalar::Scalar;
393    use crate::validity::Validity;
394
395    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
396
397    fn max_bytes(value: usize) -> NonZeroUsize {
398        NonZeroUsize::new(value).vortex_expect("non-zero max_bytes")
399    }
400
401    fn fresh_session() -> VortexSession {
402        VortexSession::empty()
403    }
404
405    #[test]
406    fn bounded_max_truncates_utf8_to_upper_bound() -> VortexResult<()> {
407        let mut ctx = SESSION.create_execution_ctx();
408        let array = VarBinViewArray::from_iter_str(["aardvark", "char🪩"]).into_array();
409        let mut acc = Accumulator::try_new(
410            BoundedMax,
411            BoundedMaxOptions {
412                max_bytes: max_bytes(5),
413            },
414            array.dtype().clone(),
415        )?;
416
417        acc.accumulate(&array, &mut ctx)?;
418
419        assert_eq!(acc.finish()?, Scalar::utf8("chas", Nullability::Nullable));
420        Ok(())
421    }
422
423    #[test]
424    fn bounded_max_unknown_upper_bound_returns_null() -> VortexResult<()> {
425        let mut ctx = SESSION.create_execution_ctx();
426        let array = VarBinViewArray::from_iter_bin([&[255u8, 255, 255][..]]).into_array();
427        let mut acc = Accumulator::try_new(
428            BoundedMax,
429            BoundedMaxOptions {
430                max_bytes: max_bytes(2),
431            },
432            array.dtype().clone(),
433        )?;
434
435        acc.accumulate(&array, &mut ctx)?;
436
437        assert_eq!(acc.finish()?, Scalar::null(array.dtype().as_nullable()));
438        Ok(())
439    }
440
441    #[test]
442    fn bounded_max_empty_does_not_poison_later_values() -> VortexResult<()> {
443        let mut ctx = SESSION.create_execution_ctx();
444        let empty = VarBinViewArray::from_iter_bin(Vec::<&[u8]>::new()).into_array();
445        let values = VarBinViewArray::from_iter_bin([&[1u8][..]]).into_array();
446        let mut acc = Accumulator::try_new(
447            BoundedMax,
448            BoundedMaxOptions {
449                max_bytes: max_bytes(2),
450            },
451            empty.dtype().clone(),
452        )?;
453
454        acc.accumulate(&empty, &mut ctx)?;
455        acc.accumulate(&values, &mut ctx)?;
456
457        assert_eq!(
458            acc.finish()?,
459            Scalar::binary(buffer![1u8], Nullability::Nullable)
460        );
461        Ok(())
462    }
463
464    #[test]
465    fn bounded_max_unknown_poisons_later_values() -> VortexResult<()> {
466        let mut ctx = SESSION.create_execution_ctx();
467        let unknown = VarBinViewArray::from_iter_bin([&[255u8, 255, 255][..]]).into_array();
468        let values = VarBinViewArray::from_iter_bin([&[1u8][..]]).into_array();
469        let mut acc = Accumulator::try_new(
470            BoundedMax,
471            BoundedMaxOptions {
472                max_bytes: max_bytes(2),
473            },
474            unknown.dtype().clone(),
475        )?;
476
477        acc.accumulate(&unknown, &mut ctx)?;
478        acc.accumulate(&values, &mut ctx)?;
479
480        assert_eq!(acc.finish()?, Scalar::null(unknown.dtype().as_nullable()));
481        Ok(())
482    }
483
484    #[test]
485    fn bounded_max_empty_partial_does_not_poison_existing_bound() -> VortexResult<()> {
486        let mut ctx = fresh_session().create_execution_ctx();
487        let values = VarBinViewArray::from_iter_bin([&[1u8][..]]).into_array();
488        let mut acc = Accumulator::try_new(
489            BoundedMax,
490            BoundedMaxOptions {
491                max_bytes: max_bytes(2),
492            },
493            values.dtype().clone(),
494        )?;
495
496        acc.accumulate(&values, &mut ctx)?;
497        let empty = acc.empty_partial()?;
498        acc.fold_partial(empty)?;
499
500        assert_eq!(
501            acc.finish()?,
502            Scalar::binary(buffer![1u8], Nullability::Nullable)
503        );
504        Ok(())
505    }
506
507    #[test]
508    fn bounded_max_unknown_partial_poisons_existing_bound() -> VortexResult<()> {
509        let mut ctx = fresh_session().create_execution_ctx();
510        let values = VarBinViewArray::from_iter_bin([&[1u8][..]]).into_array();
511        let mut acc = Accumulator::try_new(
512            BoundedMax,
513            BoundedMaxOptions {
514                max_bytes: max_bytes(2),
515            },
516            values.dtype().clone(),
517        )?;
518
519        acc.accumulate(&values, &mut ctx)?;
520        acc.fold_partial(BoundedMaxPartial {
521            state: BoundedMaxState::Unknown,
522        })?;
523
524        assert_eq!(acc.finish()?, Scalar::null(values.dtype().as_nullable()));
525        Ok(())
526    }
527
528    #[test]
529    fn bounded_max_keeps_fixed_width_values_exact() -> VortexResult<()> {
530        let mut ctx = SESSION.create_execution_ctx();
531        let array = PrimitiveArray::new(buffer![10i32, 20, 5], Validity::NonNullable).into_array();
532        let mut acc = Accumulator::try_new(
533            BoundedMax,
534            BoundedMaxOptions {
535                max_bytes: max_bytes(9),
536            },
537            array.dtype().clone(),
538        )?;
539
540        acc.accumulate(&array, &mut ctx)?;
541
542        assert_eq!(
543            acc.finish()?,
544            Scalar::primitive(20i32, Nullability::Nullable)
545        );
546        Ok(())
547    }
548
549    #[test]
550    fn bounded_max_satisfies_max_bounds() {
551        let stored = BoundedMax.bind(BoundedMaxOptions {
552            max_bytes: max_bytes(5),
553        });
554        let same = BoundedMax.bind(BoundedMaxOptions {
555            max_bytes: max_bytes(5),
556        });
557        let looser_bounded = BoundedMax.bind(BoundedMaxOptions {
558            max_bytes: max_bytes(4),
559        });
560        let tighter_bounded = BoundedMax.bind(BoundedMaxOptions {
561            max_bytes: max_bytes(6),
562        });
563
564        assert_eq!(stored.can_satisfy(&same), AggregateFnSatisfaction::Exact);
565        assert_eq!(
566            stored.can_satisfy(&looser_bounded),
567            AggregateFnSatisfaction::Approximate
568        );
569        assert_eq!(
570            stored.can_satisfy(&tighter_bounded),
571            AggregateFnSatisfaction::No
572        );
573        assert_eq!(
574            stored.can_satisfy(&Max.bind(NumericalAggregateOpts::default())),
575            AggregateFnSatisfaction::Approximate
576        );
577        assert_eq!(
578            stored.can_satisfy(&Max.bind(NumericalAggregateOpts::include_nans())),
579            AggregateFnSatisfaction::No
580        );
581        assert_eq!(
582            Max.bind(NumericalAggregateOpts::include_nans())
583                .can_satisfy(&stored),
584            AggregateFnSatisfaction::No
585        );
586        assert_eq!(
587            Max.bind(NumericalAggregateOpts::default())
588                .can_satisfy(&stored),
589            AggregateFnSatisfaction::Approximate
590        );
591        assert_eq!(
592            stored.can_satisfy(&Min.bind(NumericalAggregateOpts::default())),
593            AggregateFnSatisfaction::No
594        );
595    }
596
597    #[test]
598    fn bounded_max_options_round_trip() -> VortexResult<()> {
599        let options = BoundedMaxOptions {
600            max_bytes: max_bytes(64),
601        };
602        let metadata = BoundedMax
603            .serialize(&options)?
604            .expect("serializable options");
605        let roundtrip = BoundedMax.deserialize(&metadata, &SESSION)?;
606
607        assert_eq!(roundtrip, options);
608        Ok(())
609    }
610}