Skip to content

Commit 1aa6c29

Browse files
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/decorrelate.rs‎

Lines changed: 64 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,12 @@ pub struct PullUpCorrelatedExpr {
9797
/// grouping set that omits a correlated column can tell whether
9898
/// something above it reads the column the pull up would fill in.
9999
column_refs_above: Vec<BTreeSet<Column>>,
100+
/// For each node on that same path, whether it returns rows based only on
101+
/// whether its input has rows (see [`depends_only_on_input_having_rows`]). One
102+
/// entry per node, pushed and popped with [`Self::column_refs_above`].
103+
/// `f_down`'s `Limit` arm reads it: a `Limit` is only dropped from an
104+
/// `EXISTS` subquery when this holds for every node above it.
105+
depends_only_on_input_having_rows_above: Vec<bool>,
100106
}
101107

102108
impl Default for PullUpCorrelatedExpr {
@@ -121,6 +127,7 @@ impl PullUpCorrelatedExpr {
121127
pulled_up_scalar_agg: false,
122128
correlated_filters: Vec::new(),
123129
column_refs_above: Vec::new(),
130+
depends_only_on_input_having_rows_above: Vec::new(),
124131
}
125132
}
126133

@@ -183,6 +190,8 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
183190
column_refs.extend(expr.column_refs().into_iter().cloned());
184191
}
185192
self.column_refs_above.push(column_refs);
193+
self.depends_only_on_input_having_rows_above
194+
.push(depends_only_on_input_having_rows(&plan));
186195

187196
// This match is exhaustive on purpose. A correlated filter moves above
188197
// a node only when the node is known to keep the result the same. Add
@@ -268,9 +277,8 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
268277
if !self.exists_sub_query {
269278
return Ok(self.stop_pull_up(plan));
270279
}
271-
// Only emptiness matters for EXISTS, so remove a limit that
272-
// cannot make its input empty and replace one that always does
273-
// with an empty relation.
280+
// A `LIMIT 0` always gives an empty input, whatever is
281+
// above it, so it becomes an empty relation.
274282
let fetch = limit.get_fetch_type()?;
275283
if matches!(fetch, FetchType::Literal(Some(0))) {
276284
return Ok(Transformed::yes(LogicalPlan::EmptyRelation(
@@ -280,6 +288,20 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
280288
},
281289
)));
282290
}
291+
// `EXISTS` asks whether the whole subquery returns a row, not
292+
// whether this `Limit` does. If a node above the `Limit` looks
293+
// at which rows it gets, such as a `Filter` or the `HAVING` in
294+
// https://github.com/apache/datafusion/issues/26629, removing
295+
// the `Limit` hands it different rows and can change the
296+
// answer, so the `Limit` has to stay.
297+
let (_, above) = self
298+
.depends_only_on_input_having_rows_above
299+
.split_last()
300+
.expect("f_down pushed this Limit's own entry");
301+
if !above.iter().all(|follows| *follows) {
302+
return Ok(self.stop_pull_up(plan));
303+
}
304+
283305
match (limit.get_skip_type()?, fetch) {
284306
(SkipType::Literal(0), FetchType::Literal(_)) => {
285307
// The rewriter does not call `f_down` on the returned
@@ -289,6 +311,7 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
289311
// `f_up` call reaches this tree position once `Limit`
290312
// is gone, so only one entry must remain pushed.
291313
self.column_refs_above.pop();
314+
self.depends_only_on_input_having_rows_above.pop();
292315
let mut t = self.f_down((*limit.input).clone())?;
293316
t.transformed = true;
294317
Ok(t)
@@ -364,6 +387,7 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
364387
// Pop this node's own entry, pushed by the matching `f_down` call, so
365388
// `column_refs_above` holds only the nodes strictly above `plan`.
366389
self.column_refs_above.pop();
390+
self.depends_only_on_input_having_rows_above.pop();
367391

368392
// A node that null-extends or regroups rows can put a NULL back into
369393
// a column that a correlated filter below it rejected, so the filters
@@ -897,6 +921,43 @@ impl PullUpCorrelatedExpr {
897921
}
898922
}
899923

924+
/// Whether `plan` returns rows based only on whether its input has rows, and
925+
/// not on which rows those are.
926+
///
927+
/// This is what lets `EXISTS` drop a `Limit` with no skip and a non-zero
928+
/// fetch. Such a `Limit` returns rows exactly when its input has rows. If
929+
/// every node above it also only depends on whether it gets rows, the whole
930+
/// subquery returns rows exactly when the `Limit`'s input has rows, with or
931+
/// without the `Limit`, so removing it cannot change the `EXISTS` result.
932+
///
933+
/// It holds for:
934+
/// - `Projection`, `SubqueryAlias`, `Sort`, `Window` and `Repartition`, which
935+
/// return rows whenever their input has rows (a `Sort` with a fetch of 0
936+
/// returns none either way)
937+
/// - `DISTINCT` and a grouped `Aggregate`, which return at least one row for a
938+
/// non-empty input and none for an empty one
939+
/// - an `Aggregate` without grouping, which always returns one row
940+
/// - a materialized CTE, which returns its continuation's rows
941+
///
942+
/// It does not hold for a `Filter`, which keeps or removes rows by their
943+
/// values, so the rows the `Limit` kept decide whether any survive. A `Join`
944+
/// and an `Unnest` can also turn rows into none. Every other plan, including a
945+
/// user-defined `Extension`, is treated as not holding: the `Limit` stays and
946+
/// the subquery is not decorrelated.
947+
fn depends_only_on_input_having_rows(plan: &LogicalPlan) -> bool {
948+
matches!(
949+
plan,
950+
LogicalPlan::Projection(_)
951+
| LogicalPlan::SubqueryAlias(_)
952+
| LogicalPlan::Sort(_)
953+
| LogicalPlan::Window(_)
954+
| LogicalPlan::Repartition(_)
955+
| LogicalPlan::Distinct(Distinct::All(_))
956+
| LogicalPlan::Aggregate(_)
957+
| LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(_))
958+
)
959+
}
960+
900961
/// Whether `plan` can output a NULL in a column that a filter below it keeps
901962
/// free of NULLs: an outer join fills the columns of its unmatched side with
902963
/// NULL, a union adds the rows of its other inputs, and a grouping set fills

