Skip to content

Commit e7bf356

Browse files
2010YOUY01Omega359
authored andcommitted
refactor: Make AggregateExec state modeling and public updates safe (part2: topk) (apache#25696)
## 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. --> - Closes apache#25563 ## 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 the idea, this PR is the step 2 in the issue. For backgrounds for aggregate topk optimization (this PR targets), see - https://github.com/apache/datafusion/pull/25696/changes#diff-4ac7ea0d6b4fd9ff25f1fcfaeda2b767a3d15d3ad5b6c1ba05fd7a5dfb805819R931 ## 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. --> 1. Represent topk path in `AggregateExec` with enum state 2. Deprecate unsafe APIs on `AggregateExec`, and replace them with a atomic and safe one: - Deprecated: `with_new_limit_options` and `with_limit_options` - Safe and atomic alternative: `try_optimize_topk` 3. Update related optimizer passes to use the safe alternative ## 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 3. 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 (adapted the optimizer tests to use the new safe API for the same test goal) ## Are there any user-facing changes? Deprecating error-prone APIs on AggregateExec <!-- 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. -->
1 parent 24e351c commit e7bf356

7 files changed

Lines changed: 492 additions & 208 deletions

File tree

‎datafusion/core/tests/execution/coop.rs‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ use datafusion::physical_expr::aggregate::AggregateExprBuilder;
2424
use datafusion::physical_plan;
2525
use datafusion::physical_plan::ExecutionPlan;
2626
use datafusion::physical_plan::aggregates::{
27-
AggregateExec, AggregateMode, LimitOptions, PhysicalGroupBy,
27+
AggregateExec, AggregateMode, PhysicalGroupBy,
2828
};
2929
use datafusion::physical_plan::execution_plan::Boundedness;
3030
use datafusion::prelude::SessionContext;
@@ -261,7 +261,9 @@ async fn agg_grouped_topk_yields(
261261
inf.clone(),
262262
inf.schema(),
263263
)?
264-
.with_limit_options(Some(LimitOptions::new(100))),
264+
.try_optimize_topk(100, "max", SortOptions::new(true, false))
265+
.unwrap()
266+
.data,
265267
);
266268

267269
query_yields(aggr, session_ctx.task_ctx()).await

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

Lines changed: 13 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ use datafusion_physical_optimizer::PhysicalOptimizerRule;
3737
use datafusion_physical_optimizer::combine_partial_final_agg::CombinePartialFinalAggregate;
3838
use datafusion_physical_plan::ExecutionPlan;
3939
use datafusion_physical_plan::aggregates::{
40-
AggregateExec, AggregateMode, LimitOptions, PhysicalGroupBy,
40+
AggregateExec, AggregateMode, PhysicalGroupBy,
4141
};
4242
use datafusion_physical_plan::displayable;
4343
use datafusion_physical_plan::repartition::RepartitionExec;
@@ -244,6 +244,15 @@ fn aggregations_with_limit_combined() -> datafusion_common::Result<()> {
244244
let partial_group_by = PhysicalGroupBy::new_single(groups);
245245
let partial_agg =
246246
partial_aggregate_exec(parquet_exec(schema), partial_group_by, aggr_expr.clone());
247+
let partial_agg = Arc::new(
248+
partial_agg
249+
.downcast_ref::<AggregateExec>()
250+
.unwrap()
251+
.clone()
252+
.try_optimize_distinct_soft_limit(5)
253+
.unwrap()
254+
.data,
255+
);
247256

248257
let groups: Vec<(Arc<dyn PhysicalExpr>, String)> =
249258
vec![(col("c", &partial_agg.schema())?, "c".to_string())];
@@ -260,7 +269,9 @@ fn aggregations_with_limit_combined() -> datafusion_common::Result<()> {
260269
schema,
261270
)
262271
.unwrap()
263-
.with_limit_options(Some(LimitOptions::new(5))),
272+
.try_optimize_distinct_soft_limit(5)
273+
.unwrap()
274+
.data,
264275
);
265276
let plan: Arc<dyn ExecutionPlan> = final_agg;
266277
// should combine the Partial/Final AggregateExecs to a Single AggregateExec

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

Lines changed: 39 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -21,9 +21,10 @@
2121
use std::sync::Arc;
2222

2323
use datafusion_common::error::Result;
24+
use datafusion_common::internal_err;
2425
use datafusion_physical_plan::ExecutionPlan;
2526
use datafusion_physical_plan::aggregates::{
26-
AggregateExec, AggregateMode, PhysicalGroupBy,
27+
AggregateExec, AggregateKind, AggregateMode, PhysicalGroupBy,
2728
};
2829

