Skip to main content

vortex_array/aggregate_fn/fns/bounded_min/
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;
7
8use vortex_buffer::BufferString;
9use vortex_buffer::ByteBuffer;
10use vortex_error::VortexExpect;
11use vortex_error::VortexResult;
12use vortex_error::vortex_ensure;
13use vortex_error::vortex_ensure_eq;
14use vortex_session::VortexSession;
15use vortex_session::registry::CachedId;
16
17use crate::ArrayRef;
18use crate::Columnar;
19use crate::ExecutionCtx;
20use crate::aggregate_fn::AggregateArgs;
21use crate::aggregate_fn::AggregateFnId;
22use crate::aggregate_fn::AggregateFnRef;
23use crate::aggregate_fn::AggregateFnSatisfaction;
24use crate::aggregate_fn::AggregateFnVTable;
25use crate::aggregate_fn::NumericalAggregateOpts;
26use crate::aggregate_fn::fns::min::Min;
27use crate::aggregate_fn::fns::min_max::MinMax;
28use crate::aggregate_fn::fns::min_max::columnar_min_max;
29use crate::aggregate_fn::fns::min_max::min_max;
30use crate::dtype::DType;
31use crate::partial_ord::partial_min;
32use crate::scalar::Scalar;
33use crate::scalar::ScalarTruncation;
34use crate::scalar::lower_bound;
35
36/// Options for [`BoundedMin`].
37#[derive(Clone, Debug, PartialEq, Eq, Hash)]
38pub struct BoundedMinOptions {
39    /// Maximum byte length for UTF8/Binary bounds.
40    pub max_bytes: NonZeroUsize,
41}
42
43impl Display for BoundedMinOptions {
44    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
45        write!(f, "{}", self.max_bytes.get())
46    }
47}
48
49/// Compute a byte-bounded lower bound for the minimum non-null value of a UTF8/Binary array.
50#[derive(Clone, Debug)]
51pub struct BoundedMin;
52
53enum BoundedMinState {
54    Empty,
55    Value(Scalar),
56}
57
58/// Partial accumulator state for the bounded minimum aggregate.
59pub struct BoundedMinPartial {
60    state: BoundedMinState,
61}
62
63impl BoundedMinPartial {
64    fn merge(&mut self, min: Scalar) {
65        if min.is_null() {
66            return;
67        }
68
69        self.state = match std::mem::replace(&mut self.state, BoundedMinState::Empty) {
70            BoundedMinState::Empty => BoundedMinState::Value(min),
71            BoundedMinState::Value(current) => BoundedMinState::Value(
72                partial_min(min, current).vortex_expect("incomparable bounded min scalars"),
73            ),
74        };
75    }
76}
77
78impl AggregateFnVTable for BoundedMin {
79    type Options = BoundedMinOptions;
80    type Partial = BoundedMinPartial;
81
82    fn id(&self) -> AggregateFnId {
83        static ID: CachedId = CachedId::new("vortex.bounded_min");
84        *ID
85    }
86
87    fn serialize(&self, options: &Self::Options) -> VortexResult<Option<Vec<u8>>> {
88        let max_bytes = u64::try_from(options.max_bytes.get())?;
89        Ok(Some(max_bytes.to_le_bytes().to_vec()))
90    }
91
92    fn deserialize(
93        &self,
94        metadata: &[u8],
95        _session: &VortexSession,
96    ) -> VortexResult<Self::Options> {
97        vortex_ensure_eq!(
98            metadata.len(),
99            size_of::<u64>(),
100            "BoundedMin options have the wrong byte length"
101        );
102        let mut bytes = [0u8; size_of::<u64>()];
103        bytes.copy_from_slice(metadata);
104        let max_bytes = usize::try_from(u64::from_le_bytes(bytes))?;
105        vortex_ensure!(max_bytes > 0, "BoundedMin requires max_bytes > 0");
106        Ok(BoundedMinOptions {
107            max_bytes: NonZeroUsize::new(max_bytes).vortex_expect("checked non-zero max_bytes"),
108        })
109    }
110
111    fn return_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
112        supported_dtype(options, input_dtype).map(DType::as_nullable)
113    }
114
115    fn can_satisfy(
116        &self,
117        options: &Self::Options,
118        requested: &AggregateFnRef,
119    ) -> AggregateFnSatisfaction {
120        if let Some(other) = requested.as_opt::<Self>() {
121            return if other == options {
122                AggregateFnSatisfaction::Exact
123            } else if options.max_bytes >= other.max_bytes {
124                AggregateFnSatisfaction::Approximate
125            } else {
126                AggregateFnSatisfaction::No
127            };
128        }
129
130        // The stored bound skips NaNs, so it cannot stand in for a NaN-including minimum.
131        if requested
132            .as_opt::<Min>()
133            .is_some_and(|options| options.skip_nans)
134        {
135            AggregateFnSatisfaction::Approximate
136        } else {
137            AggregateFnSatisfaction::No
138        }
139    }
140
141    fn partial_dtype(&self, options: &Self::Options, input_dtype: &DType) -> Option<DType> {
142        self.return_dtype(options, input_dtype)
143    }
144
145    fn empty_partial(
146        &self,
147        _args: AggregateArgs<'_, Self::Options>,
148    ) -> VortexResult<Self::Partial> {
149        Ok(BoundedMinPartial {
150            state: BoundedMinState::Empty,
151        })
152    }
153
154    fn partial_from_scalar(
155        &self,
156        _args: AggregateArgs<'_, Self::Options>,
157        scalar: &Scalar,
158    ) -> VortexResult<Self::Partial> {
159        // A null partial means the producing accumulator saw nothing valid.
160        let state = if scalar.is_null() {
161            BoundedMinState::Empty
162        } else {
163            BoundedMinState::Value(scalar.clone())
164        };
165        Ok(BoundedMinPartial { state })
166    }
167
168    fn merge_partials(
169        &self,
170        _args: AggregateArgs<'_, Self::Options>,
171        mut first: Self::Partial,
172        second: Self::Partial,
173    ) -> VortexResult<Self::Partial> {
174        if let BoundedMinState::Value(min) = second.state {
175            first.merge(min);
176        }
177        Ok(first)
178    }
179
180    fn to_scalar(
181        &self,
182        args: AggregateArgs<'_, Self::Options>,
183        partial: &Self::Partial,
184    ) -> VortexResult<Scalar> {
185        let dtype = args.dtype.as_nullable();
186        match &partial.state {
187            BoundedMinState::Empty => Ok(Scalar::null(dtype)),
188            BoundedMinState::Value(min) => min.cast(&dtype),
189        }
190    }
191
192    fn is_saturated(
193        &self,
194        _args: AggregateArgs<'_, Self::Options>,
195        _partial: &Self::Partial,
196    ) -> bool {
197        false
198    }
199
200    fn try_accumulate(
201        &self,
202        args: AggregateArgs<'_, Self::Options>,
203        partial: &mut Self::Partial,
204        batch: &ArrayRef,
205        ctx: &mut ExecutionCtx,
206    ) -> VortexResult<bool> {
207        // `min_max` computes both extrema in one pass and caches both on `batch`, so a
208        // `BoundedMax` over the same batch reads the cached value instead of a second scan.
209        if let Some(result) = min_max(batch, ctx, NumericalAggregateOpts::default())? {
210            merge_min(partial, result.min, args.options.max_bytes.get())?;
211        }
212        Ok(true)
213    }
214
215    fn accumulate(
216        &self,
217        args: AggregateArgs<'_, Self::Options>,
218        partial: &mut Self::Partial,
219        batch: &Columnar,
220        ctx: &mut ExecutionCtx,
221    ) -> VortexResult<()> {
222        // Delegate to the existing min_max implementation for now. A dedicated bounded-min
223        // aggregate would avoid computing max when only min is needed.
224        let Some(result) = columnar_min_max(batch, NumericalAggregateOpts::default(), ctx)? else {
225            return Ok(());
226        };
227        merge_min(partial, result.min, args.options.max_bytes.get())
228    }
229
230    fn finalize(
231        &self,
232        _args: AggregateArgs<'_, Self::Options>,
233        partials: ArrayRef,
234    ) -> VortexResult<ArrayRef> {
235        Ok(partials)
236    }
237
238    fn finalize_scalar(
239        &self,
240        args: AggregateArgs<'_, Self::Options>,
241        partial: &Self::Partial,
242    ) -> VortexResult<Scalar> {
243        self.to_scalar(args, partial)
244    }
245}
246
247/// Merge the byte-bounded lower bound of `min` into `partial`.
248fn merge_min(partial: &mut BoundedMinPartial, min: Scalar, max_bytes: usize) -> VortexResult<()> {
249    if let Some(bound) = truncate_min(min, max_bytes)? {
250        partial.merge(bound);
251    }
252    Ok(())
253}
254
255fn supported_dtype<'a>(_options: &BoundedMinOptions, input_dtype: &'a DType) -> Option<&'a DType> {
256    MinMax
257        .return_dtype(&NumericalAggregateOpts::default(), input_dtype)
258        .map(|_| input_dtype)
259}
260
261fn truncate_min(value: Scalar, max_bytes: usize) -> VortexResult<Option<Scalar>> {
262    let nullability = value.dtype().nullability();
263    match value.dtype() {
264        DType::Utf8(_) => {
265            Ok(
266                lower_bound(BufferString::from_scalar(value)?, max_bytes, nullability)
267                    .map(|(bound, _)| bound),
268            )
269        }
270        DType::Binary(_) => {
271            Ok(
272                lower_bound(ByteBuffer::from_scalar(value)?, max_bytes, nullability)
273                    .map(|(bound, _)| bound),
274            )
275        }
276        _ => Ok(Some(value)),
277    }
278}
279#[cfg(test)]
280mod tests {
281    use std::num::NonZeroUsize;
282    use std::sync::LazyLock;
283
284    use vortex_buffer::buffer;
285    use vortex_error::VortexExpect;
286    use vortex_error::VortexResult;
287    use vortex_session::VortexSession;
288
289    use crate::IntoArray;
290    use crate::VortexSessionExecute;
291    use crate::aggregate_fn::Accumulator;
292    use crate::aggregate_fn::AggregateFnSatisfaction;
293    use crate::aggregate_fn::AggregateFnVTable;
294    use crate::aggregate_fn::AggregateFnVTableExt;
295    use crate::aggregate_fn::DynAccumulator;
296    use crate::aggregate_fn::NumericalAggregateOpts;
297    use crate::aggregate_fn::fns::bounded_min::BoundedMin;
298    use crate::aggregate_fn::fns::bounded_min::BoundedMinOptions;
299    use crate::aggregate_fn::fns::max::Max;
300    use crate::aggregate_fn::fns::min::Min;
301    use crate::arrays::PrimitiveArray;
302    use crate::arrays::VarBinViewArray;
303    use crate::dtype::Nullability;
304    use crate::scalar::Scalar;
305    use crate::validity::Validity;
306
307    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
308
309    fn max_bytes(value: usize) -> NonZeroUsize {
310        NonZeroUsize::new(value).vortex_expect("non-zero max_bytes")
311    }
312
313    fn fresh_session() -> VortexSession {
314        VortexSession::empty()
315    }
316
317    #[test]
318    fn bounded_min_truncates_utf8_to_lower_bound() -> VortexResult<()> {
319        let mut ctx = SESSION.create_execution_ctx();
320        let array =
321            VarBinViewArray::from_iter_str(["snowman⛄️snowman", "untruncated"]).into_array();
322        let mut acc = Accumulator::try_new(
323            BoundedMin,
324            BoundedMinOptions {
325                max_bytes: max_bytes(9),
326            },
327            array.dtype().clone(),
328        )?;
329
330        acc.accumulate(&array, &mut ctx)?;
331
332        assert_eq!(
333            acc.finish()?,
334            Scalar::utf8("snowman", Nullability::Nullable)
335        );
336        Ok(())
337    }
338
339    #[test]
340    fn bounded_min_keeps_fixed_width_values_exact() -> VortexResult<()> {
341        let mut ctx = SESSION.create_execution_ctx();
342        let array = PrimitiveArray::new(buffer![10i32, 20, 5], Validity::NonNullable).into_array();
343        let mut acc = Accumulator::try_new(
344            BoundedMin,
345            BoundedMinOptions {
346                max_bytes: max_bytes(9),
347            },
348            array.dtype().clone(),
349        )?;
350
351        acc.accumulate(&array, &mut ctx)?;
352
353        assert_eq!(
354            acc.finish()?,
355            Scalar::primitive(5i32, Nullability::Nullable)
356        );
357        Ok(())
358    }
359
360    #[test]
361    fn bounded_min_null_partial_does_not_poison_existing_bound() -> VortexResult<()> {
362        let mut ctx = fresh_session().create_execution_ctx();
363        let values = VarBinViewArray::from_iter_bin([&[1u8][..]]).into_array();
364        let mut acc = Accumulator::try_new(
365            BoundedMin,
366            BoundedMinOptions {
367                max_bytes: max_bytes(2),
368            },
369            values.dtype().clone(),
370        )?;
371
372        acc.accumulate(&values, &mut ctx)?;
373        let empty = acc.empty_partial()?;
374        acc.fold_partial(empty)?;
375
376        assert_eq!(
377            acc.finish()?,
378            Scalar::binary(buffer![1u8], Nullability::Nullable)
379        );
380        Ok(())
381    }
382
383    #[test]
384    fn bounded_min_satisfies_min_bounds() {
385        let stored = BoundedMin.bind(BoundedMinOptions {
386            max_bytes: max_bytes(5),
387        });
388        let same = BoundedMin.bind(BoundedMinOptions {
389            max_bytes: max_bytes(5),
390        });
391        let looser_bounded = BoundedMin.bind(BoundedMinOptions {
392            max_bytes: max_bytes(4),
393        });
394        let tighter_bounded = BoundedMin.bind(BoundedMinOptions {
395            max_bytes: max_bytes(6),
396        });
397
398        assert_eq!(stored.can_satisfy(&same), AggregateFnSatisfaction::Exact);
399        assert_eq!(
400            stored.can_satisfy(&looser_bounded),
401            AggregateFnSatisfaction::Approximate
402        );
403        assert_eq!(
404            stored.can_satisfy(&tighter_bounded),
405            AggregateFnSatisfaction::No
406        );
407        assert_eq!(
408            stored.can_satisfy(&Min.bind(NumericalAggregateOpts::default())),
409            AggregateFnSatisfaction::Approximate
410        );
411        assert_eq!(
412            stored.can_satisfy(&Min.bind(NumericalAggregateOpts::include_nans())),
413            AggregateFnSatisfaction::No
414        );
415        assert_eq!(
416            Min.bind(NumericalAggregateOpts::include_nans())
417                .can_satisfy(&stored),
418            AggregateFnSatisfaction::No
419        );
420        assert_eq!(
421            Min.bind(NumericalAggregateOpts::default())
422                .can_satisfy(&stored),
423            AggregateFnSatisfaction::Approximate
424        );
425        assert_eq!(
426            stored.can_satisfy(&Max.bind(NumericalAggregateOpts::default())),
427            AggregateFnSatisfaction::No
428        );
429    }
430
431    #[test]
432    fn bounded_min_options_round_trip() -> VortexResult<()> {
433        let options = BoundedMinOptions {
434            max_bytes: max_bytes(64),
435        };
436        let metadata = BoundedMin
437            .serialize(&options)?
438            .expect("serializable options");
439        let roundtrip = BoundedMin.deserialize(&metadata, &SESSION)?;
440
441        assert_eq!(roundtrip, options);
442        Ok(())
443    }
444}