Skip to content

Commit ad16004

Browse files
fix: emit completed groups when fully sorted final and single aggrega… (apache#26637)
## Which issue does this PR close? - Closes apache#26628. ## Rationale for this change A `Final` or `Single` aggregate over input sorted on all grouping keys fails with `ResourcesExhausted` under a memory limit that the legacy `GroupedHashAggregateStream` handles. After each input batch, `ClusteredFinalAggregateStream` and `ClusteredSingleAggregateStream` reserve memory for the whole table before emitting completed groups. If that reservation is refused and the stream cannot spill (full group clustering, or temporary files disabled), it returns the error, even though emitting the completed groups would leave only the active group in memory. This is the same problem as apache#26575 for the partial stream, fixed in apache#26576. ## What changes are included in this PR? - `ClusteredFinalAggregateStream`: when the reservation is refused and there is no spill context, take the completed groups and move to the output stage, then resume aggregation. The error is returned only when no group is complete. - `ClusteredSingleAggregateStream`: the same behavior, emitting through the existing `start_outputting` path and resuming `ReadingInput`. - Updated doc comments to describe the new behavior. The spilling path (partial group clustering with temporary files enabled) is unchanged. ## What is the testing strategy for this PR? New unit tests, modeled on the one in apache#26576: - `clustered_final_stream::tests::completed_groups_under_memory_pressure` - `clustered_single_stream::tests::fully_sorted_completed_groups_under_memory_pressure` Each runs `SUM(k) GROUP BY k` over two batches sorted on `k` that share a boundary key. It first runs with an unbounded pool to measure the most memory the stream holds when it hands off output, then reruns with a `GreedyMemoryPool` of that size and checks that the results match. Both tests fail on `main` with `ResourcesExhausted` and pass with this change. All `aggregates` unit tests in `datafusion-physical-plan` pass, and `cargo fmt` and `cargo clippy --all-targets --all-features -D warnings` on the crate are clean. ## Are there any user-facing changes? No API changes. Queries that used to fail with `ResourcesExhausted` in this situation now complete. --- _This solution was developed with AI assistance; I reviewed and tested the changes._
1 parent f362a82 commit ad16004

5 files changed

Lines changed: 311 additions & 113 deletions

File tree

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

Lines changed: 52 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -261,7 +261,9 @@ impl ClusteredFinalAggregateStream {
261261
/// 1. Start.
262262
/// 2. Merge one input batch:
263263
/// - If memory fits and no groups are complete, continue reading input.
264-
/// - If OOM, spill.
264+
/// - If OOM with a spill context, spill.
265+
/// - If OOM without one, emit the completed groups (edge 3), or return
266+
/// the error when no group is complete.
265267
/// 3. Prepare output:
266268
/// - Before any spill, a prefix of groups is complete: materialize the
267269
/// entire prefix once, retaining the input and active groups to resume
@@ -336,35 +338,44 @@ impl Aggregating {
336338
let timer = elapsed_compute.timer();
337339
self.table.aggregate_batch(&batch)?;
338340

339-
match reservation.try_resize(self.reservation_size()) {
340-
Ok(()) => {}
341+
// Check the reservation before taking completed groups, as the partial
342+
// stream does, so spilling is unchanged. Without spilling, the refusal
343+
// is returned below only if no group is complete.
344+
let oom = match reservation.try_resize(self.reservation_size()) {
345+
Ok(()) => None,
341346
Err(oom @ DataFusionError::ResourcesExhausted(_)) => {
342-
let Some(spill_context) = self.spill_context.as_mut() else {
343-
return Err(oom);
344-
};
345-
if self.table.is_empty() {
346-
return Err(oom);
347+
match self.spill_context.as_mut() {
348+
None => Some(oom),
349+
Some(spill_context) => {
350+
if self.table.is_empty() {
351+
return Err(oom);
352+
}
353+
spill_context
354+
.sort_and_spill(self.table.take_state_batch()?)?;
355+
reservation.try_resize(self.table.memory_size()).map_err(
356+
|e| {
357+
e.context(
358+
"Decreasing allocation after spilling should succeed",
359+
)
360+
},
361+
)?;
362+
continue;
363+
}
347364
}
348-
spill_context.sort_and_spill(self.table.take_state_batch()?)?;
349-
reservation
350-
.try_resize(self.table.memory_size())
351-
.map_err(|e| {
352-
e.context(
353-
"Decreasing allocation after spilling should succeed",
354-
)
355-
})?;
356-
continue;
357365
}
358366
Err(e) => return Err(e),
359-
}
367+
};
360368

361369
if self.spill_context.as_ref().is_some_and(|s| s.has_spills()) {
362370
// Spilled groups may recur, so all remaining states must go
363371
// through replay before any more final results can be emitted.
364372
continue;
365373
}
366374
let Some(batch) = self.table.take_completed_result_batch()? else {
367-
continue;
375+
match oom {
376+
Some(oom) => return Err(oom),
377+
None => continue,
378+
}
368379
};
369380
timer.done();
370381
return Ok(Some(ExecutionStage::Outputting(Outputting {
@@ -460,6 +471,11 @@ mod tests {
460471
use crate::ExecutionPlan;
461472
use crate::aggregates::GroupClusteringMode;
462473
use crate::aggregates::PhysicalGroupBy;
474+
use crate::aggregates::clustered_test_util::{
475+
assert_completed_groups_emitted_under_limit,
476+
assert_resources_exhausted_under_limit, full_batches, held_memory,
477+
single_key_batches, sum_over_sorted_input,
478+
};
463479
use crate::common::collect;
464480
use crate::test::TestMemoryExec;
465481
use arrow::array::{Int64Array, StringViewArray};
@@ -732,4 +748,21 @@ mod tests {
732748
assert_eq!(pool.reserved(), 0);
733749
Ok(())
734750
}
751+
752+
#[tokio::test]
753+
async fn fully_clustered_completed_groups_under_memory_pressure() -> Result<()> {
754+
let plan = sum_over_sorted_input(AggregateMode::Final, &["k"], full_batches())?;
755+
assert_eq!(plan.group_clustering_mode(), &GroupClusteringMode::Full);
756+
assert_completed_groups_emitted_under_limit(&plan).await
757+
}
758+
759+
/// A single key never completes a group before the input ends. The limit
760+
/// fits only the initial table.
761+
#[tokio::test]
762+
async fn memory_pressure_without_completed_groups() -> Result<()> {
763+
let plan =
764+
sum_over_sorted_input(AggregateMode::Final, &["k"], single_key_batches())?;
765+
let limit = held_memory(&plan).await?;
766+
assert_resources_exhausted_under_limit(&plan, limit).await
767+
}
735768
}

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

Lines changed: 7 additions & 70 deletions
Original file line numberDiff line numberDiff line change
@@ -422,78 +422,15 @@ impl Outputting {
422422
#[cfg(test)]
423423
mod tests {
424424
use super::*;
425-
use crate::aggregates::PhysicalGroupBy;
426-
use crate::test::TestMemoryExec;
427-
use arrow::array::Int64Array;
428-
use arrow::datatypes::{DataType, Field, Schema};
429-
use datafusion_common::test_util::batches_to_string;
430-
use datafusion_execution::memory_pool::{
431-
GreedyMemoryPool, MemoryPool, UnboundedMemoryPool,
425+
use crate::aggregates::GroupClusteringMode;
426+
use crate::aggregates::clustered_test_util::{
427+
assert_completed_groups_emitted_under_limit, full_batches, sum_over_sorted_input,
432428
};
433-
use datafusion_execution::runtime_env::RuntimeEnvBuilder;
434-
use datafusion_functions_aggregate::sum::sum_udaf;
435-
use datafusion_physical_expr::PhysicalSortExpr;
436-
use datafusion_physical_expr::aggregate::AggregateExprBuilder;
437-
use datafusion_physical_expr::expressions::col;
438-
use datafusion_physical_expr_common::sort_expr::LexOrdering;
439429

440-
/// Runs a partial `SUM(k) GROUP BY k` over two batches sorted on `k` that
441-
/// share a boundary key. Returns the output and the most memory the stream
442-
/// held between batches.
443-
async fn run(pool: Arc<dyn MemoryPool>) -> Result<(Vec<RecordBatch>, usize)> {
444-
let schema = Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
445-
let batches = [0..=256, 256..=512]
446-
.into_iter()
447-
.map(|keys| {
448-
let k = Int64Array::from_iter_values(keys);
449-
RecordBatch::try_new(Arc::clone(&schema), vec![Arc::new(k)])
450-
})
451-
.collect::<Result<Vec<_>, _>>()?;
452-
let input = TestMemoryExec::try_new(&[batches], Arc::clone(&schema), None)?
453-
.try_with_sort_information(vec![
454-
LexOrdering::new([PhysicalSortExpr::new_default(col("k", &schema)?)])
455-
.unwrap(),
456-
])?;
457-
let aggregate = AggregateExec::try_new(
458-
AggregateMode::Partial,
459-
PhysicalGroupBy::new_single(vec![(col("k", &schema)?, "k".into())]),
460-
vec![Arc::new(
461-
AggregateExprBuilder::new(sum_udaf(), vec![col("k", &schema)?])
462-
.schema(Arc::clone(&schema))
463-
.alias("sum")
464-
.build()?,
465-
)],
466-
vec![None],
467-
Arc::new(input),
468-
Arc::clone(&schema),
469-
)?;
470-
let context = Arc::new(
471-
TaskContext::default().with_runtime(
472-
RuntimeEnvBuilder::new()
473-
.with_memory_pool(Arc::clone(&pool))
474-
.build_arc()?,
475-
),
476-
);
477-
let mut stream =
478-
ClusteredPartialAggregateStream::new(&aggregate, &context, 0)?.into_stream();
479-
// Each output batch is a single slice, so the stream releases it before
480-
// handing it off and holds only the table.
481-
let mut held = pool.reserved();
482-
let mut output = vec![];
483-
while let Some(batch) = stream.next().await.transpose()? {
484-
held = held.max(pool.reserved());
485-
output.push(batch);
486-
}
487-
Ok((output, held))
488-
}
489-
490-
/// The limit fits the table with only the active group, but not the table
491-
/// before the completed groups are emitted. The result must not change.
492430
#[tokio::test]
493-
async fn completed_groups_under_memory_pressure() -> Result<()> {
494-
let (expected, held) = run(Arc::new(UnboundedMemoryPool::default())).await?;
495-
let (actual, _) = run(Arc::new(GreedyMemoryPool::new(held))).await?;
496-
assert_eq!(batches_to_string(&actual), batches_to_string(&expected));
497-
Ok(())
431+
async fn fully_clustered_completed_groups_under_memory_pressure() -> Result<()> {
432+
let plan = sum_over_sorted_input(AggregateMode::Partial, &["k"], full_batches())?;
433+
assert_eq!(plan.group_clustering_mode(), &GroupClusteringMode::Full);
434+
assert_completed_groups_emitted_under_limit(&plan).await
498435
}
499436
}

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

Lines changed: 53 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -82,8 +82,9 @@ use crate::{RecordBatchStream, SendableRecordBatchStream};
8282
/// only the current group remains active after completed groups are emitted, and
8383
/// memory usage does not grow with the total number of groups.
8484
///
85-
/// If a memory reservation nevertheless fails, the stream returns the error
86-
/// directly, indicating an unexpected behavior.
85+
/// If the reservation after an input batch fails, `ClusteredSingleAggregateStream`
86+
/// still emits the completed groups, and returns the error only when no group is
87+
/// complete.
8788
///
8889
/// ## Partial group clustering
8990
///
@@ -329,30 +330,35 @@ impl ClusteredSingleAggregateStream {
329330
spill_context.as_deref(),
330331
));
331332
timer.done();
332-
match resize_result {
333-
Ok(()) => {}
333+
// Check the reservation before taking completed groups, as the partial
334+
// stream does, so spilling is unchanged. Without spilling, the refusal
335+
// is returned below only if no group is complete.
336+
let oom = match resize_result {
337+
Ok(()) => None,
334338
Err(e @ DataFusionError::ResourcesExhausted(_)) => {
335-
let Some(spill_context) = spill_context else {
336-
// `None` means spilling is not supported, see comments
337-
// at `ClusteredSingleAggregateState` for details.
338-
return Self::break_with_err(e);
339-
};
340-
if table.is_empty() {
341-
return Self::break_with_internal_err(
342-
"Clustered single aggregate ran out of memory with no aggregated groups",
343-
);
339+
match spill_context {
340+
Some(spill_context) => {
341+
if table.is_empty() {
342+
return Self::break_with_internal_err(
343+
"Clustered single aggregate ran out of memory with no aggregated groups",
344+
);
345+
}
346+
return ControlFlow::Continue(
347+
ClusteredSingleAggregateState::Spilling {
348+
table,
349+
spill_context,
350+
},
351+
);
352+
}
353+
// Spilling is not supported, see comments at
354+
// `ClusteredSingleAggregateState` for details.
355+
None => Some(e),
344356
}
345-
return ControlFlow::Continue(
346-
ClusteredSingleAggregateState::Spilling {
347-
table,
348-
spill_context,
349-
},
350-
);
351357
}
352358
Err(e) => {
353359
return Self::break_with_err(e);
354360
}
355-
}
361+
};
356362

357363
let result = if spill_context
358364
.as_ref()
@@ -368,10 +374,10 @@ impl ClusteredSingleAggregateStream {
368374
result
369375
};
370376

371-
match result {
377+
match (result, oom) {
372378
// Some finalized groups can be emitted. Yield them in
373379
// slices, then continue aggregating input.
374-
Ok(Some(batch)) => {
380+
(Ok(Some(batch)), _) => {
375381
let table_memory = Self::reservation_size_for_table(
376382
&table,
377383
spill_context.as_deref(),
@@ -385,14 +391,15 @@ impl ClusteredSingleAggregateStream {
385391
},
386392
)
387393
}
394+
(Ok(None), Some(oom)) => Self::break_with_err(oom),
388395
// Can't do early emit, continue aggregating.
389-
Ok(None) => ControlFlow::Continue(
396+
(Ok(None), None) => ControlFlow::Continue(
390397
ClusteredSingleAggregateState::ReadingInput {
391398
table,
392399
spill_context,
393400
},
394401
),
395-
Err(e) => Self::break_with_err(e),
402+
(Err(e), _) => Self::break_with_err(e),
396403
}
397404
}
398405
Poll::Ready(Some(Err(e))) => Self::break_with_err(e),
@@ -762,6 +769,11 @@ impl RecordBatchStream for ClusteredSingleAggregateStream {
762769
mod tests {
763770
use super::*;
764771
use crate::aggregates::PhysicalGroupBy;
772+
use crate::aggregates::clustered_test_util::{
773+
assert_completed_groups_emitted_under_limit,
774+
assert_resources_exhausted_under_limit, full_batches, held_memory,
775+
single_key_batches, sum_over_sorted_input,
776+
};
765777
use crate::collect;
766778
use crate::test::TestMemoryExec;
767779
use arrow::array::Int64Array;
@@ -851,4 +863,21 @@ mod tests {
851863
);
852864
Ok(())
853865
}
866+
867+
#[tokio::test]
868+
async fn fully_clustered_completed_groups_under_memory_pressure() -> Result<()> {
869+
let plan = sum_over_sorted_input(AggregateMode::Single, &["k"], full_batches())?;
870+
assert_eq!(plan.group_clustering_mode(), &GroupClusteringMode::Full);
871+
assert_completed_groups_emitted_under_limit(&plan).await
872+
}
873+
874+
/// A single key never completes a group before the input ends. The limit
875+
/// fits only the initial table.
876+
#[tokio::test]
877+
async fn memory_pressure_without_completed_groups() -> Result<()> {
878+
let plan =
879+
sum_over_sorted_input(AggregateMode::Single, &["k"], single_key_batches())?;
880+
let limit = held_memory(&plan).await?;
881+
assert_resources_exhausted_under_limit(&plan, limit).await
882+
}
854883
}

0 commit comments

Comments
 (0)