This is an automated email from the ASF dual-hosted git repository.
morrysnow pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 45fd23c153 [feature](Nereids) transform outer join to anti join with
is null condition (#23833)
45fd23c153 is described below
commit 45fd23c15373228ac129ad1cb1e0a2f2892dc6c6
Author: 谢健 <[email protected]>
AuthorDate: Wed Sep 6 11:31:57 2023 +0800
[feature](Nereids) transform outer join to anti join with is null condition
(#23833)
create table t1(c1 int not null, c2 int not null) distributed by hash(c1)
buckets 3 PROPERTIES ("replication_allocation" = "tag.location.default: 1");
create table t2(c1 int not null, c2 int not null) distributed by hash(c1)
buckets 3 PROPERTIES ("replication_allocation" = "tag.location.default: 1");
select t2.* from t1 left outer t2 where t2.c1 is null
==>
t1 right anti t2
---
.../org/apache/doris/nereids/rules/RuleSet.java | 2 +
.../org/apache/doris/nereids/rules/RuleType.java | 1 +
.../rewrite/TransformOuterJoinToAntiJoin.java | 106 +++++++++++++++++++++
.../apache/doris/nereids/trees/plans/JoinType.java | 8 ++
.../org/apache/doris/nereids/util/TypeUtils.java | 14 +++
.../rewrite/TransformOuterJoinToAntiJoinTest.java | 75 +++++++++++++++
.../transform_outer_join_to_anti.groovy | 66 +++++++++++++
7 files changed, 272 insertions(+)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleSet.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleSet.java
index 8304fb801a..64dc7f4f6f 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleSet.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleSet.java
@@ -89,6 +89,7 @@ import
org.apache.doris.nereids.rules.rewrite.PushdownFilterThroughSort;
import org.apache.doris.nereids.rules.rewrite.PushdownFilterThroughWindow;
import org.apache.doris.nereids.rules.rewrite.PushdownJoinOtherCondition;
import org.apache.doris.nereids.rules.rewrite.PushdownProjectThroughLimit;
+import org.apache.doris.nereids.rules.rewrite.TransformOuterJoinToAntiJoin;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableList.Builder;
@@ -131,6 +132,7 @@ public class RuleSet {
new PushdownFilterThroughWindow(),
new PushdownProjectThroughLimit(),
new EliminateOuterJoin(),
+ new TransformOuterJoinToAntiJoin(),
new MergeProjects(),
new MergeFilters(),
new MergeGenerates(),
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
index ac8abbf6d1..7add24d399 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
@@ -202,6 +202,7 @@ public enum RuleType {
ELIMINATE_OUTER_JOIN(RuleTypeClass.REWRITE),
ELIMINATE_DEDUP_JOIN_CONDITION(RuleTypeClass.REWRITE),
ELIMINATE_NULL_AWARE_LEFT_ANTI_JOIN(RuleTypeClass.REWRITE),
+ TRANSFORM_OUTER_JOIN_TO_ANTI(RuleTypeClass.REWRITE),
FIND_HASH_CONDITION_FOR_JOIN(RuleTypeClass.REWRITE),
MATERIALIZED_INDEX_AGG_SCAN(RuleTypeClass.REWRITE),
MATERIALIZED_INDEX_AGG_FILTER_SCAN(RuleTypeClass.REWRITE),
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/TransformOuterJoinToAntiJoin.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/TransformOuterJoinToAntiJoin.java
new file mode 100644
index 0000000000..43a177b763
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/TransformOuterJoinToAntiJoin.java
@@ -0,0 +1,106 @@
+// 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.Expression;
+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.logical.LogicalFilter;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+import org.apache.doris.nereids.util.TypeUtils;
+
+import com.google.common.collect.ImmutableSet;
+
+import java.util.Set;
+import java.util.stream.Collectors;
+
+/**
+ * project(A.*)
+ * - filter(B.slot is null)
+ * - LeftOuterJoin(A, B)
+ * ==============================>
+ * project(A.*)
+ * - LeftAntiJoin(A, B)
+ */
+public class TransformOuterJoinToAntiJoin extends OneRewriteRuleFactory {
+
+ @Override
+ public Rule build() {
+ return logicalProject(logicalFilter(logicalJoin()
+ .when(join -> join.getJoinType().isOuterJoin())))
+ .then(this::toAntiJoin)
+ .toRule(RuleType.TRANSFORM_OUTER_JOIN_TO_ANTI);
+ }
+
+ private Plan toAntiJoin(LogicalProject<LogicalFilter<LogicalJoin<Plan,
Plan>>> project) {
+ LogicalFilter<LogicalJoin<Plan, Plan>> filter = project.child();
+ LogicalJoin<Plan, Plan> join = filter.child();
+
+ boolean leftOutput =
join.left().getOutputSet().containsAll(project.getInputSlots());
+ boolean rightOutput =
join.right().getOutputSet().containsAll(project.getInputSlots());
+
+ if (!leftOutput && !rightOutput) {
+ return null;
+ }
+
+ Set<Slot> alwaysNullSlots = filter.getConjuncts().stream()
+ .filter(p -> TypeUtils.isNull(p).isPresent())
+ .flatMap(p -> p.getInputSlots().stream())
+ .collect(Collectors.toSet());
+ Set<Slot> leftAlwaysNullSlots = join.left().getOutputSet().stream()
+ .filter(s -> alwaysNullSlots.contains(s) && !s.nullable())
+ .collect(Collectors.toSet());
+ Set<Slot> rightAlwaysNullSlots = join.right().getOutputSet().stream()
+ .filter(s -> alwaysNullSlots.contains(s) && !s.nullable())
+ .collect(Collectors.toSet());
+
+ Plan res = project;
+ if (join.getJoinType().isLeftOuterJoin() &&
!rightAlwaysNullSlots.isEmpty() && leftOutput) {
+ // When there is right slot always null, we can turn left outer
join to left anti join
+ Set<Expression> predicates = filter.getExpressions().stream()
+ .filter(p -> !(TypeUtils.isNull(p).isPresent()
+ &&
rightAlwaysNullSlots.containsAll(p.getInputSlots())))
+ .collect(ImmutableSet.toImmutableSet());
+ boolean containRightSlot = predicates.stream()
+ .anyMatch(s ->
join.right().getOutputSet().containsAll(s.getInputSlots()));
+ if (!containRightSlot) {
+ res = join.withJoinType(JoinType.LEFT_ANTI_JOIN);
+ res = predicates.isEmpty() ? res :
filter.withConjuncts(predicates).withChildren(res);
+ res = project.withChildren(res);
+ }
+ }
+ if (join.getJoinType().isRightOuterJoin() &&
!leftAlwaysNullSlots.isEmpty() && rightOutput) {
+ Set<Expression> predicates = filter.getExpressions().stream()
+ .filter(p -> !(TypeUtils.isNull(p).isPresent()
+ &&
leftAlwaysNullSlots.containsAll(p.getInputSlots())))
+ .collect(ImmutableSet.toImmutableSet());
+ boolean containLeftSlot = predicates.stream()
+ .anyMatch(s ->
join.left().getOutputSet().containsAll(s.getInputSlots()));
+ if (!containLeftSlot) {
+ res = join.withJoinType(JoinType.RIGHT_ANTI_JOIN);
+ res = predicates.isEmpty() ? res :
filter.withConjuncts(predicates).withChildren(res);
+ res = project.withChildren(res);
+ }
+ }
+ return res;
+ }
+}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/JoinType.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/JoinType.java
index b7d485059e..6470b184c8 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/JoinType.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/JoinType.java
@@ -156,10 +156,18 @@ public enum JoinType {
return this == LEFT_SEMI_JOIN || this == LEFT_ANTI_JOIN || this ==
NULL_AWARE_LEFT_ANTI_JOIN;
}
+ public final boolean isLeftAntiJoin() {
+ return this == LEFT_ANTI_JOIN;
+ }
+
public final boolean isRightSemiOrAntiJoin() {
return this == RIGHT_SEMI_JOIN || this == RIGHT_ANTI_JOIN;
}
+ public final boolean isRightAntiJoin() {
+ return this == RIGHT_ANTI_JOIN;
+ }
+
public final boolean isSemiOrAntiJoin() {
return this == LEFT_SEMI_JOIN || this == RIGHT_SEMI_JOIN || this ==
LEFT_ANTI_JOIN
|| this == NULL_AWARE_LEFT_ANTI_JOIN || this ==
RIGHT_ANTI_JOIN;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/util/TypeUtils.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/util/TypeUtils.java
index 6ec15166eb..f75b861dd2 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/util/TypeUtils.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/util/TypeUtils.java
@@ -70,4 +70,18 @@ public class TypeUtils {
return Optional.empty();
}
}
+
+ /**
+ * Judge whether the expression is `is null`.
+ *
+ * @return Optional.empty() if the expression is `is null`, otherwise
return slot.
+ */
+ public static Optional<Slot> isNull(Expression expr) {
+ if (expr instanceof IsNull
+ && (expr.child(0) instanceof SlotReference)) {
+ return Optional.of((Slot) expr.child(0));
+ } else {
+ return Optional.empty();
+ }
+ }
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/TransformOuterJoinToAntiJoinTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/TransformOuterJoinToAntiJoinTest.java
new file mode 100644
index 0000000000..369d56f02a
--- /dev/null
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/TransformOuterJoinToAntiJoinTest.java
@@ -0,0 +1,75 @@
+// 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.common.Pair;
+import org.apache.doris.nereids.trees.expressions.IsNull;
+import org.apache.doris.nereids.trees.expressions.StatementScopeIdGenerator;
+import org.apache.doris.nereids.trees.plans.JoinType;
+import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
+import org.apache.doris.nereids.util.LogicalPlanBuilder;
+import org.apache.doris.nereids.util.MemoPatternMatchSupported;
+import org.apache.doris.nereids.util.MemoTestUtils;
+import org.apache.doris.nereids.util.PlanChecker;
+import org.apache.doris.nereids.util.PlanConstructor;
+
+import com.google.common.collect.ImmutableList;
+import org.junit.jupiter.api.Test;
+
+class TransformOuterJoinToAntiJoinTest implements MemoPatternMatchSupported {
+ private final LogicalOlapScan scan1;
+ private final LogicalOlapScan scan2;
+
+ public TransformOuterJoinToAntiJoinTest() throws Exception {
+ // clear id so that slot id keep consistent every running
+ StatementScopeIdGenerator.clear();
+ scan1 = PlanConstructor.newLogicalOlapScan(0, "t1", 0);
+ scan2 = PlanConstructor.newLogicalOlapScan(1, "t2", 0);
+ }
+
+ @Test
+ void testEliminateLeftWithProject() {
+ LogicalPlan plan = new LogicalPlanBuilder(scan1)
+ .join(scan2, JoinType.LEFT_OUTER_JOIN, Pair.of(0, 0)) //
t1.id = t2.id
+ .filter(new IsNull(scan2.getOutput().get(0)))
+ .project(ImmutableList.of(0, 1))
+ .build();
+
+ PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
+ .applyTopDown(new InferFilterNotNull())
+ .applyTopDown(new TransformOuterJoinToAntiJoin())
+ .printlnTree()
+ .matches(logicalJoin().when(join ->
join.getJoinType().isLeftAntiJoin()));
+ }
+
+ @Test
+ void testEliminateRightWithProject() {
+ LogicalPlan plan = new LogicalPlanBuilder(scan1)
+ .join(scan2, JoinType.RIGHT_OUTER_JOIN, Pair.of(0, 0)) //
t1.id = t2.id
+ .filter(new IsNull(scan1.getOutput().get(0)))
+ .project(ImmutableList.of(2, 3))
+ .build();
+
+ PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
+ .applyTopDown(new InferFilterNotNull())
+ .applyTopDown(new TransformOuterJoinToAntiJoin())
+ .printlnTree()
+ .matches(logicalJoin().when(join ->
join.getJoinType().isRightAntiJoin()));
+ }
+}
diff --git
a/regression-test/suites/nereids_syntax_p0/transform_outer_join_to_anti.groovy
b/regression-test/suites/nereids_syntax_p0/transform_outer_join_to_anti.groovy
new file mode 100644
index 0000000000..06f87359d9
--- /dev/null
+++
b/regression-test/suites/nereids_syntax_p0/transform_outer_join_to_anti.groovy
@@ -0,0 +1,66 @@
+// 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.
+
+suite("transform_outer_join_to_anti") {
+ sql "SET enable_nereids_planner=true"
+ sql "SET enable_fallback_to_original_planner=false"
+
+ sql """drop table if exists eliminate_outer_join_A;"""
+ sql """drop table if exists eliminate_outer_join_B;"""
+ sql """
+ create table eliminate_outer_join_A ( a int not null, null_a int )
+ ENGINE=OLAP
+ DISTRIBUTED BY HASH(a) BUCKETS 1
+ PROPERTIES (
+ "replication_allocation" = "tag.location.default: 1",
+ "in_memory" = "false",
+ "storage_format" = "V2"
+ );
+ """
+
+ sql """
+ create table eliminate_outer_join_B ( b int not null, null_b int )
+ ENGINE=OLAP
+ DISTRIBUTED BY HASH(b) BUCKETS 1
+ PROPERTIES (
+ "replication_allocation" = "tag.location.default: 1",
+ "in_memory" = "false",
+ "storage_format" = "V2"
+ );
+ """
+
+ explain {
+ sql("select eliminate_outer_join_A.* from eliminate_outer_join_A left
outer join eliminate_outer_join_B on eliminate_outer_join_B.b =
eliminate_outer_join_A.a where eliminate_outer_join_B.b is null")
+ contains "ANTI JOIN"
+ }
+
+ explain {
+ sql("select eliminate_outer_join_B.* from eliminate_outer_join_A right
outer join eliminate_outer_join_B on eliminate_outer_join_B.b =
eliminate_outer_join_A.a where eliminate_outer_join_A.a is null")
+ contains "ANTI JOIN"
+ }
+
+ explain {
+ sql("select eliminate_outer_join_A.* from eliminate_outer_join_A left
outer join eliminate_outer_join_B on eliminate_outer_join_B.b =
eliminate_outer_join_A.a where eliminate_outer_join_B.null_b is null")
+ contains "OUTER JOIN"
+ }
+
+ explain {
+ sql("select eliminate_outer_join_B.* from eliminate_outer_join_A right
outer join eliminate_outer_join_B on eliminate_outer_join_B.b =
eliminate_outer_join_A.a where eliminate_outer_join_A.null_a is null")
+ contains "OUTER JOIN"
+ }
+}
+
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
