Wrong results: correlated `NOT IN` loses the correlation when it is an equality on the `IN` value column

[adriangb]

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

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

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 fix: correlated NOT IN with a non-equality correlation returns wrong results #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.

Checked against the open work on the same code

#25273 is the only open pull request that changes remove_duplicated_filter. It does not change this shape. A datafusion-cli built from its head ff6c625b09 gives the same three wrong results and the same plan as main:

+---+----+          Q1 (none)
| q | id |          Q2 -> 4
+---+----+          Q3 -> 2, 4, NULL
+---+----+

logical_plan
LeftAnti Join: t1.id = __correlated_sq_1.id null_aware
  TableScan: t1 projection=[id]
  SubqueryAlias: __correlated_sq_1
    TableScan: t2 projection=[id]

That pull request moves where the outer reference markers are removed: find_join_exprs keeps them, and remove_duplicated_filter removes them itself before it compares. The pair still matches, so the correlation is still dropped.

Related

• Wrong results: correlated NOT IN with a non-equality correlation returns no rows (null-aware LeftAnti join ignores the residual filter) #25336 — a correlated NOT IN with a non-equality correlation. Found while the review of fix: correlated NOT IN with a non-equality correlation returns wrong results #25339 checked the shapes around it.
• Wrong results: correlated NOT IN (subquery) ignores NULLs in the subquery #25347 — a correlated NOT IN with a constant value.
• fix: Correct ANY/ALL results for unaliased subqueries on the same table #25273 — changes remove_duplicated_filter for a different bug (When performing set comparison subqueries (such as > ANY / > ALL / = ANY, etc.) on the same table (without using aliases), silently returns wrong results (0 rows or all rows). #25258). The two changes touch the same function.