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/10/13 10:28:01 UTC
[GitHub] [doris] jackwener opened a new pull request, #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
jackwener opened a new pull request, #13353:
URL: https://github.com/apache/doris/pull/13353
# Proposed changes
Issue Number: close #xxx
## Problem summary
Describe your changes.
## Checklist(Required)
1. Does it affect the original behavior:
- [x] Yes
- [ ] No
- [ ] I don't know
2. Has unit tests been added:
- [x] Yes
- [ ] No
- [ ] No Need
3. Has document been added or modified:
- [ ] Yes
- [ ] No
- [x] No Need
4. Does it need to update dependencies:
- [ ] Yes
- [x] No
5. Are there any changes that cannot be rolled back:
- [ ] Yes (If Yes, please explain WHY)
- [x] 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 #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #13353:
URL: https://github.com/apache/doris/pull/13353#discussion_r994712048
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/MultiJoin.java:
##########
@@ -17,189 +17,170 @@
package org.apache.doris.nereids.rules.rewrite.logical;
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.expressions.SlotReference;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.logical.AbstractLogicalPlan;
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
-import org.apache.doris.nereids.util.ExpressionUtils;
-import org.apache.doris.nereids.util.JoinUtils;
-import org.apache.doris.nereids.util.PlanUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableList.Builder;
-import java.util.ArrayList;
-import java.util.HashSet;
import java.util.List;
-import java.util.Map;
import java.util.Optional;
-import java.util.Set;
import java.util.stream.Collectors;
/**
* A MultiJoin represents a join of N inputs (NAry-Join).
* The regular Join represent strictly binary input (Binary-Join).
+ * <p>
+ * One {@link MultiJoin} just contains one {@link JoinType} of SEMI/ANTI/OUTER Join.
+ * <p>
+ * onlyJoinType is Full OUTER JOIN, children.size() == 2.
+ * leftChild [Full OUTER JOIN] rightChild.
+ * <p>
+ * onlyJoinType is LEFT (OUTER/SEMI/ANTI) JOIN,
+ * children[0, last) [LEFT (OUTER/SEMI/ANTI) JOIN] lastChild.
+ * eg: MJ([LOJ] A, B, C, D) is {A B C} [LOJ] {D}.
+ * <p>
+ * onlyJoinType is RIGHT (OUTER/SEMI/ANTI) JOIN,
+ * firstChild [RIGHT (OUTER/SEMI/ANTI) JOIN] children[1, last].
+ * eg: MJ([ROJ] A, B, C, D) is {A} [ROJ] {B C D}.
*/
-public class MultiJoin extends PlanVisitor<Void, Void> {
+public class MultiJoin extends AbstractLogicalPlan {
/*
* topJoin
* / \ MultiJoin
* bottomJoin C --> / | \
* / \ A B C
* A B
*/
- public final List<Plan> joinInputs = new ArrayList<>();
- public final List<Expression> conjunctsForAllHashJoins = new ArrayList<>();
- private List<Expression> conjunctsKeepInFilter = new ArrayList<>();
-
- /**
- * reorderJoinsAccordingToConditions
- *
- * @return join or filter
- */
- public Optional<Plan> reorderJoinsAccordingToConditions() {
- if (joinInputs.size() >= 2) {
- Plan root = reorderJoinsAccordingToConditions(joinInputs, conjunctsForAllHashJoins);
- return Optional.of(PlanUtils.filterOrSelf(conjunctsKeepInFilter, root));
- }
- return Optional.empty();
+
+ // Push predicates into it.
+ // But joinFilter shouldn't contain predicate which just contains one predicate like `T.key > 1`.
+ // Because these predicate should be pushdown.
+ private final List<Expression> joinFilter;
+ // MultiJoin just contains one OUTER/SEMI/ANTI.
+ private final Optional<JoinType> onlyJoinType;
+ // When contains one OUTER/SEMI/ANTI join, keep separately its condition.
+ private final List<Expression> notInnerJoinConditions;
+
+ // private final List<@Nullable List<NamedExpression>> projFields;
Review Comment:
current it's useless
--
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] github-actions[bot] commented on pull request #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on PR #13353:
URL: https://github.com/apache/doris/pull/13353#issuecomment-1278630201
PR approved by at least one committer and no changes requested.
--
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 #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #13353:
URL: https://github.com/apache/doris/pull/13353#discussion_r994715649
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
+ // subtree can't specify the end of Pattern. so end can be GroupPlan or Filter
+ if (plan instanceof GroupPlan
+ || (plan instanceof LogicalFilter && plan.child(0) instanceof GroupPlan)) {
+ return plan;
+ }
+
+ List<Plan> inputs = Lists.newArrayList();
+ List<Expression> joinFilter = Lists.newArrayList();
+ List<Expression> notInnerJoinConditions = Lists.newArrayList();
+
+ LogicalJoin<?, ?> join;
+ if (plan instanceof LogicalFilter) {
+ LogicalFilter<?> filter = (LogicalFilter<?>) plan;
+ joinFilter.addAll(ExpressionUtils.extractConjunction(filter.getPredicates()));
+ join = (LogicalJoin<?, ?>) filter.child();
+ } else {
+ join = (LogicalJoin<?, ?>) plan;
+ }
+
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinFilter.addAll(join.getHashJoinConjuncts());
+ joinFilter.addAll(join.getOtherJoinConjuncts());
+ } else {
+ notInnerJoinConditions.addAll(join.getHashJoinConjuncts());
+ notInnerJoinConditions.addAll(join.getOtherJoinConjuncts());
+ }
+
+ // recursively convert children.
+ Plan left = joinToMultiJoin(join.left());
+ Plan right = joinToMultiJoin(join.right());
+
+ boolean changeLeft = join.getJoinType().isRightJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(left, changeLeft)) {
+ MultiJoin leftMultiJoin = (MultiJoin) left;
+ inputs.addAll(leftMultiJoin.children());
+ joinFilter.addAll(leftMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(left);
+ }
+
+ boolean changeRight = join.getJoinType().isLeftJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(right, changeRight)) {
+ MultiJoin rightMultiJoin = (MultiJoin) right;
+ inputs.addAll(rightMultiJoin.children());
+ joinFilter.addAll(rightMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(right);
+ }
+
+ Optional<JoinType> joinType;
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinType = Optional.empty();
+ } else {
+ joinType = Optional.of(join.getJoinType());
+ }
+ return new MultiJoin(
+ inputs,
+ joinFilter,
+ joinType,
+ notInnerJoinConditions);
+ }
+
+ /**
+ * Recursively convert to
+ * {@link MultiJoin}
+ * -->
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * <p>
+ * When all input is CROSS/Inner Join, all join will be flattened.
+ * Otherwise, we will split {join cluster} into multiple {@link MultiJoin}.
+ * <p>
+ * Here are examples of the {@link MultiJoin}s constructed after this rules has been applied.
+ * <p>
+ * simple example:
+ * <ul>
+ * <li>A JOIN B --> MJ(A, B)
+ * <li>A JOIN B JOIN C JOIN D --> MJ(A, B, C, D)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([LOJ/LSJ/LAJ]A, B)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([ROJ/RSJ/RAJ]A, B)
+ * <li>A FULL JOIN B --> MJ[FOJ](A, B)
+ * </ul>
+ * </p>
+ * <p>
+ * complex example:
+ * <ul>
+ * <li>A LEFT OUTER JOIN (B JOIN C) --> MJ([LOJ]A, MJ(B, C)))
+ * <li>(A JOIN B) LEFT JOIN C --> MJ(A, B, C)
+ * <li>(A LEFT OUTER JOIN B) JOIN C --> MJ(MJ(A, B), C)
+ * <li>A LEFT JOIN (B FULL JOIN C) --> MJ(A, MJ[full](B, C))
+ * <li>(A LEFT JOIN B) FULL JOIN (C RIGHT JOIN D) --> MJ[full](MJ(A, B), MJ(C, D))
+ * </ul>
+ * </p>
+ * more complex example:
+ * <ul>
+ * <li> A JOIN B JOIN C LEFT JOIN D --> MJ([LOJ]A, B, C, D)
+ * <li> A JOIN B JOIN C LEFT JOIN (D JOIN F) --> MJ([LOJ]A, B, C, MJ(D, F))
+ * <li> A RIGHT JOIN (B JOIN C JOIN D)--> MJ([ROJ]A, B, C, D)
+ * <li> A JOIN B RIGHT JOIN (C JOIN D) --> MJ(A, B, MJ([ROJ]C, D))
+ * </ul>
+ * </p>
+ * <p>
+ * Graphic presentation:
+ * A JOIN B JOIN C LEFT JOIN D JOIN F
+ * left left│
+ * A B C D F ──► A B C │ D F ──► MJ(LOJ A,B,C,MJ(DF)
+ * <p>
+ * A JOIN B RIGHT JOIN C JOIN D JOIN F
+ * right │right
+ * A B C D F ──► A B │ C D F ──► MJ(A,B,MJ(ROJ C,D,F)
+ * <p>
+ * (A JOIN B JOIN C) FULL JOIN (D JOIN F)
+ * full │
+ * A B C D F ──► A B C │ D F ──► MJ(FOJ MJ(A,B,C) MJ(D,F))
+ * </p>
+ */
+ public Plan multiJoinToJoin(MultiJoin multiJoin) {
+ if (multiJoin.arity() == 1) {
+ return PlanUtils.filterOrSelf(multiJoin.getJoinFilter(), multiJoin.child(0));
+ }
+
+ Builder<Plan> builder = ImmutableList.builder();
+ // recursively hanlde multiJoin children.
+ for (Plan child : multiJoin.children()) {
+ if (child instanceof MultiJoin) {
+ MultiJoin childMultiJoin = (MultiJoin) child;
+ builder.add(multiJoinToJoin(childMultiJoin));
+ } else {
+ builder.add(child);
+ }
+ }
+ MultiJoin multiJoinHandleChildren = multiJoin.withChildren(builder.build());
+
+ if (multiJoinHandleChildren.getOnlyJoinType().isPresent()) {
+ List<Expression> leftFilter = Lists.newArrayList();
+ List<Expression> rightFilter = Lists.newArrayList();
+ List<Expression> remainingFilter = Lists.newArrayList();
+ Plan left = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(0, multiJoinHandleChildren.arity() - 1),
+ leftFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ Plan right = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity()),
+ rightFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ if (multiJoinHandleChildren.getOnlyJoinType().get().isLeftJoin()) {
+ right = multiJoinHandleChildren.child(multiJoinHandleChildren.arity() - 1);
+ } else if (multiJoinHandleChildren.getOnlyJoinType().get().isRightJoin()) {
+ left = multiJoinHandleChildren.child(0);
+ }
+
+ // split filter
+ for (Expression expr : multiJoinHandleChildren.getJoinFilter()) {
+ Set<Slot> exprInputSlots = expr.getInputSlots();
+ Preconditions.checkState(!exprInputSlots.isEmpty());
+
+ if (left.getOutputSet().containsAll(exprInputSlots)) {
+ leftFilter.add(expr);
+ } else if (right.getOutputSet().containsAll(exprInputSlots)) {
+ rightFilter.add(expr);
+ } else if (multiJoin.getOutputSet().containsAll(exprInputSlots)) {
+ remainingFilter.add(expr);
+ } else {
+ throw new RuntimeException("invalid expression");
+ }
+ }
+
+ return PlanUtils.filterOrSelf(remainingFilter, new LogicalJoin<>(
+ multiJoinHandleChildren.getOnlyJoinType().get(),
+ ExpressionUtils.EMPTY_CONDITION,
+ multiJoinHandleChildren.getNotInnerJoinConditions(),
+ PlanUtils.filterOrSelf(leftFilter, left), PlanUtils.filterOrSelf(rightFilter, right)));
+ }
+
+ // following this multiJoin just contain INNER/CROSS.
+ List<Expression> joinFilter = multiJoinHandleChildren.getJoinFilter();
+
+ Plan left = multiJoinHandleChildren.child(0);
+ List<Plan> candidates = multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity());
+
+ LogicalJoin<? extends Plan, ? extends Plan> join = findInnerJoin(left, candidates, joinFilter);
+ List<Plan> newInputs = Lists.newArrayList();
+ newInputs.add(join);
+ newInputs.addAll(candidates.stream().filter(plan -> !join.right().equals(plan)).collect(Collectors.toList()));
+
+ joinFilter.removeAll(join.getHashJoinConjuncts());
+ joinFilter.removeAll(join.getOtherJoinConjuncts());
+ return multiJoinToJoin(new MultiJoin(
+ newInputs,
+ joinFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ }
+
+ /**
+ * Returns whether an input can be merged without changing semantics.
+ *
+ * @param input input into a MultiJoin or (GroupPlan|LogicalFilter)
+ * @param changeLeft generate nullable or left not exist.
+ * @return true if the input can be combined into a parent MultiJoin
+ */
+ private static boolean canCombine(Plan input, boolean changeLeft) {
Review Comment:
It can be SEMI/ANTI
--
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 #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
Posted by GitBox <gi...@apache.org>.
morrySnow commented on code in PR #13353:
URL: https://github.com/apache/doris/pull/13353#discussion_r994551790
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -45,13 +64,237 @@ public class ReorderJoin extends OneRewriteRuleFactory {
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
Review Comment:
add a instanceof assert. and throw exception when return object type is not MultiJoin
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/MultiJoin.java:
##########
@@ -17,189 +17,170 @@
package org.apache.doris.nereids.rules.rewrite.logical;
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.expressions.SlotReference;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.logical.AbstractLogicalPlan;
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
-import org.apache.doris.nereids.util.ExpressionUtils;
-import org.apache.doris.nereids.util.JoinUtils;
-import org.apache.doris.nereids.util.PlanUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableList.Builder;
-import java.util.ArrayList;
-import java.util.HashSet;
import java.util.List;
-import java.util.Map;
import java.util.Optional;
-import java.util.Set;
import java.util.stream.Collectors;
/**
* A MultiJoin represents a join of N inputs (NAry-Join).
* The regular Join represent strictly binary input (Binary-Join).
+ * <p>
+ * One {@link MultiJoin} just contains one {@link JoinType} of SEMI/ANTI/OUTER Join.
+ * <p>
+ * onlyJoinType is Full OUTER JOIN, children.size() == 2.
+ * leftChild [Full OUTER JOIN] rightChild.
+ * <p>
+ * onlyJoinType is LEFT (OUTER/SEMI/ANTI) JOIN,
+ * children[0, last) [LEFT (OUTER/SEMI/ANTI) JOIN] lastChild.
+ * eg: MJ([LOJ] A, B, C, D) is {A B C} [LOJ] {D}.
+ * <p>
+ * onlyJoinType is RIGHT (OUTER/SEMI/ANTI) JOIN,
+ * firstChild [RIGHT (OUTER/SEMI/ANTI) JOIN] children[1, last].
+ * eg: MJ([ROJ] A, B, C, D) is {A} [ROJ] {B C D}.
*/
-public class MultiJoin extends PlanVisitor<Void, Void> {
+public class MultiJoin extends AbstractLogicalPlan {
/*
* topJoin
* / \ MultiJoin
* bottomJoin C --> / | \
* / \ A B C
* A B
*/
- public final List<Plan> joinInputs = new ArrayList<>();
- public final List<Expression> conjunctsForAllHashJoins = new ArrayList<>();
- private List<Expression> conjunctsKeepInFilter = new ArrayList<>();
-
- /**
- * reorderJoinsAccordingToConditions
- *
- * @return join or filter
- */
- public Optional<Plan> reorderJoinsAccordingToConditions() {
- if (joinInputs.size() >= 2) {
- Plan root = reorderJoinsAccordingToConditions(joinInputs, conjunctsForAllHashJoins);
- return Optional.of(PlanUtils.filterOrSelf(conjunctsKeepInFilter, root));
- }
- return Optional.empty();
+
+ // Push predicates into it.
+ // But joinFilter shouldn't contain predicate which just contains one predicate like `T.key > 1`.
+ // Because these predicate should be pushdown.
+ private final List<Expression> joinFilter;
+ // MultiJoin just contains one OUTER/SEMI/ANTI.
+ private final Optional<JoinType> onlyJoinType;
Review Comment:
i think joinType is enough
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
+ // subtree can't specify the end of Pattern. so end can be GroupPlan or Filter
+ if (plan instanceof GroupPlan
+ || (plan instanceof LogicalFilter && plan.child(0) instanceof GroupPlan)) {
+ return plan;
+ }
+
+ List<Plan> inputs = Lists.newArrayList();
+ List<Expression> joinFilter = Lists.newArrayList();
+ List<Expression> notInnerJoinConditions = Lists.newArrayList();
+
+ LogicalJoin<?, ?> join;
+ if (plan instanceof LogicalFilter) {
+ LogicalFilter<?> filter = (LogicalFilter<?>) plan;
+ joinFilter.addAll(ExpressionUtils.extractConjunction(filter.getPredicates()));
+ join = (LogicalJoin<?, ?>) filter.child();
Review Comment:
we have a Implicit rely on MergeFilter. Add this info on class comment~
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/MultiJoin.java:
##########
@@ -17,189 +17,170 @@
package org.apache.doris.nereids.rules.rewrite.logical;
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.expressions.SlotReference;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.logical.AbstractLogicalPlan;
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
-import org.apache.doris.nereids.util.ExpressionUtils;
-import org.apache.doris.nereids.util.JoinUtils;
-import org.apache.doris.nereids.util.PlanUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableList.Builder;
-import java.util.ArrayList;
-import java.util.HashSet;
import java.util.List;
-import java.util.Map;
import java.util.Optional;
-import java.util.Set;
import java.util.stream.Collectors;
/**
* A MultiJoin represents a join of N inputs (NAry-Join).
* The regular Join represent strictly binary input (Binary-Join).
+ * <p>
+ * One {@link MultiJoin} just contains one {@link JoinType} of SEMI/ANTI/OUTER Join.
+ * <p>
+ * onlyJoinType is Full OUTER JOIN, children.size() == 2.
+ * leftChild [Full OUTER JOIN] rightChild.
+ * <p>
+ * onlyJoinType is LEFT (OUTER/SEMI/ANTI) JOIN,
+ * children[0, last) [LEFT (OUTER/SEMI/ANTI) JOIN] lastChild.
+ * eg: MJ([LOJ] A, B, C, D) is {A B C} [LOJ] {D}.
+ * <p>
+ * onlyJoinType is RIGHT (OUTER/SEMI/ANTI) JOIN,
+ * firstChild [RIGHT (OUTER/SEMI/ANTI) JOIN] children[1, last].
+ * eg: MJ([ROJ] A, B, C, D) is {A} [ROJ] {B C D}.
*/
-public class MultiJoin extends PlanVisitor<Void, Void> {
+public class MultiJoin extends AbstractLogicalPlan {
/*
* topJoin
* / \ MultiJoin
* bottomJoin C --> / | \
* / \ A B C
* A B
*/
- public final List<Plan> joinInputs = new ArrayList<>();
- public final List<Expression> conjunctsForAllHashJoins = new ArrayList<>();
- private List<Expression> conjunctsKeepInFilter = new ArrayList<>();
-
- /**
- * reorderJoinsAccordingToConditions
- *
- * @return join or filter
- */
- public Optional<Plan> reorderJoinsAccordingToConditions() {
- if (joinInputs.size() >= 2) {
- Plan root = reorderJoinsAccordingToConditions(joinInputs, conjunctsForAllHashJoins);
- return Optional.of(PlanUtils.filterOrSelf(conjunctsKeepInFilter, root));
- }
- return Optional.empty();
+
+ // Push predicates into it.
+ // But joinFilter shouldn't contain predicate which just contains one predicate like `T.key > 1`.
+ // Because these predicate should be pushdown.
+ private final List<Expression> joinFilter;
+ // MultiJoin just contains one OUTER/SEMI/ANTI.
+ private final Optional<JoinType> onlyJoinType;
+ // When contains one OUTER/SEMI/ANTI join, keep separately its condition.
+ private final List<Expression> notInnerJoinConditions;
+
+ // private final List<@Nullable List<NamedExpression>> projFields;
Review Comment:
why comment this？
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
+ // subtree can't specify the end of Pattern. so end can be GroupPlan or Filter
+ if (plan instanceof GroupPlan
+ || (plan instanceof LogicalFilter && plan.child(0) instanceof GroupPlan)) {
+ return plan;
+ }
+
+ List<Plan> inputs = Lists.newArrayList();
+ List<Expression> joinFilter = Lists.newArrayList();
+ List<Expression> notInnerJoinConditions = Lists.newArrayList();
+
+ LogicalJoin<?, ?> join;
+ if (plan instanceof LogicalFilter) {
+ LogicalFilter<?> filter = (LogicalFilter<?>) plan;
+ joinFilter.addAll(ExpressionUtils.extractConjunction(filter.getPredicates()));
+ join = (LogicalJoin<?, ?>) filter.child();
+ } else {
+ join = (LogicalJoin<?, ?>) plan;
+ }
+
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinFilter.addAll(join.getHashJoinConjuncts());
+ joinFilter.addAll(join.getOtherJoinConjuncts());
+ } else {
+ notInnerJoinConditions.addAll(join.getHashJoinConjuncts());
+ notInnerJoinConditions.addAll(join.getOtherJoinConjuncts());
+ }
+
+ // recursively convert children.
+ Plan left = joinToMultiJoin(join.left());
+ Plan right = joinToMultiJoin(join.right());
+
+ boolean changeLeft = join.getJoinType().isRightJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(left, changeLeft)) {
+ MultiJoin leftMultiJoin = (MultiJoin) left;
+ inputs.addAll(leftMultiJoin.children());
+ joinFilter.addAll(leftMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(left);
+ }
+
+ boolean changeRight = join.getJoinType().isLeftJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(right, changeRight)) {
+ MultiJoin rightMultiJoin = (MultiJoin) right;
+ inputs.addAll(rightMultiJoin.children());
+ joinFilter.addAll(rightMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(right);
+ }
+
+ Optional<JoinType> joinType;
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinType = Optional.empty();
+ } else {
+ joinType = Optional.of(join.getJoinType());
+ }
+ return new MultiJoin(
+ inputs,
+ joinFilter,
+ joinType,
+ notInnerJoinConditions);
+ }
+
+ /**
+ * Recursively convert to
+ * {@link MultiJoin}
+ * -->
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * <p>
+ * When all input is CROSS/Inner Join, all join will be flattened.
+ * Otherwise, we will split {join cluster} into multiple {@link MultiJoin}.
+ * <p>
+ * Here are examples of the {@link MultiJoin}s constructed after this rules has been applied.
+ * <p>
+ * simple example:
+ * <ul>
+ * <li>A JOIN B --> MJ(A, B)
+ * <li>A JOIN B JOIN C JOIN D --> MJ(A, B, C, D)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([LOJ/LSJ/LAJ]A, B)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([ROJ/RSJ/RAJ]A, B)
+ * <li>A FULL JOIN B --> MJ[FOJ](A, B)
+ * </ul>
+ * </p>
+ * <p>
+ * complex example:
+ * <ul>
+ * <li>A LEFT OUTER JOIN (B JOIN C) --> MJ([LOJ]A, MJ(B, C)))
+ * <li>(A JOIN B) LEFT JOIN C --> MJ(A, B, C)
+ * <li>(A LEFT OUTER JOIN B) JOIN C --> MJ(MJ(A, B), C)
+ * <li>A LEFT JOIN (B FULL JOIN C) --> MJ(A, MJ[full](B, C))
+ * <li>(A LEFT JOIN B) FULL JOIN (C RIGHT JOIN D) --> MJ[full](MJ(A, B), MJ(C, D))
+ * </ul>
+ * </p>
+ * more complex example:
+ * <ul>
+ * <li> A JOIN B JOIN C LEFT JOIN D --> MJ([LOJ]A, B, C, D)
+ * <li> A JOIN B JOIN C LEFT JOIN (D JOIN F) --> MJ([LOJ]A, B, C, MJ(D, F))
+ * <li> A RIGHT JOIN (B JOIN C JOIN D)--> MJ([ROJ]A, B, C, D)
+ * <li> A JOIN B RIGHT JOIN (C JOIN D) --> MJ(A, B, MJ([ROJ]C, D))
+ * </ul>
+ * </p>
+ * <p>
+ * Graphic presentation:
+ * A JOIN B JOIN C LEFT JOIN D JOIN F
+ * left left│
+ * A B C D F ──► A B C │ D F ──► MJ(LOJ A,B,C,MJ(DF)
+ * <p>
+ * A JOIN B RIGHT JOIN C JOIN D JOIN F
+ * right │right
+ * A B C D F ──► A B │ C D F ──► MJ(A,B,MJ(ROJ C,D,F)
+ * <p>
+ * (A JOIN B JOIN C) FULL JOIN (D JOIN F)
+ * full │
+ * A B C D F ──► A B C │ D F ──► MJ(FOJ MJ(A,B,C) MJ(D,F))
+ * </p>
+ */
+ public Plan multiJoinToJoin(MultiJoin multiJoin) {
+ if (multiJoin.arity() == 1) {
+ return PlanUtils.filterOrSelf(multiJoin.getJoinFilter(), multiJoin.child(0));
+ }
+
+ Builder<Plan> builder = ImmutableList.builder();
+ // recursively hanlde multiJoin children.
+ for (Plan child : multiJoin.children()) {
+ if (child instanceof MultiJoin) {
+ MultiJoin childMultiJoin = (MultiJoin) child;
+ builder.add(multiJoinToJoin(childMultiJoin));
+ } else {
+ builder.add(child);
+ }
+ }
+ MultiJoin multiJoinHandleChildren = multiJoin.withChildren(builder.build());
+
+ if (multiJoinHandleChildren.getOnlyJoinType().isPresent()) {
+ List<Expression> leftFilter = Lists.newArrayList();
+ List<Expression> rightFilter = Lists.newArrayList();
+ List<Expression> remainingFilter = Lists.newArrayList();
+ Plan left = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(0, multiJoinHandleChildren.arity() - 1),
+ leftFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ Plan right = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity()),
+ rightFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ if (multiJoinHandleChildren.getOnlyJoinType().get().isLeftJoin()) {
+ right = multiJoinHandleChildren.child(multiJoinHandleChildren.arity() - 1);
+ } else if (multiJoinHandleChildren.getOnlyJoinType().get().isRightJoin()) {
+ left = multiJoinHandleChildren.child(0);
+ }
+
+ // split filter
+ for (Expression expr : multiJoinHandleChildren.getJoinFilter()) {
+ Set<Slot> exprInputSlots = expr.getInputSlots();
+ Preconditions.checkState(!exprInputSlots.isEmpty());
+
+ if (left.getOutputSet().containsAll(exprInputSlots)) {
+ leftFilter.add(expr);
+ } else if (right.getOutputSet().containsAll(exprInputSlots)) {
+ rightFilter.add(expr);
+ } else if (multiJoin.getOutputSet().containsAll(exprInputSlots)) {
+ remainingFilter.add(expr);
+ } else {
+ throw new RuntimeException("invalid expression");
Review Comment:
add more info to exception, and do log
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
+ // subtree can't specify the end of Pattern. so end can be GroupPlan or Filter
+ if (plan instanceof GroupPlan
+ || (plan instanceof LogicalFilter && plan.child(0) instanceof GroupPlan)) {
+ return plan;
+ }
+
+ List<Plan> inputs = Lists.newArrayList();
+ List<Expression> joinFilter = Lists.newArrayList();
+ List<Expression> notInnerJoinConditions = Lists.newArrayList();
+
+ LogicalJoin<?, ?> join;
+ if (plan instanceof LogicalFilter) {
+ LogicalFilter<?> filter = (LogicalFilter<?>) plan;
+ joinFilter.addAll(ExpressionUtils.extractConjunction(filter.getPredicates()));
+ join = (LogicalJoin<?, ?>) filter.child();
+ } else {
+ join = (LogicalJoin<?, ?>) plan;
+ }
+
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinFilter.addAll(join.getHashJoinConjuncts());
+ joinFilter.addAll(join.getOtherJoinConjuncts());
+ } else {
+ notInnerJoinConditions.addAll(join.getHashJoinConjuncts());
+ notInnerJoinConditions.addAll(join.getOtherJoinConjuncts());
+ }
+
+ // recursively convert children.
+ Plan left = joinToMultiJoin(join.left());
+ Plan right = joinToMultiJoin(join.right());
+
+ boolean changeLeft = join.getJoinType().isRightJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(left, changeLeft)) {
+ MultiJoin leftMultiJoin = (MultiJoin) left;
+ inputs.addAll(leftMultiJoin.children());
+ joinFilter.addAll(leftMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(left);
+ }
+
+ boolean changeRight = join.getJoinType().isLeftJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(right, changeRight)) {
+ MultiJoin rightMultiJoin = (MultiJoin) right;
+ inputs.addAll(rightMultiJoin.children());
+ joinFilter.addAll(rightMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(right);
+ }
+
+ Optional<JoinType> joinType;
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinType = Optional.empty();
+ } else {
+ joinType = Optional.of(join.getJoinType());
+ }
+ return new MultiJoin(
+ inputs,
+ joinFilter,
+ joinType,
+ notInnerJoinConditions);
+ }
+
+ /**
+ * Recursively convert to
+ * {@link MultiJoin}
+ * -->
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * <p>
+ * When all input is CROSS/Inner Join, all join will be flattened.
+ * Otherwise, we will split {join cluster} into multiple {@link MultiJoin}.
+ * <p>
+ * Here are examples of the {@link MultiJoin}s constructed after this rules has been applied.
+ * <p>
+ * simple example:
+ * <ul>
+ * <li>A JOIN B --> MJ(A, B)
+ * <li>A JOIN B JOIN C JOIN D --> MJ(A, B, C, D)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([LOJ/LSJ/LAJ]A, B)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([ROJ/RSJ/RAJ]A, B)
+ * <li>A FULL JOIN B --> MJ[FOJ](A, B)
+ * </ul>
+ * </p>
+ * <p>
+ * complex example:
+ * <ul>
+ * <li>A LEFT OUTER JOIN (B JOIN C) --> MJ([LOJ]A, MJ(B, C)))
+ * <li>(A JOIN B) LEFT JOIN C --> MJ(A, B, C)
+ * <li>(A LEFT OUTER JOIN B) JOIN C --> MJ(MJ(A, B), C)
+ * <li>A LEFT JOIN (B FULL JOIN C) --> MJ(A, MJ[full](B, C))
+ * <li>(A LEFT JOIN B) FULL JOIN (C RIGHT JOIN D) --> MJ[full](MJ(A, B), MJ(C, D))
+ * </ul>
+ * </p>
+ * more complex example:
+ * <ul>
+ * <li> A JOIN B JOIN C LEFT JOIN D --> MJ([LOJ]A, B, C, D)
+ * <li> A JOIN B JOIN C LEFT JOIN (D JOIN F) --> MJ([LOJ]A, B, C, MJ(D, F))
+ * <li> A RIGHT JOIN (B JOIN C JOIN D)--> MJ([ROJ]A, B, C, D)
+ * <li> A JOIN B RIGHT JOIN (C JOIN D) --> MJ(A, B, MJ([ROJ]C, D))
+ * </ul>
+ * </p>
+ * <p>
+ * Graphic presentation:
+ * A JOIN B JOIN C LEFT JOIN D JOIN F
+ * left left│
+ * A B C D F ──► A B C │ D F ──► MJ(LOJ A,B,C,MJ(DF)
+ * <p>
+ * A JOIN B RIGHT JOIN C JOIN D JOIN F
+ * right │right
+ * A B C D F ──► A B │ C D F ──► MJ(A,B,MJ(ROJ C,D,F)
+ * <p>
+ * (A JOIN B JOIN C) FULL JOIN (D JOIN F)
+ * full │
+ * A B C D F ──► A B C │ D F ──► MJ(FOJ MJ(A,B,C) MJ(D,F))
+ * </p>
+ */
+ public Plan multiJoinToJoin(MultiJoin multiJoin) {
+ if (multiJoin.arity() == 1) {
+ return PlanUtils.filterOrSelf(multiJoin.getJoinFilter(), multiJoin.child(0));
+ }
+
+ Builder<Plan> builder = ImmutableList.builder();
+ // recursively hanlde multiJoin children.
+ for (Plan child : multiJoin.children()) {
+ if (child instanceof MultiJoin) {
+ MultiJoin childMultiJoin = (MultiJoin) child;
+ builder.add(multiJoinToJoin(childMultiJoin));
+ } else {
+ builder.add(child);
+ }
+ }
+ MultiJoin multiJoinHandleChildren = multiJoin.withChildren(builder.build());
+
+ if (multiJoinHandleChildren.getOnlyJoinType().isPresent()) {
+ List<Expression> leftFilter = Lists.newArrayList();
+ List<Expression> rightFilter = Lists.newArrayList();
+ List<Expression> remainingFilter = Lists.newArrayList();
+ Plan left = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(0, multiJoinHandleChildren.arity() - 1),
+ leftFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ Plan right = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity()),
+ rightFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ if (multiJoinHandleChildren.getOnlyJoinType().get().isLeftJoin()) {
+ right = multiJoinHandleChildren.child(multiJoinHandleChildren.arity() - 1);
+ } else if (multiJoinHandleChildren.getOnlyJoinType().get().isRightJoin()) {
+ left = multiJoinHandleChildren.child(0);
+ }
+
+ // split filter
+ for (Expression expr : multiJoinHandleChildren.getJoinFilter()) {
+ Set<Slot> exprInputSlots = expr.getInputSlots();
+ Preconditions.checkState(!exprInputSlots.isEmpty());
+
+ if (left.getOutputSet().containsAll(exprInputSlots)) {
+ leftFilter.add(expr);
+ } else if (right.getOutputSet().containsAll(exprInputSlots)) {
+ rightFilter.add(expr);
+ } else if (multiJoin.getOutputSet().containsAll(exprInputSlots)) {
+ remainingFilter.add(expr);
+ } else {
+ throw new RuntimeException("invalid expression");
+ }
+ }
+
+ return PlanUtils.filterOrSelf(remainingFilter, new LogicalJoin<>(
+ multiJoinHandleChildren.getOnlyJoinType().get(),
+ ExpressionUtils.EMPTY_CONDITION,
+ multiJoinHandleChildren.getNotInnerJoinConditions(),
+ PlanUtils.filterOrSelf(leftFilter, left), PlanUtils.filterOrSelf(rightFilter, right)));
+ }
+
+ // following this multiJoin just contain INNER/CROSS.
+ List<Expression> joinFilter = multiJoinHandleChildren.getJoinFilter();
+
+ Plan left = multiJoinHandleChildren.child(0);
+ List<Plan> candidates = multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity());
+
+ LogicalJoin<? extends Plan, ? extends Plan> join = findInnerJoin(left, candidates, joinFilter);
+ List<Plan> newInputs = Lists.newArrayList();
+ newInputs.add(join);
+ newInputs.addAll(candidates.stream().filter(plan -> !join.right().equals(plan)).collect(Collectors.toList()));
+
+ joinFilter.removeAll(join.getHashJoinConjuncts());
+ joinFilter.removeAll(join.getOtherJoinConjuncts());
+ return multiJoinToJoin(new MultiJoin(
+ newInputs,
+ joinFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
Review Comment:
could eliminate this recursion？
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
+ // subtree can't specify the end of Pattern. so end can be GroupPlan or Filter
+ if (plan instanceof GroupPlan
+ || (plan instanceof LogicalFilter && plan.child(0) instanceof GroupPlan)) {
+ return plan;
+ }
+
+ List<Plan> inputs = Lists.newArrayList();
+ List<Expression> joinFilter = Lists.newArrayList();
+ List<Expression> notInnerJoinConditions = Lists.newArrayList();
+
+ LogicalJoin<?, ?> join;
+ if (plan instanceof LogicalFilter) {
+ LogicalFilter<?> filter = (LogicalFilter<?>) plan;
+ joinFilter.addAll(ExpressionUtils.extractConjunction(filter.getPredicates()));
+ join = (LogicalJoin<?, ?>) filter.child();
+ } else {
+ join = (LogicalJoin<?, ?>) plan;
+ }
+
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinFilter.addAll(join.getHashJoinConjuncts());
+ joinFilter.addAll(join.getOtherJoinConjuncts());
+ } else {
+ notInnerJoinConditions.addAll(join.getHashJoinConjuncts());
+ notInnerJoinConditions.addAll(join.getOtherJoinConjuncts());
+ }
+
+ // recursively convert children.
+ Plan left = joinToMultiJoin(join.left());
+ Plan right = joinToMultiJoin(join.right());
+
+ boolean changeLeft = join.getJoinType().isRightJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(left, changeLeft)) {
+ MultiJoin leftMultiJoin = (MultiJoin) left;
+ inputs.addAll(leftMultiJoin.children());
+ joinFilter.addAll(leftMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(left);
+ }
+
+ boolean changeRight = join.getJoinType().isLeftJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(right, changeRight)) {
+ MultiJoin rightMultiJoin = (MultiJoin) right;
+ inputs.addAll(rightMultiJoin.children());
+ joinFilter.addAll(rightMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(right);
+ }
+
+ Optional<JoinType> joinType;
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinType = Optional.empty();
+ } else {
+ joinType = Optional.of(join.getJoinType());
+ }
+ return new MultiJoin(
+ inputs,
+ joinFilter,
+ joinType,
+ notInnerJoinConditions);
+ }
+
+ /**
+ * Recursively convert to
+ * {@link MultiJoin}
+ * -->
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * <p>
+ * When all input is CROSS/Inner Join, all join will be flattened.
+ * Otherwise, we will split {join cluster} into multiple {@link MultiJoin}.
+ * <p>
+ * Here are examples of the {@link MultiJoin}s constructed after this rules has been applied.
+ * <p>
+ * simple example:
+ * <ul>
+ * <li>A JOIN B --> MJ(A, B)
+ * <li>A JOIN B JOIN C JOIN D --> MJ(A, B, C, D)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([LOJ/LSJ/LAJ]A, B)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([ROJ/RSJ/RAJ]A, B)
+ * <li>A FULL JOIN B --> MJ[FOJ](A, B)
+ * </ul>
+ * </p>
+ * <p>
+ * complex example:
+ * <ul>
+ * <li>A LEFT OUTER JOIN (B JOIN C) --> MJ([LOJ]A, MJ(B, C)))
+ * <li>(A JOIN B) LEFT JOIN C --> MJ(A, B, C)
+ * <li>(A LEFT OUTER JOIN B) JOIN C --> MJ(MJ(A, B), C)
+ * <li>A LEFT JOIN (B FULL JOIN C) --> MJ(A, MJ[full](B, C))
+ * <li>(A LEFT JOIN B) FULL JOIN (C RIGHT JOIN D) --> MJ[full](MJ(A, B), MJ(C, D))
+ * </ul>
+ * </p>
+ * more complex example:
+ * <ul>
+ * <li> A JOIN B JOIN C LEFT JOIN D --> MJ([LOJ]A, B, C, D)
+ * <li> A JOIN B JOIN C LEFT JOIN (D JOIN F) --> MJ([LOJ]A, B, C, MJ(D, F))
+ * <li> A RIGHT JOIN (B JOIN C JOIN D)--> MJ([ROJ]A, B, C, D)
+ * <li> A JOIN B RIGHT JOIN (C JOIN D) --> MJ(A, B, MJ([ROJ]C, D))
+ * </ul>
+ * </p>
+ * <p>
+ * Graphic presentation:
+ * A JOIN B JOIN C LEFT JOIN D JOIN F
+ * left left│
+ * A B C D F ──► A B C │ D F ──► MJ(LOJ A,B,C,MJ(DF)
+ * <p>
+ * A JOIN B RIGHT JOIN C JOIN D JOIN F
+ * right │right
+ * A B C D F ──► A B │ C D F ──► MJ(A,B,MJ(ROJ C,D,F)
+ * <p>
+ * (A JOIN B JOIN C) FULL JOIN (D JOIN F)
+ * full │
+ * A B C D F ──► A B C │ D F ──► MJ(FOJ MJ(A,B,C) MJ(D,F))
+ * </p>
+ */
+ public Plan multiJoinToJoin(MultiJoin multiJoin) {
+ if (multiJoin.arity() == 1) {
+ return PlanUtils.filterOrSelf(multiJoin.getJoinFilter(), multiJoin.child(0));
+ }
+
+ Builder<Plan> builder = ImmutableList.builder();
+ // recursively hanlde multiJoin children.
+ for (Plan child : multiJoin.children()) {
+ if (child instanceof MultiJoin) {
+ MultiJoin childMultiJoin = (MultiJoin) child;
+ builder.add(multiJoinToJoin(childMultiJoin));
+ } else {
+ builder.add(child);
+ }
+ }
+ MultiJoin multiJoinHandleChildren = multiJoin.withChildren(builder.build());
+
+ if (multiJoinHandleChildren.getOnlyJoinType().isPresent()) {
+ List<Expression> leftFilter = Lists.newArrayList();
+ List<Expression> rightFilter = Lists.newArrayList();
+ List<Expression> remainingFilter = Lists.newArrayList();
+ Plan left = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(0, multiJoinHandleChildren.arity() - 1),
+ leftFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ Plan right = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity()),
+ rightFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
Review Comment:
these only use in FULL OUTER JOIN, should add a if branch
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/MultiJoin.java:
##########
@@ -17,189 +17,170 @@
package org.apache.doris.nereids.rules.rewrite.logical;
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.expressions.SlotReference;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.logical.AbstractLogicalPlan;
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
-import org.apache.doris.nereids.util.ExpressionUtils;
-import org.apache.doris.nereids.util.JoinUtils;
-import org.apache.doris.nereids.util.PlanUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableList.Builder;
-import java.util.ArrayList;
-import java.util.HashSet;
import java.util.List;
-import java.util.Map;
import java.util.Optional;
-import java.util.Set;
import java.util.stream.Collectors;
/**
* A MultiJoin represents a join of N inputs (NAry-Join).
* The regular Join represent strictly binary input (Binary-Join).
+ * <p>
+ * One {@link MultiJoin} just contains one {@link JoinType} of SEMI/ANTI/OUTER Join.
+ * <p>
+ * onlyJoinType is Full OUTER JOIN, children.size() == 2.
+ * leftChild [Full OUTER JOIN] rightChild.
Review Comment:
```suggestion
* leftChild [FULL OUTER JOIN] rightChild.
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
Review Comment:
should we put this function into JoinUtils?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
+ // subtree can't specify the end of Pattern. so end can be GroupPlan or Filter
+ if (plan instanceof GroupPlan
+ || (plan instanceof LogicalFilter && plan.child(0) instanceof GroupPlan)) {
+ return plan;
+ }
+
+ List<Plan> inputs = Lists.newArrayList();
+ List<Expression> joinFilter = Lists.newArrayList();
+ List<Expression> notInnerJoinConditions = Lists.newArrayList();
+
+ LogicalJoin<?, ?> join;
+ if (plan instanceof LogicalFilter) {
+ LogicalFilter<?> filter = (LogicalFilter<?>) plan;
+ joinFilter.addAll(ExpressionUtils.extractConjunction(filter.getPredicates()));
+ join = (LogicalJoin<?, ?>) filter.child();
+ } else {
+ join = (LogicalJoin<?, ?>) plan;
+ }
+
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinFilter.addAll(join.getHashJoinConjuncts());
+ joinFilter.addAll(join.getOtherJoinConjuncts());
+ } else {
+ notInnerJoinConditions.addAll(join.getHashJoinConjuncts());
+ notInnerJoinConditions.addAll(join.getOtherJoinConjuncts());
+ }
+
+ // recursively convert children.
+ Plan left = joinToMultiJoin(join.left());
+ Plan right = joinToMultiJoin(join.right());
+
+ boolean changeLeft = join.getJoinType().isRightJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(left, changeLeft)) {
+ MultiJoin leftMultiJoin = (MultiJoin) left;
+ inputs.addAll(leftMultiJoin.children());
+ joinFilter.addAll(leftMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(left);
+ }
+
+ boolean changeRight = join.getJoinType().isLeftJoin()
+ || join.getJoinType().isFullOuterJoin();
+ if (canCombine(right, changeRight)) {
+ MultiJoin rightMultiJoin = (MultiJoin) right;
+ inputs.addAll(rightMultiJoin.children());
+ joinFilter.addAll(rightMultiJoin.getJoinFilter());
+ } else {
+ inputs.add(right);
+ }
+
+ Optional<JoinType> joinType;
+ if (join.getJoinType().isInnerOrCrossJoin()) {
+ joinType = Optional.empty();
+ } else {
+ joinType = Optional.of(join.getJoinType());
+ }
+ return new MultiJoin(
+ inputs,
+ joinFilter,
+ joinType,
+ notInnerJoinConditions);
+ }
+
+ /**
+ * Recursively convert to
+ * {@link MultiJoin}
+ * -->
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * <p>
+ * When all input is CROSS/Inner Join, all join will be flattened.
+ * Otherwise, we will split {join cluster} into multiple {@link MultiJoin}.
+ * <p>
+ * Here are examples of the {@link MultiJoin}s constructed after this rules has been applied.
+ * <p>
+ * simple example:
+ * <ul>
+ * <li>A JOIN B --> MJ(A, B)
+ * <li>A JOIN B JOIN C JOIN D --> MJ(A, B, C, D)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([LOJ/LSJ/LAJ]A, B)
+ * <li>A LEFT (OUTER/SEMI/ANTI) JOIN B --> MJ([ROJ/RSJ/RAJ]A, B)
+ * <li>A FULL JOIN B --> MJ[FOJ](A, B)
+ * </ul>
+ * </p>
+ * <p>
+ * complex example:
+ * <ul>
+ * <li>A LEFT OUTER JOIN (B JOIN C) --> MJ([LOJ]A, MJ(B, C)))
+ * <li>(A JOIN B) LEFT JOIN C --> MJ(A, B, C)
+ * <li>(A LEFT OUTER JOIN B) JOIN C --> MJ(MJ(A, B), C)
+ * <li>A LEFT JOIN (B FULL JOIN C) --> MJ(A, MJ[full](B, C))
+ * <li>(A LEFT JOIN B) FULL JOIN (C RIGHT JOIN D) --> MJ[full](MJ(A, B), MJ(C, D))
+ * </ul>
+ * </p>
+ * more complex example:
+ * <ul>
+ * <li> A JOIN B JOIN C LEFT JOIN D --> MJ([LOJ]A, B, C, D)
+ * <li> A JOIN B JOIN C LEFT JOIN (D JOIN F) --> MJ([LOJ]A, B, C, MJ(D, F))
+ * <li> A RIGHT JOIN (B JOIN C JOIN D)--> MJ([ROJ]A, B, C, D)
+ * <li> A JOIN B RIGHT JOIN (C JOIN D) --> MJ(A, B, MJ([ROJ]C, D))
+ * </ul>
+ * </p>
+ * <p>
+ * Graphic presentation:
+ * A JOIN B JOIN C LEFT JOIN D JOIN F
+ * left left│
+ * A B C D F ──► A B C │ D F ──► MJ(LOJ A,B,C,MJ(DF)
+ * <p>
+ * A JOIN B RIGHT JOIN C JOIN D JOIN F
+ * right │right
+ * A B C D F ──► A B │ C D F ──► MJ(A,B,MJ(ROJ C,D,F)
+ * <p>
+ * (A JOIN B JOIN C) FULL JOIN (D JOIN F)
+ * full │
+ * A B C D F ──► A B C │ D F ──► MJ(FOJ MJ(A,B,C) MJ(D,F))
+ * </p>
+ */
+ public Plan multiJoinToJoin(MultiJoin multiJoin) {
+ if (multiJoin.arity() == 1) {
+ return PlanUtils.filterOrSelf(multiJoin.getJoinFilter(), multiJoin.child(0));
+ }
+
+ Builder<Plan> builder = ImmutableList.builder();
+ // recursively hanlde multiJoin children.
+ for (Plan child : multiJoin.children()) {
+ if (child instanceof MultiJoin) {
+ MultiJoin childMultiJoin = (MultiJoin) child;
+ builder.add(multiJoinToJoin(childMultiJoin));
+ } else {
+ builder.add(child);
+ }
+ }
+ MultiJoin multiJoinHandleChildren = multiJoin.withChildren(builder.build());
+
+ if (multiJoinHandleChildren.getOnlyJoinType().isPresent()) {
+ List<Expression> leftFilter = Lists.newArrayList();
+ List<Expression> rightFilter = Lists.newArrayList();
+ List<Expression> remainingFilter = Lists.newArrayList();
+ Plan left = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(0, multiJoinHandleChildren.arity() - 1),
+ leftFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ Plan right = multiJoinToJoin(new MultiJoin(
+ multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity()),
+ rightFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ if (multiJoinHandleChildren.getOnlyJoinType().get().isLeftJoin()) {
+ right = multiJoinHandleChildren.child(multiJoinHandleChildren.arity() - 1);
+ } else if (multiJoinHandleChildren.getOnlyJoinType().get().isRightJoin()) {
+ left = multiJoinHandleChildren.child(0);
+ }
+
+ // split filter
+ for (Expression expr : multiJoinHandleChildren.getJoinFilter()) {
+ Set<Slot> exprInputSlots = expr.getInputSlots();
+ Preconditions.checkState(!exprInputSlots.isEmpty());
+
+ if (left.getOutputSet().containsAll(exprInputSlots)) {
+ leftFilter.add(expr);
+ } else if (right.getOutputSet().containsAll(exprInputSlots)) {
+ rightFilter.add(expr);
+ } else if (multiJoin.getOutputSet().containsAll(exprInputSlots)) {
+ remainingFilter.add(expr);
+ } else {
+ throw new RuntimeException("invalid expression");
+ }
+ }
+
+ return PlanUtils.filterOrSelf(remainingFilter, new LogicalJoin<>(
+ multiJoinHandleChildren.getOnlyJoinType().get(),
+ ExpressionUtils.EMPTY_CONDITION,
+ multiJoinHandleChildren.getNotInnerJoinConditions(),
+ PlanUtils.filterOrSelf(leftFilter, left), PlanUtils.filterOrSelf(rightFilter, right)));
+ }
+
+ // following this multiJoin just contain INNER/CROSS.
+ List<Expression> joinFilter = multiJoinHandleChildren.getJoinFilter();
+
+ Plan left = multiJoinHandleChildren.child(0);
+ List<Plan> candidates = multiJoinHandleChildren.children().subList(1, multiJoinHandleChildren.arity());
+
+ LogicalJoin<? extends Plan, ? extends Plan> join = findInnerJoin(left, candidates, joinFilter);
+ List<Plan> newInputs = Lists.newArrayList();
+ newInputs.add(join);
+ newInputs.addAll(candidates.stream().filter(plan -> !join.right().equals(plan)).collect(Collectors.toList()));
+
+ joinFilter.removeAll(join.getHashJoinConjuncts());
+ joinFilter.removeAll(join.getOtherJoinConjuncts());
+ return multiJoinToJoin(new MultiJoin(
+ newInputs,
+ joinFilter,
+ Optional.empty(),
+ ExpressionUtils.EMPTY_CONDITION));
+ }
+
+ /**
+ * Returns whether an input can be merged without changing semantics.
+ *
+ * @param input input into a MultiJoin or (GroupPlan|LogicalFilter)
+ * @param changeLeft generate nullable or left not exist.
+ * @return true if the input can be combined into a parent MultiJoin
+ */
+ private static boolean canCombine(Plan input, boolean changeLeft) {
Review Comment:
```suggestion
private static boolean canCombine(Plan input, boolean outputNullable) {
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/MultiJoin.java:
##########
@@ -17,189 +17,170 @@
package org.apache.doris.nereids.rules.rewrite.logical;
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.expressions.SlotReference;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.logical.AbstractLogicalPlan;
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
-import org.apache.doris.nereids.util.ExpressionUtils;
-import org.apache.doris.nereids.util.JoinUtils;
-import org.apache.doris.nereids.util.PlanUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableList.Builder;
-import java.util.ArrayList;
-import java.util.HashSet;
import java.util.List;
-import java.util.Map;
import java.util.Optional;
-import java.util.Set;
import java.util.stream.Collectors;
/**
* A MultiJoin represents a join of N inputs (NAry-Join).
* The regular Join represent strictly binary input (Binary-Join).
+ * <p>
+ * One {@link MultiJoin} just contains one {@link JoinType} of SEMI/ANTI/OUTER Join.
+ * <p>
+ * onlyJoinType is Full OUTER JOIN, children.size() == 2.
+ * leftChild [Full OUTER JOIN] rightChild.
+ * <p>
+ * onlyJoinType is LEFT (OUTER/SEMI/ANTI) JOIN,
+ * children[0, last) [LEFT (OUTER/SEMI/ANTI) JOIN] lastChild.
+ * eg: MJ([LOJ] A, B, C, D) is {A B C} [LOJ] {D}.
+ * <p>
+ * onlyJoinType is RIGHT (OUTER/SEMI/ANTI) JOIN,
+ * firstChild [RIGHT (OUTER/SEMI/ANTI) JOIN] children[1, last].
+ * eg: MJ([ROJ] A, B, C, D) is {A} [ROJ] {B C D}.
*/
-public class MultiJoin extends PlanVisitor<Void, Void> {
+public class MultiJoin extends AbstractLogicalPlan {
/*
* topJoin
* / \ MultiJoin
* bottomJoin C --> / | \
* / \ A B C
* A B
*/
- public final List<Plan> joinInputs = new ArrayList<>();
- public final List<Expression> conjunctsForAllHashJoins = new ArrayList<>();
- private List<Expression> conjunctsKeepInFilter = new ArrayList<>();
-
- /**
- * reorderJoinsAccordingToConditions
- *
- * @return join or filter
- */
- public Optional<Plan> reorderJoinsAccordingToConditions() {
- if (joinInputs.size() >= 2) {
- Plan root = reorderJoinsAccordingToConditions(joinInputs, conjunctsForAllHashJoins);
- return Optional.of(PlanUtils.filterOrSelf(conjunctsKeepInFilter, root));
- }
- return Optional.empty();
+
+ // Push predicates into it.
+ // But joinFilter shouldn't contain predicate which just contains one predicate like `T.key > 1`.
+ // Because these predicate should be pushdown.
+ private final List<Expression> joinFilter;
+ // MultiJoin just contains one OUTER/SEMI/ANTI.
+ private final Optional<JoinType> onlyJoinType;
+ // When contains one OUTER/SEMI/ANTI join, keep separately its condition.
+ private final List<Expression> notInnerJoinConditions;
+
+ // private final List<@Nullable List<NamedExpression>> projFields;
+
+ public MultiJoin(List<Plan> inputs, List<Expression> joinFilter, Optional<JoinType> onlyJoinType,
+ List<Expression> notInnerJoinConditions) {
+ super(PlanType.LOGICAL_MULTI_JOIN, inputs.toArray(new Plan[0]));
+ this.joinFilter = joinFilter;
+ this.onlyJoinType = onlyJoinType;
+ this.notInnerJoinConditions = notInnerJoinConditions;
Review Comment:
Objects.isNotNull?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/MultiJoin.java:
##########
@@ -17,189 +17,170 @@
package org.apache.doris.nereids.rules.rewrite.logical;
-import org.apache.doris.common.Pair;
-import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
-import org.apache.doris.nereids.trees.expressions.SlotReference;
-import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
-import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.logical.AbstractLogicalPlan;
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
-import org.apache.doris.nereids.util.ExpressionUtils;
-import org.apache.doris.nereids.util.JoinUtils;
-import org.apache.doris.nereids.util.PlanUtils;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableList.Builder;
-import java.util.ArrayList;
-import java.util.HashSet;
import java.util.List;
-import java.util.Map;
import java.util.Optional;
-import java.util.Set;
import java.util.stream.Collectors;
/**
* A MultiJoin represents a join of N inputs (NAry-Join).
* The regular Join represent strictly binary input (Binary-Join).
+ * <p>
+ * One {@link MultiJoin} just contains one {@link JoinType} of SEMI/ANTI/OUTER Join.
+ * <p>
+ * onlyJoinType is Full OUTER JOIN, children.size() == 2.
Review Comment:
```suggestion
* onlyJoinType is FULL OUTER JOIN, children.size() == 2.
```
--
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] github-actions[bot] commented on pull request #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on PR #13353:
URL: https://github.com/apache/doris/pull/13353#issuecomment-1278630254
PR approved by anyone and no changes requested.
--
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 #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #13353:
URL: https://github.com/apache/doris/pull/13353#discussion_r994749989
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/ReorderJoin.java:
##########
@@ -37,21 +56,296 @@
* SELECT * FROM t1 JOIN t3 ON t1.id=t3.id JOIN t2 ON t2.id=t3.id
* </pre>
* </p>
- * TODO: This is tested by SSB queries currently, add more `unit` test for this rule
- * when we have a plan building and comparing framework.
+ * Using the {@link MultiJoin} to complete this task.
+ * {Join cluster}: contain multiple join with filter inside.
+ * <ul>
+ * <li> {Join cluster} to MultiJoin</li>
+ * <li> MultiJoin to {Join cluster}</li>
+ * </ul>
*/
public class ReorderJoin extends OneRewriteRuleFactory {
@Override
public Rule build() {
return logicalFilter(subTree(LogicalJoin.class, LogicalFilter.class)).thenApply(ctx -> {
LogicalFilter<Plan> filter = ctx.root;
- if (!ctx.cascadesContext.getConnectContext().getSessionVariable()
- .isEnableNereidsReorderToEliminateCrossJoin()) {
- return filter;
- }
- MultiJoin multiJoin = new MultiJoin();
- filter.accept(multiJoin, null);
- return multiJoin.reorderJoinsAccordingToConditions().orElse(filter);
+
+ MultiJoin multiJoin = (MultiJoin) joinToMultiJoin(filter);
+ Plan plan = multiJoinToJoin(multiJoin);
+ return plan;
}).toRule(RuleType.REORDER_JOIN);
}
+
+ /**
+ * Recursively convert to
+ * {@link LogicalJoin} or
+ * {@link LogicalFilter}--{@link LogicalJoin}
+ * --> {@link MultiJoin}
+ */
+ public Plan joinToMultiJoin(Plan plan) {
Review Comment:
shouldn't, it's not common function
--
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 merged pull request #13353: [feature](Nereids): use Multi join to rearrange join to eliminate cross join by using predicate.
Posted by GitBox <gi...@apache.org>.
jackwener merged PR #13353:
URL: https://github.com/apache/doris/pull/13353
--
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