2930
use crate::PhysicalOptimizerRule;
@@ -90,19 +91,49 @@ impl PhysicalOptimizerRule for CombinePartialFinalAggregate {
9091
} else {
9192
AggregateMode::SinglePartitioned
9293
};
93-
AggregateExec::try_new(
94+
let Ok(mut combined_agg) = AggregateExec::try_new(
9495
mode,
9596
input_agg_exec.group_expr().clone(),
9697
input_agg_exec.aggr_expr().to_vec(),
9798
input_agg_exec.filter_expr().to_vec(),
9899
Arc::clone(input_agg_exec.input()),
99100
input_agg_exec.input_schema(),
100-
)
101-
.map(|combined_agg| {
102-
combined_agg.with_limit_options(agg_exec.limit_options())
103-
})
104-
.ok()
105-
.map(Arc::new)
101+
) else {
102+
return Ok(Transformed::no(plan));
103+
};
104+
105+
// Re-apply distinct limit optimization.
106+
//
107+
// The optimizer related to aggregates are (in order):
108+
// - 1. Initial planning: always final/partial two stage
109+
// - 2. `LimitedDistinctAggregation`: push limit into `AggregateExec`,
110+
// and build `AggregateKind::DistinctLimit`
111+
// - 3. `CombinePartialFinalAggregate`: the current optimization
112+
//
113+
// Here it restores previously applied optimization in step 2
114+
let combined_aggr_kind = match (&agg_exec.kind, &input_agg_exec.kind) {
115+
(AggregateKind::General { .. }, AggregateKind::General { .. }) => {
116+
combined_agg.kind
117+
}
118+
(
119+
AggregateKind::DistinctLimit { limit, .. },
120+
AggregateKind::DistinctLimit {
121+
group_by,
122+
limit: partial_limit,
123+
},
124+
) if limit == partial_limit => AggregateKind::DistinctLimit {
125+
// The combined aggregate groups raw input, like the partial.
126+
group_by: Arc::clone(group_by),
127+
limit: *limit,
128+
},
129+
_ => {
130+
return internal_err!(
131+
"The AggregateKind should stay either (a) General (b) DistinctLimit introduced with the previous optimizer pass `LimitedDistinctAggregation`, it's impossible to have other variant"
132+
);
133+
}
134+
};
135+
combined_agg.kind = combined_aggr_kind;
136+
Some(Arc::new(combined_agg))
106137
} else {
107138
None
108139
};

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

Lines changed: 24 additions & 87 deletions
Original file line numberDiff line numberDiff line change
@@ -25,8 +25,7 @@ use datafusion_common::config::ConfigOptions;
2525
use datafusion_common::tree_node::{Transformed, TransformedResult, TreeNode};
2626
use datafusion_physical_expr::expressions::Column;
2727
use datafusion_physical_plan::ExecutionPlan;
28-
use datafusion_physical_plan::aggregates::LimitOptions;
29-
use datafusion_physical_plan::aggregates::{AggregateExec, topk_types_supported};
28+
use datafusion_physical_plan::aggregates::AggregateExec;
3029
use datafusion_physical_plan::execution_plan::CardinalityEffect;
3130
use datafusion_physical_plan::projection::ProjectionExec;
3231
use datafusion_physical_plan::sorts::sort::SortExec;
@@ -42,88 +41,30 @@ impl TopKAggregation {
4241
Self {}
4342
}
4443

