ARROW-13642: [C++][Compute] Hash join node supporting all semi, anti, inner, outer join types #11150
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
4e40538 to
0daa18e
Compare
48e50b5 to
c0be8ea
Compare
09ef4be to
736b8cb
Compare
8f12cf2 to
3ad2360
Compare
d326701 to
1aa4a3c
Compare
1aa4a3c to
b9a5d14
Compare
jonkeane
added a commit
that referenced
this pull request
Sep 30, 2021
This is based on #11150. Among the issues observed: * Dictionary columns aren't allowed even in the left data, though you can first `Project` to remove them * Duplicate column names aren't allowed at all, even though there is a provision for deduping with a prefix Closes #11155 from nealrichardson/join-dplyr Lead-authored-by: Neal Richardson <neal.p.richardson@gmail.com> Co-authored-by: Jonathan Keane <jkeane@gmail.com> Signed-off-by: Jonathan Keane <jkeane@gmail.com>
ViniciusSouzaRoque
pushed a commit
to s1mbi0se/arrow
that referenced
this pull request
Oct 20, 2021
… inner, outer join types Hash join node implementation. Complete implementation of in-memory hash join, except for: - residual predicates (non-equality join conditions accompanying equality conditions in case of outer joins) - support for dictionary data types. This is a simple implementation that is not performance optimized. More advanced implementation (adding e.g. Bloom-like filters) will follow. Supports all 8 flavors of the join: left semi, left anti-semi, right semi, right anti-semi, inner, left outer, right outer and full outer join. Note that left semi join, for instance, is not the same as right semi join with inputs swapped. They have the same effect but the algorithm is different in both cases. Left semi join will filter out rows with no matches coming from left (first) child exec node. Right semi join will keep track of whether there was a match for each row for right (second) child exec node inserted into a hash table and output hash table rows with matches at the end. Supports the same keys as hash group by node, except for lack of support for dictionaries and strings with 64-bit offset. Supports choosing for each corresponding pair of key fields whether null should match null or not. Closes apache#11150 from michalursa/ARROW-13642-ref-imp Lead-authored-by: michalursa <michal@ursacomputing.com> Co-authored-by: niranda perera <niranda.perera@gmail.com> Signed-off-by: Jonathan Keane <jkeane@gmail.com>
ViniciusSouzaRoque
pushed a commit
to s1mbi0se/arrow
that referenced
this pull request
Oct 20, 2021
This is based on apache#11150. Among the issues observed: * Dictionary columns aren't allowed even in the left data, though you can first `Project` to remove them * Duplicate column names aren't allowed at all, even though there is a provision for deduping with a prefix Closes apache#11155 from nealrichardson/join-dplyr Lead-authored-by: Neal Richardson <neal.p.richardson@gmail.com> Co-authored-by: Jonathan Keane <jkeane@gmail.com> Signed-off-by: Jonathan Keane <jkeane@gmail.com>
This was referenced Oct 8, 2021
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Hash join node implementation.
Complete implementation of in-memory hash join, except for:
This is a simple implementation that is not performance optimized. More advanced implementation (adding e.g. Bloom-like filters) will follow.
Supports all 8 flavors of the join: left semi, left anti-semi, right semi, right anti-semi, inner, left outer, right outer and full outer join.
Note that left semi join, for instance, is not the same as right semi join with inputs swapped. They have the same effect but the algorithm is different in both cases.
Left semi join will filter out rows with no matches coming from left (first) child exec node.
Right semi join will keep track of whether there was a match for each row for right (second) child exec node inserted into a hash table and output hash table rows with matches at the end.
Supports the same keys as hash group by node, except for lack of support for dictionaries and strings with 64-bit offset.
Supports choosing for each corresponding pair of key fields whether null should match null or not.