englefly commented on code in PR #66535: URL: https://github.com/apache/doris/pull/66535#discussion_r3781843693
########## fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/ConvertInnerJoinToSemiJoin.java: ########## @@ -0,0 +1,130 @@ +// 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 left semi join when the inner join is only used as an + * existence filter. Three conditions must be satisfied at the same time: + * + * 1. The right side columns of the join do not leak: every column referenced above the + * join comes from the left side, i.e. the right 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. + * + * 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> + * + * The conversion avoids row multiplication (the output row count stays the left side + * cardinality instead of being multiplied by the average number of right side matches), + * and lets the right side be scanned/broadcast with only the join key columns. + */ +public class ConvertInnerJoinToSemiJoin implements RewriteRuleFactory { + @Override + public List<Rule> buildRules() { + return ImmutableList.of( + // Aggregate -> InnerJoin + logicalAggregate(innerLogicalJoin() + .when(this::canConvertToSemiJoin)) + .when(this::isDistinctLikeAggregate) + .thenApply(ctx -> convert(ctx.root, ctx.root.child())) + .toRule(RuleType.CONVERT_INNER_JOIN_TO_SEMI_JOIN), + // Aggregate -> Project -> InnerJoin, where the project is a pure slot projection + logicalAggregate(logicalProject(innerLogicalJoin() + .when(this::canConvertToSemiJoin)) + .when(Project::isAllSlots)) + .when(this::isDistinctLikeAggregate) + .thenApply(ctx -> convert(ctx.root, ctx.root.child(), ctx.root.child().child())) + .toRule(RuleType.CONVERT_INNER_JOIN_TO_SEMI_JOIN) + ); + } + + /** + * 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(); + } + + /** + * Condition 3: the aggregate is a DISTINCT-like aggregate, i.e. its group-by keys + * cover exactly its output columns, so it collapses duplicate rows and the row + * multiplicity change of inner-join -> semi-join does not affect the final result. + */ + private boolean isDistinctLikeAggregate(LogicalAggregate<?> agg) { + Set<ExprId> groupBySlotIds = agg.getGroupByExpressions().stream() + .filter(Slot.class::isInstance) + .map(expr -> ((Slot) expr).getExprId()) + .collect(Collectors.toSet()); + Set<ExprId> outputSlotIds = agg.getOutput().stream() + .map(Slot::getExprId) Review Comment: 这不是问题. 没有order by 时 limit 10 输出的结果本来就不是确定的哪10行 -- 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]
