jayzhan211 commented on code in PR #26214:
URL: https://github.com/apache/datafusion/pull/26214#discussion_r4413212414
##########
datafusion/optimizer/src/decorrelate_predicate_subquery.rs:
##########
@@ -1037,6 +1042,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 {
Review Comment:
@viirya thanks for the PR! I measured the no-NULL case. Moving a NOT NULL
element to a scope key makes `correlated_row_state` build a second hash map
over every build row, but only probe rows with a NULL value key ever read it.
So multi-column `NOT IN` over nullable columns that hold no NULLs (the Q10
shape) now pays for it. Since this PR makes that the default path, could the
scope map be built lazily here (on the first probe batch with a NULL-valued
row), rather than in a follow-up?
Same build, same data. `zn` is nullable without NULLs, so it stays a value
key; `z` is NOT NULL, so it becomes a scope key. 2M rows each side, release
`datafusion-cli`, head merged with main, median of 10:
| | 1 partition | 4 partitions | `build_mem_used` |
|---|---|---|---|
| `(id_n0, zn)` value keys | 26 ms | 22 ms | 106.1 MB |
| `(id_n0, z)` scope key | 33 ms | 30 ms | 181.8 MB |
```sql
CREATE TABLE so AS SELECT CASE WHEN value < 0 THEN NULL ELSE value END AS
id_n0, value % 1000 AS z, CASE WHEN value < 0 THEN NULL ELSE value % 1000 END
AS zn FROM range(0, 2000000);
CREATE TABLE si AS SELECT CASE WHEN value < 0 THEN NULL ELSE value * 2 END
AS id_n0, value % 1000 AS z, CASE WHEN value < 0 THEN NULL ELSE value % 1000
END AS zn FROM range(0, 2000000);
EXPLAIN ANALYZE SELECT count(*) FROM so o WHERE (o.id_n0, o.zn) NOT IN
(SELECT i.id_n0, i.zn FROM si i);
EXPLAIN ANALYZE SELECT count(*) FROM so o WHERE (o.id_n0, o.z) NOT IN
(SELECT i.id_n0, i.z FROM si i);
```
##########
datafusion/sqllogictest/test_files/null_aware_multi_column.slt:
##########
@@ -546,6 +546,167 @@ z
statement ok
DEALLOCATE mc_tuple_qualified;
+#############
+## NOT NULL tuple elements
Review Comment:
Could you add a case where an element is nullable in the schema but becomes
a scope key because a correlated filter rejects NULL? That path sends NULL
scope keys into the hash join, and no current test reaches it. It's fine to do
this in a follow-up. These results match the `NOT EXISTS ... IS NOT FALSE`
reference:
```sql
statement ok
CREATE TABLE mc_scope_outer(k INT, a INT, b INT) AS VALUES
(1, 1, 2), (2, NULL, 2), (3, NULL, NULL), (4, 5, NULL), (5, NULL, 7), (6, 1,
9), (7, 3, 3);
statement ok
CREATE TABLE mc_scope_inner(x INT, y INT) AS VALUES
(1, 2), (NULL, 2), (5, NULL), (NULL, NULL), (3, 1), (8, 4);
query IB
SELECT k, (a, b) NOT IN (SELECT x, y FROM mc_scope_inner i WHERE i.y >= o.b)
FROM mc_scope_outer o ORDER BY k;
----
1 false
2 NULL
3 true
4 true
5 true
6 true
7 true
```
##########
datafusion/optimizer/src/decorrelate_predicate_subquery.rs:
##########
@@ -953,16 +955,19 @@ fn build_join(
None => vec![],
};
- // True if an `IN` value or the subquery column it is compared with can be
- // NULL inside the scope of an outer row.
- let mut value_may_be_null = false;
- for in_value in &in_values {
- value_may_be_null |= in_value.may_be_null_in_scope(
- left.schema(),
- sub_query_alias.schema(),
- &pull_up.correlated_filters,
- )?;
- }
+ // For each `IN` value, true if it or the subquery column it is compared
+ // with can be NULL inside the scope of an outer row.
+ let elements_may_be_null = in_values
+ .iter()
+ .map(|in_value| {
+ in_value.may_be_null_in_scope(
+ left.schema(),
+ sub_query_alias.schema(),
+ &pull_up.correlated_filters,
+ )
+ })
+ .collect::<Result<Vec<_>>>()?;
+ let value_may_be_null = elements_may_be_null.iter().any(|may_be_null|
*may_be_null);
Review Comment:
Optional cleanup:
```diff
- let value_may_be_null = elements_may_be_null.iter().any(|may_be_null|
*may_be_null);
+ let value_may_be_null = elements_may_be_null.contains(&true);
```
##########
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:
I agree with @sunchao, and it still reproduces at the current head (about 3
ms → 300–800 ms for LeftAnti, the mark join and NULLs in the subquery), because
the head predates #25679. With main merged in, both plans take about 1 ms on
all three shapes, so a rebase fixes it. Could you rebase and add the
constant/low-cardinality scope-key query to `null_aware_join` as you planned?
--
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]
