@@ -23,6 +23,7 @@ use std::sync::Arc;
2323use crate :: fuzz_cases:: aggregate_fuzz:: assert_spill_count_metric;
2424use crate :: fuzz_cases:: once_exec:: OnceExec ;
2525use arrow:: array:: UInt64Array ;
26+ use arrow:: row:: { RowConverter , SortField } ;
2627use arrow:: { array:: StringArray , compute:: SortOptions , record_batch:: RecordBatch } ;
2728use arrow_schema:: { DataType , Field , Schema } ;
2829use datafusion:: common:: Result ;
@@ -45,9 +46,19 @@ use datafusion_physical_plan::aggregates::{
4546 AggregateExec , AggregateMode , PhysicalGroupBy ,
4647} ;
4748use datafusion_physical_plan:: metrics:: MetricValue ;
49+ use datafusion_physical_plan:: spill:: get_record_batch_memory_size;
4850use datafusion_physical_plan:: stream:: RecordBatchStreamAdapter ;
4951use futures:: StreamExt ;
5052
53+ use arrow:: array:: Int32Array ;
54+ use datafusion:: datasource:: memory:: MemorySourceConfig ;
55+ use datafusion:: physical_plan:: sorts:: sort_preserving_merge:: SortPreservingMergeExec ;
56+ use datafusion_execution:: memory_pool:: {
57+ MemoryPool , PeakRecordingPool , UnboundedMemoryPool ,
58+ } ;
59+ use datafusion_physical_plan:: metrics:: { ExecutionPlanMetricsSet , SpillMetrics } ;
60+ use datafusion_physical_plan:: spill:: SpillManager ;
61+
5162#[ tokio:: test]
5263async fn test_sort_with_limited_memory ( ) -> Result < ( ) > {
5364 let record_batch_size = 8192 ;
@@ -290,6 +301,250 @@ async fn test_sort_with_limited_memory_and_oversized_record_batch() -> Result<()
290301 Ok ( ( ) )
291302}
292303
304+ #[ tokio:: test]
305+ async fn test_sort_preserving_merge_peak_memory_with_spilled_input_round_robin ( )
306+ -> Result < ( ) > {
307+ run_sort_preserving_merge_peak_memory_with_spilled_input ( true , false , false ) . await
308+ }
309+
310+ #[ tokio:: test]
311+ async fn test_sort_preserving_merge_peak_memory_with_spilled_input_no_round_robin ( )
312+ -> Result < ( ) > {
313+ run_sort_preserving_merge_peak_memory_with_spilled_input ( false , false , false ) . await
314+ }
315+
316+ #[ tokio:: test]
317+ async fn test_sort_preserving_merge_peak_memory_with_spilled_input_round_robin_multi_column ( )
318+ -> Result < ( ) > {
319+ run_sort_preserving_merge_peak_memory_with_spilled_input ( true , true , false ) . await
320+ }
321+
322+ #[ tokio:: test]
323+ async fn test_sort_preserving_merge_peak_memory_with_spilled_input_no_round_robin_multi_column ( )
324+ -> Result < ( ) > {
325+ run_sort_preserving_merge_peak_memory_with_spilled_input ( false , true , false ) . await
326+ }
327+
328+ #[ tokio:: test]
329+ async fn test_sort_preserving_merge_peak_memory_with_spilled_input_round_robin_tied_values ( )
330+ -> Result < ( ) > {
331+ run_sort_preserving_merge_peak_memory_with_spilled_input ( true , false , true ) . await
332+ }
333+
334+ #[ tokio:: test]
335+ async fn test_sort_preserving_merge_peak_memory_with_spilled_input_no_round_robin_tied_values ( )
336+ -> Result < ( ) > {
337+ run_sort_preserving_merge_peak_memory_with_spilled_input ( false , false , true ) . await
338+ }
339+
340+ /// Intended to measure the maximum number of record batches held in memory by
341+ /// the SortPreservingMergeStream in a convoluted way by measuring the peak
342+ /// memory reservation. Relevant for merging spilled streams, where the produced
343+ /// record batches suffer from the following issue:
344+ /// https://github.com/apache/arrow-rs/issues/6363
345+ ///
346+ /// After an IPC roundtrip, all columns in a [`RecordBatch`] share a single
347+ /// parent buffer. It causes the memory reservation to be inflated, but the
348+ /// bigger issue is the increase in the peak allocated memory caused by
349+ /// prev_cursors in SortPreservingMergeExec. The increase is caused by the fact
350+ /// that the FieldCursor inside prev_cursors holds a reference for the entire
351+ /// Buffer allocated for the input record batch, preventing it from being
352+ /// dropped and thus increasing the number of concomitent input record batches
353+ /// living during the merging phase
354+ async fn run_sort_preserving_merge_peak_memory_with_spilled_input (
355+ round_robin : bool ,
356+ multi_column_sort : bool ,
357+ tied_values : bool ,
358+ ) -> Result < ( ) > {
359+ let num_batches = 10usize ;
360+ let num_rows_per_batch = 100usize ;
361+ // payload is ~100x larger than the sort key (i32 = 4 bytes, string ≈ 400 bytes)
362+ let large_string = "x" . repeat ( 400 ) ;
363+
364+ let schema = Arc :: new ( Schema :: new ( vec ! [
365+ Field :: new( "sort_key" , DataType :: Int32 , false ) ,
366+ Field :: new( "payload" , DataType :: Utf8 , false ) ,
367+ ] ) ) ;
368+
369+ // Unbounded env used only for spilling the input; the merge runs under its
370+ // own pool below.
371+ let spill_env = Arc :: new ( RuntimeEnvBuilder :: new ( ) . build ( ) ?) ;
372+
373+ let mut partition_batches: Vec < Vec < RecordBatch > > = Vec :: new ( ) ;
374+
375+ for stream_idx in 0 ..2usize {
376+ // Each stream covers a non-overlapping key range so both are individually
377+ // sorted: stream 0 → [0, 1000), stream 1 → [1000, 2000). When
378+ // `tied_values` is set, every row of every batch in both streams
379+ // instead carries the same sort key, so every comparison between the
380+ // two streams is a tie.
381+ let batches: Vec < RecordBatch > = ( 0 ..num_batches)
382+ . map ( |b| {
383+ // Interleave streams: stream 0 → even slots [0,200,400,...],
384+ // stream 1 → odd slots [100,300,500,...] so the merge
385+ // alternates between them on every batch.
386+ let base = ( ( b * 2 + stream_idx) * num_rows_per_batch) as i32 ;
387+ let sort_col: Int32Array = if tied_values {
388+ std:: iter:: repeat_n ( 0 , num_rows_per_batch) . collect ( )
389+ } else {
390+ ( base..base + num_rows_per_batch as i32 ) . collect ( )
391+ } ;
392+ let payload_col: StringArray =
393+ std:: iter:: repeat_n ( large_string. as_str ( ) , num_rows_per_batch)
394+ . map ( Some )
395+ . collect ( ) ;
396+ RecordBatch :: try_new (
397+ Arc :: clone ( & schema) ,
398+ vec ! [ Arc :: new( sort_col) , Arc :: new( payload_col) ] ,
399+ )
400+ . unwrap ( )
401+ } )
402+ . collect ( ) ;
403+
404+ // Spill to disk then read back: each RecordBatch is now IPC-backed,
405+ // meaning all columns share a single parent buffer. As a result,
406+ // get_buffer_memory_size() on the sort_key column returns the full
407+ // parent-buffer capacity (≈ batch size of both columns combined) rather
408+ // than just the key data (num_rows * 4 bytes).
409+ let metrics = SpillMetrics :: new ( & ExecutionPlanMetricsSet :: new ( ) , 0 ) ;
410+ let manager =
411+ SpillManager :: new ( Arc :: clone ( & spill_env) , metrics, Arc :: clone ( & schema) ) ;
412+ let spill_file = manager
413+ . spill_record_batch_and_finish ( & batches, "stream" ) ?
414+ . expect ( "non-empty input should produce a spill file" ) ;
415+
416+ let mut stream = manager. read_spill_as_stream ( spill_file, None ) ?;
417+ let mut ipc_batches: Vec < RecordBatch > = Vec :: new ( ) ;
418+ while let Some ( batch) = stream. next ( ) . await {
419+ ipc_batches. push ( batch?) ;
420+ }
421+ partition_batches. push ( ipc_batches) ;
422+ }
423+
424+ let ipc_batch_size = get_record_batch_memory_size ( & partition_batches[ 0 ] [ 0 ] ) ;
425+
426+ // Build a 2-partition plan from the IPC-recovered batches.
427+ let input =
428+ MemorySourceConfig :: try_new_exec ( & partition_batches, Arc :: clone ( & schema) , None ) ?;
429+
430+ let sort_key_expr = PhysicalSortExpr {
431+ expr : col ( "sort_key" , & schema) ?,
432+ options : SortOptions {
433+ descending : false ,
434+ nulls_first : true ,
435+ } ,
436+ } ;
437+ // `payload` has the same value in every row, so adding it as a secondary
438+ // sort key doesn't change the resulting order — it only forces the merge
439+ // onto the row-oriented (`RowValues`/`RowCursorStream`) comparison path
440+ // used whenever more than one sort expression is present.
441+ let mut sort_exprs = vec ! [ sort_key_expr] ;
442+ if multi_column_sort {
443+ sort_exprs. push ( PhysicalSortExpr {
444+ expr : col ( "payload" , & schema) ?,
445+ options : SortOptions {
446+ descending : false ,
447+ nulls_first : true ,
448+ } ,
449+ } ) ;
450+ }
451+
452+ // When sorting by more than one column, the merge switches to the
453+ // row-oriented `RowValues`/`RowCursorStream` path
454+ //
455+ // `RowCursorStream` also tracks one *shared* (not per-partition)
456+ // reservation sized to `converter.size()` (`stream.rs`:
457+ // `self.reservation.try_resize(self.converter.size())`) — the
458+ // `RowConverter`'s own fixed internal state, separate from the `Rows`
459+ // it produces per batch.
460+ let ( row_batch_size, converter_size) = if multi_column_sort {
461+ let sort_fields = sort_exprs
462+ . iter ( )
463+ . map ( |s| {
464+ let data_type = s. expr . data_type ( & schema) ?;
465+ Ok ( SortField :: new_with_options ( data_type, s. options ) )
466+ } )
467+ . collect :: < Result < Vec < _ > > > ( ) ?;
468+ let converter = RowConverter :: new ( sort_fields) ?;
469+ let cols = sort_exprs
470+ . iter ( )
471+ . map ( |s| {
472+ s. expr
473+ . evaluate ( & partition_batches[ 0 ] [ 0 ] ) ?
474+ . into_array ( partition_batches[ 0 ] [ 0 ] . num_rows ( ) )
475+ } )
476+ . collect :: < Result < Vec < _ > > > ( ) ?;
477+ let rows = converter. convert_columns ( & cols) ?;
478+ ( rows. size ( ) , converter. size ( ) )
479+ } else {
480+ ( 0 , 0 )
481+ } ;
482+
483+ let merge = Arc :: new (
484+ SortPreservingMergeExec :: new ( LexOrdering :: new ( sort_exprs) . unwrap ( ) , input)
485+ . with_round_robin_repartition ( round_robin) ,
486+ ) ;
487+
488+ // PeakRecordingPool records peak reserved bytes as a running high-water mark
489+ // (via grow/shrink deltas), independent of any per-consumer registration
490+ // bookkeeping - unlike TrackConsumersPool, whose tracked-consumer entry (and
491+ // its peak) gets discarded the moment the consumer unregisters, which now
492+ // happens mid-poll (inside the drain loop below) rather than when the
493+ // caller eventually drops the returned stream.
494+ let tracking_pool = Arc :: new ( PeakRecordingPool :: new ( Arc :: new (
495+ UnboundedMemoryPool :: default ( ) ,
496+ ) ) ) ;
497+ let runtime = RuntimeEnvBuilder :: new ( )
498+ . with_memory_pool ( Arc :: clone ( & tracking_pool) as Arc < dyn MemoryPool > )
499+ . build ( ) ?;
500+ let task_ctx = Arc :: new (
501+ TaskContext :: default ( )
502+ . with_session_config ( SessionConfig :: new ( ) . with_batch_size ( num_rows_per_batch) )
503+ . with_runtime ( Arc :: new ( runtime) ) ,
504+ ) ;
505+
506+ let mut output = merge. execute ( 0 , task_ctx) ?;
507+ let mut total_rows = 0usize ;
508+ while let Some ( batch) = output. next ( ) . await {
509+ total_rows += batch?. num_rows ( ) ;
510+ }
511+ assert_eq ! ( total_rows, 2 * num_batches * num_rows_per_batch) ;
512+
513+ let peak_bytes = tracking_pool. peak_reserved ( ) ;
514+
515+ // in the single column case, the cursor takes up an ipc_batch_size worth of memory due to the
516+ // IPC roundtrip issue
517+ // for the multi-column case, we've calculated row_batch_size above
518+ let cursor_unit = if multi_column_sort {
519+ row_batch_size
520+ } else {
521+ ipc_batch_size
522+ } ;
523+
524+ // BatchBuilder needs to hold 3 Record batches simultaneously to merge two
525+ // streams (because a stream can cross a record batch boundary)
526+ // there is also one cursor needed per stream
527+ let mut max_peak = 3 * ipc_batch_size + 2 * cursor_unit + converter_size;
528+
529+ // with round robin enabled, 2 extra cursors live in memory
530+ // see https://github.com/apache/datafusion/issues/23604
531+ if round_robin {
532+ max_peak += 2 * cursor_unit;
533+ } ;
534+
535+ assert ! (
536+ peak_bytes > 0 ,
537+ "peak reservation {peak_bytes} should be greater than 0"
538+ ) ;
539+ assert ! (
540+ peak_bytes <= max_peak,
541+ "peak reservation {peak_bytes} bytes exceeds max_peak ({max_peak} bytes); \
542+ round_robin={round_robin}, multi_column_sort={multi_column_sort}",
543+ ) ;
544+
545+ Ok ( ( ) )
546+ }
547+
293548struct RunTestWithLimitedMemoryArgs {
294549 pool_size : usize ,
295550 task_ctx : Arc < TaskContext > ,
0 commit comments