11// SPDX-License-Identifier: Apache-2.0
22// SPDX-FileCopyrightText: Copyright the Vortex contributors
33
4+ use std:: cmp:: Ordering ;
45use std:: fmt:: Display ;
56use std:: fmt:: Formatter ;
67use std:: num:: NonZeroUsize ;
@@ -34,7 +35,6 @@ use crate::dtype::DType;
3435use crate :: dtype:: FieldNames ;
3536use crate :: dtype:: Nullability ;
3637use crate :: dtype:: StructFields ;
37- use crate :: partial_ord:: partial_max;
3838use crate :: scalar:: Scalar ;
3939use crate :: scalar:: ScalarTruncation ;
4040use crate :: scalar:: upper_bound;
@@ -66,27 +66,59 @@ pub struct BoundedMax;
6666
6767enum BoundedMaxState {
6868 Empty ,
69- Value ( Scalar ) ,
69+ /// The true maximum: it fit within the byte bound, so it was never truncated.
70+ Exact ( Scalar ) ,
71+ /// An upper bound of the true maximum, either because the maximum was truncated or because
72+ /// it was combined from a serialized partial, which doesn't record exactness.
73+ Inexact ( Scalar ) ,
7074 Unknown ,
7175}
7276
77+ impl BoundedMaxState {
78+ fn bound ( bound : Scalar , exact : bool ) -> Self {
79+ if exact {
80+ Self :: Exact ( bound)
81+ } else {
82+ Self :: Inexact ( bound)
83+ }
84+ }
85+ }
86+
7387/// Partial accumulator state for the bounded maximum aggregate.
7488pub struct BoundedMaxPartial {
7589 state : BoundedMaxState ,
7690}
7791
7892impl BoundedMaxPartial {
79- fn merge_bound ( & mut self , max : Scalar ) {
80- if max . is_null ( ) {
93+ fn merge_bound ( & mut self , bound : Scalar , exact : bool ) {
94+ if bound . is_null ( ) {
8195 return ;
8296 }
8397
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 ,
98+ let ( current, current_exact) =
99+ match std:: mem:: replace ( & mut self . state , BoundedMaxState :: Empty ) {
100+ BoundedMaxState :: Empty => {
101+ self . state = BoundedMaxState :: bound ( bound, exact) ;
102+ return ;
103+ }
104+ BoundedMaxState :: Unknown => {
105+ self . state = BoundedMaxState :: Unknown ;
106+ return ;
107+ }
108+ BoundedMaxState :: Exact ( current) => ( current, true ) ,
109+ BoundedMaxState :: Inexact ( current) => ( current, false ) ,
110+ } ;
111+
112+ // The larger bound wins. It is the true maximum iff it was not truncated: every other
113+ // value is at most its own bound, which is below the winner. On a tie, either side being
114+ // exact means the true maximum reaches the bound.
115+ self . state = match bound
116+ . partial_cmp ( & current)
117+ . vortex_expect ( "incomparable bounded max scalars" )
118+ {
119+ Ordering :: Greater => BoundedMaxState :: bound ( bound, exact) ,
120+ Ordering :: Less => BoundedMaxState :: bound ( current, current_exact) ,
121+ Ordering :: Equal => BoundedMaxState :: bound ( current, exact || current_exact) ,
90122 } ;
91123 }
92124
@@ -97,7 +129,7 @@ impl BoundedMaxPartial {
97129 fn final_scalar ( & self , args : AggregateArgs < ' _ , BoundedMaxOptions > ) -> VortexResult < Scalar > {
98130 let dtype = args. return_dtype . clone ( ) ;
99131 match & self . state {
100- BoundedMaxState :: Value ( max ) => max . cast ( & dtype) ,
132+ BoundedMaxState :: Exact ( bound ) | BoundedMaxState :: Inexact ( bound ) => bound . cast ( & dtype) ,
101133 BoundedMaxState :: Empty | BoundedMaxState :: Unknown => Ok ( Scalar :: null ( dtype) ) ,
102134 }
103135 }
@@ -184,6 +216,27 @@ impl AggregateFnVTable for BoundedMax {
184216 }
185217 }
186218
219+ fn partial_can_satisfy (
220+ & self ,
221+ options : & Self :: Options ,
222+ partial : & Self :: Partial ,
223+ requested : & AggregateFnRef ,
224+ ) -> AggregateFnSatisfaction {
225+ let satisfaction = self . can_satisfy ( options, requested) ;
226+ let untruncated = matches ! (
227+ partial. state,
228+ BoundedMaxState :: Empty | BoundedMaxState :: Exact ( _)
229+ ) ;
230+ if satisfaction == AggregateFnSatisfaction :: Approximate
231+ && untruncated
232+ && requested. is :: < Max > ( )
233+ {
234+ AggregateFnSatisfaction :: Exact
235+ } else {
236+ satisfaction
237+ }
238+ }
239+
187240 fn partial_dtype ( & self , options : & Self :: Options , input_dtype : & DType ) -> Option < DType > {
188241 supported_dtype ( options, input_dtype) . map ( make_bounded_max_partial_dtype)
189242 }
@@ -227,7 +280,8 @@ impl AggregateFnVTable for BoundedMax {
227280 } else if bound. is_null ( ) {
228281 BoundedMaxState :: Empty
229282 } else {
230- BoundedMaxState :: Value ( bound)
283+ // Serialized partials don't record exactness.
284+ BoundedMaxState :: Inexact ( bound)
231285 }
232286 } ;
233287 Ok ( BoundedMaxPartial { state } )
@@ -241,7 +295,8 @@ impl AggregateFnVTable for BoundedMax {
241295 ) -> VortexResult < Self :: Partial > {
242296 match second. state {
243297 BoundedMaxState :: Empty => { }
244- BoundedMaxState :: Value ( max) => first. merge_bound ( max) ,
298+ BoundedMaxState :: Exact ( bound) => first. merge_bound ( bound, true ) ,
299+ BoundedMaxState :: Inexact ( bound) => first. merge_bound ( bound, false ) ,
245300 BoundedMaxState :: Unknown => first. unknown ( ) ,
246301 }
247302 Ok ( first)
@@ -256,10 +311,10 @@ impl AggregateFnVTable for BoundedMax {
256311 let bound_dtype = args. dtype . as_nullable ( ) ;
257312 match & partial. state {
258313 BoundedMaxState :: Empty => Ok ( Scalar :: null ( dtype) ) ,
259- BoundedMaxState :: Value ( max ) => Ok ( Scalar :: struct_ (
314+ BoundedMaxState :: Exact ( bound ) | BoundedMaxState :: Inexact ( bound ) => Ok ( Scalar :: struct_ (
260315 dtype,
261316 vec ! [
262- max . cast( & bound_dtype) ?,
317+ bound . cast( & bound_dtype) ?,
263318 Scalar :: bool ( false , Nullability :: NonNullable ) ,
264319 ] ,
265320 ) ) ,
@@ -298,7 +353,7 @@ impl AggregateFnVTable for BoundedMax {
298353 return Ok ( ( ) ) ;
299354 } ;
300355 match truncate_max ( result. max , args. options . max_bytes . get ( ) ) ? {
301- Some ( bound) => partial. merge_bound ( bound) ,
356+ Some ( ( bound, truncated ) ) => partial. merge_bound ( bound, !truncated ) ,
302357 None => partial. unknown ( ) ,
303358 }
304359 Ok ( ( ) )
@@ -327,22 +382,21 @@ fn supported_dtype<'a>(_options: &BoundedMaxOptions, input_dtype: &'a DType) ->
327382 . map ( |_| input_dtype)
328383}
329384
330- fn truncate_max ( value : Scalar , max_bytes : usize ) -> VortexResult < Option < Scalar > > {
385+ /// Returns the upper bound and whether it was truncated, or `None` if no bound fits `max_bytes`.
386+ fn truncate_max ( value : Scalar , max_bytes : usize ) -> VortexResult < Option < ( Scalar , bool ) > > {
331387 let nullability = value. dtype ( ) . nullability ( ) ;
332388 match value. dtype ( ) {
333- DType :: Utf8 ( _) => {
334- Ok (
335- upper_bound ( BufferString :: from_scalar ( value) ?, max_bytes, nullability)
336- . map ( |( bound, _) | bound) ,
337- )
338- }
339- DType :: Binary ( _) => {
340- Ok (
341- upper_bound ( ByteBuffer :: from_scalar ( value) ?, max_bytes, nullability)
342- . map ( |( bound, _) | bound) ,
343- )
344- }
345- _ => Ok ( Some ( value) ) ,
389+ DType :: Utf8 ( _) => Ok ( upper_bound (
390+ BufferString :: from_scalar ( value) ?,
391+ max_bytes,
392+ nullability,
393+ ) ) ,
394+ DType :: Binary ( _) => Ok ( upper_bound (
395+ ByteBuffer :: from_scalar ( value) ?,
396+ max_bytes,
397+ nullability,
398+ ) ) ,
399+ _ => Ok ( Some ( ( value, false ) ) ) ,
346400 }
347401}
348402
@@ -589,4 +643,67 @@ mod tests {
589643 assert_eq ! ( roundtrip, options) ;
590644 Ok ( ( ) )
591645 }
646+
647+ #[ test]
648+ fn bounded_max_exactly_satisfies_max_only_when_untruncated ( ) -> VortexResult < ( ) > {
649+ let mut ctx = array_session ( ) . create_execution_ctx ( ) ;
650+ let requested = Max . bind ( NumericalAggregateOpts :: skip_nans ( ) ) ;
651+ let new_acc = || {
652+ Accumulator :: try_new (
653+ BoundedMax ,
654+ BoundedMaxOptions {
655+ max_bytes : max_bytes ( 4 ) ,
656+ } ,
657+ VarBinViewArray :: from_iter_str ( [ "x" ] ) . dtype ( ) . clone ( ) ,
658+ )
659+ } ;
660+
661+ // Every value fits the bound, so the bound is the true extremum.
662+ let mut acc = new_acc ( ) ?;
663+ acc. accumulate (
664+ & VarBinViewArray :: from_iter_str ( [ "b" , "abc" ] ) . into_array ( ) ,
665+ & mut ctx,
666+ ) ?;
667+ assert_eq ! ( acc. can_satisfy( & requested) , AggregateFnSatisfaction :: Exact ) ;
668+
669+ // A truncated value that isn't the extremum doesn't affect exactness.
670+ acc. accumulate (
671+ & VarBinViewArray :: from_iter_str ( [ "aaaaa" ] ) . into_array ( ) ,
672+ & mut ctx,
673+ ) ?;
674+ assert_eq ! ( acc. can_satisfy( & requested) , AggregateFnSatisfaction :: Exact ) ;
675+
676+ // A truncated extremum makes the bound approximate.
677+ acc. accumulate (
678+ & VarBinViewArray :: from_iter_str ( [ "bbbbb" ] ) . into_array ( ) ,
679+ & mut ctx,
680+ ) ?;
681+ assert_eq ! (
682+ acc. can_satisfy( & requested) ,
683+ AggregateFnSatisfaction :: Approximate
684+ ) ;
685+
686+ // Exactness isn't serialized, so a winning partial combined from its scalar form is
687+ // approximate even though it was exact where it was computed.
688+ let mut source = new_acc ( ) ?;
689+ source. accumulate (
690+ & VarBinViewArray :: from_iter_str ( [ "b" ] ) . into_array ( ) ,
691+ & mut ctx,
692+ ) ?;
693+ assert_eq ! (
694+ source. can_satisfy( & requested) ,
695+ AggregateFnSatisfaction :: Exact
696+ ) ;
697+ let mut acc = new_acc ( ) ?;
698+ acc. accumulate (
699+ & VarBinViewArray :: from_iter_str ( [ "a" ] ) . into_array ( ) ,
700+ & mut ctx,
701+ ) ?;
702+ acc. combine_partials ( source. partial_scalar ( ) ?) ?;
703+ assert_eq ! (
704+ acc. can_satisfy( & requested) ,
705+ AggregateFnSatisfaction :: Approximate
706+ ) ;
707+ Ok ( ( ) )
708+ }
592709}
0 commit comments