apache / apache/datafusion

CrossJoin Implementation on (M x N) Partitions

Open
#9,941 3 comments 0 reactions 0 assignees View on GitHub
enhancement
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.