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 40dbb5998df [feat](Nereids) Add support for slot pruning in functional
dependencies (#37045)
40dbb5998df is described below
commit 40dbb5998df09bc002c8bd8f4c56c86d8c2c90ae
Author: 谢健 <jianx...@gmail.com>
AuthorDate: Tue Jul 2 17:21:20 2024 +0800
[feat](Nereids) Add support for slot pruning in functional dependencies
(#37045)
Implement slot pruning functionality for functional dependencies to
optimize performance and resource utilization. This enhancement allows
for more efficient handling of dependencies by removing unnecessary
slots.
---
.../apache/doris/nereids/properties/DataTrait.java | 2 +
.../apache/doris/nereids/properties/FuncDeps.java | 6 ++-
.../doris/nereids/properties/FuncDepsDG.java | 47 +++++++++++++++++
.../rewrite/PushDownAggThroughJoinOnPkFk.java | 7 +--
.../nereids/trees/plans/logical/LogicalPlan.java | 7 +++
.../trees/plans/logical/LogicalProject.java | 3 --
.../doris/nereids/util/ImmutableEqualSet.java | 23 +++++++++
.../doris/nereids/properties/FuncDepsDGTest.java | 43 ++++++++++++++++
.../doris/nereids/util/ImmutableEqualSetTest.java | 59 ++++++++++++++++++++++
9 files changed, 190 insertions(+), 7 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 3a74f58b328..1d5210a1e6a 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
@@ -317,6 +317,8 @@ public class DataTrait {
public void pruneSlots(Set<Slot> outputSlots) {
uniformSet.removeNotContain(outputSlots);
uniqueSet.removeNotContain(outputSlots);
+ equalSetBuilder.removeNotContain(outputSlots);
+ fdDgBuilder.removeNotContain(outputSlots);
}
public void replace(Map<Slot, Slot> replaceMap) {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDeps.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDeps.java
index be7b0853605..e637af8982c 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDeps.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FuncDeps.java
@@ -33,7 +33,7 @@ import java.util.stream.Collectors;
* Function dependence items.
*/
public class FuncDeps {
- class FuncDepsItem {
+ static class FuncDepsItem {
final Set<Slot> determinants;
final Set<Slot> dependencies;
@@ -165,6 +165,10 @@ public class FuncDeps {
&& items.contains(new FuncDepsItem(dependency, dominate));
}
+ public Set<FuncDeps.FuncDepsItem> getItems() {
+ return items;
+ }
+
/**
* find the determinants of dependencies
*/
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 1245762ee29..a6637f09768 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
@@ -150,6 +150,53 @@ public class FuncDepsDG {
return new FuncDepsDG(ImmutableMap.copyOf(itemMap),
ImmutableList.copyOf(dgItems));
}
+ public void removeNotContain(Set<Slot> validSlot) {
+ FuncDeps funcDeps = findValidFuncDeps(validSlot);
+ dgItems.clear();
+ itemMap.clear();
+ for (FuncDeps.FuncDepsItem item : funcDeps.getItems()) {
+ this.addDeps(item.determinants, item.dependencies);
+ }
+ }
+
+ /**
+ * Finds all functional dependencies that are applicable to a given
set of valid slots.
+ */
+ public FuncDeps findValidFuncDeps(Set<Slot> validSlot) {
+ FuncDeps res = new FuncDeps();
+ for (Entry<Set<Slot>, Integer> entry : itemMap.entrySet()) {
+ if (validSlot.containsAll(entry.getKey())) {
+ Set<DGItem> visited = new HashSet<>();
+ Set<DGItem> children = new HashSet<>();
+ DGItem dgItem = dgItems.get(entry.getValue());
+ visited.add(dgItem);
+ collectAllChildren(validSlot, dgItem, visited, children);
+ for (DGItem child : children) {
+ res.addFuncItems(dgItem.slots, child.slots);
+ }
+ }
+ }
+ return res;
+ }
+
+ /**
+ * Helper method to recursively collect all child nodes of a given
root node
+ * that are valid according to the specified slots.
+ */
+ private void collectAllChildren(Set<Slot> validSlot, DGItem root,
+ Set<DGItem> visited, Set<DGItem> children) {
+ for (int childIdx : root.children) {
+ DGItem child = dgItems.get(childIdx);
+ if (!visited.contains(child)) {
+ if (validSlot.containsAll(child.slots)) {
+ children.add(child);
+ }
+ visited.add(child);
+ collectAllChildren(validSlot, child, visited, children);
+ }
+ }
+ }
+
public void addDeps(Set<Slot> dominant, Set<Slot> dependency) {
DGItem dominateItem = getOrCreateNode(dominant);
DGItem dependencyItem = getOrCreateNode(dependency);
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PushDownAggThroughJoinOnPkFk.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PushDownAggThroughJoinOnPkFk.java
index 0fb3ed11562..827f0819637 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PushDownAggThroughJoinOnPkFk.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PushDownAggThroughJoinOnPkFk.java
@@ -98,7 +98,8 @@ public class PushDownAggThroughJoinOnPkFk implements
RewriteRuleFactory {
if (primaryAndForeign == null) {
continue;
}
- LogicalAggregate<?> newAgg = eliminatePrimaryOutput(agg,
primaryAndForeign.first, primaryAndForeign.second);
+ LogicalAggregate<?> newAgg =
+ eliminatePrimaryOutput(agg, subJoin,
primaryAndForeign.first, primaryAndForeign.second);
if (newAgg == null) {
return null;
}
@@ -114,7 +115,7 @@ public class PushDownAggThroughJoinOnPkFk implements
RewriteRuleFactory {
}
// eliminate the slot of primary plan in agg
- private LogicalAggregate<?> eliminatePrimaryOutput(LogicalAggregate<?> agg,
+ private LogicalAggregate<?> eliminatePrimaryOutput(LogicalAggregate<?>
agg, Plan child,
Plan primary, Plan foreign) {
Set<Slot> aggInputs = agg.getInputSlots();
if (primary.getOutputSet().stream().noneMatch(aggInputs::contains)) {
@@ -122,7 +123,7 @@ public class PushDownAggThroughJoinOnPkFk implements
RewriteRuleFactory {
}
Set<Slot> primaryOutputSet = primary.getOutputSet();
Set<Slot> primarySlots = Sets.intersection(aggInputs,
primaryOutputSet);
- DataTrait dataTrait = agg.child().getLogicalProperties().getTrait();
+ DataTrait dataTrait = child.getLogicalProperties().getTrait();
FuncDeps funcDeps =
dataTrait.getAllValidFuncDeps(Sets.union(foreign.getOutputSet(),
primary.getOutputSet()));
HashMap<Slot, Slot> primaryToForeignDeps = new HashMap<>();
for (Slot slot : primarySlots) {
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 89a0ef658ba..2e1c580ca5f 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
@@ -88,6 +88,13 @@ public interface LogicalPlan extends Plan {
fdBuilder.addUniformByEqualSet(validEqualSet);
fdBuilder.addUniqueByEqualSet(validEqualSet);
}
+ Set<Slot> output = this.getOutputSet();
+ for (Plan child : children()) {
+ if (!output.containsAll(child.getOutputSet())) {
+ fdBuilder.pruneSlots(output);
+ break;
+ }
+ }
return fdBuilder.build();
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalProject.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalProject.java
index 2440c6c3c50..1a7f3e2dead 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalProject.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalProject.java
@@ -233,7 +233,6 @@ public class LogicalProject<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_
}
}
}
- builder.pruneSlots(getOutputSet());
}
@Override
@@ -252,7 +251,6 @@ public class LogicalProject<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_
}
}
}
- builder.pruneSlots(getOutputSet());
}
@Override
@@ -270,7 +268,6 @@ public class LogicalProject<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_
}
}
}
- builder.pruneSlots(getOutputSet());
}
@Override
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/util/ImmutableEqualSet.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/util/ImmutableEqualSet.java
index c8aaf60ab0b..72d7ffce2b4 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/util/ImmutableEqualSet.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/util/ImmutableEqualSet.java
@@ -20,7 +20,9 @@ package org.apache.doris.nereids.util;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
@@ -71,6 +73,27 @@ public class ImmutableEqualSet<T> {
parent = newMap;
}
+ /**
+ * Remove all not contain in containSet
+ * @param containSet the set to contain
+ */
+ public void removeNotContain(Set<T> containSet) {
+ List<Set<T>> equalSetList = calEqualSetList();
+ this.parent.clear();
+ for (Set<T> equalSet : equalSetList) {
+ Set<T> intersect = Sets.intersection(containSet, equalSet);
+ if (intersect.size() <= 1) {
+ continue;
+ }
+ Iterator<T> iterator = intersect.iterator();
+ T first = intersect.iterator().next();
+ while (iterator.hasNext()) {
+ T next = iterator.next();
+ this.addEqualPair(first, next);
+ }
+ }
+ }
+
/**
* Add a equal pair
*/
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 a20085897da..e92fa31abec 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
@@ -73,4 +73,47 @@ class FuncDepsDGTest {
FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s1, s4,
s3));
Assertions.assertEquals(2, res.size());
}
+
+ @Test
+ void testPruneTrans() {
+ 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);
+ dg.addDeps(Sets.newHashSet(s1), Sets.newHashSet(s2));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s3));
+ dg.removeNotContain(Sets.newHashSet(s1, s3));
+ FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s1, s3));
+ System.out.println(res);
+ Assertions.assertEquals(1, res.size());
+ }
+
+ @Test
+ void testPruneCircle() {
+ 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);
+ dg.addDeps(Sets.newHashSet(s1), Sets.newHashSet(s2));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s3));
+ dg.addDeps(Sets.newHashSet(s3), Sets.newHashSet(s1));
+ dg.removeNotContain(Sets.newHashSet(s1, s3));
+ FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s1, s3));
+ Assertions.assertEquals(2, res.size());
+ }
+
+ @Test
+ void testPruneTree() {
+ 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);
+ dg.addDeps(Sets.newHashSet(s1), Sets.newHashSet(s2));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s3));
+ dg.addDeps(Sets.newHashSet(s2), Sets.newHashSet(s4));
+ dg.removeNotContain(Sets.newHashSet(s1, s4, s3));
+ FuncDeps res = dg.build().findValidFuncDeps(Sets.newHashSet(s1, s4,
s3));
+ Assertions.assertEquals(2, res.size());
+ }
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/util/ImmutableEqualSetTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/util/ImmutableEqualSetTest.java
new file mode 100644
index 00000000000..9942813d377
--- /dev/null
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/util/ImmutableEqualSetTest.java
@@ -0,0 +1,59 @@
+// 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.nereids.util;
+
+import com.google.common.collect.Sets;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+class ImmutableEqualSetTest {
+ @Test
+ void testRemoveCircle() {
+ ImmutableEqualSet.Builder<Integer> builder = new
ImmutableEqualSet.Builder<>();
+ builder.addEqualPair(1, 2);
+ builder.addEqualPair(2, 3);
+ builder.addEqualPair(3, 1);
+ builder.removeNotContain(Sets.newHashSet(1, 3));
+ ImmutableEqualSet<Integer> e = builder.build();
+ Assertions.assertTrue(e.isEqual(1, 3));
+ }
+
+ @Test
+ void testRemoveInTree() {
+ ImmutableEqualSet.Builder<Integer> builder = new
ImmutableEqualSet.Builder<>();
+ builder.addEqualPair(1, 2);
+ builder.addEqualPair(2, 3);
+ builder.addEqualPair(2, 4);
+ builder.removeNotContain(Sets.newHashSet(1, 3, 4));
+ ImmutableEqualSet<Integer> e = builder.build();
+ Assertions.assertTrue(e.isEqual(3, 4));
+ Assertions.assertTrue(e.isEqual(1, 3));
+ Assertions.assertTrue(e.isEqual(1, 4));
+ }
+
+ @Test
+ void testRemoveInTrans() {
+ ImmutableEqualSet.Builder<Integer> builder = new
ImmutableEqualSet.Builder<>();
+ builder.addEqualPair(1, 2);
+ builder.addEqualPair(2, 3);
+ builder.addEqualPair(3, 4);
+ builder.removeNotContain(Sets.newHashSet(1, 4));
+ ImmutableEqualSet<Integer> e = builder.build();
+ Assertions.assertTrue(e.isEqual(1, 4));
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
