Merge join can finish before buffered key matches produce rows

perfloop-oss/velox · Premature Release

https://perfloop.ai/t/oss/case_w5kdvayjwn

Verdict

VERIFIED · settled 2026-11-11 · pull request opened as facebookincubator/velox#20299

What happened: The check fails before this change and passes with it.

Hypothesis

An inner merge join can report successful completion without returning matching rows when an equal-key group spans input batches. The driver treats that answer as permission to end the pipeline. The observed witness is small; production prevalence and the extent across other join configurations are unknown.

For inner joins, MergeJoin::isFinished returns noMoreInput_ && input_ == nullptr. It does not account for leftMatch_ or rightMatch_. MergeJoin::doGetOutput can return null while advanceMatch still needs input to complete such a group. Driver::runInternal uses isFinished after a null output to propagate EOF or close the serial output pipeline. This is a final-EOF mechanism, not the previously recorded right-join task-barrier dropInput defect in hyp_jzszcnx00r.

The native diagnostic command python3 velox/exec/tests/merge_match_count_property/check.py in call_ae8d2027023648ddaa325a9144bf0b5f built and linked the unmodified engine and reached its assertions. Public ValuesNode, MergeJoinNode and serial Task APIs received left keys [0] and right keys [0,0], independently split into one-row batches, with left streaming disabled. At output limits 1 and 8, both tasks reported finished and returned zero rows. An independent nested-loop reference expected two rows with distinct right payloads. CTest exited 8 because of that result assertion, not a build failure. The original finite search stopped at this result mismatch before checking counters; it did not establish a separate counter defect.

The Case should independently reproduce the reduced final-EOF witness and establish that buffered groups and any pending output are exhausted before completion. The required behavior is preservation of the full equal-non-null-key Cartesian product for the supported unfiltered inner operation, including batch boundaries, without defeating legitimate no-more-results termination. Tiny output limits, both streaming settings, and unequal or empty inputs are useful boundary controls. The native checker layout is provisional, not an additional repair requirement. Property prop_kywdj8d5w6 records the result-preservation contract. Confidence is medium pending independent replay and repair validation.

The actual implementations in https://github.com/facebookincubator/velox/pull/18186 (spilling and stable identities), https://github.com/facebookincubator/velox/pull/18584 (residual-filter continuation), and https://github.com/facebookincubator/velox/pull/19918 (parallel barrier participation) do not repair this unfiltered serial EOF predicate. Current-main MergeJoin.cpp matched the accepted file in the bounded comparison. Owner-path open-PR pagination is still being completed; denied GitHub discussion and Slack archive reads, and the unavailable internal review archive, remain explicit upstream gaps.

Change to test: Make final-EOF completion depend on exhausting pending match work, rather than only the current left vector. Preserve valid early termination when no further joined row is possible, and keep task-barrier drain distinct from final EOF.

Where it lives

perfloop-oss/velox

Evidence

The check fails before this change and passes with it: `For serial unfiltered MergeJoin with left (key,payload) [(0,10)] and right one-row batches [(0,20)], [(0,30)], completion returns both matching pairs for INNER/LEFT/RIGHT/FULL, one left row for LEFT SEMI, both right rows for RIGHT SEMI, and no rows for ANTI, with left streaming off/on and output limits 1 and 8.`

narrowGroupsStreamed merge join · 20 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3330926020 3315173468 −28189762 −133996303 to +139388170 loss ≤ 0.05 × |baseline median| PASSED

Checks: 3 of 3 passed. Verification: no defect found.

Timeline