NVIDIA / NVIDIA/cudf

[FEA] sort_merge_join is sensitive to left and right table size

Open
#20,375 1 comment 0 reactions 0 assignees View on GitHub
feature request libcudf Performance
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.**
I have been testing the inner sort_merge_join implementation and I found that sort merge join prefers to have the left table be smaller than the right table. This is similar to the hash join, where a smaller build table is preferred.

This is most noticeable on keys like ints, but it can still show up on complex types like string. It also is most clear when there are lots of distinct keys in the tables. I think this is related to the cost of finding the upper and lower bounds for the various keys, but I have not profiled it yet.

Image

This is from a benchmark that I can where I targeted 10,000,000 output rows with 1,000,000 distinct key values. I varied the number of rows of the left and right hand side and the explosion factor to get the desired 10 million output rows (note that this is the sum of 60 runs). The important thing to note is that the left most entry and the right most entry are for the same tables, just left and right are switched.

**Describe the solution you'd like**
Ideally the join performance would be symmetrical but it is far from this. Even on a string key I can see the skew in the numbers, but because the sort takes so long it is not as critical.

It would be nice to at least document this, or have a built in heuristic to switch automatically for inner join, like happens on some hash join APIs. For this particular case the performance difference was between 1.3x slower to 12.6x slower.

**Describe alternatives you've considered**
I can do it myself, but I wanted to document it.

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.