diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceMaterializationForInsertWithSelfScanRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceMaterializationForInsertWithSelfScanRule.java
index f4d8419..d838d71 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceMaterializationForInsertWithSelfScanRule.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceMaterializationForInsertWithSelfScanRule.java
@@ -70,10 +70,12 @@
             materializeOperator.getInputs()
                     .add(new MutableObject<ILogicalOperator>(insertOp.getInputs().get(0).getValue()));
             context.computeAndSetTypeEnvironmentForOperator(materializeOperator);
+            materializeOperator.recomputeSchema();
 
             insertOp.getInputs().clear();
             insertOp.getInputs().add(new MutableObject<ILogicalOperator>(materializeOperator));
             context.computeAndSetTypeEnvironmentForOperator(insertOp);
+            insertOp.recomputeSchema();
             return true;
         } else {
             return false;
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceRandomPartitioningFeedComputationRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceRandomPartitioningFeedComputationRule.java
index 4a75cb3..9195c5e 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceRandomPartitioningFeedComputationRule.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceRandomPartitioningFeedComputationRule.java
@@ -75,6 +75,7 @@
         exchangeOp.setExecutionMode(em);
         exchangeOp.computeDeliveredPhysicalProperties(context);
         context.computeAndSetTypeEnvironmentForOperator(exchangeOp);
+        exchangeOp.recomputeSchema();
 
         AssignOperator assignOp = (AssignOperator) opRef.getValue();
         AssignPOperator assignPhyOp = (AssignPOperator) assignOp.getPhysicalOperator();
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/SetupCommitExtensionOpRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/SetupCommitExtensionOpRule.java
index cc50dce4..fbf086b 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/SetupCommitExtensionOpRule.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/SetupCommitExtensionOpRule.java
@@ -110,6 +110,7 @@
         //update plan link
         extensionOperator.getInputs().add(eOp.getInputs().get(0));
         context.computeAndSetTypeEnvironmentForOperator(extensionOperator);
+        extensionOperator.recomputeSchema();
         opRef.setValue(extensionOperator);
         return true;
     }
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
index d887914..fa5ef51 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
@@ -247,5 +247,6 @@
         op.getInputs().set(branch, aoRef);
 
         context.computeAndSetTypeEnvironmentForOperator(ao);
+        ao.recomputeSchema();
     }
 }
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifier.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifier.java
index 1fad860..8495099 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifier.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifier.java
@@ -37,6 +37,7 @@
 import org.apache.hyracks.algebricks.core.algebra.base.LogicalExpressionTag;
 import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
 import org.apache.hyracks.algebricks.core.algebra.prettyprint.IPlanPrettyPrinter;
+import org.apache.hyracks.algebricks.core.algebra.typing.ITypingContext;
 import org.apache.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
 import org.apache.hyracks.algebricks.core.algebra.visitors.ILogicalExpressionReferenceTransform;
 
@@ -55,6 +56,10 @@
 
     private static final String ERROR_MESSAGE_TEMPLATE_2 = "shared %s (%s) between %s and %s";
 
+    private static final String ERROR_MESSAGE_TEMPLATE_3 = "missing output type environment in %s";
+
+    private static final String ERROR_MESSAGE_TEMPLATE_4 = "missing schema in %s";
+
     private final ExpressionReferenceVerifierVisitor exprVisitor = new ExpressionReferenceVerifierVisitor();
 
     private final Map<Mutable<ILogicalOperator>, ILogicalOperator> opRefMap = new IdentityHashMap<>();
@@ -69,12 +74,23 @@
 
     private final IPlanPrettyPrinter prettyPrinter;
 
