Skip to content

Commit d94df03

Browse files
compheadadriangb
andcommitted
feat: decorrelate a window below a correlated equality filter
When every correlated conjunct below a window has the form `col = <outer expr>`, add `col` to the `PARTITION BY` of every window function and pull the filter above the window. A Projection keeps the old window column names. A lossy `CAST(col)` and an input with count bug handling keep the subquery correlated. Also track the columns of the conjuncts that `remove_duplicated_filter` drops because the `IN` predicate repeats them, so that the window is partitioned by them too. Such an `IN` subquery returned wrong results. Closes apache#25897. Co-authored-by: Adrian Garcia Badaracco <[email protected]>
1 parent 1da3cf0 commit d94df03

4 files changed

Lines changed: 285 additions & 62 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 151 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,8 @@ use datafusion_common::tree_node::{
2727
Transformed, TransformedResult, TreeNode, TreeNodeRecursion, TreeNodeRewriter,
2828
};
2929
use datafusion_common::{
30-
Column, DFSchemaRef, HashMap, Result, ScalarValue, assert_or_internal_err, plan_err,
30+
Column, DFSchemaRef, HashMap, Result, ScalarValue, TableReference,
31+
assert_or_internal_err, plan_err,
3132
};
3233
use datafusion_expr::expr::{Alias, GroupingSet};
3334
use datafusion_expr::logical_plan::{Join, JoinType};
@@ -38,8 +39,9 @@ use datafusion_expr::utils::{
3839
use datafusion_expr::{
3940
BinaryExpr, Cast, Distinct, EmptyRelation, Expr, ExprSchemable, Extension, FetchType,
4041
LogicalPlan, LogicalPlanBuilder, MaterializedCte, Operator, SkipType,
41-
UserDefinedLogicalNodeCore, expr, lit,
42+
UserDefinedLogicalNodeCore, Window, expr, lit,
4243
};
44+
use itertools::Itertools;
4345

4446
/// This struct rewrite the sub query plan by pull up the correlated
4547
/// expressions(contains outer reference columns) from the inner subquery's
@@ -51,6 +53,11 @@ pub struct PullUpCorrelatedExpr {
5153
pub join_filters: Vec<Expr>,
5254
/// mapping from the plan to its holding correlated columns
5355
pub correlated_subquery_cols_map: HashMap<LogicalPlan, BTreeSet<Column>>,
56+
/// The columns of the correlated conjuncts that `remove_duplicated_filter`
57+
/// drops because the `IN` predicate repeats them. The join still applies
58+
/// those conjuncts, so a Window between them and the join has to partition
59+
/// by these columns too.
60+
in_predicate_cols_map: HashMap<LogicalPlan, BTreeSet<Column>>,
5461
pub in_predicate_opt: Option<Expr>,
5562
/// Is this an Exists(Not Exists) SubQuery. Defaults to **FALSE**
5663
pub exists_sub_query: bool,
@@ -59,6 +66,10 @@ pub struct PullUpCorrelatedExpr {
5966
/// Indicates if we encounter any correlated expression that can not be pulled up
6067
/// above a aggregation without changing the meaning of the query.
6168
can_pull_over_aggregation: bool,
69+
/// Whether every correlated conjunct seen so far satisfies
70+
/// [`is_column_equality`], so that a Window above them can partition by
71+
/// their columns.
72+
can_extend_partition_by: bool,
6273
/// Do we need to handle [the count bug] during the pull up process.
6374
///
6475
/// The "count bug" was described in [Optimization of Nested SQL
@@ -105,10 +116,12 @@ impl PullUpCorrelatedExpr {
105116
Self {
106117
join_filters: vec![],
107118
correlated_subquery_cols_map: HashMap::new(),
119+
in_predicate_cols_map: HashMap::new(),
108120
in_predicate_opt: None,
109121
exists_sub_query: false,
110122
can_pull_up: true,
111123
can_pull_over_aggregation: true,
124+
can_extend_partition_by: true,
112125
need_handle_count_bug: false,
113126
collected_count_expr_map: HashMap::new(),
114127
pull_up_having_expr: None,
@@ -347,19 +360,28 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
347360
.iter()
348361
.filter(|e| e.contains_outer())
349362
.all(|&e| can_pullup_over_aggregation(e));
363+
self.can_extend_partition_by = self.can_extend_partition_by
364+
&& subquery_filter_exprs
365+
.iter()
366+
.filter(|e| e.contains_outer())
367+
.all(|&e| is_column_equality(e));
350368
for expr in &subquery_filter_exprs {
351369
if expr.contains_outer() && !self.correlated_filters.contains(expr) {
352370
self.correlated_filters.push((*expr).clone());
353371
}
354372
}
355373
let (mut join_filters, subquery_filters) =
356374
find_join_exprs(subquery_filter_exprs)?;
375+
let mut in_predicate_cols = BTreeSet::new();
357376
if let Some(in_predicate) = &self.in_predicate_opt {
377+
in_predicate_cols =
378+
collect_subquery_cols(&join_filters, subquery_schema)?;
358379
// in_predicate may be already included in the join filters, remove it from the join filters first.
359380
join_filters = remove_duplicated_filter(join_filters, in_predicate)?;
360381
}
361382
let correlated_subquery_cols =
362383
collect_subquery_cols(&join_filters, subquery_schema)?;
384+
in_predicate_cols.retain(|col| !correlated_subquery_cols.contains(col));
363385
for expr in join_filters {
364386
if !self.join_filters.contains(&expr) {
365387
self.join_filters.push(expr)
@@ -384,19 +406,14 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
384406
None
385407
};
386408

387-
match (&pull_up_expr_opt, &self.pull_up_having_expr) {
409+
let new_plan = match (&pull_up_expr_opt, &self.pull_up_having_expr) {
388410
(Some(_), Some(_)) => {
389411
// Error path
390-
plan_err!("Unsupported Subquery plan")
412+
return plan_err!("Unsupported Subquery plan");
391413
}
392414
(Some(_), None) => {
393415
self.pull_up_having_expr = pull_up_expr_opt;
394-
let new_plan =
395-
LogicalPlanBuilder::from((*plan_filter.input).clone())
396-
.build()?;
397-
self.correlated_subquery_cols_map
398-
.insert(new_plan.clone(), correlated_subquery_cols);
399-
Ok(Transformed::yes(new_plan))
416+
LogicalPlanBuilder::from((*plan_filter.input).clone()).build()?
400417
}
401418
(None, _) => {
402419
// if the subquery still has filter expressions, restore them.
@@ -405,12 +422,16 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
405422
if let Some(expr) = conjunction(subquery_filters) {
406423
plan = plan.filter(expr)?
407424
}
408-
let new_plan = plan.build()?;
409-
self.correlated_subquery_cols_map
410-
.insert(new_plan.clone(), correlated_subquery_cols);
411-
Ok(Transformed::yes(new_plan))
425+
plan.build()?
412426
}
427+
};
428+
self.correlated_subquery_cols_map
429+
.insert(new_plan.clone(), correlated_subquery_cols);
430+
if !in_predicate_cols.is_empty() {
431+
self.in_predicate_cols_map
432+
.insert(new_plan.clone(), in_predicate_cols);
413433
}
434+
Ok(Transformed::yes(new_plan))
414435
}
415436
LogicalPlan::Projection(projection)
416437
if self.in_predicate_opt.is_some() || !self.join_filters.is_empty() =>
@@ -548,17 +569,16 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
548569
Ok(Transformed::yes(new_plan))
549570
}
550571
LogicalPlan::SubqueryAlias(alias) => {
551-
let mut local_correlated_cols = BTreeSet::new();
552-
collect_local_correlated_cols(
572+
let new_correlated_cols = aliased_local_correlated_cols(
553573
&plan,
554574
&self.correlated_subquery_cols_map,
555-
&mut local_correlated_cols,
575+
&alias.alias,
576+
);
577+
let new_in_predicate_cols = aliased_local_correlated_cols(
578+
&plan,
579+
&self.in_predicate_cols_map,
580+
&alias.alias,
556581
);
557-
let mut new_correlated_cols = BTreeSet::new();
558-
for col in local_correlated_cols.iter() {
559-
new_correlated_cols
560-
.insert(Column::new(Some(alias.alias.clone()), col.name.clone()));
561-
}
562582

563583
let new_plan = if alias.input.schema().fields().len()
564584
!= alias.schema.fields().len()
@@ -572,6 +592,10 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
572592

573593
self.correlated_subquery_cols_map
574594
.insert(new_plan.clone(), new_correlated_cols);
595+
if !new_in_predicate_cols.is_empty() {
596+
self.in_predicate_cols_map
597+
.insert(new_plan.clone(), new_in_predicate_cols);
598+
}
575599
if let Some(input_map) = self.collected_count_expr_map.get(&*alias.input)
576600
{
577601
self.collected_count_expr_map
@@ -600,19 +624,36 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
600624
&self.correlated_subquery_cols_map,
601625
&mut local_correlated_cols,
602626
);
627+
collect_local_correlated_cols(
628+
&plan,
629+
&self.in_predicate_cols_map,
630+
&mut local_correlated_cols,
631+
);
603632
// A filter that reads only `PARTITION BY` columns keeps or drops
604633
// whole partitions, so each window function sees the same rows
605-
// above it or below it. A filter on any other column changes the
606-
// rows of a partition.
607-
if !local_correlated_cols.is_empty()
608-
&& !window
634+
// above it or below it.
635+
if local_correlated_cols.is_empty()
636+
|| window
609637
.window_expr
610638
.iter()
611639
.all(|expr| partitions_by_all(expr, &local_correlated_cols))
640+
{
641+
return self.pass_through_pulled_up_cols(plan);
642+
}
643+
// A filter like `inner.y = outer.k` keeps the rows of one `y`
644+
// value for each outer row. Partitioning by `y` as well gives
645+
// each window function the same rows once the filter is above
646+
// it. This is what the pull up does for an Aggregate too.
647+
if !self.can_extend_partition_by
648+
|| self.collected_count_expr_map.contains_key(&*window.input)
612649
{
613650
self.can_pull_up = false;
651+
return self.pass_through_pulled_up_cols(plan);
614652
}
615-
self.pass_through_pulled_up_cols(plan)
653+
Ok(Transformed::yes(partition_window_by(
654+
window,
655+
&local_correlated_cols,
656+
)?))
616657
}
617658
// `f_down` checked that the pulled up filters do not read an
618659
// unnested column.
@@ -817,6 +858,56 @@ fn correlated_filter_columns(plan: &LogicalPlan) -> Vec<Column> {
817858
cols
818859
}
819860

861+
/// Adds `cols` to the `PARTITION BY` of every window function of `window`.
862+
/// That changes the names of the window function columns, so a Projection on
863+
/// top gives them their old names back.
864+
fn partition_window_by(window: &Window, cols: &BTreeSet<Column>) -> Result<LogicalPlan> {
865+
let new_window_expr = window
866+
.window_expr
867+
.iter()
868+
.map(|expr| add_partition_by(expr, cols))
869+
.collect::<Vec<_>>();
870+
let mut proj_exprs = window
871+
.input
872+
.schema()
873+
.columns()
874+
.into_iter()
875+
.map(Expr::Column)
876+
.collect::<Vec<_>>();
877+
for (old, new) in window.window_expr.iter().zip(&new_window_expr) {
878+
let new_col = Expr::Column(Column::from_name(new.schema_name().to_string()));
879+
proj_exprs.push(new_col.alias(old.schema_name().to_string()));
880+
}
881+
// Window functions that differed only in the added columns are now equal.
882+
let new_window_expr = new_window_expr.into_iter().unique().collect();
883+
LogicalPlanBuilder::from(LogicalPlan::Window(Window::try_new(
884+
new_window_expr,
885+
Arc::clone(&window.input),
886+
)?))
887+
.project(proj_exprs)?
888+
.build()
889+
}
890+
891+
fn add_partition_by(expr: &Expr, cols: &BTreeSet<Column>) -> Expr {
892+
match expr {
893+
Expr::Alias(alias) => Expr::Alias(Alias {
894+
expr: Box::new(add_partition_by(&alias.expr, cols)),
895+
..alias.clone()
896+
}),
897+
Expr::WindowFunction(window_fun) => {
898+
let mut window_fun = window_fun.clone();
899+
for col in cols {
900+
let col = Expr::Column(col.clone());
901+
if !window_fun.params.partition_by.contains(&col) {
902+
window_fun.params.partition_by.push(col);
903+
}
904+
}
905+
Expr::WindowFunction(window_fun)
906+
}
907+
_ => expr.clone(),
908+
}
909+
}
910+
820911
/// Whether the window function `expr` lists each of `cols` as a plain
821912
/// `PARTITION BY` column.
822913
fn partitions_by_all(expr: &Expr, cols: &BTreeSet<Column>) -> bool {
@@ -862,6 +953,39 @@ fn can_pullup_over_aggregation(expr: &Expr) -> bool {
862953
}
863954
}
864955

956+
/// Whether `expr` is `col = <expr>` or `<expr> = col`, where `<expr>` reads no
957+
/// subquery column. Unlike [`can_pullup_over_aggregation`], this rejects
958+
/// `CAST(col AS ..) = <expr>`: a lossy cast lets several `col` values match one
959+
/// outer row, and partitioning by `col` would split those rows.
960+
fn is_column_equality(expr: &Expr) -> bool {
961+
let Expr::BinaryExpr(BinaryExpr {
962+
left,
963+
op: Operator::Eq,
964+
right,
965+
}) = expr
966+
else {
967+
return false;
968+
};
969+
match (&**left, &**right) {
970+
(Expr::Column(_), other) | (other, Expr::Column(_)) => !other.any_column_refs(),
971+
_ => false,
972+
}
973+
}
974+
975+
/// [`collect_local_correlated_cols`], with each column qualified by `alias`.
976+
fn aliased_local_correlated_cols(
977+
plan: &LogicalPlan,
978+
all_cols_map: &HashMap<LogicalPlan, BTreeSet<Column>>,
979+
alias: &TableReference,
980+
) -> BTreeSet<Column> {
981+
let mut local_cols = BTreeSet::new();
982+
collect_local_correlated_cols(plan, all_cols_map, &mut local_cols);
983+
local_cols
984+
.into_iter()
985+
.map(|col| Column::new(Some(alias.clone()), col.name))
986+
.collect()
987+
}
988+
865989
fn collect_local_correlated_cols(
866990
plan: &LogicalPlan,
867991
all_cols_map: &HashMap<LogicalPlan, BTreeSet<Column>>,

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 51 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1107,9 +1107,10 @@ mod tests {
11071107
use crate::assert_optimized_plan_eq_display_indent_snapshot;
11081108
use arrow::datatypes::{DataType, Field, Schema};
11091109
use datafusion_expr::builder::table_source;
1110+
use datafusion_expr::expr::WindowFunction;
11101111
use datafusion_expr::{
1111-
TableScanBuilder, and, binary_expr, col, cube, grouping_set, out_ref_col, rollup,
1112-
table_scan,
1112+
ExprFunctionExt, TableScanBuilder, WindowFunctionDefinition, and, binary_expr,
1113+
col, cube, grouping_set, out_ref_col, rollup, table_scan,
11131114
};
11141115

11151116
macro_rules! assert_optimized_plan_equal {
@@ -3254,4 +3255,52 @@ mod tests {
32543255
"
32553256
)
32563257
}
3258+
3259+
/// Partitioning `rank() ORDER BY sq.b` by the correlated column `sq.a`
3260+
/// makes it equal to the other window function of the same Window, which
3261+
/// then computes it once.
3262+
#[test]
3263+
fn exists_subquery_window_functions_become_equal() -> Result<()> {
3264+
let rank = || {
3265+
Expr::from(WindowFunction::new(
3266+
WindowFunctionDefinition::WindowUDF(
3267+
datafusion_functions_window::rank::rank_udwf(),
3268+
),
3269+
vec![],
3270+
))
3271+
};
3272+
let subquery = Arc::new(
3273+
LogicalPlanBuilder::from(test_table_scan_with_name("sq")?)
3274+
.filter(col("sq.a").eq(out_ref_col(DataType::UInt32, "test.a")))?
3275+
.window(vec![
3276+
rank()
3277+
.order_by(vec![col("sq.b").sort(true, true)])
3278+
.build()?,
3279+
rank()
3280+
.partition_by(vec![col("sq.a")])
3281+
.order_by(vec![col("sq.b").sort(true, true)])
3282+
.build()?,
3283+
])?
3284+
.project(vec![col("sq.b")])?
3285+
.build()?,
3286+
);
3287+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
3288+
.filter(exists(subquery))?
3289+
.project(vec![col("test.b")])?
3290+
.build()?;
3291+
3292+
assert_optimized_plan_equal!(
3293+
plan,
3294+
@r"
3295+
Projection: test.b [b:UInt32]
3296+
LeftSemi Join: Filter: __correlated_sq_1.a = test.a [a:UInt32, b:UInt32, c:UInt32]
3297+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
3298+
SubqueryAlias: __correlated_sq_1 [b:UInt32, a:UInt32]
3299+
Projection: sq.b, sq.a [b:UInt32, a:UInt32]
3300+
Projection: sq.a, sq.b, sq.c, rank() PARTITION BY [sq.a] ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS rank() ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, rank() PARTITION BY [sq.a] ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS rank() PARTITION BY [sq.a] ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW [a:UInt32, b:UInt32, c:UInt32, rank() ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW:UInt64, rank() PARTITION BY [sq.a] ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW:UInt64]
3301+
WindowAggr: windowExpr=[[rank() PARTITION BY [sq.a] ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]] [a:UInt32, b:UInt32, c:UInt32, rank() PARTITION BY [sq.a] ORDER BY [sq.b ASC NULLS FIRST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW:UInt64]
3302+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
3303+
"
3304+
)
3305+
}
32573306
}

0 commit comments

Comments
 (0)