@@ -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
109108impl 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 ( _)
0 commit comments