-    public PlanStructureVerifier(IPlanPrettyPrinter prettyPrinter) {
+    private final ITypingContext typeEnvProvider;
+
+    private boolean ensureTypeEnv;
+
+    private boolean ensureSchema;
+
+    public PlanStructureVerifier(IPlanPrettyPrinter prettyPrinter, ITypingContext typeEnvProvider) {
         this.prettyPrinter = prettyPrinter;
+        this.typeEnvProvider = typeEnvProvider;
     }
 
     public void verifyPlanStructure(Mutable<ILogicalOperator> opRef) throws AlgebricksException {
         reset();
+        ILogicalOperator op = opRef.getValue();
+        // if root has type-env/schema then ensure that all children have them too
+        ensureTypeEnv = typeEnvProvider.getOutputTypeEnvironment(op) != null;
+        ensureSchema = op.getSchema() != null;
         walk(opRef);
         reset();
     }
@@ -84,6 +100,8 @@
         opMap.clear();
         exprRefMap.clear();
         exprMap.clear();
+        ensureTypeEnv = false;
+        ensureSchema = false;
     }
 
     private void walk(Mutable<ILogicalOperator> opRef) throws AlgebricksException {
@@ -137,6 +155,15 @@
         exprVisitor.setOperator(op);
         op.acceptExpressionTransform(exprVisitor);
 
+        if (ensureTypeEnv && typeEnvProvider.getOutputTypeEnvironment(op) == null) {
+            throw new AlgebricksException(
+                    String.format(ERROR_MESSAGE_TEMPLATE_3, PlanStabilityVerifier.printOperator(op, prettyPrinter)));
+        }
+        if (ensureSchema && op.getSchema() == null) {
+            throw new AlgebricksException(
+                    String.format(ERROR_MESSAGE_TEMPLATE_4, PlanStabilityVerifier.printOperator(op, prettyPrinter)));
+        }
+
         List<Mutable<ILogicalOperator>> children = op.getInputs();
         if (op instanceof AbstractOperatorWithNestedPlans) {
             children = new ArrayList<>(children);
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/rewriter/base/AlgebricksOptimizationContext.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/rewriter/base/AlgebricksOptimizationContext.java
index ecb8390..d1fd247 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/rewriter/base/AlgebricksOptimizationContext.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/rewriter/base/AlgebricksOptimizationContext.java
@@ -111,7 +111,7 @@
         this.conflictingTypeResovler = conflictingTypeResovler;
         this.warningCollector = warningCollector;
         boolean isSanityCheckEnabled = physicalOptimizationConfig.isSanityCheckEnabled();
-        this.planStructureVerifier = isSanityCheckEnabled ? new PlanStructureVerifier(prettyPrinter) : null;
+        this.planStructureVerifier = isSanityCheckEnabled ? new PlanStructureVerifier(prettyPrinter, this) : null;
         this.planStabilityVerifier = isSanityCheckEnabled ? new PlanStabilityVerifier(prettyPrinter) : null;
     }
 
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/test/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifierTest.java b/hyracks-fullstack/algebricks/algebricks-core/src/test/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifierTest.java
index fa4061d..f047cec 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/test/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifierTest.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/test/java/org/apache/hyracks/algebricks/core/algebra/plan/PlanStructureVerifierTest.java
@@ -19,20 +19,31 @@
 
 package org.apache.hyracks.algebricks.core.algebra.plan;
 
+import java.util.HashMap;
+import java.util.Map;
+
 import org.apache.commons.lang3.mutable.Mutable;
 import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
 import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression;
 import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
 import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
 import org.apache.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+import org.apache.hyracks.algebricks.core.algebra.expressions.IConflictingTypeResolver;
+import org.apache.hyracks.algebricks.core.algebra.expressions.IExpressionTypeComputer;
+import org.apache.hyracks.algebricks.core.algebra.expressions.IMissableTypeComputer;
+import org.apache.hyracks.algebricks.core.algebra.expressions.IVariableTypeEnvironment;
+import org.apache.hyracks.algebricks.core.algebra.metadata.IMetadataProvider;
 import org.apache.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.EmptyTupleSourceOperator;
 import org.apache.hyracks.algebricks.core.algebra.operators.logical.InnerJoinOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import org.apache.hyracks.algebricks.core.algebra.typing.ITypingContext;
 import org.junit.Assert;
 import org.junit.Test;
 
-public final class PlanStructureVerifierTest extends PlanVerifierTestBase {
+public final class PlanStructureVerifierTest extends PlanVerifierTestBase implements ITypingContext {
 
-    final PlanStructureVerifier verifier = new PlanStructureVerifier(planPrinter);
+    final PlanStructureVerifier verifier = new PlanStructureVerifier(planPrinter, this);
 
     @Test
     public void testVerifySuccess() throws Exception {
@@ -242,4 +253,99 @@
             Assert.assertTrue(e.getMessage(), e.getMessage().contains("cycle"));
         }
     }
+
+    @Test
+    public void testNoSchema() {
+        EmptyTupleSourceOperator ets = newETS();
+        ets.recomputeSchema();
+
+        AssignOperator op1 = newAssign(newVar(), newMutable(ConstantExpression.TRUE));
+        op1.getInputs().add(newMutable(ets));
+        op1.recomputeSchema();
+
+        op1.getInputs().clear();
+
+        AssignOperator op2 = newAssign(newVar(), newMutable(ConstantExpression.FALSE));
+        // no schema
+        op1.getInputs().add(newMutable(op2));
+
+        try {
+            verifier.verifyPlanStructure(newMutable(op1));
+            Assert.fail("Expected to catch " + AlgebricksException.class.getName());
+        } catch (AlgebricksException e) {
+            Assert.assertTrue(e.getMessage(), e.getMessage().contains("missing schema"));
+        }
+    }
+
+    @Test
+    public void testNoTypeEnvironment() throws Exception {
+        EmptyTupleSourceOperator ets = newETS();
+        computeAndSetTypeEnvironmentForOperator(ets);
+        ets.recomputeSchema();
+
+        SelectOperator op1 = new SelectOperator(newMutable(ConstantExpression.TRUE), false, null);
+        op1.getInputs().add(newMutable(ets));
+        computeAndSetTypeEnvironmentForOperator(op1);
+        op1.recomputeSchema();
+
+        op1.getInputs().clear();
+
+        SelectOperator op2 = new SelectOperator(newMutable(ConstantExpression.FALSE), false, null);
+        op2.getInputs().add(newMutable(ets));
+        op2.recomputeSchema();
+        // no type env
+
+        op1.getInputs().add(newMutable(op2));
+
+        try {
+            verifier.verifyPlanStructure(newMutable(op1));
+            Assert.fail("Expected to catch " + AlgebricksException.class.getName());
+        } catch (AlgebricksException e) {
+            Assert.assertTrue(e.getMessage(), e.getMessage().contains("missing output type environment"));
+        }
+    }
+
+    // ITypingContext
+
+    final Map<ILogicalOperator, IVariableTypeEnvironment> typeEnvMap = new HashMap<>();
+
+    @Override
+    public void computeAndSetTypeEnvironmentForOperator(ILogicalOperator op) throws AlgebricksException {
+        setOutputTypeEnvironment(op, op.computeOutputTypeEnvironment(this));
+    }
+
+    @Override
+    public void setOutputTypeEnvironment(ILogicalOperator op, IVariableTypeEnvironment env) {
+        typeEnvMap.put(op, env);
+    }
+
+    @Override
+    public IVariableTypeEnvironment getOutputTypeEnvironment(ILogicalOperator op) {
+        return typeEnvMap.get(op);
+    }
+
+    @Override
+    public void invalidateTypeEnvironmentForOperator(ILogicalOperator op) {
+        typeEnvMap.remove(op);
+    }
+
+    @Override
+    public IExpressionTypeComputer getExpressionTypeComputer() {
+        return null;
+    }
+
+    @Override
+    public IMissableTypeComputer getMissableTypeComputer() {
+        return null;
+    }
+
+    @Override
+    public IConflictingTypeResolver getConflictingTypeResolver() {
+        return null;
+    }
+
+    @Override
+    public IMetadataProvider<?, ?> getMetadataProvider() {
+        return null;
+    }
 }
diff --git a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonOperatorsRule.java b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonOperatorsRule.java
index 3effcc8..f9e6b13 100644
--- a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonOperatorsRule.java
+++ b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonOperatorsRule.java
@@ -185,9 +185,11 @@
                 Mutable<ILogicalOperator> beforeExchangeRef = new MutableObject<ILogicalOperator>(beforeExchange);
                 beforeExchange.getInputs().add(candidate);
                 context.computeAndSetTypeEnvironmentForOperator(beforeExchange);
+                beforeExchange.recomputeSchema();
                 rop.getInputs().add(beforeExchangeRef);
             }
             context.computeAndSetTypeEnvironmentForOperator(rop);
