morrySnow commented on code in PR #11531: URL: https://github.com/apache/doris/pull/11531#discussion_r938753103
########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomProject.java: ########## @@ -0,0 +1,61 @@ +// 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.annotation.Developing; +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.plans.logical.LogicalJoin; +import org.apache.doris.nereids.trees.plans.logical.LogicalProject; + +/** + * Rule for change inner join left associative to right. + */ +@Developing +public class JoinLAsscomProject extends OneExplorationRuleFactory { + /* + * topJoin newTopJoin + * / \ / \ + * project C newLeftProject newRightProject + * / ──► / \ + * bottomJoin newBottomJoin B + * / \ / \ + * A B A C + */ + @Override + public Rule build() { + return logicalJoin(logicalProject(logicalJoin()), groupPlan()) + .when(JoinLAsscomHelper::check) + .when(join -> join.getJoinType().isInnerJoin() || join.getJoinType().isLeftOuterJoin() + && (join.left().child().getJoinType().isInnerJoin() || join.left().child().getJoinType() + .isLeftOuterJoin())) + .then(topJoin -> { + LogicalProject<LogicalJoin<GroupPlan, GroupPlan>> project = topJoin.left(); Review Comment: no need to have this local variable ########## fe/fe-core/src/main/java/org/apache/doris/nereids/util/Utils.java: ########## @@ -107,4 +110,13 @@ public static <E> boolean equalsIgnoreOrder(List<E> one, List<E> other) { } return new HashSet<>(one).containsAll(other) && new HashSet<>(other).containsAll(one); } + + /** + * Get SlotReference from output of plam. + * Warning, plan must have bound, because exists Slot Cast to SlotReference. + */ + public static List<SlotReference> getOutputSlotReference(Plan plan) { + return plan.getOutput().stream().map(slot -> (SlotReference) slot) Review Comment: ```suggestion return plan.getOutput().stream().map(SlotReference.class::cast) ``` ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; Review Comment: we need a comment to describe plan tree ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) Review Comment: we should do `topJoinOnClauseConjunct.collect(SlotReference.class::isInstance)` only once outside if statement ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { Review Comment: ```suggestion public JoinLAsscomHelper(LogicalJoin<? extends Plan, GroupPlan> topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { ``` then type casts below are not needed ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { Review Comment: same as constructor ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), bOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), cOutputSlots) + ) { + return false; + } + } + List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunction( + bottomJoinOnClause); + + List<Expression> allOnCondition = Lists.newArrayList(); + allOnCondition.addAll(topJoinOnClauseConjuncts); + allOnCondition.addAll(bottomJoinOnClauseConjuncts); + + List<SlotReference> newBottomJoinSlots = Lists.newArrayList(); + newBottomJoinSlots.addAll(aOutputSlots); + newBottomJoinSlots.addAll(cOutputSlots); + + for (Expression onCondition : allOnCondition) { + List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance); + if (new HashSet<>(newBottomJoinSlots).containsAll(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. + // (A & B) & C -> (A & C) & B. + // (A & C) will be cross join (newBottomJoinOnCondition is empty) + if (newBottomJoinOnCondition.isEmpty() || newTopJoinOnCondition.isEmpty()) { Review Comment: we need to do infer predicate later to process `a join b on a.id = b.id join c on b.id = c.id` it could be transform to `a join c on a.id = c.id join b on b.id = c.id` ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), bOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), cOutputSlots) + ) { + return false; + } + } + List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunction( + bottomJoinOnClause); + + List<Expression> allOnCondition = Lists.newArrayList(); + allOnCondition.addAll(topJoinOnClauseConjuncts); + allOnCondition.addAll(bottomJoinOnClauseConjuncts); + + List<SlotReference> newBottomJoinSlots = Lists.newArrayList(); + newBottomJoinSlots.addAll(aOutputSlots); + newBottomJoinSlots.addAll(cOutputSlots); + + for (Expression onCondition : allOnCondition) { + List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance); + if (new HashSet<>(newBottomJoinSlots).containsAll(slots)) { Review Comment: we could make `newBottomJoinSlots` as a Set directly when we new it. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), bOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), cOutputSlots) + ) { + return false; + } + } + List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunction( + bottomJoinOnClause); Review Comment: no need wrap ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), bOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), cOutputSlots) + ) { + return false; + } + } + List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunction( + bottomJoinOnClause); + + List<Expression> allOnCondition = Lists.newArrayList(); + allOnCondition.addAll(topJoinOnClauseConjuncts); + allOnCondition.addAll(bottomJoinOnClauseConjuncts); + + List<SlotReference> newBottomJoinSlots = Lists.newArrayList(); + newBottomJoinSlots.addAll(aOutputSlots); + newBottomJoinSlots.addAll(cOutputSlots); + + for (Expression onCondition : allOnCondition) { + List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance); + if (new HashSet<>(newBottomJoinSlots).containsAll(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. + // (A & B) & C -> (A & C) & B. + // (A & C) will be cross join (newBottomJoinOnCondition is empty) + if (newBottomJoinOnCondition.isEmpty() || newTopJoinOnCondition.isEmpty()) { + return false; + } + + return true; + } + + + /** + * Get projectExpr of left and right. + * Just for project-inside. + */ + private Pair<List<NamedExpression>, List<NamedExpression>> getProjectExprs() { + Preconditions.checkArgument(topJoin.left() instanceof LogicalProject); + LogicalProject project = (LogicalProject) topJoin.left(); + + 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 (new HashSet<>(bOutputSlots).containsAll(usedSlotRefs)) { + newRightProjectExprs.add(projectExpr); + } else { + newLeftProjectExpr.add(projectExpr); + } + } + + return new Pair<>(newLeftProjectExpr, newRightProjectExprs); + } + + + private LogicalJoin<GroupPlan, GroupPlan> newBottomJoin() { + return new LogicalJoin( + bottomJoin.getJoinType(), + Optional.of(ExpressionUtils.and(newBottomJoinOnCondition)), + a, c); + } + + /** + * Create topJoin for project-inside. + */ + public LogicalJoin newProjectTopJoin() { + List<NamedExpression> newLeftProjectExpr = getProjectExprs().first; + List<NamedExpression> newRightProjectExprs = getProjectExprs().second; + + // no right project + if (newRightProjectExprs.size() == 0) { Review Comment: ```suggestion if (newRightProjectExprs.isEmpty()) { ``` ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), bOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), cOutputSlots) + ) { + return false; + } + } + List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunction( + bottomJoinOnClause); + + List<Expression> allOnCondition = Lists.newArrayList(); + allOnCondition.addAll(topJoinOnClauseConjuncts); + allOnCondition.addAll(bottomJoinOnClauseConjuncts); + + List<SlotReference> newBottomJoinSlots = Lists.newArrayList(); + newBottomJoinSlots.addAll(aOutputSlots); + newBottomJoinSlots.addAll(cOutputSlots); + + for (Expression onCondition : allOnCondition) { + List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance); + if (new HashSet<>(newBottomJoinSlots).containsAll(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. + // (A & B) & C -> (A & C) & B. + // (A & C) will be cross join (newBottomJoinOnCondition is empty) + if (newBottomJoinOnCondition.isEmpty() || newTopJoinOnCondition.isEmpty()) { + return false; + } + + return true; + } + + + /** + * Get projectExpr of left and right. + * Just for project-inside. + */ + private Pair<List<NamedExpression>, List<NamedExpression>> getProjectExprs() { + Preconditions.checkArgument(topJoin.left() instanceof LogicalProject); + LogicalProject project = (LogicalProject) topJoin.left(); + + 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 (new HashSet<>(bOutputSlots).containsAll(usedSlotRefs)) { + newRightProjectExprs.add(projectExpr); + } else { + newLeftProjectExpr.add(projectExpr); + } + } + + return new Pair<>(newLeftProjectExpr, newRightProjectExprs); + } + + + private LogicalJoin<GroupPlan, GroupPlan> newBottomJoin() { + return new LogicalJoin( + bottomJoin.getJoinType(), + Optional.of(ExpressionUtils.and(newBottomJoinOnCondition)), + a, c); + } + + /** + * Create topJoin for project-inside. + */ + public LogicalJoin newProjectTopJoin() { + List<NamedExpression> newLeftProjectExpr = getProjectExprs().first; + List<NamedExpression> newRightProjectExprs = getProjectExprs().second; + + // no right project + if (newRightProjectExprs.size() == 0) { + return new LogicalJoin( + topJoin.getJoinType(), + Optional.of(ExpressionUtils.and(newTopJoinOnCondition)), + newBottomJoin(), b); Review Comment: miss left project exprs? ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), bOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), cOutputSlots) + ) { + return false; + } + } + List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunction( + bottomJoinOnClause); + + List<Expression> allOnCondition = Lists.newArrayList(); + allOnCondition.addAll(topJoinOnClauseConjuncts); + allOnCondition.addAll(bottomJoinOnClauseConjuncts); + + List<SlotReference> newBottomJoinSlots = Lists.newArrayList(); + newBottomJoinSlots.addAll(aOutputSlots); + newBottomJoinSlots.addAll(cOutputSlots); + + for (Expression onCondition : allOnCondition) { + List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance); + if (new HashSet<>(newBottomJoinSlots).containsAll(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. + // (A & B) & C -> (A & C) & B. + // (A & C) will be cross join (newBottomJoinOnCondition is empty) + if (newBottomJoinOnCondition.isEmpty() || newTopJoinOnCondition.isEmpty()) { + return false; + } + + return true; + } + + + /** + * Get projectExpr of left and right. + * Just for project-inside. + */ + private Pair<List<NamedExpression>, List<NamedExpression>> getProjectExprs() { + Preconditions.checkArgument(topJoin.left() instanceof LogicalProject); + LogicalProject project = (LogicalProject) topJoin.left(); + + 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 (new HashSet<>(bOutputSlots).containsAll(usedSlotRefs)) { Review Comment: new set outside forloop ########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/join/JoinLAsscomHelper.java: ########## @@ -0,0 +1,219 @@ +// 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.common.Pair; +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.GroupPlan; +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.HashSet; +import java.util.List; +import java.util.Optional; + +/** + * Common function for JoinLAsscom + */ +public class JoinLAsscomHelper { + private final LogicalJoin topJoin; + private final LogicalJoin<GroupPlan, GroupPlan> bottomJoin; + private final Plan a; + private final Plan b; + private final Plan c; + + private final Expression topJoinOnClause; + private final Expression bottomJoinOnClause; + + private final List<SlotReference> aOutputSlots; + private final List<SlotReference> bOutputSlots; + private final List<SlotReference> cOutputSlots; + + private final List<Expression> newBottomJoinOnCondition = Lists.newArrayList(); + private final List<Expression> newTopJoinOnCondition = Lists.newArrayList(); + + /** + * Init plan and output. + */ + public JoinLAsscomHelper(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + this.topJoin = topJoin; + this.bottomJoin = bottomJoin; + + a = bottomJoin.left(); + b = bottomJoin.right(); + c = (Plan) topJoin.right(); + + Preconditions.checkArgument(topJoin.getCondition().isPresent(), "topJoin onClause must be present."); + topJoinOnClause = (Expression) topJoin.getCondition().get(); + Preconditions.checkArgument(bottomJoin.getCondition().isPresent(), "bottomJoin onClause must be present."); + bottomJoinOnClause = (Expression) bottomJoin.getCondition().get(); + + aOutputSlots = Utils.getOutputSlotReference(a); + bOutputSlots = Utils.getOutputSlotReference(b); + cOutputSlots = Utils.getOutputSlotReference(c); + } + + public static JoinLAsscomHelper of(LogicalJoin topJoin, LogicalJoin<GroupPlan, GroupPlan> bottomJoin) { + return new JoinLAsscomHelper(topJoin, bottomJoin); + } + + /** + * Get the onCondition of newTopJoin and newBottomJoin. + */ + public boolean initJoinOnCondition() { + List<Expression> topJoinOnClauseConjuncts = ExpressionUtils.extractConjunction(topJoinOnClause); + for (Expression topJoinOnClauseConjunct : topJoinOnClauseConjuncts) { + // Ignore join with some OnClause like: + // Join C = B + A for above example. + if (ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), aOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), bOutputSlots) + && ExpressionUtils.isIntersecting( + topJoinOnClauseConjunct.collect(SlotReference.class::isInstance), cOutputSlots) + ) { + return false; + } + } + List<Expression> bottomJoinOnClauseConjuncts = ExpressionUtils.extractConjunction( + bottomJoinOnClause); + + List<Expression> allOnCondition = Lists.newArrayList(); + allOnCondition.addAll(topJoinOnClauseConjuncts); + allOnCondition.addAll(bottomJoinOnClauseConjuncts); + + List<SlotReference> newBottomJoinSlots = Lists.newArrayList(); + newBottomJoinSlots.addAll(aOutputSlots); + newBottomJoinSlots.addAll(cOutputSlots); + + for (Expression onCondition : allOnCondition) { + List<SlotReference> slots = onCondition.collect(SlotReference.class::isInstance); + if (new HashSet<>(newBottomJoinSlots).containsAll(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. + // (A & B) & C -> (A & C) & B. + // (A & C) will be cross join (newBottomJoinOnCondition is empty) + if (newBottomJoinOnCondition.isEmpty() || newTopJoinOnCondition.isEmpty()) { + return false; + } + + return true; + } + + + /** + * Get projectExpr of left and right. + * Just for project-inside. + */ + private Pair<List<NamedExpression>, List<NamedExpression>> getProjectExprs() { + Preconditions.checkArgument(topJoin.left() instanceof LogicalProject); + LogicalProject project = (LogicalProject) topJoin.left(); + + 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 (new HashSet<>(bOutputSlots).containsAll(usedSlotRefs)) { + newRightProjectExprs.add(projectExpr); + } else { + newLeftProjectExpr.add(projectExpr); + } + } + + return new Pair<>(newLeftProjectExpr, newRightProjectExprs); + } + + + private LogicalJoin<GroupPlan, GroupPlan> newBottomJoin() { + return new LogicalJoin( + bottomJoin.getJoinType(), + Optional.of(ExpressionUtils.and(newBottomJoinOnCondition)), + a, c); + } + + /** + * Create topJoin for project-inside. + */ + public LogicalJoin newProjectTopJoin() { Review Comment: i think the better code organization is according whether right project is empty to new a top right child and then according whether left project is empty to new top left child at last new top node -- 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-unsubscr...@doris.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org For additional commands, e-mail: commits-h...@doris.apache.org
