Repository navigation
Description
Describe the bug
SortMergeJoinExec misses rows when a nested float join key (a list or struct) contains -0.0 and another element follows it.
DataFusion compares -0.0 and +0.0 as equal, inside nested values too: compare_op_for_nested and JoinKeyComparator normalize -0.0 before comparing. Sorting does not normalize. Arrow's sort uses IEEE total order, so -0.0 < +0.0.
For a flat float key that is harmless, because the two zeros only end up next to each other. For a nested key it changes the order, because the comparison then moves on to the next element:
- sorted:
[-0.0, 1.0]<[0.0, 0.0](decided by-0.0 < +0.0) - compared:
[-0.0, 1.0]>[0.0, 0.0](first elements equal, then1.0 > 0.0)
A join that sorts its inputs and then merges them with the normalizing comparator therefore reads inputs that are not sorted in the order it compares in, and misses matches.
To Reproduce
CREATE TABLE fa AS SELECT * FROM (VALUES
(1, make_array(arrow_cast(-0.0, 'Float64'), 1.0)),
(2, make_array(0.0, 0.0)),
(3, make_array(0.0, 1.0))) t(id, k);
CREATE TABLE fb AS SELECT * FROM (VALUES
(10, make_array(0.0, 1.0)),
(11, make_array(0.0, 0.0))) t(id, k);
-- SortMergeJoinExec
SET datafusion.optimizer.prefer_hash_join = false;
SELECT fa.id, fb.id FROM fa JOIN fb ON fa.k = fb.k;
-- 1 10
-- 3 10 <- (2, 11) is missing
-- HashJoinExec
SET datafusion.optimizer.prefer_hash_join = true;
SELECT fa.id, fb.id FROM fa JOIN fb ON fa.k = fb.k;
-- 1 10
-- 2 11
-- 3 10PiecewiseMergeJoinExec (with datafusion.optimizer.enable_piecewise_merge_join = true) has the same problem for range predicates on such keys, in the join types that sort their inputs (Inner/Left/Right/Full, LeftSemi/LeftAnti/LeftMark).
Expected behavior
Sort-based joins return the same rows as HashJoinExec / NestedLoopJoinExec: (1, 10), (2, 11), (3, 10) above.
Additional context
- The nested case in
negative_zero.sltjoins one-element lists ([0.0],[-0.0]), where the two orders agree, so it doesn't catch this. - Window PARTITION BY puts 0.0 and -0.0 in separate partitions #25766 is the same mismatch in window
PARTITION BY: partition boundaries are found with total order, while the rest of the engine treats-0.0and0.0as equal. - Possible directions: sort by the
-0.0-normalized key wherever a sort feeds a normalizing comparator, or don't plan sort-based joins for nested keys that contain float fields.
Activity