Skip to content

Commit 32dd1d2

Browse files
authored
fix: size aggregate spill batches by bytes as well as rows (apache#25853)
## Which issue does this PR close? - Closes apache#25851. ## Rationale for this change A grouped aggregate whose groups carry large state, such as `array_agg` over a low-cardinality key, fails with `ResourcesExhausted` after it spills, even though each group fits in memory and the same data spread over many small groups succeeds. Spilling writes the aggregate state in batches of at most `batch_size` rows, whatever their size in bytes. With fewer groups than `batch_size`, every group lands in one batch, and everything after the spill has to hold that batch at once: - With a single spill file, replay reads the batch directly and its table must hold every group at once. In the reproducer from the issue, that is 225 MB of state in a 128 MB pool, although each group is about 28 MB. - With several spill files, the merge reserves twice the largest batch of each file. When that does not fit, it tries to split the file, which first reserves twice the batch it is about to split. Even with small spilled batches, the merge combines rows until it has `batch_size` of them, rebuilding a batch of large groups. ## What changes are included in this PR? Aggregate spilling and replay now bound their batches by bytes as well as rows, with a target of 1 MiB (`SPILL_BATCH_TARGET_BYTES`): - `IncrementalSortIterator::with_max_batch_bytes` cuts the sorted state into chunks by the size each row takes once spilled, so a batch only exceeds the target when it holds a single larger group. Row sizes come from the new `SpilledRowSizes`, which counts view values as they are written after compaction and nested values by their elements. - `StreamingMergeBuilder::with_max_batch_bytes` makes the merge emit a batch once its rows reach the target, estimated from the average row size of the batches they come from, as well as at `batch_size` rows. It applies to every pass of the multi-level merge, so rows of small groups still merge in batches of `batch_size` rows. - Dictionaries whose values are mostly unique (fewer than two keys per value) count the values their keys reference, and each chunk holds only those values, since `take` keeps every value of a dictionary. Dictionaries whose values many keys share count only their keys and stay shared, as on `main`, so that each chunk does not write its own copy of them. - Replay compacts the views and dictionaries of the nested columns of merged batches (`gc_nested_arrays`). A merged batch references the buffers of every batch its rows come from, and `array_agg` keeps the lists it merges until its group completes. Both new options are crate-private and only used by aggregate spilling and replay; other merges are unchanged. The intermediate merge sizing from apache#25428 now receives the largest row count of the batches each run actually wrote. This applies to every stream built on `AggregateSpill` (hash and ordered, final and single-stage). The legacy `GroupedHashAggregateStream`, used only when `datafusion.execution.enable_migration_aggregate` is `false`, is unchanged. ## What is the testing strategy for this PR? - New Case I in `aggregate_memory_spill.slt`, with a 24 MB limit, where `EXPLAIN ANALYZE` assertions check that each query spilled. All of these fail on `main` with `ResourcesExhausted`: - `array_agg` over 32 groups of about 2 MB each, with two partitions (one spill file per partition) and with one partition (several spill files, merged). - 14 large groups, adjacent in key order, spilled together with 62,500 small groups. - Runs of large groups followed by a run of small groups. - `array_agg` over dictionary-encoded values, with two partitions and with one. - `string_agg` with one partition. - `array_agg` over dictionary values that each repeat within one group, at 8 MB. - Unit tests for `SpilledRowSizes` (including views that share bytes, nested views, fixed-width rows, and dictionaries of unique, shared and no values), for byte-limited chunks in `IncrementalSortIterator` and their dictionaries, for byte-limited merges of spill files, and for dictionary compaction. With `datafusion-cli -m 128M`, the reproducer from the issue now returns 16 groups and 3,000,000 values, and so does the variant from the issue's additional context. The reproducer with 3,000 one-value groups added, `array_agg` over dictionary-encoded Parquet strings, and the reproducer with its values cast to `Dictionary(Int32, Utf8)`, which fail on `main`, also succeed. Performance compared with `main`: - `external_aggr` (TPC-H SF1, integer keys): no case is slower; 7 are unchanged and 1 is 1.06x faster. - A spilling `GROUP BY` over 5M string keys at 256 MB is unchanged (0.61 s against 0.62 s). - 8M small groups plus 200 large `array_agg` groups take 0.80 s at 128 MB, against 2.99 s on `main`. There `main` spills 26M rows (1 GB) while merging its runs, and this PR spills each of the 8M rows once. At 512 MB, where both spill twice, this PR takes 1.00 s against 0.96 s, from measuring the rows of the spilled batch that holds the large groups. - `sort_preserving_merge` shows no change beyond run-to-run noise. Merges without a byte limit only check that none is set. - `array_agg` over a dictionary of 100 distinct values (2M rows, 100K groups, 24 MB) spills the same 10.5 MB (20-byte values) and 14.7 MB (200-byte values) as `main`, in the same time. ## Are there any user-facing changes? Aggregations whose groups have large state can now complete under memory limits where they previously failed after spilling. No API or configuration changes.
1 parent 52a8cd9 commit 32dd1d2

10 files changed

Lines changed: 1336 additions & 35 deletions

File tree

‎datafusion/physical-plan/src/aggregates/clustered_final_stream.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,8 +40,8 @@ use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
4040
/// extra index array is used in later sorting before spilling.
4141
/// - On memory pressure, materialize all group states into one batch.
4242
/// - Use [`IncrementalSortIterator`](crate::sorts::IncrementalSortIterator) to compute the full-batch index, then
43-
/// materialize and write one sorted `batch_size` slice at a time. The original
44-
/// batch and full index remain live until the run is written.
43+
/// materialize and write one sorted slice at a time. The original batch and
44+
/// full index remain live until the run is written.
4545
/// - After input ends, merge the sorted runs and replay them through a fully
4646
/// ordered final aggregate stream.
4747
pub(crate) struct ClusteredFinalAggregateStream {

‎datafusion/physical-plan/src/aggregates/spill.rs‎

Lines changed: 31 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ use datafusion_execution::memory_pool::MemoryReservation;
1414
use datafusion_physical_expr::PhysicalSortExpr;
1515
use datafusion_physical_expr::expressions::Column;
1616
use datafusion_physical_expr_common::sort_expr::LexOrdering;
17+
use futures::StreamExt;
1718

1819
use super::aggregate_hash_table::ClusteredAggregateTableMetrics;
1920
use super::clustered_final_stream::ClusteredFinalAggregateStream;
@@ -23,7 +24,19 @@ use crate::SendableRecordBatchStream;
2324
use crate::metrics::{BaselineMetrics, SpillMetrics};
2425
use crate::sorts::IncrementalSortIterator;
2526
use crate::sorts::streaming_merge::{SortedSpillFile, StreamingMergeBuilder};
27+
use crate::spill::gc_nested_arrays;
2628
use crate::spill::spill_manager::SpillManager;
29+
use crate::stream::RecordBatchStreamAdapter;
30+
31+
/// Target size in bytes of the batches that spilling writes and replay
32+
/// merges. A batch can be larger when it holds a larger group.
33+
///
34+
/// Replay holds the groups of the batch it merges in memory, and merging
35+
/// several spill files reserves memory for a few batches of each. A limit of
36+
/// `batch_size` rows alone does not bound the size of a batch: a few groups
37+
/// with large state, such as `array_agg` over a low-cardinality key, would fit
38+
/// in a single batch.
39+
const SPILL_BATCH_TARGET_BYTES: usize = 1024 * 1024;
2740

2841
/// Spill configuration and accumulated runs of one grouped aggregation stream.
2942
///
@@ -210,12 +223,18 @@ impl AggregateSpill {
210223
return Ok(());
211224
};
212225

213-
let max_batch_rows = state_batch.num_rows().min(self.batch_size);
226+
let mut max_batch_rows = 0;
214227
let sorted_iter = IncrementalSortIterator::new(
215228
state_batch,
216229
self.spill_expr.clone(),
217230
self.batch_size,
218-
);
231+
)
232+
.with_max_batch_bytes(SPILL_BATCH_TARGET_BYTES)
233+
.inspect(|batch| {
234+
if let Ok(batch) = batch {
235+
max_batch_rows = max_batch_rows.max(batch.num_rows());
236+
}
237+
});
219238
let spill_file = self
220239
.spill_manager
221240
.spill_record_batch_iter_and_return_max_batch_memory(
@@ -289,10 +308,20 @@ impl AggregateSpill {
289308
.with_expressions(&spill_expr)
290309
.with_metrics(baseline_metrics.intermediate())
291310
.with_batch_size(batch_size)
311+
.with_max_batch_bytes(Some(SPILL_BATCH_TARGET_BYTES))
292312
.with_reservation(merge_reservation)
293313
.with_replay_headroom()
294314
.with_intermediate_merge_sizing(Some(min_spill_batch_rows))
295315
.build()?;
316+
// A merged batch references the whole data buffers of the spilled
317+
// batches its rows come from, and can hold all their dictionary
318+
// values. Replay keeps the list states of a group, such as those of
319+
// `array_agg`, until the group completes, so compact them to hold only
320+
// the bytes of their own rows.
321+
let merged: SendableRecordBatchStream = Box::pin(RecordBatchStreamAdapter::new(
322+
merged.schema(),
323+
merged.map(|batch| gc_nested_arrays(&batch?)),
324+
));
296325
let replay = ClusteredFinalAggregateStream::new_with_input_and_metrics(
297326
&replay_agg,
298327
&context,

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -85,8 +85,8 @@ impl BatchBuilder {
8585
}
8686
}
8787

88-
/// Append a new batch in `stream_idx`
89-
pub fn push_batch(&mut self, stream_idx: usize, batch: RecordBatch) -> Result<()> {
88+
/// Append a new batch in `stream_idx`, returning its memory size
89+
pub fn push_batch(&mut self, stream_idx: usize, batch: RecordBatch) -> Result<usize> {
9090
let size = get_record_batch_memory_size(&batch);
9191
self.batches_mem_used += size;
9292
// Only request additional memory from the pool when actual batch
@@ -99,7 +99,7 @@ impl BatchBuilder {
9999
batch_idx,
100100
row_idx: 0,
101101
};
102-
Ok(())
102+
Ok(size)
103103
}
104104

105105
/// Append the next row from `stream_idx`

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

Lines changed: 40 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -73,6 +73,16 @@ pub(crate) struct SortPreservingMergeStream<C: CursorValues> {
7373
/// Target batch size
7474
batch_size: usize,
7575

76+
/// See [`Self::with_max_batch_bytes`]
77+
max_batch_bytes: Option<usize>,
78+
79+
/// The average memory size of the rows of each input's current batch
80+
avg_row_bytes: Vec<usize>,
81+
82+
/// The estimated memory size of the in-progress rows, tracked when
83+
/// `max_batch_bytes` is set
84+
in_progress_bytes: usize,
85+
7686
/// Cursors for each input partition. `None` means the input is exhausted
7787
cursors: Vec<Option<Cursor<C>>>,
7888

@@ -133,11 +143,22 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
133143
poll_reset_epochs: vec![0; stream_count],
134144
loser_tree: vec![],
135145
batch_size,
146+
max_batch_bytes: None,
147+
avg_row_bytes: vec![0; stream_count],
148+
in_progress_bytes: 0,
136149
fetch,
137150
produced: 0,
138151
}
139152
}
140153

154+
/// Also emits a batch once its rows take about `max_batch_bytes`, as
155+
/// estimated from the average row size of the batches they come from,
156+
/// before it has `batch_size` rows.
157+
pub(crate) fn with_max_batch_bytes(mut self, max_batch_bytes: Option<usize>) -> Self {
158+
self.max_batch_bytes = max_batch_bytes;
159+
self
160+
}
161+
141162
pub(crate) fn into_stream(self) -> SendableRecordBatchStream
142163
where
143164
C: 'static,
@@ -171,15 +192,24 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
171192
Some(Err(e)) => Poll::Ready(Err(e)),
172193
Some(Ok((cursor, batch))) => {
173194
self.cursors[idx] = Some(Cursor::new(cursor));
174-
Poll::Ready(self.in_progress.push_batch(idx, batch))
195+
let num_rows = batch.num_rows();
196+
let size = match self.in_progress.push_batch(idx, batch) {
197+
Ok(size) => size,
198+
Err(e) => return Poll::Ready(Err(e)),
199+
};
200+
self.avg_row_bytes[idx] = size.div_ceil(num_rows.max(1));
201+
Poll::Ready(Ok(()))
175202
}
176203
}
177204
}
178205

179206
fn emit_in_progress_batch(&mut self) -> Result<Option<RecordBatch>> {
180207
let rows_before = self.in_progress.len();
181208
let result = self.in_progress.build_record_batch();
182-
self.produced += rows_before - self.in_progress.len();
209+
let rows_after = self.in_progress.len();
210+
self.produced += rows_before - rows_after;
211+
// Rows kept after an offset overflow are assumed to be of average size
212+
self.in_progress_bytes = self.in_progress_bytes * rows_after / rows_before.max(1);
183213
result
184214
}
185215

@@ -237,14 +267,21 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
237267
// 3.1. add loser_tree[0] (minimum) stream to pending record batch
238268
let winner_stream = self.loser_tree[0];
239269
self.in_progress.push_row(winner_stream);
270+
if self.max_batch_bytes.is_some() {
271+
self.in_progress_bytes += self.avg_row_bytes[winner_stream];
272+
}
240273

241274
// 3.2. If the new row reached the limit
242275
if self.fetch_reached() {
243276
break;
244277
}
245278

246279
// 3.3. if there is enough to emit for a full record batch
247-
if self.in_progress.len() >= self.batch_size {
280+
if self.in_progress.len() >= self.batch_size
281+
|| self
282+
.max_batch_bytes
283+
.is_some_and(|max_bytes| self.in_progress_bytes >= max_bytes)
284+
{
248285
// 3.3.1 build pending record batch and reset builder
249286
let Some(batch) = self.emit_in_progress_batch()? else {
250287
return internal_err!("must have batch in progress to emit");

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

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -141,6 +141,8 @@ pub(crate) struct MultiLevelMergeBuilder {
141141
expr: LexOrdering,
142142
metrics: BaselineMetrics,
143143
batch_size: usize,
144+
/// See [`StreamingMergeBuilder::with_max_batch_bytes`]
145+
max_batch_bytes: Option<usize>,
144146
reservation: MemoryReservation,
145147
/// Workspace retained across retries and intermediate spill passes.
146148
merge_pool: Option<Arc<MergeMemoryPool>>,
@@ -185,6 +187,7 @@ impl MultiLevelMergeBuilder {
185187
expr,
186188
metrics,
187189
batch_size,
190+
max_batch_bytes: None,
188191
reservation,
189192
merge_pool: None,
190193
reserve_replay_headroom: false,
@@ -199,6 +202,13 @@ impl MultiLevelMergeBuilder {
199202
self
200203
}
201204

205+
/// Applies [`StreamingMergeBuilder::with_max_batch_bytes`] to every pass,
206+
/// including the passes whose output is spilled again.
207+
pub(super) fn with_max_batch_bytes(mut self, max_batch_bytes: Option<usize>) -> Self {
208+
self.max_batch_bytes = max_batch_bytes;
209+
self
210+
}
211+
202212
/// Leave replay headroom while selecting merge buffers. Temporary splitting
203213
/// workspace can still use the full pool because replay has not started.
204214
pub(super) fn with_replay_headroom(mut self, reserve: bool) -> Self {
@@ -529,7 +539,8 @@ impl MultiLevelMergeBuilder {
529539
self.metrics.intermediate()
530540
})
531541
.with_round_robin_tie_breaker(self.enable_round_robin_tie_breaker)
532-
.with_streams(streams);
542+
.with_streams(streams)
543+
.with_max_batch_bytes(self.max_batch_bytes);
533544

534545
if !all_in_memory {
535546
// Don't track memory used by this stream as we reserve that memory by worst case sceneries

0 commit comments

Comments
 (0)