You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by GitBox <gi...@apache.org> on 2020/05/29 03:46:11 UTC
[GitHub] [calcite] FatLittle opened a new pull request #1991: [CALCITE-3916] Implement top-down rule applying and upper bound space pruning in calcite
FatLittle opened a new pull request #1991:
URL: https://github.com/apache/calcite/pull/1991
related to https://github.com/apache/calcite/pull/1950
1. Introduce Top-Down rule applying strategy in VolcanoPlanner
2. Implement tasks and state transformations according to the design of Columnbia
3. Introduce a LowerBoundCost metadata to compute lower bound and used for pruning
4. Using a flag to control whether to use new strategy or not
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432883346
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteSystemProperty.java
##########
@@ -124,12 +124,21 @@
/**
* Whether to enable top-down optimization.
*
- * <p>Note: Enabling top-down optimization will automatically disable
- * the use of AbstractConverter and related rules.</p>
+ * <p>Note: Enabling top-down optimization will automatically enable
+ * top-down trait propagation.</p>
*/
public static final CalciteSystemProperty<Boolean> TOPDOWN_OPT =
booleanProperty("calcite.planner.topdown.opt", false);
+ /**
+ * Whether to enable top-down trait propagation.
+ *
+ * <p>Note: Enabling top-down optimization will automatically disable
+ * the use of AbstractConverter and related rules.</p>
+ */
+ public static final CalciteSystemProperty<Boolean> TOPDOWN_TRAITS =
+ booleanProperty("calcite.planner.topdown.traits", false);
Review comment:
Why adding this new flag to control traits propagation?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia edited a comment on pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
amaliujia edited a comment on pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#issuecomment-658413251
Awesome thanks!
Ah I took the first class of CMU 15721 when I was a master student there but I didn't remember Columbia was covered. Optimizer at that time was less fancy for me compared to lock-free data structures :)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451941971
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
##########
@@ -839,6 +806,67 @@ RelNode changeTraitsUsingConverters(
prunedNodes.add(rel);
}
+
+ /** Returns whether to skip a match. This happens if any of the
+ * {@link RelNode}s have importance zero. */
+ boolean skipMatch(VolcanoRuleMatch match) {
Review comment:
1. Currently, the planner is in charge of matching rules and pruning nodes (by importances or other mechanism). So I think it is more natural that planner judges whether a rule match is validate or not.
2. By moving to Planner, it could be easier to overwrite the logic by users, adding customized pruning logic
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433051546
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java
##########
@@ -0,0 +1,812 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.rel.PhysicalNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Predicate;
+
+class TopDownRuleDriver {
+
+ /**
+ * the Logger
+ */
+ private static final Logger LOGGER = CalciteTrace.getPlannerTaskTracer();
+
+ /**
+ * The planner
+ */
+ private final VolcanoPlanner planner;
+
+ /**
+ * the rule queue designed for top-down rule applying
+ */
+ private final CascadeRuleQueue ruleQueue;
+
+ /**
+ * all tasks waiting for execution
+ */
+ private Stack<Task> tasks = new Stack<>();
+
+ /**
+ * A task that is currently applying and may generate new RelNode.
+ * It provides a callback to schedule tasks for new RelNodes that
+ * are registered during task performing
+ */
+ private GeneratorTask applying = null;
+
+ /**
+ * relnodes that are generated by passThrough or derive
+ * these nodes will not takes part in another passThrough or derive
+ */
+ private Set<Integer> passThroughCache = new HashSet<>();
+
+ //~ Constructors -----------------------------------------------------------
+
+ TopDownRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new CascadeRuleQueue(planner);
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ void execute() {
+ TaskDescriptor description = new TaskDescriptor();
+ tasks.push(new OptimizeGroup(planner.root, planner.infCost));
+ exploreMaterializationRoots();
+ while (!tasks.isEmpty()) {
+ Task task = tasks.pop();
+ description.log(task);
+ task.perform();
+ }
+ }
+
+ private void exploreMaterializationRoots() {
+ for (RelSubset extraRoot : planner.explorationRoots) {
+ RelSet rootSet = VolcanoPlanner.equivRoot(extraRoot.set);
+ if (rootSet == planner.root.set) {
+ continue;
+ }
+ for (RelNode rel : extraRoot.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, extraRoot, true));
+ }
+ }
+ }
+ }
+
+ public CascadeRuleQueue ruleQueue() {
+ return ruleQueue;
+ }
+
+ public void reset() {
+ ruleQueue.clear();
+ tasks.clear();
+ passThroughCache.clear();
+ applying = null;
+ }
+
+ private interface Procedure {
+ void exec();
+ }
+
+ private void applyGenerator(GeneratorTask task, Procedure proc) {
+ GeneratorTask applying = this.applying;
+ this.applying = task;
+ try {
+ proc.exec();
+ } finally {
+ this.applying = applying;
+ }
+ }
+
+ void onSetMerged(RelSet set) {
+ applyGenerator(null, () -> clearProcessed(set));
+ }
+
+ private void clearProcessed(RelSet set) {
+ boolean explored = set.exploringState != null;
+ set.exploringState = null;
+
+ for (RelSubset subset : set.subsets) {
+ if (subset.resetOptimizing() || explored) {
+ Collection<RelNode> parentRels = subset.getParentRels();
+ for (RelNode parentRel : parentRels) {
+ clearProcessed(planner.getSet(parentRel));
+ }
+ if (subset == planner.root) {
+ tasks.push(new OptimizeGroup(subset, planner.infCost));
Review comment:
Task queue cannot be cleared here, because RuleMatchs are already popped from rule queue during ApplyRules. So ApplyRule tasks in the queue cannot be reproduced after cleaning.
The newly added task may rescan the root RelSet and schedule tasks for new relnodes. Duplicate tasks can be avoided as input RelSubsets still hold the previous optimizing status.
The only problem is that it may affect the rule applying sequence.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438511030
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
Review comment:
Oops, it's my typo. I should use planner.isLogical instead of a new method here. planner.isLogical is supposed to be overwritten by users.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433615977
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
I tried to reopen the test cases for top-down (see my second commit). Looks like rebasing your changes does not introduce more plan changes on old cases.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436254500
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
Review comment:
Will, it is somewhat like a metadata.
1. Different subclass of RelNodes may have different logic, like AC, RelNode, SpoolNode, RelSubset ...
2. It needs a cache and the cache should be invalidated when its input is changed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r452102742
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java
##########
@@ -0,0 +1,928 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.DeriveMode;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelTrait;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.PhysicalNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Predicate;
+
+class TopDownRuleDriver implements RuleDriver {
+
+ /**
+ * the Logger
+ */
+ private static final Logger LOGGER = CalciteTrace.getPlannerTaskTracer();
+
+ /**
+ * The planner
+ */
+ private final VolcanoPlanner planner;
+
+ /**
+ * the rule queue designed for top-down rule applying
+ */
+ private final CascadesRuleQueue ruleQueue;
+
+ /**
+ * all tasks waiting for execution
+ */
+ private Stack<Task> tasks = new Stack<>();
+
+ /**
+ * A task that is currently applying and may generate new RelNode.
+ * It provides a callback to schedule tasks for new RelNodes that
+ * are registered during task performing
+ */
+ private GeneratorTask applying = null;
+
+ /**
+ * relnodes that are generated by passThrough or derive
+ * these nodes will not takes part in another passThrough or derive
+ */
+ private Set<RelNode> passThroughCache = new HashSet<>();
+
+ //~ Constructors -----------------------------------------------------------
+
+ TopDownRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new CascadesRuleQueue(planner);
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ @Override public void drive() {
+ TaskDescriptor description = new TaskDescriptor();
+ tasks.push(new OptimizeGroup(planner.root, planner.infCost));
+ exploreMaterializationRoots();
+ while (!tasks.isEmpty()) {
+ Task task = tasks.pop();
+ description.log(task);
+ task.perform();
+ }
+ }
+
+ private void exploreMaterializationRoots() {
+ for (RelSubset extraRoot : planner.explorationRoots) {
+ RelSet rootSet = VolcanoPlanner.equivRoot(extraRoot.set);
+ if (rootSet == planner.root.set) {
+ continue;
+ }
+ for (RelNode rel : extraRoot.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, extraRoot, true));
+ }
+ }
+ }
+ }
+
+ @Override public CascadesRuleQueue getRuleQueue() {
+ return ruleQueue;
+ }
+
+ @Override public void clear() {
+ ruleQueue.clear();
+ tasks.clear();
+ passThroughCache.clear();
+ applying = null;
+ }
+
+ private interface Procedure {
+ void exec();
+ }
+
+ private void applyGenerator(GeneratorTask task, Procedure proc) {
+ GeneratorTask applying = this.applying;
+ this.applying = task;
+ try {
+ proc.exec();
+ } finally {
+ this.applying = applying;
+ }
+ }
+
+ public void onSetMerged(RelSet set) {
+ applyGenerator(null, () -> clearProcessed(set));
+ }
+
+ private void clearProcessed(RelSet set) {
+ boolean explored = set.exploringState != null;
+ set.exploringState = null;
+
+ for (RelSubset subset : set.subsets) {
+ if (subset.resetOptimizing() || explored) {
+ Collection<RelNode> parentRels = subset.getParentRels();
+ for (RelNode parentRel : parentRels) {
+ clearProcessed(planner.getSet(parentRel));
+ }
+ if (subset == planner.root) {
+ tasks.push(new OptimizeGroup(subset, planner.infCost));
+ }
+ }
+ }
+ }
+
+ public void onProduce(RelNode node, RelSubset subset) {
+ if (applying == null || subset.set
+ != VolcanoPlanner.equivRoot(applying.group().set)) {
+ return;
+ }
+
+ if (!applying.onProduce(node)) {
+ return;
+ }
+
+ if (!planner.isLogical(node)) {
+ RelSubset optimizingGroup = null;
+ boolean canPassThrough = node instanceof PhysicalNode
+ && !passThroughCache.contains(node);
+ if (!canPassThrough && subset.taskState != null) {
+ optimizingGroup = subset;
+ } else {
+ RelOptCost upperBound = planner.zeroCost;
+ RelSet set = subset.getSet();
+ List<RelSubset> subsetsToPassThrough = new ArrayList<>();
+ for (RelSubset otherSubset : set.subsets) {
+ if (!otherSubset.isRequired() || otherSubset != planner.root
+ && otherSubset.taskState != RelSubset.OptimizeState.OPTIMIZING) {
+ continue;
+ }
+ if (node.getTraitSet().satisfies(otherSubset.getTraitSet())) {
+ if (upperBound.isLt(otherSubset.upperBound)) {
+ upperBound = otherSubset.upperBound;
+ optimizingGroup = otherSubset;
+ }
+ } else if (canPassThrough) {
+ subsetsToPassThrough.add(otherSubset);
+ }
+ }
+ for (RelSubset otherSubset : subsetsToPassThrough) {
+ Task task = getOptimizeInputTask(node, otherSubset);
+ if (task != null) {
+ tasks.push(task);
+ }
+ }
+ }
+ if (optimizingGroup == null) {
+ return;
+ }
+ Task task = getOptimizeInputTask(node, optimizingGroup);
+ if (task != null) {
+ tasks.push(task);
+ }
+ } else {
+ boolean optimizing = subset.set.subsets.stream()
+ .anyMatch(s -> s.taskState == RelSubset.OptimizeState.OPTIMIZING);
+ tasks.push(
+ new OptimizeMExpr(node, applying.group(),
+ applying.exploring() && !optimizing));
+ }
+ }
+
+ //~ Inner Classes ----------------------------------------------------------
+
+ /**
+ * Base class for planner task
+ */
+ private interface Task {
+ void perform();
+ void describe(TaskDescriptor desc);
+ }
+
+ /**
+ * A class for task logging
+ */
+ private static class TaskDescriptor {
+ private boolean first = true;
+ private StringBuilder builder = new StringBuilder();
+
+ void log(Task task) {
+ if (!LOGGER.isDebugEnabled()) {
+ return;
+ }
+ first = true;
+ builder.setLength(0);
+ builder.append("Execute task: ").append(task.getClass().getSimpleName());
+ task.describe(this);
+ if (!first) {
+ builder.append(")");
+ }
+
+ LOGGER.info(builder.toString());
+ }
+
+ TaskDescriptor item(String name, Object value) {
+ if (first) {
+ first = false;
+ builder.append("(");
+ } else {
+ builder.append(", ");
+ }
+ builder.append(name).append("=").append(value);
+ return this;
+ }
+ }
+
+ private interface GeneratorTask extends Task {
+ RelSubset group();
+ boolean exploring();
+ default boolean onProduce(RelNode node) {
+ return true;
+ }
+ }
+
+ /**
+ * O_GROUP
+ */
+ private class OptimizeGroup implements Task {
+ private final RelSubset group;
+ private RelOptCost upperBound;
+
+ OptimizeGroup(RelSubset group, RelOptCost upperBound) {
+ this.group = group;
+ this.upperBound = upperBound;
+ }
+
+ @Override public void perform() {
+ RelOptCost winner = group.getWinnerCost();
+ if (winner != null) {
+ return;
+ }
+
+ if (group.taskState != null && upperBound.isLe(group.upperBound)) {
+ // this group failed to optimize before or it is a ring
+ return;
+ }
+
+ group.startOptimize(upperBound);
+
+ // cannot decide an actual lower bound before MExpr are fully explored
+ // so delay the lower bound checking
+
+ // a gate keeper to update context
+ tasks.push(new GroupOptimized(group));
+
+ // optimize mExprs in group
+ List<RelNode> physicals = new ArrayList<>();
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, false));
+ } else if (rel.isEnforcer()) {
+ // Enforcers have lower priority than other physical nodes
+ physicals.add(0, rel);
+ } else {
+ physicals.add(rel);
+ }
+ }
+ // always apply O_INPUTS first so as to get an valid upper bound
+ for (RelNode rel : physicals) {
+ Task task = getOptimizeInputTask(rel, group);
+ if (task != null) {
+ tasks.add(task);
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group).item("upperBound", upperBound);
+ }
+ }
+
+ /**
+ * Mark the group optimized
+ */
+ private static class GroupOptimized implements Task {
+ private final RelSubset group;
+
+ GroupOptimized(RelSubset group) {
+ this.group = group;
+ }
+
+ @Override public void perform() {
+ group.optimized();
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * O_EXPR
+ */
+ private class OptimizeMExpr implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean explore;
+
+ OptimizeMExpr(RelNode mExpr,
+ RelSubset group, boolean explore) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.explore = explore;
+ }
+
+ @Override public void perform() {
+ if (explore && group.isExplored()) {
+ return;
+ }
+ // 1. explode input
+ // 2. apply other rules
+ tasks.push(new ApplyRules(mExpr, group, explore));
+ for (int i = mExpr.getInputs().size() - 1; i >= 0; --i) {
+ tasks.push(new ExploreInput(mExpr, i));
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("explore", explore);
+ }
+ }
+
+ /**
+ * ensure ExploreInput are working on the correct input group since calcite
+ * may merge sets
+ */
+ private class EnsureGroupExplored implements Task {
+
+ private final RelSubset input;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ EnsureGroupExplored(RelSubset input, RelNode parent, int inputOrdinal) {
+ this.input = input;
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (parent.getInput(inputOrdinal) != input) {
+ tasks.push(new ExploreInput(parent, inputOrdinal));
+ return;
+ }
+ input.setExplored();
+ for (RelSubset subset : input.getSet().subsets) {
+ // clear the LB cache as exploring state have changed
+ input.getCluster().getMetadataQuery().clearCache(subset);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", parent).item("i", inputOrdinal);
+ }
+ }
+
+ /**
+ * E_GROUP
+ */
+ private class ExploreInput implements Task {
+ private final RelSubset group;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ ExploreInput(RelNode parent, int inputOrdinal) {
+ this.group = (RelSubset) parent.getInput(inputOrdinal);
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (!group.explore()) {
+ return;
+ }
+ tasks.push(new EnsureGroupExplored(group, parent, inputOrdinal));
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, true));
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * extract rule matches from rule queue and add them to task stack
+ */
+ private class ApplyRules implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRules(RelNode mExpr, RelSubset group, boolean exploring) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void perform() {
+ Pair<RelNode, Predicate<VolcanoRuleMatch>> category =
+ exploring ? Pair.of(mExpr, planner::isTransformationRule)
+ : Pair.of(mExpr, m -> true);
+ VolcanoRuleMatch match = ruleQueue.popMatch(category);
+ while (match != null) {
+ tasks.push(new ApplyRule(match, group, exploring));
+ match = ruleQueue.popMatch(category);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("exploring", exploring);
+ }
+ }
+
+ /**
+ * APPLY_RULE
+ */
+ private class ApplyRule implements GeneratorTask {
+ private final VolcanoRuleMatch match;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRule(VolcanoRuleMatch match, RelSubset group, boolean exploring) {
+ this.match = match;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("match", match).item("exploring", exploring);
+ }
+
+ @Override public void perform() {
+ if (!exploring && !planner.isLogical(match.rel(0)) && !checkLowerBound()) {
+ // for implementation and enforcing rules,
+ // we can skip rule match by checking the lower bound
+ // however, we cannot decide LB for logical nodes,
+ // so we only check enforcing rules now
+ if (!group.getTraitSet().satisfies(match.rels[0].getTraitSet())) {
+ // the match cannot be discarded directly
+ // because of another subset's upper bound
+ ruleQueue.addMatch(match);
+ }
+ return;
+ }
+
+ applyGenerator(this, match::onMatch);
+ }
+
+ private boolean checkLowerBound() {
+ RelOptCost upperBound = group.upperBound;
+ if (upperBound.isInfinite()) {
+ return true;
+ }
+ RelOptCost lb = planner.getLowerBound(match);
+ if (upperBound.isLe(lb)) {
+ if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug(
+ "Skip because of lower bound. LB = {}, UP = {}",
+ lb, upperBound);
+ }
+ return false;
+ }
+ return true;
+ }
+
+ @Override public RelSubset group() {
+ return group;
+ }
+
+ @Override public boolean exploring() {
+ return exploring;
+ }
+ }
+
+ private Task getOptimizeInputTask(RelNode rel, RelSubset group) {
+ if (!rel.getTraitSet().satisfies(group.getTraitSet())) {
+ RelNode passThroughRel = convert(rel, group);
+ if (passThroughRel == null) {
+ if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug("Skip optimizing because of traits: {}", rel);
+ }
+ return null;
+ }
+ final RelNode finalPassThroughRel = passThroughRel;
+ applyGenerator(null, () ->
+ planner.register(finalPassThroughRel, group));
+ rel = passThroughRel;
+ }
+ boolean unProcess = false;
+ for (RelNode input : rel.getInputs()) {
+ RelOptCost winner = ((RelSubset) input).getWinnerCost();
+ if (winner == null) {
+ unProcess = true;
+ break;
+ }
+ }
+ if (!unProcess) {
+ return new DeriveTrait(rel, group);
+ }
+ if (rel.getInputs().size() == 1) {
+ return new OptimizeInput1(rel, group);
+ }
+ return new OptimizeInputs(rel, group);
+ }
+
+ private RelNode convert(RelNode rel, RelSubset group) {
+ if (!passThroughCache.contains(rel)) {
+ RelNode passThrough = group.passThrough(rel);
+ if (passThrough != null) {
+ passThroughCache.add(passThrough);
+ return passThrough;
+ }
+ }
+ VolcanoRuleMatch match = ruleQueue.popMatch(
+ Pair.of(rel,
+ m -> m.getRule() instanceof ConverterRule
+ && m.getRule().getOutTrait().satisfies(group.getTraitSet().getConvention())));
+ if (match != null) {
+ tasks.add(new ApplyRule(match, group, false));
+ }
+ return null;
+ }
+
+ /**
+ * O_INPUT when there is only one input
+ */
+ private class OptimizeInput1 implements Task {
+
+ private final RelNode mExpr;
+ private final RelSubset group;
+
+ OptimizeInput1(RelNode mExpr, RelSubset group) {
+ this.mExpr = mExpr;
+ this.group = group;
+ }
+
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("upperBound", group.upperBound);
+ }
+
+ @Override public void perform() {
+ RelOptCost upperBound = group.upperBound;
+ RelOptCost upperForInput = planner.upperBoundForInputs(mExpr, upperBound);
+ if (upperForInput.isLe(planner.zeroCost)) {
+ if (LOGGER.isDebugEnabled()) {
Review comment:
resolved
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java
##########
@@ -0,0 +1,928 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.DeriveMode;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelTrait;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.PhysicalNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Predicate;
+
+class TopDownRuleDriver implements RuleDriver {
+
+ /**
+ * the Logger
+ */
+ private static final Logger LOGGER = CalciteTrace.getPlannerTaskTracer();
+
+ /**
+ * The planner
+ */
+ private final VolcanoPlanner planner;
+
+ /**
+ * the rule queue designed for top-down rule applying
+ */
+ private final CascadesRuleQueue ruleQueue;
+
+ /**
+ * all tasks waiting for execution
+ */
+ private Stack<Task> tasks = new Stack<>();
+
+ /**
+ * A task that is currently applying and may generate new RelNode.
+ * It provides a callback to schedule tasks for new RelNodes that
+ * are registered during task performing
+ */
+ private GeneratorTask applying = null;
+
+ /**
+ * relnodes that are generated by passThrough or derive
+ * these nodes will not takes part in another passThrough or derive
+ */
+ private Set<RelNode> passThroughCache = new HashSet<>();
+
+ //~ Constructors -----------------------------------------------------------
+
+ TopDownRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new CascadesRuleQueue(planner);
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ @Override public void drive() {
+ TaskDescriptor description = new TaskDescriptor();
+ tasks.push(new OptimizeGroup(planner.root, planner.infCost));
+ exploreMaterializationRoots();
+ while (!tasks.isEmpty()) {
+ Task task = tasks.pop();
+ description.log(task);
+ task.perform();
+ }
+ }
+
+ private void exploreMaterializationRoots() {
+ for (RelSubset extraRoot : planner.explorationRoots) {
+ RelSet rootSet = VolcanoPlanner.equivRoot(extraRoot.set);
+ if (rootSet == planner.root.set) {
+ continue;
+ }
+ for (RelNode rel : extraRoot.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, extraRoot, true));
+ }
+ }
+ }
+ }
+
+ @Override public CascadesRuleQueue getRuleQueue() {
+ return ruleQueue;
+ }
+
+ @Override public void clear() {
+ ruleQueue.clear();
+ tasks.clear();
+ passThroughCache.clear();
+ applying = null;
+ }
+
+ private interface Procedure {
+ void exec();
+ }
+
+ private void applyGenerator(GeneratorTask task, Procedure proc) {
+ GeneratorTask applying = this.applying;
+ this.applying = task;
+ try {
+ proc.exec();
+ } finally {
+ this.applying = applying;
+ }
+ }
+
+ public void onSetMerged(RelSet set) {
+ applyGenerator(null, () -> clearProcessed(set));
+ }
+
+ private void clearProcessed(RelSet set) {
+ boolean explored = set.exploringState != null;
+ set.exploringState = null;
+
+ for (RelSubset subset : set.subsets) {
+ if (subset.resetOptimizing() || explored) {
+ Collection<RelNode> parentRels = subset.getParentRels();
+ for (RelNode parentRel : parentRels) {
+ clearProcessed(planner.getSet(parentRel));
+ }
+ if (subset == planner.root) {
+ tasks.push(new OptimizeGroup(subset, planner.infCost));
+ }
+ }
+ }
+ }
+
+ public void onProduce(RelNode node, RelSubset subset) {
+ if (applying == null || subset.set
+ != VolcanoPlanner.equivRoot(applying.group().set)) {
+ return;
+ }
+
+ if (!applying.onProduce(node)) {
+ return;
+ }
+
+ if (!planner.isLogical(node)) {
+ RelSubset optimizingGroup = null;
+ boolean canPassThrough = node instanceof PhysicalNode
+ && !passThroughCache.contains(node);
+ if (!canPassThrough && subset.taskState != null) {
+ optimizingGroup = subset;
+ } else {
+ RelOptCost upperBound = planner.zeroCost;
+ RelSet set = subset.getSet();
+ List<RelSubset> subsetsToPassThrough = new ArrayList<>();
+ for (RelSubset otherSubset : set.subsets) {
+ if (!otherSubset.isRequired() || otherSubset != planner.root
+ && otherSubset.taskState != RelSubset.OptimizeState.OPTIMIZING) {
+ continue;
+ }
+ if (node.getTraitSet().satisfies(otherSubset.getTraitSet())) {
+ if (upperBound.isLt(otherSubset.upperBound)) {
+ upperBound = otherSubset.upperBound;
+ optimizingGroup = otherSubset;
+ }
+ } else if (canPassThrough) {
+ subsetsToPassThrough.add(otherSubset);
+ }
+ }
+ for (RelSubset otherSubset : subsetsToPassThrough) {
+ Task task = getOptimizeInputTask(node, otherSubset);
+ if (task != null) {
+ tasks.push(task);
+ }
+ }
+ }
+ if (optimizingGroup == null) {
+ return;
+ }
+ Task task = getOptimizeInputTask(node, optimizingGroup);
+ if (task != null) {
+ tasks.push(task);
+ }
+ } else {
+ boolean optimizing = subset.set.subsets.stream()
+ .anyMatch(s -> s.taskState == RelSubset.OptimizeState.OPTIMIZING);
+ tasks.push(
+ new OptimizeMExpr(node, applying.group(),
+ applying.exploring() && !optimizing));
+ }
+ }
+
+ //~ Inner Classes ----------------------------------------------------------
+
+ /**
+ * Base class for planner task
+ */
+ private interface Task {
+ void perform();
+ void describe(TaskDescriptor desc);
+ }
+
+ /**
+ * A class for task logging
+ */
+ private static class TaskDescriptor {
+ private boolean first = true;
+ private StringBuilder builder = new StringBuilder();
+
+ void log(Task task) {
+ if (!LOGGER.isDebugEnabled()) {
+ return;
+ }
+ first = true;
+ builder.setLength(0);
+ builder.append("Execute task: ").append(task.getClass().getSimpleName());
+ task.describe(this);
+ if (!first) {
+ builder.append(")");
+ }
+
+ LOGGER.info(builder.toString());
+ }
+
+ TaskDescriptor item(String name, Object value) {
+ if (first) {
+ first = false;
+ builder.append("(");
+ } else {
+ builder.append(", ");
+ }
+ builder.append(name).append("=").append(value);
+ return this;
+ }
+ }
+
+ private interface GeneratorTask extends Task {
+ RelSubset group();
+ boolean exploring();
+ default boolean onProduce(RelNode node) {
+ return true;
+ }
+ }
+
+ /**
+ * O_GROUP
+ */
+ private class OptimizeGroup implements Task {
+ private final RelSubset group;
+ private RelOptCost upperBound;
+
+ OptimizeGroup(RelSubset group, RelOptCost upperBound) {
+ this.group = group;
+ this.upperBound = upperBound;
+ }
+
+ @Override public void perform() {
+ RelOptCost winner = group.getWinnerCost();
+ if (winner != null) {
+ return;
+ }
+
+ if (group.taskState != null && upperBound.isLe(group.upperBound)) {
+ // this group failed to optimize before or it is a ring
+ return;
+ }
+
+ group.startOptimize(upperBound);
+
+ // cannot decide an actual lower bound before MExpr are fully explored
+ // so delay the lower bound checking
+
+ // a gate keeper to update context
+ tasks.push(new GroupOptimized(group));
+
+ // optimize mExprs in group
+ List<RelNode> physicals = new ArrayList<>();
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, false));
+ } else if (rel.isEnforcer()) {
+ // Enforcers have lower priority than other physical nodes
+ physicals.add(0, rel);
+ } else {
+ physicals.add(rel);
+ }
+ }
+ // always apply O_INPUTS first so as to get an valid upper bound
+ for (RelNode rel : physicals) {
+ Task task = getOptimizeInputTask(rel, group);
+ if (task != null) {
+ tasks.add(task);
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group).item("upperBound", upperBound);
+ }
+ }
+
+ /**
+ * Mark the group optimized
+ */
+ private static class GroupOptimized implements Task {
+ private final RelSubset group;
+
+ GroupOptimized(RelSubset group) {
+ this.group = group;
+ }
+
+ @Override public void perform() {
+ group.optimized();
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * O_EXPR
+ */
+ private class OptimizeMExpr implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean explore;
+
+ OptimizeMExpr(RelNode mExpr,
+ RelSubset group, boolean explore) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.explore = explore;
+ }
+
+ @Override public void perform() {
+ if (explore && group.isExplored()) {
+ return;
+ }
+ // 1. explode input
+ // 2. apply other rules
+ tasks.push(new ApplyRules(mExpr, group, explore));
+ for (int i = mExpr.getInputs().size() - 1; i >= 0; --i) {
+ tasks.push(new ExploreInput(mExpr, i));
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("explore", explore);
+ }
+ }
+
+ /**
+ * ensure ExploreInput are working on the correct input group since calcite
+ * may merge sets
+ */
+ private class EnsureGroupExplored implements Task {
+
+ private final RelSubset input;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ EnsureGroupExplored(RelSubset input, RelNode parent, int inputOrdinal) {
+ this.input = input;
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (parent.getInput(inputOrdinal) != input) {
+ tasks.push(new ExploreInput(parent, inputOrdinal));
+ return;
+ }
+ input.setExplored();
+ for (RelSubset subset : input.getSet().subsets) {
+ // clear the LB cache as exploring state have changed
+ input.getCluster().getMetadataQuery().clearCache(subset);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", parent).item("i", inputOrdinal);
+ }
+ }
+
+ /**
+ * E_GROUP
+ */
+ private class ExploreInput implements Task {
+ private final RelSubset group;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ ExploreInput(RelNode parent, int inputOrdinal) {
+ this.group = (RelSubset) parent.getInput(inputOrdinal);
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (!group.explore()) {
+ return;
+ }
+ tasks.push(new EnsureGroupExplored(group, parent, inputOrdinal));
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, true));
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * extract rule matches from rule queue and add them to task stack
+ */
+ private class ApplyRules implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRules(RelNode mExpr, RelSubset group, boolean exploring) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void perform() {
+ Pair<RelNode, Predicate<VolcanoRuleMatch>> category =
+ exploring ? Pair.of(mExpr, planner::isTransformationRule)
+ : Pair.of(mExpr, m -> true);
+ VolcanoRuleMatch match = ruleQueue.popMatch(category);
+ while (match != null) {
+ tasks.push(new ApplyRule(match, group, exploring));
+ match = ruleQueue.popMatch(category);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("exploring", exploring);
+ }
+ }
+
+ /**
+ * APPLY_RULE
+ */
+ private class ApplyRule implements GeneratorTask {
+ private final VolcanoRuleMatch match;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRule(VolcanoRuleMatch match, RelSubset group, boolean exploring) {
+ this.match = match;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("match", match).item("exploring", exploring);
+ }
+
+ @Override public void perform() {
+ if (!exploring && !planner.isLogical(match.rel(0)) && !checkLowerBound()) {
+ // for implementation and enforcing rules,
+ // we can skip rule match by checking the lower bound
+ // however, we cannot decide LB for logical nodes,
+ // so we only check enforcing rules now
+ if (!group.getTraitSet().satisfies(match.rels[0].getTraitSet())) {
+ // the match cannot be discarded directly
+ // because of another subset's upper bound
+ ruleQueue.addMatch(match);
+ }
+ return;
+ }
+
+ applyGenerator(this, match::onMatch);
+ }
+
+ private boolean checkLowerBound() {
+ RelOptCost upperBound = group.upperBound;
+ if (upperBound.isInfinite()) {
+ return true;
+ }
+ RelOptCost lb = planner.getLowerBound(match);
+ if (upperBound.isLe(lb)) {
+ if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug(
+ "Skip because of lower bound. LB = {}, UP = {}",
+ lb, upperBound);
+ }
+ return false;
+ }
+ return true;
+ }
+
+ @Override public RelSubset group() {
+ return group;
+ }
+
+ @Override public boolean exploring() {
+ return exploring;
+ }
+ }
+
+ private Task getOptimizeInputTask(RelNode rel, RelSubset group) {
+ if (!rel.getTraitSet().satisfies(group.getTraitSet())) {
+ RelNode passThroughRel = convert(rel, group);
+ if (passThroughRel == null) {
+ if (LOGGER.isDebugEnabled()) {
Review comment:
resolved
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
##########
@@ -1396,6 +1437,103 @@ public void setLocked(boolean locked) {
this.locked = locked;
}
+ /**
+ * decide whether a rule is logical or not
+ * @param rel the specific rel node
+ * @return true if the relnode is a logical node
+ */
+ public boolean isLogical(RelNode rel) {
+ return !(rel instanceof PhysicalNode)
+ && rel.getConvention() != rootConvention;
+ }
+
+ /**
+ * check whether a rule match is a substitute rule match
+ * @param match the rule match to check
+ * @return true if the rule match is a substitute rule match
+ */
+ protected boolean isSubstituteRule(VolcanoRuleCall match) {
+ return match.getRule() instanceof SubstitutionRule;
+ }
+
+ /**
+ * check whether a rule match is a transformation rule match
+ * @param match the rule match to check
+ * @return true if the rule match is a transformation rule match
+ */
+ protected boolean isTransformationRule(VolcanoRuleCall match) {
+ if (match.getRule() instanceof SubstitutionRule) {
+ return true;
+ }
+ if (match.getRule() instanceof ConverterRule
+ && match.getRule().getOutTrait() == rootConvention) {
+ return false;
+ }
+ return match.getRule().getOperand().trait == Convention.NONE
+ || match.getRule().getOperand().trait == null;
+ }
+
+
+ /**
+ * gets the lower bound cost of a relational operator
+ * @param rel the rel node
+ * @return the lower bound cost of the given rel. The value is ensured NOT NULL.
+ */
+ protected RelOptCost getLowerBound(RelNode rel) {
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RelOptCost lowerBound = mq.getLowerBoundCost(rel, this);
+ if (lowerBound == null) {
+ return zeroCost;
+ }
+ return lowerBound;
+ }
+
+ /**
+ * Gets the lower bound cost of a RelOptRuleCall.
+ * A match match with inputs whose Sum(LB) is higher than upper bound
+ * needs not to be applied
+ */
+ protected RelOptCost getLowerBound(RelOptRuleCall match) {
+ return getLowerBoundInternal(match, match.getOperand0());
+ }
+
+ private RelOptCost getLowerBoundInternal(
+ RelOptRuleCall match, RelOptRuleOperand op) {
+ List<RelOptRuleOperand> children = op.getChildOperands();
+ if (children == null || children.isEmpty()) {
+ RelNode rel = match.rel(op.ordinalInRule);
+ RelOptCost sum = zeroCost;
+ for (RelNode input : rel.getInputs()) {
+ RelOptCost lb = getLowerBound(input);
+ sum = sum == zeroCost ? lb : sum.plus(lb);
+ }
+ return sum;
+ }
+ RelOptCost sum = null;
+ for (RelOptRuleOperand child : children) {
+ RelOptCost lb = getLowerBoundInternal(match, child);
+ sum = sum == null ? lb : sum.plus(lb);
+ }
+ return sum;
+ }
+
+ /**
+ * Gets the upper bound of its inputs.
+ * Allow users to overwrite this method as some implementations may have
+ * different cost model on some RelNodes, like Spool.
+ */
+ protected RelOptCost upperBoundForInputs(
+ RelNode mExpr, RelOptCost upperBound) {
+ if (!upperBound.isInfinite()) {
+ RelOptCost rootCost = mExpr.computeSelfCost(this,
Review comment:
resolved
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432935754
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteSystemProperty.java
##########
@@ -124,12 +124,21 @@
/**
* Whether to enable top-down optimization.
*
- * <p>Note: Enabling top-down optimization will automatically disable
- * the use of AbstractConverter and related rules.</p>
+ * <p>Note: Enabling top-down optimization will automatically enable
+ * top-down trait propagation.</p>
*/
public static final CalciteSystemProperty<Boolean> TOPDOWN_OPT =
booleanProperty("calcite.planner.topdown.opt", false);
+ /**
+ * Whether to enable top-down trait propagation.
+ *
+ * <p>Note: Enabling top-down optimization will automatically disable
+ * the use of AbstractConverter and related rules.</p>
+ */
+ public static final CalciteSystemProperty<Boolean> TOPDOWN_TRAITS =
+ booleanProperty("calcite.planner.topdown.traits", false);
Review comment:
because we can enable trait propagation even though top down rule applying is disabled
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438510391
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/MultiPhasedRuleDriver.java
##########
@@ -0,0 +1,87 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+/***
+ * <p>The algorithm executes repeatedly in a series of phases. In each phase
+ * the exact rules that may be fired varies. The mapping of phases to rule
+ * sets is maintained in the {@link #ruleQueue}.
+ *
+ * <p>In each phase, the planner then iterates over the rule matches presented
+ * by the rule queue until the rule queue becomes empty.
+ */
+public class MultiPhasedRuleDriver implements RuleDriver {
Review comment:
OK
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433405786
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
To be prepared for the top-down rule apply. With top-down rule apply, the original code path will be different. And there will be more plan diff combining with project/filter/join's trait propagation.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Implement top-down rule applying and upper bound space pruning in calcite
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432251842
##########
File path: core/src/test/resources/sql/misc.iq
##########
@@ -378,14 +378,14 @@ where exists (select 1 from "hr"."emps" where "empid" < 0);
(0 rows)
!ok
-EnumerableCalc(expr#0..1=[{inputs}], deptno=[$t0])
+EnumerableCalc(expr#0..1=[{inputs}], deptno=[$t1])
EnumerableNestedLoopJoin(condition=[true], joinType=[inner])
Review comment:
Some join factors are swapped because when rule applying sequence changes, the id of join factors also changed. And EnumerableNestedLoopJoin has a special handling that it prefers left branch having a lower id than the right branch.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450590729
##########
File path: plus/src/test/java/org/apache/calcite/adapter/tpcds/TpcdsTest.java
##########
@@ -220,29 +220,33 @@ protected void foo(CalciteAssert.AssertThat with, String tableName,
.withHook(Hook.PROGRAM, handler(true, 2))
.explainMatches("including all attributes ",
CalciteAssert.checkMaskedResultContains(""
- + "EnumerableCalc(expr#0..9=[{inputs}], expr#10=[/($t4, $t3)], expr#11=[CAST($t10):INTEGER NOT NULL], expr#12=[*($t4, $t4)], expr#13=[/($t12, $t3)], expr#14=[-($t5, $t13)], expr#15=[1], expr#16=[=($t3, $t15)], expr#17=[null:BIGINT], expr#18=[-($t3, $t15)], expr#19=[CASE($t16, $t17, $t18)], expr#20=[/($t14, $t19)], expr#21=[0.5:DECIMAL(2, 1)], expr#22=[POWER($t20, $t21)], expr#23=[CAST($t22):INTEGER NOT NULL], expr#24=[/($t23, $t11)], expr#25=[/($t6, $t3)], expr#26=[CAST($t25):INTEGER NOT NULL], expr#27=[*($t6, $t6)], expr#28=[/($t27, $t3)], expr#29=[-($t7, $t28)], expr#30=[/($t29, $t19)], expr#31=[POWER($t30, $t21)], expr#32=[CAST($t31):INTEGER NOT NULL], expr#33=[/($t32, $t26)], expr#34=[/($t8, $t3)], expr#35=[CAST($t34):INTEGER NOT NULL], expr#36=[*($t8, $t8)], expr#37=[/($t36, $t3)], expr#38=[-($t9, $t37)], expr#39=[/($t38, $t19)], expr#40=[POWER($t39, $t21)], expr#41=[CAST($t40):INTEGER NOT NULL], expr#42=[/($t41, $t35)], proj#0..3=[{exprs}], STORE_SALES_QUANTITYAVE=[$t11], STORE_SALES_QUANTITYSTDEV=[$t23], STORE_SALES_QUANTITYCOV=[$t24], AS_STORE_RETURNS_QUANTITYCOUNT=[$t3], AS_STORE_RETURNS_QUANTITYAVE=[$t26], AS_STORE_RETURNS_QUANTITYSTDEV=[$t32], STORE_RETURNS_QUANTITYCOV=[$t33], CATALOG_SALES_QUANTITYCOUNT=[$t3], CATALOG_SALES_QUANTITYAVE=[$t35], CATALOG_SALES_QUANTITYSTDEV=[$t42], CATALOG_SALES_QUANTITYCOV=[$t42]): rowcount = 100.0, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableLimit(fetch=[100]): rowcount = 100.0, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableSort(sort0=[$0], sort1=[$1], sort2=[$2], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 5.434029018852197E26, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableAggregate(group=[{0, 1, 2}], STORE_SALES_QUANTITYCOUNT=[COUNT()], agg#1=[$SUM0($3)], agg#2=[$SUM0($6)], agg#3=[$SUM0($4)], agg#4=[$SUM0($7)], agg#5=[$SUM0($5)], agg#6=[$SUM0($8)]): rowcount = 5.434029018852197E26, cumulative cost = {1.1892372507898816E28 rows, 1.2172225002228922E30 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..211=[{inputs}], expr#212=[*($t89, $t89)], expr#213=[*($t140, $t140)], expr#214=[*($t196, $t196)], I_ITEM_ID=[$t58], I_ITEM_DESC=[$t61], S_STATE=[$t24], SS_QUANTITY=[$t89], SR_RETURN_QUANTITY=[$t140], CS_QUANTITY=[$t196], $f6=[$t212], $f7=[$t213], $f8=[$t214]): rowcount = 5.434029018852197E27, cumulative cost = {1.0873492066864028E28 rows, 1.2172225002228922E30 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[AND(=($82, $133), =($81, $132), =($88, $139))], joinType=[inner]): rowcount = 5.434029018852197E27, cumulative cost = {5.439463048011832E27 rows, 1.8506796E7 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $86)], joinType=[inner]): rowcount = 2.3008402586892598E13, cumulative cost = {4.8588854672854766E13 rows, 7281360.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE]]): rowcount = 12.0, cumulative cost = {12.0 rows, 13.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $50)], joinType=[inner]): rowcount = 1.2782445881607E13, cumulative cost = {1.279800620431234E13 rows, 7281347.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], proj#0..27=[{exprs}], $condition=[$t29]): rowcount = 10957.35, cumulative cost = {84006.35 rows, 4382941.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $24)], joinType=[inner]): rowcount = 7.7770908E9, cumulative cost = {7.783045975286664E9 rows, 2898406.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, ITEM]]): rowcount = 18000.0, cumulative cost = {18000.0 rows, 18001.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE_SALES]]): rowcount = 2880404.0, cumulative cost = {2880404.0 rows, 2880405.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[AND(=($31, $79), =($30, $91))], joinType=[inner]): rowcount = 6.9978029381741304E16, cumulative cost = {7.0048032234040472E16 rows, 1.1225436E7 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 7.87597881975E8, cumulative cost = {7.884434212216867E8 rows, 5035701.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE_RETURNS]]): rowcount = 287514.0, cumulative cost = {287514.0 rows, 287515.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 3.94888649445E9, cumulative cost = {3.9520401026966867E9 rows, 6189735.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, CATALOG_SALES]]): rowcount = 1441548.0, cumulative cost = {1441548.0 rows, 1441549.0 cpu, 0.0 io}\n"));
+ + "EnumerableCalc(expr#0..9=[{inputs}], expr#10=[/($t4, $t3)], expr#11=[CAST($t10):INTEGER NOT NULL], expr#12=[*($t4, $t4)], expr#13=[/($t12, $t3)], expr#14=[-($t5, $t13)], expr#15=[1], expr#16=[=($t3, $t15)], expr#17=[null:BIGINT], expr#18=[-($t3, $t15)], expr#19=[CASE($t16, $t17, $t18)], expr#20=[/($t14, $t19)], expr#21=[0.5:DECIMAL(2, 1)], expr#22=[POWER($t20, $t21)], expr#23=[CAST($t22):INTEGER NOT NULL], expr#24=[/($t23, $t11)], expr#25=[/($t6, $t3)], expr#26=[CAST($t25):INTEGER NOT NULL], expr#27=[*($t6, $t6)], expr#28=[/($t27, $t3)], expr#29=[-($t7, $t28)], expr#30=[/($t29, $t19)], expr#31=[POWER($t30, $t21)], expr#32=[CAST($t31):INTEGER NOT NULL], expr#33=[/($t32, $t26)], expr#34=[/($t8, $t3)], expr#35=[CAST($t34):INTEGER NOT NULL], expr#36=[*($t8, $t8)], expr#37=[/($t36, $t3)], expr#38=[-($t9, $t37)], expr#39=[/($t38, $t19)], expr#40=[POWER($t39, $t21)], expr#41=[CAST($t40):INTEGER NOT NULL], expr#42=[/($t41, $t35)], proj#0..3=[{exprs}], STORE_SALES_QUANTITYAVE=[$t11], STORE_SALES_QUANTITYSTDEV=[$t23], STORE_SALES_QUANTITYCOV=[$t24], AS_STORE_RETURNS_QUANTITYCOUNT=[$t3], AS_STORE_RETURNS_QUANTITYAVE=[$t26], AS_STORE_RETURNS_QUANTITYSTDEV=[$t32], STORE_RETURNS_QUANTITYCOV=[$t33], CATALOG_SALES_QUANTITYCOUNT=[$t3], CATALOG_SALES_QUANTITYAVE=[$t35], CATALOG_SALES_QUANTITYSTDEV=[$t42], CATALOG_SALES_QUANTITYCOV=[$t42]): rowcount = 100.0, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableLimit(fetch=[100]): rowcount = 100.0, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$0], sort1=[$1], sort2=[$2], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 5.434029018852197E26, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableAggregate(group=[{0, 1, 2}], STORE_SALES_QUANTITYCOUNT=[COUNT()], agg#1=[$SUM0($3)], agg#2=[$SUM0($6)], agg#3=[$SUM0($4)], agg#4=[$SUM0($7)], agg#5=[$SUM0($5)], agg#6=[$SUM0($8)]): rowcount = 5.434029018852197E26, cumulative cost = {1.1886938478949211E28 rows, 1.2172225014174444E30 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..211=[{inputs}], expr#212=[*($t89, $t89)], expr#213=[*($t140, $t140)], expr#214=[*($t196, $t196)], I_ITEM_ID=[$t58], I_ITEM_DESC=[$t61], S_STATE=[$t24], SS_QUANTITY=[$t89], SR_RETURN_QUANTITY=[$t140], CS_QUANTITY=[$t196], $f6=[$t212], $f7=[$t213], $f8=[$t214]): rowcount = 5.434029018852197E27, cumulative cost = {1.0868058037914423E28 rows, 1.2172225014174444E30 cpu, 0.0 io}\n"
+ + " EnumerableMergeJoin(condition=[AND(=($82, $133), =($81, $132), =($88, $139))], joinType=[inner]): rowcount = 5.434029018852197E27, cumulative cost = {5.434029019062226E27 rows, 1.1945521881363807E21 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$82], sort1=[$81], sort2=[$88], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 2.3008402586892598E13, cumulative cost = {7.159725725974736E13 rows, 2.8882188423696301E17 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $86)], joinType=[inner]): rowcount = 2.3008402586892598E13, cumulative cost = {4.8588854672854766E13 rows, 7281360.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE]]): rowcount = 12.0, cumulative cost = {12.0 rows, 13.0 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $50)], joinType=[inner]): rowcount = 1.2782445881607E13, cumulative cost = {1.279800620431234E13 rows, 7281347.0 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], proj#0..27=[{exprs}], $condition=[$t29]): rowcount = 10957.35, cumulative cost = {84006.35 rows, 4382941.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $24)], joinType=[inner]): rowcount = 7.7770908E9, cumulative cost = {7.783045975286664E9 rows, 2898406.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, ITEM]]): rowcount = 18000.0, cumulative cost = {18000.0 rows, 18001.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE_SALES]]): rowcount = 2880404.0, cumulative cost = {2880404.0 rows, 2880405.0 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$30], sort2=[$37], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 6.9978029381741304E16, cumulative cost = {1.3995607297693488E17 rows, 1.1942633662521438E21 cpu, 0.0 io}\n"
+ + " EnumerableMergeJoin(condition=[AND(=($31, $79), =($30, $91))], joinType=[inner]): rowcount = 6.9978029381741304E16, cumulative cost = {6.9978043595193584E16 rows, 2.473747714463278E13 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$30], dir0=[ASC], dir1=[ASC]): rowcount = 7.87597881975E8, cumulative cost = {1.5760413031966867E9 rows, 3.097646138009654E12 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 7.87597881975E8, cumulative cost = {7.884434212216867E8 rows, 5035701.0 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE_RETURNS]]): rowcount = 287514.0, cumulative cost = {287514.0 rows, 287515.0 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$43], dir0=[ASC], dir1=[ASC]): rowcount = 3.94888649445E9, cumulative cost = {7.900926597146687E9 rows, 2.163983100662313E13 cpu, 0.0 io}\n"
Review comment:
The only changes is that some HashJoin is changed to MergeJoin. But as you can see from the cost, the new plan do have a lower cost.
(
old cost = 1.2435775409784036E28
VS
new cost = 1.2430341380834431E28
)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r454193127
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RuleDriver.java
##########
@@ -0,0 +1,53 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+
+/**
+ * A rule driver applies rules with designed algorithms
+ */
+interface RuleDriver {
+
+ /**
+ * gets the rule queue
+ */
Review comment:
Resolved. Thanks for the reminding.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rkondakov commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
rkondakov commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432933385
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java
##########
@@ -0,0 +1,812 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.rel.PhysicalNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Predicate;
+
+class TopDownRuleDriver {
+
+ /**
+ * the Logger
+ */
+ private static final Logger LOGGER = CalciteTrace.getPlannerTaskTracer();
+
+ /**
+ * The planner
+ */
+ private final VolcanoPlanner planner;
+
+ /**
+ * the rule queue designed for top-down rule applying
+ */
+ private final CascadeRuleQueue ruleQueue;
+
+ /**
+ * all tasks waiting for execution
+ */
+ private Stack<Task> tasks = new Stack<>();
+
+ /**
+ * A task that is currently applying and may generate new RelNode.
+ * It provides a callback to schedule tasks for new RelNodes that
+ * are registered during task performing
+ */
+ private GeneratorTask applying = null;
+
+ /**
+ * relnodes that are generated by passThrough or derive
+ * these nodes will not takes part in another passThrough or derive
+ */
+ private Set<Integer> passThroughCache = new HashSet<>();
+
+ //~ Constructors -----------------------------------------------------------
+
+ TopDownRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new CascadeRuleQueue(planner);
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ void execute() {
+ TaskDescriptor description = new TaskDescriptor();
+ tasks.push(new OptimizeGroup(planner.root, planner.infCost));
+ exploreMaterializationRoots();
+ while (!tasks.isEmpty()) {
+ Task task = tasks.pop();
+ description.log(task);
+ task.perform();
+ }
+ }
+
+ private void exploreMaterializationRoots() {
+ for (RelSubset extraRoot : planner.explorationRoots) {
+ RelSet rootSet = VolcanoPlanner.equivRoot(extraRoot.set);
+ if (rootSet == planner.root.set) {
+ continue;
+ }
+ for (RelNode rel : extraRoot.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, extraRoot, true));
+ }
+ }
+ }
+ }
+
+ public CascadeRuleQueue ruleQueue() {
+ return ruleQueue;
+ }
+
+ public void reset() {
+ ruleQueue.clear();
+ tasks.clear();
+ passThroughCache.clear();
+ applying = null;
+ }
+
+ private interface Procedure {
+ void exec();
+ }
+
+ private void applyGenerator(GeneratorTask task, Procedure proc) {
+ GeneratorTask applying = this.applying;
+ this.applying = task;
+ try {
+ proc.exec();
+ } finally {
+ this.applying = applying;
+ }
+ }
+
+ void onSetMerged(RelSet set) {
+ applyGenerator(null, () -> clearProcessed(set));
+ }
+
+ private void clearProcessed(RelSet set) {
+ boolean explored = set.exploringState != null;
+ set.exploringState = null;
+
+ for (RelSubset subset : set.subsets) {
+ if (subset.resetOptimizing() || explored) {
+ Collection<RelNode> parentRels = subset.getParentRels();
+ for (RelNode parentRel : parentRels) {
+ clearProcessed(planner.getSet(parentRel));
+ }
+ if (subset == planner.root) {
+ tasks.push(new OptimizeGroup(subset, planner.infCost));
Review comment:
If I understand right, when two sets merged together the optimization task will be restarted from the root, i.e. from the very beginning. Am I right? If so, shouldn't the tasks queue be cleaned in that case? Or have I missed something here?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451938459
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
##########
@@ -128,6 +129,16 @@
*/
private boolean enforceDisabled = false;
+ /**
+ * the upper bound of the last OptimizeGroup call
+ */
+ RelOptCost upperBound;
+
+ /**
+ * RelNode ids that is invoked passThrough method before
+ */
+ Set<RelNode> passThroughCache;
Review comment:
I see no differences. Currently, RelSet + Traits = RelSubset
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432252714
##########
File path: kafka/src/test/java/org/apache/calcite/adapter/kafka/KafkaAdapterTest.java
##########
@@ -73,6 +74,7 @@
@Test void testFilterWithProject() {
assertModel(MODEL)
+ .with(CalciteConnectionProperty.TOP_DOWN_OPT.camelName(), false)
Review comment:
skip using top-down optimization here. This case will produce another plan with the same cost as the expected plan
(Two candidates are both in the memo but the new best plan is produced first). But it will hang when executing the new plan. Still don't know why it hangs.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] zinking commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
zinking commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r448349666
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/IterativeRuleDriver.java
##########
@@ -0,0 +1,87 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+/***
+ * <p>The algorithm executes repeatedly in a series of phases. In each phase
+ * the exact rules that may be fired varies. The mapping of phases to rule
+ * sets is maintained in the {@link #ruleQueue}.
+ *
+ * <p>In each phase, the planner then iterates over the rule matches presented
+ * by the rule queue until the rule queue becomes empty.
+ */
+class IterativeRuleDriver implements RuleDriver {
+
+ private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
+
+ private final VolcanoPlanner planner;
+ private final VolcanoRuleQueue ruleQueue;
+
+ IterativeRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new VolcanoRuleQueue(planner);
+ }
+
+ @Override public VolcanoRuleQueue getRuleQueue() {
+ return ruleQueue;
+ }
+
+ @Override public void drive() {
+ PLANNING:
+ for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
+ while (true) {
+ LOGGER.debug("PLANNER = {}; PHASE = {}; COST = {}",
+ this, phase.toString(), planner.root.bestCost);
+
+ VolcanoRuleMatch match = ruleQueue.popMatch(phase);
+ if (match == null) {
+ break;
+ }
+
+ assert match.getRule().matches(match);
+ try {
+ match.onMatch();
+ } catch (VolcanoTimeoutException e) {
+ planner.canonize();
+ ruleQueue.phaseCompleted(phase);
+ break PLANNING;
Review comment:
does `call` drive recursively here yield the same semantic ?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436237723
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
##########
@@ -120,6 +121,16 @@
*/
boolean triggerRule = false;
+ /**
+ * the upper bound of the last OptimizeGroup call
+ */
+ RelOptCost upperBound;
+
+ /**
+ * RelNode ids that is invoked passThrough method before
+ */
+ Set<Integer> passThroughCache;
Review comment:
We can use RelNode here, instead of rel id, for debug-ability.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433596256
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
IMHO, if we ignore those plan changes every time we commit code, the code is more vulnerable to bugs. And it will be even harder to fix plan changes in the future as we don't know which and whose commit introduced the plan change.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Implement top-down rule applying and upper bound space pruning in calcite
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432251842
##########
File path: core/src/test/resources/sql/misc.iq
##########
@@ -378,14 +378,14 @@ where exists (select 1 from "hr"."emps" where "empid" < 0);
(0 rows)
!ok
-EnumerableCalc(expr#0..1=[{inputs}], deptno=[$t0])
+EnumerableCalc(expr#0..1=[{inputs}], deptno=[$t1])
EnumerableNestedLoopJoin(condition=[true], joinType=[inner])
Review comment:
Some join factors are swapped because when rule applying order changes, the id of join factors also changed. And EnumerableNestedLoopJoin has a special handling that it prefers left branch having a lower id than the right branch.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Implement top-down rule applying and upper bound space pruning in calcite
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432662059
##########
File path: kafka/src/test/java/org/apache/calcite/adapter/kafka/KafkaAdapterTest.java
##########
@@ -73,6 +74,7 @@
@Test void testFilterWithProject() {
assertModel(MODEL)
+ .with(CalciteConnectionProperty.TOP_DOWN_OPT.camelName(), false)
Review comment:
@XuQianJin-Stars Do you have any insight?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438567550
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
##########
@@ -16,349 +16,18 @@
*/
package org.apache.calcite.plan.volcano;
-import org.apache.calcite.plan.RelOptRuleOperand;
-import org.apache.calcite.rel.RelNode;
-import org.apache.calcite.rel.rules.SubstitutionRule;
-import org.apache.calcite.util.Util;
-import org.apache.calcite.util.trace.CalciteTrace;
-
-import com.google.common.collect.HashMultimap;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Multimap;
-
-import org.slf4j.Logger;
-
-import java.io.PrintWriter;
-import java.io.StringWriter;
-import java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.EnumMap;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Set;
-
-/**
- * Priority queue of relexps whose rules have not been called, and rule-matches
- * which have not yet been acted upon.
- */
-class RuleQueue {
- //~ Static fields/initializers ---------------------------------------------
-
- private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
-
- private static final Set<String> ALL_RULES = ImmutableSet.of("<ALL RULES>");
-
- //~ Instance fields --------------------------------------------------------
-
- /**
- * Map of {@link VolcanoPlannerPhase} to a list of rule-matches. Initially,
- * there is an empty {@link PhaseMatchList} for each planner phase. As the
- * planner invokes {@link #addMatch(VolcanoRuleMatch)} the rule-match is
- * added to the appropriate PhaseMatchList(s). As the planner completes
- * phases, the matching entry is removed from this list to avoid unused
- * work.
- */
- final Map<VolcanoPlannerPhase, PhaseMatchList> matchListMap =
- new EnumMap<>(VolcanoPlannerPhase.class);
-
- private final VolcanoPlanner planner;
-
- /**
- * Maps a {@link VolcanoPlannerPhase} to a set of rule descriptions. Named rules
- * may be invoked in their corresponding phase.
- *
- * <p>See {@link VolcanoPlannerPhaseRuleMappingInitializer} for more
- * information regarding the contents of this Map and how it is initialized.
- */
- private final Map<VolcanoPlannerPhase, Set<String>> phaseRuleMapping;
-
- //~ Constructors -----------------------------------------------------------
-
- RuleQueue(VolcanoPlanner planner) {
- this.planner = planner;
-
- phaseRuleMapping = new EnumMap<>(VolcanoPlannerPhase.class);
-
- // init empty sets for all phases
- for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
- phaseRuleMapping.put(phase, new HashSet<>());
- }
-
- // configure phases
- planner.getPhaseRuleMappingInitializer().initialize(phaseRuleMapping);
-
- for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
- // empty phases get converted to "all rules"
- if (phaseRuleMapping.get(phase).isEmpty()) {
- phaseRuleMapping.put(phase, ALL_RULES);
- }
-
- // create a match list data structure for each phase
- PhaseMatchList matchList = new PhaseMatchList(phase);
-
- matchListMap.put(phase, matchList);
- }
- }
-
- //~ Methods ----------------------------------------------------------------
- /**
- * Clear internal data structure for this rule queue.
- */
- public void clear() {
- for (PhaseMatchList matchList : matchListMap.values()) {
- matchList.clear();
- }
- }
+public interface RuleQueue {
Review comment:
resolved
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/MultiPhasedRuleDriver.java
##########
@@ -0,0 +1,87 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+/***
+ * <p>The algorithm executes repeatedly in a series of phases. In each phase
+ * the exact rules that may be fired varies. The mapping of phases to rule
+ * sets is maintained in the {@link #ruleQueue}.
+ *
+ * <p>In each phase, the planner then iterates over the rule matches presented
+ * by the rule queue until the rule queue becomes empty.
+ */
+public class MultiPhasedRuleDriver implements RuleDriver {
Review comment:
resolved
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
Review comment:
resolved
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] chunweilei commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
chunweilei commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450073082
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
##########
@@ -128,6 +129,16 @@
*/
private boolean enforceDisabled = false;
+ /**
+ * the upper bound of the last OptimizeGroup call
+ */
+ RelOptCost upperBound;
+
+ /**
+ * RelNode ids that is invoked passThrough method before
+ */
+ Set<RelNode> passThroughCache;
Review comment:
Correct the comment too~
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r454111363
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
##########
@@ -18,224 +18,41 @@
import org.apache.calcite.plan.RelOptRuleOperand;
import org.apache.calcite.rel.RelNode;
-import org.apache.calcite.rel.rules.SubstitutionRule;
import org.apache.calcite.util.Util;
-import org.apache.calcite.util.trace.CalciteTrace;
-import com.google.common.collect.HashMultimap;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Multimap;
-
-import org.slf4j.Logger;
-
-import java.io.PrintWriter;
-import java.io.StringWriter;
import java.util.ArrayDeque;
import java.util.Deque;
-import java.util.EnumMap;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Set;
/**
- * Priority queue of relexps whose rules have not been called, and rule-matches
- * which have not yet been acted upon.
+ * A data structure that manages rule matches for RuleDriver.
+ * Different RuleDriver requires different ways to pop matches,
+ * thus different ways to store rule matches that are not called.
*/
-class RuleQueue {
- //~ Static fields/initializers ---------------------------------------------
-
- private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
-
- private static final Set<String> ALL_RULES = ImmutableSet.of("<ALL RULES>");
-
- //~ Instance fields --------------------------------------------------------
-
- /**
- * Map of {@link VolcanoPlannerPhase} to a list of rule-matches. Initially,
- * there is an empty {@link PhaseMatchList} for each planner phase. As the
- * planner invokes {@link #addMatch(VolcanoRuleMatch)} the rule-match is
- * added to the appropriate PhaseMatchList(s). As the planner completes
- * phases, the matching entry is removed from this list to avoid unused
- * work.
- */
- final Map<VolcanoPlannerPhase, PhaseMatchList> matchListMap =
- new EnumMap<>(VolcanoPlannerPhase.class);
-
- private final VolcanoPlanner planner;
-
- /**
- * Maps a {@link VolcanoPlannerPhase} to a set of rule descriptions. Named rules
- * may be invoked in their corresponding phase.
- *
- * <p>See {@link VolcanoPlannerPhaseRuleMappingInitializer} for more
- * information regarding the contents of this Map and how it is initialized.
- */
- private final Map<VolcanoPlannerPhase, Set<String>> phaseRuleMapping;
+public abstract class RuleQueue {
Review comment:
resolved
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#issuecomment-657939592
Yes, doing the final round review
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Implement top-down rule applying and upper bound space pruning in calcite
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432250507
##########
File path: core/src/main/java/org/apache/calcite/tools/Programs.java
##########
@@ -266,15 +266,14 @@ public static Program standard() {
public static Program standard(RelMetadataProvider metadataProvider) {
final Program program1 =
(planner, rel, requiredOutputTraits, materializations, lattices) -> {
- planner.setRoot(rel);
Review comment:
Setting root before addMaterialization will make MaterializedViewRule always fail to match
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436253879
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
##########
@@ -120,6 +121,16 @@
*/
boolean triggerRule = false;
+ /**
+ * the upper bound of the last OptimizeGroup call
+ */
+ RelOptCost upperBound;
+
+ /**
+ * RelNode ids that is invoked passThrough method before
+ */
+ Set<Integer> passThroughCache;
Review comment:
Good Point. Will resolve it.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438510170
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/CascadeRuleQueue.java
##########
@@ -0,0 +1,94 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.Pair;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * A rule queue that manage rule matches for cascade planner
+ */
+public class CascadeRuleQueue implements RuleQueue {
Review comment:
The origin cascades planner fire rules by required. But in this design, rules are fired during registering and executed by required.
We are trying to use on-demand rule firing. But it requires more controls to avoid miss-trigger or re-trigger rules. Related works are still under testings
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438511030
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
Review comment:
Oops, it's my typo. I should use planner.isLogic instead of a new method here. planner.isLogic is supposed to be overwritten by users.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438510295
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
##########
@@ -16,349 +16,18 @@
*/
package org.apache.calcite.plan.volcano;
-import org.apache.calcite.plan.RelOptRuleOperand;
-import org.apache.calcite.rel.RelNode;
-import org.apache.calcite.rel.rules.SubstitutionRule;
-import org.apache.calcite.util.Util;
-import org.apache.calcite.util.trace.CalciteTrace;
-
-import com.google.common.collect.HashMultimap;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Multimap;
-
-import org.slf4j.Logger;
-
-import java.io.PrintWriter;
-import java.io.StringWriter;
-import java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.EnumMap;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Set;
-
-/**
- * Priority queue of relexps whose rules have not been called, and rule-matches
- * which have not yet been acted upon.
- */
-class RuleQueue {
- //~ Static fields/initializers ---------------------------------------------
-
- private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
-
- private static final Set<String> ALL_RULES = ImmutableSet.of("<ALL RULES>");
-
- //~ Instance fields --------------------------------------------------------
-
- /**
- * Map of {@link VolcanoPlannerPhase} to a list of rule-matches. Initially,
- * there is an empty {@link PhaseMatchList} for each planner phase. As the
- * planner invokes {@link #addMatch(VolcanoRuleMatch)} the rule-match is
- * added to the appropriate PhaseMatchList(s). As the planner completes
- * phases, the matching entry is removed from this list to avoid unused
- * work.
- */
- final Map<VolcanoPlannerPhase, PhaseMatchList> matchListMap =
- new EnumMap<>(VolcanoPlannerPhase.class);
-
- private final VolcanoPlanner planner;
-
- /**
- * Maps a {@link VolcanoPlannerPhase} to a set of rule descriptions. Named rules
- * may be invoked in their corresponding phase.
- *
- * <p>See {@link VolcanoPlannerPhaseRuleMappingInitializer} for more
- * information regarding the contents of this Map and how it is initialized.
- */
- private final Map<VolcanoPlannerPhase, Set<String>> phaseRuleMapping;
-
- //~ Constructors -----------------------------------------------------------
-
- RuleQueue(VolcanoPlanner planner) {
- this.planner = planner;
-
- phaseRuleMapping = new EnumMap<>(VolcanoPlannerPhase.class);
-
- // init empty sets for all phases
- for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
- phaseRuleMapping.put(phase, new HashSet<>());
- }
-
- // configure phases
- planner.getPhaseRuleMappingInitializer().initialize(phaseRuleMapping);
-
- for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
- // empty phases get converted to "all rules"
- if (phaseRuleMapping.get(phase).isEmpty()) {
- phaseRuleMapping.put(phase, ALL_RULES);
- }
-
- // create a match list data structure for each phase
- PhaseMatchList matchList = new PhaseMatchList(phase);
-
- matchListMap.put(phase, matchList);
- }
- }
-
- //~ Methods ----------------------------------------------------------------
- /**
- * Clear internal data structure for this rule queue.
- */
- public void clear() {
- for (PhaseMatchList matchList : matchListMap.values()) {
- matchList.clear();
- }
- }
+public interface RuleQueue {
Review comment:
OK
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450589184
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
##########
@@ -128,6 +129,16 @@
*/
private boolean enforceDisabled = false;
+ /**
+ * the upper bound of the last OptimizeGroup call
+ */
+ RelOptCost upperBound;
+
+ /**
+ * RelNode ids that is invoked passThrough method before
+ */
+ Set<RelNode> passThroughCache;
Review comment:
Resolved
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432936019
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
you are right. Thanks for the reminding
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r452103479
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
+ }
+
+ public RelOptCost getLowerBoundCost(RelSubset subset,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+
+ if (isLogical(subset)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost winner = subset.getWinnerCost();
+ if (winner != null) {
+ // when this subset is fully optimized, just return the winner
+ return winner;
+ }
+
+ // if group is not fully explored. Its properties like cardinality
+ // would get changed after exploration. So it cannot return a valid LB
+ if (!subset.isExplored()) {
+ return null;
+ }
+
+ RelOptCost lowerBound = null;
+ for (RelNode relNode : subset.getRels()) {
+ try {
+ RelOptCost lb = mq.getLowerBoundCost(relNode, planner);
+ if (lb == null) {
+ return null;
+ }
+ if (lowerBound == null || lb.isLt(lowerBound)) {
+ lowerBound = lb;
+ }
+ } catch (CyclicMetadataException e) {
+ if (lowerBound == null) {
+ // a cyclic metadata query means this node has an INF LB
+ lowerBound = planner.getCostFactory().makeInfiniteCost();
+ }
+ }
+ }
+ return lowerBound;
+ }
+
+ public RelOptCost getLowerBoundCost(RelNode node,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ if (isLogical(node)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost selfCost = node.computeSelfCost(planner, mq);
+ if (selfCost.isInfinite()) {
+ selfCost = null;
+ }
+ for (RelNode input : node.getInputs()) {
+ RelOptCost lb = mq.getLowerBoundCost(input, planner);
+ if (lb != null) {
+ selfCost = selfCost == null ? lb : selfCost.plus(lb);
+ }
+ }
+ return selfCost;
+ }
+
+ public RelOptCost getLowerBoundCost(AbstractConverter ac,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ return mq.getLowerBoundCost(ac.getInput(), planner);
Review comment:
resolved
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436255565
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
##########
@@ -317,8 +284,8 @@ RelSubset getOrCreateSubset(
subset.setDelivered();
}
- if (needsConverter && !planner.topDownOpt) {
- addConverters(subset, required, true);
+ if (needsConverter) {
+ addConverters(subset, required, !planner.topDownOpt);
Review comment:
Yes, it is. There are reasons for adding converters eagerly:
1. The converters act as bridges between the working subset and other subsets. Currently, the OptimizeGroup task will schedule tasks for all the logical Rels in the RelSet while it skips physical Rels from other subsets. That's because we are confident that if other subset can be reached by a converter, the converter is already in the current working subset.
2. In tasks other than OptimizeGroup, when new physical Rels are added to the RelSet, the insertion of the converter is a signal for RuleDriver to schedule the optimizing tasks for the previous working subset.
3. The computation of lower bound requires the memo to be connected.
Maybe there are some other ways to achieve all this, but I cannot find a more pretty way now. I was thinking of checking the upper bound before adding the enforcer. But I cannot decide which place is suitable for adding the enforcer back when the upper bound is changed. So I leave it for further optimizations.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433108270
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteSystemProperty.java
##########
@@ -124,12 +124,21 @@
/**
* Whether to enable top-down optimization.
*
- * <p>Note: Enabling top-down optimization will automatically disable
- * the use of AbstractConverter and related rules.</p>
+ * <p>Note: Enabling top-down optimization will automatically enable
+ * top-down trait propagation.</p>
*/
public static final CalciteSystemProperty<Boolean> TOPDOWN_OPT =
booleanProperty("calcite.planner.topdown.opt", false);
+ /**
+ * Whether to enable top-down trait propagation.
+ *
+ * <p>Note: Enabling top-down optimization will automatically disable
+ * the use of AbstractConverter and related rules.</p>
+ */
+ public static final CalciteSystemProperty<Boolean> TOPDOWN_TRAITS =
+ booleanProperty("calcite.planner.topdown.traits", false);
Review comment:
Discussed with Haisheng, I will remove this flag and combine all top-down optimization capability together.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436254672
##########
File path: core/src/test/java/org/apache/calcite/test/JdbcAdapterTest.java
##########
@@ -179,6 +180,7 @@
@Test void testPushDownSort() {
CalciteAssert.model(JdbcTest.SCOTT_MODEL)
+ .with(CalciteConnectionProperty.TOPDOWN_OPT.camelName(), false)
Review comment:
In this case, the new planner is producing a plan with exactly the same cost.
However, the new plan will affect later tests' assertion. I didn't want to modified so many of them. So I added this line instead of modifying the expects.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438511633
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
+ }
+
+ public RelOptCost getLowerBoundCost(RelSubset subset,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+
+ if (isLogical(subset)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost winner = subset.getWinnerCost();
+ if (winner != null) {
+ // when this subset is fully optimized, just return the winner
+ return winner;
+ }
+
+ // if group is not fully explored. Its properties like cardinality
+ // would get changed after exploration. So it cannot return a valid LB
+ if (!subset.isExplored()) {
+ return null;
+ }
+
+ RelOptCost lowerBound = null;
+ for (RelNode relNode : subset.getRels()) {
+ try {
+ RelOptCost lb = mq.getLowerBoundCost(relNode, planner);
+ if (lb == null) {
+ return null;
+ }
+ if (lowerBound == null || lb.isLt(lowerBound)) {
+ lowerBound = lb;
+ }
+ } catch (CyclicMetadataException e) {
+ if (lowerBound == null) {
+ // a cyclic metadata query means this node has an INF LB
+ lowerBound = planner.getCostFactory().makeInfiniteCost();
+ }
+ }
+ }
+ return lowerBound;
+ }
+
+ public RelOptCost getLowerBoundCost(RelNode node,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ if (isLogical(node)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost selfCost = node.computeSelfCost(planner, mq);
+ if (selfCost.isInfinite()) {
+ selfCost = null;
+ }
+ for (RelNode input : node.getInputs()) {
+ RelOptCost lb = mq.getLowerBoundCost(input, planner);
+ if (lb != null) {
+ selfCost = selfCost == null ? lb : selfCost.plus(lb);
+ }
+ }
+ return selfCost;
+ }
+
+ public RelOptCost getLowerBoundCost(AbstractConverter ac,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ return mq.getLowerBoundCost(ac.getInput(), planner);
Review comment:
Currently it is not possible to have AC here. But as a metadata handler，I tried to make its logic as complete as possible.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433604692
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
In fact, I think Haisheng was thinking that allows each test has two expected plans: one for top-down opt, and another for old planner.
I think what you are saying is to make Volcano planner be fully compatible with top-down optimization. I think people were discussing whether there should be a new planner, or using existing Volcano planner to develop this top-down optimization. I actually don't know if there was already an agreement of it or not.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436221571
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
Review comment:
It doesn't looks like suitable for metadata. Why not just integrate it with planner, and let it overridable?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433045296
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
@amaliujia, I noticed that in #1985, default value of calcite.planner.topdown.opt has been changed to "false". Why we need this change?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436237623
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
##########
@@ -317,8 +284,8 @@ RelSubset getOrCreateSubset(
subset.setDelivered();
}
- if (needsConverter && !planner.topDownOpt) {
- addConverters(subset, required, true);
+ if (needsConverter) {
+ addConverters(subset, required, !planner.topDownOpt);
Review comment:
hmm, that means whenever a new traitset is added, it will always add the enforcer if needed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r454069324
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
##########
@@ -18,224 +18,41 @@
import org.apache.calcite.plan.RelOptRuleOperand;
import org.apache.calcite.rel.RelNode;
-import org.apache.calcite.rel.rules.SubstitutionRule;
import org.apache.calcite.util.Util;
-import org.apache.calcite.util.trace.CalciteTrace;
-import com.google.common.collect.HashMultimap;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Multimap;
-
-import org.slf4j.Logger;
-
-import java.io.PrintWriter;
-import java.io.StringWriter;
import java.util.ArrayDeque;
import java.util.Deque;
-import java.util.EnumMap;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Set;
/**
- * Priority queue of relexps whose rules have not been called, and rule-matches
- * which have not yet been acted upon.
+ * A data structure that manages rule matches for RuleDriver.
+ * Different RuleDriver requires different ways to pop matches,
+ * thus different ways to store rule matches that are not called.
*/
-class RuleQueue {
- //~ Static fields/initializers ---------------------------------------------
-
- private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
-
- private static final Set<String> ALL_RULES = ImmutableSet.of("<ALL RULES>");
-
- //~ Instance fields --------------------------------------------------------
-
- /**
- * Map of {@link VolcanoPlannerPhase} to a list of rule-matches. Initially,
- * there is an empty {@link PhaseMatchList} for each planner phase. As the
- * planner invokes {@link #addMatch(VolcanoRuleMatch)} the rule-match is
- * added to the appropriate PhaseMatchList(s). As the planner completes
- * phases, the matching entry is removed from this list to avoid unused
- * work.
- */
- final Map<VolcanoPlannerPhase, PhaseMatchList> matchListMap =
- new EnumMap<>(VolcanoPlannerPhase.class);
-
- private final VolcanoPlanner planner;
-
- /**
- * Maps a {@link VolcanoPlannerPhase} to a set of rule descriptions. Named rules
- * may be invoked in their corresponding phase.
- *
- * <p>See {@link VolcanoPlannerPhaseRuleMappingInitializer} for more
- * information regarding the contents of this Map and how it is initialized.
- */
- private final Map<VolcanoPlannerPhase, Set<String>> phaseRuleMapping;
+public abstract class RuleQueue {
Review comment:
remove public
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] danny0405 commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
danny0405 commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r454158975
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RuleDriver.java
##########
@@ -0,0 +1,53 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+
+/**
+ * A rule driver applies rules with designed algorithms
+ */
+interface RuleDriver {
+
+ /**
+ * gets the rule queue
+ */
Review comment:
All the comments should start with upper case character and end with dot.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450588879
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/IterativeRuleDriver.java
##########
@@ -0,0 +1,87 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+/***
+ * <p>The algorithm executes repeatedly in a series of phases. In each phase
+ * the exact rules that may be fired varies. The mapping of phases to rule
+ * sets is maintained in the {@link #ruleQueue}.
+ *
+ * <p>In each phase, the planner then iterates over the rule matches presented
+ * by the rule queue until the rule queue becomes empty.
+ */
+class IterativeRuleDriver implements RuleDriver {
+
+ private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
+
+ private final VolcanoPlanner planner;
+ private final VolcanoRuleQueue ruleQueue;
+
+ IterativeRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new VolcanoRuleQueue(planner);
+ }
+
+ @Override public VolcanoRuleQueue getRuleQueue() {
+ return ruleQueue;
+ }
+
+ @Override public void drive() {
+ PLANNING:
+ for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
+ while (true) {
+ LOGGER.debug("PLANNER = {}; PHASE = {}; COST = {}",
+ this, phase.toString(), planner.root.bestCost);
+
+ VolcanoRuleMatch match = ruleQueue.popMatch(phase);
+ if (match == null) {
+ break;
+ }
+
+ assert match.getRule().matches(match);
+ try {
+ match.onMatch();
+ } catch (VolcanoTimeoutException e) {
+ planner.canonize();
+ ruleQueue.phaseCompleted(phase);
+ break PLANNING;
Review comment:
this code is completely copied from previous findBestExpr method
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451787388
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/CascadesRuleQueue.java
##########
@@ -0,0 +1,90 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.Pair;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * A rule queue that manage rule matches for cascade planner
+ */
+public class CascadesRuleQueue implements RuleQueue {
+
+ private final VolcanoPlanner planner;
+
+ private final Map<Integer, List<VolcanoRuleMatch>> matches = new HashMap<>();
Review comment:
用IdentityHashMap, 可以用RelNode作为Key
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451787388
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/CascadesRuleQueue.java
##########
@@ -0,0 +1,90 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.Pair;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * A rule queue that manage rule matches for cascade planner
+ */
+public class CascadesRuleQueue implements RuleQueue {
+
+ private final VolcanoPlanner planner;
+
+ private final Map<Integer, List<VolcanoRuleMatch>> matches = new HashMap<>();
Review comment:
UseIdentityHashMap, the key can be RelNode.
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/CascadesRuleQueue.java
##########
@@ -0,0 +1,90 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.Pair;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * A rule queue that manage rule matches for cascade planner
+ */
+public class CascadesRuleQueue implements RuleQueue {
+
+ private final VolcanoPlanner planner;
+
+ private final Map<Integer, List<VolcanoRuleMatch>> matches = new HashMap<>();
Review comment:
Use IdentityHashMap, the key can be RelNode.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] chunweilei commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
chunweilei commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450077922
##########
File path: core/src/test/resources/sql/agg.iq
##########
@@ -2290,9 +2290,9 @@ select MGR, count(distinct DEPTNO, JOB), MIN(SAL), MAX(SAL) from "scott".emp gro
!ok
-EnumerableAggregate(group=[{0}], EXPR$1=[COUNT($1, $2) FILTER $5], EXPR$2=[MIN($3) FILTER $6], EXPR$3=[MIN($4) FILTER $6])
- EnumerableCalc(expr#0..5=[{inputs}], expr#6=[0], expr#7=[=($t5, $t6)], expr#8=[3], expr#9=[=($t5, $t8)], MGR=[$t1], DEPTNO=[$t2], JOB=[$t0], EXPR$2=[$t3], EXPR$3=[$t4], $g_0=[$t7], $g_3=[$t9])
- EnumerableAggregate(group=[{2, 3, 7}], groups=[[{2, 3, 7}, {3}]], EXPR$2=[MIN($5)], EXPR$3=[MAX($5)], $g=[GROUPING($3, $7, $2)])
+EnumerableAggregate(group=[{1}], EXPR$1=[COUNT($2, $0) FILTER $5], EXPR$2=[MIN($3) FILTER $6], EXPR$3=[MIN($4) FILTER $6])
+ EnumerableCalc(expr#0..5=[{inputs}], expr#6=[0], expr#7=[=($t5, $t6)], expr#8=[5], expr#9=[=($t5, $t8)], proj#0..4=[{exprs}], $g_0=[$t7], $g_5=[$t9])
+ EnumerableAggregate(group=[{2, 3, 7}], groups=[[{2, 3, 7}, {3}]], EXPR$2=[MIN($5)], EXPR$3=[MAX($5)], $g=[GROUPING($2, $3, $7)])
EnumerableTableScan(table=[[scott, EMP]])
Review comment:
Is the change expected?
##########
File path: cassandra/src/test/java/org/apache/calcite/test/CassandraAdapterTest.java
##########
@@ -100,8 +100,8 @@ static void load(Session session) {
.returns("tweet_id=f3c329de-d05b-11e5-b58b-90e2ba530b12\n"
+ "tweet_id=f3dbb03a-d05b-11e5-b58b-90e2ba530b12\n")
.explainContains("PLAN=CassandraToEnumerableConverter\n"
- + " CassandraLimit(fetch=[2])\n"
- + " CassandraProject(tweet_id=[$2])\n"
+ + " CassandraProject(tweet_id=[$2])\n"
+ + " CassandraLimit(fetch=[2])\n"
+ " CassandraFilter(condition=[=($0, '!PUBLIC!')])\n");
}
Review comment:
Does the same cost lead to the change?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
amaliujia commented on pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#issuecomment-658413251
Awesome thanks!
Ah I took the first class of CMU 15721 when I was a master student there but I didn't remember Columbia was covered.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451810231
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
##########
@@ -128,6 +129,16 @@
*/
private boolean enforceDisabled = false;
+ /**
+ * the upper bound of the last OptimizeGroup call
+ */
+ RelOptCost upperBound;
+
+ /**
+ * RelNode ids that is invoked passThrough method before
+ */
+ Set<RelNode> passThroughCache;
Review comment:
Hmm. I think it is better to store the passThroughCache to RelSet, where the key is the traitset, the value are relnodes.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Implement top-down rule applying and upper bound space pruning in calcite
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432252714
##########
File path: kafka/src/test/java/org/apache/calcite/adapter/kafka/KafkaAdapterTest.java
##########
@@ -73,6 +74,7 @@
@Test void testFilterWithProject() {
assertModel(MODEL)
+ .with(CalciteConnectionProperty.TOP_DOWN_OPT.camelName(), false)
Review comment:
skip using top-down optimization here. This case will produce another plan with the same cost with the expect plan
(two candidates are both in the memo) but it will hang when executing the new plan. Still don't know why it hangs.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450588566
##########
File path: cassandra/src/test/java/org/apache/calcite/test/CassandraAdapterTest.java
##########
@@ -100,8 +100,8 @@ static void load(Session session) {
.returns("tweet_id=f3c329de-d05b-11e5-b58b-90e2ba530b12\n"
+ "tweet_id=f3dbb03a-d05b-11e5-b58b-90e2ba530b12\n")
.explainContains("PLAN=CassandraToEnumerableConverter\n"
- + " CassandraLimit(fetch=[2])\n"
- + " CassandraProject(tweet_id=[$2])\n"
+ + " CassandraProject(tweet_id=[$2])\n"
+ + " CassandraLimit(fetch=[2])\n"
+ " CassandraFilter(condition=[=($0, '!PUBLIC!')])\n");
}
Review comment:
yes, the have the same cost. However, I do think in most case the new plan is better.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450641237
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,112 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.plan.volcano.VolcanoPlanner;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ public RelOptCost getLowerBoundCost(RelSubset subset,
+ RelMetadataQuery mq, VolcanoPlanner planner) {
+
+ if (planner.isLogical(subset)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost winner = subset.getWinnerCost();
+ if (winner != null) {
+ // when this subset is fully optimized, just return the winner
+ return winner;
+ }
+
+ // if group is not fully explored. Its properties like cardinality
+ // would get changed after exploration. So it cannot return a valid LB
+ if (!subset.isExplored()) {
+ return null;
+ }
+
+ RelOptCost lowerBound = null;
Review comment:
You‘re right. If any logical node in the same RelSet is not built, looking for the lower bound of current RelSubset's member is not valid. Will remove this logic
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451935590
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
Review comment:
After CALCITE-2018 is resolved, I think the invalidation of metadata could be removed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433407687
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
Yes, Like what Haisheng said, enable top-down opt will generate different plans for existing tests. As we still under fast development for top-down opt, we thought it could be good to disable it globally for now. We will tackle those affected tests before fully enable top-down opt.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r454148508
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/IterativeRuleDriver.java
##########
@@ -0,0 +1,87 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+/***
+ * <p>The algorithm executes repeatedly in a series of phases. In each phase
+ * the exact rules that may be fired varies. The mapping of phases to rule
+ * sets is maintained in the {@link #ruleQueue}.
+ *
+ * <p>In each phase, the planner then iterates over the rule matches presented
+ * by the rule queue until the rule queue becomes empty.
+ */
+class IterativeRuleDriver implements RuleDriver {
+
+ private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
+
+ private final VolcanoPlanner planner;
+ private final VolcanoRuleQueue ruleQueue;
+
+ IterativeRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new VolcanoRuleQueue(planner);
+ }
+
+ @Override public VolcanoRuleQueue getRuleQueue() {
+ return ruleQueue;
+ }
+
+ @Override public void drive() {
+ PLANNING:
+ for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
+ while (true) {
+ LOGGER.debug("PLANNER = {}; PHASE = {}; COST = {}",
+ this, phase.toString(), planner.root.bestCost);
+
+ VolcanoRuleMatch match = ruleQueue.popMatch(phase);
+ if (match == null) {
+ break;
+ }
+
+ assert match.getRule().matches(match);
+ try {
+ match.onMatch();
+ } catch (VolcanoTimeoutException e) {
+ planner.canonize();
+ ruleQueue.phaseCompleted(phase);
+ break PLANNING;
Review comment:
@zinking `break PLANNING;` here means step out of the for loop. It is not a recursive call.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438392066
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/CascadeRuleQueue.java
##########
@@ -0,0 +1,94 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.Pair;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * A rule queue that manage rule matches for cascade planner
+ */
+public class CascadeRuleQueue implements RuleQueue {
Review comment:
Why do we need a rule queue for top-down? Can't it just execute after matching?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433051546
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java
##########
@@ -0,0 +1,812 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.rel.PhysicalNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Predicate;
+
+class TopDownRuleDriver {
+
+ /**
+ * the Logger
+ */
+ private static final Logger LOGGER = CalciteTrace.getPlannerTaskTracer();
+
+ /**
+ * The planner
+ */
+ private final VolcanoPlanner planner;
+
+ /**
+ * the rule queue designed for top-down rule applying
+ */
+ private final CascadeRuleQueue ruleQueue;
+
+ /**
+ * all tasks waiting for execution
+ */
+ private Stack<Task> tasks = new Stack<>();
+
+ /**
+ * A task that is currently applying and may generate new RelNode.
+ * It provides a callback to schedule tasks for new RelNodes that
+ * are registered during task performing
+ */
+ private GeneratorTask applying = null;
+
+ /**
+ * relnodes that are generated by passThrough or derive
+ * these nodes will not takes part in another passThrough or derive
+ */
+ private Set<Integer> passThroughCache = new HashSet<>();
+
+ //~ Constructors -----------------------------------------------------------
+
+ TopDownRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new CascadeRuleQueue(planner);
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ void execute() {
+ TaskDescriptor description = new TaskDescriptor();
+ tasks.push(new OptimizeGroup(planner.root, planner.infCost));
+ exploreMaterializationRoots();
+ while (!tasks.isEmpty()) {
+ Task task = tasks.pop();
+ description.log(task);
+ task.perform();
+ }
+ }
+
+ private void exploreMaterializationRoots() {
+ for (RelSubset extraRoot : planner.explorationRoots) {
+ RelSet rootSet = VolcanoPlanner.equivRoot(extraRoot.set);
+ if (rootSet == planner.root.set) {
+ continue;
+ }
+ for (RelNode rel : extraRoot.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, extraRoot, true));
+ }
+ }
+ }
+ }
+
+ public CascadeRuleQueue ruleQueue() {
+ return ruleQueue;
+ }
+
+ public void reset() {
+ ruleQueue.clear();
+ tasks.clear();
+ passThroughCache.clear();
+ applying = null;
+ }
+
+ private interface Procedure {
+ void exec();
+ }
+
+ private void applyGenerator(GeneratorTask task, Procedure proc) {
+ GeneratorTask applying = this.applying;
+ this.applying = task;
+ try {
+ proc.exec();
+ } finally {
+ this.applying = applying;
+ }
+ }
+
+ void onSetMerged(RelSet set) {
+ applyGenerator(null, () -> clearProcessed(set));
+ }
+
+ private void clearProcessed(RelSet set) {
+ boolean explored = set.exploringState != null;
+ set.exploringState = null;
+
+ for (RelSubset subset : set.subsets) {
+ if (subset.resetOptimizing() || explored) {
+ Collection<RelNode> parentRels = subset.getParentRels();
+ for (RelNode parentRel : parentRels) {
+ clearProcessed(planner.getSet(parentRel));
+ }
+ if (subset == planner.root) {
+ tasks.push(new OptimizeGroup(subset, planner.infCost));
Review comment:
Task queue cannot be cleared here, because the RuleMatch is already popped from rule queue during ApplyRules. So ApplyRule tasks in the queue cannot be reproduced after cleaning.
The newly added task may rescan the root RelSet and schedule tasks for new relnodes. Duplicate tasks can be avoided as input RelSubsets still hold the previous optimizing status.
The only problem is that it may affect the rule applying sequence.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436236838
##########
File path: core/src/test/java/org/apache/calcite/test/JdbcAdapterTest.java
##########
@@ -179,6 +180,7 @@
@Test void testPushDownSort() {
CalciteAssert.model(JdbcTest.SCOTT_MODEL)
+ .with(CalciteConnectionProperty.TOPDOWN_OPT.camelName(), false)
Review comment:
why do we need this?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436255565
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
##########
@@ -317,8 +284,8 @@ RelSubset getOrCreateSubset(
subset.setDelivered();
}
- if (needsConverter && !planner.topDownOpt) {
- addConverters(subset, required, true);
+ if (needsConverter) {
+ addConverters(subset, required, !planner.topDownOpt);
Review comment:
Yes, it is. The converters act as bridges between the working subset and other subset. Currently, the OptimizeGroup task will schedule tasks for all the logical Rels in the RelSet while it skips physical Rels from other subsets. That's because we are confident that if a physical rel can be reach by a converter, the converter is already in the current working subset.
I was thinking of checking the upper bound before adding the enforcer. But I cannot decide which place is suitable for adding the enforcer back when the upper bound is changed. So I leave it for further optimizations.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
amaliujia commented on pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#issuecomment-658408913
@FatLittle thanks for your contribution.
> related to #1950
>
> 1. Introduce Top-Down rule applying strategy in VolcanoPlanner
> 2. Implement tasks and state transformations according to the design of Columnbia
Do you have a link to point to the design of Columnbia?
> 3. Introduce a LowerBoundCost metadata to compute lower bound and used for pruning
> 4. Using a flag to control whether to use new strategy or not
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan closed pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan closed pull request #1991:
URL: https://github.com/apache/calcite/pull/1991
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432883073
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
I think you need a rebase to master.
The similar code was already added in https://github.com/apache/calcite/pull/1985
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
I think you need a rebase on master.
The similar code was already added in https://github.com/apache/calcite/pull/1985
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#issuecomment-658410932
@amaliujia
Here is the Columbia's source code:
https://github.com/yongwen/columbia
Project homepage:
http://web.cecs.pdx.edu/~len/Columbia/
And papers:
https://15721.courses.cs.cmu.edu/spring2019/papers/22-optimizer1/xu-columbia-thesis1998.pdf
https://users.cs.fiu.edu/~fortega/storage/cop5725/Topic%20List%20Papers/15-optimizer2/IDEAS01.pdf
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450589184
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
##########
@@ -128,6 +129,16 @@
*/
private boolean enforceDisabled = false;
+ /**
+ * the upper bound of the last OptimizeGroup call
+ */
+ RelOptCost upperBound;
+
+ /**
+ * RelNode ids that is invoked passThrough method before
+ */
+ Set<RelNode> passThroughCache;
Review comment:
Will do it.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] zinking commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
zinking commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r448352213
##########
File path: plus/src/test/java/org/apache/calcite/adapter/tpcds/TpcdsTest.java
##########
@@ -220,29 +220,33 @@ protected void foo(CalciteAssert.AssertThat with, String tableName,
.withHook(Hook.PROGRAM, handler(true, 2))
.explainMatches("including all attributes ",
CalciteAssert.checkMaskedResultContains(""
- + "EnumerableCalc(expr#0..9=[{inputs}], expr#10=[/($t4, $t3)], expr#11=[CAST($t10):INTEGER NOT NULL], expr#12=[*($t4, $t4)], expr#13=[/($t12, $t3)], expr#14=[-($t5, $t13)], expr#15=[1], expr#16=[=($t3, $t15)], expr#17=[null:BIGINT], expr#18=[-($t3, $t15)], expr#19=[CASE($t16, $t17, $t18)], expr#20=[/($t14, $t19)], expr#21=[0.5:DECIMAL(2, 1)], expr#22=[POWER($t20, $t21)], expr#23=[CAST($t22):INTEGER NOT NULL], expr#24=[/($t23, $t11)], expr#25=[/($t6, $t3)], expr#26=[CAST($t25):INTEGER NOT NULL], expr#27=[*($t6, $t6)], expr#28=[/($t27, $t3)], expr#29=[-($t7, $t28)], expr#30=[/($t29, $t19)], expr#31=[POWER($t30, $t21)], expr#32=[CAST($t31):INTEGER NOT NULL], expr#33=[/($t32, $t26)], expr#34=[/($t8, $t3)], expr#35=[CAST($t34):INTEGER NOT NULL], expr#36=[*($t8, $t8)], expr#37=[/($t36, $t3)], expr#38=[-($t9, $t37)], expr#39=[/($t38, $t19)], expr#40=[POWER($t39, $t21)], expr#41=[CAST($t40):INTEGER NOT NULL], expr#42=[/($t41, $t35)], proj#0..3=[{exprs}], STORE_SALES_QUANTITYAVE=[$t11], STORE_SALES_QUANTITYSTDEV=[$t23], STORE_SALES_QUANTITYCOV=[$t24], AS_STORE_RETURNS_QUANTITYCOUNT=[$t3], AS_STORE_RETURNS_QUANTITYAVE=[$t26], AS_STORE_RETURNS_QUANTITYSTDEV=[$t32], STORE_RETURNS_QUANTITYCOV=[$t33], CATALOG_SALES_QUANTITYCOUNT=[$t3], CATALOG_SALES_QUANTITYAVE=[$t35], CATALOG_SALES_QUANTITYSTDEV=[$t42], CATALOG_SALES_QUANTITYCOV=[$t42]): rowcount = 100.0, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableLimit(fetch=[100]): rowcount = 100.0, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableSort(sort0=[$0], sort1=[$1], sort2=[$2], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 5.434029018852197E26, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableAggregate(group=[{0, 1, 2}], STORE_SALES_QUANTITYCOUNT=[COUNT()], agg#1=[$SUM0($3)], agg#2=[$SUM0($6)], agg#3=[$SUM0($4)], agg#4=[$SUM0($7)], agg#5=[$SUM0($5)], agg#6=[$SUM0($8)]): rowcount = 5.434029018852197E26, cumulative cost = {1.1892372507898816E28 rows, 1.2172225002228922E30 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..211=[{inputs}], expr#212=[*($t89, $t89)], expr#213=[*($t140, $t140)], expr#214=[*($t196, $t196)], I_ITEM_ID=[$t58], I_ITEM_DESC=[$t61], S_STATE=[$t24], SS_QUANTITY=[$t89], SR_RETURN_QUANTITY=[$t140], CS_QUANTITY=[$t196], $f6=[$t212], $f7=[$t213], $f8=[$t214]): rowcount = 5.434029018852197E27, cumulative cost = {1.0873492066864028E28 rows, 1.2172225002228922E30 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[AND(=($82, $133), =($81, $132), =($88, $139))], joinType=[inner]): rowcount = 5.434029018852197E27, cumulative cost = {5.439463048011832E27 rows, 1.8506796E7 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $86)], joinType=[inner]): rowcount = 2.3008402586892598E13, cumulative cost = {4.8588854672854766E13 rows, 7281360.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE]]): rowcount = 12.0, cumulative cost = {12.0 rows, 13.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $50)], joinType=[inner]): rowcount = 1.2782445881607E13, cumulative cost = {1.279800620431234E13 rows, 7281347.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], proj#0..27=[{exprs}], $condition=[$t29]): rowcount = 10957.35, cumulative cost = {84006.35 rows, 4382941.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $24)], joinType=[inner]): rowcount = 7.7770908E9, cumulative cost = {7.783045975286664E9 rows, 2898406.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, ITEM]]): rowcount = 18000.0, cumulative cost = {18000.0 rows, 18001.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE_SALES]]): rowcount = 2880404.0, cumulative cost = {2880404.0 rows, 2880405.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[AND(=($31, $79), =($30, $91))], joinType=[inner]): rowcount = 6.9978029381741304E16, cumulative cost = {7.0048032234040472E16 rows, 1.1225436E7 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 7.87597881975E8, cumulative cost = {7.884434212216867E8 rows, 5035701.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE_RETURNS]]): rowcount = 287514.0, cumulative cost = {287514.0 rows, 287515.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 3.94888649445E9, cumulative cost = {3.9520401026966867E9 rows, 6189735.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, CATALOG_SALES]]): rowcount = 1441548.0, cumulative cost = {1441548.0 rows, 1441549.0 cpu, 0.0 io}\n"));
+ + "EnumerableCalc(expr#0..9=[{inputs}], expr#10=[/($t4, $t3)], expr#11=[CAST($t10):INTEGER NOT NULL], expr#12=[*($t4, $t4)], expr#13=[/($t12, $t3)], expr#14=[-($t5, $t13)], expr#15=[1], expr#16=[=($t3, $t15)], expr#17=[null:BIGINT], expr#18=[-($t3, $t15)], expr#19=[CASE($t16, $t17, $t18)], expr#20=[/($t14, $t19)], expr#21=[0.5:DECIMAL(2, 1)], expr#22=[POWER($t20, $t21)], expr#23=[CAST($t22):INTEGER NOT NULL], expr#24=[/($t23, $t11)], expr#25=[/($t6, $t3)], expr#26=[CAST($t25):INTEGER NOT NULL], expr#27=[*($t6, $t6)], expr#28=[/($t27, $t3)], expr#29=[-($t7, $t28)], expr#30=[/($t29, $t19)], expr#31=[POWER($t30, $t21)], expr#32=[CAST($t31):INTEGER NOT NULL], expr#33=[/($t32, $t26)], expr#34=[/($t8, $t3)], expr#35=[CAST($t34):INTEGER NOT NULL], expr#36=[*($t8, $t8)], expr#37=[/($t36, $t3)], expr#38=[-($t9, $t37)], expr#39=[/($t38, $t19)], expr#40=[POWER($t39, $t21)], expr#41=[CAST($t40):INTEGER NOT NULL], expr#42=[/($t41, $t35)], proj#0..3=[{exprs}], STORE_SALES_QUANTITYAVE=[$t11], STORE_SALES_QUANTITYSTDEV=[$t23], STORE_SALES_QUANTITYCOV=[$t24], AS_STORE_RETURNS_QUANTITYCOUNT=[$t3], AS_STORE_RETURNS_QUANTITYAVE=[$t26], AS_STORE_RETURNS_QUANTITYSTDEV=[$t32], STORE_RETURNS_QUANTITYCOV=[$t33], CATALOG_SALES_QUANTITYCOUNT=[$t3], CATALOG_SALES_QUANTITYAVE=[$t35], CATALOG_SALES_QUANTITYSTDEV=[$t42], CATALOG_SALES_QUANTITYCOV=[$t42]): rowcount = 100.0, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableLimit(fetch=[100]): rowcount = 100.0, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$0], sort1=[$1], sort2=[$2], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 5.434029018852197E26, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableAggregate(group=[{0, 1, 2}], STORE_SALES_QUANTITYCOUNT=[COUNT()], agg#1=[$SUM0($3)], agg#2=[$SUM0($6)], agg#3=[$SUM0($4)], agg#4=[$SUM0($7)], agg#5=[$SUM0($5)], agg#6=[$SUM0($8)]): rowcount = 5.434029018852197E26, cumulative cost = {1.1886938478949211E28 rows, 1.2172225014174444E30 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..211=[{inputs}], expr#212=[*($t89, $t89)], expr#213=[*($t140, $t140)], expr#214=[*($t196, $t196)], I_ITEM_ID=[$t58], I_ITEM_DESC=[$t61], S_STATE=[$t24], SS_QUANTITY=[$t89], SR_RETURN_QUANTITY=[$t140], CS_QUANTITY=[$t196], $f6=[$t212], $f7=[$t213], $f8=[$t214]): rowcount = 5.434029018852197E27, cumulative cost = {1.0868058037914423E28 rows, 1.2172225014174444E30 cpu, 0.0 io}\n"
+ + " EnumerableMergeJoin(condition=[AND(=($82, $133), =($81, $132), =($88, $139))], joinType=[inner]): rowcount = 5.434029018852197E27, cumulative cost = {5.434029019062226E27 rows, 1.1945521881363807E21 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$82], sort1=[$81], sort2=[$88], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 2.3008402586892598E13, cumulative cost = {7.159725725974736E13 rows, 2.8882188423696301E17 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $86)], joinType=[inner]): rowcount = 2.3008402586892598E13, cumulative cost = {4.8588854672854766E13 rows, 7281360.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE]]): rowcount = 12.0, cumulative cost = {12.0 rows, 13.0 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $50)], joinType=[inner]): rowcount = 1.2782445881607E13, cumulative cost = {1.279800620431234E13 rows, 7281347.0 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], proj#0..27=[{exprs}], $condition=[$t29]): rowcount = 10957.35, cumulative cost = {84006.35 rows, 4382941.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $24)], joinType=[inner]): rowcount = 7.7770908E9, cumulative cost = {7.783045975286664E9 rows, 2898406.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, ITEM]]): rowcount = 18000.0, cumulative cost = {18000.0 rows, 18001.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE_SALES]]): rowcount = 2880404.0, cumulative cost = {2880404.0 rows, 2880405.0 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$30], sort2=[$37], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 6.9978029381741304E16, cumulative cost = {1.3995607297693488E17 rows, 1.1942633662521438E21 cpu, 0.0 io}\n"
+ + " EnumerableMergeJoin(condition=[AND(=($31, $79), =($30, $91))], joinType=[inner]): rowcount = 6.9978029381741304E16, cumulative cost = {6.9978043595193584E16 rows, 2.473747714463278E13 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$30], dir0=[ASC], dir1=[ASC]): rowcount = 7.87597881975E8, cumulative cost = {1.5760413031966867E9 rows, 3.097646138009654E12 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 7.87597881975E8, cumulative cost = {7.884434212216867E8 rows, 5035701.0 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE_RETURNS]]): rowcount = 287514.0, cumulative cost = {287514.0 rows, 287515.0 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$43], dir0=[ASC], dir1=[ASC]): rowcount = 3.94888649445E9, cumulative cost = {7.900926597146687E9 rows, 2.163983100662313E13 cpu, 0.0 io}\n"
Review comment:
I can't derive that these two are equivalent, how did you guys do that ?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451565232
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,112 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.plan.volcano.VolcanoPlanner;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ public RelOptCost getLowerBoundCost(RelSubset subset,
+ RelMetadataQuery mq, VolcanoPlanner planner) {
+
+ if (planner.isLogical(subset)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost winner = subset.getWinnerCost();
+ if (winner != null) {
+ // when this subset is fully optimized, just return the winner
+ return winner;
+ }
+
+ // if group is not fully explored. Its properties like cardinality
+ // would get changed after exploration. So it cannot return a valid LB
+ if (!subset.isExplored()) {
+ return null;
+ }
+
+ RelOptCost lowerBound = null;
Review comment:
resolved
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] junzheng-zheng commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
junzheng-zheng commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450615221
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,112 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.plan.volcano.VolcanoPlanner;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ public RelOptCost getLowerBoundCost(RelSubset subset,
+ RelMetadataQuery mq, VolcanoPlanner planner) {
+
+ if (planner.isLogical(subset)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost winner = subset.getWinnerCost();
+ if (winner != null) {
+ // when this subset is fully optimized, just return the winner
+ return winner;
+ }
+
+ // if group is not fully explored. Its properties like cardinality
+ // would get changed after exploration. So it cannot return a valid LB
+ if (!subset.isExplored()) {
+ return null;
+ }
+
+ RelOptCost lowerBound = null;
Review comment:
If current group is not fully optimized and has no winner, there may be problems to get the lower bound here. Since the current group's optimization may affact the input groups of the current group. E.g., the current group's optimization may push down some require traits and maybe somewhere of the inputs subtrees may enhance there's costs. So if we get the lower bound here, it may be larger than the actual lower bound which may miss optimal plan
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450590729
##########
File path: plus/src/test/java/org/apache/calcite/adapter/tpcds/TpcdsTest.java
##########
@@ -220,29 +220,33 @@ protected void foo(CalciteAssert.AssertThat with, String tableName,
.withHook(Hook.PROGRAM, handler(true, 2))
.explainMatches("including all attributes ",
CalciteAssert.checkMaskedResultContains(""
- + "EnumerableCalc(expr#0..9=[{inputs}], expr#10=[/($t4, $t3)], expr#11=[CAST($t10):INTEGER NOT NULL], expr#12=[*($t4, $t4)], expr#13=[/($t12, $t3)], expr#14=[-($t5, $t13)], expr#15=[1], expr#16=[=($t3, $t15)], expr#17=[null:BIGINT], expr#18=[-($t3, $t15)], expr#19=[CASE($t16, $t17, $t18)], expr#20=[/($t14, $t19)], expr#21=[0.5:DECIMAL(2, 1)], expr#22=[POWER($t20, $t21)], expr#23=[CAST($t22):INTEGER NOT NULL], expr#24=[/($t23, $t11)], expr#25=[/($t6, $t3)], expr#26=[CAST($t25):INTEGER NOT NULL], expr#27=[*($t6, $t6)], expr#28=[/($t27, $t3)], expr#29=[-($t7, $t28)], expr#30=[/($t29, $t19)], expr#31=[POWER($t30, $t21)], expr#32=[CAST($t31):INTEGER NOT NULL], expr#33=[/($t32, $t26)], expr#34=[/($t8, $t3)], expr#35=[CAST($t34):INTEGER NOT NULL], expr#36=[*($t8, $t8)], expr#37=[/($t36, $t3)], expr#38=[-($t9, $t37)], expr#39=[/($t38, $t19)], expr#40=[POWER($t39, $t21)], expr#41=[CAST($t40):INTEGER NOT NULL], expr#42=[/($t41, $t35)], proj#0..3=[{exprs}], STORE_SALES_QUANTITYAVE=[$t11], STORE_SALES_QUANTITYSTDEV=[$t23], STORE_SALES_QUANTITYCOV=[$t24], AS_STORE_RETURNS_QUANTITYCOUNT=[$t3], AS_STORE_RETURNS_QUANTITYAVE=[$t26], AS_STORE_RETURNS_QUANTITYSTDEV=[$t32], STORE_RETURNS_QUANTITYCOV=[$t33], CATALOG_SALES_QUANTITYCOUNT=[$t3], CATALOG_SALES_QUANTITYAVE=[$t35], CATALOG_SALES_QUANTITYSTDEV=[$t42], CATALOG_SALES_QUANTITYCOV=[$t42]): rowcount = 100.0, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableLimit(fetch=[100]): rowcount = 100.0, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableSort(sort0=[$0], sort1=[$1], sort2=[$2], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 5.434029018852197E26, cumulative cost = {1.2435775409784036E28 rows, 2.555295485909236E30 cpu, 0.0 io}\n"
- + " EnumerableAggregate(group=[{0, 1, 2}], STORE_SALES_QUANTITYCOUNT=[COUNT()], agg#1=[$SUM0($3)], agg#2=[$SUM0($6)], agg#3=[$SUM0($4)], agg#4=[$SUM0($7)], agg#5=[$SUM0($5)], agg#6=[$SUM0($8)]): rowcount = 5.434029018852197E26, cumulative cost = {1.1892372507898816E28 rows, 1.2172225002228922E30 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..211=[{inputs}], expr#212=[*($t89, $t89)], expr#213=[*($t140, $t140)], expr#214=[*($t196, $t196)], I_ITEM_ID=[$t58], I_ITEM_DESC=[$t61], S_STATE=[$t24], SS_QUANTITY=[$t89], SR_RETURN_QUANTITY=[$t140], CS_QUANTITY=[$t196], $f6=[$t212], $f7=[$t213], $f8=[$t214]): rowcount = 5.434029018852197E27, cumulative cost = {1.0873492066864028E28 rows, 1.2172225002228922E30 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[AND(=($82, $133), =($81, $132), =($88, $139))], joinType=[inner]): rowcount = 5.434029018852197E27, cumulative cost = {5.439463048011832E27 rows, 1.8506796E7 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $86)], joinType=[inner]): rowcount = 2.3008402586892598E13, cumulative cost = {4.8588854672854766E13 rows, 7281360.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE]]): rowcount = 12.0, cumulative cost = {12.0 rows, 13.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $50)], joinType=[inner]): rowcount = 1.2782445881607E13, cumulative cost = {1.279800620431234E13 rows, 7281347.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], proj#0..27=[{exprs}], $condition=[$t29]): rowcount = 10957.35, cumulative cost = {84006.35 rows, 4382941.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $24)], joinType=[inner]): rowcount = 7.7770908E9, cumulative cost = {7.783045975286664E9 rows, 2898406.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, ITEM]]): rowcount = 18000.0, cumulative cost = {18000.0 rows, 18001.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE_SALES]]): rowcount = 2880404.0, cumulative cost = {2880404.0 rows, 2880405.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[AND(=($31, $79), =($30, $91))], joinType=[inner]): rowcount = 6.9978029381741304E16, cumulative cost = {7.0048032234040472E16 rows, 1.1225436E7 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 7.87597881975E8, cumulative cost = {7.884434212216867E8 rows, 5035701.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, STORE_RETURNS]]): rowcount = 287514.0, cumulative cost = {287514.0 rows, 287515.0 cpu, 0.0 io}\n"
- + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 3.94888649445E9, cumulative cost = {3.9520401026966867E9 rows, 6189735.0 cpu, 0.0 io}\n"
- + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
- + " EnumerableTableScan(table=[[TPCDS, CATALOG_SALES]]): rowcount = 1441548.0, cumulative cost = {1441548.0 rows, 1441549.0 cpu, 0.0 io}\n"));
+ + "EnumerableCalc(expr#0..9=[{inputs}], expr#10=[/($t4, $t3)], expr#11=[CAST($t10):INTEGER NOT NULL], expr#12=[*($t4, $t4)], expr#13=[/($t12, $t3)], expr#14=[-($t5, $t13)], expr#15=[1], expr#16=[=($t3, $t15)], expr#17=[null:BIGINT], expr#18=[-($t3, $t15)], expr#19=[CASE($t16, $t17, $t18)], expr#20=[/($t14, $t19)], expr#21=[0.5:DECIMAL(2, 1)], expr#22=[POWER($t20, $t21)], expr#23=[CAST($t22):INTEGER NOT NULL], expr#24=[/($t23, $t11)], expr#25=[/($t6, $t3)], expr#26=[CAST($t25):INTEGER NOT NULL], expr#27=[*($t6, $t6)], expr#28=[/($t27, $t3)], expr#29=[-($t7, $t28)], expr#30=[/($t29, $t19)], expr#31=[POWER($t30, $t21)], expr#32=[CAST($t31):INTEGER NOT NULL], expr#33=[/($t32, $t26)], expr#34=[/($t8, $t3)], expr#35=[CAST($t34):INTEGER NOT NULL], expr#36=[*($t8, $t8)], expr#37=[/($t36, $t3)], expr#38=[-($t9, $t37)], expr#39=[/($t38, $t19)], expr#40=[POWER($t39, $t21)], expr#41=[CAST($t40):INTEGER NOT NULL], expr#42=[/($t41, $t35)], proj#0..3=[{exprs}], STORE_SALES_QUANTITYAVE=[$t11], STORE_SALES_QUANTITYSTDEV=[$t23], STORE_SALES_QUANTITYCOV=[$t24], AS_STORE_RETURNS_QUANTITYCOUNT=[$t3], AS_STORE_RETURNS_QUANTITYAVE=[$t26], AS_STORE_RETURNS_QUANTITYSTDEV=[$t32], STORE_RETURNS_QUANTITYCOV=[$t33], CATALOG_SALES_QUANTITYCOUNT=[$t3], CATALOG_SALES_QUANTITYAVE=[$t35], CATALOG_SALES_QUANTITYSTDEV=[$t42], CATALOG_SALES_QUANTITYCOV=[$t42]): rowcount = 100.0, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableLimit(fetch=[100]): rowcount = 100.0, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$0], sort1=[$1], sort2=[$2], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 5.434029018852197E26, cumulative cost = {1.2430341380834431E28 rows, 2.555295487103789E30 cpu, 0.0 io}\n"
+ + " EnumerableAggregate(group=[{0, 1, 2}], STORE_SALES_QUANTITYCOUNT=[COUNT()], agg#1=[$SUM0($3)], agg#2=[$SUM0($6)], agg#3=[$SUM0($4)], agg#4=[$SUM0($7)], agg#5=[$SUM0($5)], agg#6=[$SUM0($8)]): rowcount = 5.434029018852197E26, cumulative cost = {1.1886938478949211E28 rows, 1.2172225014174444E30 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..211=[{inputs}], expr#212=[*($t89, $t89)], expr#213=[*($t140, $t140)], expr#214=[*($t196, $t196)], I_ITEM_ID=[$t58], I_ITEM_DESC=[$t61], S_STATE=[$t24], SS_QUANTITY=[$t89], SR_RETURN_QUANTITY=[$t140], CS_QUANTITY=[$t196], $f6=[$t212], $f7=[$t213], $f8=[$t214]): rowcount = 5.434029018852197E27, cumulative cost = {1.0868058037914423E28 rows, 1.2172225014174444E30 cpu, 0.0 io}\n"
+ + " EnumerableMergeJoin(condition=[AND(=($82, $133), =($81, $132), =($88, $139))], joinType=[inner]): rowcount = 5.434029018852197E27, cumulative cost = {5.434029019062226E27 rows, 1.1945521881363807E21 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$82], sort1=[$81], sort2=[$88], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 2.3008402586892598E13, cumulative cost = {7.159725725974736E13 rows, 2.8882188423696301E17 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $86)], joinType=[inner]): rowcount = 2.3008402586892598E13, cumulative cost = {4.8588854672854766E13 rows, 7281360.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE]]): rowcount = 12.0, cumulative cost = {12.0 rows, 13.0 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $50)], joinType=[inner]): rowcount = 1.2782445881607E13, cumulative cost = {1.279800620431234E13 rows, 7281347.0 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], proj#0..27=[{exprs}], $condition=[$t29]): rowcount = 10957.35, cumulative cost = {84006.35 rows, 4382941.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $24)], joinType=[inner]): rowcount = 7.7770908E9, cumulative cost = {7.783045975286664E9 rows, 2898406.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, ITEM]]): rowcount = 18000.0, cumulative cost = {18000.0 rows, 18001.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE_SALES]]): rowcount = 2880404.0, cumulative cost = {2880404.0 rows, 2880405.0 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$30], sort2=[$37], dir0=[ASC], dir1=[ASC], dir2=[ASC]): rowcount = 6.9978029381741304E16, cumulative cost = {1.3995607297693488E17 rows, 1.1942633662521438E21 cpu, 0.0 io}\n"
+ + " EnumerableMergeJoin(condition=[AND(=($31, $79), =($30, $91))], joinType=[inner]): rowcount = 6.9978029381741304E16, cumulative cost = {6.9978043595193584E16 rows, 2.473747714463278E13 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$30], dir0=[ASC], dir1=[ASC]): rowcount = 7.87597881975E8, cumulative cost = {1.5760413031966867E9 rows, 3.097646138009654E12 cpu, 0.0 io}\n"
+ + " EnumerableHashJoin(condition=[=($0, $28)], joinType=[inner]): rowcount = 7.87597881975E8, cumulative cost = {7.884434212216867E8 rows, 5035701.0 cpu, 0.0 io}\n"
+ + " EnumerableCalc(expr#0..27=[{inputs}], expr#28=['1998Q1'], expr#29=[=($t15, $t28)], expr#30=['1998Q2'], expr#31=[=($t15, $t30)], expr#32=['1998Q3'], expr#33=[=($t15, $t32)], expr#34=[OR($t29, $t31, $t33)], proj#0..27=[{exprs}], $condition=[$t34]): rowcount = 18262.25, cumulative cost = {91311.25 rows, 4748186.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, DATE_DIM]]): rowcount = 73049.0, cumulative cost = {73049.0 rows, 73050.0 cpu, 0.0 io}\n"
+ + " EnumerableTableScan(table=[[TPCDS, STORE_RETURNS]]): rowcount = 287514.0, cumulative cost = {287514.0 rows, 287515.0 cpu, 0.0 io}\n"
+ + " EnumerableSort(sort0=[$31], sort1=[$43], dir0=[ASC], dir1=[ASC]): rowcount = 3.94888649445E9, cumulative cost = {7.900926597146687E9 rows, 2.163983100662313E13 cpu, 0.0 io}\n"
Review comment:
The only changes is that some HashJoin is changed to MergeJoin. But as you can see from the cost, the new plan do have a lower cost.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r452103207
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
##########
@@ -839,6 +806,67 @@ RelNode changeTraitsUsingConverters(
prunedNodes.add(rel);
}
+
+ /** Returns whether to skip a match. This happens if any of the
+ * {@link RelNode}s have importance zero. */
+ boolean skipMatch(VolcanoRuleMatch match) {
Review comment:
moved back
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/CascadesRuleQueue.java
##########
@@ -0,0 +1,90 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.Pair;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * A rule queue that manage rule matches for cascade planner
+ */
+public class CascadesRuleQueue implements RuleQueue {
+
+ private final VolcanoPlanner planner;
+
+ private final Map<Integer, List<VolcanoRuleMatch>> matches = new HashMap<>();
Review comment:
resolved
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433613248
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
"Two expected plans" looks like a good solution.
There are discussion about keeping one planner versus creating a new one. But no matter which way to go, the volcano model will be deprecated some day. So compatibility is necessary for both alternatives. Plan could be changed, but the new model should not produce a worse plan.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r433613248
##########
File path: core/src/main/java/org/apache/calcite/config/CalciteConnectionProperty.java
##########
@@ -105,6 +105,10 @@
* {@link org.apache.calcite.sql.parser.SqlParserImplFactory}. */
PARSER_FACTORY("parserFactory", Type.PLUGIN, null, false),
+ /** Specifies whether to use top down optimization.
+ * {@link org.apache.calcite.plan.volcano.VolcanoPlanner#setTopDownOpt(boolean)} */
+ TOP_DOWN_OPT("topDownOpt", Type.BOOLEAN, true, false),
Review comment:
Two expected plans looks like a good solution.
There are discussion about keeping one planner versus creating a new one. But no matter which way to go, the volcano model will be deprecated some day. So compatibility is necessary for both alternatives. Plan could be changed, but the new model should not produce a worse plan.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#issuecomment-658433494
> Optimizer at that time was less fancy for me compared to lock-free data structures :)
This is indeed true. :)
@FatLittle I have logged a JIRA for on-demand rule match: CALCITE-4122
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r438414610
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
##########
@@ -16,349 +16,18 @@
*/
package org.apache.calcite.plan.volcano;
-import org.apache.calcite.plan.RelOptRuleOperand;
-import org.apache.calcite.rel.RelNode;
-import org.apache.calcite.rel.rules.SubstitutionRule;
-import org.apache.calcite.util.Util;
-import org.apache.calcite.util.trace.CalciteTrace;
-
-import com.google.common.collect.HashMultimap;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Multimap;
-
-import org.slf4j.Logger;
-
-import java.io.PrintWriter;
-import java.io.StringWriter;
-import java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.EnumMap;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Set;
-
-/**
- * Priority queue of relexps whose rules have not been called, and rule-matches
- * which have not yet been acted upon.
- */
-class RuleQueue {
- //~ Static fields/initializers ---------------------------------------------
-
- private static final Logger LOGGER = CalciteTrace.getPlannerTracer();
-
- private static final Set<String> ALL_RULES = ImmutableSet.of("<ALL RULES>");
-
- //~ Instance fields --------------------------------------------------------
-
- /**
- * Map of {@link VolcanoPlannerPhase} to a list of rule-matches. Initially,
- * there is an empty {@link PhaseMatchList} for each planner phase. As the
- * planner invokes {@link #addMatch(VolcanoRuleMatch)} the rule-match is
- * added to the appropriate PhaseMatchList(s). As the planner completes
- * phases, the matching entry is removed from this list to avoid unused
- * work.
- */
- final Map<VolcanoPlannerPhase, PhaseMatchList> matchListMap =
- new EnumMap<>(VolcanoPlannerPhase.class);
-
- private final VolcanoPlanner planner;
-
- /**
- * Maps a {@link VolcanoPlannerPhase} to a set of rule descriptions. Named rules
- * may be invoked in their corresponding phase.
- *
- * <p>See {@link VolcanoPlannerPhaseRuleMappingInitializer} for more
- * information regarding the contents of this Map and how it is initialized.
- */
- private final Map<VolcanoPlannerPhase, Set<String>> phaseRuleMapping;
-
- //~ Constructors -----------------------------------------------------------
-
- RuleQueue(VolcanoPlanner planner) {
- this.planner = planner;
-
- phaseRuleMapping = new EnumMap<>(VolcanoPlannerPhase.class);
-
- // init empty sets for all phases
- for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
- phaseRuleMapping.put(phase, new HashSet<>());
- }
-
- // configure phases
- planner.getPhaseRuleMappingInitializer().initialize(phaseRuleMapping);
-
- for (VolcanoPlannerPhase phase : VolcanoPlannerPhase.values()) {
- // empty phases get converted to "all rules"
- if (phaseRuleMapping.get(phase).isEmpty()) {
- phaseRuleMapping.put(phase, ALL_RULES);
- }
-
- // create a match list data structure for each phase
- PhaseMatchList matchList = new PhaseMatchList(phase);
-
- matchListMap.put(phase, matchList);
- }
- }
-
- //~ Methods ----------------------------------------------------------------
- /**
- * Clear internal data structure for this rule queue.
- */
- public void clear() {
- for (PhaseMatchList matchList : matchListMap.values()) {
- matchList.clear();
- }
- }
+public interface RuleQueue {
Review comment:
nit: let's remove public.
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/MultiPhasedRuleDriver.java
##########
@@ -0,0 +1,87 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+/***
+ * <p>The algorithm executes repeatedly in a series of phases. In each phase
+ * the exact rules that may be fired varies. The mapping of phases to rule
+ * sets is maintained in the {@link #ruleQueue}.
+ *
+ * <p>In each phase, the planner then iterates over the rule matches presented
+ * by the rule queue until the rule queue becomes empty.
+ */
+public class MultiPhasedRuleDriver implements RuleDriver {
Review comment:
MultiPhasedRuleDriver -> IterativeRuleDriver
The multiphase doesn't work well at all. No body use it, we should consider removing multi phases in volcano planner.
and remove public
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
Review comment:
There may be other usages in down stream project that defines their own logical conventions, while still keep NONE. That means they are using 2 logical conventions......
But let's keep it simple for NONE for now.
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
+ }
+
+ public RelOptCost getLowerBoundCost(RelSubset subset,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+
+ if (isLogical(subset)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost winner = subset.getWinnerCost();
+ if (winner != null) {
+ // when this subset is fully optimized, just return the winner
+ return winner;
+ }
+
+ // if group is not fully explored. Its properties like cardinality
+ // would get changed after exploration. So it cannot return a valid LB
+ if (!subset.isExplored()) {
+ return null;
+ }
+
+ RelOptCost lowerBound = null;
+ for (RelNode relNode : subset.getRels()) {
+ try {
+ RelOptCost lb = mq.getLowerBoundCost(relNode, planner);
+ if (lb == null) {
+ return null;
+ }
+ if (lowerBound == null || lb.isLt(lowerBound)) {
+ lowerBound = lb;
+ }
+ } catch (CyclicMetadataException e) {
+ if (lowerBound == null) {
+ // a cyclic metadata query means this node has an INF LB
+ lowerBound = planner.getCostFactory().makeInfiniteCost();
+ }
+ }
+ }
+ return lowerBound;
+ }
+
+ public RelOptCost getLowerBoundCost(RelNode node,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ if (isLogical(node)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost selfCost = node.computeSelfCost(planner, mq);
+ if (selfCost.isInfinite()) {
+ selfCost = null;
+ }
+ for (RelNode input : node.getInputs()) {
+ RelOptCost lb = mq.getLowerBoundCost(input, planner);
+ if (lb != null) {
+ selfCost = selfCost == null ? lb : selfCost.plus(lb);
+ }
+ }
+ return selfCost;
+ }
+
+ public RelOptCost getLowerBoundCost(AbstractConverter ac,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ return mq.getLowerBoundCost(ac.getInput(), planner);
Review comment:
Still use abstract converter?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436255565
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
##########
@@ -317,8 +284,8 @@ RelSubset getOrCreateSubset(
subset.setDelivered();
}
- if (needsConverter && !planner.topDownOpt) {
- addConverters(subset, required, true);
+ if (needsConverter) {
+ addConverters(subset, required, !planner.topDownOpt);
Review comment:
Yes, it is.
The converters act as bridges between the working subset and other subsets. Currently, the OptimizeGroup task will schedule tasks for all the logical Rels in the RelSet while it skips physical Rels from other subsets. That's because we are confident that if other subset can be reached by a converter, the converter is already in the current working subset.
I was thinking of checking the upper bound before adding the enforcer. But I cannot decide which place is suitable for adding the enforcer back when the upper bound is changed. So I leave it for further optimizations.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r454539517
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/CascadeRuleQueue.java
##########
@@ -0,0 +1,94 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.util.Pair;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * A rule queue that manage rule matches for cascade planner
+ */
+public class CascadeRuleQueue implements RuleQueue {
Review comment:
I will create another JIRA to support on-demand rule matching.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r436254500
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
Review comment:
Will, it is somehow like a metadata.
1. Different subclass of RelNodes may have different logic, like AC, RelNode, SpoolNode, RelSubset ...
2. It needs a cache and the cache should be invalidated when its input is changed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r432252714
##########
File path: kafka/src/test/java/org/apache/calcite/adapter/kafka/KafkaAdapterTest.java
##########
@@ -73,6 +74,7 @@
@Test void testFilterWithProject() {
assertModel(MODEL)
+ .with(CalciteConnectionProperty.TOP_DOWN_OPT.camelName(), false)
Review comment:
skip using top-down optimization here. This case will produce another plan with the same cost as the expect plan
(Two candidates are both in the memo but the new best plan is produced first) but it will hang when executing the new plan. Still don't know why it hangs.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450588566
##########
File path: cassandra/src/test/java/org/apache/calcite/test/CassandraAdapterTest.java
##########
@@ -100,8 +100,8 @@ static void load(Session session) {
.returns("tweet_id=f3c329de-d05b-11e5-b58b-90e2ba530b12\n"
+ "tweet_id=f3dbb03a-d05b-11e5-b58b-90e2ba530b12\n")
.explainContains("PLAN=CassandraToEnumerableConverter\n"
- + " CassandraLimit(fetch=[2])\n"
- + " CassandraProject(tweet_id=[$2])\n"
+ + " CassandraProject(tweet_id=[$2])\n"
+ + " CassandraLimit(fetch=[2])\n"
+ " CassandraFilter(condition=[=($0, '!PUBLIC!')])\n");
}
Review comment:
yes, the costs are the same. However, I do think in most case the new plan is better.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] FatLittle commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
FatLittle commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r450589967
##########
File path: core/src/test/resources/sql/agg.iq
##########
@@ -2290,9 +2290,9 @@ select MGR, count(distinct DEPTNO, JOB), MIN(SAL), MAX(SAL) from "scott".emp gro
!ok
-EnumerableAggregate(group=[{0}], EXPR$1=[COUNT($1, $2) FILTER $5], EXPR$2=[MIN($3) FILTER $6], EXPR$3=[MIN($4) FILTER $6])
- EnumerableCalc(expr#0..5=[{inputs}], expr#6=[0], expr#7=[=($t5, $t6)], expr#8=[3], expr#9=[=($t5, $t8)], MGR=[$t1], DEPTNO=[$t2], JOB=[$t0], EXPR$2=[$t3], EXPR$3=[$t4], $g_0=[$t7], $g_3=[$t9])
- EnumerableAggregate(group=[{2, 3, 7}], groups=[[{2, 3, 7}, {3}]], EXPR$2=[MIN($5)], EXPR$3=[MAX($5)], $g=[GROUPING($3, $7, $2)])
+EnumerableAggregate(group=[{1}], EXPR$1=[COUNT($2, $0) FILTER $5], EXPR$2=[MIN($3) FILTER $6], EXPR$3=[MIN($4) FILTER $6])
+ EnumerableCalc(expr#0..5=[{inputs}], expr#6=[0], expr#7=[=($t5, $t6)], expr#8=[5], expr#9=[=($t5, $t8)], proj#0..4=[{exprs}], $g_0=[$t7], $g_5=[$t9])
+ EnumerableAggregate(group=[{2, 3, 7}], groups=[[{2, 3, 7}, {3}]], EXPR$2=[MIN($5)], EXPR$3=[MAX($5)], $g=[GROUPING($2, $3, $7)])
EnumerableTableScan(table=[[scott, EMP]])
Review comment:
the diff lays in grouping keys sequence ( [2,3,7] vs [3,7,2]). They should be equivalent.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] hsyuan commented on a change in pull request #1991: [CALCITE-3916] Support top-down rule apply and upper bound space pruning
Posted by GitBox <gi...@apache.org>.
hsyuan commented on a change in pull request #1991:
URL: https://github.com/apache/calcite/pull/1991#discussion_r451867506
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java
##########
@@ -0,0 +1,928 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.DeriveMode;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelTrait;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.PhysicalNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Predicate;
+
+class TopDownRuleDriver implements RuleDriver {
+
+ /**
+ * the Logger
+ */
+ private static final Logger LOGGER = CalciteTrace.getPlannerTaskTracer();
+
+ /**
+ * The planner
+ */
+ private final VolcanoPlanner planner;
+
+ /**
+ * the rule queue designed for top-down rule applying
+ */
+ private final CascadesRuleQueue ruleQueue;
+
+ /**
+ * all tasks waiting for execution
+ */
+ private Stack<Task> tasks = new Stack<>();
+
+ /**
+ * A task that is currently applying and may generate new RelNode.
+ * It provides a callback to schedule tasks for new RelNodes that
+ * are registered during task performing
+ */
+ private GeneratorTask applying = null;
+
+ /**
+ * relnodes that are generated by passThrough or derive
+ * these nodes will not takes part in another passThrough or derive
+ */
+ private Set<RelNode> passThroughCache = new HashSet<>();
+
+ //~ Constructors -----------------------------------------------------------
+
+ TopDownRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new CascadesRuleQueue(planner);
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ @Override public void drive() {
+ TaskDescriptor description = new TaskDescriptor();
+ tasks.push(new OptimizeGroup(planner.root, planner.infCost));
+ exploreMaterializationRoots();
+ while (!tasks.isEmpty()) {
+ Task task = tasks.pop();
+ description.log(task);
+ task.perform();
+ }
+ }
+
+ private void exploreMaterializationRoots() {
+ for (RelSubset extraRoot : planner.explorationRoots) {
+ RelSet rootSet = VolcanoPlanner.equivRoot(extraRoot.set);
+ if (rootSet == planner.root.set) {
+ continue;
+ }
+ for (RelNode rel : extraRoot.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, extraRoot, true));
+ }
+ }
+ }
+ }
+
+ @Override public CascadesRuleQueue getRuleQueue() {
+ return ruleQueue;
+ }
+
+ @Override public void clear() {
+ ruleQueue.clear();
+ tasks.clear();
+ passThroughCache.clear();
+ applying = null;
+ }
+
+ private interface Procedure {
+ void exec();
+ }
+
+ private void applyGenerator(GeneratorTask task, Procedure proc) {
+ GeneratorTask applying = this.applying;
+ this.applying = task;
+ try {
+ proc.exec();
+ } finally {
+ this.applying = applying;
+ }
+ }
+
+ public void onSetMerged(RelSet set) {
+ applyGenerator(null, () -> clearProcessed(set));
+ }
+
+ private void clearProcessed(RelSet set) {
+ boolean explored = set.exploringState != null;
+ set.exploringState = null;
+
+ for (RelSubset subset : set.subsets) {
+ if (subset.resetOptimizing() || explored) {
+ Collection<RelNode> parentRels = subset.getParentRels();
+ for (RelNode parentRel : parentRels) {
+ clearProcessed(planner.getSet(parentRel));
+ }
+ if (subset == planner.root) {
+ tasks.push(new OptimizeGroup(subset, planner.infCost));
+ }
+ }
+ }
+ }
+
+ public void onProduce(RelNode node, RelSubset subset) {
+ if (applying == null || subset.set
+ != VolcanoPlanner.equivRoot(applying.group().set)) {
+ return;
+ }
+
+ if (!applying.onProduce(node)) {
+ return;
+ }
+
+ if (!planner.isLogical(node)) {
+ RelSubset optimizingGroup = null;
+ boolean canPassThrough = node instanceof PhysicalNode
+ && !passThroughCache.contains(node);
+ if (!canPassThrough && subset.taskState != null) {
+ optimizingGroup = subset;
+ } else {
+ RelOptCost upperBound = planner.zeroCost;
+ RelSet set = subset.getSet();
+ List<RelSubset> subsetsToPassThrough = new ArrayList<>();
+ for (RelSubset otherSubset : set.subsets) {
+ if (!otherSubset.isRequired() || otherSubset != planner.root
+ && otherSubset.taskState != RelSubset.OptimizeState.OPTIMIZING) {
+ continue;
+ }
+ if (node.getTraitSet().satisfies(otherSubset.getTraitSet())) {
+ if (upperBound.isLt(otherSubset.upperBound)) {
+ upperBound = otherSubset.upperBound;
+ optimizingGroup = otherSubset;
+ }
+ } else if (canPassThrough) {
+ subsetsToPassThrough.add(otherSubset);
+ }
+ }
+ for (RelSubset otherSubset : subsetsToPassThrough) {
+ Task task = getOptimizeInputTask(node, otherSubset);
+ if (task != null) {
+ tasks.push(task);
+ }
+ }
+ }
+ if (optimizingGroup == null) {
+ return;
+ }
+ Task task = getOptimizeInputTask(node, optimizingGroup);
+ if (task != null) {
+ tasks.push(task);
+ }
+ } else {
+ boolean optimizing = subset.set.subsets.stream()
+ .anyMatch(s -> s.taskState == RelSubset.OptimizeState.OPTIMIZING);
+ tasks.push(
+ new OptimizeMExpr(node, applying.group(),
+ applying.exploring() && !optimizing));
+ }
+ }
+
+ //~ Inner Classes ----------------------------------------------------------
+
+ /**
+ * Base class for planner task
+ */
+ private interface Task {
+ void perform();
+ void describe(TaskDescriptor desc);
+ }
+
+ /**
+ * A class for task logging
+ */
+ private static class TaskDescriptor {
+ private boolean first = true;
+ private StringBuilder builder = new StringBuilder();
+
+ void log(Task task) {
+ if (!LOGGER.isDebugEnabled()) {
+ return;
+ }
+ first = true;
+ builder.setLength(0);
+ builder.append("Execute task: ").append(task.getClass().getSimpleName());
+ task.describe(this);
+ if (!first) {
+ builder.append(")");
+ }
+
+ LOGGER.info(builder.toString());
+ }
+
+ TaskDescriptor item(String name, Object value) {
+ if (first) {
+ first = false;
+ builder.append("(");
+ } else {
+ builder.append(", ");
+ }
+ builder.append(name).append("=").append(value);
+ return this;
+ }
+ }
+
+ private interface GeneratorTask extends Task {
+ RelSubset group();
+ boolean exploring();
+ default boolean onProduce(RelNode node) {
+ return true;
+ }
+ }
+
+ /**
+ * O_GROUP
+ */
+ private class OptimizeGroup implements Task {
+ private final RelSubset group;
+ private RelOptCost upperBound;
+
+ OptimizeGroup(RelSubset group, RelOptCost upperBound) {
+ this.group = group;
+ this.upperBound = upperBound;
+ }
+
+ @Override public void perform() {
+ RelOptCost winner = group.getWinnerCost();
+ if (winner != null) {
+ return;
+ }
+
+ if (group.taskState != null && upperBound.isLe(group.upperBound)) {
+ // this group failed to optimize before or it is a ring
+ return;
+ }
+
+ group.startOptimize(upperBound);
+
+ // cannot decide an actual lower bound before MExpr are fully explored
+ // so delay the lower bound checking
+
+ // a gate keeper to update context
+ tasks.push(new GroupOptimized(group));
+
+ // optimize mExprs in group
+ List<RelNode> physicals = new ArrayList<>();
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, false));
+ } else if (rel.isEnforcer()) {
+ // Enforcers have lower priority than other physical nodes
+ physicals.add(0, rel);
+ } else {
+ physicals.add(rel);
+ }
+ }
+ // always apply O_INPUTS first so as to get an valid upper bound
+ for (RelNode rel : physicals) {
+ Task task = getOptimizeInputTask(rel, group);
+ if (task != null) {
+ tasks.add(task);
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group).item("upperBound", upperBound);
+ }
+ }
+
+ /**
+ * Mark the group optimized
+ */
+ private static class GroupOptimized implements Task {
+ private final RelSubset group;
+
+ GroupOptimized(RelSubset group) {
+ this.group = group;
+ }
+
+ @Override public void perform() {
+ group.optimized();
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * O_EXPR
+ */
+ private class OptimizeMExpr implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean explore;
+
+ OptimizeMExpr(RelNode mExpr,
+ RelSubset group, boolean explore) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.explore = explore;
+ }
+
+ @Override public void perform() {
+ if (explore && group.isExplored()) {
+ return;
+ }
+ // 1. explode input
+ // 2. apply other rules
+ tasks.push(new ApplyRules(mExpr, group, explore));
+ for (int i = mExpr.getInputs().size() - 1; i >= 0; --i) {
+ tasks.push(new ExploreInput(mExpr, i));
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("explore", explore);
+ }
+ }
+
+ /**
+ * ensure ExploreInput are working on the correct input group since calcite
+ * may merge sets
+ */
+ private class EnsureGroupExplored implements Task {
+
+ private final RelSubset input;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ EnsureGroupExplored(RelSubset input, RelNode parent, int inputOrdinal) {
+ this.input = input;
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (parent.getInput(inputOrdinal) != input) {
+ tasks.push(new ExploreInput(parent, inputOrdinal));
+ return;
+ }
+ input.setExplored();
+ for (RelSubset subset : input.getSet().subsets) {
+ // clear the LB cache as exploring state have changed
+ input.getCluster().getMetadataQuery().clearCache(subset);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", parent).item("i", inputOrdinal);
+ }
+ }
+
+ /**
+ * E_GROUP
+ */
+ private class ExploreInput implements Task {
+ private final RelSubset group;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ ExploreInput(RelNode parent, int inputOrdinal) {
+ this.group = (RelSubset) parent.getInput(inputOrdinal);
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (!group.explore()) {
+ return;
+ }
+ tasks.push(new EnsureGroupExplored(group, parent, inputOrdinal));
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, true));
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * extract rule matches from rule queue and add them to task stack
+ */
+ private class ApplyRules implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRules(RelNode mExpr, RelSubset group, boolean exploring) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void perform() {
+ Pair<RelNode, Predicate<VolcanoRuleMatch>> category =
+ exploring ? Pair.of(mExpr, planner::isTransformationRule)
+ : Pair.of(mExpr, m -> true);
+ VolcanoRuleMatch match = ruleQueue.popMatch(category);
+ while (match != null) {
+ tasks.push(new ApplyRule(match, group, exploring));
+ match = ruleQueue.popMatch(category);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("exploring", exploring);
+ }
+ }
+
+ /**
+ * APPLY_RULE
+ */
+ private class ApplyRule implements GeneratorTask {
+ private final VolcanoRuleMatch match;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRule(VolcanoRuleMatch match, RelSubset group, boolean exploring) {
+ this.match = match;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("match", match).item("exploring", exploring);
+ }
+
+ @Override public void perform() {
+ if (!exploring && !planner.isLogical(match.rel(0)) && !checkLowerBound()) {
+ // for implementation and enforcing rules,
+ // we can skip rule match by checking the lower bound
+ // however, we cannot decide LB for logical nodes,
+ // so we only check enforcing rules now
+ if (!group.getTraitSet().satisfies(match.rels[0].getTraitSet())) {
+ // the match cannot be discarded directly
+ // because of another subset's upper bound
+ ruleQueue.addMatch(match);
+ }
+ return;
+ }
+
+ applyGenerator(this, match::onMatch);
+ }
+
+ private boolean checkLowerBound() {
+ RelOptCost upperBound = group.upperBound;
+ if (upperBound.isInfinite()) {
+ return true;
+ }
+ RelOptCost lb = planner.getLowerBound(match);
+ if (upperBound.isLe(lb)) {
+ if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug(
+ "Skip because of lower bound. LB = {}, UP = {}",
+ lb, upperBound);
+ }
+ return false;
+ }
+ return true;
+ }
+
+ @Override public RelSubset group() {
+ return group;
+ }
+
+ @Override public boolean exploring() {
+ return exploring;
+ }
+ }
+
+ private Task getOptimizeInputTask(RelNode rel, RelSubset group) {
+ if (!rel.getTraitSet().satisfies(group.getTraitSet())) {
+ RelNode passThroughRel = convert(rel, group);
+ if (passThroughRel == null) {
+ if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug("Skip optimizing because of traits: {}", rel);
+ }
+ return null;
+ }
+ final RelNode finalPassThroughRel = passThroughRel;
+ applyGenerator(null, () ->
+ planner.register(finalPassThroughRel, group));
+ rel = passThroughRel;
+ }
+ boolean unProcess = false;
+ for (RelNode input : rel.getInputs()) {
+ RelOptCost winner = ((RelSubset) input).getWinnerCost();
+ if (winner == null) {
+ unProcess = true;
+ break;
+ }
+ }
+ if (!unProcess) {
+ return new DeriveTrait(rel, group);
+ }
+ if (rel.getInputs().size() == 1) {
+ return new OptimizeInput1(rel, group);
+ }
+ return new OptimizeInputs(rel, group);
+ }
+
+ private RelNode convert(RelNode rel, RelSubset group) {
+ if (!passThroughCache.contains(rel)) {
+ RelNode passThrough = group.passThrough(rel);
+ if (passThrough != null) {
+ passThroughCache.add(passThrough);
+ return passThrough;
+ }
+ }
+ VolcanoRuleMatch match = ruleQueue.popMatch(
+ Pair.of(rel,
+ m -> m.getRule() instanceof ConverterRule
+ && m.getRule().getOutTrait().satisfies(group.getTraitSet().getConvention())));
+ if (match != null) {
+ tasks.add(new ApplyRule(match, group, false));
+ }
+ return null;
+ }
+
+ /**
+ * O_INPUT when there is only one input
+ */
+ private class OptimizeInput1 implements Task {
+
+ private final RelNode mExpr;
+ private final RelSubset group;
+
+ OptimizeInput1(RelNode mExpr, RelSubset group) {
+ this.mExpr = mExpr;
+ this.group = group;
+ }
+
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("upperBound", group.upperBound);
+ }
+
+ @Override public void perform() {
+ RelOptCost upperBound = group.upperBound;
+ RelOptCost upperForInput = planner.upperBoundForInputs(mExpr, upperBound);
+ if (upperForInput.isLe(planner.zeroCost)) {
+ if (LOGGER.isDebugEnabled()) {
Review comment:
All the check `if (LOGGER.isDebugEnabled()) {` in this class are redundant.
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
Review comment:
Currently every time we add a new relnode through rule transformation, the whole metadata cache will be invalidated, which is not helpful for caching lower bound value.
##########
File path: core/src/main/java/org/apache/calcite/rel/metadata/RelMdLowerBoundCost.java
##########
@@ -0,0 +1,119 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.plan.Convention;
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.volcano.AbstractConverter;
+import org.apache.calcite.plan.volcano.RelSubset;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.metadata.BuiltInMetadata.LowerBoundCost;
+import org.apache.calcite.util.BuiltInMethod;
+
+/**
+ * Default implementations of the
+ * {@link BuiltInMetadata.LowerBoundCost}
+ * metadata provider for the standard algebra.
+ */
+public class RelMdLowerBoundCost implements MetadataHandler<LowerBoundCost> {
+
+ public static final RelMetadataProvider SOURCE =
+ ReflectiveRelMetadataProvider.reflectiveSource(
+ new RelMdLowerBoundCost(), BuiltInMethod.LOWER_BOUND_COST.method);
+
+ //~ Constructors -----------------------------------------------------------
+
+ protected RelMdLowerBoundCost() {}
+
+ //~ Methods ----------------------------------------------------------------
+
+ public MetadataDef<LowerBoundCost> getDef() {
+ return BuiltInMetadata.LowerBoundCost.DEF;
+ }
+
+ private boolean isLogical(RelNode relNode) {
+ return relNode.getTraitSet().getTrait(ConventionTraitDef.INSTANCE)
+ == Convention.NONE;
+ }
+
+ public RelOptCost getLowerBoundCost(RelSubset subset,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+
+ if (isLogical(subset)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost winner = subset.getWinnerCost();
+ if (winner != null) {
+ // when this subset is fully optimized, just return the winner
+ return winner;
+ }
+
+ // if group is not fully explored. Its properties like cardinality
+ // would get changed after exploration. So it cannot return a valid LB
+ if (!subset.isExplored()) {
+ return null;
+ }
+
+ RelOptCost lowerBound = null;
+ for (RelNode relNode : subset.getRels()) {
+ try {
+ RelOptCost lb = mq.getLowerBoundCost(relNode, planner);
+ if (lb == null) {
+ return null;
+ }
+ if (lowerBound == null || lb.isLt(lowerBound)) {
+ lowerBound = lb;
+ }
+ } catch (CyclicMetadataException e) {
+ if (lowerBound == null) {
+ // a cyclic metadata query means this node has an INF LB
+ lowerBound = planner.getCostFactory().makeInfiniteCost();
+ }
+ }
+ }
+ return lowerBound;
+ }
+
+ public RelOptCost getLowerBoundCost(RelNode node,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ if (isLogical(node)) {
+ // currently only support physical, will improve in the future
+ return null;
+ }
+
+ RelOptCost selfCost = node.computeSelfCost(planner, mq);
+ if (selfCost.isInfinite()) {
+ selfCost = null;
+ }
+ for (RelNode input : node.getInputs()) {
+ RelOptCost lb = mq.getLowerBoundCost(input, planner);
+ if (lb != null) {
+ selfCost = selfCost == null ? lb : selfCost.plus(lb);
+ }
+ }
+ return selfCost;
+ }
+
+ public RelOptCost getLowerBoundCost(AbstractConverter ac,
+ RelMetadataQuery mq, RelOptPlanner planner) {
+ return mq.getLowerBoundCost(ac.getInput(), planner);
Review comment:
Nah, once you add it, it will be hard to remove it and will always maintain it. Let's remove it.
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java
##########
@@ -0,0 +1,928 @@
+/*
+ * 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.calcite.plan.volcano;
+
+import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.DeriveMode;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelTrait;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.PhysicalNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.trace.CalciteTrace;
+
+import org.slf4j.Logger;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.function.Predicate;
+
+class TopDownRuleDriver implements RuleDriver {
+
+ /**
+ * the Logger
+ */
+ private static final Logger LOGGER = CalciteTrace.getPlannerTaskTracer();
+
+ /**
+ * The planner
+ */
+ private final VolcanoPlanner planner;
+
+ /**
+ * the rule queue designed for top-down rule applying
+ */
+ private final CascadesRuleQueue ruleQueue;
+
+ /**
+ * all tasks waiting for execution
+ */
+ private Stack<Task> tasks = new Stack<>();
+
+ /**
+ * A task that is currently applying and may generate new RelNode.
+ * It provides a callback to schedule tasks for new RelNodes that
+ * are registered during task performing
+ */
+ private GeneratorTask applying = null;
+
+ /**
+ * relnodes that are generated by passThrough or derive
+ * these nodes will not takes part in another passThrough or derive
+ */
+ private Set<RelNode> passThroughCache = new HashSet<>();
+
+ //~ Constructors -----------------------------------------------------------
+
+ TopDownRuleDriver(VolcanoPlanner planner) {
+ this.planner = planner;
+ ruleQueue = new CascadesRuleQueue(planner);
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ @Override public void drive() {
+ TaskDescriptor description = new TaskDescriptor();
+ tasks.push(new OptimizeGroup(planner.root, planner.infCost));
+ exploreMaterializationRoots();
+ while (!tasks.isEmpty()) {
+ Task task = tasks.pop();
+ description.log(task);
+ task.perform();
+ }
+ }
+
+ private void exploreMaterializationRoots() {
+ for (RelSubset extraRoot : planner.explorationRoots) {
+ RelSet rootSet = VolcanoPlanner.equivRoot(extraRoot.set);
+ if (rootSet == planner.root.set) {
+ continue;
+ }
+ for (RelNode rel : extraRoot.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, extraRoot, true));
+ }
+ }
+ }
+ }
+
+ @Override public CascadesRuleQueue getRuleQueue() {
+ return ruleQueue;
+ }
+
+ @Override public void clear() {
+ ruleQueue.clear();
+ tasks.clear();
+ passThroughCache.clear();
+ applying = null;
+ }
+
+ private interface Procedure {
+ void exec();
+ }
+
+ private void applyGenerator(GeneratorTask task, Procedure proc) {
+ GeneratorTask applying = this.applying;
+ this.applying = task;
+ try {
+ proc.exec();
+ } finally {
+ this.applying = applying;
+ }
+ }
+
+ public void onSetMerged(RelSet set) {
+ applyGenerator(null, () -> clearProcessed(set));
+ }
+
+ private void clearProcessed(RelSet set) {
+ boolean explored = set.exploringState != null;
+ set.exploringState = null;
+
+ for (RelSubset subset : set.subsets) {
+ if (subset.resetOptimizing() || explored) {
+ Collection<RelNode> parentRels = subset.getParentRels();
+ for (RelNode parentRel : parentRels) {
+ clearProcessed(planner.getSet(parentRel));
+ }
+ if (subset == planner.root) {
+ tasks.push(new OptimizeGroup(subset, planner.infCost));
+ }
+ }
+ }
+ }
+
+ public void onProduce(RelNode node, RelSubset subset) {
+ if (applying == null || subset.set
+ != VolcanoPlanner.equivRoot(applying.group().set)) {
+ return;
+ }
+
+ if (!applying.onProduce(node)) {
+ return;
+ }
+
+ if (!planner.isLogical(node)) {
+ RelSubset optimizingGroup = null;
+ boolean canPassThrough = node instanceof PhysicalNode
+ && !passThroughCache.contains(node);
+ if (!canPassThrough && subset.taskState != null) {
+ optimizingGroup = subset;
+ } else {
+ RelOptCost upperBound = planner.zeroCost;
+ RelSet set = subset.getSet();
+ List<RelSubset> subsetsToPassThrough = new ArrayList<>();
+ for (RelSubset otherSubset : set.subsets) {
+ if (!otherSubset.isRequired() || otherSubset != planner.root
+ && otherSubset.taskState != RelSubset.OptimizeState.OPTIMIZING) {
+ continue;
+ }
+ if (node.getTraitSet().satisfies(otherSubset.getTraitSet())) {
+ if (upperBound.isLt(otherSubset.upperBound)) {
+ upperBound = otherSubset.upperBound;
+ optimizingGroup = otherSubset;
+ }
+ } else if (canPassThrough) {
+ subsetsToPassThrough.add(otherSubset);
+ }
+ }
+ for (RelSubset otherSubset : subsetsToPassThrough) {
+ Task task = getOptimizeInputTask(node, otherSubset);
+ if (task != null) {
+ tasks.push(task);
+ }
+ }
+ }
+ if (optimizingGroup == null) {
+ return;
+ }
+ Task task = getOptimizeInputTask(node, optimizingGroup);
+ if (task != null) {
+ tasks.push(task);
+ }
+ } else {
+ boolean optimizing = subset.set.subsets.stream()
+ .anyMatch(s -> s.taskState == RelSubset.OptimizeState.OPTIMIZING);
+ tasks.push(
+ new OptimizeMExpr(node, applying.group(),
+ applying.exploring() && !optimizing));
+ }
+ }
+
+ //~ Inner Classes ----------------------------------------------------------
+
+ /**
+ * Base class for planner task
+ */
+ private interface Task {
+ void perform();
+ void describe(TaskDescriptor desc);
+ }
+
+ /**
+ * A class for task logging
+ */
+ private static class TaskDescriptor {
+ private boolean first = true;
+ private StringBuilder builder = new StringBuilder();
+
+ void log(Task task) {
+ if (!LOGGER.isDebugEnabled()) {
+ return;
+ }
+ first = true;
+ builder.setLength(0);
+ builder.append("Execute task: ").append(task.getClass().getSimpleName());
+ task.describe(this);
+ if (!first) {
+ builder.append(")");
+ }
+
+ LOGGER.info(builder.toString());
+ }
+
+ TaskDescriptor item(String name, Object value) {
+ if (first) {
+ first = false;
+ builder.append("(");
+ } else {
+ builder.append(", ");
+ }
+ builder.append(name).append("=").append(value);
+ return this;
+ }
+ }
+
+ private interface GeneratorTask extends Task {
+ RelSubset group();
+ boolean exploring();
+ default boolean onProduce(RelNode node) {
+ return true;
+ }
+ }
+
+ /**
+ * O_GROUP
+ */
+ private class OptimizeGroup implements Task {
+ private final RelSubset group;
+ private RelOptCost upperBound;
+
+ OptimizeGroup(RelSubset group, RelOptCost upperBound) {
+ this.group = group;
+ this.upperBound = upperBound;
+ }
+
+ @Override public void perform() {
+ RelOptCost winner = group.getWinnerCost();
+ if (winner != null) {
+ return;
+ }
+
+ if (group.taskState != null && upperBound.isLe(group.upperBound)) {
+ // this group failed to optimize before or it is a ring
+ return;
+ }
+
+ group.startOptimize(upperBound);
+
+ // cannot decide an actual lower bound before MExpr are fully explored
+ // so delay the lower bound checking
+
+ // a gate keeper to update context
+ tasks.push(new GroupOptimized(group));
+
+ // optimize mExprs in group
+ List<RelNode> physicals = new ArrayList<>();
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, false));
+ } else if (rel.isEnforcer()) {
+ // Enforcers have lower priority than other physical nodes
+ physicals.add(0, rel);
+ } else {
+ physicals.add(rel);
+ }
+ }
+ // always apply O_INPUTS first so as to get an valid upper bound
+ for (RelNode rel : physicals) {
+ Task task = getOptimizeInputTask(rel, group);
+ if (task != null) {
+ tasks.add(task);
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group).item("upperBound", upperBound);
+ }
+ }
+
+ /**
+ * Mark the group optimized
+ */
+ private static class GroupOptimized implements Task {
+ private final RelSubset group;
+
+ GroupOptimized(RelSubset group) {
+ this.group = group;
+ }
+
+ @Override public void perform() {
+ group.optimized();
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * O_EXPR
+ */
+ private class OptimizeMExpr implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean explore;
+
+ OptimizeMExpr(RelNode mExpr,
+ RelSubset group, boolean explore) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.explore = explore;
+ }
+
+ @Override public void perform() {
+ if (explore && group.isExplored()) {
+ return;
+ }
+ // 1. explode input
+ // 2. apply other rules
+ tasks.push(new ApplyRules(mExpr, group, explore));
+ for (int i = mExpr.getInputs().size() - 1; i >= 0; --i) {
+ tasks.push(new ExploreInput(mExpr, i));
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("explore", explore);
+ }
+ }
+
+ /**
+ * ensure ExploreInput are working on the correct input group since calcite
+ * may merge sets
+ */
+ private class EnsureGroupExplored implements Task {
+
+ private final RelSubset input;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ EnsureGroupExplored(RelSubset input, RelNode parent, int inputOrdinal) {
+ this.input = input;
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (parent.getInput(inputOrdinal) != input) {
+ tasks.push(new ExploreInput(parent, inputOrdinal));
+ return;
+ }
+ input.setExplored();
+ for (RelSubset subset : input.getSet().subsets) {
+ // clear the LB cache as exploring state have changed
+ input.getCluster().getMetadataQuery().clearCache(subset);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", parent).item("i", inputOrdinal);
+ }
+ }
+
+ /**
+ * E_GROUP
+ */
+ private class ExploreInput implements Task {
+ private final RelSubset group;
+ private final RelNode parent;
+ private final int inputOrdinal;
+
+ ExploreInput(RelNode parent, int inputOrdinal) {
+ this.group = (RelSubset) parent.getInput(inputOrdinal);
+ this.parent = parent;
+ this.inputOrdinal = inputOrdinal;
+ }
+
+ @Override public void perform() {
+ if (!group.explore()) {
+ return;
+ }
+ tasks.push(new EnsureGroupExplored(group, parent, inputOrdinal));
+ for (RelNode rel : group.set.rels) {
+ if (planner.isLogical(rel)) {
+ tasks.push(new OptimizeMExpr(rel, group, true));
+ }
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("group", group);
+ }
+ }
+
+ /**
+ * extract rule matches from rule queue and add them to task stack
+ */
+ private class ApplyRules implements Task {
+ private final RelNode mExpr;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRules(RelNode mExpr, RelSubset group, boolean exploring) {
+ this.mExpr = mExpr;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void perform() {
+ Pair<RelNode, Predicate<VolcanoRuleMatch>> category =
+ exploring ? Pair.of(mExpr, planner::isTransformationRule)
+ : Pair.of(mExpr, m -> true);
+ VolcanoRuleMatch match = ruleQueue.popMatch(category);
+ while (match != null) {
+ tasks.push(new ApplyRule(match, group, exploring));
+ match = ruleQueue.popMatch(category);
+ }
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("mExpr", mExpr).item("exploring", exploring);
+ }
+ }
+
+ /**
+ * APPLY_RULE
+ */
+ private class ApplyRule implements GeneratorTask {
+ private final VolcanoRuleMatch match;
+ private final RelSubset group;
+ private final boolean exploring;
+
+ ApplyRule(VolcanoRuleMatch match, RelSubset group, boolean exploring) {
+ this.match = match;
+ this.group = group;
+ this.exploring = exploring;
+ }
+
+ @Override public void describe(TaskDescriptor desc) {
+ desc.item("match", match).item("exploring", exploring);
+ }
+
+ @Override public void perform() {
+ if (!exploring && !planner.isLogical(match.rel(0)) && !checkLowerBound()) {
+ // for implementation and enforcing rules,
+ // we can skip rule match by checking the lower bound
+ // however, we cannot decide LB for logical nodes,
+ // so we only check enforcing rules now
+ if (!group.getTraitSet().satisfies(match.rels[0].getTraitSet())) {
+ // the match cannot be discarded directly
+ // because of another subset's upper bound
+ ruleQueue.addMatch(match);
+ }
+ return;
+ }
+
+ applyGenerator(this, match::onMatch);
+ }
+
+ private boolean checkLowerBound() {
+ RelOptCost upperBound = group.upperBound;
+ if (upperBound.isInfinite()) {
+ return true;
+ }
+ RelOptCost lb = planner.getLowerBound(match);
+ if (upperBound.isLe(lb)) {
+ if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug(
+ "Skip because of lower bound. LB = {}, UP = {}",
+ lb, upperBound);
+ }
+ return false;
+ }
+ return true;
+ }
+
+ @Override public RelSubset group() {
+ return group;
+ }
+
+ @Override public boolean exploring() {
+ return exploring;
+ }
+ }
+
+ private Task getOptimizeInputTask(RelNode rel, RelSubset group) {
+ if (!rel.getTraitSet().satisfies(group.getTraitSet())) {
+ RelNode passThroughRel = convert(rel, group);
+ if (passThroughRel == null) {
+ if (LOGGER.isDebugEnabled()) {
Review comment:
The check `if (LOGGER.isDebugEnabled()) {` is redundant.
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
##########
@@ -839,6 +806,67 @@ RelNode changeTraitsUsingConverters(
prunedNodes.add(rel);
}
+
+ /** Returns whether to skip a match. This happens if any of the
+ * {@link RelNode}s have importance zero. */
+ boolean skipMatch(VolcanoRuleMatch match) {
Review comment:
Why not let RuleQueue be an Abstract class, and put these methods there?
##########
File path: core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
##########
@@ -1396,6 +1437,103 @@ public void setLocked(boolean locked) {
this.locked = locked;
}
+ /**
+ * decide whether a rule is logical or not
+ * @param rel the specific rel node
+ * @return true if the relnode is a logical node
+ */
+ public boolean isLogical(RelNode rel) {
+ return !(rel instanceof PhysicalNode)
+ && rel.getConvention() != rootConvention;
+ }
+
+ /**
+ * check whether a rule match is a substitute rule match
+ * @param match the rule match to check
+ * @return true if the rule match is a substitute rule match
+ */
+ protected boolean isSubstituteRule(VolcanoRuleCall match) {
+ return match.getRule() instanceof SubstitutionRule;
+ }
+
+ /**
+ * check whether a rule match is a transformation rule match
+ * @param match the rule match to check
+ * @return true if the rule match is a transformation rule match
+ */
+ protected boolean isTransformationRule(VolcanoRuleCall match) {
+ if (match.getRule() instanceof SubstitutionRule) {
+ return true;
+ }
+ if (match.getRule() instanceof ConverterRule
+ && match.getRule().getOutTrait() == rootConvention) {
+ return false;
+ }
+ return match.getRule().getOperand().trait == Convention.NONE
+ || match.getRule().getOperand().trait == null;
+ }
+
+
+ /**
+ * gets the lower bound cost of a relational operator
+ * @param rel the rel node
+ * @return the lower bound cost of the given rel. The value is ensured NOT NULL.
+ */
+ protected RelOptCost getLowerBound(RelNode rel) {
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RelOptCost lowerBound = mq.getLowerBoundCost(rel, this);
+ if (lowerBound == null) {
+ return zeroCost;
+ }
+ return lowerBound;
+ }
+
+ /**
+ * Gets the lower bound cost of a RelOptRuleCall.
+ * A match match with inputs whose Sum(LB) is higher than upper bound
+ * needs not to be applied
+ */
+ protected RelOptCost getLowerBound(RelOptRuleCall match) {
+ return getLowerBoundInternal(match, match.getOperand0());
+ }
+
+ private RelOptCost getLowerBoundInternal(
+ RelOptRuleCall match, RelOptRuleOperand op) {
+ List<RelOptRuleOperand> children = op.getChildOperands();
+ if (children == null || children.isEmpty()) {
+ RelNode rel = match.rel(op.ordinalInRule);
+ RelOptCost sum = zeroCost;
+ for (RelNode input : rel.getInputs()) {
+ RelOptCost lb = getLowerBound(input);
+ sum = sum == zeroCost ? lb : sum.plus(lb);
+ }
+ return sum;
+ }
+ RelOptCost sum = null;
+ for (RelOptRuleOperand child : children) {
+ RelOptCost lb = getLowerBoundInternal(match, child);
+ sum = sum == null ? lb : sum.plus(lb);
+ }
+ return sum;
+ }
+
+ /**
+ * Gets the upper bound of its inputs.
+ * Allow users to overwrite this method as some implementations may have
+ * different cost model on some RelNodes, like Spool.
+ */
+ protected RelOptCost upperBoundForInputs(
+ RelNode mExpr, RelOptCost upperBound) {
+ if (!upperBound.isInfinite()) {
+ RelOptCost rootCost = mExpr.computeSelfCost(this,
Review comment:
computeSelfCost is deprecated...
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org