Skip to content

Commit 78b49ba

Browse files
adriangbclaude
andcommitted
fix: keep the IN equality as on[0] for a constant correlated NOT IN
A null-aware hash join reads `on[0]` as the `NOT IN` value key and `on[1..]` as correlation scope keys. Decorrelation projected a constant value expression as an outer column only for an uncorrelated subquery, so a correlated one kept `<constant> = __sq.col` in the join filter and gave `on[0]` to the correlation. The join then applied the value-key NULL rules to the correlation key and returned wrong rows. CREATE TABLE t3(z INT) AS VALUES (10), (NULL), (7); CREATE TABLE t4(id INT, z INT) AS VALUES (NULL, 10), (1, 99), (2, 7); SELECT z FROM t3 WHERE 1 NOT IN (SELECT t4.id FROM t4 WHERE t4.z = t3.z) ORDER BY z; returned `7, 10`; DuckDB and the SQL standard give `7, NULL`. Project the constant for a correlated subquery too, and keep the `IN` equality as the leading conjunct so that it stays `on[0]`. This also removes the planning gap for a constant value with a non-equality correlation, which had no equi-join key at all. The projection is now taken only when the join really ends up null-aware, so a positive `IN` mark join keeps pushing the equality into the subquery. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 283b8ca commit 78b49ba

2 files changed

Lines changed: 105 additions & 43 deletions

File tree

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 46 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -525,29 +525,15 @@ fn build_join(
525525
replace_qualified_name(filter, &all_correlated_cols, &alias).map(Some)
526526
})?;
527527

528-
// The outer value expression of an `IN`/`NOT IN` predicate whose join filter
529-
// is nothing but that predicate, recorded together with the subquery column
530-
// it is compared against and a name for the column it can be projected as.
531-
// Correlated subqueries are excluded on purpose: their correlation predicate
532-
// is a second join key, and null-aware hash joins accept only a single key.
528+
// The outer value expression of an `IN`/`NOT IN` predicate, recorded together
529+
// with the subquery column it is compared against, a name for the column it
530+
// can be projected as, and the correlation predicates that share the join
531+
// filter with it.
533532
let mut in_value_expr = None;
534533

