Skip to content

Commit a5ba530

Browse files
committed
fix: split multi-column sort runs into smaller batches under a memory limit
A multi-column merge holds the row-format keys of every sorted run's current batch. When the sort keys are most of each row, those keys are larger than the batches, and the merge needs more memory than the sort reserved while buffering them, so the sort fails with ResourcesExhausted instead of spilling. With a memory limit, sort the runs of a multi-column merge into batches of an eighth of `batch_size`, but at least 1024 rows. The merge output keeps `batch_size`, and sorts without a memory limit are unchanged. Closes apache#26940
1 parent d3ae55e commit a5ba530

2 files changed

Lines changed: 100 additions & 12 deletions

File tree

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

Lines changed: 37 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ use datafusion_common::{
5959
use datafusion_common_runtime::SpawnedTask;
6060
use datafusion_execution::TaskContext;
6161
use datafusion_execution::memory_pool::{
62-
MemoryConsumer, MemoryPool, MemoryReservation, MergeMemoryPool,
62+
MemoryConsumer, MemoryLimit, MemoryPool, MemoryReservation, MergeMemoryPool,
6363
};
6464
use datafusion_execution::runtime_env::RuntimeEnv;
6565
use datafusion_physical_expr::LexOrdering;
@@ -707,7 +707,8 @@ impl ExternalSorter {
707707
if self.in_mem_batches.len() == 1 {
708708
let batch = self.in_mem_batches.swap_remove(0);
709709
let reservation = self.reservation.take();
710-
let sorted_stream = self.sort_batch_stream(batch, reservation, None)?;
710+
let sorted_stream =
711+
self.sort_batch_stream(batch, reservation, None, self.batch_size)?;
711712
return Ok(self.observe_if_output(sorted_stream, is_output_stream));
712713
}
713714

@@ -724,7 +725,8 @@ impl ExternalSorter {
724725
.try_resize(get_reserved_bytes_for_record_batch(&batch)?)
725726
.map_err(Self::err_with_oom_context)?;
726727
let reservation = self.reservation.take();
727-
let sorted_stream = self.sort_batch_stream(batch, reservation, None)?;
728+
let sorted_stream =
729+
self.sort_batch_stream(batch, reservation, None, self.batch_size)?;
728730
return Ok(self.observe_if_output(sorted_stream, is_output_stream));
729731
}
730732

@@ -780,13 +782,19 @@ impl ExternalSorter {
780782
let (sizes, shared_input_size) = self.sort_run_sizes(&runs)?;
781783
let shared_input =
782784
shared_input_size.map(|size| Arc::new(self.reservation.split(size)));
785+
let batch_size = self.merge_run_batch_size();
783786
let jobs =
784787
runs.into_iter()
785788
.zip(sizes)
786789
.enumerate()
787790
.map(move |(index, (batch, size))| {
788791
let reservation = self.reservation.split(size);
789-
let sort = self.sort_run(batch, reservation, shared_input.clone())?;
792+
let sort = self.sort_run(
793+
batch,
794+
reservation,
795+
shared_input.clone(),
796+
batch_size,
797+
)?;
790798
let permits = Arc::clone(&concurrency.permits);
791799
Ok::<_, DataFusionError>(async move {
792800
let stream = Self::prepare_sort_run(sort, permits).await?;
@@ -968,11 +976,12 @@ impl ExternalSorter {
968976
let (sizes, shared_input_size) = self.sort_run_sizes(&runs)?;
969977
let shared_input =
970978
shared_input_size.map(|size| Arc::new(self.reservation.split(size)));
979+
let batch_size = self.merge_run_batch_size();
971980
runs.into_iter()
972981
.zip(sizes)
973982
.map(|(run, size)| {
974983
let reservation = self.reservation.split(size);
975-
self.sort_batch_stream(run, reservation, shared_input.clone())
984+
self.sort_batch_stream(run, reservation, shared_input.clone(), batch_size)
976985
})
977986
.collect()
978987
}
@@ -995,11 +1004,11 @@ impl ExternalSorter {
9951004
batch: RecordBatch,
9961005
reservation: MemoryReservation,
9971006
shared_input: Option<Arc<MemoryReservation>>,
1007+
batch_size: usize,
9981008
) -> Result<SendableRecordBatchStream> {
9991009
let schema = batch.schema();
1000-
let stream =
1001-
futures::stream::once(self.sort_run(batch, reservation, shared_input)?)
1002-
.try_flatten();
1010+
let sort = self.sort_run(batch, reservation, shared_input, batch_size)?;
1011+
let stream = futures::stream::once(sort).try_flatten();
10031012
Ok(Box::pin(RecordBatchStreamAdapter::new(schema, stream)))
10041013
}
10051014

@@ -1012,6 +1021,7 @@ impl ExternalSorter {
10121021
batch: RecordBatch,
10131022
reservation: MemoryReservation,
10141023
shared_input: Option<Arc<MemoryReservation>>,
1024+
batch_size: usize,
10151025
) -> Result<impl Future<Output = Result<SendableRecordBatchStream>> + Send + use<>>
10161026
{
10171027
let reserved_bytes = get_reserved_bytes_for_record_batch(&batch)?;
@@ -1024,7 +1034,6 @@ impl ExternalSorter {
10241034
}
10251035

10261036
let expressions = self.expr.clone();
1027-
let batch_size = self.batch_size;
10281037
let merge_pool = Arc::clone(&self.merge_pool);
10291038
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
10301039

@@ -1068,6 +1077,23 @@ impl ExternalSorter {
10681077
})
10691078
}
10701079

1080+
/// Batch size of the sorted runs that feed a merge. A multi-column merge holds
1081+
/// the row-format keys of every run's current batch at once, and these keys can
1082+
/// be larger than the batches. With a memory limit, runs therefore use an eighth
1083+
/// of `batch_size`, but at least 1024 rows to keep the per-batch merge cost
1084+
/// small. The merge output still uses `batch_size`.
1085+
fn merge_run_batch_size(&self) -> usize {
1086+
let limited = !matches!(
1087+
self.runtime.memory_pool.memory_limit(),
1088+
MemoryLimit::Infinite
1089+
);
1090+
if limited && self.expr.len() > 1 {
1091+
(self.batch_size / 8).max(1024).min(self.batch_size)
1092+
} else {
1093+
self.batch_size
1094+
}
1095+
}
1096+
10711097
/// If this sort may spill, pre-allocates
10721098
/// `sort_spill_reservation_bytes` of memory to guarantee memory
10731099
/// left for the in memory sort/merge.
@@ -2601,7 +2627,8 @@ mod tests {
26012627
let reservation = sorter.reservation.new_empty();
26022628
reservation.try_grow(get_reserved_bytes_for_record_batch(&batch)?)?;
26032629
let before = elapsed_compute.value();
2604-
let sort = sorter.sort_run(batch.clone(), reservation, None)?;
2630+
let sort =
2631+
sorter.sort_run(batch.clone(), reservation, None, sorter.batch_size)?;
26052632
assert_eq!(elapsed_compute.value(), before);
26062633

26072634
let stream = if spawned {

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

Lines changed: 63 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,8 +9,8 @@ use crate::metrics::ExecutionPlanMetricsSet;
99
use crate::spill::get_record_batch_memory_size;
1010
use crate::spill::spill_manager::GetSlicedSize;
1111
use arrow::array::{
12-
ArrayRef, Decimal128Array, DictionaryArray, Int8Array, Int64Array, StringArray,
13-
StringViewArray,
12+
ArrayRef, Decimal128Array, DictionaryArray, Int8Array, Int32Array, Int64Array,
13+
StringArray, StringViewArray,
1414
};
1515
use arrow::compute::{SortOptions, concat_batches};
1616
use arrow::datatypes::{DataType, Field, Int8Type, Schema};
@@ -679,6 +679,67 @@ 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.
685+
async fn check_merge_keys_larger_than_batches() -> Result<()> {
686+
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)])
697+
})
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.
705+
let capacity = MERGE_BYTES + 16 * get_reserved_bytes_for_record_batch(&batches[0])?;
706+
let pool = AdjustablePool::new(capacity);
707+
let runtime = RuntimeEnvBuilder::new()
708+
.with_memory_pool(Arc::clone(&pool) as Arc<dyn MemoryPool>)
709+
.build_arc()?;
710+
let mut sorter = ExternalSorter::new(
711+
0,
712+
Arc::clone(&schema),
713+
ordering.clone(),
714+
rows as usize,
715+
MERGE_BYTES,
716+
0,
717+
SpillCompression::Uncompressed,
718+
&ExecutionPlanMetricsSet::new(),
719+
Arc::clone(&runtime),
720+
)?;
721+
for batch in &batches {
722+
sorter.insert_batch(batch.clone()).await?;
723+
}
724+
assert!(sorter.spilled_before());
725+
let output: Vec<RecordBatch> = sorter.sort().await?.try_collect().await?;
726+
let expected = sort_batch(&concat_batches(&schema, &batches)?, &ordering, None)?;
727+
assert_eq!(concat_batches(&schema, &output)?, expected);
728+
drop(sorter);
729+
assert_released(&pool, &runtime).await;
730+
Ok(())
731+
}
732+
733+
#[tokio::test]
734+
async fn test_merge_keys_larger_than_batches() -> Result<()> {
735+
check_merge_keys_larger_than_batches().await
736+
}
737+
738+
#[tokio::test(flavor = "multi_thread", worker_threads = 2)]
739+
async fn test_merge_keys_larger_than_batches_multithreaded() -> Result<()> {
740+
check_merge_keys_larger_than_batches().await
741+
}
742+
682743
#[tokio::test]
683744
async fn test_single_batch_spill_preserves_workspace_after_limit_decreases() -> Result<()>
684745
{

0 commit comments

Comments
 (0)