sunchao commented on code in PR #26214:
URL: https://github.com/apache/datafusion/pull/26214#discussion_r4318931218
##########
datafusion/optimizer/src/decorrelate_predicate_subquery.rs:
##########
@@ -929,6 +934,38 @@ fn build_join(
}
let left = projected_left.as_ref().unwrap_or(left);
+ // The first `V` keys of a null-aware join are its `NOT IN` value keys.
+ //
+ // A tuple element that cannot be NULL in scope on either side never makes
+ // the tuple comparison UNKNOWN: compared with a definite value it is
either
+ // equal, which leaves the other elements to decide, or a definite
mismatch,
+ // which makes the comparison FALSE whatever the other elements are. It
+ // therefore only selects which subquery rows a NULL in another element is
+ // compared with, which is what a correlation scope key does. Moving such
+ // elements after the ones that can be NULL turns them into scope keys, so
+ // the hash join finds the rows a NULL-valued row is compared with through
a
+ // hash lookup instead of pairing it with every row of the other side
+ // (<https://github.com/apache/datafusion/issues/26088>).
+ //
+ // A null-aware tuple has at least one element that can be NULL, so `V` is
+ // at least one. With exactly one, the join is a scalar `NOT IN` on that
+ // element, correlated by the other elements.
+ let null_aware_value_keys = if null_aware && in_values.len() > 1 {
+ let (nullable, non_nullable): (Vec<_>, Vec<_>) = in_values
+ .into_iter()
+ .zip(elements_may_be_null)
+ .partition(|(_, may_be_null)| *may_be_null);
+ let null_aware_value_keys = nullable.len();
Review Comment:
**[P2] Preserve early termination when promoting low-cardinality scope keys**
This promotion can substantially increase work when the new scope key has
few distinct values. For example, consider materialized tables with these
schemas and contents:
```sql
-- outer_t(a INT, b INT NOT NULL): 8,192 rows of (NULL, 1)
-- inner_t(x INT, y INT NOT NULL): 8,192 rows of (2, 1)
SELECT *
FROM outer_t
WHERE (a, b) NOT IN (SELECT x, y FROM inner_t);
```
Previously, both elements were value keys, so
`for_each_unmarked_cross_product` stopped once all outer rows were marked
UNKNOWN. With `b = y` promoted to a scope key, `for_each_scope_match`
enumerates every matching pair; `retain_unmarked` discards already-resolved
rows only after the lookup has produced them. Both plans return the same
result, but the new path keeps traversing the constant-key bucket.
A focused executable harness using the actual traversal/iteration helper
bodies with minimal storage shims confirmed **8,192 candidate pairs before
versus 67,108,864 afterward**, with batch size 8,192 and both paths marking
exactly 8,192 rows. These are helper-level work counts, not end-to-end query
timings. The scalar early-exit path does not apply because the join still has
two keys, and NULL marking runs before the empty full-key-map shortcut.
Could we preserve early termination or prune resolved scope entries before
applying this transformation unconditionally, and add a
constant/low-cardinality scope benchmark?
--
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]
