Skip to content

Commit b1937e7

Browse files
raghavyadav01claude
andcommitted
docs: state the EXISTS Limit rule as one property, drop duplicate unit 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]>
1 parent d8f7cd7 commit b1937e7

3 files changed

Lines changed: 44 additions & 167 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 40 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -97,13 +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-
/// Whether, for each node on that same path, the emptiness of its output
101-
/// follows from the emptiness of its input alone. One entry per node,
102-
/// pushed and popped with [`Self::column_refs_above`]. `f_down`'s `Limit`
103-
/// arm reads it: a `Limit` may only be dropped from an `EXISTS` subquery
104-
/// when this holds of every node above it, because only then can none of
105-
/// them tell apart the limited rows and the full input.
106-
emptiness_follows_input_above: Vec<bool>,
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>,
107106
}
108107

109108
impl Default for PullUpCorrelatedExpr {
@@ -128,7 +127,7 @@ impl PullUpCorrelatedExpr {
128127
pulled_up_scalar_agg: false,
129128
correlated_filters: Vec::new(),
130129
column_refs_above: Vec::new(),
131-
emptiness_follows_input_above: Vec::new(),
130+
depends_only_on_input_having_rows_above: Vec::new(),
132131
}
133132
}
134133

@@ -191,8 +190,8 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
191190
column_refs.extend(expr.column_refs().into_iter().cloned());
192191
}
193192
self.column_refs_above.push(column_refs);
194-
self.emptiness_follows_input_above
195-
.push(emptiness_follows_input(&plan));
193+
self.depends_only_on_input_having_rows_above
194+
.push(depends_only_on_input_having_rows(&plan));
196195

197196
// This match is exhaustive on purpose. A correlated filter moves above
198197
// a node only when the node is known to keep the result the same. Add
@@ -289,15 +288,14 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
289288
},
290289
)));
291290
}
292-
// Dropping the `Limit` keeps its own input's emptiness, but
293-
// what `EXISTS` reads is whether the whole subquery is empty.
294-
// A node above the `Limit` whose output can be empty for a
295-
// reason of its own - a `Filter`, which the rows the `Limit`
296-
// kept decide - returns something else once the rows the
297-
// `Limit` held back reach it, so that `Limit` has to stay.
298-
// See https://github.com/apache/datafusion/issues/26629.
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.
299297
let (_, above) = self
300-
.emptiness_follows_input_above
298+
.depends_only_on_input_having_rows_above
301299
.split_last()
302300
.expect("f_down pushed this Limit's own entry");
303301
if !above.iter().all(|follows| *follows) {
@@ -313,7 +311,7 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
313311
// `f_up` call reaches this tree position once `Limit`
314312
// is gone, so only one entry must remain pushed.
315313
self.column_refs_above.pop();
316-
self.emptiness_follows_input_above.pop();
314+
self.depends_only_on_input_having_rows_above.pop();
317315
let mut t = self.f_down((*limit.input).clone())?;
318316
t.transformed = true;
319317
Ok(t)
@@ -389,7 +387,7 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
389387
// Pop this node's own entry, pushed by the matching `f_down` call, so
390388
// `column_refs_above` holds only the nodes strictly above `plan`.
391389
self.column_refs_above.pop();
392-
self.emptiness_follows_input_above.pop();
390+
self.depends_only_on_input_having_rows_above.pop();
393391

394392
// A node that null-extends or regroups rows can put a NULL back into
395393
// a column that a correlated filter below it rejected, so the filters
@@ -923,24 +921,30 @@ impl PullUpCorrelatedExpr {
923921
}
924922
}
925923

926-
/// Whether the emptiness of `plan`'s output follows from the emptiness of its
927-
/// input alone, so that `plan` cannot tell apart two non-empty inputs. Removing
928-
/// a `Limit` below such a node changes which rows it is given, never whether it
929-
/// is given any, and so never whether the subquery is empty.
924+
/// Whether `plan` returns rows based only on whether its input has rows, and
925+
/// not on which rows those are.
930926
///
931-
/// A `Projection`, a `SubqueryAlias`, a `Sort`, a `Window` and a `Repartition`
932-
/// each output one row per input row. A `DISTINCT` and a grouped `Aggregate` output rows
933-
/// exactly when their input has rows, and an `Aggregate` without a grouping
934-
/// always outputs its one row, so no `Aggregate` can be emptied by the rows a
935-
/// `Limit` held back.
936-
/// A materialized CTE outputs exactly its continuation's rows, and only the
937-
/// continuation is rewritten, so its emptiness follows that input.
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.
938932
///
939-
/// A `Filter` is what this leaves out: it reads values, so the rows the `Limit`
940-
/// kept decide whether anything survives it. A `Join` and an `Unnest` can empty
941-
/// a non-empty input too. Every other variant is treated the same way, so that
942-
/// a new one does not silently become droppable.
943-
fn emptiness_follows_input(plan: &LogicalPlan) -> bool {
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 {
944948
matches!(
945949
plan,
946950
LogicalPlan::Projection(_)

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 0 additions & 131 deletions
Original file line numberDiff line numberDiff line change
@@ -2820,137 +2820,6 @@ mod tests {
28202820
)
28212821
}
28222822

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

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -805,6 +805,10 @@ logical_plan
805805
query error Physical plan does not support logical expression Exists
806806
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)
807807

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+
808812
#exists_subquery_with_limit_below_filter
809813
#not de-correlated, the rows the limit keeps decide the filter above it
810814
query error Physical plan does not support logical expression Exists

0 commit comments

Comments
 (0)