Repository navigation
refactor the code of the HashJoin #4356
Description
Is your feature request related to a problem or challenge? Please describe what you are trying to do.
A clear and concise description of what the problem is. Ex. I'm always frustrated when [...]
(This section helps Arrow developers understand the context and why for this feature, in addition to the what)
From the bug #4247, there are bugs for hash join for right semi/anti join.
The current code base has many match path for each Join_type, each join_type has different logic and path, it easy to produce the bugs when we add feature in the HashJoin.
Proposal:
split vectorization HashJoin to three phase:
- get the result of matched equal join : left_idx and right_idx
- apply non_equal filter to
left_idx and right_idxand get the filter_left_idx with filter_right_idx - according to the
Join Typeto construct the result
according to the matched `filter_left_idx` and `filter_right_idx` to get the result
match join_type{
inner_join:
left_join:
right_join:
full_join:
left_semi: set the left bitmap
left_anti: set the left bitmap
right_semi: set the right bitmap, and get the result from the right bitmap(set_bit)
right_anti:: set the right bitmap, and get the result from the right bitmap(not_set_bit)
}
Describe the solution you'd like
A clear and concise description of what you want to happen.
Describe alternatives you've considered
A clear and concise description of any alternative solutions or features you've considered.
Additional context
Add any other context or screenshots about the feature request here.
Activity
liukun4515 commentedon Nov 24, 2022
After this merged #4355, I will start this task
xudong963 commentedon Nov 24, 2022
Yes, I agree.
For HashJoin, there are two big phases: build and probe:
matchpaths at the beginning of probe phaseDandandan commentedon Nov 24, 2022
Thanks @liukun4515 for driving the effort to improve the hash join implementation! Makes sense to me to structure it this way. This will help make it easier to change/improve the implementation later on.
liukun4515 commentedon Nov 25, 2022
Probe phase has many common stage.
In the vectorization has join, the first stage is to get the left/right indices which are match the on join condition.
Next, use the left/right indices to generate the batch result according to the join type. But some special join type should maintain the left side bitmap to generate the result finally, for example left/full/leftanti/leftsemi.