RelOptRule.java
/*
* 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;
import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.convert.Converter;
import org.apache.calcite.rel.convert.ConverterRule;
import org.apache.calcite.rel.core.RelFactories;
import org.apache.calcite.tools.RelBuilderFactory;
import org.apache.calcite.util.Util;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Lists;
import org.checkerframework.checker.initialization.qual.UnderInitialization;
import org.checkerframework.checker.nullness.qual.Nullable;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Predicate;
import static java.util.Objects.requireNonNull;
/**
* A <code>RelOptRule</code> transforms an expression into another. It has a
* list of {@link RelOptRuleOperand}s, which determine whether the rule can be
* applied to a particular section of the tree.
*
* <p>The optimizer figures out which rules are applicable, then calls
* {@link #onMatch} on each of them.
*/
public abstract class RelOptRule {
//~ Static fields/initializers ---------------------------------------------
//~ Instance fields --------------------------------------------------------
/**
* Description of rule, must be unique within planner. Default is the name
* of the class sans package name, but derived classes are encouraged to
* override.
*/
protected final String description;
/**
* Root of operand tree.
*/
private final RelOptRuleOperand operand;
/** Factory for a builder for relational expressions.
*
* <p>The actual builder is available via {@link RelOptRuleCall#builder()}. */
public final RelBuilderFactory relBuilderFactory;
/**
* Flattened list of operands.
*/
public final List<RelOptRuleOperand> operands;
//~ Constructors -----------------------------------------------------------
/**
* Creates a rule.
*
* @param operand root operand, must not be null
*/
protected RelOptRule(RelOptRuleOperand operand) {
this(operand, RelFactories.LOGICAL_BUILDER, null);
}
/**
* Creates a rule with an explicit description.
*
* @param operand root operand, must not be null
* @param description Description, or null to guess description
*/
protected RelOptRule(RelOptRuleOperand operand, String description) {
this(operand, RelFactories.LOGICAL_BUILDER, description);
}
/**
* Creates a rule with an explicit description.
*
* @param operand root operand, must not be null
* @param description Description, or null to guess description
* @param relBuilderFactory Builder for relational expressions
*/
protected RelOptRule(RelOptRuleOperand operand,
RelBuilderFactory relBuilderFactory, @Nullable String description) {
this.operand = requireNonNull(operand, "operand");
this.relBuilderFactory =
requireNonNull(relBuilderFactory, "relBuilderFactory");
if (description == null) {
description = guessDescription(getClass().getName());
}
if (!description.matches("[A-Za-z][-A-Za-z0-9_.(),\\[\\]\\s:]*")) {
throw new RuntimeException("Rule description '" + description
+ "' is not valid");
}
this.description = description;
this.operands = flattenOperands(operand);
assignSolveOrder(operands);
}
//~ Methods for creating operands ------------------------------------------
/**
* Creates an operand that matches a relational expression that has no
* children.
*
* @param clazz Class of relational expression to match (must not be null)
* @param operandList Child operands
* @param <R> Class of relational expression to match
* @return Operand that matches a relational expression that has no
* children
*
* @deprecated Use {@link RelRule.OperandBuilder#operand(Class)}
*/
@Deprecated // to be removed before 2.0
public static <R extends RelNode> RelOptRuleOperand operand(
Class<R> clazz,
RelOptRuleOperandChildren operandList) {
return new RelOptRuleOperand(clazz, null, r -> true,
operandList.policy, operandList.operands);
}
/**
* Creates an operand that matches a relational expression that has no
* children.
*
* @param clazz Class of relational expression to match (must not be null)
* @param trait Trait to match, or null to match any trait
* @param operandList Child operands
* @param <R> Class of relational expression to match
* @return Operand that matches a relational expression that has no
* children
*
* @deprecated Use {@link RelRule.OperandBuilder#operand(Class)}
*/
@Deprecated // to be removed before 2.0
public static <R extends RelNode> RelOptRuleOperand operand(
Class<R> clazz,
RelTrait trait,
RelOptRuleOperandChildren operandList) {
return new RelOptRuleOperand(clazz, trait, r -> true,
operandList.policy, operandList.operands);
}
/**
* Creates an operand that matches a relational expression that has a
* particular trait and predicate.
*
* @param clazz Class of relational expression to match (must not be null)
* @param trait Trait to match, or null to match any trait
* @param predicate Additional match predicate
* @param operandList Child operands
* @param <R> Class of relational expression to match
* @return Operand that matches a relational expression that has a
* particular trait and predicate
*
* @deprecated Use {@link RelRule.OperandBuilder#operand(Class)}
*/
@Deprecated // to be removed before 2.0
public static <R extends RelNode> RelOptRuleOperand operandJ(
Class<R> clazz,
RelTrait trait,
Predicate<? super R> predicate,
RelOptRuleOperandChildren operandList) {
return new RelOptRuleOperand(clazz, trait, predicate, operandList.policy,
operandList.operands);
}
// CHECKSTYLE: IGNORE 1
/** @deprecated Use {@link #operandJ} */
@SuppressWarnings("Guava")
@Deprecated // to be removed before 2.0
public static <R extends RelNode> RelOptRuleOperand operand(
Class<R> clazz,
RelTrait trait,
com.google.common.base.Predicate<? super R> predicate,
RelOptRuleOperandChildren operandList) {
return operandJ(clazz, trait, (Predicate<? super R>) predicate::apply,
operandList);
}
/**
* Creates an operand that matches a relational expression that has no
* children.
*
* @param clazz Class of relational expression to match (must not be null)
* @param trait Trait to match, or null to match any trait
* @param predicate Additional match predicate
* @param first First operand
* @param rest Rest operands
* @param <R> Class of relational expression to match
* @return Operand
*
* @deprecated Use {@link RelRule.OperandBuilder#operand(Class)}
*/
@Deprecated // to be removed before 2.0
public static <R extends RelNode> RelOptRuleOperand operandJ(
Class<R> clazz,
RelTrait trait,
Predicate<? super R> predicate,
RelOptRuleOperand first,
RelOptRuleOperand... rest) {
return operandJ(clazz, trait, predicate, some(first, rest));
}
@SuppressWarnings("Guava")
@Deprecated // to be removed before 2.0
public static <R extends RelNode> RelOptRuleOperand operand(
Class<R> clazz,
RelTrait trait,
com.google.common.base.Predicate<? super R> predicate,
RelOptRuleOperand first,
RelOptRuleOperand... rest) {
return operandJ(clazz, trait, (Predicate<? super R>) predicate::apply,
first, rest);
}
/**
* Creates an operand that matches a relational expression with a given
* list of children.
*
* <p>Shorthand for <code>operand(clazz, some(...))</code>.
*
* <p>If you wish to match a relational expression that has no children
* (that is, a leaf node), write <code>operand(clazz, none())</code>.
*
* <p>If you wish to match a relational expression that has any number of
* children, write <code>operand(clazz, any())</code>.
*
* @param clazz Class of relational expression to match (must not be null)
* @param first First operand
* @param rest Rest operands
* @param <R> Class of relational expression to match
* @return Operand that matches a relational expression with a given
* list of children
*
* @deprecated Use {@link RelRule.OperandBuilder#operand(Class)}
*/
@Deprecated // to be removed before 2.0
public static <R extends RelNode> RelOptRuleOperand operand(
Class<R> clazz,
RelOptRuleOperand first,
RelOptRuleOperand... rest) {
return operand(clazz, some(first, rest));
}
/**
* Creates an operand for a converter rule.
*
* @param clazz Class of relational expression to match (must not be null)
* @param trait Trait to match, or null to match any trait
* @param predicate Predicate to apply to relational expression
*/
@Deprecated // to be removed before 2.0
protected static <R extends RelNode> ConverterRelOptRuleOperand
convertOperand(Class<R> clazz, Predicate<? super R> predicate,
RelTrait trait) {
return new ConverterRelOptRuleOperand(clazz, trait, predicate);
}
// CHECKSTYLE: IGNORE 1
/** @deprecated Use {@link #convertOperand(Class, Predicate, RelTrait)}. */
@SuppressWarnings("Guava")
@Deprecated // to be removed before 2.0
protected static <R extends RelNode> ConverterRelOptRuleOperand
convertOperand(Class<R> clazz,
com.google.common.base.Predicate<? super R> predicate,
RelTrait trait) {
return new ConverterRelOptRuleOperand(clazz, trait, predicate::apply);
}
//~ Methods for creating lists of child operands ---------------------------
/**
* Creates a list of child operands that matches child relational
* expressions in the order they appear.
*
* @param first First child operand
* @param rest Remaining child operands (may be empty)
* @return List of child operands that matches child relational
* expressions in the order
*
* @deprecated Use {@link RelRule.OperandDetailBuilder#inputs}
*/
@Deprecated // to be removed before 2.0
public static RelOptRuleOperandChildren some(
RelOptRuleOperand first,
RelOptRuleOperand... rest) {
return new RelOptRuleOperandChildren(RelOptRuleOperandChildPolicy.SOME,
Lists.asList(first, rest));
}
/**
* Creates a list of child operands that matches child relational
* expressions in any order.
*
* <p>This is useful when matching a relational expression which
* can have a variable number of children. For example, the rule to
* eliminate empty children of a Union would have operands
*
* <blockquote>Operand(Union, true, Operand(Empty))</blockquote>
*
* <p>and given the relational expressions
*
* <blockquote>Union(LogicalFilter, Empty, LogicalProject)</blockquote>
*
* <p>would fire the rule with arguments
*
* <blockquote>{Union, Empty}</blockquote>
*
* <p>It is up to the rule to deduce the other children, or indeed the
* position of the matched child.
*
* @param first First child operand
* @param rest Remaining child operands (may be empty)
* @return List of child operands that matches child relational
* expressions in any order
*/
@Deprecated // to be removed before 2.0
public static RelOptRuleOperandChildren unordered(
RelOptRuleOperand first,
RelOptRuleOperand... rest) {
return new RelOptRuleOperandChildren(
RelOptRuleOperandChildPolicy.UNORDERED,
Lists.asList(first, rest));
}
/**
* Creates an empty list of child operands.
*
* @return Empty list of child operands
*
* @deprecated Use {@link RelRule.OperandDetailBuilder#noInputs()}
*/
@Deprecated // to be removed before 2.0
public static RelOptRuleOperandChildren none() {
return RelOptRuleOperandChildren.LEAF_CHILDREN;
}
/**
* Creates a list of child operands that signifies that the operand matches
* any number of child relational expressions.
*
* @return List of child operands that signifies that the operand matches
* any number of child relational expressions
*
* @deprecated Use {@link RelRule.OperandDetailBuilder#anyInputs()}
*/
@Deprecated // to be removed before 2.0
public static RelOptRuleOperandChildren any() {
return RelOptRuleOperandChildren.ANY_CHILDREN;
}
//~ Methods ----------------------------------------------------------------
/**
* Creates a flattened list of this operand and its descendants in prefix
* order.
*
* @param rootOperand Root operand
* @return Flattened list of operands
*/
private List<RelOptRuleOperand> flattenOperands(
@UnderInitialization RelOptRule this,
RelOptRuleOperand rootOperand) {
final List<RelOptRuleOperand> operandList = new ArrayList<>();
// Flatten the operands into a list.
rootOperand.setRule(this);
rootOperand.setParent(null);
rootOperand.ordinalInParent = 0;
rootOperand.ordinalInRule = operandList.size();
operandList.add(rootOperand);
flattenRecurse(operandList, rootOperand);
return ImmutableList.copyOf(operandList);
}
/**
* Adds the operand and its descendants to the list in prefix order.
*
* @param operandList Flattened list of operands
* @param parentOperand Parent of this operand
*/
private void flattenRecurse(
@UnderInitialization RelOptRule this,
List<RelOptRuleOperand> operandList,
RelOptRuleOperand parentOperand) {
int k = 0;
for (RelOptRuleOperand operand : parentOperand.getChildOperands()) {
operand.setRule(this);
operand.setParent(parentOperand);
operand.ordinalInParent = k++;
operand.ordinalInRule = operandList.size();
operandList.add(operand);
flattenRecurse(operandList, operand);
}
}
/**
* Builds each operand's solve-order. Start with itself, then its parent, up
* to the root, then the remaining operands in prefix order.
*/
private static void assignSolveOrder(List<RelOptRuleOperand> operands) {
for (RelOptRuleOperand operand : operands) {
operand.solveOrder = new int[operands.size()];
int m = 0;
for (RelOptRuleOperand o = operand; o != null; o = o.getParent()) {
operand.solveOrder[m++] = o.ordinalInRule;
}
for (int k = 0; k < operands.size(); k++) {
boolean exists = false;
for (int n = 0; n < m; n++) {
if (operand.solveOrder[n] == k) {
exists = true;
break;
}
}
if (!exists) {
operand.solveOrder[m++] = k;
}
}
// Assert: operand appears once in the sort-order.
assert m == operands.size();
}
}
/**
* Returns the root operand of this rule.
*
* @return the root operand of this rule
*/
public RelOptRuleOperand getOperand() {
return operand;
}
/**
* Returns a flattened list of operands of this rule.
*
* @return flattened list of operands
*/
public List<RelOptRuleOperand> getOperands() {
return ImmutableList.copyOf(operands);
}
@Override public int hashCode() {
// Conventionally, hashCode() and equals() should use the same
// criteria, whereas here we only look at the description. This is
// okay, because the planner requires all rule instances to have
// distinct descriptions.
return description.hashCode();
}
@Override public boolean equals(@Nullable Object obj) {
return (obj instanceof RelOptRule)
&& equals((RelOptRule) obj);
}
/**
* Returns whether this rule is equal to another rule.
*
* <p>The base implementation checks that the rules have the same class and
* that the operands are equal; derived classes can override.
*
* @param that Another rule
* @return Whether this rule is equal to another rule
*/
@SuppressWarnings("NonOverridingEquals")
protected boolean equals(RelOptRule that) {
// Include operands and class in the equality criteria just in case
// they have chosen a poor description.
return this == that
|| this.getClass() == that.getClass()
&& this.description.equals(that.description)
&& this.operand.equals(that.operand);
}
/**
* Returns whether this rule could possibly match the given operands.
*
* <p>This method is an opportunity to apply side-conditions to a rule. The
* {@link RelOptPlanner} calls this method after matching all operands of
* the rule, and before calling {@link #onMatch(RelOptRuleCall)}.
*
* <p>In implementations of {@link RelOptPlanner} which may queue up a
* matched {@link RelOptRuleCall} for a long time before calling
* {@link #onMatch(RelOptRuleCall)}, this method is beneficial because it
* allows the planner to discard rules earlier in the process.
*
* <p>The default implementation of this method returns <code>true</code>.
* It is acceptable for any implementation of this method to give a false
* positives, that is, to say that the rule matches the operands but have
* {@link #onMatch(RelOptRuleCall)} subsequently not generate any
* successors.
*
* <p>The following script is useful to identify rules which commonly
* produce no successors. You should override this method for these rules:
*
* <blockquote>
* <pre><code>awk '
* /Apply rule/ {rule=$4; ruleCount[rule]++;}
* /generated 0 successors/ {ruleMiss[rule]++;}
* END {
* printf "%-30s %s %s\n", "Rule", "Fire", "Miss";
* for (i in ruleCount) {
* printf "%-30s %5d %5d\n", i, ruleCount[i], ruleMiss[i];
* }
* } ' FarragoTrace.log</code></pre>
* </blockquote>
*
* @param call Rule call which has been determined to match all operands of
* this rule
* @return whether this RelOptRule matches a given RelOptRuleCall
*/
public boolean matches(RelOptRuleCall call) {
return true;
}
/**
* Receives notification about a rule match. At the time that this method is
* called, {@link RelOptRuleCall#rels call.rels} holds the set of relational
* expressions which match the operands to the rule; <code>
* call.rels[0]</code> is the root expression.
*
* <p>Typically a rule would check that the nodes are valid matches, creates
* a new expression, then calls back {@link RelOptRuleCall#transformTo} to
* register the expression.
*
* @param call Rule call
* @see #matches(RelOptRuleCall)
*/
public abstract void onMatch(RelOptRuleCall call);
/**
* Returns the convention of the result of firing this rule, null if
* not known.
*
* @return Convention of the result of firing this rule, null if
* not known
*/
public @Nullable Convention getOutConvention() {
return null;
}
/**
* Returns the trait which will be modified as a result of firing this rule,
* or null if the rule is not a converter rule.
*
* @return Trait which will be modified as a result of firing this rule,
* or null if the rule is not a converter rule
*/
public @Nullable RelTrait getOutTrait() {
return null;
}
/**
* Returns the description of this rule.
*
* <p>It must be unique (for rules that are not equal) and must consist of
* only the characters A-Z, a-z, 0-9, '_', '.', '(', ')', '-', ',', '[', ']', ':', ' '.
* It must start with a letter. */
@Override public final String toString() {
return description;
}
/**
* Converts a relation expression to a given set of traits, if it does not
* already have those traits.
*
* @param rel Relational expression to convert
* @param toTraits desired traits
* @return a relational expression with the desired traits; never null
*/
public static RelNode convert(RelNode rel, RelTraitSet toTraits) {
return convert(rel.getCluster().getPlanner(), rel, toTraits);
}
public static RelNode convert(RelOptPlanner planner, RelNode rel, RelTraitSet toTraits) {
RelTraitSet outTraits = rel.getTraitSet();
for (int i = 0; i < toTraits.size(); i++) {
RelTrait toTrait = toTraits.getTrait(i);
if (toTrait != null) {
outTraits = outTraits.replace(i, toTrait);
}
}
if (rel.getTraitSet().matches(outTraits)) {
return rel;
}
return planner.changeTraits(rel, outTraits);
}
/**
* Converts one trait of a relational expression, if it does not
* already have that trait.
*
* @param rel Relational expression to convert
* @param toTrait Desired trait
* @return a relational expression with the desired trait; never null
*/
public static RelNode convert(RelNode rel, @Nullable RelTrait toTrait) {
return convert(rel.getCluster().getPlanner(), rel, toTrait);
}
public static RelNode convert(RelOptPlanner planner, RelNode rel, @Nullable RelTrait toTrait) {
RelTraitSet outTraits = rel.getTraitSet();
if (toTrait != null) {
outTraits = outTraits.replace(toTrait);
}
if (rel.getTraitSet().matches(outTraits)) {
return rel;
}
return planner.changeTraits(rel, outTraits.simplify());
}
/**
* Converts a list of relational expressions.
*
* @param rels Relational expressions
* @param trait Trait to add to each relational expression
* @return List of converted relational expressions, never null
*/
protected static List<RelNode> convertList(List<RelNode> rels,
final RelTrait trait) {
return Util.transform(rels,
rel -> convert(rel, rel.getTraitSet().replace(trait)));
}
/**
* Deduces a name for a rule by taking the name of its class and returning
* the segment after the last '.' or '$'.
*
* <p>Examples:
* <ul>
* <li>"com.foo.Bar" yields "Bar";</li>
* <li>"com.flatten.Bar$Baz" yields "Baz";</li>
* <li>"com.foo.Bar$1" yields "1" (which as an integer is an invalid
* name, and writer of the rule is encouraged to give it an
* explicit name).</li>
* </ul>
*
* @param className Name of the rule's class
* @return Last segment of the class
*/
static String guessDescription(String className) {
String description = className;
int punc =
Math.max(
className.lastIndexOf('.'),
className.lastIndexOf('$'));
if (punc >= 0) {
description = className.substring(punc + 1);
}
if (description.matches("[0-9]+")) {
throw new RuntimeException("Derived description of rule class "
+ className + " is an integer, not valid. "
+ "Supply a description manually.");
}
return description;
}
/**
* Operand to an instance of the converter rule.
*/
protected static class ConverterRelOptRuleOperand extends RelOptRuleOperand {
<R extends RelNode> ConverterRelOptRuleOperand(Class<R> clazz, RelTrait in,
Predicate<? super R> predicate) {
super(clazz, in, predicate, RelOptRuleOperandChildPolicy.ANY,
ImmutableList.of());
}
@Override public boolean matches(RelNode rel) {
// Don't apply converters to converters that operate
// on the same RelTraitDef -- otherwise we get
// an n^2 effect.
if (rel instanceof Converter) {
if (((ConverterRule) getRule()).getTraitDef()
== ((Converter) rel).getTraitDef()) {
return false;
}
}
return super.matches(rel);
}
}
}