This is an automated email from the ASF dual-hosted git repository.
hyuan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/master by this push:
new 08f4a98 [CALCITE-3886] Execute substitution rule according to the
order they get matched
08f4a98 is described below
commit 08f4a9889728f94903ff424ed9c20d940b821af5
Author: Haisheng Yuan <h.y...@alibaba-inc.com>
AuthorDate: Sat Mar 28 16:45:43 2020 -0500
[CALCITE-3886] Execute substitution rule according to the order they get
matched
Currently the substitution rule is always appended to the head of the
queue. We
prefer to executing the rule according to the order they get matched. So we
need a separate queue for substitution rule matches.
---
.../org/apache/calcite/plan/SubstitutionRule.java | 15 +++++++-
.../org/apache/calcite/plan/volcano/RuleQueue.java | 45 ++++++++++++++++------
.../calcite/plan/volcano/VolcanoRuleCall.java | 3 +-
.../calcite/rel/rules/AggregateRemoveRule.java | 1 +
.../apache/calcite/rel/rules/PruneEmptyRules.java | 38 ++++++++++++++----
5 files changed, 80 insertions(+), 22 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/plan/SubstitutionRule.java
b/core/src/main/java/org/apache/calcite/plan/SubstitutionRule.java
index a070078..6960f49 100644
--- a/core/src/main/java/org/apache/calcite/plan/SubstitutionRule.java
+++ b/core/src/main/java/org/apache/calcite/plan/SubstitutionRule.java
@@ -18,9 +18,20 @@ package org.apache.calcite.plan;
/**
* A rule that implements this interface indicates that the new RelNode
- * is definitely better than the old one, which will be pruned by setting
- * importance to 0.
+ * is typically better than the old one. All the substitution rules will
+ * be executed first until they are done. The execution order of
+ * substitution rules depends on the match order.
*/
public interface SubstitutionRule {
+ /**
+ * Whether the planner should automatically prune old node when
+ * there is at least 1 equivalent rel generated by the rule.
+ *
+ * <p>Default is false, the user needs to prune the old node
+ * manually in the rule.</p>
+ */
+ default boolean autoPruneOld() {
+ return false;
+ }
}
diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
b/core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
index 34c43ef..4e0da38 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/RuleQueue.java
@@ -34,6 +34,7 @@ import java.util.EnumMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
+import java.util.Queue;
import java.util.Set;
/**
@@ -140,11 +141,7 @@ class RuleQueue {
LOGGER.trace("{} Rule-match queued: {}", matchList.phase.toString(),
matchName);
- if (match.getRule() instanceof SubstitutionRule) {
- matchList.list.offerFirst(match);
- } else {
- matchList.list.offer(match);
- }
+ matchList.offer(match);
matchList.matchMap.put(
planner.getSubset(match.rels[0]), match);
@@ -173,11 +170,11 @@ class RuleQueue {
VolcanoRuleMatch match;
for (;;) {
- if (phaseMatchList.list.isEmpty()) {
+ if (phaseMatchList.size() == 0) {
return null;
}
- match = phaseMatchList.list.poll();
+ match = phaseMatchList.poll();
if (skipMatch(match)) {
LOGGER.debug("Skip match: {}", match);
@@ -272,14 +269,19 @@ class RuleQueue {
final VolcanoPlannerPhase phase;
/**
+ * Rule match queue for SubstitutionRule
+ */
+ private final Queue<VolcanoRuleMatch> preQueue = new LinkedList<>();
+
+ /**
* Current list of VolcanoRuleMatches for this phase. New rule-matches
- * are appended to the end of this list.
+ * are appended to the end of this queue.
* The rules are not sorted in any way.
*/
- final Deque<VolcanoRuleMatch> list = new LinkedList<>();
+ private final Queue<VolcanoRuleMatch> queue = new LinkedList<>();
/**
- * A set of rule-match names contained in {@link #list}. Allows fast
+ * A set of rule-match names contained in {@link #queue}. Allows fast
* detection of duplicate rule-matches.
*/
final Set<String> names = new HashSet<>();
@@ -294,8 +296,29 @@ class RuleQueue {
this.phase = phase;
}
+ int size() {
+ return preQueue.size() + queue.size();
+ }
+
+ VolcanoRuleMatch poll() {
+ VolcanoRuleMatch match = preQueue.poll();
+ if (match == null) {
+ match = queue.poll();
+ }
+ return match;
+ }
+
+ void offer(VolcanoRuleMatch match) {
+ if (match.getRule() instanceof SubstitutionRule) {
+ preQueue.offer(match);
+ } else {
+ queue.offer(match);
+ }
+ }
+
void clear() {
- list.clear();
+ preQueue.clear();
+ queue.clear();
names.clear();
matchMap.clear();
}
diff --git
a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
index 0d7a958..e02d848 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
@@ -140,7 +140,8 @@ public class VolcanoRuleCall extends RelOptRuleCall {
}
}
- if (this.getRule() instanceof SubstitutionRule) {
+ if (this.getRule() instanceof SubstitutionRule
+ && ((SubstitutionRule) getRule()).autoPruneOld()) {
volcanoPlanner.setImportance(rels[0], 0d);
}
diff --git
a/core/src/main/java/org/apache/calcite/rel/rules/AggregateRemoveRule.java
b/core/src/main/java/org/apache/calcite/rel/rules/AggregateRemoveRule.java
index 8f6ac60..bada07c 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/AggregateRemoveRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/AggregateRemoveRule.java
@@ -124,6 +124,7 @@ public class AggregateRemoveRule extends RelOptRule
implements SubstitutionRule
// aggregate functions, add a project for the same effect.
relBuilder.project(relBuilder.fields(aggregate.getGroupSet()));
}
+ call.getPlanner().setImportance(aggregate, 0d);
call.transformTo(relBuilder.build());
}
}
diff --git
a/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java
b/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java
index be76678..1fb6b26 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/PruneEmptyRules.java
@@ -18,6 +18,7 @@ package org.apache.calcite.rel.rules;
import org.apache.calcite.plan.RelOptRule;
import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptRuleOperand;
import org.apache.calcite.plan.RelOptUtil;
import org.apache.calcite.plan.SubstitutionRule;
import org.apache.calcite.plan.hep.HepRelVertex;
@@ -60,10 +61,31 @@ import static org.apache.calcite.plan.RelOptRule.unordered;
*
* @see LogicalValues#createEmpty
*/
-public abstract class PruneEmptyRules implements SubstitutionRule {
+public abstract class PruneEmptyRules {
//~ Static fields/initializers ---------------------------------------------
/**
+ * Abstract prune empty rule that implements SubstitutionRule interface.
+ */
+ protected abstract static class PruneEmptyRule extends RelOptRule
+ implements SubstitutionRule {
+
+ public PruneEmptyRule(final RelOptRuleOperand operand,
+ final String description) {
+ super(operand, description);
+ }
+
+ public PruneEmptyRule(final RelOptRuleOperand operand,
+ final RelBuilderFactory relBuilderFactory, final String description) {
+ super(operand, relBuilderFactory, description);
+ }
+
+ @Override public boolean autoPruneOld() {
+ return true;
+ }
+ }
+
+ /**
* Rule that removes empty children of a
* {@link org.apache.calcite.rel.logical.LogicalUnion}.
*
@@ -76,7 +98,7 @@ public abstract class PruneEmptyRules implements
SubstitutionRule {
* </ul>
*/
public static final RelOptRule UNION_INSTANCE =
- new RelOptRule(
+ new PruneEmptyRule(
operand(LogicalUnion.class,
unordered(operandJ(Values.class, null, Values::isEmpty,
none()))),
"Union") {
@@ -116,7 +138,7 @@ public abstract class PruneEmptyRules implements
SubstitutionRule {
* </ul>
*/
public static final RelOptRule MINUS_INSTANCE =
- new RelOptRule(
+ new PruneEmptyRule(
operand(LogicalMinus.class,
unordered(
operandJ(Values.class, null, Values::isEmpty, none()))),
@@ -162,7 +184,7 @@ public abstract class PruneEmptyRules implements
SubstitutionRule {
* </ul>
*/
public static final RelOptRule INTERSECT_INSTANCE =
- new RelOptRule(
+ new PruneEmptyRule(
operand(LogicalIntersect.class,
unordered(
operandJ(Values.class, null, Values::isEmpty, none()))),
@@ -248,7 +270,7 @@ public abstract class PruneEmptyRules implements
SubstitutionRule {
* </ul>
*/
public static final RelOptRule SORT_FETCH_ZERO_INSTANCE =
- new RelOptRule(
+ new PruneEmptyRule(
operand(Sort.class, any()), "PruneSortLimit0") {
@Override public void onMatch(RelOptRuleCall call) {
Sort sort = call.rel(0);
@@ -294,7 +316,7 @@ public abstract class PruneEmptyRules implements
SubstitutionRule {
* </ul>
*/
public static final RelOptRule JOIN_LEFT_INSTANCE =
- new RelOptRule(
+ new PruneEmptyRule(
operand(Join.class,
some(
operandJ(Values.class, null, Values::isEmpty, none()),
@@ -325,7 +347,7 @@ public abstract class PruneEmptyRules implements
SubstitutionRule {
* </ul>
*/
public static final RelOptRule JOIN_RIGHT_INSTANCE =
- new RelOptRule(
+ new PruneEmptyRule(
operand(Join.class,
some(
operand(RelNode.class, any()),
@@ -349,7 +371,7 @@ public abstract class PruneEmptyRules implements
SubstitutionRule {
/** Planner rule that converts a single-rel (e.g. project, sort, aggregate or
* filter) on top of the empty relational expression into empty. */
- public static class RemoveEmptySingleRule extends RelOptRule {
+ public static class RemoveEmptySingleRule extends PruneEmptyRule {
/** Creates a simple RemoveEmptySingleRule. */
public <R extends SingleRel> RemoveEmptySingleRule(Class<R> clazz,
String description) {