+            rop.recomputeSchema();
 
             for (Mutable<ILogicalOperator> parentRef : originalCandidateParents) {
                 AbstractLogicalOperator parent = (AbstractLogicalOperator) parentRef.getValue();
@@ -203,11 +205,13 @@
                     exchange.getInputs().add(new MutableObject<>(rop));
                     rop.getOutputs().add(exchangeRef);
                     context.computeAndSetTypeEnvironmentForOperator(exchange);
+                    exchange.recomputeSchema();
                     parent.getInputs().set(index, exchangeRef);
                     context.computeAndSetTypeEnvironmentForOperator(parent);
+                    parent.recomputeSchema();
                 }
             }
-            List<LogicalVariable> liveVarsNew = new ArrayList<LogicalVariable>();
+            List<LogicalVariable> liveVarsNew = new ArrayList<>();
             VariableUtilities.getLiveVariables(candidate.getValue(), liveVarsNew);
             for (Mutable<ILogicalOperator> ref : group) {
                 if (ref.equals(candidate)) {
@@ -244,8 +248,11 @@
 
                 // set the types
                 context.computeAndSetTypeEnvironmentForOperator(exchOp);
+                exchOp.recomputeSchema();
                 context.computeAndSetTypeEnvironmentForOperator(assignOperator);
+                assignOperator.recomputeSchema();
                 context.computeAndSetTypeEnvironmentForOperator(projectOperator);
+                projectOperator.recomputeSchema();
 
                 List<Mutable<ILogicalOperator>> parentOpList = childrenToParents.get(ref);
                 for (Mutable<ILogicalOperator> parentOpRef : parentOpList) {
@@ -265,8 +272,10 @@
                         exchg.getInputs().add(new MutableObject<ILogicalOperator>(childOp));
                         parentOp.getInputs().set(index, new MutableObject<ILogicalOperator>(exchg));
                         context.computeAndSetTypeEnvironmentForOperator(exchg);
+                        exchg.recomputeSchema();
                     }
                     context.computeAndSetTypeEnvironmentForOperator(parentOp);
+                    parentOp.recomputeSchema();
                 }
             }
             cleanupPlan();
