morrySnow commented on code in PR #66535: URL: https://github.com/apache/doris/pull/66535#discussion_r3765974624
########## fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/ConvertInnerJoinToSemiJoinTest.java: ########## @@ -0,0 +1,119 @@ +// 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.trees.plans.JoinType; +import org.apache.doris.nereids.util.MemoPatternMatchSupported; +import org.apache.doris.nereids.util.PlanChecker; +import org.apache.doris.utframe.TestWithFeService; + +import org.junit.jupiter.api.Test; + +class ConvertInnerJoinToSemiJoinTest extends TestWithFeService implements MemoPatternMatchSupported { + @Override + protected void runBeforeAll() throws Exception { + createDatabase("test"); + connectContext.setDatabase("test"); + connectContext.getSessionVariable().setDisableNereidsRules("PRUNE_EMPTY_PARTITION"); + createTables( + "CREATE TABLE IF NOT EXISTS t1 (\n" + + " id1 int not null,\n" + + " v1 int not null\n" + + ")\n" + + "DUPLICATE KEY(id1)\n" + + "DISTRIBUTED BY HASH(id1) BUCKETS 10\n" + + "PROPERTIES (\"replication_num\" = \"1\")\n", + "CREATE TABLE IF NOT EXISTS t2 (\n" + + " id2 int not null,\n" + + " v2 int not null\n" + + ")\n" + + "DUPLICATE KEY(id2)\n" + + "DISTRIBUTED BY HASH(id2) BUCKETS 10\n" + + "PROPERTIES (\"replication_num\" = \"1\")\n"); + } + + // select distinct t1.id1 from t1 join t2 on t1.id1 = t2.id2 + // t2's columns are not used above the join, the join keys are equal conjuncts, + // and the DISTINCT aggregate dedups the output: + // inner join -> left semi join + @Test + void testConvertInnerJoinToSemiJoin() throws Exception { + PlanChecker.from(connectContext) + .analyze("select distinct t1.id1 from t1 join t2 on t1.id1 = t2.id2") + .rewrite() + .anyMatches(logicalJoin().when(j -> j.getJoinType() == JoinType.LEFT_SEMI_JOIN)) + .nonMatch(logicalJoin().when(j -> j.getJoinType() == JoinType.INNER_JOIN)) + .printlnTree(); + } + + // t2.id2 is projected above the join, so the right side columns leak: + // keep inner join + @Test + void testNotConvertWhenRightSideColumnsUsed() throws Exception { + PlanChecker.from(connectContext) + .analyze("select distinct t1.id1, t2.id2 from t1 join t2 on t1.id1 = t2.id2") + .rewrite() + .nonMatch(logicalJoin().when(j -> j.getJoinType() == JoinType.LEFT_SEMI_JOIN)) + .printlnTree(); + } + + // no DISTINCT (or group-by) dedup guarantee above the join: + // in bag semantics inner join row multiplication matters, keep inner join + @Test + void testNotConvertWithoutDistinct() throws Exception { + PlanChecker.from(connectContext) + .analyze("select t1.id1 from t1 join t2 on t1.id1 = t2.id2") + .rewrite() + .nonMatch(logicalJoin().when(j -> j.getJoinType() == JoinType.LEFT_SEMI_JOIN)) + .printlnTree(); + } + + // non-equi join condition goes into otherJoinConjuncts: + // not a pure equi-join, keep inner join + @Test + void testNotConvertWithNonEquiCondition() throws Exception { + PlanChecker.from(connectContext) + .analyze("select distinct t1.id1 from t1 join t2 on t1.id1 > t2.id2") + .rewrite() + .nonMatch(logicalJoin().when(j -> j.getJoinType() == JoinType.LEFT_SEMI_JOIN)) + .printlnTree(); + } + + // aggregation with aggregate functions must NOT be converted: + // count(*) observes the input row multiplicity, changing it would be wrong + @Test + void testNotConvertWithAggregateFunction() throws Exception { + PlanChecker.from(connectContext) + .analyze("select t1.id1, count(*) from t1 join t2 on t1.id1 = t2.id2 group by t1.id1") + .rewrite() + .nonMatch(logicalJoin().when(j -> j.getJoinType() == JoinType.LEFT_SEMI_JOIN)) + .printlnTree(); + } + + // <=> (NullSafeEqual) is an EqualPredicate: FindHashConditionForJoin extracts it into + // hashJoinConjuncts, so the inner join can also be converted to left semi join + @Test + void testConvertWithNullSafeEqual() throws Exception { Review Comment: This test only asserts the logical plan shape for the `<=>` case (`anyMatches`/`nonMatch` on the join type). The conversion changes the physical join type, so null-safe equal (`<=>`) now also runs through the *semi join* output path of the hash join. While the BE hash join applies the per-conjunct null-safe flag (`_is_null_safe_eq_join`) in a join-type-agnostic way, this specific combination (null-safe equal + semi join probe) is only covered by this logical check. Consider adding a small result-verification test (e.g. a regression case with NULL join keys asserting the actual result rows), so execution-level correctness of `select distinct ... join ... on ... <=> ...` is pinned down. ########## fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/ConvertInnerJoinToSemiJoinTest.java: ########## @@ -0,0 +1,119 @@ +// 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.trees.plans.JoinType; +import org.apache.doris.nereids.util.MemoPatternMatchSupported; +import org.apache.doris.nereids.util.PlanChecker; +import org.apache.doris.utframe.TestWithFeService; + +import org.junit.jupiter.api.Test; + +class ConvertInnerJoinToSemiJoinTest extends TestWithFeService implements MemoPatternMatchSupported { + @Override + protected void runBeforeAll() throws Exception { + createDatabase("test"); + connectContext.setDatabase("test"); + connectContext.getSessionVariable().setDisableNereidsRules("PRUNE_EMPTY_PARTITION"); + createTables( + "CREATE TABLE IF NOT EXISTS t1 (\n" + + " id1 int not null,\n" + + " v1 int not null\n" + + ")\n" + + "DUPLICATE KEY(id1)\n" + + "DISTRIBUTED BY HASH(id1) BUCKETS 10\n" + + "PROPERTIES (\"replication_num\" = \"1\")\n", + "CREATE TABLE IF NOT EXISTS t2 (\n" + + " id2 int not null,\n" + + " v2 int not null\n" + + ")\n" + + "DUPLICATE KEY(id2)\n" + + "DISTRIBUTED BY HASH(id2) BUCKETS 10\n" + + "PROPERTIES (\"replication_num\" = \"1\")\n"); + } + + // select distinct t1.id1 from t1 join t2 on t1.id1 = t2.id2 + // t2's columns are not used above the join, the join keys are equal conjuncts, + // and the DISTINCT aggregate dedups the output: + // inner join -> left semi join + @Test + void testConvertInnerJoinToSemiJoin() throws Exception { Review Comment: All six tests exercise the direct `Aggregate -> Join` pattern (or its projection variant incidentally). The second rule pattern `Aggregate -> Project(all slots) -> Join` - which is the one that matters for the headline case `select distinct a1.* from a1, a5 ...` (column pruning inserts an all-slot project between the aggregate and the join) - is not covered by an explicit unit test. If `select distinct t1.id1 ...` happens to produce the direct pattern, the second pattern could regress without any unit test noticing (only the shape_check .out regeneration would catch it). A dedicated test (e.g. a query where a project between the DISTINCT aggregate and the join is guaranteed, or asserting the plan contains the project) would close the gap. Also, the `printlnTree()` calls in each test look like debug leftovers and can be dropped. ########## 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: The dedup guarantee here is set-equality: `groupBySlotIds.equals(outputSlotIds)` proves the aggregate collapses the join output to a set, which makes the conversion row-count safe. However, it does not preserve the *order* in which the dedup rows are produced. For queries with a LIMIT on top of the DISTINCT and no ORDER BY, e.g. ```sql select distinct t1.id1 from t1 join t2 on t1.id1 = t2.id2 limit 10 ``` with more than 10 distinct values, the inner join feeds the dedup aggregate with the join output (each left row multiplied by its right-side matches), while the semi join feeds it with left-side rows only. The insertion order into the distinct hash/sort differs, so the rows returned by `limit 10` can change after the conversion (both answers are "correct" per SQL since LIMIT without ORDER BY is non-deterministic, but it is a user-visible behavior change). This is especially relevant because `limit` is a very common companion of `select distinct` in practice. The PR description states "Behavior changed: No" - for such queries the statement does not hold. Worth either documenting in the PR/release note, or restricting the conversion when a Limit/TopN without order keys sits above the aggregate. ########## 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) + .collect(Collectors.toSet()); + return groupBySlotIds.equals(outputSlotIds); + } + + /** Aggregate -> Join */ + private Plan convert(LogicalAggregate<?> agg, LogicalJoin<?, ?> join) { + // Condition 1: the right side columns do not leak above the join. Review Comment: When condition 1 fails, the rule has already matched (aggregate is DISTINCT-like, join is a pure equi-join) and returns the plan unchanged. The rewrite framework tolerates a matched-but-unchanged result (it compares by reference/deepEquals and does not loop), so this is not a bug, but it means the rule "fires" without doing anything on every `DISTINCT-like agg -> inner join` plan whose right columns leak. Moving the condition-1 check into a `.when()` predicate (e.g. `join.when(j -> j.left().getOutputSet().containsAll(agg.getInputSlots()))`) would keep match semantics clean and avoid the no-op application, which is the convention used by neighboring rules. -- 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]
