apache / apache/datafusion

Implement Radix Hash Join

Open
#18,939 10 comments 0 reactions 0 assignees View on GitHub
enhancement performance
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:

Image

https://15721.courses.cs.cmu.edu/spring2016/papers/balkesen-icde2013.pdf

### Describe alternatives you've considered

_No response_

### Additional context

_No response_

Contributor guide

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.