@@ -120,6 +120,23 @@ impl BinaryExpr {
120120 & self . op
121121 }
122122
123+ /// Mathematical intervals do not cover values produced by wrapping arithmetic.
124+ fn integer_arithmetic_may_wrap (
125+ & self ,
126+ left : & Interval ,
127+ right : & Interval ,
128+ result : & Interval ,
129+ ) -> bool {
130+ !self . fail_on_overflow
131+ && result. data_type ( ) . is_integer ( )
132+ && matches ! (
133+ self . op,
134+ Operator :: Plus | Operator :: Minus | Operator :: Multiply
135+ )
136+ && ( result. is_unbounded ( )
137+ || unsigned_subtraction_may_underflow ( self . op , left, right, result) )
138+ }
139+
123140 /// Wrapping on overflow breaks monotonicity (e.g. the sum of two
124141 /// ascending `UInt8` columns can wrap back to small values), so the
125142 /// derived ordering is kept only when overflow is impossible. `time ±
@@ -692,7 +709,12 @@ impl PhysicalExpr for BinaryExpr {
692709 let left_interval = children[ 0 ] ;
693710 let right_interval = children[ 1 ] ;
694711 // Calculate current node's interval:
695- apply_operator ( & self . op , left_interval, right_interval)
712+ let result = apply_operator ( & self . op , left_interval, right_interval) ?;
713+ if self . integer_arithmetic_may_wrap ( left_interval, right_interval, & result) {
714+ Interval :: make_unbounded ( & result. data_type ( ) )
715+ } else {
716+ Ok ( result)
717+ }
696718 }
697719
698720 fn propagate_constraints (
@@ -704,6 +726,36 @@ impl PhysicalExpr for BinaryExpr {
704726 let left_interval = children[ 0 ] ;
705727 let right_interval = children[ 1 ] ;
706728
729+ if left_interval. data_type ( ) . is_integer ( )
730+ && right_interval. data_type ( ) . is_integer ( )
731+ && matches ! (
732+ self . op,
733+ Operator :: Plus | Operator :: Minus | Operator :: Multiply | Operator :: Divide
734+ )
735+ {
736+ // Integer division truncates: a / 2 = 1 permits both 2 and 3.
737+ // Wrapping arithmetic is likewise not invertible over mathematical
738+ // intervals. Keep the input domains rather than exclude valid rows.
739+ let contains_zero = |range : & Interval | -> Result < bool > {
740+ range. contains_value ( ScalarValue :: new_zero ( & range. data_type ( ) ) ?)
741+ } ;
742+ // If an operand can be zero, a zero product does not constrain
743+ // the other operand. Dividing the parent interval loses that case.
744+ let zero_product = self . op == Operator :: Multiply
745+ && contains_zero ( interval) ?
746+ && ( contains_zero ( left_interval) ? || contains_zero ( right_interval) ?) ;
747+ if self . op == Operator :: Divide
748+ || zero_product
749+ || self . integer_arithmetic_may_wrap (
750+ left_interval,
751+ right_interval,
752+ & apply_operator ( & self . op , left_interval, right_interval) ?,
753+ )
754+ {
755+ return Ok ( Some ( vec ! [ ] ) ) ;
756+ }
757+ }
758+
707759 if self . op . eq ( & Operator :: And ) {
708760 if interval. eq ( & Interval :: TRUE ) {
709761 // A certainly true logical conjunction can only derive from possibly
@@ -824,7 +876,7 @@ impl PhysicalExpr for BinaryExpr {
824876 let ( r_order, r_range) = ( children[ 1 ] . sort_properties , & children[ 1 ] . range ) ;
825877 match self . op ( ) {
826878 Operator :: Plus => {
827- let range = l_range . add ( r_range) ?;
879+ let range = self . evaluate_bounds ( & [ l_range , r_range] ) ?;
828880 Ok ( ExprProperties {
829881 sort_properties : self . arithmetic_sort_properties (
830882 l_order. add ( & r_order) ,
@@ -838,7 +890,7 @@ impl PhysicalExpr for BinaryExpr {
838890 } )
839891 }
840892 Operator :: Minus => {
841- let range = l_range . sub ( r_range) ?;
893+ let range = self . evaluate_bounds ( & [ l_range , r_range] ) ?;
842894 Ok ( ExprProperties {
843895 sort_properties : self . arithmetic_sort_properties (
844896 l_order. sub ( & r_order) ,
@@ -6115,6 +6167,246 @@ mod tests {
61156167 }
61166168 }
61176169
6170+ #[ test]
6171+ fn test_integer_interval_propagation_covers_runtime_values ( ) {
6172+ // Enumerate small domains and both ends of Int8, including zero divisors,
6173+ // truncation, signed overflow and checked arithmetic. Every successful
6174+ // runtime evaluation must remain possible after interval propagation.
6175+ let batch = RecordBatch :: new_empty ( Arc :: new ( Schema :: empty ( ) ) ) ;
6176+ let domains = [
6177+ ( -3i8 , 3i8 ) ,
6178+ ( 0 , 1 ) ,
6179+ ( 1 , 3 ) ,
6180+ ( -3 , -1 ) ,
6181+ ( -128 , -127 ) ,
6182+ ( 126 , 127 ) ,
6183+ ] ;
6184+ for checked in [ false , true ] {
6185+ for op in [
6186+ Operator :: Plus ,
6187+ Operator :: Minus ,
6188+ Operator :: Multiply ,
6189+ Operator :: Divide ,
6190+ ] {
6191+ let expr = BinaryExpr :: new ( lit ( 0i8 ) , op, lit ( 0i8 ) )
6192+ . with_fail_on_overflow ( checked) ;
6193+ for ( lo, hi) in domains {
6194+ for ( rlo, rhi) in
6195+ domains. into_iter ( ) . chain ( [ ( -1 , -1 ) , ( 0 , 0 ) , ( 2 , 2 ) ] )
6196+ {
6197+ let left = Interval :: make ( Some ( lo) , Some ( hi) ) . unwrap ( ) ;
6198+ let right = Interval :: make ( Some ( rlo) , Some ( rhi) ) . unwrap ( ) ;
6199+ let bounds = expr. evaluate_bounds ( & [ & left, & right] ) . unwrap ( ) ;
6200+ if matches ! ( op, Operator :: Plus | Operator :: Minus ) {
6201+ let children = [ left. clone ( ) , right. clone ( ) ] . map ( |range| {
6202+ ExprProperties {
6203+ range,
6204+ ..ExprProperties :: new_unknown ( )
6205+ }
6206+ } ) ;
6207+ assert_eq ! (
6208+ expr. get_properties( & children) . unwrap( ) . range,
6209+ bounds
6210+ ) ;
6211+ }
6212+ for a in lo..=hi {
6213+ for b in rlo..=rhi {
6214+ // Use the execution kernel as the oracle rather than
6215+ // duplicating its checked and wrapping arithmetic.
6216+ let runtime = BinaryExpr :: new ( lit ( a) , op, lit ( b) )
6217+ . with_fail_on_overflow ( checked) ;
6218+ let result = match runtime. evaluate ( & batch) {
6219+ Ok ( value) => value. into_array ( 1 ) . unwrap ( ) ,
6220+ Err ( error) => {
6221+ assert ! (
6222+ checked || op == Operator :: Divide ,
6223+ "wrapping {a} {op} {b} failed: {error}"
6224+ ) ;
6225+ continue ;
6226+ }
6227+ } ;
6228+ let result = result. as_primitive :: < Int8Type > ( ) . value ( 0 ) ;
6229+ let result =
6230+ Interval :: make ( Some ( result) , Some ( result) ) . unwrap ( ) ;
6231+ assert_eq ! (
6232+ bounds. contains( & result) . unwrap( ) ,
6233+ Interval :: TRUE ,
6234+ "forward {a} {op} {b}, checked={checked}, bounds={bounds:?}"
6235+ ) ;
6236+ let propagated = expr
6237+ . propagate_constraints ( & result, & [ & left, & right] )
6238+ . unwrap ( ) ;
6239+ let propagated = propagated
6240+ . expect ( "successful runtime result must be feasible" ) ;
6241+ if !propagated. is_empty ( ) {
6242+ assert_eq ! (
6243+ propagated[ 0 ]
6244+ . contains(
6245+ Interval :: make( Some ( a) , Some ( a) ) . unwrap( )
6246+ )
6247+ . unwrap( ) ,
6248+ Interval :: TRUE ,
6249+ "left input excluded for {a} {op} {b}, checked={checked}: {propagated:?}"
6250+ ) ;
6251+ assert_eq ! (
6252+ propagated[ 1 ]
6253+ . contains(
6254+ Interval :: make( Some ( b) , Some ( b) ) . unwrap( )
6255+ )
6256+ . unwrap( ) ,
6257+ Interval :: TRUE ,
6258+ "right input excluded for {a} {op} {b}, checked={checked}: {propagated:?}"
6259+ ) ;
6260+ }
6261+ }
6262+ }
6263+ }
6264+ }
6265+ }
6266+ }
6267+ }
6268+
6269+ #[ test]
6270+ fn test_integer_interval_error_propagation ( ) {
6271+ // Compare error messages without backtraces, which differ by call path.
6272+ let integer = Interval :: make ( Some ( 1i32 ) , Some ( 2i32 ) ) . unwrap ( ) ;
6273+ let boolean = Interval :: TRUE ;
6274+ for op in [ Operator :: Plus , Operator :: Minus ] {
6275+ let expr = BinaryExpr :: new ( lit ( 1i32 ) , op, lit ( true ) ) ;
6276+ let expected = apply_operator ( & op, & integer, & boolean)
6277+ . unwrap_err ( )
6278+ . strip_backtrace ( ) ;
6279+ assert_eq ! (
6280+ expr. evaluate_bounds( & [ & integer, & boolean] )
6281+ . unwrap_err( )
6282+ . strip_backtrace( ) ,
6283+ expected
6284+ ) ;
6285+ let children =
6286+ [ integer. clone ( ) , boolean. clone ( ) ] . map ( |range| ExprProperties {
6287+ range,
6288+ ..ExprProperties :: new_unknown ( )
6289+ } ) ;
6290+ assert_eq ! (
6291+ expr. get_properties( & children)
6292+ . unwrap_err( )
6293+ . strip_backtrace( ) ,
6294+ expected
6295+ ) ;
6296+ }
6297+
6298+ // A nonnumeric parent cannot describe an integer product. Preserve
6299+ // the error from constructing zero for its unsupported type.
6300+ let parent = Interval :: make_unbounded ( & DataType :: Utf8 ) . unwrap ( ) ;
6301+ let expr = BinaryExpr :: new ( lit ( 1i32 ) , Operator :: Multiply , lit ( 2i32 ) ) ;
6302+ assert_eq ! (
6303+ expr. propagate_constraints( & parent, & [ & integer, & integer] )
6304+ . unwrap_err( )
6305+ . strip_backtrace( ) ,
6306+ ScalarValue :: new_zero( & DataType :: Utf8 )
6307+ . unwrap_err( )
6308+ . strip_backtrace( )
6309+ ) ;
6310+ }
6311+
6312+ #[ test]
6313+ fn test_unsigned_subtraction_interval_underflow ( ) {
6314+ let expr = BinaryExpr :: new ( lit ( 0u8 ) , Operator :: Minus , lit ( 1u8 ) ) ;
6315+ let left = Interval :: make ( Some ( 0u8 ) , Some ( 2u8 ) ) . unwrap ( ) ;
6316+ let right = Interval :: make ( Some ( 1u8 ) , Some ( 1u8 ) ) . unwrap ( ) ;
6317+ let wrapped = Interval :: make ( Some ( 255u8 ) , Some ( 255u8 ) ) . unwrap ( ) ;
6318+ assert_eq ! (
6319+ expr. evaluate_bounds( & [ & left, & right] )
6320+ . unwrap( )
6321+ . contains( & wrapped)
6322+ . unwrap( ) ,
6323+ Interval :: TRUE
6324+ ) ;
6325+ assert_eq ! (
6326+ expr. propagate_constraints( & wrapped, & [ & left, & right] )
6327+ . unwrap( ) ,
6328+ Some ( vec![ ] )
6329+ ) ;
6330+ }
6331+
6332+ #[ test]
6333+ fn test_nested_wrapping_arithmetic_properties ( ) {
6334+ let difference = Arc :: new ( BinaryExpr :: new ( lit ( 0u8 ) , Operator :: Minus , lit ( 1u8 ) ) ) ;
6335+ let singleton = |value : u8 | ExprProperties {
6336+ sort_properties : SortProperties :: Singleton ,
6337+ range : Interval :: make ( Some ( value) , Some ( value) ) . unwrap ( ) ,
6338+ ..ExprProperties :: new_unknown ( )
6339+ } ;
6340+ let difference_props = difference
6341+ . get_properties ( & [ singleton ( 0 ) , singleton ( 1 ) ] )
6342+ . unwrap ( ) ;
6343+ assert_eq ! ( difference_props. sort_properties, SortProperties :: Singleton ) ;
6344+ assert ! (
6345+ difference_props
6346+ . range
6347+ . contains_value( ScalarValue :: UInt8 ( Some ( 255 ) ) )
6348+ . unwrap( )
6349+ ) ;
6350+
6351+ // The inner constant wraps to 255. An incorrect range of [0, 0]
6352+ // would let the outer addition claim to preserve ascending order.
6353+ let expr =
6354+ BinaryExpr :: new ( Arc :: new ( Column :: new ( "a" , 0 ) ) , Operator :: Plus , difference) ;
6355+ let properties = expr
6356+ . get_properties ( & [
6357+ ExprProperties {
6358+ sort_properties : SortProperties :: Ordered ( SortOptions :: default ( ) ) ,
6359+ range : Interval :: make ( Some ( 0u8 ) , Some ( 1u8 ) ) . unwrap ( ) ,
6360+ ..ExprProperties :: new_unknown ( )
6361+ } ,
6362+ difference_props,
6363+ ] )
6364+ . unwrap ( ) ;
6365+ let batch = RecordBatch :: try_new (
6366+ Arc :: new ( Schema :: new ( vec ! [ Field :: new( "a" , DataType :: UInt8 , false ) ] ) ) ,
6367+ vec ! [ Arc :: new( UInt8Array :: from( vec![ 0 , 1 ] ) ) ] ,
6368+ )
6369+ . unwrap ( ) ;
6370+ let actual = expr. evaluate ( & batch) . unwrap ( ) . into_array ( 2 ) . unwrap ( ) ;
6371+ assert_eq ! ( actual. as_ref( ) , & UInt8Array :: from( vec![ 255 , 0 ] ) ) ;
6372+ assert_eq ! ( properties. sort_properties, SortProperties :: Unordered ) ;
6373+ for value in [ 0u8 , 255 ] {
6374+ assert ! (
6375+ properties
6376+ . range
6377+ . contains_value( ScalarValue :: UInt8 ( Some ( value) ) )
6378+ . unwrap( )
6379+ ) ;
6380+ }
6381+ }
6382+
6383+ #[ test]
6384+ fn test_integer_comparison_still_propagates ( ) {
6385+ // Integer comparisons must bypass the arithmetic overflow guard and
6386+ // still narrow their inputs: a = 5 restricts a in [0, 10] to [5, 5].
6387+ let expr = BinaryExpr :: new ( lit ( 0i32 ) , Operator :: Eq , lit ( 5i32 ) ) ;
6388+ let left = Interval :: make ( Some ( 0i32 ) , Some ( 10i32 ) ) . unwrap ( ) ;
6389+ let right = Interval :: make ( Some ( 5i32 ) , Some ( 5i32 ) ) . unwrap ( ) ;
6390+ assert_eq ! (
6391+ expr. propagate_constraints( & Interval :: TRUE , & [ & left, & right] )
6392+ . unwrap( ) ,
6393+ Some ( vec![ right. clone( ) , right] )
6394+ ) ;
6395+ }
6396+
6397+ #[ test]
6398+ fn test_safe_integer_multiplication_still_propagates ( ) {
6399+ let expr = BinaryExpr :: new ( lit ( 0i32 ) , Operator :: Multiply , lit ( 2i32 ) ) ;
6400+ let left = Interval :: make ( Some ( 0i32 ) , Some ( 10i32 ) ) . unwrap ( ) ;
6401+ let right = Interval :: make ( Some ( 2i32 ) , Some ( 2i32 ) ) . unwrap ( ) ;
6402+ let parent = Interval :: make ( Some ( 4i32 ) , Some ( 4i32 ) ) . unwrap ( ) ;
6403+ assert_eq ! (
6404+ expr. propagate_constraints( & parent, & [ & left, & right] )
6405+ . unwrap( ) ,
6406+ Some ( vec![ Interval :: make( Some ( 2i32 ) , Some ( 2i32 ) ) . unwrap( ) , right] )
6407+ ) ;
6408+ }
6409+
61186410 #[ test]
61196411 fn test_evaluate_bounds_int32 ( ) {
61206412 let schema = Schema :: new ( vec ! [
0 commit comments