[FEA] Improve performance of high-multiplicity joins
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.1k
- Avg merge
- 3d 6m
- Merged PRs (30d)
- 278
Description
**Is your feature request related to a problem? Please describe.**
When the smaller table in a hash inner join has low cardinality and high multiplicity (many duplicate values), we observe degradation in data processing throughput.
**Describe the solution you'd like**
For build tables with >1-10K duplicate values, we might benefit from an alternate hash join implementation that doesn't have to manage so many hash collisions.
**Additional context**

We observe 5-50 GB/s throughput when multiplicity is =<1000, and throughput drops down to 65 MB/s when the build table has 1M duplicates of the same value.
Here is a script to set up the tables for this demonstration.
```
for cardinality in [100_000, 10_000, 1000, 100,10,5,2,1]:
left_rows = 10_000_000
df_left = cudf.DataFrame({
'key': cupy.arange(left_rows),
'payload_l': cupy.random.rand(left_rows),
})
right_rows = 1_000_000
df_right = cudf.DataFrame({
'key': cupy.arange(right_rows) % cardinality,
'payload_r': cupy.random.rand(right_rows),
})
t0 = time.time()
df = df_left.merge(df_right, on='key', how='inner')
t1 = time.time()
```
Please see https://github.com/NVIDIA/spark-rapids/issues/7529 for the Spark-RAPIDS study that identified this issue.
Contributor guide
Assessment
This issue has not been assessed yet.