Skip to content

Commit 6a3a84a

Browse files
committed
fix: correlated NOT IN ignored subquery NULLs
`x NOT IN (<subquery>)` is UNKNOWN when x is absent from the subquery result and that result holds a NULL, so a WHERE clause must drop the row. Correlated subqueries returned wrong results instead, and two shapes failed to plan. A null-aware hash join implements the three-valued semantics by scanning its equi-join keys for NULLs. That only works when the whole predicate becomes those keys. A correlation contributes a second key, and a non-equality correlation leaves a residual filter the NULL scan cannot see: * `DecorrelatePredicateSubquery` set `null_aware` on a `LeftAnti` join without checking for a residual filter, so the join answered with two-valued logic while ignoring the correlation, or failed to plan when the split left it with two keys or none. * The `LeftMark` path did check, but on failure it silently emitted a two-valued mark join, where a subquery NULL marks FALSE rather than UNKNOWN. `in_subquery_value_mark_join` already expresses `IN` as a three-valued CASE over three plain mark joins, which needs no null-aware join and places no shape restriction on the correlation. It was reachable only from a projection; this commit routes the predicates a null-aware join cannot carry to it as well. `build_join` now takes `strict_three_valued`, set for a `NOT IN` whose UNKNOWN is observable. When it cannot produce a join with correct three-valued semantics it returns `Ok(None)`, and the two callers fall back to the general rewrite. The single-key, filter-free shape still takes the null-aware fast path, so the plans that were already correct are unchanged. This fixes all 18 query shapes in the report, including the six it proposed to turn into planning errors. The `joins.slt` and `subquery.slt` plans this commit updates are the correlated shape: both dropped every row because the subquery held a NULL, even for outer rows whose correlated subquery is empty, where `NOT IN` is TRUE. The fallback plan is three mark joins where the null-aware path uses one. A correlated equality could instead use a null-aware `LeftMark` join, which already accepts a correlation key, and keep the single join; that is an optimization of the shapes fixed here, not a correctness gap. Closes apache#25347. Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01VCeMPyJNgAiFpGXaz5CxF3
1 parent f8bce4a commit 6a3a84a

5 files changed

Lines changed: 375 additions & 34 deletions

