[BUG] FULL join filtering emits spurious unmatched rows for duplicate equality keys
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.1k
- Avg merge
- 3d 6m
- Merged PRs (30d)
- 278
Description
**Describe the bug**
`cudf::filter_join_indices(..., cudf::join_kind::FULL_JOIN)` can emit spurious unmatched rows when duplicate equality keys produce both passing and failing predicate candidates.
For left `(key=1, value=10)` and right `[(1,5), (1,15)]`, a full join on equal keys with the additional predicate `left.value > right.value` should retain the successful pair and the unmatched right row. Instead, the filter also emits an unmatched left row, even though that row has a successful match.
This is a libcudf filtering bug, exposed while reviewing the Java binding in #24097.
**Steps/Code to reproduce bug**
The following reduced C++ unit test uses libcudf's test utilities. Add it to `cpp/tests/join/mixed_join_tests.cu` at the affected revision, rebuild the `JOIN_TEST` target, and run it with `--gtest_filter=FullJoinFilterRepro.DuplicateEqualityKey`.
```cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
struct FullJoinFilterRepro : cudf::test::BaseFixture {};
TEST_F(FullJoinFilterRepro, DuplicateEqualityKey)
{
using column = cudf::test::fixed_width_column_wrapper;
column left_keys{1};
column right_keys{1, 1};
column left_values{10};
column right_values{5, 15};
cudf::hash_join joiner{cudf::table_view{{right_keys}},
cudf::null_equality::UNEQUAL};
auto [left_indices, right_indices] =
joiner.full_join(cudf::table_view{{left_keys}});
cudf::ast::column_reference lhs{0, cudf::ast::table_reference::LEFT};
cudf::ast::column_reference rhs{0, cudf::ast::table_reference::RIGHT};
cudf::ast::operation predicate{cudf::ast::ast_operator::GREATER, lhs, rhs};
auto [filtered_left, filtered_right] = cudf::filter_join_indices(
cudf::table_view{{left_values}},
cudf::table_view{{right_values}},
cudf::device_span{*left_indices},
cudf::device_span{*right_indices},
predicate,
cudf::join_kind::FULL_JOIN);
// Expected pairs: (0, 0), (unmatched, 1).
// The affected implementation also emits (0, unmatched).
EXPECT_EQ(filtered_left->size(), 2);
EXPECT_EQ(filtered_right->size(), 2);
}
```
Both assertions fail because the affected implementation returns **3** rows.
**Expected behavior**
Using `unmatched` to denote the gather-map sentinel `INT32_MIN`, the output pair multiset should be:
```text
(0, 0)
(unmatched, 1)
```
The affected implementation returns:
```text
(0, 0)
(0, unmatched) // incorrect: left row 0 already matched right row 0
(unmatched, 1)
```
Output order is unspecified; the difference is the extra pair.
If `left_values{10}` is changed to `left_values{0}`, both candidates fail. The correct result has three pairs, but the implementation emits `(0, unmatched)` twice and returns four pairs. Duplicating the left side or using a null-valued predicate candidate exposes the same underlying defect.
**Environment overview**
- Affected revision: `e06741dfed37ff61eefc40390a518c9ea4e8595d`.
- Native regression reproduction: libcudf built from source in a CUDA 13.3 conda devcontainer on an NVIDIA RTX 6000 Ada GPU.
- The original reviewer also reproduced the behavior using the CUDA 12 Java CI JAR for that revision.
- Native regression coverage reproduced six failing duplicate/null/unmatched-row scenarios against the original implementation. The snippet above isolates the smallest mixed pass/fail case.
**Additional context**
The FULL branch handles each failed candidate independently: it null-extends the left row and appends a null-extended right row without checking whether either row has another passing match. Deduplicating unmatched pairs alone is insufficient, because the mixed pass/fail example still contains a spurious unmatched row.
Correct behavior requires tracking successful matches by row identity across all candidates: preserve every passing pair, then emit exactly one unmatched entry per row with no successful match.
The direct JIT filtering implementation has the same pair-splitting logic, and `filter_join_indices_output_size` counts the same incorrect output. Materialization, JIT, and size calculation need consistent semantics.
At the affected revision, `mixed_full_join` already uses left-join results followed by unmatched-right completion, so its passing tests do not establish correctness of direct FULL filtering.
Related discussion and Java reproducer: https://github.com/NVIDIA/cudf/pull/24097#discussion_r3985781913.
Contributor guide
Research direction
Add the reduced regression to cpp/tests/join/mixed_join_tests.cu, rebuild the JOIN_TEST target, and run it with --gtest_filter=FullJoinFilterRepro.DuplicateEqualityKey. Then trace cudf::filter_join_indices, the direct JIT filtering implementation, and filter_join_indices_output_size. Done means materialization, JIT, and size calculation consistently preserve passing pairs and emit exactly one unmatched entry per row with no successful match.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 62/100