Skip to content

Commit c4f93bf

Browse files
2010YOUY01alamb
andauthored
refactor: Implement optimizer hook for combining partial/final aggregate in AggregateExec (apache#25962)
## 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 #123` indicates that this PR will close issue #123. --> - Closes apache#25928 ## 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 issue for backgrounds. It implements a `AggregateExec::try_combine_partial_final()` helper, to replace the full logic in `CombineParitalFinalAggregate` optimizer rule (validation + transformation) The benefit of this pattern is - Unify the inner logic in one place for maintainability. (The current implementation already did a great job unifying all logic inside the optimizer implementation, however it's common for other rules to implement partial logic in optimizer, and partial logic in `ExecutionPlan`, which introduces inconsistency. Moving all of them to a atomic optimizer hook in `ExecutionPlan` seems like a good pattern to avoid such issues) - Avoid exposing public fields in `AggregateExec` for optimizer usage, they're in different crate. ## 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. --> ## What is the testing strategy for this PR? <!-- 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 Briefly describe how this PR is tested, and point to the specific tests you added. For example: 'This new feature is covered by the `sqllogictest` cases added in `foo.slt`'. If this PR does not add tests, explain why. For example, if the change is already covered by existing tests, please mention it. You should also check the `codecov` bot reply on this PR to confirm the changed code is exercised. --> Existing tests ## 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 --------- Co-authored-by: Andrew Lamb <[email protected]>
1 parent 92f170c commit c4f93bf

2 files changed

Lines changed: 172 additions & 149 deletions

File tree

‎datafusion/physical-optimizer/src/combine_partial_final_agg.rs‎

Lines changed: 44 additions & 134 deletions
Original file line numberDiff line numberDiff line change
@@ -22,21 +22,55 @@ use std::sync::Arc;
2222

2323
use datafusion_common::error::Result;
2424
use datafusion_physical_plan::ExecutionPlan;
25-
use datafusion_physical_plan::aggregates::{
26-
AggregateExec, AggregateKind, AggregateMode, PhysicalGroupBy,
27-
};
25+
use datafusion_physical_plan::aggregates::AggregateExec;
2826

2927
use crate::PhysicalOptimizerRule;
3028
use datafusion_common::config::ConfigOptions;
31-
use datafusion_common::tree_node::{Transformed, TransformedResult, TreeNode};
32-
use datafusion_physical_expr::aggregate::AggregateFunctionExpr;
33-
use datafusion_physical_expr::{PhysicalExpr, physical_exprs_equal};
29+
use datafusion_common::tree_node::{TransformedResult, TreeNode};
3430

35-
/// CombinePartialFinalAggregate optimizer rule combines the adjacent Partial and Final AggregateExecs
36-
/// into a Single AggregateExec if their grouping exprs and aggregate exprs equal.
31+
/// Combines adjacent partial and final `AggregateExec`s into a single aggregate
32+
/// when their grouping and aggregate expressions match.
33+
///
34+
/// ```txt
35+
/// Before:
36+
/// AggregateExec(mode=Final) <-- current plan
37+
/// AggregateExec(mode=Partial)
38+
/// DataSourceExec
39+
///
40+
/// After:
41+
/// AggregateExec(mode=Single) <-- current plan
42+
/// DataSourceExec
43+
/// ```
3744
///
3845
/// This rule should be applied after the `EnsureRequirements` rule (which
3946
/// handles both distribution and sorting enforcement).
47+
///
48+
/// # Background
49+
///
50+
/// The relevant optimization steps, in order, are:
51+
///
52+
/// 1. Initial physical planning: creates a partial/final pair so aggregation can
53+
/// run in parallel. For grouped, partitioned aggregation:
54+
///
55+
/// ```txt
56+
/// AggregateExec(mode=FinalPartitioned)
57+
/// AggregateExec(mode=Partial)
58+
/// DataSourceExec
59+
/// ```
60+
///
61+
/// 2. `EnsureRequirements` rule: inserts a `RepartitionExec` between the stages when
62+
/// needed to satisfy the final aggregate's distribution requirements:
63+
///
64+
/// ```txt
65+
/// AggregateExec(mode=FinalPartitioned)
66+
/// RepartitionExec <-- inserted here
67+
/// AggregateExec(mode=Partial)
68+
/// DataSourceExec
69+
/// ```
70+
///
71+
/// 3. This rule: If the input already satisfies these requirements, e.g. because it
72+
/// is partitioned by the grouping keys, no repartition is needed. This rule
73+
/// then combines the adjacent, compatible aggregate stages into one.
4074
#[derive(Default, Debug)]
4175
pub struct CombinePartialFinalAggregate {}
4276

@@ -53,94 +87,8 @@ impl PhysicalOptimizerRule for CombinePartialFinalAggregate {
5387
plan: Arc<dyn ExecutionPlan>,
5488
_config: &ConfigOptions,
5589
) -> Result<Arc<dyn ExecutionPlan>> {
56-
plan.transform_down(|plan| {
57-
// Check if the plan is AggregateExec
58-
let Some(agg_exec) = plan.downcast_ref::<AggregateExec>() else {
59-
return Ok(Transformed::no(plan));
60-
};
61-
62-
if !matches!(
63-
agg_exec.mode(),
64-
AggregateMode::Final | AggregateMode::FinalPartitioned
65-
) {
66-
return Ok(Transformed::no(plan));
67-
}
68-
69-
// Check if the input is AggregateExec
70-
let Some(input_agg_exec) = agg_exec.input().downcast_ref::<AggregateExec>()
71-
else {
72-
return Ok(Transformed::no(plan));
73-
};
74-
75-
let transformed = if *input_agg_exec.mode() == AggregateMode::Partial
76-
&& can_combine(
77-
(
78-
agg_exec.group_expr(),
79-
agg_exec.aggr_expr(),
80-
agg_exec.filter_expr(),
81-
),
82-
(
83-
input_agg_exec.group_expr(),
84-
input_agg_exec.aggr_expr(),
85-
input_agg_exec.filter_expr(),
86-
),
87-
) {
88-
let mode = if agg_exec.mode() == &AggregateMode::Final {
89-
AggregateMode::Single
90-
} else {
91-
AggregateMode::SinglePartitioned
92-
};
93-
let Ok(mut combined_agg) = AggregateExec::try_new(
94-
mode,
95-
input_agg_exec.group_expr().clone(),
96-
input_agg_exec.aggr_expr().to_vec(),
97-
input_agg_exec.filter_expr().to_vec(),
98-
Arc::clone(input_agg_exec.input()),
99-
input_agg_exec.input_schema(),
100-
) else {
101-
return Ok(Transformed::no(plan));
102-
};
103-
104-
// Re-apply distinct limit optimization.
105-
//
106-
// The optimizer related to aggregates are (in order):
107-
// - 1. Initial planning: always final/partial two stage
108-
// - 2. `LimitedDistinctAggregation`: push limit into `AggregateExec`,
109-
// and build `AggregateKind::DistinctLimit`
110-
// - 3. `CombinePartialFinalAggregate`: the current optimization
111-
//
112-
// Here it restores previously applied optimization in step 2
113-
let combined_aggr_kind = match (&agg_exec.kind, &input_agg_exec.kind) {
114-
(AggregateKind::General { .. }, AggregateKind::General { .. }) => {
115-
combined_agg.kind
116-
}
117-
(
118-
AggregateKind::DistinctLimit { limit, .. },
119-
AggregateKind::DistinctLimit {
120-
group_by,
121-
limit: partial_limit,
122-
},
123-
) if limit == partial_limit => AggregateKind::DistinctLimit {
124-
// The combined aggregate groups raw input, like the partial.
125-
group_by: Arc::clone(group_by),
126-
limit: *limit,
127-
},
128-
// Step 2 may limit only the final aggregate, e.g. when its
129-
// grouping differs from the partial's. Keep both stages.
130-
_ => return Ok(Transformed::no(plan)),
131-
};
132-
combined_agg.kind = combined_aggr_kind;
133-
Some(Arc::new(combined_agg))
134-
} else {
135-
None
136-
};
137-
Ok(if let Some(transformed) = transformed {
138-
Transformed::yes(transformed)
139-
} else {
140-
Transformed::no(plan)
141-
})
142-
})
143-
.data()
90+
plan.transform_down(AggregateExec::try_combine_partial_final)
91+
.data()
14492
}
14593

14694
fn name(&self) -> &str {
@@ -152,42 +100,4 @@ impl PhysicalOptimizerRule for CombinePartialFinalAggregate {
152100
}
153101
}
154102

155-
type GroupExprsRef<'a> = (
156-
&'a PhysicalGroupBy,
157-
&'a [Arc<AggregateFunctionExpr>],
158-
&'a [Option<Arc<dyn PhysicalExpr>>],
159-
);
160-
161-
fn can_combine(final_agg: GroupExprsRef, partial_agg: GroupExprsRef) -> bool {
162-
let (final_group_by, final_aggr_expr, final_filter_expr) = final_agg;
163-
let (input_group_by, input_aggr_expr, input_filter_expr) = partial_agg;
164-
165-
// Compare output expressions of the partial, and input expressions of the final operator.
166-
physical_exprs_equal(
167-
&input_group_by.output_exprs(),
168-
&final_group_by.input_exprs(),
169-
) && input_group_by.groups() == final_group_by.groups()
170-
&& input_group_by.null_expr().len() == final_group_by.null_expr().len()
171-
&& input_group_by
172-
.null_expr()
173-
.iter()
174-
.zip(final_group_by.null_expr().iter())
175-
.all(|((lhs_expr, lhs_str), (rhs_expr, rhs_str))| {
176-
lhs_expr.eq(rhs_expr) && lhs_str == rhs_str
177-
})
178-
&& final_aggr_expr.len() == input_aggr_expr.len()
179-
&& final_aggr_expr
180-
.iter()
181-
.zip(input_aggr_expr.iter())
182-
.all(|(final_expr, partial_expr)| final_expr.eq(partial_expr))
183-
&& final_filter_expr.len() == input_filter_expr.len()
184-
&& final_filter_expr.iter().zip(input_filter_expr.iter()).all(
185-
|(final_expr, partial_expr)| match (final_expr, partial_expr) {
186-
(Some(l), Some(r)) => l.eq(r),
187-
(None, None) => true,
188-
_ => false,
189-
},
190-
)
191-
}
192-
193103
// See tests in datafusion/core/tests/physical_optimizer

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

