You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "princejain756 (via GitHub)" <gi...@apache.org> on 2026/10/24 04:36:52 UTC
[PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
princejain756 opened a new pull request, #26699:
URL: https://github.com/apache/datafusion/pull/26699
## Which issue does this PR close?
Closes #26692.
## Rationale for this change
`PullUpCorrelatedExpr` tracked per-node pulled-up state (`correlated_subquery_cols_map` and `collected_count_expr_map`) in `HashMap<LogicalPlan, ...>` keyed by the rewritten `LogicalPlan` value.
When a subquery contained two subtrees that became structurally equal after `Filter` removal (for example, one branch had its correlated filter stripped by `PullUpCorrelatedExpr::f_up` and the other branch was an identical unfiltered scan or alias), the second branch visited in bottom-up order overwrote the map entry of the first branch with an empty `BTreeSet` (or `None`). Additionally, `decorrelate_lateral_join` read only the top entry of `correlated_subquery_cols_map.values().last()` rather than the union of correlated columns across the subquery.
## What changes are included in this PR?
1. Replace `correlated_subquery_cols_map: HashMap<LogicalPlan, BTreeSet<Column>>` and `collected_count_expr_map: HashMap<LogicalPlan, ExprResultMap>` on `PullUpCorrelatedExpr` with a tree-frame stack (`pulled_up_frames: Vec<PullUpFrame>`) pushed in `f_down` and popped in `f_up`, alongside accumulated `correlated_subquery_cols: BTreeSet<Column>` and root `collected_count_expr_map: Option<ExprResultMap>`.
2. Recompute the schema of pass-through multi-input or unary operators (`Join`, `AsOfJoin`, `Distinct`, `Repartition`) in `f_up` when correlated columns are added to their children.
3. Update `scalar_subquery_to_join`, `decorrelate_predicate_subquery`, and `decorrelate_lateral_join` to read `pull_up.correlated_subquery_cols` and `pull_up.collected_count_expr_map` directly.
## Are these changes tested?
Yes, added sqllogictest regression coverage in `subquery.slt` covering `EXISTS`, scalar `count(*)` subqueries, and `CROSS JOIN LATERAL` with duplicate subplans.
## Are there any user-facing changes?
Bug fix only; correlated subqueries containing equal subplans now produce the right results instead of dropping the correlation predicate or failing with a schema error.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "princejain756 (via GitHub)" <gi...@apache.org>.
princejain756 commented on PR #26699:
URL: https://github.com/apache/datafusion/pull/26699#issuecomment-6393339637
Thanks for the review and for catching the `Join` above a pulled-up groupless scalar aggregate case, @jayzhan211! Addressed in 320f268:
1. Stopped pull-up (`self.can_pull_up = false` + `TreeNodeRecursion::Stop`) at `LogicalPlan::Join(_)` and `LogicalPlan::AsOfJoin(_)` when `self.pulled_up_scalar_agg` is set, and added the 3 `EXISTS` / `IN` test cases to `subquery.slt`.
2. Updated the `subquery.slt` regression block to test the outer-shadowed `t2 AS s` `EXISTS` query and the `SELECT b` `CROSS JOIN LATERAL` query from #26692 directly.
3. Added `#[deprecated(since = "56.0.0", ...)]` to `correlated_subquery_cols_map` and `collected_count_expr_map` (with `#[expect(deprecated)]` on internal writes) and updated the doc comment on `collected_count_expr_map`.
4. Replaced `self.pulled_up_frames.pop().unwrap_or_default()` with an `internal_err!` check.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #26699:
URL: https://github.com/apache/datafusion/pull/26699#issuecomment-6393346598
<!-- semver-check-comment -->
Thank you for opening this pull request!
Reviewer note: [cargo-semver-checks](https://github.com/obi1kenobi/cargo-semver-checks) reported the current version number is not SemVer-compatible with the changes in this pull request (compared against the base branch).
<details>
<summary>Details</summary>
```
Cloning c61fb09ac123d669382287ceb7b8f36267fc4711
Building datafusion-optimizer v55.1.0 (current)
Built [ 32.882s] (current)
Parsing datafusion-optimizer v55.1.0 (current)
Parsed [ 0.036s] (current)
Building datafusion-optimizer v55.1.0 (baseline)
Built [ 7.819s] (baseline)
Parsing datafusion-optimizer v55.1.0 (baseline)
Parsed [ 0.037s] (baseline)
Checking datafusion-optimizer v55.1.0 -> v55.1.0 (no change; assume patch)
Checked [ 0.179s] 229 checks: 228 pass, 1 fail, 0 warn, 31 skip
--- failure struct_field_marked_deprecated: pub struct field is now #[deprecated] ---
Description:
A pub field of a pub struct is now marked #[deprecated]. Downstream crates will get a compiler warning when accessing this field.
ref: https://doc.rust-lang.org/reference/attributes/diagnostics.html#the-deprecated-attribute
impl: https://github.com/obi1kenobi/cargo-semver-checks/tree/v0.51.0/src/lints/struct_field_marked_deprecated.ron
Failed in:
field PullUpCorrelatedExpr.correlated_subquery_cols_map in file /home/runner/work/datafusion/datafusion/datafusion/optimizer/src/decorrelate.rs:53
field PullUpCorrelatedExpr.collected_count_expr_map in file /home/runner/work/datafusion/datafusion/datafusion/optimizer/src/decorrelate.rs:53
Summary semver requires new minor version: 0 major and 1 minor checks failed
Finished [ 41.936s] datafusion-optimizer
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26699:
URL: https://github.com/apache/datafusion/pull/26699#discussion_r4369529007
##########
datafusion/optimizer/src/decorrelate.rs:
##########
@@ -742,19 +741,49 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
// `GROUP BY` below returns a row for an outer row without
// a match, which the pulled up filter would drop.
if self.can_extend_partition_by && !self.pulled_up_scalar_agg {
- let extended =
- partition_window_by(window, &local_correlated_cols)?;
- return self.pass_through_pulled_up_cols(extended);
+ partition_window_by(window, &local_correlated_cols)?
+ } else {
+ self.can_pull_up = false;
+ plan
}
- self.can_pull_up = false;
- }
- self.pass_through_pulled_up_cols(plan)
+ } else {
+ plan
+ };
+ let transformed = self
+ .pass_through_pulled_up_cols(plan, input_count_expr_map.is_some())?;
+ (transformed, local_correlated_cols, None)
}
// `f_down` checked that the pulled up filters do not read an
// unnested column.
- LogicalPlan::Unnest(_) => self.pass_through_pulled_up_cols(plan),
- _ => Ok(Transformed::no(plan)),
+ LogicalPlan::Unnest(_)
Review Comment:
Recomputing the Join schema here lets the uncompensated EXISTS/IN fallback (`rewrite(false)` in `build_join`) get past a Join that sits above a pulled-up groupless aggregate. Before this PR that path failed with a schema error; now it returns wrong rows:
```sql
CREATE TABLE t(a INT, b INT) AS VALUES (1,1),(2,2);
CREATE TABLE t2(a INT, b INT) AS VALUES (1,1),(3,30);
CREATE TABLE t3(c INT) AS VALUES (10),(20);
-- returns 1, expected 1, 2 (count(*) gives a row for every t row)
SELECT t.a FROM t WHERE EXISTS (SELECT 1 FROM (SELECT count(*) AS c FROM t2 WHERE t2.a = t.a) x CROSS JOIN t3);
-- returns nothing, expected 2
SELECT t.a FROM t WHERE EXISTS (SELECT 1 FROM (SELECT count(*) AS c FROM t2 WHERE t2.a = t.a) x CROSS JOIN t3 WHERE x.c = 0);
-- returns nothing, expected 2
SELECT t.a FROM t WHERE t.a IN (SELECT x.c + 2 FROM (SELECT count(*) AS c FROM t2 WHERE t2.a = t.a) x CROSS JOIN t3);
```
Stopping at a Join above a pulled-up scalar aggregate puts these back to "not supported" for me, and the subquery slt files still pass. Could you add this arm and the three queries above as tests?
```rs
LogicalPlan::Join(_) | LogicalPlan::AsOfJoin(_) if self.pulled_up_scalar_agg => {
self.can_pull_up = false;
return Ok(Transformed::new(plan, false, TreeNodeRecursion::Stop));
}
```
##########
datafusion/optimizer/src/decorrelate.rs:
##########
@@ -52,7 +52,13 @@ use datafusion_expr::{
#[derive(Debug)]
pub struct PullUpCorrelatedExpr {
pub join_filters: Vec<Expr>,
- /// mapping from the plan to its holding correlated columns
+ /// Correlated inner columns collected across the subquery, including their
+ /// re-qualified names after passing through [`LogicalPlan::SubqueryAlias`].
+ pub correlated_subquery_cols: BTreeSet<Column>,
+ /// Deprecated: use [`Self::correlated_subquery_cols`] instead.
Review Comment:
nit: could the two kept maps use `#[deprecated(since = "56.0.0", note = "use `correlated_subquery_cols` / `root_count_expr_map`")]` instead of a doc note, so downstream users get a compiler warning? The internal writes would then need `#[expect(deprecated)]`. The doc on `collected_count_expr_map` also still says it maps each plan, but it now holds only the root entry.
##########
datafusion/sqllogictest/test_files/subquery.slt:
##########
@@ -4215,3 +4215,51 @@ SELECT * FROM (VALUES (1)) AS x(d)
WHERE x.d IN (SELECT t.c FROM (SELECT * FROM (VALUES (1)) AS y(c) WHERE y.c = x.d) AS t WHERE x.d > 0);
----
1
+
+# Regression test for #26692: decorrelation must not lose correlated columns
+# when a subquery contains two structurally equal subplans.
+statement ok
+CREATE TABLE sq_dup_t(a INT);
+
+statement ok
+CREATE TABLE sq_dup_t2(a INT);
+
+statement ok
+INSERT INTO sq_dup_t VALUES (1), (2), (3);
+
+statement ok
+INSERT INTO sq_dup_t2 VALUES (1), (2);
+
+query I rowsort
+SELECT a FROM sq_dup_t WHERE EXISTS (
+ SELECT 1 FROM (SELECT s.a AS x FROM sq_dup_t2 AS s WHERE s.a = sq_dup_t.a)
+ CROSS JOIN (SELECT s.a AS y FROM sq_dup_t2 AS s)
+);
+----
+1
+2
+
+query I rowsort
+SELECT (
+ SELECT count(*) FROM (SELECT * FROM sq_dup_t2 WHERE sq_dup_t2.a = sq_dup_t.a) AS s1
+ CROSS JOIN (SELECT * FROM sq_dup_t2) AS s2
+) FROM sq_dup_t;
+----
+0
+2
+2
+
+query I rowsort
+SELECT a FROM sq_dup_t WHERE EXISTS (
+ SELECT 1 FROM (SELECT sq_dup_t2.a FROM sq_dup_t2 WHERE sq_dup_t2.a = sq_dup_t.a) AS x
+ CROSS JOIN LATERAL (SELECT sq_dup_t2.a FROM sq_dup_t2 WHERE sq_dup_t2.a = x.a) AS l
Review Comment:
This LATERAL query already passes on main, so it doesn't cover the third case from #26692. The wrong-rows case, where an outer `t2 AS s` shadows the inner alias, isn't tested either. Could you add both from the issue as written? It's fine to do in a follow-up if you'd rather.
```sql
SELECT t.a FROM t, t2 AS s
WHERE EXISTS (SELECT 1 FROM (SELECT * FROM t2 AS s WHERE s.a = t.a) x CROSS JOIN t2 AS s);
-- expected: 1, 1
SELECT t.a FROM t
WHERE EXISTS (
SELECT 1 FROM (SELECT a FROM t2 WHERE t2.a = t.a) x
CROSS JOIN LATERAL (SELECT b FROM t2 WHERE t2.b = x.a) l
);
-- expected: 1
```
##########
datafusion/optimizer/src/decorrelate.rs:
##########
@@ -383,9 +408,14 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
}
fn f_up(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
- // Pop this node's own entry, pushed by the matching `f_down` call, so
- // `column_refs_above` holds only the nodes strictly above `plan`.
+ // Pop this node's own entries, pushed by the matching `f_down` call, so
+ // `column_refs_above` holds only the nodes strictly above `plan` and
+ // `frame` holds the state pulled up from `plan`'s children.
self.column_refs_above.pop();
+ let PullUpFrame {
+ correlated_cols: local_correlated_cols,
+ count_expr_map: input_count_expr_map,
+ } = self.pulled_up_frames.pop().unwrap_or_default();
Review Comment:
nit: `unwrap_or_default()` hides a push/pop mismatch between `f_down` and `f_up`, which is easy to introduce in an arm like the `Limit` one. Could this return an internal error instead?
```rs
let Some(frame) = self.pulled_up_frames.pop() else {
return internal_err!("PullUpCorrelatedExpr: f_up without a matching f_down frame");
};
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #26699:
URL: https://github.com/apache/datafusion/pull/26699#issuecomment-6531624379
Let's shoot for error instead of this fix
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #26699:
URL: https://github.com/apache/datafusion/pull/26699#issuecomment-6379946136
<!-- semver-check-comment -->
Thank you for opening this pull request!
Reviewer note: [cargo-semver-checks](https://github.com/obi1kenobi/cargo-semver-checks) reported the current version number is not SemVer-compatible with the changes in this pull request (compared against the base branch).
<details>
<summary>Details</summary>
```
Cloning 836b4dda4fb265c07c7060b1f3d341cd209ea6a4
Building datafusion-optimizer v55.1.0 (current)
Built [ 32.051s] (current)
Parsing datafusion-optimizer v55.1.0 (current)
Parsed [ 0.029s] (current)
Building datafusion-optimizer v55.1.0 (baseline)
Built [ 6.733s] (baseline)
Parsing datafusion-optimizer v55.1.0 (baseline)
Parsed [ 0.029s] (baseline)
Checking datafusion-optimizer v55.1.0 -> v55.1.0 (no change; assume patch)
Checked [ 0.134s] 229 checks: 228 pass, 1 fail, 0 warn, 31 skip
--- failure struct_pub_field_missing: pub struct's pub field removed or renamed ---
Description:
A publicly-visible struct has at least one public field that is no longer available under its prior name. It may have been renamed or removed entirely.
ref: https://doc.rust-lang.org/cargo/reference/semver.html#item-remove
impl: https://github.com/obi1kenobi/cargo-semver-checks/tree/v0.51.0/src/lints/struct_pub_field_missing.ron
Failed in:
field correlated_subquery_cols_map of struct PullUpCorrelatedExpr, previously in file /home/runner/work/datafusion/datafusion/target/semver-checks-shared/semver-checks/git-836b4dda4fb265c07c7060b1f3d341cd209ea6a4/47d7d5789832a19151fcbc5ed8cee808ff7451ef/datafusion/optimizer/src/decorrelate.rs:56
Summary semver requires new major version: 1 major and 0 minor checks failed
Finished [ 40.641s] datafusion-optimizer
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #26699:
URL: https://github.com/apache/datafusion/pull/26699#issuecomment-6479164903
I am worried about the complexity of this PR and that it may introduce new error.
When fixing this bug, I think we should make the query error rather than trying to make it work / give correct results. To make it work and have confidence it will be correct, I think we need a more general approach than patches. See here for details
- https://github.com/apache/datafusion/issues/5492#issuecomment-6479090126
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #26699:
URL: https://github.com/apache/datafusion/pull/26699#issuecomment-6479188956
Thnk you for trying to help @princejain756 and thank you for the reviw @jayzhan211
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix(optimizer): propagate pulled-up correlated state along tree frames [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed pull request #26699: fix(optimizer): propagate pulled-up correlated state along tree frames
URL: https://github.com/apache/datafusion/pull/26699
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org