Skip to content

Commit 1608ee7

Browse files
authored
refactor(hash-aggr): Let partial-reduce mode aggregation early emit when OOM (apache#24785)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes apache#123` indicates that this PR will close issue apache#123. --> Part of apache#22710 ## Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. Please explain the problem you are trying to solve in terms of the user-visible behavior, rather than the implementation. For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the implementation. "COUNT(DISTINCT) returns wrong results when the column contains nulls" is the user-visible problem. --> See apache#24486 for the rationale. That discussion covers the issue and three potential solutions: error, early-emit, and spill. This PR implements the early-emit behavior agreed on there. ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here, but it is sometimes worth providing a summary of the individual changes in this PR. --> Key changes: In datafusion/physical-plan/src/aggregates/partial_reduce_stream.rs - top comment explains the high-level ideas - To understand the implementation, start from `poll_next()` and follow along ## Are these changes tested? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> UTs (note partial-reduce aggregation can't be planned from SQL, so we can't do sqllogictests here) ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. If there are any breaking changes to public APIs, please add the `api change` label. --> No
1 parent fefc227 commit 1608ee7

2 files changed

Lines changed: 359 additions & 61 deletions

File tree

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

Lines changed: 162 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -187,7 +187,6 @@ use datafusion_common::{
187187
assert_eq_or_internal_err, internal_err, not_impl_err,
188188
};
189189
use datafusion_execution::TaskContext;
190-
use datafusion_execution::memory_pool::MemoryLimit;
191190
use datafusion_expr::{Accumulator, Aggregate};
192191
use datafusion_physical_expr::aggregate::AggregateFunctionExpr;
193192
use datafusion_physical_expr::equivalence::ProjectionMapping;
@@ -1308,12 +1307,7 @@ impl AggregateExec {
13081307
&& self.group_by.is_single()
13091308
}
13101309

1311-
fn should_use_partial_reduce_hash_stream(&self, context: &TaskContext) -> bool {
1312-
// TODO: implement memory-limited path and remove this limitation
1313-
if matches!(context.memory_pool().memory_limit(), MemoryLimit::Finite(_)) {
1314-
return false;
1315-
}
1316-
1310+
fn should_use_partial_reduce_hash_stream(&self, _context: &TaskContext) -> bool {
13171311
self.mode == AggregateMode::PartialReduce
13181312
&& self.limit_options.is_none()
13191313
&& self.input_order_mode == InputOrderMode::Linear
@@ -3241,7 +3235,7 @@ mod tests {
32413235

32423236
use arrow::array::{
32433237
BooleanArray, DictionaryArray, Float32Array, Float64Array, Int32Array,
3244-
Int64Array, StructArray, UInt32Array, UInt64Array,
3238+
Int64Array, NullArray, StructArray, UInt32Array, UInt64Array,
32453239
};
32463240
use arrow::compute::{SortOptions, concat_batches};
32473241
use arrow::datatypes::Int32Type;
@@ -4586,6 +4580,15 @@ mod tests {
45864580
}
45874581

45884582
fn partial_reduce_test_aggregate() -> Result<AggregateExec> {
4583+
partial_reduce_test_aggregate_with_batches(1)
4584+
}
4585+
4586+
/// Partial-reduce aggregate over `num_input_batches` identical input batches
4587+
/// of partial states, each reducing to groups `1, 2, 3` with sums
4588+
/// `50, 20, 30`.
4589+
fn partial_reduce_test_aggregate_with_batches(
4590+
num_input_batches: usize,
4591+
) -> Result<AggregateExec> {
45894592
let schema = Arc::new(Schema::new(vec![
45904593
Field::new("a", DataType::UInt32, false),
45914594
Field::new("b", DataType::Float64, false),
@@ -4618,7 +4621,7 @@ mod tests {
46184621
],
46194622
)?;
46204623
let partial_reduce_input = TestMemoryExec::try_new_exec(
4621-
&[vec![partial_state_batch]],
4624+
&[vec![partial_state_batch; num_input_batches]],
46224625
Arc::clone(&partial_schema),
46234626
None,
46244627
)?;
@@ -4654,26 +4657,162 @@ mod tests {
46544657
Ok(())
46554658
}
46564659

4657-
/// Spilling behavior is not implemented for partial-reduce stream yet, so fall
4658-
/// back to the existing `GroupedHashAggregateStream`
4660+
/// Partial-reduce hash aggregation emits its accumulated partial states early
4661+
/// under memory pressure instead of failing, and the early-emitted states
4662+
/// still merge into the correct result.
46594663
#[tokio::test]
4660-
async fn partial_reduce_aggregate_with_memory_limit_planning() -> Result<()> {
4661-
let partial_reduce = partial_reduce_test_aggregate()?;
4664+
async fn partial_reduce_aggregate_with_memory_limit_emits_early() -> Result<()> {
4665+
let num_input_batches = 3;
4666+
let partial_reduce =
4667+
partial_reduce_test_aggregate_with_batches(num_input_batches)?;
46624668
let runtime = RuntimeEnvBuilder::new()
46634669
.with_memory_limit(1, 1.0)
46644670
.build_arc()?;
4665-
let task_ctx =
4666-
Arc::new(
4667-
TaskContext::default()
4668-
.with_session_config(SessionConfig::new().set_bool(
4669-
"datafusion.execution.enable_migration_aggregate",
4670-
true,
4671-
))
4672-
.with_runtime(runtime),
4673-
);
4671+
// A batch size smaller than the number of flushed groups also covers
4672+
// splitting one flush across several output batches.
4673+
let batch_size = 2;
4674+
let task_ctx = Arc::new(
4675+
TaskContext::default()
4676+
.with_session_config(migrated_hash_session_config(batch_size))
4677+
.with_runtime(runtime),
4678+
);
46744679

46754680
let stream = partial_reduce.execute_typed(0, &task_ctx)?;
4676-
assert!(matches!(stream, StreamType::GroupedHash(_)));
4681+
assert!(matches!(stream, StreamType::PartialReduceHash(_)));
4682+
let stream: SendableRecordBatchStream = stream.into();
4683+
let output = collect(stream).await?;
4684+
4685+
// The table is flushed after every input batch, so each of the three
4686+
// groups is emitted once per input batch instead of being merged into a
4687+
// single row. Each flush is sliced into batches of 2 and 1 rows.
4688+
assert_eq!(output.len(), 2 * num_input_batches);
4689+
assert_snapshot!(batches_to_string(&output), @r"
4690+
+---+-------------+
4691+
| a | SUM(b)[sum] |
4692+
+---+-------------+
4693+
| 1 | 50.0 |
4694+
| 2 | 20.0 |
4695+
| 3 | 30.0 |
4696+
| 1 | 50.0 |
4697+
| 2 | 20.0 |
4698+
| 3 | 30.0 |
4699+
| 1 | 50.0 |
4700+
| 2 | 20.0 |
4701+
| 3 | 30.0 |
4702+
+---+-------------+
4703+
");
4704+
4705+
Ok(())
4706+
}
4707+
4708+
/// Same shape as [`partial_reduce_test_aggregate_with_batches`], but with multiple
4709+
/// group keys.
4710+
fn partial_reduce_test_aggregate_rows_multi_group_keys(
4711+
num_input_batches: usize,
4712+
) -> Result<AggregateExec> {
4713+
let schema = Arc::new(Schema::new(vec![
4714+
Field::new("a", DataType::UInt32, false),
4715+
Field::new("n", DataType::Null, true),
4716+
Field::new("b", DataType::Float64, false),
4717+
]));
4718+
let group_by = PhysicalGroupBy::new_single(vec![
4719+
(col("a", &schema)?, "a".to_string()),
4720+
(col("n", &schema)?, "n".to_string()),
4721+
]);
4722+
let aggregates: Vec<Arc<AggregateFunctionExpr>> = vec![Arc::new(
4723+
AggregateExprBuilder::new(sum_udaf(), vec![col("b", &schema)?])
4724+
.schema(Arc::clone(&schema))
4725+
.alias("SUM(b)")
4726+
.build()?,
4727+
)];
4728+
4729+
let empty_input =
4730+
TestMemoryExec::try_new_exec(&[vec![]], Arc::clone(&schema), None)?;
4731+
let partial = AggregateExec::try_new(
4732+
AggregateMode::Partial,
4733+
group_by.clone(),
4734+
aggregates.clone(),
4735+
vec![None],
4736+
empty_input,
4737+
Arc::clone(&schema),
4738+
)?;
4739+
let partial_schema = partial.schema();
4740+
let partial_state_batch = RecordBatch::try_new(
4741+
Arc::clone(&partial_schema),
4742+
vec![
4743+
Arc::new(UInt32Array::from(vec![1, 2, 1, 3])),
4744+
Arc::new(NullArray::new(4)),
4745+
Arc::new(Float64Array::from(vec![10.0, 20.0, 40.0, 30.0])),
4746+
],
4747+
)?;
4748+
let partial_reduce_input = TestMemoryExec::try_new_exec(
4749+
&[vec![partial_state_batch; num_input_batches]],
4750+
Arc::clone(&partial_schema),
4751+
None,
4752+
)?;
4753+
4754+
AggregateExec::try_new(
4755+
AggregateMode::PartialReduce,
4756+
group_by,
4757+
aggregates,
4758+
vec![None],
4759+
partial_reduce_input,
4760+
partial_schema,
4761+
)
4762+
}
4763+
4764+
#[tokio::test]
4765+
async fn partial_reduce_aggregate_with_memory_limit_emits_early_multi_group_keys()
4766+
-> Result<()> {
4767+
let num_input_batches = 3;
4768+
let partial_reduce =
4769+
partial_reduce_test_aggregate_rows_multi_group_keys(num_input_batches)?;
4770+
4771+
// Pin the representation: this is exactly the condition
4772+
// `new_group_values` uses to pick `GroupValuesRows` over
4773+
// `GroupValuesColumn`. If a `Null` `GroupColumn` is ever added, this
4774+
// assertion fires and the test stops covering the row-encoded path.
4775+
let group_schema = partial_reduce
4776+
.group_by
4777+
.group_schema(&partial_reduce.schema())?;
4778+
assert!(
4779+
!group_values::multi_group_by::supported_schema(&group_schema),
4780+
"expected the Null group column to force the GroupValuesRows fallback"
4781+
);
4782+
4783+
let runtime = RuntimeEnvBuilder::new()
4784+
.with_memory_limit(1, 1.0)
4785+
.build_arc()?;
4786+
let batch_size = 2;
4787+
let task_ctx = Arc::new(
4788+
TaskContext::default()
4789+
.with_session_config(migrated_hash_session_config(batch_size))
4790+
.with_runtime(runtime),
4791+
);
4792+
4793+
let stream = partial_reduce.execute_typed(0, &task_ctx)?;
4794+
assert!(matches!(stream, StreamType::PartialReduceHash(_)));
4795+
let stream: SendableRecordBatchStream = stream.into();
4796+
let output = collect(stream).await?;
4797+
4798+
// Same flush cadence as the column-backed test: one flush per input
4799+
// batch, each sliced into batches of 2 and 1 rows.
4800+
assert_eq!(output.len(), 2 * num_input_batches);
4801+
assert_snapshot!(batches_to_string(&output), @r"
4802+
+---+---+-------------+
4803+
| a | n | SUM(b)[sum] |
4804+
+---+---+-------------+
4805+
| 1 | | 50.0 |
4806+
| 2 | | 20.0 |
4807+
| 3 | | 30.0 |
4808+
| 1 | | 50.0 |
4809+
| 2 | | 20.0 |
4810+
| 3 | | 30.0 |
4811+
| 1 | | 50.0 |
4812+
| 2 | | 20.0 |
4813+
| 3 | | 30.0 |
4814+
+---+---+-------------+
4815+
");
46774816

46784817
Ok(())
46794818
}

0 commit comments

Comments
 (0)