You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by yi...@apache.org on 2022/12/20 01:43:47 UTC
[doris] branch master updated: [feature](planner) compact multi-euqals to in-predicate #14876
This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 320b264c9d [feature](planner) compact multi-euqals to in-predicate #14876
320b264c9d is described below
commit 320b264c9dabc155ee79616764b23883540a708a
Author: minghong <mi...@163.com>
AuthorDate: Tue Dec 20 09:43:34 2022 +0800
[feature](planner) compact multi-euqals to in-predicate #14876
---
.../java/org/apache/doris/analysis/Analyzer.java | 2 +
.../rewrite/CompactEqualsToInPredicateRule.java | 160 +++++++++++++++++++++
.../doris/analysis/PartitionPruneTestBase.java | 2 -
.../CompactEqualsToInPredicateRuleTest.java | 116 +++++++++++++++
.../data/performance_p0/redundant_conjuncts.out | 2 +-
5 files changed, 279 insertions(+), 3 deletions(-)
diff --git a/fe/fe-core/src/main/java/org/apache/doris/analysis/Analyzer.java b/fe/fe-core/src/main/java/org/apache/doris/analysis/Analyzer.java
index a34146c607..85289d9044 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/analysis/Analyzer.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/analysis/Analyzer.java
@@ -46,6 +46,7 @@ import org.apache.doris.planner.PlanNode;
import org.apache.doris.planner.RuntimeFilter;
import org.apache.doris.qe.ConnectContext;
import org.apache.doris.rewrite.BetweenToCompoundRule;
+import org.apache.doris.rewrite.CompactEqualsToInPredicateRule;
import org.apache.doris.rewrite.CompoundPredicateWriteRule;
import org.apache.doris.rewrite.ExprRewriteRule;
import org.apache.doris.rewrite.ExprRewriter;
@@ -410,6 +411,7 @@ public class Analyzer {
rules.add(RewriteEncryptKeyRule.INSTANCE);
rules.add(RewriteInPredicateRule.INSTANCE);
rules.add(RewriteAliasFunctionRule.INSTANCE);
+ rules.add(CompactEqualsToInPredicateRule.INSTANCE);
List<ExprRewriteRule> onceRules = Lists.newArrayList();
onceRules.add(ExtractCommonFactorsRule.INSTANCE);
onceRules.add(InferFiltersRule.INSTANCE);
diff --git a/fe/fe-core/src/main/java/org/apache/doris/rewrite/CompactEqualsToInPredicateRule.java b/fe/fe-core/src/main/java/org/apache/doris/rewrite/CompactEqualsToInPredicateRule.java
new file mode 100644
index 0000000000..7375b83121
--- /dev/null
+++ b/fe/fe-core/src/main/java/org/apache/doris/rewrite/CompactEqualsToInPredicateRule.java
@@ -0,0 +1,160 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.rewrite;
+
+import org.apache.doris.analysis.Analyzer;
+import org.apache.doris.analysis.BinaryPredicate;
+import org.apache.doris.analysis.CompoundPredicate;
+import org.apache.doris.analysis.CompoundPredicate.Operator;
+import org.apache.doris.analysis.Expr;
+import org.apache.doris.analysis.InPredicate;
+import org.apache.doris.analysis.LiteralExpr;
+import org.apache.doris.analysis.SlotRef;
+import org.apache.doris.common.AnalysisException;
+import org.apache.doris.common.Pair;
+import org.apache.doris.rewrite.ExprRewriter.ClauseType;
+
+import com.google.common.collect.Lists;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+/*
+a = 1 or a = 2 or a = 3 or a in (4, 5, 6) => a in (1, 2, 3, 4, 5, 6)
+ */
+public class CompactEqualsToInPredicateRule implements ExprRewriteRule {
+ public static CompactEqualsToInPredicateRule INSTANCE = new CompactEqualsToInPredicateRule();
+ private static final int COMPACT_SIZE = 2;
+
+ @Override
+ public Expr apply(Expr expr, Analyzer analyzer, ClauseType clauseType) throws AnalysisException {
+ if (expr == null) {
+ return expr;
+ }
+ if (expr instanceof CompoundPredicate) {
+ CompoundPredicate comp = (CompoundPredicate) expr;
+ if (comp.getOp() == Operator.OR) {
+ Pair<Boolean, Expr> compactResult = compactEqualsToInPredicate(expr);
+ if (compactResult.first) {
+ return compactResult.second;
+ }
+ }
+ }
+ return expr;
+ }
+
+ /*
+ expr in form of A or B or ...
+ */
+ private Pair<Boolean, Expr> compactEqualsToInPredicate(Expr expr) {
+ boolean changed = false;
+ List<Expr> disConjuncts = getDisconjuncts(expr);
+ if (disConjuncts.size() < COMPACT_SIZE) {
+ return Pair.of(false, expr);
+ }
+ Map<SlotRef, Set<Expr>> equalMap = new HashMap<>();
+ Map<SlotRef, InPredicate> inPredMap = new HashMap<>();
+ Expr result = null;
+ for (Expr disConj : disConjuncts) {
+ if (disConj instanceof BinaryPredicate
+ && ((BinaryPredicate) disConj).getOp() == BinaryPredicate.Operator.EQ) {
+ BinaryPredicate binary = (BinaryPredicate) disConj;
+ if (binary.getChild(0) instanceof SlotRef
+ && binary.getChild(1) instanceof LiteralExpr) {
+ equalMap.computeIfAbsent((SlotRef) binary.getChild(0), k -> new HashSet<>());
+ equalMap.get((SlotRef) binary.getChild(0)).add((LiteralExpr) binary.getChild(1));
+ } else if (binary.getChild(0) instanceof LiteralExpr
+ && binary.getChild(1) instanceof SlotRef) {
+ equalMap.computeIfAbsent((SlotRef) binary.getChild(1), k -> new HashSet<>());
+ equalMap.get((SlotRef) binary.getChild(1)).add((LiteralExpr) binary.getChild(0));
+ } else {
+ result = addDisconjunct(result, disConj);
+ }
+ } else if (disConj instanceof InPredicate && !((InPredicate) disConj).isNotIn()) {
+ InPredicate in = (InPredicate) disConj;
+ Expr compareExpr = in.getChild(0);
+ if (compareExpr instanceof SlotRef) {
+ SlotRef slot = (SlotRef) compareExpr;
+ InPredicate val = inPredMap.get(slot);
+ if (val == null) {
+ inPredMap.put(slot, in);
+ } else {
+ val.getChildren().addAll(in.getListChildren());
+ inPredMap.put(slot, val);
+ }
+ }
+ } else {
+ result = addDisconjunct(result, disConj);
+ }
+ }
+
+ for (Entry<SlotRef, Set<Expr>> entry : equalMap.entrySet()) {
+ SlotRef slot = entry.getKey();
+ InPredicate in = inPredMap.get(slot);
+ if (entry.getValue().size() >= COMPACT_SIZE || in != null) {
+ if (in == null) {
+ in = new InPredicate(entry.getKey(), Lists.newArrayList(entry.getValue()), false);
+ inPredMap.put(slot, in);
+ } else {
+ in.getChildren().addAll(Lists.newArrayList(entry.getValue()));
+ }
+ changed = true;
+ } else {
+ for (Expr right : entry.getValue()) {
+ result = addDisconjunct(result,
+ new BinaryPredicate(BinaryPredicate.Operator.EQ,
+ entry.getKey(),
+ right));
+ }
+ }
+ }
+ for (InPredicate in : inPredMap.values()) {
+ result = addDisconjunct(result, in);
+ }
+ return Pair.of(changed, result);
+ }
+
+ private Expr addDisconjunct(Expr result, Expr conj) {
+ if (result == null) {
+ return conj;
+ } else {
+ return new CompoundPredicate(Operator.OR, result, conj);
+ }
+ }
+
+ private List<Expr> getDisconjuncts(Expr expr) {
+ List<Expr> result = new ArrayList<>();
+ if (expr instanceof CompoundPredicate) {
+ CompoundPredicate comp = ((CompoundPredicate) expr);
+ if (comp.getOp() == Operator.OR) {
+ result.addAll(getDisconjuncts(comp.getChild(0)));
+ result.addAll(getDisconjuncts(comp.getChild(1)));
+ } else {
+ result.add(expr);
+ }
+ } else {
+ result.add(expr);
+ }
+ return result;
+ }
+}
diff --git a/fe/fe-core/src/test/java/org/apache/doris/analysis/PartitionPruneTestBase.java b/fe/fe-core/src/test/java/org/apache/doris/analysis/PartitionPruneTestBase.java
index 95c4790bea..7ff8e2fda1 100644
--- a/fe/fe-core/src/test/java/org/apache/doris/analysis/PartitionPruneTestBase.java
+++ b/fe/fe-core/src/test/java/org/apache/doris/analysis/PartitionPruneTestBase.java
@@ -29,8 +29,6 @@ public abstract class PartitionPruneTestBase extends TestWithFeService {
protected void doTest() throws Exception {
for (RangePartitionPruneTest.TestCase testCase : cases) {
- connectContext.getSessionVariable().partitionPruneAlgorithmVersion = 1;
- assertExplainContains(1, testCase.sql, testCase.v1Result);
connectContext.getSessionVariable().partitionPruneAlgorithmVersion = 2;
assertExplainContains(2, testCase.sql, testCase.v2Result);
}
diff --git a/fe/fe-core/src/test/java/org/apache/doris/rewrite/CompactEqualsToInPredicateRuleTest.java b/fe/fe-core/src/test/java/org/apache/doris/rewrite/CompactEqualsToInPredicateRuleTest.java
new file mode 100644
index 0000000000..baa694ea42
--- /dev/null
+++ b/fe/fe-core/src/test/java/org/apache/doris/rewrite/CompactEqualsToInPredicateRuleTest.java
@@ -0,0 +1,116 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.rewrite;
+
+import org.apache.doris.analysis.BinaryPredicate;
+import org.apache.doris.analysis.CompoundPredicate;
+import org.apache.doris.analysis.CompoundPredicate.Operator;
+import org.apache.doris.analysis.InPredicate;
+import org.apache.doris.analysis.IntLiteral;
+import org.apache.doris.analysis.SlotRef;
+import org.apache.doris.analysis.TableName;
+import org.apache.doris.common.Pair;
+import org.apache.doris.common.jmockit.Deencapsulation;
+import org.apache.doris.datasource.InternalCatalog;
+
+import com.google.common.collect.Lists;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.HashSet;
+
+public class CompactEqualsToInPredicateRuleTest {
+ private static final String internalCtl = InternalCatalog.INTERNAL_CATALOG_NAME;
+
+ //a=1 or b=2 or a=3 or b=4
+ //=> a in (1, 2) or b in (3, 4)
+ @Test
+ public void testCompactEquals() {
+ SlotRef a = new SlotRef(new TableName(internalCtl, "db1", "tb1"), "a");
+ SlotRef b = new SlotRef(new TableName(internalCtl, "db1", "tb1"), "b");
+ IntLiteral i1 = new IntLiteral(1);
+ IntLiteral i2 = new IntLiteral(2);
+ IntLiteral i3 = new IntLiteral(3);
+ IntLiteral i4 = new IntLiteral(4);
+ BinaryPredicate aeq1 = new BinaryPredicate(BinaryPredicate.Operator.EQ, i1, a);
+ BinaryPredicate aeq3 = new BinaryPredicate(BinaryPredicate.Operator.EQ, a, i3);
+ BinaryPredicate beq2 = new BinaryPredicate(BinaryPredicate.Operator.EQ, b, i2);
+ BinaryPredicate beq4 = new BinaryPredicate(BinaryPredicate.Operator.EQ, b, i4);
+ CompoundPredicate or1 = new CompoundPredicate(Operator.OR, aeq1, beq2);
+ CompoundPredicate or2 = new CompoundPredicate(Operator.OR, or1, aeq3);
+ CompoundPredicate or3 = new CompoundPredicate(Operator.OR, or2, beq4);
+ CompactEqualsToInPredicateRule rule = new CompactEqualsToInPredicateRule();
+ Pair result = Deencapsulation.invoke(rule,
+ "compactEqualsToInPredicate", or3);
+ Assertions.assertEquals(true, result.first);
+ Assertions.assertTrue(result.second instanceof CompoundPredicate);
+ CompoundPredicate or = (CompoundPredicate) result.second;
+ Assertions.assertEquals(Operator.OR, or.getOp());
+ InPredicate in1 = (InPredicate) or.getChild(0);
+ InPredicate in2 = (InPredicate) or.getChild(1);
+ SlotRef s1 = (SlotRef) in1.getChildren().get(0);
+ InPredicate tmp;
+ if (s1.getColumnName().equals("b")) {
+ tmp = in1;
+ in1 = in2;
+ in2 = tmp;
+ }
+ Assertions.assertEquals(in1.getChild(0), a);
+ Assertions.assertEquals(in2.getChild(0), b);
+
+ HashSet<IntLiteral> seta = new HashSet<>();
+ seta.add(i1);
+ seta.add(i3);
+ HashSet<IntLiteral> setb = new HashSet<>();
+ setb.add(i2);
+ setb.add(i4);
+
+ Assertions.assertTrue(seta.contains(in1.getChild(1)));
+ Assertions.assertTrue(seta.contains(in1.getChild(2)));
+
+ Assertions.assertTrue(setb.contains(in2.getChild(1)));
+ Assertions.assertTrue(setb.contains(in2.getChild(2)));
+ }
+
+ //a=1 or a in (3, 2) => a in (1, 2, 3)
+ @Test
+ public void testCompactEqualsAndIn() {
+ SlotRef a = new SlotRef(new TableName(internalCtl, "db1", "tb1"), "a");
+ IntLiteral i1 = new IntLiteral(1);
+ IntLiteral i2 = new IntLiteral(2);
+ IntLiteral i3 = new IntLiteral(3);
+ BinaryPredicate aeq1 = new BinaryPredicate(BinaryPredicate.Operator.EQ, i1, a);
+ InPredicate ain23 = new InPredicate(a, Lists.newArrayList(i2, i3), false);
+ CompoundPredicate or1 = new CompoundPredicate(Operator.OR, aeq1, ain23);
+ CompactEqualsToInPredicateRule rule = new CompactEqualsToInPredicateRule();
+ Pair result = Deencapsulation.invoke(rule,
+ "compactEqualsToInPredicate", or1);
+ Assertions.assertEquals(true, result.first);
+ Assertions.assertTrue(result.second instanceof InPredicate);
+ InPredicate in123 = (InPredicate) result.second;
+ Assertions.assertEquals(in123.getChild(0), a);
+ HashSet<IntLiteral> seta = new HashSet<>();
+ seta.add(i1);
+ seta.add(i2);
+ seta.add(i3);
+
+ Assertions.assertTrue(seta.contains(in123.getChild(1)));
+ Assertions.assertTrue(seta.contains(in123.getChild(2)));
+ Assertions.assertTrue(seta.contains(in123.getChild(3)));
+ }
+}
diff --git a/regression-test/data/performance_p0/redundant_conjuncts.out b/regression-test/data/performance_p0/redundant_conjuncts.out
index 98178f31aa..9cba503956 100644
--- a/regression-test/data/performance_p0/redundant_conjuncts.out
+++ b/regression-test/data/performance_p0/redundant_conjuncts.out
@@ -23,7 +23,7 @@ PLAN FRAGMENT 0
0:VOlapScanNode
TABLE: default_cluster:regression_test_performance_p0.redundant_conjuncts(redundant_conjuncts), PREAGGREGATION: OFF. Reason: No AggregateInfo
- PREDICATES: (`k1` = 1 OR `k1` = 2)
+ PREDICATES: `k1` IN (2, 1)
partitions=0/1, tablets=0/0, tabletList=
cardinality=0, avgRowSize=8.0, numNodes=1
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org