|
21 | 21 | //! |
22 | 22 | //! Reference: `org.apache.spark.sql.catalyst.util.QuantileSummaries`. |
23 | 23 | //! |
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: |
26 | 26 | //! - 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), |
27 | 28 | //! - the integer arithmetic: `floor(2 * relative_error * count)` for `delta`, |
28 | 29 | //! `2 * relative_error * count` for the compress/merge threshold, `/ 2` for |
29 | 30 | //! `target_error`, and `ceil(percentile * count)` for the query rank, |
@@ -158,10 +159,24 @@ impl QuantileSummaries { |
158 | 159 | } |
159 | 160 | let mut current_count = self.count; |
160 | 161 | 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. |
164 | 165 | 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 | + } |
165 | 180 |
|
166 | 181 | scratch.sampled.clear(); |
167 | 182 | scratch.sampled.reserve(self.sampled.len() + sorted.len()); |
@@ -597,14 +612,99 @@ mod tests { |
597 | 612 |
|
598 | 613 | #[test] |
599 | 614 | 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. |
602 | 617 | 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]); |
608 | 708 | } |
609 | 709 |
|
610 | 710 | #[test] |
|
0 commit comments