Skip to content

Commit b2cfc23

Browse files
adriangbclaude
andauthored
fix: pull a correlated filter only through plan nodes known to be safe (#25838)
## Which issue does this PR close? - Closes #25834. - Closes #25792. This PR also contains the code change of #25810 (`Window`) and its tests (the test commit is the same). #25810 has no reviews yet, so I suggest to review this PR instead and close #25810 when this PR merges. Related: #25837 (found while writing the tests: the `LATERAL` test uses the table name as the alias of the derived table because of it), #25507, #25792, #25808, #25283. ## Rationale for this change A correlated subquery that has an ASOF join returns wrong rows when the correlated filter is on the right side of the join. ```sql CREATE TABLE o(k INT) AS VALUES (1), (2); CREATE TABLE l(id INT, ts INT) AS VALUES (1, 10); CREATE TABLE r(ts INT, val INT) AS VALUES (5, 1), (8, 2); SELECT o.k, s.rts FROM o, LATERAL ( SELECT r.ts AS rts FROM l ASOF JOIN (SELECT * FROM r WHERE r.val = o.k) AS r MATCH_CONDITION (l.ts >= r.ts) ) AS s ORDER BY o.k; ``` | | Result | |---|---| | Correct | `(1, 5), (2, 8)` | | `main` | `(2, 8)` | | This PR | `This feature is not implemented: Physical plan does not support logical expression OuterReferenceColumn(...)` | The filter `r.val = o.k` selects the rows the ASOF join can match. The decorrelation moves it above the join. There, the join has already matched `l` to `r.ts = 8` for every outer row, and the filter removes the row for `o.k = 1`. The root cause is not specific to the ASOF join. `PullUpCorrelatedExpr` moves a correlated filter above every plan node that it does not block explicitly. Each node it does not know is a possible wrong result. #25507 (outer join) and #25792 (window) are two more cases of the same problem. `PushDownFilter` asks the same question in the other direction, and there the default is safe: a filter stays where it is unless the rule knows the node. ## What changes are included in this PR? `PullUpCorrelatedExpr::f_down` now matches every `LogicalPlan` variant, with no `_` arm. A new variant does not compile until somebody puts it in a group. | Group | Variants | What `f_down` does | |---|---|---| | Special arms (no change) | `Filter`, `Subquery`, `Join`, `Union`, `Sort`, `Extension`, `Limit` | Same as before | | Pass-through | `Projection`, `Aggregate`, `Distinct::All`, `Join` (preserved sides), `AsOfJoin` (left side), `Repartition`, `SubqueryAlias`, `TableScan`, `EmptyRelation`, `Values` | Continue. Stop when the node's own expressions hold an outer reference (same as before). | | Stop when the input holds an outer reference | `AsOfJoin` (right side) | New | | Stop when the input holds an outer reference | `Window` | New (same as #25810) | | Stop when the input holds an outer reference | `Distinct::On`, `Unnest`, `RecursiveQuery`, `Statement`, `Explain`, `Analyze`, `Dml`, `Ddl`, `Copy`, `DescribeTable` | New | "Stop" means the subquery stays correlated. The check uses `holds_outer_reference`, which does not go into a nested `Subquery`. The effect for each new stop: | Node | Before | After | |---|---|---| | `AsOfJoin`, filter on the right side | Wrong rows | Not-implemented error | | `Window` | Wrong rows | Not-implemented error | | `Unnest` | `Optimizer rule 'decorrelate_predicate_subquery' failed: Schema error: No field named t.id` | Not-implemented error | | `Distinct::On`, `RecursiveQuery` | Not reachable in the default optimizer (`ReplaceDistinctWithAggregate` runs first) or not seen in tests | Stop | | `Statement`, `Explain`, `Analyze`, `Dml`, `Ddl`, `Copy`, `DescribeTable` | Not in a subquery | Stop | ## What is the testing strategy for this PR? New `sqllogictest` cases: | File | Case | Without the fix | |---|---|---| | `asof_join.slt` | LATERAL, filter on the right side: `EXPLAIN` shows the subquery stays correlated, and the query errors | Wrong rows `(2, 8)` | | `asof_join.slt` | EXISTS, filter on the right side: the query errors | Wrong result (no rows, correct is `1`) | | `asof_join.slt` | EXISTS, filter on the left side: `EXPLAIN` and result | Same plan and result | | `asof_join.slt` | LATERAL, filter above the join: `EXPLAIN` and result | Same plan and result | | `subquery.slt` | EXISTS, filter below an `Unnest`: `EXPLAIN` and the error | Schema error | | `subquery.slt`, `lateral_join.slt` | Window cases from #25810 | Wrong rows | All new negative cases fail when `decorrelate.rs` is reverted to `main`. The full `sqllogictest` suite (including the TPC-H plan files) and `cargo test -p datafusion-optimizer` pass with no change to an existing test. ## Are there any user-facing changes? Queries that returned wrong rows (ASOF join, window) or failed with a schema error (unnest) now fail with a not-implemented error. No API change. Out of scope: the `Aggregate` and `Limit` arms still have exemptions that are too broad (#25808, #25283). This PR does not change them. `Distinct::All` is a pass-through, with the same behavior as an `Aggregate` without aggregate expressions. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Claude Opus 5.5 <[email protected]>
1 parent 14b8de8 commit b2cfc23

5 files changed

Lines changed: 630 additions & 22 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 189 additions & 22 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+
BinaryExpr, Cast, Distinct, 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
@@ -135,13 +135,6 @@ impl PullUpCorrelatedExpr {
135135
self.exists_sub_query = exists_sub_query;
136136
self
137137
}
138-
139-
/// Mark the plan as one whose correlated expressions cannot be pulled up
140-
/// and stop descending into it
141-
fn unsupported(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
142-
self.can_pull_up = false;
143-
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
144-
}
145138
}
146139

