Skip to content

Commit 61c6d51

Browse files
adriangbclaude
andcommitted
fix: do not build a null-aware join when the correlation repeats the IN predicate
`x IN (SELECT y FROM .. WHERE y = x)` writes the `IN` equality a second time, as a correlated filter. `remove_duplicated_filter` drops that filter, because `build_join` adds the same equality back as the join filter. The scope of the subquery is then gone, and the join looked uncorrelated and null-aware, so a miss gave UNKNOWN. The result of this shape is never UNKNOWN: every row the subquery keeps for an outer row satisfies `y = x`, so `y` is not NULL there and the subquery result is either empty or `{x}`. `PullUpCorrelatedExpr` now reports the shape, and the mark join and the anti join stay plain for it. A node above the dropped filter can still put a NULL into the value column, and then the result is UNKNOWN again. An outer join, a union and a grouping set do this, so the flag is cleared when the pull up passes one of them. `f_up` walks the subquery bottom up, so every such node above the filter is reached after it. This also fixes apache#25480, which is the same root cause in a `WHERE ... NOT IN` clause. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 3af8737 commit 61c6d51

2 files changed

Lines changed: 56 additions & 3 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 45 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -34,8 +34,8 @@ use datafusion_expr::utils::{
3434
collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
3535
};
3636
use datafusion_expr::{
37-
BinaryExpr, Cast, EmptyRelation, Expr, ExprSchemable, FetchType, LogicalPlan,
38-
LogicalPlanBuilder, Operator, expr, lit,
37+
BinaryExpr, Cast, EmptyRelation, Expr, ExprSchemable, FetchType, JoinType,
38+
LogicalPlan, LogicalPlanBuilder, Operator, expr, lit,
3939
};
4040

4141
/// This struct rewrite the sub query plan by pull up the correlated
@@ -74,6 +74,21 @@ pub struct PullUpCorrelatedExpr {
7474
/// whether we have converted a scalar aggregation into a group aggregation. When unnesting
7575
/// lateral joins, we need to produce a left outer join in such cases.
7676
pub pulled_up_scalar_agg: bool,
77+
/// The subquery writes the `IN` predicate a second time, as a correlated
78+
/// filter: `x IN (SELECT y FROM .. WHERE y = x)`.
79+
///
80+
/// [`remove_duplicated_filter`] drops that filter, because the caller adds
81+
/// the same equality back as the join filter. The `IN` is then never
82+
/// UNKNOWN: every row in the scope of an outer row satisfies `y = x`, so
83+
/// `y` is not NULL there and the subquery result is either empty or `{x}`.
84+
/// A null-aware join reports UNKNOWN for a miss, so the caller must not
85+
/// build one for this shape. See
86+
/// <https://github.com/apache/datafusion/issues/25480>.
87+
///
88+
/// A node above that filter can still put a NULL into the value column, so
89+
/// the flag is cleared again when the pull up passes such a node. See
90+
/// [`plan_may_add_null_rows`].
91+
pub in_predicate_is_correlation: bool,
7792
}
7893

7994
impl Default for PullUpCorrelatedExpr {
@@ -95,6 +110,7 @@ impl PullUpCorrelatedExpr {
95110
collected_count_expr_map: HashMap::new(),
96111
pull_up_having_expr: None,
97112
pulled_up_scalar_agg: false,
113+
in_predicate_is_correlation: false,
98114
}
99115
}
100116

@@ -173,6 +189,12 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
173189
}
174190

175191
fn f_up(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
192+
// `f_up` walks the subquery bottom up, so a node that this reaches
193+
// after the `Filter` sits above it and can undo what the filter
194+
// promised about the value column.
195+
if self.in_predicate_is_correlation && plan_may_add_null_rows(&plan) {
196+
self.in_predicate_is_correlation = false;
197+
}
176198
let subquery_schema = plan.schema();
177199
match &plan {
178200
LogicalPlan::Filter(plan_filter) => {
@@ -186,7 +208,9 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
186208
find_join_exprs(subquery_filter_exprs)?;
187209
if let Some(in_predicate) = &self.in_predicate_opt {
188210
// in_predicate may be already included in the join filters, remove it from the join filters first.
211+
let filter_count = join_filters.len();
189212
join_filters = remove_duplicated_filter(join_filters, in_predicate)?;
213+
self.in_predicate_is_correlation |= join_filters.len() < filter_count;
190214
}
191215
let correlated_subquery_cols =
192216
collect_subquery_cols(&join_filters, subquery_schema)?;
@@ -480,6 +504,25 @@ fn collect_local_correlated_cols(
480504
}
481505
}
482506

507+
/// Can this plan node give a row whose value column is NULL although a filter
508+
/// below it kept only rows where that column equals the `IN` value?
509+
///
510+
/// See [`PullUpCorrelatedExpr::in_predicate_is_correlation`].
511+
fn plan_may_add_null_rows(plan: &LogicalPlan) -> bool {
512+
match plan {
513+
// An outer join gives a NULL for every column of an unmatched side.
514+
LogicalPlan::Join(join) => join.join_type != JoinType::Inner,
515+
// A filter in one branch of a union says nothing about the others.
516+
LogicalPlan::Union(_) => true,
517+
// A grouping set gives a NULL for each grouping column it rolls up.
518+
LogicalPlan::Aggregate(aggregate) => aggregate
519+
.group_expr
520+
.iter()
521+
.any(|expr| matches!(expr, Expr::GroupingSet(_))),
522+
_ => false,
523+
}
524+
}
525+
483526
fn remove_duplicated_filter(
484527
filters: Vec<Expr>,
485528
in_predicate: &Expr,

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -718,6 +718,10 @@ fn build_join(
718718
// filters stay on the legacy path because hash join execution cannot
719719
// mark UNKNOWN candidates for residual predicates.
720720
let null_aware = match hashable_only_split {
721+
// The subquery repeats the `IN` predicate as its correlation, so
722+
// its result is never UNKNOWN and a plain mark join is exact. See
723+
// `PullUpCorrelatedExpr::in_predicate_is_correlation`.
724+
Some(_) if pull_up.in_predicate_is_correlation => false,
721725
Some((equijoin_keys, residual_filter)) => join_keys_may_be_null(
722726
equijoin_keys,
723727
residual_filter.as_ref(),
@@ -757,7 +761,13 @@ fn build_join(
757761
//
758762
// Additionally, if no join key can be NULL on either side, we don't need
759763
// null-aware semantics because NULLs cannot exist in the keys.
760-
let null_aware = if join_type == JoinType::LeftAnti && in_predicate_opt.is_some() {
764+
//
765+
// A subquery that repeats the `IN` predicate as its correlation is never
766+
// UNKNOWN either, see `PullUpCorrelatedExpr::in_predicate_is_correlation`.
767+
let null_aware = if join_type == JoinType::LeftAnti
768+
&& in_predicate_opt.is_some()
769+
&& !pull_up.in_predicate_is_correlation
770+
{
761771
let (equijoin_keys, residual_filter) = split_eq_and_noneq_join_predicate(
762772
join_filter.clone(),
763773
left.schema(),

0 commit comments

Comments
 (0)