Skip to content

fix: keep a subquery correlated when its filter is below a window function - #25810

Closed
adriangb wants to merge 2 commits into
apache:mainfrom
pydantic:decorrelate-window-25792
Closed

fix: keep a subquery correlated when its filter is below a window function#25810
adriangb wants to merge 2 commits into
apache:mainfrom
pydantic:decorrelate-window-25792

Conversation

@adriangb

@adriangb adriangb commented Sep 27, 2026

Copy link
Copy Markdown
Contributor

Which issue does this PR close?

Rationale for this change

A correlated filter below a window function gives wrong results. The window function must see only the rows that match the current outer row.

CREATE TABLE o(k INT) AS VALUES (1), (2), (5);
CREATE TABLE b(id INT, y INT) AS VALUES (1, 1), (2, 2);

SELECT o.k FROM o WHERE EXISTS (
  SELECT 1 FROM (SELECT b.id, row_number() OVER (ORDER BY b.id) AS rn
                 FROM (SELECT * FROM b WHERE b.y = o.k) AS b) AS w
  WHERE w.rn = 1)
ORDER BY o.k;
Query form Correct result (DuckDB 1.5.2, PostgreSQL 17) main This PR
EXISTS (above) 1, 2 1 not-implemented error
NOT EXISTS 5 2, 5 not-implemented error
1 IN (SELECT row_number() OVER (ORDER BY id) FROM b WHERE b.y = o.k) 1, 2 1 not-implemented error
scalar max(rn) (1, 1), (2, 1), (5, NULL) (1, 1), (2, 2), (5, NULL) not-implemented error
LATERAL rn = 1 for k = 2 rn = 2 for k = 2 not-implemented error

PullUpCorrelatedExpr moves the filter b.y = o.k from below the WindowAggr to the join that replaces the subquery. Then row_number() numbers the rows of all outer rows together.

An error is better than wrong rows. A query that decorrelates correctly does not change.

What changes are included in this PR?

  • In PullUpCorrelatedExpr::f_down, a LogicalPlan::Window whose input holds an outer reference sets can_pull_up = false. The subquery stays correlated.
  • It uses holds_outer_reference, which fix: keep a correlated filter below the nullable side of an outer join #25764 added, to find an outer reference in the window input. That helper does not go into a LogicalPlan::Subquery, because the outer references there belong to a nested scope (for example a nested LATERAL).

A correlated filter above the window does not change. The window input does not depend on the outer row, so the filter is pulled up as before.

This is the same class of bug as #25507 (correlated filter below an outer join), which #25764 fixed with the same guard pattern. #25808 is another bug of this class (LATERAL with SELECT DISTINCT), which this PR does not fix.

A later change can decorrelate some of these queries. For example, when the correlated filter is an equality on an inner column, the pull up can add that column to PARTITION BY. This PR does not do that.

What is the testing strategy for this PR?

New sqllogictest cases:

  • subquery.slt: an EXPLAIN that shows the subquery stays correlated, and statement error cases for EXISTS, NOT EXISTS, IN and a scalar subquery. An EXPLAIN and a result for a correlated filter above the window, which is still decorrelated.
  • lateral_join.slt: a statement error case for the LATERAL form, and an EXPLAIN and a result for a correlated filter above the window.

Without the fix, all six new error and EXPLAIN cases fail: each query returns the wrong rows in the table above. The full sqllogictest suite and cargo test -p datafusion-optimizer pass, and no existing plan changes.

Are there any user-facing changes?

Queries with a correlated filter below a window function now fail with a not-implemented error. Before, they returned wrong results. No public API changes.

🤖 Generated with Claude Code

@github-actions github-actions Bot added optimizer Optimizer rules sqllogictest SQL Logic Tests (.slt) labels Sep 27, 2026
@codecov-commenter

codecov-commenter commented Sep 27, 2026 •
edited
Loading

Copy link
Copy Markdown

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 82.55%. Comparing base (991fd23) to head (3ebce96).

Additional details and impacted files 
@@            Coverage Diff             @@
##             main   #25810      +/-   ##
==========================================
- Coverage   82.55%   82.55%   -0.01%     
==========================================
  Files        1141     1141              
  Lines      440209   440212       +3     
  Branches   440209   440212       +3     
==========================================
- Hits       363409   363399      -10     
- Misses      54829    54836       +7     
- Partials    21971    21977       +6

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
  • 📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

adriangb and others added 2 commits September 28, 2026 10:27
@adriangb @claude
fix: keep a subquery correlated when its filter is below a window fun…
69c6c15 
…ction

