jayzhan211 opened a new issue, #26138:
URL: https://github.com/apache/datafusion/issues/26138
### Is your feature request related to a problem or challenge?
#22835 made `-0.0` and `+0.0` compare equal, as PostgreSQL, DuckDB and Spark
do. It works by rewriting `-0.0` to `+0.0` (`normalize_float_zero`) before
calling Arrow kernels, at selected call sites. Arrow's kernels compare floats
by bit pattern and IEEE total order. So every call site that doesn't rewrite
first still treats the two zeros as different values.
Since then, fixes have arrived one call site at a time:
- Merged: #24432, #24431, #25133, #25300, #25972.
- Open: #25186 and #25912 (IN list), #25766 and #26020 (window `PARTITION
BY`), #24375 (ASOF keys), #26115 (sort-merge joins on nested keys), #25981 and
#25913 (datafusion-spark).
- #26091 proposes the same treatment for NaN.
#25300, #25972 and #25912 only make the repeated rewriting cheaper. #26020
and #24375 each add their own `NormalizeFloatZeroExpr` with a protobuf message.
The question came up on #22835 itself ("how we'll enforce/ensure we remember to
apply this normalization each time"), and the `array_replace` case raised there
is still wrong. datafusion-comet hit the same pattern with Spark semantics and
is fixing it systematically in apache/datafusion-comet#6385.
These still give wrong results on main (95a1961cc). Here `z` is
`arrow_cast(-0.0, 'Float64')`:
| Query | DataFusion | Expected (`-0.0 = 0.0`) |
|---|---|---|
| `ORDER BY a, b` over `(z, 1), (0.0, 0)` | `(-0.0, 1), (0.0, 0)` | `(0.0,
0), (-0.0, 1)` |
| the same with `LIMIT 1` | `(-0.0, 1)` | `(0.0, 0)` |
| `rank() OVER (ORDER BY a)` over `z, 0.0` | 1, 2 | 1, 1 |
| `sum(b) OVER (ORDER BY a RANGE BETWEEN CURRENT ROW AND CURRENT ROW)` over
`(z, 1), (0.0, 2)` | 1, 2 | 3, 3 |
| `row_number() OVER (PARTITION BY a)` over `z, 0.0` (#25766) | 1, 1 | 1, 2 |
| `first_value(b ORDER BY a, b)` over `(z, 1), (0.0, 0)` | 1 | 0 |
| `DISTINCT ON (g) g, b ... ORDER BY g, a, b` over `(1, z, 1), (1, 0.0, 0)`
| b = 1 | b = 0 |
| `ORDER BY k` over `k = [z, 1.0]`, `[0.0, 0.0]` | `[-0.0, 1.0]` first |
`[0.0, 0.0]` first |
| `min(k)`, `max(k)` over the same lists | `[-0.0, 1.0]`, `[0.0, 0.0]` |
`[0.0, 0.0]`, `[-0.0, 1.0]` |
| `z IN (0.0, 1.0)` | true for Float64, false for Float32 | true |
| `z IN (0.0, 1.0, ..., 25.0)` (26 values) | false | true |
| `array_has(make_array(z), 0.0)`, also `array_has_any` and `array_has_all`
| false | true |
| `array_position(make_array(z, 1.0), 0.0)` | NULL | 1 |
| `nullif(z, 0.0)` | -0.0 | NULL |
| `CASE z WHEN 0.0 THEN 'eq' ELSE 'ne' END` | ne | eq |
`=`, `<`, GROUP BY, DISTINCT, `count(DISTINCT)`, set operations and hash
joins are already right.
There are two reasons the per-site fixes don't converge:
1. Nothing marks which call sites need the rewrite. Roughly 60 non-test call
sites use Arrow's compare, sort, row-format or partition kernels: 21
`RowConverter::new`, 11 sort or lexsort, 9 `make_comparator`, 4
`evaluate_partition_ranges` callers, and 15 files that use the `cmp` kernels.
About 15 of them rewrite first. Other code compares floats by hand:
- `compare_rows` and `ScalarValue::partial_cmp`, which drive RANGE
frames, `first_value(... ORDER BY)` and nested `min`/`max`
- the IN list's bitwise `OrderedFloat64` wrapper
- `.is_eq` fast paths such as the one in `array_has`
The IN list above even disagrees with itself, depending on list length
and float width.
2. Equality was fixed, but ordering was not. Sorting still uses total order,
where `-0.0 < +0.0`.
- For a single flat key this is harmless, because the two zeros end up
next to each other.
- For multi-column, list and struct keys it is not. A tie on the first
value should defer to the next one, but total order decides on the first value.
- Other operators consume the sort order: sort-merge join, merge, window
partition boundaries, rank peers. So it can't be fixed inside one operator.
#26020 ran into exactly this.
### Describe the solution you'd like
Map each float to one representative of its SQL value: `-0.0` → `+0.0`, and,
if #26091 is accepted, every NaN → the canonical NaN. On those values, Arrow's
bit equality is SQL equality and Arrow's total order is SQL order. This holds
for lists and structs too, because they compare element by element. The
canonical NaN already sorts last, where PostgreSQL, DuckDB and Spark put it.
So no kernel needs SQL-specific code. One rule is enough: never compare,
sort, hash or partition floats that haven't been mapped this way. I propose two
parts:
1. **One module.** A small module, for example `datafusion_common::key`,
owns SQL float semantics. It provides:
- The mapping for arrays, scalars, and the float bits that
`create_hashes` uses. The array version is today's `normalize_float_zero`,
which already handles nested types and dictionaries.
- Thin wrappers with Arrow's signatures: `eq`/`distinct`/...,
`make_comparator`, `sort_to_indices`, `lexsort_to_indices`, and a
`RowConverter` wrapper.
- SQL-order comparison for scalars and native values. The DataFusion
helpers that compare by hand today would use it: `compare_rows`,
`compare_with_eq`, `evaluate_partition_ranges`, nested `min`/`max`, the IN list
filters and the `array_*` fast paths.
Operators map their join, group, sort and partition keys once, when they
evaluate them. Everything derived from those arrays is then already mapped:
rows, hashes, scalars kept across batches. Long-lived arrays, such as a hash
join's build side, are scanned once.
Inside the module, each operation can either map the values and then call
Arrow, or compare in SQL order directly. Mapping first is simple and works for
nested types and row encoding. Comparing directly is faster for flat
comparisons; #11585 suggested this and apache/datafusion-comet#6590 does it.
Call sites don't change either way.
2. **One differential test.** Run special floats through operators that must
agree. The inputs are ±0, NaN variants, ±inf and nested values, built with the
generators from #24433. The test compares:
- hash vs sort-merge vs nested-loop joins
- hash vs sorted aggregation
- window partitions vs GROUP BY counts
- ORDER BY vs a reference sort
- each function vs `=`
This catches the next regression no matter which code path it comes from.
A sweep like this is also what made apache/datafusion-comet#6385 converge.
Optionally, add a lint at the end. Putting the raw Arrow kernels in
`disallowed-methods` in `clippy.toml` (as is already done for `tokio::spawn` →
`SpawnedTask`) stops new code from calling them directly. It only sees direct
kernel calls, though: 8 of the 15 rows above go through one. RANGE frames,
`first_value`/`DISTINCT ON`, nested `min`/`max`, the IN list and `array_has`'s
fast path compare by hand, and banning `is_eq`/`total_cmp` by name would mostly
flag integer and bit-identity code. So the lint protects new code; it isn't how
existing bugs get found.
What stays bit-level:
- `ScalarValue` `Eq`/`Hash`/`Ord`. This is expression identity: the
optimizer must not merge `lit(-0.0)` with `lit(0.0)`, because `1 / x` differs.
This is also why #24431 kept bit equality.
- The values themselves. `-0.0` still prints as `-0.0`, and arithmetic
doesn't change.
- `min`/`max`/`greatest`/`least`, which pick a value. They use SQL order
with total order as the tie-break, which keeps the determinism from #24432.
User-visible change: `ORDER BY a` treats `-0.0` and `0.0` as ties, as
PostgreSQL does. GROUP BY keeps returning `0.0`.
Possible steps, each useful on its own:
- [ ] Add the module and the differential test, and route the sort path
through the module: sort, merge, TopK, partial sort, PWMJ. This closes #26115
and fixes multi-column ORDER BY, TopK, list ORDER BY and `array_sort`.
- [ ] Move the #22835 call sites onto the module. This is a refactor with no
behavior change.
- [ ] Window and row comparisons: `evaluate_partition_ranges` and
`compare_rows`. This closes #25766 and fixes rank and RANGE frames. Together
with the first step, it also fixes `first_value(... ORDER BY)` and `DISTINCT
ON`.
- [ ] Expression-level equality: IN list, CASE, `nullif`, the `array_*`
functions, `min`/`max` on nested values.
- [ ] NaN, if #26091 is accepted: change the mapping function and nothing
else.
- [ ] Optional: the clippy lint.
### Describe alternatives you've considered
- **Keep fixing call sites.** The list above shows this doesn't converge.
Each new operator (ASOF, PWMJ, IN-list filters) runs into it again.
- **Remove `-0.0` where it is produced** (scans, arithmetic). `-0.0` is
observable (`1 / -0.0`, display, #25702), so this would change results.
- **Wrap key expressions in the plan.** Spark's `NormalizeFloatingNumbers`
does this, and #26020 and #24375 do it per operator.
- Spark needs it only for its binary row comparisons, because its
comparator already treats `-0.0 = 0.0`.
- In DataFusion every Arrow kernel compares bits, so every float sort key
would need wrapping too. That changes how the optimizer matches orderings and
hash partitioning (`a` vs `normalize(a)`).
- It still misses expression-level equality (IN, CASE, `array_*`).
- If we prefer this direction anyway, it should be one rule for all key
positions, not one expression per operator.
- **An arrow-rs option to normalize floats inside the row format and sort
kernels.** This would be a later optimization that saves one pass. It isn't
needed for correctness.
### Additional context
- **Cost.**
- Nothing for non-float keys.
- Comet measured the mapping per batch of 8192 doubles on an M3 Max
(apache/datafusion-comet#6590):
- Copying mapped values: 1.71 µs.
- A branch-free "anything to map?" check: 1.3–1.7 µs.
- An early-exit `any()`, which `normalize_float_zero` uses today: 4.4
µs, because it does not vectorize.
- The comparison itself: 3.8–6.8 µs.
- So for a flat comparison, mapping is a large share of the cost, and
comparing in SQL order directly is better.
- For sort, join and window, where a batch costs hundreds of µs, mapping
once per key column per batch is around 1%. The first step should come with a
sort/TopK benchmark on float keys.
- **Why Arrow uses total order.** apache/arrow-rs#2568 asked for
SQL-compliant float kernels. It settled on `total_cmp` because it sorts NaN
last, but that ignores sign-bit NaNs and `±0`. apache/arrow-rs#3509 then made
`make_comparator` treat `±0` as distinct, to match. So SQL float semantics
belong in DataFusion, not in Arrow.
- It would help to agree on a direction before #26020 and #24375 merge,
because both add a protobuf message for an expression this design doesn't need.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