Lines changed: 128 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -197,7 +197,7 @@ use datafusion_physical_expr::aggregate::AggregateFunctionExpr;
197197
use datafusion_physical_expr::equivalence::ProjectionMapping;
198198
use datafusion_physical_expr::expressions::{Column, DynamicFilterPhysicalExpr, lit};
199199
use datafusion_physical_expr::{
200-
ConstExpr, EquivalenceProperties, physical_exprs_contains,
200+
ConstExpr, EquivalenceProperties, physical_exprs_contains, physical_exprs_equal,
201201
};
202202
use datafusion_physical_expr_common::physical_expr::{PhysicalExpr, fmt_sql};
203203
use datafusion_physical_expr_common::sort_expr::{
@@ -850,13 +850,8 @@ impl LimitOptions {
850850
}
851851

852852
/// Mutually exclusive aggregation implementations and their configuration.
853-
///
854-
/// # Public Only for Internal Use:
855-
/// `datafusion-physical-optimizer` inspects and combines aggregate kinds.
856-
/// This enum is not part of the supported public API.
857-
#[doc(hidden)]
858853
#[derive(Debug, Clone)]
859-
pub enum AggregateKind {
854+
enum AggregateKind {
860855
/// Ordinary aggregation, with no limit on the groups retained.
861856
General {
862857
group_by: Arc<PhysicalGroupBy>,
@@ -891,13 +886,7 @@ pub struct AggregateExec {
891886
/// Aggregation mode (full, partial)
892887
mode: AggregateMode,
893888
/// Aggregation implementation and its configuration.
894-
///
895-
/// # Public Only for Internal Use:
896-
/// `datafusion-physical-optimizer` updates this when combining aggregates.
897-
/// Changes must preserve the expressions, schema, and plan properties.
898-
/// This field is not part of the supported public API.
899-
#[doc(hidden)]
900-
pub kind: AggregateKind,
889+
kind: AggregateKind,
901890
/// Input plan, could be a partial aggregate or the input to the aggregate
902891
pub input: Arc<dyn ExecutionPlan>,
903892
/// Schema after the aggregate is applied. Contains the group by columns followed by the
@@ -1172,6 +1161,130 @@ impl AggregateExec {
11721161
Some(Transformed::yes(self))
11731162
}
11741163

1164+
/// Combines adjacent partial and final aggregates in the given plan if they are
1165+
/// compatible. See [`CombinePartialFinalAggregate`] for the invariants required
1166+
/// by this transformation.
1167+
///
1168+
/// If input plan is not aggregate, this function will short-circuit with
1169+
/// `Transformed::No`.
1170+
///
1171+
/// ```txt
1172+
/// Before Plan:
1173+
/// AggregateExec(mode=Final) <-- current plan
1174+
/// AggregateExec(mode=Partial)
1175+
/// DataSourceExec
1176+
///
1177+
/// After Plan:
1178+
/// AggregateExec(mode=Single) <-- current plan
1179+
/// DataSourceExec
1180+
/// ```
1181+
///
1182+
/// # Public Only for Internal Use:
1183+
///
1184+
/// This is not a public API and is for internal use only in physical optimizer;
1185+
/// see [API policy] for details.
1186+
///
1187+
/// [`CombinePartialFinalAggregate`]: https://docs.rs/datafusion/latest/datafusion/physical_optimizer/combine_partial_final_agg/struct.CombinePartialFinalAggregate.html
1188+
/// [API policy]: https://datafusion.apache.org/contributor-guide/api-health.html#internal-public-apis
1189+
#[doc(hidden)]
1190+
pub fn try_combine_partial_final(
1191+
plan: Arc<dyn ExecutionPlan>,
1192+
) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
1193+
// Step 1: Ensure the below plan shape
1194+
//
1195+
// AggregateExec(mode=final) <-- current plan
1196+
// AggregateExec(mode=partial)
1197+
1198+
let Some(final_agg) = plan.downcast_ref::<Self>() else {
1199+
return Ok(Transformed::no(plan));
1200+
};
1201+
let mode = match final_agg.mode {
1202+
AggregateMode::Final => AggregateMode::Single,
1203+
AggregateMode::FinalPartitioned => AggregateMode::SinglePartitioned,
1204+
_ => return Ok(Transformed::no(plan)),
1205+
};
1206+
let Some(partial) = final_agg.input.downcast_ref::<Self>() else {
1207+
return Ok(Transformed::no(plan));
1208+
};
1209+
if partial.mode != AggregateMode::Partial {
1210+
return Ok(Transformed::no(plan));
1211+
}
1212+
1213+
// Step 2: Check compatibility between partial and final `AggregateExec`
1214+
1215+
let final_group_by = final_agg.group_expr();
1216+
let input_group_by = partial.group_expr();
1217+
let final_aggr_expr = final_agg.aggr_expr();
1218+
let input_aggr_expr = partial.aggr_expr();
1219+
let final_filter_expr = final_agg.filter_expr();
1220+
let input_filter_expr = partial.filter_expr();
1221+
1222+
// Compare the partial's output expressions with the final's input expressions.
1223+
let can_combine = physical_exprs_equal(
1224+
&input_group_by.output_exprs(),
1225+
&final_group_by.input_exprs(),
1226+
) && input_group_by.groups() == final_group_by.groups()
1227+
&& input_group_by.null_expr().len() == final_group_by.null_expr().len()
1228+
&& input_group_by
1229+
.null_expr()
1230+
.iter()
1231+
.zip(final_group_by.null_expr().iter())
1232+
.all(|((lhs_expr, lhs_str), (rhs_expr, rhs_str))| {
1233+
lhs_expr.eq(rhs_expr) && lhs_str == rhs_str
1234+
})
1235+
&& final_aggr_expr.len() == input_aggr_expr.len()
1236+
&& final_aggr_expr
1237+
.iter()
1238+
.zip(input_aggr_expr.iter())
1239+
.all(|(final_expr, partial_expr)| final_expr.eq(partial_expr))
1240+
&& final_filter_expr.len() == input_filter_expr.len()
1241+
&& final_filter_expr.iter().zip(input_filter_expr.iter()).all(
1242+
|(final_expr, partial_expr)| match (final_expr, partial_expr) {
1243+
(Some(l), Some(r)) => l.eq(r),
1244+
(None, None) => true,
1245+
_ => false,
1246+
},
1247+
);
1248+
if !can_combine {
1249+
return Ok(Transformed::no(plan));
1250+
}
1251+
1252+
let Ok(mut combined) = Self::try_new(
1253+
mode,
1254+
input_group_by.clone(),
1255+
input_aggr_expr.to_vec(),
1256+
input_filter_expr.to_vec(),
1257+
Arc::clone(partial.input()),
1258+
partial.input_schema(),
1259+
) else {
1260+
return Ok(Transformed::no(plan));
1261+
};
1262+
1263+
// LimitedDistinctAggregation runs before this optimization. Preserve its
1264+
// limit while using the partial's grouping expressions over raw input.
1265+
//
1266+
// The following logic recognizes all possible patterns produced by `LimitedDistinctAggregation`
1267+
// See its comment for details.
1268+
combined.kind = match (&final_agg.kind, &partial.kind) {
1269+
(AggregateKind::General { .. }, AggregateKind::General { .. }) => {
1270+
combined.kind
1271+
}
1272+
(
1273+
AggregateKind::DistinctLimit { limit, .. },
1274+
AggregateKind::DistinctLimit {
1275+
group_by,
1276+
limit: partial_limit,
1277+
},
1278+
) if limit == partial_limit => AggregateKind::DistinctLimit {
1279+
group_by: Arc::clone(group_by),
1280+
limit: *limit,
1281+
},
1282+
// Not possible in the default optimizer pipeline
1283+
_ => return Ok(Transformed::no(plan)),
1284+
};
1285+
Ok(Transformed::yes(Arc::new(combined)))
1286+
}
1287+
11751288
/// Clone with replacement aggregate expressions.
11761289
///
11771290
/// The caller must preserve the schema, filters, and ordering requirements.
@@ -1689,7 +1802,7 @@ impl AggregateExec {
16891802
.downcast_ref::<AggregateExec>()
16901803
.is_some_and(|partial| {
16911804
partial.mode == AggregateMode::Partial
1692-
&& datafusion_physical_expr::physical_exprs_equal(
1805+
&& physical_exprs_equal(
16931806
&partial.output_group_expr(),
16941807
&self.group_by().input_exprs(),
16951808
)

0 commit comments

Comments
 (0)