Implement Radix Hash Join
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
Hash Joins with large build side & lots of hash-duplicates are relatively slow in DataFusion.
The cost seems largely associated with traversing the chain of duplicates (`chain_traverse`) (1) + which is known to be very cache-inefficient, as the access pattern is mostly random.
Currently, we implement hash joins partitioned by hash, but we can implement a more efficient algorithm (radix hash join) that splits build data into smaller tables that individually mostly fits in CPU caches and allow more efficient access patterns.
_[TODO: collect some issues / examples]_
(1) https://github.com/apache/datafusion/issues/17494
### Describe the solution you'd like
Implement a version of Radix Hash Joins:
https://15721.courses.cs.cmu.edu/spring2016/papers/balkesen-icde2013.pdf
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
Contributor guide
Research direction
Start with issue #17494 and the linked Radix Hash Join paper, then locate DataFusion's current hash-join implementation and its chain_traverse path. Define the radix partitioning approach and collect representative large-build, duplicate-heavy examples before implementation; done means radix joins are implemented and their performance improves for that workload.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100