@@ -41,6 +41,24 @@ use datafusion_physical_expr_common::sort_expr::LexOrdering;
4141use futures:: TryStreamExt ;
4242use futures:: { Stream , StreamExt } ;
4343
44+ /// Leave memory for others sharing the execution pool when a merge seats
45+ /// more than the minimum two runs.
46+ #[ derive( Debug , Clone ) ]
47+ pub ( crate ) struct FanInHeadroom {
48+ /// The execution pool: the parent of the merge pool when there is one.
49+ pub ( crate ) pool : Arc < dyn MemoryPool > ,
50+ /// Other partitions share `pool`, even if they hold nothing right now.
51+ pub ( crate ) siblings : bool ,
52+ }
53+
54+ impl FanInHeadroom {
55+ /// Whether another consumer may need the pool: sibling partitions exist,
56+ /// or the pool holds more than the `owned` bytes this merge holds in it.
57+ fn is_contended ( & self , owned : usize ) -> bool {
58+ self . siblings || self . pool . reserved ( ) > owned
59+ }
60+ }
61+
4462/// Merges a stream of sorted cursors and record batches into a single sorted stream
4563///
4664/// This is a wrapper around [`SortPreservingMergeStream`](crate::sorts::merge::SortPreservingMergeStream)
@@ -159,10 +177,11 @@ pub(crate) struct MultiLevelMergeBuilder {
159177 merge_pool : Option < Arc < MergeMemoryPool > > ,
160178 /// Leave memory for the aggregate consuming the merged spill rows.
161179 reserve_replay_headroom : bool ,
162- /// Seat runs beyond the minimum two only while the pool can admit their
163- /// buffers plus equal headroom, so a merge does not take memory that the
164- /// operator consuming it and other partitions sharing the pool need.
165- reserve_fan_in_headroom : bool ,
180+ /// When set and the pool is shared, seat runs beyond the minimum two only
181+ /// if the pool can admit their buffers plus as much again as they exceed
182+ /// the retained workspace, so a merge does not take the memory that other
183+ /// partitions sharing the pool need.
184+ fan_in_headroom : Option < FanInHeadroom > ,
166185 /// Avoid merging more runs than needed before the final replay pass.
167186 size_intermediate_merges : bool ,
168187 fetch : Option < usize > ,
@@ -205,7 +224,7 @@ impl MultiLevelMergeBuilder {
205224 reservation,
206225 merge_pool : None ,
207226 reserve_replay_headroom : false ,
208- reserve_fan_in_headroom : false ,
227+ fan_in_headroom : None ,
209228 size_intermediate_merges : false ,
210229 enable_round_robin_tie_breaker,
211230 fetch,
@@ -224,10 +243,14 @@ impl MultiLevelMergeBuilder {
224243 self
225244 }
226245
227- /// Leave headroom when seating runs beyond the minimum two. The minimum
228- /// merge is admitted against the pool alone, as without headroom.
229- pub ( super ) fn with_fan_in_headroom ( mut self , reserve : bool ) -> Self {
230- self . reserve_fan_in_headroom = reserve;
246+ /// Leave headroom when seating runs beyond the minimum two while the pool
247+ /// is shared. The minimum merge is admitted against the pool alone, as
248+ /// without headroom.
249+ pub ( super ) fn with_fan_in_headroom (
250+ mut self ,
251+ headroom : Option < FanInHeadroom > ,
252+ ) -> Self {
253+ self . fan_in_headroom = headroom;
231254 self
232255 }
233256
@@ -604,6 +627,14 @@ impl MultiLevelMergeBuilder {
604627 . merge_pool
605628 . as_ref ( )
606629 . map_or_else ( || reservation. size ( ) , |pool| pool. reserved ( ) ) ;
630+ // Headroom is for others sharing the pool. With no sibling partitions
631+ // and nobody else holding memory in it, seat every run that fits, as
632+ // without headroom, rather than rewrite runs in an extra merge pass
633+ // for no one.
634+ let fan_in_contended = self
635+ . fan_in_headroom
636+ . as_ref ( )
637+ . is_some_and ( |headroom| headroom. is_contended ( owned) ) ;
607638
608639 for ( spill, _) in & self . sorted_spill_files {
609640 if number_of_spills_to_read_for_current_phase >= max_spill_files
@@ -630,7 +661,7 @@ impl MultiLevelMergeBuilder {
630661 < minimum_number_of_required_streams;
631662 let check_headroom = self . reserve_replay_headroom && !skip_headroom;
632663 let check_fan_in_headroom = !check_headroom
633- && self . reserve_fan_in_headroom
664+ && fan_in_contended
634665 && number_of_spills_to_read_for_current_phase
635666 >= minimum_number_of_required_streams;
636667 let admission = if check_fan_in_headroom {
@@ -710,7 +741,7 @@ impl MultiLevelMergeBuilder {
710741 }
711742 }
712743
713- if self . reserve_replay_headroom || self . reserve_fan_in_headroom {
744+ if self . reserve_replay_headroom || fan_in_contended {
714745 // `total_needed` may include a rejected candidate. Keep only the
715746 // buffers that were admitted, releasing temporary replay headroom.
716747 reservation. shrink ( reservation. size ( ) - accepted_memory) ;
@@ -1507,11 +1538,31 @@ mod tests {
15071538 Ok ( ( ) )
15081539 }
15091540
1541+ /// Registers a consumer holding `size` bytes of `pool`, so a merge sharing
1542+ /// it sees another user and leaves headroom.
1543+ fn hold ( pool : & Arc < dyn MemoryPool > , size : usize ) -> Result < MemoryReservation > {
1544+ let other = MemoryConsumer :: new ( "other consumer" ) . register ( pool) ;
1545+ other. try_grow ( size) ?;
1546+ Ok ( other)
1547+ }
1548+
1549+ /// Headroom for others sharing `pool`, with or without sibling partitions.
1550+ fn headroom ( pool : & Arc < dyn MemoryPool > , siblings : bool ) -> Option < FanInHeadroom > {
1551+ Some ( FanInHeadroom {
1552+ pool : Arc :: clone ( pool) ,
1553+ siblings,
1554+ } )
1555+ }
1556+
15101557 #[ rstest:: rstest]
1511- #[ case:: without_headroom( false , 4 , 8 ) ]
1512- #[ case:: with_headroom( true , 3 , 6 ) ]
1558+ #[ case:: without_headroom( false , true , false , 4 , 8 ) ]
1559+ #[ case:: headroom_without_others( true , false , false , 4 , 8 ) ]
1560+ #[ case:: headroom_with_others( true , true , false , 3 , 6 ) ]
1561+ #[ case:: headroom_with_idle_siblings( true , false , true , 3 , 6 ) ]
15131562 fn fan_in_headroom_limits_runs_beyond_the_minimum (
1514- #[ case] headroom : bool ,
1563+ #[ case] with_headroom : bool ,
1564+ #[ case] others : bool ,
1565+ #[ case] siblings : bool ,
15151566 #[ case] seated : usize ,
15161567 #[ case] retained_batches : usize ,
15171568 ) -> Result < ( ) > {
@@ -1524,8 +1575,11 @@ mod tests {
15241575 let batch_memory = spills[ 0 ] . max_record_batch_memory ;
15251576 let pool: Arc < dyn MemoryPool > =
15261577 Arc :: new ( GreedyMemoryPool :: new ( 13 * batch_memory) ) ;
1578+ let other = others. then ( || hold ( & pool, 1 ) ) . transpose ( ) ?;
15271579 let mut builder = build_merge_builder ( spill_manager, schema, spills, & pool, 1 )
1528- . with_fan_in_headroom ( headroom) ;
1580+ . with_fan_in_headroom (
1581+ with_headroom. then ( || headroom ( & pool, siblings) . unwrap ( ) ) ,
1582+ ) ;
15291583 let mut reservation = builder. reservation . new_empty ( ) ;
15301584 let SpillFilesToMerge :: Ready ( spills, buffer_len) =
15311585 builder. get_sorted_spill_files_to_merge ( 1 , 2 , & mut reservation, false ) ?
@@ -1534,14 +1588,106 @@ mod tests {
15341588 } ;
15351589 assert_eq ! ( buffer_len, 1 ) ;
15361590 // Each run takes two batches. With headroom, the third run needs 12
1537- // batches and is seated; the fourth needs 16 and is not.
1591+ // batches and is seated; the fourth needs 16 and is not. When nobody
1592+ // else holds memory and there are no sibling partitions, all four are
1593+ // seated, as without headroom.
15381594 assert_eq ! ( spills. len( ) , seated) ;
15391595 assert_eq ! ( reservation. size( ) , retained_batches * batch_memory) ;
1540- drop ( ( reservation, spills, builder) ) ;
1596+ drop ( ( reservation, spills, builder, other ) ) ;
15411597 assert_eq ! ( pool. reserved( ) , 0 ) ;
15421598 Ok ( ( ) )
15431599 }
15441600
1601+ /// The minimum two runs are admitted against the pool alone, even when
1602+ /// their buffers plus headroom would not fit.
1603+ #[ test]
1604+ fn fan_in_headroom_admits_the_minimum_merge_without_headroom ( ) -> Result < ( ) > {
1605+ let env = Arc :: new ( RuntimeEnv :: default ( ) ) ;
1606+ let schema = test_schema ( ) ;
1607+ let spill_manager = build_spill_manager ( & env, & schema) ;
1608+ let spills = ( 0 ..3 )
1609+ . map ( |value| make_sorted_spill_file ( & spill_manager, & schema, vec ! [ value] ) )
1610+ . collect :: < Vec < _ > > ( ) ;
1611+ let batch_memory = spills[ 0 ] . max_record_batch_memory ;
1612+ let pool: Arc < dyn MemoryPool > = Arc :: new ( GreedyMemoryPool :: new ( 5 * batch_memory) ) ;
1613+ let other = hold ( & pool, 1 ) ?;
1614+ let mut builder = build_merge_builder ( spill_manager, schema, spills, & pool, 1 )
1615+ . with_fan_in_headroom ( headroom ( & pool, false ) ) ;
1616+ let mut reservation = builder. reservation . new_empty ( ) ;
1617+ let SpillFilesToMerge :: Ready ( spills, _) =
1618+ builder. get_sorted_spill_files_to_merge ( 1 , 2 , & mut reservation, false ) ?
1619+ else {
1620+ panic ! ( "the minimum merge should fit the pool" ) ;
1621+ } ;
1622+ // Two runs take four batches; with headroom they would take eight. The
1623+ // third would take twelve.
1624+ assert_eq ! ( spills. len( ) , 2 ) ;
1625+ assert_eq ! ( reservation. size( ) , 4 * batch_memory) ;
1626+ drop ( ( reservation, spills, builder, other) ) ;
1627+ assert_eq ! ( pool. reserved( ) , 0 ) ;
1628+ Ok ( ( ) )
1629+ }
1630+
1631+ /// With a retained workspace `W`, seating the third run, for buffers `T`
1632+ /// in all, asks the parent for `2 * (T - W)` more, and nothing when
1633+ /// `T <= W`. Afterwards the child holds `T` and the parent is charged
1634+ /// `max(W, T)`.
1635+ #[ rstest:: rstest]
1636+ #[ case:: runs_within_workspace( 6 , 0 , 0 , 3 ) ]
1637+ #[ case:: runs_below_workspace( 8 , 0 , 0 , 3 ) ]
1638+ #[ case:: exactly_the_headroom( 2 , 8 , 0 , 3 ) ]
1639+ #[ case:: just_below_the_headroom( 2 , 8 , 1 , 2 ) ]
1640+ fn fan_in_headroom_counts_the_retained_workspace (
1641+ #[ case] workspace_batches : usize ,
1642+ #[ case] free_batches : usize ,
1643+ #[ case] short_by_bytes : usize ,
1644+ #[ case] seated : usize ,
1645+ ) -> Result < ( ) > {
1646+ let env = Arc :: new ( RuntimeEnv :: default ( ) ) ;
1647+ let schema = test_schema ( ) ;
1648+ let spill_manager = build_spill_manager ( & env, & schema) ;
1649+ let spills = ( 0 ..3 )
1650+ . map ( |value| make_sorted_spill_file ( & spill_manager, & schema, vec ! [ value] ) )
1651+ . collect :: < Vec < _ > > ( ) ;
1652+ let batch_memory = spills[ 0 ] . max_record_batch_memory ;
1653+ let per_run =
1654+ get_reserved_bytes_for_record_batch_size ( batch_memory, batch_memory) ;
1655+ assert_eq ! ( per_run, 2 * batch_memory) ;
1656+ let workspace = workspace_batches * batch_memory;
1657+ let free = free_batches * batch_memory - short_by_bytes;
1658+ let capacity = 32 * batch_memory;
1659+ let parent: Arc < dyn MemoryPool > = Arc :: new ( GreedyMemoryPool :: new ( capacity) ) ;
1660+ let merge_pool = Arc :: new ( MergeMemoryPool :: new (
1661+ Arc :: clone ( & parent) ,
1662+ MemoryConsumer :: new ( "merge workspace" ) ,
1663+ ) ) ;
1664+ let pool: Arc < dyn MemoryPool > = Arc :: clone ( & merge_pool) as Arc < dyn MemoryPool > ;
1665+ let mut builder = build_merge_builder ( spill_manager, schema, spills, & pool, 1 )
1666+ . with_merge_pool ( Some ( Arc :: clone ( & merge_pool) ) )
1667+ . with_fan_in_headroom ( headroom ( & parent, false ) ) ;
1668+ builder. reservation . try_grow ( workspace) ?;
1669+ merge_pool. retain ( workspace) ;
1670+ builder. reservation . free ( ) ;
1671+ assert_eq ! ( merge_pool. reserved( ) , workspace) ;
1672+ let other = hold ( & parent, capacity - workspace - free) ?;
1673+
1674+ let mut reservation = builder. reservation . new_empty ( ) ;
1675+ let SpillFilesToMerge :: Ready ( spills, _) =
1676+ builder. get_sorted_spill_files_to_merge ( 1 , 2 , & mut reservation, false ) ?
1677+ else {
1678+ panic ! ( "the minimum merge should fit the pool" ) ;
1679+ } ;
1680+ assert_eq ! ( spills. len( ) , seated) ;
1681+ let total = seated * per_run;
1682+ assert_eq ! ( reservation. size( ) , total) ;
1683+ assert_eq ! ( merge_pool. reserved( ) , workspace. max( total) ) ;
1684+ assert_eq ! ( parent. reserved( ) , other. size( ) + workspace. max( total) ) ;
1685+ drop ( ( reservation, spills, builder, other) ) ;
1686+ merge_pool. release_unused ( ) ;
1687+ assert_eq ! ( parent. reserved( ) , 0 ) ;
1688+ Ok ( ( ) )
1689+ }
1690+
15451691 #[ test]
15461692 fn fan_in_headroom_beyond_usize_stops_seating_runs ( ) -> Result < ( ) > {
15471693 let env = Arc :: new ( RuntimeEnv :: default ( ) ) ;
@@ -1557,8 +1703,9 @@ mod tests {
15571703 } )
15581704 . collect :: < Vec < _ > > ( ) ;
15591705 let pool: Arc < dyn MemoryPool > = Arc :: new ( UnboundedMemoryPool :: default ( ) ) ;
1706+ let other = hold ( & pool, 1 ) ?;
15601707 let mut builder = build_merge_builder ( spill_manager, schema, spills, & pool, 1 )
1561- . with_fan_in_headroom ( true ) ;
1708+ . with_fan_in_headroom ( headroom ( & pool , false ) ) ;
15621709 let mut reservation = builder. reservation . new_empty ( ) ;
15631710 let SpillFilesToMerge :: Ready ( spills, _) =
15641711 builder. get_sorted_spill_files_to_merge ( 1 , 2 , & mut reservation, false ) ?
@@ -1567,7 +1714,7 @@ mod tests {
15671714 } ;
15681715 assert_eq ! ( spills. len( ) , 2 ) ;
15691716 assert_eq ! ( reservation. size( ) , 4 * batch_memory) ;
1570- drop ( ( reservation, spills, builder) ) ;
1717+ drop ( ( reservation, spills, builder, other ) ) ;
15711718 assert_eq ! ( pool. reserved( ) , 0 ) ;
15721719 Ok ( ( ) )
15731720 }
0 commit comments