Repository navigation
Commit 1aa6c29
fix: keep a LIMIT inside EXISTS that an operator above it can empty (apache#26640)
## Which issue does this PR close?
- Closes apache#26629.
## Rationale for this change
`PullUpCorrelatedExpr::f_down` reasoned that "for EXISTS only emptiness
matters" and dropped any
`Limit` with `skip=0` and a non-zero fetch out of an `EXISTS` subquery.
That holds for the emptiness of the `Limit`'s own output. What `EXISTS`
reads is whether the
**whole subquery** is empty, so the argument breaks as soon as a node
above the `Limit` can be
empty for a reason of its own. On the `subquery.slt` tables:
```sql
SELECT t1_id FROM t1 WHERE EXISTS (
SELECT 1 FROM (SELECT t2_id FROM t2 WHERE t2_int = t1_int LIMIT 1) s
HAVING count(*) > 1
);
```
`count(*)` over the single row `LIMIT 1` keeps can never exceed 1,
whichever row that is, so the
`HAVING` holds for nothing and the query returns no rows. Dropping the
`Limit` lets the aggregate
count the whole scan, and on `main` this returns `33`. A `Filter` above
the `Limit` goes wrong the
same way.
## What changes are included in this PR?
`PullUpCorrelatedExpr` now tracks, per node on the path from the
subquery's root, whether the
emptiness of that node's output follows from the emptiness of its input
alone, and only drops the
`Limit` when that holds of every node above it. The entry is pushed and
popped in lockstep with
the existing `column_refs_above`.
**The condition is emptiness, not row count**, which matters for how
little this rejects. A
`Projection`, a `SubqueryAlias`, a `Sort`, a `Window` and a
`Repartition` each output one row per
input row. A `DISTINCT` and a grouped `Aggregate` output rows exactly
when their input has rows,
and an `Aggregate` without a grouping always outputs its one row — so no
`Aggregate` can be
emptied by the rows a `Limit` held back. These all keep decorrelating:
```sql
EXISTS (SELECT count(*) FROM (SELECT t2_id FROM t2 WHERE t2_id = t1_id LIMIT 1) s)
EXISTS (SELECT DISTINCT s.t2_id FROM (SELECT t2_id FROM t2 WHERE t2_id = t1_id LIMIT 1) s)
EXISTS (SELECT s.t2_id FROM (SELECT t2_id FROM t2 WHERE t2_id = t1_id LIMIT 1) s GROUP BY s.t2_id)
EXISTS (SELECT 1 FROM t2 WHERE t2_id = t1_id LIMIT 1)
```
`Filter` is what the predicate leaves out, together with the nodes that
can empty a non-empty
input: `Join`, `Union`, `Unnest`. Anything not listed is treated as
unsafe, so a new `LogicalPlan`
variant does not silently become droppable.
`LIMIT 0` keeps its existing rewrite to an empty relation, which is
sound whatever sits above it,
since both sides are always empty.
### The trade-off worth reviewing
Where the `Limit` now has to stay, the subquery does not decorrelate and
the query fails to plan
with `Physical plan does not support logical expression Exists(..)`.
That is the trade `subquery.slt` already records a few lines above these
new tests, for
`EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)`, asserted to
error *"rather than
returning wrong rows"* — and `main` does the same for the equivalent
correlated `IN` subquery with
a `LIMIT`. So this puts the two broken shapes into an existing,
already-asserted bucket rather
than inventing a new behaviour. Happy to go further if you would rather
these decorrelate properly
via the `row_number()` route the issue mentions; that looked like a much
larger change and I did
not want to bundle it.
## What is the testing strategy for this PR?
`datafusion/sqllogictest/test_files/subquery.slt`, in the existing
`EXISTS`-with-`Limit`/`offset`
block: the two shapes that returned wrong answers, and the four above
that must keep working.
**The three new assertions all fail on `main`** — the `explain` shows
`main` dropping the `Limit`
into a `LeftSemi` join, and both error assertions fail because `main`
returns rows.
The rule's own unit tests in `decorrelate_predicate_subquery.rs` pin the
decorrelated plan shape
for a `Limit` under a `Projection` and under an `Aggregate`, and that
the `HAVING` and `Filter`
shapes are left untransformed.
- `cargo test -p datafusion-optimizer`: 951 pass.
- Full `sqllogictests`: fails in the same 236 places before and after
this change, identical sets.
- `cargo clippy --all-targets --workspace --features
avro,integration-tests,extended_tests -- -D warnings`: clean.
- `cargo fmt --all --check`, `typos`, and `RUSTDOCFLAGS="-D warnings"
cargo doc --document-private-items`: clean.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
---------
Signed-off-by: Raghvendra Yadav <[email protected]>
Co-authored-by: Claude Opus 5 (1M context) <[email protected]>1 parent 0f5c9eb commit 1aa6c29
3 files changed
Lines changed: 149 additions & 3 deletions
File tree
- datafusion
- optimizer/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
97 | 97 | | |
98 | 98 | | |
99 | 99 | | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
100 | 106 | | |
101 | 107 | | |
102 | 108 | | |
| |||
121 | 127 | | |
122 | 128 | | |
123 | 129 | | |
| 130 | + | |
124 | 131 | | |
125 | 132 | | |
126 | 133 | | |
| |||
183 | 190 | | |
184 | 191 | | |
185 | 192 | | |
| 193 | + | |
| 194 | + | |
186 | 195 | | |
187 | 196 | | |
188 | 197 | | |
| |||
268 | 277 | | |
269 | 278 | | |
270 | 279 | | |
271 | | - | |
272 | | - | |
273 | | - | |
| 280 | + | |
| 281 | + | |
274 | 282 | | |
275 | 283 | | |
276 | 284 | | |
| |||
280 | 288 | | |
281 | 289 | | |
282 | 290 | | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
283 | 305 | | |
284 | 306 | | |
285 | 307 | | |
| |||
289 | 311 | | |
290 | 312 | | |
291 | 313 | | |
| 314 | + | |
292 | 315 | | |
293 | 316 | | |
294 | 317 | | |
| |||
364 | 387 | | |
365 | 388 | | |
366 | 389 | | |
| 390 | + | |
367 | 391 | | |
368 | 392 | | |
369 | 393 | | |
| |||
897 | 921 | | |
898 | 922 | | |
899 | 923 | | |
| 924 | + | |
| 925 | + | |
| 926 | + | |
| 927 | + | |
| 928 | + | |
| 929 | + | |
| 930 | + | |
| 931 | + | |
| 932 | + | |
| 933 | + | |
| 934 | + | |
| 935 | + | |
| 936 | + | |
| 937 | + | |
| 938 | + | |
| 939 | + | |
| 940 | + | |
| 941 | + | |
| 942 | + | |
| 943 | + | |
| 944 | + | |
| 945 | + | |
| 946 | + | |
| 947 | + | |
| 948 | + | |
| 949 | + | |
| 950 | + | |
| 951 | + | |
| 952 | + | |
| 953 | + | |
| 954 | + | |
| 955 | + | |
| 956 | + | |
| 957 | + | |
| 958 | + | |
| 959 | + | |
| 960 | + | |
900 | 961 | | |
901 | 962 | | |
902 | 963 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
210 | 210 | | |
211 | 211 | | |
212 | 212 | | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
213 | 229 | | |
214 | 230 | | |
215 | 231 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
779 | 779 | | |
780 | 780 | | |
781 | 781 | | |
| 782 | + | |
| 783 | + | |
| 784 | + | |
| 785 | + | |
| 786 | + | |
| 787 | + | |
| 788 | + | |
| 789 | + | |
| 790 | + | |
| 791 | + | |
| 792 | + | |
| 793 | + | |
| 794 | + | |
| 795 | + | |
| 796 | + | |
| 797 | + | |
| 798 | + | |
| 799 | + | |
| 800 | + | |
| 801 | + | |
| 802 | + | |
| 803 | + | |
| 804 | + | |
| 805 | + | |
| 806 | + | |
| 807 | + | |
| 808 | + | |
| 809 | + | |
| 810 | + | |
| 811 | + | |
| 812 | + | |
| 813 | + | |
| 814 | + | |
| 815 | + | |
| 816 | + | |
| 817 | + | |
| 818 | + | |
| 819 | + | |
| 820 | + | |
| 821 | + | |
| 822 | + | |
| 823 | + | |
| 824 | + | |
| 825 | + | |
| 826 | + | |
| 827 | + | |
| 828 | + | |
| 829 | + | |
| 830 | + | |
| 831 | + | |
| 832 | + | |
| 833 | + | |
| 834 | + | |
| 835 | + | |
| 836 | + | |
| 837 | + | |
| 838 | + | |
| 839 | + | |
| 840 | + | |
| 841 | + | |
| 842 | + | |
| 843 | + | |
| 844 | + | |
| 845 | + | |
| 846 | + | |
| 847 | + | |
| 848 | + | |
| 849 | + | |
| 850 | + | |
782 | 851 | | |
783 | 852 | | |
784 | 853 | | |
| |||
0 commit comments