adriangb opened a new issue, #25480:
URL: https://github.com/apache/datafusion/issues/25480
### Describe the bug
`x NOT IN (SELECT y FROM inner WHERE y = x)` returns no rows when `inner.y`
holds a NULL. The correct answer is every row of the outer table whose `x` is
not in `inner.y`.
The correlation predicate `y = x` and the `IN` predicate `x = y` are the
same equality. `PullUpCorrelatedExpr` removes the duplicate, so the correlation
is gone from the plan. What is left is the **uncorrelated** `x NOT IN (SELECT y
FROM inner)`, and that query is UNKNOWN for every row as soon as `inner.y`
holds a NULL.
The removal is correct for `IN` (a `LeftSemi` join), because `x IN (SELECT y
FROM inner WHERE y = x)` and `x IN (SELECT y FROM inner)` give the same answer.
It is not correct for `NOT IN`. The correlation makes the subquery result `{x}`
or the empty set, and neither can hold a NULL, so a correlated `NOT IN` of this
shape is never UNKNOWN.
There is no error and no warning.
### To Reproduce
```sql
CREATE TABLE t1(id INT, z INT) AS VALUES (1,10), (2,20), (NULL,30), (4,40);
CREATE TABLE t2(id INT, z INT) AS VALUES (1,5), (NULL,50), (5,10);
SELECT id FROM t1 WHERE id NOT IN (SELECT t2.id FROM t2 WHERE t2.id = t1.id)
ORDER BY id;
```
`datafusion-cli`:
```
+----+
| id |
+----+
+----+
0 row(s) fetched.
```
Expected: `2`, `4`, `NULL`. DuckDB 1.5.2 gives those three rows.
#### Why `2`, `4` and `NULL` are correct
The subquery result is different for each row of `t1`.
| `t1.id` | subquery result | `id NOT IN ...` | keep the row? |
| --- | --- | --- | --- |
| 1 | `{1}` | FALSE | no |
| 2 | `{}` | TRUE | yes |
| NULL | `{}` | TRUE | yes |
| 4 | `{}` | TRUE | yes |
The row `t2.id = NULL` never reaches a subquery result, because `NULL =
t1.id` is UNKNOWN for every value of `t1.id`. Therefore no row of this query is
UNKNOWN.
#### Full matrix
The same two tables. `z = 40` is only there to move the `NOT IN` into a
larger expression.
| # | Query (`... FROM t1 WHERE`) | Correct | DataFusion |
| --- | --- | --- | --- |
| Q1 | `id NOT IN (SELECT t2.id FROM t2 WHERE t2.id = t1.id)` | `2, 4, NULL`
| *(none)* ❌ |
| Q2 | `id NOT IN (SELECT t2.id FROM t2 WHERE t2.id = t1.id) OR z = 40` |
`2, 4, NULL` | `4` ❌ |
| Q3 | `(id NOT IN (SELECT t2.id FROM t2 WHERE t2.id = t1.id)) IS NULL` |
*(none)* | `2, 4, NULL` ❌ |
| Q4 | `SELECT id, id NOT IN (SELECT t2.id FROM t2 WHERE t2.id = t1.id) AS m
FROM t1` | `1 false, 2 true, 4 true, NULL true` | same ✅ |
| Q5 | `id IN (SELECT t2.id FROM t2 WHERE t2.id = t1.id)` | `1` | `1` ✅ |
| C1 | `id NOT IN (SELECT t2.id FROM t2 WHERE t2.z = t1.z)` (correlation on
another column) | `1, 2, 4, NULL` | planner error, see #25336 |
| C2 | `id NOT IN (SELECT t2.id FROM t2)` (no correlation) | *(none)* |
*(none)* ✅ |
Q1, Q2 and Q3 are wrong. Q4 goes through the three-join materialization of a
projected `IN`, which is not affected.
### Expected behavior
Q1 and Q2 give `2`, `4` and `NULL`. Q3 gives no rows.
### Additional context
Tested with a release `datafusion-cli` built from `main` at `c4f5a9e0f2`.
The results are the same on the branch of #25339, so that pull request does not
change this shape.
`EXPLAIN` for Q1 shows that the correlation is gone. The subquery side is a
bare `TableScan: t2`, and the join key is the `IN` equality:
```
logical_plan
LeftAnti Join: t1.id = __correlated_sq_1.id null_aware
TableScan: t1 projection=[id]
SubqueryAlias: __correlated_sq_1
TableScan: t2 projection=[id]
physical_plan
HashJoinExec: mode=CollectLeft, join_type=LeftAnti, on=[(id@0, id@0)],
null_aware
DataSourceExec: partitions=1, partition_sizes=[1]
DataSourceExec: partitions=1, partition_sizes=[1]
```
This is the plan of the uncorrelated `SELECT id FROM t1 WHERE id NOT IN
(SELECT id FROM t2)`, which correctly gives no rows.
#### Suspected root cause
`PullUpCorrelatedExpr` removes a correlation filter that is the same
expression as the `IN` predicate:
https://github.com/apache/datafusion/blob/c4f5a9e0f2/datafusion/optimizer/src/decorrelate.rs#L185-L190
```rust
let (mut join_filters, subquery_filters) =
find_join_exprs(subquery_filter_exprs)?;
if let Some(in_predicate) = &self.in_predicate_opt {
// in_predicate may be already included in the join filters, remove it
from the join filters first.
join_filters = remove_duplicated_filter(join_filters, in_predicate)?;
}
```
`remove_duplicated_filter` also treats the swapped operand order as the same
expression, so `t2.id = t1.id` matches the `IN` predicate `t1.id = t2.id`.
For a `LeftSemi` join the removal changes nothing. For a null-aware
`LeftAnti` or `LeftMark` join it drops the very predicate that keeps the NULLs
out of the subquery result.
#### Fix sketch
- Keep the duplicate correlation predicate when the join is a null-aware
`LeftAnti` or `LeftMark` join. The join then has the `IN` value key and the
correlation scope key, which #25339 supports. Note that `on[0]` must stay the
`IN` value key.
- Or, because the subquery result of this shape can never hold a NULL, plan
it as a plain (not null-aware) anti join plus the `x IS NULL` case. This is the
cheaper plan, but it needs the optimizer to prove that the correlation is an
equality on the `IN` value expression itself.
### Related
- #25336 — a correlated `NOT IN` with a non-equality correlation. Found
while the review of #25339 checked the shapes around it.
- #25347 — a correlated `NOT IN` with a constant value.
--
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]