147140
/// Used to indicate the unmatched rows from the inner(subquery) table after the left out Join
@@ -159,6 +152,9 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
159152
type Node = LogicalPlan;
160153

161154
fn f_down(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
155+
// This match is exhaustive on purpose. A correlated filter moves above
156+
// a node only when the node is known to keep the result the same. Add
157+
// each new `LogicalPlan` variant to one of the groups below.
162158
match plan {
163159
LogicalPlan::Filter(_) => Ok(Transformed::no(plan)),
164160
// Subquery nodes are scope boundaries for correlation. A nested
@@ -174,24 +170,49 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
174170
// join does not output cannot give its columns to a pulled up
175171
// filter either.
176172
LogicalPlan::Join(ref join) if !correlated_inputs_are_preserved(join) => {
177-
// the unsupported case
178-
self.can_pull_up = false;
179-
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
173+
Ok(self.stop_pull_up(plan))
180174
}
175+
// An ASOF join keeps each left row once, so a filter on the left
176+
// side can move above it. A filter on the right side selects the
177+
// rows the join can match, so it must stay below the join.
178+
LogicalPlan::AsOfJoin(ref join) if holds_outer_reference(&join.right) => {
179+
Ok(self.stop_pull_up(plan))
180+
}
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+
// The SQL planner unnests a new `__unnest_placeholder` column and
185+
// passes the original column through, so this only stops plans
186+
// built with `unnest_column` and similar.
187+
LogicalPlan::Unnest(ref unnest)
188+
if correlated_filter_columns(&unnest.input).iter().any(|col| {
189+
unnest
190+
.exec_columns
191+
.iter()
192+
.any(|exec_col| exec_col.name == col.name)
193+
}) =>
194+
{
195+
Ok(self.stop_pull_up(plan))
196+
}
197+
// A correlated filter cannot move out of one input of a Union, and
198+
// `f_up` does not add its columns to a Sort or an Extension, so no
199+
// correlated filter may be below these nodes.
181200
LogicalPlan::Union(_) | LogicalPlan::Sort(_) | LogicalPlan::Extension(_) => {
182-
let plan_hold_outer = !plan.all_out_ref_exprs().is_empty();
183-
if plan_hold_outer {
184-
self.unsupported(plan)
201+
if holds_outer_reference(&plan) {
202+
Ok(self.stop_pull_up(plan))
185203
} else {
186204
Ok(Transformed::no(plan))
187205
}
188206
}
207+
// For EXISTS only emptiness matters, so `f_down` removes or
208+
// replaces a Limit over a correlated filter where it can. Any other
209+
// Limit keeps the correlated filters below it.
189210
LogicalPlan::Limit(ref limit) => {
190-
if plan.all_out_ref_exprs().is_empty() {
211+
if !holds_outer_reference(&plan) {
191212
return Ok(Transformed::no(plan));
192213
}
193214
if !self.exists_sub_query {
194-
return self.unsupported(plan);
215+
return Ok(self.stop_pull_up(plan));
195216
}
196217
// Only emptiness matters for EXISTS, so remove a limit that
197218
// cannot make its input empty and replace one that always does
@@ -213,14 +234,67 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
213234
t.transformed = true;
214235
Ok(t)
215236
}
216-
_ => self.unsupported(plan),
237+
_ => Ok(self.stop_pull_up(plan)),
217238
}
218239
}
219-
_ if plan.contains_outer_reference() => {
220-
// the unsupported cases, the plan expressions contain out reference columns(like window expressions)
221-
self.unsupported(plan)
240+
// A correlated filter below these nodes can move above them. The
241+
// node itself must not hold an outer reference, because only a
242+
// Filter gives its outer references to the join.
243+
// - `f_up` adds the columns the pulled up filter needs to a
244+
// Projection or an Aggregate, and checks that the filter can move
245+
// above an Aggregate.
246+
// - A `DISTINCT` shares the exemption of an Aggregate without
247+
// aggregate functions: its output takes the columns the node
248+
// below it adds, so they become part of its keys. This is only
249+
// right when the pulled up filter fixes those columns for each
250+
// outer row. A non-equality filter can return duplicates, see
251+
// https://github.com/apache/datafusion/issues/25808.
252+
// - A Window keeps or drops whole partitions when the filter reads
253+
// only its `PARTITION BY` columns. `f_up` checks this.
254+
// - An Unnest maps each input row to its own output rows, so a
255+
// filter on a column it passes through keeps the same rows.
256+
// The arm above checks that the filter does not read an unnested
257+
// column.
258+
LogicalPlan::Projection(_)
259+
| LogicalPlan::Aggregate(_)
260+
| LogicalPlan::Distinct(Distinct::All(_))
261+
| LogicalPlan::Window(_)
262+
| LogicalPlan::Unnest(_)
263+
| LogicalPlan::Join(_)
264+
| LogicalPlan::AsOfJoin(_)
265+
| LogicalPlan::Repartition(_)
266+
| LogicalPlan::SubqueryAlias(_)
267+
| LogicalPlan::TableScan(_)
268+
| LogicalPlan::EmptyRelation(_)
269+
| LogicalPlan::Values(_) => {
270+
if plan.contains_outer_reference() {
271+
// the unsupported cases, the plan expressions contain out
272+
// reference columns
273+
Ok(self.stop_pull_up(plan))
274+
} else {
275+
Ok(Transformed::no(plan))
276+
}
277+
}
278+
// A correlated filter below these nodes cannot move above them:
279+
// - `DISTINCT ON` keeps the first row of each group, so the filter
280+
// changes which row is first.
281+
// - A RecursiveQuery repeats its recursive term.
282+
// - The other nodes are not queries and are not in a subquery.
283+
LogicalPlan::Distinct(Distinct::On(_))
284+
| LogicalPlan::RecursiveQuery(_)
285+
| LogicalPlan::Statement(_)
286+
| LogicalPlan::Explain(_)
287+
| LogicalPlan::Analyze(_)
288+
| LogicalPlan::Dml(_)
289+
| LogicalPlan::Ddl(_)
290+
| LogicalPlan::Copy(_)
291+
| LogicalPlan::DescribeTable(_) => {
292+
if holds_outer_reference(&plan) {
293+
Ok(self.stop_pull_up(plan))
294+
} else {
295+
Ok(Transformed::no(plan))
296+
}
222297
}
223-
_ => Ok(Transformed::no(plan)),
224298
}
225299
}
226300

@@ -486,12 +560,64 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
486560
}
487561
Ok(Transformed::no(plan))
488562
}
563+
LogicalPlan::Window(window) => {
564+
let mut local_correlated_cols = BTreeSet::new();
565+
collect_local_correlated_cols(
566+
&plan,
567+
&self.correlated_subquery_cols_map,
568+
&mut local_correlated_cols,
569+
);
570+
// A filter that reads only `PARTITION BY` columns keeps or drops
571+
// whole partitions, so each window function sees the same rows
572+
// above it or below it. A filter on any other column changes the
573+
// rows of a partition.
574+
if !local_correlated_cols.is_empty()
575+
&& !window
576+
.window_expr
577+
.iter()
578+
.all(|expr| partitions_by_all(expr, &local_correlated_cols))
579+
{
580+
self.can_pull_up = false;
581+
}
582+
self.pass_through_pulled_up_cols(plan)
583+
}
584+
// `f_down` checked that the pulled up filters do not read an
585+
// unnested column.
586+
LogicalPlan::Unnest(_) => self.pass_through_pulled_up_cols(plan),
489587
_ => Ok(Transformed::no(plan)),
490588
}
491589
}
492590
}
493591

