fix: keep a LIMIT inside EXISTS that an operator above it can empty by raghavyadav01 · Pull Request #26640 · apache/datafusion

raghavyadav01 · 2026-10-23T05:56:40Z

Which issue does this PR close?

Closes decorrelate_predicate_subquery removes inner LIMIT inside EXISTS even when a HAVING or WHERE above it depends on the row count #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:

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:

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

`PullUpCorrelatedExpr::f_down` reasoned that "for EXISTS only emptiness matters" and dropped any `Limit` with `skip=0` and a non-zero fetch from 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: 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 the `subquery.slt` tables this returned `33`. A `Filter` above the `Limit` goes wrong the same way. Track, 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 drop the `Limit` when that holds of every node above it. The condition is emptiness, not row count. 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 - `EXISTS (SELECT count(*) FROM (.. LIMIT 1) s)`, `EXISTS (SELECT DISTINCT .. FROM (.. LIMIT 1) s)` and a `GROUP BY` above the limit all keep decorrelating, as does the common `EXISTS (SELECT 1 FROM t WHERE t.a = o.a LIMIT 1)`. A `Filter` is what this leaves out, together with the nodes that can empty a non-empty input: `Join`, `Union`, `Unnest`. Where the `Limit` now has to stay, the subquery does not decorrelate and the query fails to plan. That is the same trade `subquery.slt` already records for `EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)`, which is asserted to error "rather than returning wrong rows", and for the equivalent correlated `IN` subquery with a `LIMIT`. `LIMIT 0` keeps its existing rewrite to an empty relation, which is sound whatever sits above it: both sides are always empty. Tests go in `subquery.slt` next to the existing `offset` cases: the two shapes that were wrong, and the four that must keep working. The three new assertions all fail on `main`. The rule's own unit tests cover the decorrelated plan shape. The full sqllogictest run fails in the same 236 places before and after. Fixes apache#26629 Co-Authored-By: Claude Opus 5 (1M context) <[email protected]> Signed-off-by: Raghvendra Yadav <[email protected]>

raghavyadav01 · 2026-10-24T20:16:05Z

Rebased past #26551 — no conflict; that change is in the Filter arm of PullUpCorrelatedExpr and this one is in Limit. Optimizer tests pass, and the one subquery_sort.slt failure reproduces identically on untouched main.

@jayzhan211 would you have time to look? You merged #26551 and #25781 in this area. The change is narrow: EXISTS currently drops an inner LIMIT unconditionally, which is wrong when a node above the LIMIT can empty the subquery on its own — subquery.slt already asserts the offset 1 case should fail rather than return wrong rows, and this extends that reasoning to fetch.

raghavyadav01 · 2026-10-26T20:26:31Z

@alamb could you take a look when you have a moment, or point me at a better reviewer? It's green and mergeable, and it has been quiet since I asked @jayzhan211 on the 24th.

Short version: EXISTS drops an inner LIMIT unconditionally, which is wrong when a node above the LIMIT can empty the subquery on its own. subquery.slt already pins the offset 1 case; this applies the same reasoning to fetch.

jayzhan211 · 2026-10-27T12:30:23Z

I'll take a look, but please note that the PR queue is long, so it may take several days.

jayzhan211 · 2026-10-28T12:29:39Z

+            | LogicalPlan::Window(_)
+            | LogicalPlan::Repartition(_)
+            | LogicalPlan::Distinct(Distinct::All(_))
+            | LogicalPlan::Aggregate(_)


@raghavyadav01 thanks for the fix! One regression I hit: an EXISTS with a MATERIALIZED CTE whose LIMIT sits at the root of the continuation now fails to plan, but on main it returns the right rows. The Cte arm pushes false for itself and then calls continuation.rewrite(self), so the Limit inside sees a blocking node above it. A Cte outputs exactly its continuation's rows, and only the continuation is rewritten, so its emptiness follows its input.

Repro (main: 1, 2; this PR: Physical plan does not support logical expression Exists):

