neilconway opened a new pull request, #22957:
URL: https://github.com/apache/datafusion/pull/22957
## Which issue does this PR close?
- Closes #22931
## Rationale for this change
To evaluate a semi join, we support two orientations: `LeftSemi` or
`RightSemi` (analogously for anti and mark joins; I'll just refer to semijoins
here to simplify the discussion). Under `RightSemi`, we build the non-preserved
("filter") input and stream the preserved input; we do the inverse for
`LeftSemi`. There are significant differences in evaluation behavior between
these two orientations:
* The build-side hash table has to be resident in memory; all else being
equal, building the smaller join input is a good general rule, and that's the
main rule we follow today.
* `RightSemi` only needs to store the join keys for the build side;
`LeftSemi` needs to store wider rows. By definition, the consumer of a semijoin
can't be interested in any values from the filter side of the join. So even if
the filter side has more rows than the preserved side, building the hash table
on the filter side might still require less memory.
* `RightSemi` preserves the partitioning of the preserved input, whereas
`LeftSemi` + `CollectLeft` emits with `UnknownPartitioning`.
* `RightSemi` works better with dynamic filter pushdown: I don't know the
dynamic filter code super well, but I'd imagine that since `RightSemi` builds
the filter side before streaming the preserved side, that gives us more
information we can use to push down filters into the preserved-side scan.
The current optimizer rules don't reflect this:
* `LeftSemi` and `RightSemi` are considered symmetrically; whichever
semijoin input is predicted to be smaller is placed on the build side
* If there are absent stats, `LeftSemi` is the default orientation
This PR revises these rules as follows:
* Prefer `RightSemi` over `LeftSemi`, _unless_ the filter side is twice as
large as the preserved side (configurable via `semi_join_swap_bias`
configuration variable)
* If there are absent stats, prefer `RightSemi`
## What changes are included in this PR?
* Add `semi_join_swap_bias` configuration variable
* Refactor code to use a single routine when considering when to swap hash
join inputs
* Apply configured bias to HJ swap input decision
* Add unit tests
* Update expected plans in SLT
## Are these changes tested?
Yes.
## Are there any user-facing changes?
Changes in plans for user queries.
--
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]