‎datafusion/sqllogictest/test_files/cte_materialized.slt‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -210,6 +210,22 @@ SELECT k FROM t WHERE v IN (
210210
3
211211
4
212212

213+
# A LIMIT at the root of the continuation does not change whether it is empty.
214+
query I rowsort
215+
SELECT k FROM t WHERE EXISTS (
216+
WITH r AS MATERIALIZED (SELECT k AS rk FROM t)
217+
SELECT 1 FROM r WHERE r.rk = t.k + 1 LIMIT 1)
218+
----
219+
1
220+
2
221+
3
222+
223+
# A filter above the LIMIT reads the row the LIMIT kept, so it stays correlated.
224+
query error Physical plan does not support logical expression Exists
225+
SELECT k FROM t WHERE EXISTS (
226+
WITH r AS MATERIALIZED (SELECT k AS rk, v AS rv FROM t)
227+
SELECT 1 FROM (SELECT * FROM r WHERE r.rk = t.k LIMIT 1) s WHERE s.rv > 0)
228+
213229
# A body that refers to the outer query would have to run once per outer row.
214230
# Such a CTE is inlined, as if MATERIALIZED was not given.
215231
query I rowsort

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -779,6 +779,75 @@ SELECT t1_id FROM t1 WHERE EXISTS (SELECT 1 FROM (SELECT * FROM t2 WHERE t2_id =
779779
----
780780
22
781781

782+
#exists_subquery_with_limit_below_having
783+
#not de-correlated, the limit decides the count the HAVING reads: count(*) over
784+
#the one row LIMIT 1 keeps can never exceed 1, so the subquery is always empty.
785+
#Dropping the limit counted the whole scan and this returned 33.
786+
#https://github.com/apache/datafusion/issues/26629
787+
query TT
788+
explain 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)
789+
----
790+
logical_plan
791+
01)Projection: t1.t1_id
792+
02)--Filter: EXISTS (<subquery>)
793+
03)----Subquery:
794+
04)------Projection: Int64(1)
795+
05)--------Filter: count(Int64(1)) > Int64(1)
796+
06)----------Aggregate: groupBy=[[]], aggr=[[count(Int64(1))]]
797+
07)------------SubqueryAlias: s
798+
08)--------------Projection: t2.t2_id
799+
09)----------------Limit: skip=0, fetch=1
800+
10)------------------Filter: t2.t2_int = outer_ref(t1.t1_int)
801+
11)--------------------TableScan: t2
802+
12)----TableScan: t1 projection=[t1_id, t1_int]
803+
804+
# errors rather than returning wrong rows
805+
query error Physical plan does not support logical expression Exists
806+
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)
807+
808+
# same for NOT EXISTS, which returned 11, 22, 44 instead of every row
809+
query error Physical plan does not support logical expression Exists
810+
SELECT t1_id FROM t1 WHERE NOT EXISTS (SELECT 1 FROM (SELECT t2_id FROM t2 WHERE t2_int = t1_int LIMIT 1) s HAVING count(*) > 1)
811+
812+
#exists_subquery_with_limit_below_filter
813+
#not de-correlated, the rows the limit keeps decide the filter above it
814+
query error Physical plan does not support logical expression Exists
815+
SELECT t1_id FROM t1 WHERE EXISTS (SELECT 1 FROM (SELECT t2_id, t2_int FROM t2 WHERE t2_id = t1_id LIMIT 1) s WHERE s.t2_int > 2)
816+
817+
#exists_subquery_with_limit_below_aggregate
818+
#de-correlated, an aggregate without a grouping always returns its one row, so
819+
#the rows the limit held back cannot change whether the subquery is empty
820+
query TT
821+
explain SELECT t1_id FROM t1 WHERE EXISTS (SELECT count(*) FROM (SELECT t2_id FROM t2 WHERE t2_id = t1_id LIMIT 1) s)
822+
----
823+
logical_plan TableScan: t1 projection=[t1_id]
824+
825+
query I rowsort
826+
SELECT t1_id FROM t1 WHERE EXISTS (SELECT count(*) FROM (SELECT t2_id FROM t2 WHERE t2_id = t1_id LIMIT 1) s)
827+
----
828+
11
829+
22
830+
33
831+
44
832+
833+
#exists_subquery_with_limit_below_distinct
834+
#de-correlated, a DISTINCT has rows exactly when its input has rows
835+
query I rowsort
836+
SELECT t1_id FROM t1 WHERE EXISTS (SELECT DISTINCT s.t2_id FROM (SELECT t2_id FROM t2 WHERE t2_id = t1_id LIMIT 1) s)
837+
----
838+
11
839+
22
840+
44
841+
842+
#exists_subquery_with_limit_below_group_by
843+
#de-correlated, a grouping has rows exactly when its input has rows
844+
query I rowsort
845+
SELECT t1_id FROM t1 WHERE EXISTS (SELECT s.t2_id FROM (SELECT t2_id FROM t2 WHERE t2_id = t1_id LIMIT 1) s GROUP BY s.t2_id)
846+
----
847+
11
848+
22
849+
44
850+
782851
#in_correlated_subquery_with_limit
783852
#not de-correlated
784853
query TT

0 commit comments

Comments
 (0)