Repository navigation
Commit b2cfc23
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
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
36 | 36 | | |
37 | 37 | | |
38 | 38 | | |
39 | | - | |
40 | | - | |
| 39 | + | |
| 40 | + | |
41 | 41 | | |
42 | 42 | | |
43 | 43 | | |
| |||
135 | 135 | | |
136 | 136 | | |
137 | 137 | | |
138 | | - | |
139 | | - | |
140 | | - | |
141 | | - | |
142 | | - | |
143 | | - | |
144 | | - | |
145 | 138 | | |
146 | 139 | | |
147 | 140 | | |
| |||
159 | 152 | | |
160 | 153 | | |
161 | 154 | | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
162 | 158 | | |
163 | 159 | | |
164 | 160 | | |
| |||
174 | 170 | | |
175 | 171 | | |
176 | 172 | | |
177 | | - | |
178 | | - | |
179 | | - | |
| 173 | + | |
180 | 174 | | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
181 | 200 | | |
182 | | - | |
183 | | - | |
184 | | - | |
| 201 | + | |
| 202 | + | |
185 | 203 | | |
186 | 204 | | |
187 | 205 | | |
188 | 206 | | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
189 | 210 | | |
190 | | - | |
| 211 | + | |
191 | 212 | | |
192 | 213 | | |
193 | 214 | | |
194 | | - | |
| 215 | + | |
195 | 216 | | |
196 | 217 | | |
197 | 218 | | |
| |||
213 | 234 | | |
214 | 235 | | |
215 | 236 | | |
216 | | - | |
| 237 | + | |
217 | 238 | | |
218 | 239 | | |
219 | | - | |
220 | | - | |
221 | | - | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
222 | 297 | | |
223 | | - | |
224 | 298 | | |
225 | 299 | | |
226 | 300 | | |
| |||
486 | 560 | | |
487 | 561 | | |
488 | 562 | | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
| 566 | + | |
| 567 | + | |
| 568 | + | |
| 569 | + | |
| 570 | + | |
| 571 | + | |
| 572 | + | |
| 573 | + | |
| 574 | + | |
| 575 | + | |
| 576 | + | |
| 577 | + | |
| 578 | + | |
| 579 | + | |
| 580 | + | |
| 581 | + | |
| 582 | + | |
| 583 | + | |
| 584 | + | |
| 585 | + | |
| 586 | + | |
489 | 587 | | |
490 | 588 | | |
491 | 589 | | |
492 | 590 | | |
493 | 591 | | |
494 | 592 | | |
| 593 | + | |
| 594 | + | |
| 595 | + | |
| 596 | + | |
| 597 | + | |
| 598 | + | |
| 599 | + | |
| 600 | + | |
| 601 | + | |
| 602 | + | |
| 603 | + | |
| 604 | + | |
| 605 | + | |
| 606 | + | |
| 607 | + | |
| 608 | + | |
| 609 | + | |
| 610 | + | |
| 611 | + | |
| 612 | + | |
| 613 | + | |
| 614 | + | |
| 615 | + | |
| 616 | + | |
| 617 | + | |
| 618 | + | |
| 619 | + | |
| 620 | + | |
495 | 621 | | |
496 | 622 | | |
497 | 623 | | |
| |||
634 | 760 | | |
635 | 761 | | |
636 | 762 | | |
| 763 | + | |
| 764 | + | |
| 765 | + | |
| 766 | + | |
| 767 | + | |
| 768 | + | |
| 769 | + | |
| 770 | + | |
| 771 | + | |
| 772 | + | |
| 773 | + | |
| 774 | + | |
| 775 | + | |
| 776 | + | |
| 777 | + | |
| 778 | + | |
| 779 | + | |
| 780 | + | |
| 781 | + | |
| 782 | + | |
| 783 | + | |
| 784 | + | |
| 785 | + | |
| 786 | + | |
| 787 | + | |
| 788 | + | |
| 789 | + | |
| 790 | + | |
| 791 | + | |
| 792 | + | |
| 793 | + | |
| 794 | + | |
| 795 | + | |
| 796 | + | |
| 797 | + | |
| 798 | + | |
| 799 | + | |
| 800 | + | |
| 801 | + | |
| 802 | + | |
| 803 | + | |
637 | 804 | | |
638 | 805 | | |
639 | 806 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
3072 | 3072 | | |
3073 | 3073 | | |
3074 | 3074 | | |
| 3075 | + | |
| 3076 | + | |
| 3077 | + | |
| 3078 | + | |
| 3079 | + | |
| 3080 | + | |
| 3081 | + | |
| 3082 | + | |
| 3083 | + | |
| 3084 | + | |
| 3085 | + | |
| 3086 | + | |
| 3087 | + | |
| 3088 | + | |
| 3089 | + | |
| 3090 | + | |
| 3091 | + | |
| 3092 | + | |
| 3093 | + | |
| 3094 | + | |
| 3095 | + | |
| 3096 | + | |
| 3097 | + | |
| 3098 | + | |
| 3099 | + | |
| 3100 | + | |
| 3101 | + | |
| 3102 | + | |
| 3103 | + | |
| 3104 | + | |
| 3105 | + | |
| 3106 | + | |
| 3107 | + | |
| 3108 | + | |
| 3109 | + | |
| 3110 | + | |
| 3111 | + | |
| 3112 | + | |
3075 | 3113 | | |
0 commit comments