Skip to content

Commit 1a2ad03

Browse files
adriangbclaude
andcommitted
feat: decorrelate a window below a correlated equality filter
When a correlated filter below a Window fixes the value of each column it reads for each outer row (`inner.y = outer.k`), add those columns to the PARTITION BY of every window function and pull the filter above the window. This is what Spark and DuckDB do, and it decorrelates apache#25792. A Projection on top keeps the old window column names. Other filters on non-partition columns still keep the subquery correlated. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01NZEssuMQANC3qLy1k2zUus
1 parent decd3ec commit 1a2ad03

3 files changed

Lines changed: 135 additions & 39 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 67 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ use datafusion_expr::utils::{
3737
};
3838
use datafusion_expr::{
3939
BinaryExpr, Cast, Distinct, EmptyRelation, Expr, ExprSchemable, FetchType,
40-
LogicalPlan, LogicalPlanBuilder, Operator, expr, lit,
40+
LogicalPlan, LogicalPlanBuilder, Operator, Window, expr, lit,
4141
};
4242

4343
/// This struct rewrite the sub query plan by pull up the correlated
@@ -563,17 +563,30 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
563563
);
564564
// A filter that reads only `PARTITION BY` columns keeps or drops
565565
// whole partitions, so each window function sees the same rows
566-
// above it or below it. A filter on any other column changes the
567-
// rows of a partition.
568-
if !local_correlated_cols.is_empty()
569-
&& !window
566+
// above it or below it.
567+
if local_correlated_cols.is_empty()
568+
|| window
570569
.window_expr
571570
.iter()
572571
.all(|expr| partitions_by_all(expr, &local_correlated_cols))
572+
{
573+
return self.pass_through_pulled_up_cols(plan);
574+
}
575+
// A filter that fixes the value of each column it reads for each
576+
// outer row, like `inner.y = outer.k`, keeps the rows of one
577+
// value of those columns. Partitioning by those columns as well
578+
// gives each window function the same rows once the filter is
579+
// above it. This is what the pull up does for an Aggregate too.
580+
if !self.can_pull_over_aggregation
581+
|| self.collected_count_expr_map.contains_key(&*window.input)
573582
{
574583
self.can_pull_up = false;
584+
return self.pass_through_pulled_up_cols(plan);
575585
}
576-
self.pass_through_pulled_up_cols(plan)
586+
Ok(Transformed::yes(partition_window_by(
587+
window,
588+
&local_correlated_cols,
589+
)?))
577590
}
578591
// `f_down` checked that the pulled up filters do not read an
579592
// unnested column.
@@ -777,6 +790,54 @@ fn correlated_filter_columns(plan: &LogicalPlan) -> Vec<Column> {
777790
cols
778791
}
779792

