Skip to content

Commit f40f3c9

Browse files
xavleeTristan1900
authored andcommitted
feat: stream aggregates over grouped input (apache#24497)
## Which issue does this PR close? - Closes apache#24438. - Builds on apache#24737, apache#24697, and apache#24698 (all merged). ## Rationale for this change An aggregate can emit a completed group once it knows that the same complete grouping tuple cannot appear again in its input partition. `EquivalenceProperties::grouping_satisfy` now provides that guarantee for both lexicographically ordered input and explicitly grouped input. For example, these complete `(key, time_bin)` groups are contiguous even though their values are not globally sorted: ```text (A, 20), (A, 20) | (B, 20), (B, 20) | (A, 0), (A, 0) ``` The aggregate can therefore release each group as its run ends. Its clustering mode describes that guarantee, while equivalence properties describe any actual output ordering. ## What changes are included in this PR? - Query the input equivalence properties for the complete `GROUP BY` tuple during `AggregateExec` construction. - Select `GroupClusteringMode::Full` when complete grouping tuple is satisfied, at least one grouping expression is non-constant, and grouping uses one non-nulling mask. - Select clustered execution for grouped input, allowing completed groups to be emitted incrementally. - Use input group metadata for clustered execution in `Single`, `SinglePartitioned`, and `Partial` aggregations. In a two-stage plan, the partial aggregate clears explicit grouping metadata from its output, so this property alone does not enabled clustered final aggregation. The final stage can still use ordering provided by its own input. ```text input grouping: [[key, time_bin]] GROUP BY: [key, time_bin] output ordering: none grouping_satisfy(GROUP BY) -> GroupClusteringMode::Full -> EmissionType::Incremental -> ClusteredSingleAggregateStream ``` ## Stack 1. [apache#24737 — test: cover unsorted contiguous groups in one partition](apache#24737) (merged) 2. [apache#24697 — refactor: use group clustering terminology in aggregate execution](apache#24697) (merged) 3. [apache#24698 — feat: add grouping equivalence properties](apache#24698) (merged) 4. [apache#24497 — feat: stream aggregates over grouped input](apache#24497) ← **this PR** ## Are these changes tested? The characterization test from apache#24737 declares its complete grouping tuple and verifies `GroupClusteringMode::Full`, `EmissionType::Incremental`, and `ClusteredSingleAggregateStream`. It uses `BarrierExec` to hold back the second input batch until the first completed group is emitted, then checks the full result, including a group spanning both batches. Regression tests cover `PartialReduce` with ordered and explicitly grouped input, and constant-only grouping with both a literal and a column made constant by a filter. A projection test verifies that a semantically equivalent `date_bin` grouping tuple reaches `AggregateExec` and enables incremental emission. A repeated-mask regression compares grouped and unannotated inputs and verifies that both produce the same merged groups with `GroupClusteringMode::None`. ## Are there any user-facing changes? Yes. Aggregates whose complete grouping tuple is satisfied by the input equivalence properties can execute with full group clustering and incremental emission on unsorted input. ## Review this layer [View only this PR layer](xavlee/datafusion@a616831...3b42751) --------- Co-authored-by: Jay Zhan <[email protected]> (cherry picked from commit e7c51c7)
1 parent b190abc commit f40f3c9

3 files changed

Lines changed: 262 additions & 35 deletions

File tree

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

Lines changed: 219 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -48,10 +48,11 @@
4848
//!
4949
//! See [`PartialHashAggregateStream`] and [`FinalHashAggregateStream`] for details.
5050
//!
51-
//! ### Ordering optimization
51+
//! ### Group clustering optimization
5252
//!
53-
//! When the input is ordered by the group key, an ordered fast path is used. It
54-
//! uses a similar two-stage hash aggregation with an early-emission optimization.
53+
//! When the input is ordered by group keys, or its equivalence properties declare
54+
//! them grouped, rows are clustered by those keys. The clustered paths use this
55+
//! guarantee to emit completed groups early.
5556
//!
5657
//! ```text
5758
//! AggregateExec (final, ordered)
@@ -1020,9 +1021,7 @@ impl AggregateExec {
10201021
{
10211022
GroupClusteringMode::None
10221023
} else if has_non_constant_groupby_exprs
1023-
&& indices.len() == groupby_exprs.len()
1024-
&& !indices.is_empty()
1025-
&& group_by.groups.len() == 1
1024+
&& input_eq_properties.grouping_satisfy(groupby_exprs.iter().cloned())?
10261025
{
10271026
GroupClusteringMode::Full
10281027
} else if has_non_constant_groupby_exprs && !indices.is_empty() {
@@ -3188,15 +3187,15 @@ mod tests {
31883187
use crate::test::TestMemoryExec;
31893188
use crate::test::assert_is_pending;
31903189
use crate::test::exec::{
3191-
BlockingExec, StatisticsExec, assert_strong_count_converges_to_zero,
3190+
BarrierExec, BlockingExec, StatisticsExec, assert_strong_count_converges_to_zero,
31923191
};
31933192

31943193
use arrow::array::{
31953194
BooleanArray, DictionaryArray, Float32Array, Float64Array, Int32Array,
31963195
Int64Array, StructArray, UInt32Array, UInt64Array,
31973196
};
31983197
use arrow::compute::{SortOptions, concat_batches};
3199-
use arrow::datatypes::Int32Type;
3198+
use arrow::datatypes::{Int32Type, TimeUnit};
32003199
use datafusion_common::test_util::{batches_to_sort_string, batches_to_string};
32013200
use datafusion_common::{DataFusionError, internal_err};
32023201
use datafusion_execution::config::SessionConfig;
@@ -3207,6 +3206,7 @@ mod tests {
32073206
Accumulator, AggregateUDF, AggregateUDFImpl, EmitTo, GroupsAccumulator, Operator,
32083207
Signature, Volatility,
32093208
};
3209+
use datafusion_functions::datetime::date_bin;
32103210
use datafusion_functions_aggregate::approx_percentile_cont::approx_percentile_cont_udaf;
32113211
use datafusion_functions_aggregate::array_agg::array_agg_udaf;
32123212
use datafusion_functions_aggregate::average::avg_udaf;
@@ -3215,10 +3215,9 @@ mod tests {
32153215
use datafusion_functions_aggregate::median::median_udaf;
32163216
use datafusion_functions_aggregate::min_max::min_udaf;
32173217
use datafusion_functions_aggregate::sum::sum_udaf;
3218-
use datafusion_physical_expr::Partitioning;
3219-
use datafusion_physical_expr::PhysicalSortExpr;
32203218
use datafusion_physical_expr::aggregate::AggregateExprBuilder;
32213219
use datafusion_physical_expr::expressions::{Literal, NotExpr, binary};
3220+
use datafusion_physical_expr::{Partitioning, PhysicalSortExpr, ScalarFunctionExpr};
32223221

32233222
use crate::projection::ProjectionExec;
32243223
use crate::repartition::RepartitionExec;
@@ -4790,71 +4789,104 @@ mod tests {
47904789
}
47914790

47924791
#[tokio::test]
4793-
async fn unsorted_contiguous_groups_use_final_emission() -> Result<()> {
4792+
async fn unsorted_contiguous_groups_use_incremental_emission() -> Result<()> {
47944793
let schema = Arc::new(Schema::new(vec![
47954794
Field::new("key", DataType::Int32, false),
47964795
Field::new("time_bin", DataType::Int64, false),
47974796
Field::new("value", DataType::Int64, false),
47984797
]));
4799-
// Two sorted logical runs are emitted as batches in one DataFusion
4800-
// partition. Every distinct grouping tuple occupies one contiguous range,
4801-
// but tuple order resets at the batch boundary, so (key, time_bin) is not
4802-
// globally sorted.
4798+
// Every grouping tuple occupies one contiguous range in a single
4799+
// partition, with (2, 20) spanning both batches. Tuple order resets
4800+
// within the second batch, so (key, time_bin) is not globally sorted.
48034801
let input_batches = vec![
48044802
RecordBatch::try_new(
48054803
Arc::clone(&schema),
48064804
vec![
4807-
Arc::new(Int32Array::from(vec![1, 1, 2, 2])),
4808-
Arc::new(Int64Array::from(vec![20, 20, 20, 20])),
4809-
Arc::new(Int64Array::from(vec![10, 20, 30, 40])),
4805+
Arc::new(Int32Array::from(vec![1, 1, 2])),
4806+
Arc::new(Int64Array::from(vec![20, 20, 20])),
4807+
Arc::new(Int64Array::from(vec![10, 20, 30])),
48104808
],
48114809
)?,
48124810
RecordBatch::try_new(
48134811
Arc::clone(&schema),
48144812
vec![
4815-
Arc::new(Int32Array::from(vec![1, 1, 2, 2])),
4816-
Arc::new(Int64Array::from(vec![0, 0, 0, 0])),
4817-
Arc::new(Int64Array::from(vec![50, 60, 70, 80])),
4813+
Arc::new(Int32Array::from(vec![2, 1, 1, 2, 2])),
4814+
Arc::new(Int64Array::from(vec![20, 0, 0, 0, 0])),
4815+
Arc::new(Int64Array::from(vec![40, 50, 60, 70, 80])),
48184816
],
48194817
)?,
48204818
];
4819+
let key = col("key", &schema)?;
4820+
let time_bin = col("time_bin", &schema)?;
48214821
let group_by = PhysicalGroupBy::new_single(vec![
4822-
(col("key", &schema)?, "key".to_string()),
4823-
(col("time_bin", &schema)?, "time_bin".to_string()),
4822+
(Arc::clone(&key), "key".to_string()),
4823+
(Arc::clone(&time_bin), "time_bin".to_string()),
48244824
]);
48254825
let aggr_expr = Arc::new(
48264826
AggregateExprBuilder::new(sum_udaf(), vec![col("value", &schema)?])
48274827
.schema(Arc::clone(&schema))
48284828
.alias("SUM(value)")
48294829
.build()?,
48304830
);
4831-
let input: Arc<dyn ExecutionPlan> =
4832-
TestMemoryExec::try_new_exec(&[input_batches], Arc::clone(&schema), None)?;
4833-
assert_eq!(input.output_partitioning().partition_count(), 1);
4831+
let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
4832+
eq_properties.add_groupings([vec![key, time_bin]]);
4833+
let input = Arc::new(
4834+
BarrierExec::new(vec![input_batches], Arc::clone(&schema))
4835+
.without_start_barrier()
4836+
.with_batch_barrier()
4837+
.with_equivalence_properties(eq_properties)
4838+
.with_log(false),
4839+
);
4840+
assert_eq!(
4841+
input.properties().output_partitioning().partition_count(),
4842+
1
4843+
);
48344844

48354845
let aggregate = AggregateExec::try_new(
48364846
AggregateMode::Single,
48374847
group_by,
48384848
vec![aggr_expr],
48394849
vec![None],
4840-
input,
4850+
Arc::clone(&input) as Arc<dyn ExecutionPlan>,
48414851
schema,
48424852
)?;
48434853

48444854
assert_eq!(
48454855
aggregate.group_clustering_mode(),
4846-
&GroupClusteringMode::None
4856+
&GroupClusteringMode::Full
48474857
);
4848-
// This captures the behavior before #24438. When the source can declare
4849-
// `(key, time_bin)` group-contiguous, the corresponding case can use
4850-
// `EmissionType::Incremental`.
4851-
assert_eq!(aggregate.cache().emission_type, EmissionType::Final);
4858+
assert_eq!(aggregate.cache().emission_type, EmissionType::Incremental);
4859+
assert!(
4860+
aggregate
4861+
.cache()
4862+
.equivalence_properties()
4863+
.geq_class()
4864+
.is_empty()
4865+
);
4866+
assert!(aggregate.cache().output_ordering().is_none());
48524867

48534868
let task_ctx = new_migrated_hash_ctx(1024);
48544869
let stream = aggregate.execute_typed(0, &task_ctx)?;
4855-
assert!(matches!(stream, StreamType::SingleHash(_)));
4856-
let stream: SendableRecordBatchStream = stream.into();
4857-
let output = collect(stream).await?;
4870+
assert!(matches!(stream, StreamType::GroupedHash(_)));
4871+
let mut stream: SendableRecordBatchStream = stream.into();
4872+
input.wait_batch().await;
4873+
// The second batch and EOF remain blocked until the first completed
4874+
// group has been emitted.
4875+
let first =
4876+
tokio::time::timeout(std::time::Duration::from_secs(5), stream.next())
4877+
.await
4878+
.expect("completed group was not emitted before the next input batch")
4879+
.expect("stream ended before the next input batch")?;
4880+
assert_snapshot!(batches_to_string(std::slice::from_ref(&first)), @r"
4881+
+-----+----------+------------+
4882+
| key | time_bin | SUM(value) |
4883+
+-----+----------+------------+
4884+
| 1 | 20 | 30 |
4885+
+-----+----------+------------+
4886+
");
4887+
input.wait_batch().await;
4888+
let mut output = vec![first];
4889+
output.extend(collect(stream).await?);
48584890
assert_snapshot!(batches_to_sort_string(&output), @r"
48594891
+-----+----------+------------+
48604892
| key | time_bin | SUM(value) |
@@ -4869,6 +4901,158 @@ mod tests {
48694901
Ok(())
48704902
}
48714903

4904+
#[tokio::test]
4905+
async fn grouped_input_uses_clustered_partial_and_single_partitioned() -> Result<()> {
4906+
let schema = Arc::new(Schema::new(vec![
4907+
Field::new("key", DataType::Int32, false),
4908+
Field::new("value", DataType::Int64, false),
4909+
]));
4910+
let batch = |keys: Vec<i32>, values: Vec<i64>| {
4911+
RecordBatch::try_new(
4912+
Arc::clone(&schema),
4913+
vec![
4914+
Arc::new(Int32Array::from(keys)),
4915+
Arc::new(Int64Array::from(values)),
4916+
],
4917+
)
4918+
};
4919+
// Groups are contiguous within each partition but not sorted. Key 1 spans
4920+
// a batch boundary, and keys 2 and 3 occur in both partitions.
4921+
let partitions = vec![
4922+
vec![
4923+
batch(vec![2, 1], vec![1, 2])?,
4924+
batch(vec![1, 3], vec![3, 4])?,
4925+
],
4926+
vec![batch(vec![3, 3, 2], vec![5, 6, 7])?],
4927+
];
4928+
let key = col("key", &schema)?;
4929+
let input: Arc<dyn ExecutionPlan> = Arc::new(
4930+
TestMemoryExec::try_new(&partitions, Arc::clone(&schema), None)?
4931+
.try_with_grouping_information(vec![vec![Arc::clone(&key)]])?,
4932+
);
4933+
let group_by = PhysicalGroupBy::new_single(vec![(key, "key".to_string())]);
4934+
let aggr_expr = Arc::new(
4935+
AggregateExprBuilder::new(sum_udaf(), vec![col("value", &schema)?])
4936+
.schema(Arc::clone(&schema))
4937+
.alias("SUM(value)")
4938+
.build()?,
4939+
);
4940+
let task_ctx = new_migrated_hash_ctx(1024);
4941+
4942+
let single_partitioned = AggregateExec::try_new(
4943+
AggregateMode::SinglePartitioned,
4944+
group_by.clone(),
4945+
vec![Arc::clone(&aggr_expr)],
4946+
vec![None],
4947+
Arc::clone(&input),
4948+
Arc::clone(&schema),
4949+
)?;
4950+
assert_eq!(
4951+
single_partitioned.group_clustering_mode(),
4952+
&GroupClusteringMode::Full
4953+
);
4954+
assert!(matches!(
4955+
single_partitioned.execute_typed(0, &task_ctx)?,
4956+
StreamType::GroupedHash(_)
4957+
));
4958+
4959+
let partial = Arc::new(AggregateExec::try_new(
4960+
AggregateMode::Partial,
4961+
group_by.clone(),
4962+
vec![Arc::clone(&aggr_expr)],
4963+
vec![None],
4964+
input,
4965+
Arc::clone(&schema),
4966+
)?);
4967+
assert_eq!(partial.group_clustering_mode(), &GroupClusteringMode::Full);
4968+
assert!(matches!(
4969+
partial.execute_typed(0, &task_ctx)?,
4970+
StreamType::ClusteredPartialAggregate(_)
4971+
));
4972+
4973+
let final_aggregate = AggregateExec::try_new(
4974+
AggregateMode::Final,
4975+
group_by.as_final(),
4976+
vec![aggr_expr],
4977+
vec![None],
4978+
Arc::new(CoalescePartitionsExec::new(partial)),
4979+
schema,
4980+
)?;
4981+
let output = collect(final_aggregate.execute(0, task_ctx)?).await?;
4982+
assert_snapshot!(batches_to_sort_string(&output), @r"
4983+
+-----+------------+
4984+
| key | SUM(value) |
4985+
+-----+------------+
4986+
| 1 | 5 |
4987+
| 2 | 8 |
4988+
| 3 | 15 |
4989+
+-----+------------+
4990+
");
4991+
Ok(())
4992+
}
4993+
4994+
#[test]
4995+
fn grouped_date_bin_projects_to_aggregate() -> Result<()> {
4996+
let schema = Arc::new(Schema::new(vec![
4997+
Field::new("key", DataType::Int32, false),
4998+
Field::new("time", DataType::Timestamp(TimeUnit::Second, None), false),
4999+
]));
5000+
let time_bin_expr = || -> Result<Arc<dyn PhysicalExpr>> {
5001+
Ok(Arc::new(ScalarFunctionExpr::try_new(
5002+
date_bin(),
5003+
vec![
5004+
lit(ScalarValue::new_interval_dt(0, 10_000)),
5005+
col("time", &schema)?,
5006+
],
5007+
&schema,
5008+
Arc::new(ConfigOptions::default()),
5009+
)?))
5010+
};
5011+
let input = TestMemoryExec::try_new(&[vec![]], Arc::clone(&schema), None)?
5012+
.try_with_grouping_information(vec![vec![
5013+
col("key", &schema)?,
5014+
time_bin_expr()?,
5015+
]])?;
5016+
let projection = ProjectionExec::try_new(
5017+
[
5018+
ProjectionExpr::new(col("key", &schema)?, "key"),
5019+
// Build this expression independently from the source
5020+
// assertion so the test exercises semantic expression matching.
5021+
ProjectionExpr::new(time_bin_expr()?, "time_bin"),
5022+
],
5023+
Arc::new(input),
5024+
)?;
5025+
5026+
let projected_schema = projection.schema();
5027+
let key = col("key", &projected_schema)?;
5028+
let time_bin = col("time_bin", &projected_schema)?;
5029+
assert!(
5030+
projection
5031+
.properties()
5032+
.equivalence_properties()
5033+
.grouping_satisfy([Arc::clone(&key), Arc::clone(&time_bin)])?
5034+
);
5035+
let aggregate = AggregateExec::try_new(
5036+
AggregateMode::Single,
5037+
PhysicalGroupBy::new_single(vec![
5038+
(key, "key".to_string()),
5039+
(time_bin, "time_bin".to_string()),
5040+
]),
5041+
vec![],
5042+
vec![],
5043+
Arc::new(projection),
5044+
projected_schema,
5045+
)?;
5046+
5047+
assert!(aggregate.input().output_ordering().is_none());
5048+
assert_eq!(
5049+
aggregate.group_clustering_mode(),
5050+
&GroupClusteringMode::Full
5051+
);
5052+
assert_eq!(aggregate.cache().emission_type, EmissionType::Incremental);
5053+
Ok(())
5054+
}
5055+
48725056
/// Ensures for ordered input, `ClusteredPartialAggregateStream` is used.
48735057
#[tokio::test]
48745058
async fn ordered_partial_aggregate_planning() -> Result<()> {

0 commit comments

Comments
 (0)