Skip to content

Commit 42adbba

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 e5fdc9d commit 42adbba

5 files changed

Lines changed: 219 additions & 70 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 189 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, Distinct, EmptyRelation, Expr, ExprSchemable, FetchType,
40-
LogicalPlan, LogicalPlanBuilder, Operator, SkipType, expr, lit,
39+
Aggregate, BinaryExpr, Cast, Distinct, EmptyRelation, Expr, ExprSchemable,
40+
FetchType, 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

@@ -135,6 +143,43 @@ impl PullUpCorrelatedExpr {
135143
self.exists_sub_query = exists_sub_query;
136144
self
137145
}
146+
147+
/// Mark the plan as one whose correlated expressions cannot be pulled up
148+
/// and stop descending into it
149+
fn unsupported(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
150+
self.can_pull_up = false;
151+
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
152+
}
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,
138183
}
139184

140185
/// Used to indicate the unmatched rows from the inner(subquery) table after the left out Join
@@ -437,42 +482,54 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
437482
&mut local_correlated_cols,
438483
);
439484

440-
// A grouping set cannot take the columns the pull up adds.
441-
// `LogicalPlanBuilder::aggregate` cross joins a plain group
442-
// expression with the sets that are already there, so `ROLLUP(i.k)`,
443-
// which is `GROUPING SETS ((i.k), ())`, becomes
444-
// `GROUPING SETS ((i.k), (i.k, i.k))`. The empty set is gone, and
445-
// with it the grand total row the subquery returns for every outer
446-
// row, including the rows whose correlated filter matches nothing.
447-
// The join that replaces the filter cannot bring those rows back,
448-
// so the subquery stays correlated unless every set already groups
449-
// by each column the pull up would add.
485+
// A grouping set that omits a column the pull up adds either
486+
// keeps its sets as they are (every set already groups by the
487+
// column), or gains the column in every set, `ROLLUP(i.k)`
488+
// (`GROUPING SETS ((i.k), ())`) becoming
489+
// `GROUPING SETS ((i.k), (i.k, i.k))`. The latter loses the
490+
// empty set, and with it the grand total row the subquery
491+
// returns for every outer row, including the rows whose
492+
// correlated filter matches nothing, so it is only safe when
493+
// no set is empty and nothing reads the column the fill
494+
// changes from `NULL` to the correlated value.
450495
let mut missing_exprs = if aggregate
451496
.group_expr
452497
.iter()
453498
.any(|expr| matches!(expr, Expr::GroupingSet(_)))
454499
{
455-
if self.grouping_sets_cover_pull_up_cols(
456-
&aggregate.group_expr,
457-
&local_correlated_cols,
458-
) {
459-
// Every set already groups by them, so the sets stay as
460-
// they are. Adding the columns again would repeat them
461-
// inside every set.
462-
aggregate.group_expr.to_vec()
463-
} else {
464-
self.can_pull_up = false;
465-
// The rewrite still runs, the same way the
466-
// `can_pull_over_aggregation` case above does. The callers
467-
// read `can_pull_up` only after the whole rewrite has
468-
// finished, and the nodes above this one still expect the
469-
// pulled up columns in its output, so leaving them out here
470-
// would fail the rewrite with a schema error instead. They
471-
// drop this plan and keep the correlated subquery.
472-
self.collect_missing_exprs(
473-
&aggregate.group_expr,
474-
&local_correlated_cols,
475-
)?
500+
match self
501+
.grouping_sets_pull_up_outcome(aggregate, &local_correlated_cols)
502+
{
503+
GroupingSetsPullUp::NoColumnsToAdd => {
504+
// Every set already groups by them, so the sets stay as
505+
// they are. Adding the columns again would repeat them
506+
// inside every set.
507+
aggregate.group_expr.to_vec()
508+
}
509+
GroupingSetsPullUp::SafeToExtend => {
510+
// No set is empty and nothing reads the columns the
511+
// fill changes from `NULL` to the correlated value,
512+
// so extending every set is invisible to the rest of
513+
// the query.
514+
self.collect_missing_exprs(
515+
&aggregate.group_expr,
516+
&local_correlated_cols,
517+
)?
518+
}
519+
GroupingSetsPullUp::Unsafe => {
520+
self.can_pull_up = false;
521+
// The rewrite still runs, the same way the
522+
// `can_pull_over_aggregation` case above does. The callers
523+
// read `can_pull_up` only after the whole rewrite has
524+
// finished, and the nodes above this one still expect the
525+
// pulled up columns in its output, so leaving them out here
526+
// would fail the rewrite with a schema error instead. They
527+
// drop this plan and keep the correlated subquery.
528+
self.collect_missing_exprs(
529+
&aggregate.group_expr,
530+
&local_correlated_cols,
531+
)?
532+
}
476533
}
477534
} else {
478535
// add missing columns to Aggregation's group expressions
@@ -618,26 +675,41 @@ impl PullUpCorrelatedExpr {
618675
Ok(Transformed::yes(plan.recompute_schema()?))
619676
}
620677

621-
/// Whether the pull up can add its columns to `group_expr` without changing
622-
/// what the aggregate returns.
678+
/// Whether the pull up can add its columns to a grouping set `Aggregate`,
679+
/// and whether it needs to.
623680
///
624-
/// `true` when `group_expr` holds no grouping set, and when every set of every
625-
/// grouping set it holds already groups by each column
626-
/// [`Self::collect_missing_exprs`] would add. In the second case the pull up
627-
/// adds nothing and the aggregate keeps the sets it has.
681+
/// [`GroupingSetsPullUp::NoColumnsToAdd`] when every set of every grouping
682+
/// set already groups by each column [`Self::collect_missing_exprs`]
683+
/// would add: the pull up adds nothing and the aggregate keeps the sets
684+
/// it has.
628685
///
629-
/// `ROLLUP` and `CUBE` always contain the empty set, which yields a row for
630-
/// outer rows the correlated filter matches nothing for, so they are only safe
631-
/// when there is nothing to add.
686+
/// Otherwise some set leaves a required column out, which fills that
687+
/// column with `NULL` in the set's rows. Adding the column to every set
688+
/// (`LogicalPlanBuilder::aggregate` cross joins a plain group expression
689+
/// with the sets that are already there) gives it a value instead. This
690+
/// is only invisible to the rest of the query when:
691+
/// - no set is empty. `ROLLUP(i.k)`, `GROUPING SETS ((i.k), ())`, always
692+
/// holds one, and turns into `GROUPING SETS ((i.k), (i.k, i.k))`,
693+
/// losing the empty set and the grand total row it yields for every
694+
/// outer row, including the rows the correlated filter matches
695+
/// nothing for. The join that replaces the filter cannot bring that
696+
/// row back.
697+
/// - the aggregate does not compute `GROUPING`/`GROUPING_ID`, which
698+
/// reads whether a row's set groups by a column.
699+
/// - nothing above the aggregate reads the column, which
700+
/// `column_refs_above_aggregate` was populated with ahead of time (this
701+
/// rewrite runs bottom-up, so a `HAVING` or `Projection` above the
702+
/// aggregate is only visited after it).
632703
///
633-
/// A non-empty set that leaves a column out fills it with NULL. Adding the
634-
/// column would give it a value instead, which a `HAVING` or a projection
635-
/// above the aggregate can read, so such a set is rejected as well.
636-
fn grouping_sets_cover_pull_up_cols(
704+
/// When one of these fails, [`GroupingSetsPullUp::Unsafe`] is returned:
705+
/// the columns are still added, so the schema the nodes above expect
706+
/// stays correct, but the caller must give up on decorrelating.
707+
fn grouping_sets_pull_up_outcome(
637708
&self,
638-
group_expr: &[Expr],
709+
aggregate: &Aggregate,
639710
correlated_subquery_cols: &BTreeSet<Column>,
640-
) -> bool {
711+
) -> GroupingSetsPullUp {
712+
let group_expr = &aggregate.group_expr;
641713
let grouping_sets = group_expr
642714
.iter()
643715
.filter_map(|expr| match expr {
@@ -646,7 +718,7 @@ impl PullUpCorrelatedExpr {
646718
})
647719
.collect::<Vec<_>>();
648720
if grouping_sets.is_empty() {
649-
return true;
721+
return GroupingSetsPullUp::NoColumnsToAdd;
650722
}
651723

652724
// The same columns `collect_missing_exprs` appends: the correlated columns
@@ -662,18 +734,37 @@ impl PullUpCorrelatedExpr {
662734
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
663735
});
664736
if required_cols.is_empty() {
665-
return true;
737+
return GroupingSetsPullUp::NoColumnsToAdd;
666738
}
667739

668-
grouping_sets.iter().all(|grouping_set| match grouping_set {
669-
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => false,
670-
GroupingSet::GroupingSets(sets) => sets.iter().all(|set| {
671-
required_cols.iter().all(|col| {
672-
set.iter()
673-
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
674-
})
675-
}),
676-
})
740+
let already_covered =
741+
grouping_sets.iter().all(|grouping_set| match grouping_set {
742+
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => false,
743+
GroupingSet::GroupingSets(sets) => sets.iter().all(|set| {
744+
required_cols.iter().all(|col| {
745+
set.iter()
746+
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
747+
})
748+
}),
749+
});
750+
if already_covered {
751+
return GroupingSetsPullUp::NoColumnsToAdd;
752+
}
753+
754+
let has_empty_set = grouping_sets.iter().any(|grouping_set| match grouping_set {
755+
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => true,
756+
GroupingSet::GroupingSets(sets) => sets.iter().any(|set| set.is_empty()),
757+
});
758+
let reads_grouping_fn = aggregate.aggr_expr.iter().any(is_grouping_call);
759+
let read_above = required_cols
760+
.iter()
761+
.any(|col| self.column_refs_above_aggregate.contains(*col));
762+
763+
if has_empty_set || reads_grouping_fn || read_above {
764+
GroupingSetsPullUp::Unsafe
765+
} else {
766+
GroupingSetsPullUp::SafeToExtend
767+
}
677768
}
678769

679770
fn collect_missing_exprs(
@@ -828,6 +919,45 @@ fn can_pullup_over_aggregation(expr: &Expr) -> bool {
828919
}
829920
}
830921

922+
/// Whether `expr` computes `GROUPING`/`GROUPING_ID`, which reads whether a
923+
/// row's grouping set groups by a particular column.
924+
fn is_grouping_call(expr: &Expr) -> bool {
925+
matches!(expr, Expr::AggregateFunction(agg) if agg.func.name().eq_ignore_ascii_case("grouping"))
926+
}
927+
928+
/// Columns read by a node strictly above the first `Aggregate` found in
929+
/// `plan`, which is the subquery's original, not yet rewritten, plan.
930+
///
931+
/// [`PullUpCorrelatedExpr::f_up`] runs bottom-up, so by the time it visits an
932+
/// `Aggregate` it cannot yet tell whether a `HAVING` or `Projection` above it
933+
/// reads one of the columns a grouping set pull up would add. This walks the
934+
/// plan top-down instead, before the rewrite starts, and stops at the first
935+
/// `Aggregate` along each branch, collecting the columns every node above it
936+
/// reads in its own expressions. A nested `Subquery` is a different
937+
/// correlation scope and is skipped, the same way
938+
/// [`PullUpCorrelatedExpr::f_down`] skips it.
939+
fn columns_read_above_aggregate(plan: &LogicalPlan) -> BTreeSet<Column> {
940+
fn walk(plan: &LogicalPlan, above: &mut BTreeSet<Column>) -> bool {
941+
if matches!(plan, LogicalPlan::Subquery(_)) {
942+
return false;
943+
}
944+
if matches!(plan, LogicalPlan::Aggregate(_)) {
945+
return true;
946+
}
947+
let found_below = plan.inputs().into_iter().any(|child| walk(child, above));
948+
if found_below {
949+
for expr in plan.expressions() {
950+
above.extend(expr.column_refs().into_iter().cloned());
951+
}
952+
}
953+
found_below
954+
}
955+
956+
let mut above = BTreeSet::new();
957+
walk(plan, &mut above);
958+
above
959+
}
960+
831961
fn collect_local_correlated_cols(
832962
plan: &LogicalPlan,
833963
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)