@@ -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,15 @@ 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 > ( ) + row_data_size + unique_mapping_size + values_cache_size + key_to_group_size
324332 }
325333 fn len ( & self ) -> usize {
326- self . seen_elements . len ( )
334+ self . row_offsets . len ( )
327335 }
328336 fn is_empty ( & self ) -> bool {
329- self . seen_elements . is_empty ( )
337+ self . row_offsets . is_empty ( )
330338 }
331339 fn intern ( & mut self , cols : & [ ArrayRef ] , groups : & mut Vec < usize > ) -> Result < ( ) > {
332340 assert_eq ! (
@@ -390,46 +398,19 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
390398 Ok ( ( ) )
391399 }
392400 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- }
401+ let n = match emit_to {
402+ EmitTo :: All => self . row_offsets . len ( ) ,
403+ EmitTo :: First ( k) => k. min ( self . row_offsets . len ( ) ) ,
423404 } ;
405+ let null_id = self . null_group_id . filter ( |& id| id < n) ;
424406
425- let n = elements_to_emit. len ( ) ;
426407 if !valid_bounds :: < K > ( n) {
427408 return Err ( Internal ( format ! (
428409 "group count {n} overflows key type {:?}" ,
429410 K :: DATA_TYPE
430411 ) ) ) ;
431412 }
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
413+ let values_array = self . transform_into_array ( n , null_id ) ?;
433414
434415 let mut keys_builder = PrimitiveBuilder :: < K > :: with_capacity ( n) ;
435416 if let Some ( null_id) = null_id {
@@ -447,17 +428,58 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
447428 }
448429 let dict_array =
449430 DictionaryArray :: < K > :: try_new ( keys_builder. finish ( ) , values_array) ?;
431+
432+ match emit_to {
433+ EmitTo :: All => {
434+ self . null_group_id = None ;
435+ self . unique_dict_value_mapping . clear ( ) ;
436+ self . row_buffer . clear ( ) ;
437+ self . row_offsets . clear ( ) ;
438+ }
439+ EmitTo :: First ( _) => {
440+ if let Some ( nid) = self . null_group_id {
441+ if nid < n {
442+ self . null_group_id = None ;
443+ } else {
444+ self . null_group_id = Some ( nid - n) ;
445+ }
446+ }
447+ let retain_start = self
448+ . row_offsets
449+ . get ( n)
450+ . copied ( )
451+ . unwrap_or ( self . row_buffer . len ( ) ) ;
452+ self . row_offsets . drain ( 0 ..n) ;
453+ for off in & mut self . row_offsets {
454+ * off -= retain_start;
455+ }
456+ self . row_buffer . drain ( 0 ..retain_start) ;
457+ self . unique_dict_value_mapping . retain ( |e| {
458+ if e. group_id < n {
459+ return false ;
460+ }
461+ e. group_id -= n;
462+ e. offset -= retain_start;
463+ true
464+ } ) ;
465+ }
466+ }
467+
450468 Ok ( vec ! [ Arc :: new( dict_array) ] )
451469 }
452470 fn clear_shrink ( & mut self , num_rows : usize ) {
453- self . seen_elements . clear ( ) ;
454- self . seen_elements . shrink_to ( num_rows) ;
471+ self . row_buffer . clear ( ) ;
472+ self . row_buffer
473+ . shrink_to ( num_rows * AVG_BYTES_PER_DICT_VALUE ) ;
474+ self . row_offsets . clear ( ) ;
475+ self . row_offsets . shrink_to ( num_rows) ;
455476 self . null_group_id = None ;
456477 self . unique_dict_value_mapping . clear ( ) ;
457478 self . unique_dict_value_mapping
458479 . shrink_to ( num_rows, |e| e. hash ) ;
459480 self . values_cache . 0 = None ;
460481 self . key_to_group . clear ( ) ;
482+ self . key_to_group . shrink_to ( num_rows) ;
461483 self . values_cache . 1 . clear ( ) ;
462484 self . values_cache . 1 . shrink_to ( num_rows) ;
463485 }
@@ -834,6 +856,37 @@ mod test {
834856 mod streaming_emit {
835857 use super :: * ;
836858
859+ #[ test]
860+ fn test_null_only_group_emit_first ( ) {
861+ let mut gv = GroupValuesDictionary :: < Int32Type > :: new ( & DataType :: Utf8 ) ;
862+ let mut groups = Vec :: new ( ) ;
863+
864+ // intern a single null value (key is null; the value slot is irrelevant)
865+ let values = make_utf8_values ( vec ! [ Some ( "x" ) ] ) ;
866+ let dict = make_dict_array ( values, vec ! [ None ] ) ;
867+ gv. intern ( & [ dict] , & mut groups) . expect ( "intern should succeed" ) ;
868+
869+ assert_eq ! ( gv. len( ) , 1 ) ;
870+ assert_eq ! ( groups, vec![ 0 ] ) ;
871+
872+ // emit First(1) -- the null group is the ONLY group
873+ let result = gv. emit ( EmitTo :: First ( 1 ) ) . expect ( "emit should succeed" ) ;
874+ assert_eq ! ( result. len( ) , 1 ) ;
875+
876+ let emitted = result[ 0 ]
877+ . as_any ( )
878+ . downcast_ref :: < DictionaryArray < Int32Type > > ( )
879+ . expect ( "Expected DictionaryArray" ) ;
880+
881+ // The emitted DictionaryArray should have 1 element, and it should be null
882+ assert_eq ! ( emitted. len( ) , 1 ) ;
883+ assert ! ( emitted. is_null( 0 ) , "the emitted row should be null" ) ;
884+
885+ // post-emit state: everything should be cleared
886+ assert_eq ! ( gv. len( ) , 0 ) ;
887+ assert ! ( gv. is_empty( ) ) ;
888+ }
889+
837890 #[ test]
838891 fn test_emit_first_shifts_and_retains ( ) {
839892 let mut gv = GroupValuesDictionary :: < Int32Type > :: new ( & DataType :: Utf8 ) ;
0 commit comments