vortex_array/aggregate_fn/fns/bounded_min/
mod.rs1use 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#[derive(Clone, Debug, PartialEq, Eq, Hash)]
38pub struct BoundedMinOptions {
39 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#[derive(Clone, Debug)]
51pub struct BoundedMin;
52
53enum BoundedMinState {
54 Empty,
55 Value(Scalar),
56}
57
58pub 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 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 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 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 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
247fn 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}