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 ;
@@ -33,7 +34,6 @@ use crate::dtype::DType;
3334use crate :: dtype:: FieldNames ;
3435use crate :: dtype:: Nullability ;
3536use crate :: dtype:: StructFields ;
36- use crate :: partial_ord:: partial_max;
3737use crate :: scalar:: Scalar ;
3838use crate :: scalar:: ScalarTruncation ;
3939use crate :: scalar:: upper_bound;
@@ -65,27 +65,59 @@ pub struct BoundedMax;
6565
6666enum BoundedMaxState {
6767 Empty ,
68- Value ( Scalar ) ,
68+ /// The true maximum: it fit within the byte bound, so it was never truncated.
69+ Exact ( Scalar ) ,
70+ /// An upper bound of the true maximum, either because the maximum was truncated or because
71+ /// it was combined from a serialized partial, which doesn't record exactness.
72+ Inexact ( Scalar ) ,
6973 Unknown ,
7074}
7175
76+ impl BoundedMaxState {
77+ fn bound ( bound : Scalar , exact : bool ) -> Self {
78+ if exact {
79+ Self :: Exact ( bound)
80+ } else {
81+ Self :: Inexact ( bound)
82+ }
83+ }
84+ }
85+
7286/// Partial accumulator state for the bounded maximum aggregate.
7387pub struct BoundedMaxPartial {
7488 state : BoundedMaxState ,
7589}
7690
7791impl BoundedMaxPartial {
78- fn merge_bound ( & mut self , max : Scalar ) {
79- if max . is_null ( ) {
92+ fn merge_bound ( & mut self , bound : Scalar , exact : bool ) {
93+ if bound . is_null ( ) {
8094 return ;
8195 }
8296
83- self . state = match std:: mem:: replace ( & mut self . state , BoundedMaxState :: Empty ) {
84- BoundedMaxState :: Empty => BoundedMaxState :: Value ( max) ,
85- BoundedMaxState :: Value ( current) => BoundedMaxState :: Value (
86- partial_max ( max, current) . vortex_expect ( "incomparable bounded max scalars" ) ,
87- ) ,
88- BoundedMaxState :: Unknown => BoundedMaxState :: Unknown ,
97+ let ( current, current_exact) =
98+ match std:: mem:: replace ( & mut self . state , BoundedMaxState :: Empty ) {
99+ BoundedMaxState :: Empty => {
100+ self . state = BoundedMaxState :: bound ( bound, exact) ;
101+ return ;
102+ }
103+ BoundedMaxState :: Unknown => {
104+ self . state = BoundedMaxState :: Unknown ;
105+ return ;
106+ }
107+ BoundedMaxState :: Exact ( current) => ( current, true ) ,
108+ BoundedMaxState :: Inexact ( current) => ( current, false ) ,
109+ } ;
110+
111+ // The larger bound wins. It is the true maximum iff it was not truncated: every other
112+ // value is at most its own bound, which is below the winner. On a tie, either side being
113+ // exact means the true maximum reaches the bound.
114+ self . state = match bound
115+ . partial_cmp ( & current)
116+ . vortex_expect ( "incomparable bounded max scalars" )
117+ {
118+ Ordering :: Greater => BoundedMaxState :: bound ( bound, exact) ,
119+ Ordering :: Less => BoundedMaxState :: bound ( current, current_exact) ,
120+ Ordering :: Equal => BoundedMaxState :: bound ( current, exact || current_exact) ,
89121 } ;
90122 }
91123
@@ -96,7 +128,7 @@ impl BoundedMaxPartial {
96128 fn final_scalar ( & self , args : AggregateArgs < ' _ , BoundedMaxOptions > ) -> VortexResult < Scalar > {
97129 let dtype = args. return_dtype . clone ( ) ;
98130 match & self . state {
99- BoundedMaxState :: Value ( max ) => max . cast ( & dtype) ,
131+ BoundedMaxState :: Exact ( bound ) | BoundedMaxState :: Inexact ( bound ) => bound . cast ( & dtype) ,
100132 BoundedMaxState :: Empty | BoundedMaxState :: Unknown => Ok ( Scalar :: null ( dtype) ) ,
101133 }
102134 }
@@ -183,6 +215,27 @@ impl AggregateFnVTable for BoundedMax {
183215 }
184216 }
185217
218+ fn partial_can_satisfy (
219+ & self ,
220+ options : & Self :: Options ,
221+ partial : & Self :: Partial ,
222+ requested : & AggregateFnRef ,
223+ ) -> AggregateFnSatisfaction {
224+ let satisfaction = self . can_satisfy ( options, requested) ;
225+ let untruncated = matches ! (
226+ partial. state,
227+ BoundedMaxState :: Empty | BoundedMaxState :: Exact ( _)
228+ ) ;
229+ if satisfaction == AggregateFnSatisfaction :: Approximate
230+ && untruncated
231+ && requested. is :: < Max > ( )
232+ {
233+ AggregateFnSatisfaction :: Exact
234+ } else {
235+ satisfaction
236+ }
237+ }
238+
186239 fn partial_dtype ( & self , options : & Self :: Options , input_dtype : & DType ) -> Option < DType > {
187240 supported_dtype ( options, input_dtype) . map ( make_bounded_max_partial_dtype)
188241 }
@@ -226,7 +279,8 @@ impl AggregateFnVTable for BoundedMax {
226279 } else if bound. is_null ( ) {
227280 BoundedMaxState :: Empty
228281 } else {
229- BoundedMaxState :: Value ( bound)
282+ // Serialized partials don't record exactness.
283+ BoundedMaxState :: Inexact ( bound)
230284 }
231285 } ;
232286 Ok ( BoundedMaxPartial { state } )
@@ -240,7 +294,8 @@ impl AggregateFnVTable for BoundedMax {
240294 ) -> VortexResult < Self :: Partial > {
241295 match second. state {
242296 BoundedMaxState :: Empty => { }
243- BoundedMaxState :: Value ( max) => first. merge_bound ( max) ,
297+ BoundedMaxState :: Exact ( bound) => first. merge_bound ( bound, true ) ,
298+ BoundedMaxState :: Inexact ( bound) => first. merge_bound ( bound, false ) ,
244299 BoundedMaxState :: Unknown => first. unknown ( ) ,
245300 }
246301 Ok ( first)
@@ -255,10 +310,10 @@ impl AggregateFnVTable for BoundedMax {
255310 let bound_dtype = args. dtype . as_nullable ( ) ;
256311 match & partial. state {
257312 BoundedMaxState :: Empty => Ok ( Scalar :: null ( dtype) ) ,
258- BoundedMaxState :: Value ( max ) => Ok ( Scalar :: struct_ (
313+ BoundedMaxState :: Exact ( bound ) | BoundedMaxState :: Inexact ( bound ) => Ok ( Scalar :: struct_ (
259314 dtype,
260315 vec ! [
261- max . cast( & bound_dtype) ?,
316+ bound . cast( & bound_dtype) ?,
262317 Scalar :: bool ( false , Nullability :: NonNullable ) ,
263318 ] ,
264319 ) ) ,
@@ -293,7 +348,7 @@ impl AggregateFnVTable for BoundedMax {
293348 return Ok ( ( ) ) ;
294349 } ;
295350 match truncate_max ( result. max , args. options . max_bytes . get ( ) ) ? {
296- Some ( bound) => partial. merge_bound ( bound) ,
351+ Some ( ( bound, truncated ) ) => partial. merge_bound ( bound, !truncated ) ,
297352 None => partial. unknown ( ) ,
298353 }
299354 Ok ( ( ) )
@@ -322,22 +377,21 @@ fn supported_dtype<'a>(_options: &BoundedMaxOptions, input_dtype: &'a DType) ->
322377 . map ( |_| input_dtype)
323378}
324379
325- fn truncate_max ( value : Scalar , max_bytes : usize ) -> VortexResult < Option < Scalar > > {
380+ /// Returns the upper bound and whether it was truncated, or `None` if no bound fits `max_bytes`.
381+ fn truncate_max ( value : Scalar , max_bytes : usize ) -> VortexResult < Option < ( Scalar , bool ) > > {
326382 let nullability = value. dtype ( ) . nullability ( ) ;
327383 match value. dtype ( ) {
328- DType :: Utf8 ( _) => {
329- Ok (
330- upper_bound ( BufferString :: from_scalar ( value) ?, max_bytes, nullability)
331- . map ( |( bound, _) | bound) ,
332- )
333- }
334- DType :: Binary ( _) => {
335- Ok (
336- upper_bound ( ByteBuffer :: from_scalar ( value) ?, max_bytes, nullability)
337- . map ( |( bound, _) | bound) ,
338- )
339- }
340- _ => Ok ( Some ( value) ) ,
384+ DType :: Utf8 ( _) => Ok ( upper_bound (
385+ BufferString :: from_scalar ( value) ?,
386+ max_bytes,
387+ nullability,
388+ ) ) ,
389+ DType :: Binary ( _) => Ok ( upper_bound (
390+ ByteBuffer :: from_scalar ( value) ?,
391+ max_bytes,
392+ nullability,
393+ ) ) ,
394+ _ => Ok ( Some ( ( value, false ) ) ) ,
341395 }
342396}
343397
@@ -584,4 +638,67 @@ mod tests {
584638 assert_eq ! ( roundtrip, options) ;
585639 Ok ( ( ) )
586640 }
641+
642+ #[ test]
643+ fn bounded_max_exactly_satisfies_max_only_when_untruncated ( ) -> VortexResult < ( ) > {
644+ let mut ctx = array_session ( ) . create_execution_ctx ( ) ;
645+ let requested = Max . bind ( NumericalAggregateOpts :: skip_nans ( ) ) ;
646+ let new_acc = || {
647+ Accumulator :: try_new (
648+ BoundedMax ,
649+ BoundedMaxOptions {
650+ max_bytes : max_bytes ( 4 ) ,
651+ } ,
652+ VarBinViewArray :: from_iter_str ( [ "x" ] ) . dtype ( ) . clone ( ) ,
653+ )
654+ } ;
655+
656+ // Every value fits the bound, so the bound is the true extremum.
657+ let mut acc = new_acc ( ) ?;
658+ acc. accumulate (
659+ & VarBinViewArray :: from_iter_str ( [ "b" , "abc" ] ) . into_array ( ) ,
660+ & mut ctx,
661+ ) ?;
662+ assert_eq ! ( acc. can_satisfy( & requested) , AggregateFnSatisfaction :: Exact ) ;
663+
664+ // A truncated value that isn't the extremum doesn't affect exactness.
665+ acc. accumulate (
666+ & VarBinViewArray :: from_iter_str ( [ "aaaaa" ] ) . into_array ( ) ,
667+ & mut ctx,
668+ ) ?;
669+ assert_eq ! ( acc. can_satisfy( & requested) , AggregateFnSatisfaction :: Exact ) ;
670+
671+ // A truncated extremum makes the bound approximate.
672+ acc. accumulate (
673+ & VarBinViewArray :: from_iter_str ( [ "bbbbb" ] ) . into_array ( ) ,
674+ & mut ctx,
675+ ) ?;
676+ assert_eq ! (
677+ acc. can_satisfy( & requested) ,
678+ AggregateFnSatisfaction :: Approximate
679+ ) ;
680+
681+ // Exactness isn't serialized, so a winning partial combined from its scalar form is
682+ // approximate even though it was exact where it was computed.
683+ let mut source = new_acc ( ) ?;
684+ source. accumulate (
685+ & VarBinViewArray :: from_iter_str ( [ "b" ] ) . into_array ( ) ,
686+ & mut ctx,
687+ ) ?;
688+ assert_eq ! (
689+ source. can_satisfy( & requested) ,
690+ AggregateFnSatisfaction :: Exact
691+ ) ;
692+ let mut acc = new_acc ( ) ?;
693+ acc. accumulate (
694+ & VarBinViewArray :: from_iter_str ( [ "a" ] ) . into_array ( ) ,
695+ & mut ctx,
696+ ) ?;
697+ acc. combine_partials ( source. partial_scalar ( ) ?) ?;
698+ assert_eq ! (
699+ acc. can_satisfy( & requested) ,
700+ AggregateFnSatisfaction :: Approximate
701+ ) ;
702+ Ok ( ( ) )
703+ }
587704}
0 commit comments