diff --git a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java
index c4ae57d..5745d9b 100644
--- a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java
+++ b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java
@@ -82,7 +82,9 @@
         projectOp.setPhysicalOperator(new StreamProjectPOperator());
         projectOp.setExecutionMode(inputOp.getExecutionMode());
         context.computeAndSetTypeEnvironmentForOperator(projectOp);
+        projectOp.recomputeSchema();
         context.computeAndSetTypeEnvironmentForOperator(inputOp);
+        inputOp.recomputeSchema();
     }
 
     private boolean isIdentical(List<LogicalVariable> finalSchema, List<LogicalVariable> inputSchema)
diff --git a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java
index af67be2..ca92331 100644
--- a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java
+++ b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java
@@ -165,6 +165,7 @@
                     projectOp.getInputs().add(new MutableObject<ILogicalOperator>(childOp));
                     op.getInputs().get(i).setValue(projectOp);
                     context.computeAndSetTypeEnvironmentForOperator(projectOp);
+                    projectOp.recomputeSchema();
                     modified = true;
                 }
             }
@@ -183,6 +184,7 @@
 
         if (modified) {
             context.computeAndSetTypeEnvironmentForOperator(op);
+            op.recomputeSchema();
         }
         return modified;
     }
diff --git a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java
index 35b2dea..e13ec30 100644
--- a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java
+++ b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java
@@ -27,10 +27,8 @@
 import org.apache.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
 import org.apache.hyracks.algebricks.core.algebra.base.PhysicalOperatorTag;
 import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
-import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
 import org.apache.hyracks.algebricks.core.algebra.operators.logical.ExchangeOperator;
 import org.apache.hyracks.algebricks.core.algebra.operators.physical.OneToOneExchangePOperator;
-import org.apache.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
 import org.apache.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
 
 public class IsolateHyracksOperatorsRule implements IAlgebraicRewriteRule {
@@ -124,20 +122,17 @@
         return false;
     }
 
-    private final static void insertOneToOneExchange(Mutable<ILogicalOperator> i, IOptimizationContext context)
+    private static void insertOneToOneExchange(Mutable<ILogicalOperator> inOpRef, IOptimizationContext context)
             throws AlgebricksException {
+        ILogicalOperator inOp = inOpRef.getValue();
+
         ExchangeOperator e = new ExchangeOperator();
         e.setPhysicalOperator(new OneToOneExchangePOperator());
-        ILogicalOperator inOp = i.getValue();
-
-        e.getInputs().add(new MutableObject<ILogicalOperator>(inOp));
-        i.setValue(e);
-        // e.recomputeSchema();
-        OperatorPropertiesUtil.computeSchemaAndPropertiesRecIfNull(e, context);
-        ExecutionMode em = ((AbstractLogicalOperator) inOp).getExecutionMode();
-        e.setExecutionMode(em);
-        e.computeDeliveredPhysicalProperties(context);
+        e.getInputs().add(new MutableObject<>(inOp));
+        e.setExecutionMode(inOp.getExecutionMode());
         context.computeAndSetTypeEnvironmentForOperator(e);
-    }
+        e.recomputeSchema();
 
