This is an automated email from the ASF dual-hosted git repository.
morrysnow 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 77233b559b2 [opt](Nereids) Replace Slot in Each Data Trait Separately
(#36886)
77233b559b2 is described below
commit 77233b559b23bfdc088cf806fee5ae7d383433f2
Author: 谢健 <jianx...@gmail.com>
AuthorDate: Wed Jul 3 14:36:25 2024 +0800
[opt](Nereids) Replace Slot in Each Data Trait Separately (#36886)
To avoid replacing slots in each data trait repeatedly, we split the
replace function into four functions and replaced them separately.
---
.../apache/doris/nereids/properties/DataTrait.java | 12 ++++-
.../doris/nereids/properties/FuncDepsDG.java | 23 ++++++++++
.../doris/nereids/trees/plans/AbstractPlan.java | 2 +-
.../trees/plans/BlockFuncDepsPropagation.java | 2 +-
.../nereids/trees/plans/PropagateFuncDeps.java | 2 +-
.../nereids/trees/plans/logical/LogicalExcept.java | 52 +++++++--------------
.../trees/plans/logical/LogicalIntersect.java | 23 ++++++----
.../nereids/trees/plans/logical/LogicalPlan.java | 2 +-
.../trees/plans/logical/LogicalSubQueryAlias.java | 12 +++--
.../doris/nereids/properties/FuncDepsDGTest.java | 53 ++++++++++++++++++++++
10 files changed, 129 insertions(+), 54 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/DataTrait.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/DataTrait.java
index 1d5210a1e6a..e97fad6f479 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/DataTrait.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/DataTrait.java
@@ -321,11 +321,21 @@ public class DataTrait {
fdDgBuilder.removeNotContain(outputSlots);
}
- public void replace(Map<Slot, Slot> replaceMap) {
+ public void replaceUniformBy(Map<Slot, Slot> replaceMap) {
uniformSet.replace(replaceMap);
+ }
+
+ public void replaceUniqueBy(Map<Slot, Slot> replaceMap) {
uniqueSet.replace(replaceMap);
+ }
+
+ public void replaceEqualSetBy(Map<Slot, Slot> replaceMap) {
equalSetBuilder.replace(replaceMap);
}
+
+ public void replaceFuncDepsBy(Map<Slot, Slot> replaceMap) {
+ fdDgBuilder.replace(replaceMap);
+ }
}
static class NestedSet {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDepsDG.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDepsDG.java
index a6637f09768..09bc85e084d 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDepsDG.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDepsDG.java
@@ -68,6 +68,14 @@ public class FuncDepsDG {
this.parents = new HashSet<>(dgItem.parents);
this.children = new HashSet<>(dgItem.children);
}
+
+ public void replace(Map<Slot, Slot> replaceMap) {
+ Set<Slot> newSlots = new HashSet<>();
+ for (Slot slot : slots) {
+ newSlots.add(replaceMap.getOrDefault(slot, slot));
+ }
+ this.slots = newSlots;
+ }
}
private final Map<Set<Slot>, Integer> itemMap; // Maps sets of slots to
their indices in the dgItems list
@@ -211,6 +219,21 @@ public class FuncDepsDG {
}
}
+ public void replace(Map<Slot, Slot> replaceSlotMap) {
+ for (DGItem item : dgItems) {
+ item.replace(replaceSlotMap);
+ }
+ Map<Set<Slot>, Integer> newItemMap = new HashMap<>();
+ for (Entry<Set<Slot>, Integer> e : itemMap.entrySet()) {
+ Set<Slot> key = new HashSet<>();
+ for (Slot slot : e.getKey()) {
+ key.add(replaceSlotMap.getOrDefault(slot, slot));
+ }
+ newItemMap.put(key, e.getValue());
+ }
+ this.itemMap = newItemMap;
+ }
+
private DGItem getOrCreateNode(Set<Slot> slots) {
if (!itemMap.containsKey(slots)) {
itemMap.put(slots, dgItems.size());
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/AbstractPlan.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/AbstractPlan.java
index c764dfff3a8..9dfca3195d6 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/AbstractPlan.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/AbstractPlan.java
@@ -203,7 +203,7 @@ public abstract class AbstractPlan extends
AbstractTreeNode<Plan> implements Pla
} else {
Supplier<List<Slot>> outputSupplier =
Suppliers.memoize(this::computeOutput);
Supplier<DataTrait> fdSupplier = () -> this instanceof LogicalPlan
- ? ((LogicalPlan) this).computeFuncDeps()
+ ? ((LogicalPlan) this).computeDataTrait()
: DataTrait.EMPTY_TRAIT;
return new LogicalProperties(outputSupplier, fdSupplier);
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/BlockFuncDepsPropagation.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/BlockFuncDepsPropagation.java
index 37a111167db..c7b93af9ceb 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/BlockFuncDepsPropagation.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/BlockFuncDepsPropagation.java
@@ -28,7 +28,7 @@ import com.google.common.collect.ImmutableSet;
*/
public interface BlockFuncDepsPropagation extends LogicalPlan {
@Override
- default DataTrait computeFuncDeps() {
+ default DataTrait computeDataTrait() {
return DataTrait.EMPTY_TRAIT;
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/PropagateFuncDeps.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/PropagateFuncDeps.java
index 11a86105409..f94a13b3f8e 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/PropagateFuncDeps.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/PropagateFuncDeps.java
@@ -28,7 +28,7 @@ import com.google.common.collect.ImmutableSet;
*/
public interface PropagateFuncDeps extends LogicalPlan {
@Override
- default DataTrait computeFuncDeps() {
+ default DataTrait computeDataTrait() {
if (children().size() == 1) {
// Note when changing function dependencies, we always clone it.
// So it's safe to return a reference
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalExcept.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalExcept.java
index 51cb5d9f1ff..cc07c7244e1 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalExcept.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalExcept.java
@@ -132,62 +132,42 @@ public class LogicalExcept extends LogicalSetOperation {
return builder.build();
}
- @Override
- public void computeUnique(Builder builder) {
- builder.addUniqueSlot(child(0).getLogicalProperties().getTrait());
- if (qualifier == Qualifier.DISTINCT) {
- builder.addUniqueSlot(ImmutableSet.copyOf(getOutput()));
- }
+ Map<Slot, Slot> constructReplaceMapForChild(int index) {
Map<Slot, Slot> replaceMap = new HashMap<>();
List<Slot> output = getOutput();
List<? extends Slot> originalOutputs = regularChildrenOutputs.isEmpty()
- ? child(0).getOutput()
- : regularChildrenOutputs.get(0);
+ ? child(index).getOutput()
+ : regularChildrenOutputs.get(index);
for (int i = 0; i < output.size(); i++) {
replaceMap.put(originalOutputs.get(i), output.get(i));
}
- builder.replace(replaceMap);
+ return replaceMap;
+ }
+
+ @Override
+ public void computeUnique(Builder builder) {
+ builder.addUniqueSlot(child(0).getLogicalProperties().getTrait());
+ if (qualifier == Qualifier.DISTINCT) {
+ builder.addUniqueSlot(ImmutableSet.copyOf(getOutput()));
+ }
+ builder.replaceUniqueBy(constructReplaceMapForChild(0));
}
@Override
public void computeEqualSet(DataTrait.Builder builder) {
builder.addEqualSet(child(0).getLogicalProperties().getTrait());
- Map<Slot, Slot> replaceMap = new HashMap<>();
- List<Slot> output = getOutput();
- List<? extends Slot> originalOutputs = regularChildrenOutputs.isEmpty()
- ? child(0).getOutput()
- : regularChildrenOutputs.get(0);
- for (int i = 0; i < output.size(); i++) {
- replaceMap.put(originalOutputs.get(i), output.get(i));
- }
- builder.replace(replaceMap);
+ builder.replaceEqualSetBy(constructReplaceMapForChild(0));
}
@Override
public void computeFd(DataTrait.Builder builder) {
builder.addFuncDepsDG(child(0).getLogicalProperties().getTrait());
- Map<Slot, Slot> replaceMap = new HashMap<>();
- List<Slot> output = getOutput();
- List<? extends Slot> originalOutputs = regularChildrenOutputs.isEmpty()
- ? child(0).getOutput()
- : regularChildrenOutputs.get(0);
- for (int i = 0; i < output.size(); i++) {
- replaceMap.put(originalOutputs.get(i), output.get(i));
- }
- builder.replace(replaceMap);
+ builder.replaceFuncDepsBy(constructReplaceMapForChild(0));
}
@Override
public void computeUniform(Builder builder) {
builder.addUniformSlot(child(0).getLogicalProperties().getTrait());
- Map<Slot, Slot> replaceMap = new HashMap<>();
- List<Slot> output = getOutput();
- List<? extends Slot> originalOutputs = regularChildrenOutputs.isEmpty()
- ? child(0).getOutput()
- : regularChildrenOutputs.get(0);
- for (int i = 0; i < output.size(); i++) {
- replaceMap.put(originalOutputs.get(i), output.get(i));
- }
- builder.replace(replaceMap);
+ builder.replaceUniformBy(constructReplaceMapForChild(0));
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalIntersect.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalIntersect.java
index b8737ab24c1..e3b9cf3ed9f 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalIntersect.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalIntersect.java
@@ -18,7 +18,6 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
-import org.apache.doris.nereids.properties.DataTrait;
import org.apache.doris.nereids.properties.DataTrait.Builder;
import org.apache.doris.nereids.properties.ExprFdItem;
import org.apache.doris.nereids.properties.FdFactory;
@@ -109,13 +108,17 @@ public class LogicalIntersect extends LogicalSetOperation
{
Optional.empty(), Optional.empty(), children);
}
- void replaceSlotInFuncDeps(DataTrait.Builder builder,
- List<Slot> originalOutputs, List<Slot> newOutputs) {
+ Map<Slot, Slot> constructReplaceMap() {
Map<Slot, Slot> replaceMap = new HashMap<>();
- for (int i = 0; i < newOutputs.size(); i++) {
- replaceMap.put(originalOutputs.get(i), newOutputs.get(i));
+ for (int i = 0; i < children.size(); i++) {
+ List<? extends Slot> originOutputs =
this.regularChildrenOutputs.size() == children.size()
+ ? child(i).getOutput()
+ : regularChildrenOutputs.get(i);
+ for (int j = 0; j < originOutputs.size(); j++) {
+ replaceMap.put(originOutputs.get(j), getOutput().get(j));
+ }
}
- builder.replace(replaceMap);
+ return replaceMap;
}
@Override
@@ -123,8 +126,8 @@ public class LogicalIntersect extends LogicalSetOperation {
for (Plan child : children) {
builder.addUniqueSlot(
child.getLogicalProperties().getTrait());
- replaceSlotInFuncDeps(builder, child.getOutput(), getOutput());
}
+ builder.replaceUniqueBy(constructReplaceMap());
if (qualifier == Qualifier.DISTINCT) {
builder.addUniqueSlot(ImmutableSet.copyOf(getOutput()));
}
@@ -135,8 +138,8 @@ public class LogicalIntersect extends LogicalSetOperation {
for (Plan child : children) {
builder.addUniformSlot(
child.getLogicalProperties().getTrait());
- replaceSlotInFuncDeps(builder, child.getOutput(), getOutput());
}
+ builder.replaceUniformBy(constructReplaceMap());
}
@Override
@@ -144,8 +147,8 @@ public class LogicalIntersect extends LogicalSetOperation {
for (Plan child : children) {
builder.addEqualSet(
child.getLogicalProperties().getTrait());
- replaceSlotInFuncDeps(builder, child.getOutput(), getOutput());
}
+ builder.replaceEqualSetBy(constructReplaceMap());
}
@Override
@@ -153,8 +156,8 @@ public class LogicalIntersect extends LogicalSetOperation {
for (Plan child : children) {
builder.addFuncDepsDG(
child.getLogicalProperties().getTrait());
- replaceSlotInFuncDeps(builder, child.getOutput(), getOutput());
}
+ builder.replaceFuncDepsBy(constructReplaceMap());
}
@Override
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPlan.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPlan.java
index 2e1c580ca5f..c7eb8c838f2 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPlan.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPlan.java
@@ -62,7 +62,7 @@ public interface LogicalPlan extends Plan {
* - BlockFDPropagation: clean the fd
* - PropagateFD: propagate the fd
*/
- default DataTrait computeFuncDeps() {
+ default DataTrait computeDataTrait() {
DataTrait.Builder fdBuilder = new DataTrait.Builder();
computeUniform(fdBuilder);
computeUnique(fdBuilder);
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalSubQueryAlias.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalSubQueryAlias.java
index 23129e86d33..04f3ad34b49 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalSubQueryAlias.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalSubQueryAlias.java
@@ -171,7 +171,7 @@ public class LogicalSubQueryAlias<CHILD_TYPE extends Plan>
extends LogicalUnary<
for (int i = 0; i < outputs.size(); i++) {
replaceMap.put(child(0).getOutput().get(i), outputs.get(i));
}
- builder.replace(replaceMap);
+ builder.replaceUniqueBy(replaceMap);
}
@Override
@@ -182,7 +182,7 @@ public class LogicalSubQueryAlias<CHILD_TYPE extends Plan>
extends LogicalUnary<
for (int i = 0; i < outputs.size(); i++) {
replaceMap.put(child(0).getOutput().get(i), outputs.get(i));
}
- builder.replace(replaceMap);
+ builder.replaceUniformBy(replaceMap);
}
@Override
@@ -199,12 +199,18 @@ public class LogicalSubQueryAlias<CHILD_TYPE extends
Plan> extends LogicalUnary<
for (int i = 0; i < outputs.size(); i++) {
replaceMap.put(child(0).getOutput().get(i), outputs.get(i));
}
- builder.replace(replaceMap);
+ builder.replaceEqualSetBy(replaceMap);
}
@Override
public void computeFd(DataTrait.Builder builder) {
builder.addFuncDepsDG(child().getLogicalProperties().getTrait());
+ Map<Slot, Slot> replaceMap = new HashMap<>();
+ List<Slot> outputs = getOutput();
+ for (int i = 0; i < outputs.size(); i++) {
+ replaceMap.put(child(0).getOutput().get(i), outputs.get(i));
+ }
+ builder.replaceFuncDepsBy(replaceMap);
}
public void setRelationId(RelationId relationId) {
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/properties/FuncDepsDGTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/properties/FuncDepsDGTest.java
index e92fa31abec..d504176e807 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/properties/FuncDepsDGTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/properties/FuncDepsDGTest.java
@@ -25,6 +25,9 @@ import com.google.common.collect.Sets;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
+import java.util.HashMap;
+import java.util.Map;
+
class FuncDepsDGTest {
@Test
void testBasic() {
@@ -116,4 +119,54 @@ class FuncDepsDGTest {
FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s1, s4,
s3));
Assertions.assertEquals(2, res.size());
}
+
+ @Test
+ void testReplaceTrans() {
+ FuncDepsDG.Builder dg = new FuncDepsDG.Builder();
+ Slot s1 = new SlotReference("s1", IntegerType.INSTANCE);
+ Slot s2 = new SlotReference("s2", IntegerType.INSTANCE);
+ Slot s3 = new SlotReference("s3", IntegerType.INSTANCE);
+ Slot s5 = new SlotReference("s5", IntegerType.INSTANCE);
+ dg.addDeps(Sets.newHashSet(s1), Sets.newHashSet(s2));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s3));
+ Map<Slot, Slot> replaceMap = new HashMap<>();
+ replaceMap.put(s1, s5);
+ dg.replace(replaceMap);
+ FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s5, s3));
+ System.out.println(res);
+ Assertions.assertEquals(1, res.size());
+ }
+
+ @Test
+ void testReplaceCircle() {
+ FuncDepsDG.Builder dg = new FuncDepsDG.Builder();
+ Slot s1 = new SlotReference("s1", IntegerType.INSTANCE);
+ Slot s2 = new SlotReference("s2", IntegerType.INSTANCE);
+ Slot s5 = new SlotReference("s5", IntegerType.INSTANCE);
+ dg.addDeps(Sets.newHashSet(s1), Sets.newHashSet(s2));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s1));
+ Map<Slot, Slot> replaceMap = new HashMap<>();
+ replaceMap.put(s1, s5);
+ dg.replace(replaceMap);
+ FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s5, s2));
+ Assertions.assertEquals(2, res.size());
+ }
+
+ @Test
+ void testReplaceTree() {
+ FuncDepsDG.Builder dg = new FuncDepsDG.Builder();
+ Slot s1 = new SlotReference("s1", IntegerType.INSTANCE);
+ Slot s2 = new SlotReference("s2", IntegerType.INSTANCE);
+ Slot s3 = new SlotReference("s3", IntegerType.INSTANCE);
+ Slot s4 = new SlotReference("s4", IntegerType.INSTANCE);
+ Slot s5 = new SlotReference("s5", IntegerType.INSTANCE);
+ dg.addDeps(Sets.newHashSet(s1), Sets.newHashSet(s2));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s3));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s4));
+ Map<Slot, Slot> replaceMap = new HashMap<>();
+ replaceMap.put(s1, s5);
+ dg.replace(replaceMap);
+ FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s5, s4,
s3));
+ Assertions.assertEquals(2, res.size());
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
