You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "adriangb (via GitHub)" <gi...@apache.org> on 2026/09/18 16:00:33 UTC
[I] Wrong results: correlated `NOT IN` loses the correlation when it is an equality on the `IN` value column [datafusion]
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: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Wrong results: correlated `NOT IN` loses the correlation when it is an equality on the `IN` value column [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #25480: Wrong results: correlated `NOT IN` loses the correlation when it is an equality on the `IN` value column
URL: https://github.com/apache/datafusion/issues/25480
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Wrong results: correlated `NOT IN` loses the correlation when it is an equality on the `IN` value column [datafusion]
Posted by "raghavyadav01 (via GitHub)" <gi...@apache.org>.
raghavyadav01 commented on issue #25480:
URL: https://github.com/apache/datafusion/issues/25480#issuecomment-6506155514
Checked on current main (14aa185dd), this returns the right rows now:
```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;
-- 2, 4, NULL
```
Same as DuckDB 1.5.6. I think this can be closed.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Wrong results: correlated `NOT IN` loses the correlation when it is an equality on the `IN` value column [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #25480:
URL: https://github.com/apache/datafusion/issues/25480#issuecomment-6507471956
Agreed -- I doubel checked. Thank you @raghavyadav01
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Wrong results: correlated `NOT IN` loses the correlation when it is an equality on the `IN` value column [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #25480:
URL: https://github.com/apache/datafusion/issues/25480#issuecomment-6479356286
When fixing this bug, I think we should make the query error rather than trying to make it work / give correct results. To make it work and have confidence it will be correct, I think we need a more general approach than patches. See here for details
- https://github.com/apache/datafusion/issues/5492#issuecomment-6479090126
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org