AbstractRelNode.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.rel;
import org.apache.calcite.plan.Convention;
import org.apache.calcite.plan.ConventionTraitDef;
import org.apache.calcite.plan.RelDigest;
import org.apache.calcite.plan.RelOptCluster;
import org.apache.calcite.plan.RelOptCost;
import org.apache.calcite.plan.RelOptPlanner;
import org.apache.calcite.plan.RelOptTable;
import org.apache.calcite.plan.RelOptUtil;
import org.apache.calcite.plan.RelTraitSet;
import org.apache.calcite.rel.core.CorrelationId;
import org.apache.calcite.rel.hint.Hintable;
import org.apache.calcite.rel.hint.RelHint;
import org.apache.calcite.rel.metadata.Metadata;
import org.apache.calcite.rel.metadata.MetadataFactory;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.rex.RexShuttle;
import org.apache.calcite.runtime.PairList;
import org.apache.calcite.sql.SqlExplainLevel;
import org.apache.calcite.util.Litmus;
import org.apache.calcite.util.Pair;
import org.apache.calcite.util.Util;
import com.google.common.collect.ImmutableSet;
import org.apiguardian.api.API;
import org.checkerframework.checker.initialization.qual.UnknownInitialization;
import org.checkerframework.checker.nullness.qual.MonotonicNonNull;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.checkerframework.dataflow.qual.Pure;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import static com.google.common.base.Preconditions.checkNotNull;
import static java.util.Objects.requireNonNull;
/**
* Base class for every relational expression ({@link RelNode}).
*/
public abstract class AbstractRelNode implements RelNode {
//~ Static fields/initializers ---------------------------------------------
/** Generator for {@link #id} values. */
private static final AtomicInteger NEXT_ID = new AtomicInteger(0);
//~ Instance fields --------------------------------------------------------
/**
* Cached type of this relational expression.
*/
protected @MonotonicNonNull RelDataType rowType;
/**
* The digest that uniquely identifies the node.
*/
@API(since = "1.24", status = API.Status.INTERNAL)
protected final RelDigest digest;
private final RelOptCluster cluster;
/** Unique id of this object, for debugging. */
protected final int id;
/** RelTraitSet that describes the traits of this RelNode. */
protected final RelTraitSet traitSet;
//~ Constructors -----------------------------------------------------------
/**
* Creates an <code>AbstractRelNode</code>.
*/
protected AbstractRelNode(RelOptCluster cluster, RelTraitSet traitSet) {
super();
this.cluster = requireNonNull(cluster, "cluster");
this.traitSet = requireNonNull(traitSet, "traitSet");
this.id = NEXT_ID.getAndIncrement();
this.digest = new InnerRelDigest();
}
//~ Methods ----------------------------------------------------------------
@Override public RelNode copy(RelTraitSet traitSet, List<RelNode> inputs) {
// Note that empty set equals empty set, so relational expressions
// with zero inputs do not generally need to implement their own copy
// method.
if (getInputs().equals(inputs)
&& traitSet == getTraitSet()) {
return this;
}
throw new AssertionError("Relational expression should override copy. "
+ "Class=[" + getClass()
+ "]; traits=[" + getTraitSet()
+ "]; desired traits=[" + traitSet
+ "]");
}
protected static <T> T sole(List<T> collection) {
assert collection.size() == 1;
return collection.get(0);
}
@Override public final RelOptCluster getCluster() {
return cluster;
}
@Pure
@Override public final @Nullable Convention getConvention(
@UnknownInitialization AbstractRelNode this) {
return traitSet == null ? null : traitSet.getTrait(ConventionTraitDef.INSTANCE);
}
@Override public RelTraitSet getTraitSet() {
return traitSet;
}
@Override public @Nullable String getCorrelVariable() {
return null;
}
@Override public int getId() {
return id;
}
@Override public RelNode getInput(int i) {
List<RelNode> inputs = getInputs();
return inputs.get(i);
}
@Override public void register(RelOptPlanner planner) {
Util.discard(planner);
}
// It is not recommended to override this method, but sub-classes can do it at their own risk.
@Override public String getRelTypeName() {
String cn = getClass().getName();
int i = cn.length();
while (--i >= 0) {
if (cn.charAt(i) == '$' || cn.charAt(i) == '.') {
return cn.substring(i + 1);
}
}
return cn;
}
@Override public boolean isValid(Litmus litmus, @Nullable Context context) {
return litmus.succeed();
}
@Override public final RelDataType getRowType() {
if (rowType == null) {
rowType = checkNotNull(deriveRowType(), "null row type for %s", this);
}
return rowType;
}
protected RelDataType deriveRowType() {
// This method is only called if rowType is null, so you don't NEED to
// implement it if rowType is always set.
throw new UnsupportedOperationException();
}
@Override public RelDataType getExpectedInputRowType(int ordinalInParent) {
return getRowType();
}
@Override public List<RelNode> getInputs() {
return Collections.emptyList();
}
@Override public double estimateRowCount(RelMetadataQuery mq) {
return 1.0;
}
@Override public Set<CorrelationId> getVariablesSet() {
return ImmutableSet.of();
}
@Override public void collectVariablesUsed(Set<CorrelationId> variableSet) {
// for default case, nothing to do
}
@Override public boolean isEnforcer() {
return false;
}
@Override public void collectVariablesSet(Set<CorrelationId> variableSet) {
}
@Override public void childrenAccept(RelVisitor visitor) {
List<RelNode> inputs = getInputs();
for (int i = 0; i < inputs.size(); i++) {
visitor.visit(inputs.get(i), i, this);
}
}
@Override public RelNode accept(RelShuttle shuttle) {
// Call fall-back method. Specific logical types (such as LogicalProject
// and LogicalJoin) have their own RelShuttle.visit methods.
return shuttle.visit(this);
}
@Override public RelNode accept(RexShuttle shuttle) {
return this;
}
@Override public @Nullable RelOptCost computeSelfCost(RelOptPlanner planner,
RelMetadataQuery mq) {
// by default, assume cost is proportional to number of rows
double rowCount = mq.getRowCount(this);
return planner.getCostFactory().makeCost(rowCount, rowCount, 0);
}
@Deprecated // to be removed before 2.0
@Override public final <@Nullable M extends @Nullable Metadata> M metadata(Class<M> metadataClass,
RelMetadataQuery mq) {
final MetadataFactory factory = cluster.getMetadataFactory();
final M metadata = factory.query(this, mq, metadataClass);
checkNotNull(metadata, "no provider found (rel=%s, m=%s); "
+ "a backstop provider is recommended", this, metadataClass);
// Usually the metadata belongs to the rel that created it. RelSubset and
// HepRelVertex are notable exceptions, so disable the assertion. It's not
// worth the performance hit to override this method for them.
// assert metadata.rel() == this : "someone else's metadata";
return metadata;
}
@Override public void explain(RelWriter pw) {
explainTerms(pw).done(this);
}
/**
* Describes the inputs and attributes of this relational expression.
* Each node should call {@code super.explainTerms}, then call the
* {@link org.apache.calcite.rel.externalize.RelWriterImpl#input(String, RelNode)}
* and
* {@link RelWriter#item(String, Object)}
* methods for each input and attribute.
*
* @param pw Plan writer
* @return Plan writer for fluent-explain pattern
*/
public RelWriter explainTerms(RelWriter pw) {
return pw;
}
@Override public RelNode onRegister(RelOptPlanner planner) {
List<RelNode> oldInputs = getInputs();
List<RelNode> inputs = new ArrayList<>(oldInputs.size());
for (final RelNode input : oldInputs) {
RelNode e = planner.ensureRegistered(input, null);
assert e == input || RelOptUtil.equal("rowtype of rel before registration",
input.getRowType(),
"rowtype of rel after registration",
e.getRowType(),
Litmus.THROW);
inputs.add(e);
}
RelNode r = this;
if (!Util.equalShallow(oldInputs, inputs)) {
r = copy(getTraitSet(), inputs);
}
r.recomputeDigest();
assert r.isValid(Litmus.THROW, null);
return r;
}
@Override public void recomputeDigest() {
digest.clear();
}
@Override public void replaceInput(
int ordinalInParent,
RelNode p) {
throw new UnsupportedOperationException("replaceInput called on " + this);
}
/** Description; consists of id plus digest. */
@Override public String toString() {
return "rel#" + id + ':' + getDigest();
}
@Deprecated // to be removed before 2.0
@Override public final String getDescription() {
return this.toString();
}
@Override public String getDigest() {
return digest.toString();
}
@Override public final RelDigest getRelDigest() {
return digest;
}
@Override public @Nullable RelOptTable getTable() {
return null;
}
/**
* {@inheritDoc}
*
* <p>This method (and {@link #hashCode} is intentionally final. We do not want
* sub-classes of {@link RelNode} to redefine identity. Various algorithms
* (e.g. visitors, planner) can define the identity as meets their needs.
*/
@Override public final boolean equals(@Nullable Object obj) {
return super.equals(obj);
}
/**
* {@inheritDoc}
*
* <p>This method (and {@link #equals} is intentionally final. We do not want
* sub-classes of {@link RelNode} to redefine identity. Various algorithms
* (e.g. visitors, planner) can define the identity as meets their needs.
*/
@Override public final int hashCode() {
return super.hashCode();
}
/**
* Equality check for RelNode digest.
*
* <p>By default this method collects digest attributes from
* {@link #explainTerms(RelWriter)}, then compares each attribute pair.
* This should work well for most cases. If this method is a performance
* bottleneck for your project, or the default behavior can't handle
* your scenario properly, you can choose to override this method and
* {@link #deepHashCode()}. See {@code LogicalJoin} as an example.
*
* @return Whether the 2 RelNodes are equivalent or have the same digest.
* @see #deepHashCode()
*/
@API(since = "1.25", status = API.Status.MAINTAINED)
@Override public boolean deepEquals(@Nullable Object obj) {
if (this == obj) {
return true;
}
if (obj == null || this.getClass() != obj.getClass()) {
return false;
}
AbstractRelNode that = (AbstractRelNode) obj;
boolean result = this.getTraitSet().equals(that.getTraitSet())
&& this.getRowType().equalsSansFieldNames(that.getRowType());
if (!result) {
return false;
}
PairList<String, @Nullable Object> items1 = this.getDigestItems();
PairList<String, @Nullable Object> items2 = that.getDigestItems();
if (items1.size() != items2.size()) {
return false;
}
for (int i = 0; result && i < items1.size(); i++) {
Map.Entry<String, @Nullable Object> attr1 = items1.get(i);
Map.Entry<String, @Nullable Object> attr2 = items2.get(i);
if (attr1.getValue() instanceof RelNode) {
result = ((RelNode) attr1.getValue()).deepEquals(attr2.getValue());
} else {
result = attr1.equals(attr2);
}
}
return result;
}
/**
* Compute hash code for RelNode digest.
*
* @see RelNode#deepEquals(Object)
*/
@API(since = "1.25", status = API.Status.MAINTAINED)
@Override public int deepHashCode() {
int result = 31 + getTraitSet().hashCode();
PairList<String, @Nullable Object> items = this.getDigestItems();
for (@Nullable Object value : items.rightList()) {
final int h;
if (value == null) {
h = 0;
} else if (value instanceof RelNode) {
h = ((RelNode) value).deepHashCode();
} else {
h = value.hashCode();
}
result = result * 31 + h;
}
return result;
}
private PairList<String, @Nullable Object> getDigestItems() {
RelDigestWriter rdw = new RelDigestWriter();
explainTerms(rdw);
if (this instanceof Hintable) {
List<RelHint> hints = ((Hintable) this).getHints();
rdw.itemIf("hints", hints, !hints.isEmpty());
}
return rdw.attrs;
}
/** Implementation of {@link RelDigest}. */
private class InnerRelDigest implements RelDigest {
/** Cached hash code. */
private int hash = 0;
@Override public RelNode getRel() {
return AbstractRelNode.this;
}
@Override public void clear() {
hash = 0;
}
@Override public boolean equals(final @Nullable Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final InnerRelDigest relDigest = (InnerRelDigest) o;
return deepEquals(relDigest.getRel());
}
@Override public int hashCode() {
if (hash == 0) {
hash = deepHashCode();
}
return hash;
}
@Override public String toString() {
RelDigestWriter rdw = new RelDigestWriter();
explain(rdw);
return requireNonNull(rdw.digest, "digest");
}
}
/**
* A writer object used exclusively for computing the digest of a RelNode.
*
* <p>The writer is meant to be used only for computing a single digest and
* then thrown away. After calling {@link #done(RelNode)} the writer should
* be used only to obtain the computed {@link #digest}. Any other action is
* prohibited.
*/
private static final class RelDigestWriter implements RelWriter {
private final PairList<String, @Nullable Object> attrs = PairList.of();
@Nullable String digest = null;
@Override public void explain(final RelNode rel,
final List<Pair<String, @Nullable Object>> valueList) {
throw new IllegalStateException("Should not be called for computing digest");
}
@Override public SqlExplainLevel getDetailLevel() {
return SqlExplainLevel.DIGEST_ATTRIBUTES;
}
@Override public RelWriter item(String term, @Nullable Object value) {
if (value != null && value.getClass().isArray()) {
// We can't call hashCode and equals on Array, so
// convert it to String to keep the same behaviour.
value = "" + value;
}
attrs.add(term, value);
return this;
}
@Override public RelWriter done(RelNode node) {
StringBuilder sb = new StringBuilder();
sb.append(node.getRelTypeName());
sb.append('.');
sb.append(node.getTraitSet());
sb.append('(');
attrs.forEachIndexed((j, left, right) -> {
if (j > 0) {
sb.append(',');
}
sb.append(left);
sb.append('=');
if (right instanceof RelNode) {
RelNode input = (RelNode) right;
sb.append(input.getRelTypeName());
sb.append('#');
sb.append(input.getId());
} else {
sb.append(right);
}
});
sb.append(')');
digest = sb.toString();
return this;
}
}
}