Skip to content

Commit b7cd911

Browse files
committed
refactor: address review feedback on aggregate spill batch sizing
- Remove the coalescing of replay output. Ordered aggregation emits the groups that each input batch completes, which can be few, and that is better handled within the operator in a follow-up. - Check with EXPLAIN ANALYZE that the last two Case H queries spill. - Apply the view size rule of SpilledRowSizes in one view_bytes helper, and test max_row next to the row sizes of the same arrays. - Test byte-limited merges only from spill files, the only merges that set a byte limit. - Rename row_bytes to avg_row_bytes, and document that IncrementalSortIterator chunks can be shorter than batch_size.
1 parent 832a7eb commit b7cd911

6 files changed

Lines changed: 143 additions & 283 deletions

File tree

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

Lines changed: 5 additions & 139 deletions
Original file line numberDiff line numberDiff line change
@@ -19,26 +19,22 @@
1919
2020
use std::sync::Arc;
2121

22-
use arrow::compute::concat_batches;
2322
use arrow::datatypes::SchemaRef;
2423
use arrow::record_batch::RecordBatch;
25-
use datafusion_common::{DataFusionError, Result, internal_err};
24+
use datafusion_common::{Result, internal_err};
25+
use datafusion_execution::TaskContext;
2626
use datafusion_execution::memory_pool::MemoryReservation;
27-
use datafusion_execution::{TaskContext, TryEmitter, async_try_stream};
2827
use datafusion_physical_expr::PhysicalSortExpr;
2928
use datafusion_physical_expr::expressions::Column;
3029
use datafusion_physical_expr_common::sort_expr::LexOrdering;
31-
use futures::StreamExt;
3230

3331
use super::aggregate_hash_table::OrderedAggregateTableMetrics;
3432
use super::ordered_final_stream::OrderedFinalAggregateStream;
3533
use super::{AggregateExec, AggregateMode};
36-
use crate::metrics::{BaselineMetrics, SpillMetrics, Time};
34+
use crate::metrics::{BaselineMetrics, SpillMetrics};
3735
use crate::sorts::IncrementalSortIterator;
3836
use crate::sorts::streaming_merge::{SortedSpillFile, StreamingMergeBuilder};
39-
use crate::spill::get_record_batch_memory_size;
4037
use crate::spill::spill_manager::SpillManager;
41-
use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
4238
use crate::{InputOrderMode, SendableRecordBatchStream};
4339

