NVIDIA / NVIDIA/cudf

[FEA] Add a perfect hash join API to libcudf

Open
#23,126 0 comments 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.**

Hash joins in libcudf always pay for hashing, probing, and key comparisons, even when the join keys are known to be collision free (dense integer primary keys, dictionary indices, or IDs produced by `cudf::key_remapping`). In those cases the matched row index can be computed directly from the key value, with no hash table build or probe. libcudf cannot detect this itself since it does not introspect data, but downstream engines (Spark, Velox, GQE) have the metadata (PK/FK constraints, dictionary encoding, a prior `key_remapping` pass) to know when it applies.

**Describe the solution you'd like**

Following the `distinct_hash_join` model, add a `perfect_hash_join` API where the caller guarantees the preconditions: the provided hash (or identity mapping for dense integer keys) is collision free over the right table's keys, and the maximum hash value (i.e. the table capacity) is within an acceptable range. Behavior is undefined otherwise.

A minimal first version:
- integer keys only (or keys pre-mapped via `cudf::key_remapping`)
- no nulls, no duplicates on the right table
- `inner_join` only, with `left_join` as a follow-up
- an explicit capacity argument so the caller controls the memory footprint

**Describe alternatives you've considered**

- `distinct_hash_join`: exploits right-table uniqueness but still builds and probes a hash table.
- `cudf::key_remapping`: effectively a form of perfect hashing (complex keys to dense integer IDs, plus `get_distinct_count()` for strategy selection), and a natural front end for `perfect_hash_join`, but the resulting IDs still go through a regular join today.
- Engine-side gather kernels: bypass libcudf's null handling and join semantics, and duplicate work across engines.

**Additional context**

Requested during a perfect hashing discussion with query engine teams. GQE measured meaningful TPC-H speedups from enabling perfect hashing for joins. Capacity is a real concern at large scale factors (e.g. a dense table on `o_orderkey` at SF10K), hence the explicit capacity bound. Feedback from Velox and GQE on naming and interface is welcome.

Also there is related work in https://github.com/rapidsai/cudf/pull/21041 which explores replacing the mapping step in `key_remapping` with a dictionary encode step. For non-nested types we could probably replace the mapping step with dictionary encode, plus computing "max" on the values column.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing distinct_hash_join and key_remapping APIs, including how inner_join currently handles integer keys, nulls, and right-side duplicates. Define the minimal perfect_hash_join interface around the caller-provided capacity and collision-free mapping, then verify that the inner-join behavior and documented preconditions match the issue; left_join is explicitly follow-up work.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend-api-design, data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.