andygrove opened a new issue, #26235:
URL: https://github.com/apache/datafusion/issues/26235
### Is your feature request related to a problem or challenge?
After #26228 (fixing #26226), `HashJoinExec` keeps build-side rows in input
order on both build paths (`ArrayMap` and `JoinHashMap`). For `LeftSemi`,
`LeftAnti` and `LeftMark`, every output row comes from the final visited-bitmap
emission. That emission walks the bitmap in build index order and runs in a
single stream (the last probe partition to finish), so the output already
follows the build side's order, in both `CollectLeft` and `Partitioned` mode.
The planner doesn't know this, because `maintains_input_order` only ever
reports the probe side:
```rust
fn maintains_input_order(join_type: JoinType) -> Vec<bool> {
vec![false, !need_produce_result_in_final(join_type)]
}
```
So the order is an implementation detail, protected only by the tests added
in #26228. Comet relies on it for null-aware anti joins (`NOT IN`), where
Spark's streamed side becomes DataFusion's build side, and currently restores a
sort above the native join instead (apache/datafusion-comet#6787,
apache/datafusion-comet#6810).
### Describe the solution you'd like
Report the build side as order-preserving for these join types:
```rust
vec![
matches!(join_type, JoinType::LeftSemi | JoinType::LeftAnti |
JoinType::LeftMark),
!need_produce_result_in_final(join_type),
]
```
`join_equivalence_properties` and `calculate_join_output_ordering` already
handle `[true, false]` for these join types by passing the left ordering
through. No right-side ordering is appended, so #25052 doesn't apply. This also
makes the property symmetric under `JoinSelection`'s input swap, since
`RightSemi` / `RightAnti` / `RightMark` already report probe-side order.
Things to test:
- A sort above a `LeftSemi` / `LeftAnti` / `LeftMark` hash join over a
sorted build side is removed, and multi-batch builds keep their order on both
map paths.
- Null-aware anti and mark joins keep the order. Their final-index
post-processing only filters rows, so it should hold.
- Plan diffs: with the left side order-preserving, `EnforceDistribution` /
`EnforceSorting` may choose differently under a `CollectLeft` build side, e.g.
an order-preserving merge instead of `CoalescePartitionsExec`.
Interactions with planned work:
- #22929 (emit `LeftSemi` output incrementally) would emit matched rows in
probe order, so `LeftSemi` would have to stop reporting build order if that
lands. If that's likely, starting with `LeftAnti` and `LeftMark` avoids the
conflict, since neither can emit anything before the probe side is exhausted.
- #24768 (spilling hash join) emits unmatched build rows per bucket once
something spills, so the property would need to be dropped under
`enable_hash_join_spilling`, the same way that epic already plans to drop the
probe-side property.
### Describe alternatives you've considered
Document the build-side order on `HashJoinExec` without reporting it to the
planner. Embedders would get a documented contract, but DataFusion couldn't use
it to remove sorts.
### Additional context
- #26226 / #26228: makes the build-side order independent of which map the
build uses
- apache/datafusion-comet#6787, apache/datafusion-comet#6810
--
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]
