Skip to content

Commit 24e351c

Browse files
fornwallkosiew
authored andcommitted
fix: keep the OFFSET of a correlated EXISTS subquery (apache#25284)
## Which issue does this PR close? Closes apache#25283. ## Rationale for this change A correlated `EXISTS` subquery with an `OFFSET` returns wrong results, because the `OFFSET` is dropped when the subquery is rewritten into a semi join: ```sql CREATE TABLE t1(k INT) AS VALUES (1), (2), (3); CREATE TABLE t2(v INT) AS VALUES (1), (1), (3); SELECT k FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2.v = t1.k OFFSET 1); ``` Only `k = 1` has two matching rows, so the expected result is a single row with `1` (as SQLite returns). DataFusion returns `1` and `3`. `NOT EXISTS` is wrong the same way. `PullUpCorrelatedExpr` removes the `LIMIT` above the correlated filter of an `EXISTS` subquery, since `LIMIT n` with `n > 0` cannot change whether any row exists. But the same node carries the `OFFSET`, which can turn a non-empty subquery into an empty one. The decision to remove a `Limit` was also keyed on whether *any* correlated predicate had been collected so far, not on whether one sat below *this* `Limit`. In a join inside the `EXISTS` the correlated side is visited first, so a `LIMIT` on an uncorrelated sibling branch was removed too, changing the result: ```sql SELECT t1_id FROM t1 WHERE EXISTS ( SELECT 1 FROM (SELECT * FROM t2 WHERE t2_id = t1_id) a JOIN (SELECT * FROM t3 ORDER BY t3_id LIMIT 1) b ON a.t2_int = b.t3_int) ``` With the `subquery.slt` fixtures this returned `11, 22, 44` instead of `11, 44`. ## What changes are included in this PR? `PullUpCorrelatedExpr` now decides per `Limit`, in `f_down`, whether it sits above correlated expressions, using the outer references of its own subtree (as it already did for `IN` subqueries), and rewrites the `Limit` right there. For a correlated `EXISTS`, the `Limit` is only removed when it cannot change whether the subquery is empty: a zero offset with a literal fetch. A zero fetch still becomes an empty relation. Anything else (a positive or non-literal offset, or a non-literal fetch) marks the subquery as not pull-up-able, so it stays correlated and fails as unsupported instead of returning wrong rows. A `Limit` with no correlated expressions below it is left alone. ## What is the testing strategy for this PR? New sqllogictest cases in `subquery.slt`: - `LIMIT 1 OFFSET 0` is still decorrelated. - `OFFSET 1` keeps the subquery correlated, and running the query fails with a not-implemented error. The explain case fails without the fix. The same for `NOT EXISTS`, and for `EXISTS` in a disjunction. - `LIMIT 0 OFFSET 1` still becomes an empty relation. - A non-literal `LIMIT` keeps the subquery correlated. - A `LIMIT` or `OFFSET` on an uncorrelated branch of a join inside the `EXISTS` is kept and the query returns the correct rows. Both fail without the per-`Limit` decision. ## Are there any user-facing changes? - A correlated `EXISTS` / `NOT EXISTS` subquery with a positive `OFFSET`, or with a non-literal `LIMIT`, now fails with a not-implemented error instead of returning wrong results (previously the `LIMIT` / `OFFSET` was silently dropped). I can file an issue and take a stab at supporting these in a follow-up once this is merged. - A `LIMIT` or `OFFSET` on an uncorrelated branch inside a correlated `EXISTS` subquery is no longer dropped, so such queries now return correct results. Disclaimer: Created with fable 5.1 in claude code. I have reviewed the code. --------- Signed-off-by: Fredrik Fornwall <[email protected]> Co-authored-by: kosiew <[email protected]>
1 parent 9eda9e7 commit 24e351c

2 files changed

Lines changed: 197 additions & 33 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 41 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ use datafusion_expr::utils::{
3737
};
3838
use datafusion_expr::{
3939
BinaryExpr, Cast, EmptyRelation, Expr, ExprSchemable, FetchType, LogicalPlan,
40-
LogicalPlanBuilder, Operator, expr, lit,
40+
LogicalPlanBuilder, Operator, SkipType, expr, lit,
4141
};
4242

4343
/// This struct rewrite the sub query plan by pull up the correlated
@@ -135,6 +135,13 @@ impl PullUpCorrelatedExpr {
135135
self.exists_sub_query = exists_sub_query;
136136
self
137137
}
138+
139+
/// Mark the plan as one whose correlated expressions cannot be pulled up
140+
/// and stop descending into it
141+
fn unsupported(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
142+
self.can_pull_up = false;
143+
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
144+
}
138145
}
139146

