@@ -30,13 +30,16 @@ use arrow::buffer::{NullBuffer, OffsetBuffer};
3030use arrow:: compute:: { cast, concat, interleave, take} ;
3131use arrow:: datatypes:: { DataType , Field , FieldRef } ;
3232use arrow:: row:: { RowConverter , SortField } ;
33- use datafusion:: common:: { internal_datafusion_err, internal_err, Result as DFResult , ScalarValue } ;
33+ use datafusion:: common:: {
34+ internal_datafusion_err, internal_err, DataFusionError , Result as DFResult , ScalarValue ,
35+ } ;
3436use datafusion:: logical_expr:: function:: { AccumulatorArgs , StateFieldsArgs } ;
3537use datafusion:: logical_expr:: {
3638 Accumulator , AggregateUDFImpl , EmitTo , GroupsAccumulator , Signature ,
3739} ;
3840use datafusion_spark:: function:: aggregate:: collect:: { SparkCollectList , SparkCollectSet } ;
3941use std:: mem:: { size_of, take as take_field} ;
42+ use std:: ops:: Range ;
4043use std:: sync:: Arc ;
4144use twox_hash:: XxHash64 ;
4245
@@ -503,12 +506,46 @@ fn single_row_lists(
503506/// One distinct `(group, value)` pair. `start` and `len` address the value's row-encoded bytes
504507/// in [`CollectSetGroupsAccumulator::arena`], and `hash` is of those bytes alone, so it survives
505508/// the group renumbering [`CollectSetGroupsAccumulator::compact`] does.
509+ ///
510+ /// `start` is 64-bit because the arena holds every group's bytes: a large execution-memory
511+ /// budget can push it past 4 GiB while every group's own result, and the combined `List<i32>`
512+ /// element count, stay valid, since that limit counts elements rather than encoded bytes. `len`
513+ /// stays 32-bit and is range-checked on insert, which keeps the struct at three machine words.
514+ /// Field order is chosen so the wider `start` costs nothing: `size_of::<SetEntry>()` is pinned
515+ /// by [`tests::set_entry_stays_three_words`].
506516#[ derive( Debug , Clone , Copy ) ]
507517struct SetEntry {
518+ hash : u64 ,
519+ start : u64 ,
508520 group : u32 ,
509- start : u32 ,
510521 len : u32 ,
511- hash : u64 ,
522+ }
523+
524+ /// Largest row-encoded value a [`SetEntry`] can address. A single Spark value cannot approach
525+ /// this, but the conversion is checked rather than truncating.
526+ const MAX_ENTRY_LEN : usize = u32:: MAX as usize ;
527+
528+ /// Narrows an encoded value's length to the 32 bits a [`SetEntry`] stores, erroring rather than
529+ /// truncating a length whose low bits would address a shorter, wrong slice.
530+ fn checked_entry_len ( len : usize ) -> DFResult < u32 > {
531+ u32:: try_from ( len) . map_err ( |_| {
532+ DataFusionError :: Execution ( format ! (
533+ "collect_set value of {len} encoded bytes exceeds the {MAX_ENTRY_LEN} byte limit"
534+ ) )
535+ } )
536+ }
537+
538+ /// Byte range of `entry` within the arena, computed in 64-bit and widened once.
539+ ///
540+ /// Split out from [`CollectSetGroupsAccumulator::entry_bytes`] so the arithmetic can be tested at
541+ /// the 4 GiB boundary without allocating an arena that large.
542+ #[ inline]
543+ fn entry_range ( start : u64 , len : u32 ) -> Range < usize > {
544+ let start = usize:: try_from ( start) . expect ( "arena offset exceeds the address space" ) ;
545+ let end = start
546+ . checked_add ( len as usize )
547+ . expect ( "arena entry end exceeds the address space" ) ;
548+ start..end
512549}
513550
514551/// `GroupsAccumulator` for Spark's `collect_set`.
@@ -545,7 +582,8 @@ impl CollectSetGroupsAccumulator {
545582
546583 /// Records `(group, encoded)` unless the group already holds that value. `hash` is of
547584 /// `encoded` alone, so a caller that already has it (`compact`) need not recompute it.
548- fn insert ( & mut self , group : u32 , hash : u64 , encoded : & [ u8 ] ) {
585+ fn insert ( & mut self , group : u32 , hash : u64 , encoded : & [ u8 ] ) -> DFResult < ( ) > {
586+ let len = checked_entry_len ( encoded. len ( ) ) ?;
549587 let Self {
550588 arena,
551589 entries,
@@ -557,30 +595,31 @@ impl CollectSetGroupsAccumulator {
557595 let entry = & entries[ entry_idx as usize ] ;
558596 entry. group == group
559597 && entry. hash == hash
560- && & arena[ entry . start as usize .. ( entry. start + entry. len ) as usize ] == encoded
598+ && & arena[ entry_range ( entry. start , entry. len ) ] == encoded
561599 } ) else {
562- return ;
600+ return Ok ( ( ) ) ;
563601 } ;
564602 let entry_idx = entries. len ( ) as u32 ;
565603 entries. push ( SetEntry {
566- group,
567- start : arena. len ( ) as u32 ,
568- len : encoded. len ( ) as u32 ,
569604 hash,
605+ start : arena. len ( ) as u64 ,
606+ group,
607+ len,
570608 } ) ;
571609 arena. extend_from_slice ( encoded) ;
572610 index. fill ( slot, entry_idx) ;
573611 if index. is_full ( entries. len ( ) ) {
574612 index. grow ( entries. iter ( ) . map ( |e| key_hash ( e. group , e. hash ) ) ) ;
575613 }
614+ Ok ( ( ) )
576615 }
577616
578617 fn entry_bytes ( & self , entry : & SetEntry ) -> & [ u8 ] {
579- & self . arena [ entry . start as usize .. ( entry. start + entry. len ) as usize ]
618+ & self . arena [ entry_range ( entry. start , entry. len ) ]
580619 }
581620
582621 /// Drops the entries of groups `0..emit_groups` and renumbers what is left to start at 0.
583- fn compact ( & mut self , emit_groups : u32 ) {
622+ fn compact ( & mut self , emit_groups : u32 ) -> DFResult < ( ) > {
584623 let old_entries = take_field ( & mut self . entries ) ;
585624 let old_arena = take_field ( & mut self . arena ) ;
586625 self . index = RowIndex :: default ( ) ;
@@ -589,9 +628,10 @@ impl CollectSetGroupsAccumulator {
589628 if entry. group < emit_groups {
590629 continue ;
591630 }
592- let bytes = & old_arena[ entry . start as usize .. ( entry. start + entry. len ) as usize ] ;
593- self . insert ( entry. group - emit_groups, entry. hash , bytes) ;
631+ let bytes = & old_arena[ entry_range ( entry. start , entry. len ) ] ;
632+ self . insert ( entry. group - emit_groups, entry. hash , bytes) ? ;
594633 }
634+ Ok ( ( ) )
595635 }
596636
597637 fn clear ( & mut self ) {
@@ -626,7 +666,7 @@ impl GroupsAccumulator for CollectSetGroupsAccumulator {
626666 continue ;
627667 }
628668 let row = rows. row ( row_idx) ;
629- self . insert ( group_idx as u32 , value_hash ( row. as_ref ( ) ) , row. as_ref ( ) ) ;
669+ self . insert ( group_idx as u32 , value_hash ( row. as_ref ( ) ) , row. as_ref ( ) ) ? ;
630670 }
631671 Ok ( ( ) )
632672 }
@@ -653,7 +693,7 @@ impl GroupsAccumulator for CollectSetGroupsAccumulator {
653693 }
654694 for pos in offsets[ row_idx] as usize ..offsets[ row_idx + 1 ] as usize {
655695 let row = rows. row ( pos) ;
656- self . insert ( group_idx as u32 , value_hash ( row. as_ref ( ) ) , row. as_ref ( ) ) ;
696+ self . insert ( group_idx as u32 , value_hash ( row. as_ref ( ) ) , row. as_ref ( ) ) ? ;
657697 }
658698 }
659699 Ok ( ( ) )
@@ -705,7 +745,7 @@ impl GroupsAccumulator for CollectSetGroupsAccumulator {
705745
706746 match emit_to {
707747 EmitTo :: All => self . clear ( ) ,
708- EmitTo :: First ( n) => self . compact ( n as u32 ) ,
748+ EmitTo :: First ( n) => self . compact ( n as u32 ) ? ,
709749 }
710750
711751 Ok ( Arc :: new ( ListArray :: new (
@@ -1138,6 +1178,66 @@ mod tests {
11381178
11391179 /// The two UDFs forward the rest of `AggregateUDFImpl` to `datafusion_spark`, and the
11401180 /// planner and the `GroupsAccumulator` both depend on what those forwards report.
1181+ /// The arena addresses every group's bytes at once, so its offsets have to stay valid past
1182+ /// 4 GiB. The old 32-bit `start`/`len` pair wrapped there: `0xFFFF_FFFB + 8` came back as 3,
1183+ /// and the resulting slice either panicked or read another entry's bytes. Nothing about a
1184+ /// group's own result or the combined `List<i32>` element count bounds the arena, because that
1185+ /// limit counts elements rather than encoded bytes.
1186+ ///
1187+ /// Checked here on the range arithmetic rather than through a real accumulator, so the
1188+ /// boundary is covered without allocating a 4 GiB arena.
1189+ #[ test]
1190+ fn entry_range_stays_valid_past_four_gibibytes ( ) {
1191+ const FOUR_GIB : u64 = u32:: MAX as u64 + 1 ;
1192+
1193+ // Straddling the boundary: the wrapping version produced 3..3 for this pair.
1194+ assert_eq ! (
1195+ entry_range( u32 :: MAX as u64 - 4 , 8 ) ,
1196+ 4_294_967_291 ..4_294_967_299
1197+ ) ;
1198+ // Wholly above it.
1199+ assert_eq ! ( entry_range( FOUR_GIB , 8 ) , 4_294_967_296 ..4_294_967_304 ) ;
1200+ // A later start is no longer truncated back into the first 4 GiB.
1201+ assert_eq ! ( entry_range( FOUR_GIB + 16 , 0 ) . start, 4_294_967_312 ) ;
1202+ // Ordinary offsets are unaffected.
1203+ assert_eq ! ( entry_range( 0 , 0 ) , 0 ..0 ) ;
1204+ assert_eq ! ( entry_range( 24 , 8 ) , 24 ..32 ) ;
1205+ }
1206+
1207+ /// Widening `start` to 64 bits is only free because of the field order. If someone reorders
1208+ /// `SetEntry`, padding appears and every distinct value in the aggregate pays 8 more bytes,
1209+ /// which `size()` reports to the memory pool.
1210+ #[ test]
1211+ fn set_entry_stays_three_words ( ) {
1212+ assert_eq ! ( size_of:: <SetEntry >( ) , 3 * size_of:: <u64 >( ) ) ;
1213+ }
1214+
1215+ /// `len` stays 32-bit, so it is the one narrowing conversion left. Reaching it through the
1216+ /// accumulator would need a single row-encoded value over 4 GiB, so the conversion is checked
1217+ /// on its own: it must error rather than truncate a length into a shorter slice that would
1218+ /// silently return part of a value.
1219+ #[ test]
1220+ fn oversized_entry_len_is_rejected_rather_than_truncated ( ) {
1221+ assert_eq ! ( checked_entry_len( 0 ) . unwrap( ) , 0 ) ;
1222+ assert_eq ! ( checked_entry_len( 24 ) . unwrap( ) , 24 ) ;
1223+ assert_eq ! ( checked_entry_len( MAX_ENTRY_LEN ) . unwrap( ) , u32 :: MAX ) ;
1224+ let err = checked_entry_len ( MAX_ENTRY_LEN + 1 ) . unwrap_err ( ) ;
1225+ assert ! ( err. to_string( ) . contains( "exceeds" ) , "{err}" ) ;
1226+ }
1227+
1228+ /// The ordinary path still round-trips through the widened representation.
1229+ #[ test]
1230+ fn entry_bytes_round_trip_through_the_arena ( ) {
1231+ let mut acc = CollectSetGroupsAccumulator :: try_new ( DataType :: Int32 ) . unwrap ( ) ;
1232+ acc. insert ( 0 , 1 , & [ 1 , 2 , 3 ] ) . unwrap ( ) ;
1233+ acc. insert ( 1 , 2 , & [ 4 , 5 ] ) . unwrap ( ) ;
1234+ acc. insert ( 0 , 1 , & [ 1 , 2 , 3 ] ) . unwrap ( ) ; // duplicate, not stored again
1235+ assert_eq ! ( acc. entries. len( ) , 2 ) ;
1236+ assert_eq ! ( acc. entry_bytes( & acc. entries[ 0 ] ) , & [ 1 , 2 , 3 ] ) ;
1237+ assert_eq ! ( acc. entry_bytes( & acc. entries[ 1 ] ) , & [ 4 , 5 ] ) ;
1238+ assert_eq ! ( acc. entries[ 1 ] . start, 3 ) ;
1239+ }
1240+
11411241 #[ test]
11421242 fn collect_functions_forward_their_shape_to_datafusion_spark ( ) {
11431243 for udf in [
0 commit comments