Skip to content

Commit 571f7f9

Browse files
committed
fix: split runs for every row-format merge without raising their charge
- Split runs whenever the merge uses the row format, including a single key without a specialized cursor, such as `FixedSizeBinary`. - Compact the view arrays of split runs, so each batch is charged for its own strings rather than for the run's whole data buffers. - Keep `batch_size` when split batches would still share buffers, such as dictionary values.
1 parent b02c75e commit 571f7f9

3 files changed

Lines changed: 116 additions & 34 deletions

File tree

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

Lines changed: 29 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -30,10 +30,12 @@ use crate::metrics::{
3030
};
3131
use crate::projection::{ProjectionExec, make_with_child, update_ordering};
3232
use crate::sorts::IncrementalSortIterator;
33-
use crate::sorts::streaming_merge::{SortedSpillFile, StreamingMergeBuilder};
34-
use crate::spill::get_record_batch_memory_size;
33+
use crate::sorts::streaming_merge::{
34+
SortedSpillFile, StreamingMergeBuilder, merges_in_row_format,
35+
};
3536
use crate::spill::in_progress_spill_file::InProgressSpillFile;
3637
use crate::spill::spill_manager::{GetSlicedSize, SpillManager};
38+
use crate::spill::{gc_view_arrays, get_record_batch_memory_size};
3739
use crate::statistics::{ChildStats, StatisticsArgs, with_per_partition_fetch};
3840
use crate::stream::ReservationStream;
3941
use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
@@ -1035,6 +1037,8 @@ impl ExternalSorter {
10351037
let expressions = self.expr.clone();
10361038
let merge_pool = Arc::clone(&self.merge_pool);
10371039
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
1040+
// Set when `merge_run_batch_size` split this run
1041+
let split = batch_size < self.batch_size;
10381042

10391043
Ok(async move {
10401044
// Held until `batch` is sorted, when this block ends. The last run to
@@ -1045,7 +1049,16 @@ impl ExternalSorter {
10451049
let schema = batch.schema();
10461050

10471051
// Sort the batch immediately and get all output batches
1048-
let sorted_batches = sort_batch_chunked(&batch, &expressions, batch_size)?;
1052+
let mut sorted_batches =
1053+
sort_batch_chunked(&batch, &expressions, batch_size)?;
1054+
// `take` keeps the data buffers of view arrays, so splitting would
1055+
// charge every batch for all of them.
1056+
if split && sorted_batches.len() > 1 {
1057+
sorted_batches = sorted_batches
1058+
.iter()
1059+
.map(gc_view_arrays)
1060+
.collect::<Result<_>>()?;
1061+
}
10491062

10501063
// Chunked output can retain shared buffers in every batch and
10511064
// exceed the input estimate. Borrow only already-reserved spill
@@ -1087,17 +1100,25 @@ impl ExternalSorter {
10871100
})
10881101
}
10891102

1090-
/// Batch size of the sorted runs that feed a merge. A multi-column merge holds
1091-
/// the row-format keys of every run's current batch at once, and these keys can
1092-
/// be larger than the batches. With a memory limit, runs therefore use an eighth
1103+
/// Batch size of the sorted runs that feed a merge. A merge in the row format
1104+
/// holds the keys of every run's current batch at once, and these keys can be
1105+
/// larger than the batches. With a memory limit, runs therefore use an eighth
10931106
/// of `batch_size`, but at least 1024 rows to keep the per-batch merge cost
1094-
/// small. The merge output still uses `batch_size`.
1107+
/// small. The merge output still uses `batch_size`. Runs keep `batch_size`
1108+
/// when their batches would share buffers other than the data of top-level
1109+
/// view columns, such as dictionary values, since every batch is charged for
1110+
/// them.
10951111
fn merge_run_batch_size(&self) -> usize {
10961112
let limited = !matches!(
10971113
self.runtime.memory_pool.memory_limit(),
10981114
MemoryLimit::Infinite
10991115
);
1100-
if limited && self.expr.len() > 1 {
1116+
let shares_buffers = self.schema.fields().iter().any(|field| {
1117+
let data_type = field.data_type();
1118+
sorted_copy_keeps_buffers(data_type)
1119+
&& !matches!(data_type, DataType::Utf8View | DataType::BinaryView)
1120+
});
1121+
if limited && !shares_buffers && merges_in_row_format(&self.expr, &self.schema) {
11011122
(self.batch_size / 8).max(1024).min(self.batch_size)
11021123
} else {
11031124
self.batch_size

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

Lines changed: 64 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -9,10 +9,10 @@ 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, Int32Array, Int64Array,
13-
StringArray, StringViewArray,
12+
ArrayRef, Decimal128Array, DictionaryArray, FixedSizeBinaryArray, Int8Array,
13+
Int32Array, Int64Array, StringArray, StringViewArray,
1414
};
15-
use arrow::compute::{SortOptions, concat_batches};
15+
use arrow::compute::{SortOptions, cast, concat_batches};
1616
use arrow::datatypes::{DataType, Field, Int8Type, Schema};
1717
use arrow::record_batch::RecordBatch;
1818
use datafusion_common::config::{ExecutionOptions, SpillCompression};
@@ -679,29 +679,69 @@ 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.
682+
/// Merging sorted runs in the row format holds the keys of every run's current
683+
/// batch. Two `Int32` keys encode to 18 bytes per row against 8 bytes in the
684+
/// batches, and a single `FixedSizeBinary(16)` key also merges in the row
685+
/// format, so merging full-size runs needs more memory than the sort reserves
686+
/// while buffering them. The `Utf8View` and dictionary payloads keep buffers
687+
/// shared after sorting, which must not be charged once per split batch.
685688
async fn check_merge_keys_larger_than_batches() -> Result<()> {
686689
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)])
690+
let int_keys = |batch: i32| -> Vec<ArrayRef> {
691+
vec![
692+
Arc::new(Int32Array::from_iter_values(
693+
(0..rows).map(|i| (i * 31 + batch) % 1000),
694+
)),
695+
Arc::new(Int32Array::from_iter_values((0..rows).rev())),
696+
]
697+
};
698+
let int_fields = [("a", DataType::Int32), ("b", DataType::Int32)];
699+
check_merge_keys(&int_fields, 2, |batch| Ok(int_keys(batch))).await?;
700+
// Longer than 12 bytes, so views keep them in data buffers.
701+
let strings = |batch: i32| -> StringArray {
702+
(0..rows)
703+
.map(|i| Some(format!("{batch}-{i:0>64}")))
704+
.collect()
705+
};
706+
let dictionary =
707+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8));
708+
for payload in [DataType::Utf8View, dictionary] {
709+
let fields = [&int_fields[..], &[("c", payload.clone())]].concat();
710+
check_merge_keys(&fields, 2, |batch| {
711+
let payload = cast(&strings(batch), &payload)?;
712+
Ok([int_keys(batch), vec![payload]].concat())
697713
})
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.
714+
.await?;
715+
}
716+
check_merge_keys(&[("k", DataType::FixedSizeBinary(16))], 1, |batch| {
717+
let keys = (0..rows).map(|i| u128::from(((i * 31 + batch) % 1000) as u32));
718+
let keys = FixedSizeBinaryArray::try_from_iter(keys.map(u128::to_be_bytes))?;
719+
Ok(vec![Arc::new(keys)])
720+
})
721+
.await
722+
}
723+
724+
/// Sorts 64 batches of `columns` by the first `keys` fields with room to buffer
725+
/// 16 of them, then checks the spilled output and that all memory is released.
726+
async fn check_merge_keys(
727+
fields: &[(&str, DataType)],
728+
keys: usize,
729+
columns: impl Fn(i32) -> Result<Vec<ArrayRef>>,
730+
) -> Result<()> {
731+
let schema = Arc::new(Schema::new(
732+
fields
733+
.iter()
734+
.map(|(name, data_type)| Field::new(*name, data_type.clone(), false))
735+
.collect::<Vec<_>>(),
736+
));
737+
let batches = (0..64)
738+
.map(|batch| Ok(RecordBatch::try_new(Arc::clone(&schema), columns(batch)?)?))
739+
.collect::<Result<Vec<_>>>()?;
740+
let ordering =
741+
LexOrdering::new((0..keys).map(|i| {
742+
PhysicalSortExpr::new_default(Arc::new(Column::new(fields[i].0, i)))
743+
}))
744+
.expect("at least one sort key");
705745
let capacity = MERGE_BYTES + 16 * get_reserved_bytes_for_record_batch(&batches[0])?;
706746
let pool = AdjustablePool::new(capacity);
707747
let runtime = RuntimeEnvBuilder::new()
@@ -711,7 +751,7 @@ async fn check_merge_keys_larger_than_batches() -> Result<()> {
711751
0,
712752
Arc::clone(&schema),
713753
ordering.clone(),
714-
rows as usize,
754+
batches[0].num_rows(),
715755
MERGE_BYTES,
716756
0,
717757
SpillCompression::Uncompressed,

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

Lines changed: 23 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ use crate::sorts::{
1313
};
1414
use crate::{EmptyRecordBatchStream, SendableRecordBatchStream, SpillManager};
1515
use arrow::array::*;
16-
use arrow::datatypes::{DataType, SchemaRef};
16+
use arrow::datatypes::{DataType, Schema, SchemaRef};
1717
use datafusion_common::human_readable_size;
1818
use datafusion_common::{Result, assert_or_internal_err, internal_err};
1919
use datafusion_execution::SpillFile;
@@ -263,7 +263,8 @@ impl<'a> StreamingMergeBuilder<'a> {
263263
let reservation =
264264
reservation.expect("Reservation cannot be empty for streaming merge");
265265

266-
// Special case single column comparisons with optimized cursor implementations
266+
// Special case single column comparisons with optimized cursor implementations.
267+
// `merges_in_row_format` must match this choice.
267268
if expressions.len() == 1 {
268269
let sort = expressions[0].clone();
269270
let data_type = sort.expr.data_type(schema.as_ref())?;
@@ -297,6 +298,26 @@ impl<'a> StreamingMergeBuilder<'a> {
297298
}
298299
}
299300

301+
/// Returns whether [`StreamingMergeBuilder::build`] merges on `expressions` in
302+
/// the row format rather than with a cursor for a single column.
303+
pub(crate) fn merges_in_row_format(expressions: &LexOrdering, schema: &Schema) -> bool {
304+
if expressions.len() > 1 {
305+
return true;
306+
}
307+
let Ok(data_type) = expressions[0].expr.data_type(schema) else {
308+
return true;
309+
};
310+
!(data_type.is_primitive()
311+
|| matches!(
312+
data_type,
313+
DataType::Utf8
314+
| DataType::Utf8View
315+
| DataType::LargeUtf8
316+
| DataType::Binary
317+
| DataType::LargeBinary
318+
))
319+
}
320+
300321
#[cfg(test)]
301322
mod tests {
302323
use crate::{common::collect, stream::RecordBatchStreamAdapter};

0 commit comments

Comments
 (0)