535534
let mut join_filter = match (join_filter_opt, in_predicate_opt.cloned()) {
536535
(
537-
Some(join_filter),
538-
Some(Expr::BinaryExpr(BinaryExpr {
539-
left,
540-
op: Operator::Eq,
541-
right,
542-
})),
543-
) => {
544-
let right_col = create_col_from_scalar_expr(&right, alias)?;
545-
let in_predicate = Expr::eq(left.deref().clone(), Expr::Column(right_col));
546-
in_predicate.and(join_filter)
547-
}
548-
(Some(join_filter), _) => join_filter,
549-
(
550-
_,
536+
correlation_opt,
551537
Some(Expr::BinaryExpr(BinaryExpr {
552538
left,
553539
op: Operator::Eq,
@@ -557,10 +543,19 @@ fn build_join(
557543
let value_name = format!("{alias}_value");
558544
let right_col = create_col_from_scalar_expr(&right, alias)?;
559545
let value = left.deref().clone();
560-
in_value_expr = Some((value.clone(), right_col.clone(), value_name));
546+
let in_predicate = Expr::eq(value.clone(), Expr::Column(right_col.clone()));
547+
// The `IN` equality is the leading conjunct so that it becomes
548+
// `on[0]`, the key position a null-aware hash join reads as the
549+
// `NOT IN` value key (see `HashJoinExec::null_aware`).
550+
let join_filter = match &correlation_opt {
551+
Some(correlation) => in_predicate.and(correlation.clone()),
552+
None => in_predicate,
553+
};
554+
in_value_expr = Some((value, right_col, value_name, correlation_opt));
561555

562-
Expr::eq(value, Expr::Column(right_col))
556+
join_filter
563557
}
558+
(Some(join_filter), _) => join_filter,
564559
(None, None) => lit(true),
565560
_ => return Ok(None),
566561
};
@@ -572,12 +567,21 @@ fn build_join(
572567
// right-only, so `push_down_filter` moves it into the subquery and drops the
573568
// very NULLs that make `NOT IN` UNKNOWN, and a join without equi-join keys
574569
// is planned as a nested loop join, which has no null-aware implementation.
570+
// A correlated subquery hits a third problem: its correlation predicate is a
571+
// valid equi-join key, so it takes `on[0]`, the position the null-aware hash
572+
// join reads as the `NOT IN` value key.
575573
// Projecting the constant as a column of the outer side turns the predicate
576-
// into a real equi-join key so the null-aware hash join handles it.
574+
// into a real equi-join key, which fixes all three.
575+
// The projection only pays for itself on a join that ends up null-aware, so
576+
// its guard repeats the `null_aware` conditions below.
577577
let mut projected_left = None;
578-
if let Some((value, right_col, mut value_name)) = in_value_expr
578+
if let Some((value, right_col, mut value_name, correlation_opt)) = in_value_expr
579579
&& value.column_refs().is_empty()
580-
&& matches!(join_type, JoinType::LeftAnti | JoinType::LeftMark)
580+
&& match join_type {
581+
JoinType::LeftAnti => true,
582+
JoinType::LeftMark => needs_null_aware_mark,
583+
_ => false,
584+
}
581585
&& join_keys_may_be_null(&join_filter, left.schema(), sub_query_alias.schema())?
582586
{
583587
// The projected column is unqualified, so a left field that already has
@@ -598,9 +602,13 @@ fn build_join(
598602
.project(projections)?
599603
.build()?,
600604
);
601-
// `in_value_expr` is only set when the `IN` equality is the whole join
602-
// filter, so it can simply be rebuilt against the projected column.
603-
join_filter = Expr::eq(Expr::Column(value_col), Expr::Column(right_col));
605+
// Rebuild the `IN` equality against the projected column, keeping it
606+
// ahead of the correlation predicates so that it stays `on[0]`.
607+
let in_predicate = Expr::eq(Expr::Column(value_col), Expr::Column(right_col));
608+
join_filter = match correlation_opt {
609+
Some(correlation) => in_predicate.and(correlation),
610+
None => in_predicate,
611+
};
604612
}
605613
let left = projected_left.as_ref().unwrap_or(left);
606614

@@ -1537,11 +1545,11 @@ mod tests {
15371545
)
15381546
}
15391547

1540-
/// The same rewrite must not fire for a correlated subquery: the
1541-
/// correlation predicate is a second equi-join key, and null-aware hash
1542-
/// joins accept only one.
1548+
/// The same rewrite fires for a correlated subquery, where it also keeps the
1549+
/// `IN` equality ahead of the correlation predicate so that the equality
1550+
/// stays `on[0]`, the null-aware hash join's value key.
15431551
#[test]
1544-
fn constant_not_in_correlated_subquery_is_not_rewritten() -> Result<()> {
1552+
fn constant_not_in_correlated_subquery_is_rewritten() -> Result<()> {
15451553
let outer_scan = nullable_scalar_mark_scan("outer_t")?;
15461554
let inner_scan = nullable_scalar_mark_scan("inner_t")?;
15471555

@@ -1561,11 +1569,13 @@ mod tests {
15611569
assert_optimized_plan_equal!(
15621570
plan,
15631571
@r"
1564-
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]
1565-
TableScan: outer_t [id:Int32;N, grp:Int32;N]
1566-
SubqueryAlias: __correlated_sq_1 [id:Int32;N, grp:Int32;N]
1567-
Projection: inner_t.id, inner_t.grp [id:Int32;N, grp:Int32;N]
1568-
TableScan: inner_t [id:Int32;N, grp:Int32;N]
1572+
Projection: outer_t.id, outer_t.grp [id:Int32;N, grp:Int32;N]
1573+
LeftAnti Join: Filter: __correlated_sq_1_value = __correlated_sq_1.id AND outer_t.grp = __correlated_sq_1.grp null_aware [id:Int32;N, grp:Int32;N, __correlated_sq_1_value:Int32]
1574+
Projection: outer_t.id, outer_t.grp, Int32(3) AS __correlated_sq_1_value [id:Int32;N, grp:Int32;N, __correlated_sq_1_value:Int32]
1575+
TableScan: outer_t [id:Int32;N, grp:Int32;N]
1576+
SubqueryAlias: __correlated_sq_1 [id:Int32;N, grp:Int32;N]
1577+
Projection: inner_t.id, inner_t.grp [id:Int32;N, grp:Int32;N]
1578+
TableScan: inner_t [id:Int32;N, grp:Int32;N]
15691579
"
15701580
)
15711581
}

‎datafusion/sqllogictest/test_files/null_aware_anti_join.slt‎

Lines changed: 59 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -641,26 +641,78 @@ ORDER BY 1;
641641
statement ok
642642
DROP TABLE naconst_clash;
643643

644-
# A constant value expression with a non-equality correlation leaves the
645-
# null-aware join without any equi-join key. Only `HashJoinExec` implements
646-
# null-aware semantics and it needs a key, so the planner reports the gap
647-
# instead of falling back to a nested loop join that ignores the NULLs and
648-
# silently returns wrong results.
644+
# The rewrite also fires for a correlated subquery. The projected value column
645+
# is the first equi-join key, which is the position the null-aware hash join
646+
# reads as the `NOT IN` value key; the correlation follows it.
649647
statement ok
650648
CREATE TABLE naconst_corr_t1(id INT, g INT) AS VALUES (1, 1), (2, 2);
651649

652650
statement ok
653651
CREATE TABLE naconst_corr_t2(id INT, g INT) AS VALUES (1, 1), (NULL, 2);
654652

655-
query error DataFusion error: Error during planning: null_aware LeftAnti join requires equi\-join keys, but the join has none
656-
SELECT id FROM naconst_corr_t1 WHERE 3 NOT IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g > naconst_corr_t1.g);
653+
# A non-equality correlation stays in the join filter. Row (1, 1) sees the NULL
654+
# of (NULL, 2), so its `NOT IN` is UNKNOWN; row (2, 2) sees an empty subquery,
655+
# so its `NOT IN` is TRUE. Expected results verified with DuckDB.
656+
query I
657+
SELECT id FROM naconst_corr_t1 WHERE 3 NOT IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g > naconst_corr_t1.g) ORDER BY id;
658+
----
659+
2
660+
661+
query I
662+
SELECT id FROM naconst_corr_t1 WHERE NOT (3 IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g > naconst_corr_t1.g)) ORDER BY id;
663+
----
664+
2
665+
666+
# An equality correlation becomes a second equi-join key. Without the rewrite
667+
# the correlation would take the first key position and the join would apply
668+
# the value-key NULL rules to it.
669+
query II
670+
SELECT id, g FROM naconst_corr_t1 WHERE 3 NOT IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g = naconst_corr_t1.g) ORDER BY id;
671+
----
672+
1 1
673+
674+
# With `1` as the value, row (1, 1) is FALSE rather than TRUE, so no row survives.
675+
query II
676+
SELECT id, g FROM naconst_corr_t1 WHERE 1 NOT IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g = naconst_corr_t1.g) ORDER BY id;
677+
----
657678