45-
fn transform_agg(
46-
aggr: &AggregateExec,
47-
order_by: &str,
48-
order_desc: bool,
49-
nulls_first: bool,
50-
limit: usize,
51-
) -> Option<Arc<dyn ExecutionPlan>> {
52-
// Current only support single group key
53-
let (group_key, group_key_alias) =
54-
aggr.group_expr().expr().iter().exactly_one().ok()?;
55-
let kt = group_key.data_type(&aggr.input().schema()).ok()?;
56-
let vt = if let Some((field, _)) = aggr.get_minmax_desc() {
57-
field.data_type().clone()
58-
} else {
59-
kt.clone()
60-
};
61-
if !topk_types_supported(&kt, &vt) {
62-
return None;
63-
}
64-
if aggr.filter_expr().iter().any(|e| e.is_some()) {
65-
return None;
66-
}
67-
68-
// Check if this is ordering by an aggregate function (MIN/MAX)
69-
if let Some((field, desc)) = aggr.get_minmax_desc() {
70-
// A nullable MIN/MAX starts as NULL and becomes non-NULL when the
71-
// group sees its first value. With NULLS FIRST that transition
72-
// worsens the group's rank, so a bounded aggregation cannot safely
73-
// discard other NULL groups. Use regular aggregation for exact
74-
// results. Non-nullable inputs never take this transition and can
75-
// still use TopK.
76-
let input_nullable = aggr
77-
.aggr_expr()
78-
.iter()
79-
.exactly_one()
80-
.ok()?
81-
.expressions()
82-
.into_iter()
83-
.exactly_one()
84-
.ok()?
85-
.nullable(aggr.input_schema.as_ref())
86-
.ok()?;
87-
if nulls_first && input_nullable {
88-
return None;
89-
}
90-
// ensure the sort direction matches aggregate function
91-
if desc != order_desc {
92-
return None;
93-
}
94-
// ensure the sort is on the same field as the aggregate output
95-
if order_by != field.name() {
96-
return None;
97-
}
98-
} else if aggr.aggr_expr().is_empty() {
99-
// This is a GROUP BY without aggregates, check if ordering is on the group key itself
100-
if order_by != group_key_alias {
101-
return None;
102-
}
103-
} else {
104-
// Has aggregates but not MIN/MAX, or doesn't DISTINCT
105-
return None;
106-
}
107-
108-
// We found what we want: clone, copy the limit down, and return modified node
109-
let new_aggr = AggregateExec::with_new_limit_options(
110-
aggr,
111-
Some(LimitOptions::new_with_order(limit, order_desc)),
112-
);
113-
Some(Arc::new(new_aggr))
114-
}
115-
44+
/// Push the bound into eligible aggregates to retain fewer groups; keep the
45+
/// sort to enforce the final ordering and row count.
46+
///
47+
/// ```txt
48+
/// Before:
49+
/// Sort(fetch=K)
50+
/// Aggregate
51+
/// input
52+
///
53+
/// After:
54+
/// Sort(fetch=K)
55+
/// Aggregate(TopK(k))
56+
/// input
57+
/// ```
11658
fn transform_sort(plan: &Arc<dyn ExecutionPlan>) -> Option<Arc<dyn ExecutionPlan>> {
11759
let sort = plan.downcast_ref::<SortExec>()?;
11860

11961
let children = sort.children();
12062
let child = children.into_iter().exactly_one().ok()?;
12163
let order = sort.properties().output_ordering()?;
12264
let order = order.iter().exactly_one().ok()?;
123-
let order_desc = order.options.descending;
124-
let nulls_first = order.options.nulls_first;
65+
let sort_options = order.options;
12566
let order = order.expr.downcast_ref::<Column>()?;
126-
let mut cur_col_name = order.name().to_string();
67+
let mut sort_col_name = order.name().to_string();
12768
let limit = sort.fetch()?;
12869

12970
let mut cardinality_preserved = true;
@@ -132,25 +73,21 @@ impl TopKAggregation {
13273
return Ok(Transformed::no(plan));
13374
}
13475
if let Some(aggr) = plan.downcast_ref::<AggregateExec>() {
135-
// either we run into an Aggregate and transform it
136-
match Self::transform_agg(
137-
aggr,
138-
&cur_col_name,
139-
order_desc,
140-
nulls_first,
141-
limit,
142-
) {
76+
match aggr
77+
.clone()
78+
.try_optimize_topk(limit, &sort_col_name, sort_options)
79+
{
14380
None => cardinality_preserved = false,
144-
Some(plan) => return Ok(Transformed::yes(plan)),
81+
Some(aggr) => return Ok(Transformed::yes(Arc::new(aggr.data))),
14582
}
14683
} else if let Some(proj) = plan.downcast_ref::<ProjectionExec>() {
14784
// track renames due to successive projections
14885
for proj_expr in proj.expr() {
14986
let Some(src_col) = proj_expr.expr.downcast_ref::<Column>() else {
15087
continue;
15188
};
152-
if proj_expr.alias == cur_col_name {
153-
cur_col_name = src_col.name().to_string();
89+
if proj_expr.alias == sort_col_name {
90+
sort_col_name = src_col.name().to_string();
15491
}
15592
}
15693
} else {

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

Lines changed: 14 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -19,8 +19,6 @@
1919
2020
use crate::aggregates::group_values::{AggregateArgumentMetrics, GroupByMetrics};
2121
use crate::aggregates::topk::priority_map::PriorityMap;
22-
#[cfg(debug_assertions)]
23-
use crate::aggregates::topk_types_supported;
2422
use crate::aggregates::{
2523
AggregateExec, PhysicalGroupBy, aggregate_expressions, aggregate_metric_label,
2624
evaluate_group_by,
@@ -33,7 +31,6 @@ use arrow::compute::concat;
3331
use arrow::datatypes::SchemaRef;
3432
use arrow::util::pretty::print_batches;
3533
use datafusion_common::Result;
36-
use datafusion_common::internal_datafusion_err;
3734
use datafusion_execution::TaskContext;
3835
use datafusion_physical_expr::PhysicalExpr;
3936
use datafusion_physical_expr_common::metrics::RecordOutput;
@@ -69,6 +66,7 @@ impl GroupedTopKAggregateStream {
6966
context: &Arc<TaskContext>,
7067
partition: usize,
7168
limit: usize,
69+
descending: bool,
7270
) -> Result<Self> {
7371
let agg_schema = Arc::clone(&aggr.schema);
7472
let group_by = Arc::clone(aggr.group_by());
@@ -88,38 +86,17 @@ impl GroupedTopKAggregateStream {
8886
let (expr, _) = &aggr.group_expr().expr()[0];
8987
let kt = expr.data_type(&aggr.input().schema())?;
9088

91-
// Check if this is a MIN/MAX aggregate or a DISTINCT-like operation
92-
let (vt, desc) = if let Some((val_field, desc)) = aggr.get_minmax_desc() {
93-
// MIN/MAX case: use the aggregate output type
94-
(val_field.data_type().clone(), desc)
95-
} else {
96-
// DISTINCT case: use the group key type and get ordering from limit_order_descending
97-
// The ordering direction is set by the optimizer when it pushes down the limit
98-
let desc = aggr
99-
.limit_options()
100-
.and_then(|config| config.descending)
101-
.ok_or_else(|| {
102-
internal_datafusion_err!(
103-
"Ordering direction required for DISTINCT with limit"
104-
)
105-
})?;
106-
(kt.clone(), desc)
107-
};
108-
109-
// Type validation is performed by the optimizer and can_use_topk() check.
110-
// This debug assertion documents the contract without runtime overhead in release builds.
111-
#[cfg(debug_assertions)]
112-
{
113-
debug_assert!(
114-
topk_types_supported(&kt, &vt),
115-
"TopK type validation should have been performed by optimizer and can_use_topk(). \
116-
Found unsupported types: key={kt:?}, value={vt:?}"
117-
);
118-
}
89+
// The TopK state has already validated the single key/aggregate shape,
90+
// types, and direction. MIN/MAX use their value type; grouping-only
91+
// aggregation uses its key as the priority value too.
92+
let vt = aggr.aggr_expr().first().map_or_else(
93+
|| kt.clone(),
94+
|aggregate| aggregate.field().data_type().clone(),
95+
);
11996

12097
// Note: Null values in aggregate columns are filtered by the aggregation layer
12198
// before reaching the heap, so the heap implementations don't need explicit null handling.
122-
let priority_map = PriorityMap::new(kt, vt, limit, desc)?;
99+
let priority_map = PriorityMap::new(kt, vt, limit, descending)?;
123100

124101
Ok(GroupedTopKAggregateStream {
125102
partition,
@@ -329,11 +306,12 @@ impl Stream for GroupedTopKAggregateStream {
329306
mod tests {
330307
use super::*;
331308
use crate::ExecutionPlan;
332-
use crate::aggregates::{AggregateMode, LimitOptions};
309+
use crate::aggregates::AggregateMode;
333310
use crate::collect;
334311
use crate::metrics::MetricValue;
335312
use crate::test::TestMemoryExec;
336313
use arrow::array::{Float64Array, UInt32Array};
314+
use arrow::compute::SortOptions;
337315
use arrow::datatypes::{DataType, Field, Schema};
338316
use arrow::record_batch::RecordBatch;
339317
use datafusion_common::assert_batches_eq;
@@ -373,7 +351,9 @@ mod tests {
373351
input,
374352
schema,
375353
)?
376-
.with_limit_options(Some(LimitOptions::new(2))),
354+
.try_optimize_topk(2, "MIN(a)", SortOptions::new(false, false))
355+
.unwrap()
356+
.data,
377357
);
378358
let context = Arc::new(TaskContext::default());
379359
let result = collect(Arc::clone(&aggregate_exec) as _, context).await?;

0 commit comments

Comments
 (0)