Skip to content

Commit 24297ff

Browse files
fix: keep sort merge headroom only while sibling partitions read input
A partition that finishes last kept fan-in headroom for siblings that had already finished, and rewrote rows in an extra merge pass. Count the partitions of a SortExec still reading their input instead, and keep headroom only while another one is. Merges already in progress hold pool memory, so the existing pool check still covers them. Also add a SortExec-level test for the condition, and return the headroom test helper's struct directly.
1 parent ab2f232 commit 24297ff

3 files changed

Lines changed: 134 additions & 31 deletions

File tree

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

Lines changed: 7 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1534,11 +1534,11 @@ mod tests {
15341534
}
15351535

15361536
/// Headroom for others sharing `pool`, with or without sibling partitions.
1537-
fn headroom(pool: &Arc<dyn MemoryPool>, siblings: bool) -> Option<FanInHeadroom> {
1538-
Some(FanInHeadroom {
1537+
fn headroom(pool: &Arc<dyn MemoryPool>, siblings: bool) -> FanInHeadroom {
1538+
FanInHeadroom {
15391539
pool: Arc::clone(pool),
15401540
siblings,
1541-
})
1541+
}
15421542
}
15431543

15441544
#[rstest::rstest]
@@ -1564,9 +1564,7 @@ mod tests {
15641564
Arc::new(GreedyMemoryPool::new(13 * batch_memory));
15651565
let other = others.then(|| hold(&pool, 1)).transpose()?;
15661566
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
1567-
.with_fan_in_headroom(
1568-
with_headroom.then(|| headroom(&pool, siblings).unwrap()),
1569-
);
1567+
.with_fan_in_headroom(with_headroom.then(|| headroom(&pool, siblings)));
15701568
let mut reservation = builder.reservation.new_empty();
15711569
let SpillFilesToMerge::Ready(spills, buffer_len) =
15721570
builder.get_sorted_spill_files_to_merge(1, 2, &mut reservation, false)?
@@ -1599,7 +1597,7 @@ mod tests {
15991597
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(5 * batch_memory));
16001598
let other = hold(&pool, 1)?;
16011599
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
1602-
.with_fan_in_headroom(headroom(&pool, false));
1600+
.with_fan_in_headroom(Some(headroom(&pool, false)));
16031601
let mut reservation = builder.reservation.new_empty();
16041602
let SpillFilesToMerge::Ready(spills, _) =
16051603
builder.get_sorted_spill_files_to_merge(1, 2, &mut reservation, false)?
@@ -1651,7 +1649,7 @@ mod tests {
16511649
let pool: Arc<dyn MemoryPool> = Arc::clone(&merge_pool) as Arc<dyn MemoryPool>;
16521650
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
16531651
.with_merge_pool(Some(Arc::clone(&merge_pool)))
1654-
.with_fan_in_headroom(headroom(&parent, false));
1652+
.with_fan_in_headroom(Some(headroom(&parent, false)));
16551653
builder.reservation.try_grow(workspace)?;
16561654
merge_pool.retain(workspace);
16571655
builder.reservation.free();
@@ -1692,7 +1690,7 @@ mod tests {
16921690
let pool: Arc<dyn MemoryPool> = Arc::new(UnboundedMemoryPool::default());
16931691
let other = hold(&pool, 1)?;
16941692
let mut builder = build_merge_builder(spill_manager, schema, spills, &pool, 1)
1695-
.with_fan_in_headroom(headroom(&pool, false));
1693+
.with_fan_in_headroom(Some(headroom(&pool, false)));
16961694
let mut reservation = builder.reservation.new_empty();
16971695
let SpillFilesToMerge::Ready(spills, _) =
16981696
builder.get_sorted_spill_files_to_merge(1, 2, &mut reservation, false)?

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

Lines changed: 43 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
use std::fmt;
1010
use std::fmt::{Debug, Formatter};
1111
use std::future::Future;
12+
use std::sync::atomic::{AtomicUsize, Ordering};
1213
use std::sync::{Arc, OnceLock};
1314

1415
use parking_lot::RwLock;
@@ -309,9 +310,9 @@ struct ExternalSorter {
309310
/// How much memory to reserve for performing in-memory sort/merges
310311
/// prior to spilling.
311312
sort_spill_reservation_bytes: usize,
312-
/// Other partitions of this sort run alongside this one and share its
313-
/// memory pool.
314-
has_sibling_partitions: bool,
313+
/// Partitions of the owning `SortExec`, this one included, still reading
314+
/// their input. Each one will need memory from the pool this sort shares.
315+
partitions_reading_input: Arc<AtomicUsize>,
315316
/// Shared by the owning SortExec's partitions. Initialized on the runtime
316317
/// that polls the sort, which may differ from the one calling `execute`.
317318
sort_concurrency: Arc<OnceLock<SortConcurrency>>,
@@ -375,17 +376,25 @@ impl ExternalSorter {
375376
batch_size,
376377
sort_spill_reservation_bytes,
377378
sort_in_place_threshold_bytes,
378-
has_sibling_partitions: false,
379+
partitions_reading_input: Arc::new(AtomicUsize::new(1)),
379380
sort_concurrency: Arc::new(OnceLock::new()),
380381
})
381382
}
382383

383-
/// Record whether other partitions of this sort share its memory pool.
384-
fn with_sibling_partitions(mut self, has_sibling_partitions: bool) -> Self {
385-
self.has_sibling_partitions = has_sibling_partitions;
384+
/// Share the count of partitions still reading their input with the
385+
/// other partitions of this sort. It must include this partition.
386+
fn with_partitions_reading_input(mut self, reading: Arc<AtomicUsize>) -> Self {
387+
self.partitions_reading_input = reading;
386388
self
387389
}
388390

391+
/// Records that this partition has read all its input, and returns whether
392+
/// another partition still reads its own. Executing partitions again
393+
/// without `reset_state` can wrap the count, which only keeps headroom.
394+
fn finish_reading_input(&self) -> bool {
395+
self.partitions_reading_input.fetch_sub(1, Ordering::AcqRel) > 1
396+
}
397+
389398
/// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
390399
///
391400
/// Updates memory usage metrics, and possibly triggers spilling to disk
@@ -416,6 +425,7 @@ impl ExternalSorter {
416425
/// 2. A combined streaming merge incorporating both in-memory
417426
/// batches and data from spill files on disk.
418427
async fn sort(&mut self) -> Result<SendableRecordBatchStream> {
428+
let other_partitions_reading = self.finish_reading_input();
419429
if self.spilled_before() {
420430
// Sort `in_mem_batches` and spill it first. If there are many
421431
// `in_mem_batches` and the memory limit is almost reached, merging
@@ -444,15 +454,17 @@ impl ExternalSorter {
444454
// Other partitions of this sort, still buffering input, share
445455
// the pool with this merge, and may hold nothing at the moment
446456
// it seats its runs. Seating every run the pool admits would
447-
// leave them nothing, so keep headroom while they exist or
448-
// anyone else holds memory in the pool. A lone partition with
449-
// the pool to itself seats every run that fits: the operator
450-
// consuming its output reserves nothing before its first
451-
// batch, and keeping headroom for it would cost an extra merge
452-
// pass whether or not it ever needs the memory.
457+
// leave them nothing, so keep headroom while any of them is
458+
// still reading or anyone else holds memory in the pool;
459+
// partitions already merging hold memory, so the second check
460+
// covers them. A lone partition, or the last one to finish
461+
// reading, with the pool to itself seats every run that fits:
462+
// the operator consuming its output reserves nothing before
463+
// its first batch, and keeping headroom for it would cost an
464+
// extra merge pass whether or not it ever needs the memory.
453465
.with_fan_in_headroom(
454466
Arc::clone(&self.runtime.memory_pool),
455-
self.has_sibling_partitions,
467+
other_partitions_reading,
456468
)
457469
.build()
458470
} else {
@@ -1349,6 +1361,10 @@ pub struct SortExec {
13491361
/// Batch-sort limit shared by partitions and clones.
13501362
/// `reset_state` returns a new plan with a fresh limit.
13511363
sort_concurrency: Arc<OnceLock<SortConcurrency>>,
1364+
/// Partitions still reading their input, shared with their sorters. Set
1365+
/// on the first `execute`, once the input can no longer change.
1366+
/// `reset_state` returns a new plan with a fresh count.
1367+
partitions_reading_input: Arc<OnceLock<Arc<AtomicUsize>>>,
13521368
}
13531369

13541370
impl SortExec {
@@ -1369,6 +1385,7 @@ impl SortExec {
13691385
cache: Arc::new(cache),
13701386
filter: None,
13711387
sort_concurrency: Arc::new(OnceLock::new()),
1388+
partitions_reading_input: Arc::new(OnceLock::new()),
13721389
}
13731390
}
13741391

@@ -1446,6 +1463,7 @@ impl SortExec {
14461463
cache: Arc::clone(&self.cache),
14471464
filter: self.filter.clone(),
14481465
sort_concurrency: Arc::clone(&self.sort_concurrency),
1466+
partitions_reading_input: Arc::clone(&self.partitions_reading_input),
14491467
}
14501468
}
14511469

@@ -1776,14 +1794,15 @@ impl ExecutionPlan for SortExec {
17761794
.downcast_ref::<SortExec>()
17771795
.expect("rebuilt SortExec with new children")
17781796
.clone();
1779-
// Our dynamic filter, execution metrics and sort concurrency are the state
1780-
// we need to reset.
1797+
// Our dynamic filter, execution metrics, sort concurrency and count of
1798+
// partitions reading input are the state we need to reset.
17811799
if let Some(filter) = &new_sort.filter {
17821800
filter.read().expr().reset();
17831801
new_sort.filter = Some(new_sort.create_filter());
17841802
}
17851803
new_sort.metrics_set = ExecutionPlanMetricsSet::new();
17861804
new_sort.sort_concurrency = Arc::new(OnceLock::new());
1805+
new_sort.partitions_reading_input = Arc::new(OnceLock::new());
17871806

17881807
Ok(Arc::new(new_sort))
17891808
}
@@ -1865,9 +1884,13 @@ impl ExecutionPlan for SortExec {
18651884
&self.metrics_set,
18661885
context.runtime_env(),
18671886
)?
1868-
.with_sibling_partitions(
1869-
self.input.output_partitioning().partition_count() > 1,
1870-
);
1887+
.with_partitions_reading_input(Arc::clone(
1888+
self.partitions_reading_input.get_or_init(|| {
1889+
Arc::new(AtomicUsize::new(
1890+
self.input.output_partitioning().partition_count(),
1891+
))
1892+
}),
1893+
));
18711894
sorter.sort_concurrency = Arc::clone(&self.sort_concurrency);
18721895
Ok(Box::pin(RecordBatchStreamAdapter::new(
18731896
self.schema(),
@@ -2070,6 +2093,7 @@ impl ExecutionPlan for SortExec {
20702093
filter,
20712094
// Execution state, initialized on the runtime polling the decoded plan.
20722095
sort_concurrency: _,
2096+
partitions_reading_input: _,
20732097
} = self;
20742098
let input = ctx.encode_child(input)?;
20752099
let expr = expr

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

Lines changed: 84 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,12 +3,14 @@
33
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
44

55
use super::{
6-
ExternalSorter, get_reserved_bytes_for_record_batch,
6+
ExternalSorter, SortExec, get_reserved_bytes_for_record_batch,
77
get_reserved_bytes_for_record_batch_size, sort_batch, sort_batch_chunked,
88
};
9+
use crate::ExecutionPlan;
910
use crate::metrics::ExecutionPlanMetricsSet;
1011
use crate::spill::get_record_batch_memory_size;
1112
use crate::spill::spill_manager::GetSlicedSize;
13+
use crate::test::TestMemoryExec;
1214
use arrow::array::{
1315
ArrayRef, Decimal128Array, DictionaryArray, Int8Array, Int64Array, StringArray,
1416
StringViewArray,
@@ -18,6 +20,8 @@ use arrow::datatypes::{DataType, Field, Int8Type, Schema};
1820
use arrow::record_batch::RecordBatch;
1921
use datafusion_common::config::{ExecutionOptions, SpillCompression};
2022
use datafusion_common::{DataFusionError, Result};
23+
use datafusion_execution::TaskContext;
24+
use datafusion_execution::config::SessionConfig;
2125
use datafusion_execution::disk_manager::{DiskManagerBuilder, DiskManagerMode};
2226
use datafusion_execution::memory_pool::{
2327
GreedyMemoryPool, MemoryConsumer, MemoryLimit, MemoryPool, MemoryReservation,
@@ -27,6 +31,7 @@ use datafusion_physical_expr::expressions::Column;
2731
use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr};
2832
use futures::TryStreamExt;
2933
use std::fmt::{Display, Formatter};
34+
use std::sync::atomic::AtomicUsize;
3035
use std::sync::{Arc, Mutex};
3136
use std::time::Duration;
3237

@@ -1208,7 +1213,7 @@ async fn test_single_batch_spill_returns_live_workspace_loan_on_drop() -> Result
12081213
/// still sorting their input. Seating every run the pool admits leaves them
12091214
/// nothing, so whatever the merge takes beyond its own workspace, it must leave
12101215
/// as much free: while another consumer holds memory, and while sibling
1211-
/// partitions exist even if they hold nothing at the moment.
1216+
/// partitions still read their input even if they hold nothing at the moment.
12121217
#[rstest::rstest]
12131218
#[case::other_consumer_holds_memory(false)]
12141219
#[case::idle_sibling_partitions(true)]
@@ -1221,7 +1226,9 @@ async fn test_final_spilled_merge_leaves_headroom(#[case] siblings: bool) -> Res
12211226
// Spill under the fixture's limit, then merge with room for every run.
12221227
pool.set_limit(fixture.capacity);
12231228
let (sorter, runtime) = sorter(&fixture, Arc::clone(&pool))?;
1224-
let mut sorter = sorter.with_sibling_partitions(siblings);
1229+
let mut sorter = sorter.with_partitions_reading_input(Arc::new(AtomicUsize::new(
1230+
1 + usize::from(siblings),
1231+
)));
12251232
for batch in &fixture.batches {
12261233
sorter.insert_batch(batch.clone()).await?;
12271234
}
@@ -1287,3 +1294,77 @@ async fn test_final_spilled_merge_leaves_headroom(#[case] siblings: bool) -> Res
12871294
assert_released(&pool, &runtime).await;
12881295
Ok(())
12891296
}
1297+
1298+
/// Whether a `SortExec` keeps fan-in headroom follows its partitions still
1299+
/// reading input. The pool fits every run's buffers but not the headroom on
1300+
/// top, so with headroom the final merge seats fewer runs and rewrites rows in
1301+
/// an extra pass. Partition 0 runs alone, so nothing else ever holds pool
1302+
/// memory and the outcome is deterministic. In the last case its sibling has
1303+
/// already read all its input, so there is nobody to keep headroom for.
1304+
#[rstest::rstest]
1305+
#[case::lone_partition(1, false, false)]
1306+
#[case::idle_sibling(2, false, true)]
1307+
#[case::finished_sibling(2, true, false)]
1308+
#[tokio::test]
1309+
async fn test_sort_exec_keeps_headroom_only_while_siblings_read_input(
1310+
#[case] input_partitions: usize,
1311+
#[case] finish_sibling_first: bool,
1312+
#[case] rewrites_rows: bool,
1313+
) -> Result<()> {
1314+
let schema = Arc::new(Schema::new(vec![
1315+
Field::new("key", DataType::Int64, false),
1316+
Field::new("payload", DataType::Utf8, false),
1317+
]));
1318+
let (batches, rows) = (64, 1024);
1319+
let batches = (0..batches)
1320+
.map(|batch| {
1321+
let keys = (0..rows).map(|row| ((batch * rows + row) * 2654435761) % 1000003);
1322+
let payload = (0..rows).map(|row| format!("{row:0120}"));
1323+
let columns: Vec<ArrayRef> = vec![
1324+
Arc::new(Int64Array::from_iter_values(keys)),
1325+
Arc::new(StringArray::from_iter_values(payload)),
1326+
];
1327+
Ok(RecordBatch::try_new(Arc::clone(&schema), columns)?)
1328+
})
1329+
.collect::<Result<Vec<_>>>()?;
1330+
let total_rows: usize = batches.iter().map(RecordBatch::num_rows).sum();
1331+
let mut partitions = vec![batches];
1332+
partitions.resize(input_partitions, vec![]);
1333+
let input = TestMemoryExec::try_new_exec(&partitions, Arc::clone(&schema), None)?;
1334+
let ordering: LexOrdering = [PhysicalSortExpr::new_default(Arc::new(Column::new(
1335+
"key", 0,
1336+
)))]
1337+
.into();
1338+
let sort = SortExec::new(ordering, input).with_preserve_partitioning(true);
1339+
let runtime = RuntimeEnvBuilder::new()
1340+
.with_memory_pool(Arc::new(GreedyMemoryPool::new(3500 * 1024)))
1341+
.build_arc()?;
1342+
let context = Arc::new(
1343+
TaskContext::default()
1344+
.with_session_config(
1345+
SessionConfig::new()
1346+
.with_batch_size(1024)
1347+
.with_sort_spill_reservation_bytes(128 * 1024),
1348+
)
1349+
.with_runtime(runtime),
1350+
);
1351+
1352+
if finish_sibling_first {
1353+
let sibling: Vec<RecordBatch> =
1354+
sort.execute(1, Arc::clone(&context))?.try_collect().await?;
1355+
assert!(sibling.is_empty());
1356+
}
1357+
let output: Vec<RecordBatch> = sort.execute(0, context)?.try_collect().await?;
1358+
1359+
assert_eq!(
1360+
output.iter().map(RecordBatch::num_rows).sum::<usize>(),
1361+
total_rows
1362+
);
1363+
let spilled_rows = sort.metrics().unwrap().spilled_rows().unwrap();
1364+
if rewrites_rows {
1365+
assert!(spilled_rows > total_rows, "{spilled_rows} <= {total_rows}");
1366+
} else {
1367+
assert_eq!(spilled_rows, total_rows);
1368+
}
1369+
Ok(())
1370+
}

0 commit comments

Comments
 (0)