Wrong results: correlated NOT IN with a non-equality correlation returns no rows (null-aware LeftAnti join ignores the residual filter)

[adriangb]

Describe the bug

A correlated NOT IN subquery gives wrong results when the correlation is a non-equality predicate.

DataFusion drops every row. The correct answer has rows. DuckDB 1.5.2 and PostgreSQL 17.11 both give the correct answer.

The optimizer rewrites the query to a null_aware LeftAnti hash join that keeps the correlated predicate as a residual join filter. At run time, a NULL key on the subquery side makes the join emit nothing. The residual filter is never applied to that NULL row. In this example the residual filter removes the NULL row for every outer row, so the NULL must not affect the result.

There is a second symptom with the same cause. When the IN predicate is inside a disjunction, the planner uses a LeftMark join. That join is correctly not null_aware when a residual filter is present, but the non null-aware fallback then gives false instead of UNKNOWN for a NULL key. NOT false is true, so an extra NULL row appears in the output.

This is a silent wrong-results bug. There is no error and no warning.

Tested on commit add66e424f (datafusion-cli 55.1.0, release build).

To Reproduce

DDL:

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);

Queries:

-- Q1
SELECT id FROM t1 WHERE id NOT IN (SELECT t2.id FROM t2 WHERE t2.z < t1.z) ORDER BY id;

-- Q2
SELECT id FROM t1 WHERE NOT (id IN (SELECT t2.id FROM t2 WHERE t2.z < t1.z)) ORDER BY id;

-- Q3
SELECT id FROM t1 WHERE NOT (id IN (SELECT t2.id FROM t2 WHERE t2.z < t1.z)) OR id = 4 ORDER BY id;

-- CTL (control, the positive form of Q1)
SELECT id FROM t1 WHERE id IN (SELECT t2.id FROM t2 WHERE t2.z < t1.z) ORDER BY id;

-- Q4 (uncorrelated residual, NULL row removed by the residual)
SELECT id FROM t1 WHERE id NOT IN (SELECT t2.id FROM t2 WHERE t2.z < 40) ORDER BY id;

-- Q5 (uncorrelated residual, NULL row kept by the residual)
SELECT id FROM t1 WHERE id NOT IN (SELECT t2.id FROM t2 WHERE t2.z < 100) ORDER BY id;

-- Q6 (correlated residual, NULL row kept for every outer row)
SELECT id FROM t1 WHERE id NOT IN (SELECT t2.id FROM t2 WHERE t2.z > t1.z) ORDER BY id;

Results:

Query	DataFusion add66e424f	DuckDB 1.5.2	PostgreSQL 17.11	Correct
Q1	(no rows)	2, 4	2, 4	2, 4
Q2	(no rows)	2, 4	2, 4	2, 4
Q3	2, 4, NULL	2, 4	2, 4	2, 4
CTL	1	1	1	1
Q4	2, 4	2, 4	2, 4	2, 4
Q5	(no rows)	(no rows)	(no rows)	(no rows)
Q6	(no rows)	(no rows)	(no rows)	(no rows)

Q1, Q2 and Q3 are wrong. The control and Q4, Q5 and Q6 are correct.

Q5 and Q6 show that the null-aware behaviour is correct when the NULL row truly is a member of the subquery result. Q4 shows that an uncorrelated residual is safe, because the optimizer pushes it into the subquery and no residual join filter remains.

Manual check of Q1 for id = 2. The subquery for t1.z = 20 is SELECT t2.id FROM t2 WHERE t2.z < 20, which is {1}. 2 NOT IN {1} is true, so id = 2 must be in the output. The maximum t1.z is 40, so the row t2.id = NULL, t2.z = 50 never satisfies t2.z < t1.z. That NULL is not a member of the subquery result for any outer row.

Expected behavior

Q1 and Q2 return 2 and 4. Q3 returns 2 and 4.

Additional context

EXPLAIN for Q1 on add66e424f:

