Skip to content

Commit 52a3a33

Browse files
authored
fix: match Spark percentile ordering for negative NaNs (#6829)
1 parent d735166 commit 52a3a33

2 files changed

Lines changed: 176 additions & 12 deletions

File tree

‎native/spark-expr/src/agg_funcs/quantile_summaries.rs‎

Lines changed: 112 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -21,9 +21,10 @@
2121
//!
2222
//! Reference: `org.apache.spark.sql.catalyst.util.QuantileSummaries`.
2323
//!
24-
//! Results are bit-identical to Spark for deterministic plans. What is
25-
//! load-bearing for that identity, and must not change:
24+
//! Results match Spark for deterministic plans (NaN bit patterns are not
25+
//! specified). What is load-bearing for that identity, and must not change:
2626
//! - the 50000-value head-buffer flush boundary (`DEFAULT_HEAD_SIZE`),
27+
//! - Java's primitive-array ordering of that buffer (all NaNs last, -0.0 before 0.0),
2728
//! - the integer arithmetic: `floor(2 * relative_error * count)` for `delta`,
2829
//! `2 * relative_error * count` for the compress/merge threshold, `/ 2` for
2930
//! `target_error`, and `ceil(percentile * count)` for the query rank,
@@ -158,10 +159,24 @@ impl QuantileSummaries {
158159
}
159160
let mut current_count = self.count;
160161
let mut sorted = std::mem::take(&mut self.head_sampled);
161-
// Spark relies on `Array[Double].sorted`. The sort key is the value
162-
// itself, so equal keys are bit-equal elements and stability is
163-
// irrelevant; `total_cmp` gives a deterministic total order.
162+
// Spark's `Array[Double].sorted` puts every NaN last, regardless of
163+
// sign or payload. IEEE total order agrees for every other value,
164+
// including -0.0 before 0.0, but puts negative NaNs at the front.
164165
sorted.sort_unstable_by(|a, b| a.total_cmp(b));
166+
// Move that leading NaN block behind the already sorted values and
167+
// positive NaNs. Java compares all NaNs equal, so their suffix order
168+
// does not affect ranks. This preserves their original bits and adds
169+
// no per-comparison cost. Negative NaNs form a prefix in total order,
170+
// so finding its end needs only a binary search, even for all-NaN input.
171+
// Most buffers have no negative NaN. Avoid the binary search in that
172+
// case, especially for the many small buffers of grouped aggregates.
173+
if sorted
174+
.first()
175+
.is_some_and(|v| v.is_nan() && v.is_sign_negative())
176+
{
177+
let leading_nans = sorted.partition_point(|v| v.is_nan() && v.is_sign_negative());
178+
sorted.rotate_left(leading_nans);
179+
}
165180

166181
scratch.sampled.clear();
167182
scratch.sampled.reserve(self.sampled.len() + sorted.len());
@@ -597,14 +612,99 @@ mod tests {
597612

598613
#[test]
599614
fn signed_zero_ordering_is_deterministic() {
600-
// `total_cmp` orders -0.0 before 0.0; inserting both must not panic and
601-
// must produce a value drawn from the input.
615+
// Java's primitive-array ordering puts -0.0 before 0.0, including at
616+
// the percentile endpoints. SQL ordering treats the two zeros as equal.
602617
let qs = summary_of(&[-0.0, 0.0, -0.0, 0.0, 1.0]);
603-
let got = qs.query(&[0.5]).unwrap()[0];
604-
assert!(
605-
got == 0.0 || got == 1.0,
606-
"median of signed zeros produced {got}"
607-
);
618+
assert_eq!(qs.query(&[0.0]).unwrap()[0].to_bits(), (-0.0f64).to_bits());
619+
let zeros = summary_of(&[0.0, -0.0, 0.0, -0.0]);
620+
assert_eq!(zeros.query(&[1.0]).unwrap()[0].to_bits(), 0.0f64.to_bits());
621+
}
622+
623+
#[test]
624+
fn non_finite_values_use_java_primitive_array_order() {
625+
let qs = summary_of(&[
626+
-f64::NAN,
627+
f64::INFINITY,
628+
1.5,
629+
-0.0,
630+
f64::from_bits(0xfff0_0000_0000_0001),
631+
f64::NEG_INFINITY,
632+
0.0,
633+
-1.5,
634+
f64::NAN,
635+
]);
636+
let expected = [f64::NEG_INFINITY, -1.5, -0.0, 0.0, 1.5, f64::INFINITY];
637+
assert_eq!(qs.sampled.len(), 9);
638+
for (sample, value) in qs.sampled.iter().zip(expected) {
639+
assert_eq!(sample.value.to_bits(), value.to_bits());
640+
}
641+
assert!(qs.sampled[expected.len()..]
642+
.iter()
643+
.all(|s| s.value.is_nan()));
644+
let mut nan_bits: Vec<_> = qs.sampled[expected.len()..]
645+
.iter()
646+
.map(|s| s.value.to_bits())
647+
.collect();
648+
nan_bits.sort_unstable();
649+
let mut expected_nan_bits = [
650+
(-f64::NAN).to_bits(),
651+
f64::NAN.to_bits(),
652+
0xfff0_0000_0000_0001,
653+
];
654+
expected_nan_bits.sort_unstable();
655+
assert_eq!(nan_bits, expected_nan_bits);
656+
}
657+
658+
#[test]
659+
fn nan_sign_and_payload_match_spark_across_head_flushes() {
660+
// Spark's result for 300000 ascending values with the first replaced
661+
// by NaN, at the default accuracy. Six head-buffer flushes exercise
662+
// both the initial sort and its interleave with an existing summary.
663+
let percentages = [0.0, 0.25, 0.5, 0.75, 1.0];
664+
let expected = [1.0, 75001.0, 150000.0, 225013.0];
665+
for bits in [
666+
0x7ff8_0000_0000_0000,
667+
0xfff8_0000_0000_0000,
668+
0x7ff8_0000_0000_0042,
669+
0xfff8_0000_0000_0042,
670+
0x7ff0_0000_0000_0001,
671+
0xfff0_0000_0000_0001,
672+
] {
673+
let mut values: Vec<f64> = (0..300_000).map(|i| i as f64).collect();
674+
values[0] = f64::from_bits(bits);
675+
let qs = summary_of(&values);
676+
let got = qs.query(&percentages).unwrap();
677+
assert_eq!(qs.count(), values.len() as i64);
678+
assert_eq!(&got[..4], &expected, "NaN bits: {bits:#x}");
679+
assert!(got[4].is_nan(), "maximum for NaN bits {bits:#x}: {got:?}");
680+
}
681+
}
682+
683+
#[test]
684+
fn nan_sign_does_not_change_serialized_partial_merges() {
685+
let percentages = [0.0, 0.25, 0.5, 0.75, 1.0];
686+
let mut merged = Vec::new();
687+
for nan in [f64::NAN, -f64::NAN] {
688+
let mut summary =
689+
QuantileSummaries::new(QuantileSummaries::DEFAULT_COMPRESS_THRESHOLD, EPS);
690+
let mut scratch = QuantileSummariesScratch::default();
691+
for partition in 0..3 {
692+
let start = partition * 100_000;
693+
let mut values: Vec<f64> = (start..start + 100_000).map(|i| i as f64).collect();
694+
values[0] = nan;
695+
let partial = summary_of(&values);
696+
let decoded = QuantileSummaries::from_bytes(
697+
QuantileSummaries::DEFAULT_COMPRESS_THRESHOLD,
698+
&partial.to_bytes(),
699+
);
700+
summary.merge(&decoded, &mut scratch);
701+
}
702+
assert_eq!(summary.count(), 300_000);
703+
let got = summary.query(&percentages).unwrap();
704+
assert!(got[4].is_nan(), "maximum after merging: {got:?}");
705+
merged.push(got);
706+
}
707+
assert_eq!(&merged[0][..4], &merged[1][..4]);
608708
}
609709

610710
#[test]
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
-- Licensed to the Apache Software Foundation (ASF) under one
2+
-- or more contributor license agreements. See the NOTICE file
3+
-- distributed with this work for additional information
4+
-- regarding copyright ownership. The ASF licenses this file
5+
-- to you under the Apache License, Version 2.0 (the
6+
-- "License"); you may not use this file except in compliance
7+
-- with the License. You may obtain a copy of the License at
8+
--
9+
-- http://www.apache.org/licenses/LICENSE-2.0
10+
--
11+
-- Unless required by applicable law or agreed to in writing,
12+
-- software distributed under the License is distributed on an
13+
-- "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
-- KIND, either express or implied. See the License for the
15+
-- specific language governing permissions and limitations
16+
-- under the License.
17+
18+
-- One input partition, with more than the 50000-value head-buffer threshold
19+
-- for both scalar and grouped aggregates. Negate NaN after the Parquet scan:
20+
-- Spark canonicalizes NaNs on write, so storing -NaN would miss this bug.
21+
-- Plain queries assert native execution as well as exact Spark results.
22+
-- Config: spark.sql.files.maxPartitionBytes=134217728
23+
24+
statement
25+
CREATE TABLE test_approx_percentile_nan(d double, f float, g int) USING parquet
26+
27+
statement
28+
INSERT INTO test_approx_percentile_nan
29+
SELECT IF(id = 0, double('NaN'), cast(id AS double)),
30+
IF(id = 0, float('NaN'), cast(id AS float)),
31+
cast(id % 2 AS int)
32+
FROM range(0, 300000, 1, 1)
33+
34+
-- Canonical NaN control, with both numeric input types and array output.
35+
query
36+
SELECT percentile_approx(d, array(0.0D, 0.25D, 0.5D, 0.75D, 1.0D)),
37+
approx_percentile(f, array(0.0D, 0.25D, 0.5D, 0.75D, 1.0D))
38+
FROM test_approx_percentile_nan
39+
40+
-- Negative-sign NaN must not change any rank or replace the maximum with a
41+
-- finite value. Six head-buffer flushes reproduce issue #6519.
42+
query
43+
SELECT percentile_approx(IF(isnan(d), -d, d), array(0.0D, 0.25D, 0.5D, 0.75D, 1.0D))
44+
FROM test_approx_percentile_nan
45+
46+
query
47+
SELECT approx_percentile(IF(isnan(f), -f, f), array(0.0D, 0.25D, 0.5D, 0.75D, 1.0D))
48+
FROM test_approx_percentile_nan
49+
50+
-- Grouped accumulators and their partial-to-final serialized states. Each
51+
-- group exceeds the head-buffer threshold; only group 0 contains a NaN.
52+
query
53+
SELECT g,
54+
percentile_approx(IF(isnan(d), -d, d), array(0.0D, 0.25D, 0.5D, 0.75D, 1.0D)),
55+
approx_percentile(IF(isnan(f), -f, f), array(0.0D, 0.25D, 0.5D, 0.75D, 1.0D))
56+
FROM test_approx_percentile_nan GROUP BY g ORDER BY g
57+
58+
-- Scalar output uses the same ordering, including the NaN endpoint.
59+
query
60+
SELECT percentile_approx(IF(isnan(d), -d, d), 0.5D),
61+
isnan(percentile_approx(IF(isnan(d), -d, d), 1.0D)),
62+
approx_percentile(IF(isnan(f), -f, f), 0.5D),
63+
isnan(approx_percentile(IF(isnan(f), -f, f), 1.0D))
64+
FROM test_approx_percentile_nan

0 commit comments

Comments
 (0)