This is an automated email from the ASF dual-hosted git repository. yiguolei pushed a commit to branch branch-2.1 in repository https://gitbox.apache.org/repos/asf/doris.git
commit 6c14efc6d577fe3072302ffe807e15018c6a589e 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]