logical_plan
Projection: t1.id
  LeftAnti Join: t1.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < t1.z null_aware
    TableScan: t1 projection=[id, z]
    SubqueryAlias: __correlated_sq_1
      TableScan: t2 projection=[id, z]
physical_plan
HashJoinExec: mode=CollectLeft, join_type=LeftAnti, on=[(id@0, id@0)], filter=z@1 < z@0, projection=[id@0], null_aware
  DataSourceExec: partitions=1, partition_sizes=[1]
  DataSourceExec: partitions=1, partition_sizes=[1]

EXPLAIN for Q3 on add66e424f:

logical_plan
Projection: t1.id
  Filter: NOT __correlated_sq_1.mark OR t1.id = Int32(4)
    Projection: t1.id, __correlated_sq_1.mark
      LeftMark Join: t1.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < t1.z
        TableScan: t1 projection=[id, z]
        SubqueryAlias: __correlated_sq_1
          TableScan: t2 projection=[id, z]

Suspected root cause

The null_aware decision is made in build_join in datafusion/optimizer/src/decorrelate_predicate_subquery.rs.

The LeftMark path at line 452 first checks that the join predicate has no residual part. It calls split_eq_and_noneq_join_predicate and requires residual_filter.is_none():

let mark_filter_is_hashable_only =
    if join_type == JoinType::LeftMark && in_predicate_opt.is_some() {
        let (_, residual_filter) = split_eq_and_noneq_join_predicate(...)?;
        residual_filter.is_none()
    } else {
        false
    };

The LeftAnti path at line 504 has no such check. It only tests key nullability:

let null_aware = join_type == JoinType::LeftAnti
    && in_predicate_opt.is_some()
    && join_keys_may_be_null(&join_filter, left.schema(), sub_query_alias.schema())?;

So a LeftAnti join keeps null_aware even when the correlated predicate stays as a residual join filter.

The execution side cannot handle that combination. In datafusion/physical-plan/src/joins/hash_join/stream.rs, null_aware_skip_probe_batch at line 1217 looks only at the join key column of the probe batch:

let probe_key_column = &state.values[0];
let probe_has_null = match mode {
    NullAwareMode::LeftAnti if !has_filter => {
        probe_key_column.logical_null_count() > 0
    }
    _ => probe_key_column.null_count() > 0,
};
left_data.record_probe_batch(state.batch.num_rows() > 0, probe_has_null);
mode == NullAwareMode::LeftAnti && left_data.probe_side_has_null_hint()

The has_filter flag only selects logical_null_count or null_count. The residual filter itself is never evaluated. A NULL in t2.id therefore sets the shared "probe side has NULL" flag, and the whole probe batch is skipped.

null_aware_left_anti_final_indices at line 1275 then drops everything:

if probe_summary.has_null {
    return (UInt64Array::new_null(0), UInt32Array::new_null(0));
}

This is correct for a plain NOT IN with no residual, because one NULL in the subquery result makes the predicate UNKNOWN for every outer row. It is wrong with a residual filter, because the residual decides per outer row whether the NULL row is in the subquery result at all.

The LeftAnti null_aware decision in the decorrelation rule was added in commit 4c67d02089, from #19635. The LeftMark residual check was added later, in commit bed9dcd548, from #21585. The residual guard was not applied to the LeftAnti path at that time.

Fix sketch

The small fix is to gate the LeftAnti null_aware decision on the same condition as the LeftMark path. Compute split_eq_and_noneq_join_predicate for the anti case too, and set null_aware only when there is no residual filter. This makes Q1 and Q2 fall back to a plain anti join plus the existing correct handling, at the cost of the null-aware optimization for correlated NOT IN with a non-equality correlation. The alternative and larger fix is to make the null-aware execution residual-aware, so that a probe row with a NULL key only poisons the outer rows for which the residual filter is true. That needs the per-outer-row evaluation that the current shared-flag design does not have. Q3 needs a separate change on the LeftMark side, because the non null-aware mark column gives false where SQL requires UNKNOWN.