SET datafusion.sql_parser.dialect = 'PostgreSQL'; CREATE TABLE a(k INT, x INT) AS VALUES (1, 10), (2, 20), (3, 30); CREATE TABLE b(k INT, v INT) AS VALUES (1, 100), (1, 200), (2, 300); SELECT a.k FROM a WHERE EXISTS ( WITH c AS MATERIALIZED (SELECT * FROM b) SELECT 1 FROM c WHERE c.k = a.k LIMIT 1);

Fix:

| LogicalPlan::Distinct(Distinct::All(_)) | LogicalPlan::Aggregate(_) + | LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(_)) )

Could you add these two cases to cte_materialized.slt (just before "A body that refers to the outer query…")? The first must decorrelate, and the second must stay refused (on main it wrongly returns 1):

# A LIMIT at the root of the continuation does not change whether it is empty. query I rowsort SELECT k FROM t WHERE EXISTS ( WITH r AS MATERIALIZED (SELECT k AS rk FROM t) SELECT 1 FROM r WHERE r.rk = t.k + 1 LIMIT 1) ---- 1 2 3 # A filter above the LIMIT reads the row the LIMIT kept, so it stays correlated. query error Physical plan does not support logical expression Exists SELECT k FROM t WHERE EXISTS ( WITH r AS MATERIALIZED (SELECT k AS rk, v AS rv FROM t) SELECT 1 FROM (SELECT * FROM r WHERE r.rk = t.k LIMIT 1) s WHERE s.rv > 0)

jayzhan211 · 2026-10-28T12:29:39Z

+/// kept decide whether anything survives it. A `Join`, a `Union` and an
+/// `Unnest` can empty a non-empty input too. Every other variant is treated the
+/// same way, so that a new one does not silently become droppable.


Optional cleanup: a Union can't empty a non-empty input, because its output is non-empty whenever any input is. It's left off the list because the Union arm already stops the pull-up when it holds an outer reference. Maybe:

-/// kept decide whether anything survives it. A `Join`, a `Union` and an -/// `Unnest` can empty a non-empty input too. Every other variant is treated the -/// same way, so that a new one does not silently become droppable. +/// kept decide whether anything survives it. A `Join` and an `Unnest` can empty +/// a non-empty input too. Every other variant is treated the same way, so that +/// a new one does not silently become droppable.

alamb

As I mentioned elsewhere (sorry for the repeated content) I don't think we should be trying to patch these subquery casees to make them work, rather I think we should make the query error rather than trying to make it work / give correct results. To make it work and have confidence it will be correct, I think we need a more general approach than patches. See here for details

#5492 (comment)

… EXISTS limit Addresses review: a LIMIT at the root of a MATERIALIZED CTE continuation is safe to drop. Adds both cases to cte_materialized.slt.

raghavyadav01 · 2026-10-29T01:25:03Z

@alamb agreed, and I think this PR already takes that route: it adds no new rewrite. Today EXISTS drops an inner LIMIT even when a filter above it reads the limited rows, which returns wrong rows (#26629). With this change that shape stays correlated, so the query fails with Physical plan does not support logical expression Exists instead. Every shape that decorrelates today still does.

@jayzhan211 thanks, applied both: the materialized CTE case and the Union doc cleanup, plus your two slt cases. Confirmed the first one fails without the fix.

alamb · 2026-10-29T18:14:23Z

Thank you -- will and give it a look again

alamb

I think this is reasonable but it is hard to understand and I am not sure about is theoretical foundation to be honest

I think we are getting closer though. Let me know what you thin

Thank you for sticking with us @raghavyadav01 and @jayzhan211

alamb · 2026-10-29T20:27:37Z

    }
 }

+/// Whether the emptiness of `plan`'s output follows from the emptiness of its


I don't really understand what emptness means in this context. Is this saying if the input to the plan is non empty than the output will also be non empty?

How will we know that for user defined plans?

Yes, that's the idea. The property is that whether the node returns any rows depends only on whether its input has any, not on which ones. A Limit with no skip and fetch > 0 has it too, so if every node above it does, the subquery returns a row exactly when the Limit's input does, with or without the Limit. That's the whole argument.

User-defined plans aren't in the list, so for an Extension the Limit stays and the subquery isn't decorrelated, the same as the offset 1 case. I rewrote the doc comment along these lines and renamed the function to depends_only_on_input_having_rows.

