Skip to content

Commit 9baa581

Browse files
author
Gene Bordegaray
committed
Aggregations Support Partitioning::Range (apache#23239)
<!-- 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#23191. - Related discussion: apache#23184, apache#23236. <!-- 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. --> Range partitioning can satisfy aggregate hash partitioning: equal group keys are already partitioned, even though the partitioning is not hash-based. This is the first unary-operator implementation from the range partitioning discussion before making broader public API changes around `HashPartitioned` / `KeyPartitioned`. <!-- 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. --> - Let compatible range partitioning satisfy aggregate hash distribution requirements in `EnforceDistribution` - Keep this private to aggregate planning for now to not make public API changes to `Distribution` enum variants yet until more operators are supported <!-- 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)? --> Yes. <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. --> Yes. Range-partitioned aggregate plans can now avoid hash repartitioning. <!-- If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent e2d9f84 commit 9baa581

4 files changed

Lines changed: 257 additions & 18 deletions

File tree

‎datafusion/core/tests/physical_optimizer/enforce_distribution.rs‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -933,6 +933,86 @@ fn non_inner_range_join_rehashes() -> Result<()> {
933933
Ok(())
934934
}
935935

936+
#[test]
937+
fn range_aggregate_reuses_range_partitioning() -> Result<()> {
938+
let input = parquet_exec_with_output_partitioning(range_partitioning(
939+
"a",
940+
[10, 20, 30],
941+
SortOptions::default(),
942+
)?);
943+
let aggregate =
944+
aggregate_exec_with_alias(input, vec![("a".to_string(), "a".to_string())]);
945+
946+
let plan = TestConfig::default()
947+
.with_query_execution_partitions(4)
948+
.to_plan(aggregate, &DISTRIB_DISTRIB_SORT);
949+
950+
assert_plan!(
951+
plan,
952+
@r"
953+
AggregateExec: mode=FinalPartitioned, gby=[a@0 as a], aggr=[]
954+
AggregateExec: mode=Partial, gby=[a@0 as a], aggr=[]
955+
PartitionedTestExec: output_partitioning=Range([a@0 ASC], [(10), (20), (30)], 4)
956+
"
957+
);
958+
959+
Ok(())
960+
}
961+
962+
#[test]
963+
fn range_grouping_set_aggregate_rehashes_with_grouping_id() -> Result<()> {
964+
let input = parquet_exec_with_output_partitioning(range_partitioning(
965+
"a",
966+
[10, 20],
967+
SortOptions::default(),
968+
)?);
969+
let input_schema = input.schema();
970+
let group_by = PhysicalGroupBy::new(
971+
vec![
972+
(col("a", &input_schema)?, "a".to_string()),
973+
(col("b", &input_schema)?, "b".to_string()),
974+
],
975+
vec![
976+
(lit(ScalarValue::Int64(None)), "a".to_string()),
977+
(lit(ScalarValue::Int64(None)), "b".to_string()),
978+
],
979+
vec![vec![false, true], vec![false, false]],
980+
true,
981+
);
982+
let partial = Arc::new(AggregateExec::try_new(
983+
AggregateMode::Partial,
984+
group_by.clone(),
985+
vec![],
986+
vec![],
987+
input,
988+
Arc::clone(&input_schema),
989+
)?);
990+
let aggregate = Arc::new(AggregateExec::try_new(
991+
AggregateMode::FinalPartitioned,
992+
group_by.as_final(),
993+
vec![],
994+
vec![],
995+
Arc::clone(&partial) as _,
996+
partial.schema(),
997+
)?);
998+
999+
let plan = TestConfig::default()
1000+
.with_query_execution_partitions(3)
1001+
.to_plan(aggregate, &DISTRIB_DISTRIB_SORT);
1002+
1003+
assert_plan!(
1004+
plan,
1005+
@r"
1006+
AggregateExec: mode=FinalPartitioned, gby=[a@0 as a, b@1 as b, __grouping_id@2 as __grouping_id], aggr=[]
1007+
RepartitionExec: partitioning=Hash([a@0, b@1, __grouping_id@2], 3), input_partitions=3
1008+
AggregateExec: mode=Partial, gby=[(a@0 as a, NULL as b), (a@0 as a, b@1 as b)], aggr=[]
1009+
PartitionedTestExec: output_partitioning=Range([a@0 ASC], [(10), (20)], 3)
1010+
"
1011+
);
1012+
1013+
Ok(())
1014+
}
1015+
9361016
#[test]
9371017
fn multi_hash_joins() -> Result<()> {
9381018
let left = parquet_exec();

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

Lines changed: 78 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,9 @@ use std::sync::Arc;
2828
use crate::optimizer::PhysicalOptimizerRule;
2929
use crate::output_requirements::OutputRequirementExec;
3030
use crate::utils::{
31-
add_sort_above_with_check, is_coalesce_partitions, is_repartition,
32-
is_sort_preserving_merge,
31+
add_sort_above_with_check, aggregate_can_reuse_range_partitioning,
32+
is_coalesce_partitions, is_repartition, is_sort_preserving_merge,
33+
range_partitioning_satisfies_key_partitioning,
3334
};
3435

3536
use arrow::compute::SortOptions;
@@ -926,6 +927,49 @@ fn add_hash_on_top(
926927
Ok(input)
927928
}
928929

930+
// TODO: remove this private helper once Range generally satisfies
931+
// KeyPartitioned requirements through Partitioning::satisfaction.
932+
// See <https://github.com/apache/datafusion/issues/23266>.
933+
//
934+
// Partial aggregates do not require key partitioning, but they preserve their
935+
// input partitioning for the final aggregate. Until Range satisfies
936+
// KeyPartitioned generally, this check keeps preserve_file_partitions from
937+
// inserting RoundRobin between a reusable Range input and the partial aggregate.
938+
fn partial_aggregate_preserves_reusable_partitioning(
939+
plan: &Arc<dyn ExecutionPlan>,
940+
child: &Arc<dyn ExecutionPlan>,
941+
allow_subset_satisfy_partitioning: bool,
942+
) -> bool {
943+
let Some(aggregate) = plan.downcast_ref::<AggregateExec>() else {
944+
return false;
945+
};
946+
if aggregate.mode() != &AggregateMode::Partial
947+
|| aggregate.group_expr().is_empty()
948+
|| aggregate.group_expr().has_grouping_set()
949+
{
950+
return false;
951+
}
952+
953+
let group_exprs = aggregate.group_expr().input_exprs();
954+
let output_partitioning = child.output_partitioning();
955+
let eq_properties = child.equivalence_properties();
956+
let key_distribution = Distribution::KeyPartitioned(group_exprs.clone());
957+
958+
output_partitioning
959+
.satisfaction(
960+
&key_distribution,
961+
eq_properties,
962+
allow_subset_satisfy_partitioning,
963+
)
964+
.is_satisfied()
965+
|| range_partitioning_satisfies_key_partitioning(
966+
output_partitioning,
967+
&group_exprs,
968+
eq_properties,
969+
allow_subset_satisfy_partitioning,
970+
)
971+
}
972+
929973
/// Adds a [`SortPreservingMergeExec`] or a [`CoalescePartitionsExec`] operator
930974
/// on top of the given plan node to satisfy a single partition requirement
931975
/// while preserving ordering constraints.
@@ -1398,33 +1442,44 @@ pub fn ensure_distribution(
13981442
force_hash_to_target,
13991443
},
14001444
)| {
1401-
let increases_partition_count =
1402-
child.plan.output_partitioning().partition_count() < target_partitions;
1403-
1404-
let add_roundrobin = enable_round_robin
1405-
// Operator benefits from partitioning (e.g. filter):
1406-
&& roundrobin_beneficial
1407-
&& roundrobin_beneficial_stats
1408-
// Unless partitioning increases the partition count, it is not beneficial:
1409-
&& increases_partition_count;
1410-
14111445
// Allow subset satisfaction when:
14121446
// 1. Current partition count >= threshold
14131447
// 2. Not a partitioned join since must use exact hash matching for joins
14141448
// 3. Not a grouping set aggregate (requires exact hash including __grouping_id)
14151449
let current_partitions = child.plan.output_partitioning().partition_count();
1450+
let preserve_file_partition_threshold_met =
1451+
config.optimizer.preserve_file_partitions > 0
1452+
&& current_partitions >= config.optimizer.preserve_file_partitions;
14161453

14171454
let allow_subset_satisfy_partitioning = (current_partitions
14181455
>= subset_satisfaction_threshold
14191456
// `preserve_file_partitions` exposes existing file-group
14201457
// partitioning to the optimizer. Respect it when the only
14211458
// reason to repartition would be to increase partition count
14221459
// beyond the preserved file-group count.
1423-
|| (config.optimizer.preserve_file_partitions > 0
1460+
|| (preserve_file_partition_threshold_met
14241461
&& current_partitions < target_partitions))
14251462
&& !is_partitioned_join
14261463
&& !requirement_includes_grouping_id(&requirement);
14271464

1465+
let increases_partition_count = current_partitions < target_partitions;
1466+
1467+
let preserve_partial_aggregate_partitioning =
1468+
preserve_file_partition_threshold_met
1469+
&& partial_aggregate_preserves_reusable_partitioning(
1470+
&plan,
1471+
&child.plan,
1472+
allow_subset_satisfy_partitioning,
1473+
);
1474+
1475+
let add_roundrobin = enable_round_robin
1476+
// Operator benefits from partitioning (e.g. filter):
1477+
&& roundrobin_beneficial
1478+
&& roundrobin_beneficial_stats
1479+
// Unless partitioning increases the partition count, it is not beneficial:
1480+
&& increases_partition_count
1481+
&& !preserve_partial_aggregate_partitioning;
1482+
14281483
// When `repartition_file_scans` is set, attempt to increase
14291484
// parallelism at the source.
14301485
//
@@ -1446,9 +1501,18 @@ pub fn ensure_distribution(
14461501
}
14471502
Distribution::HashPartitioned(exprs)
14481503
| Distribution::KeyPartitioned(exprs) => {
1504+
let range_satisfied_for_aggregate =
1505+
aggregate_can_reuse_range_partitioning(&plan)
1506+
&& range_partitioning_satisfies_key_partitioning(
1507+
child.plan.output_partitioning(),
1508+
exprs,
1509+
child.plan.equivalence_properties(),
1510+
allow_subset_satisfy_partitioning,
1511+
);
1512+
14491513
// See https://github.com/apache/datafusion/issues/18341#issuecomment-3503238325 for background
14501514
// When inserting hash is necessary to satisfy hash requirement, insert hash repartition.
1451-
if hash_necessary {
1515+
if hash_necessary && !range_satisfied_for_aggregate {
14521516
child = add_hash_on_top(
14531517
child,
14541518
exprs.to_vec(),

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

Lines changed: 22 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@
2424
use std::sync::Arc;
2525

2626
use datafusion_common::Result;
27+
use datafusion_physical_expr::Distribution;
2728
use datafusion_physical_plan::ExecutionPlan;
2829

2930
use datafusion_common::config::{ConfigOptions, OptimizerOptions};
@@ -37,6 +38,9 @@ use datafusion_physical_plan::joins::{
3738
use datafusion_physical_plan::{ExecutionPlanProperties, get_plan_string};
3839

3940
use crate::PhysicalOptimizerRule;
41+
use crate::utils::{
42+
aggregate_can_reuse_range_partitioning, range_partitioning_satisfies_key_partitioning,
43+
};
4044
use datafusion_physical_expr_common::sort_expr::format_physical_sort_requirement_list;
4145
use itertools::izip;
4246

@@ -164,11 +168,26 @@ pub fn check_plan_sanity(
164168
}
165169
}
166170

167-
if !child
171+
let child_satisfies_distribution = child
168172
.output_partitioning()
169173
.satisfaction(&dist_req, child_eq_props, true)
170-
.is_satisfied()
171-
{
174+
.is_satisfied();
175+
let range_satisfies_aggregate_distribution =
176+
aggregate_can_reuse_range_partitioning(plan)
177+
&& match &dist_req {
178+
Distribution::HashPartitioned(exprs)
179+
| Distribution::KeyPartitioned(exprs) => {
180+
range_partitioning_satisfies_key_partitioning(
181+
child.output_partitioning(),
182+
exprs,
183+
child_eq_props,
184+
true,
185+
)
186+
}
187+
_ => false,
188+
};
189+
190+
if !(child_satisfies_distribution || range_satisfies_aggregate_distribution) {
172191
let plan_str = get_plan_string(plan);
173192
return plan_err!(
174193
"Plan: {:?} does not satisfy distribution requirements: {}. Child-{} output partitioning: {}",

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

Lines changed: 77 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,11 @@
1818
use std::sync::Arc;
1919

2020
use datafusion_common::Result;
21-
use datafusion_physical_expr::{LexOrdering, LexRequirement};
21+
use datafusion_physical_expr::{
22+
EquivalenceProperties, LexOrdering, LexRequirement, Partitioning, PhysicalExpr,
23+
physical_exprs_equal,
24+
};
25+
use datafusion_physical_plan::aggregates::{AggregateExec, AggregateMode};
2226
use datafusion_physical_plan::coalesce_partitions::CoalescePartitionsExec;
2327
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
2428
use datafusion_physical_plan::repartition::RepartitionExec;
@@ -108,6 +112,78 @@ pub fn is_repartition(plan: &Arc<dyn ExecutionPlan>) -> bool {
108112
plan.is::<RepartitionExec>()
109113
}
110114

115+
/// TODO: remove once Range generally satisfies KeyPartitioned requirements
116+
/// through Partitioning::satisfaction.
117+
/// See <https://github.com/apache/datafusion/issues/23266>.
118+
///
119+
/// Checks whether range partitioning satisfies a key partitioning requirement.
120+
/// This is intentionally separate from general partitioning satisfaction while
121+
/// range reuse is rolled out operator by operator.
122+
pub(crate) fn range_partitioning_satisfies_key_partitioning(
123+
partitioning: &Partitioning,
124+
required_exprs: &[Arc<dyn PhysicalExpr>],
125+
eq_properties: &EquivalenceProperties,
126+
allow_subset: bool,
127+
) -> bool {
128+
match partitioning {
129+
Partitioning::Range(range) => {
130+
let partition_exprs = range
131+
.ordering()
132+
.iter()
133+
.map(|sort_expr| Arc::clone(&sort_expr.expr))
134+
.collect::<Vec<_>>();
135+
136+
if partition_exprs.is_empty() || required_exprs.is_empty() {
137+
return false;
138+
}
139+
140+
let eq_group = eq_properties.eq_group();
141+
let normalized_partition_exprs = partition_exprs
142+
.iter()
143+
.map(|expr| eq_group.normalize_expr(Arc::clone(expr)))
144+
.collect::<Vec<_>>();
145+
let normalized_required_exprs = required_exprs
146+
.iter()
147+
.map(|expr| eq_group.normalize_expr(Arc::clone(expr)))
148+
.collect::<Vec<_>>();
149+
150+
if physical_exprs_equal(
151+
&normalized_required_exprs,
152+
&normalized_partition_exprs,
153+
) {
154+
return true;
155+
}
156+
157+
allow_subset
158+
&& normalized_partition_exprs.len() < normalized_required_exprs.len()
159+
&& normalized_partition_exprs.iter().all(|partition_expr| {
160+
normalized_required_exprs
161+
.iter()
162+
.any(|required_expr| partition_expr.eq(required_expr))
163+
})
164+
}
165+
_ => false,
166+
}
167+
}
168+
169+
/// TODO: remove once Range generally satisfies KeyPartitioned requirements
170+
/// through Partitioning::satisfaction.
171+
/// See <https://github.com/apache/datafusion/issues/23266>.
172+
///
173+
/// Checks whether an aggregate can reuse range partitioning to satisfy its key
174+
/// partitioning requirement.
175+
pub(crate) fn aggregate_can_reuse_range_partitioning(
176+
plan: &Arc<dyn ExecutionPlan>,
177+
) -> bool {
178+
plan.downcast_ref::<AggregateExec>()
179+
.is_some_and(|aggregate| {
180+
matches!(
181+
aggregate.mode(),
182+
AggregateMode::FinalPartitioned | AggregateMode::SinglePartitioned
183+
) && !aggregate.group_expr().has_grouping_set()
184+
})
185+
}
186+
111187
/// Checks whether the given operator is a limit;
112188
/// i.e. either a [`LocalLimitExec`] or a [`GlobalLimitExec`].
113189
pub fn is_limit(plan: &Arc<dyn ExecutionPlan>) -> bool {

0 commit comments

Comments
 (0)