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

[bdice]

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.

#include <cudf_test/base_fixture.hpp>
#include <cudf_test/column_wrapper.hpp>
#include <cudf_test/cudf_gtest.hpp>

#include <cudf/ast/expressions.hpp>
#include <cudf/join/hash_join.hpp>
#include <cudf/join/join.hpp>
#include <cudf/table/table_view.hpp>
#include <cudf/types.hpp>
#include <cudf/utilities/span.hpp>

struct FullJoinFilterRepro : cudf::test::BaseFixture {};

TEST_F(FullJoinFilterRepro, DuplicateEqualityKey)
{
  using column = cudf::test::fixed_width_column_wrapper<cudf::size_type>;

  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<cudf::size_type const>{*left_indices},
    cudf::device_span<cudf::size_type const>{*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:

(0, 0)
(unmatched, 1)

The affected implementation returns:

(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: #24097 (comment).