4440
/// Target size in bytes of the batches that spilling writes and replay
@@ -311,141 +307,11 @@ impl AggregateSpill {
311307
partition,
312308
merged,
313309
&InputOrderMode::Sorted,
314-
baseline_metrics.intermediate(),
310+
baseline_metrics.clone(),
315311
metrics,
316312
None,
317313
reservation,
318314
)?;
319-
// Replay emits the groups of each merged batch, which may be few
320-
let output = coalesce(
321-
replay.into_stream(),
322-
batch_size,
323-
SPILL_BATCH_TARGET_BYTES,
324-
baseline_metrics.elapsed_compute().clone(),
325-
);
326-
Ok(Box::pin(ObservedStream::new(
327-
output,
328-
baseline_metrics.clone(),
329-
None,
330-
)))
331-
}
332-
}
333-
334-
/// Combines consecutive small batches of `input` into batches of up to
335-
/// `batch_size` rows and `max_bytes`. Batches of at least half that size are
336-
/// passed on as they are.
337-
fn coalesce(
338-
mut input: SendableRecordBatchStream,
339-
batch_size: usize,
340-
max_bytes: usize,
341-
elapsed_compute: Time,
342-
) -> SendableRecordBatchStream {
343-
let schema = input.schema();
344-
let output_schema = Arc::clone(&schema);
345-
let output = async_try_stream(move |mut emitter| async move {
346-
let mut pending = vec![];
347-
let (mut rows, mut bytes) = (0, 0);
348-
while let Some(batch) = input.next().await.transpose()? {
349-
let batch_bytes = get_record_batch_memory_size(&batch);
350-
let passed_on =
351-
batch.num_rows() >= batch_size / 2 || batch_bytes >= max_bytes / 2;
352-
if passed_on
353-
|| rows + batch.num_rows() > batch_size
354-
|| bytes + batch_bytes > max_bytes
355-
{
356-
emit_combined(&schema, &mut pending, &mut emitter, &elapsed_compute)
357-
.await?;
358-
(rows, bytes) = (0, 0);
359-
}
360-
if passed_on {
361-
emitter.emit(batch).await;
362-
continue;
363-
}
364-
rows += batch.num_rows();
365-
bytes += batch_bytes;
366-
pending.push(batch);
367-
}
368-
emit_combined(&schema, &mut pending, &mut emitter, &elapsed_compute).await
369-
});
370-
Box::pin(RecordBatchStreamAdapter::new(output_schema, output))
371-
}
372-
373-
/// Emits the batches in `pending`, if any, as one batch.
374-
async fn emit_combined(
375-
schema: &SchemaRef,
376-
pending: &mut Vec<RecordBatch>,
377-
emitter: &mut TryEmitter<RecordBatch, DataFusionError>,
378-
elapsed_compute: &Time,
379-
) -> Result<()> {
380-
if pending.is_empty() {
381-
return Ok(());
382-
}
383-
let batch = {
384-
let _timer = elapsed_compute.timer();
385-
concat_batches(schema, pending.iter())?
386-
};
387-
pending.clear();
388-
emitter.emit(batch).await;
389-
Ok(())
390-
}
391-
392-
#[cfg(test)]
393-
mod tests {
394-
use super::*;
395-
use crate::common::collect;
396-
use arrow::array::{ArrayRef, AsArray, Int32Array, StringArray};
397-
use arrow::datatypes::Int32Type;
398-
399-
#[tokio::test]
400-
async fn coalesce_combines_small_batches() -> Result<()> {
401-
// Keys `start..end`, each with a value of `value_len` bytes
402-
let batch = |start: i32, end: i32, value_len: usize| {
403-
let values = (start..end).map(|_| "x".repeat(value_len));
404-
RecordBatch::try_from_iter([
405-
(
406-
"key",
407-
Arc::new(Int32Array::from_iter_values(start..end)) as ArrayRef,
408-
),
409-
(
410-
"value",
411-
Arc::new(StringArray::from_iter_values(values)) as ArrayRef,
412-
),
413-
])
414-
.unwrap()
415-
};
416-
let input = vec![
417-
batch(0, 3, 0),
418-
batch(3, 6, 0),
419-
batch(6, 9, 0),
420-
batch(9, 12, 0),
421-
batch(12, 14, 20_000),
422-
batch(14, 17, 0),
423-
batch(17, 20, 0),
424-
batch(20, 25, 0),
425-
];
426-
let schema = input[0].schema();
427-
let input = Box::pin(RecordBatchStreamAdapter::new(
428-
schema,
429-
futures::stream::iter(input.into_iter().map(Ok)),
430-
));
431-
432-
let output = collect(coalesce(input, 8, 10_000, Time::new())).await?;
433-
434-
// Small batches are combined up to 8 rows. The batch over half of
435-
// 10,000 bytes and the batch of half of 8 rows are passed on alone.
436-
let num_rows: Vec<usize> = output.iter().map(RecordBatch::num_rows).collect();
437-
assert_eq!(num_rows, vec![6, 6, 2, 6, 5]);
438-
let keys: Vec<i32> = output
439-
.iter()
440-
.flat_map(|batch| {
441-
batch
442-
.column(0)
443-
.as_primitive::<Int32Type>()
444-
.values()
445-
.to_vec()
446-
})
447-
.collect();
448-
assert_eq!(keys, (0..25).collect::<Vec<_>>());
449-
Ok(())
315+
Ok(replay.into_stream())
450316
}
451317
}

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -90,7 +90,7 @@ pub(crate) struct SortPreservingMergeStream<C: CursorValues> {
9090
max_batch_bytes: Option<usize>,
9191

9292
/// The average memory size of the rows of each input's current batch
93-
row_bytes: Vec<usize>,
93+
avg_row_bytes: Vec<usize>,
9494

9595
/// The estimated memory size of the in-progress rows, tracked when
9696
/// `max_batch_bytes` is set
@@ -157,7 +157,7 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
157157
loser_tree: vec![],
158158
batch_size,
159159
max_batch_bytes: None,
160-
row_bytes: vec![0; stream_count],
160+
avg_row_bytes: vec![0; stream_count],
161161
in_progress_bytes: 0,
162162
fetch,
163163
produced: 0,
@@ -210,7 +210,7 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
210210
Ok(size) => size,
211211
Err(e) => return Poll::Ready(Err(e)),
212212
};
213-
self.row_bytes[idx] = size.div_ceil(num_rows.max(1));
213+
self.avg_row_bytes[idx] = size.div_ceil(num_rows.max(1));
214214
Poll::Ready(Ok(()))
215215
}
216216
}
@@ -281,7 +281,7 @@ impl<C: CursorValues> SortPreservingMergeStream<C> {
281281
let winner_stream = self.loser_tree[0];
282282
self.in_progress.push_row(winner_stream);
283283
if self.max_batch_bytes.is_some() {
284-
self.in_progress_bytes += self.row_bytes[winner_stream];
284+
self.in_progress_bytes += self.avg_row_bytes[winner_stream];
285285
}
286286

287287
// 3.2. If the new row reached the limit

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

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -290,12 +290,13 @@ impl<T: CursorArray> PartitionedStream for FieldCursorStream<T> {
290290
/// peak memory to hold both the unsorted and sorted copies simultaneously).
291291
///
292292
/// On the first call to `next()`, a sorted index array (`UInt32Array`) is
293-
/// computed via `lexsort_to_indices`. Subsequent calls yield chunks of
294-
/// `batch_size` rows by `take`-ing from the original batch using slices of
295-
/// this index array. Each `take` copies data for the chunk (not zero-copy),
296-
/// but only one chunk is live at a time since the caller consumes it before
297-
/// requesting the next. Once all rows have been yielded, the original batch
298-
/// and index array are dropped to free memory.
293+
/// computed via `lexsort_to_indices`. Subsequent calls yield chunks of up to
294+
/// `batch_size` rows, fewer if [`Self::with_max_batch_bytes`] is set, by
295+
/// `take`-ing from the original batch using slices of this index array. Each
296+
/// `take` copies data for the chunk (not zero-copy), but only one chunk is
297+
/// live at a time since the caller consumes it before requesting the next.
298+
/// Once all rows have been yielded, the original batch and index array are
299+
/// dropped to free memory.
299300
///
300301
/// The caller must reserve `sizeof(batch) + sizeof(one chunk)` for this iterator,
301302
/// and free the reservation once the iterator is depleted.

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

Lines changed: 48 additions & 61 deletions
Original file line numberDiff line numberDiff line change
@@ -338,10 +338,9 @@ mod tests {
338338
ExecutionPlanMetricsSet, SpillMetrics,
339339
};
340340

341-
/// Merges five 1000 byte rows, one per batch, with 1000 small rows in
342-
/// batches of 100, either from spill files or from in-memory streams.
341+
/// Merges a spill file of five 1000 byte rows, one per batch, with a spill
342+
/// file of 1000 small rows in batches of 100.
343343
async fn merge_wide_and_narrow_rows(
344-
from_spill_files: bool,
345344
max_batch_bytes: Option<usize>,
346345
) -> Result<Vec<RecordBatch>> {
347346
let schema = Arc::new(Schema::new(vec![
@@ -366,43 +365,34 @@ mod tests {
366365

367366
let sort: LexOrdering =
368367
[PhysicalSortExpr::new_default(col("key", &schema)?)].into();
369-
let mut builder = StreamingMergeBuilder::new()
368+
let spill_manager = SpillManager::new(
369+
Arc::new(TaskContext::default()).runtime_env(),
370+
SpillMetrics::new(&ExecutionPlanMetricsSet::new(), 0),
371+
Arc::clone(&schema),
372+
);
373+
let spill = |batches: &[RecordBatch]| SortedSpillFile {
374+
file: spill_manager
375+
.spill_record_batch_and_finish(batches, "test")
376+
.unwrap()
377+
.unwrap(),
378+
max_record_batch_memory: batches
379+
.iter()
380+
.map(RecordBatch::get_array_memory_size)
381+
.max()
382+
.unwrap(),
383+
};
384+
let sorted_spill_files = vec![spill(&wide), spill(&narrow)];
385+
let merged = StreamingMergeBuilder::new()
370386
.with_schema(Arc::clone(&schema))
371387
.with_expressions(&sort)
372388
.with_metrics(BaselineMetrics::new(&ExecutionPlanMetricsSet::new(), 0))
373389
.with_batch_size(100)
374390
.with_max_batch_bytes(max_batch_bytes)
375-
.with_bypass_mempool();
376-
if from_spill_files {
377-
let spill_manager = SpillManager::new(
378-
Arc::new(TaskContext::default()).runtime_env(),
379-
SpillMetrics::new(&ExecutionPlanMetricsSet::new(), 0),
380-
Arc::clone(&schema),
381-
);
382-
let spill = |batches: &[RecordBatch]| SortedSpillFile {
383-
file: spill_manager
384-
.spill_record_batch_and_finish(batches, "test")
385-
.unwrap()
386-
.unwrap(),
387-
max_record_batch_memory: batches
388-
.iter()
389-
.map(RecordBatch::get_array_memory_size)
390-
.max()
391-
.unwrap(),
392-
};
393-
builder = builder
394-
.with_sorted_spill_files(vec![spill(&wide), spill(&narrow)])
395-
.with_spill_manager(spill_manager);
396-
} else {
397-
let stream = |batches: Vec<RecordBatch>| {
398-
Box::pin(RecordBatchStreamAdapter::new(
399-
Arc::clone(&schema),
400-
futures::stream::iter(batches.into_iter().map(Ok)),
401-
)) as SendableRecordBatchStream
402-
};
403-
builder = builder.with_streams(vec![stream(wide), stream(narrow)]);
404-
}
405-
let batches = collect(builder.build()?).await?;
391+
.with_bypass_mempool()
392+
.with_sorted_spill_files(sorted_spill_files)
393+
.with_spill_manager(spill_manager)
394+
.build()?;
395+
let batches = collect(merged).await?;
406396

407397
let keys: Vec<i32> = batches
408398
.iter()
@@ -424,32 +414,29 @@ mod tests {
424414
let num_rows = |batches: &[RecordBatch]| -> Vec<usize> {
425415
batches.iter().map(RecordBatch::num_rows).collect()
426416
};
427-
for from_spill_files in [true, false] {
428-
// By rows only, the five large rows end up in the first batch
429-
let batches = merge_wide_and_narrow_rows(from_spill_files, None).await?;
430-
assert_eq!(num_rows(&batches), [vec![100; 10], vec![5]].concat());
431-
432-
// Three large rows exceed 3000 bytes, so the first batch holds
433-
// fewer. Once the large rows are merged, batches of small rows
434-
// still hold `batch_size` rows.
435-
let batches =
436-
merge_wide_and_narrow_rows(from_spill_files, Some(3000)).await?;
437-
let rows = num_rows(&batches);
438-
assert!(rows[0] < 5, "{rows:?}");
439-
let last_wide = batches
440-
.iter()
441-
.position(|batch| {
442-
batch
443-
.column(0)
444-
.as_primitive::<Int32Type>()
445-
.values()
446-
.contains(&4)
447-
})
448-
.unwrap();
449-
let narrow_only = &rows[last_wide + 1..rows.len() - 1];
450-
assert!(narrow_only.len() > 5, "{rows:?}");
451-
assert!(narrow_only.iter().all(|&rows| rows == 100), "{rows:?}");
452-
}
417+
// By rows only, the five large rows end up in the first batch
418+
let batches = merge_wide_and_narrow_rows(None).await?;
419+
assert_eq!(num_rows(&batches), [vec![100; 10], vec![5]].concat());
420+
421+
// Three large rows exceed 3000 bytes, so the first batch holds fewer.
422+
// Once the large rows are merged, batches of small rows still hold
423+
// `batch_size` rows.
424+
let batches = merge_wide_and_narrow_rows(Some(3000)).await?;
425+
let rows = num_rows(&batches);
426+
assert!(rows[0] < 5, "{rows:?}");
427+
let last_wide = batches
428+
.iter()
429+
.position(|batch| {
430+
batch
431+
.column(0)
432+
.as_primitive::<Int32Type>()
433+
.values()
434+
.contains(&4)
435+
})
436+
.unwrap();
437+
let narrow_only = &rows[last_wide + 1..rows.len() - 1];
438+
assert!(narrow_only.len() > 5, "{rows:?}");
439+
assert!(narrow_only.iter().all(|&rows| rows == 100), "{rows:?}");
453440
Ok(())
454441
}
455442

0 commit comments

Comments
 (0)