File tree

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 113 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -129,7 +129,23 @@ impl OptimizerRule for DecorrelatePredicateSubquery {
129129
match build_join_top(&subquery, &cur_input, config.alias_generator())?
130130
{
131131
Some(plan) => cur_input = plan,
132-
// If the subquery can not be converted to a Join, reconstruct the subquery expression and add it to the Filter
132+
// Only a `NOT IN` reaches this arm with a three-valued
133+
// predicate the anti join could not carry (see
134+
// `build_join`); the general rewrite expresses it
135+
// without a null-aware join. Every other `None` means
136+
// the subquery is not decorrelatable at all, so the
137+
// expression goes back into the filter as before.
138+
None if subquery.where_in_expr.is_some() && subquery.negated => {
139+
let (plan, expr_without_subqueries) =
140+
rewrite_inner_subqueries(
141+
cur_input,
142+
subquery.expr(),
143+
config,
144+
true,
145+
)?;
146+
cur_input = plan;
147+
other_exprs.push(expr_without_subqueries);
148+
}
133149
None => other_exprs.push(subquery.expr()),
134150
}
135151
}
@@ -206,7 +222,26 @@ fn rewrite_inner_subqueries(
206222
.map_or(plan_err!("single expression required."), |output_expr| {
207223
Ok(Expr::eq(*expr.clone(), output_expr))
208224
})?;
209-
mark_join(&cur_input, &subquery, Some(&in_predicate), negated, alias)?
225+
match mark_join(
226+
&cur_input,
227+
&subquery,
228+
Some(&in_predicate),
229+
negated,
230+
alias,
231+
)? {
232+
rewritten @ Some(_) => rewritten,
233+
// The mark join cannot carry this predicate's three-valued
234+
// semantics (see `build_join`), so materialize the `IN`
235+
// value instead: that form distinguishes UNKNOWN from FALSE
236+
// without needing a null-aware join.
237+
None => in_subquery_value_mark_join(
238+
&cur_input,
239+
&subquery,
240+
*expr.clone(),
241+
negated,
242+
alias,
243+
)?,
244+
}
210245
};
211246
match rewritten {
212247
Some((plan, exists_expr)) => {
@@ -371,6 +406,7 @@ fn build_join_top(
371406
in_predicate_opt.as_ref(),
372407
join_type,
373408
subquery_alias,
409+
query_info.negated && in_predicate_opt.is_some(),
374410
)
375411
}
376412

@@ -401,10 +437,15 @@ fn mark_join(
401437
let exists_col = Expr::Column(Column::new(Some(alias.clone()), "mark"));
402438
let exists_expr = if negated { !exists_col } else { exists_col };
403439

404-
Ok(
405-
build_join(left, subquery, in_predicate_opt, JoinType::LeftMark, alias)?
406-
.map(|plan| (plan, exists_expr)),
407-
)
440+
Ok(build_join(
441+
left,
442+
subquery,
443+
in_predicate_opt,
444+
JoinType::LeftMark,
445+
alias,
446+
negated && in_predicate_opt.is_some(),
447+
)?
448+
.map(|plan| (plan, exists_expr)))
408449
}
409450

410451
/// Check if join keys in the join filter may contain NULL values
@@ -440,12 +481,19 @@ fn join_keys_may_be_null(
440481
Ok(false)
441482
}
442483

484+
/// `strict_three_valued` marks a predicate whose UNKNOWN result is observable
485+
/// — a `NOT IN`, whose negation turns UNKNOWN into a dropped row rather than a
486+
/// kept one. For those, returning a join that cannot carry null-aware semantics
487+
/// would silently answer with two-valued logic, so this function returns
488+
/// `Ok(None)` instead and the caller falls back to the general three-valued
489+
/// rewrite (see [`in_subquery_value_mark_join`]).
443490
fn build_join(
444491
left: &LogicalPlan,
445492
subquery: &LogicalPlan,
446493
in_predicate_opt: Option<&Expr>,
447494
join_type: JoinType,
448495
alias: String,
496+
strict_three_valued: bool,
449497
) -> Result<Option<LogicalPlan>> {
450498
let mut pull_up = PullUpCorrelatedExpr::new()
451499
.with_in_predicate_opt(in_predicate_opt.cloned())
@@ -609,6 +657,21 @@ fn build_join(
609657
right_projected.schema(),
610658
)?;
611659

660+
// Without `null_aware` the mark column is two-valued: a subquery NULL
661+
// marks FALSE rather than UNKNOWN. `NOT IN` then keeps a row it must
662+
// drop, so hand the predicate to the general three-valued rewrite. Only
663+
// nullable join keys can produce the UNKNOWN in the first place.
664+
if strict_three_valued
665+
&& !null_aware
666+
&& join_keys_may_be_null(
667+
&join_filter,
668+
left.schema(),
669+
right_projected.schema(),
670+
)?
671+
{
672+
return Ok(None);
673+
}
674+
612675
let new_plan = LogicalPlanBuilder::from(left.clone())
613676
.join_detailed_with_options(
614677
right_projected,
@@ -636,10 +699,29 @@ fn build_join(
636699
//
637700
// Additionally, if the join keys are non-nullable on both sides, we don't need
638701
// null-aware semantics because NULLs cannot exist in the data.
639-
let null_aware = join_type == JoinType::LeftAnti
702+
let needs_null_aware = join_type == JoinType::LeftAnti
640703
&& in_predicate_opt.is_some()
641704
&& join_keys_may_be_null(&join_filter, left.schema(), sub_query_alias.schema())?;
642705

706+
// `HashJoinExec` implements a null-aware anti join by scanning a single
707+
// equi-join key for NULLs. A correlation predicate contributes a second key
708+
// and a non-equality correlation leaves a residual filter, and the NULL scan
709+
// sees neither: the join would answer with two-valued logic. Only the
710+
// single-key, filter-free shape is safe here; the rest goes to the general
711+
// three-valued rewrite.
712+
let null_aware = needs_null_aware && {
713+
let (equi_keys, residual_filter) = split_eq_and_noneq_join_predicate(
714+
join_filter.clone(),
715+
left.schema(),
716+
sub_query_alias.schema(),
717+
)?;
718+
let expressible = equi_keys.len() == 1 && residual_filter.is_none();
719+
if !expressible && strict_three_valued {
720+
return Ok(None);
721+
}
722+
expressible
723+
};
724+
643725
// join our sub query into the main plan
644726
let new_plan = if null_aware {
645727
// Use join_detailed_with_options to set null_aware flag
@@ -1495,11 +1577,12 @@ mod tests {
14951577
)
14961578
}
14971579

1498-
/// The same rewrite must not fire for a correlated subquery: the
1499-
/// correlation predicate is a second equi-join key, and null-aware hash
1500-
/// joins accept only one.
1580+
/// A correlated subquery cannot use the projected-constant key: the
1581+
/// correlation predicate is a second equi-join key and a null-aware anti
1582+
/// join accepts only one. The predicate is three-valued, so the rule falls
1583+
/// back to the general rewrite instead of emitting a two-valued join.
15011584
#[test]
1502-
fn constant_not_in_correlated_subquery_is_not_rewritten() -> Result<()> {
1585+
fn constant_not_in_correlated_subquery_uses_three_valued_rewrite() -> Result<()> {
15031586
let outer_scan = nullable_scalar_mark_scan("outer_t")?;
15041587
let inner_scan = nullable_scalar_mark_scan("inner_t")?;
15051588

@@ -1519,11 +1602,25 @@ mod tests {
15191602
assert_optimized_plan_equal!(
15201603
plan,
15211604
@r"
1522-
LeftAnti Join: Filter: Int32(3) = __correlated_sq_1.id AND outer_t.grp = __correlated_sq_1.grp null_aware [id:Int32;N, grp:Int32;N]
1523-
TableScan: outer_t [id:Int32;N, grp:Int32;N]
1524-
SubqueryAlias: __correlated_sq_1 [id:Int32;N, grp:Int32;N]
1525-
Projection: inner_t.id, inner_t.grp [id:Int32;N, grp:Int32;N]
1526-
TableScan: inner_t [id:Int32;N, grp:Int32;N]
1605+
Projection: outer_t.id, outer_t.grp [id:Int32;N, grp:Int32;N]
1606+
Filter: NOT CASE WHEN __correlated_sq_2.mark THEN Boolean(true) WHEN __correlated_sq_3.mark OR Int32(3) IS NULL AND __correlated_sq_4.mark THEN Boolean(NULL) ELSE Boolean(false) END [id:Int32;N, grp:Int32;N, mark:Boolean;N, mark:Boolean;N, mark:Boolean;N]
1607+
LeftMark Join: Filter: outer_t.grp = __correlated_sq_4.grp [id:Int32;N, grp:Int32;N, mark:Boolean;N, mark:Boolean;N, mark:Boolean;N]
1608+
LeftMark Join: Filter: outer_t.grp = __correlated_sq_3.grp [id:Int32;N, grp:Int32;N, mark:Boolean;N, mark:Boolean;N]
1609+
LeftMark Join: Filter: Int32(3) = __correlated_sq_2.id AND outer_t.grp = __correlated_sq_2.grp [id:Int32;N, grp:Int32;N, mark:Boolean;N]
1610+
TableScan: outer_t [id:Int32;N, grp:Int32;N]
1611+
Projection: __correlated_sq_2.id, __correlated_sq_2.grp [id:Int32;N, grp:Int32;N]
1612+
SubqueryAlias: __correlated_sq_2 [id:Int32;N, grp:Int32;N]
1613+
Projection: inner_t.id, inner_t.grp [id:Int32;N, grp:Int32;N]
1614+
TableScan: inner_t [id:Int32;N, grp:Int32;N]
1615+
Projection: __correlated_sq_3.grp [grp:Int32;N]
1616+
SubqueryAlias: __correlated_sq_3 [id:Int32;N, grp:Int32;N]
1617+
Filter: inner_t.id IS NULL [id:Int32;N, grp:Int32;N]
1618+
Projection: inner_t.id, inner_t.grp [id:Int32;N, grp:Int32;N]
1619+
TableScan: inner_t [id:Int32;N, grp:Int32;N]
1620+
Projection: __correlated_sq_4.grp [grp:Int32;N]
1621+
SubqueryAlias: __correlated_sq_4 [id:Int32;N, grp:Int32;N]
1622+
Projection: inner_t.id, inner_t.grp [id:Int32;N, grp:Int32;N]
1623+
TableScan: inner_t [id:Int32;N, grp:Int32;N]
15271624
"
15281625
)
15291626
}

0 commit comments

Comments
 (0)