asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ima...@apache.org
Subject [06/51] [partial] incubator-asterixdb-hyracks git commit: Change folder structure for Java repackage
Date Tue, 25 Aug 2015 16:41:19 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/PullSelectOutOfEqJoin.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PullSelectOutOfEqJoin.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PullSelectOutOfEqJoin.java
new file mode 100644
index 0000000..b268e77
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PullSelectOutOfEqJoin.java
@@ -0,0 +1,114 @@
+/*
+ * 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.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.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+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.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PullSelectOutOfEqJoin 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 op = (AbstractLogicalOperator) opRef.getValue();
+
+        if (op.getOperatorTag() != LogicalOperatorTag.INNERJOIN) {
+            return false;
+        }
+        AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) op;
+
+        ILogicalExpression expr = join.getCondition().getValue();
+        if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return false;
+        }
+        AbstractFunctionCallExpression fexp = (AbstractFunctionCallExpression) expr;
+        FunctionIdentifier fi = fexp.getFunctionIdentifier();
+        if (!fi.equals(AlgebricksBuiltinFunctions.AND)) {
+            return false;
+        }
+        List<Mutable<ILogicalExpression>> eqVarVarComps = new ArrayList<Mutable<ILogicalExpression>>();
+        List<Mutable<ILogicalExpression>> otherPredicates = new ArrayList<Mutable<ILogicalExpression>>();
+        for (Mutable<ILogicalExpression> arg : fexp.getArguments()) {
+            if (isEqVarVar(arg.getValue())) {
+                eqVarVarComps.add(arg);
+            } else {
+                otherPredicates.add(arg);
+            }
+        }
+        if (eqVarVarComps.isEmpty() || otherPredicates.isEmpty()) {
+            return false;
+        }
+        // pull up
+        ILogicalExpression pulledCond = makeCondition(otherPredicates, context);
+        SelectOperator select = new SelectOperator(new MutableObject<ILogicalExpression>(pulledCond), false, null);
+        ILogicalExpression newJoinCond = makeCondition(eqVarVarComps, context);
+        join.getCondition().setValue(newJoinCond);
+        select.getInputs().add(new MutableObject<ILogicalOperator>(join));
+        opRef.setValue(select);
+        context.computeAndSetTypeEnvironmentForOperator(select);
+        return true;
+    }
+
+    private ILogicalExpression makeCondition(List<Mutable<ILogicalExpression>> predList, IOptimizationContext context) {
+        if (predList.size() > 1) {
+            IFunctionInfo finfo = context.getMetadataProvider().lookupFunction(AlgebricksBuiltinFunctions.AND);
+            return new ScalarFunctionCallExpression(finfo, predList);
+        } else {
+            return predList.get(0).getValue();
+        }
+    }
+
+    private boolean isEqVarVar(ILogicalExpression expr) {
+        if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return false;
+        }
+        AbstractFunctionCallExpression f = (AbstractFunctionCallExpression) expr;
+        if (!f.getFunctionIdentifier().equals(AlgebricksBuiltinFunctions.EQ)) {
+            return false;
+        }
+        ILogicalExpression e1 = f.getArguments().get(0).getValue();
+        if (e1.getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+            return false;
+        } else {
+            ILogicalExpression e2 = f.getArguments().get(1).getValue();
+            return e2.getExpressionTag() == LogicalExpressionTag.VARIABLE;
+        }
+    }
+
+}

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/PushAssignBelowUnionAllRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignBelowUnionAllRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignBelowUnionAllRule.java
new file mode 100644
index 0000000..418ee36
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignBelowUnionAllRule.java
@@ -0,0 +1,165 @@
+/*
+ * 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.common.utils.Triple;
+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.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.AssignOperator;
+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;
+
+/**
+ * Pushes an AssignOperator below a UnionAll operator by creating an new AssignOperator below each of
+ * the UnionAllOperator's branches with appropriate variable replacements.
+ * This rule can help to enable other rules that are difficult to fire across a UnionAllOperator,
+ * for example, eliminating common sub-expressions.
+ * Example:
+ * Before plan:
+ * ...
+ * assign [$$20, $$21] <- [funcA($$3), funcB($$6)]
+ * union ($$1, $$2, $$3) ($$4, $$5, $$6)
+ * union_branch_0
+ * ...
+ * union_branch_1
+ * ...
+ * After plan:
+ * ...
+ * union ($$1, $$2, $$3) ($$4, $$5, $$6) ($$22, $$24, $$20) ($$23, $$25, $$21)
+ * assign [$$22, $$23] <- [funcA($$1), funcB($$4)]
+ * union_branch_0
+ * ...
+ * assign [$$24, $$25] <- [funcA($$2), funcB($$5)]
+ * union_branch_1
+ * ...
+ */
+public class PushAssignBelowUnionAllRule 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 op = (AbstractLogicalOperator) opRef.getValue();
+        if (!op.hasInputs()) {
+            return false;
+        }
+
+        boolean modified = false;
+        for (int i = 0; i < op.getInputs().size(); i++) {
+            AbstractLogicalOperator childOp = (AbstractLogicalOperator) op.getInputs().get(i).getValue();
+            if (childOp.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+                continue;
+            }
+            AssignOperator assignOp = (AssignOperator) childOp;
+            for (Mutable<ILogicalExpression> expr : assignOp.getExpressions()) {
+                if (!expr.getValue().isFunctional()) {
+                    return false;
+                }
+            }
+
+            AbstractLogicalOperator childOfChildOp = (AbstractLogicalOperator) assignOp.getInputs().get(0).getValue();
+            if (childOfChildOp.getOperatorTag() != LogicalOperatorTag.UNIONALL) {
+                continue;
+            }
+            UnionAllOperator unionOp = (UnionAllOperator) childOfChildOp;
+
+            Set<LogicalVariable> assignUsedVars = new HashSet<LogicalVariable>();
+            VariableUtilities.getUsedVariables(assignOp, assignUsedVars);
+
+            List<LogicalVariable> assignVars = assignOp.getVariables();
+
+            AssignOperator[] newAssignOps = new AssignOperator[2];
+            for (int j = 0; j < unionOp.getInputs().size(); j++) {
+                newAssignOps[j] = createAssignBelowUnionAllBranch(unionOp, j, assignOp, assignUsedVars, context);
+            }
+            // Add original assign variables to the union variable mappings.
+            for (int j = 0; j < assignVars.size(); j++) {
+                LogicalVariable first = newAssignOps[0].getVariables().get(j);
+                LogicalVariable second = newAssignOps[1].getVariables().get(j);
+                Triple<LogicalVariable, LogicalVariable, LogicalVariable> varMapping = new Triple<LogicalVariable, LogicalVariable, LogicalVariable>(
+                        first, second, assignVars.get(j));
+                unionOp.getVariableMappings().add(varMapping);
+            }
+            context.computeAndSetTypeEnvironmentForOperator(unionOp);
+
+            // Remove original assign operator.
+            op.getInputs().set(i, assignOp.getInputs().get(0));
+            context.computeAndSetTypeEnvironmentForOperator(op);
+            modified = true;
+        }
+
+        return modified;
+    }
+
+    private AssignOperator createAssignBelowUnionAllBranch(UnionAllOperator unionOp, int inputIndex,
+            AssignOperator originalAssignOp, Set<LogicalVariable> assignUsedVars, IOptimizationContext context)
+            throws AlgebricksException {
+        AssignOperator newAssignOp = cloneAssignOperator(originalAssignOp, context);
+        newAssignOp.getInputs()
+                .add(new MutableObject<ILogicalOperator>(unionOp.getInputs().get(inputIndex).getValue()));
+        context.computeAndSetTypeEnvironmentForOperator(newAssignOp);
+        unionOp.getInputs().get(inputIndex).setValue(newAssignOp);
+        int numVarMappings = unionOp.getVariableMappings().size();
+        for (int i = 0; i < numVarMappings; i++) {
+            Triple<LogicalVariable, LogicalVariable, LogicalVariable> varMapping = unionOp.getVariableMappings().get(i);
+            if (assignUsedVars.contains(varMapping.third)) {
+                LogicalVariable replacementVar;
+                if (inputIndex == 0) {
+                    replacementVar = varMapping.first;
+                } else {
+                    replacementVar = varMapping.second;
+                }
+                VariableUtilities.substituteVariables(newAssignOp, varMapping.third, replacementVar, context);
+            }
+        }
+        return newAssignOp;
+    }
+
+    /**
+     * Clones the given assign operator changing the returned variables to be new ones.
+     * Also, leaves the inputs of the clone clear.
+     */
+    private AssignOperator cloneAssignOperator(AssignOperator assignOp, IOptimizationContext context) {
+        List<LogicalVariable> vars = new ArrayList<LogicalVariable>();
+        List<Mutable<ILogicalExpression>> exprs = new ArrayList<Mutable<ILogicalExpression>>();
+        int numVars = assignOp.getVariables().size();
+        for (int i = 0; i < numVars; i++) {
+            vars.add(context.newVar());
+            exprs.add(new MutableObject<ILogicalExpression>(assignOp.getExpressions().get(i).getValue()
+                    .cloneExpression()));
+        }
+        AssignOperator assignCloneOp = new AssignOperator(vars, exprs);
+        assignCloneOp.setExecutionMode(assignOp.getExecutionMode());
+        return assignCloneOp;
+    }
+}

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/PushAssignDownThroughProductRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignDownThroughProductRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignDownThroughProductRule.java
new file mode 100644
index 0000000..d8523f6
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushAssignDownThroughProductRule.java
@@ -0,0 +1,87 @@
+/*
+ * 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.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.AbstractBinaryJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushAssignDownThroughProductRule 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.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+            return false;
+        }
+        Mutable<ILogicalOperator> op2Ref = op1.getInputs().get(0);
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+        if (op2.getOperatorTag() != LogicalOperatorTag.INNERJOIN) {
+            return false;
+        }
+        AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) op2;
+        if (join.getCondition().getValue() != ConstantExpression.TRUE) {
+            return false;
+        }
+
+        List<LogicalVariable> used = new ArrayList<LogicalVariable>();
+        VariableUtilities.getUsedVariables(op1, used);
+
+        Mutable<ILogicalOperator> b0Ref = op2.getInputs().get(0);
+        ILogicalOperator b0 = b0Ref.getValue();
+        List<LogicalVariable> b0Scm = new ArrayList<LogicalVariable>();
+        VariableUtilities.getLiveVariables(b0, b0Scm);
+        if (b0Scm.containsAll(used)) {
+            // push assign on left branch
+            op2Ref.setValue(b0);
+            b0Ref.setValue(op1);
+            opRef.setValue(op2);
+            return true;
+        } else {
+            Mutable<ILogicalOperator> b1Ref = op2.getInputs().get(1);
+            ILogicalOperator b1 = b1Ref.getValue();
+            List<LogicalVariable> b1Scm = new ArrayList<LogicalVariable>();
+            VariableUtilities.getLiveVariables(b1, b1Scm);
+            if (b1Scm.containsAll(used)) {
+                // push assign on right branch
+                op2Ref.setValue(b1);
+                b1Ref.setValue(op1);
+                opRef.setValue(op2);
+                return true;
+            } else {
+                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/PushFunctionsBelowJoin.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushFunctionsBelowJoin.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushFunctionsBelowJoin.java
new file mode 100644
index 0000000..0d24618
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushFunctionsBelowJoin.java
@@ -0,0 +1,208 @@
+/*
+ * 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.Iterator;
+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.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.AbstractBinaryJoinOperator;
+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.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Pushes function-call expressions below a join if possible.
+ * Assigns the result of such function-calls expressions to new variables, and replaces the original
+ * expression with a corresponding variable reference expression.
+ * This rule can help reduce the cost of computing expensive functions by pushing them below
+ * a join (which may blow up the cardinality).
+ * Also, this rule may help to enable other rules such as common subexpression elimination, again to reduce
+ * the number of calls to expensive functions.
+ * 
+ * Example: (we are pushing pushMeFunc)
+ * 
+ * Before plan:
+ * assign [$$10] <- [funcA(funcB(pushMeFunc($$3, $$4)))]
+ *   join (some condition) 
+ *     join_branch_0 where $$3 and $$4 are not live
+ *       ...
+ *     join_branch_1 where $$3 and $$4 are live
+ *       ...
+ * 
+ * After plan:
+ * assign [$$10] <- [funcA(funcB($$11))]
+ *   join (some condition) 
+ *     join_branch_0 where $$3 and $$4 are not live
+ *       ...
+ *     join_branch_1 where $$3 and $$4 are live
+ *       assign[$$11] <- [pushMeFunc($$3, $$4)]
+ *         ...
+ */
+public class PushFunctionsBelowJoin implements IAlgebraicRewriteRule {
+
+    private final Set<FunctionIdentifier> toPushFuncIdents;
+    private final List<Mutable<ILogicalExpression>> funcExprs = new ArrayList<Mutable<ILogicalExpression>>();
+    private final List<LogicalVariable> usedVars = new ArrayList<LogicalVariable>();
+    private final List<LogicalVariable> liveVars = new ArrayList<LogicalVariable>();
+
+    public PushFunctionsBelowJoin(Set<FunctionIdentifier> toPushFuncIdents) {
+        this.toPushFuncIdents = toPushFuncIdents;
+    }
+
+    @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 op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+            return false;
+        }
+        AssignOperator assignOp = (AssignOperator) op;
+
+        // Find a join operator below this assign.
+        Mutable<ILogicalOperator> joinOpRef = findJoinOp(assignOp.getInputs().get(0));
+        if (joinOpRef == null) {
+            return false;
+        }
+        AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) joinOpRef.getValue();
+
+        // Check if the assign uses a function that we wish to push below the join if possible.
+        funcExprs.clear();
+        gatherFunctionCalls(assignOp, funcExprs);
+        if (funcExprs.isEmpty()) {
+            return false;
+        }
+
+        // Try to push the functions down the input branches of the join.
+        boolean modified = false;
+        if (pushDownFunctions(joinOp, 0, funcExprs, context)) {
+            modified = true;
+        }
+        if (pushDownFunctions(joinOp, 1, funcExprs, context)) {
+            modified = true;
+        }
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(joinOp);
+        }
+        return modified;
+    }
+
+    private Mutable<ILogicalOperator> findJoinOp(Mutable<ILogicalOperator> opRef) {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        switch (op.getOperatorTag()) {
+            case INNERJOIN:
+            case LEFTOUTERJOIN: {
+                return opRef;
+            }
+            // Bail on these operators.
+            case GROUP:
+            case AGGREGATE:
+            case DISTINCT:
+            case UNNEST_MAP: {
+                return null;
+            }
+            // Traverse children.
+            default: {
+                for (Mutable<ILogicalOperator> childOpRef : op.getInputs()) {
+                    return findJoinOp(childOpRef);
+                }
+            }
+        }
+        return null;
+    }
+
+    private void gatherFunctionCalls(AssignOperator assignOp, List<Mutable<ILogicalExpression>> funcExprs) {
+        for (Mutable<ILogicalExpression> exprRef : assignOp.getExpressions()) {
+            gatherFunctionCalls(exprRef, funcExprs);
+        }
+    }
+
+    private void gatherFunctionCalls(Mutable<ILogicalExpression> exprRef, List<Mutable<ILogicalExpression>> funcExprs) {
+        AbstractLogicalExpression expr = (AbstractLogicalExpression) exprRef.getValue();
+        if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return;
+        }
+        // Check whether the function is a function we want to push.
+        AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) expr;
+        if (toPushFuncIdents.contains(funcExpr.getFunctionIdentifier())) {
+            funcExprs.add(exprRef);
+        }
+        // Traverse arguments.
+        for (Mutable<ILogicalExpression> funcArg : funcExpr.getArguments()) {
+            gatherFunctionCalls(funcArg, funcExprs);
+        }
+    }
+
+    private boolean pushDownFunctions(AbstractBinaryJoinOperator joinOp, int inputIndex,
+            List<Mutable<ILogicalExpression>> funcExprs, IOptimizationContext context) throws AlgebricksException {
+        ILogicalOperator joinInputOp = joinOp.getInputs().get(inputIndex).getValue();
+        liveVars.clear();
+        VariableUtilities.getLiveVariables(joinInputOp, liveVars);
+        Iterator<Mutable<ILogicalExpression>> funcIter = funcExprs.iterator();
+        List<LogicalVariable> assignVars = null;
+        List<Mutable<ILogicalExpression>> assignExprs = null;
+        while (funcIter.hasNext()) {
+            Mutable<ILogicalExpression> funcExprRef = funcIter.next();
+            ILogicalExpression funcExpr = funcExprRef.getValue();
+            usedVars.clear();
+            funcExpr.getUsedVariables(usedVars);
+            // Check if we can push the function down this branch.
+            if (liveVars.containsAll(usedVars)) {
+                if (assignVars == null) {
+                    assignVars = new ArrayList<LogicalVariable>();
+                    assignExprs = new ArrayList<Mutable<ILogicalExpression>>();
+                }
+                // Replace the original expression with a variable reference expression.
+                LogicalVariable replacementVar = context.newVar();
+                assignVars.add(replacementVar);
+                assignExprs.add(new MutableObject<ILogicalExpression>(funcExpr));
+                funcExprRef.setValue(new VariableReferenceExpression(replacementVar));
+                funcIter.remove();
+            }
+        }
+        // Create new assign operator below the join if any functions can be pushed.
+        if (assignVars != null) {
+            AssignOperator newAssign = new AssignOperator(assignVars, assignExprs);
+            newAssign.getInputs().add(new MutableObject<ILogicalOperator>(joinInputOp));
+            newAssign.setExecutionMode(joinOp.getExecutionMode());
+            joinOp.getInputs().get(inputIndex).setValue(newAssign);
+            context.computeAndSetTypeEnvironmentForOperator(newAssign);
+            return true;
+        }
+        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/PushGroupByIntoSortRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushGroupByIntoSortRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushGroupByIntoSortRule.java
new file mode 100644
index 0000000..56b2a8e
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushGroupByIntoSortRule.java
@@ -0,0 +1,150 @@
+/*
+ * 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.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.base.PhysicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.IMergeAggregationExpressionFactory;
+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.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.AbstractStableSortPOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.SortGroupByPOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * @author yingyib
+ *         merge externalsort+preclustered-gby into sort-gby
+ */
+public class PushGroupByIntoSortRule 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 {
+        ILogicalOperator op1 = opRef.getValue();
+        if (op1 == null) {
+            return false;
+        }
+        boolean changed = false;
+        for (Mutable<ILogicalOperator> childRef : op1.getInputs()) {
+            AbstractLogicalOperator op = (AbstractLogicalOperator) childRef.getValue();
+            if (op.getOperatorTag() == LogicalOperatorTag.GROUP) {
+                PhysicalOperatorTag opTag = op.getPhysicalOperator().getOperatorTag();
+                GroupByOperator groupByOperator = (GroupByOperator) op;
+                if (opTag == PhysicalOperatorTag.PRE_CLUSTERED_GROUP_BY) {
+                    Mutable<ILogicalOperator> op2Ref = op.getInputs().get(0).getValue().getInputs().get(0);
+                    AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+                    if (op2.getPhysicalOperator().getOperatorTag() == PhysicalOperatorTag.STABLE_SORT) {
+                        AbstractStableSortPOperator sortPhysicalOperator = (AbstractStableSortPOperator) op2
+                                .getPhysicalOperator();
+                        if (groupByOperator.getNestedPlans().size() != 1) {
+                            //Sort group-by currently works only for one nested plan with one root containing
+                            //an aggregate and a nested-tuple-source.
+                            continue;
+                        }
+                        ILogicalPlan p0 = groupByOperator.getNestedPlans().get(0);
+                        if (p0.getRoots().size() != 1) {
+                            //Sort group-by currently works only for one nested plan with one root containing
+                            //an aggregate and a nested-tuple-source.
+                            continue;
+                        }
+
+                        Mutable<ILogicalOperator> r0 = p0.getRoots().get(0);
+                        AbstractLogicalOperator r0Logical = (AbstractLogicalOperator) r0.getValue();
+                        if (r0Logical.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+                            //we only rewrite aggregation function; do nothing for running aggregates
+                            continue;
+                        }
+                        AggregateOperator aggOp = (AggregateOperator) r0.getValue();
+                        AbstractLogicalOperator aggInputOp = (AbstractLogicalOperator) aggOp.getInputs().get(0)
+                                .getValue();
+                        if (aggInputOp.getOperatorTag() != LogicalOperatorTag.NESTEDTUPLESOURCE) {
+                            continue;
+                        }
+
+                        boolean hasIntermediateAggregate = generateMergeAggregationExpressions(groupByOperator, context);
+                        if (!hasIntermediateAggregate) {
+                            continue;
+                        }
+
+                        //replace preclustered gby with sort gby
+                        op.setPhysicalOperator(new SortGroupByPOperator(groupByOperator.getGroupByList(), context
+                                .getPhysicalOptimizationConfig().getMaxFramesExternalGroupBy(), sortPhysicalOperator
+                                .getSortColumns()));
+
+                        // remove the stable sort operator
+                        op.getInputs().clear();
+                        op.getInputs().addAll(op2.getInputs());
+                        changed = true;
+                    }
+                }
+                continue;
+            } else {
+                continue;
+            }
+        }
+        return changed;
+    }
+
+    private boolean generateMergeAggregationExpressions(GroupByOperator gby, IOptimizationContext context)
+            throws AlgebricksException {
+        if (gby.getNestedPlans().size() != 1) {
+            throw new AlgebricksException(
+                    "External/sort group-by currently works only for one nested plan with one root containing"
+                            + "an aggregate and a nested-tuple-source.");
+        }
+        ILogicalPlan p0 = gby.getNestedPlans().get(0);
+        if (p0.getRoots().size() != 1) {
+            throw new AlgebricksException(
+                    "External/sort group-by currently works only for one nested plan with one root containing"
+                            + "an aggregate and a nested-tuple-source.");
+        }
+        IMergeAggregationExpressionFactory mergeAggregationExpressionFactory = context
+                .getMergeAggregationExpressionFactory();
+        Mutable<ILogicalOperator> r0 = p0.getRoots().get(0);
+        AggregateOperator aggOp = (AggregateOperator) r0.getValue();
+        List<Mutable<ILogicalExpression>> aggFuncRefs = aggOp.getExpressions();
+        List<LogicalVariable> originalAggVars = aggOp.getVariables();
+        int n = aggOp.getExpressions().size();
+        List<Mutable<ILogicalExpression>> mergeExpressionRefs = new ArrayList<Mutable<ILogicalExpression>>();
+        for (int i = 0; i < n; i++) {
+            ILogicalExpression mergeExpr = mergeAggregationExpressionFactory.createMergeAggregation(
+                    originalAggVars.get(i), aggFuncRefs.get(i).getValue(), context);
+            if (mergeExpr == null) {
+                return false;
+            }
+            mergeExpressionRefs.add(new MutableObject<ILogicalExpression>(mergeExpr));
+        }
+        aggOp.setMergeExpressions(mergeExpressionRefs);
+        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/PushMapOperatorDownThroughProductRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushMapOperatorDownThroughProductRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushMapOperatorDownThroughProductRule.java
new file mode 100644
index 0000000..16a71a4
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushMapOperatorDownThroughProductRule.java
@@ -0,0 +1,87 @@
+/*
+ * 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.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+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.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushMapOperatorDownThroughProductRule 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.isMap()) {
+            return false;
+        }
+        Mutable<ILogicalOperator> op2Ref = op1.getInputs().get(0);
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) op2Ref.getValue();
+        if (op2.getOperatorTag() != LogicalOperatorTag.INNERJOIN) {
+            return false;
+        }
+        AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) op2;
+        if (!OperatorPropertiesUtil.isAlwaysTrueCond(join.getCondition().getValue())) {
+            return false;
+        }
+
+        List<LogicalVariable> used = new ArrayList<LogicalVariable>();
+        VariableUtilities.getUsedVariables(op1, used);
+
+        Mutable<ILogicalOperator> b0Ref = op2.getInputs().get(0);
+        ILogicalOperator b0 = b0Ref.getValue();
+        List<LogicalVariable> b0Scm = new ArrayList<LogicalVariable>();
+        VariableUtilities.getLiveVariables(b0, b0Scm);
+        if (b0Scm.containsAll(used)) {
+            // push operator on left branch
+            op2Ref.setValue(b0);
+            b0Ref.setValue(op1);
+            opRef.setValue(op2);
+            return true;
+        } else {
+            Mutable<ILogicalOperator> b1Ref = op2.getInputs().get(1);
+            ILogicalOperator b1 = b1Ref.getValue();
+            List<LogicalVariable> b1Scm = new ArrayList<LogicalVariable>();
+            VariableUtilities.getLiveVariables(b1, b1Scm);
+            if (b1Scm.containsAll(used)) {
+                // push operator on right branch
+                op2Ref.setValue(b1);
+                b1Ref.setValue(op1);
+                opRef.setValue(op2);
+                return true;
+            } else {
+                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/PushNestedOrderByUnderPreSortedGroupByRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushNestedOrderByUnderPreSortedGroupByRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushNestedOrderByUnderPreSortedGroupByRule.java
new file mode 100644
index 0000000..476096d
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushNestedOrderByUnderPreSortedGroupByRule.java
@@ -0,0 +1,119 @@
+/*
+ * 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.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.base.PhysicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.AbstractPhysicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.StableSortPOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushNestedOrderByUnderPreSortedGroupByRule 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 op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.GROUP) {
+            return false;
+        }
+        if (op.getPhysicalOperator() == null) {
+            return false;
+        }
+        AbstractPhysicalOperator pOp = (AbstractPhysicalOperator) op.getPhysicalOperator();
+        if (pOp.getOperatorTag() != PhysicalOperatorTag.PRE_CLUSTERED_GROUP_BY) {
+            return false;
+        }
+        GroupByOperator gby = (GroupByOperator) op;
+        ILogicalPlan plan = gby.getNestedPlans().get(0);
+        AbstractLogicalOperator op1 = (AbstractLogicalOperator) plan.getRoots().get(0).getValue();
+        if (op1.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+            return false;
+        }
+        Mutable<ILogicalOperator> opRef2 = op1.getInputs().get(0);
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+        if (op2.getOperatorTag() != LogicalOperatorTag.ORDER) {
+            return false;
+        }
+        OrderOperator order1 = (OrderOperator) op2;
+        if (!isIndependentFromChildren(order1)) {
+            return false;
+        }
+        AbstractPhysicalOperator pOrder1 = (AbstractPhysicalOperator) op2.getPhysicalOperator();
+        if (pOrder1.getOperatorTag() != PhysicalOperatorTag.STABLE_SORT
+                && pOrder1.getOperatorTag() != PhysicalOperatorTag.IN_MEMORY_STABLE_SORT) {
+            return false;
+        }
+        // StableSortPOperator sort1 = (StableSortPOperator) pOrder1;
+        AbstractLogicalOperator op3 = (AbstractLogicalOperator) op.getInputs().get(0).getValue();
+        if (op3.getOperatorTag() != LogicalOperatorTag.ORDER) {
+            return false;
+        }
+        AbstractPhysicalOperator pOp3 = (AbstractPhysicalOperator) op3.getPhysicalOperator();
+        if (pOp3.getOperatorTag() != PhysicalOperatorTag.STABLE_SORT) {
+            return false;
+        }
+        OrderOperator order2 = (OrderOperator) op3;
+        StableSortPOperator sort2 = (StableSortPOperator) pOp3;
+        // int n1 = sort1.getSortColumns().length;
+        // int n2 = sort2.getSortColumns().length;
+        // OrderColumn[] sortColumns = new OrderColumn[n2 + n1];
+        // System.arraycopy(sort2.getSortColumns(), 0, sortColumns, 0, n2);
+        // int k = 0;
+        for (Pair<IOrder, Mutable<ILogicalExpression>> oe : order1.getOrderExpressions()) {
+            order2.getOrderExpressions().add(oe);
+            // sortColumns[n2 + k] = sort1.getSortColumns()[k];
+            // ++k;
+        }
+        // sort2.setSortColumns(sortColumns);
+        sort2.computeDeliveredProperties(order2, null);
+        // remove order1
+        ILogicalOperator underOrder1 = order1.getInputs().get(0).getValue();
+        opRef2.setValue(underOrder1);
+        return true;
+    }
+
+    private boolean isIndependentFromChildren(OrderOperator order1) throws AlgebricksException {
+        Set<LogicalVariable> free = new HashSet<LogicalVariable>();
+        OperatorPropertiesUtil.getFreeVariablesInSelfOrDesc(order1, free);
+        Set<LogicalVariable> usedInOrder = new HashSet<LogicalVariable>();
+        VariableUtilities.getUsedVariables(order1, usedInOrder);
+        return free.containsAll(usedInOrder);
+    }
+
+}

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/PushProjectDownRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java
new file mode 100644
index 0000000..b8ff247
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectDownRule.java
@@ -0,0 +1,219 @@
+/*
+ * 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.HashSet;
+import java.util.LinkedList;
+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.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.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Pushes projections through its input operator, provided that operator does
+ * not produce the projected variables.
+ * 
+ * @author Nicola
+ */
+public class PushProjectDownRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.PROJECT) {
+            return false;
+        }
+        ProjectOperator pi = (ProjectOperator) op;
+        Mutable<ILogicalOperator> opRef2 = pi.getInputs().get(0);
+
+        HashSet<LogicalVariable> toPush = new HashSet<LogicalVariable>();
+        toPush.addAll(pi.getVariables());
+
+        Pair<Boolean, Boolean> p = pushThroughOp(toPush, opRef2, op, context);
+        boolean smthWasPushed = p.first;
+        if (p.second) { // the original projection is redundant
+            opRef.setValue(op.getInputs().get(0).getValue());
+            smthWasPushed = true;
+        }
+
+        return smthWasPushed;
+    }
+
+    private static Pair<Boolean, Boolean> pushThroughOp(HashSet<LogicalVariable> toPush,
+            Mutable<ILogicalOperator> opRef2, ILogicalOperator initialOp, IOptimizationContext context)
+            throws AlgebricksException {
+        List<LogicalVariable> initProjectList = new ArrayList<LogicalVariable>(toPush);
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+        do {
+            if (op2.getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE
+                    || op2.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE
+                    || op2.getOperatorTag() == LogicalOperatorTag.PROJECT
+                    || op2.getOperatorTag() == LogicalOperatorTag.REPLICATE
+                    || op2.getOperatorTag() == LogicalOperatorTag.UNIONALL) {
+                return new Pair<Boolean, Boolean>(false, false);
+            }
+            if (!op2.isMap()) {
+                break;
+            }
+            LinkedList<LogicalVariable> usedVars = new LinkedList<LogicalVariable>();
+            VariableUtilities.getUsedVariables(op2, usedVars);
+            toPush.addAll(usedVars);
+            LinkedList<LogicalVariable> producedVars = new LinkedList<LogicalVariable>();
+            VariableUtilities.getProducedVariables(op2, producedVars);
+            toPush.removeAll(producedVars);
+            // we assume pipelineable ops. have only one input
+            opRef2 = op2.getInputs().get(0);
+            op2 = (AbstractLogicalOperator) opRef2.getValue();
+        } while (true);
+
+        LinkedList<LogicalVariable> produced2 = new LinkedList<LogicalVariable>();
+        VariableUtilities.getProducedVariables(op2, produced2);
+        LinkedList<LogicalVariable> used2 = new LinkedList<LogicalVariable>();
+        VariableUtilities.getUsedVariables(op2, used2);
+
+        boolean canCommuteProjection = initProjectList.containsAll(toPush) && initProjectList.containsAll(produced2)
+                && initProjectList.containsAll(used2);
+        // if true, we can get rid of the initial projection
+
+        // get rid of useless decor vars.
+        if (!canCommuteProjection && op2.getOperatorTag() == LogicalOperatorTag.GROUP) {
+            boolean gbyChanged = false;
+            GroupByOperator gby = (GroupByOperator) op2;
+            List<Pair<LogicalVariable, Mutable<ILogicalExpression>>> newDecorList = new ArrayList<Pair<LogicalVariable, Mutable<ILogicalExpression>>>();
+            for (Pair<LogicalVariable, Mutable<ILogicalExpression>> p : gby.getDecorList()) {
+                LogicalVariable decorVar = GroupByOperator.getDecorVariable(p);
+                if (!toPush.contains(decorVar)) {
+                    used2.remove(decorVar);
+                    gbyChanged = true;
+                } else {
+                    newDecorList.add(p);
+                }
+            }
+            gby.getDecorList().clear();
+            gby.getDecorList().addAll(newDecorList);
+            if (gbyChanged) {
+                context.computeAndSetTypeEnvironmentForOperator(gby);
+            }
+        }
+        used2.clear();
+        VariableUtilities.getUsedVariables(op2, used2);
+
+        toPush.addAll(used2); // remember that toPush is a Set
+        toPush.removeAll(produced2);
+
+        if (toPush.isEmpty()) {
+            return new Pair<Boolean, Boolean>(false, false);
+        }
+
+        boolean smthWasPushed = false;
+        for (Mutable<ILogicalOperator> c : op2.getInputs()) {
+            if (pushNeededProjections(toPush, c, context, initialOp)) {
+                smthWasPushed = true;
+            }
+        }
+        if (op2.hasNestedPlans()) {
+            AbstractOperatorWithNestedPlans n = (AbstractOperatorWithNestedPlans) op2;
+            for (ILogicalPlan p : n.getNestedPlans()) {
+                for (Mutable<ILogicalOperator> r : p.getRoots()) {
+                    if (pushNeededProjections(toPush, r, context, initialOp)) {
+                        smthWasPushed = true;
+                    }
+                }
+            }
+        }
+        return new Pair<Boolean, Boolean>(smthWasPushed, canCommuteProjection);
+    }
+
+    // It does not try to push above another Projection.
+    private static boolean pushNeededProjections(HashSet<LogicalVariable> toPush, Mutable<ILogicalOperator> opRef,
+            IOptimizationContext context, ILogicalOperator initialOp) throws AlgebricksException {
+        HashSet<LogicalVariable> allP = new HashSet<LogicalVariable>();
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        VariableUtilities.getLiveVariables(op, allP);
+
+        HashSet<LogicalVariable> toProject = new HashSet<LogicalVariable>();
+        for (LogicalVariable v : toPush) {
+            if (allP.contains(v)) {
+                toProject.add(v);
+            }
+        }
+        if (toProject.equals(allP)) {
+            // 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) {
+                push = true;
+            }
+            return push;
+        } else {
+            return pushAllProjectionsOnTopOf(toProject, opRef, context, initialOp);
+        }
+    }
+
+    // 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 {
+        if (toPush.isEmpty()) {
+            return false;
+        }
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+
+        if (context.checkAndAddToAlreadyCompared(initialOp, op)) {
+            return false;
+        }
+
+        switch (op.getOperatorTag()) {
+            case EXCHANGE: {
+                opRef = opRef.getValue().getInputs().get(0);
+                op = (AbstractLogicalOperator) opRef.getValue();
+                break;
+            }
+            case PROJECT: {
+                return false;
+            }
+        }
+
+        ProjectOperator pi2 = new ProjectOperator(new ArrayList<LogicalVariable>(toPush));
+        pi2.getInputs().add(new MutableObject<ILogicalOperator>(op));
+        opRef.setValue(pi2);
+        pi2.setExecutionMode(op.getExecutionMode());
+        context.computeAndSetTypeEnvironmentForOperator(pi2);
+        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/PushProjectIntoDataSourceScanRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectIntoDataSourceScanRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectIntoDataSourceScanRule.java
new file mode 100644
index 0000000..b17d50f
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushProjectIntoDataSourceScanRule.java
@@ -0,0 +1,60 @@
+/*
+ * 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 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.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.DataSourceScanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushProjectIntoDataSourceScanRule 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 op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getInputs().size() <= 0)
+            return false;
+        AbstractLogicalOperator project = (AbstractLogicalOperator) op.getInputs().get(0).getValue();
+        if (project.getOperatorTag() != LogicalOperatorTag.PROJECT)
+            return false;
+        AbstractLogicalOperator exchange = (AbstractLogicalOperator) project.getInputs().get(0).getValue();
+        if (exchange.getOperatorTag() != LogicalOperatorTag.EXCHANGE)
+            return false;
+        AbstractLogicalOperator inputOp = (AbstractLogicalOperator) exchange.getInputs().get(0).getValue();
+        if (inputOp.getOperatorTag() != LogicalOperatorTag.DATASOURCESCAN)
+            return false;
+        DataSourceScanOperator scanOp = (DataSourceScanOperator) inputOp;
+        ProjectOperator projectOp = (ProjectOperator) project;
+        scanOp.addProjectVariables(projectOp.getVariables());
+        if (op.getOperatorTag() != LogicalOperatorTag.EXCHANGE) {
+            op.getInputs().set(0, project.getInputs().get(0));
+        } else {
+            op.getInputs().set(0, exchange.getInputs().get(0));
+        }
+        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/PushSelectDownRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectDownRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectDownRule.java
new file mode 100644
index 0000000..cc65996
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectDownRule.java
@@ -0,0 +1,98 @@
+/*
+ * 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.LinkedList;
+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.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.SelectOperator;
+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.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushSelectDownRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.SELECT) {
+            return false;
+        }
+
+        Mutable<ILogicalOperator> opRef2 = op.getInputs().get(0);
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+
+        if (context.checkAndAddToAlreadyCompared(op, op2)) {
+            return false;
+        }
+
+        LogicalOperatorTag tag2 = op2.getOperatorTag();
+
+        if (tag2 == LogicalOperatorTag.INNERJOIN || tag2 == LogicalOperatorTag.LEFTOUTERJOIN
+                || tag2 == LogicalOperatorTag.REPLICATE) {
+            return false;
+        } else { // not a join
+            boolean res = propagateSelectionRec(opRef, opRef2);
+            if (res) {
+                OperatorPropertiesUtil.typeOpRec(opRef, context);
+            }
+            return res;
+        }
+    }
+
+    private static boolean propagateSelectionRec(Mutable<ILogicalOperator> sigmaRef, Mutable<ILogicalOperator> opRef2)
+            throws AlgebricksException {
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) opRef2.getValue();
+        if (op2.getInputs().size() != 1 || op2.getOperatorTag() == LogicalOperatorTag.DATASOURCESCAN) {
+            return false;
+        }
+
+        SelectOperator sigma = (SelectOperator) sigmaRef.getValue();
+        LinkedList<LogicalVariable> usedInSigma = new LinkedList<LogicalVariable>();
+        sigma.getCondition().getValue().getUsedVariables(usedInSigma);
+
+        LinkedList<LogicalVariable> produced2 = new LinkedList<LogicalVariable>();
+        VariableUtilities.getProducedVariables(op2, produced2);
+        if (OperatorPropertiesUtil.disjoint(produced2, usedInSigma)) {
+            // just swap
+            opRef2.setValue(sigma);
+            sigmaRef.setValue(op2);
+            List<Mutable<ILogicalOperator>> sigmaInpList = sigma.getInputs();
+            sigmaInpList.clear();
+            sigmaInpList.addAll(op2.getInputs());
+            List<Mutable<ILogicalOperator>> op2InpList = op2.getInputs();
+            op2InpList.clear();
+            op2InpList.add(opRef2);
+            propagateSelectionRec(opRef2, sigma.getInputs().get(0));
+            return true;
+
+        }
+        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/PushSelectIntoJoinRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectIntoJoinRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectIntoJoinRule.java
new file mode 100644
index 0000000..e29299c
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/PushSelectIntoJoinRule.java
@@ -0,0 +1,309 @@
+/*
+ * 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.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+
+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.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.ScalarFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+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.InnerJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+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.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class PushSelectIntoJoinRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        Collection<LogicalVariable> joinLiveVarsLeft = new HashSet<LogicalVariable>();
+        Collection<LogicalVariable> joinLiveVarsRight = new HashSet<LogicalVariable>();
+        Collection<LogicalVariable> liveInOpsToPushLeft = new HashSet<LogicalVariable>();
+        Collection<LogicalVariable> liveInOpsToPushRight = new HashSet<LogicalVariable>();
+
+        List<ILogicalOperator> pushedOnLeft = new ArrayList<ILogicalOperator>();
+        List<ILogicalOperator> pushedOnRight = new ArrayList<ILogicalOperator>();
+        LinkedList<ILogicalOperator> notPushedStack = new LinkedList<ILogicalOperator>();
+        Collection<LogicalVariable> usedVars = new HashSet<LogicalVariable>();
+        Collection<LogicalVariable> producedVars = new HashSet<LogicalVariable>();
+
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.SELECT) {
+            return false;
+        }
+        SelectOperator select = (SelectOperator) op;
+        Mutable<ILogicalOperator> opRef2 = op.getInputs().get(0);
+        AbstractLogicalOperator son = (AbstractLogicalOperator) opRef2.getValue();
+        AbstractLogicalOperator op2 = son;
+        boolean needToPushOps = false;
+        while (son.isMap()) {
+            needToPushOps = true;
+            Mutable<ILogicalOperator> opRefLink = son.getInputs().get(0);
+            son = (AbstractLogicalOperator) opRefLink.getValue();
+        }
+
+        if (son.getOperatorTag() != LogicalOperatorTag.INNERJOIN
+                && son.getOperatorTag() != LogicalOperatorTag.LEFTOUTERJOIN) {
+            return false;
+        }
+        boolean isLoj = son.getOperatorTag() == LogicalOperatorTag.LEFTOUTERJOIN;
+        AbstractBinaryJoinOperator join = (AbstractBinaryJoinOperator) son;
+
+        Mutable<ILogicalOperator> joinBranchLeftRef = join.getInputs().get(0);
+        Mutable<ILogicalOperator> joinBranchRightRef = join.getInputs().get(1);
+
+        if (needToPushOps) {
+            ILogicalOperator joinBranchLeft = joinBranchLeftRef.getValue();
+            ILogicalOperator joinBranchRight = joinBranchRightRef.getValue();
+            VariableUtilities.getLiveVariables(joinBranchLeft, joinLiveVarsLeft);
+            VariableUtilities.getLiveVariables(joinBranchRight, joinLiveVarsRight);
+            Mutable<ILogicalOperator> opIterRef = opRef2;
+            ILogicalOperator opIter = op2;
+            while (opIter != join) {
+                LogicalOperatorTag tag = ((AbstractLogicalOperator) opIter).getOperatorTag();
+                if (tag == LogicalOperatorTag.PROJECT) {
+                    notPushedStack.addFirst(opIter);
+                } else {
+                    VariableUtilities.getUsedVariables(opIter, usedVars);
+                    VariableUtilities.getProducedVariables(opIter, producedVars);
+                    if (joinLiveVarsLeft.containsAll(usedVars)) {
+                        pushedOnLeft.add(opIter);
+                        liveInOpsToPushLeft.addAll(producedVars);
+                    } else if (joinLiveVarsRight.containsAll(usedVars)) {
+                        pushedOnRight.add(opIter);
+                        liveInOpsToPushRight.addAll(producedVars);
+                    } else {
+                        return false;
+                    }
+                }
+                opIterRef = opIter.getInputs().get(0);
+                opIter = opIterRef.getValue();
+            }
+            if (isLoj && pushedOnLeft.isEmpty()) {
+                return false;
+            }
+        }
+
+        boolean intersectsAllBranches = true;
+        boolean[] intersectsBranch = new boolean[join.getInputs().size()];
+        LinkedList<LogicalVariable> selectVars = new LinkedList<LogicalVariable>();
+        select.getCondition().getValue().getUsedVariables(selectVars);
+        int i = 0;
+        for (Mutable<ILogicalOperator> branch : join.getInputs()) {
+            LinkedList<LogicalVariable> branchVars = new LinkedList<LogicalVariable>();
+            VariableUtilities.getLiveVariables(branch.getValue(), branchVars);
+            if (i == 0) {
+                branchVars.addAll(liveInOpsToPushLeft);
+            } else {
+                branchVars.addAll(liveInOpsToPushRight);
+            }
+            if (OperatorPropertiesUtil.disjoint(selectVars, branchVars)) {
+                intersectsAllBranches = false;
+            } else {
+                intersectsBranch[i] = true;
+            }
+            i++;
+        }
+        if (!intersectsBranch[0] && !intersectsBranch[1]) {
+            return false;
+        }
+        if (needToPushOps) {
+            pushOps(pushedOnLeft, joinBranchLeftRef, context);
+            pushOps(pushedOnRight, joinBranchRightRef, context);
+        }
+        if (intersectsAllBranches) {
+            addCondToJoin(select, join, context);
+        } else { // push down
+            Iterator<Mutable<ILogicalOperator>> branchIter = join.getInputs().iterator();
+            ILogicalExpression selectCondition = select.getCondition().getValue();
+            boolean lojToInner = false;
+            for (int j = 0; j < intersectsBranch.length; j++) {
+                Mutable<ILogicalOperator> branch = branchIter.next();
+                boolean inter = intersectsBranch[j];
+                if (inter) {
+                    if (j > 0 && isLoj) {
+                        // if a left outer join, if the select condition is not-null filtering,
+                        // we rewrite left outer join
+                        // to inner join for this case.
+                        if (containsNotNullFiltering(selectCondition)) {
+                            lojToInner = true;
+                        }
+                    }
+                    if ((j > 0 && isLoj) && containsNullFiltering(selectCondition)) {
+                        // Select is-null($$var) cannot be pushed in the right branch of a LOJ;
+                        notPushedStack.addFirst(select);
+                    } else {
+                        // Conditions for the left branch can always be pushed.
+                        // Other conditions can be pushed to the right branch of a LOJ.
+                        copySelectToBranch(select, branch, context);
+                    }
+                }
+            }
+            if (lojToInner) {
+                // Rewrites left outer join  to inner join.
+                InnerJoinOperator innerJoin = new InnerJoinOperator(join.getCondition());
+                innerJoin.getInputs().addAll(join.getInputs());
+                join = innerJoin;
+                context.computeAndSetTypeEnvironmentForOperator(join);
+            }
+        }
+        ILogicalOperator top = join;
+        for (ILogicalOperator npOp : notPushedStack) {
+            List<Mutable<ILogicalOperator>> npInpList = npOp.getInputs();
+            npInpList.clear();
+            npInpList.add(new MutableObject<ILogicalOperator>(top));
+            context.computeAndSetTypeEnvironmentForOperator(npOp);
+            top = npOp;
+        }
+        opRef.setValue(top);
+        return true;
+
+    }
+
+    private void pushOps(List<ILogicalOperator> opList, Mutable<ILogicalOperator> joinBranch,
+            IOptimizationContext context) throws AlgebricksException {
+        ILogicalOperator topOp = joinBranch.getValue();
+        ListIterator<ILogicalOperator> iter = opList.listIterator(opList.size());
+        while (iter.hasPrevious()) {
+            ILogicalOperator op = iter.previous();
+            List<Mutable<ILogicalOperator>> opInpList = op.getInputs();
+            opInpList.clear();
+            opInpList.add(new MutableObject<ILogicalOperator>(topOp));
+            topOp = op;
+            context.computeAndSetTypeEnvironmentForOperator(op);
+        }
+        joinBranch.setValue(topOp);
+    }
+
+    private static void addCondToJoin(SelectOperator select, AbstractBinaryJoinOperator join,
+            IOptimizationContext context) {
+        ILogicalExpression cond = join.getCondition().getValue();
+        if (OperatorPropertiesUtil.isAlwaysTrueCond(cond)) { // the join was a product
+            join.getCondition().setValue(select.getCondition().getValue());
+        } else {
+            boolean bAddedToConj = false;
+            if (cond.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                AbstractFunctionCallExpression fcond = (AbstractFunctionCallExpression) cond;
+                if (fcond.getFunctionIdentifier().equals(AlgebricksBuiltinFunctions.AND)) {
+                    AbstractFunctionCallExpression newCond = new ScalarFunctionCallExpression(context
+                            .getMetadataProvider().lookupFunction(AlgebricksBuiltinFunctions.AND));
+                    newCond.getArguments().add(select.getCondition());
+                    newCond.getArguments().addAll(fcond.getArguments());
+                    join.getCondition().setValue(newCond);
+                    bAddedToConj = true;
+                }
+            }
+            if (!bAddedToConj) {
+                AbstractFunctionCallExpression newCond = new ScalarFunctionCallExpression(context.getMetadataProvider()
+                        .lookupFunction(AlgebricksBuiltinFunctions.AND), select.getCondition(),
+                        new MutableObject<ILogicalExpression>(join.getCondition().getValue()));
+                join.getCondition().setValue(newCond);
+            }
+        }
+    }
+
+    private static void copySelectToBranch(SelectOperator select, Mutable<ILogicalOperator> branch,
+            IOptimizationContext context) throws AlgebricksException {
+        ILogicalOperator newSelect = new SelectOperator(select.getCondition(), select.getRetainNull(),
+                select.getNullPlaceholderVariable());
+        Mutable<ILogicalOperator> newRef = new MutableObject<ILogicalOperator>(branch.getValue());
+        newSelect.getInputs().add(newRef);
+        branch.setValue(newSelect);
+        context.computeAndSetTypeEnvironmentForOperator(newSelect);
+    }
+
+    /**
+     * Whether the expression contains a not-null filtering
+     * 
+     * @param expr
+     * @return true if the expression contains a not-null filtering function call; false otherwise.
+     */
+    private boolean containsNotNullFiltering(ILogicalExpression expr) {
+        if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return false;
+        }
+        ScalarFunctionCallExpression func = (ScalarFunctionCallExpression) expr;
+        if (func.getFunctionIdentifier() == AlgebricksBuiltinFunctions.AND) {
+            for (Mutable<ILogicalExpression> argumentRef : func.getArguments()) {
+                if (containsNotNullFiltering(argumentRef.getValue())) {
+                    return true;
+                }
+            }
+            return false;
+        }
+        if (func.getFunctionIdentifier() != AlgebricksBuiltinFunctions.NOT) {
+            return false;
+        }
+        ILogicalExpression arg = func.getArguments().get(0).getValue();
+        if (arg.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return false;
+        }
+        ScalarFunctionCallExpression func2 = (ScalarFunctionCallExpression) arg;
+        if (func2.getFunctionIdentifier() != AlgebricksBuiltinFunctions.IS_NULL) {
+            return false;
+        }
+        return true;
+    }
+
+    /**
+     * Whether the expression contains a null filtering
+     * 
+     * @param expr
+     * @return true if the expression contains a null filtering function call; false otherwise.
+     */
+    private boolean containsNullFiltering(ILogicalExpression expr) {
+        if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return false;
+        }
+        ScalarFunctionCallExpression func = (ScalarFunctionCallExpression) expr;
+        if (func.getFunctionIdentifier() == AlgebricksBuiltinFunctions.AND) {
+            for (Mutable<ILogicalExpression> argumentRef : func.getArguments()) {
+                if (containsNullFiltering(argumentRef.getValue())) {
+                    return true;
+                }
+            }
+            return false;
+        }
+        if (func.getFunctionIdentifier() != AlgebricksBuiltinFunctions.IS_NULL) {
+            return false;
+        }
+        return true;
+    }
+}
\ No newline at end of file


Mime
View raw message