NVIDIA / NVIDIA/cudf

[BUG] FULL join filtering emits spurious unmatched rows for duplicate equality keys

Open
#24,145 0 comments 0 reactions 0 assignees View on GitHub
? - Needs Triage bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.