Skip to content

Commit 8f77b41

Browse files
authored
fix: correct NaN grouping and eviction in TopK aggregation (apache#26445)
## Which issue does this PR close? Closes apache#26444. ## Rationale for this change Repeated identical NaN keys can form separate TopK groups, and evicting a NaN group can panic. Valid `GROUP BY ... ORDER BY ... LIMIT` queries can therefore return incorrect results or fail. ## What changes are included in this PR? - Compare primitive grouping keys with Arrow equality so identical NaN payloads match. - Normalize signed zero with `HashValue::normalize_key`, consistent with ordinary grouping while preserving distinct NaN payloads. - Remove occupied entries by their known store index during eviction and NULL aggregate transitions. A separate prerequisite commit retains the RSS sampling fix from apache#26208. It samples the current process before query execution so short queries cannot leave the recorded maximum at zero. Memory thresholds are unchanged. ## What is the testing strategy for this PR? The SQL regressions cover repeated NaN keys and eviction. At main commit `7f493a565`, the eviction regression fails with `internal error: entered unreachable code`; it passes with this fix. Hash-table tests cover Float16/32/64, distinct NaN payloads, signed zero, and NULL aggregate transitions. Validation was rerun after merging main at `350ca7650`. The extended workspace suite, including the migrated `extended_tests` target, full SQL logic suite, and `cargo test --profile ci -p datafusion-cli` passed. `cargo fmt --all`, `cargo clippy --all-targets --all-features -- -D warnings`, and `UV_FROZEN=true uv run ./dev/rust_lint.sh` also passed. The existing `topk_aggregate` primitive-key benchmark was run against main at `c61fb09ac` using the unoptimized CI profile on a shared host. Timing varied too much to draw a performance conclusion. ## Are there any user-facing changes? Identical NaN keys form one TopK group, and evicting a NaN group succeeds. Signed-zero grouping matches ordinary aggregation. There are no public API changes. AI-assisted contribution.
1 parent 6341b5c commit 8f77b41

3 files changed

Lines changed: 137 additions & 27 deletions

File tree

‎datafusion/core/tests/memory_limit_validation/utils.rs‎

Lines changed: 14 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -30,30 +30,35 @@ where
3030
F: FnOnce() -> Fut,
3131
Fut: Future<Output = T>,
3232
{
33-
// Initialize system information
34-
let mut system = System::new_all();
35-
system.refresh_all();
36-
3733
// Get the current process ID
3834
let pid = sysinfo::get_current_pid().expect("Failed to get current PID");
39-
40-
// Shared atomic variable to store max RSS
41-
let max_rss = Arc::new(AtomicUsize::new(0));
35+
let mut system = System::new();
36+
system.refresh_processes_specifics(
37+
ProcessesToUpdate::Some(&[pid]),
38+
true,
39+
ProcessRefreshKind::nothing().with_memory().without_tasks(),
40+
);
41+
let initial_rss = system
42+
.process(pid)
43+
.expect("Current process is missing")
44+
.memory();
45+
// Capture a baseline before execution; monitor startup may outlast a short query.
46+
let max_rss = Arc::new(AtomicUsize::new(initial_rss as usize));
4247

4348
// Clone for the monitoring task
4449
let max_rss_clone = Arc::clone(&max_rss);
4550

4651
// Spawn a monitoring task
4752
let monitor_handle = SpawnedTask::spawn(async move {
48-
let mut sys = System::new_all();
53+
let mut sys = system;
4954
let mut interval = interval(Duration::from_millis(7));
5055

5156
loop {
5257
interval.tick().await;
5358
sys.refresh_processes_specifics(
5459
ProcessesToUpdate::Some(&[pid]),
5560
true,
56-
ProcessRefreshKind::nothing().with_memory(),
61+
ProcessRefreshKind::nothing().with_memory().without_tasks(),
5762
);
5863
if let Some(process) = sys.process(pid) {
5964
let rss_bytes = process.memory();

‎datafusion/physical-plan/src/aggregates/topk/hash_table.rs‎

Lines changed: 95 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -5,11 +5,11 @@
55
//! A wrapper around `hashbrown::HashTable` that allows entries to be tracked by index
66
77
use crate::aggregates::group_values::HashValue;
8-
use crate::aggregates::topk::heap::Comparable;
98
use arrow::array::types::{IntervalDayTime, IntervalMonthDayNano};
109
use arrow::array::{
11-
Array, ArrayRef, ArrowPrimitiveType, LargeStringArray, PrimitiveArray, StringArray,
12-
StringViewArray, builder::PrimitiveBuilder, cast::AsArray, downcast_primitive,
10+
Array, ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, LargeStringArray,
11+
PrimitiveArray, StringArray, StringViewArray, builder::PrimitiveBuilder,
12+
cast::AsArray, downcast_primitive,
1313
};
1414
use arrow::array::{ArrayAccessor, StringArrayType};
1515
use arrow::datatypes::{DataType, i256};
@@ -119,10 +119,7 @@ where
119119
}
120120

121121
// An implementation of ArrowHashTable for any `ArrowPrimitiveType` key
122-
struct PrimitiveHashTable<VAL: ArrowPrimitiveType>
123-
where
124-
Option<<VAL as ArrowPrimitiveType>::Native>: Comparable,
125-
{
122+
struct PrimitiveHashTable<VAL: ArrowPrimitiveType> {
126123
owned: PrimitiveArray<VAL>,
127124
map: TopKHashTable<VAL::Native>,
128125
rnd: RandomState,
@@ -211,7 +208,8 @@ where
211208

212209
impl<VAL: ArrowPrimitiveType> PrimitiveHashTable<VAL>
213210
where
214-
Option<<VAL as ArrowPrimitiveType>::Native>: Comparable + HashValue,
211+
VAL::Native: HashValue,
212+
Option<VAL::Native>: HashValue,
215213
{
216214
pub fn new(limit: usize, value_type: DataType) -> Self {
217215
Self {
@@ -225,20 +223,25 @@ where
225223
/// Computes the id and its hash for the given row, for hash table lookups
226224
#[inline]
227225
fn id_and_hash(&self, row_idx: usize) -> (Option<VAL::Native>, u64) {
228-
let id: Option<VAL::Native> = some_value(&self.owned, row_idx);
226+
let id = some_value(&self.owned, row_idx).map(HashValue::normalize_key);
229227
let hash: u64 = id.hash(&self.rnd);
230228
(id, hash)
231229
}
232230

233231
#[inline]
234232
fn eq_fn(id: Option<VAL::Native>) -> impl Fn(&Option<VAL::Native>) -> bool {
235-
move |mi| id == *mi
233+
move |mi| match (id, *mi) {
234+
(Some(left), Some(right)) => left.is_eq(right),
235+
(None, None) => true,
236+
_ => false,
237+
}
236238
}
237239
}
238240

239241
impl<VAL: ArrowPrimitiveType> ArrowHashTable for PrimitiveHashTable<VAL>
240242
where
241-
Option<<VAL as ArrowPrimitiveType>::Native>: Comparable + HashValue,
243+
VAL::Native: HashValue,
244+
Option<VAL::Native>: HashValue,
242245
{
243246
fn set_batch(&mut self, ids: ArrayRef) {
244247
self.owned = ids.as_primitive().clone();
@@ -293,7 +296,7 @@ where
293296
}
294297
}
295298

296-
impl<ID: PartialEq> TopKHashTable<ID> {
299+
impl<ID> TopKHashTable<ID> {
297300
pub fn new(limit: usize, capacity: usize) -> Self {
298301
Self {
299302
map: HashTable::with_capacity(capacity),
@@ -311,11 +314,8 @@ impl<ID: PartialEq> TopKHashTable<ID> {
311314

312315
/// Remove the entry stored at `map_idx`, freeing its store slot for reuse
313316
fn remove_at(&mut self, map_idx: usize) {
314-
let item_to_remove = &self.store[map_idx];
315-
let hash = item_to_remove.hash;
316-
let id_to_remove = &item_to_remove.id;
317-
318-
let eq = |idx: &usize| self.store[*idx].id == *id_to_remove;
317+
let hash = self.store[map_idx].hash;
318+
let eq = |idx: &usize| *idx == map_idx;
319319
let hasher = |idx: &usize| self.store[*idx].hash;
320320
match self.map.entry(hash, eq, hasher) {
321321
Entry::Occupied(entry) => {
@@ -609,16 +609,93 @@ pub fn new_hash_table(
609609
mod tests {
610610
use super::*;
611611
use arrow::array::TimestampMillisecondArray;
612+
use arrow::datatypes::{Float16Type, Float32Type, Float64Type};
612613
use arrow_schema::TimeUnit;
613614
use std::collections::BTreeMap;
614615

615-
fn assert_nulls<ID: PartialEq>(map: &TopKHashTable<ID>, expected: &[usize]) {
616+
fn assert_nulls<ID>(map: &TopKHashTable<ID>, expected: &[usize]) {
616617
assert_eq!(map.null_count, expected.len());
617618
let mut actual = Vec::new();
618619
assert_eq!(map.null_map_idxs(&mut actual), expected.len());
619620
assert_eq!(actual, expected);
620621
}
621622

623+
fn check_float_keys<T: ArrowPrimitiveType>(
624+
nan: T::Native,
625+
other_nan: T::Native,
626+
negative_zero: T::Native,
627+
) -> Result<()> {
628+
let ids: ArrayRef = Arc::new(PrimitiveArray::<T>::from_iter_values([
629+
nan,
630+
nan,
631+
other_nan,
632+
negative_zero,
633+
T::Native::default(),
634+
]));
635+
let data_type = ids.data_type().clone();
636+
let mut ht = new_hash_table(3, data_type.clone())?;
637+
ht.set_batch(Arc::clone(&ids));
638+
639+
let (nan_idx, kind) = ht.find_or_insert(0, 0);
640+
assert_eq!(kind, InsertKind::New);
641+
assert_eq!(ht.find_or_insert(1, 0), (nan_idx, InsertKind::Existing));
642+
let (_, kind) = ht.find_or_insert(2, 0);
643+
assert_eq!(kind, InsertKind::New);
644+
let (zero_idx, kind) = ht.find_or_insert(3, 0);
645+
assert_eq!(kind, InsertKind::New);
646+
assert_eq!(ht.find_or_insert(4, 0), (zero_idx, InsertKind::Existing));
647+
assert_eq!(ht.len(), 3);
648+
let keys = ht.take_all(vec![zero_idx]);
649+
assert!(
650+
keys.as_primitive::<T>()
651+
.value(0)
652+
.is_eq(T::Native::default())
653+
);
654+
655+
// A NaN key must also survive NULL aggregate value transitions.
656+
assert!(ht.insert_null(0));
657+
assert!(!ht.insert_null(1));
658+
let (nan_idx, kind) = ht.find_or_insert(1, 0);
659+
assert_eq!(kind, InsertKind::ReplacedNull);
660+
ht.take_all(vec![nan_idx]);
661+
assert!(ht.insert_null(0));
662+
assert!(ht.remove_if_null(1));
663+
assert_eq!(ht.len(), 0);
664+
665+
let mut ht = new_hash_table(1, data_type)?;
666+
ht.set_batch(ids);
667+
ht.find_or_insert(0, 0);
668+
let (zero_idx, kind) = ht.find_or_insert(3, 0);
669+
assert_eq!(kind, InsertKind::New);
670+
assert_eq!(ht.len(), 1);
671+
let keys = ht.take_all(vec![zero_idx]);
672+
assert!(
673+
keys.as_primitive::<T>()
674+
.value(0)
675+
.is_eq(T::Native::default())
676+
);
677+
Ok(())
678+
}
679+
680+
#[test]
681+
fn should_handle_float_keys() -> Result<()> {
682+
check_float_keys::<Float16Type>(
683+
f16::from_bits(0x7e00),
684+
f16::from_bits(0x7e01),
685+
f16::from_bits(0x8000),
686+
)?;
687+
check_float_keys::<Float32Type>(
688+
f32::NAN,
689+
f32::from_bits(f32::NAN.to_bits() + 1),
690+
-0.0,
691+
)?;
692+
check_float_keys::<Float64Type>(
693+
f64::NAN,
694+
f64::from_bits(f64::NAN.to_bits() + 1),
695+
-0.0,
696+
)
697+
}
698+
622699
#[test]
623700
fn should_emit_correct_type() -> Result<()> {
624701
let ids =

‎datafusion/sqllogictest/test_files/aggregates_topk.slt‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -858,3 +858,31 @@ drop table topk_parquet_keys;
858858

859859
statement ok
860860
drop table topk_parquet;
861+
862+
# Repeated NaN keys must form one group. Evicting that group must also work.
863+
statement ok
864+
set datafusion.execution.target_partitions = 1;
865+
866+
query RI
867+
SELECT k, MAX(v) FROM (VALUES
868+
(CAST('NaN' AS DOUBLE), 1),
869+
(CAST('NaN' AS DOUBLE), 2),
870+
(CAST(0 AS DOUBLE), 3)
871+
) AS t(k, v)
872+
GROUP BY k ORDER BY MAX(v) DESC NULLS LAST LIMIT 3;
873+
----
874+
0 3
875+
NaN 2
876+
877+
query RI
878+
SELECT k, MAX(v) FROM (VALUES
879+
(CAST('NaN' AS DOUBLE), 1),
880+
(CAST('NaN' AS DOUBLE), 2),
881+
(CAST(0 AS DOUBLE), 3)
882+
) AS t(k, v)
883+
GROUP BY k ORDER BY MAX(v) DESC NULLS LAST LIMIT 1;
884+
----
885+
0 3
886+
887+
statement ok
888+
set datafusion.execution.target_partitions = 4;

0 commit comments

Comments
 (0)