You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by GitBox <gi...@apache.org> on 2022/07/13 13:22:53 UTC
[GitHub] [doris] jackwener opened a new pull request, #10479: [feature](nereids): join reorder
jackwener opened a new pull request, #10479:
URL: https://github.com/apache/doris/pull/10479
# Proposed changes
Issue Number: close #xxx
## Problem Summary:
Enhance join reorder.
## Checklist(Required)
1. Does it affect the original behavior: (No)
2. Has unit tests been added: (No)
3. Has document been added or modified: (No Need)
4. Does it need to update dependencies: (No)
5. Are there any changes that cannot be rolled back: (No)
## Further comments
If this is a relatively large or complex change, kick off the discussion at [dev@doris.apache.org](mailto:dev@doris.apache.org) by explaining why you chose the solution you did and what alternatives you considered, etc...
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r920962460
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -38,14 +50,101 @@ public class JoinLAsscom extends OneExplorationRuleFactory {
@Override
public Rule<Plan> build() {
return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
+
LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
GroupPlan a = bottomJoin.left();
GroupPlan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ assert (optTopJoinOnClause.isPresent());
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ // TODO: empty onClause.
+ assert (optBottomJoinOnClause.isPresent());
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aSlots = a.collect(SlotReference.class::isInstance);
+ List<SlotReference> bSlots = b.collect(SlotReference.class::isInstance);
+ List<SlotReference> cSlots = c.collect(SlotReference.class::isInstance);
+
+ // Check whether lhs and rhs (both are List<SlotReference>>) are intersecting.
+ BiPredicate<List<SlotReference>, List<SlotReference>> isIntersecting = (lhs, rhs) -> {
+ for (SlotReference lSlot : lhs) {
+ for (SlotReference rSlot : rhs) {
+ // TODO: tmp judge intersecting
+ if (lSlot.getExprId() != rSlot.getExprId()) {
+ return false;
Review Comment:
It should be `==` instead of `!=`π
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] wangshuo128 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
wangshuo128 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r927581617
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/PushPredicateThroughJoin.java:
##########
@@ -42,28 +42,29 @@
/**
* Push the predicate in the LogicalFilter or LogicalJoin to the join children.
- * For example:
- * select a.k1,b.k1 from a join b on a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5 where a.k1 > 1 and b.k1 > 2
- * Logical plan tree:
- * project
- * |
- * filter (a.k1 > 1 and b.k1 > 2)
- * |
- * join (a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5)
- * / \
- * scan scan
- * transformed:
- * project
- * |
- * join (a.k1 = b.k1)
- * / \
- * filter(a.k1 > 1 and a.k2 > 2 ) filter(b.k1 > 2 and b.k2 > 5)
- * | |
- * scan scan
* todo: Now, only support eq on condition for inner join, support other case later
*/
public class PushPredicateThroughJoin extends OneRewriteRuleFactory {
-
+ /*
Review Comment:
Comments should be wrapped in HTML tag <pre></pre> to avoid indents changed.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] wangshuo128 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
wangshuo128 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r927581617
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/PushPredicateThroughJoin.java:
##########
@@ -42,28 +42,29 @@
/**
* Push the predicate in the LogicalFilter or LogicalJoin to the join children.
- * For example:
- * select a.k1,b.k1 from a join b on a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5 where a.k1 > 1 and b.k1 > 2
- * Logical plan tree:
- * project
- * |
- * filter (a.k1 > 1 and b.k1 > 2)
- * |
- * join (a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5)
- * / \
- * scan scan
- * transformed:
- * project
- * |
- * join (a.k1 = b.k1)
- * / \
- * filter(a.k1 > 1 and a.k2 > 2 ) filter(b.k1 > 2 and b.k2 > 5)
- * | |
- * scan scan
* todo: Now, only support eq on condition for inner join, support other case later
*/
public class PushPredicateThroughJoin extends OneRewriteRuleFactory {
-
+ /*
Review Comment:
Comments should be wrapped in HTML tag `<pre></pre>` to avoid indents changed.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] morrySnow commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
morrySnow commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r926206191
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinProjectLAsscom.java:
##########
@@ -0,0 +1,178 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
+
+/**
+ * Rule for change inner join left associative to right.
+ */
+public class JoinProjectLAsscom extends OneExplorationRuleFactory {
+ /*
+ * topJoin newTopJoin
+ * / \ / \
+ * project C newLeftProject newRightProject
+ * / βββΊ / \
+ * bottomJoin newBottomJoin B
+ * / \ / \
+ * A B A C
+ */
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(logicalProject(innerLogicalJoin(any(), any())), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
+
+ LogicalProject<LogicalJoin<Plan, Plan>> project = topJoin.left();
+ LogicalJoin<Plan, Plan> bottomJoin = project.child();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
+ Plan c = topJoin.right();
+
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> bOutputSlots = b.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> cOutputSlots = c.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+
+ // Ignore join with some OnClause like:
+ // Join C = B + A for above example.
+ List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(topJoinOnClause);
+ for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) {
+ if (Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ bOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ cOutputSlots)
+ ) {
+ return null;
+ }
+ }
+ List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(bottomJoinOnClause);
+
+ List<Expression> allOnCondition = Lists.newArrayList();
+ allOnCondition.addAll(topJoinOnClauseConjuncts);
+ allOnCondition.addAll(bottomJoinOnClauseConjuncts);
+
+ List<SlotReference> newBottomJoinSlots = Lists.newArrayList();
+ newBottomJoinSlots.addAll(aOutputSlots);
+ newBottomJoinSlots.addAll(cOutputSlots);
+
+ List<Expression> newBottomJoinOnCondition = Lists.newArrayList();
+ List<Expression> newTopJoinOnCondition = Lists.newArrayList();
+ for (Expression onCondition : allOnCondition) {
+ List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance);
+ if (Utils.containsAll(newBottomJoinSlots, slots)) {
+ newBottomJoinOnCondition.add(onCondition);
+ } else {
+ newTopJoinOnCondition.add(onCondition);
+ }
+ }
+
+ // newBottomJoinOnCondition/newTopJoinOnCondition is empty. They are cross join.
+ // Example:
+ // A: col1, col2. B: col2, col3. C: col3, col4
+ // (A & B on A.col2=B.col2) & C on B.col3=C.col3.
+ // If (A & B) & C -> (A & C) & B.
+ // (A & C) will be cross join (newBottomJoinOnCondition is empty)
+ if (newBottomJoinOnCondition.isEmpty() || newTopJoinOnCondition.isEmpty()) {
+ return null;
+ }
+
+ Plan newBottomJoin = new LogicalJoin(
+ bottomJoin.getJoinType(),
+ Optional.of(ExpressionUtils.and(newBottomJoinOnCondition)),
+ a, c);
+
+ // Handle project.
+ // TODO: split project into right child(b) and newRightProject.
+ List<NamedExpression> projectExprs = project.getProjects();
+ List<NamedExpression> newRightProjectExprs = Lists.newArrayList();
+ List<NamedExpression> newLeftProjectExpr = Lists.newArrayList();
+ for (NamedExpression projectExpr : projectExprs) {
+ List<SlotReference> usedSlotRefs = projectExpr.collect(SlotReference.class::isInstance);
+ if (Utils.containsAll(bOutputSlots, usedSlotRefs)) {
+ newRightProjectExprs.add(projectExpr);
+ } else {
+ newLeftProjectExpr.add(projectExpr);
+ }
+ }
+
+ // project include b, add project for right.
+ if (newRightProjectExprs.size() != 0) {
Review Comment:
need to mod join order context
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] wangshuo128 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
wangshuo128 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r927227488
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
Review Comment:
I meant to use a clear name, `LAsscom` is hard to understand.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925388681
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> bOutputSlots = b.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> cOutputSlots = c.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+
+ // Ignore join with some OnClause like:
+ // Join C = B + A for above example.
+ List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(topJoinOnClause);
+ for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) {
+ if (Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ bOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ cOutputSlots)
+ ) {
+ return null;
+ }
+ }
+ List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(bottomJoinOnClause);
+
+ List<Expression> allOnCondition = Lists.newArrayList();
+ allOnCondition.addAll(topJoinOnClauseConjuncts);
+ allOnCondition.addAll(bottomJoinOnClauseConjuncts);
+
+ List<SlotReference> newBottomJoinSlots = Lists.newArrayList();
+ newBottomJoinSlots.addAll(aOutputSlots);
+ newBottomJoinSlots.addAll(cOutputSlots);
+
+ List<Expression> newBottomJoinOnCondition = Lists.newArrayList();
Review Comment:
For chain-join, the explanation exist in UT `testChainJoinLAsscom`
LAsscom shouldn't reorder `a.id = b.id and b.id = c.id` directly.
Instead,
A -- B -- C
commute ->
A -- C
|
B
LAsscom should apply result after `commute` instead of directly apply it by `infer onCondition`.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] 924060929 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
924060929 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925446907
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> bOutputSlots = b.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> cOutputSlots = c.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+
+ // Ignore join with some OnClause like:
+ // Join C = B + A for above example.
+ List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(topJoinOnClause);
+ for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) {
+ if (Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ bOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ cOutputSlots)
+ ) {
+ return null;
+ }
+ }
+ List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(bottomJoinOnClause);
+
+ List<Expression> allOnCondition = Lists.newArrayList();
+ allOnCondition.addAll(topJoinOnClauseConjuncts);
+ allOnCondition.addAll(bottomJoinOnClauseConjuncts);
+
+ List<SlotReference> newBottomJoinSlots = Lists.newArrayList();
+ newBottomJoinSlots.addAll(aOutputSlots);
+ newBottomJoinSlots.addAll(cOutputSlots);
+
+ List<Expression> newBottomJoinOnCondition = Lists.newArrayList();
Review Comment:
ok
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] 924060929 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
924060929 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925327364
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
Review Comment:
output maybe Alias?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left(),
+ join.getJoinReorderContext()
+ );
+ newJoin.getJoinReorderContext().setHasCommute(true);
+ if (swapType == SwapType.ZIG_ZAG && !isBottomJoin) {
+ newJoin.getJoinReorderContext().setHasCommuteZigZag(true);
+ }
+
+ return newJoin;
+ }).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ }
+
+
+ private boolean check(LogicalJoin join) {
+ if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean isBottomJoin(LogicalJoin join) {
Review Comment:
rename to childrenHasJoin, and return flip boolean result
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> bOutputSlots = b.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> cOutputSlots = c.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+
+ // Ignore join with some OnClause like:
+ // Join C = B + A for above example.
+ List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(topJoinOnClause);
+ for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) {
+ if (Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ bOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ cOutputSlots)
+ ) {
+ return null;
+ }
+ }
+ List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(bottomJoinOnClause);
+
+ List<Expression> allOnCondition = Lists.newArrayList();
+ allOnCondition.addAll(topJoinOnClauseConjuncts);
+ allOnCondition.addAll(bottomJoinOnClauseConjuncts);
+
+ List<SlotReference> newBottomJoinSlots = Lists.newArrayList();
+ newBottomJoinSlots.addAll(aOutputSlots);
+ newBottomJoinSlots.addAll(cOutputSlots);
+
+ List<Expression> newBottomJoinOnCondition = Lists.newArrayList();
Review Comment:
if the join condition is `a.id = b.id and b.id = c.id`, we should generate `a.id = c.id` here?
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] EmmyMiao87 closed pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
EmmyMiao87 closed pull request #10479: [feature](nereids): join reorder
URL: https://github.com/apache/doris/pull/10479
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r920957774
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommutative.java:
##########
@@ -50,11 +51,54 @@ enum SwapType {
@Override
public Rule<Plan> build() {
- return innerLogicalJoin().then(join -> new LogicalJoin(
- join.getJoinType().swap(),
- join.getCondition(),
- join.right(),
- join.left())
- ).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ return innerLogicalJoin().then(join -> {
+ if (check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left()
+ );
+ newJoin.getJoinReorderContext().copyFrom(join.getJoinReorderContext());
+ newJoin.getJoinReorderContext().setHasCommute(true);
+ if (swapType == SwapType.ZIG_ZAG && !isBottomJoin) {
+ newJoin.getJoinReorderContext().setHasCommuteZigZag(true);
+ }
+
+ return newJoin;
+ }).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ }
+
+
+ private boolean check(LogicalJoin join) {
+ if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean isBottomJoin(LogicalJoin join) {
+ if (join.left() instanceof LogicalProject) {
Review Comment:
Greatπ
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r920969169
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommutative.java:
##########
@@ -50,11 +51,54 @@ enum SwapType {
@Override
public Rule<Plan> build() {
- return innerLogicalJoin().then(join -> new LogicalJoin(
- join.getJoinType().swap(),
- join.getCondition(),
- join.right(),
- join.left())
- ).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ return innerLogicalJoin().then(join -> {
+ if (check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left()
+ );
+ newJoin.getJoinReorderContext().copyFrom(join.getJoinReorderContext());
Review Comment:
JoinReorderContext is mutable.
Has added it into constructor
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r926200131
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/PushPredicateThroughJoin.java:
##########
@@ -42,28 +42,29 @@
/**
* Push the predicate in the LogicalFilter or LogicalJoin to the join children.
- * For example:
- * select a.k1,b.k1 from a join b on a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5 where a.k1 > 1 and b.k1 > 2
- * Logical plan tree:
- * project
- * |
- * filter (a.k1 > 1 and b.k1 > 2)
- * |
- * join (a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5)
- * / \
- * scan scan
- * transformed:
- * project
- * |
- * join (a.k1 = b.k1)
- * / \
- * filter(a.k1 > 1 and a.k2 > 2 ) filter(b.k1 > 2 and b.k2 > 5)
- * | |
- * scan scan
* todo: Now, only support eq on condition for inner join, support other case later
*/
public class PushPredicateThroughJoin extends OneRewriteRuleFactory {
-
+ /*
Review Comment:
Javadoc will format indentation automatically.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r927233396
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
Review Comment:
Annotation is already enough.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] 924060929 merged pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
924060929 merged PR #10479:
URL: https://github.com/apache/doris/pull/10479
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] wangshuo128 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
wangshuo128 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r927227488
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
Review Comment:
I meant to use a clear name, `LAsscom` is hard to understand.
IIUC, `LAsscom` could be renamed to `LeftAssociateAndCommute`?
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r920968243
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -38,14 +50,101 @@ public class JoinLAsscom extends OneExplorationRuleFactory {
@Override
public Rule<Plan> build() {
return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
+
LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
GroupPlan a = bottomJoin.left();
GroupPlan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ assert (optTopJoinOnClause.isPresent());
Review Comment:
use preconditon.assert()
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommutative.java:
##########
@@ -50,11 +51,54 @@ enum SwapType {
@Override
public Rule<Plan> build() {
- return innerLogicalJoin().then(join -> new LogicalJoin(
- join.getJoinType().swap(),
- join.getCondition(),
- join.right(),
- join.left())
- ).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ return innerLogicalJoin().then(join -> {
+ if (check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left()
+ );
+ newJoin.getJoinReorderContext().copyFrom(join.getJoinReorderContext());
+ newJoin.getJoinReorderContext().setHasCommute(true);
+ if (swapType == SwapType.ZIG_ZAG && !isBottomJoin) {
+ newJoin.getJoinReorderContext().setHasCommuteZigZag(true);
+ }
+
+ return newJoin;
+ }).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ }
+
+
+ private boolean check(LogicalJoin join) {
+ if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean isBottomJoin(LogicalJoin join) {
+ if (join.left() instanceof LogicalProject) {
Review Comment:
Add TODO
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] morrySnow commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
morrySnow commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925889535
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left(),
+ join.getJoinReorderContext()
+ );
+ newJoin.getJoinReorderContext().setHasCommute(true);
Review Comment:
could we use copyWith or a Builder inside oinReorderContext to set all attribute in oinReorderContext with final?
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r927225768
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
Review Comment:
It's from paper.
LAsscom is (commute + asscom) instead of associative,
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] wangshuo128 commented on pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
wangshuo128 commented on PR #10479:
URL: https://github.com/apache/doris/pull/10479#issuecomment-1192090727
Please add `@Developing` once #11077 merged.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925393492
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
Review Comment:
Slot just inherit by `UnboundSlot` and `SlotReference`
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] morrySnow commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
morrySnow commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925873343
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLeftAssociate.java:
##########
@@ -26,7 +26,7 @@
/**
* Rule factory for change inner join left associative to right.
*/
-public class JoinLeftAssociative extends OneExplorationRuleFactory {
+public class JoinLeftAssociate extends OneExplorationRuleFactory {
Review Comment:
why set two new join's condition to root.getCondition()?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
Review Comment:
check could be replaced by when?
```java
innerLogicalJoin().when(join -> {
if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
return false;
}
return true;
} ).
```
##########
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomTest.java:
##########
@@ -0,0 +1,152 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.catalog.AggregateType;
+import org.apache.doris.catalog.Column;
+import org.apache.doris.catalog.Table;
+import org.apache.doris.catalog.Type;
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.PlannerContext;
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.plans.JoinType;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
+import org.apache.doris.nereids.types.IntegerType;
+import org.apache.doris.nereids.types.StringType;
+
+import com.google.common.collect.ImmutableList;
+import mockit.Mocked;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.List;
+import java.util.Optional;
+
+public class JoinLAsscomTest {
+ public Pair<LogicalJoin, LogicalJoin> testJoinLAsscom(PlannerContext plannerContext,
+ Expression bottomJoinOnCondition, Expression topJoinOnCondition) {
+ /*
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
+ */
+ Table t1 = new Table(0L, "t1", Table.TableType.OLAP,
+ ImmutableList.of(new Column("id", Type.INT, true, AggregateType.NONE, "0", ""),
+ new Column("name", Type.STRING, true, AggregateType.NONE, "0", "")));
+ LogicalOlapScan scan1 = new LogicalOlapScan(t1, ImmutableList.of());
+
+ Table t2 = new Table(0L, "t2", Table.TableType.OLAP,
+ ImmutableList.of(new Column("id", Type.INT, true, AggregateType.NONE, "0", ""),
+ new Column("name", Type.STRING, true, AggregateType.NONE, "0", "")));
+ LogicalOlapScan scan2 = new LogicalOlapScan(t2, ImmutableList.of());
+
+ Table t3 = new Table(0L, "t3", Table.TableType.OLAP,
+ ImmutableList.of(new Column("id", Type.INT, true, AggregateType.NONE, "0", ""),
+ new Column("name", Type.STRING, true, AggregateType.NONE, "0", "")));
+ LogicalOlapScan scan3 = new LogicalOlapScan(t3, ImmutableList.of());
+
+ LogicalJoin<LogicalOlapScan, LogicalOlapScan> bottomJoin = new LogicalJoin<>(JoinType.INNER_JOIN,
+ Optional.of(bottomJoinOnCondition), scan1, scan2);
+ LogicalJoin<LogicalJoin<LogicalOlapScan, LogicalOlapScan>, LogicalOlapScan> topJoin = new LogicalJoin<>(
+ JoinType.INNER_JOIN, Optional.of(topJoinOnCondition), bottomJoin, scan3);
+
+ Rule rule = new JoinLAsscom().build();
+ List<Plan> transform = rule.transform(topJoin, plannerContext);
+ Assert.assertEquals(1, transform.size());
+ Assert.assertTrue(transform.get(0) instanceof LogicalJoin);
+ LogicalJoin newTopJoin = (LogicalJoin) transform.get(0);
+ return new Pair<>(topJoin, newTopJoin);
+ }
+
+ @Test
+ public void testStarJoinLAsscom(@Mocked PlannerContext plannerContext) {
+ /*
+ * Star-Join
+ * t1 -- t2
+ * |
+ * t3
+ * <p>
+ * t1.id=t3.id t1.id=t2.id
+ * topJoin newTopJoin
+ * / \ / \
+ * t1.id=t2.id t3 t1.id=t3.id t2
+ * bottomJoin --> newBottomJoin
+ * / \ / \
+ * t1 t2 t1 t3
+ */
+ Expression bottomJoinOnCondition = new EqualTo(
Review Comment:
u should set ExprId manually to ensure same SlotReference in child output and join Condition has the same ID. In real world this is always true.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/Utils.java:
##########
@@ -51,4 +53,43 @@ public static List<String> qualifiedNameParts(List<String> qualifier, String nam
public static String qualifiedName(List<String> qualifier, String name) {
return StringUtils.join(qualifiedNameParts(qualifier, name), ".");
}
+
+
+ /**
+ * Check whether lhs and rhs (both are List of SlotReference) are intersecting.
+ */
+ public static boolean isIntersecting(List<SlotReference> lhs, List<SlotReference> rhs) {
Review Comment:
should we put these helper function into ExpressionUtils?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/PushPredicateThroughJoin.java:
##########
@@ -42,28 +42,29 @@
/**
* Push the predicate in the LogicalFilter or LogicalJoin to the join children.
- * For example:
- * select a.k1,b.k1 from a join b on a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5 where a.k1 > 1 and b.k1 > 2
- * Logical plan tree:
- * project
- * |
- * filter (a.k1 > 1 and b.k1 > 2)
- * |
- * join (a.k1 = b.k1 and a.k2 > 2 and b.k2 > 5)
- * / \
- * scan scan
- * transformed:
- * project
- * |
- * join (a.k1 = b.k1)
- * / \
- * filter(a.k1 > 1 and a.k2 > 2 ) filter(b.k1 > 2 and b.k2 > 5)
- * | |
- * scan scan
* todo: Now, only support eq on condition for inner join, support other case later
*/
public class PushPredicateThroughJoin extends OneRewriteRuleFactory {
-
+ /*
Review Comment:
why move this?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ExpressionUtils.java:
##########
@@ -36,14 +36,26 @@
*/
public class ExpressionUtils {
- public static List<Expression> extractConjunct(Expression expr) {
+ public static List<Expression> extractConjunctive(Expression expr) {
return extract(ExpressionType.AND, expr);
}
- public static List<Expression> extractDisjunct(Expression expr) {
+ public static List<Expression> extractDisjunctive(Expression expr) {
return extract(ExpressionType.OR, expr);
}
+ /**
Review Comment:
ππ»
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
Review Comment:
why need `innerLogicalJoin(any(), any())`, could we just use `innerLogicalJoin()`?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left(),
+ join.getJoinReorderContext()
+ );
+ newJoin.getJoinReorderContext().setHasCommute(true);
+ if (swapType == SwapType.ZIG_ZAG && !isBottomJoin) {
+ newJoin.getJoinReorderContext().setHasCommuteZigZag(true);
+ }
+
+ return newJoin;
+ }).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ }
+
+
+ private boolean check(LogicalJoin join) {
+ if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean isBottomJoin(LogicalJoin join) {
+ // TODO: wait for tree model of pattern-match.
+ if (join.left() instanceof LogicalProject) {
Review Comment:
maybe a simple recursive algorithm is better
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/types/DataType.java:
##########
@@ -72,4 +72,14 @@ public static DataType convertFromCatalogDataType(Type catalogType) {
public abstract Type toCatalogDataType();
+ @Override
+ public boolean equals(Object that) {
Review Comment:
we need to implement in sub class. since some type has attributes
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left(),
+ join.getJoinReorderContext()
+ );
+ newJoin.getJoinReorderContext().setHasCommute(true);
Review Comment:
could we use copyWith or a Builder inside oinReorderContext to set all attribute in oinReorderContext with final?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
Review Comment:
currently, we generate a TrueLiteral for empty join condition after PushDownThroughJoin, we need to notice that
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
Review Comment:
these also could put into when?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> bOutputSlots = b.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> cOutputSlots = c.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+
+ // Ignore join with some OnClause like:
+ // Join C = B + A for above example.
+ List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(topJoinOnClause);
+ for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) {
+ if (Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots)
Review Comment:
as discuss in WeChat, ExprId always equal between two equal SlotReference, so we could use equals directly. If we found that ExprId between child's output's SlotReference and expressions in parent. It is a bug absolutely
##########
fe/fe-core/src/test/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomTest.java:
##########
@@ -0,0 +1,152 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.catalog.AggregateType;
+import org.apache.doris.catalog.Column;
+import org.apache.doris.catalog.Table;
+import org.apache.doris.catalog.Type;
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.PlannerContext;
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.plans.JoinType;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
+import org.apache.doris.nereids.types.IntegerType;
+import org.apache.doris.nereids.types.StringType;
+
+import com.google.common.collect.ImmutableList;
+import mockit.Mocked;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.List;
+import java.util.Optional;
+
+public class JoinLAsscomTest {
+ public Pair<LogicalJoin, LogicalJoin> testJoinLAsscom(PlannerContext plannerContext,
Review Comment:
private?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinProjectLAsscom.java:
##########
@@ -0,0 +1,178 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
+
+/**
+ * Rule for change inner join left associative to right.
+ */
+public class JoinProjectLAsscom extends OneExplorationRuleFactory {
+ /*
+ * topJoin newTopJoin
+ * / \ / \
+ * project C newLeftProject newRightProject
+ * / βββΊ / \
+ * bottomJoin newBottomJoin B
+ * / \ / \
+ * A B A C
+ */
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(logicalProject(innerLogicalJoin(any(), any())), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
+
+ LogicalProject<LogicalJoin<Plan, Plan>> project = topJoin.left();
+ LogicalJoin<Plan, Plan> bottomJoin = project.child();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
+ Plan c = topJoin.right();
+
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> bOutputSlots = b.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+ List<SlotReference> cOutputSlots = c.getOutput().stream().map(slot -> (SlotReference) slot)
+ .collect(Collectors.toList());
+
+ // Ignore join with some OnClause like:
+ // Join C = B + A for above example.
+ List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(topJoinOnClause);
+ for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) {
+ if (Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ bOutputSlots)
+ && Utils.isIntersecting(topJoinOnClauseConjunct.collect(SlotReference.class::isInstance),
+ cOutputSlots)
+ ) {
+ return null;
+ }
+ }
+ List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunctive(bottomJoinOnClause);
+
+ List<Expression> allOnCondition = Lists.newArrayList();
+ allOnCondition.addAll(topJoinOnClauseConjuncts);
+ allOnCondition.addAll(bottomJoinOnClauseConjuncts);
+
+ List<SlotReference> newBottomJoinSlots = Lists.newArrayList();
+ newBottomJoinSlots.addAll(aOutputSlots);
+ newBottomJoinSlots.addAll(cOutputSlots);
+
+ List<Expression> newBottomJoinOnCondition = Lists.newArrayList();
+ List<Expression> newTopJoinOnCondition = Lists.newArrayList();
+ for (Expression onCondition : allOnCondition) {
+ List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance);
+ if (Utils.containsAll(newBottomJoinSlots, slots)) {
+ newBottomJoinOnCondition.add(onCondition);
+ } else {
+ newTopJoinOnCondition.add(onCondition);
+ }
+ }
+
+ // newBottomJoinOnCondition/newTopJoinOnCondition is empty. They are cross join.
+ // Example:
+ // A: col1, col2. B: col2, col3. C: col3, col4
+ // (A & B on A.col2=B.col2) & C on B.col3=C.col3.
+ // If (A & B) & C -> (A & C) & B.
+ // (A & C) will be cross join (newBottomJoinOnCondition is empty)
+ if (newBottomJoinOnCondition.isEmpty() || newTopJoinOnCondition.isEmpty()) {
+ return null;
+ }
+
+ Plan newBottomJoin = new LogicalJoin(
+ bottomJoin.getJoinType(),
+ Optional.of(ExpressionUtils.and(newBottomJoinOnCondition)),
+ a, c);
+
+ // Handle project.
+ // TODO: split project into right child(b) and newRightProject.
Review Comment:
this TODO is already done, right?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
/*
- * topJoin newTopJoin
- * / \ / \
- * bottomJoin C --> newBottomJoin B
- * / \ / \
- * A B A C
+ * topJoin newTopJoin
+ * / \ / \
+ * bottomJoin C --> newBottomJoin B
+ * / \ / \
+ * A B A C
*/
@Override
public Rule build() {
- return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
- LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
+ return innerLogicalJoin(innerLogicalJoin(any(), any()), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
- GroupPlan a = bottomJoin.left();
- GroupPlan b = bottomJoin.right();
+ LogicalJoin<Plan, Plan> bottomJoin = topJoin.left();
+
+ Plan a = bottomJoin.left();
+ Plan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ // inner join, onClause can't be empty().
+ Preconditions.checkArgument(optTopJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ Preconditions.checkArgument(optBottomJoinOnClause.isPresent(),
+ "bottomJoin in inner join, onClause must be present.");
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aOutputSlots = a.getOutput().stream().map(slot -> (SlotReference) slot)
Review Comment:
maybe we need to re-introduce our expression system on SIG meeting
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] morrySnow commented on pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
morrySnow commented on PR #10479:
URL: https://github.com/apache/doris/pull/10479#issuecomment-1190547011
please describe more details about this PR in commit msg, 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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] wangshuo128 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
wangshuo128 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r926229221
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -20,32 +20,130 @@
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.ExpressionUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.Optional;
+import java.util.stream.Collectors;
/**
* Rule for change inner join left associative to right.
*/
public class JoinLAsscom extends OneExplorationRuleFactory {
Review Comment:
nit: `JoinLAsscom` -> `JoinAssociative`, it's better to use a full word instead of a prefix, which is easy to understand.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] 924060929 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
924060929 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r920091457
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommutative.java:
##########
@@ -50,11 +51,54 @@ enum SwapType {
@Override
public Rule<Plan> build() {
- return innerLogicalJoin().then(join -> new LogicalJoin(
- join.getJoinType().swap(),
- join.getCondition(),
- join.right(),
- join.left())
- ).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ return innerLogicalJoin().then(join -> {
+ if (check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left()
+ );
+ newJoin.getJoinReorderContext().copyFrom(join.getJoinReorderContext());
+ newJoin.getJoinReorderContext().setHasCommute(true);
+ if (swapType == SwapType.ZIG_ZAG && !isBottomJoin) {
+ newJoin.getJoinReorderContext().setHasCommuteZigZag(true);
+ }
+
+ return newJoin;
+ }).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ }
+
+
+ private boolean check(LogicalJoin join) {
+ if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean isBottomJoin(LogicalJoin join) {
+ if (join.left() instanceof LogicalProject) {
Review Comment:
the pattern `innerLogicalJoin()` will capture the INNER LogicalJoin with GroupPlan as children.
So this line never working. You can wait @wangshuo128 add the tree pattern, then you can capture the children by some type, e.g.
```java
innerLogicalJoin(tree(LogicalProject.class, LogicalJoin.class), tree(LogicalProject.class, LogicalJoin.class)).then(topJoin ->
...
)
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -38,14 +50,101 @@ public class JoinLAsscom extends OneExplorationRuleFactory {
@Override
public Rule<Plan> build() {
return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
+
LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
GroupPlan a = bottomJoin.left();
GroupPlan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ assert (optTopJoinOnClause.isPresent());
+ Expression topJoinOnClause = optTopJoinOnClause.get();
+ Optional<Expression> optBottomJoinOnClause = bottomJoin.getCondition();
+ // TODO: empty onClause.
+ assert (optBottomJoinOnClause.isPresent());
+ Expression bottomJoinOnClause = optBottomJoinOnClause.get();
+
+ List<SlotReference> aSlots = a.collect(SlotReference.class::isInstance);
+ List<SlotReference> bSlots = b.collect(SlotReference.class::isInstance);
+ List<SlotReference> cSlots = c.collect(SlotReference.class::isInstance);
+
+ // Check whether lhs and rhs (both are List<SlotReference>>) are intersecting.
+ BiPredicate<List<SlotReference>, List<SlotReference>> isIntersecting = (lhs, rhs) -> {
+ for (SlotReference lSlot : lhs) {
+ for (SlotReference rSlot : rhs) {
+ // TODO: tmp judge intersecting
+ if (lSlot.getExprId() != rSlot.getExprId()) {
+ return false;
Review Comment:
this intersecting logic is right? `lSlot.getExprId()` should equals to **all of** the `rSlot.getExprId()`?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/Utils.java:
##########
@@ -32,4 +44,115 @@ public static String quoteIfNeeded(String part) {
return part.matches("\\w*[\\w&&[^\\d]]+\\w*")
? part : part.replace("`", "``");
}
+
+ /**
+ * Split predicates with `And` form recursively.
+ * <p>
+ * Some examples:
+ * a and b -> a, b
+ * (a and b) and c -> a, b, c
+ * (a or b) and (c and d) -> (a and b), c , d
Review Comment:
(a or b) and (c and d) -> (a or b), c , d
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscom.java:
##########
@@ -38,14 +50,101 @@ public class JoinLAsscom extends OneExplorationRuleFactory {
@Override
public Rule<Plan> build() {
return innerLogicalJoin(innerLogicalJoin(), any()).then(topJoin -> {
+ if (!check(topJoin)) {
+ return null;
+ }
+
LogicalJoin<GroupPlan, GroupPlan> bottomJoin = topJoin.left();
GroupPlan a = bottomJoin.left();
GroupPlan b = bottomJoin.right();
Plan c = topJoin.right();
- Plan newBottomJoin = new LogicalJoin(bottomJoin.getJoinType(), bottomJoin.getCondition(), a, c);
- return new LogicalJoin(bottomJoin.getJoinType(), topJoin.getCondition(), newBottomJoin, b);
+ Optional<Expression> optTopJoinOnClause = topJoin.getCondition();
+ assert (optTopJoinOnClause.isPresent());
Review Comment:
assert just working when running unit test, are you sure not throw exception in the production environment?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommutative.java:
##########
@@ -50,11 +51,54 @@ enum SwapType {
@Override
public Rule<Plan> build() {
- return innerLogicalJoin().then(join -> new LogicalJoin(
- join.getJoinType().swap(),
- join.getCondition(),
- join.right(),
- join.left())
- ).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ return innerLogicalJoin().then(join -> {
+ if (check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left()
+ );
+ newJoin.getJoinReorderContext().copyFrom(join.getJoinReorderContext());
Review Comment:
why not add a immutable JoinReorderContext field into LogicalJoin and create in the constructor
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] wangshuo128 commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
wangshuo128 commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r920970186
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/Utils.java:
##########
@@ -32,4 +44,115 @@ public static String quoteIfNeeded(String part) {
return part.matches("\\w*[\\w&&[^\\d]]+\\w*")
? part : part.replace("`", "``");
}
+
+ /**
+ * Split predicates with `And` form recursively.
+ * <p>
+ * Some examples:
+ * a and b -> a, b
+ * (a and b) and c -> a, b, c
+ * (a or b) and (c and d) -> (a or b), c , d
+ * <p>
+ * Stop recursion when meeting `Or`, so this func will ignore `And` inside `Or`.
+ * Warning examples:
+ * (a and b) or c -> (a and b) or c
+ */
+ public static List<Expression> extractConjunctive(Expression expr) {
Review Comment:
It's duplicated with `ExpressionUtils.extractConjunct`.
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925389671
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left(),
+ join.getJoinReorderContext()
+ );
+ newJoin.getJoinReorderContext().setHasCommute(true);
+ if (swapType == SwapType.ZIG_ZAG && !isBottomJoin) {
+ newJoin.getJoinReorderContext().setHasCommuteZigZag(true);
+ }
+
+ return newJoin;
+ }).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ }
+
+
+ private boolean check(LogicalJoin join) {
+ if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean isBottomJoin(LogicalJoin join) {
Review Comment:
It's for just apply `commute` for `bottom-join`
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] jackwener commented on a diff in pull request #10479: [feature](nereids): join reorder
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #10479:
URL: https://github.com/apache/doris/pull/10479#discussion_r925389671
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinCommute.java:
##########
@@ -0,0 +1,97 @@
+// 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.
+
+package org.apache.doris.nereids.rules.exploration.join;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.exploration.OneExplorationRuleFactory;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+
+/**
+ * rule factory for exchange inner join's children.
+ */
+public class JoinCommute extends OneExplorationRuleFactory {
+ private final SwapType swapType;
+
+ public JoinCommute() {
+ this.swapType = SwapType.ALL;
+ }
+
+ public JoinCommute(SwapType swapType) {
+ this.swapType = swapType;
+ }
+
+ enum SwapType {
+ BOTTOM_JOIN, ZIG_ZAG, ALL
+ }
+
+ @Override
+ public Rule build() {
+ return innerLogicalJoin(any(), any()).then(join -> {
+ if (!check(join)) {
+ return null;
+ }
+ boolean isBottomJoin = isBottomJoin(join);
+ if (swapType == SwapType.BOTTOM_JOIN && !isBottomJoin) {
+ return null;
+ }
+
+ LogicalJoin newJoin = new LogicalJoin(
+ join.getJoinType(),
+ join.getCondition(),
+ join.right(), join.left(),
+ join.getJoinReorderContext()
+ );
+ newJoin.getJoinReorderContext().setHasCommute(true);
+ if (swapType == SwapType.ZIG_ZAG && !isBottomJoin) {
+ newJoin.getJoinReorderContext().setHasCommuteZigZag(true);
+ }
+
+ return newJoin;
+ }).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE);
+ }
+
+
+ private boolean check(LogicalJoin join) {
+ if (join.getJoinReorderContext().hasCommute() || join.getJoinReorderContext().hasExchange()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean isBottomJoin(LogicalJoin join) {
Review Comment:
It's for just apply `commute` for `bottom-join`
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org