658679
statement ok
659680
DROP TABLE naconst_corr_t1;
660681

661682
statement ok
662683
DROP TABLE naconst_corr_t2;
663684

685+
# https://github.com/apache/datafusion/pull/25339#issuecomment-5738402844
686+
# The outer row with a NULL correlation value matches no subquery row at all,
687+
# so its `NOT IN` is TRUE. Expected results verified with DuckDB.
688+
statement ok
689+
CREATE TABLE naconst_corr_t3(z INT) AS VALUES (10), (NULL), (7);
690+
691+
statement ok
692+
CREATE TABLE naconst_corr_t4(id INT, z INT) AS VALUES (NULL, 10), (1, 99), (2, 7);
693+
694+
query I
695+
SELECT z FROM naconst_corr_t3 WHERE 1 NOT IN (SELECT naconst_corr_t4.id FROM naconst_corr_t4 WHERE naconst_corr_t4.z = naconst_corr_t3.z) ORDER BY z;
696+
----
697+
7
698+
NULL
699+
700+
query I
701+
SELECT z FROM naconst_corr_t3 WHERE 2 NOT IN (SELECT naconst_corr_t4.id FROM naconst_corr_t4 WHERE naconst_corr_t4.z = naconst_corr_t3.z) ORDER BY z;
702+
----
703+
NULL
704+
705+
query I
706+
SELECT z FROM naconst_corr_t3 WHERE 1 NOT IN (SELECT naconst_corr_t4.id FROM naconst_corr_t4 WHERE naconst_corr_t4.z > naconst_corr_t3.z) ORDER BY z;
707+
----
708+
NULL
709+
710+
statement ok
711+
DROP TABLE naconst_corr_t3;
712+
713+
statement ok
714+
DROP TABLE naconst_corr_t4;
715+
664716
statement ok
665717
DROP TABLE naconst_t1;
666718

0 commit comments

Comments
 (0)