Skip to content

Commit 0bc3b6c

Browse files
committed
fix: address review of bounded spill batches
- Bound the merge of spill files' output batches by the spill bound, so wide rows cannot build batch_size-row outputs outside the memory pool. - Bound spilled batches by a quarter of sort_spill_reservation_bytes (at least 1 MiB), so the minimum two-file merge fits in the headroom; 0 means no bound. - Compact dictionaries, view arrays and list views at any depth, and only those; record the size a reader decodes, including IPC padding. - Measure used dictionary values with a bitmap instead of garbage collecting. - Count rows per written piece; make SpillManager::with_max_batch_bytes crate-private. - Tests: check read-back sizes against the recorded size, nested dictionaries, list views, unsplit dictionary chunks, and that the sort spills and bounds its merged batches. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01KH2jVfxgqF5R3J7wxqvbTn
1 parent caa7814 commit 0bc3b6c

9 files changed

Lines changed: 640 additions & 120 deletions

File tree

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

Lines changed: 41 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -26,14 +26,16 @@
2626
use std::sync::Arc;
2727

2828
use arrow::array::{
29-
ArrayRef, Int64Array, ListBuilder, RecordBatch, StringArray, StringBuilder,
29+
ArrayRef, AsArray, Int64Array, ListBuilder, RecordBatch, StringArray, StringBuilder,
3030
StringViewArray,
3131
};
3232
use arrow_schema::{DataType, Field, Schema};
3333
use datafusion::datasource::MemTable;
3434
use datafusion::execution::memory_pool::FairSpillPool;
3535
use datafusion::execution::runtime_env::RuntimeEnvBuilder;
36+
use datafusion::physical_plan::collect;
3637
use datafusion::prelude::{SessionConfig, SessionContext};
38+
use datafusion_common::utils::memory::get_record_batch_memory_size;
3739

3840
/// 64 KiB per row.
3941
const ROW_BYTES: usize = 64 * 1024;
@@ -43,6 +45,22 @@ const ROWS: usize = 512;
4345
const INPUT_BATCH_ROWS: usize = 4;
4446
/// Holds about 190 rows, less than half of `ROWS`, so the sort must spill.
4547
const POOL_BYTES: usize = 12 * 1024 * 1024;
48+
const SPILL_RESERVATION_BYTES: usize = 1024 * 1024;
49+
/// The sort bounds spilled and merged batches by a quarter of
50+
/// `sort_spill_reservation_bytes`, but by no less than 1 MiB.
51+
const MAX_MERGED_BATCH_BYTES: usize = 1024 * 1024;
52+
53+
fn compact_views(batch: &RecordBatch) -> RecordBatch {
54+
let columns = batch
55+
.columns()
56+
.iter()
57+
.map(|column| match column.as_string_view_opt() {
58+
Some(views) => Arc::new(views.gc()) as ArrayRef,
59+
None => Arc::clone(column),
60+
})
61+
.collect();
62+
RecordBatch::try_new(batch.schema(), columns).unwrap()
63+
}
4664

