Skip to content

Commit fb08efa

Browse files
adriangbclaude
andcommitted
refactor: derive null-aware joins from the IN value in scope
The rule decided null-awareness with three special cases: a flag that `PullUpCorrelatedExpr` set when it dropped a duplicated correlation and cleared again for a list of plan nodes, a switch to a weaker column test when the null-aware `LeftAnti` executor could not take the join, and an empty key list that selected that weaker test at the constant `IN` call. Replace them with one question. `IN` can only be UNKNOWN when its value or the subquery output can be NULL inside the scope of an outer row. A correlated conjunct such as `y = x` is never TRUE for a NULL, so a key it compares cannot be NULL in scope. `PullUpCorrelatedExpr` now records every correlated conjunct before it drops the duplicated one, and `JoinKeys` asks the two sides of the `IN` predicate for their nullability against those conjuncts. A correlation key that is NULL only empties the scope, so it never makes the join null-aware. The executor limits are then applied in one place. A `NOT IN` whose value can be NULL and whose join has more than one key becomes a null-aware `LeftMark` join, which takes any number of keys, plus a filter on the mark. A `NOT IN` with a residual filter becomes the mark joins that materialize its three-valued result, the same plan as a projected `IN`. Both shapes failed to plan or gave wrong results before. The constant value projection now applies to correlated subqueries too, since the mark join accepts the correlation as a second key. The guard for a grouping set above the dropped filter is gone with the flag. That query is wrong on `main` for `EXISTS` as well, because the pull up moves the filter above the aggregate; that is apache#25519. Co-Authored-By: Claude Fable 5.1 <[email protected]>
1 parent 7bb69a5 commit fb08efa

5 files changed

Lines changed: 470 additions & 350 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 17 additions & 44 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, JoinType,
38-
LogicalPlan, LogicalPlanBuilder, Operator, expr, lit,
37+
BinaryExpr, Cast, EmptyRelation, Expr, ExprSchemable, FetchType, LogicalPlan,
38+
LogicalPlanBuilder, Operator, expr, lit,
3939
};
4040

4141
/// This struct rewrite the sub query plan by pull up the correlated
@@ -74,21 +74,16 @@ 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)`.
77+
/// Every correlated conjunct that a `Filter` of the subquery applies,
78+
/// before [`remove_duplicated_filter`] drops the ones that the `IN`
79+
/// predicate already covers.
7980
///
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,
81+
/// `join_filters` holds only the conjuncts that the join still needs.
82+
/// This list is what the subquery enforces on its own rows. The caller
83+
/// uses it to tell if a join key can be NULL inside the scope of an outer
84+
/// row: `x IN (SELECT y FROM .. WHERE y = x)` keeps every NULL `y` out of
85+
/// its result, although `join_filters` no longer says so.
86+
pub correlated_filters: Vec<Expr>,
9287
}
9388

9489
impl Default for PullUpCorrelatedExpr {
@@ -110,7 +105,7 @@ impl PullUpCorrelatedExpr {
110105
collected_count_expr_map: HashMap::new(),
111106
pull_up_having_expr: None,
112107
pulled_up_scalar_agg: false,
113-
in_predicate_is_correlation: false,
108+
correlated_filters: Vec::new(),
114109
}
115110
}
116111

@@ -189,12 +184,6 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
189184
}
190185

191186
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-
}
198187
let subquery_schema = plan.schema();
199188
match &plan {
200189
LogicalPlan::Filter(plan_filter) => {
@@ -206,11 +195,14 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
206195
.all(|&e| can_pullup_over_aggregation(e));
207196
let (mut join_filters, subquery_filters) =
208197
find_join_exprs(subquery_filter_exprs)?;
198+
for expr in &join_filters {
199+
if !self.correlated_filters.contains(expr) {
200+
self.correlated_filters.push(expr.clone());
201+
}
202+
}
209203
if let Some(in_predicate) = &self.in_predicate_opt {
210204
// in_predicate may be already included in the join filters, remove it from the join filters first.
211-
let filter_count = join_filters.len();
212205
join_filters = remove_duplicated_filter(join_filters, in_predicate)?;
213-
self.in_predicate_is_correlation |= join_filters.len() < filter_count;
214206
}
215207
let correlated_subquery_cols =
216208
collect_subquery_cols(&join_filters, subquery_schema)?;
@@ -504,25 +496,6 @@ fn collect_local_correlated_cols(
504496
}
505497
}
506498

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-
526499
fn remove_duplicated_filter(
527500
filters: Vec<Expr>,
528501
in_predicate: &Expr,

0 commit comments

Comments
 (0)