This is an automated email from the ASF dual-hosted git repository. jackietien pushed a commit to branch force_ci/object_type in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit a113051e3b49d072631766f565b6696e8e739607 Author: alpass163 <[email protected]> AuthorDate: Sat Nov 29 07:27:05 2025 +0800 implement intersect and except related optimization rule: MergeIntersect, MergeExcept, RemoveEmptyIntersectBranchs, EvaluateEmptyIntersect, PruneIntersectSourceColumns, PruneExceptSourceColmns (#16761) (cherry picked from commit bd813d85c622e1884bdd8b45d7a9338aad2f1cd3) --- .../iterative/rule/EvaluateEmptyIntersect.java | 63 +++++++++ .../planner/iterative/rule/MergeExcept.java | 47 +++++++ .../planner/iterative/rule/MergeIntersect.java | 47 +++++++ .../iterative/rule/PruneExceptSourceColumns.java | 54 ++++++++ .../rule/PruneIntersectSourceColumns.java | 55 ++++++++ .../iterative/rule/RemoveEmptyExceptBranches.java | 139 +++++++++++++++++++ .../planner/iterative/rule/SetOperationMerge.java | 123 +++++++++++++++-- .../optimizations/LogicalOptimizeFactory.java | 34 +++-- .../analyzer/EvaluateEmptyIntersectTest.java | 48 +++++++ .../plan/relational/analyzer/MergeExceptTest.java | 147 +++++++++++++++++++++ .../relational/analyzer/MergeIntersectTest.java | 112 ++++++++++++++++ .../analyzer/RemoveEmptyExceptBranchesTest.java | 101 ++++++++++++++ 12 files changed, 950 insertions(+), 20 deletions(-) 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 00000000000..03c8bba9a7e --- /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 00000000000..08fb908e22f --- /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 00000000000..1786909ec99 --- /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 00000000000..cc210653426 --- /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 00000000000..9fabb9b5b1b --- /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 00000000000..b07531ef9a1 --- /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 563a3883cbb..04dee3888bb 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.planner.plan.node.PlanNode; 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 @@ public class SetOperationMerge { 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 @@ public class SetOperationMerge { 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 @@ public class SetOperationMerge { 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 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 UnionNode( - node.getPlanNodeId(), newSources, newMappingsBuilder.build(), node.getOutputSymbols())); + new ExceptNode( + node.getPlanNodeId(), + newSources, + newMappingsBuilder.build(), + node.getOutputSymbols(), + mergedQuantifier.get())); } private void addMergedMappings( @@ -126,9 +180,24 @@ public class SetOperationMerge { /** * 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 @@ public class SetOperationMerge { 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 d7084c3d24e..1c73274ec99 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.Iterati 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.Im 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.Pr 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.Pu 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 @@ public class LogicalOptimizeFactory { new PruneCorrelatedJoinColumns(), new PruneCorrelatedJoinCorrelation(), new PruneEnforceSingleRowColumns(), + new PruneExceptSourceColumns(), new PruneFilterColumns(), + new PruneIntersectSourceColumns(), new PruneGapFillColumns(), new PruneFillColumns(), new PruneLimitColumns(), @@ -216,6 +224,8 @@ public class LogicalOptimizeFactory { ImmutableSet.of( new ImplementTableFunctionSource(), new RemoveEmptyUnionBranches(), + new EvaluateEmptyIntersect(), + new RemoveEmptyExceptBranches(), new MergeFilters(), new InlineProjections(plannerContext), new RemoveRedundantIdentityProjections(), @@ -258,8 +268,10 @@ public class LogicalOptimizeFactory { .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 @@ public class LogicalOptimizeFactory { .addAll( ImmutableSet.of( new MergeUnion(), - // new MergeIntersect - // new MergeExcept + new MergeIntersect(), + new MergeExcept(), new PruneDistinctAggregation())) .build()), new IterativeOptimizer( @@ -336,11 +348,17 @@ public class LogicalOptimizeFactory { // 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 00000000000..a69b4af288c --- /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 00000000000..41275bf99ba --- /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 00000000000..caaff833e9d --- /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 00000000000..914a9bdae0b --- /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")))))))))); + } +}
