http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableJoin.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/mutable/MutableJoin.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableJoin.java
new file mode 100644
index 0000000..09d5a1c
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableJoin.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.rel.mutable;
+
+import org.apache.calcite.rel.core.CorrelationId;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexNode;
+
+import java.util.Objects;
+import java.util.Set;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Join}. */
+public class MutableJoin extends MutableBiRel {
+  public final RexNode condition;
+  public final Set<CorrelationId> variablesSet;
+  public final JoinRelType joinType;
+
+  private MutableJoin(
+      RelDataType rowType,
+      MutableRel left,
+      MutableRel right,
+      RexNode condition,
+      JoinRelType joinType,
+      Set<CorrelationId> variablesSet) {
+    super(MutableRelType.JOIN, left.cluster, rowType, left, right);
+    this.condition = condition;
+    this.variablesSet = variablesSet;
+    this.joinType = joinType;
+  }
+
+  /**
+   * Creates a MutableJoin.
+   *
+   * @param rowType           Row type
+   * @param left              Left input relational expression
+   * @param right             Right input relational expression
+   * @param condition         Join condition
+   * @param joinType          Join type
+   * @param variablesStopped  Set of variables that are set by the LHS and
+   *                          used by the RHS and are not available to
+   *                          nodes above this join in the tree
+   */
+  public static MutableJoin of(RelDataType rowType, MutableRel left,
+      MutableRel right, RexNode condition, JoinRelType joinType,
+      Set<CorrelationId> variablesStopped) {
+    return new MutableJoin(rowType, left, right, condition, joinType,
+        variablesStopped);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableJoin
+        && joinType == ((MutableJoin) obj).joinType
+        && condition.toString().equals(
+            ((MutableJoin) obj).condition.toString())
+        && Objects.equals(variablesSet,
+            ((MutableJoin) obj).variablesSet)
+        && left.equals(((MutableJoin) obj).left)
+        && right.equals(((MutableJoin) obj).right);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(left, right,
+        condition.toString(), joinType, variablesSet);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Join(joinType: ").append(joinType)
+        .append(", condition: ").append(condition)
+        .append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableJoin.of(rowType, left.clone(),
+        right.clone(), condition, joinType, variablesSet);
+  }
+}
+
+// End MutableJoin.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableLeafRel.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableLeafRel.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableLeafRel.java
new file mode 100644
index 0000000..6ea92e2
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableLeafRel.java
@@ -0,0 +1,48 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.RelNode;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+
+/** Abstract base class for implementations of {@link MutableRel} that have
+ * no inputs. */
+abstract class MutableLeafRel extends MutableRel {
+  protected final RelNode rel;
+
+  protected MutableLeafRel(MutableRelType type, RelNode rel) {
+    super(rel.getCluster(), rel.getRowType(), type);
+    this.rel = rel;
+  }
+
+  public void setInput(int ordinalInParent, MutableRel input) {
+    throw new IllegalArgumentException();
+  }
+
+  public List<MutableRel> getInputs() {
+    return ImmutableList.of();
+  }
+
+  public void childrenAccept(MutableRelVisitor visitor) {
+    // no children - nothing to do
+  }
+}
+
+// End MutableLeafRel.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableMinus.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableMinus.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableMinus.java
new file mode 100644
index 0000000..42b3968
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableMinus.java
@@ -0,0 +1,55 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.rel.type.RelDataType;
+
+import java.util.List;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Minus}. */
+public class MutableMinus extends MutableSetOp {
+  private MutableMinus(RelOptCluster cluster, RelDataType rowType,
+      List<MutableRel> inputs, boolean all) {
+    super(cluster, rowType, MutableRelType.MINUS, inputs, all);
+  }
+
+  /**
+   * Creates a MutableMinus.
+   *
+   * @param rowType Row type
+   * @param inputs  Input relational expressions
+   * @param all     Whether to perform a multiset subtraction or a set
+   *                subtraction
+   */
+  public static MutableMinus of(
+      RelDataType rowType, List<MutableRel> inputs, boolean all) {
+    assert inputs.size() >= 2;
+    final MutableRel input0 = inputs.get(0);
+    return new MutableMinus(input0.cluster, rowType, inputs, all);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Minus(all: ").append(all).append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableMinus.of(rowType, cloneChildren(), all);
+  }
+}
+
+// End MutableMinus.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableMultiRel.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableMultiRel.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableMultiRel.java
new file mode 100644
index 0000000..6c026bd
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableMultiRel.java
@@ -0,0 +1,65 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.rel.type.RelDataType;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+
+/** Base Class for relations with three or more inputs */
+abstract class MutableMultiRel extends MutableRel {
+  protected final List<MutableRel> inputs;
+
+  protected MutableMultiRel(RelOptCluster cluster,
+      RelDataType rowType, MutableRelType type, List<MutableRel> inputs) {
+    super(cluster, rowType, type);
+    this.inputs = inputs;
+  }
+
+  @Override public void setInput(int ordinalInParent, MutableRel input) {
+    inputs.set(ordinalInParent, input);
+    if (input != null) {
+      input.parent = this;
+      input.ordinalInParent = ordinalInParent;
+    }
+  }
+
+  @Override public List<MutableRel> getInputs() {
+    return inputs;
+  }
+
+  @Override public void childrenAccept(MutableRelVisitor visitor) {
+    for (MutableRel input : inputs) {
+      visitor.visit(input);
+    }
+  }
+
+  protected List<MutableRel> cloneChildren() {
+    return Lists.transform(inputs,
+        new Function<MutableRel, MutableRel>() {
+          public MutableRel apply(MutableRel mutableRel) {
+            return mutableRel.clone();
+          }
+        });
+  }
+}
+
+// End MutableMultiRel.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableProject.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableProject.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableProject.java
new file mode 100644
index 0000000..4ff921b
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableProject.java
@@ -0,0 +1,100 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.core.Project;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.sql.validate.SqlValidatorUtil;
+import org.apache.calcite.util.Litmus;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.mapping.Mappings;
+
+import java.util.List;
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Project}. */
+public class MutableProject extends MutableSingleRel {
+  public final List<RexNode> projects;
+
+  private MutableProject(RelDataType rowType, MutableRel input,
+      List<RexNode> projects) {
+    super(MutableRelType.PROJECT, rowType, input);
+    this.projects = projects;
+    assert RexUtil.compatibleTypes(projects, rowType, Litmus.THROW);
+  }
+
+  /**
+   * Creates a MutableProject.
+   *
+   * @param rowType   Row type
+   * @param input     Input relational expression
+   * @param projects  List of expressions for the input columns
+   */
+  public static MutableProject of(RelDataType rowType, MutableRel input,
+      List<RexNode> projects) {
+    return new MutableProject(rowType, input, projects);
+  }
+
+  /**
+   * Creates a MutableProject.
+   *
+   * @param input         Input relational expression
+   * @param exprList      List of expressions for the input columns
+   * @param fieldNameList Aliases of the expressions, or null to generate
+   */
+  public static MutableRel of(MutableRel input, List<RexNode> exprList,
+      List<String> fieldNameList) {
+    final RelDataType rowType =
+        RexUtil.createStructType(input.cluster.getTypeFactory(), exprList,
+            fieldNameList, SqlValidatorUtil.F_SUGGESTER);
+    return of(rowType, input, exprList);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableProject
+        && MutableRel.PAIRWISE_STRING_EQUIVALENCE.equivalent(
+            projects, ((MutableProject) obj).projects)
+        && input.equals(((MutableProject) obj).input);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(input,
+        MutableRel.PAIRWISE_STRING_EQUIVALENCE.hash(projects));
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Project(projects: ").append(projects).append(")");
+  }
+
+  /** Returns a list of (expression, name) pairs. */
+  public final List<Pair<RexNode, String>> getNamedProjects() {
+    return Pair.zip(projects, rowType.getFieldNames());
+  }
+
+  public Mappings.TargetMapping getMapping() {
+    return Project.getMapping(input.rowType.getFieldCount(), projects);
+  }
+
+  @Override public MutableRel clone() {
+    return MutableProject.of(rowType, input.clone(), projects);
+  }
+}
+
+// End MutableProject.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableRel.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/mutable/MutableRel.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRel.java
new file mode 100644
index 0000000..385ea44
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRel.java
@@ -0,0 +1,148 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.avatica.util.Spaces;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.type.RelDataType;
+
+import com.google.common.base.Equivalence;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+
+/** Mutable equivalent of {@link RelNode}.
+ *
+ * <p>Each node has mutable state, and keeps track of its parent and position
+ * within parent.
+ * It doesn't make sense to canonize {@code MutableRels},
+ * otherwise one node could end up with multiple parents.
+ * It follows that {@code #hashCode} and {@code #equals} are less efficient
+ * than their {@code RelNode} counterparts.
+ * But, you don't need to copy a {@code MutableRel} in order to change it.
+ * For this reason, you should use {@code MutableRel} for short-lived
+ * operations, and transcribe back to {@code RelNode} when you are done.</p>
+ */
+public abstract class MutableRel {
+
+  /** Equivalence that compares objects by their {@link Object#toString()}
+   * method. */
+  protected static final Equivalence<Object> STRING_EQUIVALENCE =
+      new Equivalence<Object>() {
+        @Override protected boolean doEquivalent(Object o, Object o2) {
+          return o.toString().equals(o2.toString());
+        }
+
+        @Override protected int doHash(Object o) {
+          return o.toString().hashCode();
+        }
+      };
+
+  /** Equivalence that compares {@link Lists}s by the
+   * {@link Object#toString()} of their elements. */
+  @SuppressWarnings("unchecked")
+  protected static final Equivalence<List<?>> PAIRWISE_STRING_EQUIVALENCE =
+      (Equivalence) STRING_EQUIVALENCE.pairwise();
+
+  public final RelOptCluster cluster;
+  public final RelDataType rowType;
+  protected final MutableRelType type;
+
+  protected MutableRel parent;
+  protected int ordinalInParent;
+
+  protected MutableRel(RelOptCluster cluster,
+      RelDataType rowType, MutableRelType type) {
+    this.cluster = Preconditions.checkNotNull(cluster);
+    this.rowType = Preconditions.checkNotNull(rowType);
+    this.type = Preconditions.checkNotNull(type);
+  }
+
+  public MutableRel getParent() {
+    return parent;
+  }
+
+  public abstract void setInput(int ordinalInParent, MutableRel input);
+
+  public abstract List<MutableRel> getInputs();
+
+  public abstract MutableRel clone();
+
+  public abstract void childrenAccept(MutableRelVisitor visitor);
+
+  /** Replaces this {@code MutableRel} in its parent with another node at the
+   * same position.
+   *
+   * <p>Before the method, {@code child} must be an orphan (have null parent)
+   * and after this method, this {@code MutableRel} is an orphan.
+   *
+   * @return The parent
+   */
+  public MutableRel replaceInParent(MutableRel child) {
+    final MutableRel parent = this.parent;
+    if (this != child) {
+      if (parent != null) {
+        parent.setInput(ordinalInParent, child);
+        this.parent = null;
+        this.ordinalInParent = 0;
+      }
+    }
+    return parent;
+  }
+
+  public abstract StringBuilder digest(StringBuilder buf);
+
+  public final String deep() {
+    return new MutableRelDumper().apply(this);
+  }
+
+  @Override public final String toString() {
+    return deep();
+  }
+
+  /**
+   * Implementation of MutableVisitor that dumps the details
+   * of a MutableRel tree.
+   */
+  private class MutableRelDumper extends MutableRelVisitor {
+    private final StringBuilder buf = new StringBuilder();
+    private int level;
+
+    @Override public void visit(MutableRel node) {
+      Spaces.append(buf, level * 2);
+      if (node == null) {
+        buf.append("null");
+      } else {
+        node.digest(buf);
+        buf.append("\n");
+        ++level;
+        super.visit(node);
+        --level;
+      }
+    }
+
+    public String apply(MutableRel rel) {
+      go(rel);
+      return buf.toString();
+    }
+  }
+
+}
+
+// End MutableRel.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelType.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelType.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelType.java
new file mode 100644
index 0000000..c42c331
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelType.java
@@ -0,0 +1,44 @@
+/*
+ * 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.mutable;
+
+/** Type of {@code MutableRel}. */
+enum MutableRelType {
+  AGGREGATE,
+  CALC,
+  COLLECT,
+  CORRELATE,
+  EXCHANGE,
+  FILTER,
+  INTERSECT,
+  JOIN,
+  MINUS,
+  PROJECT,
+  SAMPLE,
+  SEMIJOIN,
+  SORT,
+  TABLE_FUNCTION_SCAN,
+  TABLE_MODIFY,
+  TABLE_SCAN,
+  UNCOLLECT,
+  UNION,
+  VALUES,
+  WINDOW,
+  HOLDER
+}
+
+// End MutableRelType.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelVisitor.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelVisitor.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelVisitor.java
new file mode 100644
index 0000000..aea7c5c
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRelVisitor.java
@@ -0,0 +1,34 @@
+/*
+ * 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.mutable;
+
+/** Visitor over {@link MutableRel}. */
+public class MutableRelVisitor {
+  private MutableRel root;
+
+  public void visit(MutableRel node) {
+    node.childrenAccept(this);
+  }
+
+  public MutableRel go(MutableRel p) {
+    this.root = p;
+    visit(p);
+    return root;
+  }
+}
+
+// End MutableRelVisitor.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java
new file mode 100644
index 0000000..04b1849
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java
@@ -0,0 +1,400 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Aggregate;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.core.Collect;
+import org.apache.calcite.rel.core.Correlate;
+import org.apache.calcite.rel.core.Exchange;
+import org.apache.calcite.rel.core.Filter;
+import org.apache.calcite.rel.core.Intersect;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rel.core.Minus;
+import org.apache.calcite.rel.core.Project;
+import org.apache.calcite.rel.core.Sample;
+import org.apache.calcite.rel.core.SemiJoin;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.core.TableFunctionScan;
+import org.apache.calcite.rel.core.TableModify;
+import org.apache.calcite.rel.core.TableScan;
+import org.apache.calcite.rel.core.Uncollect;
+import org.apache.calcite.rel.core.Union;
+import org.apache.calcite.rel.core.Values;
+import org.apache.calcite.rel.core.Window;
+import org.apache.calcite.rel.logical.LogicalAggregate;
+import org.apache.calcite.rel.logical.LogicalCalc;
+import org.apache.calcite.rel.logical.LogicalCorrelate;
+import org.apache.calcite.rel.logical.LogicalExchange;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.logical.LogicalIntersect;
+import org.apache.calcite.rel.logical.LogicalJoin;
+import org.apache.calcite.rel.logical.LogicalMinus;
+import org.apache.calcite.rel.logical.LogicalProject;
+import org.apache.calcite.rel.logical.LogicalSort;
+import org.apache.calcite.rel.logical.LogicalTableFunctionScan;
+import org.apache.calcite.rel.logical.LogicalTableModify;
+import org.apache.calcite.rel.logical.LogicalUnion;
+import org.apache.calcite.rel.logical.LogicalWindow;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.util.Util;
+import org.apache.calcite.util.mapping.Mappings;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Lists;
+
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.List;
+
+/** Utilities for dealing with {@link MutableRel}s. */
+public abstract class MutableRels {
+
+  public static boolean contains(MutableRel ancestor,
+      final MutableRel target) {
+    if (ancestor.equals(target)) {
+      // Short-cut common case.
+      return true;
+    }
+    try {
+      new MutableRelVisitor() {
+        @Override public void visit(MutableRel node) {
+          if (node.equals(target)) {
+            throw Util.FoundOne.NULL;
+          }
+          super.visit(node);
+        }
+        // CHECKSTYLE: IGNORE 1
+      }.go(ancestor);
+      return false;
+    } catch (Util.FoundOne e) {
+      return true;
+    }
+  }
+
+  public static MutableRel preOrderTraverseNext(MutableRel node) {
+    MutableRel parent = node.getParent();
+    int ordinal = node.ordinalInParent + 1;
+    while (parent != null) {
+      if (parent.getInputs().size() > ordinal) {
+        return parent.getInputs().get(ordinal);
+      }
+      node = parent;
+      parent = node.getParent();
+      ordinal = node.ordinalInParent + 1;
+    }
+    return null;
+  }
+
+  public static List<MutableRel> descendants(MutableRel query) {
+    final List<MutableRel> list = new ArrayList<>();
+    descendantsRecurse(list, query);
+    return list;
+  }
+
+  private static void descendantsRecurse(List<MutableRel> list,
+      MutableRel rel) {
+    list.add(rel);
+    for (MutableRel input : rel.getInputs()) {
+      descendantsRecurse(list, input);
+    }
+  }
+
+  /** Based on
+   * {@link org.apache.calcite.rel.rules.ProjectRemoveRule#strip}. */
+  public static MutableRel strip(MutableProject project) {
+    return isTrivial(project) ? project.getInput() : project;
+  }
+
+  /** Based on
+   * {@link 
org.apache.calcite.rel.rules.ProjectRemoveRule#isTrivial(org.apache.calcite.rel.core.Project)}.
 */
+  public static boolean isTrivial(MutableProject project) {
+    MutableRel child = project.getInput();
+    return RexUtil.isIdentity(project.projects, child.rowType);
+  }
+
+  /** Equivalent to
+   * {@link RelOptUtil#createProject(org.apache.calcite.rel.RelNode, 
java.util.List)}
+   * for {@link MutableRel}. */
+  public static MutableRel createProject(final MutableRel child,
+      final List<Integer> posList) {
+    final RelDataType rowType = child.rowType;
+    if (Mappings.isIdentity(posList, rowType.getFieldCount())) {
+      return child;
+    }
+    return MutableProject.of(
+        RelOptUtil.permute(child.cluster.getTypeFactory(), rowType,
+            Mappings.bijection(posList)),
+        child,
+        new AbstractList<RexNode>() {
+          public int size() {
+            return posList.size();
+          }
+
+          public RexNode get(int index) {
+            final int pos = posList.get(index);
+            return RexInputRef.of(pos, rowType);
+          }
+        });
+  }
+
+  /** Equivalence to {@link org.apache.calcite.plan.RelOptUtil#createCastRel}
+   * for {@link MutableRel}. */
+  public static MutableRel createCastRel(MutableRel rel,
+      RelDataType castRowType, boolean rename) {
+    RelDataType rowType = rel.rowType;
+    if (RelOptUtil.areRowTypesEqual(rowType, castRowType, rename)) {
+      // nothing to do
+      return rel;
+    }
+    List<RexNode> castExps =
+        RexUtil.generateCastExpressions(rel.cluster.getRexBuilder(),
+            castRowType, rowType);
+    final List<String> fieldNames =
+        rename ? castRowType.getFieldNames() : rowType.getFieldNames();
+    return MutableProject.of(rel, castExps, fieldNames);
+  }
+
+  public static RelNode fromMutable(MutableRel node) {
+    switch (node.type) {
+    case TABLE_SCAN:
+    case VALUES:
+      return ((MutableLeafRel) node).rel;
+    case PROJECT:
+      final MutableProject project = (MutableProject) node;
+      return LogicalProject.create(
+          fromMutable(project.input), project.projects, project.rowType);
+    case FILTER:
+      final MutableFilter filter = (MutableFilter) node;
+      return LogicalFilter.create(fromMutable(filter.input),
+          filter.condition);
+    case AGGREGATE:
+      final MutableAggregate aggregate = (MutableAggregate) node;
+      return LogicalAggregate.create(fromMutable(aggregate.input),
+          aggregate.indicator, aggregate.groupSet, aggregate.groupSets,
+          aggregate.aggCalls);
+    case SORT:
+      final MutableSort sort = (MutableSort) node;
+      return LogicalSort.create(fromMutable(sort.input), sort.collation,
+          sort.offset, sort.fetch);
+    case CALC:
+      final MutableCalc calc = (MutableCalc) node;
+      return LogicalCalc.create(fromMutable(calc.input), calc.program);
+    case EXCHANGE:
+      final MutableExchange exchange = (MutableExchange) node;
+      return LogicalExchange.create(
+          fromMutable(exchange.getInput()), exchange.distribution);
+    case COLLECT: {
+      final MutableCollect collect = (MutableCollect) node;
+      final RelNode child = fromMutable(collect.getInput());
+      return new Collect(collect.cluster, child.getTraitSet(), child, 
collect.fieldName);
+    }
+    case UNCOLLECT: {
+      final MutableUncollect uncollect = (MutableUncollect) node;
+      final RelNode child = fromMutable(uncollect.getInput());
+      return Uncollect.create(child.getTraitSet(), child, 
uncollect.withOrdinality);
+    }
+    case WINDOW: {
+      final MutableWindow window = (MutableWindow) node;
+      final RelNode child = fromMutable(window.getInput());
+      return LogicalWindow.create(child.getTraitSet(),
+          child, window.constants, window.rowType, window.groups);
+    }
+    case TABLE_MODIFY:
+      final MutableTableModify modify = (MutableTableModify) node;
+      return LogicalTableModify.create(modify.table, modify.catalogReader,
+          fromMutable(modify.getInput()), modify.operation, 
modify.updateColumnList,
+          modify.sourceExpressionList, modify.flattened);
+    case SAMPLE:
+      final MutableSample sample = (MutableSample) node;
+      return new Sample(sample.cluster, fromMutable(sample.getInput()), 
sample.params);
+    case TABLE_FUNCTION_SCAN:
+      final MutableTableFunctionScan tableFunctionScan = 
(MutableTableFunctionScan) node;
+      return LogicalTableFunctionScan.create(tableFunctionScan.cluster,
+          fromMutables(tableFunctionScan.getInputs()), 
tableFunctionScan.rexCall,
+          tableFunctionScan.elementType, tableFunctionScan.rowType,
+          tableFunctionScan.columnMappings);
+    case JOIN:
+      final MutableJoin join = (MutableJoin) node;
+      return LogicalJoin.create(fromMutable(join.getLeft()), 
fromMutable(join.getRight()),
+          join.condition, join.variablesSet, join.joinType);
+    case SEMIJOIN:
+      final MutableSemiJoin semiJoin = (MutableSemiJoin) node;
+      return SemiJoin.create(fromMutable(semiJoin.getLeft()),
+          fromMutable(semiJoin.getRight()), semiJoin.condition,
+          semiJoin.leftKeys, semiJoin.rightKeys);
+    case CORRELATE:
+      final MutableCorrelate correlate = (MutableCorrelate) node;
+      return LogicalCorrelate.create(fromMutable(correlate.getLeft()),
+          fromMutable(correlate.getRight()), correlate.correlationId,
+          correlate.requiredColumns, correlate.joinType);
+    case UNION:
+      final MutableUnion union = (MutableUnion) node;
+      return LogicalUnion.create(MutableRels.fromMutables(union.inputs), 
union.all);
+    case MINUS:
+      final MutableMinus minus = (MutableMinus) node;
+      return LogicalMinus.create(MutableRels.fromMutables(minus.inputs), 
minus.all);
+    case INTERSECT:
+      final MutableIntersect intersect = (MutableIntersect) node;
+      return 
LogicalIntersect.create(MutableRels.fromMutables(intersect.inputs), 
intersect.all);
+    default:
+      throw new AssertionError(node.deep());
+    }
+  }
+
+  private static List<RelNode> fromMutables(List<MutableRel> nodes) {
+    return Lists.transform(nodes,
+        new Function<MutableRel, RelNode>() {
+          public RelNode apply(MutableRel mutableRel) {
+            return fromMutable(mutableRel);
+          }
+        });
+  }
+
+  public static MutableRel toMutable(RelNode rel) {
+    if (rel instanceof TableScan) {
+      return MutableScan.of((TableScan) rel);
+    }
+    if (rel instanceof Values) {
+      return MutableValues.of((Values) rel);
+    }
+    if (rel instanceof Project) {
+      final Project project = (Project) rel;
+      final MutableRel input = toMutable(project.getInput());
+      return MutableProject.of(input, project.getProjects(),
+          project.getRowType().getFieldNames());
+    }
+    if (rel instanceof Filter) {
+      final Filter filter = (Filter) rel;
+      final MutableRel input = toMutable(filter.getInput());
+      return MutableFilter.of(input, filter.getCondition());
+    }
+    if (rel instanceof Aggregate) {
+      final Aggregate aggregate = (Aggregate) rel;
+      final MutableRel input = toMutable(aggregate.getInput());
+      return MutableAggregate.of(input, aggregate.indicator,
+          aggregate.getGroupSet(), aggregate.getGroupSets(),
+          aggregate.getAggCallList());
+    }
+    if (rel instanceof Sort) {
+      final Sort sort = (Sort) rel;
+      final MutableRel input = toMutable(sort.getInput());
+      return MutableSort.of(input, sort.getCollation(), sort.offset, 
sort.fetch);
+    }
+    if (rel instanceof Calc) {
+      final Calc calc = (Calc) rel;
+      final MutableRel input = toMutable(calc.getInput());
+      return MutableCalc.of(input, calc.getProgram());
+    }
+    if (rel instanceof Exchange) {
+      final Exchange exchange = (Exchange) rel;
+      final MutableRel input = toMutable(exchange.getInput());
+      return MutableExchange.of(input, exchange.getDistribution());
+    }
+    if (rel instanceof Collect) {
+      final Collect collect = (Collect) rel;
+      final MutableRel input = toMutable(collect.getInput());
+      return MutableCollect.of(collect.getRowType(), input, 
collect.getFieldName());
+    }
+    if (rel instanceof Uncollect) {
+      final Uncollect uncollect = (Uncollect) rel;
+      final MutableRel input = toMutable(uncollect.getInput());
+      return MutableUncollect.of(uncollect.getRowType(), input, 
uncollect.withOrdinality);
+    }
+    if (rel instanceof Window) {
+      final Window window = (Window) rel;
+      final MutableRel input = toMutable(window.getInput());
+      return MutableWindow.of(window.getRowType(),
+          input, window.groups, window.getConstants());
+    }
+    if (rel instanceof TableModify) {
+      final TableModify modify = (TableModify) rel;
+      final MutableRel input = toMutable(modify.getInput());
+      return MutableTableModify.of(modify.getRowType(), input, 
modify.getTable(),
+          modify.getCatalogReader(), modify.getOperation(), 
modify.getUpdateColumnList(),
+          modify.getSourceExpressionList(), modify.isFlattened());
+    }
+    if (rel instanceof Sample) {
+      final Sample sample = (Sample) rel;
+      final MutableRel input = toMutable(sample.getInput());
+      return MutableSample.of(input, sample.getSamplingParameters());
+    }
+    if (rel instanceof TableFunctionScan) {
+      final TableFunctionScan tableFunctionScan = (TableFunctionScan) rel;
+      final List<MutableRel> inputs = 
toMutables(tableFunctionScan.getInputs());
+      return MutableTableFunctionScan.of(tableFunctionScan.getCluster(),
+          tableFunctionScan.getRowType(), inputs, tableFunctionScan.getCall(),
+          tableFunctionScan.getElementType(), 
tableFunctionScan.getColumnMappings());
+    }
+    // It is necessary that SemiJoin is placed in front of Join here, since 
SemiJoin
+    // is a sub-class of Join.
+    if (rel instanceof SemiJoin) {
+      final SemiJoin semiJoin = (SemiJoin) rel;
+      final MutableRel left = toMutable(semiJoin.getLeft());
+      final MutableRel right = toMutable(semiJoin.getRight());
+      return MutableSemiJoin.of(semiJoin.getRowType(), left, right,
+          semiJoin.getCondition(), semiJoin.getLeftKeys(), 
semiJoin.getRightKeys());
+    }
+    if (rel instanceof Join) {
+      final Join join = (Join) rel;
+      final MutableRel left = toMutable(join.getLeft());
+      final MutableRel right = toMutable(join.getRight());
+      return MutableJoin.of(join.getRowType(), left, right,
+          join.getCondition(), join.getJoinType(), join.getVariablesSet());
+    }
+    if (rel instanceof Correlate) {
+      final Correlate correlate = (Correlate) rel;
+      final MutableRel left = toMutable(correlate.getLeft());
+      final MutableRel right = toMutable(correlate.getRight());
+      return MutableCorrelate.of(correlate.getRowType(), left, right,
+          correlate.getCorrelationId(), correlate.getRequiredColumns(),
+          correlate.getJoinType());
+    }
+    if (rel instanceof Union) {
+      final Union union = (Union) rel;
+      final List<MutableRel> inputs = toMutables(union.getInputs());
+      return MutableUnion.of(union.getRowType(), inputs, union.all);
+    }
+    if (rel instanceof Minus) {
+      final Minus minus = (Minus) rel;
+      final List<MutableRel> inputs = toMutables(minus.getInputs());
+      return MutableMinus.of(minus.getRowType(), inputs, minus.all);
+    }
+    if (rel instanceof Intersect) {
+      final Intersect intersect = (Intersect) rel;
+      final List<MutableRel> inputs = toMutables(intersect.getInputs());
+      return MutableIntersect.of(intersect.getRowType(), inputs, 
intersect.all);
+    }
+    throw new RuntimeException("cannot translate " + rel + " to MutableRel");
+  }
+
+  private static List<MutableRel> toMutables(List<RelNode> nodes) {
+    return Lists.transform(nodes,
+        new Function<RelNode, MutableRel>() {
+          public MutableRel apply(RelNode relNode) {
+            return toMutable(relNode);
+          }
+        });
+  }
+}
+
+// End MutableRels.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableSample.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableSample.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSample.java
new file mode 100644
index 0000000..9b9da35
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSample.java
@@ -0,0 +1,69 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptSamplingParameters;
+
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Sample}. */
+public class MutableSample extends MutableSingleRel {
+  public final RelOptSamplingParameters params;
+
+  private MutableSample(MutableRel input, RelOptSamplingParameters params) {
+    super(MutableRelType.SAMPLE, input.rowType, input);
+    this.params = params;
+  }
+
+  /**
+   * Creates a MutableSample.
+   *
+   * @param input   Input relational expression
+   * @param params  parameters necessary to produce a sample of a relation
+   */
+  public static MutableSample of(
+      MutableRel input, RelOptSamplingParameters params) {
+    return new MutableSample(input, params);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableSample
+        && params.equals(((MutableSample) obj).params)
+        && input.equals(((MutableSample) obj).input);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(input, params);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Sample(mode: ")
+        .append(params.isBernoulli() ? "bernoulli" : "system")
+        .append("rate")
+        .append(params.getSamplingPercentage())
+        .append("repeatableSeed")
+        .append(params.isRepeatable() ? params.getRepeatableSeed() : "-")
+        .append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableSample.of(input.clone(), params);
+  }
+}
+
+// End MutableSample.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableScan.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/mutable/MutableScan.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableScan.java
new file mode 100644
index 0000000..4d63519
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableScan.java
@@ -0,0 +1,56 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.core.TableScan;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.TableScan}. */
+public class MutableScan extends MutableLeafRel {
+  private MutableScan(TableScan rel) {
+    super(MutableRelType.TABLE_SCAN, rel);
+  }
+
+  /**
+   * Creates a MutableScan.
+   *
+   * @param scan  The underlying TableScan object
+   */
+  public static MutableScan of(TableScan scan) {
+    return new MutableScan(scan);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableScan
+        && rel.equals(((MutableScan) obj).rel);
+  }
+
+  @Override public int hashCode() {
+    return rel.hashCode();
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Scan(table: ")
+        .append(rel.getTable().getQualifiedName()).append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableScan.of((TableScan) rel);
+  }
+}
+
+// End MutableScan.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableSemiJoin.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableSemiJoin.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSemiJoin.java
new file mode 100644
index 0000000..c2e81b7
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSemiJoin.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.rel.mutable;
+
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.ImmutableIntList;
+
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.SemiJoin}. */
+public class MutableSemiJoin extends MutableBiRel {
+  public final RexNode condition;
+  public final ImmutableIntList leftKeys;
+  public final ImmutableIntList rightKeys;
+
+  private MutableSemiJoin(
+      RelDataType rowType,
+      MutableRel left,
+      MutableRel right,
+      RexNode condition,
+      ImmutableIntList leftKeys,
+      ImmutableIntList rightKeys) {
+    super(MutableRelType.SEMIJOIN, left.cluster, rowType, left, right);
+    this.condition = condition;
+    this.leftKeys = leftKeys;
+    this.rightKeys = rightKeys;
+  }
+
+  /**
+   * Creates a MutableSemiJoin.
+   *
+   * @param rowType   Row type
+   * @param left      Left input relational expression
+   * @param right     Right input relational expression
+   * @param condition Join condition
+   * @param leftKeys  Left join keys
+   * @param rightKeys Right join keys
+   */
+  public static MutableSemiJoin of(RelDataType rowType, MutableRel left,
+      MutableRel right, RexNode condition, ImmutableIntList leftKeys,
+      ImmutableIntList rightKeys) {
+    return new MutableSemiJoin(rowType, left, right, condition, leftKeys,
+        rightKeys);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableSemiJoin
+        && condition.toString().equals(
+            ((MutableSemiJoin) obj).condition.toString())
+        && leftKeys.equals(((MutableSemiJoin) obj).leftKeys)
+        && rightKeys.equals(((MutableSemiJoin) obj).rightKeys)
+        && left.equals(((MutableSemiJoin) obj).left)
+        && right.equals(((MutableSemiJoin) obj).right);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(left, right,
+        condition.toString(), leftKeys, rightKeys);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("SemiJoin(condition: ").append(condition)
+        .append(", leftKeys: ").append(leftKeys)
+        .append(", rightKeys: ").append(rightKeys)
+        .append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableSemiJoin.of(rowType, left.clone(),
+        right.clone(), condition, leftKeys, rightKeys);
+  }
+}
+
+// End MutableSemiJoin.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableSetOp.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableSetOp.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSetOp.java
new file mode 100644
index 0000000..ad241f8
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSetOp.java
@@ -0,0 +1,52 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.rel.type.RelDataType;
+
+import java.util.List;
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.SetOp}. */
+abstract class MutableSetOp extends MutableMultiRel {
+  protected final boolean all;
+
+  protected MutableSetOp(RelOptCluster cluster, RelDataType rowType,
+      MutableRelType type, List<MutableRel> inputs, boolean all) {
+    super(cluster, rowType, type, inputs);
+    this.all = all;
+  }
+
+  public boolean isAll() {
+    return all;
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableSetOp
+        && type == ((MutableSetOp) obj).type
+        && all == ((MutableSetOp) obj).all
+        && inputs.equals(((MutableSetOp) obj).getInputs());
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(type, inputs, all);
+  }
+}
+
+// End MutableSetOp.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableSingleRel.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableSingleRel.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSingleRel.java
new file mode 100644
index 0000000..e310ac9
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSingleRel.java
@@ -0,0 +1,61 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.type.RelDataType;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.SingleRel}. */
+abstract class MutableSingleRel extends MutableRel {
+  protected MutableRel input;
+
+  protected MutableSingleRel(MutableRelType type,
+      RelDataType rowType, MutableRel input) {
+    super(input.cluster, rowType, type);
+    this.input = input;
+    input.parent = this;
+    input.ordinalInParent = 0;
+  }
+
+  public void setInput(int ordinalInParent, MutableRel input) {
+    if (ordinalInParent > 0) {
+      throw new IllegalArgumentException();
+    }
+    this.input = input;
+    if (input != null) {
+      input.parent = this;
+      input.ordinalInParent = 0;
+    }
+  }
+
+  public List<MutableRel> getInputs() {
+    return ImmutableList.of(input);
+  }
+
+  public void childrenAccept(MutableRelVisitor visitor) {
+    visitor.visit(input);
+  }
+
+  public MutableRel getInput() {
+    return input;
+  }
+}
+
+// End MutableSingleRel.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableSort.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/mutable/MutableSort.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSort.java
new file mode 100644
index 0000000..36268c7
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableSort.java
@@ -0,0 +1,81 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rex.RexNode;
+
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Sort}. */
+public class MutableSort extends MutableSingleRel {
+  public final RelCollation collation;
+  public final RexNode offset;
+  public final RexNode fetch;
+
+  private MutableSort(MutableRel input, RelCollation collation,
+      RexNode offset, RexNode fetch) {
+    super(MutableRelType.SORT, input.rowType, input);
+    this.collation = collation;
+    this.offset = offset;
+    this.fetch = fetch;
+  }
+
+  /**
+   * Creates a MutableSort.
+   *
+   * @param input     Input relational expression
+   * @param collation Array of sort specifications
+   * @param offset    Expression for number of rows to discard before returning
+   *                  first row
+   * @param fetch     Expression for number of rows to fetch
+   */
+  public static MutableSort of(MutableRel input, RelCollation collation,
+      RexNode offset, RexNode fetch) {
+    return new MutableSort(input, collation, offset, fetch);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableSort
+        && collation.equals(((MutableSort) obj).collation)
+        && Objects.equals(offset, ((MutableSort) obj).offset)
+        && Objects.equals(fetch, ((MutableSort) obj).fetch)
+        && input.equals(((MutableSort) obj).input);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(input, collation, offset, fetch);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    buf.append("Sort(collation: ").append(collation);
+    if (offset != null) {
+      buf.append(", offset: ").append(offset);
+    }
+    if (fetch != null) {
+      buf.append(", fetch: ").append(fetch);
+    }
+    return buf.append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableSort.of(input.clone(), collation, offset, fetch);
+  }
+}
+
+// End MutableSort.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableFunctionScan.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableFunctionScan.java
 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableFunctionScan.java
