@@ -131,26 +131,43 @@ impl ScalarUDFImpl for SparkArraysOverlap {
131131 Ok ( ColumnarValue :: Array ( result) )
132132 }
133133 ( left, right) => {
134- // Handle scalar inputs by converting to arrays
134+ // At least one side is a scalar. It stays a one-row list that every output row
135+ // reads, rather than being repeated to the batch length: repeating a long list
136+ // could overflow the list's offsets. Only two scalars produce a scalar result.
137+ let left_scalar = matches ! ( left, ColumnarValue :: Scalar ( _) ) ;
138+ let right_scalar = matches ! ( right, ColumnarValue :: Scalar ( _) ) ;
139+ let both_scalar = left_scalar && right_scalar;
140+ let rows = RowMapping {
141+ len : if both_scalar { 1 } else { args. number_rows } ,
142+ left_scalar,
143+ right_scalar,
144+ } ;
135145 let left_arr = left. to_array ( 1 ) ?;
136146 let right_arr = right. to_array ( 1 ) ?;
137147 let result = match ( left_arr. data_type ( ) , right_arr. data_type ( ) ) {
138- ( DataType :: List ( _) , DataType :: List ( _) ) => arrays_overlap_list :: < i32 > (
148+ ( DataType :: List ( _) , DataType :: List ( _) ) => arrays_overlap_rows :: < i32 > (
139149 left_arr. as_any ( ) . downcast_ref ( ) . unwrap ( ) ,
140150 right_arr. as_any ( ) . downcast_ref ( ) . unwrap ( ) ,
151+ rows,
141152 ) ?,
142- ( DataType :: LargeList ( _) , DataType :: LargeList ( _) ) => arrays_overlap_list :: < i64 > (
153+ ( DataType :: LargeList ( _) , DataType :: LargeList ( _) ) => arrays_overlap_rows :: < i64 > (
143154 left_arr. as_any ( ) . downcast_ref ( ) . unwrap ( ) ,
144155 right_arr. as_any ( ) . downcast_ref ( ) . unwrap ( ) ,
156+ rows,
145157 ) ?,
146158 ( l, r) => {
147159 return exec_err ! (
148160 "spark_arrays_overlap does not support types '{l}' and '{r}'"
149161 )
150162 }
151163 } ;
152- let scalar = ScalarValue :: try_from_array ( & result, 0 ) ?;
153- Ok ( ColumnarValue :: Scalar ( scalar) )
164+ if both_scalar {
165+ Ok ( ColumnarValue :: Scalar ( ScalarValue :: try_from_array (
166+ & result, 0 ,
167+ ) ?) )
168+ } else {
169+ Ok ( ColumnarValue :: Array ( result) )
170+ }
154171 }
155172 }
156173 }
@@ -166,19 +183,63 @@ impl ScalarUDFImpl for SparkArraysOverlap {
166183fn arrays_overlap_list < OffsetSize : OffsetSizeTrait > (
167184 left : & GenericListArray < OffsetSize > ,
168185 right : & GenericListArray < OffsetSize > ,
186+ ) -> Result < ArrayRef > {
187+ arrays_overlap_rows ( left, right, RowMapping :: aligned ( left. len ( ) ) )
188+ }
189+
190+ /// Which input row each output row reads. A scalar input is a one-row list that every output row
191+ /// reads; otherwise output row `i` reads input row `i`.
192+ #[ derive( Clone , Copy ) ]
193+ struct RowMapping {
194+ len : usize ,
195+ left_scalar : bool ,
196+ right_scalar : bool ,
197+ }
198+
199+ impl RowMapping {
200+ fn aligned ( len : usize ) -> Self {
201+ Self {
202+ len,
203+ left_scalar : false ,
204+ right_scalar : false ,
205+ }
206+ }
207+
208+ fn left ( & self , i : usize ) -> usize {
209+ if self . left_scalar {
210+ 0
211+ } else {
212+ i
213+ }
214+ }
215+
216+ fn right ( & self , i : usize ) -> usize {
217+ if self . right_scalar {
218+ 0
219+ } else {
220+ i
221+ }
222+ }
223+ }
224+
225+ /// `arrays_overlap_list` over `rows.len` output rows, reading the input rows `rows` maps them to.
226+ fn arrays_overlap_rows < OffsetSize : OffsetSizeTrait > (
227+ left : & GenericListArray < OffsetSize > ,
228+ right : & GenericListArray < OffsetSize > ,
229+ rows : RowMapping ,
169230) -> Result < ArrayRef > {
170231 let left_values = left. values ( ) ;
171232 let right_values = right. values ( ) ;
172233
173234 if left_values. data_type ( ) != right_values. data_type ( ) {
174- return arrays_overlap_list_generic ( left, right) ;
235+ return arrays_overlap_list_generic ( left, right, rows ) ;
175236 }
176237
177238 // Fast paths for flat element types: probe the flat value buffers directly instead of
178239 // slicing each row and running an Arrow compare kernel once per probe element.
179240 macro_rules! flat_fast_path {
180241 ( $l: expr, $r: expr) => {
181- return Ok ( overlap_rows( left, right, flat_row_overlap( $l, $r) ) )
242+ return Ok ( overlap_rows( left, right, rows , flat_row_overlap( $l, $r) ) )
182243 } ;
183244 }
184245 macro_rules! primitive_fast_path {
@@ -223,7 +284,7 @@ fn arrays_overlap_list<OffsetSize: OffsetSizeTrait>(
223284 left_values. as_string:: <i64 >( ) ,
224285 right_values. as_string:: <i64 >( )
225286 ) ,
226- _ => arrays_overlap_list_generic ( left, right) ,
287+ _ => arrays_overlap_list_generic ( left, right, rows ) ,
227288 }
228289}
229290
@@ -233,9 +294,10 @@ fn arrays_overlap_list<OffsetSize: OffsetSizeTrait>(
233294fn overlap_rows < OffsetSize : OffsetSizeTrait > (
234295 left : & GenericListArray < OffsetSize > ,
235296 right : & GenericListArray < OffsetSize > ,
297+ rows : RowMapping ,
236298 mut row_overlap : impl FnMut ( Range < usize > , Range < usize > ) -> bool ,
237299) -> ArrayRef {
238- let len = left . len ( ) ;
300+ let len = rows . len ;
239301 let left_offsets = left. offsets ( ) ;
240302 let right_offsets = right. offsets ( ) ;
241303 let left_element_nulls = left. values ( ) . nulls ( ) ;
@@ -244,13 +306,14 @@ fn overlap_rows<OffsetSize: OffsetSizeTrait>(
244306 let mut builder = BooleanArray :: builder ( len) ;
245307
246308 for i in 0 ..len {
247- if left. is_null ( i) || right. is_null ( i) {
309+ let ( li, ri) = ( rows. left ( i) , rows. right ( i) ) ;
310+ if left. is_null ( li) || right. is_null ( ri) {
248311 builder. append_null ( ) ;
249312 continue ;
250313 }
251314
252- let left_range = left_offsets[ i ] . as_usize ( ) ..left_offsets[ i + 1 ] . as_usize ( ) ;
253- let right_range = right_offsets[ i ] . as_usize ( ) ..right_offsets[ i + 1 ] . as_usize ( ) ;
315+ let left_range = left_offsets[ li ] . as_usize ( ) ..left_offsets[ li + 1 ] . as_usize ( ) ;
316+ let right_range = right_offsets[ ri ] . as_usize ( ) ..right_offsets[ ri + 1 ] . as_usize ( ) ;
254317
255318 if left_range. is_empty ( ) || right_range. is_empty ( ) {
256319 builder. append_value ( false ) ;
@@ -413,6 +476,7 @@ fn normalize_list_element_floats<OffsetSize: OffsetSizeTrait>(
413476fn arrays_overlap_list_generic < OffsetSize : OffsetSizeTrait > (
414477 left : & GenericListArray < OffsetSize > ,
415478 right : & GenericListArray < OffsetSize > ,
479+ rows : RowMapping ,
416480) -> Result < ArrayRef > {
417481 let left_owned =
418482 has_float_leaf ( left. values ( ) . data_type ( ) ) . then ( || normalize_list_element_floats ( left) ) ;
@@ -421,17 +485,18 @@ fn arrays_overlap_list_generic<OffsetSize: OffsetSizeTrait>(
421485 has_float_leaf ( right. values ( ) . data_type ( ) ) . then ( || normalize_list_element_floats ( right) ) ;
422486 let right: & GenericListArray < OffsetSize > = right_owned. as_ref ( ) . unwrap_or ( right) ;
423487
424- let len = left . len ( ) ;
488+ let len = rows . len ;
425489 let mut builder = BooleanArray :: builder ( len) ;
426490
427491 for i in 0 ..len {
428- if left. is_null ( i) || right. is_null ( i) {
492+ let ( li, ri) = ( rows. left ( i) , rows. right ( i) ) ;
493+ if left. is_null ( li) || right. is_null ( ri) {
429494 builder. append_null ( ) ;
430495 continue ;
431496 }
432497
433- let left_values = left. value ( i ) ;
434- let right_values = right. value ( i ) ;
498+ let left_values = left. value ( li ) ;
499+ let right_values = right. value ( ri ) ;
435500
436501 if left_values. is_empty ( ) || right_values. is_empty ( ) {
437502 builder. append_value ( false ) ;
@@ -538,7 +603,7 @@ fn needs_comparator(dt: &DataType) -> bool {
538603mod tests {
539604 use super :: * ;
540605 use arrow:: array:: {
541- Float64Array , Float64Builder , Int32Array , Int32Builder , ListArray , ListBuilder ,
606+ Float64Array , Float64Builder , Int32Array , Int32Builder , ListArray , ListBuilder , NullArray ,
542607 StructArray , StructBuilder ,
543608 } ;
544609 use arrow:: buffer:: { NullBuffer , OffsetBuffer } ;
@@ -1148,4 +1213,119 @@ mod tests {
11481213 assert ! ( result. is_null( 0 ) ) ;
11491214 Ok ( ( ) )
11501215 }
1216+
1217+ fn invoke ( left : ColumnarValue , right : ColumnarValue , rows : usize ) -> Result < ColumnarValue > {
1218+ SparkArraysOverlap :: new ( ) . invoke_with_args ( ScalarFunctionArgs {
1219+ args : vec ! [ left, right] ,
1220+ arg_fields : vec ! [ ] ,
1221+ number_rows : rows,
1222+ return_field : Arc :: new ( Field :: new ( "result" , DataType :: Boolean , true ) ) ,
1223+ config_options : Arc :: new ( datafusion:: config:: ConfigOptions :: default ( ) ) ,
1224+ } )
1225+ }
1226+
1227+ fn scalar_list ( list : ListArray ) -> ColumnarValue {
1228+ ColumnarValue :: Scalar ( ScalarValue :: List ( Arc :: new ( list) ) )
1229+ }
1230+
1231+ fn booleans ( result : ColumnarValue ) -> Vec < Option < bool > > {
1232+ match result {
1233+ ColumnarValue :: Array ( array) => array
1234+ . as_any ( )
1235+ . downcast_ref :: < BooleanArray > ( )
1236+ . unwrap ( )
1237+ . iter ( )
1238+ . collect ( ) ,
1239+ ColumnarValue :: Scalar ( _) => panic ! ( "expected an array result" ) ,
1240+ }
1241+ }
1242+
1243+ /// A constant array beside an array column is compared with every row, on either side.
1244+ #[ test]
1245+ fn scalar_beside_column_compares_every_row ( ) -> Result < ( ) > {
1246+ // [0], [1], [2], [NULL] against the constant [1]
1247+ let column = make_list_array (
1248+ & Int32Array :: from ( vec ! [ Some ( 0 ) , Some ( 1 ) , Some ( 2 ) , None ] ) ,
1249+ & [ 0 , 1 , 2 , 3 , 4 ] ,
1250+ None ,
1251+ ) ;
1252+ let constant = make_list_array ( & Int32Array :: from ( vec ! [ 1 ] ) , & [ 0 , 1 ] , None ) ;
1253+ let expected = vec ! [ Some ( false ) , Some ( true ) , Some ( false ) , None ] ;
1254+
1255+ let column_first = invoke (
1256+ ColumnarValue :: Array ( Arc :: new ( column. clone ( ) ) ) ,
1257+ scalar_list ( constant. clone ( ) ) ,
1258+ 4 ,
1259+ ) ?;
1260+ assert_eq ! ( booleans( column_first) , expected) ;
1261+ let constant_first = invoke (
1262+ scalar_list ( constant) ,
1263+ ColumnarValue :: Array ( Arc :: new ( column) ) ,
1264+ 4 ,
1265+ ) ?;
1266+ assert_eq ! ( booleans( constant_first) , expected) ;
1267+ Ok ( ( ) )
1268+ }
1269+
1270+ /// The same for the nested-element path.
1271+ #[ test]
1272+ fn scalar_beside_column_compares_every_row_nested ( ) -> Result < ( ) > {
1273+ let rows = [
1274+ make_struct_list ( vec ! [ Some ( ( Some ( 1 ) , Some ( 2 ) ) ) ] ) ,
1275+ make_struct_list ( vec ! [ Some ( ( Some ( 3 ) , Some ( 4 ) ) ) ] ) ,
1276+ ] ;
1277+ let column = arrow:: compute:: concat ( & [ & rows[ 0 ] , & rows[ 1 ] ] ) ?;
1278+ let constant = make_struct_list ( vec ! [ Some ( ( Some ( 3 ) , Some ( 4 ) ) ) ] ) ;
1279+ let expected = vec ! [ Some ( false ) , Some ( true ) ] ;
1280+
1281+ let constant_first = invoke (
1282+ scalar_list ( constant. clone ( ) ) ,
1283+ ColumnarValue :: Array ( Arc :: clone ( & column) ) ,
1284+ 2 ,
1285+ ) ?;
1286+ assert_eq ! ( booleans( constant_first) , expected) ;
1287+ let column_first = invoke ( ColumnarValue :: Array ( column) , scalar_list ( constant) , 2 ) ?;
1288+ assert_eq ! ( booleans( column_first) , expected) ;
1289+ Ok ( ( ) )
1290+ }
1291+
1292+ /// A long constant list is read in place for every row rather than repeated to the batch
1293+ /// length: 262,144 elements repeated over 8,192 rows would overflow a list's 32-bit offsets.
1294+ #[ test]
1295+ fn long_scalar_list_is_not_repeated ( ) -> Result < ( ) > {
1296+ let field = Arc :: new ( Field :: new ( "item" , DataType :: Null , true ) ) ;
1297+ let constant = ListArray :: new (
1298+ Arc :: clone ( & field) ,
1299+ OffsetBuffer :: new ( vec ! [ 0 , 262_144 ] . into ( ) ) ,
1300+ Arc :: new ( NullArray :: new ( 262_144 ) ) ,
1301+ None ,
1302+ ) ;
1303+ let rows = 8_192 ;
1304+ let column = ListArray :: new (
1305+ field,
1306+ OffsetBuffer :: new ( vec ! [ 0 ; rows + 1 ] . into ( ) ) ,
1307+ Arc :: new ( NullArray :: new ( 0 ) ) ,
1308+ None ,
1309+ ) ;
1310+
1311+ let result = invoke (
1312+ scalar_list ( constant) ,
1313+ ColumnarValue :: Array ( Arc :: new ( column) ) ,
1314+ rows,
1315+ ) ?;
1316+ assert_eq ! ( booleans( result) , vec![ Some ( false ) ; rows] ) ;
1317+ Ok ( ( ) )
1318+ }
1319+
1320+ /// Two constants still produce a constant.
1321+ #[ test]
1322+ fn two_scalars_return_a_scalar ( ) -> Result < ( ) > {
1323+ let one = make_list_array ( & Int32Array :: from ( vec ! [ 1 ] ) , & [ 0 , 1 ] , None ) ;
1324+ let result = invoke ( scalar_list ( one. clone ( ) ) , scalar_list ( one) , 4 ) ?;
1325+ assert ! ( matches!(
1326+ result,
1327+ ColumnarValue :: Scalar ( ScalarValue :: Boolean ( Some ( true ) ) )
1328+ ) ) ;
1329+ Ok ( ( ) )
1330+ }
11511331}
0 commit comments