Skip to content

Commit da9f7b7

Browse files
fix: decorrelate grouping sets that leave out the correlated column when safe
correlated column, even when nothing would ever observe the difference. Only reject now when a set is empty, the aggregate computes GROUPING/GROUPING_ID, or something above the aggregate (checked ahead of time, since the rewrite runs bottom-up and hasn't visited it yet) reads the column that would change. Fixes apache#25708
1 parent 141663e commit da9f7b7

5 files changed

Lines changed: 212 additions & 70 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 182 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -36,8 +36,8 @@ use datafusion_expr::utils::{
3636
collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
3737
};
3838
use datafusion_expr::{
39-
BinaryExpr, Cast, EmptyRelation, Expr, ExprSchemable, FetchType, LogicalPlan,
40-
LogicalPlanBuilder, Operator, SkipType, expr, lit,
39+
Aggregate, BinaryExpr, Cast, EmptyRelation, Expr, ExprSchemable, FetchType,
40+
LogicalPlan, LogicalPlanBuilder, Operator, SkipType, expr, lit,
4141
};
4242

4343
/// This struct rewrite the sub query plan by pull up the correlated
@@ -91,6 +91,13 @@ pub struct PullUpCorrelatedExpr {
9191
/// The list is cleared when the pull up passes a node that can put a NULL
9292
/// back into such a column: an outer join, a union or a grouping set.
9393
pub correlated_filters: Vec<Expr>,
94+
/// Columns read, above the subquery's `Aggregate`, by a node the rewrite
95+
/// has not reached yet when it visits that `Aggregate` (the rewrite runs
96+
/// bottom-up, so a `Projection` or `HAVING` above it is only visited
97+
/// afterwards). Populated once, from the original subquery plan, by
98+
/// [`Self::with_column_refs_above_aggregate`], since [`Self::f_up`] has no
99+
/// way to compute it on its own.
100+
column_refs_above_aggregate: BTreeSet<Column>,
94101
}
95102

96103
impl Default for PullUpCorrelatedExpr {
@@ -113,6 +120,7 @@ impl PullUpCorrelatedExpr {
113120
pull_up_having_expr: None,
114121
pulled_up_scalar_agg: false,
115122
correlated_filters: Vec::new(),
123+
column_refs_above_aggregate: BTreeSet::new(),
116124
}
117125
}
118126

@@ -142,6 +150,36 @@ impl PullUpCorrelatedExpr {
142150
self.can_pull_up = false;
143151
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
144152
}
153+
154+
/// Record the columns read above the subquery's `Aggregate`, computed
155+
/// from `subquery_plan` (the plan as it is before this rewrite runs).
156+
///
157+
/// A grouping set that omits a correlated column only needs to reject the
158+
/// pull up when something reads the column the pull up would fill in, so
159+
/// [`Self::f_up`] needs this computed ahead of time. See
160+
/// [`columns_read_above_aggregate`].
161+
pub fn with_column_refs_above_aggregate(
162+
mut self,
163+
subquery_plan: &LogicalPlan,
164+
) -> Self {
165+
self.column_refs_above_aggregate = columns_read_above_aggregate(subquery_plan);
166+
self
167+
}
168+
}
169+
170+
/// The outcome of trying to fold the pull up's columns into a grouping set
171+
/// `Aggregate`. See [`PullUpCorrelatedExpr::grouping_sets_pull_up_outcome`].
172+
#[derive(Debug, PartialEq, Eq)]
173+
enum GroupingSetsPullUp {
174+
/// Every set already groups by the columns; the aggregate's `group_expr`
175+
/// stays as it is.
176+
NoColumnsToAdd,
177+
/// Some set leaves a required column out, but extending every set with it
178+
/// changes nothing the rest of the query can observe.
179+
SafeToExtend,
180+
/// Some set leaves a required column out, and extending every set with it
181+
/// would change what the query returns.
182+
Unsafe,
145183
}
146184

147185
/// Used to indicate the unmatched rows from the inner(subquery) table after the left out Join
@@ -363,42 +401,54 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
363401
&mut local_correlated_cols,
364402
);
365403

