dwsmith1983 opened a new issue, #26226: URL: https://github.com/apache/datafusion/issues/26226
### Describe the bug On the hash map build path, `HashJoinExec` concatenates the build batches in reverse batch order. Rows keep their order inside each batch, but whole batches come out last to first. - Any build-side row emitted in index order (for example an anti or semi join's unmatched build rows in `CollectLeft` mode) loses the build side's input order across batches. - The array map (perfect hash) path concatenates forward and keeps the order. That path is skipped only when keys are sparse: `range >= perfect_hash_join_small_build_threshold` (1024) and `density <= perfect_hash_join_min_key_density` (0.15). So whether the output keeps input order depends on the key distribution. #### Why it's reversed `JoinHashMap` chains are LIFO. To keep a key's earlier rows on top of its chain, `update_hash` runs over the batches last to first, and offsets are assigned in that same order. The concatenated batch then has to be reversed too so the indices line up. The doc comment above `HashJoinExec` explains this with a 3-batch diagram. ### To Reproduce A `LeftAnti` `HashJoinExec` in `CollectLeft` mode, with two build batches (keys `[10, 20]` and `[3000, 4000]`) and a probe side that matches none of them, returns `[3000, 4000, 10, 20]`. ### Expected behavior `[10, 20, 3000, 4000]`, the build side's input order, regardless of which map the build uses. ### Proposed fix Suggested by @andygrove in https://github.com/apache/datafusion-comet/pull/6810#discussion_r4248180112: 1. Keep inserting batches last to first, so the per-key chain order is unchanged. 2. Give each batch the offset of its start position in forward order: batch `k` gets the total row count of batches `0..k`. 3. Concatenate forward. This preserves both the chain order and the input order, and the result no longer depends on which path the build takes. Tests to add: the repro above asserting `[10, 20, 3000, 4000]`, and a variant with duplicate keys across batches for an inner join, checking that matches still come back in build order. ### Additional context Code on main (6663e43): - `update_hash` over `batches.iter().rev()` and `concat_build_batches(..., true, ...)`: https://github.com/apache/datafusion/blob/6663e4348049cc7b70109c9e0f8e39049794ea23/datafusion/physical-plan/src/joins/hash_join/exec.rs#L3383-L3412 - The `reverse` flag in `concat_build_batches`: https://github.com/apache/datafusion/blob/6663e4348049cc7b70109c9e0f8e39049794ea23/datafusion/physical-plan/src/joins/hash_join/exec.rs#L3180-L3184 - Doc comment and diagram: https://github.com/apache/datafusion/blob/6663e4348049cc7b70109c9e0f8e39049794ea23/datafusion/physical-plan/src/joins/hash_join/exec.rs#L860-L895 The same code in 55.2.0 (500744d), the version Comet pins: - Build loop and reverse concat: https://github.com/apache/datafusion/blob/500744d5c25499055e3b2ca46b022bc425989203/datafusion/physical-plan/src/joins/hash_join/exec.rs#L2342-L2365 - Array map skip rule: https://github.com/apache/datafusion/blob/500744d5c25499055e3b2ca46b022bc425989203/datafusion/physical-plan/src/joins/hash_join/exec.rs#L176-L180 How Comet hits it: Comet runs a null-aware anti join (`NOT IN`) unswapped in `CollectLeft` mode, so Spark's streamed side becomes DataFusion's build side. With sparse keys and more than one build batch, the output comes out in reverse batch order. Spark has already removed the sort above the join because the join reports the streamed side's order, so `sortWithinPartitions` / `SORT BY` above it can return unsorted partitions. - Comet issue: https://github.com/apache/datafusion-comet/issues/6787 - https://github.com/apache/datafusion-comet/pull/6810 restores the sort above the native join - https://github.com/apache/datafusion-comet/pull/6835 covers the outer join shapes -- 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]
