NVIDIA / NVIDIA/cudf

filter_join_indices corrupts results and reads out of bounds past 2^31 candidate pairs

Open
#23,827 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

`filter_join_indices` and its internal use by mixed joins index candidate pairs with 32-bit arithmetic and silently corrupt or read out of bounds when the equality-match candidate count exceeds `2^31`, which column row limits do not prevent.

Candidate count is the hash-join match count, bounded only by memory (~8 bytes/pair), not by libcudf's int32 row limit: two ~47k-row tables sharing one distinct key already exceed 2^31 candidates. The left-join branch of the same file was deliberately made 64-bit for exactly this shape (comments at `cpp/src/join/filter_join_indices/filter_join_indices.cu:237-288` cite "index vectors of size greater than integer limits"), but these sites were left 32-bit:

- `cpp/src/join/filter_join_indices/filter_join_indices_kernel.cuh:55`: `for (cudf::size_type i = tid; ...)` truncates the int64 thread id; wrapped-negative values exit the loop via uint64 promotion, so candidate positions >= 2^31 are never evaluated and the tail of the uninitialized `predicate_results` buffer feeds downstream count/copy as garbage.
- `cpp/src/join/filter_join_indices/filter_join_indices.cu:179-180` (INNER count): `static_cast(left_indices.size())` wraps negative before iteration; count runs over a negative-distance range producing garbage counts.
- `cpp/src/join/filter_join_indices/filter_join_indices.cu:196` (INNER stencil): the `counting_iterator` wraps at offset 2^31 inside CUB `DeviceSelect::FlaggedIf`; the lambda then indexes `predicate_results_ptr[negative]`, an out-of-bounds read, and garbage flags can select more elements than the sized outputs, overrunning them.
- Same pattern in the FULL branch: lines 321-322, 334-335, 362.

No guard rejects oversized inputs on any of these paths; only cross join has a `CUDF_EXPECTS` on result rows (`cpp/src/join/cross_join.cu:51`). The default public path (`mixed_inner_join` with no `output_size`) goes through the INNER branch, so production workloads hit this without opting into anything. A >2^31 candidate span with a predicate that rejects most candidates triggers every site while keeping the final result small enough to look healthy.

The newer output-size kernel shows the intended pattern (`auto i = tid` deducing `thread_index_type`, host reduction into `std::size_t`). Suggested fix: propagate that pattern to the predicate kernel loop and all INNER/FULL counting/stencil sites, mirroring the existing 64-bit left-join branch, plus a `CUDF_EXPECTS` capping the post-filter result count at `size_type` max before materializing columns, matching cross join.

Contributor guide

Open the contributing guide

Research direction

Start with cpp/src/join/filter_join_indices/filter_join_indices_kernel.cuh:55 and the INNER/FULL sites at lines 179-196 and 321-362. Compare them with the 64-bit left-join branch at cpp/src/join/filter_join_indices/filter_join_indices.cu:237-288 and the newer output-size kernel. Done means candidate indexing and counting no longer wrap at 2^31, and oversized post-filter results are rejected before column materialization.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
data, databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.