Filtered merge joins fail when the first output batch exceeds tracker capacity
perfloop-oss/velox · Extent mismatch
https://perfloop.ai/t/oss/case_qxka0hq71v
Verdict
VERIFIED · settled 2026-11-10 · pull request opened as facebookincubator/velox#20289
What happened: The check fails before this change and passes with it.
Hypothesis
MergeJoin can use dynamic output sizing. The first output batch then uses `merge_join_output_batch_start_size`. That setting is documented as the starting batch size and is not required to stay below `preferred_output_batch_rows`. MergeJoin sizes its per-output-row join tracker from the preferred row count instead. If the start size is larger, filtered outer, semi and anti joins can write tracking entries beyond that capacity. A native check reproduces a failed query in a Debug build. Release-build behavior is still unmeasured.
Source trace at 5b9931ffa4a99927e80cc42ac93c777662c43cfb: - The `MergeJoin` constructor sets `outputBatchSize_` to `mergeJoinOutputBatchStartSize()` when it is nonzero. - `initialize()` constructs `JoinTracker(preferredOutputBatchRows_, pool())` for filtered left, right, full, semi and anti joins, and for unfiltered anti joins. `JoinTracker` sizes both `matchingRows_` and `leftRowNumbers_` from that value. - `tryAddOutputRow` calls `addMatch(..., outputSize_)` for row indexes up to `outputBatchSize_ - 1`. - `applyFilter` and `filterOutputForAntiJoin` call `matchingRows(numRows)`. That calls `setValidRange(numRows, size)`, which requires `numRows <= size`. - `updateOutputBatchSize` caps only later batches at the preferred count. Neither `QueryConfig` nor `configs.rst` caps the start size. Existing dynamic-size tests in `MergeJoinTest.cpp` use start size 1.
Native check: property `prop_g8pwdppd9k`, run `toolu_vrtx_01YLYRNUXKiPJeAE2YiXdn5v`, command `python3 velox/exec/tests/merge_extent_property/check.py`. It built the unmodified engine in Debug through public `Task`, `ValuesNode` and `MergeJoinNode` with the repository GoogleTest/CTest helper. All 72 control cases passed, meaning start zero or start no greater than the preferred count. One filtered inner case with a larger start size also passed; inner joins do not create a tracker. The first tracked failure used `preferred_output_batch_rows=1`, start size 2, and a filtered LEFT join. Left keys were {0,0,0,0,0,1}, right keys were {0,0,0,0,2}, and the filter was `lv < rv`. MergeJoin failed in `SelectivityVector::setValidRange` with `end >= begin (1 vs. 2)`, VeloxRuntimeError INVALID_STATE. CTest exit 8 is that assertion, not a build failure. The stored replay `1 2 1` reproduces the failure deterministically.
Unmeasured: the 94 remaining enumerated cases, including other join types and start size 70, did not run. In Release the debug check is compiled out, so the effect could be wrong results or out-of-bounds writes; this is a hypothesis for the Case. Whether `filterInput_`, also sized from the preferred count, has the same problem is unproven; the one inner-filter case passed.
Upstream: no open pull request touching `MergeJoin.cpp`, `MergeJoin.h`, `MergeJoinTest.cpp`, `Operator.*` or `task-barrier.rst` appeared in pages scanned back to 2026-10-19. Landed #19947 and #20104 change filter-result continuation and left streaming, not tracker capacity. GitHub Discussions and Slack archive reads were refused, so those venues remain an evidence gap. This lead is separate from the barrier right-join cutoff finding `hyp_jzszcnx00r`.
Proof target: the stored replay should pass after the repair. The full 168-case enumeration should then show results matching the nested-loop reference. A Case could add an ASan or Release run of the same replay.
Change to test: Make every per-output-row structure fit the largest batch the operator can produce. One option is to size or grow `JoinTracker` (and check `filterInput_`) from the largest possible `outputBatchSize_`, not the preferred count; another is to reject or clamp a start size above the preferred count. Preserve join results and the later dynamic-size cap. Rejecting or clamping changes documented configuration behavior, so the Case must record that choice.
Where it lives
Evidence
The check fails before this change and passes with it: `With merge_join_output_batch_start_size (16) larger than preferred_output_batch_rows (2), MergeJoin returns the same rows as DuckDB without error for filtered LEFT, RIGHT, FULL, LEFT SEMI, RIGHT SEMI and ANTI joins and an unfiltered ANTI join on duplicate join keys (MergeJoinTest.dynamicOutputBatchSizingWithLargeStartSize, Debug build).`
Checks: 1 of 1 passed. Verification: no defect found.
Timeline
2026-11-10· Case opened2026-11-11· PR opened