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 52031c86b7c2fbe713740740a488f150676eabde
Author: seawinde <149132972+seawi...@users.noreply.github.com>
AuthorDate: Thu Apr 25 22:11:14 2024 +0800
[improvement](mtmv) Optimize the performance of nested materialized view
rewriting (#34127)
Optimize the performance of nested materialized view rewriting gracefully,
future performance optimzie base on this.
---
.../java/org/apache/doris/nereids/memo/Memo.java | 17 ++++-
.../apache/doris/nereids/memo/StructInfoMap.java | 86 +++++++++++-----------
.../mv/AbstractMaterializedViewRule.java | 1 +
.../exploration/mv/MaterializedViewUtils.java | 13 +++-
.../doris/nereids/memo/StructInfoMapTest.java | 20 ++---
5 files changed, 77 insertions(+), 60 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 db12c02e79a..8793cb5be51 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
@@ -17,6 +17,7 @@
package org.apache.doris.nereids.memo;
+import org.apache.doris.catalog.MTMV;
import org.apache.doris.common.IdGenerator;
import org.apache.doris.common.Pair;
import org.apache.doris.nereids.cost.Cost;
@@ -33,6 +34,7 @@ import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.plans.GroupPlan;
import org.apache.doris.nereids.trees.plans.LeafPlan;
import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.algebra.CatalogRelation;
import org.apache.doris.nereids.trees.plans.algebra.SetOperation;
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
@@ -55,6 +57,7 @@ import java.util.Map;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Set;
+import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import javax.annotation.Nullable;
@@ -69,6 +72,8 @@ public class Memo {
EventChannel.getDefaultChannel().addConsumers(new
LogConsumer(GroupMergeEvent.class, EventChannel.LOG)));
private static long stateId = 0;
private final ConnectContext connectContext;
+ private final Set<Long> needRefreshTableIdSet = new HashSet<>();
+ private final AtomicLong refreshVersion = new AtomicLong(1);
private final IdGenerator<GroupId> groupIdGenerator =
GroupId.createGenerator();
private final Map<GroupId, Group> groups = Maps.newLinkedHashMap();
// we could not use Set, because Set does not have get method.
@@ -118,6 +123,10 @@ public class Memo {
return groupExpressions.size();
}
+ public long getRefreshVersion() {
+ return refreshVersion.get();
+ }
+
private Plan skipProject(Plan plan, Group targetGroup) {
// Some top project can't be eliminated
if (plan instanceof LogicalProject && ((LogicalProject<?>)
plan).canEliminate()) {
@@ -406,14 +415,15 @@ public class Memo {
plan.getLogicalProperties(),
targetGroup.getLogicalProperties());
throw new IllegalStateException("Insert a plan into targetGroup
but differ in logicalproperties");
}
+ // TODO Support sync materialized view in the future
+ if (plan instanceof CatalogRelation && ((CatalogRelation)
plan).getTable() instanceof MTMV) {
+ refreshVersion.incrementAndGet();
+ }
Optional<GroupExpression> groupExpr = plan.getGroupExpression();
if (groupExpr.isPresent()) {
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.
@@ -562,7 +572,6 @@ 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 4119c6f2f89..efa2bef1792 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
@@ -42,31 +42,34 @@ 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;
+ private long refreshVersion = 0;
/**
* get struct info according to table map
*
- * @param mvTableMap the original table map
+ * @param tableMap the original table map
* @param foldTableMap the fold table map
* @param group the group that the mv matched
* @return struct info or null if not found
*/
- public @Nullable StructInfo getStructInfo(BitSet mvTableMap, BitSet
foldTableMap, Group group, Plan originPlan) {
- if (!infoMap.containsKey(mvTableMap)) {
- if ((groupExpressionMap.containsKey(foldTableMap) ||
groupExpressionMap.isEmpty())
- && !groupExpressionMap.containsKey(mvTableMap)) {
- refresh(group);
- }
- if (groupExpressionMap.containsKey(mvTableMap)) {
- Pair<GroupExpression, List<BitSet>> groupExpressionBitSetPair
= getGroupExpressionWithChildren(
- mvTableMap);
- StructInfo structInfo =
constructStructInfo(groupExpressionBitSetPair.first,
- groupExpressionBitSetPair.second, mvTableMap,
originPlan);
- infoMap.put(mvTableMap, structInfo);
- }
+ public @Nullable StructInfo getStructInfo(Memo memo, BitSet tableMap,
BitSet foldTableMap,
+ Group group, Plan originPlan) {
+ StructInfo structInfo = infoMap.get(tableMap);
+ if (structInfo != null) {
+ return structInfo;
+ }
+ if (groupExpressionMap.isEmpty() ||
!groupExpressionMap.containsKey(tableMap)) {
+ refresh(group, memo.getRefreshVersion(), foldTableMap);
+
group.getstructInfoMap().setRefreshVersion(memo.getRefreshVersion());
}
- return infoMap.get(mvTableMap);
+ if (groupExpressionMap.containsKey(tableMap)) {
+ Pair<GroupExpression, List<BitSet>> groupExpressionBitSetPair =
getGroupExpressionWithChildren(
+ tableMap);
+ structInfo = constructStructInfo(groupExpressionBitSetPair.first,
+ groupExpressionBitSetPair.second, tableMap, originPlan);
+ infoMap.put(tableMap, structInfo);
+ }
+ return structInfo;
}
public Set<BitSet> getTableMaps() {
@@ -81,12 +84,12 @@ public class StructInfoMap {
return groupExpressionMap.get(tableMap);
}
- public boolean isRefreshed() {
- return refreshed;
+ public long getRefreshVersion() {
+ return refreshVersion;
}
- public void setRefreshed(boolean refreshed) {
- this.refreshed = refreshed;
+ public void setRefreshVersion(long refreshVersion) {
+ this.refreshVersion = refreshVersion;
}
private StructInfo constructStructInfo(GroupExpression groupExpression,
List<BitSet> children,
@@ -114,27 +117,24 @@ public class StructInfoMap {
*
* @param group the root group
*
- * @return whether groupExpressionMap is updated
*/
- public boolean refresh(Group group) {
- Set<Group> refreshedGroup = new HashSet<>();
- int originSize = groupExpressionMap.size();
+ public void refresh(Group group, long refreshVersion, BitSet targetBitSet)
{
+ Set<Integer> refreshedGroup = new HashSet<>();
for (GroupExpression groupExpression : group.getLogicalExpressions()) {
- List<Set<BitSet>> childrenTableMap = new ArrayList<>();
- boolean needRefresh = groupExpressionMap.isEmpty();
+ List<Set<BitSet>> childrenTableMap = new LinkedList<>();
if (groupExpression.children().isEmpty()) {
BitSet leaf = constructLeaf(groupExpression);
- groupExpressionMap.put(leaf, Pair.of(groupExpression, new
ArrayList<>()));
+ groupExpressionMap.put(leaf, Pair.of(groupExpression, new
LinkedList<>()));
continue;
}
-
for (Group child : groupExpression.children()) {
- if (!refreshedGroup.contains(child) &&
!child.getstructInfoMap().isRefreshed()) {
- StructInfoMap childStructInfoMap =
child.getstructInfoMap();
- needRefresh |= childStructInfoMap.refresh(child);
- childStructInfoMap.setRefreshed(true);
+ StructInfoMap childStructInfoMap = child.getstructInfoMap();
+ if (!refreshedGroup.contains(child.getGroupId().asInt())
+ && refreshVersion !=
childStructInfoMap.getRefreshVersion()) {
+ childStructInfoMap.refresh(child, refreshVersion,
targetBitSet);
+ childStructInfoMap.setRefreshVersion(refreshVersion);
}
- refreshedGroup.add(child);
+ refreshedGroup.add(child.getGroupId().asInt());
childrenTableMap.add(child.getstructInfoMap().getTableMaps());
}
// if one same groupExpression have refreshed, continue
@@ -150,15 +150,14 @@ public class StructInfoMap {
}
// if cumulative child table map is different from current
// or current group expression map is empty, should update the
groupExpressionMap currently
- 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));
- }
+ Collection<Pair<BitSet, List<BitSet>>> bitSetWithChildren =
cartesianProduct(childrenTableMap,
+ new BitSet());
+ for (Pair<BitSet, List<BitSet>> bitSetWithChild :
bitSetWithChildren) {
+ groupExpressionMap.putIfAbsent(bitSetWithChild.first,
+ Pair.of(groupExpression, bitSetWithChild.second));
}
+
}
- return originSize != groupExpressionMap.size();
}
private BitSet constructLeaf(GroupExpression groupExpression) {
@@ -172,7 +171,8 @@ public class StructInfoMap {
return tableMap;
}
- private Collection<Pair<BitSet, List<BitSet>>>
cartesianProduct(List<Set<BitSet>> childrenTableMap) {
+ private Collection<Pair<BitSet, List<BitSet>>>
cartesianProduct(List<Set<BitSet>> childrenTableMap,
+ BitSet targetBitSet) {
Set<List<BitSet>> cartesianLists =
Sets.cartesianProduct(childrenTableMap);
List<Pair<BitSet, List<BitSet>>> resultPairSet = new LinkedList<>();
for (List<BitSet> bitSetList : cartesianLists) {
@@ -180,6 +180,10 @@ public class StructInfoMap {
for (BitSet b : bitSetList) {
bitSet.or(b);
}
+ // filter the useless bitset which targetBitSet not contains,
avoid exponential expansion
+ if (!targetBitSet.isEmpty() &&
!StructInfo.containsAll(targetBitSet, bitSet)) {
+ continue;
+ }
resultPairSet.add(Pair.of(bitSet, bitSetList));
}
return resultPairSet;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewRule.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewRule.java
index 6bf47f00c35..3405942c3a8 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewRule.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/AbstractMaterializedViewRule.java
@@ -142,6 +142,7 @@ public abstract class AbstractMaterializedViewRule
implements ExplorationRuleFac
protected List<StructInfo> getValidQueryStructInfos(Plan queryPlan,
CascadesContext cascadesContext,
BitSet materializedViewTableSet) {
List<StructInfo> validStructInfos = new ArrayList<>();
+ // For every materialized view we should trigger refreshing struct
info map
List<StructInfo> uncheckedStructInfos =
MaterializedViewUtils.extractStructInfo(queryPlan, cascadesContext,
materializedViewTableSet);
uncheckedStructInfos.forEach(queryStructInfo -> {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/MaterializedViewUtils.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/MaterializedViewUtils.java
index 46d0adde06e..5f7dc419eaf 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/MaterializedViewUtils.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/MaterializedViewUtils.java
@@ -148,16 +148,23 @@ public class MaterializedViewUtils {
if (plan.getGroupExpression().isPresent()) {
Group ownerGroup = plan.getGroupExpression().get().getOwnerGroup();
StructInfoMap structInfoMap = ownerGroup.getstructInfoMap();
- structInfoMap.refresh(ownerGroup);
+ if (cascadesContext.getMemo().getRefreshVersion() !=
structInfoMap.getRefreshVersion()
+ || structInfoMap.getTableMaps().isEmpty()) {
+ structInfoMap.refresh(ownerGroup,
cascadesContext.getMemo().getRefreshVersion(),
+ materializedViewTableSet);
+
structInfoMap.setRefreshVersion(cascadesContext.getMemo().getRefreshVersion());
+ }
Set<BitSet> queryTableSets = structInfoMap.getTableMaps();
ImmutableList.Builder<StructInfo> structInfosBuilder =
ImmutableList.builder();
if (!queryTableSets.isEmpty()) {
for (BitSet queryTableSet : queryTableSets) {
+ // TODO As only support MatchMode.COMPLETE, so only get
equaled query table struct info
if (!materializedViewTableSet.isEmpty()
- &&
!StructInfo.containsAll(materializedViewTableSet, queryTableSet)) {
+ &&
!materializedViewTableSet.equals(queryTableSet)) {
continue;
}
- StructInfo structInfo =
structInfoMap.getStructInfo(queryTableSet, queryTableSet, ownerGroup, plan);
+ StructInfo structInfo =
structInfoMap.getStructInfo(cascadesContext.getMemo(),
+ queryTableSet, queryTableSet, ownerGroup, plan);
if (structInfo != null) {
structInfosBuilder.add(structInfo);
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/StructInfoMapTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/StructInfoMapTest.java
index 13bdf35252e..9192f86cf3b 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/StructInfoMapTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/StructInfoMapTest.java
@@ -50,7 +50,7 @@ class StructInfoMapTest extends SqlTestBase {
Group root = c1.getMemo().getRoot();
Set<BitSet> tableMaps = root.getstructInfoMap().getTableMaps();
Assertions.assertTrue(tableMaps.isEmpty());
- root.getstructInfoMap().refresh(root);
+ root.getstructInfoMap().refresh(root, 1, new BitSet());
Assertions.assertEquals(1, tableMaps.size());
new MockUp<MTMVRelationManager>() {
@Mock
@@ -76,7 +76,7 @@ class StructInfoMapTest extends SqlTestBase {
.optimize()
.printlnBestPlanTree();
root = c1.getMemo().getRoot();
- root.getstructInfoMap().refresh(root);
+ root.getstructInfoMap().refresh(root, 1, new BitSet());
tableMaps = root.getstructInfoMap().getTableMaps();
Assertions.assertEquals(2, tableMaps.size());
dropMvByNereids("drop materialized view mv1");
@@ -97,10 +97,8 @@ class StructInfoMapTest extends SqlTestBase {
Group root = c1.getMemo().getRoot();
Set<BitSet> tableMaps = root.getstructInfoMap().getTableMaps();
Assertions.assertTrue(tableMaps.isEmpty());
- boolean refreshed = root.getstructInfoMap().refresh(root);
- Assertions.assertTrue(refreshed);
- refreshed = root.getstructInfoMap().refresh(root);
- Assertions.assertFalse(refreshed);
+ root.getstructInfoMap().refresh(root, 1, new BitSet());
+ root.getstructInfoMap().refresh(root, 1, new BitSet());
Assertions.assertEquals(1, tableMaps.size());
new MockUp<MTMVRelationManager>() {
@Mock
@@ -126,10 +124,8 @@ class StructInfoMapTest extends SqlTestBase {
.optimize()
.printlnBestPlanTree();
root = c1.getMemo().getRoot();
- refreshed = root.getstructInfoMap().refresh(root);
- Assertions.assertTrue(refreshed);
- refreshed = root.getstructInfoMap().refresh(root);
- Assertions.assertFalse(refreshed);
+ root.getstructInfoMap().refresh(root, 1, new BitSet());
+ root.getstructInfoMap().refresh(root, 1, new BitSet());
tableMaps = root.getstructInfoMap().getTableMaps();
Assertions.assertEquals(2, tableMaps.size());
dropMvByNereids("drop materialized view mv1");
@@ -166,13 +162,13 @@ class StructInfoMapTest extends SqlTestBase {
.rewrite()
.optimize();
Group root = c1.getMemo().getRoot();
- root.getstructInfoMap().refresh(root);
+ root.getstructInfoMap().refresh(root, 1, new BitSet());
StructInfoMap structInfoMap = root.getstructInfoMap();
Assertions.assertEquals(2, structInfoMap.getTableMaps().size());
BitSet mvMap = structInfoMap.getTableMaps().stream()
.filter(b -> b.cardinality() == 2)
.collect(Collectors.toList()).get(0);
- StructInfo structInfo = structInfoMap.getStructInfo(mvMap, mvMap,
root, null);
+ StructInfo structInfo = structInfoMap.getStructInfo(c1.getMemo(),
mvMap, mvMap, root, null);
System.out.println(structInfo.getOriginalPlan().treeString());
BitSet bitSet = new BitSet();
structInfo.getRelations().forEach(r -> bitSet.set((int)
r.getTable().getId()));
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
