sunchao opened a new pull request, #25584: URL: https://github.com/apache/datafusion/pull/25584
## Which issue does this PR close? Closes #25581. ## Rationale for this change Semi/anti sort-merge joins can repeatedly search the same equality-key group to answer an existence question. A group with many duplicate values and no qualifying witness is particularly expensive. For eligible predicates, an exact summary replaces repeated residual searches with one pass over each input group. For `outer.x <> inner.y`, the summary retains one non-null representative until a second distinct value appears, then only a multiple-values flag. Ordered comparisons retain the appropriate minimum or maximum. Each outer row gets an ordinary Boolean existence result, preserving duplicate rows and SQL null behavior. ## What changes are included in this PR? - Add the default-off `datafusion.execution.enable_sort_merge_join_existence_summary` session option, read when executing a sort-merge join. It does not change planner join selection or the serialized plan format. - Compile supported residuals once: inequality/range comparisons over supported scalar types (including strings, temporal values and decimals), safe side-local guards, and bounded OR combinations. Unsupported expressions and conjunctions requiring multiple cross-side comparisons retain the existing implementation. - Summarize one sorted equality-key group at a time and reuse its state across outer batches. Retain only owned scalar values, reserve their memory through a non-spillable consumer, and yield cooperatively after bounded row work. Continue consuming the group after saturation to preserve upstream errors and group boundaries. - Expose activation/fallback, groups, inner/probe rows, and peak retained-state metrics only when the feature is requested. Keep the disabled execution path separately specialized and preserve existing unfiltered fast paths. Hash joins, mark/null-aware joins, arbitrary inline functions/casts/arithmetic, floating-point residuals, distinct aggregation, and pre-shuffle reduction are outside this PR. Summary state does not spill. If an owned representative cannot be admitted to the memory pool, execution returns a resource-exhaustion error; it does not attempt to replay a partially consumed group through the generic path. ## What is the testing strategy for this PR? - `cargo fmt --all` and `cargo clippy --all-targets --all-features -- -D warnings` passed. - The full unmodified `./dev/rust_lint.sh` suite passed, including generated-doc checks, dependency checks, and rustdoc with warnings denied. - All 18 focused summary tests and the new SQL/session-config activation test passed. - The full extended workspace test command passed: 12,072 Rust tests, 8 ignored, plus all 523 SQL logic files. The new SQL logic file also passed in a targeted run. Tests cover scalar-oracle and existing-join parity, all four semi/anti orientations, null keys and residuals, duplicate outputs, sort/null ordering, strings/temporal/decimal values, guarded OR, same-witness fallback, multiple batches, bounded memory, upstream errors, cooperative yielding and stream-drop cleanup. SQL tests verify results and actual native activation through session configuration. Benchmark fixtures cover large no-witness inequality/range groups, many small groups, and early witnesses. All timed fixtures use Int64; other supported types were tested for correctness, not benchmarked here. Results are operator microbenchmarks, not TPC-H or production full-query speedups. Benchmarked against Apache main `0576a0b400437ade5a6f3b102465d954a539f263`, Rust 1.98.1, Linux x86_64, `release-nonlto`, `test_utils`. Times are means of two independent Criterion run means. Execution, collection, and output destruction are timed; input and fresh-plan construction are outside the timer. | Fixture | Main baseline | Candidate off | Candidate on | Off/on speedup | |---|---:|---:|---:|---:| | `<>` anti, 1 key, 256/4096 rows, no witness | 7061.71 us | 6853.65 us | 118.91 us | 57.64x | | `>` semi, 1 key, 256/4096 rows, no witness | 7570.92 us | 7090.54 us | 72.37 us | 97.98x | | `<>` anti, 4096 keys, 2/3 rows per key | 8108.10 us | 7983.86 us | 5095.21 us | 1.57x | | `<>` semi, 16 keys, 64/128 rows per key, early witness | 68.59 us | 67.74 us | 59.20 us | 1.14x | Serial order: main/off/on/on/off/main; each run used 10 samples, 500 ms warmup, and a 2-second measurement target. Output counts and activation were checked before timing. Both builds used identical dependency resolution. The benchmark baseline differs from main only by these fixtures (with the new option removed) and the same external dependency-source overlay. Eight existing SMJ controls ran main/candidate/candidate/main with the feature off. Three buffered-batch cases had higher candidate means (+0.05%, +1.63%, +2.06%); the others ranged from -1.0% to -6.0%. Shared-host drift reached approximately 16% in a baseline control, so small changes are inconclusive. Processes were not CPU-pinned; other users' activity and CPU frequency were not controlled. These measurements do not establish a blanket absence of regressions. The local dependency mirror lacks some versions required by main. Validation and both benchmark builds therefore used an external Cargo overlay with release sources for Arrow 60.0.0, object_store 0.14.2, sqlparser 0.63.0, and compression-codecs 0.4.42. No dependency manifests, lockfiles, or overlay configuration are changed in this PR. CI will additionally validate the normal registry dependency path. ## Are there any user-facing changes? The new execution option is disabled by default. Enable it with: ```sql SET datafusion.execution.enable_sort_merge_join_existence_summary = true; ``` It takes effect only when a supported semi/anti sort-merge join is executed. Existing join-selection settings still apply. Configuration documentation and information-schema expectations are updated. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
