Visitar URL original
SortMergeJoin misses rows for nested float keys containing -0.0 · Issue #26115 · apache/datafusion · GitHub
Skip to content

SortMergeJoin misses rows for nested float keys containing -0.0 #26115

Description

@jayzhan211

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, then 1.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 10

PiecewiseMergeJoinExec (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.slt joins 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.0 and 0.0 as 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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions