NVIDIA / NVIDIA/cudf

[FEA] Improve performance of high-multiplicity joins

Open
#16,025 6 comments 0 reactions 0 assignees View on GitHub
feature request libcudf
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**
![image](https://github.com/rapidsai/cudf/assets/12725111/eb8a4d94-1cb3-404e-98d0-ae6c86fa6ffb)
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.