You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/10/14 22:55:42 UTC
(datafusion) branch gh-readonly-queue/main/pr-25820-d173279fd8af20093a0d2bedf694125f92168e9f created (now e0d64fca0f)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-25820-d173279fd8af20093a0d2bedf694125f92168e9f
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at e0d64fca0f fix: count buffers shared between sort input batches once (#25820)
This branch includes the following new commits:
new e0d64fca0f fix: count buffers shared between sort input batches once (#25820)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: fix: count buffers shared between sort input batches once (#25820)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-25820-d173279fd8af20093a0d2bedf694125f92168e9f
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit e0d64fca0f5e59030cfba21b18da003be3b20e0b
Author: Andy Grove <ag...@apache.org>
AuthorDate: Wed Oct 14 20:46:20 2026 +0000
fix: count buffers shared between sort input batches once (#25820)
## Which issue does this PR close?
- Part of #25804 (finding 5).
- Related to #22526.
## Rationale for this change
A grouped aggregate emits its output as zero-copy slices of one batch.
`SortExec` reserves every buffered batch's full buffer capacity, so each
slice is charged for the whole aggregate output. A sort after a `GROUP
BY` therefore reserves several times the memory it holds: it spills when
it doesn't need to, and with spilling disabled it fails with
`ResourcesExhausted`. For example, `select group_key, sum(payload) as s
from t group by group_key order by group_key` over 100,000 groups needs
a 24 MB memory limit on `main` and runs in 6 MB with this change.
## What changes are included in this PR?
- `ExternalSorter` counts its buffered batches with a
`RecordBatchMemoryCounter`, as #22862 did for the hash join build side,
so a buffer shared between batches is reserved once. Each batch still
reserves its sliced size for sorting it.
- When the buffered batches are sorted as separate runs and the runs
share buffers, the reservation for the runs' input is held until every
run is sorted, because a run still waiting to be sorted keeps the shared
buffers alive. Runs that share nothing release their input as soon as
they are sorted, as before.
- Coalescing batches into runs for single-column sorts sizes the batches
the same way.
- Schemas with view, dictionary or list view types keep reserving each
batch on its own. Sorting those types keeps referencing the input's data
buffers or values, and the sorted runs and the merge charge those
buffers once per run. Counting them once at insert would let a spill
take more runs than the merge can then hold
(`sort_spill_is_compacted_for_view_arrays` fails that way). Counting
them once needs the merge side to change too; see #25800 and #25791.
## What is the testing strategy for this PR?
- `sort_after_group_by_reserves_shared_output_once` in `memory_limit`
runs `GROUP BY ... ORDER BY` with one sort key and with two, under a 12
MB limit with spilling disabled. It fails on `main` with `Memory
Exhausted while Sorting` for either ordering.
- The `spill_tests` fixture now builds each batch separately. Its
batches were slices of one batch, and the tests relied on each slice
being charged for the whole batch to create memory pressure.
Benchmarks: `cargo bench -p datafusion --bench sort` with the
`release-nonlto` profile, running `main` and this PR alternately, median
of three runs:
| benchmark | `main` | this PR | change |
|---|---|---|---|
| sort i64 1M | 24.11 ms | 23.94 ms | -0.7% |
| sort partitioned i64 1M | 3.05 ms | 3.21 ms | +5.3% |
| sort utf8 high cardinality 1M | 59.54 ms | 60.72 ms | +2.0% |
| sort partitioned utf8 high cardinality 1M | 4.84 ms | 4.93 ms | +2.0%
|
| sort utf8 dictionary tuple 1M | 510.35 ms | 511.02 ms | +0.1% |
| sort partitioned utf8 dictionary tuple 1M | 10.44 ms | 10.65 ms |
+2.0% |
| sort mixed tuple 1M | 106.05 ms | 106.43 ms | +0.4% |
| sort partitioned mixed tuple 1M | 11.51 ms | 11.12 ms | -3.4% |
`sort partitioned i64 1M` was 5-12% slower across longer runs. The
difference comes from moving the shared reservation, empty in this
benchmark, into each run's sort future: a build that doesn't move it
matches `main`. The counting itself costs about 2 µs per partition. The
dictionary cases don't take the new path, which puts the noise at about
2%.
## Are there any user-facing changes?
Sorts over sliced input without view or dictionary columns, such as the
output of a grouped aggregate, reserve less memory and spill less. No
API changes.
---
datafusion/core/tests/memory_limit/mod.rs | 30 ++++
datafusion/physical-plan/src/sorts/sort.rs | 177 ++++++++++++++++++---
.../physical-plan/src/sorts/sort/spill_tests.rs | 41 +++--
3 files changed, 213 insertions(+), 35 deletions(-)
diff --git a/datafusion/core/tests/memory_limit/mod.rs b/datafusion/core/tests/memory_limit/mod.rs
index 2d48ad6790..0faa4a64cf 100644
--- a/datafusion/core/tests/memory_limit/mod.rs
+++ b/datafusion/core/tests/memory_limit/mod.rs
@@ -446,6 +446,36 @@ async fn group_by_count_distinct_utf8_view() {
.await
}
+/// A grouped aggregate emits its output as zero-copy slices of one batch, and
+/// the sort that buffers them must reserve their shared buffers once rather
+/// than once per slice. For 100,000 groups that needs about 6 MB instead of
+/// about 24 MB, so 12 MB separates the two. The two orderings cover both ways
+/// the buffered slices are sorted: coalesced into runs for a single sort key,
+/// and one run per slice otherwise. The in-place threshold is below the slice
+/// size, so that coalescing keeps the slices as separate runs.
+#[tokio::test]
+async fn sort_after_group_by_reserves_shared_output_once() {
+ for order_by in ["group_key", "s desc, group_key"] {
+ TestCase::new()
+ .with_query(format!(
+ "select group_key, sum(payload) as s from t group by group_key order by {order_by}"
+ ))
+ .with_scenario(Scenario::GroupedDistinctStrings {
+ groups: 100_000,
+ string_view: false,
+ })
+ .with_config(
+ SessionConfig::new()
+ .with_target_partitions(1)
+ .with_sort_in_place_threshold_bytes(64 * 1024),
+ )
+ .with_memory_limit(12_000_000)
+ .with_expected_success()
+ .run()
+ .await
+ }
+}
+
#[tokio::test]
async fn join_by_key_multiple_partitions() {
let config = SessionConfig::new().with_target_partitions(2);
diff --git a/datafusion/physical-plan/src/sorts/sort.rs b/datafusion/physical-plan/src/sorts/sort.rs
index 7c34545b77..13065bed07 100644
--- a/datafusion/physical-plan/src/sorts/sort.rs
+++ b/datafusion/physical-plan/src/sorts/sort.rs
@@ -59,9 +59,10 @@ use crate::{
use arrow::array::{RecordBatch, RecordBatchOptions};
use arrow::compute::{concat_batches, lexsort_to_indices, take_arrays};
-use arrow::datatypes::SchemaRef;
+use arrow::datatypes::{DataType, SchemaRef};
use datafusion_common::config::SpillCompression;
use datafusion_common::tree_node::TreeNodeRecursion;
+use datafusion_common::utils::memory::RecordBatchMemoryCounter;
use datafusion_common::{
DataFusionError, Result, assert_or_internal_err, internal_datafusion_err,
unwrap_or_internal_err,
@@ -236,6 +237,12 @@ struct ExternalSorter {
// ========================================================================
/// Unsorted input batches stored in the memory buffer
in_mem_batches: Vec<RecordBatch>,
+ /// Counts the buffers retained by `in_mem_batches`. The batches can share
+ /// buffers, for example zero-copy slices of one larger batch, and each
+ /// buffer is reserved only once. `None` if the sorted runs keep referencing
+ /// input buffers (see [`sorted_copy_keeps_buffers`]), in which case each
+ /// batch is reserved on its own.
+ in_mem_batches_counter: Option<RecordBatchMemoryCounter>,
/// During external sorting, in-memory intermediate data will be appended to
/// this file incrementally. Once finished, this file will be moved to [`Self::finished_spill_files`].
@@ -310,9 +317,16 @@ impl ExternalSorter {
)
.with_compression_type(spill_compression);
+ let in_mem_batches_counter = (!schema
+ .fields()
+ .iter()
+ .any(|field| sorted_copy_keeps_buffers(field.data_type())))
+ .then(RecordBatchMemoryCounter::new);
+
Ok(Self {
schema,
in_mem_batches: vec![],
+ in_mem_batches_counter,
in_progress_spill_file: None,
finished_spill_files: vec![],
expr,
@@ -643,6 +657,9 @@ impl ExternalSorter {
return Ok(self.observe_if_output(empty_stream, is_output_stream));
}
+ // Every path below consumes all of `in_mem_batches`
+ self.in_mem_batches_counter = self.new_buffered_batches_counter();
+
// The elapsed compute timer is updated when the value is dropped.
// There is no need for an explicit call to drop.
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
@@ -657,7 +674,7 @@ impl ExternalSorter {
if self.in_mem_batches.len() == 1 {
let batch = self.in_mem_batches.swap_remove(0);
let reservation = self.reservation.take();
- let sorted_stream = self.sort_batch_stream(batch, reservation)?;
+ let sorted_stream = self.sort_batch_stream(batch, reservation, None)?;
return Ok(self.observe_if_output(sorted_stream, is_output_stream));
}
@@ -674,7 +691,7 @@ impl ExternalSorter {
.try_resize(get_reserved_bytes_for_record_batch(&batch)?)
.map_err(Self::err_with_oom_context)?;
let reservation = self.reservation.take();
- let sorted_stream = self.sort_batch_stream(batch, reservation)?;
+ let sorted_stream = self.sort_batch_stream(batch, reservation, None)?;
return Ok(self.observe_if_output(sorted_stream, is_output_stream));
}
@@ -690,16 +707,11 @@ impl ExternalSorter {
batches
};
- let streams = runs
+ let streams = self
+ .sort_run_streams(runs)?
.into_iter()
- .map(|batch| {
- let reservation = self
- .reservation
- .split(get_reserved_bytes_for_record_batch(&batch)?);
- let input = self.sort_batch_stream(batch, reservation)?;
- Ok(spawn_buffered(input, 1))
- })
- .collect::<Result<_>>()?;
+ .map(|stream| spawn_buffered(stream, 1))
+ .collect();
StreamingMergeBuilder::new()
.with_streams(streams)
@@ -728,6 +740,8 @@ impl ExternalSorter {
let mut runs: Vec<RecordBatch> = Vec::new();
let mut group: Vec<RecordBatch> = Vec::new();
let mut group_bytes = 0usize;
+ // Count the buffers the batches share as when they were buffered
+ let mut counter = self.new_buffered_batches_counter();
// Flush a group into a run, skipping the copy for a single-batch group.
let flush = |group: &mut Vec<RecordBatch>,
@@ -746,7 +760,8 @@ impl ExternalSorter {
};
for batch in batches {
- let bytes = get_reserved_bytes_for_record_batch(&batch)?;
+ let bytes =
+ get_reserved_bytes_for_next_record_batch(&batch, counter.as_mut())?;
if !group.is_empty() && group_bytes.saturating_add(bytes) > target {
flush(&mut group, &mut runs, &self.schema)?;
group_bytes = 0;
@@ -757,9 +772,10 @@ impl ExternalSorter {
flush(&mut group, &mut runs, &self.schema)?;
// Realign the reservation: concatenation may shift the footprint slightly.
+ let mut counter = self.new_buffered_batches_counter();
let total: usize = runs
.iter()
- .map(get_reserved_bytes_for_record_batch)
+ .map(|run| get_reserved_bytes_for_next_record_batch(run, counter.as_mut()))
.sum::<Result<usize>>()?;
self.reservation
.try_resize(total)
@@ -768,10 +784,64 @@ impl ExternalSorter {
Ok(runs)
}
+ /// Returns a counter for sizing batches that are buffered together, or
+ /// `None` if each batch is sized on its own (see
+ /// [`Self::in_mem_batches_counter`]).
+ fn new_buffered_batches_counter(&self) -> Option<RecordBatchMemoryCounter> {
+ self.in_mem_batches_counter
+ .as_ref()
+ .map(|_| RecordBatchMemoryCounter::new())
+ }
+
+ /// Sorts each run into its own stream, splitting `self.reservation` between
+ /// them.
+ ///
+ /// Runs can share buffers, for example zero-copy slices of one larger batch,
+ /// and `self.reservation` covers each shared buffer once. A shared buffer
+ /// stays alive until the last run holding it is sorted, so if any buffers are
+ /// shared, the reservation for every run's input is held until all the runs
+ /// are sorted. Otherwise each run releases its input once it is sorted.
+ fn sort_run_streams(
+ &self,
+ runs: Vec<RecordBatch>,
+ ) -> Result<Vec<SendableRecordBatchStream>> {
+ let mut counter = self.new_buffered_batches_counter();
+ let mut shares_buffers = false;
+ let mut sizes = Vec::with_capacity(runs.len());
+ for run in &runs {
+ let memory_size = get_record_batch_memory_size(run);
+ let retained = counter
+ .as_mut()
+ .map_or(memory_size, |counter| counter.count_batch(run));
+ shares_buffers |= retained < memory_size;
+ sizes.push((retained, run.get_sliced_size()?));
+ }
+
+ let shared_input = shares_buffers.then(|| {
+ let retained = sizes.iter().map(|(retained, _)| retained).sum();
+ Arc::new(self.reservation.split(retained))
+ });
+
+ runs.into_iter()
+ .zip(sizes)
+ .map(|(run, (retained, sliced))| {
+ let size = match shared_input {
+ Some(_) => sliced,
+ None => get_reserved_bytes_for_record_batch_size(retained, sliced),
+ };
+ let reservation = self.reservation.split(size);
+ self.sort_batch_stream(run, reservation, shared_input.clone())
+ })
+ .collect()
+ }
+
/// Sorts a single `RecordBatch` into a single stream.
///
/// This may output multiple batches depending on the size of the
/// sorted data and the target batch size.
+ /// If given, `shared_input` covers the input buffers of every run, which can
+ /// share buffers, and `reservation` only covers sorting `batch`. This stream
+ /// drops its handle to `shared_input` once `batch` is sorted.
/// For single-batch output cases, `reservation` will be freed immediately after sorting,
/// as the batch will be output and is expected to be reserved by the consumer of the stream.
/// For multi-batch output cases, `reservation` and any borrowed spill workspace
@@ -781,11 +851,14 @@ impl ExternalSorter {
&self,
batch: RecordBatch,
reservation: MemoryReservation,
+ shared_input: Option<Arc<MemoryReservation>>,
) -> Result<SendableRecordBatchStream> {
- assert_eq!(
- get_reserved_bytes_for_record_batch(&batch)?,
- reservation.size()
- );
+ let reserved_bytes = get_reserved_bytes_for_record_batch(&batch)?;
+ match &shared_input {
+ None => assert_eq!(reserved_bytes, reservation.size()),
+ // `shared_input` covers every buffer of every run's input
+ Some(shared) => assert!(reservation.size() + shared.size() >= reserved_bytes),
+ }
let schema = batch.schema();
let expressions = self.expr.clone();
@@ -793,6 +866,9 @@ impl ExternalSorter {
let merge_pool = Arc::clone(&self.merge_pool);
let stream = futures::stream::once(async move {
+ // Held until `batch` is sorted, when this block ends. The last run to
+ // drop it releases the reservation for the runs' input.
+ let _shared_input = shared_input;
let schema = batch.schema();
// Sort the batch immediately and get all output batches
@@ -865,7 +941,10 @@ impl ExternalSorter {
&mut self,
input: &RecordBatch,
) -> Result<()> {
- let size = get_reserved_bytes_for_record_batch(input)?;
+ let size = get_reserved_bytes_for_next_record_batch(
+ input,
+ self.in_mem_batches_counter.as_mut(),
+ )?;
match self.reservation.try_grow(size) {
Ok(_) => Ok(()),
@@ -874,8 +953,13 @@ impl ExternalSorter {
return Err(Self::err_with_oom_context(e));
}
- // Spill and try again.
+ // Spill and try again. Nothing is buffered after the spill, so
+ // `input` shares no buffers with a buffered batch.
self.sort_and_spill_in_mem_batches().await?;
+ let size = get_reserved_bytes_for_next_record_batch(
+ input,
+ self.in_mem_batches_counter.as_mut(),
+ )?;
self.reservation
.try_grow(size)
.map_err(Self::err_with_oom_context)
@@ -946,6 +1030,59 @@ pub(crate) fn get_reserved_bytes_for_record_batch(batch: &RecordBatch) -> Result
})
}
+/// Estimate how much memory is needed to sort `batch` when it is buffered with
+/// the batches `counter` has already counted.
+///
+/// Like [`get_reserved_bytes_for_record_batch`], but only counts the buffers of
+/// `batch` that `counter` has not seen. Buffered batches can share buffers, for
+/// example zero-copy slices of one larger batch, and a shared buffer only needs
+/// to be reserved once. Without a `counter`, every buffer of `batch` is counted.
+fn get_reserved_bytes_for_next_record_batch(
+ batch: &RecordBatch,
+ counter: Option<&mut RecordBatchMemoryCounter>,
+) -> Result<usize> {
+ let Some(counter) = counter else {
+ return get_reserved_bytes_for_record_batch(batch);
+ };
+ let sliced_size = batch.get_sliced_size()?;
+ Ok(get_reserved_bytes_for_record_batch_size(
+ counter.count_batch(batch),
+ sliced_size,
+ ))
+}
+
+/// Returns whether the sorted copy of an array of `data_type` keeps
+/// referencing some of the array's buffers.
+///
+/// Sorting takes the selected rows into new buffers, except that `take` keeps
+/// the data buffers of view arrays and the values of dictionaries and list
+/// views. Every sorted run is charged for those buffers in full, so buffered
+/// batches that share them must be charged for them each, too. Otherwise the
+/// sorter buffers more batches than the merge of their sorted runs can hold.
+fn sorted_copy_keeps_buffers(data_type: &DataType) -> bool {
+ match data_type {
+ DataType::Utf8View
+ | DataType::BinaryView
+ | DataType::Dictionary(_, _)
+ | DataType::ListView(_)
+ | DataType::LargeListView(_) => true,
+ DataType::List(field)
+ | DataType::LargeList(field)
+ | DataType::FixedSizeList(field, _)
+ | DataType::Map(field, _) => sorted_copy_keeps_buffers(field.data_type()),
+ DataType::Struct(fields) => fields
+ .iter()
+ .any(|field| sorted_copy_keeps_buffers(field.data_type())),
+ DataType::Union(fields, _) => fields
+ .iter()
+ .any(|(_, field)| sorted_copy_keeps_buffers(field.data_type())),
+ DataType::RunEndEncoded(_, values) => {
+ sorted_copy_keeps_buffers(values.data_type())
+ }
+ _ => false,
+ }
+}
+
impl Debug for ExternalSorter {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.debug_struct("ExternalSorter")
diff --git a/datafusion/physical-plan/src/sorts/sort/spill_tests.rs b/datafusion/physical-plan/src/sorts/sort/spill_tests.rs
index f41ca4507c..60b151030c 100644
--- a/datafusion/physical-plan/src/sorts/sort/spill_tests.rs
+++ b/datafusion/physical-plan/src/sorts/sort/spill_tests.rs
@@ -146,21 +146,32 @@ fn fixture() -> Result<Fixture> {
Field::new("sales", DataType::Decimal128(28, 2), true),
Field::new("payload", DataType::Utf8, false),
]));
- let categories = StringArray::from_iter(
- (0..total).map(|i| (i % 11 != 0).then(|| format!("category-{:04}", i % 100))),
- );
- // Every non-null sales value is distinct, so sorting has no ambiguous ties.
- let sales = Decimal128Array::from_iter(
- (0..total).map(|i| (i != 1).then_some(((total - i) * 100) as i128)),
- )
- .with_precision_and_scale(28, 2)?;
- let payload = StringArray::from_iter_values(
- (0..total).map(|i| format!("row-{i:08}-{}", "x".repeat(64))),
- );
- let columns: Vec<ArrayRef> =
- vec![Arc::new(categories), Arc::new(sales), Arc::new(payload)];
- let parent = RecordBatch::try_new(schema, columns)?;
- let batches: Vec<_> = (0..count).map(|i| parent.slice(i * rows, rows)).collect();
+ // Build each batch separately so it owns its buffers. Zero-copy slices of
+ // one parent would share them, and the sort reserves shared buffers once.
+ let batches = (0..count)
+ .map(|batch| {
+ let range = batch * rows..(batch + 1) * rows;
+ let categories = StringArray::from_iter(
+ range
+ .clone()
+ .map(|i| (i % 11 != 0).then(|| format!("category-{:04}", i % 100))),
+ );
+ // Every non-null sales value is distinct, so sorting has no ambiguous ties.
+ let sales = Decimal128Array::from_iter(
+ range
+ .clone()
+ .map(|i| (i != 1).then_some(((total - i) * 100) as i128)),
+ )
+ .with_precision_and_scale(28, 2)?;
+ let payload = StringArray::from_iter_values(
+ range.map(|i| format!("row-{i:08}-{}", "x".repeat(64))),
+ );
+ let columns: Vec<ArrayRef> =
+ vec![Arc::new(categories), Arc::new(sales), Arc::new(payload)];
+ Ok(RecordBatch::try_new(Arc::clone(&schema), columns)?)
+ })
+ .collect::<Result<Vec<_>>>()?;
+ let parent = concat_batches(&schema, &batches)?;
let ordering = [
PhysicalSortExpr::new(
Arc::new(Column::new("category", 0)),
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org