Skip to content

Commit e0d64fc

Browse files
authored
fix: count buffers shared between sort input batches once (apache#25820)
## Which issue does this PR close? - Part of apache#25804 (finding 5). - Related to apache#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 apache#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 apache#25800 and apache#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.
1 parent d173279 commit e0d64fc

3 files changed

Lines changed: 213 additions & 35 deletions

File tree

‎datafusion/core/tests/memory_limit/mod.rs‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -446,6 +446,36 @@ async fn group_by_count_distinct_utf8_view() {
446446
.await
447447
}
448448

449+
/// A grouped aggregate emits its output as zero-copy slices of one batch, and
450+
/// the sort that buffers them must reserve their shared buffers once rather
451+
/// than once per slice. For 100,000 groups that needs about 6 MB instead of
452+
/// about 24 MB, so 12 MB separates the two. The two orderings cover both ways
453+
/// the buffered slices are sorted: coalesced into runs for a single sort key,
454+
/// and one run per slice otherwise. The in-place threshold is below the slice
455+
/// size, so that coalescing keeps the slices as separate runs.
456+
#[tokio::test]
457+
async fn sort_after_group_by_reserves_shared_output_once() {
458+
for order_by in ["group_key", "s desc, group_key"] {
459+
TestCase::new()
460+
.with_query(format!(
461+
"select group_key, sum(payload) as s from t group by group_key order by {order_by}"
462+
))
463+
.with_scenario(Scenario::GroupedDistinctStrings {
464+
groups: 100_000,
465+
string_view: false,
466+
})
467+
.with_config(
468+
SessionConfig::new()
469+
.with_target_partitions(1)
470+
.with_sort_in_place_threshold_bytes(64 * 1024),
471+
)
472+
.with_memory_limit(12_000_000)
473+
.with_expected_success()
474+
.run()
475+
.await
476+
}
477+
}
478+
449479
#[tokio::test]
450480
async fn join_by_key_multiple_partitions() {
451481
let config = SessionConfig::new().with_target_partitions(2);

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

Lines changed: 157 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -59,9 +59,10 @@ use crate::{
5959

6060
use arrow::array::{RecordBatch, RecordBatchOptions};
6161
use arrow::compute::{concat_batches, lexsort_to_indices, take_arrays};
62-
use arrow::datatypes::SchemaRef;
62+
use arrow::datatypes::{DataType, SchemaRef};
6363
use datafusion_common::config::SpillCompression;
6464
use datafusion_common::tree_node::TreeNodeRecursion;
65+
use datafusion_common::utils::memory::RecordBatchMemoryCounter;
6566
use datafusion_common::{
6667
DataFusionError, Result, assert_or_internal_err, internal_datafusion_err,
6768
unwrap_or_internal_err,
@@ -236,6 +237,12 @@ struct ExternalSorter {
236237
// ========================================================================
237238
/// Unsorted input batches stored in the memory buffer
238239
in_mem_batches: Vec<RecordBatch>,
240+
/// Counts the buffers retained by `in_mem_batches`. The batches can share
241+
/// buffers, for example zero-copy slices of one larger batch, and each
242+
/// buffer is reserved only once. `None` if the sorted runs keep referencing
243+
/// input buffers (see [`sorted_copy_keeps_buffers`]), in which case each
244+
/// batch is reserved on its own.
245+
in_mem_batches_counter: Option<RecordBatchMemoryCounter>,
239246

240247
/// During external sorting, in-memory intermediate data will be appended to
241248
/// this file incrementally. Once finished, this file will be moved to [`Self::finished_spill_files`].
@@ -310,9 +317,16 @@ impl ExternalSorter {
310317
)
311318
.with_compression_type(spill_compression);
312319

320+
let in_mem_batches_counter = (!schema
321+
.fields()
322+
.iter()
323+
.any(|field| sorted_copy_keeps_buffers(field.data_type())))
324+
.then(RecordBatchMemoryCounter::new);
325+
313326
Ok(Self {
314327
schema,
315328
in_mem_batches: vec![],
329+
in_mem_batches_counter,
316330
in_progress_spill_file: None,
317331
finished_spill_files: vec![],
318332
expr,
@@ -643,6 +657,9 @@ impl ExternalSorter {
643657
return Ok(self.observe_if_output(empty_stream, is_output_stream));
644658
}
645659

660+
// Every path below consumes all of `in_mem_batches`
661+
self.in_mem_batches_counter = self.new_buffered_batches_counter();
662+
646663
// The elapsed compute timer is updated when the value is dropped.
647664
// There is no need for an explicit call to drop.
648665
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
@@ -657,7 +674,7 @@ impl ExternalSorter {
657674
if self.in_mem_batches.len() == 1 {
658675
let batch = self.in_mem_batches.swap_remove(0);
659676
let reservation = self.reservation.take();
660-
let sorted_stream = self.sort_batch_stream(batch, reservation)?;
677+
let sorted_stream = self.sort_batch_stream(batch, reservation, None)?;
661678
return Ok(self.observe_if_output(sorted_stream, is_output_stream));
662679
}
663680

@@ -674,7 +691,7 @@ impl ExternalSorter {
674691
.try_resize(get_reserved_bytes_for_record_batch(&batch)?)
675692
.map_err(Self::err_with_oom_context)?;
676693
let reservation = self.reservation.take();
677-
let sorted_stream = self.sort_batch_stream(batch, reservation)?;
694+
let sorted_stream = self.sort_batch_stream(batch, reservation, None)?;
678695
return Ok(self.observe_if_output(sorted_stream, is_output_stream));
679696
}
680697

@@ -690,16 +707,11 @@ impl ExternalSorter {
690707
batches
691708
};
692709

693-
let streams = runs
710+
let streams = self
711+
.sort_run_streams(runs)?
694712
.into_iter()
695-
.map(|batch| {
696-
let reservation = self
697-
.reservation
698-
.split(get_reserved_bytes_for_record_batch(&batch)?);
699-
let input = self.sort_batch_stream(batch, reservation)?;
700-
Ok(spawn_buffered(input, 1))
701-
})
702-
.collect::<Result<_>>()?;
713+
.map(|stream| spawn_buffered(stream, 1))
714+
.collect();
703715

704716
StreamingMergeBuilder::new()
705717
.with_streams(streams)
@@ -728,6 +740,8 @@ impl ExternalSorter {
728740
let mut runs: Vec<RecordBatch> = Vec::new();
729741
let mut group: Vec<RecordBatch> = Vec::new();
730742
let mut group_bytes = 0usize;
743+
// Count the buffers the batches share as when they were buffered
744+
let mut counter = self.new_buffered_batches_counter();
731745

732746
// Flush a group into a run, skipping the copy for a single-batch group.
733747
let flush = |group: &mut Vec<RecordBatch>,
@@ -746,7 +760,8 @@ impl ExternalSorter {
746760
};
747761

748762
for batch in batches {
749-
let bytes = get_reserved_bytes_for_record_batch(&batch)?;
763+
let bytes =
764+
get_reserved_bytes_for_next_record_batch(&batch, counter.as_mut())?;
750765
if !group.is_empty() && group_bytes.saturating_add(bytes) > target {
751766
flush(&mut group, &mut runs, &self.schema)?;
752767
group_bytes = 0;
@@ -757,9 +772,10 @@ impl ExternalSorter {
757772
flush(&mut group, &mut runs, &self.schema)?;
758773

759774
// Realign the reservation: concatenation may shift the footprint slightly.
775+
let mut counter = self.new_buffered_batches_counter();
760776
let total: usize = runs
761777
.iter()
762-
.map(get_reserved_bytes_for_record_batch)
778+
.map(|run| get_reserved_bytes_for_next_record_batch(run, counter.as_mut()))
763779
.sum::<Result<usize>>()?;
764780
self.reservation
765781
.try_resize(total)
@@ -768,10 +784,64 @@ impl ExternalSorter {
768784
Ok(runs)
769785
}
770786

787+
/// Returns a counter for sizing batches that are buffered together, or
788+
/// `None` if each batch is sized on its own (see
789+
/// [`Self::in_mem_batches_counter`]).
790+
fn new_buffered_batches_counter(&self) -> Option<RecordBatchMemoryCounter> {
791+
self.in_mem_batches_counter
792+
.as_ref()
793+
.map(|_| RecordBatchMemoryCounter::new())
794+
}
795+
796+
/// Sorts each run into its own stream, splitting `self.reservation` between
797+
/// them.
798+
///
799+
/// Runs can share buffers, for example zero-copy slices of one larger batch,
800+
/// and `self.reservation` covers each shared buffer once. A shared buffer
801+
/// stays alive until the last run holding it is sorted, so if any buffers are
802+
/// shared, the reservation for every run's input is held until all the runs
803+
/// are sorted. Otherwise each run releases its input once it is sorted.
804+
fn sort_run_streams(
805+
&self,
806+
runs: Vec<RecordBatch>,
807+
) -> Result<Vec<SendableRecordBatchStream>> {
808+
let mut counter = self.new_buffered_batches_counter();
809+
let mut shares_buffers = false;
810+
let mut sizes = Vec::with_capacity(runs.len());
811+
for run in &runs {
812+
let memory_size = get_record_batch_memory_size(run);
813+
let retained = counter
814+
.as_mut()
815+
.map_or(memory_size, |counter| counter.count_batch(run));
816+
shares_buffers |= retained < memory_size;
817+
sizes.push((retained, run.get_sliced_size()?));
818+
}
819+
820+
let shared_input = shares_buffers.then(|| {
821+
let retained = sizes.iter().map(|(retained, _)| retained).sum();
822+
Arc::new(self.reservation.split(retained))
823+
});
824+
825+
runs.into_iter()
826+
.zip(sizes)
827+
.map(|(run, (retained, sliced))| {
828+
let size = match shared_input {
829+
Some(_) => sliced,
830+
None => get_reserved_bytes_for_record_batch_size(retained, sliced),
831+
};
832+
let reservation = self.reservation.split(size);
833+
self.sort_batch_stream(run, reservation, shared_input.clone())
834+
})
835+
.collect()
836+
}
837+
771838
/// Sorts a single `RecordBatch` into a single stream.
772839
///
773840
/// This may output multiple batches depending on the size of the
774841
/// sorted data and the target batch size.
842+
/// If given, `shared_input` covers the input buffers of every run, which can
843+
/// share buffers, and `reservation` only covers sorting `batch`. This stream
844+
/// drops its handle to `shared_input` once `batch` is sorted.
775845
/// For single-batch output cases, `reservation` will be freed immediately after sorting,
776846
/// as the batch will be output and is expected to be reserved by the consumer of the stream.
777847
/// For multi-batch output cases, `reservation` and any borrowed spill workspace
@@ -781,18 +851,24 @@ impl ExternalSorter {
781851
&self,
782852
batch: RecordBatch,
783853
reservation: MemoryReservation,
854+
shared_input: Option<Arc<MemoryReservation>>,
784855
) -> Result<SendableRecordBatchStream> {
785-
assert_eq!(
786-
get_reserved_bytes_for_record_batch(&batch)?,
787-
reservation.size()
788-
);
856+
let reserved_bytes = get_reserved_bytes_for_record_batch(&batch)?;
857+
match &shared_input {
858+
None => assert_eq!(reserved_bytes, reservation.size()),
859+
// `shared_input` covers every buffer of every run's input
860+
Some(shared) => assert!(reservation.size() + shared.size() >= reserved_bytes),
861+
}
789862

790863
let schema = batch.schema();
791864
let expressions = self.expr.clone();
792865
let batch_size = self.batch_size;
793866
let merge_pool = Arc::clone(&self.merge_pool);
794867

795868
let stream = futures::stream::once(async move {
869+
// Held until `batch` is sorted, when this block ends. The last run to
870+
// drop it releases the reservation for the runs' input.
871+
let _shared_input = shared_input;
796872
let schema = batch.schema();
797873

798874
// Sort the batch immediately and get all output batches
@@ -865,7 +941,10 @@ impl ExternalSorter {
865941
&mut self,
866942
input: &RecordBatch,
867943
) -> Result<()> {
868-
let size = get_reserved_bytes_for_record_batch(input)?;
944+
let size = get_reserved_bytes_for_next_record_batch(
945+
input,
946+
self.in_mem_batches_counter.as_mut(),
947+
)?;
869948

870949
match self.reservation.try_grow(size) {
871950
Ok(_) => Ok(()),
@@ -874,8 +953,13 @@ impl ExternalSorter {
874953
return Err(Self::err_with_oom_context(e));
875954
}
876955

877-
// Spill and try again.
956+
// Spill and try again. Nothing is buffered after the spill, so
957+
// `input` shares no buffers with a buffered batch.
878958
self.sort_and_spill_in_mem_batches().await?;
959+
let size = get_reserved_bytes_for_next_record_batch(
960+
input,
961+
self.in_mem_batches_counter.as_mut(),
962+
)?;
879963
self.reservation
880964
.try_grow(size)
881965
.map_err(Self::err_with_oom_context)
@@ -946,6 +1030,59 @@ pub(crate) fn get_reserved_bytes_for_record_batch(batch: &RecordBatch) -> Result
9461030
})
9471031
}
9481032

1033+
/// Estimate how much memory is needed to sort `batch` when it is buffered with
1034+
/// the batches `counter` has already counted.
1035+
///
1036+
/// Like [`get_reserved_bytes_for_record_batch`], but only counts the buffers of
1037+
/// `batch` that `counter` has not seen. Buffered batches can share buffers, for
1038+
/// example zero-copy slices of one larger batch, and a shared buffer only needs
1039+
/// to be reserved once. Without a `counter`, every buffer of `batch` is counted.
1040+
fn get_reserved_bytes_for_next_record_batch(
1041+
batch: &RecordBatch,
1042+
counter: Option<&mut RecordBatchMemoryCounter>,
1043+
) -> Result<usize> {
1044+
let Some(counter) = counter else {
1045+
return get_reserved_bytes_for_record_batch(batch);
1046+
};
1047+
let sliced_size = batch.get_sliced_size()?;
1048+
Ok(get_reserved_bytes_for_record_batch_size(
1049+
counter.count_batch(batch),
1050+
sliced_size,
1051+
))
1052+
}
1053+
1054+
/// Returns whether the sorted copy of an array of `data_type` keeps
1055+
/// referencing some of the array's buffers.
1056+
///
1057+
/// Sorting takes the selected rows into new buffers, except that `take` keeps
1058+
/// the data buffers of view arrays and the values of dictionaries and list
1059+
/// views. Every sorted run is charged for those buffers in full, so buffered
1060+
/// batches that share them must be charged for them each, too. Otherwise the
1061+
/// sorter buffers more batches than the merge of their sorted runs can hold.
1062+
fn sorted_copy_keeps_buffers(data_type: &DataType) -> bool {
1063+
match data_type {
1064+
DataType::Utf8View
1065+
| DataType::BinaryView
1066+
| DataType::Dictionary(_, _)
1067+
| DataType::ListView(_)
1068+
| DataType::LargeListView(_) => true,
1069+
DataType::List(field)
1070+
| DataType::LargeList(field)
1071+
| DataType::FixedSizeList(field, _)
1072+
| DataType::Map(field, _) => sorted_copy_keeps_buffers(field.data_type()),
1073+
DataType::Struct(fields) => fields
1074+
.iter()
1075+
.any(|field| sorted_copy_keeps_buffers(field.data_type())),
1076+
DataType::Union(fields, _) => fields
1077+
.iter()
1078+
.any(|(_, field)| sorted_copy_keeps_buffers(field.data_type())),
1079+
DataType::RunEndEncoded(_, values) => {
1080+
sorted_copy_keeps_buffers(values.data_type())
1081+
}
1082+
_ => false,
1083+
}
1084+
}
1085+
9491086
impl Debug for ExternalSorter {
9501087
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
9511088
f.debug_struct("ExternalSorter")

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

Lines changed: 26 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -146,21 +146,32 @@ fn fixture() -> Result<Fixture> {
146146
Field::new("sales", DataType::Decimal128(28, 2), true),
147147
Field::new("payload", DataType::Utf8, false),
148148
]));
149-
let categories = StringArray::from_iter(
150-
(0..total).map(|i| (i % 11 != 0).then(|| format!("category-{:04}", i % 100))),
151-
);
152-
// Every non-null sales value is distinct, so sorting has no ambiguous ties.
153-
let sales = Decimal128Array::from_iter(
154-
(0..total).map(|i| (i != 1).then_some(((total - i) * 100) as i128)),
155-
)
156-
.with_precision_and_scale(28, 2)?;
157-
let payload = StringArray::from_iter_values(
158-
(0..total).map(|i| format!("row-{i:08}-{}", "x".repeat(64))),
159-
);
160-
let columns: Vec<ArrayRef> =
161-
vec![Arc::new(categories), Arc::new(sales), Arc::new(payload)];
162-
let parent = RecordBatch::try_new(schema, columns)?;
163-
let batches: Vec<_> = (0..count).map(|i| parent.slice(i * rows, rows)).collect();
149+
// Build each batch separately so it owns its buffers. Zero-copy slices of
150+
// one parent would share them, and the sort reserves shared buffers once.
151+
let batches = (0..count)
152+
.map(|batch| {
153+
let range = batch * rows..(batch + 1) * rows;
154+
let categories = StringArray::from_iter(
155+
range
156+
.clone()
157+
.map(|i| (i % 11 != 0).then(|| format!("category-{:04}", i % 100))),
158+
);
159+
// Every non-null sales value is distinct, so sorting has no ambiguous ties.
160+
let sales = Decimal128Array::from_iter(
161+
range
162+
.clone()
163+
.map(|i| (i != 1).then_some(((total - i) * 100) as i128)),
164+
)
165+
.with_precision_and_scale(28, 2)?;
166+
let payload = StringArray::from_iter_values(
167+
range.map(|i| format!("row-{i:08}-{}", "x".repeat(64))),
168+
);
169+
let columns: Vec<ArrayRef> =
170+
vec![Arc::new(categories), Arc::new(sales), Arc::new(payload)];
171+
Ok(RecordBatch::try_new(Arc::clone(&schema), columns)?)
172+
})
173+
.collect::<Result<Vec<_>>>()?;
174+
let parent = concat_batches(&schema, &batches)?;
164175
let ordering = [
165176
PhysicalSortExpr::new(
166177
Arc::new(Column::new("category", 0)),

0 commit comments

Comments
 (0)