Skip to content

Commit 1305241

Browse files
u70b3kosiew
authored andcommitted
fix: TopK aggregation drops groups whose MIN/MAX value is NULL (apache#23684)
## Which issue does this PR close? - Closes apache#23440 - Closes apache#22190 ## Rationale for this change When `TopKAggregation` pushes a `LIMIT` into a MIN/MAX aggregate, a group whose aggregate inputs are all NULL can disappear instead of being returned with a NULL aggregate value. The stream previously skipped NULL aggregate inputs without registering the group. This is correct for an individual MIN/MAX input, but not for a group whose inputs are all NULL. There is also an important correctness boundary: nullable MIN/MAX with `NULLS FIRST` is not monotonic for a bounded aggregation. A group can start at NULL, later become non-NULL, and thereby move to a worse rank. Keeping only `limit` NULL candidates can therefore discard a group that belongs in the final result. ## What changes are included? - Track up to `limit` all-NULL candidates alongside valued TopK groups and emit them for the parent sort to rank and truncate. - Correctly convert a tracked NULL group when its first value arrives, or unregister it when that value cannot enter the valued TopK. - Skip TopK pushdown for nullable MIN/MAX with `NULLS FIRST`; regular aggregation is used for exact results. TopK remains enabled for `NULLS LAST`, non-nullable MIN/MAX inputs, and GROUP BY-only/DISTINCT queries. - Replace the single reusable hash-table slot with a free-slot stack. A NULL-to-value conversion can free both the NULL registration and an evicted valued group, so retaining only one slot caused unbounded backing-store growth under repeated conversions. - Select NULL-aware insertion once per batch, keeping NULL bookkeeping off the common no-NULL per-row hot path. - Add regression coverage for all-NULL groups, mixed NULL/value batches, bounded NULL candidate backfill, evicted groups, hash-table slot reuse, and optimizer plan selection. ## Are these changes tested? Yes. The following passed on the final commit: - `cargo fmt --all -- --check` - `cargo clippy --all-targets --all-features -- -D warnings` - TopK physical-plan unit tests (33 tests) - `aggregates_topk.slt` and affected `group_by.slt` tests - The repository's extended workspace command with `avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption`, including all 495 sqllogic files and extended/fuzz suites ## Performance The `topk_aggregate` 10-million-row time-series benchmark exposed an initial ~5.5% regression from checking NULL state on every row. Moving NULL handling to a batch-selected slow path removed the measurable regression. Final 30-sample 95% intervals on the same machine and settings: - `main`: 25.630–26.436 ms - this PR: 25.151–27.061 ms ## Are there any user-facing changes? Queries that previously dropped all-NULL groups under `ORDER BY <min/max> ... LIMIT` now return correct SQL results. Nullable MIN/MAX queries using `NULLS FIRST` may use regular aggregation rather than the bounded TopK optimization to guarantee correctness. There are no API or configuration changes.
1 parent ce862b4 commit 1305241

6 files changed

Lines changed: 837 additions & 63 deletions

File tree

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

Lines changed: 29 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@ impl TopKAggregation {
4646
aggr: &AggregateExec,
4747
order_by: &str,
4848
order_desc: bool,
49+
nulls_first: bool,
4950
limit: usize,
5051
) -> Option<Arc<dyn ExecutionPlan>> {
5152
// Current only support single group key
@@ -66,6 +67,26 @@ impl TopKAggregation {
6667

6768
// Check if this is ordering by an aggregate function (MIN/MAX)
6869
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+
}
6990
// ensure the sort direction matches aggregate function
7091
if desc != order_desc {
7192
return None;
@@ -100,6 +121,7 @@ impl TopKAggregation {
100121
let order = sort.properties().output_ordering()?;
101122
let order = order.iter().exactly_one().ok()?;
102123
let order_desc = order.options.descending;
124+
let nulls_first = order.options.nulls_first;
103125
let order = order.expr.downcast_ref::<Column>()?;
104126
let mut cur_col_name = order.name().to_string();
105127
let limit = sort.fetch()?;
@@ -111,7 +133,13 @@ impl TopKAggregation {
111133
}
112134
if let Some(aggr) = plan.downcast_ref::<AggregateExec>() {
113135
// either we run into an Aggregate and transform it
114-
match Self::transform_agg(aggr, &cur_col_name, order_desc, limit) {
136+
match Self::transform_agg(
137+
aggr,
138+
&cur_col_name,
139+
order_desc,
140+
nulls_first,
141+
limit,
142+
) {
115143
None => cardinality_preserved = false,
116144
Some(plan) => return Ok(Transformed::yes(plan)),
117145
}

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

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -149,11 +149,26 @@ impl GroupedTopKAggregateStream {
149149
if has_nulls && self.is_group_by_only() {
150150
self.null_group_seen = true;
151151
}
152+
// Keep the common no-NULL path free of NULL bookkeeping. Once a NULL
153+
// group exists, use the NULL-aware path until it has been resolved.
154+
let track_null_groups = !self.is_group_by_only()
155+
&& (has_nulls || self.priority_map.has_null_groups());
152156
for row_idx in 0..len {
153157
if has_nulls && vals.is_null(row_idx) {
158+
// MIN/MAX ignore NULL inputs, but a group whose values are all
159+
// NULL must still be emitted with a NULL aggregate value, so
160+
// track it. (GROUP BY-only aggregations handle NULL group keys
161+
// via `null_group_seen` instead.)
162+
if !self.is_group_by_only() {
163+
self.priority_map.insert_null(row_idx);
164+
}
154165
continue;
155166
}
156-
self.priority_map.insert(row_idx)?;
167+
if track_null_groups {
168+
self.priority_map.insert_with_null_groups(row_idx)?;
169+
} else {
170+
self.priority_map.insert(row_idx)?;
171+
}
157172
}
158173
Ok(())
159174
}

0 commit comments

Comments
 (0)