366-
// A grouping set cannot take the columns the pull up adds.
367-
// `LogicalPlanBuilder::aggregate` cross joins a plain group
368-
// expression with the sets that are already there, so `ROLLUP(i.k)`,
369-
// which is `GROUPING SETS ((i.k), ())`, becomes
370-
// `GROUPING SETS ((i.k), (i.k, i.k))`. The empty set is gone, and
371-
// with it the grand total row the subquery returns for every outer
372-
// row, including the rows whose correlated filter matches nothing.
373-
// The join that replaces the filter cannot bring those rows back,
374-
// so the subquery stays correlated unless every set already groups
375-
// by each column the pull up would add.
404+
// A grouping set that omits a column the pull up adds either
405+
// keeps its sets as they are (every set already groups by the
406+
// column), or gains the column in every set, `ROLLUP(i.k)`
407+
// (`GROUPING SETS ((i.k), ())`) becoming
408+
// `GROUPING SETS ((i.k), (i.k, i.k))`. The latter loses the
409+
// empty set, and with it the grand total row the subquery
410+
// returns for every outer row, including the rows whose
411+
// correlated filter matches nothing, so it is only safe when
412+
// no set is empty and nothing reads the column the fill
413+
// changes from `NULL` to the correlated value.
376414
let mut missing_exprs = if aggregate
377415
.group_expr
378416
.iter()
379417
.any(|expr| matches!(expr, Expr::GroupingSet(_)))
380418
{
381-
if self.grouping_sets_cover_pull_up_cols(
382-
&aggregate.group_expr,
383-
&local_correlated_cols,
384-
) {
385-
// Every set already groups by them, so the sets stay as
386-
// they are. Adding the columns again would repeat them
387-
// inside every set.
388-
aggregate.group_expr.to_vec()
389-
} else {
390-
self.can_pull_up = false;
391-
// The rewrite still runs, the same way the
392-
// `can_pull_over_aggregation` case above does. The callers
393-
// read `can_pull_up` only after the whole rewrite has
394-
// finished, and the nodes above this one still expect the
395-
// pulled up columns in its output, so leaving them out here
396-
// would fail the rewrite with a schema error instead. They
397-
// drop this plan and keep the correlated subquery.
398-
self.collect_missing_exprs(
399-
&aggregate.group_expr,
400-
&local_correlated_cols,
401-
)?
419+
match self
420+
.grouping_sets_pull_up_outcome(aggregate, &local_correlated_cols)
421+
{
422+
GroupingSetsPullUp::NoColumnsToAdd => {
423+
// Every set already groups by them, so the sets stay as
424+
// they are. Adding the columns again would repeat them
425+
// inside every set.
426+
aggregate.group_expr.to_vec()
427+
}
428+
GroupingSetsPullUp::SafeToExtend => {
429+
// No set is empty and nothing reads the columns the
430+
// fill changes from `NULL` to the correlated value,
431+
// so extending every set is invisible to the rest of
432+
// the query.
433+
self.collect_missing_exprs(
434+
&aggregate.group_expr,
435+
&local_correlated_cols,
436+
)?
437+
}
438+
GroupingSetsPullUp::Unsafe => {
439+
self.can_pull_up = false;
440+
// The rewrite still runs, the same way the
441+
// `can_pull_over_aggregation` case above does. The callers
442+
// read `can_pull_up` only after the whole rewrite has
443+
// finished, and the nodes above this one still expect the
444+
// pulled up columns in its output, so leaving them out here
445+
// would fail the rewrite with a schema error instead. They
446+
// drop this plan and keep the correlated subquery.
447+
self.collect_missing_exprs(
448+
&aggregate.group_expr,
449+
&local_correlated_cols,
450+
)?
451+
}
402452
}
403453
} else {
404454
// add missing columns to Aggregation's group expressions
@@ -492,26 +542,41 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
492542
}
493543

494544
impl PullUpCorrelatedExpr {
495-
/// Whether the pull up can add its columns to `group_expr` without changing
496-
/// what the aggregate returns.
545+
/// Whether the pull up can add its columns to a grouping set `Aggregate`,
546+
/// and whether it needs to.
497547
///
498-
/// `true` when `group_expr` holds no grouping set, and when every set of every
499-
/// grouping set it holds already groups by each column
500-
/// [`Self::collect_missing_exprs`] would add. In the second case the pull up
501-
/// adds nothing and the aggregate keeps the sets it has.
548+
/// [`GroupingSetsPullUp::NoColumnsToAdd`] when every set of every grouping
549+
/// set already groups by each column [`Self::collect_missing_exprs`]
550+
/// would add: the pull up adds nothing and the aggregate keeps the sets
551+
/// it has.
502552
///
503-
/// `ROLLUP` and `CUBE` always contain the empty set, which yields a row for
504-
/// outer rows the correlated filter matches nothing for, so they are only safe
505-
/// when there is nothing to add.
553+
/// Otherwise some set leaves a required column out, which fills that
554+
/// column with `NULL` in the set's rows. Adding the column to every set
555+
/// (`LogicalPlanBuilder::aggregate` cross joins a plain group expression
556+
/// with the sets that are already there) gives it a value instead. This
557+
/// is only invisible to the rest of the query when:
558+
/// - no set is empty. `ROLLUP(i.k)`, `GROUPING SETS ((i.k), ())`, always
559+
/// holds one, and turns into `GROUPING SETS ((i.k), (i.k, i.k))`,
560+
/// losing the empty set and the grand total row it yields for every
561+
/// outer row, including the rows the correlated filter matches
562+
/// nothing for. The join that replaces the filter cannot bring that
563+
/// row back.
564+
/// - the aggregate does not compute `GROUPING`/`GROUPING_ID`, which
565+
/// reads whether a row's set groups by a column.
566+
/// - nothing above the aggregate reads the column, which
567+
/// `column_refs_above_aggregate` was populated with ahead of time (this
568+
/// rewrite runs bottom-up, so a `HAVING` or `Projection` above the
569+
/// aggregate is only visited after it).
506570
///
507-
/// A non-empty set that leaves a column out fills it with NULL. Adding the
508-
/// column would give it a value instead, which a `HAVING` or a projection
509-
/// above the aggregate can read, so such a set is rejected as well.
510-
fn grouping_sets_cover_pull_up_cols(
571+
/// When one of these fails, [`GroupingSetsPullUp::Unsafe`] is returned:
572+
/// the columns are still added, so the schema the nodes above expect
573+
/// stays correct, but the caller must give up on decorrelating.
574+
fn grouping_sets_pull_up_outcome(
511575
&self,
512-
group_expr: &[Expr],
576+
aggregate: &Aggregate,
513577
correlated_subquery_cols: &BTreeSet<Column>,
514-
) -> bool {
578+
) -> GroupingSetsPullUp {
579+
let group_expr = &aggregate.group_expr;
515580
let grouping_sets = group_expr
516581
.iter()
517582
.filter_map(|expr| match expr {
@@ -520,7 +585,7 @@ impl PullUpCorrelatedExpr {
520585
})
521586
.collect::<Vec<_>>();
522587
if grouping_sets.is_empty() {
523-
return true;
588+
return GroupingSetsPullUp::NoColumnsToAdd;
524589
}
525590

526591
// The same columns `collect_missing_exprs` appends: the correlated columns
@@ -536,18 +601,37 @@ impl PullUpCorrelatedExpr {
536601
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
537602
});
538603
if required_cols.is_empty() {
539-
return true;
604+
return GroupingSetsPullUp::NoColumnsToAdd;
540605
}
541606

542-
grouping_sets.iter().all(|grouping_set| match grouping_set {
543-
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => false,
544-
GroupingSet::GroupingSets(sets) => sets.iter().all(|set| {
545-
required_cols.iter().all(|col| {
546-
set.iter()
547-
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
548-
})
549-
}),
550-
})
607+
let already_covered =
608+
grouping_sets.iter().all(|grouping_set| match grouping_set {
609+
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => false,
610+
GroupingSet::GroupingSets(sets) => sets.iter().all(|set| {
611+
required_cols.iter().all(|col| {
612+
set.iter()
613+
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
614+
})
615+
}),
616+
});
617+
if already_covered {
618+
return GroupingSetsPullUp::NoColumnsToAdd;
619+
}
620+
621+
let has_empty_set = grouping_sets.iter().any(|grouping_set| match grouping_set {
622+
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => true,
623+
GroupingSet::GroupingSets(sets) => sets.iter().any(|set| set.is_empty()),
624+
});
625+
let reads_grouping_fn = aggregate.aggr_expr.iter().any(is_grouping_call);
626+
let read_above = required_cols
627+
.iter()
628+
.any(|col| self.column_refs_above_aggregate.contains(*col));
629+
630+
if has_empty_set || reads_grouping_fn || read_above {
631+
GroupingSetsPullUp::Unsafe
632+
} else {
633+
GroupingSetsPullUp::SafeToExtend
634+
}
551635
}
552636

553637
fn collect_missing_exprs(
@@ -661,6 +745,45 @@ fn can_pullup_over_aggregation(expr: &Expr) -> bool {
661745
}
662746
}
663747

748+
/// Whether `expr` computes `GROUPING`/`GROUPING_ID`, which reads whether a
749+
/// row's grouping set groups by a particular column.
750+
fn is_grouping_call(expr: &Expr) -> bool {
751+
matches!(expr, Expr::AggregateFunction(agg) if agg.func.name().eq_ignore_ascii_case("grouping"))
752+
}
753+
754+
/// Columns read by a node strictly above the first `Aggregate` found in
755+
/// `plan`, which is the subquery's original, not yet rewritten, plan.
756+
///
757+
/// [`PullUpCorrelatedExpr::f_up`] runs bottom-up, so by the time it visits an
758+
/// `Aggregate` it cannot yet tell whether a `HAVING` or `Projection` above it
759+
/// reads one of the columns a grouping set pull up would add. This walks the
760+
/// plan top-down instead, before the rewrite starts, and stops at the first
761+
/// `Aggregate` along each branch, collecting the columns every node above it
762+
/// reads in its own expressions. A nested `Subquery` is a different
763+
/// correlation scope and is skipped, the same way
764+
/// [`PullUpCorrelatedExpr::f_down`] skips it.
765+
fn columns_read_above_aggregate(plan: &LogicalPlan) -> BTreeSet<Column> {
766+
fn walk(plan: &LogicalPlan, above: &mut BTreeSet<Column>) -> bool {
767+
if matches!(plan, LogicalPlan::Subquery(_)) {
768+
return false;
769+
}
770+
if matches!(plan, LogicalPlan::Aggregate(_)) {
771+
return true;
772+
}
773+
let found_below = plan.inputs().into_iter().any(|child| walk(child, above));
774+
if found_below {
775+
for expr in plan.expressions() {
776+
above.extend(expr.column_refs().into_iter().cloned());
777+
}
778+
}
779+
found_below
780+
}
781+
782+
let mut above = BTreeSet::new();
783+
walk(plan, &mut above);
784+
above
785+
}
786+
664787
fn collect_local_correlated_cols(
665788
plan: &LogicalPlan,
666789
all_cols_map: &HashMap<LogicalPlan, BTreeSet<Column>>,

‎datafusion/optimizer/src/decorrelate_lateral_join.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -107,7 +107,9 @@ fn rewrite_internal(join: Join) -> Result<Transformed<LogicalPlan>> {
107107
// Walk the subquery plan bottom-up, extracting correlated filter
108108
// predicates into join conditions and converting ungrouped aggregates
109109
// into group-by aggregates keyed on the correlation columns.
110-
let mut pull_up = PullUpCorrelatedExpr::new().with_need_handle_count_bug(true);
110+
let mut pull_up = PullUpCorrelatedExpr::new()
111+
.with_need_handle_count_bug(true)
112+
.with_column_refs_above_aggregate(subquery_plan);
111113
let rewritten_subquery = subquery_plan.clone().rewrite(&mut pull_up).data()?;
112114
if !pull_up.can_pull_up {
113115
return Ok(Transformed::no(LogicalPlan::Join(join)));

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -735,7 +735,8 @@ fn build_join(
735735
) -> Result<Option<BuiltJoin>> {
736736
let mut pull_up = PullUpCorrelatedExpr::new()
737737
.with_in_predicate_opt(in_predicate_opt.cloned())
738-
.with_exists_sub_query(in_predicate_opt.is_none());
738+
.with_exists_sub_query(in_predicate_opt.is_none())
739+
.with_column_refs_above_aggregate(subquery);
739740

740741
let new_plan = subquery.clone().rewrite(&mut pull_up).data()?;
741742
if !pull_up.can_pull_up {

‎datafusion/optimizer/src/scalar_subquery_to_join.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -351,7 +351,9 @@ fn build_join(
351351
// join with `Boolean(true)`) when the
352352
// `enable_physical_uncorrelated_scalar_subquery` option is disabled.
353353
let subquery_plan = subquery.subquery.as_ref();
354-
let mut pull_up = PullUpCorrelatedExpr::new().with_need_handle_count_bug(true);
354+
let mut pull_up = PullUpCorrelatedExpr::new()
355+
.with_need_handle_count_bug(true)
356+
.with_column_refs_above_aggregate(subquery_plan);
355357
let decorrelated_subquery = subquery_plan.clone().rewrite(&mut pull_up).data()?;
356358
if !pull_up.can_pull_up {
357359
return Ok(None);

0 commit comments

Comments
 (0)