Skip to content

Commit c7c5b19

Browse files
fix: keep spill merge headroom only when the pool is shared
The fan-in headroom made a lone sort partition that has the pool to itself rewrite runs in an extra merge pass, for no one: with 60 x 8192 rows of Int64 plus a 120-byte string, 1 MB sort_spill_reservation_bytes and a 16 MB GreedyMemoryPool, it wrote 1,589,248 rows to spill instead of 983,040. Keep the headroom only while the sort has other partitions sharing the pool, or another consumer holds memory in it. Sibling partitions count even when they hold nothing at the moment the merge seats its runs. The operator consuming the output of a lone partition is not counted: it reserves nothing before its first batch, and keeping headroom for it would cost the extra pass whether or not it ever needs the memory. With one partition, the case above writes the same rows as without headroom in all four configurations measured. With four partitions in a 32 MB pool and 1 MB reservations, the sort fails with "Not enough memory to continue external sort" without headroom and succeeds with it. Also cover the minimum two runs under a budget below their headroom, and seating against a retained merge workspace on both sides of 2 * (T - W).
1 parent 5c59c07 commit c7c5b19

4 files changed

Lines changed: 235 additions & 44 deletions

File tree

‎datafusion/physical-plan/src/sorts/multi_level_merge.rs‎

Lines changed: 166 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,24 @@ use datafusion_physical_expr_common::sort_expr::LexOrdering;
4141
use futures::TryStreamExt;
4242
use 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
}

‎datafusion/physical-plan/src/sorts/sort.rs‎

Lines changed: 27 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -272,6 +272,9 @@ struct ExternalSorter {
272272
/// How much memory to reserve for performing in-memory sort/merges
273273
/// prior to spilling.
274274
sort_spill_reservation_bytes: usize,
275+
/// Other partitions of this sort run alongside this one and share its
276+
/// memory pool.
277+
has_sibling_partitions: bool,
275278
}
276279

277280
impl ExternalSorter {
@@ -325,9 +328,16 @@ impl ExternalSorter {
325328
batch_size,
326329
sort_spill_reservation_bytes,
327330
sort_in_place_threshold_bytes,
331+
has_sibling_partitions: false,
328332
})
329333
}
330334

335+
/// Record whether other partitions of this sort share its memory pool.
336+
fn with_sibling_partitions(mut self, has_sibling_partitions: bool) -> Self {
337+
self.has_sibling_partitions = has_sibling_partitions;
338+
self
339+
}
340+
331341
/// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
332342
///
333343
/// Updates memory usage metrics, and possibly triggers spilling to disk
@@ -383,11 +393,19 @@ impl ExternalSorter {
383393
.with_fetch(None)
384394
.with_reservation(self.merge_reservation.take())
385395
.with_merge_pool(Arc::clone(&self.merge_pool))
386-
// The operator consuming the sorted output, and the other
387-
// partitions of this sort still buffering input, share the
388-
// pool with this merge. Seating every run the pool admits
389-
// would leave them nothing.
390-
.with_fan_in_headroom()
396+
// Other partitions of this sort, still buffering input, share
397+
// the pool with this merge, and may hold nothing at the moment
398+
// it seats its runs. Seating every run the pool admits would
399+
// leave them nothing, so keep headroom while they exist or
400+
// anyone else holds memory in the pool. A lone partition with
401+
// the pool to itself seats every run that fits: the operator
402+
// consuming its output reserves nothing before its first
403+
// batch, and keeping headroom for it would cost an extra merge
404+
// pass whether or not it ever needs the memory.
405+
.with_fan_in_headroom(
406+
Arc::clone(&self.runtime.memory_pool),
407+
self.has_sibling_partitions,
408+
)
391409
.build()
392410
} else {
393411
// Final output needs no reserve for future spills. Return unused
@@ -1522,7 +1540,10 @@ impl ExecutionPlan for SortExec {
15221540
context.session_config().spill_compression(),
15231541
&self.metrics_set,
15241542
context.runtime_env(),
1525-
)?;
1543+
)?
1544+
.with_sibling_partitions(
1545+
self.input.output_partitioning().partition_count() > 1,
1546+
);
15261547
Ok(Box::pin(RecordBatchStreamAdapter::new(
15271548
self.schema(),
15281549
futures::stream::once(async move {

0 commit comments

Comments
 (0)