You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "skyzh (via GitHub)" <gi...@apache.org> on 2025/02/11 01:08:56 UTC
[PR] support simple lateral joins [datafusion]
skyzh opened a new pull request, #14595:
URL: https://github.com/apache/datafusion/pull/14595
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
- part of https://github.com/apache/datafusion/issues/10048
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
Add partial lateral join support.
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
The lateral join logical plan is like:
```
CrossJoin
Left
Right (with outer column reference)
```
We added a new rule `DecorrelateLateralJoin` to handle this case. We reuse the scalar/predicate subquery handling code for decorrelating lateral joins.
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
New test case in sqllogictest.
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
Some lateral joins are now supported. Note that we still have some of them in `joins.slt` that cannot be planned, and can be fixed gradually.
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2661667504
The current one-pass subquery unnesting implementation in `PullUpCorrelatedExpr` does not handle cases such as when we have joins in subqueries:
```sql
SELECT * FROM t0, LATERAL (SELECT 1), LATERAL (SELECT * FROM t1 WHERE t0.v0 = t1.v0);
```
Just note it down here and we can improve it in the future. We could implement a rule-based unnesting to push down the lateral join operator.
--
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] support simple/cross lateral joins [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2825977774
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days.
--
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] support simple/cross lateral joins [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2848475409
@skyzh Hi, I address the comment mentioned above in https://github.com/skyzh/datafusion/pull/1, if looks good to you we can merge this PR.
--
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] support simple/cross lateral joins [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#discussion_r1953460041
##########
datafusion/optimizer/src/decorrelate_lateral_join.rs:
##########
@@ -0,0 +1,106 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! [`DecorrelateLateralJoin`] decorrelates logical plans produced by lateral joins.
+
+use crate::optimizer::ApplyOrder;
+use crate::{decorrelate_predicate_subquery, OptimizerConfig, OptimizerRule};
+
+use datafusion_common::tree_node::{Transformed, TreeNodeRecursion, TreeNodeVisitor};
+use datafusion_common::Result;
+use datafusion_expr::logical_plan::JoinType;
+use datafusion_expr::LogicalPlan;
+
+/// Optimizer rule for rewriting lateral joins to joins
+#[derive(Default, Debug)]
+pub struct DecorrelateLateralJoin {}
+
+impl DecorrelateLateralJoin {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self::default()
+ }
+}
+
+impl OptimizerRule for DecorrelateLateralJoin {
+ fn supports_rewrite(&self) -> bool {
+ true
+ }
+
+ fn rewrite(
+ &self,
+ plan: LogicalPlan,
+ config: &dyn OptimizerConfig,
+ ) -> Result<Transformed<LogicalPlan>> {
+ // Find cross joins with outer column references on the right side (i.e., the apply operator).
+ let LogicalPlan::Join(join) = &plan else {
+ return Ok(Transformed::no(plan));
+ };
+ if join.join_type != JoinType::Inner {
+ return Ok(Transformed::no(plan));
+ }
+ // TODO: this makes the rule to be quadratic to the number of nodes, in theory, we can build this property
Review Comment:
I believe you can cause `rewrite` to be called in a bottom up fashion by using:
https://docs.rs/datafusion/latest/datafusion/optimizer/trait.OptimizerRule.html#method.apply_order
Then you could maybe add a `contains_outer_reference` type flag to `DecorrelateLateralJoin`
##########
datafusion/optimizer/src/decorrelate_lateral_join.rs:
##########
@@ -0,0 +1,106 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! [`DecorrelateLateralJoin`] decorrelates logical plans produced by lateral joins.
+
+use crate::optimizer::ApplyOrder;
+use crate::{decorrelate_predicate_subquery, OptimizerConfig, OptimizerRule};
+
+use datafusion_common::tree_node::{Transformed, TreeNodeRecursion, TreeNodeVisitor};
+use datafusion_common::Result;
+use datafusion_expr::logical_plan::JoinType;
+use datafusion_expr::LogicalPlan;
+
+/// Optimizer rule for rewriting lateral joins to joins
+#[derive(Default, Debug)]
+pub struct DecorrelateLateralJoin {}
+
+impl DecorrelateLateralJoin {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self::default()
+ }
+}
+
+impl OptimizerRule for DecorrelateLateralJoin {
+ fn supports_rewrite(&self) -> bool {
+ true
+ }
+
+ fn rewrite(
+ &self,
+ plan: LogicalPlan,
+ config: &dyn OptimizerConfig,
+ ) -> Result<Transformed<LogicalPlan>> {
+ // Find cross joins with outer column references on the right side (i.e., the apply operator).
+ let LogicalPlan::Join(join) = &plan else {
+ return Ok(Transformed::no(plan));
+ };
+ if join.join_type != JoinType::Inner {
+ return Ok(Transformed::no(plan));
+ }
+ // TODO: this makes the rule to be quadratic to the number of nodes, in theory, we can build this property
+ // bottom-up.
+ if !plan_contains_outer_reference(&join.right) {
+ return Ok(Transformed::no(plan));
+ }
+ // The right side contains outer references, we need to decorrelate it.
+ let LogicalPlan::Subquery(subquery) = &*join.right else {
+ return Ok(Transformed::no(plan));
+ };
+ let alias = config.alias_generator();
+ let Some(new_plan) = decorrelate_predicate_subquery::build_join(
+ &join.left,
+ subquery.subquery.as_ref(),
+ None,
+ join.join_type,
+ alias.next("__lateral_sq"),
+ )?
+ else {
+ return Ok(Transformed::no(plan));
+ };
+ Ok(Transformed::new(new_plan, true, TreeNodeRecursion::Jump))
+ }
+
+ fn name(&self) -> &str {
+ "decorrelate_lateral_join"
+ }
+
+ fn apply_order(&self) -> Option<ApplyOrder> {
+ Some(ApplyOrder::TopDown)
+ }
+}
+
+fn plan_contains_outer_reference(plan: &LogicalPlan) -> bool {
+ struct Visitor {
+ contains: bool,
+ }
+ impl<'n> TreeNodeVisitor<'n> for Visitor {
+ type Node = LogicalPlan;
+ fn f_down(&mut self, plan: &'n LogicalPlan) -> Result<TreeNodeRecursion> {
+ if plan.contains_outer_reference() {
+ self.contains = true;
+ Ok(TreeNodeRecursion::Stop)
+ } else {
+ Ok(TreeNodeRecursion::Continue)
+ }
+ }
+ }
+ let mut visitor = Visitor { contains: false };
+ plan.visit_with_subqueries(&mut visitor).unwrap();
+ visitor.contains
Review Comment:
I think you can do this more simply using `apply_subqueries` as described here: https://datafusion.apache.org/library-user-guide/query-optimizer.html#recursively-walk-an-expression-tree
Something like (untested):
```rust
fn plan_contains_outer_reference(plan: &LogicalPlan) -> bool {
let mut contains = false;
plan.apply_subqueries(|plan| {
if plan.contains_outer_reference() {
self.contains = true;
Ok(TreeNodeRecursion::Stop)
} else {
Ok(TreeNodeRecursion::Continue)
}
}).unwrap();
contains
}
```
##########
datafusion/sqllogictest/test_files/join.slt.part:
##########
@@ -1312,3 +1312,85 @@ SELECT a+b*2,
statement ok
drop table t1;
+
+
+statement ok
+CREATE TABLE t1(v0 BIGINT, v1 BIGINT);
+
+statement ok
+CREATE TABLE t0(v0 BIGINT, v1 BIGINT);
+
+statement ok
Review Comment:
Thanks!
Could we please add some negative cases to these tests too such as:
1. When there are two subqueries
2. When the subqueries have no correlation
##########
datafusion/sqllogictest/test_files/join.slt.part:
##########
@@ -1312,3 +1312,85 @@ SELECT a+b*2,
statement ok
drop table t1;
+
+
+statement ok
+CREATE TABLE t1(v0 BIGINT, v1 BIGINT);
+
+statement ok
+CREATE TABLE t0(v0 BIGINT, v1 BIGINT);
+
+statement ok
+INSERT INTO t0(v0, v1) VALUES (1, 1), (1, 2), (3, 3);
+
+statement ok
+INSERT INTO t1(v0, v1) VALUES (1, 1), (3, 2), (3, 5);
+
+query TT
+explain SELECT *
+FROM t0,
+LATERAL (SELECT sum(v1) FROM t1 WHERE t0.v0 = t1.v0);
+----
+logical_plan
+01)Projection: t0.v0, t0.v1, sum(t1.v1)
+02)--Inner Join: t0.v0 = __lateral_sq_1.v0
+03)----TableScan: t0 projection=[v0, v1]
+04)----SubqueryAlias: __lateral_sq_1
+05)------Projection: sum(t1.v1), t1.v0
+06)--------Aggregate: groupBy=[[t1.v0]], aggr=[[sum(t1.v1)]]
+07)----------TableScan: t1 projection=[v0, v1]
+physical_plan
+01)ProjectionExec: expr=[v0@1 as v0, v1@2 as v1, sum(t1.v1)@0 as sum(t1.v1)]
Review Comment:
So the DuckDB plan has 2 joins in it (I don't know what a `RIGHT_DELIM_JOIN` is) but this plan has only one
```
D explain SELECT *
FROM t0,
LATERAL (SELECT sum(v1) FROM t1 WHERE t0.v0 = t1.v0);
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Physical Plan ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│ PROJECTION │
│ ──────────────────── │
│ v0 │
│ v1 │
│ sum(v1) │
│ │
│ ~3 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ RIGHT_DELIM_JOIN │
│ ──────────────────── │
│ Join Type: INNER │
│ │
│ Conditions: ├──────────────┐
│ v0 IS NOT DISTINCT FROM v0│ │
│ │ │
│ ~3 Rows │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ HASH_JOIN │
│ ──────────────────── ││ ──────────────────── │
│ t0 ││ Join Type: INNER │
│ ││ │
│ Projections: ││ Conditions: ├───────────────────────────────────────────┐
│ v0 ││ v0 IS NOT DISTINCT FROM v0│ │
│ v1 ││ │ │
│ ││ │ │
│ ~3 Rows ││ ~3 Rows │ │
└───────────────────────────┘└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐ ┌─────────────┴─────────────┐
│ PROJECTION │ │ DUMMY_SCAN │
│ ──────────────────── │ │ │
│ sum(v1) │ │ │
│ v0 │ │ │
│ │ │ │
│ ~1 Rows │ │ │
└─────────────┬─────────────┘ └───────────────────────────┘
┌─────────────┴─────────────┐
│ HASH_JOIN │
│ ──────────────────── │
│ Join Type: LEFT │
│ │
│ Conditions: ├──────────────┐
│ v0 IS NOT DISTINCT FROM #0│ │
│ │ │
│ ~1 Rows │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ DELIM_SCAN ││ PROJECTION │
│ ──────────────────── ││ ──────────────────── │
│ Delim Index: 1 ││__internal_decompress_integ│
│ ││ ral_bigint(#0, 1) │
│ ││ #1 │
│ ││ │
│ ~1 Rows ││ ~0 Rows │
└───────────────────────────┘└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PERFECT_HASH_GROUP_BY │
│ ──────────────────── │
│ Groups: #0 │
│ │
│ Aggregates: │
│ sum_no_overflow(#1) │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PROJECTION │
│ ──────────────────── │
│ v0 │
│ v1 │
│ │
│ ~3 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PROJECTION │
│ ──────────────────── │
│__internal_compress_integra│
│ l_utinyint(#0, 1) │
│ #1 │
│ │
│ ~3 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ SEQ_SCAN │
│ ──────────────────── │
│ t1 │
│ │
│ Projections: │
│ v0 │
│ v1 │
│ │
│ ~3 Rows │
└───────────────────────────┘
```
--
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] support simple/cross lateral joins [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2656160457
> So back to the semantics of the lateral join,
Thank you @skyzh -- this is an amazing description. THank you -- hopefully we can include that in the source code eventually once we work through this issue
Ideally in my mind when someone found the lateral join support in DataFusion they would also have enough background via comments / links to understand what was going on.
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on code in PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#discussion_r1957438517
##########
datafusion/sqllogictest/test_files/join.slt.part:
##########
@@ -1312,3 +1312,85 @@ SELECT a+b*2,
statement ok
drop table t1;
+
+
+statement ok
+CREATE TABLE t1(v0 BIGINT, v1 BIGINT);
+
+statement ok
+CREATE TABLE t0(v0 BIGINT, v1 BIGINT);
+
+statement ok
Review Comment:
only added (2) in https://github.com/apache/datafusion/pull/14595/commits/c353246262f264a06d433b5977994b5d468bad76, I have some test cases for (1) in the comments but I don't plan to support them right now.
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2652702195
should pass all sqllogictests :)
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2655639889
Okay, I just realized that the plan is not correct. I'll need to do more transformation to make it work :(
So back to the semantics of the lateral join,
```
SELECT *
FROM t0,
LATERAL (SELECT sum(v1) FROM t1 WHERE t0.v0 = t1.v0);
```
is basically saying that "for every row in t0, run the lateral query", which is equivalent to the following program:
```
for row in t0:
lateral_result = run_query(SELECT sum(v1) FROM t1 WHERE t0.v0 = t1.v0)
if lateral_result is not empty
output.append(row ++ lateral_result)
```
Note that sum will produce 1 row of null even when the right table doesn't contain any matching row.
The produced plan with this patch is:
```
Inner Join t0.v0 = t1.v0
Scan t0
Aggregate: groupBy=[[t1.v0]], aggr=[[sum(t1.v1)]]
Scan t1
```
If t0 = (0, 0), (1, 1) and t1 = (0, 0), the output should have 2 rows, while this plan will only produce 1 row.
The correct plan should be:
```
Left Outer Join t0.v0 = t1.v0
Scan t0
Aggregate: groupBy=[[t1.v0]], aggr=[[sum(t1.v1)]]
Scan t1
```
And aggregations like `count(*)` needs to be handled separately, which I already see some code on that in the codebase.
Back to the DuckDB plan. They are using the Hyper subquery unnesting. The idea of Hyper is that it will first eliminate duplicates on the join column. Therefore, in the case where the left table has a lot of duplicated rows, it only needs to compute the subquery once for all such rows. So what they are doing is that: eliminate the duplicates from the left table, then compute the subquery result, and finally join it back to the original one, which will be planned like:
```
^1:
Left Outer Join t0.v0 = t1.v0
DistinctScan/DelimScan t0
Aggregate: groupBy=[[t1.v0]], aggr=[[sum(t1.v1)]]
Scan t1
```
which computes the right side row for every value in the left table. We will get (distinct t0.*, sum(t1.v1)) at this step. And then, deduplicate the result of the subquery (this step seems unnecessary?)
```
^2:
Dedup (HashJoin)
^1
```
And finally, join the result back to the original table,
```
HashJoin
Scan t0
^2
```
The result should be the same as the corrected plan.
--
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] support simple/cross lateral joins [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#discussion_r1965506306
##########
datafusion/optimizer/src/decorrelate_lateral_join.rs:
##########
@@ -0,0 +1,106 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! [`DecorrelateLateralJoin`] decorrelates logical plans produced by lateral joins.
+
+use crate::optimizer::ApplyOrder;
+use crate::{decorrelate_predicate_subquery, OptimizerConfig, OptimizerRule};
+
+use datafusion_common::tree_node::{Transformed, TreeNodeRecursion, TreeNodeVisitor};
+use datafusion_common::Result;
+use datafusion_expr::logical_plan::JoinType;
+use datafusion_expr::LogicalPlan;
+
+/// Optimizer rule for rewriting lateral joins to joins
+#[derive(Default, Debug)]
+pub struct DecorrelateLateralJoin {}
+
+impl DecorrelateLateralJoin {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self::default()
+ }
+}
+
+impl OptimizerRule for DecorrelateLateralJoin {
+ fn supports_rewrite(&self) -> bool {
+ true
+ }
+
+ fn rewrite(
+ &self,
+ plan: LogicalPlan,
+ config: &dyn OptimizerConfig,
+ ) -> Result<Transformed<LogicalPlan>> {
+ // Find cross joins with outer column references on the right side (i.e., the apply operator).
+ let LogicalPlan::Join(join) = &plan else {
+ return Ok(Transformed::no(plan));
+ };
+ if join.join_type != JoinType::Inner {
+ return Ok(Transformed::no(plan));
+ }
+ // TODO: this makes the rule to be quadratic to the number of nodes, in theory, we can build this property
+ // bottom-up.
+ if !plan_contains_outer_reference(&join.right) {
+ return Ok(Transformed::no(plan));
+ }
+ // The right side contains outer references, we need to decorrelate it.
+ let LogicalPlan::Subquery(subquery) = &*join.right else {
+ return Ok(Transformed::no(plan));
+ };
+ let alias = config.alias_generator();
+ let Some(new_plan) = decorrelate_predicate_subquery::build_join(
+ &join.left,
+ subquery.subquery.as_ref(),
+ None,
+ join.join_type,
+ alias.next("__lateral_sq"),
+ )?
+ else {
+ return Ok(Transformed::no(plan));
+ };
+ Ok(Transformed::new(new_plan, true, TreeNodeRecursion::Jump))
+ }
+
+ fn name(&self) -> &str {
+ "decorrelate_lateral_join"
+ }
+
+ fn apply_order(&self) -> Option<ApplyOrder> {
+ Some(ApplyOrder::TopDown)
+ }
+}
+
+fn plan_contains_outer_reference(plan: &LogicalPlan) -> bool {
+ struct Visitor {
+ contains: bool,
+ }
+ impl<'n> TreeNodeVisitor<'n> for Visitor {
+ type Node = LogicalPlan;
+ fn f_down(&mut self, plan: &'n LogicalPlan) -> Result<TreeNodeRecursion> {
+ if plan.contains_outer_reference() {
+ self.contains = true;
+ Ok(TreeNodeRecursion::Stop)
+ } else {
+ Ok(TreeNodeRecursion::Continue)
+ }
+ }
+ }
+ let mut visitor = Visitor { contains: false };
+ plan.visit_with_subqueries(&mut visitor).unwrap();
+ visitor.contains
Review Comment:
You can use `apply_with_subqueries()`.
--
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] support simple lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2649598864
cc @alamb would you please help take a look as you were engaged on lateral join discussions before? Thanks :)
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on code in PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#discussion_r1957439224
##########
datafusion/optimizer/src/decorrelate_lateral_join.rs:
##########
@@ -0,0 +1,106 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! [`DecorrelateLateralJoin`] decorrelates logical plans produced by lateral joins.
+
+use crate::optimizer::ApplyOrder;
+use crate::{decorrelate_predicate_subquery, OptimizerConfig, OptimizerRule};
+
+use datafusion_common::tree_node::{Transformed, TreeNodeRecursion, TreeNodeVisitor};
+use datafusion_common::Result;
+use datafusion_expr::logical_plan::JoinType;
+use datafusion_expr::LogicalPlan;
+
+/// Optimizer rule for rewriting lateral joins to joins
+#[derive(Default, Debug)]
+pub struct DecorrelateLateralJoin {}
+
+impl DecorrelateLateralJoin {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self::default()
+ }
+}
+
+impl OptimizerRule for DecorrelateLateralJoin {
+ fn supports_rewrite(&self) -> bool {
+ true
+ }
+
+ fn rewrite(
+ &self,
+ plan: LogicalPlan,
+ config: &dyn OptimizerConfig,
+ ) -> Result<Transformed<LogicalPlan>> {
+ // Find cross joins with outer column references on the right side (i.e., the apply operator).
+ let LogicalPlan::Join(join) = &plan else {
+ return Ok(Transformed::no(plan));
+ };
+ if join.join_type != JoinType::Inner {
+ return Ok(Transformed::no(plan));
+ }
+ // TODO: this makes the rule to be quadratic to the number of nodes, in theory, we can build this property
Review Comment:
https://github.com/apache/datafusion/pull/14595/commits/24a375dc47d830eb0655bb6c4ec699a6b61a623a I decided to use `TreeNodeRecursion::Jump` to skip all children to make it O(n).
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2661668777
For multiple subqueries like:
```
SELECT * FROM t0, LATERAL (SELECT * FROM t1 WHERE t0.v0 = t1.v0 AND t1.v1 > (SELECT SUM(v1) FROM t2 WHERE t1.v0 = t2.v0));
```
I'm not planning to support it in this patch now as I don't think the current one-pass de-correlate process can handle it correctly without significant refactor :(
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on code in PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#discussion_r1957444892
##########
datafusion/optimizer/src/decorrelate_lateral_join.rs:
##########
@@ -0,0 +1,106 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! [`DecorrelateLateralJoin`] decorrelates logical plans produced by lateral joins.
+
+use crate::optimizer::ApplyOrder;
+use crate::{decorrelate_predicate_subquery, OptimizerConfig, OptimizerRule};
+
+use datafusion_common::tree_node::{Transformed, TreeNodeRecursion, TreeNodeVisitor};
+use datafusion_common::Result;
+use datafusion_expr::logical_plan::JoinType;
+use datafusion_expr::LogicalPlan;
+
+/// Optimizer rule for rewriting lateral joins to joins
+#[derive(Default, Debug)]
+pub struct DecorrelateLateralJoin {}
+
+impl DecorrelateLateralJoin {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self::default()
+ }
+}
+
+impl OptimizerRule for DecorrelateLateralJoin {
+ fn supports_rewrite(&self) -> bool {
+ true
+ }
+
+ fn rewrite(
+ &self,
+ plan: LogicalPlan,
+ config: &dyn OptimizerConfig,
+ ) -> Result<Transformed<LogicalPlan>> {
+ // Find cross joins with outer column references on the right side (i.e., the apply operator).
+ let LogicalPlan::Join(join) = &plan else {
+ return Ok(Transformed::no(plan));
+ };
+ if join.join_type != JoinType::Inner {
+ return Ok(Transformed::no(plan));
+ }
+ // TODO: this makes the rule to be quadratic to the number of nodes, in theory, we can build this property
+ // bottom-up.
+ if !plan_contains_outer_reference(&join.right) {
+ return Ok(Transformed::no(plan));
+ }
+ // The right side contains outer references, we need to decorrelate it.
+ let LogicalPlan::Subquery(subquery) = &*join.right else {
+ return Ok(Transformed::no(plan));
+ };
+ let alias = config.alias_generator();
+ let Some(new_plan) = decorrelate_predicate_subquery::build_join(
+ &join.left,
+ subquery.subquery.as_ref(),
+ None,
+ join.join_type,
+ alias.next("__lateral_sq"),
+ )?
+ else {
+ return Ok(Transformed::no(plan));
+ };
+ Ok(Transformed::new(new_plan, true, TreeNodeRecursion::Jump))
+ }
+
+ fn name(&self) -> &str {
+ "decorrelate_lateral_join"
+ }
+
+ fn apply_order(&self) -> Option<ApplyOrder> {
+ Some(ApplyOrder::TopDown)
+ }
+}
+
+fn plan_contains_outer_reference(plan: &LogicalPlan) -> bool {
+ struct Visitor {
+ contains: bool,
+ }
+ impl<'n> TreeNodeVisitor<'n> for Visitor {
+ type Node = LogicalPlan;
+ fn f_down(&mut self, plan: &'n LogicalPlan) -> Result<TreeNodeRecursion> {
+ if plan.contains_outer_reference() {
+ self.contains = true;
+ Ok(TreeNodeRecursion::Stop)
+ } else {
+ Ok(TreeNodeRecursion::Continue)
+ }
+ }
+ }
+ let mut visitor = Visitor { contains: false };
+ plan.visit_with_subqueries(&mut visitor).unwrap();
+ visitor.contains
Review Comment:
This is not equivalent to the current visitor unfortunately because `apply_subqueries` only visits the subqueries 🤣
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2661674964
And ready for review again :)
After trying understanding what's happening in `decorrelate.rs`, I think we need new code path to support a variety of logical plans produced by lateral joins. The key is that we should make the decorrelation code aware of the joins while de-correlating, instead of first gathering the information and then generate a join at the top.
If we are going towards making the optimizer able to unnest any subqueries and lateral joins, then we will likely have a meta rule that recursively apply the following rules top-down:
* Convert join operators into LogicalApply if the right side of the join contains outer column reference. This can also be done in the SQL->logical phase when we encounter a lateral join. For the correlated filter predicate and scalar subqueries (exists/in), we can also convert them into the apply operator in the future.
* Have a set of rules like: push down apply->join, push down apply->aggregation, push down apply->filter, etc.
* Apply these rules top-down until no outer column reference is in the plan tree.
We can either use the Hyper unnesting rules (we implemented it in CMU-DB's [optd](https://github.com/cmu-db/optd-original/blob/main/optd-datafusion-repr/src/rules/subquery/depjoin_pushdown.rs) optimizer) or the SQL server unnesting rules (which we've implemented in [risinglight](https://github.com/risinglightdb/risinglight/blob/f12ea232a502b1dbda37ddaa3e98c3b8d1e6439b/src/planner/rules/plan.rs#L204-L280)).
This meta unnesting rule is more powerful than what we have right now (decorrelate predicate subquery + scalar subquery unnesting rule) and we can eventually replace these two rules with the new meta unnesting rule in the future.
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2661671600
I think this patch will not regress existing supported cases as they get fully decorrelated with the scalar query rule and the predicate subquery rule. The patch unlocks a new set of plans produced by lateral joins, though it is possible that we could have missed some cases and generated incorrect plans for those newly-supported one. For queries that can be optimized into a physical plan: `count(*)` is not handled correctly. For queries they we know we don't support for now: as in the above comments.
--
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] support simple/cross lateral joins [datafusion]
Posted by "skyzh (via GitHub)" <gi...@apache.org>.
skyzh commented on PR #14595:
URL: https://github.com/apache/datafusion/pull/14595#issuecomment-2661676052
And FYI, the Hyper paper https://dl.gi.de/server/api/core/bitstreams/10f3ad20-e9ae-4876-abdf-5c8e83e4c595/content, and the SQL server paper https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2000-31.pdf
--
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] support simple/cross lateral joins [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #14595: support simple/cross lateral joins
URL: https://github.com/apache/datafusion/pull/14595
--
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