Skip to content

Commit 1bc8b2f

Browse files
authored
refactor: Centralize float normalization (apache#26595)
## Which issue does this PR close? - Part of apache#26138 bringing the existing `0.0/-0.0` float handling into one place. ## Rationale for this change DataFusion treats `-0.0` and `0.0` as the same number apache#22835. The code that makes this work is spread across multiple places. This PR moves the existing code into one module without changing its semantics. ### The new module DataFusion Comet has a similar module, [`native/spark-expr/src/float_semantics`](https://github.com/apache/datafusion-comet/blob/main/native/spark-expr/src/float_semantics/mod.rs), which puts Spark's `-0.0`/NaN rules in one place. This PR follows its naming. The public API is a set of free functions: ```rust /// `-0.0` becomes `0.0`; everything else, including NaN payloads, is kept. pub fn normalize_float<T: FloatSemantics>(v: T) -> T; /// The order DataFusion sorts floats in (IEEE 754 totalOrder, same as Arrow). pub fn compare_floats<T: FloatSemantics>(left: T, right: T) -> Ordering; pub fn float_lt<T: FloatSemantics>(left: T, right: T) -> bool; pub fn float_gt<T: FloatSemantics>(left: T, right: T) -> bool; /// The value hashed in place of a float. pub fn hash_input<T: FloatSemantics>(v: T) -> T; /// `normalize_float` applied to every float in an array (including nested ones) or a scalar. pub fn normalize_floats(array: &ArrayRef) -> ArrayRef; pub fn normalize_float_scalar(scalar: ScalarValue) -> ScalarValue; pub fn has_float_leaf(data_type: &DataType) -> bool; ``` Comet's functions are generic over `num::Float`. DataFusion also has to cover `f16`, and `half` is built without its `num-traits` feature, so a small trait, `FloatSemantics`, serves as the bound. It is implemented for `f16`, `f32` and `f64`: ```rust pub trait FloatSemantics: Copy { /// Whether `normalize_float` would change this value. fn needs_normalization(self) -> bool; fn normalize(self) -> Self; fn compare(self, other: Self) -> Ordering; } ``` There are two major differences from Comet. `normalize_floats` also reaches floats inside nested types, where Comet has a separate `normalize_nested_floats`. And normalization here only folds `-0.0`; NaN canonicalization and SQL ordering are not part of this PR. Once those are added, Comet's layout (`normalize`, `compare` and `kernels` submodules) is a good template for growing the module. ## What changes are included in this PR? A new module, `datafusion_common::float_semantics`, now decides when two floats count as the same value and how floats are ordered. All the following parts now use this module: - hashing (hash joins/grouping) - GROUP BY, DISTINCT and the array_* set functions - comparisons like = and IS DISTINCT FROM - the join types that compare keys - min, max, ORDER BY ... LIMIT (TopK) and range repartitioning ## What is the testing strategy for this PR? - Query results don't change, so the existing tests are the main check. - unit tests for the new module. ## Are there any user-facing changes? - Added `datafusion_common::float_semantics` with the functions above and the `FloatSemantics` trait. - `normalize_float_zero` and `normalize_float_zero_scalar` in `datafusion_common::utils` are deprecated in favor of `normalize_floats` and `normalize_float_scalar`. - No change in query behaviour. ## LLM-generated code disclosure This PR includes LLM-generated code and comments. All LLM-generated content has been manually reviewed.
1 parent c8c0464 commit 1bc8b2f

22 files changed

Lines changed: 438 additions & 203 deletions

File tree

Lines changed: 347 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,347 @@
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+
//! Float semantics for DataFusion.
19+
//!
20+
//! Arrow's comparison kernels work on the bit pattern of a float,
21+
//! i.e. IEEE 754 totalOrder. DataFusion deviates from that in one
22+
//! respect: `+0.0` and `-0.0` are equal, hash the same and fall into the same
23+
//! group. See [`normalize_float`], [`normalize_floats`] and
24+
//! [`normalize_float_scalar`]. Ordering still follows totalOrder, so
25+
//! [`compare_floats`] sorts `-0.0` before `+0.0`.
26+
//!
27+
//! Every comparison, hash or grouping boundary should be built from these
28+
//! helpers rather than inspecting float bits itself:
29+
//!
30+
//! - Equality and grouping: normalize first ([`normalize_float`],
31+
//! [`normalize_floats`], [`normalize_float_scalar`]), then compare bits or
32+
//! call Arrow's `eq`, `RowConverter` or `make_comparator`. Hash
33+
//! [`hash_input`].
34+
//! - Ordering: use [`compare_floats`], [`float_lt`] or [`float_gt`]. Sorting
35+
//! does not normalize yet, so `-0.0` still sorts before `+0.0`.
36+
//!
37+
38+
use std::cmp::Ordering;
39+
use std::sync::Arc;
40+
41+
use arrow::array::{Array, ArrayRef, AsArray, make_array};
42+
use arrow::datatypes::{
43+
ArrowPrimitiveType, DataType, Float16Type, Float32Type, Float64Type,
44+
};
45+
use half::f16;
46+
47+
use crate::ScalarValue;
48+
49+
/// The floating point types the functions in this module are defined for:
50+
/// [`f16`](struct@f16), [`f32`] and [`f64`].
51+
pub trait FloatSemantics: Copy {
52+
/// Whether [`normalize_float`] would change this value. This is a cheap
53+
/// check that lets callers skip rewriting data which is already
54+
/// normalized.
55+
fn needs_normalization(self) -> bool;
56+
57+
/// See [`normalize_float`].
58+
fn normalize(self) -> Self;
59+
60+
/// See [`compare_floats`].
61+
fn compare(self, other: Self) -> Ordering;
62+
}
63+
64+
macro_rules! impl_float_semantics {
65+
($(($t:ty, $bits:ty, $zero:expr)),+ $(,)?) => {
66+
$(impl FloatSemantics for $t {
67+
#[inline]
68+
fn needs_normalization(self) -> bool {
69+
// `-0.0` has only the sign bit set; no other value shares
70+
// this bit pattern.
71+
self.to_bits() == 1 << (<$bits>::BITS - 1)
72+
}
73+
74+
#[inline]
75+
fn normalize(self) -> Self {
76+
if self.needs_normalization() { $zero } else { self }
77+
}
78+
79+
#[inline]
80+
fn compare(self, other: Self) -> Ordering {
81+
self.total_cmp(&other)
82+
}
83+
})+
84+
};
85+
}
86+
impl_float_semantics!((f16, u16, f16::ZERO), (f32, u32, 0.0), (f64, u64, 0.0));
87+
88+
/// `-0.0` becomes `0.0`, so two values that DataFusion treats as equal also
89+
/// have the same bits. All other values, including NaN payloads, are kept as
90+
/// they are.
91+
#[inline]
92+
pub fn normalize_float<T: FloatSemantics>(v: T) -> T {
93+
v.normalize()
94+
}
95+
96+
/// Compares two values in the order DataFusion sorts them.
97+
///
98+
/// This is IEEE 754 totalOrder (`total_cmp`), which matches Arrow's sort
99+
/// kernels and row encoding. Note that it orders `-0.0` before `+0.0`.
100+
/// The grouped `MIN`/`MAX` accumulators start from the extremes of this
101+
/// order, so they must change together with it.
102+
#[inline]
103+
pub fn compare_floats<T: FloatSemantics>(left: T, right: T) -> Ordering {
104+
left.compare(right)
105+
}
106+
107+
/// Whether `left` sorts before `right`, the same as
108+
/// `compare_floats(left, right).is_lt()`.
109+
#[inline]
110+
pub fn float_lt<T: FloatSemantics>(left: T, right: T) -> bool {
111+
compare_floats(left, right).is_lt()
112+
}
113+
114+
/// Whether `left` sorts after `right`, the same as
115+
/// `compare_floats(left, right).is_gt()`.
116+
#[inline]
117+
pub fn float_gt<T: FloatSemantics>(left: T, right: T) -> bool {
118+
compare_floats(left, right).is_gt()
119+
}
120+
121+
/// The value that DataFusion hashes in place of a float. Values that DataFusion
122+
/// treats as equal hash the same, so this is the value [`normalize_float`]
123+
/// returns.
124+
#[inline]
125+
pub fn hash_input<T: FloatSemantics>(v: T) -> T {
126+
normalize_float(v)
127+
}
128+
129+
/// Applies [`normalize_float`] to every float in `array`, including floats
130+
/// nested inside lists, structs, maps, unions, dictionaries and run-end
131+
/// encoded arrays. Arrays without floats are returned unchanged.
132+
///
133+
/// Callers use this before handing float data to Arrow kernels that compare
134+
/// bit patterns, so that `+0.0 = -0.0` holds.
135+
///
136+
/// The common case - nothing to normalize - is allocation-free: a single
137+
/// read-only scan of the values buffer (auto-vectorizable to an OR-reduction)
138+
/// decides whether to fall through to the rewriting path. Only arrays that
139+
/// contain values to normalize pay for a new buffer.
140+
pub fn normalize_floats(array: &ArrayRef) -> ArrayRef {
141+
match array.data_type() {
142+
DataType::Float16 => normalize_primitive::<Float16Type>(array),
143+
DataType::Float32 => normalize_primitive::<Float32Type>(array),
144+
DataType::Float64 => normalize_primitive::<Float64Type>(array),
145+
dt if has_float_leaf(dt) => {
146+
let data = array.to_data();
147+
let children = data
148+
.child_data()
149+
.iter()
150+
.map(|child| normalize_floats(&make_array(child.clone())).to_data())
151+
.collect::<Vec<_>>();
152+
if children
153+
.iter()
154+
.zip(data.child_data())
155+
.all(|(new, old)| new.ptr_eq(old))
156+
{
157+
return Arc::clone(array);
158+
}
159+
make_array(
160+
data.into_builder()
161+
.child_data(children)
162+
.build()
163+
.expect("rewriting float leaves preserves the array layout"),
164+
)
165+
}
166+
_ => Arc::clone(array),
167+
}
168+
}
169+
170+
fn normalize_primitive<T>(array: &ArrayRef) -> ArrayRef
171+
where
172+
T: ArrowPrimitiveType,
173+
T::Native: FloatSemantics,
174+
{
175+
let arr = array.as_primitive::<T>();
176+
if !arr.values().iter().any(|v| v.needs_normalization()) {
177+
return Arc::clone(array);
178+
}
179+
Arc::new(arr.unary::<_, T>(normalize_float))
180+
}
181+
182+
/// Applies [`normalize_float`] to a `Float16`, `Float32` or `Float64` scalar.
183+
/// Other scalars are returned as is.
184+
pub fn normalize_float_scalar(scalar: ScalarValue) -> ScalarValue {
185+
match scalar {
186+
ScalarValue::Float16(Some(v)) => ScalarValue::Float16(Some(normalize_float(v))),
187+
ScalarValue::Float32(Some(v)) => ScalarValue::Float32(Some(normalize_float(v))),
188+
ScalarValue::Float64(Some(v)) => ScalarValue::Float64(Some(normalize_float(v))),
189+
other => other,
190+
}
191+
}
192+
193+
/// Whether `data_type` is a float or contains a float at any depth of its
194+
/// nested children.
195+
pub fn has_float_leaf(data_type: &DataType) -> bool {
196+
match data_type {
197+
DataType::Float16 | DataType::Float32 | DataType::Float64 => true,
198+
DataType::List(f)
199+
| DataType::LargeList(f)
200+
| DataType::ListView(f)
201+
| DataType::LargeListView(f)
202+
| DataType::FixedSizeList(f, _)
203+
| DataType::Map(f, _)
204+
| DataType::RunEndEncoded(_, f) => has_float_leaf(f.data_type()),
205+
DataType::Struct(fields) => fields.iter().any(|f| has_float_leaf(f.data_type())),
206+
DataType::Union(fields, _) => {
207+
fields.iter().any(|(_, f)| has_float_leaf(f.data_type()))
208+
}
209+
DataType::Dictionary(_, values) => has_float_leaf(values),
210+
_ => false,
211+
}
212+
}
213+
214+
#[cfg(test)]
215+
mod tests {
216+
use super::*;
217+
use arrow::array::{Float16Array, Float32Array, Float64Array, Int32Array, ListArray};
218+
use arrow::datatypes::Int32Type;
219+
220+
#[test]
221+
fn normalize_float_folds_negative_zero() {
222+
assert_eq!(normalize_float(-0.0_f64).to_bits(), 0.0_f64.to_bits());
223+
assert_eq!(normalize_float(-0.0_f32).to_bits(), 0.0_f32.to_bits());
224+
assert_eq!(
225+
normalize_float(f16::NEG_ZERO).to_bits(),
226+
f16::ZERO.to_bits()
227+
);
228+
assert_eq!(
229+
hash_input(-0.0_f64).to_bits(),
230+
hash_input(0.0_f64).to_bits()
231+
);
232+
assert!((-0.0_f64).needs_normalization());
233+
assert!(!0.0_f64.needs_normalization());
234+
}
235+
236+
#[test]
237+
fn normalize_float_keeps_other_values() {
238+
let neg_nan = f64::from_bits(f64::NAN.to_bits() | (1 << 63));
239+
let payload_nan = f64::from_bits(f64::NAN.to_bits() | 1);
240+
for v in [
241+
1.5,
242+
-1.5,
243+
f64::INFINITY,
244+
f64::NEG_INFINITY,
245+
f64::MIN_POSITIVE,
246+
-f64::MIN_POSITIVE,
247+
f64::NAN,
248+
neg_nan,
249+
payload_nan,
250+
] {
251+
assert!(!v.needs_normalization());
252+
assert_eq!(normalize_float(v).to_bits(), v.to_bits());
253+
}
254+
}
255+
256+
#[test]
257+
fn compare_floats_is_total_order() {
258+
let neg_nan = f64::from_bits(f64::NAN.to_bits() | (1 << 63));
259+
assert_eq!(compare_floats(1.0_f64, 2.0), Ordering::Less);
260+
assert_eq!(compare_floats(-0.0_f64, 0.0), Ordering::Less);
261+
assert_eq!(compare_floats(f64::NAN, f64::INFINITY), Ordering::Greater);
262+
assert_eq!(compare_floats(neg_nan, f64::NEG_INFINITY), Ordering::Less);
263+
assert_eq!(compare_floats(f16::ONE, f16::ZERO), Ordering::Greater);
264+
assert!(float_lt(1.0_f64, 2.0) && !float_lt(2.0_f64, 1.0));
265+
assert!(float_gt(f64::NAN, f64::INFINITY) && !float_gt(1.0_f64, 1.0));
266+
}
267+
268+
#[test]
269+
fn normalize_floats_rewrites_negative_zero() {
270+
let array: ArrayRef =
271+
Arc::new(Float64Array::from(vec![Some(-0.0), None, Some(1.0)]));
272+
let result = normalize_floats(&array);
273+
let result = result.as_primitive::<Float64Type>();
274+
assert_eq!(result.value(0).to_bits(), 0.0_f64.to_bits());
275+
assert!(result.is_null(1));
276+
assert_eq!(result.value(2), 1.0);
277+
278+
let array: ArrayRef = Arc::new(Float32Array::from(vec![-0.0_f32]));
279+
let result = normalize_floats(&array);
280+
assert_eq!(
281+
result.as_primitive::<Float32Type>().value(0).to_bits(),
282+
0.0_f32.to_bits()
283+
);
284+
285+
let array: ArrayRef = Arc::new(Float16Array::from(vec![f16::NEG_ZERO]));
286+
let result = normalize_floats(&array);
287+
assert_eq!(
288+
result.as_primitive::<Float16Type>().value(0).to_bits(),
289+
f16::ZERO.to_bits()
290+
);
291+
}
292+
293+
#[test]
294+
fn normalize_floats_reuses_normalized_input() {
295+
let array: ArrayRef = Arc::new(Float64Array::from(vec![0.0, 1.0, f64::NAN]));
296+
assert!(Arc::ptr_eq(&normalize_floats(&array), &array));
297+
298+
let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2]));
299+
assert!(Arc::ptr_eq(&normalize_floats(&array), &array));
300+
}
301+
302+
#[test]
303+
fn normalize_floats_rewrites_nested_floats() {
304+
let list = ListArray::from_iter_primitive::<Float64Type, _, _>(vec![
305+
Some(vec![Some(-0.0), Some(2.0)]),
306+
None,
307+
]);
308+
let array: ArrayRef = Arc::new(list);
309+
let result = normalize_floats(&array);
310+
assert!(!Arc::ptr_eq(&result, &array));
311+
let values = result.as_list::<i32>().value(0);
312+
assert_eq!(
313+
values.as_primitive::<Float64Type>().value(0).to_bits(),
314+
0.0_f64.to_bits()
315+
);
316+
assert!(result.is_null(1));
317+
318+
let list =
319+
ListArray::from_iter_primitive::<Int32Type, _, _>(vec![Some(vec![Some(1)])]);
320+
let array: ArrayRef = Arc::new(list);
321+
assert!(Arc::ptr_eq(&normalize_floats(&array), &array));
322+
}
323+
324+
#[test]
325+
fn normalize_float_scalar_folds_negative_zero() {
326+
assert_eq!(
327+
normalize_float_scalar(ScalarValue::Float64(Some(-0.0))),
328+
ScalarValue::Float64(Some(0.0))
329+
);
330+
assert_eq!(
331+
normalize_float_scalar(ScalarValue::Float32(Some(-0.0))),
332+
ScalarValue::Float32(Some(0.0))
333+
);
334+
assert_eq!(
335+
normalize_float_scalar(ScalarValue::Float16(Some(f16::NEG_ZERO))),
336+
ScalarValue::Float16(Some(f16::ZERO))
337+
);
338+
assert_eq!(
339+
normalize_float_scalar(ScalarValue::Float64(None)),
340+
ScalarValue::Float64(None)
341+
);
342+
assert_eq!(
343+
normalize_float_scalar(ScalarValue::Int32(Some(0))),
344+
ScalarValue::Int32(Some(0))
345+
);
346+
}
347+
}

