Skip to content

Commit e7a2e05

Browse files
authored
Fix TopK DISTINCT aggregation preserving NULLs (apache#22571)
## 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#22554. ## Rationale for this change TopK aggregation dropped NULL group keys for ordered DISTINCT queries. For example, `SELECT DISTINCT v FROM t ORDER BY v ASC NULLS FIRST LIMIT 1` could return an empty string instead of NULL when TopK aggregation was enabled. <!-- 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. --> ## What changes are included in this PR? This PR preserves NULL group keys for DISTINCT TopK aggregation by tracking whether a NULL group key was seen separately from the heap. The heap still only stores non-NULL values. This avoids making the TopK heap implementations handle NULL values directly. The stream also now marks itself done after emitting, so NULL-only DISTINCT results are emitted once and do not repeat. <!-- 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. --> ## Are these changes tested? Yes <!-- 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)? --> ## Are there any user-facing changes? No API Change <!-- 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 d8c4588 commit e7a2e05

3 files changed

Lines changed: 261 additions & 10 deletions

File tree

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

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -553,3 +553,87 @@ async fn test_count_distinct_optimization() -> Result<()> {
553553

554554
Ok(())
555555
}
556+
557+
/// Regression test for https://github.com/apache/datafusion/issues/22554
558+
///
559+
/// TopK aggregation for DISTINCT queries was unconditionally dropping NULL
560+
/// group keys, producing wrong results with NULLS FIRST / NULLS LAST ordering.
561+
#[tokio::test]
562+
async fn topk_distinct_preserves_nulls() -> Result<()> {
563+
let ctx = SessionContext::new_with_config(SessionConfig::new());
564+
565+
let batch = RecordBatch::try_new(
566+
Arc::new(Schema::new(vec![Field::new("v", DataType::Utf8, true)])),
567+
vec![Arc::new(StringArray::from(vec![None, Some(""), Some("a")]))],
568+
)?;
569+
let table = MemTable::try_new(batch.schema(), vec![vec![batch]])?;
570+
ctx.register_table("t", Arc::new(table))?;
571+
572+
// ASC NULLS FIRST LIMIT 1 → NULL should come first
573+
let result = ctx
574+
.sql("SELECT DISTINCT v FROM t ORDER BY v ASC NULLS FIRST LIMIT 1")
575+
.await?
576+
.collect()
577+
.await?;
578+
assert_batches_eq!(&["+---+", "| v |", "+---+", "| |", "+---+"], &result);
579+
assert!(result[0].column(0).is_null(0), "first row should be NULL");
580+
581+
// ASC NULLS FIRST LIMIT 2 → NULL, then empty string
582+
let result = ctx
583+
.sql("SELECT DISTINCT v FROM t ORDER BY v ASC NULLS FIRST LIMIT 2")
584+
.await?
585+
.collect()
586+
.await?;
587+
assert_eq!(result[0].num_rows(), 2);
588+
assert!(result[0].column(0).is_null(0));
589+
assert!(!result[0].column(0).is_null(1));
590+
591+
// ASC NULLS LAST LIMIT 1 → empty string (smallest non-null)
592+
let result = ctx
593+
.sql("SELECT DISTINCT v FROM t ORDER BY v ASC NULLS LAST LIMIT 1")
594+
.await?
595+
.collect()
596+
.await?;
597+
assert!(
598+
!result[0].column(0).is_null(0),
599+
"first row should NOT be NULL"
600+
);
601+
602+
// Full result with NULLS LAST should include NULL at end
603+
let result = ctx
604+
.sql("SELECT DISTINCT v FROM t ORDER BY v ASC NULLS LAST LIMIT 3")
605+
.await?
606+
.collect()
607+
.await?;
608+
assert_eq!(result[0].num_rows(), 3);
609+
assert!(result[0].column(0).is_null(2), "last row should be NULL");
610+
611+
// Integer column
612+
let batch = RecordBatch::try_new(
613+
Arc::new(Schema::new(vec![Field::new("v", DataType::Int64, true)])),
614+
vec![Arc::new(Int64Array::from(vec![None, Some(3), Some(1)]))],
615+
)?;
616+
let table = MemTable::try_new(batch.schema(), vec![vec![batch]])?;
617+
ctx.register_table("t_int", Arc::new(table))?;
618+
619+
let result = ctx
620+
.sql("SELECT DISTINCT v FROM t_int ORDER BY v ASC NULLS FIRST LIMIT 1")
621+
.await?
622+
.collect()
623+
.await?;
624+
assert!(
625+
result[0].column(0).is_null(0),
626+
"integer NULL should be first"
627+
);
628+
629+
let result = ctx
630+
.sql("SELECT DISTINCT v FROM t_int ORDER BY v DESC NULLS LAST LIMIT 2")
631+
.await?
632+
.collect()
633+
.await?;
634+
assert_eq!(result[0].num_rows(), 2);
635+
assert!(!result[0].column(0).is_null(0));
636+
assert!(!result[0].column(0).is_null(1));
637+
638+
Ok(())
639+
}

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

Lines changed: 56 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,8 @@ use crate::aggregates::{
2828
use crate::metrics::BaselineMetrics;
2929
use crate::stream::EmptyRecordBatchStream;
3030
use crate::{RecordBatchStream, SendableRecordBatchStream};
31-
use arrow::array::{Array, ArrayRef, RecordBatch};
31+
use arrow::array::{Array, ArrayRef, RecordBatch, new_null_array};
32+
use arrow::compute::concat;
3233
use arrow::datatypes::SchemaRef;
3334
use arrow::util::pretty::print_batches;
3435
use datafusion_common::Result;
@@ -46,13 +47,16 @@ pub struct GroupedTopKAggregateStream {
4647
partition: usize,
4748
row_count: usize,
4849
started: bool,
50+
done: bool,
4951
schema: SchemaRef,
5052
input: SendableRecordBatchStream,
5153
baseline_metrics: BaselineMetrics,
5254
group_by_metrics: GroupByMetrics,
5355
aggregate_arguments: Vec<Vec<Arc<dyn PhysicalExpr>>>,
5456
group_by: Arc<PhysicalGroupBy>,
5557
priority_map: PriorityMap,
58+
/// Whether a NULL group key has been seen for a group-by-only aggregation.
59+
null_group_seen: bool,
5660
}
5761

5862
impl GroupedTopKAggregateStream {
@@ -109,6 +113,7 @@ impl GroupedTopKAggregateStream {
109113
Ok(GroupedTopKAggregateStream {
110114
partition,
111115
started: false,
116+
done: false,
112117
row_count: 0,
113118
schema: agg_schema,
114119
input,
@@ -117,6 +122,7 @@ impl GroupedTopKAggregateStream {
117122
aggregate_arguments,
118123
group_by,
119124
priority_map,
125+
null_group_seen: false,
120126
})
121127
}
122128
}
@@ -128,6 +134,10 @@ impl RecordBatchStream for GroupedTopKAggregateStream {
128134
}
129135

130136
impl GroupedTopKAggregateStream {
137+
fn is_group_by_only(&self) -> bool {
138+
self.aggregate_arguments.is_empty()
139+
}
140+
131141
fn intern(&mut self, ids: &ArrayRef, vals: &ArrayRef) -> Result<()> {
132142
let _timer = self.group_by_metrics.time_calculating_group_ids.timer();
133143

@@ -136,6 +146,9 @@ impl GroupedTopKAggregateStream {
136146
.set_batch(Arc::clone(ids), Arc::clone(vals));
137147

138148
let has_nulls = vals.null_count() > 0;
149+
if has_nulls && self.is_group_by_only() {
150+
self.null_group_seen = true;
151+
}
139152
for row_idx in 0..len {
140153
if has_nulls && vals.is_null(row_idx) {
141154
continue;
@@ -144,6 +157,39 @@ impl GroupedTopKAggregateStream {
144157
}
145158
Ok(())
146159
}
160+
161+
fn emit_columns(&mut self) -> Result<Vec<ArrayRef>> {
162+
let mut cols = if self.priority_map.is_empty() {
163+
vec![]
164+
} else {
165+
self.priority_map.emit()?
166+
};
167+
168+
// GROUP BY-only aggregation covers DISTINCT-like queries. The group
169+
// key and heap value are the same column, but the output schema has
170+
// only the group key.
171+
if self.is_group_by_only() {
172+
cols.truncate(1);
173+
if self.null_group_seen {
174+
self.append_null_group(&mut cols)?;
175+
}
176+
}
177+
178+
Ok(cols)
179+
}
180+
181+
fn append_null_group(&self, cols: &mut Vec<ArrayRef>) -> Result<()> {
182+
let dt = self.schema.field(0).data_type();
183+
let null_arr = new_null_array(dt, 1);
184+
if cols.is_empty() {
185+
cols.push(null_arr);
186+
} else {
187+
// NULL group keys are tracked outside the heap, so append a
188+
// one-row NULL array to the emitted non-NULL group key column.
189+
cols[0] = concat(&[cols[0].as_ref(), null_arr.as_ref()])?;
190+
}
191+
Ok(())
192+
}
147193
}
148194

149195
impl Stream for GroupedTopKAggregateStream {
@@ -153,6 +199,9 @@ impl Stream for GroupedTopKAggregateStream {
153199
mut self: Pin<&mut Self>,
154200
cx: &mut Context<'_>,
155201
) -> Poll<Option<Self::Item>> {
202+
if self.done {
203+
return Poll::Ready(None);
204+
}
156205
let elapsed_compute = self.baseline_metrics.elapsed_compute().clone();
157206
let emitting_time = self.group_by_metrics.emitting_time.clone();
158207
while let Poll::Ready(res) = self.input.poll_next_unpin(cx) {
@@ -185,8 +234,8 @@ impl Stream for GroupedTopKAggregateStream {
185234
"Exactly 1 group value required"
186235
);
187236
let group_by_values = Arc::clone(&group_by_values[0][0]);
188-
let input_values = if self.aggregate_arguments.is_empty() {
189-
// DISTINCT case: use group key as both key and value
237+
let input_values = if self.is_group_by_only() {
238+
// GROUP BY-only case: use group key as both key and value
190239
Arc::clone(&group_by_values)
191240
} else {
192241
// MIN/MAX case: evaluate aggregate expressions
@@ -209,18 +258,14 @@ impl Stream for GroupedTopKAggregateStream {
209258
// Release the input pipeline's resources before emitting.
210259
let input_schema = self.input.schema();
211260
self.input = Box::pin(EmptyRecordBatchStream::new(input_schema));
212-
if self.priority_map.is_empty() {
261+
if self.priority_map.is_empty() && !self.null_group_seen {
213262
trace!("partition {} emit None", self.partition);
263+
self.done = true;
214264
return Poll::Ready(None);
215265
}
216266
let batch = {
217267
let _timer = emitting_time.timer();
218-
let mut cols = self.priority_map.emit()?;
219-
// For DISTINCT case (no aggregate expressions), only use the group key column
220-
// since the schema only has one field and key/value are the same
221-
if self.aggregate_arguments.is_empty() {
222-
cols.truncate(1);
223-
}
268+
let cols = self.emit_columns()?;
224269
RecordBatch::try_new(Arc::clone(&self.schema), cols)?
225270
};
226271
let batch = batch.record_output(&self.baseline_metrics);
@@ -232,6 +277,7 @@ impl Stream for GroupedTopKAggregateStream {
232277
if log::log_enabled!(Level::Trace) {
233278
print_batches(std::slice::from_ref(&batch))?;
234279
}
280+
self.done = true;
235281
return Poll::Ready(Some(Ok(batch)));
236282
}
237283
// inner had error, return to caller

‎datafusion/sqllogictest/test_files/aggregates_topk.slt‎

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -456,6 +456,127 @@ select count(*) from (select category from values_table group by category order
456456
----
457457
3
458458

459+
# Test DISTINCT with NULLs and NULLS FIRST ordering (issue #22554)
460+
statement ok
461+
create table nullable_vals (v varchar) as values (NULL), (''), ('a'), ('b');
462+
463+
# Verify this regression test exercises the TopK aggregation path
464+
query TT
465+
explain select distinct v from nullable_vals order by v asc nulls first limit 1;
466+
----
467+
logical_plan
468+
01)Sort: nullable_vals.v ASC NULLS FIRST, fetch=1
469+
02)--Aggregate: groupBy=[[nullable_vals.v]], aggr=[[]]
470+
03)----TableScan: nullable_vals projection=[v]
471+
physical_plan
472+
01)SortPreservingMergeExec: [v@0 ASC], fetch=1
473+
02)--SortExec: TopK(fetch=1), expr=[v@0 ASC], preserve_partitioning=[true]
474+
03)----AggregateExec: mode=FinalPartitioned, gby=[v@0 as v], aggr=[], lim=[1]
475+
04)------RepartitionExec: partitioning=Hash([v@0], 4), input_partitions=1
476+
05)--------AggregateExec: mode=Partial, gby=[v@0 as v], aggr=[], lim=[1]
477+
06)----------DataSourceExec: partitions=1, partition_sizes=[1]
478+
479+
# NULLS FIRST: NULL should be the first row returned by LIMIT
480+
query T
481+
select distinct v from nullable_vals order by v asc nulls first limit 1;
482+
----
483+
NULL
484+
485+
query T
486+
select distinct v from nullable_vals order by v asc nulls first limit 2;
487+
----
488+
NULL
489+
(empty)
490+
491+
query T
492+
select distinct v from nullable_vals order by v asc nulls first limit 3;
493+
----
494+
NULL
495+
(empty)
496+
a
497+
498+
# NULLS LAST: non-null values come first
499+
query T
500+
select distinct v from nullable_vals order by v asc nulls last limit 1;
501+
----
502+
(empty)
503+
504+
query T
505+
select distinct v from nullable_vals order by v asc nulls last limit 4;
506+
----
507+
(empty)
508+
a
509+
b
510+
NULL
511+
512+
# DESC NULLS FIRST: NULL comes first
513+
query T
514+
select distinct v from nullable_vals order by v desc nulls first limit 1;
515+
----
516+
NULL
517+
518+
# DESC NULLS LAST: NULL comes last
519+
query T
520+
select distinct v from nullable_vals order by v desc nulls last limit 1;
521+
----
522+
b
523+
524+
query T
525+
select distinct v from nullable_vals order by v desc nulls last limit 4;
526+
----
527+
b
528+
a
529+
(empty)
530+
NULL
531+
532+
# Test with integer column containing NULLs
533+
statement ok
534+
create table nullable_ints (v int) as values (NULL), (3), (1), (2);
535+
536+
query I
537+
select distinct v from nullable_ints order by v asc nulls first limit 1;
538+
----
539+
NULL
540+
541+
query I
542+
select distinct v from nullable_ints order by v asc nulls first limit 3;
543+
----
544+
NULL
545+
1
546+
2
547+
548+
query I
549+
select distinct v from nullable_ints order by v desc nulls last limit 2;
550+
----
551+
3
552+
2
553+
554+
query I
555+
select distinct v from nullable_ints order by v asc nulls last limit 4;
556+
----
557+
1
558+
2
559+
3
560+
NULL
561+
562+
# Test with all-NULL column
563+
statement ok
564+
create table all_nulls (v varchar) as values (NULL), (NULL);
565+
566+
query T
567+
select distinct v from all_nulls order by v asc nulls first limit 1;
568+
----
569+
NULL
570+
571+
statement ok
572+
drop table nullable_vals;
573+
574+
statement ok
575+
drop table nullable_ints;
576+
577+
statement ok
578+
drop table all_nulls;
579+
459580
statement ok
460581
drop table values_table;
461582

0 commit comments

Comments
 (0)