Skip to content

Commit f31fc8c

Browse files
adriangbclaude
andcommitted
fix: pull correlated filters through Window and Unnest when safe
Address review feedback: - Window: pull a correlated filter above the window when it reads only plain PARTITION BY columns of every window function, so it keeps or drops whole partitions. - Unnest: recompute the Unnest schema so it carries the columns the pull up adds below it. Stop when the filter reads an unnested column. - Stop at a Window or Unnest over an aggregate with count bug handling. - Use holds_outer_reference for Union, Sort, Extension and Limit. - Note that DISTINCT shares the Aggregate exemption and link apache#25808. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01NZEssuMQANC3qLy1k2zUus
1 parent 276de02 commit f31fc8c

4 files changed

Lines changed: 264 additions & 39 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 129 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -178,35 +178,64 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
178178
LogicalPlan::AsOfJoin(ref join) if holds_outer_reference(&join.right) => {
179179
Ok(self.stop_pull_up(plan))
180180
}
181+
// An Unnest replaces the column it unnests with the values of that
182+
// column, so a filter on it means something else above the
183+
// Unnest. The output column loses its qualifier, so compare names.
184+
LogicalPlan::Unnest(ref unnest)
185+
if correlated_filter_columns(&unnest.input).iter().any(|col| {
186+
unnest
187+
.exec_columns
188+
.iter()
189+
.any(|exec_col| exec_col.name == col.name)
190+
}) =>
191+
{
192+
Ok(self.stop_pull_up(plan))
193+
}
194+
// A correlated filter cannot move out of one input of a Union, and
195+
// `f_up` does not add its columns to a Sort or an Extension, so no
196+
// correlated filter may be below these nodes.
181197
LogicalPlan::Union(_) | LogicalPlan::Sort(_) | LogicalPlan::Extension(_) => {
182-
let plan_hold_outer = !plan.all_out_ref_exprs().is_empty();
183-
if plan_hold_outer {
184-
// the unsupported case
198+
if holds_outer_reference(&plan) {
185199
Ok(self.stop_pull_up(plan))
186200
} else {
187201
Ok(Transformed::no(plan))
188202
}
189203
}
204+
// `f_up` drops the Limit of an EXISTS subquery, which does not
205+
// change whether the subquery returns a row. Any other Limit keeps
206+
// the correlated filters below it.
190207
LogicalPlan::Limit(_) => {
191-
let plan_hold_outer = !plan.all_out_ref_exprs().is_empty();
192-
match (self.exists_sub_query, plan_hold_outer) {
208+
match (self.exists_sub_query, holds_outer_reference(&plan)) {
193209
(false, true) => {
194210
// the unsupported case
195211
Ok(self.stop_pull_up(plan))
196212
}
197213
_ => Ok(Transformed::no(plan)),
198214
}
199215
}
200-
// A correlated filter below these nodes can move above them. `f_up`
201-
// adds the columns the pulled up filter needs to a Projection or an
202-
// Aggregate, and checks that the filter can move above an
203-
// Aggregate. A `DISTINCT` gives the same rows when a filter runs
204-
// before it or after it, and its output takes the columns the node
205-
// below it adds. The node itself must not hold an outer reference,
206-
// because only a Filter gives its outer references to the join.
216+
// A correlated filter below these nodes can move above them. The
217+
// node itself must not hold an outer reference, because only a
218+
// Filter gives its outer references to the join.
219+
// - `f_up` adds the columns the pulled up filter needs to a
220+
// Projection or an Aggregate, and checks that the filter can move
221+
// above an Aggregate.
222+
// - A `DISTINCT` shares the exemption of an Aggregate without
223+
// aggregate functions: its output takes the columns the node
224+
// below it adds, so they become part of its keys. This is only
225+
// right when the pulled up filter fixes those columns for each
226+
// outer row. A non-equality filter can return duplicates, see
227+
// https://github.com/apache/datafusion/issues/25808.
228+
// - A Window keeps or drops whole partitions when the filter reads
229+
// only its `PARTITION BY` columns. `f_up` checks this.
230+
// - An Unnest maps each input row to its own output rows, so a
231+
// filter on a column it passes through keeps the same rows.
232+
// The arm above checks that the filter does not read an unnested
233+
// column.
207234
LogicalPlan::Projection(_)
208235
| LogicalPlan::Aggregate(_)
209236
| LogicalPlan::Distinct(Distinct::All(_))
237+
| LogicalPlan::Window(_)
238+
| LogicalPlan::Unnest(_)
210239
| LogicalPlan::Join(_)
211240
| LogicalPlan::AsOfJoin(_)
212241
| LogicalPlan::Repartition(_)
@@ -223,17 +252,11 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
223252
}
224253
}
225254
// A correlated filter below these nodes cannot move above them:
226-
// - A Window function reads the rows of its partition, so the
227-
// filter changes the rows each function sees.
228255
// - `DISTINCT ON` keeps the first row of each group, so the filter
229256
// changes which row is first.
230-
// - The pull up does not carry the columns of the pulled up filter
231-
// through an Unnest, and fails with a schema error.
232257
// - A RecursiveQuery repeats its recursive term.
233258
// - The other nodes are not queries and are not in a subquery.
234-
LogicalPlan::Window(_)
235-
| LogicalPlan::Distinct(Distinct::On(_))
236-
| LogicalPlan::Unnest(_)
259+
LogicalPlan::Distinct(Distinct::On(_))
237260
| LogicalPlan::RecursiveQuery(_)
238261
| LogicalPlan::Statement(_)
239262
| LogicalPlan::Explain(_)
@@ -528,6 +551,30 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
528551
}
529552
Ok(new_plan)
530553
}
554+
LogicalPlan::Window(window) => {
555+
let mut local_correlated_cols = BTreeSet::new();
556+
collect_local_correlated_cols(
557+
&plan,
558+
&self.correlated_subquery_cols_map,
559+
&mut local_correlated_cols,
560+
);
561+
// A filter that reads only `PARTITION BY` columns keeps or drops
562+
// whole partitions, so each window function sees the same rows
563+
// above it or below it. A filter on any other column changes the
564+
// rows of a partition.
565+
if !local_correlated_cols.is_empty()
566+
&& !window
567+
.window_expr
568+
.iter()
569+
.all(|expr| partitions_by_all(expr, &local_correlated_cols))
570+
{
571+
self.can_pull_up = false;
572+
}
573+
self.pass_through_pulled_up_cols(plan)
574+
}
575+
// `f_down` checked that the pulled up filters do not read an
576+
// unnested column.
577+
LogicalPlan::Unnest(_) => self.pass_through_pulled_up_cols(plan),
531578
_ => Ok(Transformed::no(plan)),
532579
}
533580
}
@@ -541,6 +588,32 @@ impl PullUpCorrelatedExpr {
541588
Transformed::new(plan, false, TreeNodeRecursion::Jump)
542589
}
543590

