@@ -21,8 +21,8 @@ use std::sync::{Arc, LazyLock};
2121use std:: task:: { Context , Poll } ;
2222
2323use arrow:: array:: {
24- Array , ArrayRef , BinaryViewArray , BufferSpec , GenericByteViewArray , StringViewArray ,
25- layout, make_array,
24+ Array , ArrayRef , AsArray , BinaryViewArray , BufferSpec , GenericByteViewArray ,
25+ StringViewArray , layout, make_array,
2626} ;
2727use arrow:: buffer:: { Buffer , ScalarBuffer } ;
2828use arrow:: datatypes:: DataType ;
@@ -37,6 +37,7 @@ use arrow_data::{ArrayDataBuilder, ByteView, MAX_INLINE_VIEW_LEN};
3737#[ cfg( test) ]
3838use arrow_ipc:: writer:: StreamWriter ;
3939use arrow_ipc:: { CompressionType , root_as_message} ;
40+ use arrow_select:: dictionary:: garbage_collect_any_dictionary;
4041
4142use datafusion_common:: config:: SpillCompression ;
4243use datafusion_common:: { Result , internal_datafusion_err} ;
@@ -736,7 +737,7 @@ fn get_max_alignment_for_schema(schema: &Schema) -> usize {
736737#[ cfg( test) ]
737738const VIEW_SIZE_BYTES : usize = 16 ;
738739
739- /// Performs garbage collection on StringView and BinaryView arrays before spilling to reduce memory usage .
740+ /// Compacts view buffers and oversized dictionaries before spilling.
740741///
741742/// # Why GC is needed
742743///
@@ -757,19 +758,25 @@ const VIEW_SIZE_BYTES: usize = 16;
757758/// containing only the data referenced by the current views
758759/// 4. Returns a new batch with GC'd arrays (or original arrays if GC not needed)
759760///
761+ /// Dictionary arrays with more values than keys are also compacted using Arrow's
762+ /// dictionary garbage collector before visiting their children. This avoids spilling
763+ /// whole value tables retained by sliced or merged dictionaries.
764+ ///
760765/// # When GC is triggered
761766///
762- /// GC is only performed when data buffers exceed a threshold (currently 10KB).
767+ /// View GC is only performed when data buffers exceed a threshold (currently 10KB).
763768/// This balances memory savings against the CPU overhead of garbage collection.
764- /// Small arrays are passed through unchanged since the GC overhead would exceed
769+ /// Small view buffers are passed through unchanged since the GC overhead would exceed
765770/// any memory savings.
766771///
767772/// # Performance considerations
768773///
769- /// - If no view arrays need compaction, the original batch is cloned cheaply
770- /// - GC is skipped for small buffers to avoid unnecessary CPU overhead
774+ /// - If no arrays need compaction, the original batch is cloned cheaply
775+ /// - View GC is skipped for small buffers to avoid unnecessary CPU overhead
771776/// - Nested container types are traversed recursively so view arrays inside
772777/// `List`, `Map`, `Union`, `Dictionary`, and other child-bearing arrays are compacted too
778+ /// - Traversal uses physical children, not logical reachability. For example,
779+ /// unused ListView child entries can still retain dictionary values
773780/// - The Arrow `gc()` method itself is optimized and only copies referenced data
774781pub ( crate ) fn gc_view_arrays ( batch : & RecordBatch ) -> Result < RecordBatch > {
775782 let mut mutated = false ;
@@ -810,6 +817,15 @@ fn gc_array(array: &ArrayRef) -> Result<(ArrayRef, bool)> {
810817 None => ( Arc :: clone ( array) , false ) ,
811818 } )
812819 }
820+ DataType :: Dictionary ( _, _)
821+ if array. as_any_dictionary ( ) . values ( ) . len ( ) > array. len ( ) =>
822+ {
823+ // Struct-valued merge dictionaries can concatenate whole value tables.
824+ // Prune the outer dictionary before compacting its retained children.
825+ let compacted = garbage_collect_any_dictionary ( array. as_any_dictionary ( ) ) ?;
826+ let ( compacted, _) = gc_array_children ( & compacted) ?;
827+ Ok ( ( compacted, true ) )
828+ }
813829 _ => gc_array_children ( array) ,
814830 }
815831}
@@ -992,9 +1008,12 @@ mod tests {
9921008 use crate :: metrics:: SpillMetrics ;
9931009 use crate :: spill:: spill_manager:: SpillManager ;
9941010 use crate :: test:: build_table_i32;
995- use arrow:: array:: { ArrayRef , Int32Array , StringArray } ;
1011+ use arrow:: array:: {
1012+ ArrayRef , DictionaryArray , Int32Array , ListArray , StringArray , StructArray ,
1013+ } ;
1014+ use arrow:: buffer:: OffsetBuffer ;
9961015 use arrow:: compute:: cast;
997- use arrow:: datatypes:: { DataType , Field } ;
1016+ use arrow:: datatypes:: { DataType , Field , Int32Type } ;
9981017 use arrow:: ipc:: reader:: StreamReader ;
9991018 use datafusion_execution:: runtime_env:: RuntimeEnv ;
10001019 use futures:: StreamExt as _;
@@ -2693,6 +2712,64 @@ mod tests {
26932712 Ok ( ( ) )
26942713 }
26952714
2715+ #[ rstest:: rstest]
2716+ #[ case( SpillCompression :: Uncompressed ) ]
2717+ #[ case( SpillCompression :: Lz4Frame ) ]
2718+ #[ case( SpillCompression :: Zstd ) ]
2719+ #[ tokio:: test]
2720+ async fn test_spill_prunes_unused_nested_dictionary_values (
2721+ #[ case] compression : SpillCompression ,
2722+ ) -> Result < ( ) > {
2723+ let values = Arc :: new ( StructArray :: from ( vec ! [
2724+ (
2725+ Arc :: new( Field :: new( "id" , DataType :: Int32 , false ) ) ,
2726+ Arc :: new( Int32Array :: from_iter_values( 0 ..1024 ) ) as ArrayRef ,
2727+ ) ,
2728+ (
2729+ Arc :: new( Field :: new( "name" , DataType :: Utf8View , false ) ) ,
2730+ Arc :: new( StringViewArray :: from_iter_values(
2731+ ( 0 ..1024 ) . map( |id| format!( "{id}:{}" , "x" . repeat( 256 ) ) ) ,
2732+ ) ) as ArrayRef ,
2733+ ) ,
2734+ ] ) ) as ArrayRef ;
2735+ let batch = |keys, values| -> Result < RecordBatch > {
2736+ let dictionary = DictionaryArray :: < Int32Type > :: try_new ( keys, values) ?;
2737+ let list = ListArray :: new (
2738+ Arc :: new ( Field :: new_list_field ( dictionary. data_type ( ) . clone ( ) , true ) ) ,
2739+ OffsetBuffer :: new ( vec ! [ 0_i32 , 1 , 3 , 4 ] . into ( ) ) ,
2740+ Arc :: new ( dictionary) ,
2741+ None ,
2742+ ) ;
2743+ Ok ( RecordBatch :: try_from_iter ( [ (
2744+ "stacktrace" ,
2745+ Arc :: new ( list) as ArrayRef ,
2746+ ) ] ) ?)
2747+ } ;
2748+ let input = batch (
2749+ Int32Array :: from ( vec ! [ Some ( 1023 ) , None , Some ( 17 ) , Some ( 1023 ) ] ) ,
2750+ Arc :: clone ( & values) ,
2751+ ) ?;
2752+ let expected = batch (
2753+ Int32Array :: from ( vec ! [ Some ( 1 ) , None , Some ( 0 ) , Some ( 1 ) ] ) ,
2754+ arrow:: compute:: take ( & values, & Int32Array :: from ( vec ! [ 17 , 1023 ] ) , None ) ?,
2755+ ) ?;
2756+ let metrics = SpillMetrics :: new ( & ExecutionPlanMetricsSet :: new ( ) , 0 ) ;
2757+ let manager =
2758+ SpillManager :: new ( Arc :: new ( RuntimeEnv :: default ( ) ) , metrics, input. schema ( ) )
2759+ . with_compression_type ( compression) ;
2760+ let file = manager
2761+ . spill_record_batch_and_finish ( & [ input] , "nested dictionary GC" ) ?
2762+ . unwrap ( ) ;
2763+ let size = file. size ( ) . unwrap ( ) ;
2764+ assert ! (
2765+ size < 16 * 1024 ,
2766+ "unused dictionary values spilled: {size} bytes"
2767+ ) ;
2768+ let actual = collect ( manager. read_spill_as_stream ( file, None ) ?) . await ?;
2769+ assert_eq ! ( actual, vec![ expected] ) ;
2770+ Ok ( ( ) )
2771+ }
2772+
26962773 #[ tokio:: test]
26972774 async fn test_spill_file_size_gc_verification_string_view ( ) -> Result < ( ) > {
26982775 use arrow:: array:: StringViewArray ;
0 commit comments