This is an automated email from the ASF dual-hosted git repository.
yiguolei 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 81f1fbe4831 [nereids] group by key elimination (#30774)
81f1fbe4831 is described below
commit 81f1fbe48318e2c8aabb99bdfce9d410d407af80
Author: xzj7019 <[email protected]>
AuthorDate: Tue Feb 6 13:53:50 2024 +0800
[nereids] group by key elimination (#30774)
---
.../doris/nereids/jobs/executor/Rewriter.java | 6 +
.../ExprFdItem.java} | 24 ++-
.../apache/doris/nereids/properties/FdFactory.java | 43 ++++
.../apache/doris/nereids/properties/FdItem.java | 64 ++++++
.../nereids/properties/FunctionalDependencies.java | 23 ++-
.../nereids/properties/LogicalProperties.java | 6 +-
.../doris/nereids/properties/TableFdItem.java | 93 +++++++++
.../org/apache/doris/nereids/rules/RuleType.java | 1 +
.../nereids/rules/rewrite/EliminateGroupByKey.java | 217 +++++++++++++++++++++
.../trees/plans/BlockFuncDepsPropagation.java | 8 +
.../nereids/trees/plans/PropagateFuncDeps.java | 19 ++
.../trees/plans/logical/LogicalAggregate.java | 28 +++
.../plans/logical/LogicalCatalogRelation.java | 53 +++++
.../plans/logical/LogicalDeferMaterializeTopN.java | 23 +++
.../nereids/trees/plans/logical/LogicalExcept.java | 30 +++
.../nereids/trees/plans/logical/LogicalFilter.java | 13 ++
.../trees/plans/logical/LogicalGenerate.java | 9 +
.../nereids/trees/plans/logical/LogicalHaving.java | 13 ++
.../trees/plans/logical/LogicalIntersect.java | 32 +++
.../nereids/trees/plans/logical/LogicalJoin.java | 165 +++++++++++++++-
.../nereids/trees/plans/logical/LogicalLimit.java | 24 +++
.../trees/plans/logical/LogicalOneRowRelation.java | 22 +++
.../nereids/trees/plans/logical/LogicalPlan.java | 4 +
.../trees/plans/logical/LogicalProject.java | 13 ++
.../nereids/trees/plans/logical/LogicalRepeat.java | 14 ++
.../trees/plans/logical/LogicalSubQueryAlias.java | 10 +
.../nereids/trees/plans/logical/LogicalTopN.java | 24 +++
.../nereids/trees/plans/logical/LogicalUnion.java | 24 +++
.../nereids/trees/plans/logical/LogicalWindow.java | 35 +++-
.../org/apache/doris/nereids/util/PlanUtils.java | 25 +++
.../constraints/query23.out | 47 +++--
.../constraints/query23.groovy | 2 +
32 files changed, 1071 insertions(+), 43 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
index 34f7afe4995..8f60fbddfdf 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Rewriter.java
@@ -56,6 +56,7 @@ import
org.apache.doris.nereids.rules.rewrite.EliminateDedupJoinCondition;
import org.apache.doris.nereids.rules.rewrite.EliminateEmptyRelation;
import org.apache.doris.nereids.rules.rewrite.EliminateFilter;
import org.apache.doris.nereids.rules.rewrite.EliminateGroupBy;
+import org.apache.doris.nereids.rules.rewrite.EliminateGroupByKey;
import org.apache.doris.nereids.rules.rewrite.EliminateJoinByFK;
import org.apache.doris.nereids.rules.rewrite.EliminateJoinByUnique;
import org.apache.doris.nereids.rules.rewrite.EliminateJoinCondition;
@@ -314,6 +315,11 @@ public class Rewriter extends AbstractBatchJobExecutor {
custom(RuleType.ELIMINATE_UNNECESSARY_PROJECT,
EliminateUnnecessaryProject::new)
),
+ // this rule should invoke after topic "Join pull up"
+ topic("eliminate group by keys according to fd items",
+ topDown(new EliminateGroupByKey())
+ ),
+
topic("Limit optimization",
// TODO: the logical plan should not contains any phase
information,
// we should refactor like AggregateStrategies, e.g.
LimitStrategies,
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/properties/ExprFdItem.java
similarity index 57%
copy from
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/BlockFuncDepsPropagation.java
copy to
fe/fe-core/src/main/java/org/apache/doris/nereids/properties/ExprFdItem.java
index 3f60727576d..9a36f6e0d97 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/properties/ExprFdItem.java
@@ -15,21 +15,27 @@
// specific language governing permissions and limitations
// under the License.
-package org.apache.doris.nereids.trees.plans;
+package org.apache.doris.nereids.properties;
-import org.apache.doris.nereids.properties.FunctionalDependencies;
-import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
-import java.util.List;
-import java.util.function.Supplier;
+import com.google.common.collect.ImmutableSet;
/**
- * Block fd propagation, it always returns an empty fd
+ * Expression level function dependence items.
*/
-public interface BlockFuncDepsPropagation extends LogicalPlan {
+public class ExprFdItem extends FdItem {
+ private ImmutableSet<SlotReference> childExprs;
+
+ public ExprFdItem(ImmutableSet<SlotReference> parentExprs, boolean
isUnique,
+ ImmutableSet<SlotReference> childExprs) {
+ super(parentExprs, isUnique, false);
+ this.childExprs = ImmutableSet.copyOf(childExprs);
+ }
+
@Override
- default FunctionalDependencies computeFuncDeps(Supplier<List<Slot>>
outputSupplier) {
- return FunctionalDependencies.EMPTY_FUNC_DEPS;
+ public boolean checkExprInChild(SlotReference slot, LogicalPlan childPlan)
{
+ return childExprs.contains(slot);
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FdFactory.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FdFactory.java
new file mode 100644
index 00000000000..cd08ce50563
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FdFactory.java
@@ -0,0 +1,43 @@
+// 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.properties;
+
+import org.apache.doris.catalog.TableIf;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+
+import com.google.common.collect.ImmutableSet;
+
+/**
+ * Function dependence building factory.
+ */
+public class FdFactory {
+
+ public static final FdFactory INSTANCE = new FdFactory();
+
+ public TableFdItem createTableFdItem(ImmutableSet<SlotReference>
parentExprs, boolean isUnique,
+ boolean isCandidate, ImmutableSet<TableIf> tableIds) {
+ TableFdItem fdItem = new TableFdItem(parentExprs, isUnique,
isCandidate, tableIds);
+ return fdItem;
+ }
+
+ public ExprFdItem createExprFdItem(ImmutableSet<SlotReference>
parentExprs, boolean isUnique,
+ ImmutableSet<SlotReference> childExprs) {
+ ExprFdItem fdItem = new ExprFdItem(parentExprs, isUnique, childExprs);
+ return fdItem;
+ }
+}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FdItem.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FdItem.java
new file mode 100644
index 00000000000..4f8bf602695
--- /dev/null
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FdItem.java
@@ -0,0 +1,64 @@
+// 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.properties;
+
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
+
+import com.google.common.collect.ImmutableSet;
+
+/**
+ * Function dependence items.
+ */
+public class FdItem {
+ private ImmutableSet<SlotReference> parentExprs;
+
+ private boolean isUnique;
+
+ private boolean isCandidate;
+
+ public FdItem(ImmutableSet<SlotReference> parentExprs, boolean isUnique,
boolean isCandidate) {
+ this.parentExprs = ImmutableSet.copyOf(parentExprs);
+ this.isUnique = isUnique;
+ this.isCandidate = isCandidate;
+ }
+
+ public boolean isCandidate() {
+ return isCandidate;
+ }
+
+ public void setCandidate(boolean isCandidate) {
+ this.isCandidate = isCandidate;
+ }
+
+ public boolean isUnique() {
+ return isUnique;
+ }
+
+ public void setUnique(boolean isUnique) {
+ this.isUnique = isUnique;
+ }
+
+ public ImmutableSet<SlotReference> getParentExprs() {
+ return parentExprs;
+ }
+
+ public boolean checkExprInChild(SlotReference slot, LogicalPlan childPlan)
{
+ return false;
+ }
+}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FunctionalDependencies.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FunctionalDependencies.java
index b7395ecb8cf..30bcdaec3dd 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FunctionalDependencies.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/FunctionalDependencies.java
@@ -34,13 +34,16 @@ import java.util.stream.Collectors;
public class FunctionalDependencies {
public static final FunctionalDependencies EMPTY_FUNC_DEPS
- = new FunctionalDependencies(new NestedSet().toImmutable(), new
NestedSet().toImmutable());
+ = new FunctionalDependencies(new NestedSet().toImmutable(),
+ new NestedSet().toImmutable(), new
ImmutableSet.Builder<FdItem>().build());
private final NestedSet uniqueSet;
private final NestedSet uniformSet;
+ private final ImmutableSet<FdItem> fdItems;
- private FunctionalDependencies(NestedSet uniqueSet, NestedSet uniformSet) {
+ private FunctionalDependencies(NestedSet uniqueSet, NestedSet uniformSet,
ImmutableSet<FdItem> fdItems) {
this.uniqueSet = uniqueSet;
this.uniformSet = uniformSet;
+ this.fdItems = fdItems;
}
public boolean isEmpty() {
@@ -83,9 +86,13 @@ public class FunctionalDependencies {
return slotSet.stream().noneMatch(Slot::nullable) &&
isUniform(slotSet);
}
+ public ImmutableSet<FdItem> getFdItems() {
+ return fdItems;
+ }
+
@Override
public String toString() {
- return String.format("FuncDeps[uniform:%s, unique:%s]", uniformSet,
uniqueSet);
+ return String.format("FuncDeps[uniform:%s, unique:%s, fdItems:%s]",
uniformSet, uniqueSet, fdItems);
}
/**
@@ -94,15 +101,18 @@ public class FunctionalDependencies {
public static class Builder {
private final NestedSet uniqueSet;
private final NestedSet uniformSet;
+ private ImmutableSet<FdItem> fdItems;
public Builder() {
uniqueSet = new NestedSet();
uniformSet = new NestedSet();
+ fdItems = new ImmutableSet.Builder<FdItem>().build();
}
public Builder(FunctionalDependencies other) {
this.uniformSet = new NestedSet(other.uniformSet);
this.uniqueSet = new NestedSet(other.uniqueSet);
+ this.fdItems = ImmutableSet.copyOf(other.fdItems);
}
public void addUniformSlot(Slot slot) {
@@ -125,13 +135,18 @@ public class FunctionalDependencies {
uniqueSet.add(slotSet);
}
+ public void addFdItems(ImmutableSet<FdItem> items) {
+ fdItems = ImmutableSet.copyOf(items);
+ }
+
public void addFunctionalDependencies(FunctionalDependencies fd) {
uniformSet.add(fd.uniformSet);
uniqueSet.add(fd.uniqueSet);
}
public FunctionalDependencies build() {
- return new FunctionalDependencies(uniqueSet.toImmutable(),
uniformSet.toImmutable());
+ return new FunctionalDependencies(uniqueSet.toImmutable(),
uniformSet.toImmutable(),
+ ImmutableSet.copyOf(fdItems));
}
public void pruneSlots(Set<Slot> outputSlots) {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/LogicalProperties.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/LogicalProperties.java
index f82b43eaea6..07d28828942 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/LogicalProperties.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/LogicalProperties.java
@@ -45,7 +45,8 @@ public class LogicalProperties {
protected final Supplier<FunctionalDependencies> fdSupplier;
private Integer hashCode = null;
- public LogicalProperties(Supplier<List<Slot>> outputSupplier,
Supplier<FunctionalDependencies> fdSupplier) {
+ public LogicalProperties(Supplier<List<Slot>> outputSupplier,
+ Supplier<FunctionalDependencies> fdSupplier) {
this(outputSupplier, fdSupplier, ImmutableList::of);
}
@@ -56,7 +57,8 @@ public class LogicalProperties {
* throw exception for which children have
UnboundRelation
*/
public LogicalProperties(Supplier<List<Slot>> outputSupplier,
- Supplier<FunctionalDependencies> fdSupplier, Supplier<List<Slot>>
nonUserVisibleOutputSupplier) {
+ Supplier<FunctionalDependencies> fdSupplier,
+ Supplier<List<Slot>> nonUserVisibleOutputSupplier) {
this.outputSupplier = Suppliers.memoize(
Objects.requireNonNull(outputSupplier, "outputSupplier can not
be null")
);
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/TableFdItem.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/TableFdItem.java
new file mode 100644
index 00000000000..e919ea2f05d
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/properties/TableFdItem.java
@@ -0,0 +1,93 @@
+// 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.properties;
+
+import org.apache.doris.catalog.TableIf;
+import org.apache.doris.nereids.trees.expressions.Alias;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.plans.logical.LogicalCatalogRelation;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+import org.apache.doris.nereids.util.PlanUtils;
+
+import com.google.common.collect.ImmutableSet;
+
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * Table level function dependence items.
+ */
+public class TableFdItem extends FdItem {
+
+ private ImmutableSet<TableIf> childTables;
+
+ public TableFdItem(ImmutableSet<SlotReference> parentExprs, boolean
isUnique,
+ boolean isCandidate, ImmutableSet<TableIf> childTables) {
+ super(parentExprs, isUnique, isCandidate);
+ this.childTables = ImmutableSet.copyOf(childTables);
+ }
+
+ @Override
+ public boolean checkExprInChild(SlotReference slot, LogicalPlan childPlan)
{
+ NamedExpression slotInChild = null;
+ // find in child project based on exprid matching
+ List<NamedExpression> exprList = ((LogicalProject)
childPlan).getProjects();
+ for (NamedExpression expr : exprList) {
+ if (expr.getExprId().equals(slot.getExprId())) {
+ slotInChild = expr;
+ break;
+ }
+ }
+ if (slotInChild == null) {
+ return false;
+ } else {
+ Set<Slot> slotSet = new HashSet<>();
+ if (slotInChild instanceof Alias) {
+ slotSet = slotInChild.getInputSlots();
+ } else {
+ slotSet.add((Slot) slotInChild);
+ }
+ // get table list from slotSet
+ Set<TableIf> tableSets = getTableSets(slotSet, childPlan);
+ if (tableSets.isEmpty()) {
+ return false;
+ } else if (childTables.containsAll(tableSets)) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+ }
+
+ private Set<TableIf> getTableSets(Set<Slot> slotSet, LogicalPlan plan) {
+ Set<LogicalCatalogRelation> tableSets =
PlanUtils.getLogicalScanFromRootPlan(plan);
+ Set<TableIf> resultSet = new HashSet<>();
+ for (Slot slot : slotSet) {
+ for (LogicalCatalogRelation table : tableSets) {
+ if (table.getOutputExprIds().contains(slot.getExprId())) {
+ resultSet.add(table.getTable());
+ }
+ }
+ }
+ return resultSet;
+ }
+}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
index 594f49a3b70..89f4ce29eb5 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleType.java
@@ -209,6 +209,7 @@ public enum RuleType {
ELIMINATE_MARK_JOIN(RuleTypeClass.REWRITE),
ELIMINATE_GROUP_BY(RuleTypeClass.REWRITE),
ELIMINATE_JOIN_BY_UK(RuleTypeClass.REWRITE),
+ ELIMINATE_GROUP_BY_KEY(RuleTypeClass.REWRITE),
ELIMINATE_DEDUP_JOIN_CONDITION(RuleTypeClass.REWRITE),
ELIMINATE_NULL_AWARE_LEFT_ANTI_JOIN(RuleTypeClass.REWRITE),
ELIMINATE_ASSERT_NUM_ROWS(RuleTypeClass.REWRITE),
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateGroupByKey.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateGroupByKey.java
new file mode 100644
index 00000000000..d922252bebc
--- /dev/null
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateGroupByKey.java
@@ -0,0 +1,217 @@
+// 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.rules.rewrite;
+
+import org.apache.doris.nereids.properties.FdItem;
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
+import org.apache.doris.qe.ConnectContext;
+
+import com.google.common.collect.ImmutableSet;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+/**
+ * Eliminate group by key based on fd item information.
+ */
+public class EliminateGroupByKey extends OneRewriteRuleFactory {
+ @Override
+ public Rule build() {
+ return logicalAggregate(logicalProject()).then(agg -> {
+ Set<Integer> enableNereidsRules =
ConnectContext.get().getSessionVariable().getEnableNereidsRules();
+ if
(!enableNereidsRules.contains(RuleType.ELIMINATE_GROUP_BY_KEY.type())) {
+ return null;
+ }
+ LogicalPlan childPlan = agg.child();
+ List<FdItem> uniqueFdItems = new ArrayList<>();
+ List<FdItem> nonUniqueFdItems = new ArrayList<>();
+ if (agg.getGroupByExpressions().isEmpty()
+ ||
agg.getGroupByExpressions().equals(agg.getOutputExpressions())
+ || !agg.getGroupByExpressions().stream().allMatch(e -> e
instanceof SlotReference)
+ || agg.getGroupByExpressions().stream().allMatch(e ->
+ ((SlotReference) e).getColumn().isPresent() &&
((SlotReference) e).getTable().isPresent())) {
+ return null;
+ }
+ ImmutableSet<FdItem> fdItems =
childPlan.getLogicalProperties().getFunctionalDependencies().getFdItems();
+ if (fdItems.isEmpty()) {
+ return null;
+ }
+ List<SlotReference> candiExprs =
agg.getGroupByExpressions().stream()
+
.map(SlotReference.class::cast).collect(Collectors.toList());
+
+ fdItems.stream().filter(e -> !e.isCandidate()).forEach(e -> {
+ if (e.isUnique()) {
+ uniqueFdItems.add(e);
+ } else {
+ nonUniqueFdItems.add(e);
+ }
+ }
+ );
+
+ int minParentExprCnt = -1;
+ ImmutableSet<SlotReference> minParentExprs = ImmutableSet.of();
+ // if unique fd items exists, try to find the one which has the
+ // smallest parent exprs
+ for (int i = 0; i < uniqueFdItems.size(); i++) {
+ FdItem fdItem = uniqueFdItems.get(i);
+ ImmutableSet<SlotReference> parentExprs =
fdItem.getParentExprs();
+ if (minParentExprCnt == -1 || parentExprs.size() <
minParentExprCnt) {
+ boolean isContain = isExprsContainFdParent(candiExprs,
fdItem);
+ if (isContain) {
+ minParentExprCnt = parentExprs.size();
+ minParentExprs = ImmutableSet.copyOf(parentExprs);
+ }
+ }
+ }
+
+ Set<Integer> rootExprsSet = new HashSet<>();
+ List<SlotReference> rootExprs = new ArrayList<>();
+ Set<Integer> eliminateSet = new HashSet<>();
+ if (minParentExprs.size() > 0) {
+ // if any unique fd item found, find the expr which matching
parentExprs
+ // from candiExprs directly
+ for (int i = 0; i < minParentExprs.size(); i++) {
+ int index = findEqualExpr(candiExprs,
minParentExprs.asList().get(i));
+ if (index != -1) {
+ rootExprsSet.add(new Integer(index));
+ } else {
+ return null;
+ }
+ }
+ } else {
+ // no unique fd item found, try to find the smallest root
exprs set
+ // from non-unique fd items.
+ for (int i = 0; i < nonUniqueFdItems.size() &&
eliminateSet.size() < candiExprs.size(); i++) {
+ FdItem fdItem = nonUniqueFdItems.get(i);
+ ImmutableSet<SlotReference> parentExprs =
fdItem.getParentExprs();
+ boolean isContains = isExprsContainFdParent(candiExprs,
fdItem);
+ if (isContains) {
+ List<SlotReference> leftDomain = new ArrayList<>();
+ List<SlotReference> rightDomain = new ArrayList<>();
+ // generate new root exprs
+ for (int j = 0; j < rootExprs.size(); j++) {
+ leftDomain.add(rootExprs.get(j));
+ boolean isInChild =
fdItem.checkExprInChild(rootExprs.get(j), childPlan);
+ if (!isInChild) {
+ rightDomain.add(rootExprs.get(j));
+ }
+ }
+ for (int j = 0; j < parentExprs.size(); j++) {
+ int index = findEqualExpr(candiExprs,
parentExprs.asList().get(j));
+ if (index != -1) {
+ rightDomain.add(candiExprs.get(index));
+ if (!eliminateSet.contains(index)) {
+ leftDomain.add(candiExprs.get(index));
+ }
+ }
+ }
+ // check fd can eliminate new candi expr
+ for (int j = 0; j < candiExprs.size(); j++) {
+ if (!eliminateSet.contains(j)) {
+ boolean isInChild =
fdItem.checkExprInChild(candiExprs.get(j), childPlan);
+ if (isInChild) {
+ eliminateSet.add(j);
+ }
+ }
+ }
+ // if fd eliminate new candi exprs or new root exprs
is smaller than the older,
+ // than use new root expr to replace old ones
+ List<SlotReference> newRootExprs = leftDomain.size()
<= rightDomain.size()
+ ? leftDomain : rightDomain;
+ rootExprs.clear();
+ rootExprs.addAll(newRootExprs);
+ }
+ }
+ }
+ // find the root expr, add into root exprs set, indicate the index
in
+ // candiExprs list
+ for (int i = 0; i < rootExprs.size(); i++) {
+ int index = findEqualExpr(candiExprs, rootExprs.get(i));
+ if (index != -1) {
+ rootExprsSet.add(new Integer(index));
+ } else {
+ return null;
+ }
+ }
+ // other can't be determined expr, add into root exprs directly
+ if (eliminateSet.size() < candiExprs.size()) {
+ for (int i = 0; i < candiExprs.size(); i++) {
+ if (!eliminateSet.contains(i)) {
+ rootExprsSet.add(i);
+ }
+ }
+ }
+ rootExprs.clear();
+ for (int i = 0; i < candiExprs.size(); i++) {
+ if (rootExprsSet.contains(i)) {
+ rootExprs.add(candiExprs.get(i));
+ }
+ }
+
+ // use the new rootExprs as new group by keys
+ List<Expression> resultExprs = new ArrayList<>();
+ for (int i = 0; i < rootExprs.size(); i++) {
+ resultExprs.add(rootExprs.get(i));
+ }
+
+ // eliminate outputs keys
+ // TODO: remove outputExprList computing
+ List<NamedExpression> outputExprList = new ArrayList<>();
+ for (int i = 0; i < agg.getOutputExpressions().size(); i++) {
+ if (rootExprsSet.contains(i)) {
+ outputExprList.add(agg.getOutputExpressions().get(i));
+ }
+ }
+ // find the remained outputExprs list
+ List<NamedExpression> remainedOutputExprList = new ArrayList<>();
+ for (int i = 0; i < agg.getOutputExpressions().size(); i++) {
+ NamedExpression outputExpr = agg.getOutputExpressions().get(i);
+ if (!agg.getGroupByExpressions().contains(outputExpr)) {
+ remainedOutputExprList.add(outputExpr);
+ }
+ }
+ outputExprList.addAll(remainedOutputExprList);
+ return new LogicalAggregate<>(resultExprs,
agg.getOutputExpressions(), agg.child());
+ }).toRule(RuleType.ELIMINATE_GROUP_BY_KEY);
+ }
+
+ /**
+ * find the equal expr index from expr list.
+ */
+ public int findEqualExpr(List<SlotReference> exprList, SlotReference expr)
{
+ for (int i = 0; i < exprList.size(); i++) {
+ if (exprList.get(i).equals(expr)) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ private boolean isExprsContainFdParent(List<SlotReference> candiExprs,
FdItem fdItem) {
+ return fdItem.getParentExprs().stream().allMatch(e ->
candiExprs.contains(e));
+ }
+}
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 3f60727576d..07804587e3b 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
@@ -17,10 +17,13 @@
package org.apache.doris.nereids.trees.plans;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.trees.expressions.Slot;
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
+import com.google.common.collect.ImmutableSet;
+
import java.util.List;
import java.util.function.Supplier;
@@ -32,4 +35,9 @@ public interface BlockFuncDepsPropagation extends LogicalPlan
{
default FunctionalDependencies computeFuncDeps(Supplier<List<Slot>>
outputSupplier) {
return FunctionalDependencies.EMPTY_FUNC_DEPS;
}
+
+ @Override
+ default ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ return ImmutableSet.of();
+ }
}
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 332a80c99ee..c344f22ca21 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
@@ -17,10 +17,13 @@
package org.apache.doris.nereids.trees.plans;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.trees.expressions.Slot;
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
+import com.google.common.collect.ImmutableSet;
+
import java.util.List;
import java.util.function.Supplier;
@@ -39,6 +42,22 @@ public interface PropagateFuncDeps extends LogicalPlan {
children().stream()
.map(p -> p.getLogicalProperties().getFunctionalDependencies())
.forEach(builder::addFunctionalDependencies);
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ default ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ if (children().size() == 1) {
+ // Note when changing function dependencies, we always clone it.
+ // So it's safe to return a reference
+ return
child(0).getLogicalProperties().getFunctionalDependencies().getFdItems();
+ }
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ children().stream()
+ .map(p ->
p.getLogicalProperties().getFunctionalDependencies().getFdItems())
+ .forEach(builder::addAll);
return builder.build();
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalAggregate.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalAggregate.java
index edf962838d3..20647a3808e 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalAggregate.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalAggregate.java
@@ -18,9 +18,12 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.properties.TableFdItem;
import org.apache.doris.nereids.trees.expressions.Alias;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.NamedExpression;
@@ -360,6 +363,31 @@ public class LogicalAggregate<CHILD_TYPE extends Plan>
// group by keys is unique
fdBuilder.addUniqueSlot(groupByKeys);
fdBuilder.pruneSlots(outputSet);
+
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ fdBuilder.addFdItems(fdItems);
+
return fdBuilder.build();
}
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<SlotReference> groupByExprs =
getGroupByExpressions().stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+
+ // inherit from child
+ ImmutableSet<FdItem> childItems =
child().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ builder.addAll(childItems);
+
+ // todo: fill the table sets
+ TableFdItem fdItem =
FdFactory.INSTANCE.createTableFdItem(groupByExprs, true,
+ false, ImmutableSet.of());
+ builder.add(fdItem);
+
+ return builder.build();
+ }
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalCatalogRelation.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalCatalogRelation.java
index f0ff94c4c60..4076e8348e2 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalCatalogRelation.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalCatalogRelation.java
@@ -25,9 +25,13 @@ import org.apache.doris.catalog.TableIf;
import org.apache.doris.datasource.CatalogIf;
import org.apache.doris.nereids.exceptions.AnalysisException;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.properties.TableFdItem;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
import org.apache.doris.nereids.trees.expressions.Slot;
import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.PlanType;
@@ -154,6 +158,55 @@ public abstract class LogicalCatalogRelation extends
LogicalRelation implements
.collect(ImmutableSet.toImmutableSet());
fdBuilder.addUniqueSlot(slotSet);
});
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ fdBuilder.addFdItems(fdItems);
return fdBuilder.build();
}
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ Set<NamedExpression> output =
ImmutableSet.copyOf(outputSupplier.get());
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ table.getPrimaryKeyConstraints().forEach(c -> {
+ Set<Column> columns = c.getPrimaryKeys(this.getTable());
+ ImmutableSet<SlotReference> slotSet = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .filter(s -> s.getColumn().isPresent()
+ && columns.contains(s.getColumn().get()))
+ .collect(ImmutableSet.toImmutableSet());
+ TableFdItem tableFdItem =
FdFactory.INSTANCE.createTableFdItem(slotSet, true,
+ false, ImmutableSet.of(table));
+ builder.add(tableFdItem);
+ });
+ table.getUniqueConstraints().forEach(c -> {
+ Set<Column> columns = c.getUniqueKeys(this.getTable());
+ boolean allNotNull = columns.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .allMatch(s -> !s.nullable());
+ if (allNotNull) {
+ ImmutableSet<SlotReference> slotSet = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .filter(s -> s.getColumn().isPresent()
+ && columns.contains(s.getColumn().get()))
+ .collect(ImmutableSet.toImmutableSet());
+ TableFdItem tableFdItem =
FdFactory.INSTANCE.createTableFdItem(slotSet,
+ true, false, ImmutableSet.of(table));
+ builder.add(tableFdItem);
+ } else {
+ ImmutableSet<SlotReference> slotSet = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .filter(s -> s.getColumn().isPresent()
+ && columns.contains(s.getColumn().get()))
+ .collect(ImmutableSet.toImmutableSet());
+ TableFdItem tableFdItem =
FdFactory.INSTANCE.createTableFdItem(slotSet,
+ true, true, ImmutableSet.of(table));
+ builder.add(tableFdItem);
+ }
+ });
+ return builder.build();
+ }
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalDeferMaterializeTopN.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalDeferMaterializeTopN.java
index 6b6f6d432eb..5bf0afe1fae 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalDeferMaterializeTopN.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalDeferMaterializeTopN.java
@@ -18,6 +18,9 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ExprFdItem;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
@@ -34,6 +37,7 @@ import org.apache.doris.nereids.util.Utils;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.List;
import java.util.Objects;
@@ -123,11 +127,30 @@ public class LogicalDeferMaterializeTopN<CHILD_TYPE
extends Plan> extends Logica
List<Slot> output = outputSupplier.get();
output.forEach(builder::addUniformSlot);
output.forEach(builder::addUniqueSlot);
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
fd = builder.build();
}
return fd;
}
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet<FdItem> fdItems =
child(0).getLogicalProperties().getFunctionalDependencies().getFdItems();
+ if (getLimit() == 1) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ List<Slot> output = outputSupplier.get();
+ ImmutableSet<SlotReference> slotSet = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+ ExprFdItem fdItem = FdFactory.INSTANCE.createExprFdItem(slotSet,
true, slotSet);
+ builder.add(fdItem);
+ fdItems = builder.build();
+ }
+ return fdItems;
+ }
+
@Override
public <R, C> R accept(PlanVisitor<R, C> visitor, C context) {
return visitor.visitLogicalDeferMaterializeTopN(this, context);
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 c1753f147e4..707da68fe8f 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
@@ -18,6 +18,9 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ExprFdItem;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.NamedExpression;
@@ -35,6 +38,7 @@ import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
+import java.util.Set;
import java.util.function.Supplier;
/**
@@ -120,6 +124,32 @@ public class LogicalExcept extends LogicalSetOperation {
if (qualifier == Qualifier.DISTINCT) {
builder.addUniqueSlot(ImmutableSet.copyOf(outputSupplier.get()));
}
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ Set<NamedExpression> output =
ImmutableSet.copyOf(outputSupplier.get());
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<SlotReference> exprs = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+
+ if (qualifier == Qualifier.DISTINCT) {
+ ExprFdItem fdItem = FdFactory.INSTANCE.createExprFdItem(exprs,
true, exprs);
+ builder.add(fdItem);
+
+ // only inherit from left side
+ ImmutableSet<FdItem> leftFdItems = child(0).getLogicalProperties()
+ .getFunctionalDependencies().getFdItems();
+
+ builder.addAll(leftFdItems);
+ }
+
return builder.build();
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
index 0c4699fcbe2..67ccc672bf4 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalFilter.java
@@ -18,6 +18,7 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
@@ -146,6 +147,18 @@ public class LogicalFilter<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_T
Builder fdBuilder = new Builder(
child().getLogicalProperties().getFunctionalDependencies());
getConjuncts().forEach(e ->
fdBuilder.addUniformSlot(ExpressionUtils.extractUniformSlot(e)));
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ fdBuilder.addFdItems(fdItems);
return fdBuilder.build();
}
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<FdItem> childItems =
child().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ builder.addAll(childItems);
+
+ return builder.build();
+ }
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalGenerate.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalGenerate.java
index 0de6e46ce25..2bb5d79b48b 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalGenerate.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalGenerate.java
@@ -18,6 +18,7 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
@@ -31,6 +32,7 @@ import org.apache.doris.nereids.util.Utils;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import java.util.List;
@@ -146,6 +148,13 @@ public class LogicalGenerate<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD
public FunctionalDependencies computeFuncDeps(Supplier<List<Slot>>
outputSupplier) {
FunctionalDependencies.Builder builder = new
FunctionalDependencies.Builder();
builder.addUniformSlot(child(0).getLogicalProperties().getFunctionalDependencies());
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
return builder.build();
}
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ return ImmutableSet.of();
+ }
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalHaving.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalHaving.java
index 25600c56d26..e4d01f12748 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalHaving.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalHaving.java
@@ -18,6 +18,7 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
@@ -123,9 +124,21 @@ public class LogicalHaving<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_T
Builder fdBuilder = new Builder(
child().getLogicalProperties().getFunctionalDependencies());
getConjuncts().forEach(e ->
fdBuilder.addUniformSlot(ExpressionUtils.extractUniformSlot(e)));
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ fdBuilder.addFdItems(fdItems);
return fdBuilder.build();
}
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<FdItem> childItems =
child().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ builder.addAll(childItems);
+
+ return builder.build();
+ }
+
@Override
public String toString() {
return Utils.toSqlString("LogicalHaving", "predicates",
getPredicate());
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 2d3006bda59..2fbdbd24561 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,6 +18,9 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ExprFdItem;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.NamedExpression;
@@ -35,6 +38,7 @@ import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
+import java.util.Set;
import java.util.function.Supplier;
/**
@@ -125,6 +129,34 @@ public class LogicalIntersect extends LogicalSetOperation {
if (qualifier == Qualifier.DISTINCT) {
builder.addUniqueSlot(ImmutableSet.copyOf(outputSupplier.get()));
}
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ Set<NamedExpression> output =
ImmutableSet.copyOf(outputSupplier.get());
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<SlotReference> exprs = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+
+ if (qualifier == Qualifier.DISTINCT) {
+ ExprFdItem fdItem = FdFactory.INSTANCE.createExprFdItem(exprs,
true, exprs);
+ builder.add(fdItem);
+ // inherit from both sides
+ ImmutableSet<FdItem> leftFdItems = child(0).getLogicalProperties()
+ .getFunctionalDependencies().getFdItems();
+ ImmutableSet<FdItem> rightFdItems = child(1).getLogicalProperties()
+ .getFunctionalDependencies().getFdItems();
+
+ builder.addAll(leftFdItems);
+ builder.addAll(rightFdItems);
+ }
+
return builder.build();
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
index d6d183408a7..80a40024a88 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalJoin.java
@@ -17,13 +17,17 @@
package org.apache.doris.nereids.trees.plans.logical;
+import org.apache.doris.catalog.TableIf;
import org.apache.doris.common.Pair;
import org.apache.doris.nereids.hint.DistributeHint;
import org.apache.doris.nereids.jobs.joinorder.hypergraph.bitmap.LongBitmap;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.properties.TableFdItem;
import org.apache.doris.nereids.rules.exploration.join.JoinReorderContext;
import org.apache.doris.nereids.trees.expressions.EqualPredicate;
import org.apache.doris.nereids.trees.expressions.EqualTo;
@@ -40,6 +44,7 @@ import
org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
import org.apache.doris.nereids.util.ExpressionUtils;
import org.apache.doris.nereids.util.ImmutableEqualSet;
import org.apache.doris.nereids.util.JoinUtils;
+import org.apache.doris.nereids.util.PlanUtils;
import org.apache.doris.nereids.util.Utils;
import com.google.common.base.Preconditions;
@@ -374,14 +379,16 @@ public class LogicalJoin<LEFT_CHILD_TYPE extends Plan,
RIGHT_CHILD_TYPE extends
public LogicalJoin<Plan, Plan> withJoinConjuncts(List<Expression>
hashJoinConjuncts,
List<Expression> otherJoinConjuncts) {
return new LogicalJoin<>(joinType, hashJoinConjuncts,
otherJoinConjuncts, markJoinConjuncts,
- hint, markJoinSlotReference, Optional.empty(),
Optional.empty(), children, null);
+ hint, markJoinSlotReference, Optional.empty(),
Optional.empty(),
+ children, null);
}
public LogicalJoin<Plan, Plan> withJoinConjuncts(List<Expression>
hashJoinConjuncts,
List<Expression>
otherJoinConjuncts,
List<Expression>
markJoinConjuncts) {
return new LogicalJoin<>(joinType, hashJoinConjuncts,
otherJoinConjuncts, markJoinConjuncts,
- hint, markJoinSlotReference, Optional.empty(),
Optional.empty(), children, null);
+ hint, markJoinSlotReference, Optional.empty(),
Optional.empty(),
+ children, null);
}
public LogicalJoin<Plan, Plan> withHashJoinConjunctsAndChildren(
@@ -409,7 +416,8 @@ public class LogicalJoin<LEFT_CHILD_TYPE extends Plan,
RIGHT_CHILD_TYPE extends
public LogicalJoin<Plan, Plan> withJoinType(JoinType joinType) {
return new LogicalJoin<>(joinType, hashJoinConjuncts,
otherJoinConjuncts, markJoinConjuncts,
- hint, markJoinSlotReference, Optional.empty(),
Optional.empty(), children, null);
+ hint, markJoinSlotReference, Optional.empty(),
Optional.empty(),
+ children, null);
}
public LogicalJoin<Plan, Plan> withTypeChildren(JoinType joinType, Plan
left, Plan right) {
@@ -510,9 +518,160 @@ public class LogicalJoin<LEFT_CHILD_TYPE extends Plan,
RIGHT_CHILD_TYPE extends
}
fdBuilder.addUniformSlot(left().getLogicalProperties().getFunctionalDependencies());
}
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ fdBuilder.addFdItems(fdItems);
return fdBuilder.build();
}
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ if (isMarkJoin() || joinType.isNullAwareLeftAntiJoin()
+ || joinType.isFullOuterJoin()
+ || !otherJoinConjuncts.isEmpty()) {
+ return ImmutableSet.of();
+ } else if (joinType.isLeftAntiJoin() || joinType.isLefSemiJoin()) {
+ return
left().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ } else if (joinType.isRightSemiJoin() || joinType.isRightAntiJoin()) {
+ return
right().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ } else if (joinType.isInnerJoin()) {
+ Pair<Set<Slot>, Set<Slot>> keys = extractNullRejectHashKeys();
+ if (keys == null) {
+ return ImmutableSet.of();
+ }
+ Set<Slot> leftSlotSet = keys.first;
+ Set<Slot> rightSlotSet = keys.second;
+
+ // enhance the fd from candidate to formal
+ ImmutableSet<FdItem> leftItems =
left().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ leftItems.stream().filter(e -> e.isCandidate()).forEach(f -> {
+ if (leftSlotSet.containsAll(f.getParentExprs())) {
+ f.setCandidate(false);
+ }
+ }
+ );
+ boolean isLeftUnique = leftItems.stream().filter(e ->
e.isCandidate())
+ .anyMatch(f ->
leftSlotSet.containsAll(f.getParentExprs()));
+
+ ImmutableSet<FdItem> rightItems =
right().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ rightItems.stream().filter(e -> e.isCandidate()).forEach(f -> {
+ if (rightSlotSet.containsAll(f.getParentExprs())) {
+ f.setCandidate(false);
+ }
+ }
+ );
+ boolean isRightUnique = rightItems.stream().filter(e ->
e.isCandidate())
+ .anyMatch(f ->
rightSlotSet.containsAll(f.getParentExprs()));
+
+ if (isRightUnique) {
+ // n to 1 unique
+ ImmutableSet<TableIf> rightTableSet =
PlanUtils.getTableSet((LogicalPlan) right());
+ leftItems.stream().filter(e -> e.isUnique()).forEach(f -> {
+ TableFdItem tableFdItem =
FdFactory.INSTANCE.createTableFdItem(f.getParentExprs(),
+ f.isUnique(), false, rightTableSet);
+ builder.add(tableFdItem);
+ }
+ );
+ } else if (isLeftUnique) {
+ // n to 1 unique
+ ImmutableSet<TableIf> leftTableSet =
PlanUtils.getTableSet((LogicalPlan) left());
+ rightItems.stream().filter(e -> e.isUnique()).forEach(f -> {
+ TableFdItem tableFdItem =
FdFactory.INSTANCE.createTableFdItem(f.getParentExprs(),
+ f.isUnique(), false, leftTableSet);
+ builder.add(tableFdItem);
+ }
+ );
+ } else {
+ // n to n, set the unique false
+ leftItems.stream().forEach(e ->
+ e.setUnique(false)
+ );
+ rightItems.stream().forEach(e ->
+ e.setUnique(false)
+ );
+ }
+ builder.addAll(leftItems);
+ builder.addAll(rightItems);
+ return builder.build();
+ } else if (joinType.isLeftOuterJoin()) {
+ Pair<Set<Slot>, Set<Slot>> keys = extractNullRejectHashKeys();
+ if (keys == null) {
+ return ImmutableSet.of();
+ }
+ Set<Slot> leftSlotSet = keys.first;
+ Set<Slot> rightSlotSet = keys.second;
+
+ // enhance the fd from candidate to formal
+ ImmutableSet<FdItem> leftItems =
left().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ leftItems.stream().filter(e -> e.isCandidate()).forEach(f -> {
+ if (leftSlotSet.containsAll(f.getParentExprs())) {
+ f.setCandidate(false);
+ }
+ }
+ );
+
+ ImmutableSet<FdItem> rightItems =
right().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ boolean isRightUnique = rightItems.stream().filter(e ->
e.isCandidate())
+ .anyMatch(f ->
rightSlotSet.containsAll(f.getParentExprs()));
+ if (isRightUnique) {
+ // n to 1 unique
+ ImmutableSet<TableIf> rightTableSet =
PlanUtils.getTableSet((LogicalPlan) right());
+ leftItems.stream().filter(e -> e.isUnique()).forEach(f -> {
+ TableFdItem tableFdItem =
FdFactory.INSTANCE.createTableFdItem(f.getParentExprs(),
+ f.isUnique(), false, rightTableSet);
+ builder.add(tableFdItem);
+ }
+ );
+ } else {
+ // n to n, set the unique false
+ leftItems.stream().forEach(e ->
+ e.setUnique(false)
+ );
+ }
+ builder.addAll(leftItems);
+ return builder.build();
+ } else if (joinType.isRightOuterJoin()) {
+ Pair<Set<Slot>, Set<Slot>> keys = extractNullRejectHashKeys();
+ if (keys == null) {
+ return ImmutableSet.of();
+ }
+ Set<Slot> leftSlotSet = keys.first;
+ Set<Slot> rightSlotSet = keys.second;
+
+ // enhance the fd from candidate to formal
+ ImmutableSet<FdItem> leftItems =
left().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ boolean isLeftUnique = leftItems.stream().filter(e ->
e.isCandidate())
+ .anyMatch(f ->
leftSlotSet.containsAll(f.getParentExprs()));
+
+ ImmutableSet<FdItem> rightItems =
right().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ rightItems.stream().filter(e -> e.isCandidate()).forEach(f -> {
+ if (rightSlotSet.containsAll(f.getParentExprs())) {
+ f.setCandidate(false);
+ }
+ }
+ );
+ if (isLeftUnique) {
+ // n to 1 unique
+ ImmutableSet<TableIf> leftTableSet =
PlanUtils.getTableSet((LogicalPlan) left());
+ rightItems.stream().filter(e -> e.isUnique()).forEach(f -> {
+ TableFdItem tableFdItem =
FdFactory.INSTANCE.createTableFdItem(f.getParentExprs(),
+ f.isUnique(), false, leftTableSet);
+ builder.add(tableFdItem);
+ }
+ );
+ } else {
+ // n to n, set the unique false
+ rightItems.stream().forEach(e ->
+ e.setUnique(false)
+ );
+ }
+ builder.addAll(rightItems);
+ return builder.build();
+ } else {
+ return ImmutableSet.of();
+ }
+ }
+
/**
* get Equal slot from join
*/
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalLimit.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalLimit.java
index df18b134f10..482c7e26058 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalLimit.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalLimit.java
@@ -18,11 +18,15 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ExprFdItem;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.LimitPhase;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.PlanType;
@@ -32,6 +36,7 @@ import org.apache.doris.nereids.util.Utils;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.List;
import java.util.Objects;
@@ -151,8 +156,27 @@ public class LogicalLimit<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TY
Builder builder = new Builder();
outputSupplier.get().forEach(builder::addUniformSlot);
outputSupplier.get().forEach(builder::addUniqueSlot);
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
fd = builder.build();
}
return fd;
}
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet<FdItem> fdItems =
child(0).getLogicalProperties().getFunctionalDependencies().getFdItems();
+ if (getLimit() == 1 && !phase.isLocal()) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ List<Slot> output = outputSupplier.get();
+ ImmutableSet<SlotReference> slotSet = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+ ExprFdItem fdItem = FdFactory.INSTANCE.createExprFdItem(slotSet,
true, slotSet);
+ builder.add(fdItem);
+ fdItems = builder.build();
+ }
+ return fdItems;
+ }
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalOneRowRelation.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalOneRowRelation.java
index c0c25f79693..d338be5cc88 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalOneRowRelation.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalOneRowRelation.java
@@ -18,11 +18,15 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ExprFdItem;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.NamedExpression;
import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.PlanType;
import org.apache.doris.nereids.trees.plans.RelationId;
@@ -31,10 +35,12 @@ import
org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
import org.apache.doris.nereids.util.Utils;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.List;
import java.util.Objects;
import java.util.Optional;
+import java.util.Set;
import java.util.function.Supplier;
/**
@@ -136,6 +142,22 @@ public class LogicalOneRowRelation extends LogicalRelation
implements OneRowRela
builder.addUniformSlot(s);
builder.addUniqueSlot(s);
});
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ Set<NamedExpression> output =
ImmutableSet.copyOf(outputSupplier.get());
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ ImmutableSet<SlotReference> slotSet = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+ ExprFdItem fdItem = FdFactory.INSTANCE.createExprFdItem(slotSet, true,
slotSet);
+ builder.add(fdItem);
+
return builder.build();
}
}
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 3c058c6e4d7..860bd263acb 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
@@ -17,11 +17,13 @@
package org.apache.doris.nereids.trees.plans.logical;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.trees.expressions.Slot;
import org.apache.doris.nereids.trees.plans.Plan;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.List;
import java.util.Optional;
@@ -60,4 +62,6 @@ public interface LogicalPlan extends Plan {
* - PropagateFD: propagate the fd
*/
FunctionalDependencies computeFuncDeps(Supplier<List<Slot>>
outputSupplier);
+
+ ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>> outputSupplier);
}
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 cdacfe95b66..5dda7bb56a9 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
@@ -20,6 +20,7 @@ package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.analyzer.Unbound;
import org.apache.doris.nereids.analyzer.UnboundStar;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Alias;
@@ -246,6 +247,18 @@ public class LogicalProject<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_
}
}
});
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<FdItem> childItems =
child().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ builder.addAll(childItems);
+
return builder.build();
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalRepeat.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalRepeat.java
index 8ee9e465a29..1c8a468b44b 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalRepeat.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalRepeat.java
@@ -18,6 +18,7 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
@@ -33,6 +34,7 @@ import org.apache.doris.nereids.util.Utils;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.List;
import java.util.Objects;
@@ -187,6 +189,18 @@ public class LogicalRepeat<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_T
outputSupplier.get().stream()
.filter(child(0).getLogicalProperties().getFunctionalDependencies()::isUniform)
.forEach(builder::addUniformSlot);
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<FdItem> childItems =
child().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ builder.addAll(childItems);
+
return builder.build();
}
}
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 73ae70e62bc..68a451f1df1 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
@@ -18,6 +18,7 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
@@ -30,6 +31,7 @@ import org.apache.doris.nereids.util.Utils;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
import org.apache.commons.lang3.StringUtils;
@@ -172,9 +174,17 @@ public class LogicalSubQueryAlias<CHILD_TYPE extends Plan>
extends LogicalUnary<
replaceMap.put(child(0).getOutput().get(i), outputs.get(i));
}
builder.replace(replaceMap);
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
return builder.build();
}
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ // TODO: inherit from child with replaceMap
+ return ImmutableSet.of();
+ }
+
public void setRelationId(RelationId relationId) {
this.relationId = relationId;
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
index a38778d8d50..5d2656eee59 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalTopN.java
@@ -18,12 +18,16 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ExprFdItem;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.FunctionalDependencies.Builder;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.properties.OrderKey;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.PlanType;
import org.apache.doris.nereids.trees.plans.algebra.TopN;
@@ -32,6 +36,7 @@ import org.apache.doris.nereids.util.Utils;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.List;
import java.util.Objects;
@@ -160,8 +165,27 @@ public class LogicalTopN<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TYP
List<Slot> output = outputSupplier.get();
output.forEach(builder::addUniformSlot);
output.forEach(builder::addUniqueSlot);
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
fd = builder.build();
}
return fd;
}
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet<FdItem> fdItems =
child(0).getLogicalProperties().getFunctionalDependencies().getFdItems();
+ if (getLimit() == 1) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ List<Slot> output = outputSupplier.get();
+ ImmutableSet<SlotReference> slotSet = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+ ExprFdItem fdItem = FdFactory.INSTANCE.createExprFdItem(slotSet,
true, slotSet);
+ builder.add(fdItem);
+ fdItems = builder.build();
+ }
+ return fdItems;
+ }
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalUnion.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalUnion.java
index 48d3fdf12ef..a7120cd2709 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalUnion.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalUnion.java
@@ -18,6 +18,9 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.ExprFdItem;
+import org.apache.doris.nereids.properties.FdFactory;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
@@ -37,6 +40,7 @@ import com.google.common.collect.ImmutableSet;
import java.util.List;
import java.util.Objects;
import java.util.Optional;
+import java.util.Set;
import java.util.function.Supplier;
/**
@@ -188,6 +192,26 @@ public class LogicalUnion extends LogicalSetOperation
implements Union, OutputPr
}
FunctionalDependencies.Builder builder = new
FunctionalDependencies.Builder();
builder.addUniqueSlot(ImmutableSet.copyOf(outputSupplier.get()));
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ Set<NamedExpression> output =
ImmutableSet.copyOf(outputSupplier.get());
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+
+ ImmutableSet<SlotReference> exprs = output.stream()
+ .filter(SlotReference.class::isInstance)
+ .map(SlotReference.class::cast)
+ .collect(ImmutableSet.toImmutableSet());
+
+ if (qualifier == Qualifier.DISTINCT) {
+ ExprFdItem fdItem = FdFactory.INSTANCE.createExprFdItem(exprs,
true, exprs);
+ builder.add(fdItem);
+ }
+
return builder.build();
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalWindow.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalWindow.java
index e8c16b49026..086643e9f8b 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalWindow.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalWindow.java
@@ -18,6 +18,7 @@
package org.apache.doris.nereids.trees.plans.logical;
import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.FdItem;
import org.apache.doris.nereids.properties.FunctionalDependencies;
import org.apache.doris.nereids.properties.LogicalProperties;
import org.apache.doris.nereids.trees.expressions.Expression;
@@ -234,7 +235,6 @@ public class LogicalWindow<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_T
}
WindowExpression windowExpr = (WindowExpression)
namedExpression.child(0);
List<Expression> partitionKeys = windowExpr.getPartitionKeys();
-
// Now we only support slot type keys
if (!partitionKeys.stream().allMatch(Slot.class::isInstance)) {
return;
@@ -260,6 +260,24 @@ public class LogicalWindow<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_T
}
}
+ private void updateFuncDepsByWindowExpr(NamedExpression namedExpression,
ImmutableSet.Builder<FdItem> builder) {
+ if (namedExpression.children().size() != 1 ||
!(namedExpression.child(0) instanceof WindowExpression)) {
+ return;
+ }
+ WindowExpression windowExpr = (WindowExpression)
namedExpression.child(0);
+ List<Expression> partitionKeys = windowExpr.getPartitionKeys();
+
+ // Now we only support slot type keys
+ if (!partitionKeys.stream().allMatch(Slot.class::isInstance)) {
+ return;
+ }
+ //ImmutableSet<Slot> slotSet = partitionKeys.stream()
+ // .map(s -> (Slot) s)
+ // .collect(ImmutableSet.toImmutableSet());
+ // TODO: if partition by keys are unique, output is uniform
+ // TODO: if partition by keys are uniform, output is unique
+ }
+
@Override
public FunctionalDependencies computeFuncDeps(Supplier<List<Slot>>
outputSupplier) {
FunctionalDependencies.Builder builder = new
FunctionalDependencies.Builder(
@@ -267,6 +285,21 @@ public class LogicalWindow<CHILD_TYPE extends Plan>
extends LogicalUnary<CHILD_T
for (NamedExpression namedExpression : windowExpressions) {
updateFuncDepsByWindowExpr(namedExpression, builder);
}
+ ImmutableSet<FdItem> fdItems = computeFdItems(outputSupplier);
+ builder.addFdItems(fdItems);
+ return builder.build();
+ }
+
+ @Override
+ public ImmutableSet<FdItem> computeFdItems(Supplier<List<Slot>>
outputSupplier) {
+ ImmutableSet.Builder<FdItem> builder = ImmutableSet.builder();
+ ImmutableSet<FdItem> childItems =
child().getLogicalProperties().getFunctionalDependencies().getFdItems();
+ builder.addAll(childItems);
+
+ for (NamedExpression namedExpression : windowExpressions) {
+ updateFuncDepsByWindowExpr(namedExpression, builder);
+ }
+
return builder.build();
}
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/util/PlanUtils.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/util/PlanUtils.java
index 405d0282d8c..45dbd5b8e82 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/util/PlanUtils.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/util/PlanUtils.java
@@ -17,19 +17,25 @@
package org.apache.doris.nereids.util;
+import org.apache.doris.catalog.TableIf;
import org.apache.doris.nereids.trees.expressions.ComparisonPredicate;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.NamedExpression;
import org.apache.doris.nereids.trees.expressions.Slot;
import org.apache.doris.nereids.trees.plans.Plan;
import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate;
+import org.apache.doris.nereids.trees.plans.logical.LogicalCatalogRelation;
import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
import org.apache.doris.nereids.trees.plans.logical.LogicalLimit;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
+import java.util.Collection;
+import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
@@ -96,4 +102,23 @@ public class PlanUtils {
}
return plan;
}
+
+ public static Set<LogicalCatalogRelation>
getLogicalScanFromRootPlan(LogicalPlan rootPlan) {
+ Set<LogicalCatalogRelation> tableSet = new HashSet<>();
+ tableSet.addAll((Collection<? extends LogicalCatalogRelation>) rootPlan
+ .collect(LogicalCatalogRelation.class::isInstance));
+ return tableSet;
+ }
+
+ /**
+ * get table set from plan root.
+ */
+ public static ImmutableSet<TableIf> getTableSet(LogicalPlan plan) {
+ Set<LogicalCatalogRelation> tableSet = new HashSet<>();
+ tableSet.addAll((Collection<? extends LogicalCatalogRelation>) plan
+ .collect(LogicalCatalogRelation.class::isInstance));
+ ImmutableSet<TableIf> resultSet = tableSet.stream().map(e ->
e.getTable())
+ .collect(ImmutableSet.toImmutableSet());
+ return resultSet;
+ }
}
diff --git
a/regression-test/data/nereids_tpcds_shape_sf100_p0/constraints/query23.out
b/regression-test/data/nereids_tpcds_shape_sf100_p0/constraints/query23.out
index 8491810ebf8..01138e6aea9 100644
--- a/regression-test/data/nereids_tpcds_shape_sf100_p0/constraints/query23.out
+++ b/regression-test/data/nereids_tpcds_shape_sf100_p0/constraints/query23.out
@@ -4,22 +4,21 @@ PhysicalCteAnchor ( cteId=CTEId#0 )
--PhysicalCteProducer ( cteId=CTEId#0 )
----PhysicalProject
------filter((cnt > 4))
---------hashAgg[GLOBAL]
-----------PhysicalDistribute[DistributionSpecHash]
-------------hashAgg[LOCAL]
---------------PhysicalProject
-----------------hashJoin[INNER_JOIN] hashCondition=((store_sales.ss_item_sk =
item.i_item_sk)) otherCondition=() build RFs:RF1 i_item_sk->[ss_item_sk]
-------------------PhysicalProject
---------------------hashJoin[INNER_JOIN]
hashCondition=((store_sales.ss_sold_date_sk = date_dim.d_date_sk))
otherCondition=() build RFs:RF0 d_date_sk->[ss_sold_date_sk]
-----------------------PhysicalProject
-------------------------PhysicalOlapScan[store_sales] apply RFs: RF0 RF1
-----------------------PhysicalDistribute[DistributionSpecReplicated]
-------------------------PhysicalProject
---------------------------filter(d_year IN (2000, 2001, 2002, 2003))
-----------------------------PhysicalOlapScan[date_dim]
-------------------PhysicalDistribute[DistributionSpecReplicated]
+--------hashAgg[LOCAL]
+----------PhysicalProject
+------------hashJoin[INNER_JOIN] hashCondition=((store_sales.ss_item_sk =
item.i_item_sk)) otherCondition=() build RFs:RF1 i_item_sk->[ss_item_sk]
+--------------PhysicalDistribute[DistributionSpecHash]
+----------------PhysicalProject
+------------------hashJoin[INNER_JOIN]
hashCondition=((store_sales.ss_sold_date_sk = date_dim.d_date_sk))
otherCondition=() build RFs:RF0 d_date_sk->[ss_sold_date_sk]
--------------------PhysicalProject
-----------------------PhysicalOlapScan[item]
+----------------------PhysicalOlapScan[store_sales] apply RFs: RF0 RF1
+--------------------PhysicalDistribute[DistributionSpecReplicated]
+----------------------PhysicalProject
+------------------------filter(d_year IN (2000, 2001, 2002, 2003))
+--------------------------PhysicalOlapScan[date_dim]
+--------------PhysicalDistribute[DistributionSpecHash]
+----------------PhysicalProject
+------------------PhysicalOlapScan[item]
--PhysicalCteAnchor ( cteId=CTEId#2 )
----PhysicalCteProducer ( cteId=CTEId#2 )
------PhysicalProject
@@ -56,10 +55,7 @@ PhysicalCteAnchor ( cteId=CTEId#0 )
--------------hashAgg[LOCAL]
----------------PhysicalUnion
------------------PhysicalProject
---------------------hashJoin[RIGHT_SEMI_JOIN]
hashCondition=((catalog_sales.cs_item_sk = frequent_ss_items.item_sk))
otherCondition=() build RFs:RF4 cs_item_sk->[item_sk]
-----------------------PhysicalDistribute[DistributionSpecHash]
-------------------------PhysicalProject
---------------------------PhysicalCteConsumer ( cteId=CTEId#0 ) apply RFs: RF4
+--------------------hashJoin[LEFT_SEMI_JOIN]
hashCondition=((catalog_sales.cs_item_sk = frequent_ss_items.item_sk))
otherCondition=()
----------------------PhysicalDistribute[DistributionSpecHash]
------------------------PhysicalProject
--------------------------hashJoin[LEFT_SEMI_JOIN]
hashCondition=((catalog_sales.cs_bill_customer_sk =
best_ss_customer.c_customer_sk)) otherCondition=()
@@ -74,18 +70,18 @@ PhysicalCteAnchor ( cteId=CTEId#0 )
----------------------------PhysicalDistribute[DistributionSpecHash]
------------------------------PhysicalProject
--------------------------------PhysicalCteConsumer ( cteId=CTEId#2 )
-------------------PhysicalProject
---------------------hashJoin[RIGHT_SEMI_JOIN]
hashCondition=((web_sales.ws_item_sk = frequent_ss_items.item_sk))
otherCondition=() build RFs:RF6 ws_item_sk->[item_sk]
----------------------PhysicalDistribute[DistributionSpecHash]
------------------------PhysicalProject
---------------------------PhysicalCteConsumer ( cteId=CTEId#0 ) apply RFs: RF6
+--------------------------PhysicalCteConsumer ( cteId=CTEId#0 )
+------------------PhysicalProject
+--------------------hashJoin[LEFT_SEMI_JOIN]
hashCondition=((web_sales.ws_item_sk = frequent_ss_items.item_sk))
otherCondition=()
----------------------PhysicalDistribute[DistributionSpecHash]
------------------------PhysicalProject
--------------------------hashJoin[LEFT_SEMI_JOIN]
hashCondition=((web_sales.ws_bill_customer_sk =
best_ss_customer.c_customer_sk)) otherCondition=()
----------------------------PhysicalDistribute[DistributionSpecHash]
-------------------------------hashJoin[INNER_JOIN]
hashCondition=((web_sales.ws_sold_date_sk = date_dim.d_date_sk))
otherCondition=() build RFs:RF5 d_date_sk->[ws_sold_date_sk]
+------------------------------hashJoin[INNER_JOIN]
hashCondition=((web_sales.ws_sold_date_sk = date_dim.d_date_sk))
otherCondition=() build RFs:RF4 d_date_sk->[ws_sold_date_sk]
--------------------------------PhysicalProject
-----------------------------------PhysicalOlapScan[web_sales] apply RFs: RF5
+----------------------------------PhysicalOlapScan[web_sales] apply RFs: RF4
--------------------------------PhysicalDistribute[DistributionSpecReplicated]
----------------------------------PhysicalProject
------------------------------------filter((date_dim.d_moy = 5) and
(date_dim.d_year = 2000))
@@ -93,4 +89,7 @@ PhysicalCteAnchor ( cteId=CTEId#0 )
----------------------------PhysicalDistribute[DistributionSpecHash]
------------------------------PhysicalProject
--------------------------------PhysicalCteConsumer ( cteId=CTEId#2 )
+----------------------PhysicalDistribute[DistributionSpecHash]
+------------------------PhysicalProject
+--------------------------PhysicalCteConsumer ( cteId=CTEId#0 )
diff --git
a/regression-test/suites/nereids_tpcds_shape_sf100_p0/constraints/query23.groovy
b/regression-test/suites/nereids_tpcds_shape_sf100_p0/constraints/query23.groovy
index 33d3f5d2176..43e5a404bb8 100644
---
a/regression-test/suites/nereids_tpcds_shape_sf100_p0/constraints/query23.groovy
+++
b/regression-test/suites/nereids_tpcds_shape_sf100_p0/constraints/query23.groovy
@@ -29,6 +29,8 @@ suite("query23") {
sql 'set forbid_unknown_col_stats=true'
sql 'set enable_nereids_timeout = false'
sql 'set enable_runtime_filter_prune=false'
+ sql 'set runtime_filter_type=8'
+ sql "set enable_nereids_rules='ELIMINATE_GROUP_BY_KEY'"
def ds = """with frequent_ss_items as
(select substr(i_item_desc,1,30) itemdesc,i_item_sk item_sk,d_date
solddate,count(*) cnt
from store_sales
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
