1use 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
42pub const BOUNDED_MAX_BOUND: &str = "bound";
44pub const BOUNDED_MAX_UNKNOWN: &str = "unknown";
46
47static NAMES: LazyLock<FieldNames> =
48 LazyLock::new(|| FieldNames::from([BOUNDED_MAX_BOUND, BOUNDED_MAX_UNKNOWN]));
49
50#[derive(Clone, Debug, PartialEq, Eq, Hash)]
52pub struct BoundedMaxOptions {
53 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#[derive(Clone, Debug)]
65pub struct BoundedMax;
66
67enum BoundedMaxState {
68 Empty,
69 Value(Scalar),
70 Unknown,
71}
72
73pub 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
106pub 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 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 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 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 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
331fn 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}