This is an automated email from the ASF dual-hosted git repository.
huajianlan pushed a commit to branch branch-2.1
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-2.1 by this push:
new 3f6c71e47b0 [enhancement](Nereids) fast compute hash code of deep
expression tree to reduce conflict (#38981) (#39133)
3f6c71e47b0 is described below
commit 3f6c71e47b0507c8e9a40f5ed0a75d353f760c06
Author: 924060929 <[email protected]>
AuthorDate: Fri Aug 9 16:28:24 2024 +0800
[enhancement](Nereids) fast compute hash code of deep expression tree to
reduce conflict (#38981) (#39133)
The Expression.hashCode default is getClass().hashCode(), just contains one
level information, so the lots of expressions which is same type will return
the same hash code and conflict, then compare deeply in the HashMap cause
inefficient and hold table lock for long time.
This pr support fast compute hash code by the bottom literal and slot,
reduce the compare expression time because of the conflict of hash code
In my test case, the sql planner time can reduce from 20 minutes(not
finished) to 35 seconds
---
.../post/CommonSubExpressionCollector.java | 14 +++++++++----
.../rules/exploration/mv/PredicatesSplitter.java | 8 ++++----
.../nereids/rules/rewrite/EliminateNotNull.java | 2 +-
.../nereids/trees/expressions/Expression.java | 23 ++++++++++++++++++++--
.../nereids/trees/expressions/Placeholder.java | 10 ++++++++++
.../nereids/trees/expressions/SlotReference.java | 5 +++++
.../nereids/trees/expressions/literal/Literal.java | 5 +++++
.../org/apache/doris/qe/PointQueryExecutor.java | 2 +-
.../rules/expression/PredicatesSplitterTest.java | 2 +-
9 files changed, 58 insertions(+), 13 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/processor/post/CommonSubExpressionCollector.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/processor/post/CommonSubExpressionCollector.java
index 5abc5f6f60f..877e411a539 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/processor/post/CommonSubExpressionCollector.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/processor/post/CommonSubExpressionCollector.java
@@ -37,8 +37,15 @@ public class CommonSubExpressionCollector extends
ExpressionVisitor<Integer, Voi
if (expr.children().isEmpty()) {
return 0;
}
- return
collectCommonExpressionByDepth(expr.children().stream().map(child ->
- child.accept(this, context)).reduce(Math::max).map(m -> m +
1).orElse(1), expr);
+ return collectCommonExpressionByDepth(
+ expr.children()
+ .stream()
+ .map(child -> child.accept(this, context))
+ .reduce(Math::max)
+ .map(m -> m + 1)
+ .orElse(1),
+ expr
+ );
}
private int collectCommonExpressionByDepth(int depth, Expression expr) {
@@ -53,7 +60,6 @@ public class CommonSubExpressionCollector extends
ExpressionVisitor<Integer, Voi
public static Set<Expression> getExpressionsFromDepthMap(
int depth, Map<Integer, Set<Expression>> depthMap) {
- depthMap.putIfAbsent(depth, new LinkedHashSet<>());
- return depthMap.get(depth);
+ return depthMap.computeIfAbsent(depth, d -> new LinkedHashSet<>());
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/PredicatesSplitter.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/PredicatesSplitter.java
index f1c0ae8f96a..f7182eeab73 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/PredicatesSplitter.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/PredicatesSplitter.java
@@ -28,7 +28,7 @@ import
org.apache.doris.nereids.trees.expressions.literal.Literal;
import
org.apache.doris.nereids.trees.expressions.visitor.DefaultExpressionVisitor;
import org.apache.doris.nereids.util.ExpressionUtils;
-import java.util.HashSet;
+import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
@@ -39,9 +39,9 @@ import java.util.Set;
*/
public class PredicatesSplitter {
- private final Set<Expression> equalPredicates = new HashSet<>();
- private final Set<Expression> rangePredicates = new HashSet<>();
- private final Set<Expression> residualPredicates = new HashSet<>();
+ private final Set<Expression> equalPredicates = new LinkedHashSet<>();
+ private final Set<Expression> rangePredicates = new LinkedHashSet<>();
+ private final Set<Expression> residualPredicates = new LinkedHashSet<>();
private final List<Expression> conjunctExpressions;
public PredicatesSplitter(Expression target) {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateNotNull.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateNotNull.java
index 22393cb55f8..b3fe2e1aa91 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateNotNull.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateNotNull.java
@@ -81,7 +81,7 @@ public class EliminateNotNull implements RewriteRuleFactory {
// predicatesNotContainIsNotNull infer nonNullable slots: `id`
// slotsFromIsNotNull: `id`, `name`
// remove `name` (it's generated), remove `id` (because `id > 0`
already contains it)
- Set<Expression> predicatesNotContainIsNotNull = Sets.newHashSet();
+ Set<Expression> predicatesNotContainIsNotNull =
Sets.newLinkedHashSet();
List<Slot> slotsFromIsNotNull = Lists.newArrayList();
for (Expression expr : exprs) {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Expression.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Expression.java
index d7f400955c0..e355cd204cd 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Expression.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Expression.java
@@ -70,6 +70,7 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
private final boolean compareWidthAndDepth;
private final Supplier<Set<Slot>> inputSlots = Suppliers.memoize(
() -> collect(e -> e instanceof Slot && !(e instanceof
ArrayItemSlot)));
+ private final int fastChildrenHashCode;
protected Expression(Expression... children) {
super(children);
@@ -80,12 +81,14 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
this.depth = 1;
this.width = 1;
this.compareWidthAndDepth = supportCompareWidthAndDepth();
+ this.fastChildrenHashCode = 0;
break;
case 1:
Expression child = children[0];
this.depth = child.depth + 1;
this.width = child.width;
this.compareWidthAndDepth = child.compareWidthAndDepth &&
supportCompareWidthAndDepth();
+ this.fastChildrenHashCode = child.fastChildrenHashCode() + 1;
break;
case 2:
Expression left = children[0];
@@ -94,21 +97,25 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
this.width = left.width + right.width;
this.compareWidthAndDepth =
left.compareWidthAndDepth &&
right.compareWidthAndDepth && supportCompareWidthAndDepth();
+ this.fastChildrenHashCode = left.fastChildrenHashCode() +
right.fastChildrenHashCode() + 2;
break;
default:
int maxChildDepth = 0;
int sumChildWidth = 0;
boolean compareWidthAndDepth = true;
+ int fastChildrenHashCode = 0;
for (Expression expression : children) {
child = expression;
maxChildDepth = Math.max(child.depth, maxChildDepth);
sumChildWidth += child.width;
hasUnbound |= child.hasUnbound;
compareWidthAndDepth &= child.compareWidthAndDepth;
+ fastChildrenHashCode = fastChildrenHashCode +
expression.fastChildrenHashCode() + 1;
}
this.depth = maxChildDepth + 1;
this.width = sumChildWidth;
this.compareWidthAndDepth = compareWidthAndDepth;
+ this.fastChildrenHashCode = fastChildrenHashCode;
}
checkLimit();
@@ -129,12 +136,14 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
this.depth = 1;
this.width = 1;
this.compareWidthAndDepth = supportCompareWidthAndDepth();
+ this.fastChildrenHashCode = 0;
break;
case 1:
Expression child = children.get(0);
this.depth = child.depth + 1;
this.width = child.width;
this.compareWidthAndDepth = child.compareWidthAndDepth &&
supportCompareWidthAndDepth();
+ this.fastChildrenHashCode = child.fastChildrenHashCode() + 1;
break;
case 2:
Expression left = children.get(0);
@@ -143,21 +152,25 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
this.width = left.width + right.width;
this.compareWidthAndDepth =
left.compareWidthAndDepth &&
right.compareWidthAndDepth && supportCompareWidthAndDepth();
+ this.fastChildrenHashCode = left.fastChildrenHashCode() +
right.fastChildrenHashCode() + 2;
break;
default:
int maxChildDepth = 0;
int sumChildWidth = 0;
boolean compareWidthAndDepth = true;
+ int fastChildrenhashCode = 0;
for (Expression expression : children) {
child = expression;
maxChildDepth = Math.max(child.depth, maxChildDepth);
sumChildWidth += child.width;
hasUnbound |= child.hasUnbound;
compareWidthAndDepth &= child.compareWidthAndDepth;
+ fastChildrenhashCode = fastChildrenhashCode +
expression.fastChildrenHashCode() + 1;
}
this.depth = maxChildDepth + 1;
this.width = sumChildWidth;
this.compareWidthAndDepth = compareWidthAndDepth &&
supportCompareWidthAndDepth();
+ this.fastChildrenHashCode = fastChildrenhashCode;
}
checkLimit();
@@ -211,6 +224,10 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
return checkInputDataTypesInternal();
}
+ public int fastChildrenHashCode() {
+ return fastChildrenHashCode;
+ }
+
protected TypeCheckResult checkInputDataTypesInternal() {
return TypeCheckResult.SUCCESS;
}
@@ -406,7 +423,9 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
return false;
}
Expression that = (Expression) o;
- if ((compareWidthAndDepth && (this.width != that.width || this.depth
!= that.depth))
+ if ((compareWidthAndDepth
+ && (this.width != that.width || this.depth != that.depth
+ || this.fastChildrenHashCode != that.fastChildrenHashCode))
|| arity() != that.arity() || !extraEquals(that)) {
return false;
}
@@ -430,7 +449,7 @@ public abstract class Expression extends
AbstractTreeNode<Expression> implements
@Override
public int hashCode() {
- return getClass().hashCode();
+ return getClass().hashCode() + fastChildrenHashCode();
}
/**
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Placeholder.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Placeholder.java
index 0432beadd2c..c79c2d9db6d 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Placeholder.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/Placeholder.java
@@ -60,11 +60,21 @@ public class Placeholder extends Expression implements
LeafExpression {
return true;
}
+ @Override
+ public String toString() {
+ return "$" + placeholderId.asInt();
+ }
+
@Override
public String toSql() {
return "?";
}
+ @Override
+ public int fastChildrenHashCode() {
+ return placeholderId.asInt();
+ }
+
@Override
public DataType getDataType() throws UnboundException {
return NullType.INSTANCE;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/SlotReference.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/SlotReference.java
index 145d8dd29f7..679c8ab73bd 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/SlotReference.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/SlotReference.java
@@ -237,6 +237,11 @@ public class SlotReference extends Slot {
return exprId.asInt();
}
+ @Override
+ public int fastChildrenHashCode() {
+ return exprId.asInt();
+ }
+
@Override
public <R, C> R accept(ExpressionVisitor<R, C> visitor, C context) {
return visitor.visitSlotReference(this, context);
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/literal/Literal.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/literal/Literal.java
index fe53cbf0e2a..e8e37aaf697 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/literal/Literal.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/expressions/literal/Literal.java
@@ -365,6 +365,11 @@ public abstract class Literal extends Expression
implements LeafExpression, Comp
return Objects.hashCode(getValue());
}
+ @Override
+ public int fastChildrenHashCode() {
+ return Objects.hashCode(getValue());
+ }
+
@Override
public String toString() {
return String.valueOf(getValue());
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/qe/PointQueryExecutor.java
b/fe/fe-core/src/main/java/org/apache/doris/qe/PointQueryExecutor.java
index b0af8431471..68b1eb6ab93 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/qe/PointQueryExecutor.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/qe/PointQueryExecutor.java
@@ -136,7 +136,7 @@ public class PointQueryExecutor implements CoordInterface {
} else if (binaryPredicate.getChild(1) instanceof LiteralExpr) {
binaryPredicate.setChild(1, conjunctVals.get(i));
} else {
- Preconditions.checkState(false, "Should conatains literal in "
+ binaryPredicate.toSqlImpl());
+ Preconditions.checkState(false, "Should contains literal in "
+ binaryPredicate.toSqlImpl());
}
}
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/expression/PredicatesSplitterTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/expression/PredicatesSplitterTest.java
index 56c0a6b8341..0374244ce56 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/expression/PredicatesSplitterTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/expression/PredicatesSplitterTest.java
@@ -61,7 +61,7 @@ public class PredicatesSplitterTest extends
ExpressionRewriteTestHelper {
String expectedRangeExpr,
String expectedResidualExpr) {
- Map<String, Slot> mem = Maps.newHashMap();
+ Map<String, Slot> mem = Maps.newLinkedHashMap();
Expression targetExpr =
replaceUnboundSlot(PARSER.parseExpression(expression), mem);
SplitPredicate splitPredicate = Predicates.splitPredicates(targetExpr);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
