adriangb opened a new issue, #25347:
URL: https://github.com/apache/datafusion/issues/25347
# Wrong results: correlated `NOT IN (subquery)` ignores NULLs in the subquery
_(Title for the issue; body follows.)_
## Describe the bug
`NOT IN` uses three-valued logic. If the value is not in the subquery
result, and the subquery result has a NULL, the answer is UNKNOWN. A `WHERE`
clause must remove the row.
DataFusion gives wrong results when the subquery is correlated. A correlated
subquery reads a column of the outer query.
Most of these queries give no error and no warning. Two of them give a
planner error.
Uncorrelated subqueries are correct. #25340 made the last of them correct.
## To Reproduce
```sql
CREATE TABLE t_out(id INT, g INT) AS VALUES (1, 1), (2, 2);
CREATE TABLE t_in(id INT, g INT) AS VALUES (1, 1), (NULL, 2);
SELECT id FROM t_out
WHERE 3 NOT IN (SELECT id FROM t_in WHERE t_in.g = t_out.g)
ORDER BY id;
```
`datafusion-cli` gives two rows:
```
+----+
| id |
+----+
| 1 |
| 2 |
+----+
```
DuckDB 1.5.2 and PostgreSQL 17.11 give one row: `1`.
### Why `1` is correct
The subquery is correlated. It gives a different result for each row of
`t_out`.
| `t_out` row | subquery result | `3 NOT IN` result | keep the row? |
|---|---|---|---|
| `id=1, g=1` | `{1}` | TRUE | yes |
| `id=2, g=2` | `{NULL}` | UNKNOWN | no |
Row `id=2` is the wrong one. Its subquery result is `{NULL}`. The value `3`
is not `NULL`, but `3` is also not known to be absent. Therefore the answer is
UNKNOWN, and the `WHERE` clause must remove the row.
## Expected behavior
The query gives one row: `1`.
## Which queries are correct
This diagram shows the boundary.
```
NOT IN (subquery)
│
├── The subquery does not read an outer column ───────────▶ CORRECT
│ SELECT id FROM t_in
│
└── The subquery reads an outer column (correlated)
│
├── The condition is an equality ──────────────────────▶ WRONG or ERROR
│ WHERE t_in.g = t_out.g
│
└── The condition is not an equality ──────────────────▶ WRONG
WHERE t_in.g > t_out.g
```
## Full test matrix
All queries use the two tables above. `g = 99` is always false, so it does
not change the correct answer. It only moves the `NOT IN` into a larger
expression.
The value is either a constant (`3`) or a column (`id`).
**Group A — the `NOT IN` is the whole `WHERE` clause**
| # | Query | Correct | DataFusion |
|---|---|---|---|
| A1 | `WHERE 3 NOT IN (SELECT id FROM t_in)` | *(none)* | *(none)* ✅ |
| A2 | `WHERE id NOT IN (SELECT id FROM t_in)` | *(none)* | *(none)* ✅ |
| A3 | `WHERE 3 NOT IN (SELECT id FROM t_in WHERE t_in.g = t_out.g)` | `1` |
`1, 2` ❌ |
| A4 | `WHERE id NOT IN (SELECT id FROM t_in WHERE t_in.g = t_out.g)` |
*(none)* | **error** ❌ |
| A5 | `WHERE 3 NOT IN (SELECT id FROM t_in WHERE t_in.g > t_out.g)` | `2` |
**error** ❌ |
| A6 | `WHERE id NOT IN (SELECT id FROM t_in WHERE t_in.g > t_out.g)` | `2`
| *(none)* ❌ |
**Group B — the `NOT IN` is one side of an `OR`** (add `OR g = 99`)
| # | Query | Correct | DataFusion |
|---|---|---|---|
| B1 | `WHERE 3 NOT IN (SELECT id FROM t_in) OR g = 99` | *(none)* |
*(none)* ✅ |
| B2 | `WHERE id NOT IN (SELECT id FROM t_in) OR g = 99` | *(none)* |
*(none)* ✅ |
| B3 | `WHERE 3 NOT IN (... WHERE t_in.g = t_out.g) OR g = 99` | `1` | `1,
2` ❌ |
| B4 | `WHERE id NOT IN (... WHERE t_in.g = t_out.g) OR g = 99` | *(none)* |
*(none)* ✅ |
| B5 | `WHERE 3 NOT IN (... WHERE t_in.g > t_out.g) OR g = 99` | `2` | `1,
2` ❌ |
| B6 | `WHERE id NOT IN (... WHERE t_in.g > t_out.g) OR g = 99` | `2` | `1,
2` ❌ |
**Group C — the query asks for UNKNOWN directly** (`(... ) IS NULL`)
| # | Query | Correct | DataFusion |
|---|---|---|---|
| C1 | `WHERE (3 NOT IN (SELECT id FROM t_in)) IS NULL` | `1, 2` | `1, 2` ✅ |
| C2 | `WHERE (id NOT IN (SELECT id FROM t_in)) IS NULL` | `2` | `2` ✅ |
| C3 | `WHERE (3 NOT IN (... WHERE t_in.g = t_out.g)) IS NULL` | `2` |
*(none)* ❌ |
| C4 | `WHERE (id NOT IN (... WHERE t_in.g = t_out.g)) IS NULL` | `2` | `2`
✅ |
| C5 | `WHERE (3 NOT IN (... WHERE t_in.g > t_out.g)) IS NULL` | `1` |
*(none)* ❌ |
| C6 | `WHERE (id NOT IN (... WHERE t_in.g > t_out.g)) IS NULL` | `1` |
*(none)* ❌ |
**Totals: 8 queries give wrong results. 2 queries give an error. 8 queries
are correct.**
The two errors are:
```
Error during planning: null_aware LeftAnti joins only support single column
join key, got 2 columns
Error during planning: null_aware LeftAnti join requires equi-join keys, but
the join has none
```
## The three parts of the problem
The failures are not one problem. They are three. Each part needs a
different change.
**Part 1 — A correlated `NOT IN` in a `WHERE` clause needs more than one
join key. (A3, A4)**
The query needs two keys: one for the `IN` value, one for the correlation. A
null-aware anti join accepts only one key today. A null-aware *mark* join
already accepts more than one key. B4 and C4 use the mark join, and they are
correct. This shows that the mark join is a possible model for the anti join.
**Part 2 — A constant value does not become a join key when the subquery is
correlated. (B3, C3)**
Compare B3 with B4. Both use the same subquery. B4 uses a column (`id`) and
is correct. B3 uses a constant (`3`) and is wrong. The constant does not become
a join key, so the join loses its null-aware behaviour.
**Part 3 — A correlated condition that is not an equality is not supported.
(A5, A6, B5, B6, C5, C6)**
The condition `t_in.g > t_out.g` cannot be a join key. It stays as a join
filter. A null-aware join looks for NULLs only in the *key*. It does not look
at the filter. Therefore a NULL in the filter column does not make the result
UNKNOWN, and the result is wrong.
## Suggested order of work
1. **Part 3 first, as an error.** A null-aware join with a leftover filter
is not correct today. Report an error for it. Do not give a wrong answer. This
makes Part 2 safe to fix.
2. **Part 2.** Give a constant the same treatment as a column. This is a
small change to `DecorrelatePredicateSubquery`.
3. **Part 1.** Let a null-aware anti join use more than one key, or rewrite
the anti join as a mark join.
Do Part 3 before Part 2. If you do Part 2 first, query A5 changes from a
clear error into a silent wrong answer.
## Additional context
- The same problem applies to `IN` when the query reads the UNKNOWN result,
as in group C.
- `NOT EXISTS` is not affected. It uses two-valued logic.
- Version: `datafusion-cli` 55.x. The results above come from a branch that
contains the fix for #25340.
## Related
- #25340 — `<constant> NOT IN (<subquery>)` ignores NULLs. This covers the
uncorrelated case only.
- #25336 — a related limit on null-aware mark joins.
--
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]
