Skip to content

Commit f031ee7

Browse files
fix: Decide NOT IN null-aware joins from expression nullability, not just column nullability
closes: apache#25473 closes: apache#25474 `join_keys_may_be_null` only checked the schema nullability of the columns a join filter references. A NULL constant or an expression that is nullable even though every column it reads is NOT NULL (CASE without ELSE, NULLIF, arithmetic with a NULL operand) was therefore never treated as needing null-aware semantics, so a NOT IN predicate that should be UNKNOWN silently kept the outer row instead. Replace the column walk with a per-equality-conjunct nullability check that evaluates each operand as an expression against whichever schema it resolves to, falling back to nullable when that can't be determined.
1 parent 04e6b37 commit f031ee7

2 files changed

Lines changed: 285 additions & 18 deletions

File tree

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 148 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -34,10 +34,12 @@ use datafusion_common::{
3434
use datafusion_expr::expr::{Exists, InSubquery};
3535
use datafusion_expr::expr_rewriter::create_col_from_scalar_expr;
3636
use datafusion_expr::logical_plan::{JoinType, Subquery};
37-
use datafusion_expr::utils::{conjunction, expr_to_columns, split_conjunction_owned};
37+
use datafusion_expr::utils::{
38+
conjunction, expr_to_columns, split_conjunction, split_conjunction_owned,
39+
};
3840
use datafusion_expr::{
39-
BinaryExpr, Expr, Filter, LogicalPlan, LogicalPlanBuilder, Operator, exists,
40-
in_subquery, lit, not, not_exists, not_in_subquery, when,
41+
BinaryExpr, Expr, ExprSchemable, Filter, LogicalPlan, LogicalPlanBuilder, Operator,
42+
exists, in_subquery, lit, not, not_exists, not_in_subquery, when,
4143
};
4244

4345
use log::debug;
@@ -479,29 +481,31 @@ fn mark_join(
479481

480482
/// Check if join keys in the join filter may contain NULL values
481483
///
482-
/// Returns true if any join key column is nullable on either side.
484+
/// Returns true if either side of an equality conjunct can itself be NULL, as
485+
/// an expression rather than just the columns it references. A `CASE` without
486+
/// `ELSE`, `NULLIF`, or a NULL constant is nullable even when every column it
487+
/// reads is declared `NOT NULL`.
483488
/// This is used to optimize null-aware anti joins: if all join keys are non-nullable,
484489
/// we can use a regular anti join instead of the more expensive null-aware variant.
485490
fn join_keys_may_be_null(
486491
join_filter: &Expr,
487492
left_schema: &DFSchemaRef,
488493
right_schema: &DFSchemaRef,
489494
) -> Result<bool> {
490-
// Extract columns from the join filter
491-
let mut columns = std::collections::HashSet::new();
492-
expr_to_columns(join_filter, &mut columns)?;
493-
494-
// Check if any column is nullable
495-
for col in columns {
496-
// Check in left schema
497-
if let Ok(field) = left_schema.field_from_column(&col)
498-
&& field.as_ref().is_nullable()
499-
{
495+
for conjunct in split_conjunction(join_filter) {
496+
let Expr::BinaryExpr(BinaryExpr {
497+
left,
498+
op: Operator::Eq,
499+
right,
500+
}) = conjunct
501+
else {
502+
// Only equality conjuncts become hash-join keys; a residual
503+
// conjunct's nullability isn't decided here, so stay conservative.
500504
return Ok(true);
501-
}
502-
// Check in right schema
503-
if let Ok(field) = right_schema.field_from_column(&col)
504-
&& field.as_ref().is_nullable()
505+
};
506+
507+
if operand_may_be_null(left, left_schema, right_schema)?
508+
|| operand_may_be_null(right, left_schema, right_schema)?
505509
{
506510
return Ok(true);
507511
}
@@ -522,6 +526,35 @@ fn in_predicate_first(in_predicate: Expr, correlation: Option<Expr>) -> Expr {
522526
}
523527
}
524528

529+
/// Whether `expr` can evaluate to NULL, resolving it against whichever side's
530+
/// schema its column references belong to. Falls back to `true`, the
531+
/// conservative answer, when that side can't be determined uniquely: treating
532+
/// a key as nullable costs a null-aware join, treating it as non-nullable
533+
/// risks wrong results.
534+
fn operand_may_be_null(
535+
expr: &Expr,
536+
left_schema: &DFSchemaRef,
537+
right_schema: &DFSchemaRef,
538+
) -> Result<bool> {
539+
let mut columns = std::collections::HashSet::new();
540+
expr_to_columns(expr, &mut columns)?;
541+
542+
let references_left = columns
543+
.iter()
544+
.any(|col| left_schema.field_from_column(col).is_ok());
545+
let references_right = columns
546+
.iter()
547+
.any(|col| right_schema.field_from_column(col).is_ok());
548+
549+
match (references_left, references_right) {
550+
(true, true) => Ok(true),
551+
(true, false) => expr.nullable(left_schema.as_ref()),
552+
// A constant references neither schema; either one gives the same
553+
// answer, since a literal's nullability doesn't depend on the schema.
554+
(false, true) | (false, false) => expr.nullable(right_schema.as_ref()),
555+
}
556+
}
557+
525558
fn build_join(
526559
left: &LogicalPlan,
527560
subquery: &LogicalPlan,
@@ -805,6 +838,16 @@ mod tests {
805838
table_scan(Some(name), &schema, None)?.build()
806839
}
807840

841+
fn has_null_aware_left_anti_join(plan: &LogicalPlan) -> bool {
842+
if let LogicalPlan::Join(join) = plan
843+
&& join.join_type == JoinType::LeftAnti
844+
{
845+
return join.null_aware;
846+
}
847+
848+
plan.inputs().into_iter().any(has_null_aware_left_anti_join)
849+
}
850+
808851
fn has_null_aware_left_mark_join(plan: &LogicalPlan) -> bool {
809852
if let LogicalPlan::Join(join) = plan
810853
&& join.join_type == JoinType::LeftMark
@@ -1542,6 +1585,93 @@ mod tests {
15421585
)
15431586
}
15441587

1588+
/// A NULL constant against a `NOT NULL` subquery column must still
1589+
/// trigger the null-aware rewrite: `join_keys_may_be_null` has to see the
1590+
/// constant's own nullability, not just the nullability of the columns
1591+
/// the join filter references.
1592+
/// <https://github.com/apache/datafusion/issues/25473>
1593+
#[test]
1594+
fn constant_null_not_in_subquery_is_null_aware_over_not_null_column() -> Result<()> {
1595+
let outer_scan = nullable_scalar_mark_scan("outer_t")?;
1596+
let subquery = test_subquery_with_name("inner_t")?;
1597+
1598+
let plan = LogicalPlanBuilder::from(outer_scan)
1599+
.filter(not_in_subquery(
1600+
Expr::Literal(ScalarValue::Int32(None), None),
1601+
subquery,
1602+
))?
1603+
.build()?;
1604+
1605+
let optimized = optimize_with_decorrelate(plan)?;
1606+
assert!(
1607+
has_null_aware_left_anti_join(&optimized),
1608+
"{}",
1609+
optimized.display_indent_schema()
1610+
);
1611+
1612+
Ok(())
1613+
}
1614+
1615+
/// An expression that can be NULL even though every column it reads is
1616+
/// `NOT NULL` (`CASE` without `ELSE`, here) must also trigger the
1617+
/// null-aware rewrite. `join_keys_may_be_null` has to check the
1618+
/// expression's own nullability rather than only the schema nullability
1619+
/// of the columns it references.
1620+
/// <https://github.com/apache/datafusion/issues/25474>
1621+
#[test]
1622+
fn nullable_expression_not_in_subquery_is_null_aware_over_not_null_columns()
1623+
-> Result<()> {
1624+
let outer_scan = test_table_scan_with_name("outer_t")?;
1625+
let subquery = test_subquery_with_name("inner_t")?;
1626+
1627+
let value = when(col("outer_t.a").gt(lit(100u32)), col("outer_t.a")).end()?;
1628+
let plan = LogicalPlanBuilder::from(outer_scan)
1629+
.filter(not_in_subquery(value, subquery))?
1630+
.build()?;
1631+
1632+
let optimized = optimize_with_decorrelate(plan)?;
1633+
assert!(
1634+
has_null_aware_left_anti_join(&optimized),
1635+
"{}",
1636+
optimized.display_indent_schema()
1637+
);
1638+
1639+
Ok(())
1640+
}
1641+
1642+
/// The same rewrite must not fire for a correlated subquery: the
1643+
/// correlation predicate is a second equi-join key, and null-aware hash
1644+
/// joins accept only one.
1645+
#[test]
1646+
fn constant_not_in_correlated_subquery_is_not_rewritten() -> Result<()> {
1647+
let outer_scan = nullable_scalar_mark_scan("outer_t")?;
1648+
let inner_scan = nullable_scalar_mark_scan("inner_t")?;
1649+
1650+
let subquery = Arc::new(
1651+
LogicalPlanBuilder::from(inner_scan)
1652+
.filter(
1653+
out_ref_col(DataType::Int32, "outer_t.grp").eq(col("inner_t.grp")),
1654+
)?
1655+
.project(vec![col("inner_t.id")])?
1656+
.build()?,
1657+
);
1658+
1659+
let plan = LogicalPlanBuilder::from(outer_scan)
1660+
.filter(not_in_subquery(lit(3i32), subquery))?
1661+
.build()?;
1662+
1663+
assert_optimized_plan_equal!(
1664+
plan,
1665+
@r"
1666+
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]
1667+
TableScan: outer_t [id:Int32;N, grp:Int32;N]
1668+
SubqueryAlias: __correlated_sq_1 [id:Int32;N, grp:Int32;N]
1669+
Projection: inner_t.id, inner_t.grp [id:Int32;N, grp:Int32;N]
1670+
TableScan: inner_t [id:Int32;N, grp:Int32;N]
1671+
"
1672+
)
1673+
}
1674+
15451675
#[test]
15461676
fn correlated_not_in_mark_join_is_null_aware_for_hashable_filter() -> Result<()> {
15471677
let outer_scan = nullable_scalar_mark_scan("outer_t")?;

‎datafusion/sqllogictest/test_files/null_aware_anti_join.slt‎

Lines changed: 137 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -942,3 +942,140 @@ DROP TABLE nai_res_outer;
942942

943943
statement ok
944944
DROP TABLE nai_res_inner;
945+
946+
#############
947+
## Regression: `join_keys_may_be_null` must see expression nullability, not
948+
## just the schema nullability of the columns an expression references.
949+
## https://github.com/apache/datafusion/issues/25473
950+
## https://github.com/apache/datafusion/issues/25474
951+
##
952+
## A NULL constant, or an expression that is nullable even though every
953+
## column it reads is `NOT NULL` (`CASE` without `ELSE`, `NULLIF`), must still
954+
## make `NOT IN` null-aware. Otherwise the NULL outer value is never
955+
## recognized: the predicate is pushed into the subquery and the row is kept
956+
## instead of becoming UNKNOWN.
957+
#############
958+
959+
statement ok
960+
CREATE TABLE nainull_o(x INT NOT NULL) AS VALUES (1), (2);
961+
962+
statement ok
963+
CREATE TABLE nainull_i(id INT NOT NULL) AS VALUES (1), (3);
964+
965+
statement ok
966+
CREATE TABLE nainull_ie(id INT NOT NULL) AS SELECT * FROM (VALUES (1)) t(id) WHERE false;
967+
968+
# A typed NULL constant against a NOT NULL subquery column.
969+
query I
970+
SELECT x FROM nainull_o WHERE CAST(NULL AS INT) NOT IN (SELECT id FROM nainull_i) ORDER BY x;
971+
----
972+
973+
query I
974+
SELECT x FROM nainull_o WHERE NULL NOT IN (SELECT id FROM nainull_i) ORDER BY x;
975+
----
976+
977+
query I
978+
SELECT x FROM nainull_o WHERE NULLIF(1, 1) NOT IN (SELECT id FROM nainull_i) ORDER BY x;
979+
----
980+
981+
# The mark form behind an OR: the NULL constant's UNKNOWN must survive.
982+
query I
983+
SELECT x FROM nainull_o WHERE CAST(NULL AS INT) NOT IN (SELECT id FROM nainull_i) OR x = 99 ORDER BY x;
984+
----
985+
986+
# Double negation flips the outer row set: false -> true.
987+
query I
988+
SELECT x FROM nainull_o WHERE NOT (CAST(NULL AS INT) NOT IN (SELECT id FROM nainull_i)) ORDER BY x;
989+
----
990+
991+
# Control: `NOT IN (<empty subquery>)` is TRUE even for a NULL outer value.
992+
query I
993+
SELECT x FROM nainull_o WHERE CAST(NULL AS INT) NOT IN (SELECT id FROM nainull_ie) ORDER BY x;
994+
----
995+
1
996+
2
997+
998+
query TT
999+
EXPLAIN SELECT x FROM nainull_o WHERE CAST(NULL AS INT) NOT IN (SELECT id FROM nainull_i);
1000+
----
1001+
logical_plan
1002+
01)Projection: nainull_o.x
1003+
02)--LeftAnti Join: __correlated_sq_1_value = __correlated_sq_1.id null_aware
1004+
03)----Projection: nainull_o.x, Int32(NULL) AS __correlated_sq_1_value
1005+
04)------TableScan: nainull_o projection=[x]
1006+
05)----SubqueryAlias: __correlated_sq_1
1007+
06)------TableScan: nainull_i projection=[id]
1008+
physical_plan
1009+
01)HashJoinExec: mode=CollectLeft, join_type=LeftAnti, on=[(__correlated_sq_1_value@1, id@0)], projection=[x@0], null_aware
1010+
02)--ProjectionExec: expr=[x@0 as x, NULL as __correlated_sq_1_value]
1011+
03)----DataSourceExec: partitions=1, partition_sizes=[1]
1012+
04)--DataSourceExec: partitions=1, partition_sizes=[1]
1013+
1014+
statement ok
1015+
DROP TABLE nainull_o;
1016+
1017+
statement ok
1018+
DROP TABLE nainull_i;
1019+
1020+
statement ok
1021+
DROP TABLE nainull_ie;
1022+
1023+
# An outer expression that is nullable even though the only column it reads
1024+
# (`x`) is `NOT NULL`. `on2` is the same data with a nullable `x`, as a
1025+
# control that this was already correct via column nullability.
1026+
statement ok
1027+
CREATE TABLE nainull_e_o(x INT NOT NULL) AS VALUES (1), (2);
1028+
1029+
statement ok
1030+
CREATE TABLE nainull_e_o2(x INT) AS VALUES (1), (2);
1031+
1032+
statement ok
1033+
CREATE TABLE nainull_e_i(id INT NOT NULL) AS VALUES (1), (3);
1034+
1035+
# `CASE` without `ELSE` is NULL for every row here.
1036+
query I
1037+
SELECT x FROM nainull_e_o WHERE (CASE WHEN x > 100 THEN 1 END) NOT IN (SELECT id FROM nainull_e_i) ORDER BY x;
1038+
----
1039+
1040+
query I
1041+
SELECT x FROM nainull_e_o WHERE NULLIF(x, x) NOT IN (SELECT id FROM nainull_e_i) ORDER BY x;
1042+
----
1043+
1044+
query I
1045+
SELECT x FROM nainull_e_o WHERE x + CAST(NULL AS INT) NOT IN (SELECT id FROM nainull_e_i) ORDER BY x;
1046+
----
1047+
1048+
query I
1049+
SELECT x FROM nainull_e_o WHERE (CASE WHEN x > 100 THEN 1 END) NOT IN (SELECT id FROM nainull_e_i) OR x = 99 ORDER BY x;
1050+
----
1051+
1052+
# Same expression, but the column it reads is nullable: must give the same
1053+
# (correct) result as the `NOT NULL` cases above.
1054+
query I
1055+
SELECT x FROM nainull_e_o2 WHERE (CASE WHEN x > 100 THEN 1 END) NOT IN (SELECT id FROM nainull_e_i) ORDER BY x;
1056+
----
1057+
1058+
query TT
1059+
EXPLAIN SELECT x FROM nainull_e_o WHERE (CASE WHEN x > 100 THEN 1 END) NOT IN (SELECT id FROM nainull_e_i);
1060+
----
1061+
logical_plan
1062+
01)LeftAnti Join: CASE WHEN nainull_e_o.x > Int32(100) THEN Int64(1) END = __correlated_sq_1.nainull_e_i.id null_aware
1063+
02)--TableScan: nainull_e_o projection=[x]
1064+
03)--SubqueryAlias: __correlated_sq_1
1065+
04)----Projection: CAST(nainull_e_i.id AS Int64)
1066+
05)------TableScan: nainull_e_i projection=[id]
1067+
physical_plan
1068+
01)HashJoinExec: mode=CollectLeft, join_type=RightAnti, on=[(nainull_e_i.id@0, CASE WHEN nainull_e_o.x > Int32(100) THEN Int64(1) END@1)], projection=[x@0], null_aware
1069+
02)--ProjectionExec: expr=[CAST(id@0 AS Int64) as nainull_e_i.id]
1070+
03)----DataSourceExec: partitions=1, partition_sizes=[1]
1071+
04)--ProjectionExec: expr=[x@0 as x, CASE WHEN x@0 > 100 THEN 1 END as CASE WHEN nainull_e_o.x > Int32(100) THEN Int64(1) END]
1072+
05)----DataSourceExec: partitions=1, partition_sizes=[1]
1073+
1074+
statement ok
1075+
DROP TABLE nainull_e_o;
1076+
1077+
statement ok
1078+
DROP TABLE nainull_e_o2;
1079+
1080+
statement ok
1081+
DROP TABLE nainull_e_i;

0 commit comments

Comments
 (0)