englefly commented on code in PR #66535: URL: https://github.com/apache/doris/pull/66535#discussion_r3803251488
########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/ConvertInnerJoinToSemiJoin.java: ########## @@ -0,0 +1,151 @@ +// 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.rewrite; + +import org.apache.doris.nereids.rules.Rule; +import org.apache.doris.nereids.rules.RuleType; +import org.apache.doris.nereids.trees.expressions.ExprId; +import org.apache.doris.nereids.trees.expressions.Slot; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.algebra.Project; +import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate; +import org.apache.doris.nereids.trees.plans.logical.LogicalJoin; +import org.apache.doris.nereids.trees.plans.logical.LogicalProject; + +import com.google.common.collect.ImmutableList; + +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +/** + * Convert an inner join to a semi join when the inner join is only used as an + * existence filter. The output side of the join (the side whose columns are consumed + * above the join) becomes the probe side of the semi join: a left semi join when the + * output side is the left child, a right semi join when it is the right child. Three + * conditions must be satisfied at the same time: + * + * 1. The other side columns of the join do not leak: every column referenced above the + * join comes from the output side, i.e. the other side is only used in the join + * conditions. (the "existence filter" property) + * 2. All join conditions are equal conjuncts: hashJoinConjuncts is not empty and + * otherJoinConjuncts is empty, so the join is a pure equi-join. + * 3. There is a deduplication guarantee above the join: the aggregate that consumes the + * join output is a DISTINCT-like aggregate, i.e. its group-by keys cover exactly its + * output columns. Otherwise, in bag semantics, the row multiplication of an inner + * join (a left row matching N right rows produces N copies) would change the result + * after the conversion, because a semi join never multiplies rows. + * + * All three conditions are enforced in the rule's match predicates, so the rule only + * fires when the conversion actually applies. + * + * Example: + * <pre> + * select distinct a1.* from a1, a5 + * where a1.lot_id = a5.lot_id and a1.ope_no = a5.ope_no and ... + * ======> + * select distinct a1.* from a1 left semi join a5 + * on a1.lot_id = a5.lot_id and a1.ope_no = a5.ope_no and ... + * </pre> + * + * and symmetrically, when only the right side columns are consumed above the join: + * <pre> + * select distinct a5.* from a1, a5 + * where a1.lot_id = a5.lot_id and a1.ope_no = a5.ope_no and ... + * ======> + * select distinct a5.* from a1 right semi join a5 + * on a1.lot_id = a5.lot_id and a1.ope_no = a5.ope_no and ... + * </pre> + * + * The conversion avoids row multiplication (the output row count stays the output side + * cardinality instead of being multiplied by the average number of other side matches), + * and lets the other side be scanned/broadcast with only the join key columns. + */ +public class ConvertInnerJoinToSemiJoin implements RewriteRuleFactory { + @Override + public List<Rule> buildRules() { + ImmutableList.Builder<Rule> rules = ImmutableList.builder(); + for (boolean outputSideIsLeft : new boolean[] {true, false}) { + JoinType semiJoinType = outputSideIsLeft ? JoinType.LEFT_SEMI_JOIN : JoinType.RIGHT_SEMI_JOIN; + // Aggregate -> InnerJoin + rules.add(logicalAggregate(innerLogicalJoin() + .when(this::canConvertToSemiJoin)) + .when(this::isDistinctLikeAggregate) + .when(agg -> columnsDoNotLeak(agg.child(), outputSideIsLeft, agg.getInputSlots())) + .thenApply(ctx -> convert(ctx.root, ctx.root.child(), semiJoinType)) + .toRule(RuleType.CONVERT_INNER_JOIN_TO_SEMI_JOIN)); + // Aggregate -> Project -> InnerJoin, where the project is a pure slot projection + rules.add(logicalAggregate(logicalProject(innerLogicalJoin() + .when(this::canConvertToSemiJoin)) + .when(Project::isAllSlots)) + .when(this::isDistinctLikeAggregate) + .when(agg -> columnsDoNotLeak(agg.child().child(), outputSideIsLeft, + agg.child().getInputSlots())) + .thenApply(ctx -> convert(ctx.root, ctx.root.child(), ctx.root.child().child(), semiJoinType)) + .toRule(RuleType.CONVERT_INNER_JOIN_TO_SEMI_JOIN)); + } + return rules.build(); + } + + /** + * Condition 2: the join is a pure equi-join (hash conjuncts exist and no other + * conjuncts), and it is not a mark join. + */ + private boolean canConvertToSemiJoin(LogicalJoin<?, ?> join) { + return !join.isMarkJoin() + && !join.getHashJoinConjuncts().isEmpty() + && join.getOtherJoinConjuncts().isEmpty(); Review Comment: 不用 规则用的是 innerLogicalJoin() 模式, ASOF join 解析后恒为 ASOF_LEFT_INNER_JOIN/ASOF_RIGHT_INNER_JOIN, 不匹配 -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
