NVIDIA / NVIDIA/cudf

[FEA] Support per-key null equality in libcudf joins

Open
#23,481 1 comment 1 reaction 0 assignees View on GitHub
feature request
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.

libcudf join APIs accept a single `null_equality compare_nulls` value for all equality-key columns. SQL joins can assign different null semantics to individual keys:

```sql
SELECT ...
FROM a JOIN b
ON a.x = b.x
AND a.y IS NOT DISTINCT FROM b.y;
```

These predicates require different semantics:

- `a.x = b.x`: NULL must not match NULL (`UNEQUAL`).
- `a.y IS NOT DISTINCT FROM b.y`: NULL must match NULL (`EQUAL`).

No operation-wide value represents both semantics when both columns participate in the equality key:

- `EQUAL` can incorrectly match rows whose `x` values are both NULL.
- `UNEQUAL` incorrectly rejects rows whose `y` values are both NULL.

This can be expressed with `mixed_*_join` by hashing only `x` with `UNEQUAL` and evaluating `y` through an AST `NULL_EQUAL` predicate. That is correct, but `y` no longer participates in hash candidate selection. If `x` has low cardinality, this can substantially increase candidate multiplicity and predicate-evaluation cost.

### Describe the solution you'd like

Allow `null_equality` to be specified independently for each top-level equality-key column. For example:

```cpp
host_span compare_nulls; // {UNEQUAL, EQUAL}
```

The span length would equal the number of equality-key columns, with each entry applying to the corresponding left/right key pair.

The existing scalar overload could remain as a convenience and backward-compatible shorthand that broadcasts one policy to every key.

Ideally, per-key policies would be supported consistently by libcudf join APIs that currently accept an operation-wide `null_equality`, including:

- hash_join and the inner_join / left_join / full_join free functions
- mixed_*_join, including mixed semi/anti joins and corresponding size APIs
- sort_merge_join
- distinct_hash_join
- filtered_join and its semi/anti probe operations
- mark_join

The exact API representation and initial implementation scope are open to discussion.

### Describe alternatives you've considered

- **Use `mixed_*_join`**: keep ordinary equality columns in the hash key and move null-safe columns into an AST `NULL_EQUAL` predicate. This is correct, but may generate many more candidate pairs because the null-safe columns do not participate in hashing.
- **Join with `EQUAL` and post-filter** rows containing NULLs in ordinary equality keys. This requires extra passes and intermediate materialization. For outer, semi, and anti joins, Filtering invalid matches must also restore rows that should be treated as unmatched.
- **Split the operation into multiple joins**, then combine their outputs.

### Related issues

- [#5637](https://github.com/rapidsai/cudf/pull/5637) introduced the current operation-wide `null_equality` parameter for joins.
- [#7934](https://github.com/rapidsai/cudf/issues/7934) describes a related lack of a universal null policy when join keys combine nullable struct components and primitive columns. This request focuses on independently configurable semantics for top-level equality keys.

Contributor guide

Open the contributing guide

Research direction

Start by surveying the join APIs named in the issue: hash_join, inner_join, left_join, full_join, mixed_*_join, sort_merge_join, distinct_hash_join, filtered_join, and mark_join. Compare their current operation-wide null_equality interfaces and determine an agreed initial scope and per-key representation. Done means the selected APIs consistently support independent policies while retaining the scalar shorthand where specified.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.