adriangb opened a new issue, #25336:
URL: https://github.com/apache/datafusion/issues/25336
### 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:
```sql
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:
```sql
-- 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()`:
```rust
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:
```rust
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:
```rust
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:
```rust
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 https://github.com/apache/datafusion/pull/19635. The
`LeftMark` residual check was added later, in commit `bed9dcd548`, from
https://github.com/apache/datafusion/pull/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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
