CrossJoin Implementation on (M x N) Partitions
- 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?
There is a TODO item in CrossJoin: https://github.com/apache/arrow-datafusion/blob/2f550032140d42d1ee6d8ed86f7790766fa7302e/datafusion/physical-plan/src/joins/cross_join.rs#L122
Currently CrossJoin partition count is the partition count of the right child. We can increase parallelism here if allowed.
### Describe the solution you'd like
Let's say left has M and right has N partitions, and the target partition is T. We can increase the parallelism by getting the left partitions count to floor[T/N] (assuming T is not smaller than N). If (M x N) is smaller or equal than T, there would be no need to coalesce left partitions also.
### Describe alternatives you've considered
-
### Additional context
Theoretically, for example, 1x8 partitions of joins does the same amount of unit work with 2x4, but in practice, 2x4 parallelism may be more preferable (I have no solid evidence). So, without changing the target partitions, such kind of parallelism adjustment also be done if it is proved that it works better.
Contributor guide
Research direction
Start at datafusion/physical-plan/src/joins/cross_join.rs around line 122 and inspect how CrossJoin derives its partition count from the right child. Work through the M×N partitioning proposal, including the cases where T is smaller or larger than N. Done means the implementation increases parallelism without changing the target partition behavior described in the issue, with validation for the relevant partition-count cases.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- distributed-systems, performance
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100