Wrong results: `NOT IN (subquery)` ignores NULLs from a nullable outer expression over `NOT NULL` columns

[kosiew]

Related PR

#25348

Problem

If the outer side of NOT IN (subquery) is an expression that can produce
NULL, but every column it references is declared NOT NULL, the decorrelated
join is not null-aware. Rows where the expression is NULL are then returned
instead of being filtered out as UNKNOWN.

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

CREATE TABLE o(x INT NOT NULL) AS VALUES (1), (2);
CREATE TABLE on2(x INT) AS VALUES (1), (2);           -- same data, nullable column
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;

For every row below the outer expression evaluates to NULL.

Query	Expected	Actual
SELECT x FROM o WHERE (CASE WHEN x > 100 THEN 1 END) NOT IN (SELECT id FROM i)	no rows	1, 2 ❌
SELECT x FROM o WHERE NULLIF(x, x) NOT IN (SELECT id FROM i)	no rows	1, 2 ❌
SELECT x FROM o WHERE x + CAST(NULL AS INT) NOT IN (SELECT id FROM i)	no rows	1, 2 ❌
SELECT x FROM o WHERE (CASE WHEN x > 100 THEN 1 END) NOT IN (SELECT id FROM i) OR x = 99	no rows	1, 2 ❌
same CASE query over on2 (nullable x)	no rows	no rows ✅
CASE query against empty ie	1, 2	1, 2 ✅
SELECT x FROM o WHERE x NOT IN (SELECT CASE WHEN id > 100 THEN id END FROM i)	no rows	no rows ✅

The only difference between the failing CASE query and the on2 control is
the declared nullability of x. The expression evaluates to NULL in both.

The subquery side is already handled correctly (last row). Subquery
expressions are projected into the __correlated_sq_N alias, so their
nullability reaches the schema as a column.

Root cause

join_keys_may_be_null in
datafusion/optimizer/src/decorrelate_predicate_subquery.rs (added in #19635)
decides whether NOT IN needs null-aware semantics by collecting the
columns in the join filter and checking each field's schema nullability.
An outer expression is never projected into a column, so its own nullability is
never considered. Only the nullability of the columns it references is.

Expressions that are nullable over non-nullable inputs include CASE without
ELSE, NULLIF, arithmetic with a NULL operand, and scalar functions that can
return NULL. For all of them, the helper returns false and:

• LeftAnti path (line ~639): a plain anti join is built. The physical plan is
  HashJoinExec: join_type=RightAnti, on=[(i.id, CASE WHEN ... END)] without
  null_aware, so an outer row with a NULL key finds no match and is emitted.
• LeftMark path (line ~603): the mark join is not null-aware, so the mark is
  false instead of NULL, and NOT mark OR ... keeps the row.

By code history this bug predates #25348. The helper and both gates come from
#19635. It was not bisected against an older build.

Why it matters

Silent wrong results. The pattern is realistic: CASE, NULLIF and
COALESCE-like expressions over NOT NULL columns are common in NOT IN
predicates, and schemas from Parquet or CREATE TABLE ... NOT NULL often
declare columns non-nullable.

Invariant / desired behavior

For NOT IN (subquery), the decision to use null-aware semantics must be
based on whether each side of the comparison, as an expression, can be
NULL. The nullability of the columns an expression references is not enough.
A nullable expression over non-nullable columns must get the same result as
the same values in a nullable column.

Proposed direction

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

Replace the column walk in join_keys_may_be_null with expression-level
nullability of the IN equality operands:

• For each a = b conjunct produced from the IN predicate, evaluate
  a.nullable(left_schema) and b.nullable(right_schema), choosing the
  schema each operand resolves against.
• If an operand's nullability can't be determined (for example, it mixes both
  schemas), fall back to true. Treating a key as nullable costs a null-aware
  join; treating it as non-nullable gives wrong results.

This is the earliest boundary where the bad decision is made, and both the
LeftAnti and LeftMark gates call it. It should also cover #25473,
because Int32(NULL).nullable(..) is true.

Risks to check while implementing:

• More queries will take the null-aware path. Confirm the physical planner
  accepts a null-aware hash join whose left key is a non-column expression. A
  non-null-aware join with such a key already plans with a ProjectionExec.
• Null-aware hash joins accept a single key. Check that correlated NOT IN with
  a nullable outer expression (an equality key plus a correlation key) either
  stays correct or is kept off the null-aware path, as it is today for
  nullable columns.
• Watch for plan changes in existing EXPLAIN SLTs and benchmark queries
  (TPC-H Q16 uses NOT IN) where operands become nullable-by-expression.

Scope

In

• join_keys_may_be_null and its callers in build_join (the LeftAnti and
  LeftMark null-aware gates).
• Uncorrelated NOT IN with a nullable outer expression over NOT NULL
  columns.

Out

• The constant-projection gate for NULL constants (Wrong results: nullable constant NOT IN (subquery) returns every row when the subquery column is NOT NULL #25473). It is fixed
  here only if this change naturally covers it.
• Adding null-aware support for multi-key or residual-filter joins.
• NOT EXISTS, which uses two-valued logic and is correct as is.

Acceptance criteria

• Every ❌ row in the table above returns the expected result.
• Every ✅ row is unchanged, including the empty-subquery case (1, 2).
• EXPLAIN for the CASE query on o shows a null_aware anti join,
  matching the on2 plan shape.
• Queries whose NOT IN operands are provably non-nullable expressions
  (for example x + 1 over NOT NULL x) still plan a non-null-aware join.
• No unexplained plan changes in the existing SLT EXPLAIN output or the
  TPC-H plans.

Tests / verification

• SLT in datafusion/sqllogictest/test_files/null_aware_anti_join.slt: CASE
  without ELSE, NULLIF(x, x) and x + NULL over a NOT NULL column, each
  compared with the same query over a nullable column, plus an 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.
• Optimizer unit tests in decorrelate_predicate_subquery.rs: null-aware for a
  nullable expression over a non-nullable column, and not null-aware for
  x + 1 over non-nullable x.
• cargo test -p datafusion-optimizer,
  cargo test -p datafusion-sqllogictest --test sqllogictests, which includes the TPC-H
  plan SLTs under test_files/tpch.

Related

• feat: Add null-aware anti join support #19635: introduced join_keys_may_be_null and null-aware anti joins.
• Wrong results: nullable constant NOT IN (subquery) returns every row when the subquery column is NOT NULL #25473: the same helper misses nullable constants. A fix here likely
  covers it.