Wrong results: nullable constant `NOT IN (subquery)` returns every row when the subquery column is `NOT NULL`

[kosiew]

Related PR

#25348

Problem

If the outer value of NOT IN (subquery) is a constant that is, or can be,
NULL, and the subquery column is declared NOT NULL, DataFusion returns every
outer row. SQL three-valued logic says NULL NOT IN (non-empty set) is
UNKNOWN, so a WHERE clause must return no rows.

Tested with a datafusion-cli built from main at 3b16a3d0ee:

CREATE TABLE o(x INT NOT NULL) AS VALUES (1), (2);
CREATE TABLE i(id INT NOT NULL) AS VALUES (1), (3);
CREATE TABLE ie(id INT NOT NULL) AS SELECT * FROM (VALUES (1)) WHERE false;

Query (SELECT x FROM o WHERE ...)	Expected	Actual
CAST(NULL AS INT) NOT IN (SELECT id FROM i)	no rows	1, 2 ❌
NULL NOT IN (SELECT id FROM i)	no rows	1, 2 ❌
NULLIF(1, 1) NOT IN (SELECT id FROM i)	no rows	1, 2 ❌
CAST(NULL AS INT) NOT IN (SELECT id FROM i) OR x = 99	no rows	1, 2 ❌
NOT (CAST(NULL AS INT) NOT IN (SELECT id FROM i))	no rows	no rows ✅
CAST(NULL AS INT) NOT IN (SELECT id FROM ie) (empty set)	1, 2	1, 2 ✅
5 NOT IN (SELECT id FROM i)	1, 2	1, 2 ✅

The nullability of the outer table doesn't matter. The result is also wrong
when x is nullable, because only i.id appears in the join filter.

In the SELECT list, CAST(NULL AS INT) NOT IN (SELECT id FROM i) AS m
returns NULL correctly. That form goes through the rewrite_set_comparison
path and is not affected.

Root cause

This is a gap in the fix for #25340 (PR #25348, edc936f38b). It is not a
regression from that PR: the constant case was wrong in general before it.

In build_join (datafusion/optimizer/src/decorrelate_predicate_subquery.rs),
the constant path projects the outer value as a column only when
join_keys_may_be_null(&join_filter, ...) returns true (line ~527). That
helper collects the columns in the join filter and checks their schema
nullability. For Int32(NULL) = __correlated_sq_1.id the only column is
__correlated_sq_1.id, which is NOT NULL, so the helper returns false,
even though the constant itself is NULL.

The same helper then gates null_aware on both the LeftAnti path
(line ~639) and the LeftMark path (line ~603). So:

1. The constant is not projected, and the join is not null-aware.
2. push_down_filter moves the right-only filter Int32(NULL) = i.id into the
   subquery, and simplify_expressions folds it to Boolean(NULL).
3. The subquery becomes empty. For LeftAnti, every outer row survives. For
   LeftMark (the ... OR x = 99 form), EXPLAIN shows the right side as
   EmptyRelation, so the mark is false instead of NULL, and
   NOT mark is true.

EXPLAIN VERBOSE shows the anti-join steps:

decorrelate_predicate_subquery:  LeftAnti Join:  Filter: Int32(NULL) = __correlated_sq_1.id   (no null_aware)
push_down_filter:                LeftAnti Join:  /  Filter: Int32(NULL) = i.id  (inside subquery)
simplify_expressions:            Filter: Boolean(NULL)

Why it matters

Silent wrong results: rows that SQL requires to be filtered out are returned.
Typed NULL constants are common in generated SQL, for example parameter
placeholders bound to NULL, CAST(NULL AS ...) from ORMs, and NULLIF or
CASE over literals.

Invariant / desired behavior

For <value> NOT IN (<uncorrelated subquery>) with a constant <value>:

• Null-aware semantics (projecting the constant and setting null_aware) must
  apply whenever either side of the comparison can be NULL. That includes
  the constant expression itself, not only the columns it references.
• A NULL outer value against a non-empty subquery yields UNKNOWN: no row in
  WHERE, NULL as a mark.
• A NULL outer value against an empty subquery yields TRUE. This already works
  and must stay that way.

Proposed direction

Unvalidated: not implemented or tested. Confirm with the tests below.

Decide nullability of the constant from the expression, not from its column
references. At the constant-projection gate in build_join, also accept
value.nullable(left.schema())?:

&& (value.nullable(left.schema())?
    || join_keys_may_be_null(&join_filter, left.schema(), sub_query_alias.schema())?)

After projection, the new __correlated_sq_N_value column gets its
nullability from value, so the existing column-based checks at the
LeftAnti and LeftMark null_aware gates should then see a nullable column
without further changes. Verify that assumption rather than trusting it.

If #25474 is fixed by making join_keys_may_be_null itself use
expression nullability, that change should cover this issue too. In that case,
land both regression suites with it and close both issues.

Scope

In

• The uncorrelated constant NOT IN path in build_join, for LeftAnti and
  LeftMark.
• Typed NULL, untyped NULL, and nullable scalar constant expressions such as
  NULLIF(1, 1).

Out

• Non-constant outer expressions that are nullable over NOT NULL columns (see
  Wrong results: NOT IN (subquery) ignores NULLs from a nullable outer expression over NOT NULL columns #25474).
• Correlated NOT IN. The constant path deliberately excludes it because
  null-aware hash joins accept a single key.
• Constant-folding NULL NOT IN (subquery) into an emptiness check. This may be
  worth doing as an optimization, but the fix above is simpler.

Acceptance criteria

• Every ❌ row in the table above returns the expected result.
• Every ✅ row is unchanged.
• EXPLAIN for CAST(NULL AS INT) NOT IN (SELECT id FROM i) shows a
  null_aware LeftAnti join on the projected value column, and no filter
  pushed into the subquery.
• The results hold with target_partitions = 1 and > 1.

Tests / verification

• SLT in datafusion/sqllogictest/test_files/null_aware_anti_join.slt: typed
  NULL, untyped NULL and NULLIF(1, 1) against a NOT NULL subquery column,
  with both nullable and NOT NULL outer tables. Include the empty-subquery
  control and an EXPLAIN assertion.
• SLT in datafusion/sqllogictest/test_files/null_aware_mark_join.slt: the
  ... NOT IN (...) OR x = 99 form, plus the SELECT-list form as a control.
• Optimizer unit test in decorrelate_predicate_subquery.rs asserting
  null_aware for a NULL constant against a non-nullable subquery column.
• cargo test -p datafusion-optimizer and
  cargo test -p datafusion-sqllogictest --test sqllogictests -- null_aware.

Related

• Wrong results: constant NOT IN (subquery) in a WHERE clause ignores NULLs in the subquery #25340 / fix: NOT IN (subquery) with a constant value ignores NULLs in the subquery #25348: the constant NOT IN fix this issue extends.