Skip to content

Commit bacbf2a

Browse files
authored
Release consumed sort input batches after partial output (apache#25406)
## Which issue does this PR close? - Closes apache#25405. ## Rationale for this change External sort can keep already-consumed input batches alive after producing a partial output batch. Releasing those batches earlier reduces how long memory stays reserved for sorts that emit output in multiple chunks. ## What changes are included in this PR? This PR updates `BatchBuilder` cleanup after output emission to retain only batches that are still referenced by pending row indices or live cursors. It remaps remaining indices and cursors after dropping consumed batches. The change is limited to earlier release of consumed input batches. It does not add sort byte-targeting, spill admission changes, or new configuration. The tradeoff is that partial-output cleanup now marks live batches and remaps remaining row indices/cursors so consumed batches can be released earlier. I do not have an independent performance measurement for this first change yet. ## What is the testing strategy for this PR? Added a `BatchBuilder` test that emits a partial output batch and checks both directions: - the consumed input batch is released and its memory reservation is returned; - batches still needed by pending indices or a live cursor remain available and produce the expected later output. Also ran: - `cargo fmt --check` - `cargo test -p datafusion-physical-plan sorts::builder --lib` - `git diff --check HEAD^ HEAD` ## Are there any user-facing changes? No API or configuration changes. This only releases internal sort input batch memory earlier.
1 parent 5a2000a commit bacbf2a

1 file changed

Lines changed: 182 additions & 28 deletions

File tree

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

Lines changed: 182 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -26,14 +26,23 @@ use datafusion_execution::memory_pool::MemoryReservation;
2626
use log::warn;
2727
use std::sync::Arc;
2828

29-
#[derive(Debug, Copy, Clone, Default)]
29+
#[derive(Debug, Copy, Clone)]
3030
struct BatchCursor {
3131
/// The index into BatchBuilder::batches
3232
batch_idx: usize,
3333
/// The row index within the given batch
3434
row_idx: usize,
3535
}
3636

37+
impl BatchCursor {
38+
/// A cursor whose batch has been released. `push_row` must not be called
39+
/// for the stream until `push_batch` installs a new cursor.
40+
const RELEASED: Self = Self {
41+
batch_idx: usize::MAX,
42+
row_idx: 0,
43+
};
44+
}
45+
3746
/// Provides an API to incrementally build a [`RecordBatch`] from partitioned [`RecordBatch`]
3847
#[derive(Debug)]
3948
pub struct BatchBuilder {
@@ -81,7 +90,7 @@ impl BatchBuilder {
8190
Self {
8291
schema,
8392
batches: Vec::with_capacity(stream_count * 2),
84-
cursors: vec![BatchCursor::default(); stream_count],
93+
cursors: vec![BatchCursor::RELEASED; stream_count],
8594
indices: Vec::with_capacity(batch_size),
8695
reservation,
8796
batches_mem_used: 0,
@@ -108,6 +117,14 @@ impl BatchBuilder {
108117

109118
/// Append the next row from `stream_idx`
110119
pub fn push_row(&mut self, stream_idx: usize) {
120+
debug_assert!(
121+
self.batches
122+
.get(self.cursors[stream_idx].batch_idx)
123+
.is_some_and(|(_, batch)| {
124+
self.cursors[stream_idx].row_idx < batch.num_rows()
125+
}),
126+
"push_row on stream {stream_idx} with no live batch"
127+
);
111128
let cursor = &mut self.cursors[stream_idx];
112129
let row_idx = cursor.row_idx;
113130
cursor.row_idx += 1;
@@ -157,33 +174,10 @@ impl BatchBuilder {
157174
// Remove consumed indices, keeping any remaining for the next call.
158175
self.indices.drain(..rows_to_emit);
159176

160-
// Only clean up fully-consumed batches when all indices are drained,
161-
// because remaining indices may still reference earlier batches.
162-
// In the overflow/partial-emit case this may retain some extra memory
163-
// across a few drain polls, but avoids costly index scanning on the
164-
// hot path. The retention is bounded and short-lived since leftover
165-
// rows are drained over subsequent polls.
166177
if self.indices.is_empty() {
167-
// New cursors are only created once the previous cursor for the stream
168-
// is finished. This means all remaining rows from all but the last batch
169-
// for each stream have been yielded to the newly created record batch
170-
//
171-
// We can therefore drop all but the last batch for each stream
172-
let mut batch_idx = 0;
173-
let mut retained = 0;
174-
self.batches.retain(|(stream_idx, batch)| {
175-
let stream_cursor = &mut self.cursors[*stream_idx];
176-
let retain = stream_cursor.batch_idx == batch_idx;
177-
batch_idx += 1;
178-
179-
if retain {
180-
stream_cursor.batch_idx = retained;
181-
retained += 1;
182-
} else {
183-
self.batches_mem_used -= get_record_batch_memory_size(batch);
184-
}
185-
retain
186-
});
178+
self.retain_cursor_batches();
179+
} else {
180+
self.retain_live_batches();
187181
}
188182

189183
// Release excess memory back to the pool, but never shrink below
@@ -197,6 +191,75 @@ impl BatchBuilder {
197191
RecordBatch::try_new(Arc::clone(&self.schema), columns).map_err(Into::into)
198192
}
199193

194+
fn retain_cursor_batches(&mut self) {
195+
// New cursors are only created once the previous cursor for the stream
196+
// is finished. This means all remaining rows from all but the last batch
197+
// for each stream have been yielded to the newly created record batch
198+
//
199+
// We can therefore drop all but the last live cursor batch for each stream
200+
let mut batch_idx = 0;
201+
let mut retained = 0;
202+
self.batches.retain(|(stream_idx, batch)| {
203+
let stream_cursor = &mut self.cursors[*stream_idx];
204+
let is_cursor_batch = stream_cursor.batch_idx == batch_idx;
205+
let retain = is_cursor_batch && stream_cursor.row_idx < batch.num_rows();
206+
batch_idx += 1;
207+
208+
if retain {
209+
stream_cursor.batch_idx = retained;
210+
retained += 1;
211+
} else {
212+
if is_cursor_batch {
213+
*stream_cursor = BatchCursor::RELEASED;
214+
}
215+
self.batches_mem_used -= get_record_batch_memory_size(batch);
216+
}
217+
retain
218+
});
219+
}
220+
221+
fn retain_live_batches(&mut self) {
222+
let mut retain_batch = vec![false; self.batches.len()];
223+
for (batch_idx, _) in &self.indices {
224+
retain_batch[*batch_idx] = true;
225+
}
226+
227+
for cursor in &self.cursors {
228+
if self
229+
.batches
230+
.get(cursor.batch_idx)
231+
.is_some_and(|(_, batch)| cursor.row_idx < batch.num_rows())
232+
{
233+
retain_batch[cursor.batch_idx] = true;
234+
}
235+
}
236+
237+
let mut batch_idx = 0;
238+
let mut retained = 0;
239+
let mut remap = vec![usize::MAX; self.batches.len()];
240+
self.batches.retain(|(_, batch)| {
241+
let retain = retain_batch[batch_idx];
242+
if retain {
243+
remap[batch_idx] = retained;
244+
retained += 1;
245+
} else {
246+
self.batches_mem_used -= get_record_batch_memory_size(batch);
247+
}
248+
batch_idx += 1;
249+
retain
250+
});
251+
252+
for (batch_idx, _) in &mut self.indices {
253+
*batch_idx = remap[*batch_idx];
254+
}
255+
for cursor in &mut self.cursors {
256+
if let Some(new_idx) = remap.get(cursor.batch_idx) {
257+
// `usize::MAX` means the cursor's batch was released.
258+
cursor.batch_idx = *new_idx;
259+
}
260+
}
261+
}
262+
200263
/// Drains the in_progress row indexes, and builds a new RecordBatch from them
201264
///
202265
/// Will then drop any batches for which all rows have been yielded to the output.
@@ -280,6 +343,7 @@ mod tests {
280343
use arrow::array::{Array, ArrayDataBuilder, Int32Array, ListArray};
281344
use arrow::buffer::Buffer;
282345
use arrow::datatypes::{DataType, Field, Schema};
346+
use arrow::record_batch::RecordBatch;
283347
use datafusion_execution::memory_pool::{
284348
MemoryConsumer, MemoryPool, UnboundedMemoryPool,
285349
};
@@ -303,6 +367,96 @@ mod tests {
303367
RecordBatch::try_new(schema, vec![Arc::new(list)]).unwrap()
304368
}
305369

370+
fn reservation() -> MemoryReservation {
371+
let pool: Arc<dyn MemoryPool> = Arc::new(UnboundedMemoryPool::default());
372+
MemoryConsumer::new("test").register(&pool)
373+
}
374+
375+
fn int_batch(values: Vec<i32>) -> RecordBatch {
376+
let schema = Arc::new(Schema::new(vec![Field::new("i", DataType::Int32, false)]));
377+
RecordBatch::try_new(schema, vec![Arc::new(Int32Array::from(values))]).unwrap()
378+
}
379+
380+
fn push_n_rows(builder: &mut BatchBuilder, stream_idx: usize, n: usize) {
381+
for _ in 0..n {
382+
builder.push_row(stream_idx);
383+
}
384+
}
385+
386+
fn emit_n_rows(builder: &mut BatchBuilder, n: usize) -> RecordBatch {
387+
let columns = builder
388+
.try_interleave_columns(&builder.indices[..n])
389+
.unwrap();
390+
builder.finish_record_batch(n, columns).unwrap()
391+
}
392+
393+
fn assert_int_output(batch: &RecordBatch, expected: &[i32]) {
394+
let actual = batch
395+
.column(0)
396+
.as_any()
397+
.downcast_ref::<Int32Array>()
398+
.unwrap()
399+
.values();
400+
assert_eq!(actual, expected);
401+
}
402+
403+
#[test]
404+
fn test_partial_emit_releases_unreferenced_and_retains_live_batches() {
405+
let batch0 = int_batch(vec![10, 11]);
406+
let batch1 = int_batch(vec![20, 21]);
407+
let batch2 = int_batch(vec![30, 31]);
408+
let batch1_size = get_record_batch_memory_size(&batch1);
409+
let batch2_size = get_record_batch_memory_size(&batch2);
410+
let schema = batch0.schema();
411+
let mut builder = BatchBuilder::new(Arc::clone(&schema), 3, 6, reservation());
412+
413+
builder.push_batch(0, batch0).unwrap();
414+
push_n_rows(&mut builder, 0, 2);
415+
builder.push_batch(1, batch1).unwrap();
416+
push_n_rows(&mut builder, 1, 2);
417+
// Keep one stream empty so an unloaded cursor cannot retain consumed batches.
418+
builder.push_batch(0, batch2).unwrap();
419+
420+
let output = emit_n_rows(&mut builder, 2);
421+
assert_int_output(&output, &[10, 11]);
422+
423+
assert_eq!(builder.len(), 2);
424+
assert_eq!(builder.batches.len(), 2);
425+
assert_eq!(builder.batches_mem_used, batch1_size + batch2_size);
426+
assert_eq!(builder.reservation.size(), batch1_size + batch2_size);
427+
428+
push_n_rows(&mut builder, 0, 2);
429+
let output = emit_n_rows(&mut builder, 4);
430+
assert_int_output(&output, &[20, 21, 30, 31]);
431+
432+
assert!(builder.is_empty());
433+
assert!(builder.batches.is_empty());
434+
assert_eq!(builder.batches_mem_used, 0);
435+
assert_eq!(builder.reservation.size(), 0);
436+
}
437+
438+
#[test]
439+
fn test_released_cursor_accepts_new_batch_for_stream() {
440+
let batch0 = int_batch(vec![10]);
441+
let batch1 = int_batch(vec![20]);
442+
let schema = batch0.schema();
443+
let mut builder = BatchBuilder::new(Arc::clone(&schema), 1, 1, reservation());
444+
445+
builder.push_batch(0, batch0).unwrap();
446+
builder.push_row(0);
447+
let output = emit_n_rows(&mut builder, 1);
448+
assert_int_output(&output, &[10]);
449+
assert!(builder.batches.is_empty());
450+
451+
builder.push_batch(0, batch1).unwrap();
452+
builder.push_row(0);
453+
let output = emit_n_rows(&mut builder, 1);
454+
assert_int_output(&output, &[20]);
455+
assert!(builder.batches.is_empty());
456+
assert_eq!(builder.batches_mem_used, 0);
457+
assert_eq!(builder.reservation.size(), 0);
458+
}
459+
306460
#[test]
307461
fn test_retry_interleave_halves_rows_until_success() {
308462
let mut attempts = Vec::new();

0 commit comments

Comments
 (0)