asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ima...@apache.org
Subject [07/51] [partial] incubator-asterixdb-hyracks git commit: Change folder structure for Java repackage
Date Tue, 25 Aug 2015 16:41:20 GMT
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineVariablesRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineVariablesRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineVariablesRule.java
new file mode 100644
index 0000000..6390efc
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineVariablesRule.java
@@ -0,0 +1,253 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalExpressionTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractLogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.plan.ALogicalPlanImpl;
+import edu.uci.ics.hyracks.algebricks.core.algebra.visitors.ILogicalExpressionReferenceTransform;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Replaces variable reference expressions with their assigned function-call expression where applicable
+ * (some variables are generated by datasources).
+ * Inlining variables may enable other optimizations by allowing selects and assigns to be moved
+ * (e.g., a select may be pushed into a join to enable an efficient physical join operator).
+ * Preconditions/Assumptions:
+ * Assumes no projects are in the plan. Only inlines variables whose assigned expression is a function call
+ * (i.e., this rule ignores right-hand side constants and other variable references expressions
+ * Postconditions/Examples:
+ * All qualifying variables have been inlined.
+ * Example (simplified):
+ * Before plan:
+ * select <- [$$1 < $$2 + $$0]
+ * assign [$$2] <- [funcZ() + $$0]
+ * assign [$$0, $$1] <- [funcX(), funcY()]
+ * After plan:
+ * select <- [funcY() < funcZ() + funcX() + funcX()]
+ * assign [$$2] <- [funcZ() + funcX()]
+ * assign [$$0, $$1] <- [funcX(), funcY()]
+ */
+public class InlineVariablesRule implements IAlgebraicRewriteRule {
+
+    // Map of variables that could be replaced by their producing expression.
+    // Populated during the top-down sweep of the plan.
+    protected Map<LogicalVariable, ILogicalExpression> varAssignRhs = new HashMap<LogicalVariable, ILogicalExpression>();
+
+    // Visitor for replacing variable reference expressions with their originating expression.
+    protected InlineVariablesVisitor inlineVisitor = new InlineVariablesVisitor(varAssignRhs);
+
+    // Set of FunctionIdentifiers that we should not inline.
+    protected Set<FunctionIdentifier> doNotInlineFuncs = new HashSet<FunctionIdentifier>();
+
+    protected boolean hasRun = false;
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        if (hasRun) {
+            return false;
+        }
+        if (context.checkIfInDontApplySet(this, opRef.getValue())) {
+            return false;
+        }
+        prepare(context);
+        boolean modified = inlineVariables(opRef, context);
+        if (performFinalAction()) {
+            modified = true;
+        }
+        hasRun = true;
+        return modified;
+    }
+
+    protected void prepare(IOptimizationContext context) {
+        varAssignRhs.clear();
+        inlineVisitor.setContext(context);
+    }
+
+    protected boolean performBottomUpAction(AbstractLogicalOperator op) throws AlgebricksException {
+        // Only inline variables in operators that can deal with arbitrary expressions.
+        if (!op.requiresVariableReferenceExpressions()) {
+            inlineVisitor.setOperator(op);
+            return op.acceptExpressionTransform(inlineVisitor);
+        }
+        return false;
+    }
+
+    protected boolean performFinalAction() throws AlgebricksException {
+        return false;
+    }
+
+    protected boolean inlineVariables(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+
+        // Update mapping from variables to expressions during top-down traversal.
+        if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+            AssignOperator assignOp = (AssignOperator) op;
+            List<LogicalVariable> vars = assignOp.getVariables();
+            List<Mutable<ILogicalExpression>> exprs = assignOp.getExpressions();
+            for (int i = 0; i < vars.size(); i++) {
+                ILogicalExpression expr = exprs.get(i).getValue();
+                // Ignore functions that are either in the doNotInline set or are non-functional               
+                if (expr.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                    AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) expr;
+                    if (doNotInlineFuncs.contains(funcExpr.getFunctionIdentifier()) || !funcExpr.isFunctional()) {
+                        continue;
+                    }
+                }
+                varAssignRhs.put(vars.get(i), exprs.get(i).getValue());
+            }
+        }
+
+        // Descend into children removing projects on the way.
+        boolean modified = false;
+        for (Mutable<ILogicalOperator> inputOpRef : op.getInputs()) {
+            if (inlineVariables(inputOpRef, context)) {
+                modified = true;
+            }
+        }
+
+        // Descend into subplan
+        if (op.getOperatorTag() == LogicalOperatorTag.SUBPLAN) {
+            ALogicalPlanImpl subPlan = (ALogicalPlanImpl) ((SubplanOperator) op).getNestedPlans().get(0);
+            Mutable<ILogicalOperator> subPlanRootOpRef = subPlan.getRoots().get(0);
+            if (inlineVariables(subPlanRootOpRef, context)) {
+                modified = true;
+            }
+        }
+
+        if (performBottomUpAction(op)) {
+            modified = true;
+        }
+
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(op);
+            context.addToDontApplySet(this, op);
+            // Re-enable rules that we may have already tried. They could be applicable now after inlining.
+            context.removeFromAlreadyCompared(opRef.getValue());
+        }
+
+        return modified;
+    }
+
+    protected class InlineVariablesVisitor implements ILogicalExpressionReferenceTransform {
+
+        private final Map<LogicalVariable, ILogicalExpression> varAssignRhs;
+        private final Set<LogicalVariable> liveVars = new HashSet<LogicalVariable>();
+        private final List<LogicalVariable> rhsUsedVars = new ArrayList<LogicalVariable>();
+        private ILogicalOperator op;
+        private IOptimizationContext context;
+        // If set, only replace this variable reference.
+        private LogicalVariable targetVar;
+
+        public InlineVariablesVisitor(Map<LogicalVariable, ILogicalExpression> varAssignRhs) {
+            this.varAssignRhs = varAssignRhs;
+        }
+
+        public void setTargetVariable(LogicalVariable targetVar) {
+            this.targetVar = targetVar;
+        }
+
+        public void setContext(IOptimizationContext context) {
+            this.context = context;
+        }
+
+        public void setOperator(ILogicalOperator op) throws AlgebricksException {
+            this.op = op;
+            liveVars.clear();
+        }
+
+        @Override
+        public boolean transform(Mutable<ILogicalExpression> exprRef) throws AlgebricksException {
+            ILogicalExpression e = exprRef.getValue();
+            switch (((AbstractLogicalExpression) e).getExpressionTag()) {
+                case VARIABLE: {
+                    LogicalVariable var = ((VariableReferenceExpression) e).getVariableReference();
+                    // Restrict replacement to targetVar if it has been set.
+                    if (targetVar != null && var != targetVar) {
+                        return false;
+                    }
+
+                    // Make sure has not been excluded from inlining.
+                    if (context.shouldNotBeInlined(var)) {
+                        return false;
+                    }
+
+                    ILogicalExpression rhs = varAssignRhs.get(var);
+                    if (rhs == null) {
+                        // Variable was not produced by an assign.
+                        return false;
+                    }
+
+                    // Make sure used variables from rhs are live.
+                    if (liveVars.isEmpty()) {
+                        VariableUtilities.getLiveVariables(op, liveVars);
+                    }
+                    rhsUsedVars.clear();
+                    rhs.getUsedVariables(rhsUsedVars);
+                    for (LogicalVariable rhsUsedVar : rhsUsedVars) {
+                        if (!liveVars.contains(rhsUsedVar)) {
+                            return false;
+                        }
+                    }
+
+                    // Replace variable reference with a clone of the rhs expr.
+                    exprRef.setValue(rhs.cloneExpression());
+                    return true;
+                }
+                case FUNCTION_CALL: {
+                    AbstractFunctionCallExpression fce = (AbstractFunctionCallExpression) e;
+                    boolean modified = false;
+                    for (Mutable<ILogicalExpression> arg : fce.getArguments()) {
+                        if (transform(arg)) {
+                            modified = true;
+                        }
+                    }
+                    return modified;
+                }
+                default: {
+                    return false;
+                }
+            }
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertOuterJoinRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertOuterJoinRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertOuterJoinRule.java
new file mode 100644
index 0000000..c5aee3c
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertOuterJoinRule.java
@@ -0,0 +1,121 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.Iterator;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.InnerJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.LeftOuterJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class InsertOuterJoinRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op0 = (AbstractLogicalOperator) opRef.getValue();
+        if (op0.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+            return false;
+        }
+        SubplanOperator subplan = (SubplanOperator) op0;
+
+        Iterator<ILogicalPlan> plansIter = subplan.getNestedPlans().iterator();
+        ILogicalPlan p = null;
+        while (plansIter.hasNext()) {
+            p = plansIter.next();
+        }
+        if (p == null) {
+            return false;
+        }
+        if (p.getRoots().size() != 1) {
+            return false;
+        }
+        Mutable<ILogicalOperator> subplanRoot = p.getRoots().get(0);
+        AbstractLogicalOperator op1 = (AbstractLogicalOperator) subplanRoot.getValue();
+        Mutable<ILogicalOperator> opUnder = subplan.getInputs().get(0);
+
+        if (OperatorPropertiesUtil.isNullTest((AbstractLogicalOperator) opUnder.getValue())) {
+            return false;
+        }
+
+        switch (op1.getOperatorTag()) {
+            case INNERJOIN: {
+                InnerJoinOperator join = (InnerJoinOperator) op1;
+                Mutable<ILogicalOperator> leftRef = join.getInputs().get(0);
+                Mutable<ILogicalOperator> rightRef = join.getInputs().get(1);
+                Mutable<ILogicalOperator> ntsRef = getNtsAtEndOfPipeline(leftRef);
+                if (ntsRef == null) {
+                    ntsRef = getNtsAtEndOfPipeline(rightRef);
+                    if (ntsRef == null) {
+                        return false;
+                    } else {
+                        Mutable<ILogicalOperator> t = leftRef;
+                        leftRef = rightRef;
+                        rightRef = t;
+                    }
+                }
+                ntsRef.setValue(opUnder.getValue());
+                LeftOuterJoinOperator loj = new LeftOuterJoinOperator(join.getCondition());
+                loj.getInputs().add(leftRef);
+                loj.getInputs().add(rightRef);
+                opRef.setValue(loj);
+                context.computeAndSetTypeEnvironmentForOperator(loj);
+                return true;
+            }
+            case LEFTOUTERJOIN: {
+                LeftOuterJoinOperator join = (LeftOuterJoinOperator) op1;
+                Mutable<ILogicalOperator> leftRef = join.getInputs().get(0);
+                Mutable<ILogicalOperator> ntsRef = getNtsAtEndOfPipeline(leftRef);
+                if (ntsRef == null) {
+                    return false;
+                }
+                ntsRef.setValue(opUnder.getValue());
+                opRef.setValue(join);
+                context.computeAndSetTypeEnvironmentForOperator(join);
+                return true;
+            }
+            default: {
+                return false;
+            }
+        }
+    }
+
+    private Mutable<ILogicalOperator> getNtsAtEndOfPipeline(Mutable<ILogicalOperator> opRef) {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
+            return opRef;
+        }
+        if (op.getInputs().size() != 1) {
+            return null;
+        }
+        return getNtsAtEndOfPipeline(op.getInputs().get(0));
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java
new file mode 100644
index 0000000..80b8815
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InsertProjectBeforeUnionRule.java
@@ -0,0 +1,110 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.utils.Triple;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnionAllOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.StreamProjectPOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class InsertProjectBeforeUnionRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        return false;
+    }
+
+    /**
+     * When the input schema to WriteOperator is different from the output
+     * schema in terms of variable order, add a project operator to get the
+     * write order
+     */
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.UNIONALL) {
+            return false;
+        }
+        UnionAllOperator opUnion = (UnionAllOperator) op;
+        List<Triple<LogicalVariable, LogicalVariable, LogicalVariable>> varMap = opUnion.getVariableMappings();
+        ArrayList<LogicalVariable> usedVariablesFromOne = new ArrayList<LogicalVariable>();
+        ArrayList<LogicalVariable> usedVariablesFromTwo = new ArrayList<LogicalVariable>();
+
+        for (Triple<LogicalVariable, LogicalVariable, LogicalVariable> triple : varMap) {
+            usedVariablesFromOne.add(triple.first);
+            usedVariablesFromTwo.add(triple.second);
+        }
+
+        ArrayList<LogicalVariable> inputSchemaOne = new ArrayList<LogicalVariable>();
+        VariableUtilities.getLiveVariables(opUnion.getInputs().get(0).getValue(), inputSchemaOne);
+
+        ArrayList<LogicalVariable> inputSchemaTwo = new ArrayList<LogicalVariable>();
+        VariableUtilities.getLiveVariables(opUnion.getInputs().get(1).getValue(), inputSchemaTwo);
+
+        boolean rewritten = false;
+        if (!isIdentical(usedVariablesFromOne, inputSchemaOne)) {
+            insertProjectOperator(opUnion, 0, usedVariablesFromOne, context);
+            rewritten = true;
+        }
+        if (!isIdentical(usedVariablesFromTwo, inputSchemaTwo)) {
+            insertProjectOperator(opUnion, 1, usedVariablesFromTwo, context);
+            rewritten = true;
+        }
+        return rewritten;
+    }
+
+    private void insertProjectOperator(UnionAllOperator opUnion, int branch, ArrayList<LogicalVariable> usedVariables,
+            IOptimizationContext context) throws AlgebricksException {
+        ProjectOperator projectOp = new ProjectOperator(usedVariables);
+        ILogicalOperator parentOp = opUnion.getInputs().get(branch).getValue();
+        projectOp.getInputs().add(new MutableObject<ILogicalOperator>(parentOp));
+        opUnion.getInputs().get(branch).setValue(projectOp);
+        projectOp.setPhysicalOperator(new StreamProjectPOperator());
+        context.computeAndSetTypeEnvironmentForOperator(projectOp);
+        context.computeAndSetTypeEnvironmentForOperator(parentOp);
+    }
+
+    private boolean isIdentical(List<LogicalVariable> finalSchema, List<LogicalVariable> inputSchema)
+            throws AlgebricksException {
+        int finalSchemaSize = finalSchema.size();
+        int inputSchemaSize = inputSchema.size();
+        if (finalSchemaSize != inputSchemaSize) {
+            return false;
+        }
+        for (int i = 0; i < finalSchemaSize; i++) {
+            LogicalVariable var1 = finalSchema.get(i);
+            LogicalVariable var2 = inputSchema.get(i);
+            if (!var1.equals(var2))
+                return false;
+        }
+        return true;
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroHashPartitionMergeExchange.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroHashPartitionMergeExchange.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroHashPartitionMergeExchange.java
new file mode 100644
index 0000000..51f2025
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroHashPartitionMergeExchange.java
@@ -0,0 +1,74 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.PhysicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.HashPartitionExchangePOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.HashPartitionMergeExchangePOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.SortMergeExchangePOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.properties.OrderColumn;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class IntroHashPartitionMergeExchange implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op1 = (AbstractLogicalOperator) opRef.getValue();
+        if (op1.getPhysicalOperator() == null
+                || (op1.getPhysicalOperator().getOperatorTag() != PhysicalOperatorTag.HASH_PARTITION_EXCHANGE && op1
+                        .getPhysicalOperator().getOperatorTag() != PhysicalOperatorTag.HASH_PARTITION_MERGE_EXCHANGE)) {
+            return false;
+        }
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) op1.getInputs().get(0).getValue();
+        if (op2.getPhysicalOperator() == null
+                || op2.getPhysicalOperator().getOperatorTag() != PhysicalOperatorTag.SORT_MERGE_EXCHANGE) {
+            return false;
+        }
+        if (op1.getPhysicalOperator().getOperatorTag() == PhysicalOperatorTag.HASH_PARTITION_MERGE_EXCHANGE) {
+            // if it is a hash_partition_merge_exchange, the sort_merge_exchange can be simply removed
+            op1.getInputs().get(0).setValue(op2.getInputs().get(0).getValue());
+            op1.computeDeliveredPhysicalProperties(context);
+            return true;
+        }
+        HashPartitionExchangePOperator hpe = (HashPartitionExchangePOperator) op1.getPhysicalOperator();
+        SortMergeExchangePOperator sme = (SortMergeExchangePOperator) op2.getPhysicalOperator();
+        List<OrderColumn> ocList = new ArrayList<OrderColumn>();
+        for (OrderColumn oc : sme.getSortColumns()) {
+            ocList.add(oc);
+        }
+        HashPartitionMergeExchangePOperator hpme = new HashPartitionMergeExchangePOperator(ocList, hpe.getHashFields(),
+                hpe.getDomain());
+        op1.setPhysicalOperator(hpme);
+        op1.getInputs().get(0).setValue(op2.getInputs().get(0).getValue());
+        op1.computeDeliveredPhysicalProperties(context);
+        return true;
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroJoinInsideSubplanRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroJoinInsideSubplanRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroJoinInsideSubplanRule.java
new file mode 100644
index 0000000..8929623
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroJoinInsideSubplanRule.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.HashSet;
+import java.util.ListIterator;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.InnerJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.NestedTupleSourceOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorManipulationUtil;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+
+public class IntroJoinInsideSubplanRule extends AbstractDecorrelationRule {
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op0 = (AbstractLogicalOperator) opRef.getValue();
+        if (op0.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+            return false;
+        }
+        SubplanOperator subplan = (SubplanOperator) op0;
+
+        Mutable<ILogicalOperator> leftRef = subplan.getInputs().get(0);
+        if (((AbstractLogicalOperator) leftRef.getValue()).getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE) {
+            return false;
+        }
+
+        ListIterator<ILogicalPlan> plansIter = subplan.getNestedPlans().listIterator();
+        ILogicalPlan p = null;
+        while (plansIter.hasNext()) {
+            p = plansIter.next();
+        }
+        if (p == null) {
+            return false;
+        }
+        if (p.getRoots().size() != 1) {
+            return false;
+        }
+        Mutable<ILogicalOperator> opRef1 = p.getRoots().get(0);
+
+        while (true) {
+            AbstractLogicalOperator op1 = (AbstractLogicalOperator) opRef1.getValue();
+            if (op1.getInputs().size() != 1) {
+                return false;
+            }
+            if (op1.getOperatorTag() == LogicalOperatorTag.SELECT) {
+                Mutable<ILogicalOperator> op2Ref = op1.getInputs().get(0);
+                AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+                if (op2.getOperatorTag() != LogicalOperatorTag.SELECT && descOrSelfIsScanOrJoin(op2)) {
+                    Set<LogicalVariable> free2 = new HashSet<LogicalVariable>();
+                    OperatorPropertiesUtil.getFreeVariablesInSelfOrDesc(op2, free2);
+                    if (free2.isEmpty()) {
+                        Set<LogicalVariable> free1 = new HashSet<LogicalVariable>();
+                        OperatorPropertiesUtil.getFreeVariablesInSelfOrDesc(op1, free1);
+                        if (!free1.isEmpty()) {
+                            OperatorManipulationUtil.ntsToEts(op2Ref, context);
+                            NestedTupleSourceOperator nts = new NestedTupleSourceOperator(
+                                    new MutableObject<ILogicalOperator>(subplan));
+                            Mutable<ILogicalOperator> ntsRef = new MutableObject<ILogicalOperator>(nts);
+                            Mutable<ILogicalOperator> innerRef = new MutableObject<ILogicalOperator>(op2);
+                            InnerJoinOperator join = new InnerJoinOperator(new MutableObject<ILogicalExpression>(
+                                    ConstantExpression.TRUE), ntsRef, innerRef);
+                            op2Ref.setValue(join);
+                            context.computeAndSetTypeEnvironmentForOperator(nts);
+                            context.computeAndSetTypeEnvironmentForOperator(join);
+                            return true;
+                        }
+                    }
+                }
+            }
+            opRef1 = op1.getInputs().get(0);
+        }
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceAggregateCombinerRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceAggregateCombinerRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceAggregateCombinerRule.java
new file mode 100644
index 0000000..b0dbb1e
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceAggregateCombinerRule.java
@@ -0,0 +1,57 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.HashSet;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.utils.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AggregateOperator;
+
+public class IntroduceAggregateCombinerRule extends AbstractIntroduceCombinerRule {
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (context.checkIfInDontApplySet(this, op)) {
+            return false;
+        }
+        context.addToDontApplySet(this, op);
+        if (op.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+            return false;
+        }
+        AggregateOperator aggOp = (AggregateOperator) op;
+        if (!aggOp.isGlobal() || aggOp.getExecutionMode() == ExecutionMode.LOCAL) {
+            return false;
+        }
+        Set<SimilarAggregatesInfo> toReplaceSet = new HashSet<SimilarAggregatesInfo>();
+        Pair<Boolean, Mutable<ILogicalOperator>> result = tryToPushAgg(aggOp, null, toReplaceSet, context);
+        if (!result.first || result.second == null) {
+            return false;
+        }
+        replaceOriginalAggFuncs(toReplaceSet);
+        context.computeAndSetTypeEnvironmentForOperator(aggOp);
+        return true;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByCombinerRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByCombinerRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByCombinerRule.java
new file mode 100644
index 0000000..aa418ea
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByCombinerRule.java
@@ -0,0 +1,31 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.List;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+
+public class IntroduceGroupByCombinerRule extends AbstractIntroduceGroupByCombinerRule {
+
+    @Override
+    protected void processNullTest(IOptimizationContext context, GroupByOperator nestedGby,
+            List<LogicalVariable> aggregateVarsProducedByCombiner) {
+        /** The default introduce group-by combiner rule ignores null test, however a language implementor can decide their own semantics. */
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java
new file mode 100644
index 0000000..a6d9ab0
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceGroupByForSubplanRule.java
@@ -0,0 +1,323 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ *
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
+import edu.uci.ics.hyracks.algebricks.common.utils.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AggregateOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.DataSourceScanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.NestedTupleSourceOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.plan.ALogicalPlanImpl;
+import edu.uci.ics.hyracks.algebricks.core.algebra.properties.FunctionalDependency;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorManipulationUtil;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.config.AlgebricksConfig;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+import edu.uci.ics.hyracks.algebricks.rewriter.util.PhysicalOptimizationsUtil;
+
+/**
+ * The rule searches for SUBPLAN operator with a optional PROJECT operator and
+ * an AGGREGATE followed by a join operator.
+ *
+ * <pre>
+ * Before
+ * 
+ *   plan__parent
+ *   SUBPLAN {
+ *     PROJECT?
+ *     AGGREGATE
+ *     plan__nested_A
+ *     INNER_JOIN | LEFT_OUTER_JOIN ($condition, $left, $right)
+ *       plan__nested_B
+ *   }
+ *   plan__child
+ * 
+ *   where $condition does not equal a constant true.
+ * 
+ * After (This is a general application of the rule, specifics may vary based on the query plan.)
+ * 
+ *   plan__parent
+ *   GROUP_BY {
+ *     PROJECT?
+ *     AGGREGATE
+ *     plan__nested_A
+ *     SELECT( algebricks:not( is_null( $right ) ) )
+ *     NESTED_TUPLE_SOURCE
+ *   }
+ *   SUBPLAN {
+ *     INNER_JOIN | LEFT_OUTER_JOIN ($condition, $left, $right)
+ *       plan__nested_B
+ *   }
+ *   plan__child
+ * </pre>
+ *
+ * @author prestonc
+ */
+
+public class IntroduceGroupByForSubplanRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op0 = (AbstractLogicalOperator) opRef.getValue();
+        if (op0.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+            return false;
+        }
+        SubplanOperator subplan = (SubplanOperator) op0;
+
+        Iterator<ILogicalPlan> plansIter = subplan.getNestedPlans().iterator();
+        ILogicalPlan p = null;
+        while (plansIter.hasNext()) {
+            p = plansIter.next();
+        }
+        if (p == null) {
+            return false;
+        }
+        if (p.getRoots().size() != 1) {
+            return false;
+        }
+        Mutable<ILogicalOperator> subplanRoot = p.getRoots().get(0);
+        AbstractLogicalOperator op1 = (AbstractLogicalOperator) subplanRoot.getValue();
+
+        Mutable<ILogicalOperator> botRef = subplanRoot;
+        AbstractLogicalOperator op2;
+        // Project is optional
+        if (op1.getOperatorTag() != LogicalOperatorTag.PROJECT) {
+            op2 = op1;
+        } else {
+            ProjectOperator project = (ProjectOperator) op1;
+            botRef = project.getInputs().get(0);
+            op2 = (AbstractLogicalOperator) botRef.getValue();
+        }
+        if (op2.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+            return false;
+        }
+        AggregateOperator aggregate = (AggregateOperator) op2;
+
+        Set<LogicalVariable> free = new HashSet<LogicalVariable>();
+        VariableUtilities.getUsedVariables(aggregate, free);
+
+        Mutable<ILogicalOperator> op3Ref = aggregate.getInputs().get(0);
+        AbstractLogicalOperator op3 = (AbstractLogicalOperator) op3Ref.getValue();
+
+        while (op3.getInputs().size() == 1) {
+            Set<LogicalVariable> prod = new HashSet<LogicalVariable>();
+            VariableUtilities.getProducedVariables(op3, prod);
+            free.removeAll(prod);
+            VariableUtilities.getUsedVariables(op3, free);
+            botRef = op3Ref;
+            op3Ref = op3.getInputs().get(0);
+            op3 = (AbstractLogicalOperator) op3Ref.getValue();
+        }
+
+        if (op3.getOperatorTag() != LogicalOperatorTag.INNERJOIN
+                && op3.getOperatorTag() != LogicalOperatorTag.LEFTOUTERJOIN) {
+            return false;
+        }
+        AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) op3;
+        if (join.getCondition().getValue() == ConstantExpression.TRUE) {
+            return false;
+        }
+        VariableUtilities.getUsedVariables(join, free);
+
+        AbstractLogicalOperator b0 = (AbstractLogicalOperator) join.getInputs().get(0).getValue();
+        // see if there's an NTS at the end of the pipeline
+        NestedTupleSourceOperator outerNts = getNts(b0);
+        if (outerNts == null) {
+            AbstractLogicalOperator b1 = (AbstractLogicalOperator) join.getInputs().get(1).getValue();
+            outerNts = getNts(b1);
+            if (outerNts == null) {
+                return false;
+            }
+        }
+
+        Set<LogicalVariable> pkVars = computeGbyVars(outerNts, free, context);
+        if (pkVars == null || pkVars.size() < 1) {
+            // there is no non-trivial primary key, group-by keys are all live variables
+            ILogicalOperator subplanInput = subplan.getInputs().get(0).getValue();
+            pkVars = new HashSet<LogicalVariable>();
+            VariableUtilities.getLiveVariables(subplanInput, pkVars);
+        }
+        AlgebricksConfig.ALGEBRICKS_LOGGER.fine("Found FD for introducing group-by: " + pkVars);
+
+        Mutable<ILogicalOperator> rightRef = join.getInputs().get(1);
+        LogicalVariable testForNull = null;
+        AbstractLogicalOperator right = (AbstractLogicalOperator) rightRef.getValue();
+        switch (right.getOperatorTag()) {
+            case UNNEST: {
+                UnnestOperator innerUnnest = (UnnestOperator) right;
+                // Select [ $y != null ]
+                testForNull = innerUnnest.getVariable();
+                break;
+            }
+            case RUNNINGAGGREGATE: {
+                ILogicalOperator inputToRunningAggregate = right.getInputs().get(0).getValue();
+                Set<LogicalVariable> producedVars = new ListSet<LogicalVariable>();
+                VariableUtilities.getProducedVariables(inputToRunningAggregate, producedVars);
+                if (!producedVars.isEmpty()) {
+                    // Select [ $y != null ]
+                    testForNull = producedVars.iterator().next();
+                }
+                break;
+            }
+            case DATASOURCESCAN: {
+                DataSourceScanOperator innerScan = (DataSourceScanOperator) right;
+                // Select [ $y != null ]
+                if (innerScan.getVariables().size() == 1) {
+                    testForNull = innerScan.getVariables().get(0);
+                }
+                break;
+            }
+        }
+        if (testForNull == null) {
+            testForNull = context.newVar();
+            AssignOperator tmpAsgn = new AssignOperator(testForNull, new MutableObject<ILogicalExpression>(
+                    ConstantExpression.TRUE));
+            tmpAsgn.getInputs().add(new MutableObject<ILogicalOperator>(rightRef.getValue()));
+            rightRef.setValue(tmpAsgn);
+            context.computeAndSetTypeEnvironmentForOperator(tmpAsgn);
+        }
+
+        IFunctionInfo finfoEq = context.getMetadataProvider().lookupFunction(AlgebricksBuiltinFunctions.IS_NULL);
+        ILogicalExpression isNullTest = new ScalarFunctionCallExpression(finfoEq,
+                new MutableObject<ILogicalExpression>(new VariableReferenceExpression(testForNull)));
+        IFunctionInfo finfoNot = context.getMetadataProvider().lookupFunction(AlgebricksBuiltinFunctions.NOT);
+        ScalarFunctionCallExpression nonNullTest = new ScalarFunctionCallExpression(finfoNot,
+                new MutableObject<ILogicalExpression>(isNullTest));
+        SelectOperator selectNonNull = new SelectOperator(new MutableObject<ILogicalExpression>(nonNullTest), false,
+                null);
+        GroupByOperator g = new GroupByOperator();
+        Mutable<ILogicalOperator> newSubplanRef = new MutableObject<ILogicalOperator>(subplan);
+        NestedTupleSourceOperator nts = new NestedTupleSourceOperator(new MutableObject<ILogicalOperator>(g));
+        opRef.setValue(g);
+        selectNonNull.getInputs().add(new MutableObject<ILogicalOperator>(nts));
+
+        List<Mutable<ILogicalOperator>> prodInpList = botRef.getValue().getInputs();
+        prodInpList.clear();
+        prodInpList.add(new MutableObject<ILogicalOperator>(selectNonNull));
+
+        ILogicalPlan gPlan = new ALogicalPlanImpl(new MutableObject<ILogicalOperator>(subplanRoot.getValue()));
+        g.getNestedPlans().add(gPlan);
+        subplanRoot.setValue(op3Ref.getValue());
+        g.getInputs().add(newSubplanRef);
+
+        HashSet<LogicalVariable> underVars = new HashSet<LogicalVariable>();
+        VariableUtilities.getLiveVariables(subplan.getInputs().get(0).getValue(), underVars);
+        underVars.removeAll(pkVars);
+        Map<LogicalVariable, LogicalVariable> mappedVars = buildVarExprList(pkVars, context, g, g.getGroupByList());
+        context.updatePrimaryKeys(mappedVars);
+        for (LogicalVariable uv : underVars) {
+            g.getDecorList().add(
+                    new Pair<LogicalVariable, Mutable<ILogicalExpression>>(null, new MutableObject<ILogicalExpression>(
+                            new VariableReferenceExpression(uv))));
+        }
+        OperatorPropertiesUtil.typeOpRec(subplanRoot, context);
+        OperatorPropertiesUtil.typeOpRec(gPlan.getRoots().get(0), context);
+        context.computeAndSetTypeEnvironmentForOperator(g);
+        return true;
+    }
+
+    private NestedTupleSourceOperator getNts(AbstractLogicalOperator op) {
+        AbstractLogicalOperator alo = op;
+        do {
+            if (alo.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
+                return (NestedTupleSourceOperator) alo;
+            }
+            if (alo.getInputs().size() != 1) {
+                return null;
+            }
+            alo = (AbstractLogicalOperator) alo.getInputs().get(0).getValue();
+        } while (true);
+    }
+
+    protected Set<LogicalVariable> computeGbyVars(AbstractLogicalOperator op, Set<LogicalVariable> freeVars,
+            IOptimizationContext context) throws AlgebricksException {
+        PhysicalOptimizationsUtil.computeFDsAndEquivalenceClasses(op, context);
+        List<FunctionalDependency> fdList = context.getFDList(op);
+        if (fdList == null) {
+            return null;
+        }
+        // check if any of the FDs is a key
+        List<LogicalVariable> all = new ArrayList<LogicalVariable>();
+        VariableUtilities.getLiveVariables(op, all);
+        all.retainAll(freeVars);
+        for (FunctionalDependency fd : fdList) {
+            if (fd.getTail().containsAll(all)) {
+                return new HashSet<LogicalVariable>(fd.getHead());
+            }
+        }
+        return null;
+    }
+
+    private Map<LogicalVariable, LogicalVariable> buildVarExprList(Collection<LogicalVariable> vars,
+            IOptimizationContext context, GroupByOperator g,
+            List<Pair<LogicalVariable, Mutable<ILogicalExpression>>> outVeList) throws AlgebricksException {
+        Map<LogicalVariable, LogicalVariable> m = new HashMap<LogicalVariable, LogicalVariable>();
+        for (LogicalVariable ov : vars) {
+            LogicalVariable newVar = context.newVar();
+            ILogicalExpression varExpr = new VariableReferenceExpression(newVar);
+            outVeList.add(new Pair<LogicalVariable, Mutable<ILogicalExpression>>(ov,
+                    new MutableObject<ILogicalExpression>(varExpr)));
+            for (ILogicalPlan p : g.getNestedPlans()) {
+                for (Mutable<ILogicalOperator> r : p.getRoots()) {
+                    OperatorManipulationUtil.substituteVarRec((AbstractLogicalOperator) r.getValue(), ov, newVar, true,
+                            context);
+                }
+            }
+            AbstractLogicalOperator opUnder = (AbstractLogicalOperator) g.getInputs().get(0).getValue();
+            OperatorManipulationUtil.substituteVarRec(opUnder, ov, newVar, true, context);
+            m.put(ov, newVar);
+        }
+        return m;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java
new file mode 100644
index 0000000..3c96bc2
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IntroduceProjectsRule.java
@@ -0,0 +1,171 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.utils.Triple;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnionAllOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Projects away unused variables at the earliest possible point.
+ * Does a full DFS sweep of the plan adding ProjectOperators in the bottom-up pass.
+ * Also, removes projects that have become useless.
+ * TODO: This rule 'recklessly' adds as many projects as possible, but there is no guarantee
+ * that the overall cost of the plan is reduced since project operators also add a cost.
+ */
+public class IntroduceProjectsRule implements IAlgebraicRewriteRule {
+
+    private final Set<LogicalVariable> usedVars = new HashSet<LogicalVariable>();
+    private final Set<LogicalVariable> liveVars = new HashSet<LogicalVariable>();
+    private final Set<LogicalVariable> producedVars = new HashSet<LogicalVariable>();
+    private final List<LogicalVariable> projectVars = new ArrayList<LogicalVariable>();
+    protected boolean hasRun = false;
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        if (hasRun) {
+            return false;
+        }
+        hasRun = true;
+        return introduceProjects(null, -1, opRef, Collections.<LogicalVariable> emptySet(), context);
+    }
+
+    protected boolean introduceProjects(AbstractLogicalOperator parentOp, int parentInputIndex,
+            Mutable<ILogicalOperator> opRef, Set<LogicalVariable> parentUsedVars, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        boolean modified = false;
+
+        usedVars.clear();
+        VariableUtilities.getUsedVariables(op, usedVars);
+
+        // In the top-down pass, maintain a set of variables that are used in op and all its parents.
+        HashSet<LogicalVariable> parentsUsedVars = new HashSet<LogicalVariable>();
+        parentsUsedVars.addAll(parentUsedVars);
+        parentsUsedVars.addAll(usedVars);
+
+        // Descend into children.        
+        for (int i = 0; i < op.getInputs().size(); i++) {
+            Mutable<ILogicalOperator> inputOpRef = op.getInputs().get(i);
+            if (introduceProjects(op, i, inputOpRef, parentsUsedVars, context)) {
+                modified = true;
+            }
+        }
+
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(op);
+        }
+        // In the bottom-up pass, determine which live variables are not used by op's parents.
+        // Such variables are be projected away.
+        liveVars.clear();
+        VariableUtilities.getLiveVariables(op, liveVars);
+        producedVars.clear();
+        VariableUtilities.getProducedVariables(op, producedVars);
+        liveVars.removeAll(producedVars);
+
+        projectVars.clear();
+        for (LogicalVariable liveVar : liveVars) {
+            if (parentsUsedVars.contains(liveVar)) {
+                projectVars.add(liveVar);
+            }
+        }
+
+        // Some of the variables that are live at this op are not used above.
+        if (projectVars.size() != liveVars.size()) {
+            // Add a project operator under each of op's qualifying input branches.
+            for (int i = 0; i < op.getInputs().size(); i++) {
+                ILogicalOperator childOp = op.getInputs().get(i).getValue();
+                liveVars.clear();
+                VariableUtilities.getLiveVariables(childOp, liveVars);
+                List<LogicalVariable> vars = new ArrayList<LogicalVariable>();
+                vars.addAll(projectVars);
+                // Only retain those variables that are live in the i-th input branch.
+                vars.retainAll(liveVars);
+                if (vars.size() != liveVars.size()) {
+                    ProjectOperator projectOp = new ProjectOperator(vars);
+                    projectOp.getInputs().add(new MutableObject<ILogicalOperator>(childOp));
+                    op.getInputs().get(i).setValue(projectOp);
+                    context.computeAndSetTypeEnvironmentForOperator(projectOp);
+                    modified = true;
+                }
+            }
+        } else if (op.getOperatorTag() == LogicalOperatorTag.PROJECT) {
+            // Check if the existing project has become useless.
+            liveVars.clear();
+            VariableUtilities.getLiveVariables(op.getInputs().get(0).getValue(), liveVars);
+            ProjectOperator projectOp = (ProjectOperator) op;
+            List<LogicalVariable> projectVars = projectOp.getVariables();
+            if (liveVars.size() == projectVars.size() && liveVars.containsAll(projectVars)) {
+                boolean eliminateProject = true;
+                // For UnionAll the variables must also be in exactly the correct order.
+                if (parentOp.getOperatorTag() == LogicalOperatorTag.UNIONALL) {
+                    eliminateProject = canEliminateProjectBelowUnion((UnionAllOperator) parentOp, projectOp,
+                            parentInputIndex);
+                }
+                if (eliminateProject) {
+                    // The existing project has become useless. Remove it.
+                    parentOp.getInputs().get(parentInputIndex).setValue(op.getInputs().get(0).getValue());
+                }
+            }
+        }
+
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(op);
+        }
+        return modified;
+    }
+    
+    private boolean canEliminateProjectBelowUnion(UnionAllOperator unionOp, ProjectOperator projectOp,
+            int unionInputIndex) throws AlgebricksException {
+        List<LogicalVariable> orderedLiveVars = new ArrayList<LogicalVariable>();
+        VariableUtilities.getLiveVariables(projectOp.getInputs().get(0).getValue(), orderedLiveVars);
+        int numVars = orderedLiveVars.size();
+        for (int i = 0; i < numVars; i++) {
+            Triple<LogicalVariable, LogicalVariable, LogicalVariable> varTriple = unionOp.getVariableMappings().get(i);
+            if (unionInputIndex == 0) {
+                if (varTriple.first != orderedLiveVars.get(i)) {
+                    return false;
+                }
+            } else {
+                if (varTriple.second != orderedLiveVars.get(i)) {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java
new file mode 100644
index 0000000..71af64b
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/IsolateHyracksOperatorsRule.java
@@ -0,0 +1,140 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IPhysicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.PhysicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ExchangeOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.OneToOneExchangePOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class IsolateHyracksOperatorsRule implements IAlgebraicRewriteRule {
+
+    private final PhysicalOperatorTag[] operatorsBelowWhichJobGenIsDisabled;
+
+    public IsolateHyracksOperatorsRule(PhysicalOperatorTag[] operatorsBelowWhichJobGenIsDisabled) {
+        this.operatorsBelowWhichJobGenIsDisabled = operatorsBelowWhichJobGenIsDisabled;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        IPhysicalOperator pt = op.getPhysicalOperator();
+
+        if (pt == null || op.getOperatorTag() == LogicalOperatorTag.EXCHANGE) {
+            return false;
+        }
+        if (!pt.isMicroOperator()) {
+            return testIfExchangeBelow(opRef, context);
+        } else {
+            return testIfExchangeAbove(opRef, context);
+        }
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    private boolean testIfExchangeBelow(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        boolean exchInserted = false;
+
+        for (Mutable<ILogicalOperator> i : op.getInputs()) {
+            AbstractLogicalOperator c = (AbstractLogicalOperator) i.getValue();
+            if (c.getOperatorTag() != LogicalOperatorTag.EXCHANGE) {
+                if (c.getPhysicalOperator() == null) {
+                    return false;
+                }
+                insertOneToOneExchange(i, context);
+                exchInserted = true;
+            }
+        }
+        IPhysicalOperator pt = op.getPhysicalOperator();
+        if (pt.isJobGenDisabledBelowMe() || arrayContains(operatorsBelowWhichJobGenIsDisabled, pt.getOperatorTag())) {
+            for (Mutable<ILogicalOperator> i : op.getInputs()) {
+                disableJobGenRec(i.getValue());
+            }
+        }
+        return exchInserted;
+    }
+
+    private void disableJobGenRec(ILogicalOperator operator) {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) operator;
+        op.disableJobGen();
+        for (Mutable<ILogicalOperator> i : op.getInputs()) {
+            disableJobGenRec(i.getValue());
+        }
+    }
+
+    private boolean testIfExchangeAbove(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() == LogicalOperatorTag.EXCHANGE) {
+            return false;
+        }
+        boolean exchInserted = false;
+        for (Mutable<ILogicalOperator> i : op.getInputs()) {
+            AbstractLogicalOperator c = (AbstractLogicalOperator) i.getValue();
+            IPhysicalOperator cpop = c.getPhysicalOperator();
+            if (c.getOperatorTag() == LogicalOperatorTag.EXCHANGE || cpop == null) {
+                continue;
+            }
+            if (!cpop.isMicroOperator()) {
+                insertOneToOneExchange(i, context);
+                exchInserted = true;
+            }
+        }
+        return exchInserted;
+    }
+
+    private final static <T> boolean arrayContains(T[] array, T tag) {
+        for (int i = 0; i < array.length; i++) {
+            if (array[i] == tag) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private final static void insertOneToOneExchange(Mutable<ILogicalOperator> i, IOptimizationContext context)
+            throws AlgebricksException {
+        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);
+        context.computeAndSetTypeEnvironmentForOperator(e);
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java
new file mode 100644
index 0000000..5867abd
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/MoveFreeVariableOperatorOutOfSubplanRule.java
@@ -0,0 +1,183 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ *
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.HashSet;
+import java.util.ListIterator;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.rewriter.rules.AbstractDecorrelationRule;
+
+/**
+ * The rule searches for operators that can be moved outside the subplan.
+ *
+ * <pre>
+ * Before
+ * 
+ *   %PARENT_PLAN
+ *   SUBPLAN{
+ *     %NESTED_OPERATORS_B+
+ *     ASSIGN || %SUBPLAN
+ *     %NESTED_OPERATORS_A*
+ *     NESTEDTUPLESOURCE
+ *   }
+ *   %CHILD_PLAN
+ * 
+ *   where
+ *     %SUBPLAN has one nested plan with a root AGGREGATE operator.
+ * 
+ * After
+ * 
+ *   %PARENT_PLAN
+ *   SUBPLAN{
+ *     %NESTED_OPERATORS_B+
+ *     %NESTED_OPERATORS_A*
+ *     NESTEDTUPLESOURCE
+ *   }
+ *   ASSIGN || %SUBPLAN
+ *   %CHILD_PLAN
+ * </pre>
+ */
+public class MoveFreeVariableOperatorOutOfSubplanRule extends AbstractDecorrelationRule {
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op0 = (AbstractLogicalOperator) opRef.getValue();
+        if (op0.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+            return false;
+        }
+        SubplanOperator subplan = (SubplanOperator) op0;
+
+        Mutable<ILogicalOperator> leftRef = subplan.getInputs().get(0);
+        if (((AbstractLogicalOperator) leftRef.getValue()).getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE) {
+            return false;
+        }
+
+        ListIterator<ILogicalPlan> plansIter = subplan.getNestedPlans().listIterator();
+        ILogicalPlan p = null;
+        while (plansIter.hasNext()) {
+            p = plansIter.next();
+        }
+        if (p == null) {
+            return false;
+        }
+        if (p.getRoots().size() != 1) {
+            return false;
+        }
+        Mutable<ILogicalOperator> opRef1 = p.getRoots().get(0);
+
+        //The root operator will not be movable. Start with the second op
+        AbstractLogicalOperator op1 = (AbstractLogicalOperator) opRef1.getValue();
+        if (op1.getInputs().size() != 1) {
+            return false;
+        }
+        Mutable<ILogicalOperator> op2Ref = op1.getInputs().get(0);
+
+        //Get all variables that come from outside of the loop
+        Set<LogicalVariable> free = new HashSet<LogicalVariable>();
+        OperatorPropertiesUtil.getFreeVariablesInSelfOrDesc(op1, free);
+
+        while (op2Ref != null) {
+            //Get the operator that we want to look at
+            AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+
+            //Make sure we are looking at subplan with a scan/join
+            if (op2.getInputs().size() != 1 || !descOrSelfIsScanOrJoin(op2)) {
+                return false;
+            }
+            boolean notApplicable = false;
+
+            //Get its used variables
+            Set<LogicalVariable> used = new HashSet<LogicalVariable>();
+
+            //not movable if the operator is not an assign or subplan
+            //Might be helpful in the future for other operations in the future
+            if (movableOperator(op2.getOperatorTag())) {
+                if (op2.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+                    VariableUtilities.getUsedVariables(op2, used);
+                } else if (op2.getOperatorTag() == LogicalOperatorTag.SUBPLAN) {
+                    // Nested plan must have an aggregate root.
+                    ListIterator<ILogicalPlan> subplansIter = ((SubplanOperator) op2).getNestedPlans().listIterator();
+                    ILogicalPlan plan = null;
+                    while (subplansIter.hasNext()) {
+                        plan = subplansIter.next();
+                    }
+                    if (plan == null) {
+                        return false;
+                    }
+                    if (plan.getRoots().size() != 1) {
+                        return false;
+                    }
+                    ILogicalOperator op3 = plan.getRoots().get(0).getValue();
+                    if (op3.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+                        return false;
+                    }
+                    // Used variables do not include ones created in the subplan.
+                    VariableUtilities.getUsedVariables(op2, used);
+                    Set<LogicalVariable> subplanProducedAndDown = new HashSet<LogicalVariable>();
+                    VariableUtilities.getProducedVariablesInDescendantsAndSelf(op3, subplanProducedAndDown);
+                    used.removeAll(subplanProducedAndDown);
+                } else {
+                    notApplicable = true;
+                }
+            } else {
+                notApplicable = true;
+            }
+
+            //Make sure that all of its used variables come from outside
+            for (LogicalVariable var : used) {
+                if (!free.contains(var)) {
+                    notApplicable = true;
+                }
+            }
+
+            if (notApplicable) {
+                op2Ref = op2.getInputs().get(0);
+            } else {
+                //Make the input of op2 be the input of op1
+                op2Ref.setValue(op2.getInputs().get(0).getValue());
+
+                //Make the outside of the subplan the input of op2
+                Mutable<ILogicalOperator> outsideRef = op2.getInputs().get(0);
+                outsideRef.setValue(op0.getInputs().get(0).getValue());
+
+                //Make op2 the input of the subplan
+                Mutable<ILogicalOperator> op2OutsideRef = op0.getInputs().get(0);
+                op2OutsideRef.setValue(op2);
+
+                return true;
+            }
+
+        }
+        return false;
+    }
+
+    protected boolean movableOperator(LogicalOperatorTag operatorTag) {
+        return (operatorTag == LogicalOperatorTag.ASSIGN || operatorTag == LogicalOperatorTag.SUBPLAN);
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/NestedSubplanToJoinRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/NestedSubplanToJoinRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/NestedSubplanToJoinRule.java
new file mode 100644
index 0000000..6484202
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/NestedSubplanToJoinRule.java
@@ -0,0 +1,136 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ * 
+ *     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 edu.uci.ics.hyracks.algebricks.rewriter.rules;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.EmptyTupleSourceOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.LeftOuterJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * replace Subplan operators with nested loop joins where the join condition is true, if the Subplan
+ * does not contain free variables (does not have correlations to the input stream).
+ * 
+ * @author yingyib
+ */
+public class NestedSubplanToJoinRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        if (context.checkIfInDontApplySet(this, opRef.getValue()))
+            return false;
+        context.addToDontApplySet(this, opRef.getValue());
+
+        ILogicalOperator op1 = opRef.getValue();
+        if (op1.getInputs().size() == 0) {
+            return false;
+        }
+
+        boolean rewritten = false;
+        for (int index = 0; index < op1.getInputs().size(); index++) {
+            AbstractLogicalOperator child = (AbstractLogicalOperator) op1.getInputs().get(index).getValue();
+            if (child.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+                continue;
+            }
+
+            AbstractOperatorWithNestedPlans subplan = (AbstractOperatorWithNestedPlans) child;
+            Set<LogicalVariable> freeVars = new HashSet<LogicalVariable>();
+            OperatorPropertiesUtil.getFreeVariablesInSubplans(subplan, freeVars);
+            if (!freeVars.isEmpty()) {
+                /**
+                 * the subplan is correlated with the outer plan, other rules can deal with it
+                 */
+                continue;
+            }
+
+            /** get the input operator of the subplan operator */
+            ILogicalOperator subplanInput = subplan.getInputs().get(0).getValue();
+            AbstractLogicalOperator subplanInputOp = (AbstractLogicalOperator) subplanInput;
+
+            /** If the other join branch is a trivial plan, do not do the rewriting. */
+            if (subplanInputOp.getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE) {
+                continue;
+            }
+
+            /** get all nested top operators */
+            List<ILogicalPlan> nestedPlans = subplan.getNestedPlans();
+            List<Mutable<ILogicalOperator>> nestedRoots = new ArrayList<Mutable<ILogicalOperator>>();
+            for (ILogicalPlan nestedPlan : nestedPlans) {
+                nestedRoots.addAll(nestedPlan.getRoots());
+            }
+            if (nestedRoots.size() == 0) {
+                /** there is no nested top operators */
+                continue;
+            }
+
+            /** expend the input and roots into a DAG of nested loop joins */
+            Mutable<ILogicalExpression> expr = new MutableObject<ILogicalExpression>(ConstantExpression.TRUE);
+            Mutable<ILogicalOperator> nestedRootRef = nestedRoots.get(0);
+            ILogicalOperator join = new LeftOuterJoinOperator(expr, new MutableObject<ILogicalOperator>(subplanInput),
+                    nestedRootRef);
+
+            /** rewrite the nested tuple source to be empty tuple source */
+            rewriteNestedTupleSource(nestedRootRef);
+
+            for (int i = 1; i < nestedRoots.size(); i++) {
+                join = new LeftOuterJoinOperator(expr, new MutableObject<ILogicalOperator>(join), nestedRoots.get(i));
+            }
+            op1.getInputs().get(index).setValue(join);
+            context.computeAndSetTypeEnvironmentForOperator(join);
+            rewritten = true;
+        }
+        return rewritten;
+    }
+
+    /**
+     * rewrite NestedTupleSource operators to EmptyTupleSource operators
+     * 
+     * @param nestedRootRef
+     */
+    private void rewriteNestedTupleSource(Mutable<ILogicalOperator> nestedRootRef) {
+        AbstractLogicalOperator nestedRoot = (AbstractLogicalOperator) nestedRootRef.getValue();
+        if (nestedRoot.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
+            nestedRootRef.setValue(new EmptyTupleSourceOperator());
+        }
+        List<Mutable<ILogicalOperator>> inputs = nestedRoot.getInputs();
+        for (Mutable<ILogicalOperator> input : inputs) {
+            rewriteNestedTupleSource(input);
+        }
+    }
+}


Mime
View raw message