+        inOpRef.setValue(e);
+    }
 }
diff --git a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java
index 9457b60..c919195 100644
--- a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java
+++ b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java
@@ -68,7 +68,9 @@
         Set<LogicalVariable> toPush = new LinkedHashSet<LogicalVariable>();
         toPush.addAll(pi.getVariables());
 
-        Pair<Boolean, Boolean> p = pushThroughOp(toPush, opRef2, op, context);
+        boolean recomputeSchema = op.getSchema() != null;
+
+        Pair<Boolean, Boolean> p = pushThroughOp(toPush, opRef2, op, context, recomputeSchema);
         boolean smthWasPushed = p.first;
         if (p.second) { // the original projection is redundant
             opRef.setValue(op.getInputs().get(0).getValue());
@@ -79,7 +81,8 @@
     }
 
     private static Pair<Boolean, Boolean> pushThroughOp(Set<LogicalVariable> toPush, Mutable<ILogicalOperator> opRef2,
-            ILogicalOperator initialOp, IOptimizationContext context) throws AlgebricksException {
+            ILogicalOperator initialOp, IOptimizationContext context, boolean recomputeSchema)
+            throws AlgebricksException {
         List<LogicalVariable> initProjectList = new ArrayList<LogicalVariable>(toPush);
         AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
         do {
@@ -135,6 +138,9 @@
             gby.getDecorList().addAll(newDecorList);
             if (gbyChanged) {
                 context.computeAndSetTypeEnvironmentForOperator(gby);
+                if (recomputeSchema) {
+                    gby.recomputeSchema();
+                }
             }
         }
         used2.clear();
@@ -149,7 +155,7 @@
 
         boolean smthWasPushed = false;
         for (Mutable<ILogicalOperator> c : op2.getInputs()) {
-            if (pushNeededProjections(toPush, c, context, initialOp)) {
+            if (pushNeededProjections(toPush, c, context, initialOp, recomputeSchema)) {
                 smthWasPushed = true;
             }
         }
@@ -157,7 +163,7 @@
             AbstractOperatorWithNestedPlans n = (AbstractOperatorWithNestedPlans) op2;
             for (ILogicalPlan p : n.getNestedPlans()) {
                 for (Mutable<ILogicalOperator> r : p.getRoots()) {
-                    if (pushNeededProjections(toPush, r, context, initialOp)) {
+                    if (pushNeededProjections(toPush, r, context, initialOp, recomputeSchema)) {
                         smthWasPushed = true;
                     }
                 }
@@ -168,7 +174,8 @@
 
     // It does not try to push above another Projection.
     private static boolean pushNeededProjections(Set<LogicalVariable> toPush, Mutable<ILogicalOperator> opRef,
-            IOptimizationContext context, ILogicalOperator initialOp) throws AlgebricksException {
+            IOptimizationContext context, ILogicalOperator initialOp, boolean recomputeSchema)
+            throws AlgebricksException {
         Set<LogicalVariable> allP = new LinkedHashSet<LogicalVariable>();
         AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
         VariableUtilities.getSubplanLocalLiveVariables(op, allP);
@@ -183,19 +190,19 @@
             // projection would be redundant, since we would project everything
             // but we can try with the children
             boolean push = false;
-            if (pushThroughOp(toProject, opRef, initialOp, context).first) {
+            if (pushThroughOp(toProject, opRef, initialOp, context, recomputeSchema).first) {
                 push = true;
             }
             return push;
         } else {
-            return pushAllProjectionsOnTopOf(toProject, opRef, context, initialOp);
+            return pushAllProjectionsOnTopOf(toProject, opRef, context, initialOp, recomputeSchema);
         }
     }
 
     // It does not try to push above another Projection.
     private static boolean pushAllProjectionsOnTopOf(Collection<LogicalVariable> toPush,
-            Mutable<ILogicalOperator> opRef, IOptimizationContext context, ILogicalOperator initialOp)
-            throws AlgebricksException {
+            Mutable<ILogicalOperator> opRef, IOptimizationContext context, ILogicalOperator initialOp,
+            boolean recomputeSchema) throws AlgebricksException {
         if (toPush.isEmpty()) {
             return false;
         }
@@ -215,6 +222,9 @@
         opRef.setValue(pi2);
         pi2.setExecutionMode(op.getExecutionMode());
         context.computeAndSetTypeEnvironmentForOperator(pi2);
+        if (recomputeSchema) {
+            pi2.recomputeSchema();
+        }
         return true;
     }