@@ -28,7 +28,6 @@ use datafusion_common::Result;
2828use datafusion_common:: hash_utils:: create_hashes;
2929use datafusion_expr:: EmitTo ;
3030use hashbrown:: HashTable ;
31- use hashbrown:: hash_table:: Entry as HashTableEntry ;
3231use std:: borrow:: Cow ;
3332use std:: marker:: PhantomData ;
3433use std:: sync:: Arc ;
@@ -88,16 +87,18 @@ macro_rules! decode_scalar_string {
8887 Ok ( Arc :: new( builder. finish( ) ) as ArrayRef )
8988 } } ;
9089}
91- /// Entry stored inside `unique_dict_value_mapping`. Caching `hash` on the entry
9290struct DictEntry {
9391 hash : u64 ,
9492 group_id : usize ,
95- bytes : Vec < u8 > ,
93+ offset : usize ,
94+ len : usize ,
9695}
9796
9897pub struct GroupValuesDictionary < K : ArrowDictionaryKeyType + Send > {
99- // stores the order new unique elements are seen for self.emit()
100- seen_elements : Vec < Option < Vec < u8 > > > ,
98+ /// Packed byte storage for all group values.
99+ row_buffer : Vec < u8 > ,
100+ /// `row_offsets[g]` = start of group `g` in `row_buffer`;
101+ row_offsets : Vec < usize > ,
101102 value_dt : DataType ,
102103 _phantom : PhantomData < K > ,
103104 // keeps track of which values weve already seen, keyed by raw value hash.
@@ -117,7 +118,8 @@ pub struct GroupValuesDictionary<K: ArrowDictionaryKeyType + Send> {
117118impl < K : ArrowDictionaryKeyType + Send > GroupValuesDictionary < K > {
118119 pub fn new ( data_type : & DataType ) -> Self {
119120 Self {
120- seen_elements : Vec :: new ( ) ,
121+ row_buffer : Vec :: new ( ) ,
122+ row_offsets : Vec :: new ( ) ,
121123 unique_dict_value_mapping : HashTable :: new ( ) ,
122124 value_dt : data_type. clone ( ) ,
123125 _phantom : PhantomData ,
@@ -128,25 +130,28 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValuesDictionary<K> {
128130 }
129131 }
130132
131- /// Returns the existing `group_id` for the value with this hash and bytes,
132- /// or inserts a new entry and returns the freshly assigned group_id.
133133 fn lookup_or_insert_in_table ( & mut self , hash : u64 , raw : & [ u8 ] ) -> usize {
134- match self
135- . unique_dict_value_mapping
136- . entry ( hash, |e| e. bytes == raw, |e| e. hash )
137- {
138- HashTableEntry :: Occupied ( o) => o. get ( ) . group_id ,
139- HashTableEntry :: Vacant ( v) => {
140- let new_group_id = self . seen_elements . len ( ) ;
141- self . seen_elements . push ( Some ( raw. to_vec ( ) ) ) ; // replace this with raw buffer to avoid this double copy #TODO see https://github.com/apache/datafusion/issues/22078
142- v. insert ( DictEntry {
143- hash,
144- group_id : new_group_id,
145- bytes : raw. to_vec ( ) ,
146- } ) ;
147- new_group_id
148- }
134+ let row_buffer = & self . row_buffer ;
135+ if let Some ( e) = self . unique_dict_value_mapping . find ( hash, |e| {
136+ e. hash == hash && & row_buffer[ e. offset ..e. offset + e. len ] == raw
137+ } ) {
138+ return e. group_id ;
149139 }
140+ let new_group_id = self . row_offsets . len ( ) ;
141+ let offset = self . row_buffer . len ( ) ;
142+ self . row_offsets . push ( offset) ;
143+ self . row_buffer . extend_from_slice ( raw) ;
144+ self . unique_dict_value_mapping . insert_unique (
145+ hash,
146+ DictEntry {
147+ hash,
148+ group_id : new_group_id,
149+ offset,
150+ len : raw. len ( ) ,
151+ } ,
152+ |e| e. hash ,
153+ ) ;
154+ new_group_id
150155 }
151156 fn compute_value_hashes ( & mut self , values : & ArrayRef ) -> Result < ( ) > {
152157 self . values_cache . 1 . clear ( ) ;
@@ -220,52 +225,64 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValuesDictionary<K> {
220225 if let Some ( group_id) = self . null_group_id {
221226 group_id
222227 } else {
223- let new_group_id = self . seen_elements . len ( ) ;
224- self . seen_elements . push ( None ) ;
228+ let new_group_id = self . row_offsets . len ( ) ;
229+ self . row_offsets . push ( self . row_buffer . len ( ) ) ; // null: empty span
225230 self . null_group_id = Some ( new_group_id) ;
226231 new_group_id
227232 }
228233 }
229- fn transform_into_array ( & self , raw : & [ Option < Vec < u8 > > ] ) -> Result < ArrayRef > {
230- let item_capacity = raw. len ( ) ;
231- let data_capacity = item_capacity * AVG_BYTES_PER_DICT_VALUE ;
234+
235+ fn transform_into_array (
236+ & self ,
237+ n : usize ,
238+ null_group_id : Option < usize > ,
239+ ) -> Result < ArrayRef > {
240+ let data_capacity = n * AVG_BYTES_PER_DICT_VALUE ;
241+ let raw = ( 0 ..n) . map ( |i| {
242+ if Some ( i) == null_group_id {
243+ return None ;
244+ }
245+ let start = self . row_offsets [ i] ;
246+ // last group has no i+1 entry; its end is the buffer tail.
247+ let end = self
248+ . row_offsets
249+ . get ( i + 1 )
250+ . copied ( )
251+ . unwrap_or ( self . row_buffer . len ( ) ) ;
252+ Some ( & self . row_buffer [ start..end] )
253+ } ) ;
232254 match & self . value_dt {
233- DataType :: Utf8 => decode_scalar_string ! (
234- raw,
235- StringBuilder :: with_capacity( item_capacity, data_capacity)
236- ) ,
255+ DataType :: Utf8 => {
256+ decode_scalar_string ! ( raw, StringBuilder :: with_capacity( n, data_capacity) )
257+ }
237258 DataType :: LargeUtf8 => decode_scalar_string ! (
238259 raw,
239- LargeStringBuilder :: with_capacity( item_capacity, data_capacity)
240- ) ,
241- DataType :: Utf8View => decode_scalar_string ! (
242- raw,
243- StringViewBuilder :: with_capacity( item_capacity)
260+ LargeStringBuilder :: with_capacity( n, data_capacity)
244261 ) ,
262+ DataType :: Utf8View => {
263+ decode_scalar_string ! ( raw, StringViewBuilder :: with_capacity( n) )
264+ }
245265 DataType :: List ( field) => match field. data_type ( ) {
246266 DataType :: Utf8 => decode_list ! (
247267 raw,
248268 ListBuilder :: with_capacity(
249- StringBuilder :: with_capacity( item_capacity , data_capacity) ,
250- item_capacity ,
269+ StringBuilder :: with_capacity( n , data_capacity) ,
270+ n ,
251271 )
252272 . with_field( Arc :: clone( field) )
253273 ) ,
254274 DataType :: LargeUtf8 => decode_list ! (
255275 raw,
256276 ListBuilder :: with_capacity(
257- LargeStringBuilder :: with_capacity( item_capacity , data_capacity) ,
258- item_capacity ,
277+ LargeStringBuilder :: with_capacity( n , data_capacity) ,
278+ n ,
259279 )
260280 . with_field( Arc :: clone( field) )
261281 ) ,
262282 DataType :: Utf8View => decode_list ! (
263283 raw,
264- ListBuilder :: with_capacity(
265- StringViewBuilder :: with_capacity( item_capacity) ,
266- item_capacity,
267- )
268- . with_field( Arc :: clone( field) )
284+ ListBuilder :: with_capacity( StringViewBuilder :: with_capacity( n) , n, )
285+ . with_field( Arc :: clone( field) )
269286 ) ,
270287 other => Err ( NotImplemented ( format ! (
271288 "transform_into_array not implemented for List<{other:?}>"
@@ -295,22 +312,11 @@ fn valid_bounds<K: ArrowDictionaryKeyType>(n: usize) -> bool {
295312
296313impl < K : ArrowDictionaryKeyType + Send > GroupValues for GroupValuesDictionary < K > {
297314 fn size ( & self ) -> usize {
298- let seen_elements_size = self . seen_elements . capacity ( )
299- * size_of :: < Option < Vec < u8 > > > ( )
300- + self
301- . seen_elements
302- . iter ( )
303- . filter_map ( |opt| opt. as_ref ( ) )
304- . map ( |inner| inner. capacity ( ) )
305- . sum :: < usize > ( ) ;
306-
307- let unique_mapping_size = self . unique_dict_value_mapping . capacity ( )
308- * size_of :: < DictEntry > ( )
309- + self
310- . unique_dict_value_mapping
311- . iter ( )
312- . map ( |e| e. bytes . capacity ( ) )
313- . sum :: < usize > ( ) ;
315+ let row_data_size =
316+ self . row_buffer . capacity ( ) + self . row_offsets . capacity ( ) * size_of :: < usize > ( ) ;
317+
318+ let unique_mapping_size =
319+ self . unique_dict_value_mapping . capacity ( ) * size_of :: < DictEntry > ( ) ;
314320
315321 let values_cache_size = self . values_cache . 1 . capacity ( ) * size_of :: < u64 > ( )
316322 + self
@@ -320,13 +326,19 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
320326 . map ( |a| a. to_data ( ) . get_slice_memory_size ( ) . unwrap_or ( 0 ) )
321327 . unwrap_or ( 0 ) ;
322328
323- size_of :: < Self > ( ) + seen_elements_size + unique_mapping_size + values_cache_size
329+ let key_to_group_size = self . key_to_group . capacity ( ) * size_of :: < Option < usize > > ( ) ;
330+
331+ size_of :: < Self > ( )
332+ + row_data_size
333+ + unique_mapping_size
334+ + values_cache_size
335+ + key_to_group_size
324336 }
325337 fn len ( & self ) -> usize {
326- self . seen_elements . len ( )
338+ self . row_offsets . len ( )
327339 }
328340 fn is_empty ( & self ) -> bool {
329- self . seen_elements . is_empty ( )
341+ self . row_offsets . is_empty ( )
330342 }
331343 fn intern ( & mut self , cols : & [ ArrayRef ] , groups : & mut Vec < usize > ) -> Result < ( ) > {
332344 assert_eq ! (
@@ -390,46 +402,19 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
390402 Ok ( ( ) )
391403 }
392404 fn emit ( & mut self , emit_to : EmitTo ) -> Result < Vec < ArrayRef > > {
393- let ( elements_to_emit, null_id) = match emit_to {
394- EmitTo :: All => {
395- let original_null_id = self . null_group_id ;
396- self . null_group_id = None ;
397- self . unique_dict_value_mapping . clear ( ) ;
398- ( std:: mem:: take ( & mut self . seen_elements ) , original_null_id)
399- }
400- EmitTo :: First ( n) => {
401- let n = n. min ( self . seen_elements . len ( ) ) ;
402- let first_n = self . seen_elements . drain ( ..n) . collect :: < Vec < _ > > ( ) ; // again read from raw buffer directly
403- let original_null_id = self . null_group_id . filter ( |& id| id < n) ;
404- // update null_group_id if the null group was in the first n
405- if let Some ( null_id) = self . null_group_id {
406- if null_id < n {
407- self . null_group_id = None ;
408- } else {
409- self . null_group_id = Some ( null_id - n) ;
410- }
411- }
412- // shift all remaining group indices down by n in the table
413- self . unique_dict_value_mapping . retain ( |e| {
414- if e. group_id < n {
415- false
416- } else {
417- e. group_id -= n;
418- true
419- }
420- } ) ;
421- ( first_n, original_null_id)
422- }
405+ let n = match emit_to {
406+ EmitTo :: All => self . row_offsets . len ( ) ,
407+ EmitTo :: First ( k) => k. min ( self . row_offsets . len ( ) ) ,
423408 } ;
409+ let null_id = self . null_group_id . filter ( |& id| id < n) ;
424410
425- let n = elements_to_emit. len ( ) ;
426411 if !valid_bounds :: < K > ( n) {
427412 return Err ( Internal ( format ! (
428413 "group count {n} overflows key type {:?}" ,
429414 K :: DATA_TYPE
430415 ) ) ) ;
431416 }
432- let values_array = self . transform_into_array ( & elements_to_emit ) ?; // ingest a buffer + n then produce an array. should also update the len+offset of other entries #TODO see https://github.com/apache/datafusion/issues/22078
417+ let values_array = self . transform_into_array ( n , null_id ) ?;
433418
434419 let mut keys_builder = PrimitiveBuilder :: < K > :: with_capacity ( n) ;
435420 if let Some ( null_id) = null_id {
@@ -447,17 +432,58 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
447432 }
448433 let dict_array =
449434 DictionaryArray :: < K > :: try_new ( keys_builder. finish ( ) , values_array) ?;
435+
436+ match emit_to {
437+ EmitTo :: All => {
438+ self . null_group_id = None ;
439+ self . unique_dict_value_mapping . clear ( ) ;
440+ self . row_buffer . clear ( ) ;
441+ self . row_offsets . clear ( ) ;
442+ }
443+ EmitTo :: First ( _) => {
444+ if let Some ( nid) = self . null_group_id {
445+ if nid < n {
446+ self . null_group_id = None ;
447+ } else {
448+ self . null_group_id = Some ( nid - n) ;
449+ }
450+ }
451+ let retain_start = self
452+ . row_offsets
453+ . get ( n)
454+ . copied ( )
455+ . unwrap_or ( self . row_buffer . len ( ) ) ;
456+ self . row_offsets . drain ( 0 ..n) ;
457+ for off in & mut self . row_offsets {
458+ * off -= retain_start;
459+ }
460+ self . row_buffer . drain ( 0 ..retain_start) ;
461+ self . unique_dict_value_mapping . retain ( |e| {
462+ if e. group_id < n {
463+ return false ;
464+ }
465+ e. group_id -= n;
466+ e. offset -= retain_start;
467+ true
468+ } ) ;
469+ }
470+ }
471+
450472 Ok ( vec ! [ Arc :: new( dict_array) ] )
451473 }
452474 fn clear_shrink ( & mut self , num_rows : usize ) {
453- self . seen_elements . clear ( ) ;
454- self . seen_elements . shrink_to ( num_rows) ;
475+ self . row_buffer . clear ( ) ;
476+ self . row_buffer
477+ . shrink_to ( num_rows * AVG_BYTES_PER_DICT_VALUE ) ;
478+ self . row_offsets . clear ( ) ;
479+ self . row_offsets . shrink_to ( num_rows) ;
455480 self . null_group_id = None ;
456481 self . unique_dict_value_mapping . clear ( ) ;
457482 self . unique_dict_value_mapping
458483 . shrink_to ( num_rows, |e| e. hash ) ;
459484 self . values_cache . 0 = None ;
460485 self . key_to_group . clear ( ) ;
486+ self . key_to_group . shrink_to ( num_rows) ;
461487 self . values_cache . 1 . clear ( ) ;
462488 self . values_cache . 1 . shrink_to ( num_rows) ;
463489 }
@@ -834,6 +860,38 @@ mod test {
834860 mod streaming_emit {
835861 use super :: * ;
836862
863+ #[ test]
864+ fn test_null_only_group_emit_first ( ) {
865+ let mut gv = GroupValuesDictionary :: < Int32Type > :: new ( & DataType :: Utf8 ) ;
866+ let mut groups = Vec :: new ( ) ;
867+
868+ // intern a single null value (key is null; the value slot is irrelevant)
869+ let values = make_utf8_values ( vec ! [ Some ( "x" ) ] ) ;
870+ let dict = make_dict_array ( values, vec ! [ None ] ) ;
871+ gv. intern ( & [ dict] , & mut groups)
872+ . expect ( "intern should succeed" ) ;
873+
874+ assert_eq ! ( gv. len( ) , 1 ) ;
875+ assert_eq ! ( groups, vec![ 0 ] ) ;
876+
877+ // emit First(1) -- the null group is the ONLY group
878+ let result = gv. emit ( EmitTo :: First ( 1 ) ) . expect ( "emit should succeed" ) ;
879+ assert_eq ! ( result. len( ) , 1 ) ;
880+
881+ let emitted = result[ 0 ]
882+ . as_any ( )
883+ . downcast_ref :: < DictionaryArray < Int32Type > > ( )
884+ . expect ( "Expected DictionaryArray" ) ;
885+
886+ // The emitted DictionaryArray should have 1 element, and it should be null
887+ assert_eq ! ( emitted. len( ) , 1 ) ;
888+ assert ! ( emitted. is_null( 0 ) , "the emitted row should be null" ) ;
889+
890+ // post-emit state: everything should be cleared
891+ assert_eq ! ( gv. len( ) , 0 ) ;
892+ assert ! ( gv. is_empty( ) ) ;
893+ }
894+
837895 #[ test]
838896 fn test_emit_first_shifts_and_retains ( ) {
839897 let mut gv = GroupValuesDictionary :: < Int32Type > :: new ( & DataType :: Utf8 ) ;
0 commit comments