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
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
2026-11-11· Case opened2026-11-11· PR opened