This is an automated email from the ASF dual-hosted git repository.
jakevin pushed a commit to branch branch-2.0
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-2.0 by this push:
new 9f8a11c26ad [fix](Nereids): Except just can merge with left deep shape
(#30270) (#30524)
9f8a11c26ad is described below
commit 9f8a11c26add04a582ef541c1a61e7d939fd1234
Author: jakevin <jakevin...@gmail.com>
AuthorDate: Tue Jan 30 14:21:59 2024 +0800
[fix](Nereids): Except just can merge with left deep shape (#30270) (#30524)
(cherry picked from commit aaa854f8ba8d31fc6eec219fb9da97bff4128b55)
---
.../doris/nereids/jobs/executor/Rewriter.java | 3 +-
.../org/apache/doris/nereids/rules/RuleType.java | 2 +
.../nereids/rules/rewrite/MergeSetOperations.java | 22 ++-
.../rules/rewrite/MergeSetOperationsExcept.java | 64 +++++++++
.../data/nereids_p0/set_operations/except.out | 148 +++++++++++++++++++++
.../suites/nereids_p0/set_operations/except.groovy | 126 ++++++++++++++++++
6 files changed, 358 insertions(+), 7 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
index 1f17d15ae61..881750f23dd 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
@@ -77,6 +77,7 @@ import org.apache.doris.nereids.rules.rewrite.MergeFilters;
import org.apache.doris.nereids.rules.rewrite.MergeOneRowRelationIntoUnion;
import org.apache.doris.nereids.rules.rewrite.MergeProjects;
import org.apache.doris.nereids.rules.rewrite.MergeSetOperations;
+import org.apache.doris.nereids.rules.rewrite.MergeSetOperationsExcept;
import org.apache.doris.nereids.rules.rewrite.NormalizeSort;
import org.apache.doris.nereids.rules.rewrite.OrExpansion;
import org.apache.doris.nereids.rules.rewrite.PruneEmptyPartition;
@@ -253,7 +254,7 @@ public class Rewriter extends AbstractBatchJobExecutor {
topic("Set operation optimization",
// Do MergeSetOperation first because we hope to match
pattern of Distinct SetOperator.
topDown(new PushProjectThroughUnion(), new
MergeProjects()),
- bottomUp(new MergeSetOperations()),
+ bottomUp(new MergeSetOperations(), new
MergeSetOperationsExcept()),
bottomUp(new PushProjectIntoOneRowRelation()),
topDown(new MergeOneRowRelationIntoUnion()),
topDown(new BuildAggForUnion())
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 3bdcf18fd44..a0c32509a65 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
@@ -236,6 +236,8 @@ public enum RuleType {
MERGE_ONE_ROW_RELATION_INTO_UNION(RuleTypeClass.REWRITE),
PUSH_PROJECT_INTO_ONE_ROW_RELATION(RuleTypeClass.REWRITE),
MERGE_SET_OPERATION(RuleTypeClass.REWRITE),
+ MERGE_SET_OPERATION_EXCEPT(RuleTypeClass.REWRITE),
+ MERGE_TOP_N(RuleTypeClass.REWRITE),
BUILD_AGG_FOR_UNION(RuleTypeClass.REWRITE),
COUNT_DISTINCT_REWRITE(RuleTypeClass.REWRITE),
INNER_TO_CROSS_JOIN(RuleTypeClass.REWRITE),
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeSetOperations.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeSetOperations.java
index 152409d2b53..33d9d50acaa 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeSetOperations.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeSetOperations.java
@@ -22,6 +22,7 @@ import org.apache.doris.nereids.rules.RuleType;
import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.algebra.SetOperation.Qualifier;
+import org.apache.doris.nereids.trees.plans.logical.LogicalExcept;
import org.apache.doris.nereids.trees.plans.logical.LogicalSetOperation;
import com.google.common.collect.ImmutableList;
@@ -43,12 +44,22 @@ import java.util.List;
* / | \
* scan1 scan2 scan3
* </pre>
+ * Notice: this rule ignore Except.
+ * Relational Algebra: Union (R U S), Intersect Syntax: (R ∩ S), Except
Syntax: (R - S)
+ * TODO: Except need other Rewrite.
+ * <ul> (R - S) U T = (R U T) - S </ul>
+ * <ul> (R - S) U (T - U) = (R U T) - (S U U) </ul>
+ * <ul> R - (S U T) = (R - S) - T </ul>
+ * <ul> R - (S - T) = (R - S) U T </ul>
+ * <ul> ...... and so on </ul>
*/
-public class MergeSetOperations implements RewriteRuleFactory {
+public class MergeSetOperations extends OneRewriteRuleFactory {
@Override
- public List<Rule> buildRules() {
- return ImmutableList.of(
- logicalSetOperation(any(),
any()).when(MergeSetOperations::canMerge).then(parentSetOperation -> {
+ public Rule build() {
+ return logicalSetOperation(any(), any())
+ .whenNot(LogicalExcept.class::isInstance)
+ .when(MergeSetOperations::canMerge)
+ .then(parentSetOperation -> {
ImmutableList.Builder<Plan> newChildren =
ImmutableList.builder();
ImmutableList.Builder<List<SlotReference>>
newChildrenOutputs = ImmutableList.builder();
for (int i = 0; i < parentSetOperation.arity(); i++) {
@@ -64,8 +75,7 @@ public class MergeSetOperations implements RewriteRuleFactory
{
}
return parentSetOperation.withChildrenAndTheirOutputs(
newChildren.build(), newChildrenOutputs.build());
- }).toRule(RuleType.MERGE_SET_OPERATION)
- );
+ }).toRule(RuleType.MERGE_SET_OPERATION);
}
/** canMerge */
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeSetOperationsExcept.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeSetOperationsExcept.java
new file mode 100644
index 00000000000..2eb284e69c5
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/MergeSetOperationsExcept.java
@@ -0,0 +1,64 @@
+// 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.SlotReference;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalExcept;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+
+/**
+ * Merge left deep except
+ * <pre>
+ * Except
+ * / \
+ * Except scan3
+ * / \
+ * scan1 scan2
+ * -->
+ * Except
+ * / | \
+ * scan1 scan2 scan3
+ * </pre>
+ */
+public class MergeSetOperationsExcept extends OneRewriteRuleFactory {
+ @Override
+ public Rule build() {
+ return logicalExcept(logicalExcept(), any())
+ .when(e -> e.getQualifier() == ((LogicalExcept)
e.child(0)).getQualifier())
+ .then(parentExcept -> {
+ LogicalExcept childExcept = (LogicalExcept)
parentExcept.child(0);
+
+ ImmutableList.Builder<Plan> newChildren =
ImmutableList.builder();
+ ImmutableList.Builder<List<SlotReference>>
newChildrenOutputs = ImmutableList.builder();
+
+ newChildren.addAll(childExcept.children());
+ newChildren.addAll(parentExcept.children().subList(1,
parentExcept.children().size()));
+
newChildrenOutputs.addAll(childExcept.getRegularChildrenOutputs());
+ newChildrenOutputs.addAll(
+
parentExcept.getRegularChildrenOutputs().subList(1,
parentExcept.children().size()));
+
+ return
parentExcept.withChildrenAndTheirOutputs(newChildren.build(),
newChildrenOutputs.build());
+ }).toRule(RuleType.MERGE_SET_OPERATION_EXCEPT);
+ }
+}
diff --git a/regression-test/data/nereids_p0/set_operations/except.out
b/regression-test/data/nereids_p0/set_operations/except.out
new file mode 100644
index 00000000000..618df8d7ef6
--- /dev/null
+++ b/regression-test/data/nereids_p0/set_operations/except.out
@@ -0,0 +1,148 @@
+-- This file is automatically generated. You should know what you did if you
want to edit this
+-- !except_left_deep --
+1 a
+2 b
+3 c
+4 d
+5 e
+6 f
+7 g
+8 h
+9 i
+
+-- !except_left_deep_shape --
+PhysicalResultSink
+--PhysicalExcept
+----filter((t1.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t1]
+----filter((t2.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t2]
+----filter((t3.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t3]
+
+-- !except_right_deep --
+1 a
+10 j
+2 b
+3 c
+4 d
+5 e
+6 f
+7 g
+8 h
+9 i
+
+-- !except_right_deep_shape --
+PhysicalResultSink
+--PhysicalExcept
+----filter((t1.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t1]
+----PhysicalExcept
+------filter((t2.__DORIS_DELETE_SIGN__ = 0))
+--------PhysicalOlapScan[t2]
+------filter((t3.__DORIS_DELETE_SIGN__ = 0))
+--------PhysicalOlapScan[t3]
+
+-- !except_left_deep_right_deep --
+1 a
+2 b
+3 c
+4 d
+5 e
+6 f
+7 g
+8 h
+9 i
+
+-- !except_left_deep_right_deep_shape --
+PhysicalResultSink
+--PhysicalExcept
+----filter((t1.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t1]
+----filter((t2.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t2]
+----PhysicalExcept
+------filter((t3.__DORIS_DELETE_SIGN__ = 0))
+--------PhysicalOlapScan[t3]
+------filter((t2.__DORIS_DELETE_SIGN__ = 0))
+--------PhysicalOlapScan[t2]
+
+-- !except_left_deep --
+1 a
+2 b
+3 c
+3 l
+4 d
+5 e
+6 f
+7 g
+8 h
+9 i
+9 o
+
+-- !except_left_deep_shape --
+PhysicalResultSink
+--PhysicalExcept
+----hashAgg[GLOBAL]
+------hashAgg[LOCAL]
+--------PhysicalUnion
+----------filter((t1.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t1]
+----------filter((t2.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t2]
+----filter((t3.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t3]
+
+-- !except_right_deep --
+1 a
+2 b
+3 c
+4 d
+5 e
+6 f
+7 g
+8 h
+9 i
+
+-- !except_right_deep_shape --
+PhysicalResultSink
+--PhysicalExcept
+----filter((t1.__DORIS_DELETE_SIGN__ = 0))
+------PhysicalOlapScan[t1]
+----hashAgg[GLOBAL]
+------hashAgg[LOCAL]
+--------PhysicalUnion
+----------filter((t2.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t2]
+----------filter((t3.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t3]
+
+-- !except_left_deep_right_deep --
+1 a
+2 b
+3 c
+4 d
+5 e
+6 f
+7 g
+8 h
+9 i
+
+-- !except_left_deep_right_deep_shape --
+PhysicalResultSink
+--PhysicalExcept
+----hashAgg[GLOBAL]
+------hashAgg[LOCAL]
+--------PhysicalUnion
+----------filter((t1.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t1]
+----------filter((t2.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t2]
+----hashAgg[GLOBAL]
+------hashAgg[LOCAL]
+--------PhysicalUnion
+----------filter((t3.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t3]
+----------filter((t2.__DORIS_DELETE_SIGN__ = 0))
+------------PhysicalOlapScan[t2]
+
diff --git a/regression-test/suites/nereids_p0/set_operations/except.groovy
b/regression-test/suites/nereids_p0/set_operations/except.groovy
new file mode 100644
index 00000000000..522299acedd
--- /dev/null
+++ b/regression-test/suites/nereids_p0/set_operations/except.groovy
@@ -0,0 +1,126 @@
+// 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("test_except", "query") {
+ sql "SET enable_nereids_planner=true"
+ sql "SET enable_fallback_to_original_planner=false"
+ sql "drop table if exists t1;"
+ sql "drop table if exists t2;"
+ sql "drop table if exists t3;"
+ sql "set ignore_shape_nodes='PhysicalDistribute,PhysicalProject'"
+
+ sql '''
+ CREATE TABLE t1 (
+ a int NOT NULL,
+ b VARCHAR(25) NOT NULL,
+ )ENGINE=OLAP
+ unique KEY(`a`)
+ COMMENT "OLAP"
+ DISTRIBUTED BY HASH(`a`) BUCKETS 1
+ PROPERTIES (
+ "replication_num" = "1"
+ );
+ '''
+ sql '''
+ CREATE TABLE t2 (
+ a int NOT NULL,
+ b VARCHAR(25) NOT NULL,
+ )ENGINE=OLAP
+ unique KEY(`a`)
+ COMMENT "OLAP"
+ DISTRIBUTED BY HASH(`a`) BUCKETS 1
+ PROPERTIES (
+ "replication_num" = "1"
+ );
+ '''
+ sql '''
+ CREATE TABLE t3 (
+ a int NOT NULL,
+ b VARCHAR(25) NOT NULL,
+ )ENGINE=OLAP
+ unique KEY(`a`)
+ COMMENT "OLAP"
+ DISTRIBUTED BY HASH(`a`) BUCKETS 1
+ PROPERTIES (
+ "replication_num" = "1"
+ );
+ '''
+
+ sql """
+ insert into t1 values(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e'), (6,
'f'), (7, 'g'), (8, 'h'), (9, 'i'), (10, 'j');
+ """
+ sql """
+ insert into t2 values(1, 'k'), (3, 'l'), (5, 'm'), (7, 'n'), (9, 'o');
+ """
+ sql """
+ insert into t3 values(10, 'j'), (1, 'k'), (4, 'l'), (5, 'm'), (7, 'n'),
(8, 'o');
+ """
+
+ // (a except b) except c
+ order_qt_except_left_deep """
+ select * from (select * from t1 except select * from t2) t except
select * from t3;
+ """
+
+ qt_except_left_deep_shape """
+ explain shape plan select * from (select * from t1 except select *
from t2) t except select * from t3;
+ """
+
+ // a except (b except c)
+ order_qt_except_right_deep """
+ select * from t1 except select * from (select * from t2 except select
* from t3) t;
+ """
+
+ qt_except_right_deep_shape """
+ explain shape plan select * from t1 except select * from (select *
from t2 except select * from t3) t;
+ """
+
+ // (a except b) except (c except d)
+ order_qt_except_left_deep_right_deep """
+ select * from (select * from t1 except select * from t2) t except
select * from (select * from t3 except select * from t2) t;
+ """
+
+ qt_except_left_deep_right_deep_shape """
+ explain shape plan select * from (select * from t1 except select *
from t2) t except select * from (select * from t3 except select * from t2) t;
+ """
+
+ // (a union b) except c
+ order_qt_except_left_deep """
+ select * from (select * from t1 union select * from t2) t except
select * from t3;
+ """
+
+ qt_except_left_deep_shape """
+ explain shape plan select * from (select * from t1 union select * from
t2) t except select * from t3;
+ """
+
+ // a except (b union c)
+ order_qt_except_right_deep """
+ select * from t1 except select * from (select * from t2 union select *
from t3) t;
+ """
+
+ qt_except_right_deep_shape """
+ explain shape plan select * from t1 except select * from (select *
from t2 union select * from t3) t;
+ """
+
+ // (a union b) except (c union d)
+ order_qt_except_left_deep_right_deep """
+ select * from (select * from t1 union select * from t2) t except
select * from (select * from t3 union select * from t2) t;
+ """
+
+ qt_except_left_deep_right_deep_shape """
+ explain shape plan select * from (select * from t1 union select * from
t2) t except select * from (select * from t3 union select * from t2) t;
+ """
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
