asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ima...@apache.org
Subject [08/51] [partial] incubator-asterixdb-hyracks git commit: Change folder structure for Java repackage
Date Tue, 25 Aug 2015 16:41:21 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/ExtractCommonExpressionsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonExpressionsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonExpressionsRule.java
new file mode 100644
index 0000000..41cf470
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonExpressionsRule.java
@@ -0,0 +1,436 @@
+/*
+ * 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.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.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.ConstantExpression;
+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.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.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.visitors.ILogicalExpressionReferenceTransform;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Factors out common sub-expressions by assigning them to a variables, and replacing the common sub-expressions with references to those variables.
+ * Preconditions/Assumptions:
+ * Assumes no projects are in the plan. This rule ignores variable reference expressions and constants (other rules deal with those separately).
+ * Postconditions/Examples:
+ * Plan with extracted sub-expressions. Generates one assign operator per extracted expression.
+ * Example 1 - Simple Arithmetic Example (simplified)
+ * Before plan:
+ * assign [$$1] <- [5 + 6 - 10]
+ * assign [$$0] <- [5 + 6 + 30]
+ * After plan:
+ * assign [$$1] <- [$$5 - 10]
+ * assign [$$0] <- [$$5 + 30]
+ * assign [$$5] <- [5 + 6]
+ * Example 2 - Cleaning up 'Distinct By' (simplified)
+ * Before plan: (notice how $$0 is not live after the distinct)
+ * assign [$$3] <- [field-access($$0, 1)]
+ * distinct ([%0->$$5])
+ * assign [$$5] <- [field-access($$0, 1)]
+ * unnest $$0 <- [scan-dataset]
+ * After plan: (notice how the issue of $$0 is fixed)
+ * assign [$$3] <- [$$5]
+ * distinct ([$$5])
+ * assign [$$5] <- [field-access($$0, 1)]
+ * unnest $$0 <- [scan-dataset]
+ * Example 3 - Pulling Common Expressions Above Joins (simplified)
+ * Before plan:
+ * assign [$$9] <- funcZ(funcY($$8))
+ * join (funcX(funcY($$8)))
+ * After plan:
+ * assign [$$9] <- funcZ($$10))
+ * select (funcX($$10))
+ * assign [$$10] <- [funcY($$8)]
+ * join (TRUE)
+ */
+public class ExtractCommonExpressionsRule implements IAlgebraicRewriteRule {
+
+    private final List<ILogicalExpression> originalAssignExprs = new ArrayList<ILogicalExpression>();
+
+    private final CommonExpressionSubstitutionVisitor substVisitor = new CommonExpressionSubstitutionVisitor();
+    private final Map<ILogicalExpression, ExprEquivalenceClass> exprEqClassMap = new HashMap<ILogicalExpression, ExprEquivalenceClass>();
+
+    // Set of operators for which common subexpression elimination should not be performed.
+    private static final Set<LogicalOperatorTag> ignoreOps = new HashSet<LogicalOperatorTag>();
+    static {
+        ignoreOps.add(LogicalOperatorTag.UNNEST);
+        ignoreOps.add(LogicalOperatorTag.UNNEST_MAP);
+        ignoreOps.add(LogicalOperatorTag.ORDER);
+        ignoreOps.add(LogicalOperatorTag.PROJECT);
+        ignoreOps.add(LogicalOperatorTag.AGGREGATE);
+        ignoreOps.add(LogicalOperatorTag.RUNNINGAGGREGATE);
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        exprEqClassMap.clear();
+        substVisitor.setContext(context);
+        boolean modified = removeCommonExpressions(opRef, context);
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(opRef.getValue());
+        }
+        return modified;
+    }
+
+    private void updateEquivalenceClassMap(LogicalVariable lhs, Mutable<ILogicalExpression> rhsExprRef,
+            ILogicalExpression rhsExpr, ILogicalOperator op) {
+        ExprEquivalenceClass exprEqClass = exprEqClassMap.get(rhsExpr);
+        if (exprEqClass == null) {
+            exprEqClass = new ExprEquivalenceClass(op, rhsExprRef);
+            exprEqClassMap.put(rhsExpr, exprEqClass);
+        }
+        exprEqClass.setVariable(lhs);
+    }
+
+    private boolean removeCommonExpressions(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (context.checkIfInDontApplySet(this, opRef.getValue())) {
+            return false;
+        }
+
+        boolean modified = false;
+        // Recurse into children.
+        for (Mutable<ILogicalOperator> inputOpRef : op.getInputs()) {
+            if (removeCommonExpressions(inputOpRef, context)) {
+                modified = true;
+            }
+        }
+
+        // TODO: Deal with replicate properly. Currently, we just clear the expr equivalence map, since we want to avoid incorrect expression replacement
+        // (the resulting new variables should be assigned live below a replicate).
+        if (op.getOperatorTag() == LogicalOperatorTag.REPLICATE) {
+            exprEqClassMap.clear();
+            return modified;
+        }
+        // Exclude these operators.
+        if (ignoreOps.contains(op.getOperatorTag())) {
+            return modified;
+        }
+
+        // Remember a copy of the original assign expressions, so we can add them to the equivalence class map
+        // after replacing expressions within the assign operator itself.
+        if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+            AssignOperator assignOp = (AssignOperator) op;
+            originalAssignExprs.clear();
+            int numVars = assignOp.getVariables().size();
+            for (int i = 0; i < numVars; i++) {
+                Mutable<ILogicalExpression> exprRef = assignOp.getExpressions().get(i);
+                ILogicalExpression expr = exprRef.getValue();
+                originalAssignExprs.add(expr.cloneExpression());
+            }
+        }
+
+        // Perform common subexpression elimination.
+        substVisitor.setOperator(op);
+        if (op.acceptExpressionTransform(substVisitor)) {
+            modified = true;
+        }
+
+        // Update equivalence class map.
+        if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+            AssignOperator assignOp = (AssignOperator) op;
+            int numVars = assignOp.getVariables().size();
+            for (int i = 0; i < numVars; i++) {
+                Mutable<ILogicalExpression> exprRef = assignOp.getExpressions().get(i);
+                ILogicalExpression expr = exprRef.getValue();
+                if (expr.getExpressionTag() == LogicalExpressionTag.VARIABLE
+                        || expr.getExpressionTag() == LogicalExpressionTag.CONSTANT) {
+                    continue;
+                }
+                // Update equivalence class map.
+                LogicalVariable lhs = assignOp.getVariables().get(i);
+                updateEquivalenceClassMap(lhs, exprRef, exprRef.getValue(), op);
+
+                // Update equivalence class map with original assign expression.
+                updateEquivalenceClassMap(lhs, exprRef, originalAssignExprs.get(i), op);
+            }
+        }
+
+        // TODO: For now do not perform replacement in nested plans
+        // due to the complication of figuring out whether the firstOp in an equivalence class is within a subplan, 
+        // and the resulting variable will not be visible to the outside.
+        // Since subplans should be eliminated in most cases, this behavior is acceptable for now.
+        /*
+        if (op.hasNestedPlans()) {
+            AbstractOperatorWithNestedPlans opWithNestedPlan = (AbstractOperatorWithNestedPlans) op;
+            for (ILogicalPlan nestedPlan : opWithNestedPlan.getNestedPlans()) {
+                for (Mutable<ILogicalOperator> rootRef : nestedPlan.getRoots()) {
+                    if (removeCommonExpressions(rootRef, context)) {
+                        modified = true;
+                    }
+                }
+            }
+        }
+        */
+
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(op);
+            context.addToDontApplySet(this, op);
+        }
+        return modified;
+    }
+
+    private class CommonExpressionSubstitutionVisitor implements ILogicalExpressionReferenceTransform {
+
+        private IOptimizationContext context;
+        private ILogicalOperator op;
+
+        public void setContext(IOptimizationContext context) {
+            this.context = context;
+        }
+
+        public void setOperator(ILogicalOperator op) throws AlgebricksException {
+            this.op = op;
+        }
+
+        @Override
+        public boolean transform(Mutable<ILogicalExpression> exprRef) throws AlgebricksException {
+            AbstractLogicalExpression expr = (AbstractLogicalExpression) exprRef.getValue();
+            boolean modified = false;
+            ExprEquivalenceClass exprEqClass = exprEqClassMap.get(expr);
+            if (exprEqClass != null) {
+                // Replace common subexpression with existing variable. 
+                if (exprEqClass.variableIsSet()) {
+                    Set<LogicalVariable> liveVars = new HashSet<LogicalVariable>();
+                    List<LogicalVariable> usedVars = new ArrayList<LogicalVariable>();
+                    VariableUtilities.getLiveVariables(op, liveVars);
+                    VariableUtilities.getUsedVariables(op, usedVars);
+                    // Check if the replacing variable is live at this op.
+                    // However, if the op is already using variables that are not live, then a replacement may enable fixing the plan.
+                    // This behavior is necessary to, e.g., properly deal with distinct by.
+                    // Also just replace the expr if we are replacing common exprs from within the same operator.
+                    if (liveVars.contains(exprEqClass.getVariable()) || !liveVars.containsAll(usedVars)
+                            || op == exprEqClass.getFirstOperator()) {
+                        exprRef.setValue(new VariableReferenceExpression(exprEqClass.getVariable()));
+                        // Do not descend into children since this expr has been completely replaced.
+                        return true;
+                    }
+                } else {
+                    if (expr.isFunctional() && assignCommonExpression(exprEqClass, expr)) {
+                        //re-obtain the live vars after rewriting in the method called in the if condition
+                        Set<LogicalVariable> liveVars = new HashSet<LogicalVariable>();
+                        VariableUtilities.getLiveVariables(op, liveVars);
+                        //rewrite only when the variable is live
+                        if (liveVars.contains(exprEqClass.getVariable())) {
+                            exprRef.setValue(new VariableReferenceExpression(exprEqClass.getVariable()));
+                            // Do not descend into children since this expr has been completely replaced.
+                            return true;
+                        }
+                    }
+                }
+            } else {
+                if (expr.getExpressionTag() != LogicalExpressionTag.VARIABLE
+                        && expr.getExpressionTag() != LogicalExpressionTag.CONSTANT) {
+                    exprEqClass = new ExprEquivalenceClass(op, exprRef);
+                    exprEqClassMap.put(expr, exprEqClass);
+                }
+            }
+
+            // Descend into function arguments.
+            if (expr.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) expr;
+                for (Mutable<ILogicalExpression> arg : funcExpr.getArguments()) {
+                    if (transform(arg)) {
+                        modified = true;
+                    }
+                }
+            }
+            return modified;
+        }
+
+        private boolean assignCommonExpression(ExprEquivalenceClass exprEqClass, ILogicalExpression expr)
+                throws AlgebricksException {
+            AbstractLogicalOperator firstOp = (AbstractLogicalOperator) exprEqClass.getFirstOperator();
+            Mutable<ILogicalExpression> firstExprRef = exprEqClass.getFirstExpression();
+            if (firstOp.getOperatorTag() == LogicalOperatorTag.INNERJOIN
+                    || firstOp.getOperatorTag() == LogicalOperatorTag.LEFTOUTERJOIN) {
+                // Do not extract common expressions from within the same join operator.
+                if (firstOp == op) {
+                    return false;
+                }
+                AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) firstOp;
+                Mutable<ILogicalExpression> joinCond = joinOp.getCondition();
+                ILogicalExpression enclosingExpr = getEnclosingExpression(joinCond, firstExprRef.getValue());
+                if (enclosingExpr == null) {
+                    // No viable enclosing expression that we can pull out from the join.
+                    return false;
+                }
+                // Place a Select operator beneath op that contains the enclosing expression.
+                SelectOperator selectOp = new SelectOperator(new MutableObject<ILogicalExpression>(enclosingExpr),
+                        false, null);
+                selectOp.getInputs().add(new MutableObject<ILogicalOperator>(op.getInputs().get(0).getValue()));
+                op.getInputs().get(0).setValue(selectOp);
+                // Set firstOp to be the select below op, since we want to assign the common subexpr there.
+                firstOp = (AbstractLogicalOperator) selectOp;
+            } else if (firstOp.getInputs().size() > 1) {
+                // Bail for any non-join operator with multiple inputs.
+                return false;
+            }
+            LogicalVariable newVar = context.newVar();
+            AssignOperator newAssign = new AssignOperator(newVar, new MutableObject<ILogicalExpression>(firstExprRef
+                    .getValue().cloneExpression()));
+            // Place assign below firstOp.
+            newAssign.getInputs().add(new MutableObject<ILogicalOperator>(firstOp.getInputs().get(0).getValue()));
+            newAssign.setExecutionMode(firstOp.getExecutionMode());
+            firstOp.getInputs().get(0).setValue(newAssign);
+            // Replace original expr with variable reference, and set var in expression equivalence class.
+            firstExprRef.setValue(new VariableReferenceExpression(newVar));
+            exprEqClass.setVariable(newVar);
+            context.computeAndSetTypeEnvironmentForOperator(newAssign);
+            context.computeAndSetTypeEnvironmentForOperator(firstOp);
+            return true;
+        }
+
+        private ILogicalExpression getEnclosingExpression(Mutable<ILogicalExpression> conditionExprRef,
+                ILogicalExpression commonSubExpr) {
+            ILogicalExpression conditionExpr = conditionExprRef.getValue();
+            if (conditionExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+                return null;
+            }
+            if (isEqJoinCondition(commonSubExpr)) {
+                // Do not eliminate the common expression if we could use it for an equi-join.
+                return null;
+            }
+            AbstractFunctionCallExpression conditionFuncExpr = (AbstractFunctionCallExpression) conditionExpr;
+            // Boolean expression that encloses the common subexpression.
+            ILogicalExpression enclosingBoolExpr = null;
+            // We are not dealing with arbitrarily nested and/or expressions here.
+            FunctionIdentifier funcIdent = conditionFuncExpr.getFunctionIdentifier();
+            if (funcIdent.equals(AlgebricksBuiltinFunctions.AND) || funcIdent.equals(AlgebricksBuiltinFunctions.OR)) {
+                Iterator<Mutable<ILogicalExpression>> argIter = conditionFuncExpr.getArguments().iterator();
+                while (argIter.hasNext()) {
+                    Mutable<ILogicalExpression> argRef = argIter.next();
+                    if (containsExpr(argRef.getValue(), commonSubExpr)) {
+                        enclosingBoolExpr = argRef.getValue();
+                        // Remove the enclosing expression from the argument list.
+                        // We are going to pull it out into a new select operator.
+                        argIter.remove();
+                        break;
+                    }
+                }
+                // If and/or only has a single argument left, pull it out and remove the and/or function.
+                if (conditionFuncExpr.getArguments().size() == 1) {
+                    conditionExprRef.setValue(conditionFuncExpr.getArguments().get(0).getValue());
+                }
+            } else {
+                if (!containsExpr(conditionExprRef.getValue(), commonSubExpr)) {
+                    return null;
+                }
+                enclosingBoolExpr = conditionFuncExpr;
+                // Replace the enclosing expression with TRUE.
+                conditionExprRef.setValue(ConstantExpression.TRUE);
+            }
+            return enclosingBoolExpr;
+        }
+    }
+
+    private boolean containsExpr(ILogicalExpression expr, ILogicalExpression searchExpr) {
+        if (expr == searchExpr) {
+            return true;
+        }
+        if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return false;
+        }
+        AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) expr;
+        for (Mutable<ILogicalExpression> argRef : funcExpr.getArguments()) {
+            if (containsExpr(argRef.getValue(), searchExpr)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private boolean isEqJoinCondition(ILogicalExpression expr) {
+        AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) expr;
+        if (funcExpr.getFunctionIdentifier().equals(AlgebricksBuiltinFunctions.EQ)) {
+            ILogicalExpression arg1 = funcExpr.getArguments().get(0).getValue();
+            ILogicalExpression arg2 = funcExpr.getArguments().get(1).getValue();
+            if (arg1.getExpressionTag() == LogicalExpressionTag.VARIABLE
+                    && arg2.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private final class ExprEquivalenceClass {
+        // First operator in which expression is used.
+        private final ILogicalOperator firstOp;
+
+        // Reference to expression in first op.
+        private final Mutable<ILogicalExpression> firstExprRef;
+
+        // Variable that this expression has been assigned to.
+        private LogicalVariable var;
+
+        public ExprEquivalenceClass(ILogicalOperator firstOp, Mutable<ILogicalExpression> firstExprRef) {
+            this.firstOp = firstOp;
+            this.firstExprRef = firstExprRef;
+        }
+
+        public ILogicalOperator getFirstOperator() {
+            return firstOp;
+        }
+
+        public Mutable<ILogicalExpression> getFirstExpression() {
+            return firstExprRef;
+        }
+
+        public void setVariable(LogicalVariable var) {
+            this.var = var;
+        }
+
+        public LogicalVariable getVariable() {
+            return var;
+        }
+
+        public boolean variableIsSet() {
+            return var != null;
+        }
+    }
+}

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/ExtractCommonOperatorsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonOperatorsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonOperatorsRule.java
new file mode 100644
index 0000000..07621ce
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractCommonOperatorsRule.java
@@ -0,0 +1,502 @@
+/*
+ * 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.BitSet;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableInt;
+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.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.VariableReferenceExpression;
+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.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ExchangeOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ReplicateOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.IsomorphismUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.AssignPOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.OneToOneExchangePOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.ReplicatePOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.physical.StreamProjectPOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class ExtractCommonOperatorsRule implements IAlgebraicRewriteRule {
+
+    private final HashMap<Mutable<ILogicalOperator>, List<Mutable<ILogicalOperator>>> childrenToParents = new HashMap<Mutable<ILogicalOperator>, List<Mutable<ILogicalOperator>>>();
+    private final List<Mutable<ILogicalOperator>> roots = new ArrayList<Mutable<ILogicalOperator>>();
+    private final List<List<Mutable<ILogicalOperator>>> equivalenceClasses = new ArrayList<List<Mutable<ILogicalOperator>>>();
+    private final HashMap<Mutable<ILogicalOperator>, BitSet> opToCandidateInputs = new HashMap<Mutable<ILogicalOperator>, BitSet>();
+    private final HashMap<Mutable<ILogicalOperator>, MutableInt> clusterMap = new HashMap<Mutable<ILogicalOperator>, MutableInt>();
+    private final HashMap<Integer, BitSet> clusterWaitForMap = new HashMap<Integer, BitSet>();
+    private int lastUsedClusterId = 0;
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.WRITE && op.getOperatorTag() != LogicalOperatorTag.WRITE_RESULT
+                && op.getOperatorTag() != LogicalOperatorTag.DISTRIBUTE_RESULT) {
+            return false;
+        }
+        if (!roots.contains(op))
+            roots.add(new MutableObject<ILogicalOperator>(op));
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.WRITE && op.getOperatorTag() != LogicalOperatorTag.WRITE_RESULT
+                && op.getOperatorTag() != LogicalOperatorTag.DISTRIBUTE_RESULT) {
+            return false;
+        }
+        boolean rewritten = false;
+        boolean changed = false;
+        if (roots.size() > 0) {
+            do {
+                changed = false;
+                // applying the rewriting until fixpoint
+                topDownMaterialization(roots);
+                genCandidates(context);
+                removeTrivialShare();
+                if (equivalenceClasses.size() > 0)
+                    changed = rewrite(context);
+                if (!rewritten)
+                    rewritten = changed;
+                equivalenceClasses.clear();
+                childrenToParents.clear();
+                opToCandidateInputs.clear();
+                clusterMap.clear();
+                clusterWaitForMap.clear();
+                lastUsedClusterId = 0;
+            } while (changed);
+            roots.clear();
+        }
+        return rewritten;
+    }
+
+    private void removeTrivialShare() {
+        for (List<Mutable<ILogicalOperator>> candidates : equivalenceClasses) {
+            for (int i = candidates.size() - 1; i >= 0; i--) {
+                Mutable<ILogicalOperator> opRef = candidates.get(i);
+                AbstractLogicalOperator aop = (AbstractLogicalOperator) opRef.getValue();
+                if (aop.getOperatorTag() == LogicalOperatorTag.EXCHANGE)
+                    aop = (AbstractLogicalOperator) aop.getInputs().get(0).getValue();
+                if (aop.getOperatorTag() == LogicalOperatorTag.EMPTYTUPLESOURCE)
+                    candidates.remove(i);
+            }
+        }
+        for (int i = equivalenceClasses.size() - 1; i >= 0; i--)
+            if (equivalenceClasses.get(i).size() < 2)
+                equivalenceClasses.remove(i);
+    }
+
+    private boolean rewrite(IOptimizationContext context) throws AlgebricksException {
+        boolean changed = false;
+        for (List<Mutable<ILogicalOperator>> members : equivalenceClasses) {
+            if (rewriteForOneEquivalentClass(members, context))
+                changed = true;
+        }
+        return changed;
+    }
+
+    private boolean rewriteForOneEquivalentClass(List<Mutable<ILogicalOperator>> members, IOptimizationContext context)
+            throws AlgebricksException {
+        List<Mutable<ILogicalOperator>> group = new ArrayList<Mutable<ILogicalOperator>>();
+        boolean rewritten = false;
+        while (members.size() > 0) {
+            group.clear();
+            Mutable<ILogicalOperator> candidate = members.remove(members.size() - 1);
+            group.add(candidate);
+            for (int i = members.size() - 1; i >= 0; i--) {
+                Mutable<ILogicalOperator> peer = members.get(i);
+                if (IsomorphismUtilities.isOperatorIsomorphic(candidate.getValue(), peer.getValue())) {
+                    group.add(peer);
+                    members.remove(i);
+                }
+            }
+            boolean[] materializationFlags = computeMaterilizationFlags(group);
+            if (group.isEmpty()) {
+                continue;
+            }
+            candidate = group.get(0);
+            ReplicateOperator rop = new ReplicateOperator(group.size(), materializationFlags);
+            rop.setPhysicalOperator(new ReplicatePOperator());
+            rop.setExecutionMode(ExecutionMode.PARTITIONED);
+            Mutable<ILogicalOperator> ropRef = new MutableObject<ILogicalOperator>(rop);
+            AbstractLogicalOperator aopCandidate = (AbstractLogicalOperator) candidate.getValue();
+            List<Mutable<ILogicalOperator>> originalCandidateParents = childrenToParents.get(candidate);
+
+            if (aopCandidate.getOperatorTag() == LogicalOperatorTag.EXCHANGE) {
+                rop.getInputs().add(candidate);
+            } else {
+                AbstractLogicalOperator beforeExchange = new ExchangeOperator();
+                beforeExchange.setPhysicalOperator(new OneToOneExchangePOperator());
+                Mutable<ILogicalOperator> beforeExchangeRef = new MutableObject<ILogicalOperator>(beforeExchange);
+                beforeExchange.getInputs().add(candidate);
+                context.computeAndSetTypeEnvironmentForOperator(beforeExchange);
+                rop.getInputs().add(beforeExchangeRef);
+            }
+            context.computeAndSetTypeEnvironmentForOperator(rop);
+
+            for (Mutable<ILogicalOperator> parentRef : originalCandidateParents) {
+                AbstractLogicalOperator parent = (AbstractLogicalOperator) parentRef.getValue();
+                int index = parent.getInputs().indexOf(candidate);
+                if (parent.getOperatorTag() == LogicalOperatorTag.EXCHANGE) {
+                    parent.getInputs().set(index, ropRef);
+                    rop.getOutputs().add(parentRef);
+                } else {
+                    AbstractLogicalOperator exchange = new ExchangeOperator();
+                    exchange.setPhysicalOperator(new OneToOneExchangePOperator());
+                    MutableObject<ILogicalOperator> exchangeRef = new MutableObject<ILogicalOperator>(exchange);
+                    exchange.getInputs().add(ropRef);
+                    rop.getOutputs().add(exchangeRef);
+                    context.computeAndSetTypeEnvironmentForOperator(exchange);
+                    parent.getInputs().set(index, exchangeRef);
+                    context.computeAndSetTypeEnvironmentForOperator(parent);
+                }
+            }
+            List<LogicalVariable> liveVarsNew = new ArrayList<LogicalVariable>();
+            VariableUtilities.getLiveVariables(candidate.getValue(), liveVarsNew);
+            ArrayList<Mutable<ILogicalExpression>> assignExprs = new ArrayList<Mutable<ILogicalExpression>>();
+            for (LogicalVariable liveVar : liveVarsNew)
+                assignExprs.add(new MutableObject<ILogicalExpression>(new VariableReferenceExpression(liveVar)));
+            for (Mutable<ILogicalOperator> ref : group) {
+                if (ref.equals(candidate))
+                    continue;
+                ArrayList<LogicalVariable> liveVars = new ArrayList<LogicalVariable>();
+                Map<LogicalVariable, LogicalVariable> variableMappingBack = new HashMap<LogicalVariable, LogicalVariable>();
+                IsomorphismUtilities.mapVariablesTopDown(ref.getValue(), candidate.getValue(), variableMappingBack);
+                for (int i = 0; i < liveVarsNew.size(); i++) {
+                    liveVars.add(variableMappingBack.get(liveVarsNew.get(i)));
+                }
+
+                AbstractLogicalOperator assignOperator = new AssignOperator(liveVars, assignExprs);
+                assignOperator.setPhysicalOperator(new AssignPOperator());
+                AbstractLogicalOperator projectOperator = new ProjectOperator(liveVars);
+                projectOperator.setPhysicalOperator(new StreamProjectPOperator());
+                AbstractLogicalOperator exchOp = new ExchangeOperator();
+                exchOp.setPhysicalOperator(new OneToOneExchangePOperator());
+                exchOp.getInputs().add(ropRef);
+                MutableObject<ILogicalOperator> exchOpRef = new MutableObject<ILogicalOperator>(exchOp);
+                rop.getOutputs().add(exchOpRef);
+                assignOperator.getInputs().add(exchOpRef);
+                projectOperator.getInputs().add(new MutableObject<ILogicalOperator>(assignOperator));
+
+                // set the types
+                context.computeAndSetTypeEnvironmentForOperator(exchOp);
+                context.computeAndSetTypeEnvironmentForOperator(assignOperator);
+                context.computeAndSetTypeEnvironmentForOperator(projectOperator);
+
+                List<Mutable<ILogicalOperator>> parentOpList = childrenToParents.get(ref);
+                for (Mutable<ILogicalOperator> parentOpRef : parentOpList) {
+                    AbstractLogicalOperator parentOp = (AbstractLogicalOperator) parentOpRef.getValue();
+                    int index = parentOp.getInputs().indexOf(ref);
+                    if (parentOp.getOperatorTag() == LogicalOperatorTag.EXCHANGE) {
+                        AbstractLogicalOperator parentOpNext = (AbstractLogicalOperator) childrenToParents
+                                .get(parentOpRef).get(0).getValue();
+                        if (parentOpNext.isMap()) {
+                            index = parentOpNext.getInputs().indexOf(parentOpRef);
+                            parentOp = parentOpNext;
+                        }
+                    }
+
+                    ILogicalOperator childOp = parentOp.getOperatorTag() == LogicalOperatorTag.PROJECT ? assignOperator
+                            : projectOperator;
+                    if (parentOp.isMap()) {
+                        parentOp.getInputs().set(index, new MutableObject<ILogicalOperator>(childOp));
+                    } else {
+                        AbstractLogicalOperator exchg = new ExchangeOperator();
+                        exchg.setPhysicalOperator(new OneToOneExchangePOperator());
+                        exchg.getInputs().add(new MutableObject<ILogicalOperator>(childOp));
+                        parentOp.getInputs().set(index, new MutableObject<ILogicalOperator>(exchg));
+                        context.computeAndSetTypeEnvironmentForOperator(exchg);
+                    }
+                    context.computeAndSetTypeEnvironmentForOperator(parentOp);
+                }
+            }
+            rewritten = true;
+        }
+        return rewritten;
+    }
+
+    private void genCandidates(IOptimizationContext context) throws AlgebricksException {
+        List<List<Mutable<ILogicalOperator>>> previousEquivalenceClasses = new ArrayList<List<Mutable<ILogicalOperator>>>();
+        while (equivalenceClasses.size() > 0) {
+            previousEquivalenceClasses.clear();
+            for (List<Mutable<ILogicalOperator>> candidates : equivalenceClasses) {
+                List<Mutable<ILogicalOperator>> candidatesCopy = new ArrayList<Mutable<ILogicalOperator>>();
+                candidatesCopy.addAll(candidates);
+                previousEquivalenceClasses.add(candidatesCopy);
+            }
+            List<Mutable<ILogicalOperator>> currentLevelOpRefs = new ArrayList<Mutable<ILogicalOperator>>();
+            for (List<Mutable<ILogicalOperator>> candidates : equivalenceClasses) {
+                if (candidates.size() > 0) {
+                    for (Mutable<ILogicalOperator> opRef : candidates) {
+                        List<Mutable<ILogicalOperator>> refs = childrenToParents.get(opRef);
+                        if (refs != null)
+                            currentLevelOpRefs.addAll(refs);
+                    }
+                }
+                if (currentLevelOpRefs.size() == 0)
+                    continue;
+                candidatesGrow(currentLevelOpRefs, candidates);
+            }
+            if (currentLevelOpRefs.size() == 0)
+                break;
+            prune(context);
+        }
+        if (equivalenceClasses.size() < 1 && previousEquivalenceClasses.size() > 0) {
+            equivalenceClasses.addAll(previousEquivalenceClasses);
+            prune(context);
+        }
+    }
+
+    private void topDownMaterialization(List<Mutable<ILogicalOperator>> tops) {
+        List<Mutable<ILogicalOperator>> candidates = new ArrayList<Mutable<ILogicalOperator>>();
+        List<Mutable<ILogicalOperator>> nextLevel = new ArrayList<Mutable<ILogicalOperator>>();
+        for (Mutable<ILogicalOperator> op : tops) {
+            for (Mutable<ILogicalOperator> opRef : op.getValue().getInputs()) {
+                List<Mutable<ILogicalOperator>> opRefList = childrenToParents.get(opRef);
+                if (opRefList == null) {
+                    opRefList = new ArrayList<Mutable<ILogicalOperator>>();
+                    childrenToParents.put(opRef, opRefList);
+                    nextLevel.add(opRef);
+                }
+                opRefList.add(op);
+            }
+            if (op.getValue().getInputs().size() == 0)
+                candidates.add(op);
+        }
+        if (equivalenceClasses.size() > 0) {
+            equivalenceClasses.get(0).addAll(candidates);
+        } else {
+            equivalenceClasses.add(candidates);
+        }
+        if (nextLevel.size() > 0) {
+            topDownMaterialization(nextLevel);
+        }
+    }
+
+    private void candidatesGrow(List<Mutable<ILogicalOperator>> opList, List<Mutable<ILogicalOperator>> candidates) {
+        List<Mutable<ILogicalOperator>> previousCandidates = new ArrayList<Mutable<ILogicalOperator>>();
+        previousCandidates.addAll(candidates);
+        candidates.clear();
+        boolean validCandidate = false;
+        for (Mutable<ILogicalOperator> op : opList) {
+            List<Mutable<ILogicalOperator>> inputs = op.getValue().getInputs();
+            for (int i = 0; i < inputs.size(); i++) {
+                Mutable<ILogicalOperator> inputRef = inputs.get(i);
+                validCandidate = false;
+                for (Mutable<ILogicalOperator> candidate : previousCandidates) {
+                    // if current input is in candidates
+                    if (inputRef.getValue().equals(candidate.getValue())) {
+                        if (inputs.size() == 1) {
+                            validCandidate = true;
+                        } else {
+                            BitSet candidateInputBitMap = opToCandidateInputs.get(op);
+                            if (candidateInputBitMap == null) {
+                                candidateInputBitMap = new BitSet(inputs.size());
+                                opToCandidateInputs.put(op, candidateInputBitMap);
+                            }
+                            candidateInputBitMap.set(i);
+                            if (candidateInputBitMap.cardinality() == inputs.size()) {
+                                validCandidate = true;
+                            }
+                        }
+                        break;
+                    }
+                }
+            }
+            if (!validCandidate)
+                continue;
+            if (!candidates.contains(op))
+                candidates.add(op);
+        }
+    }
+
+    private void prune(IOptimizationContext context) throws AlgebricksException {
+        List<List<Mutable<ILogicalOperator>>> previousEquivalenceClasses = new ArrayList<List<Mutable<ILogicalOperator>>>();
+        for (List<Mutable<ILogicalOperator>> candidates : equivalenceClasses) {
+            List<Mutable<ILogicalOperator>> candidatesCopy = new ArrayList<Mutable<ILogicalOperator>>();
+            candidatesCopy.addAll(candidates);
+            previousEquivalenceClasses.add(candidatesCopy);
+        }
+        equivalenceClasses.clear();
+        for (List<Mutable<ILogicalOperator>> candidates : previousEquivalenceClasses) {
+            boolean[] reserved = new boolean[candidates.size()];
+            for (int i = 0; i < reserved.length; i++)
+                reserved[i] = false;
+            for (int i = candidates.size() - 1; i >= 0; i--) {
+                if (reserved[i] == false) {
+                    List<Mutable<ILogicalOperator>> equivalentClass = new ArrayList<Mutable<ILogicalOperator>>();
+                    ILogicalOperator candidate = candidates.get(i).getValue();
+                    equivalentClass.add(candidates.get(i));
+                    for (int j = i - 1; j >= 0; j--) {
+                        ILogicalOperator peer = candidates.get(j).getValue();
+                        if (IsomorphismUtilities.isOperatorIsomorphic(candidate, peer)) {
+                            reserved[i] = true;
+                            reserved[j] = true;
+                            equivalentClass.add(candidates.get(j));
+                        }
+                    }
+                    if (equivalentClass.size() > 1) {
+                        equivalenceClasses.add(equivalentClass);
+                        Collections.reverse(equivalentClass);
+                    }
+                }
+            }
+            for (int i = candidates.size() - 1; i >= 0; i--) {
+                if (!reserved[i]) {
+                    candidates.remove(i);
+                }
+            }
+        }
+    }
+
+    private boolean[] computeMaterilizationFlags(List<Mutable<ILogicalOperator>> group) {
+        lastUsedClusterId = 0;
+        for (Mutable<ILogicalOperator> root : roots) {
+            computeClusters(null, root, new MutableInt(++lastUsedClusterId));
+        }
+        boolean[] materializationFlags = new boolean[group.size()];
+        boolean worthMaterialization = worthMaterialization(group.get(0));
+        boolean requiresMaterialization;
+        // get clusterIds for each candidate in the group
+        List<Integer> groupClusterIds = new ArrayList<Integer>(group.size());
+        for (int i = 0; i < group.size(); i++) {
+            groupClusterIds.add(clusterMap.get(group.get(i)).getValue());
+        }
+        for (int i = group.size() - 1; i >= 0; i--) {
+            requiresMaterialization = requiresMaterialization(groupClusterIds, i);
+            if (requiresMaterialization && !worthMaterialization) {
+                group.remove(i);
+                groupClusterIds.remove(i);
+            }
+            materializationFlags[i] = requiresMaterialization;
+        }
+        if (group.size() < 2) {
+            group.clear();
+        }
+        // if does not worth materialization, the flags for the remaining candidates should be false
+        return worthMaterialization ? materializationFlags : new boolean[group.size()];
+    }
+
+    private boolean requiresMaterialization(List<Integer> groupClusterIds, int index) {
+        Integer clusterId = groupClusterIds.get(index);
+        BitSet blockingClusters = new BitSet();
+        getAllBlockingClusterIds(clusterId, blockingClusters);
+        if (!blockingClusters.isEmpty()) {
+            for (int i = 0; i < groupClusterIds.size(); i++) {
+                if (i == index) {
+                    continue;
+                }
+                if (blockingClusters.get(groupClusterIds.get(i))) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    private void getAllBlockingClusterIds(int clusterId, BitSet blockingClusters) {
+        BitSet waitFor = clusterWaitForMap.get(clusterId);
+        if (waitFor != null) {
+            for (int i = waitFor.nextSetBit(0); i >= 0; i = waitFor.nextSetBit(i + 1)) {
+                getAllBlockingClusterIds(i, blockingClusters);
+            }
+            blockingClusters.or(waitFor);
+        }
+    }
+
+    private void computeClusters(Mutable<ILogicalOperator> parentRef, Mutable<ILogicalOperator> opRef,
+            MutableInt currentClusterId) {
+        // only replicate operator has multiple outputs
+        int outputIndex = 0;
+        if (opRef.getValue().getOperatorTag() == LogicalOperatorTag.REPLICATE) {
+            ReplicateOperator rop = (ReplicateOperator) opRef.getValue();
+            List<Mutable<ILogicalOperator>> outputs = rop.getOutputs();
+            for (outputIndex = 0; outputIndex < outputs.size(); outputIndex++) {
+                if (outputs.get(outputIndex).equals(parentRef)) {
+                    break;
+                }
+            }
+        }
+        AbstractLogicalOperator aop = (AbstractLogicalOperator) opRef.getValue();
+        Pair<int[], int[]> labels = aop.getPhysicalOperator().getInputOutputDependencyLabels(opRef.getValue());
+        List<Mutable<ILogicalOperator>> inputs = opRef.getValue().getInputs();
+        for (int i = 0; i < inputs.size(); i++) {
+            Mutable<ILogicalOperator> inputRef = inputs.get(i);
+            if (labels.second[outputIndex] == 1 && labels.first[i] == 0) { // 1 -> 0
+                if (labels.second.length == 1) {
+                    clusterMap.put(opRef, currentClusterId);
+                    // start a new cluster
+                    MutableInt newClusterId = new MutableInt(++lastUsedClusterId);
+                    computeClusters(opRef, inputRef, newClusterId);
+                    BitSet waitForList = clusterWaitForMap.get(currentClusterId.getValue());
+                    if (waitForList == null) {
+                        waitForList = new BitSet();
+                        clusterWaitForMap.put(currentClusterId.getValue(), waitForList);
+                    }
+                    waitForList.set(newClusterId.getValue());
+                }
+            } else { // 0 -> 0 and 1 -> 1
+                MutableInt prevClusterId = clusterMap.get(opRef);
+                if (prevClusterId == null || prevClusterId.getValue().equals(currentClusterId.getValue())) {
+                    clusterMap.put(opRef, currentClusterId);
+                    computeClusters(opRef, inputRef, currentClusterId);
+                } else {
+                    // merge prevClusterId and currentClusterId: update all the map entries that has currentClusterId to prevClusterId
+                    for (BitSet bs : clusterWaitForMap.values()) {
+                        if (bs.get(currentClusterId.getValue())) {
+                            bs.clear(currentClusterId.getValue());
+                            bs.set(prevClusterId.getValue());
+                        }
+                    }
+                    currentClusterId.setValue(prevClusterId.getValue());
+                }
+            }
+        }
+    }
+
+    protected boolean worthMaterialization(Mutable<ILogicalOperator> candidate) {
+        AbstractLogicalOperator aop = (AbstractLogicalOperator) candidate.getValue();
+        if (aop.getPhysicalOperator().expensiveThanMaterialization()) {
+            return true;
+        }
+        List<Mutable<ILogicalOperator>> inputs = candidate.getValue().getInputs();
+        for (Mutable<ILogicalOperator> inputRef : inputs) {
+            if (worthMaterialization(inputRef)) {
+                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/ExtractFunctionsFromJoinConditionRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractFunctionsFromJoinConditionRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractFunctionsFromJoinConditionRule.java
new file mode 100644
index 0000000..8f8e62b
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractFunctionsFromJoinConditionRule.java
@@ -0,0 +1,155 @@
+/*
+ * 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.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+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.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;
+
+/**
+ * Factors out function expressions from each comparison function or similarity function in join condition by
+ * assigning them to a variables, and replacing the function expressions with references to those variables.
+ * Examples:
+ * Plan with function expressions in comparison or similarity condition of join expression.
+ * Generates one assign operator per extracted function expression.
+ *
+ * <pre>
+ * Before plan:
+ * 
+ *   join ( eq( funcX($$1), funcX($$2) ) )
+ * 
+ * After plan:
+ * 
+ *   join (eq($$3,$$4))
+ *   assign [$$4] <- [funcY($$2)]
+ *   assign [$$3] <- [funcX($$1)]
+ * </pre>
+ */
+public class ExtractFunctionsFromJoinConditionRule 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
+                && op.getOperatorTag() != LogicalOperatorTag.LEFTOUTERJOIN) {
+            return false;
+        }
+        AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) op;
+        ILogicalExpression expr = joinOp.getCondition().getValue();
+
+        return assignFunctionExpressions(joinOp, expr, context);
+
+    }
+
+    private boolean assignFunctionExpressions(AbstractLogicalOperator joinOp, ILogicalExpression expr,
+            IOptimizationContext context) throws AlgebricksException {
+        if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+            return false;
+        }
+        AbstractFunctionCallExpression fexp = (AbstractFunctionCallExpression) expr;
+        FunctionIdentifier fi = fexp.getFunctionIdentifier();
+
+        boolean modified = false;
+        if (fi.equals(AlgebricksBuiltinFunctions.AND) || fi.equals(AlgebricksBuiltinFunctions.OR)
+                || processArgumentsToFunction(fi)) {
+            for (Mutable<ILogicalExpression> a : fexp.getArguments()) {
+                if (assignFunctionExpressions(joinOp, a.getValue(), context)) {
+                    modified = true;
+                }
+            }
+            return modified;
+        } else if (AlgebricksBuiltinFunctions.isComparisonFunction(fi) || isComparisonFunction(fi)) {
+            for (Mutable<ILogicalExpression> exprRef : fexp.getArguments()) {
+                if (exprRef.getValue().getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                    LogicalVariable newVar = context.newVar();
+                    AssignOperator newAssign = new AssignOperator(newVar, new MutableObject<ILogicalExpression>(exprRef
+                            .getValue().cloneExpression()));
+                    newAssign.setExecutionMode(joinOp.getExecutionMode());
+
+                    // Place assign below joinOp.
+                    List<LogicalVariable> used = new ArrayList<LogicalVariable>();
+                    VariableUtilities.getUsedVariables(newAssign, used);
+
+                    Mutable<ILogicalOperator> leftBranchRef = joinOp.getInputs().get(0);
+                    ILogicalOperator leftBranch = leftBranchRef.getValue();
+                    List<LogicalVariable> leftBranchVariables = new ArrayList<LogicalVariable>();
+                    VariableUtilities.getLiveVariables(leftBranch, leftBranchVariables);
+                    if (leftBranchVariables.containsAll(used)) {
+                        // place assign on left branch
+                        newAssign.getInputs().add(new MutableObject<ILogicalOperator>(leftBranch));
+                        leftBranchRef.setValue(newAssign);
+                        modified = true;
+                    } else {
+                        Mutable<ILogicalOperator> rightBranchRef = joinOp.getInputs().get(1);
+                        ILogicalOperator rightBranch = rightBranchRef.getValue();
+                        List<LogicalVariable> rightBranchVariables = new ArrayList<LogicalVariable>();
+                        VariableUtilities.getLiveVariables(rightBranch, rightBranchVariables);
+                        if (rightBranchVariables.containsAll(used)) {
+                            // place assign on right branch
+                            newAssign.getInputs().add(new MutableObject<ILogicalOperator>(rightBranch));
+                            rightBranchRef.setValue(newAssign);
+                            modified = true;
+                        }
+                    }
+
+                    if (modified) {
+                        // Replace original expr with variable reference.
+                        exprRef.setValue(new VariableReferenceExpression(newVar));
+                        context.computeAndSetTypeEnvironmentForOperator(newAssign);
+                        context.computeAndSetTypeEnvironmentForOperator(joinOp);
+                    }
+                }
+            }
+            return modified;
+        } else {
+            return false;
+        }
+    }
+
+    protected boolean processArgumentsToFunction(FunctionIdentifier fi) {
+        return false;
+    }
+
+    protected boolean isComparisonFunction(FunctionIdentifier fi) {
+        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/ExtractGbyExpressionsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractGbyExpressionsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractGbyExpressionsRule.java
new file mode 100644
index 0000000..2790166
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/ExtractGbyExpressionsRule.java
@@ -0,0 +1,111 @@
+/*
+ * 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.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.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.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+
+/**
+ * Needed only bc. current Hyrax operators require keys to be fields.
+ */
+public class ExtractGbyExpressionsRule extends AbstractExtractExprRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op1 = (AbstractLogicalOperator) opRef.getValue();
+        if (op1.getOperatorTag() != LogicalOperatorTag.GROUP) {
+            return false;
+        }
+
+        if (context.checkIfInDontApplySet(this, op1)) {
+            return false;
+        }
+        context.addToDontApplySet(this, op1);
+        GroupByOperator g = (GroupByOperator) op1;
+        boolean r1 = gbyExprWasRewritten(g, context);
+        boolean r2 = decorExprWasRewritten(g, context);
+        boolean fired = r1 || r2;
+        if (fired) {
+            context.computeAndSetTypeEnvironmentForOperator(g);
+        }
+        return fired;
+    }
+
+    private boolean gbyExprWasRewritten(GroupByOperator g, IOptimizationContext context) throws AlgebricksException {
+        if (!gbyHasComplexExpr(g)) {
+            return false;
+        }
+        Mutable<ILogicalOperator> opRef2 = g.getInputs().get(0);
+        for (Pair<LogicalVariable, Mutable<ILogicalExpression>> gbyPair : g.getGroupByList()) {
+            ILogicalExpression expr = gbyPair.second.getValue();
+            if (expr.getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+                LogicalVariable v = extractExprIntoAssignOpRef(expr, opRef2, context);
+                gbyPair.second.setValue(new VariableReferenceExpression(v));
+            }
+        }
+        return true;
+    }
+
+    private boolean decorExprWasRewritten(GroupByOperator g, IOptimizationContext context) throws AlgebricksException {
+        if (!decorHasComplexExpr(g)) {
+            return false;
+        }
+        Mutable<ILogicalOperator> opRef2 = g.getInputs().get(0);
+        for (Pair<LogicalVariable, Mutable<ILogicalExpression>> decorPair : g.getDecorList()) {
+            ILogicalExpression expr = decorPair.second.getValue();
+            if (expr.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+                LogicalVariable v = extractExprIntoAssignOpRef(expr, opRef2, context);
+                decorPair.second.setValue(new VariableReferenceExpression(v));
+            }
+        }
+        return true;
+    }
+
+    private boolean gbyHasComplexExpr(GroupByOperator g) {
+        for (Pair<LogicalVariable, Mutable<ILogicalExpression>> gbyPair : g.getGroupByList()) {
+            if (gbyPair.second.getValue().getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private boolean decorHasComplexExpr(GroupByOperator g) {
+        for (Pair<LogicalVariable, Mutable<ILogicalExpression>> gbyPair : g.getDecorList()) {
+            if (gbyPair.second.getValue().getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+                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/FactorRedundantGroupAndDecorVarsRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/FactorRedundantGroupAndDecorVarsRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/FactorRedundantGroupAndDecorVarsRule.java
new file mode 100644
index 0000000..6cb01f2
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/FactorRedundantGroupAndDecorVarsRule.java
@@ -0,0 +1,92 @@
+/*
+ * 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.HashMap;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+
+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.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.VariableReferenceExpression;
+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.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class FactorRedundantGroupAndDecorVarsRule 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;
+        }
+        GroupByOperator gby = (GroupByOperator) op;
+        Map<LogicalVariable, LogicalVariable> varRhsToLhs = new HashMap<LogicalVariable, LogicalVariable>();
+        boolean gvChanged = factorRedundantRhsVars(gby.getGroupByList(), opRef, varRhsToLhs, context);
+        boolean dvChanged = factorRedundantRhsVars(gby.getDecorList(), opRef, varRhsToLhs, context);
+
+        return gvChanged || dvChanged;
+    }
+
+    private boolean factorRedundantRhsVars(List<Pair<LogicalVariable, Mutable<ILogicalExpression>>> veList,
+            Mutable<ILogicalOperator> opRef, Map<LogicalVariable, LogicalVariable> varRhsToLhs,
+            IOptimizationContext context) throws AlgebricksException {
+        varRhsToLhs.clear();
+        ListIterator<Pair<LogicalVariable, Mutable<ILogicalExpression>>> iter = veList.listIterator();
+        boolean changed = false;
+        while (iter.hasNext()) {
+            Pair<LogicalVariable, Mutable<ILogicalExpression>> p = iter.next();
+            if (p.second.getValue().getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+                continue;
+            }
+            LogicalVariable v = GroupByOperator.getDecorVariable(p);
+            LogicalVariable lhs = varRhsToLhs.get(v);
+            if (lhs != null) {
+                if (p.first != null) {
+                    AssignOperator assign = new AssignOperator(p.first, new MutableObject<ILogicalExpression>(
+                            new VariableReferenceExpression(lhs)));
+                    ILogicalOperator op = opRef.getValue();
+                    assign.getInputs().add(new MutableObject<ILogicalOperator>(op));
+                    opRef.setValue(assign);
+                    context.computeAndSetTypeEnvironmentForOperator(assign);
+                }
+                iter.remove();
+                changed = true;
+            } else {
+                varRhsToLhs.put(v, p.first);
+            }
+        }
+        return changed;
+    }
+
+}

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/InferTypesRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InferTypesRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InferTypesRule.java
new file mode 100644
index 0000000..3530a5f
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InferTypesRule.java
@@ -0,0 +1,42 @@
+/*
+ * 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.rewriter.base.IAlgebraicRewriteRule;
+
+public class InferTypesRule 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 op = opRef.getValue();
+        if (context.getOutputTypeEnvironment(op) != null) {
+            return false;
+        }
+        context.computeAndSetTypeEnvironmentForOperator(op);
+        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/InlineAssignIntoAggregateRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineAssignIntoAggregateRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineAssignIntoAggregateRule.java
new file mode 100644
index 0000000..99a1fae
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineAssignIntoAggregateRule.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.List;
+
+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.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+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.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.visitors.AbstractConstVarFunVisitor;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class InlineAssignIntoAggregateRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        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;
+        }
+        boolean changed = false;
+        GroupByOperator gbyOp = (GroupByOperator) op;
+        for (ILogicalPlan p : gbyOp.getNestedPlans()) {
+            for (Mutable<ILogicalOperator> r : p.getRoots()) {
+                if (inlined(r)) {
+                    changed = true;
+                }
+            }
+        }
+        return changed;
+    }
+
+    private boolean inlined(Mutable<ILogicalOperator> r) throws AlgebricksException {
+        AbstractLogicalOperator op1 = (AbstractLogicalOperator) r.getValue();
+        if (op1.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+            return false;
+        }
+        AbstractLogicalOperator op2 = (AbstractLogicalOperator) op1.getInputs().get(0).getValue();
+        if (op2.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+            return false;
+        }
+        AggregateOperator agg = (AggregateOperator) op1;
+        AssignOperator assign = (AssignOperator) op2;
+        VarExprSubstitution ves = new VarExprSubstitution(assign.getVariables(), assign.getExpressions());
+        for (Mutable<ILogicalExpression> exprRef : agg.getExpressions()) {
+            ILogicalExpression expr = exprRef.getValue();
+            Pair<Boolean, ILogicalExpression> p = expr.accept(ves, null);
+            if (p.first == true) {
+                exprRef.setValue(p.second);
+            }
+            // AbstractLogicalExpression ale = (AbstractLogicalExpression) expr;
+            // ale.accept(ves, null);
+        }
+        List<Mutable<ILogicalOperator>> op1InpList = op1.getInputs();
+        op1InpList.clear();
+        op1InpList.add(op2.getInputs().get(0));
+        return true;
+    }
+
+    private class VarExprSubstitution extends AbstractConstVarFunVisitor<Pair<Boolean, ILogicalExpression>, Void> {
+
+        private List<LogicalVariable> variables;
+        private List<Mutable<ILogicalExpression>> expressions;
+
+        public VarExprSubstitution(List<LogicalVariable> variables, List<Mutable<ILogicalExpression>> expressions) {
+            this.variables = variables;
+            this.expressions = expressions;
+        }
+
+        @Override
+        public Pair<Boolean, ILogicalExpression> visitConstantExpression(ConstantExpression expr, Void arg) {
+            return new Pair<Boolean, ILogicalExpression>(false, expr);
+        }
+
+        @Override
+        public Pair<Boolean, ILogicalExpression> visitFunctionCallExpression(AbstractFunctionCallExpression expr,
+                Void arg) throws AlgebricksException {
+            boolean changed = false;
+            for (Mutable<ILogicalExpression> eRef : expr.getArguments()) {
+                ILogicalExpression e = eRef.getValue();
+                Pair<Boolean, ILogicalExpression> p = e.accept(this, arg);
+                if (p.first) {
+                    eRef.setValue(p.second);
+                    changed = true;
+                }
+            }
+            return new Pair<Boolean, ILogicalExpression>(changed, expr);
+        }
+
+        @Override
+        public Pair<Boolean, ILogicalExpression> visitVariableReferenceExpression(VariableReferenceExpression expr,
+                Void arg) {
+            LogicalVariable v = expr.getVariableReference();
+            int idx = variables.indexOf(v);
+            if (idx < 0) {
+                return new Pair<Boolean, ILogicalExpression>(false, expr);
+            } else {
+                return new Pair<Boolean, ILogicalExpression>(true, expressions.get(idx).getValue());
+            }
+
+        }
+
+    }
+}

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/InlineSingleReferenceVariablesRule.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineSingleReferenceVariablesRule.java b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineSingleReferenceVariablesRule.java
new file mode 100644
index 0000000..9ae94ba
--- /dev/null
+++ b/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/InlineSingleReferenceVariablesRule.java
@@ -0,0 +1,94 @@
+/*
+ * 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.List;
+import java.util.Map;
+
+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.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+
+/**
+ * Inlines variables that are referenced exactly once.
+ * 
+ * Preconditions/Assumptions:
+ * Assumes no projects are in the plan.
+ * 
+ * Example assuming variable $$3 is referenced exactly once.
+ * 
+ * Before plan:
+ * select (funcA($$3))
+ *   ...
+ *     assign [$$3] <- [field-access($$0, 1)]
+ * 
+ * After plan:
+ * select (funcA(field-access($$0, 1))
+ *   ...
+ *     assign [] <- []
+ */
+public class InlineSingleReferenceVariablesRule extends InlineVariablesRule {
+
+    // Maps from variable to a list of operators using that variable.
+    protected Map<LogicalVariable, List<ILogicalOperator>> usedVarsMap = new HashMap<LogicalVariable, List<ILogicalOperator>>();
+    protected List<LogicalVariable> usedVars = new ArrayList<LogicalVariable>();
+    
+    @Override
+    protected void prepare(IOptimizationContext context) {
+        super.prepare(context);
+        usedVarsMap.clear();
+        usedVars.clear();
+    }
+    
+    @Override
+    protected boolean performFinalAction() throws AlgebricksException {
+        boolean modified = false;
+        for (Map.Entry<LogicalVariable, List<ILogicalOperator>> entry : usedVarsMap.entrySet()) {
+            // Perform replacement only if variable is referenced a single time.
+            if (entry.getValue().size() == 1) {
+                ILogicalOperator op = entry.getValue().get(0);
+                if (!op.requiresVariableReferenceExpressions()) {
+                    inlineVisitor.setOperator(op);
+                    inlineVisitor.setTargetVariable(entry.getKey());
+                    if (op.acceptExpressionTransform(inlineVisitor)) {
+                        modified = true;
+                    }
+                    inlineVisitor.setTargetVariable(null);
+                }         
+            }
+        }
+        return modified;
+    }
+
+    @Override
+    protected boolean performBottomUpAction(AbstractLogicalOperator op) throws AlgebricksException {
+        usedVars.clear();
+        VariableUtilities.getUsedVariables(op, usedVars);
+        for (LogicalVariable var : usedVars) {
+            List<ILogicalOperator> opsUsingVar = usedVarsMap.get(var);
+            if (opsUsingVar == null) {
+                opsUsingVar = new ArrayList<ILogicalOperator>();
+                usedVarsMap.put(var, opsUsingVar);
+            }
+            opsUsingVar.add(op);
+        }
+        return false;
+    }
+}


Mime
View raw message