This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch branch-2.1
in repository https://gitbox.apache.org/repos/asf/doris.git
commit a720e03a02d833ba548479bc538391cb268b233c
Author: seawinde <149132972+seawi...@users.noreply.github.com>
AuthorDate: Wed Apr 24 18:56:36 2024 +0800
[improvement](mtmv) Optimize the nested materialized view rewrite
performance (#34050)
Optimize the nested materialized view rewrite performance when exists many
join
This is brought by #33362
---
.../java/org/apache/doris/nereids/memo/Memo.java | 4 ++
.../apache/doris/nereids/memo/StructInfoMap.java | 59 +++++++++++++++-------
.../nereids/rules/exploration/mv/StructInfo.java | 14 +++--
3 files changed, 57 insertions(+), 20 deletions(-)
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
index 854ff0f51cb..db12c02e79a 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
@@ -411,6 +411,9 @@ public class Memo {
Preconditions.checkState(groupExpressions.containsKey(groupExpr.get()));
return CopyInResult.of(false, groupExpr.get());
}
+ if (targetGroup != null) {
+ targetGroup.getstructInfoMap().setRefreshed(false);
+ }
List<Group> childrenGroups = Lists.newArrayList();
for (int i = 0; i < plan.children().size(); i++) {
// skip useless project.
@@ -559,6 +562,7 @@ public class Memo {
if (source == root) {
root = destination;
}
+ destination.getstructInfoMap().setRefreshed(false);
groups.remove(source.getGroupId());
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/StructInfoMap.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/StructInfoMap.java
index a14c2070a8f..4119c6f2f89 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/StructInfoMap.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/StructInfoMap.java
@@ -29,10 +29,11 @@ import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
-import java.util.stream.Collectors;
import javax.annotation.Nullable;
/**
@@ -41,6 +42,7 @@ import javax.annotation.Nullable;
public class StructInfoMap {
private final Map<BitSet, Pair<GroupExpression, List<BitSet>>>
groupExpressionMap = new HashMap<>();
private final Map<BitSet, StructInfo> infoMap = new HashMap<>();
+ private boolean refreshed;
/**
* get struct info according to table map
@@ -79,6 +81,14 @@ public class StructInfoMap {
return groupExpressionMap.get(tableMap);
}
+ public boolean isRefreshed() {
+ return refreshed;
+ }
+
+ public void setRefreshed(boolean refreshed) {
+ this.refreshed = refreshed;
+ }
+
private StructInfo constructStructInfo(GroupExpression groupExpression,
List<BitSet> children,
BitSet tableMap, Plan originPlan) {
// this plan is not origin plan, should record origin plan in struct
info
@@ -111,7 +121,7 @@ public class StructInfoMap {
int originSize = groupExpressionMap.size();
for (GroupExpression groupExpression : group.getLogicalExpressions()) {
List<Set<BitSet>> childrenTableMap = new ArrayList<>();
- boolean needRefresh = false;
+ boolean needRefresh = groupExpressionMap.isEmpty();
if (groupExpression.children().isEmpty()) {
BitSet leaf = constructLeaf(groupExpression);
groupExpressionMap.put(leaf, Pair.of(groupExpression, new
ArrayList<>()));
@@ -119,18 +129,33 @@ public class StructInfoMap {
}
for (Group child : groupExpression.children()) {
- if (!refreshedGroup.contains(child)) {
+ if (!refreshedGroup.contains(child) &&
!child.getstructInfoMap().isRefreshed()) {
StructInfoMap childStructInfoMap =
child.getstructInfoMap();
needRefresh |= childStructInfoMap.refresh(child);
+ childStructInfoMap.setRefreshed(true);
}
refreshedGroup.add(child);
childrenTableMap.add(child.getstructInfoMap().getTableMaps());
}
+ // if one same groupExpression have refreshed, continue
+ BitSet oneOfGroupExpressionTableSet = new BitSet();
+ for (Set<BitSet> groupExpressionBitSet : childrenTableMap) {
+ Iterator<BitSet> iterator = groupExpressionBitSet.iterator();
+ if (iterator.hasNext()) {
+ oneOfGroupExpressionTableSet.or(iterator.next());
+ }
+ }
+ if (groupExpressionMap.containsKey(oneOfGroupExpressionTableSet)) {
+ continue;
+ }
// if cumulative child table map is different from current
// or current group expression map is empty, should update the
groupExpressionMap currently
- Set<Pair<BitSet, List<BitSet>>> bitSetWithChildren =
cartesianProduct(childrenTableMap);
- for (Pair<BitSet, List<BitSet>> bitSetWithChild :
bitSetWithChildren) {
- groupExpressionMap.putIfAbsent(bitSetWithChild.first,
Pair.of(groupExpression, bitSetWithChild.second));
+ Collection<Pair<BitSet, List<BitSet>>> bitSetWithChildren =
cartesianProduct(childrenTableMap);
+ if (needRefresh) {
+ for (Pair<BitSet, List<BitSet>> bitSetWithChild :
bitSetWithChildren) {
+ groupExpressionMap.putIfAbsent(bitSetWithChild.first,
+ Pair.of(groupExpression, bitSetWithChild.second));
+ }
}
}
return originSize != groupExpressionMap.size();
@@ -147,17 +172,17 @@ public class StructInfoMap {
return tableMap;
}
- private Set<Pair<BitSet, List<BitSet>>> cartesianProduct(List<Set<BitSet>>
childrenTableMap) {
- return Sets.cartesianProduct(childrenTableMap)
- .stream()
- .map(bitSetList -> {
- BitSet bitSet = new BitSet();
- for (BitSet b : bitSetList) {
- bitSet.or(b);
- }
- return Pair.of(bitSet, bitSetList);
- })
- .collect(Collectors.toSet());
+ private Collection<Pair<BitSet, List<BitSet>>>
cartesianProduct(List<Set<BitSet>> childrenTableMap) {
+ Set<List<BitSet>> cartesianLists =
Sets.cartesianProduct(childrenTableMap);
+ List<Pair<BitSet, List<BitSet>>> resultPairSet = new LinkedList<>();
+ for (List<BitSet> bitSetList : cartesianLists) {
+ BitSet bitSet = new BitSet();
+ for (BitSet b : bitSetList) {
+ bitSet.or(b);
+ }
+ resultPairSet.add(Pair.of(bitSet, bitSetList));
+ }
+ return resultPairSet;
}
@Override
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
index 4979f11c28e..757004071ee 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/StructInfo.java
@@ -443,10 +443,18 @@ public class StructInfo {
}
}
+ /** Judge if source contains all target */
public static boolean containsAll(BitSet source, BitSet target) {
- BitSet intersection = (BitSet) source.clone();
- intersection.and(target);
- return intersection.equals(target);
+ if (source.size() < target.size()) {
+ return false;
+ }
+ for (int i = target.nextSetBit(0); i >= 0; i = target.nextSetBit(i +
1)) {
+ boolean contains = source.get(i);
+ if (!contains) {
+ return false;
+ }
+ }
+ return true;
}
/**
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
