NVIDIA / NVIDIA/cudf

[FEA] Rewrite mixed join internals using normal join + pre/post-filtering

Open
#22,124 1 comment 2 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.**

The `mixed_*_join` family of APIs (`mixed_inner_join`, `mixed_left_join`, `mixed_full_join`, `mixed_left_semi_join`, `mixed_left_anti_join`, and their `_size` variants) combines equality-based hash joins with AST predicate evaluation within a single kernel. Although this design was intended to improve efficiency by avoiding the materialization of intermediate join results, in practice, composing standard joins with pre- and post-filtering has proven to be both more performant and more flexible.

The mixed join implementation is also quite complex to maintain and build. Any enhancements to the core hash join such as bloom filter prefiltering or chunked probing must be independently ported to the mixed join kernels, resulting in an ongoing maintenance burden. Likewise, the mixed semi/anti join kernels duplicate logic found in `mark_join` and `filtered_join`, without benefiting from the optimizations present in those implementations.

**Describe the solution you'd like**

Refactor the mixed join internals to delegate to standard join APIs combined with pre- and post-filtering, while keeping the public `mixed_*_join` APIs unchanged. This approach removes duplicate kernel code and preserves backward compatibility.

***Inner, left, and full joins, completely ready once https://github.com/rapidsai/cudf/pull/22108 is in***

The implementation can be simplified by composing `hash_join` with `filter_join_indices`:

```cpp
// mixed_inner_join internals become:
auto hash_joiner = cudf::hash_join(right_equality, compare_nulls);
auto [left_idx, right_idx] = hash_joiner.inner_join(left_equality);
auto [filtered_left, filtered_right] = cudf::filter_join_indices(
left_conditional, right_conditional,
*left_idx, *right_idx,
predicate, cudf::join_kind::INNER_JOIN);
return {std::move(filtered_left), std::move(filtered_right)};
```

The same pattern applies to `mixed_left_join` (using `LEFT_JOIN`) and `mixed_full_join` (using `FULL_JOIN`). No new APIs are required.

***Semi and anti joins — design in progress***

All current use cases rely on cross-table AST predicates (e.g., `left.col0 > right.col0`), which cannot be evaluated independently on a single table. The proposed direction is to first apply a cross-table predicate filter, followed by `mark_join` or `filtered_join`.

**Describe alternatives you've considered**

Instead of rewriting internals, deprecate and remove all `mixed_*_join` public APIs, forcing callers to migrate to the composable approach directly. This is simpler to implement but breaks backward compatibility across C++, pylibcudf, and Java layers.

**Additional context**
The device-side AST infrastructure `expression_evaluator` https://github.com/rapidsai/cudf/blob/66623ccc139f7b943d680ac8369150f23dee6c19/cpp/include/cudf/ast/detail/expression_evaluator.cuh#L220-L789 already supports resolving `table_reference::LEFT` and `table_reference::RIGHT` using independent row indices. This functionality is currently leveraged internally by both `filter_join_indices` and the mixed join kernels.

Exposing this capability as a public two-table evaluation API could enable the proposed semi/anti join pre-filtering strategy and unlock additional composable execution patterns.

**Performance snapshot**

Image

Data processing throughput for inner joins with nullable INT32 keys. Based on libcudf microbenchmarks [here](https://github.com/rapidsai/cudf/blob/6afb2990f8db306fc552c220ebc8ae83ea338a32/cpp/benchmarks/join/filter_join_indices.cu#L41). “Hash join plus filter indices” approach shows higher throughput, and much better performance with complex predicates.

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.