alamb · 2026-10-29T20:28:05Z

+/// A materialized CTE outputs exactly its continuation's rows, and only the
+/// continuation is rewritten, so its emptiness follows that input.
+///
+/// A `Filter` is what this leaves out: it reads values, so the rows the `Limit`


I found this really hard to understand -- it seems to be saying that Filter removes rows ?

Yes. A Filter keeps rows by their values, so which rows the Limit kept decides whether any get through. Reworded that paragraph to say it directly.

alamb · 2026-10-29T20:28:20Z

        )
    }

+    /// A `Limit` whose row count nothing above it can observe is still dropped,


what value do these tests add over just SLT tests?

Not much. The SLT cases cover the same shapes, and a subquery that isn't decorrelated fails to plan, so the passing SLT results already show the rewrite happened. Removed them.

Making progress

…t tests The plan tests pinned the same shapes the subquery.slt cases cover, and a subquery that is not decorrelated fails to plan, so the SLT results already show the rewrite happened. Also cover the NOT EXISTS form of apache#26629. Co-Authored-By: Claude Opus 5.5 (1M context) <[email protected]>

raghavyadav01 · 2026-10-30T17:12:08Z

Thanks @alamb. Pushed b1937e7: the doc comments now state one property (a node returns rows based only on whether its input has rows), and the unit tests that duplicated the SLT cases are gone. Replies inline.

Checked against DuckDB 1.5.6: the shapes that still decorrelate return the same rows, and the HAVING shape from #26629 (and its NOT EXISTS form, now in subquery.slt) errors instead of returning wrong rows.

jayzhan211 · 2026-11-02T14:36:51Z

Thanks @raghavyadav01 @alamb I think it is ready to merge

alamb · 2026-11-02T19:49:19Z

Thanks for getting this one in

github-actions Bot added optimizer Optimizer rules sqllogictest SQL Logic Tests (.slt) labels Oct 23, 2026

raghavyadav01 force-pushed the fix/exists-limit-below-row-counting-node branch from 1dd5a07 to 1cf3189 Compare October 24, 2026 20:14

Merge branch 'main' into fix/exists-limit-below-row-counting-node

a810d5e

jayzhan211 self-requested a review October 26, 2026 14:19

jayzhan211 requested changes Oct 28, 2026

View reviewed changes

alamb previously requested changes Oct 28, 2026

View reviewed changes

alamb marked this pull request as draft October 28, 2026 20:00

raghavyadav01 added 2 commits October 28, 2026 21:02

Merge branch 'main' into fix/exists-limit-below-row-counting-node

91c32c6

fix: treat a materialized CTE as following its input when dropping an…

d8f7cd7

… EXISTS limit Addresses review: a LIMIT at the root of a MATERIALIZED CTE continuation is safe to drop. Adds both cases to cte_materialized.slt.

alamb marked this pull request as ready for review October 29, 2026 18:14

alamb reviewed Oct 29, 2026

View reviewed changes

jayzhan211 approved these changes Nov 2, 2026

View reviewed changes

jayzhan211 added this pull request to the merge queue Nov 2, 2026

Merged via the queue into apache:main with commit 1aa6c29 Nov 2, 2026
44 checks passed

github-actions Bot added the v56.0.0 label Nov 2, 2026

jayzhan211 mentioned this pull request Nov 8, 2026

test: add correlated subquery cases for general decorrelation #26904

Merged

Conversation

raghavyadav01 commented Oct 23, 2026

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

The trade-off worth reviewing

What is the testing strategy for this PR?

Uh oh!

raghavyadav01 commented Oct 24, 2026

Uh oh!

raghavyadav01 commented Oct 26, 2026

Uh oh!

jayzhan211 commented Oct 27, 2026

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alamb left a comment

Choose a reason for hiding this comment

Uh oh!

raghavyadav01 commented Oct 29, 2026

Uh oh!

alamb commented Oct 29, 2026

Uh oh!

alamb left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

raghavyadav01 commented Oct 30, 2026

Uh oh!

jayzhan211 commented Nov 2, 2026

Uh oh!

Uh oh!

alamb commented Nov 2, 2026

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants