viirya opened a new pull request, #26214:
URL: https://github.com/apache/datafusion/pull/26214
## Which issue does this PR close?
- Closes #26088.
## Rationale for this change
A multi-column `(a, b) NOT IN (SELECT x, y ...)` plans as a null-aware hash
join that decides UNKNOWN per build row. Without correlation keys, every row
with a NULL in any tuple element is paired with every row on the other side, so
the NULL path costs O(rows x NULL-valued rows).
A tuple element that cannot be NULL in scope on either side never makes the
tuple comparison UNKNOWN: against a definite value it is either equal, which
leaves the other elements to decide, or a definite mismatch, which makes the
comparison FALSE. It only selects which rows a NULL in another element is
compared with, which is exactly what a correlation scope key does. For example,
with `b` and `y` NOT NULL, a NULL `a` only needs to be compared with the
subquery rows whose `y` equals its `b`.
## What changes are included in this PR?
- **Decorrelation** (`build_join`): for a null-aware tuple, the elements are
partitioned by `may_be_null_in_scope`, keeping their order within each group.
The elements that can be NULL come first and are the `NOT IN` value keys
(`null_aware_value_keys` counts only them); the others follow as scope keys,
before any correlation keys. The "value keys first" layout is unchanged, so the
hash join needs no change: it already narrows the NULL candidate pairs through
its scope hash map.
- All elements NOT NULL: the join is not null-aware, as before.
- Exactly one nullable element: `V = 1`, a scalar `NOT IN` on that element
correlated by the others.
- `LeftMark` (projection / `OR`) is reordered the same way and stays
three-valued exact.
- A NOT NULL element that is not a hashable equi-join key (e.g.
RunEndEncoded) now stays in the join filter like any correlation instead of
being rejected. A nullable one is still rejected.
- Docs: `Join::null_aware_value_keys`, `HashJoinExec::null_aware_value_keys`
and the 56.0.0 upgrade guide describe the new key layout.
- The Q11 / Q12 comments of the `null_aware_join` benchmark now describe the
scope-key path: their `z` column (`value % 1000`) is NOT NULL.
## What is the testing strategy for this PR?
- `null_aware_anti_join.slt`: EXPLAIN plans for the reordering, with a
correlation, with two nullable elements and one NOT NULL element, a constant
element, NOT NULL on the outer side only (not reordered), and a mark join.
- `null_aware_multi_column.slt` (batch size matrix): results with NOT NULL
elements for `LeftAnti`, `LeftMark` and `OR`, equivalence with the scalar `NOT
IN` shape, correlated subqueries, an empty subquery, a constant element and a
non-hashable NOT NULL element.
- `null_aware_join_fuzz.rs`: NOT NULL columns on both sides and seven mixed
shapes, compared with the `NOT EXISTS ... IS NOT FALSE` reference. Placing the
NOT NULL elements first fails this fuzz on its first seed.
- `roundtrip_logical_plan.rs`: the existing multi-column case had only NOT
NULL `VALUES` columns for `b`/`y`, so it now expects one value key; a variant
with a nullable `b` keeps covering two value keys.
Benchmark `null_aware_join` against `main` (mean of 3 alternating runs):
| NAJ_ROWS | Q10 (no NULL) | Q11 (1% NULL in subquery) | Q12 (1% NULL in
outer) |
|---|---|---|---|
| 10000 | 0.34 ms -> 0.34 ms | 3.55 ms -> 0.35 ms | 0.72 ms -> 0.36 ms |
| 20000 | 0.42 ms -> 0.47 ms | 7.85 ms -> 0.49 ms | 0.77 ms -> 0.51 ms |
Q01 to Q09 are unchanged. Q10 (20000 rows, one outlier run dropped) is
slightly slower: with a scope key, the build side eagerly builds a scope hash
map over all build rows, which is only probed for NULL-valued probe rows. This
is the existing behavior of correlated scalar `NOT IN`; building that map
lazily could be a follow-up.
## Are there any user-facing changes?
Faster multi-column `NOT IN` when some tuple elements are NOT NULL. Plans
show fewer `NOT IN` value keys (`null_aware(value_keys=N)`) for such tuples. No
API change.
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]
