Skip to content

Commit 1bfc59e

Browse files
viiryaIsaac
andauthored
fix: release clustered aggregate table capacity after emitting completed groups on memory pressure (apache#26726)
## Which issue does this PR close? - Closes apache#26725. ## Rationale for this change When a reservation is refused, the clustered aggregate streams emit their completed groups instead of failing. apache#26576 did this for the partial stream under full group clustering, and apache#26637 did it for the final and single streams. The remaining table keeps the capacity it grew for the batch, so re-reserving it can still fail with `ResourcesExhausted`. With 8192 distinct `Int64` keys per batch, the partial table still needs 344 KB, while a table holding only the active group needs 5.6 KB. The issue has the details. ## What changes are included in this PR? - `GroupValues::shrink_to_fit` (new, does nothing by default) releases capacity that the stored groups do not need. It is implemented for: - `GroupValuesPrimitive`: the hash table and values. - `GroupValuesClustered`: `new_groups`. - `GroupValuesColumn`: the hash table and the scratch buffers of one `intern` call. - `GroupValuesRows`: the hash table, hashes, and rows buffers. `GroupValuesBytes` and `GroupValuesBytesView` already rebuild their map on `EmitTo::First`. - `ClusteredAggregateTable::shrink_to_fit` (new) calls it and also releases `group_indices`. - After a refused reservation, `ClusteredPartialAggregateStream` (under full group clustering), `ClusteredFinalAggregateStream`, and `ClusteredSingleAggregateStream` emit the completed groups as before and then call `shrink_to_fit`. The output does not change, and each stream still returns the refusal when no group is complete. The path without memory pressure does not call it. Accumulator scratch, such as the `APPROX_DISTINCT` hashes, is not released yet; see apache#26781. ## What is the testing strategy for this PR? - `clustered_partial_stream::tests::completed_groups_under_memory_pressure` runs three batches of 8192 distinct keys whose boundaries share a key, under a 100 KiB limit, and compares the output exactly with an unlimited run. It covers one key each for `GroupValuesPrimitive` (`Int64`), `GroupValuesClustered` (`Int64, Int64`), `GroupValuesColumn` (`Float64, Float64`), and `GroupValuesRows` (`Int64, List`). All four cases fail on `main` with `ResourcesExhausted`. The `Int64`, `Float64, Float64`, and `Int64, List` cases also fail if only `group_indices` is released. - `completed_groups_release_batch_capacity` in `clustered_final_stream` and `clustered_single_stream` runs the same input with an `Int64` key under the same limit, using the new `distinct_key_batches` and `assert_output_unchanged_under_limit` helpers in `clustered_test_util`. Both fail on `main` with `ResourcesExhausted`. ## Are there any user-facing changes? No. `GroupValues` gains a method with a default implementation. This pull request and its description were written by Isaac. --------- Co-authored-by: Isaac <[email protected]>
1 parent 98360e3 commit 1bfc59e

10 files changed

Lines changed: 262 additions & 11 deletions

File tree

‎datafusion/physical-plan/src/aggregates/aggregate_hash_table/common_clustered.rs‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -286,6 +286,17 @@ impl<AggrMode> ClusteredAggregateTable<AggrMode> {
286286
+ self.buffer.group_indices.allocated_size()
287287
}
288288

289+
/// Releases the capacity that the buffer holds beyond its stored groups,
290+
/// such as hash table slots and the per-batch `group_indices` scratch, so
291+
/// that [`Self::memory_size`] reflects the remaining groups.
292+
///
293+
/// Accumulator capacity is not released.
294+
pub(in crate::aggregates) fn shrink_to_fit(&mut self) {
295+
self.buffer.group_values.shrink_to_fit();
296+
self.buffer.group_indices.clear();
297+
self.buffer.group_indices.shrink_to_fit();
298+
}
299+
289300
pub(in crate::aggregates) fn metrics(&self) -> ClusteredAggregateTableMetrics {
290301
ClusteredAggregateTableMetrics {
291302
group_by: self.group_by_metrics.clone(),

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

Lines changed: 19 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -364,6 +364,11 @@ impl Aggregating {
364364
None => continue,
365365
}
366366
};
367+
if oom.is_some() {
368+
// Release the capacity the table grew for this batch so that
369+
// reserving the remaining groups can succeed.
370+
self.table.shrink_to_fit();
371+
}
367372
timer.done();
368373
return Ok(Some(ExecutionStage::Outputting(Outputting {
369374
batch,
@@ -459,9 +464,9 @@ mod tests {
459464
use crate::aggregates::GroupClusteringMode;
460465
use crate::aggregates::PhysicalGroupBy;
461466
use crate::aggregates::clustered_test_util::{
462-
assert_completed_groups_emitted_under_limit,
463-
assert_resources_exhausted_under_limit, full_batches, held_memory,
464-
single_key_batches, sum_over_sorted_input,
467+
assert_completed_groups_emitted_under_limit, assert_output_unchanged_under_limit,
468+
assert_resources_exhausted_under_limit, distinct_key_batches, full_batches,
469+
held_memory, single_key_batches, sum_over_sorted_input,
465470
};
466471
use crate::common::collect;
467472
use crate::test::TestMemoryExec;
@@ -743,6 +748,17 @@ mod tests {
743748
assert_completed_groups_emitted_under_limit(&plan).await
744749
}
745750

751+
/// The limit fits the active group, but not the capacity the table grows
752+
/// for one batch, so the table must release it after the completed groups
753+
/// are emitted.
754+
#[tokio::test]
755+
async fn completed_groups_release_batch_capacity() -> Result<()> {
756+
let plan =
757+
sum_over_sorted_input(AggregateMode::Final, &["k"], distinct_key_batches())?;
758+
assert_eq!(plan.group_clustering_mode(), &GroupClusteringMode::Full);
759+
assert_output_unchanged_under_limit(&plan, 100 * 1024).await
760+
}
761+
746762
/// A single key never completes a group before the input ends. The limit
747763
/// fits only the initial table.
748764
#[tokio::test]

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

Lines changed: 143 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,9 @@ use crate::{SendableRecordBatchStream, metrics};
7474
///
7575
/// If the reservation after an input batch fails, `ClusteredPartialAggregateStream`
7676
/// still emits the completed groups, and returns the error only when no group is
77-
/// complete.
77+
/// complete. After the emit it releases the capacity the table grew for the batch,
78+
/// such as hash table slots and per-batch scratch buffers, so only the active
79+
/// group stays reserved.
7880
///
7981
/// ## Partial group clustering
8082
///
@@ -249,6 +251,8 @@ impl ClusteredPartialAggregateStream {
249251
/// 3. Prepare output:
250252
/// - A prefix of groups is complete: materialize the entire prefix once,
251253
/// retaining the input and active groups to resume aggregation.
254+
/// - On memory pressure with full group clustering, materialize the
255+
/// completed prefix and release the capacity the table grew for it.
252256
/// - On memory pressure with partial group clustering, materialize all
253257
/// current states, including incomplete groups, and reset the table.
254258
/// - At EOF, materialize all remaining states and prepare to output.
@@ -306,11 +310,17 @@ impl Aggregating {
306310
let output = match reservation.try_resize(self.table.memory_size()) {
307311
Ok(()) => self.table.take_completed_state_batch()?,
308312
Err(oom @ DataFusionError::ResourcesExhausted(_)) => {
309-
// Partial group clustering may have an unbounded active key range.
310-
// The final stage can merge incomplete states emitted here.
311313
if matches!(self.table.group_clustering(), GroupClustering::Full(_)) {
312-
Some(self.table.take_completed_state_batch()?.ok_or(oom)?)
314+
// Only the active group remains after the emit. Release the
315+
// capacity the table grew for this batch so that reserving
316+
// the table can succeed.
317+
let batch =
318+
self.table.take_completed_state_batch()?.ok_or(oom)?;
319+
self.table.shrink_to_fit();
320+
Some(batch)
313321
} else {
322+
// Partial group clustering may have an unbounded active key range.
323+
// The final stage can merge incomplete states emitted here.
314324
Some(self.table.take_state_batch()?.ok_or(oom)?)
315325
}
316326
}
@@ -408,11 +418,140 @@ impl Outputting {
408418

409419
#[cfg(test)]
410420
mod tests {
421+
use std::ops::Range;
422+
411423
use super::*;
412424
use crate::aggregates::GroupClusteringMode;
425+
use crate::aggregates::PhysicalGroupBy;
413426
use crate::aggregates::clustered_test_util::{
414427
assert_completed_groups_emitted_under_limit, full_batches, sum_over_sorted_input,
415428
};
429+
use crate::test::TestMemoryExec;
430+
use arrow::array::{ArrayRef, Float64Array, Int64Array, ListArray};
431+
use arrow::datatypes::{DataType, Field, Int64Type, Schema};
432+
use datafusion_common::test_util::batches_to_string;
433+
use datafusion_execution::memory_pool::{
434+
GreedyMemoryPool, MemoryPool, UnboundedMemoryPool,
435+
};
436+
use datafusion_execution::runtime_env::RuntimeEnvBuilder;
437+
use datafusion_functions_aggregate::sum::sum_udaf;
438+
use datafusion_physical_expr::PhysicalSortExpr;
439+
use datafusion_physical_expr::aggregate::AggregateExprBuilder;
440+
use datafusion_physical_expr::expressions::col;
441+
use datafusion_physical_expr_common::sort_expr::LexOrdering;
442+
443+
/// One batch per range. Every key column and the value column `v` hold the
444+
/// range values, as the given key types.
445+
fn batches(
446+
key_types: &[DataType],
447+
ranges: &[Range<i64>],
448+
) -> Result<Vec<RecordBatch>> {
449+
let mut fields: Vec<_> = key_types
450+
.iter()
451+
.enumerate()
452+
.map(|(i, data_type)| Field::new(format!("k{i}"), data_type.clone(), false))
453+
.collect();
454+
fields.push(Field::new("v", DataType::Int64, false));
455+
let schema = Arc::new(Schema::new(fields));
456+
ranges
457+
.iter()
458+
.map(|range| {
459+
let int64: ArrayRef =
460+
Arc::new(Int64Array::from_iter_values(range.clone()));
461+
let mut columns = key_types
462+
.iter()
463+
.map(|data_type| match data_type {
464+
DataType::Int64 => Arc::clone(&int64),
465+
DataType::Float64 => Arc::new(Float64Array::from_iter_values(
466+
range.clone().map(|v| v as f64),
467+
)),
468+
DataType::List(_) => {
469+
Arc::new(ListArray::from_iter_primitive::<Int64Type, _, _>(
470+
range.clone().map(|v| Some([Some(v)])),
471+
))
472+
}
473+
_ => unreachable!("unsupported key type {data_type}"),
474+
})
475+
.collect::<Vec<_>>();
476+
columns.push(int64);
477+
Ok(RecordBatch::try_new(Arc::clone(&schema), columns)?)
478+
})
479+
.collect()
480+
}
481+
482+
/// Runs a partial `SUM(v) GROUP BY k0, ..` over `batches`, which are sorted
483+
/// on every key.
484+
async fn run(
485+
batches: Vec<RecordBatch>,
486+
pool: Arc<dyn MemoryPool>,
487+
) -> Result<Vec<RecordBatch>> {
488+
let schema = batches[0].schema();
489+
let keys = (0..schema.fields().len() - 1)
490+
.map(|i| Ok((col(&format!("k{i}"), &schema)?, format!("k{i}"))))
491+
.collect::<Result<Vec<_>>>()?;
492+
let ordering = LexOrdering::new(
493+
keys.iter()
494+
.map(|(expr, _)| PhysicalSortExpr::new_default(Arc::clone(expr))),
495+
)
496+
.unwrap();
497+
let input = TestMemoryExec::try_new(&[batches], Arc::clone(&schema), None)?
498+
.try_with_sort_information(vec![ordering])?;
499+
let aggregate = AggregateExec::try_new(
500+
AggregateMode::Partial,
501+
PhysicalGroupBy::new_single(keys),
502+
vec![Arc::new(
503+
AggregateExprBuilder::new(sum_udaf(), vec![col("v", &schema)?])
504+
.schema(Arc::clone(&schema))
505+
.alias("sum")
506+
.build()?,
507+
)],
508+
vec![None],
509+
Arc::new(input),
510+
Arc::clone(&schema),
511+
)?;
512+
assert_eq!(aggregate.group_clustering_mode, GroupClusteringMode::Full);
513+
let context = Arc::new(
514+
TaskContext::default().with_runtime(
515+
RuntimeEnvBuilder::new()
516+
.with_memory_pool(pool)
517+
.build_arc()?,
518+
),
519+
);
520+
let stream =
521+
ClusteredPartialAggregateStream::new(&aggregate, &context, 0)?.into_stream();
522+
crate::common::collect(stream).await
523+
}
524+
525+
/// Every row is a distinct group, and each batch shares its first key with
526+
/// the previous one, so the active group spans the batches. Aggregating a
527+
/// batch grows the table for about 8192 groups, for example the single-key
528+
/// hash table (~272 KB) and the `group_indices` scratch (64 KB). After the
529+
/// completed groups are emitted, the table must release that capacity, or
530+
/// reserving it fails the limit although the active group needs a few KB.
531+
/// The output must not change.
532+
#[tokio::test]
533+
async fn completed_groups_under_memory_pressure() -> Result<()> {
534+
let list = DataType::List(Arc::new(Field::new_list_field(DataType::Int64, true)));
535+
for key_types in [
536+
// `GroupValuesPrimitive`
537+
vec![DataType::Int64],
538+
// `GroupValuesClustered`
539+
vec![DataType::Int64, DataType::Int64],
540+
// `GroupValuesColumn`
541+
vec![DataType::Float64, DataType::Float64],
542+
// `GroupValuesRows`
543+
vec![DataType::Int64, list],
544+
] {
545+
let input = || batches(&key_types, &[0..8193, 8192..16385, 16384..24576]);
546+
let expected =
547+
run(input()?, Arc::new(UnboundedMemoryPool::default())).await?;
548+
let actual = run(input()?, Arc::new(GreedyMemoryPool::new(100 * 1024)))
549+
.await
550+
.map_err(|e| e.context(format!("key types {key_types:?}")))?;
551+
assert_eq!(batches_to_string(&actual), batches_to_string(&expected));
552+
}
553+
Ok(())
554+
}
416555

417556
#[tokio::test]
418557
async fn fully_clustered_completed_groups_under_memory_pressure() -> Result<()> {

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

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -364,7 +364,12 @@ impl ClusteredSingleAggregateStream {
364364
match (result, oom) {
365365
// Some finalized groups can be emitted. Yield them in
366366
// slices, then continue aggregating input.
367-
(Ok(Some(batch)), _) => {
367+
(Ok(Some(batch)), oom) => {
368+
if oom.is_some() {
369+
// Release the capacity the table grew for this batch
370+
// so that reserving the remaining groups can succeed.
371+
table.shrink_to_fit();
372+
}
368373
let table_memory = Self::reservation_size_for_table(
369374
&table,
370375
spill_context.as_deref(),
@@ -757,9 +762,9 @@ mod tests {
757762
use super::*;
758763
use crate::aggregates::PhysicalGroupBy;
759764
use crate::aggregates::clustered_test_util::{
760-
assert_completed_groups_emitted_under_limit,
761-
assert_resources_exhausted_under_limit, full_batches, held_memory,
762-
single_key_batches, sum_over_sorted_input,
765+
assert_completed_groups_emitted_under_limit, assert_output_unchanged_under_limit,
766+
assert_resources_exhausted_under_limit, distinct_key_batches, full_batches,
767+
held_memory, single_key_batches, sum_over_sorted_input,
763768
};
764769
use crate::collect;
765770
use crate::test::TestMemoryExec;
@@ -858,6 +863,17 @@ mod tests {
858863
assert_completed_groups_emitted_under_limit(&plan).await
859864
}
860865

866+
/// The limit fits the active group, but not the capacity the table grows
867+
/// for one batch, so the table must release it after the completed groups
868+
/// are emitted.
869+
#[tokio::test]
870+
async fn completed_groups_release_batch_capacity() -> Result<()> {
871+
let plan =
872+
sum_over_sorted_input(AggregateMode::Single, &["k"], distinct_key_batches())?;
873+
assert_eq!(plan.group_clustering_mode(), &GroupClusteringMode::Full);
874+
assert_output_unchanged_under_limit(&plan, 100 * 1024).await
875+
}
876+
861877
/// A single key never completes a group before the input ends. The limit
862878
/// fits only the initial table.
863879
#[tokio::test]

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

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,17 @@ pub(super) fn full_batches() -> Vec<Vec<Vec<i64>>> {
3535
vec![vec![(0..=256).collect()], vec![(256..=512).collect()]]
3636
}
3737

38+
/// Key columns of three batches of 8192 distinct keys sorted on `k`, where each
39+
/// batch shares its first key with the previous one. Aggregating a batch grows
40+
/// the table for about 8192 groups, while the active group needs a few KB.
41+
pub(super) fn distinct_key_batches() -> Vec<Vec<Vec<i64>>> {
42+
vec![
43+
vec![(0..8193).collect()],
44+
vec![(8192..16385).collect()],
45+
vec![(16384..24576).collect()],
46+
]
47+
}
48+
3849
/// Key column of two batches that hold the same single key, so no group
3950
/// completes before the input ends.
4051
pub(super) fn single_key_batches() -> Vec<Vec<Vec<i64>>> {
@@ -168,6 +179,20 @@ pub(super) async fn assert_completed_groups_emitted_under_limit(
168179
Ok(())
169180
}
170181

182+
/// Runs `plan` without a memory limit, then under `limit`. The result must not
183+
/// change.
184+
pub(super) async fn assert_output_unchanged_under_limit(
185+
plan: &AggregateExec,
186+
limit: usize,
187+
) -> Result<()> {
188+
let (expected, _) =
189+
collect_with_held_memory(plan, Arc::new(UnboundedMemoryPool::default())).await?;
190+
let (actual, _) =
191+
collect_with_held_memory(plan, Arc::new(GreedyMemoryPool::new(limit))).await?;
192+
assert_eq!(batches_to_string(&actual), batches_to_string(&expected));
193+
Ok(())
194+
}
195+
171196
/// Runs `plan` under `limit`, where emitting completed groups cannot bring the
172197
/// table under the limit, so the refused reservation must be returned.
173198
pub(super) async fn assert_resources_exhausted_under_limit(

‎datafusion/physical-plan/src/aggregates/group_values/mod.rs‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,16 @@ pub trait GroupValues: Send {
120120

121121
/// Clear the contents and shrink the capacity to the size of the batch (free up memory usage)
122122
fn clear_shrink(&mut self, num_rows: usize);
123+
124+
/// Keeps the stored groups but releases capacity they do not need, such as
125+
/// hash table slots and per-batch scratch buffers, so that [`Self::size`]
126+
/// reflects the stored groups. For example, after [`EmitTo::First`] removes
127+
/// most groups, the hash table may keep the slots it grew for them.
128+
///
129+
/// The default does nothing.
130+
///
131+
/// [`EmitTo::First`]: datafusion_expr::EmitTo::First
132+
fn shrink_to_fit(&mut self) {}
123133
}
124134

125135
/// Return a specialized implementation of [`GroupValues`] for the given schema.

‎datafusion/physical-plan/src/aggregates/group_values/multi_group_by/clustered.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -168,6 +168,12 @@ impl GroupValues for GroupValuesClustered {
168168
true
169169
}
170170

171+
fn shrink_to_fit(&mut self) {
172+
// Scratch for one `intern` call.
173+
self.new_groups.clear();
174+
self.new_groups.shrink_to_fit();
175+
}
176+
171177
fn clear_shrink(&mut self, num_rows: usize) {
172178
self.columns = GroupValuesColumn::<true>::build_group_columns(&self.schema)
173179
.expect("schema validated by GroupValuesClustered::try_new");

‎datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1222,6 +1222,19 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
12221222
true
12231223
}
12241224

1225+
fn shrink_to_fit(&mut self) {
1226+
self.map.shrink_to_fit(|(hash, _)| *hash);
1227+
self.map_size = self.map.capacity() * size_of::<(u64, usize)>();
1228+
// Scratch for one `intern` call.
1229+
self.hashes_buffer.clear();
1230+
self.hashes_buffer.shrink_to_fit();
1231+
if !STREAMING {
1232+
self.emit_group_index_list_buffer.clear();
1233+
self.emit_group_index_list_buffer.shrink_to_fit();
1234+
self.vectorized_operation_buffers.clear_shrink(0);
1235+
}
1236+
}
1237+
12251238
fn clear_shrink(&mut self, num_rows: usize) {
12261239
// Reset to a fresh column-builder vector. The schema was validated
12271240
// in `try_new`, so rebuilding cannot fail unless something else

‎datafusion/physical-plan/src/aggregates/group_values/row.rs‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -279,6 +279,16 @@ impl GroupValues for GroupValuesRows {
279279
true
280280
}
281281

282+
fn shrink_to_fit(&mut self) {
283+
self.map.shrink_to_fit(|(hash, _)| *hash);
284+
// Scratch for one `intern` call.
285+
self.hashes_buffer.clear();
286+
self.hashes_buffer.shrink_to_fit();
287+
if self.rows_buffer.size() > self.initial_rows_buffer_size {
288+
self.rows_buffer = Self::new_rows_buffer(&self.row_converter);
289+
}
290+
}
291+
282292
fn clear_shrink(&mut self, num_rows: usize) {
283293
self.group_values = if num_rows == 0 {
284294
None

0 commit comments

Comments
 (0)