new file mode 100644
index 0000000..514cdf2
--- /dev/null
+++ 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableFunctionScan.java
@@ -0,0 +1,96 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.rel.metadata.RelColumnMapping;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexNode;
+
+import java.lang.reflect.Type;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+
+/** Mutable equivalent of
+ * {@link org.apache.calcite.rel.core.TableFunctionScan}. */
+public class MutableTableFunctionScan extends MutableMultiRel {
+  public final RexNode rexCall;
+  public final Type elementType;
+  public final Set<RelColumnMapping> columnMappings;
+
+  private MutableTableFunctionScan(RelOptCluster cluster,
+      RelDataType rowType, List<MutableRel> inputs, RexNode rexCall,
+      Type elementType, Set<RelColumnMapping> columnMappings) {
+    super(cluster, rowType, MutableRelType.TABLE_FUNCTION_SCAN, inputs);
+    this.rexCall = rexCall;
+    this.elementType = elementType;
+    this.columnMappings = columnMappings;
+  }
+
+  /**
+   * Creates a MutableTableFunctionScan.
+   *
+   * @param cluster         Cluster that this relational expression belongs to
+   * @param rowType         Row type
+   * @param inputs          Input relational expressions
+   * @param rexCall         Function invocation expression
+   * @param elementType     Element type of the collection that will implement
+   *                        this table
+   * @param columnMappings  Column mappings associated with this function
+   */
+  public static MutableTableFunctionScan of(RelOptCluster cluster,
+      RelDataType rowType, List<MutableRel> inputs, RexNode rexCall,
+      Type elementType, Set<RelColumnMapping> columnMappings) {
+    return new MutableTableFunctionScan(
+        cluster, rowType, inputs, rexCall, elementType, columnMappings);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableTableFunctionScan
+        && STRING_EQUIVALENCE.equivalent(rexCall,
+            ((MutableTableFunctionScan) obj).rexCall)
+        && Objects.equals(elementType,
+            ((MutableTableFunctionScan) obj).elementType)
+        && Objects.equals(columnMappings,
+            ((MutableTableFunctionScan) obj).columnMappings)
+        && inputs.equals(((MutableSetOp) obj).getInputs());
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(inputs,
+        STRING_EQUIVALENCE.hash(rexCall), elementType, columnMappings);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    buf.append("TableFunctionScan(rexCall: ").append(rexCall);
+    if (elementType != null) {
+      buf.append(", elementType: ").append(elementType);
+    }
+    return buf.append(")");
+  }
+
+  @Override public MutableRel clone() {
+    // TODO Auto-generated method stub
+    return MutableTableFunctionScan.of(cluster, rowType,
+        cloneChildren(), rexCall, elementType, columnMappings);
+  }
+
+}
+
+// End MutableTableFunctionScan.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableModify.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableModify.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableModify.java
new file mode 100644
index 0000000..ba188f8
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableTableModify.java
@@ -0,0 +1,113 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptTable;
+import org.apache.calcite.prepare.Prepare;
+import org.apache.calcite.rel.core.TableModify.Operation;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexNode;
+
+import java.util.List;
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.TableModify}. */
+public class MutableTableModify extends MutableSingleRel {
+  public final Prepare.CatalogReader catalogReader;
+  public final RelOptTable table;
+  public final Operation operation;
+  public final List<String> updateColumnList;
+  public final List<RexNode> sourceExpressionList;
+  public final boolean flattened;
+
+  private MutableTableModify(RelDataType rowType, MutableRel input,
+      RelOptTable table, Prepare.CatalogReader catalogReader,
+      Operation operation, List<String> updateColumnList,
+      List<RexNode> sourceExpressionList, boolean flattened) {
+    super(MutableRelType.TABLE_MODIFY, rowType, input);
+    this.table = table;
+    this.catalogReader = catalogReader;
+    this.operation = operation;
+    this.updateColumnList = updateColumnList;
+    this.sourceExpressionList = sourceExpressionList;
+    this.flattened = flattened;
+  }
+
+  /**
+   * Creates a MutableTableModify.
+   *
+   * @param rowType               Row type
+   * @param input                 Input relational expression
+   * @param table                 Target table to modify
+   * @param catalogReader         Accessor to the table metadata
+   * @param operation             Modify operation (INSERT, UPDATE, DELETE)
+   * @param updateColumnList      List of column identifiers to be updated
+   *                              (e.g. ident1, ident2); null if not UPDATE
+   * @param sourceExpressionList  List of value expressions to be set
+   *                              (e.g. exp1, exp2); null if not UPDATE
+   * @param flattened             Whether set flattens the input row type
+   */
+  public static MutableTableModify of(RelDataType rowType,
+      MutableRel input, RelOptTable table,
+      Prepare.CatalogReader catalogReader,
+      Operation operation, List<String> updateColumnList,
+      List<RexNode> sourceExpressionList, boolean flattened) {
+    return new MutableTableModify(rowType, input, table, catalogReader,
+        operation, updateColumnList, sourceExpressionList, flattened);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableTableModify
+        && table.getQualifiedName().equals(
+            ((MutableTableModify) obj).table.getQualifiedName())
+        && operation == ((MutableTableModify) obj).operation
+        && Objects.equals(updateColumnList,
+            ((MutableTableModify) obj).updateColumnList)
+        && MutableRel.PAIRWISE_STRING_EQUIVALENCE.equivalent(
+            sourceExpressionList, ((MutableTableModify) 
obj).sourceExpressionList)
+        && flattened == ((MutableTableModify) obj).flattened
+        && input.equals(((MutableTableModify) obj).input);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(input, table.getQualifiedName(),
+        operation, updateColumnList,
+        MutableRel.PAIRWISE_STRING_EQUIVALENCE.hash(sourceExpressionList),
+        flattened);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    buf.append("TableModify(table: ").append(table.getQualifiedName())
+        .append(", operation: ").append(operation);
+    if (updateColumnList != null) {
+      buf.append(", updateColumnList: ").append(updateColumnList);
+    }
+    if (sourceExpressionList != null) {
+      buf.append(", sourceExpressionList: ").append(sourceExpressionList);
+    }
+    return buf.append(", flattened: ").append(flattened).append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableTableModify.of(rowType, input.clone(), table, catalogReader,
+        operation, updateColumnList, sourceExpressionList, flattened);
+  }
+
+}
+
+// End MutableTableModify.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableUncollect.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableUncollect.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableUncollect.java
new file mode 100644
index 0000000..eb3afcc
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableUncollect.java
@@ -0,0 +1,67 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.type.RelDataType;
+
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Uncollect}. */
+public class MutableUncollect extends MutableSingleRel {
+  public final boolean withOrdinality;
+
+  private MutableUncollect(RelDataType rowType,
+      MutableRel input, boolean withOrdinality) {
+    super(MutableRelType.UNCOLLECT, rowType, input);
+    this.withOrdinality = withOrdinality;
+  }
+
+  /**
+   * Creates a MutableUncollect.
+   *
+   * @param rowType         Row type
+   * @param input           Input relational expression
+   * @param withOrdinality  Whether the output contains an extra
+   *                        {@code ORDINALITY} column
+   */
+  public static MutableUncollect of(RelDataType rowType,
+      MutableRel input, boolean withOrdinality) {
+    return new MutableUncollect(rowType, input, withOrdinality);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableUncollect
+        && withOrdinality == ((MutableUncollect) obj).withOrdinality
+        && input.equals(((MutableUncollect) obj).input);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(input, withOrdinality);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Uncollect(withOrdinality: ")
+        .append(withOrdinality).append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableUncollect.of(rowType, input.clone(), withOrdinality);
+  }
+}
+
+// End MutableUncollect.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableUnion.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableUnion.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableUnion.java
new file mode 100644
index 0000000..a60dd68
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableUnion.java
@@ -0,0 +1,55 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.rel.type.RelDataType;
+
+import java.util.List;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Union}. */
+public class MutableUnion extends MutableSetOp {
+  private MutableUnion(RelOptCluster cluster, RelDataType rowType,
+      List<MutableRel> inputs, boolean all) {
+    super(cluster, rowType, MutableRelType.UNION, inputs, all);
+  }
+
+  /**
+   * Creates a MutableUnion.
+   *
+   * @param rowType Row type
+   * @param inputs  Input relational expressions
+   * @param all     Whether the union result should include all rows or
+   *                eliminate duplicates from input relational expressions
+   */
+  public static MutableUnion of(
+      RelDataType rowType, List<MutableRel> inputs, boolean all) {
+    assert inputs.size() >= 2;
+    final MutableRel input0 = inputs.get(0);
+    return new MutableUnion(input0.cluster, rowType, inputs, all);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Union(all: ").append(all).append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableUnion.of(rowType, cloneChildren(), all);
+  }
+}
+
+// End MutableUnion.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableValues.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableValues.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableValues.java
new file mode 100644
index 0000000..299db16
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableValues.java
@@ -0,0 +1,56 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.core.Values;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Values}. */
+public class MutableValues extends MutableLeafRel {
+  private MutableValues(Values rel) {
+    super(MutableRelType.VALUES, rel);
+  }
+
+  /**
+   * Creates a MutableValue.
+   *
+   * @param values  The underlying Values object
+   */
+  public static MutableValues of(Values values) {
+    return new MutableValues(values);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableValues
+        && rel == ((MutableValues) obj).rel;
+  }
+
+  @Override public int hashCode() {
+    return rel.hashCode();
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Values(tuples: ")
+        .append(((Values) rel).getTuples()).append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableValues.of((Values) rel);
+  }
+}
+
+// End MutableValues.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/MutableWindow.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/MutableWindow.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/MutableWindow.java
new file mode 100644
index 0000000..ee82875
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableWindow.java
@@ -0,0 +1,73 @@
+/*
+ * 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.mutable;
+
+import org.apache.calcite.rel.core.Window.Group;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexLiteral;
+
+import java.util.List;
+import java.util.Objects;
+
+/** Mutable equivalent of {@link org.apache.calcite.rel.core.Window}. */
+public class MutableWindow extends MutableSingleRel {
+  public final List<Group> groups;
+  public final List<RexLiteral> constants;
+
+  private MutableWindow(RelDataType rowType, MutableRel input,
+      List<Group> groups, List<RexLiteral> constants) {
+    super(MutableRelType.WINDOW, rowType, input);
+    this.groups = groups;
+    this.constants = constants;
+  }
+
+  /**
+   * Creates a MutableWindow.
+   *
+   * @param rowType   Row type
+   * @param input     Input relational expression
+   * @param groups    Window groups
+   * @param constants List of constants that are additional inputs
+   */
+  public static MutableWindow of(RelDataType rowType,
+      MutableRel input, List<Group> groups, List<RexLiteral> constants) {
+    return new MutableWindow(rowType, input, groups, constants);
+  }
+
+  @Override public boolean equals(Object obj) {
+    return obj == this
+        || obj instanceof MutableWindow
+        && groups.equals(((MutableWindow) obj).groups)
+        && constants.equals(((MutableWindow) obj).constants)
+        && input.equals(((MutableWindow) obj).input);
+  }
+
+  @Override public int hashCode() {
+    return Objects.hash(input, groups, constants);
+  }
+
+  @Override public StringBuilder digest(StringBuilder buf) {
+    return buf.append("Window(groups: ").append(groups)
+        .append(", constants: ").append(constants).append(")");
+  }
+
+  @Override public MutableRel clone() {
+    return MutableWindow.of(rowType, input.clone(), groups, constants);
+  }
+}
+
+// End MutableWindow.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/main/java/org/apache/calcite/rel/mutable/package-info.java
----------------------------------------------------------------------
diff --git 
a/core/src/main/java/org/apache/calcite/rel/mutable/package-info.java 
b/core/src/main/java/org/apache/calcite/rel/mutable/package-info.java
new file mode 100644
index 0000000..c932029
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/mutable/package-info.java
@@ -0,0 +1,39 @@
+/*
+ * 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.
+ */
+
+/**
+ * Defines mutable relational expressions.
+ *
+ * <h2>Related packages and classes</h2>
+ * <ul>
+ *
+ * <li>Package <code>
+ * <a 
href="../core/package-summary.html">org.apache.calcite.rel.core</a></code>
+ * contains core relational expressions
+ *
+ * <li>Package <code>
+ * <a href="../package-summary.html">org.apache.calcite.rex</a></code>
+ * defines the relational expression API
+ *
+ * </ul>
+ */
+@PackageMarker
+package org.apache.calcite.rel.mutable;
+
+import org.apache.calcite.avatica.util.PackageMarker;
+
+// End package-info.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java 
b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
index df0167d..5fdd793 100644
--- a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
+++ b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
@@ -137,6 +137,7 @@ import org.junit.runners.Suite;
     CollationConversionTest.class,
     TraitConversionTest.class,
     ComboRuleTest.class,
+    MutableRelTest.class,
 
     // slow tests (above 1s)
     UdfTest.class,

http://git-wip-us.apache.org/repos/asf/calcite/blob/316a0587/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
----------------------------------------------------------------------
diff --git 
a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java 
b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
index f6ec85d..04abcfd 100644
--- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
+++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
@@ -946,6 +946,35 @@ public class MaterializationTest {
     }
   }
 
