viirya opened a new pull request, #26213:
URL: https://github.com/apache/datafusion/pull/26213
## Which issue does this PR close?
- Closes #26089.
## Rationale for this change
A multi-column `(a, b) NOT IN (SELECT x, y ...)`, and a correlated `NOT IN`
with scope keys or a join filter, plans as a null-aware `LeftAnti` hash join
that `JoinSelection` never swaps. The outer side is always the build side and
is held in memory even when the subquery is tiny. With @comphead's repro
(2M-row outer table, 100-row subquery, `--memory-limit 64M`), the scalar `NOT
IN` runs but the multi-column one fails with `Resources exhausted ...
HashJoinInput`.
## What changes are included in this PR?
- `JoinSelection` may swap every null-aware `LeftAnti` into a `RightAnti`
that builds on the subquery side, not only the single-key, unfiltered one. The
swap keeps `null_aware_value_keys` and the key order, and the join filter is
swapped with the inputs. A null-aware `LeftMark` is not swapped.
- `NullAwareMode::RightAnti` now carries `{ correlated, value_keys }`, and
`NullAwareMode::try_new` accepts a multi-key or filtered null-aware `RightAnti`
(still `CollectLeft` only).
- Uncorrelated (single key, no filter): unchanged. A NULL build key
silences every batch and NULL probe keys are dropped.
- Correlated: each outer (probe) row is decided while streaming. An exact
match is found by the main hash lookup (FALSE). The probe rows that are UNKNOWN
are found once per probe batch by the existing NULL candidate pairing of the
correlated `LeftAnti`: NULL-valued build rows against all probe rows, and
NULL-valued probe rows against all build rows, narrowed by the scope maps, then
the element-wise "no definite mismatch" check (`retain_value_mismatch_free`)
and the join filter. The UNKNOWN rows are dropped from the output.
- The pairing helpers in `stream.rs` take an `UnknownMarks` that says which
side of a candidate pair is marked: build rows in the shared null-indices
bitmap (`LeftAnti` / `LeftMark`, unchanged) or rows of the current probe batch
(`RightAnti`). A correlated `RightAnti` builds the scope maps but not the
per-build-row bitmap, and has no state shared across probe partitions.
The build side is not deduplicated, since that does not hold with a join
filter. The NULL pairing still costs (NULL-valued rows) x (rows on the other
side) without scope keys; #26088 narrows that.
## What is the testing strategy for this PR?
- `exec.rs` unit tests:
- `test_null_aware_multi_column_right_anti` runs a two-column `NOT IN` as
`LeftAnti` and as the swapped `RightAnti` across batch sizes, including an
all-NULL-valued subquery (empty full-key map) and an empty subquery.
- `test_null_aware_left_anti_multi_column_scope` also checks the swapped
`RightAnti`.
- The validation tests now accept a multi-key or filtered null-aware
`RightAnti`.
- `join_selection.rs`: a filtered null-aware `LeftAnti` swaps, and the
filter's sides are swapped too. A multi-key null-aware `LeftAnti` swaps with
`value_keys` 1 and 2 kept.
- `null_aware_multi_column.slt` adds
`datafusion.optimizer.join_reordering=true,false` to its `configMatrix`, so
every result is checked with the `RightAnti` and the `LeftAnti` plan. Plans in
`null_aware_anti_join.slt` and `subquery_projection.slt` are updated; no query
result changed.
- `null_aware_join_fuzz.rs`: half of the seeds use a much smaller subquery
table, and the test counts the null-aware plans it ran and asserts it reached
`LeftAnti`, `RightAnti` and a correlated (multi-key or filtered) `RightAnti`. A
run had 228 / 1692 / 1602 of them. Disabling the mismatch check on the
`RightAnti` path makes the fuzz fail.
- `memory_limit/null_aware_not_in.rs`: a small-scale version of the repro
above. A 200k-row outer table against a 101-row subquery (one NULL-valued row)
under a 2 MB limit gives the right count with join reordering on, and runs out
of memory in `HashJoinInput` with it off. The test fails without the
`JoinSelection` change.
`null_aware_join` benchmark, Q10 / Q11 / Q12 (multi-column, which now plan
as `RightAnti`), mean of 3 interleaved runs, in ms:
| | main | this PR |
|---|---|---|
| NAJ_ROWS=10000 | 0.343 / 3.508 / 0.572 | 0.348 / 3.520 / 0.557 |
| NAJ_ROWS=20000 | 0.394 / 7.800 / 0.756 | 0.414 / 6.634 / 0.627 |
They take about the same time because the NULL pairs are the same. The gain
is that the build side is now the subquery, which the memory-limit test covers.
The other queries of the suite stay within run-to-run noise.
## Are there any user-facing changes?
Multi-column and correlated `NOT IN` subqueries can now plan as a null-aware
`RightAnti` hash join built on the subquery side, so `EXPLAIN` output changes
and memory use drops when the subquery is the smaller side. No public API
changes.
This pull request and its description were written by Isaac.
--
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]