4765
fn payload(i: usize) -> String {
4866
format!("{i:08}{}", "x".repeat(ROW_BYTES))
@@ -93,18 +111,37 @@ async fn sort_wide_rows(data_type: DataType) {
93111
.with_target_partitions(1)
94112
// 512 rows of 64 KiB is 32 MiB, more than the pool.
95113
.with_batch_size(ROWS)
96-
.with_sort_spill_reservation_bytes(1024 * 1024);
114+
.with_sort_spill_reservation_bytes(SPILL_RESERVATION_BYTES);
97115
let ctx = SessionContext::new_with_config_rt(config, runtime);
98116
ctx.register_table("t", Arc::new(table)).unwrap();
99117

100-
let result = ctx
118+
let plan = ctx
101119
.sql("SELECT id, payload FROM t ORDER BY id DESC")
102120
.await
103121
.unwrap()
104-
.collect()
122+
.create_physical_plan()
123+
.await
124+
.unwrap();
125+
let result = collect(Arc::clone(&plan), ctx.task_ctx())
105126
.await
106127
.expect("the sort must spill and finish");
107128

129+
let spill_count = plan.metrics().and_then(|m| m.spill_count()).unwrap_or(0);
130+
assert!(spill_count > 0, "the sort must spill, plan:\n{plan:?}");
131+
132+
// The merge of the spill files reserves memory for the largest spilled batch of each
133+
// file, not for its output, so it must bound its output batches in bytes too (by at
134+
// least 1 MiB), plus up to one row. Merged view arrays point into the input batches'
135+
// data buffers, so compact them to measure what the output itself holds.
136+
for batch in &result {
137+
let size = get_record_batch_memory_size(&compact_views(batch));
138+
assert!(
139+
size <= MAX_MERGED_BATCH_BYTES + 2 * ROW_BYTES,
140+
"merged a batch of {size} bytes ({} rows)",
141+
batch.num_rows()
142+
);
143+
}
144+
108145
let ids: Vec<i64> = result
109146
.iter()
110147
.flat_map(|batch| {

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

Lines changed: 42 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,13 @@ pub struct BatchBuilder {
7676
/// The accumulated stream indexes from which to pull rows
7777
/// Consists of a tuple of `(batch_idx, row_idx)`
7878
indices: Vec<(usize, usize)>,
79+
80+
/// Estimated bytes per row of the current batch of each stream: the batch's memory
81+
/// size divided by its row count.
82+
cursor_row_bytes: Vec<usize>,
83+
84+
/// Estimated size of the rows in `indices`, the sum of their `cursor_row_bytes`.
85+
in_progress_bytes: usize,
7986
}
8087

8188
impl BatchBuilder {
@@ -95,6 +102,8 @@ impl BatchBuilder {
95102
reservation,
96103
batches_mem_used: 0,
97104
initial_reservation,
105+
cursor_row_bytes: vec![0; stream_count],
106+
in_progress_bytes: 0,
98107
}
99108
}
100109

@@ -106,6 +115,7 @@ impl BatchBuilder {
106115
// usage exceeds the current reservation (which may include
107116
// pre-reserved bytes from sort_spill_reservation_bytes).
108117
try_grow_reservation_to_at_least(&mut self.reservation, self.batches_mem_used)?;
118+
self.cursor_row_bytes[stream_idx] = size / batch.num_rows().max(1);
109119
let batch_idx = self.batches.len();
110120
self.batches.push((stream_idx, batch));
111121
self.cursors[stream_idx] = BatchCursor {
@@ -129,6 +139,16 @@ impl BatchBuilder {
129139
let row_idx = cursor.row_idx;
130140
cursor.row_idx += 1;
131141
self.indices.push((cursor.batch_idx, row_idx));
142+
self.in_progress_bytes += self.cursor_row_bytes[stream_idx];
143+
}
144+
145+
/// Returns the estimated in-memory size of the in-progress rows, from the average
146+
/// row size of the batch each row comes from.
147+
///
148+
/// This is an estimate: rows of one batch can differ in size, and the interleaved
149+
/// output can be smaller than its share of the input buffers (e.g. dictionaries).
150+
pub fn in_progress_bytes(&self) -> usize {
151+
self.in_progress_bytes
132152
}
133153

134154
/// Returns the number of in-progress rows in this [`BatchBuilder`]
@@ -171,8 +191,16 @@ impl BatchBuilder {
171191
rows_to_emit: usize,
172192
columns: Vec<ArrayRef>,
173193
) -> Result<RecordBatch> {
174-
// Remove consumed indices, keeping any remaining for the next call.
194+
// Remove consumed indices, keeping any remaining for the next call. The
195+
// remaining rows keep their proportional share of the size estimate.
196+
let rows_before = self.indices.len();
175197
self.indices.drain(..rows_to_emit);
198+
self.in_progress_bytes = if self.indices.is_empty() {
199+
0
200+
} else {
201+
(self.in_progress_bytes as u128 * self.indices.len() as u128
202+
/ rows_before as u128) as usize
203+
};
176204

177205
if self.indices.is_empty() {
178206
self.retain_cursor_batches();
@@ -510,4 +538,17 @@ mod tests {
510538

511539
assert!(is_offset_overflow(&error));
512540
}
541+
542+
#[test]
543+
fn test_in_progress_bytes_tracks_rows_and_partial_emit() {
544+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
545+
let mut builder = BatchBuilder::new(Arc::clone(&schema), 1, 8, reservation());
546+
let batch = int_batch((0..8).collect());
547+
let row_bytes = get_record_batch_memory_size(&batch) / 8;
548+
builder.push_batch(0, batch).unwrap();
549+
push_n_rows(&mut builder, 0, 4);
550+
assert_eq!(builder.in_progress_bytes(), 4 * row_bytes);
551+
emit_n_rows(&mut builder, 4);
552+
assert_eq!(builder.in_progress_bytes(), 0);
553+
}
513554
}

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

Lines changed: 23 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,10 @@ pub(crate) struct SortPreservingMergeStream<C: CursorValues> {
8686
/// Target batch size
8787
batch_size: usize,
8888

89+
/// Optional upper bound on the estimated in-memory size of an output batch. A batch
90+
/// is emitted when it reaches `batch_size` rows or this many bytes, whichever first.
91+
max_batch_bytes: Option<usize>,
92+
8993
/// Cursors for each input partition. `None` means the input is exhausted
9094
cursors: Vec<Option<Cursor<C>>>,
9195

@@ -146,11 +150,29 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
146150
poll_reset_epochs: vec![0; stream_count],
147151
loser_tree: vec![],
148152
batch_size,
153+
max_batch_bytes: None,
149154
fetch,
150155
produced: 0,
151156
}
152157
}
153158

159+
/// Emit an output batch once its estimated in-memory size reaches
160+
/// `max_batch_bytes`, even if it has fewer than `batch_size` rows. See
161+
/// [`BatchBuilder::in_progress_bytes`] for how the size is estimated.
162+
pub(crate) fn with_max_batch_bytes(mut self, max_batch_bytes: Option<usize>) -> Self {
163+
self.max_batch_bytes = max_batch_bytes;
164+
self
165+
}
166+
167+
/// Returns `true` if the in-progress batch has reached `batch_size` rows or
168+
/// `max_batch_bytes` bytes.
169+
fn in_progress_is_full(&self) -> bool {
170+
self.in_progress.len() >= self.batch_size
171+
|| self
172+
.max_batch_bytes
173+
.is_some_and(|max| self.in_progress.in_progress_bytes() >= max)
174+
}
175+
154176
pub(crate) fn into_stream(self) -> SendableRecordBatchStream
155177
where
156178
C: 'static,
@@ -257,7 +279,7 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
257279
}
258280

259281
// 3.3. if there is enough to emit for a full record batch
260-
if self.in_progress.len() >= self.batch_size {
282+
if self.in_progress_is_full() {
261283
// 3.3.1 build pending record batch and reset builder
262284
let Some(batch) = self.emit_in_progress_batch()? else {
263285
return internal_err!("must have batch in progress to emit");

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -542,6 +542,11 @@ impl MultiLevelMergeBuilder {
542542
self.metrics.intermediate()
543543
})
544544
.with_round_robin_tie_breaker(self.enable_round_robin_tie_breaker)
545+
// Bound merged batches by the same size as spilled ones. A merge reserves
546+
// memory for the largest batch of each spill file it reads but not for its
547+
// own output, so wide rows would otherwise build `batch_size`-row outputs
548+
// many times larger than that reservation.
549+
.with_max_batch_bytes(self.spill_manager.max_batch_bytes)
545550
.with_streams(streams);
546551

547552
if !all_in_memory {

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

Lines changed: 34 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -309,11 +309,7 @@ impl ExternalSorter {
309309
Arc::clone(&schema),
310310
)
311311
.with_compression_type(spill_compression)
312-
// The final merge starts with `sort_spill_reservation_bytes` of headroom and
313-
// reserves memory for the largest batch of each spill file. Bound spilled batches
314-
// to that headroom, so wide rows (`batch_size` rows of several MB each) do not make
315-
// one spilled batch larger than the memory the merge has for it.
316-
.with_max_batch_bytes(Some(sort_spill_reservation_bytes.max(1)));
312+
.with_max_batch_bytes(spill_max_batch_bytes(sort_spill_reservation_bytes));
317313

318314
Ok(Self {
319315
schema,
@@ -919,6 +915,29 @@ impl ExternalSorter {
919915
}
920916
}
921917

918+
/// The bound on the in-memory size of each batch that [`ExternalSorter`] spills, and of
919+
/// each batch its merge of spill files outputs.
920+
///
921+
/// The merge starts with `sort_spill_reservation_bytes` of headroom. It needs at least two
922+
/// spill files, and reserves [`get_reserved_bytes_for_record_batch_size`] (twice the
923+
/// largest batch) per file and read-ahead slot, with read-ahead reduced down to one slot
924+
/// under pressure. So the minimum merge reserves four times the largest batch, and a
925+
/// quarter of the headroom is the largest batch that still fits it.
926+
///
927+
/// The bound is at least [`MIN_SPILL_MAX_BATCH_BYTES`]: a smaller headroom cannot seat
928+
/// the merge anyway (it then takes memory from the pool), and a bound of a few bytes
929+
/// would write, read and merge one-row batches. It is `None`, no bound, when
930+
/// `sort_spill_reservation_bytes` is 0.
931+
fn spill_max_batch_bytes(sort_spill_reservation_bytes: usize) -> Option<usize> {
932+
const MIN_MERGE_BATCHES: usize = 4;
933+
(sort_spill_reservation_bytes > 0).then(|| {
934+
(sort_spill_reservation_bytes / MIN_MERGE_BATCHES).max(MIN_SPILL_MAX_BATCH_BYTES)
935+
})
936+
}
937+
938+
/// The smallest bound [`spill_max_batch_bytes`] returns.
939+
const MIN_SPILL_MAX_BATCH_BYTES: usize = 1024 * 1024;
940+
922941
/// Estimate how much memory is needed to sort a `RecordBatch`.
923942
///
924943
/// This is used to pre-reserve memory for the sort/merge. The sort/merge process involves
@@ -2411,6 +2430,16 @@ mod tests {
24112430
}
24122431
}
24132432

2433+
#[test]
2434+
fn test_spill_max_batch_bytes_fits_minimum_merge() {
2435+
assert_eq!(spill_max_batch_bytes(0), None);
2436+
assert_eq!(spill_max_batch_bytes(3), Some(MIN_SPILL_MAX_BATCH_BYTES));
2437+
let headroom = 10 * 1024 * 1024;
2438+
let bound = spill_max_batch_bytes(headroom).unwrap();
2439+
// Two spill files, one read-ahead slot each, reserved at twice the batch size.
2440+
assert!(2 * get_reserved_bytes_for_record_batch_size(bound, bound) <= headroom);
2441+
}
2442+
24142443
#[tokio::test]
24152444
async fn test_in_mem_sort() -> Result<()> {
24162445
let task_ctx = Arc::new(TaskContext::default());

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,6 @@ use super::{
2020
};
2121
use crate::metrics::ExecutionPlanMetricsSet;
2222
use crate::spill::get_record_batch_memory_size;
23-
use crate::spill::spill_manager::GetSlicedSize;
2423
use arrow::array::{
2524
ArrayRef, Decimal128Array, DictionaryArray, Int8Array, Int64Array, StringArray,
2625
StringViewArray,
@@ -860,7 +859,9 @@ async fn check_final_spilled_merge_releases_unused_workspace(
860859
.iter()
861860
.all(|spill| spill.max_record_batch_memory == large_spill_bytes)
862861
);
863-
let tail_spill_bytes = sort_batch(&tail, &ordering, None)?.get_sliced_size()?;
862+
let tail_spill_bytes = crate::spill::in_progress_spill_file::bounded_spill_size(
863+
&sort_batch(&tail, &ordering, None)?,
864+
)?;
864865
let single_buffer_bytes = if intermediate {
865866
4 * large_spill_bytes // Two intermediate files remain for the final merge.
866867
} else {

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

Lines changed: 21 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ macro_rules! primitive_merge_helper {
4343
}
4444

4545
macro_rules! merge_helper {
46-
($t:ty, $sort:ident, $streams:ident, $schema:ident, $tracking_metrics:ident, $batch_size:ident, $fetch:ident, $reservation:ident, $enable_round_robin_tie_breaker:ident) => {{
46+
($t:ty, $sort:ident, $streams:ident, $schema:ident, $tracking_metrics:ident, $batch_size:ident, $fetch:ident, $reservation:ident, $enable_round_robin_tie_breaker:ident, $max_batch_bytes:ident) => {{
4747
let streams =
4848
FieldCursorStream::<$t>::new($sort, $streams, $reservation.new_empty());
4949
return Ok(SortPreservingMergeStream::new(
@@ -55,6 +55,7 @@ macro_rules! merge_helper {
5555
$reservation,
5656
$enable_round_robin_tie_breaker,
5757
)
58+
.with_max_batch_bytes($max_batch_bytes)
5859
.into_stream());
5960
}};
6061
}
@@ -100,6 +101,7 @@ pub struct StreamingMergeBuilder<'a> {
100101
reserve_replay_headroom: bool,
101102
min_spill_batch_rows: Option<usize>,
102103
enable_round_robin_tie_breaker: bool,
104+
max_batch_bytes: Option<usize>,
103105
}
104106

105107
impl<'a> StreamingMergeBuilder<'a> {
@@ -196,6 +198,16 @@ impl<'a> StreamingMergeBuilder<'a> {
196198
self
197199
}
198200

201+
/// Emit an output batch once its estimated in-memory size reaches
202+
/// `max_batch_bytes`, even if it has fewer than `batch_size` rows.
203+
///
204+
/// Not applied to merges of sorted spill files, which take the bound from the
205+
/// [`SpillManager`] (see [`SpillManager::with_max_batch_bytes`]).
206+
pub(crate) fn with_max_batch_bytes(mut self, max_batch_bytes: Option<usize>) -> Self {
207+
self.max_batch_bytes = max_batch_bytes;
208+
self
209+
}
210+
199211
/// Bypass the mempool and avoid using the memory reservation.
200212
///
201213
/// This is not marked as `pub` because it is not recommended to use this method
@@ -222,6 +234,7 @@ impl<'a> StreamingMergeBuilder<'a> {
222234
fetch,
223235
expressions,
224236
enable_round_robin_tie_breaker,
237+
max_batch_bytes,
225238
} = self;
226239

227240
// Early return if expressions are empty:
@@ -281,12 +294,12 @@ impl<'a> StreamingMergeBuilder<'a> {
281294
let sort = expressions[0].clone();
282295
let data_type = sort.expr.data_type(schema.as_ref())?;
283296
downcast_primitive! {
284-
data_type => (primitive_merge_helper, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker),
285-
DataType::Utf8 => merge_helper!(StringArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker)
286-
DataType::Utf8View => merge_helper!(StringViewArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker)
287-
DataType::LargeUtf8 => merge_helper!(LargeStringArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker)
288-
DataType::Binary => merge_helper!(BinaryArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker)
289-
DataType::LargeBinary => merge_helper!(LargeBinaryArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker)
297+
data_type => (primitive_merge_helper, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker, max_batch_bytes),
298+
DataType::Utf8 => merge_helper!(StringArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker, max_batch_bytes)
299+
DataType::Utf8View => merge_helper!(StringViewArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker, max_batch_bytes)
300+
DataType::LargeUtf8 => merge_helper!(LargeStringArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker, max_batch_bytes)
301+
DataType::Binary => merge_helper!(BinaryArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker, max_batch_bytes)
302+
DataType::LargeBinary => merge_helper!(LargeBinaryArray, sort, streams, schema, metrics, batch_size, fetch, reservation, enable_round_robin_tie_breaker, max_batch_bytes)
290303
_ => {}
291304
}
292305
}
@@ -306,6 +319,7 @@ impl<'a> StreamingMergeBuilder<'a> {
306319
reservation,
307320
enable_round_robin_tie_breaker,
308321
)
322+
.with_max_batch_bytes(max_batch_bytes)
309323
.into_stream())
310324
}
311325
}

0 commit comments

Comments
 (0)