filter_join_indices corrupts results and reads out of bounds past 2^31 candidate pairs
- 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
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