494592
impl PullUpCorrelatedExpr {
593+
/// Keeps the correlated expressions below `plan` where they are. The caller
594+
/// then keeps the subquery correlated.
595+
fn stop_pull_up(&mut self, plan: LogicalPlan) -> Transformed<LogicalPlan> {
596+
self.can_pull_up = false;
597+
Transformed::new(plan, false, TreeNodeRecursion::Jump)
598+
}
599+
600+
/// Rebuilds a node whose output holds every column of its input, so that
601+
/// it outputs the columns the pull up added below it.
602+
///
603+
/// The count bug handling of a Projection or a Filter above reads the
604+
/// values an aggregate below gives on an empty input. Those values do not
605+
/// hold once a Window or an Unnest runs over the aggregate, so the pull up
606+
/// stops in that case.
607+
fn pass_through_pulled_up_cols(
608+
&mut self,
609+
plan: LogicalPlan,
610+
) -> Result<Transformed<LogicalPlan>> {
611+
if plan
612+
.inputs()
613+
.iter()
614+
.any(|input| self.collected_count_expr_map.contains_key(*input))
615+
{
616+
self.can_pull_up = false;
617+
}
618+
Ok(Transformed::yes(plan.recompute_schema()?))
619+
}
620+
495621
/// Whether the pull up can add its columns to `group_expr` without changing
496622
/// what the aggregate returns.
497623
///
@@ -634,6 +760,47 @@ fn holds_outer_reference(plan: &LogicalPlan) -> bool {
634760
found
635761
}
636762

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

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

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

0 commit comments

Comments
 (0)