Skip to content

Commit 3d9037c

Browse files
fix: avoid quadratic row-buffer accounting in sort merges (apache#26366)
## Which issue does this PR close? Follow-up to apache#25372, related to apache#23174. ## Rationale for this change Multi-key sorts over many small batches spend quadratic time accounting for retained row buffers, delaying their first merged output. The merge caches one encoded row buffer per input stream. Each new batch currently scans every cache slot to recalculate the reservation. Reading the first batch from each of N streams therefore requires N full scans. A large merge can spend seconds doing this bookkeeping in a single Tokio poll. ## What changes are included in this PR? - Track each stream's reserved bytes and update the total by that stream's change, making each accounting update constant-time. - Keep the existing charge while a buffer is reused. Failed buffer growth and stream completion release only that stream's charge. - Add a SQL-based case to the existing `sort` benchmark that sorts two million rows loaded in 32-row batches. Two sort keys exercise the affected row-format merge. Data generation happens before timing. ## What is the testing strategy for this PR? A focused regression test fills a bounded memory pool, then rejects growth of a reused row buffer. It checks that the failed stream releases its previous reservation while another stream remains accounted for. The SQL benchmark runs a single query, with no concurrent workload: ```bash cargo bench -p datafusion --bench sort -- small_batches/two_keys ``` [Benchmark bot results](apache#26366 (comment)): **13.9 s → 3.4 s (4.09× faster)** for `small_batches/two_keys`. ## Are there any user-facing changes? Large row-format merges perform less bookkeeping while preserving their memory reservations. The internal reservation invariant is documented alongside the per-stream sizes. Developed with AI assistance.
1 parent 0ee3978 commit 3d9037c

2 files changed

Lines changed: 108 additions & 9 deletions

File tree

‎datafusion/core/benches/sort.rs‎

Lines changed: 60 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1065,5 +1065,64 @@ fn with_extra_columns(batches: Vec<RecordBatch>, n: usize) -> Vec<RecordBatch> {
10651065
.collect()
10661066
}
10671067

1068-
criterion_group!(benches, criterion_benchmark, sort_axis_benchmark);
1068+
fn small_batches_benchmark(c: &mut Criterion) {
1069+
let mut group = c.benchmark_group("small_batches");
1070+
group.sample_size(10);
1071+
group.sampling_mode(criterion::SamplingMode::Flat);
1072+
group.bench_function("two_keys", |b| {
1073+
let runtime = Runtime::new().unwrap();
1074+
let ctx = SessionContext::new_with_config(
1075+
SessionConfig::new()
1076+
.with_target_partitions(1)
1077+
.with_batch_size(32),
1078+
);
1079+
1080+
// Store small input batches before timing, then restore normal output batches.
1081+
runtime.block_on(async {
1082+
ctx.sql(
1083+
"CREATE TABLE sort_input AS \
1084+
SELECT value % 997 AS sort_key, value FROM range(2000000)",
1085+
)
1086+
.await
1087+
.unwrap()
1088+
.collect()
1089+
.await
1090+
.unwrap();
1091+
ctx.sql("SET datafusion.execution.batch_size = 8192")
1092+
.await
1093+
.unwrap()
1094+
.collect()
1095+
.await
1096+
.unwrap();
1097+
});
1098+
1099+
// Two keys exercise row-format merging of the small sorted runs.
1100+
b.iter(|| {
1101+
runtime.block_on(async {
1102+
let mut stream = ctx
1103+
.sql(
1104+
"SELECT sort_key, value FROM sort_input ORDER BY sort_key, value",
1105+
)
1106+
.await
1107+
.unwrap()
1108+
.execute_stream()
1109+
.await
1110+
.unwrap();
1111+
let mut row_count = 0;
1112+
while let Some(batch) = stream.next().await {
1113+
row_count += batch.unwrap().num_rows();
1114+
}
1115+
row_count
1116+
})
1117+
});
1118+
});
1119+
group.finish();
1120+
}
1121+
1122+
criterion_group!(
1123+
benches,
1124+
criterion_benchmark,
1125+
sort_axis_benchmark,
1126+
small_batches_benchmark
1127+
);
10691128
criterion_main!(benches);

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

Lines changed: 48 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -103,6 +103,9 @@ impl FusedStreams {
103103
#[derive(Debug)]
104104
struct ReusableRows {
105105
inner: Vec<Option<Arc<Rows>>>,
106+
/// Each stream's charge stays reserved while its buffer is taken for reuse.
107+
/// The sum of these sizes equals `reservation.size()`.
108+
reserved_sizes: Vec<usize>,
106109
reservation: MemoryReservation,
107110
}
108111

@@ -130,23 +133,27 @@ impl ReusableRows {
130133
/// reservation is free for the same reason. A pool that cannot cover the buffer
131134
/// fails the query here, as it did before the buffer was cached at all.
132135
fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
133-
self.inner[stream_idx] = Some(Arc::clone(rows));
134-
let retained = self.retained_size();
136+
let size = rows.size();
137+
let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
135138
debug_assert!(retained >= self.reservation.size());
136139
if let Err(e) = self.reservation.try_resize(retained) {
137-
self.inner[stream_idx] = None;
138-
self.reservation.try_resize(self.retained_size())?;
140+
self.release(stream_idx);
139141
return Err(e);
140142
}
143+
self.inner[stream_idx] = Some(Arc::clone(rows));
144+
self.reserved_sizes[stream_idx] = size;
141145
Ok(())
142146
}
143147

144148
// drop whatever a finished stream was holding
145149
fn release(&mut self, stream_idx: usize) {
146150
debug_assert!(self.reservation.size() >= self.retained_size());
147-
if let Some(rows) = self.inner[stream_idx].take() {
148-
self.reservation.shrink(rows.size());
149-
}
151+
self.inner[stream_idx] = None;
152+
let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
153+
self.reservation.resize(self.reservation.size() - reserved);
154+
// Verify the incremental accounting against a full recomputation, avoiding
155+
// the cost of scanning all buffers in release builds.
156+
debug_assert_eq!(self.reservation.size(), self.retained_size());
150157
}
151158

152159
fn retained_size(&self) -> usize {
@@ -200,6 +207,7 @@ impl RowCursorStream {
200207
streams: FusedStreams(streams),
201208
rows: ReusableRows {
202209
inner: vec![None; stream_count],
210+
reserved_sizes: vec![0; stream_count],
203211
reservation: rows_reservation,
204212
},
205213
})
@@ -442,7 +450,7 @@ mod tests {
442450
use datafusion_common::DataFusionError;
443451
use datafusion_execution::RecordBatchStream;
444452
use datafusion_execution::memory_pool::{
445-
GreedyMemoryPool, MemoryConsumer, MemoryPool,
453+
GreedyMemoryPool, MemoryConsumer, MemoryLimit, MemoryPool,
446454
};
447455
use datafusion_physical_expr::expressions::col;
448456
use futures::Stream;
@@ -907,4 +915,36 @@ mod tests {
907915

908916
Ok(())
909917
}
918+
919+
// The buffer has already been taken out of the cache when its reservation fails
920+
// to grow. Cleanup must still release its previous charge.
921+
#[test]
922+
fn failed_buffer_growth_releases_only_its_stream_reservation() -> Result<()> {
923+
let small = (64, 8);
924+
let large = (2048, 128);
925+
let mut harness =
926+
RowCursorHarness::with_shapes(vec![vec![small, large], vec![small]])?;
927+
928+
// Cache stream 1's buffer and record the reservation that must survive.
929+
assert!(harness.poll_and_drop_cursor(1)?);
930+
let expected_remaining = harness.reserved();
931+
assert!(harness.poll_and_drop_cursor(0)?);
932+
933+
// Leave no space for stream 0's larger batch.
934+
let MemoryLimit::Finite(limit) = harness.pool.memory_limit() else {
935+
unreachable!("the harness uses a bounded memory pool");
936+
};
937+
let competitor = MemoryConsumer::new("competitor").register(&harness.pool);
938+
competitor.try_grow(limit - harness.reserved())?;
939+
940+
assert!(matches!(
941+
harness.poll_cursor(0),
942+
Err(DataFusionError::ResourcesExhausted(_))
943+
));
944+
drop(competitor);
945+
946+
// Only stream 1's buffer and the shared converter remain reserved.
947+
assert_eq!(harness.reserved(), expected_remaining);
948+
Ok(())
949+
}
910950
}

0 commit comments

Comments
 (0)