implement intersect and except related optimization rule: MergeIntersect, MergeExcept, RemoveEmptyIntersectBranchs, EvaluateEmptyIntersect, PruneIntersectSourceColumns, PruneExceptSourceColmns (#16761)
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/EvaluateEmptyIntersect.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/EvaluateEmptyIntersect.java
new file mode 100644
index 0000000..03c8bba
--- /dev/null
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/EvaluateEmptyIntersect.java
@@ -0,0 +1,63 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.iterative.rule;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Assignments;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Lookup;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.IntersectNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ProjectNode;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Captures;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Pattern;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.node.Patterns.intersect;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.QueryCardinalityUtil.isEmpty;
+
+public class EvaluateEmptyIntersect implements Rule<IntersectNode> {
+
+ private static final Pattern<IntersectNode> PATTERN = intersect();
+
+ @Override
+ public Pattern<IntersectNode> getPattern() {
+ return PATTERN;
+ }
+
+ /** if any child of the intersect node is empty set, then the result set is empty */
+ @Override
+ public Result apply(IntersectNode node, Captures captures, Context context) {
+
+ Lookup lookup = context.getLookup();
+ for (int i = 0; i < node.getChildren().size(); i++) {
+ if (isEmpty(node.getChildren().get(i), lookup)) {
+
+ // replace the intersect node with project node, append the empty node to the project node
+ Assignments.Builder assignments = Assignments.builder();
+ for (Symbol symbol : node.getOutputSymbols()) {
+ assignments.put(symbol, node.getSymbolMapping().get(symbol).get(i).toSymbolReference());
+ }
+ return Result.ofPlanNode(
+ new ProjectNode(node.getPlanNodeId(), node.getChildren().get(i), assignments.build()));
+ }
+ }
+
+ return Result.empty();
+ }
+}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/MergeExcept.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/MergeExcept.java
new file mode 100644
index 0000000..08fb908
--- /dev/null
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/MergeExcept.java
@@ -0,0 +1,47 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.iterative.rule;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ExceptNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.Patterns;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.SetOperationNode;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Captures;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Pattern;
+
+import java.util.Optional;
+
+public class MergeExcept implements Rule<ExceptNode> {
+
+ private final Pattern<ExceptNode> pattern = Patterns.except();
+
+ @Override
+ public Pattern<ExceptNode> getPattern() {
+ return pattern;
+ }
+
+ @Override
+ public Result apply(ExceptNode node, Captures captures, Context context) {
+
+ SetOperationMerge mergeOperation = new SetOperationMerge(node, context);
+ Optional<SetOperationNode> result = mergeOperation.mergeFirstSource();
+ return result.map(Result::ofPlanNode).orElseGet(Result::empty);
+ }
+}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/MergeIntersect.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/MergeIntersect.java
new file mode 100644
index 0000000..1786909
--- /dev/null
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/MergeIntersect.java
@@ -0,0 +1,47 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.iterative.rule;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.IntersectNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.Patterns;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.SetOperationNode;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Captures;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Pattern;
+
+import java.util.Optional;
+
+public class MergeIntersect implements Rule<IntersectNode> {
+
+ private final Pattern<IntersectNode> pattern = Patterns.intersect();
+
+ @Override
+ public Pattern<IntersectNode> getPattern() {
+ return pattern;
+ }
+
+ @Override
+ public Result apply(IntersectNode node, Captures captures, Context context) {
+
+ SetOperationMerge mergeOperation = new SetOperationMerge(node, context);
+ Optional<SetOperationNode> result = mergeOperation.merge();
+ return result.map(Result::ofPlanNode).orElseGet(Result::empty);
+ }
+}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/PruneExceptSourceColumns.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/PruneExceptSourceColumns.java
new file mode 100644
index 0000000..cc21065
--- /dev/null
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/PruneExceptSourceColumns.java
@@ -0,0 +1,54 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.iterative.rule;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ExceptNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.Patterns;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Captures;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Pattern;
+
+import com.google.common.collect.ImmutableSet;
+
+import java.util.Set;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.Util.restrictChildOutputs;
+
+public class PruneExceptSourceColumns implements Rule<ExceptNode> {
+
+ @Override
+ public Pattern<ExceptNode> getPattern() {
+ return Patterns.except();
+ }
+
+ @Override
+ public Result apply(ExceptNode node, Captures captures, Context context) {
+
+ @SuppressWarnings("unchecked")
+ Set<Symbol>[] referencedInputs = new Set[node.getChildren().size()];
+ for (int i = 0; i < node.getChildren().size(); i++) {
+ referencedInputs[i] = ImmutableSet.copyOf(node.sourceOutputLayout(i));
+ }
+ return restrictChildOutputs(context.getIdAllocator(), node, referencedInputs)
+ .map(Rule.Result::ofPlanNode)
+ .orElse(Rule.Result.empty());
+ }
+}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/PruneIntersectSourceColumns.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/PruneIntersectSourceColumns.java
new file mode 100644
index 0000000..9fabb9b
--- /dev/null
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/PruneIntersectSourceColumns.java
@@ -0,0 +1,55 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.iterative.rule;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.IntersectNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.Patterns;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Captures;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Pattern;
+
+import com.google.common.collect.ImmutableSet;
+
+import java.util.Set;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.Util.restrictChildOutputs;
+
+public class PruneIntersectSourceColumns implements Rule<IntersectNode> {
+
+ @Override
+ public Pattern<IntersectNode> getPattern() {
+ return Patterns.intersect();
+ }
+
+ @Override
+ public Result apply(IntersectNode node, Captures captures, Context context) {
+
+ @SuppressWarnings("unchecked")
+ Set<Symbol>[] referencedInputs = new Set[node.getChildren().size()];
+ for (int i = 0; i < node.getChildren().size(); i++) {
+ referencedInputs[i] = ImmutableSet.copyOf(node.sourceOutputLayout(i));
+ }
+
+ return restrictChildOutputs(context.getIdAllocator(), node, referencedInputs)
+ .map(Rule.Result::ofPlanNode)
+ .orElse(Rule.Result.empty());
+ }
+}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/RemoveEmptyExceptBranches.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/RemoveEmptyExceptBranches.java
new file mode 100644
index 0000000..b07531e
--- /dev/null
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/RemoveEmptyExceptBranches.java
@@ -0,0 +1,139 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.iterative.rule;
+
+import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Assignments;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Lookup;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ExceptNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.Patterns;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ProjectNode;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Captures;
+import org.apache.iotdb.db.queryengine.plan.relational.utils.matching.Pattern;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableListMultimap;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ListMultimap;
+
+import java.util.List;
+import java.util.Map;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.node.AggregationNode.singleAggregation;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.node.AggregationNode.singleGroupingSet;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.optimizations.QueryCardinalityUtil.isEmpty;
+
+public class RemoveEmptyExceptBranches implements Rule<ExceptNode> {
+ private final Pattern<ExceptNode> pattern = Patterns.except();
+
+ @Override
+ public Pattern<ExceptNode> getPattern() {
+ return pattern;
+ }
+
+ @Override
+ public Result apply(ExceptNode node, Captures captures, Context context) {
+
+ // pre-check
+ Lookup lookup = context.getLookup();
+ ImmutableList.Builder<Boolean> emptyFlagsBuilder = ImmutableList.builder();
+ boolean anyEmpty = false;
+ for (PlanNode child : node.getChildren()) {
+ boolean isEmpty = isEmpty(child, lookup);
+ anyEmpty |= isEmpty;
+ emptyFlagsBuilder.add(isEmpty);
+ }
+ if (!anyEmpty) {
+ return Result.empty();
+ }
+
+ ImmutableList<Boolean> emptyFlags = emptyFlagsBuilder.build();
+ // if the first child of Except is empty set, replace the Except Node with Project node,
+ // and let the first child append to the Project node
+ if (emptyFlags.get(0)) {
+ Assignments.Builder assignments = Assignments.builder();
+ for (Symbol symbol : node.getOutputSymbols()) {
+ assignments.put(symbol, node.getSymbolMapping().get(symbol).get(0).toSymbolReference());
+ }
+ return Result.ofPlanNode(
+ new ProjectNode(node.getPlanNodeId(), node.getChildren().get(0), assignments.build()));
+ }
+
+ boolean hasEmptyBranches = false;
+ ImmutableList.Builder<PlanNode> newSourcesBuilder = ImmutableList.builder();
+ ImmutableListMultimap.Builder<Symbol, Symbol> outputsToInputsBuilder =
+ ImmutableListMultimap.builder();
+ for (int i = 0; i < node.getChildren().size(); i++) {
+ PlanNode source = node.getChildren().get(i);
+ // first source is the set we're excluding rows from, so treat it separately
+ if (i == 0 || !emptyFlags.get(i)) {
+ newSourcesBuilder.add(source);
+
+ for (Symbol symbol : node.getOutputSymbols()) {
+ outputsToInputsBuilder.put(symbol, node.getSymbolMapping().get(symbol).get(i));
+ }
+ } else {
+ hasEmptyBranches = true;
+ }
+ }
+
+ if (!hasEmptyBranches) {
+ return Result.empty();
+ }
+
+ List<PlanNode> newSources = newSourcesBuilder.build();
+ ListMultimap<Symbol, Symbol> outputsToInputs = outputsToInputsBuilder.build();
+
+ // if the first child of Except node is non-empty set and other children of the Except node are
+ // empty set, replace the Except node with project node, add the aggregation node above the
+ // project node if Except that with distinct
+ if (newSources.size() == 1) {
+ Assignments.Builder assignments = Assignments.builder();
+ for (Map.Entry<Symbol, Symbol> entry : outputsToInputs.entries()) {
+ assignments.put(entry.getKey(), entry.getValue().toSymbolReference());
+ }
+
+ ProjectNode projectNode =
+ new ProjectNode(
+ context.getIdAllocator().genPlanNodeId(), newSources.get(0), assignments.build());
+
+ if (node.isDistinct()) {
+ return Result.ofPlanNode(
+ singleAggregation(
+ context.getIdAllocator().genPlanNodeId(),
+ projectNode,
+ ImmutableMap.of(),
+ singleGroupingSet(node.getOutputSymbols())));
+ }
+
+ return Result.ofPlanNode(projectNode);
+ }
+
+ return Result.ofPlanNode(
+ new ExceptNode(
+ node.getPlanNodeId(),
+ newSources,
+ outputsToInputs,
+ node.getOutputSymbols(),
+ node.isDistinct()));
+ }
+}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/SetOperationMerge.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/SetOperationMerge.java
index 563a388..04dee38 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/SetOperationMerge.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/iterative/rule/SetOperationMerge.java
@@ -23,6 +23,8 @@
import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Lookup;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ExceptNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.IntersectNode;
import org.apache.iotdb.db.queryengine.plan.relational.planner.node.SetOperationNode;
import org.apache.iotdb.db.queryengine.plan.relational.planner.node.UnionNode;
@@ -50,11 +52,13 @@
this.newSources = new ArrayList<>();
}
- // Merge multiple union into one union
+ /** Merge multiple union into one union or multiple intersect into one intersect */
public Optional<SetOperationNode> merge() {
checkState(
- node instanceof UnionNode, "unexpected node type: %s", node.getClass().getSimpleName());
+ node instanceof UnionNode || node instanceof IntersectNode,
+ "unexpected node type: %s",
+ node.getClass().getSimpleName());
Lookup lookup = context.getLookup();
// Pre-check
boolean anyMerge =
@@ -65,22 +69,26 @@
return Optional.empty();
}
- List<PlanNode> childrenOfUnion =
+ List<PlanNode> children =
node.getChildren().stream().map(lookup::resolve).collect(toImmutableList());
ImmutableListMultimap.Builder<Symbol, Symbol> newMappingsBuilder =
ImmutableListMultimap.builder();
+ boolean resultIsDistinct = false;
boolean rewritten = false;
- for (int i = 0; i < childrenOfUnion.size(); i++) {
- PlanNode child = childrenOfUnion.get(i);
+ for (int i = 0; i < children.size(); i++) {
+ PlanNode child = children.get(i);
// Determine if set operations can be merged and whether the resulting set operation is
// quantified DISTINCT or ALL
- Optional<Boolean> mergedQuantifier = mergedQuantifierIsDistinct(node, child);
+ Optional<Boolean> mergedQuantifier = judgeQuantifierForUnionAndIntersect(node, child);
if (mergedQuantifier.isPresent()) {
addMergedMappings((SetOperationNode) child, i, newMappingsBuilder);
+ // for intersect : as long as one of intersect node is (intersect distinct), the merged
+ // intersect would be (intersect distinct).
+ resultIsDistinct = resultIsDistinct || mergedQuantifier.get();
rewritten = true;
} else {
// Keep mapping as it is
@@ -92,10 +100,56 @@
return Optional.empty();
}
- // the union has merged
+ if (node instanceof UnionNode) {
+ return Optional.of(
+ new UnionNode(
+ node.getPlanNodeId(),
+ newSources,
+ newMappingsBuilder.build(),
+ node.getOutputSymbols()));
+ }
+
return Optional.of(
- new UnionNode(
- node.getPlanNodeId(), newSources, newMappingsBuilder.build(), node.getOutputSymbols()));
+ new IntersectNode(
+ node.getPlanNodeId(),
+ newSources,
+ newMappingsBuilder.build(),
+ node.getOutputSymbols(),
+ resultIsDistinct));
+ }
+
+ /** only for except node, only merge first source node */
+ public Optional<SetOperationNode> mergeFirstSource() {
+
+ checkState(
+ node instanceof ExceptNode, "unexpected node type: %s", node.getClass().getSimpleName());
+
+ Lookup lookup = context.getLookup();
+
+ List<PlanNode> children =
+ node.getChildren().stream().map(lookup::resolve).collect(toImmutableList());
+ PlanNode firstChild = children.get(0);
+ Optional<Boolean> mergedQuantifier = judgeQuantifierForExcept((ExceptNode) node, firstChild);
+ if (!mergedQuantifier.isPresent()) {
+ return Optional.empty();
+ }
+
+ ImmutableListMultimap.Builder<Symbol, Symbol> newMappingsBuilder =
+ ImmutableListMultimap.builder();
+ addMergedMappings((SetOperationNode) firstChild, 0, newMappingsBuilder);
+ // Keep remaining as it is
+ for (int i = 1; i < children.size(); i++) {
+ PlanNode child = children.get(i);
+ addOriginalMappings(child, i, newMappingsBuilder);
+ }
+
+ return Optional.of(
+ new ExceptNode(
+ node.getPlanNodeId(),
+ newSources,
+ newMappingsBuilder.build(),
+ node.getOutputSymbols(),
+ mergedQuantifier.get()));
}
private void addMergedMappings(
@@ -126,9 +180,24 @@
/**
* Check if node and child are mergeable based on their set operation type and quantifier.
*
+ * <p>For parent and child of type UNION, merge is always possible and the assumed quantifier is
+ * ALL, because UnionNode always represents UNION ALL.
+ *
+ * <p>For parent and child of type INTERSECT, merge is always possible: 1. If parent and child are
+ * both INTERSECT ALL, the resulting set operation is INTERSECT ALL. 2. Otherwise, the resulting
+ * set operation is INTERSECT DISTINCT: a. If the parent is DISTINCT, the result has unique
+ * values, regardless of whether child branches were DISTINCT or ALL. b. If the child is DISTINCT,
+ * that branch is guaranteed to have unique values, so at most one element of the other branches
+ * will be retained -- this is equivalent to just doing DISTINCT on the parent.
+ *
* <p>Optional.empty() indicates that merge is not possible.
+ *
+ * <p>Optional.of(false) indicates that merged node with quantifier which is all.
+ *
+ * <p>Optional.of(true) indicates that merged node with quantifier which is distinct.
*/
- private Optional<Boolean> mergedQuantifierIsDistinct(SetOperationNode node, PlanNode child) {
+ private Optional<Boolean> judgeQuantifierForUnionAndIntersect(
+ SetOperationNode node, PlanNode child) {
if (!node.getClass().equals(child.getClass())) {
return Optional.empty();
@@ -138,7 +207,37 @@
return Optional.of(false);
}
- // the Judgment logic for intersect and except wait for supplying
- return Optional.empty();
+ if (node instanceof IntersectNode) {
+ if (!((IntersectNode) node).isDistinct() && !((IntersectNode) child).isDistinct()) {
+ return Optional.of(false);
+ }
+ return Optional.of(true);
+ }
+
+ // never should reach here
+ throw new IllegalStateException(
+ "unexpected setOperation node type: " + node.getClass().getSimpleName());
+ }
+
+ /**
+ * Check if node and child are mergeable based on their set operation type and quantifier.
+ *
+ * <p>For parent and child of type EXCEPT: 1. if parent is EXCEPT DISTINCT and child is EXCEPT
+ * ALL, merge is not possible 2. if parent and child are both EXCEPT DISTINCT, the resulting set
+ * operation is EXCEPT DISTINCT 3. if parent and child are both EXCEPT ALL, the resulting set
+ * operation is EXCEPT ALL 4. if parent is EXCEPT ALL and child is EXCEPT DISTINCT, the resulting
+ * set operation is EXCEPT DISTINCT
+ */
+ private Optional<Boolean> judgeQuantifierForExcept(ExceptNode node, PlanNode child) {
+
+ if (!node.getClass().equals(child.getClass())) {
+ return Optional.empty();
+ }
+
+ if (node.isDistinct() && !((ExceptNode) child).isDistinct()) {
+ return Optional.empty();
+ }
+
+ return Optional.of(((ExceptNode) child).isDistinct());
}
}
diff --git a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/LogicalOptimizeFactory.java b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/LogicalOptimizeFactory.java
index d7084c3..1c73274 100644
--- a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/LogicalOptimizeFactory.java
+++ b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/LogicalOptimizeFactory.java
@@ -26,6 +26,7 @@
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Rule;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.RuleStatsRecorder;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.CanonicalizeExpressions;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.EvaluateEmptyIntersect;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.ImplementExceptAll;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.ImplementExceptDistinctAsUnion;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.ImplementIntersectAll;
@@ -33,7 +34,9 @@
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.ImplementPatternRecognition;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.ImplementTableFunctionSource;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.InlineProjections;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.MergeExcept;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.MergeFilters;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.MergeIntersect;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.MergeLimitOverProjectWithSort;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.MergeLimitWithSort;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.MergeLimits;
@@ -50,10 +53,12 @@
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneCorrelatedJoinCorrelation;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneDistinctAggregation;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneEnforceSingleRowColumns;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneExceptSourceColumns;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneExplainAnalyzeColumns;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneFillColumns;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneFilterColumns;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneGapFillColumns;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneIntersectSourceColumns;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneJoinChildrenColumns;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneJoinColumns;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PruneLimitColumns;
@@ -76,6 +81,7 @@
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PushProjectionThroughUnion;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.PushTopKThroughUnion;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.RemoveDuplicateConditions;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.RemoveEmptyExceptBranches;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.RemoveEmptyUnionBranches;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.RemoveRedundantEnforceSingleRowNode;
import org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.rule.RemoveRedundantExists;
@@ -126,7 +132,9 @@
new PruneCorrelatedJoinColumns(),
new PruneCorrelatedJoinCorrelation(),
new PruneEnforceSingleRowColumns(),
+ new PruneExceptSourceColumns(),
new PruneFilterColumns(),
+ new PruneIntersectSourceColumns(),
new PruneGapFillColumns(),
new PruneFillColumns(),
new PruneLimitColumns(),
@@ -216,6 +224,8 @@
ImmutableSet.of(
new ImplementTableFunctionSource(),
new RemoveEmptyUnionBranches(),
+ new EvaluateEmptyIntersect(),
+ new RemoveEmptyExceptBranches(),
new MergeFilters(),
new InlineProjections(plannerContext),
new RemoveRedundantIdentityProjections(),
@@ -258,8 +268,10 @@
.addAll(limitPushdownRules)
.addAll(
ImmutableSet.of(
- new MergeUnion(),
new RemoveEmptyUnionBranches(),
+ new EvaluateEmptyIntersect(),
+ new RemoveEmptyExceptBranches(),
+ new MergeUnion(),
new MergeFilters(),
new RemoveTrivialFilters(),
new MergeLimits(),
@@ -275,8 +287,8 @@
.addAll(
ImmutableSet.of(
new MergeUnion(),
- // new MergeIntersect
- // new MergeExcept
+ new MergeIntersect(),
+ new MergeExcept(),
new PruneDistinctAggregation()))
.build()),
new IterativeOptimizer(
@@ -336,11 +348,17 @@
// Currently, we inline symbols but do not simplify them in predicate push down.
// So we have to add extra simplifyOptimizer here
simplifyOptimizer,
- // Currently, Distinct is not supported, so we cant use this rule for now.
- // new IterativeOptimizer(
- // plannerContext,
- // ruleStats,
- // ImmutableSet.of(new TransformFilteringSemiJoinToInnerJoin())),
+ new IterativeOptimizer(
+ plannerContext,
+ ruleStats,
+ ImmutableSet.of(
+ new RemoveEmptyUnionBranches(),
+ new EvaluateEmptyIntersect(),
+ new RemoveEmptyExceptBranches()
+ // Currently, Distinct is not supported, so we cant use this rule for now.
+ // new TransformFilteringSemiJoinToInnerJoin()
+ )),
+
// redo columnPrune and inlineProjections after pushPredicateIntoTableScan
columnPruningOptimizer,
inlineProjectionLimitFiltersOptimizer,
diff --git a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/EvaluateEmptyIntersectTest.java b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/EvaluateEmptyIntersectTest.java
new file mode 100644
index 0000000..a69b4af
--- /dev/null
+++ b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/EvaluateEmptyIntersectTest.java
@@ -0,0 +1,48 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.analyzer;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.PlanTester;
+
+import org.junit.Test;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanAssert.assertPlan;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.limit;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.output;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.tableScan;
+
+public class EvaluateEmptyIntersectTest {
+
+ @Test
+ public void EvaluateEmptyIntersectTest() {
+ // Normal case
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1 limit 0) intersect (select tag1 from t2) intersect (select tag1 from t3)"),
+ output((limit(0, tableScan("testdb.t1")))));
+
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1 ) intersect all (select tag1 from t2 limit 0) intersect all (select tag1 from t3)"),
+ output((limit(0, tableScan("testdb.t2")))));
+ }
+}
diff --git a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/MergeExceptTest.java b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/MergeExceptTest.java
new file mode 100644
index 0000000..41275bf
--- /dev/null
+++ b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/MergeExceptTest.java
@@ -0,0 +1,147 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.analyzer;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.PlanTester;
+
+import org.junit.Test;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanAssert.assertPlan;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.aggregation;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.filter;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.output;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.project;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.sort;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.tableScan;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.union;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.window;
+
+/**
+ * for except node, only merge first source node
+ *
+ * <p>For parent and child of type EXCEPT: 1. if parent is EXCEPT DISTINCT and child is EXCEPT ALL,
+ * merge is not possible 2. if parent and child are both EXCEPT DISTINCT, the resulting set
+ * operation is EXCEPT DISTINCT 3. if parent and child are both EXCEPT ALL, the resulting set
+ * operation is EXCEPT ALL 4. if parent is EXCEPT ALL and child is EXCEPT DISTINCT, the resulting
+ * set operation is EXCEPT DISTINCT
+ */
+public class MergeExceptTest {
+
+ @Test
+ public void mergeTwoExceptAll() {
+ PlanTester planTester = new PlanTester();
+
+ // the parent
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 except all select tag1 from t2 except all select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ project(
+ window(
+ sort(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3"))))))))));
+ }
+
+ @Test
+ public void mergeTwoExceptDistinct() {
+ PlanTester planTester = new PlanTester();
+
+ // the parent
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 except distinct select tag1 from t2 except distinct select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3"))))))));
+ }
+
+ @Test
+ public void mergeExceptAllAndExceptDistinct() {
+ PlanTester planTester = new PlanTester();
+
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 except distinct select tag1 from t2 except all select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3"))))))));
+ }
+
+ @Test
+ public void testMergeNotPossibleForDistinctOverAll() {
+ PlanTester planTester = new PlanTester();
+
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 except all select tag1 from t2 except select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(
+ project(
+ filter(
+ project(
+ window(
+ sort(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2"))))))))),
+ project(tableScan("testdb.t3"))))))));
+ }
+
+ @Test
+ public void testNoMergeForRightChild() {
+ PlanTester planTester = new PlanTester();
+
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 except (select tag1 from t2 except select tag1 from t3) "),
+ output(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t1")),
+ project(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3")))))))))))));
+ }
+}
diff --git a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/MergeIntersectTest.java b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/MergeIntersectTest.java
new file mode 100644
index 0000000..caaff83
--- /dev/null
+++ b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/MergeIntersectTest.java
@@ -0,0 +1,112 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.analyzer;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.PlanTester;
+
+import org.junit.Test;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanAssert.assertPlan;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.aggregation;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.filter;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.output;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.project;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.sort;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.tableScan;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.union;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.window;
+
+/**
+ * For parent and child of type INTERSECT, merge is always possible: 1. if parent and child are both
+ * INTERSECT ALL, the resulting set operation is INTERSECT ALL 2. otherwise, the resulting set
+ * operation is INTERSECT DISTINCT: 3. if the parent is DISTINCT, the result has unique values,
+ * regardless of whether child branches were DISTINCT or ALL, 4. if the child is DISTINCT, that
+ * branch is guaranteed to have unique values, so at most one element of the other branches will be
+ * retained -- this is equivalent to just doing DISTINCT on the parent.
+ */
+public class MergeIntersectTest {
+
+ @Test
+ public void mergeTwoIntersectAll() {
+ PlanTester planTester = new PlanTester();
+
+ // the parent
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 intersect all select tag1 from t2 intersect all select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ project(
+ window(
+ sort(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3"))))))))));
+ }
+
+ @Test
+ public void mergeTwoIntersectDistinct() {
+ PlanTester planTester = new PlanTester();
+
+ // the parent
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 intersect distinct select tag1 from t2 intersect distinct select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3"))))))));
+ }
+
+ @Test
+ public void mergeIntersectAllAndIntersectDistinct() {
+ PlanTester planTester = new PlanTester();
+
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 intersect all select tag1 from t2 intersect distinct select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3"))))))));
+
+ assertPlan(
+ planTester.createPlan(
+ "select tag1 from t1 intersect select tag1 from t2 intersect all select tag1 from t3 "),
+ output(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")),
+ project(tableScan("testdb.t3"))))))));
+ }
+}
diff --git a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/RemoveEmptyExceptBranchesTest.java b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/RemoveEmptyExceptBranchesTest.java
new file mode 100644
index 0000000..914a9bd
--- /dev/null
+++ b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/RemoveEmptyExceptBranchesTest.java
@@ -0,0 +1,101 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.analyzer;
+
+import org.apache.iotdb.db.queryengine.plan.relational.planner.PlanTester;
+
+import org.junit.Test;
+
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanAssert.assertPlan;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.aggregation;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.filter;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.limit;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.output;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.project;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.sort;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.tableScan;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.union;
+import static org.apache.iotdb.db.queryengine.plan.relational.planner.assertions.PlanMatchPattern.window;
+
+public class RemoveEmptyExceptBranchesTest {
+
+ @Test
+ public void removeEmptyExceptBranchesTest1() {
+ // Normal case
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1 limit 0) except (select tag1 from t2) except (select tag1 from t3)"),
+ output((limit(0, tableScan("testdb.t1")))));
+
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1 limit 0) except all (select tag1 from t2) except all (select tag1 from t3)"),
+ output((limit(0, tableScan("testdb.t1")))));
+ }
+
+ @Test
+ public void removeEmptyExceptBranchesTest2() {
+ // Normal case
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1 ) except (select tag1 from t2 limit 0) except (select tag1 from t3 limit 0)"),
+ output(aggregation(tableScan("testdb.t1"))));
+
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1) except all (select tag1 from t2 limit 0) except all (select tag1 from t3 limit 0)"),
+ output((tableScan("testdb.t1"))));
+ }
+
+ @Test
+ public void removeEmptyExceptBranchesTest3() {
+ // Normal case
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1) except (select tag1 from t2) except (select tag1 from t3 limit 0)"),
+ output(
+ aggregation(
+ project(
+ filter(
+ aggregation(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2")))))))));
+
+ assertPlan(
+ new PlanTester()
+ .createPlan(
+ "(select tag1 from t1) except all (select tag1 from t2 ) except all (select tag1 from t3 limit 0)"),
+ output(
+ project(
+ filter(
+ project(
+ window(
+ sort(
+ union(
+ project(tableScan("testdb.t1")),
+ project(tableScan("testdb.t2"))))))))));
+ }
+}