591+
/// Rebuilds a node whose output holds every column of its input, so that
592+
/// it outputs the columns the pull up added below it.
593+
///
594+
/// The count bug handling of a Projection or a Filter above reads the
595+
/// values an aggregate below gives on an empty input. Those values do not
596+
/// hold once a Window or an Unnest runs over the aggregate, so the pull up
597+
/// stops in that case.
598+
fn pass_through_pulled_up_cols(
599+
&mut self,
600+
plan: LogicalPlan,
601+
) -> Result<Transformed<LogicalPlan>> {
602+
if plan
603+
.inputs()
604+
.iter()
605+
.any(|input| self.collected_count_expr_map.contains_key(*input))
606+
{
607+
self.can_pull_up = false;
608+
}
609+
let new_plan = plan.clone().recompute_schema()?;
610+
if new_plan.schema() == plan.schema() {
611+
Ok(Transformed::no(plan))
612+
} else {
613+
Ok(Transformed::yes(new_plan))
614+
}
615+
}
616+
544617
/// Whether the pull up can add its columns to `group_expr` without changing
545618
/// what the aggregate returns.
546619
///
@@ -683,6 +756,43 @@ fn holds_outer_reference(plan: &LogicalPlan) -> bool {
683756
found
684757
}
685758

759+
/// The columns that the correlated conjuncts of the Filters in `plan` read,
760+
/// in the scope being decorrelated. Like [`holds_outer_reference`], this does
761+
/// not descend into a [`LogicalPlan::Subquery`].
762+
fn correlated_filter_columns(plan: &LogicalPlan) -> Vec<Column> {
763+
let mut cols = vec![];
764+
plan.apply(|node| {
765+
Ok(match node {
766+
LogicalPlan::Subquery(_) => TreeNodeRecursion::Jump,
767+
LogicalPlan::Filter(filter) => {
768+
for expr in split_conjunction(&filter.predicate) {
769+
if expr.contains_outer() {
770+
cols.extend(expr.column_refs().into_iter().cloned());
771+
}
772+
}
773+
TreeNodeRecursion::Continue
774+
}
775+
_ => TreeNodeRecursion::Continue,
776+
})
777+
})
778+
.expect("apply closure is infallible");
779+
cols
780+
}
781+
782+
/// Whether the window function `expr` lists each of `cols` as a plain
783+
/// `PARTITION BY` column.
784+
fn partitions_by_all(expr: &Expr, cols: &BTreeSet<Column>) -> bool {
785+
let Expr::WindowFunction(window_fun) = expr.clone().unalias_nested().data else {
786+
return false;
787+
};
788+
let partition_by = &window_fun.params.partition_by;
789+
cols.iter().all(|col| {
790+
partition_by
791+
.iter()
792+
.any(|expr| matches!(expr, Expr::Column(c) if c == col))
793+
})
794+
}
795+
686796
fn can_pullup_over_aggregation(expr: &Expr) -> bool {
687797
if let Expr::BinaryExpr(BinaryExpr {
688798
left,

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3077,4 +3077,42 @@ mod tests {
30773077
"
30783078
)
30793079
}
3080+
3081+
/// An Unnest replaces the column it unnests with the values of that
3082+
/// column. A correlated filter on that column below the Unnest compares
3083+
/// the whole list, so it cannot move above the Unnest.
3084+
#[test]
3085+
fn exists_subquery_filter_on_unnested_column() -> Result<()> {
3086+
let list_type =
3087+
DataType::List(Arc::new(Field::new_list_field(DataType::Int32, true)));
3088+
let schema = Schema::new(vec![
3089+
Field::new("id", DataType::Int32, true),
3090+
Field::new("arr", list_type.clone(), true),
3091+
]);
3092+
let subquery = Arc::new(
3093+
table_scan(Some("sq"), &schema, None)?
3094+
.filter(col("sq.arr").eq(out_ref_col(list_type, "outer_t.arr")))?
3095+
.unnest_column("arr")?
3096+
.project(vec![col("sq.id")])?
3097+
.build()?,
3098+
);
3099+
let plan = table_scan(Some("outer_t"), &schema, None)?
3100+
.filter(exists(subquery))?
3101+
.project(vec![col("outer_t.id")])?
3102+
.build()?;
3103+
3104+
assert_optimized_plan_equal!(
3105+
plan,
3106+
@r"
3107+
Projection: outer_t.id [id:Int32;N]
3108+
Filter: EXISTS (<subquery>) [id:Int32;N, arr:List(Int32);N]
3109+
Subquery: [id:Int32;N]
3110+
Projection: sq.id [id:Int32;N]
3111+
Unnest: lists[sq.arr|depth=1] structs[] [id:Int32;N, arr:Int32;N]
3112+
Filter: sq.arr = outer_ref(outer_t.arr) [id:Int32;N, arr:List(Int32);N]
3113+
TableScan: sq [id:Int32;N, arr:List(Int32);N]
3114+
TableScan: outer_t [id:Int32;N, arr:List(Int32);N]
3115+
"
3116+
)
3117+
}
30803118
}

‎datafusion/sqllogictest/test_files/lateral_join.slt‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -810,6 +810,57 @@ ORDER BY t1.id, sub.id;
810810
1 20 2
811811
2 30 3
812812

813+
# A correlated filter below the window that reads only a `PARTITION BY` column
814+
# keeps or drops whole partitions, so it is pulled above the window.
815+
query TT
816+
EXPLAIN SELECT t1.id, sub.id, sub.rn
817+
FROM t1, LATERAL (
818+
SELECT t2.id, row_number() OVER (PARTITION BY t2.t1_id ORDER BY t2.id) AS rn
819+
FROM t2 WHERE t2.t1_id = t1.id
820+
) AS sub
821+
ORDER BY t1.id, sub.id;
822+
----
823+
logical_plan
824+
01)Sort: t1.id ASC NULLS LAST, sub.id ASC NULLS LAST
825+
02)--Projection: t1.id, sub.id, sub.rn
826+
03)----Inner Join: t1.id = sub.t1_id
827+
04)------TableScan: t1 projection=[id]
828+
05)------SubqueryAlias: sub
829+
06)--------Projection: t2.id, row_number() PARTITION BY [t2.t1_id] ORDER BY [t2.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS rn, t2.t1_id
830+
07)----------WindowAggr: windowExpr=[[row_number() PARTITION BY [t2.t1_id] ORDER BY [t2.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
831+
08)------------TableScan: t2 projection=[id, t1_id]
832+
physical_plan
833+
01)SortExec: expr=[id@0 ASC NULLS LAST, id@1 ASC NULLS LAST], preserve_partitioning=[false]
834+
02)--HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(t1_id@2, id@0)], projection=[id@3, id@0, rn@1]
835+
03)----ProjectionExec: expr=[id@0 as id, row_number() PARTITION BY [t2.t1_id] ORDER BY [t2.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as rn, t1_id@1 as t1_id]
836+
04)------BoundedWindowAggExec: wdw=[row_number() PARTITION BY [t2.t1_id] ORDER BY [t2.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [t2.t1_id] ORDER BY [t2.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
837+
05)--------SortExec: expr=[t1_id@1 ASC NULLS LAST, id@0 ASC NULLS LAST], preserve_partitioning=[false]
838+
06)----------DataSourceExec: partitions=1, partition_sizes=[1]
839+
07)----DataSourceExec: partitions=1, partition_sizes=[1]
840+
841+
query III
842+
SELECT t1.id, sub.id, sub.rn
843+
FROM t1, LATERAL (
844+
SELECT t2.id, row_number() OVER (PARTITION BY t2.t1_id ORDER BY t2.id) AS rn
845+
FROM t2 WHERE t2.t1_id = t1.id
846+
) AS sub
847+
ORDER BY t1.id, sub.id;
848+
----
849+
1 10 1
850+
1 20 2
851+
2 30 1
852+
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
855+
SELECT t1.id, sub.id, sub.rn, sub.c
856+
FROM t1, LATERAL (
857+
SELECT t2.id,
858+
row_number() OVER (PARTITION BY t2.t1_id ORDER BY t2.id) AS rn,
859+
count(*) OVER (PARTITION BY t2.data) AS c
860+
FROM t2 WHERE t2.t1_id = t1.id
861+
) AS sub
862+
ORDER BY t1.id, sub.id;
863+
813864
# --- Implicit LATERAL (comma without LATERAL keyword) ---
814865
# DuckDB auto-detects lateral correlation; DataFusion requires
815866
# the explicit LATERAL keyword.

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 46 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -3108,9 +3108,10 @@ DROP TABLE win_outer;
31083108
statement ok
31093109
DROP TABLE win_inner;
31103110

