Wrong results: correlated `NOT IN (subquery)` ignores NULLs in the subquery

[adriangb]

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

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 Wrong results: constant NOT IN (subquery) in a WHERE clause ignores NULLs in the subquery #25340.

Related

• Wrong results: constant NOT IN (subquery) in a WHERE clause ignores NULLs in the subquery #25340 — <constant> NOT IN (<subquery>) ignores NULLs. This covers the uncorrelated case only.
• Wrong results: correlated NOT IN with a non-equality correlation returns no rows (null-aware LeftAnti join ignores the residual filter) #25336 — a related limit on null-aware mark joins.

[adriangb]

Most of this is already covered by the two open PRs. I measured the 18-shape matrix at each stage; what is left is one small gap.

Where the matrix stands

#25339 fixes every column-value shape, A2/A4/A6 and their B and C counterparts included. With #25348 on top of it, the shapes still wrong are exactly the six with a constant value and a correlated subquery:

#	Query	Correct	With #25339 + #25348
A3	WHERE 3 NOT IN (... WHERE t_in.g = t_out.g)	1	1, 2 ❌
A5	WHERE 3 NOT IN (... WHERE t_in.g > t_out.g)	2	error ❌
B3	... OR g = 99, equality correlation	1	1, 2 ❌
B5	... OR g = 99, non-equality correlation	2	error ❌
C3	(...) IS NULL, equality correlation	2	(none) ❌
C5	(...) IS NULL, non-equality correlation	1	error ❌

The errors are:

Error during planning: null_aware LeftAnti join requires equi-join keys, but the join has none
Error during planning: null_aware LeftMark join requires equi-join keys, but the join has none

The other twelve shapes are correct at that point. So this issue reduces to part 2 of the plan above — the constant value — and parts 1 and 3 are handled by #25339.

Root cause of the remaining six

A constant value expression holds no column reference, so 3 = sq.id is not a valid equi-join key and cannot serve as the null-aware join's value comparison.

For an uncorrelated subquery that left the join with no key at all, which is what #25348 fixes by projecting the constant as a column of the outer side. For a correlated subquery it is worse: the correlation supplies the only equi-join key, so the join compares grp and never compares the value at all, while still reporting itself null-aware.

The fix

Extend the projection #25348 already performs to the correlated case: keep the correlation predicate aside, rebuild the IN equality against the projected column, then restore the correlation as a separate conjunct. The join then has the value comparison as one key and the correlation as the other:

LeftAnti Join: __correlated_sq_1_value = __correlated_sq_1.id
               AND outer_t.grp = __correlated_sq_1.grp null_aware
  Projection: outer_t.id, outer_t.grp, Int32(3) AS __correlated_sq_1_value
    TableScan: outer_t
  SubqueryAlias: __correlated_sq_1
    ...

Multiple keys and a residual filter are both carried by the null-aware join itself after #25339, so no shape needs a fallback and the plan stays a single join — no three-valued decomposition, no extra scans of the subquery.

With this applied, all 18 of 18 shapes match DuckDB 1.5.2 and PostgreSQL 17.11.

Status

The change is 44 lines in decorrelate_predicate_subquery.rs plus tests, and a new correlated_not_in.slt covering the full matrix from this issue. Verified on #25339 + #25348 + this commit:

check	result
matrix	18/18 correct
full sqllogictest suite	pass, 521 files
datafusion-optimizer unit tests	853 pass
cargo fmt --all / cargo clippy	clean

It depends on both #25339 and #25348 being in history, so rather than post a three-PR stack I will open the PR once those two merge. The patch is attached here in the meantime.

---

Generated by Claude Code

25347-constant-correlated-not-in.patch

[AdamGS]

I think this is similar to #25024? I'll try and pick it back up later today.