140147
/// Used to indicate the unmatched rows from the inner(subquery) table after the left out Join
@@ -174,28 +181,44 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
174181
LogicalPlan::Union(_) | LogicalPlan::Sort(_) | LogicalPlan::Extension(_) => {
175182
let plan_hold_outer = !plan.all_out_ref_exprs().is_empty();
176183
if plan_hold_outer {
177-
// the unsupported case
178-
self.can_pull_up = false;
179-
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
184+
self.unsupported(plan)
180185
} else {
181186
Ok(Transformed::no(plan))
182187
}
183188
}
184-
LogicalPlan::Limit(_) => {
185-
let plan_hold_outer = !plan.all_out_ref_exprs().is_empty();
186-
match (self.exists_sub_query, plan_hold_outer) {
187-
(false, true) => {
188-
// the unsupported case
189-
self.can_pull_up = false;
190-
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
189+
LogicalPlan::Limit(ref limit) => {
190+
if plan.all_out_ref_exprs().is_empty() {
191+
return Ok(Transformed::no(plan));
192+
}
193+
if !self.exists_sub_query {
194+
return self.unsupported(plan);
195+
}
196+
// Only emptiness matters for EXISTS, so remove a limit that
197+
// cannot make its input empty and replace one that always does
198+
// with an empty relation.
199+
let fetch = limit.get_fetch_type()?;
200+
if matches!(fetch, FetchType::Literal(Some(0))) {
201+
return Ok(Transformed::yes(LogicalPlan::EmptyRelation(
202+
EmptyRelation {
203+
produce_one_row: false,
204+
schema: Arc::clone(limit.input.schema()),
205+
},
206+
)));
207+
}
208+
match (limit.get_skip_type()?, fetch) {
209+
(SkipType::Literal(0), FetchType::Literal(_)) => {
210+
// The rewriter does not call `f_down` on the returned
211+
// node, so do it here
212+
let mut t = self.f_down((*limit.input).clone())?;
213+
t.transformed = true;
214+
Ok(t)
191215
}
192-
_ => Ok(Transformed::no(plan)),
216+
_ => self.unsupported(plan),
193217
}
194218
}
195219
_ if plan.contains_outer_reference() => {
196220
// the unsupported cases, the plan expressions contain out reference columns(like window expressions)
197-
self.can_pull_up = false;
198-
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
221+
self.unsupported(plan)
199222
}
200223
_ => Ok(Transformed::no(plan)),
201224
}
@@ -455,28 +478,13 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
455478
}
456479
}
457480
LogicalPlan::Limit(limit) => {
458-
let input_expr_map =
459-
self.collected_count_expr_map.get(&*limit.input).cloned();
460-
// handling the limit clause in the subquery
461-
let new_plan = match (self.exists_sub_query, self.join_filters.is_empty())
481+
if let Some(input_map) =
482+
self.collected_count_expr_map.get(&*limit.input).cloned()
462483
{
463-
// Correlated exist subquery, remove the limit(so that correlated expressions can pull up)
464-
(true, false) => Transformed::yes(match limit.get_fetch_type()? {
465-
FetchType::Literal(Some(0)) => {
466-
LogicalPlan::EmptyRelation(EmptyRelation {
467-
produce_one_row: false,
468-
schema: Arc::clone(limit.input.schema()),
469-
})
470-
}
471-
_ => LogicalPlanBuilder::from((*limit.input).clone()).build()?,
472-
}),
473-
_ => Transformed::no(plan),
474-
};
475-
if let Some(input_map) = input_expr_map {
476484
self.collected_count_expr_map
477-
.insert(new_plan.data.clone(), input_map);
485+
.insert(plan.clone(), input_map);
478486
}
479-
Ok(new_plan)
487+
Ok(Transformed::no(plan))
480488
}
481489
_ => Ok(Transformed::no(plan)),
482490
}

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -656,6 +656,142 @@ SELECT t1_id, t1_name FROM t1 WHERE NOT EXISTS (SELECT * FROM t2 WHERE t2_id = t
656656
33 c
657657
44 d
658658

659+
#exists_subquery_with_offset0
660+
#de-correlated, limit is removed
661+
query TT
662+
explain SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id limit 1 offset 0)
663+
----
664+
logical_plan
665+
01)LeftSemi Join: t1.t1_id = __correlated_sq_1.t2_id
666+
02)--TableScan: t1 projection=[t1_id, t1_name]
667+
03)--SubqueryAlias: __correlated_sq_1
668+
04)----TableScan: t2 projection=[t2_id]
669+
670+
query IT rowsort
671+
SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id limit 1 offset 0)
672+
----
673+
11 a
674+
22 b
675+
44 d
676+
677+
#exists_subquery_with_offset
678+
#not de-correlated, the offset could make the subquery empty
679+
query TT
680+
explain SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)
681+
----
682+
logical_plan
683+
01)Filter: EXISTS (<subquery>)
684+
02)--Subquery:
685+
03)----Limit: skip=1, fetch=None
686+
04)------Projection: t2.t2_id, t2.t2_name, t2.t2_int
687+
05)--------Filter: t2.t2_id = outer_ref(t1.t1_id)
688+
06)----------TableScan: t2
689+
07)--TableScan: t1 projection=[t1_id, t1_name]
690+
691+
# errors rather than returning wrong rows
692+
query error Physical plan does not support logical expression Exists
693+
SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)
694+
695+
#not_exists_subquery_with_offset
696+
#not de-correlated, the offset could make the subquery empty
697+
query TT
698+
explain SELECT t1_id, t1_name FROM t1 WHERE NOT EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)
699+
----
700+
logical_plan
701+
01)Filter: NOT EXISTS (<subquery>)
702+
02)--Subquery:
703+
03)----Limit: skip=1, fetch=None
704+
04)------Projection: t2.t2_id, t2.t2_name, t2.t2_int
705+
05)--------Filter: t2.t2_id = outer_ref(t1.t1_id)
706+
06)----------TableScan: t2
707+
07)--TableScan: t1 projection=[t1_id, t1_name]
708+
709+
# errors rather than returning wrong rows
710+
query error Physical plan does not support logical expression Exists
711+
SELECT t1_id, t1_name FROM t1 WHERE NOT EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)
712+
713+
#exists_subquery_with_offset_in_disjunction
714+
#not de-correlated, errors rather than returning wrong rows
715+
query error Physical plan does not support logical expression Exists
716+
SELECT t1_id, t1_name FROM t1 WHERE t1_id > 40 OR EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)
717+
718+
#exists_subquery_with_limit0_and_offset
719+
#de-correlated, limit 0 is empty whatever the offset
720+
query TT
721+
explain SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id limit 0 offset 1)
722+
----
723+
logical_plan EmptyRelation: rows=0
724+
725+
query IT rowsort
726+
SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id limit 0 offset 1)
727+
----
728+
729+
#exists_subquery_with_non_literal_limit
730+
#not de-correlated, the fetch could evaluate to 0 and make the subquery empty
731+
query TT
732+
explain SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id limit (SELECT count(*) FROM t2))
733+
----
734+
logical_plan
735+
01)Filter: EXISTS (<subquery>)
736+
02)--Subquery:
737+
03)----Limit: skip=0, fetch=(<subquery>)
738+
04)------Subquery:
739+
05)--------Projection: count(Int64(1)) AS count(*)
740+
06)----------Aggregate: groupBy=[[]], aggr=[[count(Int64(1))]]
741+
07)------------TableScan: t2
742+
08)------Projection: t2.t2_id, t2.t2_name, t2.t2_int
743+
09)--------Filter: t2.t2_id = outer_ref(t1.t1_id)
744+
10)----------TableScan: t2
745+
11)--TableScan: t1 projection=[t1_id, t1_name]
746+
747+
#exists_subquery_with_non_literal_offset
748+
#not de-correlated, the offset could be positive and make the subquery empty
749+
query TT
750+
explain SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset (SELECT 1))
751+
----
752+
logical_plan
753+
01)Filter: EXISTS (<subquery>)
754+
02)--Subquery:
755+
03)----Limit: skip=(<subquery>), fetch=None
756+
04)------Subquery:
757+
05)--------Projection: Int64(1)
758+
06)----------EmptyRelation: rows=1
759+
07)------Projection: t2.t2_id, t2.t2_name, t2.t2_int
760+
08)--------Filter: t2.t2_id = outer_ref(t1.t1_id)
761+
09)----------TableScan: t2
762+
10)--TableScan: t1 projection=[t1_id, t1_name]
763+
764+
#exists_subquery_with_limit_on_uncorrelated_branch
765+
#de-correlated, the limit is on an uncorrelated branch so it stays
766+
query TT
767+
explain SELECT t1_id FROM t1 WHERE EXISTS (SELECT 1 FROM (SELECT * FROM t2 WHERE t2_id = t1_id) a JOIN (SELECT * FROM t3 ORDER BY t3_id LIMIT 1) b ON a.t2_int = b.t3_int)
768+
----
769+
logical_plan
770+
01)LeftSemi Join: t1.t1_id = __correlated_sq_1.t2_id
771+
02)--TableScan: t1 projection=[t1_id]
772+
03)--SubqueryAlias: __correlated_sq_1
773+
04)----Projection: a.t2_id
774+
05)------LeftSemi Join: a.t2_int = b.t3_int
775+
06)--------SubqueryAlias: a
776+
07)----------TableScan: t2 projection=[t2_id, t2_int]
777+
08)--------SubqueryAlias: b
778+
09)----------Projection: t3.t3_int
779+
10)------------Sort: t3.t3_id ASC NULLS LAST, fetch=1
780+
11)--------------TableScan: t3 projection=[t3_id, t3_int]
781+
782+
query I rowsort
783+
SELECT t1_id FROM t1 WHERE EXISTS (SELECT 1 FROM (SELECT * FROM t2 WHERE t2_id = t1_id) a JOIN (SELECT * FROM t3 ORDER BY t3_id LIMIT 1) b ON a.t2_int = b.t3_int)
784+
----
785+
11
786+
44
787+
788+
#exists_subquery_with_offset_on_uncorrelated_branch
789+
#de-correlated, the offset is on an uncorrelated branch so it stays
790+
query I rowsort
791+
SELECT t1_id FROM t1 WHERE EXISTS (SELECT 1 FROM (SELECT * FROM t2 WHERE t2_id = t1_id) a JOIN (SELECT * FROM t3 ORDER BY t3_id LIMIT 1 OFFSET 1) b ON a.t2_int = b.t3_int)
792+
----
793+
22
794+
659795
#in_correlated_subquery_with_limit
660796
#not de-correlated
661797
query TT
@@ -717,6 +853,26 @@ logical_plan
717853
09)----------TableScan: t2
718854
10)--TableScan: t1 projection=[t1_id, t1_name]
719855