+  @Test public void testTableModify() {
+    final String m = "select \"deptno\", \"empid\", \"name\""
+        + "from \"emps\" where \"deptno\" = 10";
+    final String q = "upsert into \"dependents\""
+        + "select \"empid\" + 1 as x, \"name\""
+        + "from \"emps\" where \"deptno\" = 10";
+
+    final List<List<List<String>>> substitutedNames = new ArrayList<>();
+    try (final TryThreadLocal.Memo ignored = Prepare.THREAD_TRIM.push(true)) {
+      MaterializationService.setThreadLocal();
+      CalciteAssert.that()
+          .withMaterializations(JdbcTest.HR_MODEL,
+              "m0", m)
+          .query(q)
+          .withHook(Hook.SUB,
+              new Function<RelNode, Void>() {
+                public Void apply(RelNode input) {
+                  substitutedNames.add(new TableNameVisitor().run(input));
+                  return null;
+                }
+              })
+          .enableMaterializations(true)
+          .explainContains("hr, m0");
+    } catch (Exception e) {
+      // Table "dependents" not modifiable.
+    }
+    assertThat(substitutedNames, is(list3(new String[][][]{{{"hr", "m0"}}})));
+  }
+
   /** Test case for
    * <a href="https://issues.apache.org/jira/browse/CALCITE-761";>[CALCITE-761]
    * Pre-populated materializations</a>. */

Reply via email to