3111-
# A correlated filter below an Unnest is not pulled above the Unnest. The pull
3112-
# up does not carry the columns of the filter through the Unnest, so it failed
3113-
# with a schema error.
3111+
# A correlated filter below an Unnest is pulled above the Unnest. An Unnest maps
3112+
# each input row to its own output rows, so a filter on a column it passes
3113+
# through keeps the same rows. The Unnest must output the columns the pull up
3114+
# adds below it, which failed with a schema error before.
31143115
statement ok
31153116
CREATE TABLE unnest_outer(k INT) AS VALUES (1), (2);
31163117

@@ -3124,24 +3125,49 @@ query TT
31243125
EXPLAIN SELECT unnest_outer.k FROM unnest_outer WHERE EXISTS (SELECT 1 FROM (SELECT unnest(t.arr) AS u FROM (SELECT * FROM unnest_inner WHERE unnest_inner.id = unnest_outer.k) AS t) AS x WHERE x.u = 3);
31253126
----
31263127
logical_plan
3127-
01)Filter: EXISTS (<subquery>)
3128-
02)--Subquery:
3129-
03)----Projection: Int64(1)
3130-
04)------SubqueryAlias: x
3131-
05)--------Projection: __unnest_placeholder(t.arr,depth=1) AS UNNEST(t.arr) AS u
3132-
06)----------Filter: __unnest_placeholder(t.arr,depth=1) = Int32(3)
3133-
07)------------Unnest: lists[__unnest_placeholder(t.arr)|depth=1] structs[]
3134-
08)--------------Projection: t.arr AS __unnest_placeholder(t.arr)
3135-
09)----------------SubqueryAlias: t
3136-
10)------------------Projection: unnest_inner.id, unnest_inner.arr
3137-
11)--------------------Filter: unnest_inner.id = outer_ref(unnest_outer.k)
3138-
12)----------------------TableScan: unnest_inner
3139-
13)--TableScan: unnest_outer projection=[k]
3140-
3141-
# The subquery stays correlated, which the physical planner does not support.
3142-
# The right answer is `1`.
3143-
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
3128+
01)LeftSemi Join: unnest_outer.k = __correlated_sq_1.id
3129+
02)--TableScan: unnest_outer projection=[k]
3130+
03)--SubqueryAlias: __correlated_sq_1
3131+
04)----SubqueryAlias: x
3132+
05)------Projection: t.id
3133+
06)--------Filter: __unnest_placeholder(t.arr,depth=1) = Int32(3)
3134+
07)----------Unnest: lists[__unnest_placeholder(t.arr)|depth=1] structs[]
3135+
08)------------Projection: t.arr AS __unnest_placeholder(t.arr), t.id
3136+
09)--------------SubqueryAlias: t
3137+
10)----------------TableScan: unnest_inner projection=[id, arr]
3138+
3139+
query I
31443140
SELECT unnest_outer.k FROM unnest_outer WHERE EXISTS (SELECT 1 FROM (SELECT unnest(t.arr) AS u FROM (SELECT * FROM unnest_inner WHERE unnest_inner.id = unnest_outer.k) AS t) AS x WHERE x.u = 3);
3141+
----
3142+
1
3143+
3144+
query I
3145+
SELECT unnest_outer.k FROM unnest_outer WHERE NOT EXISTS (SELECT 1 FROM (SELECT unnest(t.arr) AS u FROM (SELECT * FROM unnest_inner WHERE unnest_inner.id = unnest_outer.k) AS t) AS x WHERE x.u = 3);
3146+
----
3147+
2
3148+
3149+
# The correlated column is selected next to the unnested one.
3150+
query TT
3151+
EXPLAIN SELECT unnest_outer.k, s.u FROM unnest_outer, LATERAL (SELECT i.id, unnest(i.arr) AS u FROM unnest_inner AS i WHERE i.id = unnest_outer.k) AS s ORDER BY unnest_outer.k, s.u;
3152+
----
3153+
logical_plan
3154+
01)Sort: unnest_outer.k ASC NULLS LAST, s.u ASC NULLS LAST
3155+
02)--Projection: unnest_outer.k, s.u
3156+
03)----Inner Join: unnest_outer.k = s.id
3157+
04)------TableScan: unnest_outer projection=[k]
3158+
05)------SubqueryAlias: s
3159+
06)--------Projection: i.id, __unnest_placeholder(i.arr,depth=1) AS UNNEST(i.arr) AS u
3160+
07)----------Unnest: lists[__unnest_placeholder(i.arr)|depth=1] structs[]
3161+
08)------------Projection: i.id, i.arr AS __unnest_placeholder(i.arr)
3162+
09)--------------SubqueryAlias: i
3163+
10)----------------TableScan: unnest_inner projection=[id, arr]
3164+
3165+
query II
3166+
SELECT unnest_outer.k, s.u FROM unnest_outer, LATERAL (SELECT i.id, unnest(i.arr) AS u FROM unnest_inner AS i WHERE i.id = unnest_outer.k) AS s ORDER BY unnest_outer.k, s.u;
3167+
----
3168+
1 3
3169+
1 4
3170+
2 5
31453171

31463172
statement ok
31473173
RESET datafusion.explain.logical_plan_only;

0 commit comments

Comments
 (0)