Repository navigation
Native existence join enumerates every duplicate build match (N*M candidates for M markers) #6484
Description
Describe the problem
Comet maps Spark's ExistenceJoin (always BuildRight) onto DataFusion's mark join, which after the input swap becomes a RightMark. The DataFusion 55.1 hash-join lookup enumerates every equal-key candidate pair before the RightMark path reduces duplicate probe indices to Boolean markers. With N identical build keys and M matching probe rows this evaluates N*M candidate matches to produce only M output markers, whereas Spark's existence lookup stops after the first match per probe row.
Example (from review): 10,000 identical build keys and 1,000 matching probe rows imply ~10 million candidate matches even though only 1,000 markers are needed.
Impact
Correctness is unaffected — the marker is still "at least one match." This is a performance/scalability concern for skewed build keys. The current benchmark uses distinct build keys and does not exercise this path.
Suggested direction
Deduplicate the evaluated build-key tuples for residual-free existence joins, or use a mark-join implementation that stops after the first match. Any dedup helper must account for its own memory and support bounded spilling, and must not discard distinct right payloads while a residual predicate can still use them.
Context
Split out from PR #4587 (native ExistenceJoin). Reviewer thread: #4587 (comment) . Deferring per discussion (feature is useful now; the mark join can be improved in the background). Related upstream perf work: apache/datafusion#23870
Activity
andygrove commentedon Oct 1, 2026
Native semi and anti joins have the same walk today. With
BuildRightthey becomeRightSemiandRightAnti, which go through the samelookup_join_hashmapand only collapse duplicates afterwards inadjust_indices_by_join_type. In a debug build on 09-25, with 200k probe rows and 2,000 of them matching one key, repeating that key 20k times on the build side took the semi join to 242 ms and the existence join to 371 ms. Spark stayed at 50 to 65 ms. Spark answers all three with a single lookup when there is no condition, and itsShuffledHashJoinExecdrops duplicate build keys for them (ignoreDuplicatedKey). Could we widen this issue to cover semi and anti joins too, so one fix lands for all three?