@@ -9,10 +9,10 @@ use crate::metrics::ExecutionPlanMetricsSet;
99use crate :: spill:: get_record_batch_memory_size;
1010use crate :: spill:: spill_manager:: GetSlicedSize ;
1111use arrow:: array:: {
12- ArrayRef , Decimal128Array , DictionaryArray , Int8Array , Int32Array , Int64Array ,
13- StringArray , StringViewArray ,
12+ ArrayRef , Decimal128Array , DictionaryArray , FixedSizeBinaryArray , Int8Array ,
13+ Int32Array , Int64Array , StringArray , StringViewArray ,
1414} ;
15- use arrow:: compute:: { SortOptions , concat_batches} ;
15+ use arrow:: compute:: { SortOptions , cast , concat_batches} ;
1616use arrow:: datatypes:: { DataType , Field , Int8Type , Schema } ;
1717use arrow:: record_batch:: RecordBatch ;
1818use datafusion_common:: config:: { ExecutionOptions , SpillCompression } ;
@@ -679,29 +679,69 @@ async fn test_sort_preparation_keeps_output_reserved() -> Result<()> {
679679 Ok ( ( ) )
680680}
681681
682- /// Two `Int32` keys encode to 18 bytes per row for the merge, more than twice
683- /// the 8 bytes per row of the batches. Merging full-size runs would need more
684- /// memory than the sort reserves while buffering them.
682+ /// Merging sorted runs in the row format holds the keys of every run's current
683+ /// batch. Two `Int32` keys encode to 18 bytes per row against 8 bytes in the
684+ /// batches, and a single `FixedSizeBinary(16)` key also merges in the row
685+ /// format, so merging full-size runs needs more memory than the sort reserves
686+ /// while buffering them. The `Utf8View` and dictionary payloads keep buffers
687+ /// shared after sorting, which must not be charged once per split batch.
685688async fn check_merge_keys_larger_than_batches ( ) -> Result < ( ) > {
686689 let rows = 8192 ;
687- let schema = Arc :: new ( Schema :: new ( vec ! [
688- Field :: new( "a" , DataType :: Int32 , false ) ,
689- Field :: new( "b" , DataType :: Int32 , false ) ,
690- ] ) ) ;
691- let batches = ( 0 ..64 )
692- . map ( |batch| {
693- let a =
694- Int32Array :: from_iter_values ( ( 0 ..rows) . map ( |i| ( i * 31 + batch) % 1000 ) ) ;
695- let b = Int32Array :: from_iter_values ( ( 0 ..rows) . rev ( ) ) ;
696- RecordBatch :: try_new ( Arc :: clone ( & schema) , vec ! [ Arc :: new( a) , Arc :: new( b) ] )
690+ let int_keys = |batch : i32 | -> Vec < ArrayRef > {
691+ vec ! [
692+ Arc :: new( Int32Array :: from_iter_values(
693+ ( 0 ..rows) . map( |i| ( i * 31 + batch) % 1000 ) ,
694+ ) ) ,
695+ Arc :: new( Int32Array :: from_iter_values( ( 0 ..rows) . rev( ) ) ) ,
696+ ]
697+ } ;
698+ let int_fields = [ ( "a" , DataType :: Int32 ) , ( "b" , DataType :: Int32 ) ] ;
699+ check_merge_keys ( & int_fields, 2 , |batch| Ok ( int_keys ( batch) ) ) . await ?;
700+ // Longer than 12 bytes, so views keep them in data buffers.
701+ let strings = |batch : i32 | -> StringArray {
702+ ( 0 ..rows)
703+ . map ( |i| Some ( format ! ( "{batch}-{i:0>64}" ) ) )
704+ . collect ( )
705+ } ;
706+ let dictionary =
707+ DataType :: Dictionary ( Box :: new ( DataType :: Int32 ) , Box :: new ( DataType :: Utf8 ) ) ;
708+ for payload in [ DataType :: Utf8View , dictionary] {
709+ let fields = [ & int_fields[ ..] , & [ ( "c" , payload. clone ( ) ) ] ] . concat ( ) ;
710+ check_merge_keys ( & fields, 2 , |batch| {
711+ let payload = cast ( & strings ( batch) , & payload) ?;
712+ Ok ( [ int_keys ( batch) , vec ! [ payload] ] . concat ( ) )
697713 } )
698- . collect :: < Result < Vec < _ > , _ > > ( ) ?;
699- let ordering: LexOrdering = [
700- PhysicalSortExpr :: new_default ( Arc :: new ( Column :: new ( "a" , 0 ) ) ) ,
701- PhysicalSortExpr :: new_default ( Arc :: new ( Column :: new ( "b" , 1 ) ) ) ,
702- ]
703- . into ( ) ;
704- // Spill every 16 batches.
714+ . await ?;
715+ }
716+ check_merge_keys ( & [ ( "k" , DataType :: FixedSizeBinary ( 16 ) ) ] , 1 , |batch| {
717+ let keys = ( 0 ..rows) . map ( |i| u128:: from ( ( ( i * 31 + batch) % 1000 ) as u32 ) ) ;
718+ let keys = FixedSizeBinaryArray :: try_from_iter ( keys. map ( u128:: to_be_bytes) ) ?;
719+ Ok ( vec ! [ Arc :: new( keys) ] )
720+ } )
721+ . await
722+ }
723+
724+ /// Sorts 64 batches of `columns` by the first `keys` fields with room to buffer
725+ /// 16 of them, then checks the spilled output and that all memory is released.
726+ async fn check_merge_keys (
727+ fields : & [ ( & str , DataType ) ] ,
728+ keys : usize ,
729+ columns : impl Fn ( i32 ) -> Result < Vec < ArrayRef > > ,
730+ ) -> Result < ( ) > {
731+ let schema = Arc :: new ( Schema :: new (
732+ fields
733+ . iter ( )
734+ . map ( |( name, data_type) | Field :: new ( * name, data_type. clone ( ) , false ) )
735+ . collect :: < Vec < _ > > ( ) ,
736+ ) ) ;
737+ let batches = ( 0 ..64 )
738+ . map ( |batch| Ok ( RecordBatch :: try_new ( Arc :: clone ( & schema) , columns ( batch) ?) ?) )
739+ . collect :: < Result < Vec < _ > > > ( ) ?;
740+ let ordering =
741+ LexOrdering :: new ( ( 0 ..keys) . map ( |i| {
742+ PhysicalSortExpr :: new_default ( Arc :: new ( Column :: new ( fields[ i] . 0 , i) ) )
743+ } ) )
744+ . expect ( "at least one sort key" ) ;
705745 let capacity = MERGE_BYTES + 16 * get_reserved_bytes_for_record_batch ( & batches[ 0 ] ) ?;
706746 let pool = AdjustablePool :: new ( capacity) ;
707747 let runtime = RuntimeEnvBuilder :: new ( )
@@ -711,7 +751,7 @@ async fn check_merge_keys_larger_than_batches() -> Result<()> {
711751 0 ,
712752 Arc :: clone ( & schema) ,
713753 ordering. clone ( ) ,
714- rows as usize ,
754+ batches [ 0 ] . num_rows ( ) ,
715755 MERGE_BYTES ,
716756 0 ,
717757 SpillCompression :: Uncompressed ,
0 commit comments