793+
/// Adds `cols` to the `PARTITION BY` of every window function of `window`.
794+
/// That changes the names of the window function columns, so a Projection on
795+
/// top gives them their old names back.
796+
fn partition_window_by(window: &Window, cols: &BTreeSet<Column>) -> Result<LogicalPlan> {
797+
let new_window_expr = window
798+
.window_expr
799+
.iter()
800+
.map(|expr| add_partition_by(expr, cols))
801+
.collect::<Vec<_>>();
802+
let mut proj_exprs = window
803+
.input
804+
.schema()
805+
.columns()
806+
.into_iter()
807+
.map(Expr::Column)
808+
.collect::<Vec<_>>();
809+
for (old, new) in window.window_expr.iter().zip(&new_window_expr) {
810+
let new_col = Expr::Column(Column::from_name(new.schema_name().to_string()));
811+
proj_exprs.push(new_col.alias(old.schema_name().to_string()));
812+
}
813+
LogicalPlanBuilder::from(LogicalPlan::Window(Window::try_new(
814+
new_window_expr,
815+
Arc::clone(&window.input),
816+
)?))
817+
.project(proj_exprs)?
818+
.build()
819+
}
820+
821+
fn add_partition_by(expr: &Expr, cols: &BTreeSet<Column>) -> Expr {
822+
match expr {
823+
Expr::Alias(alias) => Expr::Alias(Alias {
824+
expr: Box::new(add_partition_by(&alias.expr, cols)),
825+
..alias.clone()
826+
}),
827+
Expr::WindowFunction(window_fun) => {
828+
let mut window_fun = window_fun.clone();
829+
for col in cols {
830+
let col = Expr::Column(col.clone());
831+
if !window_fun.params.partition_by.contains(&col) {
832+
window_fun.params.partition_by.push(col);
833+
}
834+
}
835+
Expr::WindowFunction(window_fun)
836+
}
837+
_ => expr.clone(),
838+
}
839+
}
840+
780841
/// Whether the window function `expr` lists each of `cols` as a plain
781842
/// `PARTITION BY` column.
782843
fn partitions_by_all(expr: &Expr, cols: &BTreeSet<Column>) -> bool {

‎datafusion/sqllogictest/test_files/lateral_join.slt‎

Lines changed: 25 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -755,16 +755,20 @@ ORDER BY t1.id, sub.x;
755755

756756
# --- Correlated filter below a window function ---
757757
# https://github.com/apache/datafusion/issues/25792
758-
# Pulling `t2.t1_id = t1.id` above the window would number the t2 rows of all
759-
# t1 rows together instead of the t2 rows of each t1 row.
760-
# Expected result once supported: (1, 10, 1), (1, 20, 2), (2, 30, 1).
761-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression OuterReferenceColumn
758+
# Pulling `t2.t1_id = t1.id` above the window as it is would number the t2 rows
759+
# of all t1 rows together. The filter fixes `t2.t1_id` for each t1 row, so the
760+
# pull up adds `t2.t1_id` to the `PARTITION BY` of the window instead.
761+
query III
762762
SELECT t1.id, sub.id, sub.rn
763763
FROM t1, LATERAL (
764764
SELECT t2.id, row_number() OVER (ORDER BY t2.id) AS rn
765765
FROM (SELECT * FROM t2 WHERE t2.t1_id = t1.id) AS t2
766766
) AS sub
767767
ORDER BY t1.id, sub.id;
768+
----
769+
1 10 1
770+
1 20 2
771+
2 30 1
768772

769773
# A correlated filter above the window is still decorrelated. The window
770774
# numbers all t2 rows, then the filter keeps the rows of each t1 row.
@@ -850,8 +854,8 @@ ORDER BY t1.id, sub.id;
850854
1 20 2
851855
2 30 1
852856

853-
# The filter must read a `PARTITION BY` column of every window function.
854-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression OuterReferenceColumn
857+
# Every window function is partitioned by the columns of the filter.
858+
query IIII
855859
SELECT t1.id, sub.id, sub.rn, sub.c
856860
FROM t1, LATERAL (
857861
SELECT t2.id,
@@ -860,6 +864,21 @@ FROM t1, LATERAL (
860864
FROM t2 WHERE t2.t1_id = t1.id
861865
) AS sub
862866
ORDER BY t1.id, sub.id;
867+
----
868+
1 10 1 1
869+
1 20 2 1
870+
2 30 1 1
871+
872+
# A non-equality filter does not fix the value of its column for each t1 row,
873+
# so partitioning by the column would split the rows of one t1 row. The
874+
# subquery stays correlated.
875+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression OuterReferenceColumn
876+
SELECT t1.id, sub.id, sub.rn
877+
FROM t1, LATERAL (
878+
SELECT t2.id, row_number() OVER (ORDER BY t2.id) AS rn
879+
FROM t2 WHERE t2.t1_id >= t1.id
880+
) AS sub
881+
ORDER BY t1.id, sub.id;
863882

864883
# --- Implicit LATERAL (comma without LATERAL keyword) ---
865884
# DuckDB auto-detects lateral correlation; DataFusion requires

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 43 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -3032,10 +3032,11 @@ DROP TABLE oj_a;
30323032
statement ok
30333033
DROP TABLE oj_b;
30343034

3035-
# Regression test for #25792: a correlated filter below a window function must
3036-
# not be pulled above the window. The filter selects the rows the window
3037-
# function sees for each outer row, so once it is above the window the window
3038-
# function runs over all rows and computes different values.
3035+
# Regression test for #25792: a correlated filter below a window function
3036+
# selects the rows the window function sees for each outer row. Pulled above
3037+
# the window as it is, the window function would run over all rows and compute
3038+
# different values. The filter `y = k` fixes `y` for each outer row, so the pull
3039+
# up adds `y` to the `PARTITION BY` of the window, which keeps the values.
30393040
statement ok
30403041
CREATE TABLE win_outer(k INT) AS VALUES (1), (2), (5);
30413042

@@ -3045,39 +3046,49 @@ CREATE TABLE win_inner(id INT, y INT) AS VALUES (1, 1), (2, 2);
30453046
statement ok
30463047
set datafusion.explain.logical_plan_only = true;
30473048

3048-
# The correlated filter is below the window, so the subquery stays correlated.
3049+
# The correlated filter is below the window, so the window is partitioned by b.y.
30493050
query TT
30503051
EXPLAIN SELECT win_outer.k FROM win_outer WHERE EXISTS (SELECT 1 FROM (SELECT b.id, row_number() OVER (ORDER BY b.id) AS rn FROM (SELECT * FROM win_inner WHERE win_inner.y = win_outer.k) AS b) AS w WHERE w.rn = 1);
30513052
----
30523053
logical_plan
3053-
01)Filter: EXISTS (<subquery>)
3054-
02)--Subquery:
3055-
03)----Projection: Int64(1)
3056-
04)------SubqueryAlias: w
3057-
05)--------Projection: b.id, row_number() ORDER BY [b.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS rn
3058-
06)----------Filter: row_number() ORDER BY [b.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW = UInt64(1)
3059-
07)------------WindowAggr: windowExpr=[[row_number() ORDER BY [b.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
3060-
08)--------------SubqueryAlias: b
3061-
09)----------------Projection: win_inner.id, win_inner.y
3062-
10)------------------Filter: win_inner.y = outer_ref(win_outer.k)
3063-
11)--------------------TableScan: win_inner
3064-
12)--TableScan: win_outer projection=[k]
3065-
3066-
# It errors rather than returning wrong results. The right answer is `1, 2`.
3067-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
3054+
01)LeftSemi Join: win_outer.k = __correlated_sq_1.y
3055+
02)--TableScan: win_outer projection=[k]
3056+
03)--SubqueryAlias: __correlated_sq_1
3057+
04)----SubqueryAlias: w
3058+
05)------Projection: b.y
3059+
06)--------Filter: row_number() PARTITION BY [b.y] ORDER BY [b.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW = UInt64(1)
3060+
07)----------Projection: b.y, row_number() PARTITION BY [b.y] ORDER BY [b.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
3061+
08)------------WindowAggr: windowExpr=[[row_number() PARTITION BY [b.y] ORDER BY [b.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
3062+
09)--------------SubqueryAlias: b
3063+
10)----------------TableScan: win_inner projection=[id, y]
3064+
3065+
# The right answer is `1, 2`.
3066+
query I
30683067
SELECT win_outer.k FROM win_outer WHERE EXISTS (SELECT 1 FROM (SELECT b.id, row_number() OVER (ORDER BY b.id) AS rn FROM (SELECT * FROM win_inner WHERE win_inner.y = win_outer.k) AS b) AS w WHERE w.rn = 1) ORDER BY win_outer.k;
3068+
----
3069+
1
3070+
2
30693071

30703072
# The same for NOT EXISTS. The right answer is `5`.
3071-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
3073+
query I
30723074
SELECT win_outer.k FROM win_outer WHERE NOT EXISTS (SELECT 1 FROM (SELECT b.id, row_number() OVER (ORDER BY b.id) AS rn FROM (SELECT * FROM win_inner WHERE win_inner.y = win_outer.k) AS b) AS w WHERE w.rn = 1) ORDER BY win_outer.k;
3075+
----
3076+
5
30733077

30743078
# The same for IN. The right answer is `1, 2`.
3075-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression InSubquery
3079+
query I
30763080
SELECT win_outer.k FROM win_outer WHERE 1 IN (SELECT row_number() OVER (ORDER BY win_inner.id) FROM win_inner WHERE win_inner.y = win_outer.k) ORDER BY win_outer.k;
3081+
----
3082+
1
3083+
2
30773084

30783085
# And for a scalar subquery. The right answer is `(1, 1), (2, 1), (5, NULL)`.
3079-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression ScalarSubquery
3086+
query II
30803087
SELECT win_outer.k, (SELECT max(w.rn) FROM (SELECT row_number() OVER (ORDER BY win_inner.id) AS rn FROM win_inner WHERE win_inner.y = win_outer.k) AS w) AS m FROM win_outer ORDER BY win_outer.k;
3088+
----
3089+
1 1
3090+
2 1
3091+
5 NULL
30813092

30823093
# A correlated filter above the window is still pulled up, because the window
30833094
# input does not depend on the outer row.
@@ -3100,8 +3111,8 @@ SELECT win_outer.k FROM win_outer WHERE EXISTS (SELECT 1 FROM (SELECT win_inner.
31003111
2
31013112

31023113
# A correlated filter below the window that reads only a `PARTITION BY` column
3103-
# keeps or drops whole partitions, so it is pulled above the window. This holds
3104-
# for a non-equality filter too. The right answer is `1`.
3114+
# keeps or drops whole partitions, so it is pulled above the window as it is.
3115+
# This holds for a non-equality filter too. The right answer is `1`.
31053116
query I
31063117
SELECT win_outer.k FROM win_outer WHERE EXISTS (SELECT 1 FROM (SELECT row_number() OVER (PARTITION BY win_inner.y ORDER BY win_inner.id) AS rn FROM win_inner WHERE win_inner.y > win_outer.k) AS w WHERE w.rn = 1) ORDER BY win_outer.k;
31073118
----
@@ -3122,9 +3133,14 @@ SELECT win_outer.k, (SELECT max(w.rn) FROM (SELECT row_number() OVER (PARTITION
31223133
2 1
31233134
5 NULL
31243135

3125-
# A window that partitions by an expression of the column does not count.
3126-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression ScalarSubquery
3136+
# A window that partitions by an expression of the column is partitioned by
3137+
# the column as well.
3138+
query II
31273139
SELECT win_outer.k, (SELECT max(w.rn) FROM (SELECT row_number() OVER (PARTITION BY win_inner.y + 0 ORDER BY win_inner.id) AS rn FROM win_inner WHERE win_inner.y = win_outer.k) AS w) AS m FROM win_outer ORDER BY win_outer.k;
3140+
----
3141+
1 1
3142+
2 1
3143+
5 NULL
31283144

31293145
# A window over an aggregate with count bug handling stays correlated.
31303146
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression ScalarSubquery

0 commit comments

Comments
 (0)