Skip to content

Commit 1cf3189

Browse files
raghavyadav01claude
andcommitted
fix: keep a LIMIT inside EXISTS that an operator above it can empty
`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]>
1 parent cd571e5 commit 1cf3189

3 files changed

Lines changed: 253 additions & 3 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 57 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -110,6 +110,13 @@ pub struct PullUpCorrelatedExpr {
110110
/// grouping set that omits a correlated column can tell whether
111111
/// something above it reads the column the pull up would fill in.
112112
column_refs_above: Vec<BTreeSet<Column>>,
113+
/// Whether, for each node on that same path, the emptiness of its output
114+
/// follows from the emptiness of its input alone. One entry per node,
115+
/// pushed and popped with [`Self::column_refs_above`]. `f_down`'s `Limit`
116+
/// arm reads it: a `Limit` may only be dropped from an `EXISTS` subquery
117+
/// when this holds of every node above it, because only then can none of
118+
/// them tell apart the limited rows and the full input.
119+
emptiness_follows_input_above: Vec<bool>,
113120
}
114121

115122
impl Default for PullUpCorrelatedExpr {
@@ -134,6 +141,7 @@ impl PullUpCorrelatedExpr {
134141
pulled_up_scalar_agg: false,
135142
correlated_filters: Vec::new(),
136143
column_refs_above: Vec::new(),
144+
emptiness_follows_input_above: Vec::new(),
137145
}
138146
}
139147

@@ -196,6 +204,8 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
196204
column_refs.extend(expr.column_refs().into_iter().cloned());
197205
}
198206
self.column_refs_above.push(column_refs);
207+
self.emptiness_follows_input_above
208+
.push(emptiness_follows_input(&plan));
199209

200210
// This match is exhaustive on purpose. A correlated filter moves above
201211
// a node only when the node is known to keep the result the same. Add
@@ -281,9 +291,8 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
281291
if !self.exists_sub_query {
282292
return Ok(self.stop_pull_up(plan));
283293
}
284-
// Only emptiness matters for EXISTS, so remove a limit that
285-
// cannot make its input empty and replace one that always does
286-
// with an empty relation.
294+
// A `LIMIT 0` always gives an empty input, whatever is
295+
// above it, so it becomes an empty relation.
287296
let fetch = limit.get_fetch_type()?;
288297
if matches!(fetch, FetchType::Literal(Some(0))) {
289298
return Ok(Transformed::yes(LogicalPlan::EmptyRelation(
@@ -293,6 +302,21 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
293302
},
294303
)));
295304
}
305+
// Dropping the `Limit` keeps its own input's emptiness, but
306+
// what `EXISTS` reads is whether the whole subquery is empty.
307+
// A node above the `Limit` whose output can be empty for a
308+
// reason of its own - a `Filter`, which the rows the `Limit`
309+
// kept decide - returns something else once the rows the
310+
// `Limit` held back reach it, so that `Limit` has to stay.
311+
// See https://github.com/apache/datafusion/issues/26629.
312+
let (_, above) = self
313+
.emptiness_follows_input_above
314+
.split_last()
315+
.expect("f_down pushed this Limit's own entry");
316+
if !above.iter().all(|follows| *follows) {
317+
return Ok(self.stop_pull_up(plan));
318+
}
319+
296320
match (limit.get_skip_type()?, fetch) {
297321
(SkipType::Literal(0), FetchType::Literal(_)) => {
298322
// The rewriter does not call `f_down` on the returned
@@ -302,6 +326,7 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
302326
// `f_up` call reaches this tree position once `Limit`
303327
// is gone, so only one entry must remain pushed.
304328
self.column_refs_above.pop();
329+
self.emptiness_follows_input_above.pop();
305330
let mut t = self.f_down((*limit.input).clone())?;
306331
t.transformed = true;
307332
Ok(t)
@@ -377,6 +402,7 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
377402
// Pop this node's own entry, pushed by the matching `f_down` call, so
378403
// `column_refs_above` holds only the nodes strictly above `plan`.
379404
self.column_refs_above.pop();
405+
self.emptiness_follows_input_above.pop();
380406

381407
// A node that null-extends or regroups rows can put a NULL back into
382408
// a column that a correlated filter below it rejected, so the filters
@@ -910,6 +936,34 @@ impl PullUpCorrelatedExpr {
910936
}
911937
}
912938

939+
/// Whether the emptiness of `plan`'s output follows from the emptiness of its
940+
/// input alone, so that `plan` cannot tell apart two non-empty inputs. Removing
941+
/// a `Limit` below such a node changes which rows it is given, never whether it
942+
/// is given any, and so never whether the subquery is empty.
943+
///
944+
/// A `Projection`, a `SubqueryAlias`, a `Sort`, a `Window` and a `Repartition`
945+
/// each output one row per input row. A `DISTINCT` and a grouped `Aggregate` output rows
946+
/// exactly when their input has rows, and an `Aggregate` without a grouping
947+
/// always outputs its one row, so no `Aggregate` can be emptied by the rows a
948+
/// `Limit` held back.
949+
///
950+
/// A `Filter` is what this leaves out: it reads values, so the rows the `Limit`
951+
/// kept decide whether anything survives it. A `Join`, a `Union` and an
952+
/// `Unnest` can empty a non-empty input too. Every other variant is treated the
953+
/// same way, so that a new one does not silently become droppable.
954+
fn emptiness_follows_input(plan: &LogicalPlan) -> bool {
955+
matches!(
956+
plan,
957+
LogicalPlan::Projection(_)
958+
| LogicalPlan::SubqueryAlias(_)
959+
| LogicalPlan::Sort(_)
960+
| LogicalPlan::Window(_)
961+
| LogicalPlan::Repartition(_)
962+
| LogicalPlan::Distinct(Distinct::All(_))
963+
| LogicalPlan::Aggregate(_)
964+
)
965+
}
966+
913967
/// Whether `plan` can output a NULL in a column that a filter below it keeps
914968
/// free of NULLs: an outer join fills the columns of its unmatched side with
915969
/// NULL, a union adds the rows of its other inputs, and a grouping set fills

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2804,6 +2804,137 @@ mod tests {
28042804
)
28052805
}
28062806

2807+
/// A `Limit` whose row count nothing above it can observe is still dropped,
2808+
/// so the subquery decorrelates. Here only a `Projection`, which outputs one
2809+
/// row per input row, sits above it.
2810+
#[test]
2811+
fn exists_subquery_with_limit_below_projection_is_decorrelated() -> Result<()> {
2812+
let sq = Arc::new(
2813+
LogicalPlanBuilder::from(scan_tpch_table("orders"))
2814+
.filter(
2815+
out_ref_col(DataType::Int64, "customer.c_custkey")
2816+
.eq(col("orders.o_custkey")),
2817+
)?
2818+
.limit(0, Some(1))?
2819+
.project(vec![col("orders.o_custkey")])?
2820+
.build()?,
2821+
);
2822+
2823+
let plan = LogicalPlanBuilder::from(scan_tpch_table("customer"))
2824+
.filter(exists(sq))?
2825+
.project(vec![col("customer.c_custkey")])?
2826+
.build()?;
2827+
2828+
assert_optimized_plan_equal!(
2829+
plan,
2830+
@r"
2831+
Projection: customer.c_custkey [c_custkey:Int64]
2832+
LeftSemi Join: Filter: customer.c_custkey = __correlated_sq_1.o_custkey [c_custkey:Int64, c_name:Utf8]
2833+
TableScan: customer [c_custkey:Int64, c_name:Utf8]
2834+
SubqueryAlias: __correlated_sq_1 [o_custkey:Int64]
2835+
Projection: orders.o_custkey [o_custkey:Int64]
2836+
TableScan: orders [o_orderkey:Int64, o_custkey:Int64, o_orderstatus:Utf8, o_totalprice:Float64;N]
2837+
"
2838+
)
2839+
}
2840+
2841+
/// An `Aggregate` above the `Limit` does not stop the `Limit` going away:
2842+
/// a grouping outputs rows exactly when its input has rows, and a grouping
2843+
/// -free `Aggregate` always outputs its one row, so neither can be emptied
2844+
/// by the rows the `Limit` held back.
2845+
#[test]
2846+
fn exists_subquery_with_limit_below_aggregate_is_decorrelated() -> Result<()> {
2847+
let sq = Arc::new(
2848+
LogicalPlanBuilder::from(scan_tpch_table("orders"))
2849+
.filter(
2850+
out_ref_col(DataType::Int64, "customer.c_custkey")
2851+
.eq(col("orders.o_custkey")),
2852+
)?
2853+
.limit(0, Some(1))?
2854+
.aggregate(Vec::<Expr>::new(), vec![count_udaf().call(vec![])])?
2855+
.build()?,
2856+
);
2857+
2858+
let plan = LogicalPlanBuilder::from(scan_tpch_table("customer"))
2859+
.filter(exists(sq))?
2860+
.project(vec![col("customer.c_custkey")])?
2861+
.build()?;
2862+
2863+
assert_optimized_plan_equal!(
2864+
plan,
2865+
@r"
2866+
Projection: customer.c_custkey [c_custkey:Int64]
2867+
Projection: customer.c_custkey, customer.c_name [c_custkey:Int64, c_name:Utf8]
2868+
Filter: Boolean(true) [c_custkey:Int64, c_name:Utf8, o_custkey:Int64;N, __always_true:Boolean;N, count():Int64;N]
2869+
Left Join: Filter: customer.c_custkey = __correlated_sq_1.o_custkey [c_custkey:Int64, c_name:Utf8, o_custkey:Int64;N, __always_true:Boolean;N, count():Int64;N]
2870+
TableScan: customer [c_custkey:Int64, c_name:Utf8]
2871+
SubqueryAlias: __correlated_sq_1 [o_custkey:Int64, __always_true:Boolean, count():Int64]
2872+
Aggregate: groupBy=[[orders.o_custkey, Boolean(true) AS __always_true]], aggr=[[count()]] [o_custkey:Int64, __always_true:Boolean, count():Int64]
2873+
TableScan: orders [o_orderkey:Int64, o_custkey:Int64, o_orderstatus:Utf8, o_totalprice:Float64;N]
2874+
"
2875+
)
2876+
}
2877+
2878+
/// A `HAVING` above the `Aggregate` reads the aggregate's value, so the
2879+
/// rows the `Limit` kept decide it: `HAVING count(*) > 1` can never hold
2880+
/// over the one row `LIMIT 1` keeps, however many rows the scan has.
2881+
/// https://github.com/apache/datafusion/issues/26629
2882+
#[test]
2883+
fn exists_subquery_with_limit_below_having_is_left_unchanged() -> Result<()> {
2884+
let sq = Arc::new(
2885+
LogicalPlanBuilder::from(scan_tpch_table("orders"))
2886+
.filter(
2887+
out_ref_col(DataType::Int64, "customer.c_custkey")
2888+
.eq(col("orders.o_custkey")),
2889+
)?
2890+
.limit(0, Some(1))?
2891+
.aggregate(Vec::<Expr>::new(), vec![count_udaf().call(vec![])])?
2892+
.filter(col("count()").gt(lit(1)))?
2893+
.build()?,
2894+
);
2895+
2896+
let plan = LogicalPlanBuilder::from(scan_tpch_table("customer"))
2897+
.filter(exists(sq))?
2898+
.project(vec![col("customer.c_custkey")])?
2899+
.build()?;
2900+
2901+
let result = DecorrelatePredicateSubquery::new()
2902+
.rewrite(plan.clone(), &crate::OptimizerContext::new())?;
2903+
2904+
assert!(!result.transformed);
2905+
assert_eq!(result.data, plan);
2906+
Ok(())
2907+
}
2908+
2909+
/// A `Filter` above the `Limit` reads the rows the `Limit` kept, so dropping
2910+
/// the `Limit` lets rows it held back decide the filter.
2911+
/// https://github.com/apache/datafusion/issues/26629
2912+
#[test]
2913+
fn exists_subquery_with_limit_below_filter_is_left_unchanged() -> Result<()> {
2914+
let sq = Arc::new(
2915+
LogicalPlanBuilder::from(scan_tpch_table("orders"))
2916+
.filter(
2917+
out_ref_col(DataType::Int64, "customer.c_custkey")
2918+
.eq(col("orders.o_custkey")),
2919+
)?
2920+
.limit(0, Some(1))?
2921+
.filter(col("orders.o_orderkey").eq(lit(1)))?
2922+
.build()?,
2923+
);
2924+
2925+
let plan = LogicalPlanBuilder::from(scan_tpch_table("customer"))
2926+
.filter(exists(sq))?
2927+
.project(vec![col("customer.c_custkey")])?
2928+
.build()?;
2929+
2930+
let result = DecorrelatePredicateSubquery::new()
2931+
.rewrite(plan.clone(), &crate::OptimizerContext::new())?;
2932+
2933+
assert!(!result.transformed);
2934+
assert_eq!(result.data, plan);
2935+
Ok(())
2936+
}
2937+
28072938
#[test]
28082939
fn exists_subquery_no_cols() -> Result<()> {
28092940
let sq = Arc::new(

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -792,6 +792,71 @@ SELECT t1_id FROM t1 WHERE EXISTS (SELECT 1 FROM (SELECT * FROM t2 WHERE t2_id =
792792
----
793793
22
794794

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

0 commit comments

Comments
 (0)