PullUpCorrelatedExpr moved a correlated filter from below a Window to the
decorrelated join. The window function then ran over all rows of its
input instead of only the rows for each outer row, so row_number(),
rank(), lag() and similar functions gave wrong values.

A Window whose input holds an outer reference of the current scope now
sets can_pull_up = false. The subquery stays correlated and fails with a
not-implemented error instead of wrong results. A correlated filter above
the window is still pulled up.

Closes apache#25792

Co-Authored-By: Claude Opus 5.5 <[email protected]>
@adriangb @claude
test: cover correlated filters below and above a window function
3ebce96 
Co-Authored-By: Claude Opus 5.5 <[email protected]>
@adriangb
adriangb force-pushed the decorrelate-window-25792 branch from 4215cfc to 3ebce96 Compare September 28, 2026 15:27
This was referenced Sep 28, 2026
Closed
Merged
jayzhan211
jayzhan211 reviewed Oct 1, 2026
View reviewed changes

@jayzhan211 jayzhan211 left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks @adriangb , 1 comment

Comment thread datafusion/optimizer/src/decorrelate.rs
// rows for each outer row. If the filter moves above the window,
// the window function runs over all rows of the input, and the
// values it computes are different.
LogicalPlan::Window(ref window) if holds_outer_reference(&window.input) => {

@jayzhan211 jayzhan211 Oct 1, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This also rejects queries that main already decorrelates correctly: when the window is PARTITION BY the inner column of the correlated equality, pulling the filter up keeps the result. Both queries below return correct rows on main (2, and (1,1,1),(2,2,1),(2,3,2)) and error on this branch, which contradicts "a query that decorrelates correctly does not change."

CREATE TABLE po(k INT) AS VALUES (1), (2), (5);
CREATE TABLE pb(id INT, y INT) AS VALUES (1, 1), (2, 2), (3, 2);
SELECT po.k FROM po WHERE EXISTS (SELECT 1 FROM (SELECT b.id, row_number() OVER (PARTITION BY b.y ORDER BY b.id) AS rn FROM (SELECT * FROM pb WHERE pb.y = po.k) AS b) AS w WHERE w.rn = 2);
SELECT po.k, sub.id, sub.rn FROM po, LATERAL (SELECT pb.id, row_number() OVER (PARTITION BY pb.y ORDER BY pb.id) AS rn FROM pb WHERE pb.y = po.k) AS sub;

Suggest allowing the pull-up when every correlated predicate in window.input is inner_col = outer_ref with inner_col in each window expr's partition_by. Better still, append inner_col to partition_by, which fixes the unpartitioned top-N-per-row case too.

STUNSLAP pushed a commit to STUNSLAP/IIIllllIIl that referenced this pull request Oct 3, 2026
@adriangb @claude
fix: pull a correlated filter only through plan nodes known to be safe (
b2cfc23 
apache#25838)

## Which issue does this PR close?

- Closes apache#25834.
- Closes apache#25792.

This PR also contains the code change of
apache#25810 (`Window`) and its tests
(the test commit is the same). apache#25810 has no reviews yet, so I suggest
to review this PR instead and close apache#25810 when this PR merges.

Related: apache#25837 (found while
writing the tests: the `LATERAL` test uses the table name as the alias
of the derived table because of it),
apache#25507,
apache#25792,
apache#25808,
apache#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.
apache#25507 (outer join) and
apache#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
apache#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
apache#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 (apache#25808,
apache#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]>
Omega359 pushed a commit to Omega359/arrow-datafusion that referenced this pull request Oct 11, 2026
@adriangb @claude @Omega359
fix: pull a correlated filter only through plan nodes known to be safe (
6aed072 
apache#25838)

## Which issue does this PR close?

- Closes apache#25834.
- Closes apache#25792.

This PR also contains the code change of
apache#25810 (`Window`) and its tests
(the test commit is the same). apache#25810 has no reviews yet, so I suggest
to review this PR instead and close apache#25810 when this PR merges.

Related: apache#25837 (found while
writing the tests: the `LATERAL` test uses the table name as the alias
of the derived table because of it),
apache#25507,
apache#25792,
apache#25808,
apache#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.
apache#25507 (outer join) and
apache#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
apache#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
apache#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 (apache#25808,
apache#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]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@jayzhan211 jayzhan211 jayzhan211 left review comments

Assignees

No one assigned

Labels

optimizer Optimizer rules sqllogictest SQL Logic Tests (.slt)

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Wrong results: a correlated filter under a window function is pulled above the window

3 participants

@adriangb @codecov-commenter @jayzhan211