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.

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

Group B — the NOT IN is one side of an OR (add OR g = 99)

Group C — the query asks for UNKNOWN directly ((... ) IS NULL)

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.