‎datafusion/common/src/hash_utils.rs‎

Lines changed: 7 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@ use crate::cast::{
8989
};
9090
use crate::error::Result;
9191
use crate::error::{_internal_datafusion_err, _internal_err};
92+
use crate::float_semantics::hash_input;
9293
#[cfg(not(feature = "force_hash_collisions"))]
9394
use crate::utils::offset_span;
9495
use std::cell::RefCell;
@@ -258,24 +259,20 @@ hash_value!(i8, i16, i32, i64, i128, i256, u8, u16, u32, u64, u128);
258259
hash_value!(bool, str, [u8], IntervalDayTime, IntervalMonthDayNano);
259260

260261
macro_rules! hash_float_value {
261-
($(($t:ty, $i:ty)),+) => {
262+
($($t:ty),+) => {
262263
$(impl HashValue for $t {
264+
// Hash the normalized bits so values SQL considers equal
265+
// (e.g. +0.0 and -0.0) hash the same.
263266
fn hash_one<S: BuildHasher>(&self, state: &S) -> u64 {
264-
// +0.0 and -0.0 differ only in the sign bit but compare equal
265-
// under IEEE 754; normalize -0.0 → +0.0 so Hash agrees with Eq.
266-
let bits = <$i>::from_ne_bytes(self.to_ne_bytes());
267-
let bits = if bits << 1 == 0 { 0 } else { bits };
268-
state.hash_one(bits)
267+
state.hash_one(hash_input(*self).to_bits())
269268
}
270269
fn hash_write(&self, hasher: &mut impl Hasher) {
271-
let bits = <$i>::from_ne_bytes(self.to_ne_bytes());
272-
let bits: $i = if bits << 1 == 0 { 0 } else { bits };
273-
hasher.write(&bits.to_ne_bytes())
270+
hasher.write(&hash_input(*self).to_bits().to_ne_bytes())
274271
}
275272
})+
276273
};
277274
}
278-
hash_float_value!((half::f16, u16), (f32, u32), (f64, u64));
275+
hash_float_value!(half::f16, f32, f64);
279276

280277
#[cfg(not(feature = "force_hash_collisions"))]
281278
trait ChildHashing {

0 commit comments

Comments
 (0)