856+
#exists_subquery_with_limit_over_union
857+
#not de-correlated, the union below the removed limit still holds outer references
858+
query TT
859+
explain SELECT t1_id, t1_name FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id UNION ALL SELECT * FROM t2 WHERE upper(t2_name) = upper(t1.t1_name) LIMIT 1)
860+
----
861+
logical_plan
862+
01)Filter: EXISTS (<subquery>)
863+
02)--Subquery:
864+
03)----Limit: skip=0, fetch=1
865+
04)------Union
866+
05)--------Projection: t2.t2_id, t2.t2_name, t2.t2_int
867+
06)----------Limit: skip=0, fetch=1
868+
07)------------Filter: t2.t2_id = outer_ref(t1.t1_id)
869+
08)--------------TableScan: t2
870+
09)--------Projection: t2.t2_id, t2.t2_name, t2.t2_int
871+
10)----------Limit: skip=0, fetch=1
872+
11)------------Filter: upper(t2.t2_name) = upper(outer_ref(t1.t1_name))
873+
12)--------------TableScan: t2
874+
13)--TableScan: t1 projection=[t1_id, t1_name]
875+
720876
#simple_uncorrelated_scalar_subquery
721877
query TT
722878
explain select (select count(*) from t1) as b

0 commit comments

Comments
 (0)