Started to split the original misnamed AsterixInlineVariablesRule into simpler rules. Inlining constants will now be done by the proper variable inlining rule.

git-svn-id: https://asterixdb.googlecode.com/svn/branches/asterix_inline_vars@784 eaa15691-b419-025a-1212-ee371bd00084
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
index 17b0b1d..cc89d60 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
@@ -41,6 +41,7 @@
 import edu.uci.ics.asterix.optimizer.rules.PushGroupByThroughProduct;
 import edu.uci.ics.asterix.optimizer.rules.PushProperJoinThroughProduct;
 import edu.uci.ics.asterix.optimizer.rules.RemoveRedundantListifyRule;
+import edu.uci.ics.asterix.optimizer.rules.RemoveRedundantVariablesRule;
 import edu.uci.ics.asterix.optimizer.rules.SetAsterixPhysicalOperatorsRule;
 import edu.uci.ics.asterix.optimizer.rules.SetClosedRecordConstructorsRule;
 import edu.uci.ics.asterix.optimizer.rules.SimilarityCheckRule;
@@ -147,12 +148,13 @@
         fieldLoads.add(new PushFieldAccessRule());
         // fieldLoads.add(new ByNameToByHandleFieldAccessRule()); -- disabled
         fieldLoads.add(new ByNameToByIndexFieldAccessRule());
-        fieldLoads.add(new AsterixInlineVariablesRule());
-        // fieldLoads.add(new InlineRecordAccessRule());
-        fieldLoads.add(new RemoveUnusedAssignAndAggregateRule());
-        fieldLoads.add(new ConstantFoldingRule());
+        //fieldLoads.add(new AsterixInlineVariablesRule());
+        fieldLoads.add(new RemoveRedundantVariablesRule());
+        //fieldLoads.add(new AsterixProperInlineVariablesRule());
+        fieldLoads.add(new RemoveUnusedAssignAndAggregateRule());        
+        fieldLoads.add(new ConstantFoldingRule());        
         fieldLoads.add(new FeedScanCollectionToUnnest());
-        fieldLoads.add(new ComplexJoinInferenceRule());
+        fieldLoads.add(new ComplexJoinInferenceRule());        
         return fieldLoads;
     }
 
@@ -171,18 +173,15 @@
         consolidation.add(new IntroduceGroupByCombinerRule());
         consolidation.add(new IntroduceAggregateCombinerRule());
         consolidation.add(new CountVarToCountOneRule());
-        consolidation.add(new RemoveUnusedAssignAndAggregateRule());
-        consolidation.add(new IntroduceSecondaryIndexInsertDeleteRule());
+        consolidation.add(new RemoveUnusedAssignAndAggregateRule());        
         return consolidation;
     }
     
     public final static List<IAlgebraicRewriteRule> buildAccessMethodRuleCollection() {
-        List<IAlgebraicRewriteRule> accessMethod = new LinkedList<IAlgebraicRewriteRule>();        
+        List<IAlgebraicRewriteRule> accessMethod = new LinkedList<IAlgebraicRewriteRule>();
         accessMethod.add(new IntroduceSelectAccessMethodRule());
-        //accessMethod.add(new AsterixProperInlineVariablesRule());
-        //accessMethod.add(new PushSelectIntoJoinRule());
-        //accessMethod.add(new RemoveUnusedAssignAndAggregateRule());        
         accessMethod.add(new IntroduceJoinAccessMethodRule());
+        accessMethod.add(new IntroduceSecondaryIndexInsertDeleteRule());
         return accessMethod;
     }
 
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/AsterixProperInlineVariablesRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/AsterixProperInlineVariablesRule.java
index 3eeb731..ea47fdc 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/AsterixProperInlineVariablesRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/AsterixProperInlineVariablesRule.java
@@ -53,14 +53,15 @@
     
     private InlineVariablesVisitor inlineVisitor = new InlineVariablesVisitor(varAssignRhs);
     
+    // Do not inline field accesses because doing so would interfere with our access method rewrites.
     // TODO: For now we must exclude these functions to avoid breaking our type casting rules
-    // IntroduceStaticTypeCastRule and IntroduceDynamicTypeCastRule.
+    // IntroduceStaticTypeCastRule and IntroduceDynamicTypeCastRule. 
     private static Set<FunctionIdentifier> doNotInlineFuncs = new HashSet<FunctionIdentifier>();
     static {
+        doNotInlineFuncs.add(AsterixBuiltinFunctions.FIELD_ACCESS_BY_NAME);
+        doNotInlineFuncs.add(AsterixBuiltinFunctions.FIELD_ACCESS_BY_INDEX);
         doNotInlineFuncs.add(AsterixBuiltinFunctions.CLOSED_RECORD_CONSTRUCTOR);
         doNotInlineFuncs.add(AsterixBuiltinFunctions.OPEN_RECORD_CONSTRUCTOR);
-        //doNotInlineFuncs.add(AsterixBuiltinFunctions.FIELD_ACCESS_BY_INDEX);
-        //doNotInlineFuncs.add(AsterixBuiltinFunctions.FIELD_ACCESS_BY_NAME);
     }
     
     @Override
@@ -69,18 +70,13 @@
     }
 
     @Override
-    /**
-     * 
-     * Does one big DFS sweep over the plan.
-     * 
-     */
     public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
         varAssignRhs.clear();
         affectedProjects.clear();
         inlineVisitor.setContext(context);
         boolean modified = inlineVariables(opRef, context);
         if (modified) {
-            context.addToDontApplySet(this, opRef.getValue());
+            context.addToDontApplySet(this, opRef.getValue());            
         }
         return modified;
     }
@@ -88,10 +84,6 @@
     private boolean inlineVariables(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
             throws AlgebricksException {
         AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
-        if (context.checkIfInDontApplySet(this, op)) {
-            return false;
-        }
-
         // Update mapping from variables to expressions during descent.
         if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
             AssignOperator assignOp = (AssignOperator) op;
@@ -131,34 +123,19 @@
             }
         }
 
-        switch (op.getOperatorTag()) {
-            case WRITE: 
-            case WRITE_RESULT:
-            case INSERT_DELETE:
-            case INDEX_INSERT_DELETE:
-            case PROJECT:
-            // We can currently only order/group by a variable reference expression.
-            case GROUP:
-            case DISTINCT:
-            case AGGREGATE:
-            case ORDER:
-            case INNERJOIN:
-            case LEFTOUTERJOIN:
-            // TODO: Enabling this will require fixes in the access method rewrite rules.
-            case UNNEST_MAP: {
-                break;
-            }
-            default: {
-                inlineVisitor.setOperator(op);
-                if (op.acceptExpressionTransform(inlineVisitor)) {
-                    modified = true;
-                }
+        // Only inline for operators that can deal with arbitrary expressions.
+        if (!op.requiresVariableReferenceExpressions()) {
+            inlineVisitor.setOperator(op);
+            if (op.acceptExpressionTransform(inlineVisitor)) {
+                modified = true;
             }
         }
         
         if (modified) {
             context.computeAndSetTypeEnvironmentForOperator(op);
             context.addToDontApplySet(this, op);
+            // Re-enable rules that we had already tried since they could be applicable after inlining.
+            context.removeFromAlreadyCompared(opRef.getValue());
         }
 
         return modified;
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/RemoveRedundantVariablesRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/RemoveRedundantVariablesRule.java
new file mode 100644
index 0000000..ff66973
--- /dev/null
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/RemoveRedundantVariablesRule.java
@@ -0,0 +1,344 @@
+/*
+ * Copyright 2009-2010 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.asterix.optimizer.rules;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+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.EquivalenceClass;
+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.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ProjectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.visitors.ILogicalExpressionReferenceTransform;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * Replaces redundant variable references with their bottom-most equivalent representative.
+ * Does a DFS sweep over the plan keeping track of variable equivalence classes.
+ * For example, this rule would perform the following rewrite.
+ * 
+ * Before Plan:
+ * select (function-call: func, Args:[%0->$$11])
+ *   project [$11]
+ *     assign [$$11] <- [$$10]
+ *       assign [$$10] <- [$$9]
+ *         assign [$$9] <- ...
+ *           ...
+ *           
+ * After Plan:
+ * select (function-call: func, Args:[%0->$$9])
+ *   project [$9]
+ *     assign [$$11] <- [$$9]
+ *       assign [$$10] <- [$$9]
+ *         assign [$$9] <- ...
+ *           ...
+ */
+public class RemoveRedundantVariablesRule implements IAlgebraicRewriteRule {
+
+    private final VariableSubstitutionVisitor substVisitor = new VariableSubstitutionVisitor();
+    // TODO: Rename to equivalentVarsMap
+    private final Map<LogicalVariable, List<LogicalVariable>> equivalenceClasses = new HashMap<LogicalVariable, List<LogicalVariable>>();
+    
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context) {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        if (context.checkIfInDontApplySet(this, opRef.getValue())) {
+            return false;
+        }
+        boolean modified = removeRedundantVariables(opRef, context);
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(opRef.getValue());
+        }
+        return modified;
+    }
+
+    private void updateEquivalenceClassMap(LogicalVariable lhs, LogicalVariable rhs) {
+        List<LogicalVariable> equivalentVars = equivalenceClasses.get(rhs);
+        if (equivalentVars == null) {
+            equivalentVars = new ArrayList<LogicalVariable>();
+            // The first element in the list is the bottom-most representative which will replace all equivalent vars.
+            equivalentVars.add(rhs);
+            equivalentVars.add(lhs);
+            equivalenceClasses.put(rhs, equivalentVars);
+        }
+        equivalenceClasses.put(lhs, equivalentVars);
+        equivalentVars.get(0);
+    }
+    
+    private boolean removeRedundantVariables(Mutable<ILogicalOperator> opRef,
+            IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();        
+        boolean modified = false;
+        
+        // Recurse into children.
+        for (Mutable<ILogicalOperator> inputOpRef : op.getInputs()) {
+            if (removeRedundantVariables(inputOpRef, context)) {
+                modified = true;
+            }
+        }
+
+        // Update equivalence classes and replace variable references with their first representative.
+        if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {            
+            AssignOperator assignOp = (AssignOperator) op;
+            int numVars = assignOp.getVariables().size();
+            for (int i = 0; i < numVars; i++) {
+                ILogicalExpression expr = assignOp.getExpressions().get(i).getValue();
+                if (expr.getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+                    continue;
+                }
+                VariableReferenceExpression rhsVarRefExpr = (VariableReferenceExpression) expr;
+                // Update equivalence class map.
+                LogicalVariable lhs = assignOp.getVariables().get(i);
+                LogicalVariable rhs = rhsVarRefExpr.getVariableReference();
+                updateEquivalenceClassMap(lhs, rhs);
+            }
+        }
+        
+        switch (op.getOperatorTag()) {
+            case PROJECT: {
+                // The project operator does not use expressions, so we need to replace it's variables manually.
+                if (replaceProjectVars((ProjectOperator) op)) {
+                    modified = true;
+                }
+                break;
+            }
+            default: {
+                if (op.acceptExpressionTransform(substVisitor)) {
+                    modified = true;
+                    context.computeAndSetTypeEnvironmentForOperator(op);
+                }
+            }
+        }
+        
+
+        /*
+        if (op.hasNestedPlans()) {
+            AbstractOperatorWithNestedPlans n = (AbstractOperatorWithNestedPlans) op;
+            List<EquivalenceClass> eqc = equivClasses;
+            if (n.getOperatorTag() == LogicalOperatorTag.SUBPLAN) {
+                eqc = new LinkedList<EquivalenceClass>();
+            } else {
+                eqc = equivClasses;
+            }
+            for (ILogicalPlan p : n.getNestedPlans()) {
+                for (Mutable<ILogicalOperator> r : p.getRoots()) {
+                    Pair<Boolean, Boolean> bb = collectEqClassesAndRemoveRedundantOps(r, context, false, eqc,
+                            substVisitor, substVisitorForWrites);
+                    if (bb.first) {
+                        modified = true;
+                    }
+                    if (bb.second) {
+                        ecChange = true;
+                    }
+                }
+            }
+        }
+        // we assume a variable is assigned a value only once
+        if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+            AssignOperator a = (AssignOperator) op;
+            ILogicalExpression rhs = a.getExpressions().get(0).getValue();
+            if (rhs.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+                LogicalVariable varLeft = a.getVariables().get(0);
+                VariableReferenceExpression varRef = (VariableReferenceExpression) rhs;
+                LogicalVariable varRight = varRef.getVariableReference();
+
+                EquivalenceClass ecRight = findEquivClass(varRight, equivClasses);
+                if (ecRight != null) {
+                    ecRight.addMember(varLeft);
+                } else {
+                    List<LogicalVariable> m = new LinkedList<LogicalVariable>();
+                    m.add(varRight);
+                    m.add(varLeft);
+                    EquivalenceClass ec = new EquivalenceClass(m, varRight);
+                    equivClasses.add(ec);
+                    if (AlgebricksConfig.DEBUG) {
+                        AlgebricksConfig.ALGEBRICKS_LOGGER.finest("--- New equivalence class: " + ec + "\n");
+                    }
+                }
+                ecChange = true;
+            } else if (((AbstractLogicalExpression) rhs).getExpressionTag() == LogicalExpressionTag.CONSTANT) {
+                LogicalVariable varLeft = a.getVariables().get(0);
+                List<LogicalVariable> m = new LinkedList<LogicalVariable>();
+                m.add(varLeft);
+                EquivalenceClass ec = new EquivalenceClass(m, (ConstantExpression) rhs);
+                // equivClassesForParent.add(ec);
+                equivClasses.add(ec);
+                ecChange = true;
+            }
+        } else if (op.getOperatorTag() == LogicalOperatorTag.GROUP && !(context.checkIfInDontApplySet(this, op))) {
+            GroupByOperator group = (GroupByOperator) op;
+            Pair<Boolean, Boolean> r1 = processVarExprPairs(group.getGroupByList(), equivClasses);
+            Pair<Boolean, Boolean> r2 = processVarExprPairs(group.getDecorList(), equivClasses);
+            modified = modified || r1.first || r2.first;
+            ecChange = r1.second || r2.second;
+        }
+        if (op.getOperatorTag() == LogicalOperatorTag.PROJECT) {
+            assignVarsNeededByProject((ProjectOperator) op, equivClasses, context);
+        } else {
+            boolean assignRecord = false;
+            if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+                AssignOperator assignOp = (AssignOperator) op;
+                List<Mutable<ILogicalExpression>> exprRefs = assignOp.getExpressions();
+                for (Mutable<ILogicalExpression> exprRef : exprRefs) {
+                    ILogicalExpression expr = exprRef.getValue();
+                    if (expr.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                        ScalarFunctionCallExpression funExpr = (ScalarFunctionCallExpression) expr;
+                        if (funExpr.getFunctionIdentifier().equals(AsterixBuiltinFunctions.OPEN_RECORD_CONSTRUCTOR)
+                                || funExpr.getFunctionIdentifier().equals(AsterixBuiltinFunctions.CLOSED_RECORD_CONSTRUCTOR)) {
+                            assignRecord = true;
+                            break;
+                        }
+
+                    }
+                }
+            }
+
+            if (op.getOperatorTag() == LogicalOperatorTag.WRITE
+                    || op.getOperatorTag() == LogicalOperatorTag.INSERT_DELETE
+                    || op.getOperatorTag() == LogicalOperatorTag.INDEX_INSERT_DELETE
+                    || op.getOperatorTag() == LogicalOperatorTag.WRITE_RESULT || assignRecord) {
+                substVisitorForWrites.setEquivalenceClasses(equivClasses);
+                if (op.acceptExpressionTransform(substVisitorForWrites)) {
+                    modified = true;
+                }
+            } else {
+                substVisitor.setEquivalenceClasses(equivClasses);
+                if (op.acceptExpressionTransform(substVisitor)) {
+                    modified = true;
+                    if (op.getOperatorTag() == LogicalOperatorTag.GROUP) {
+                        GroupByOperator group = (GroupByOperator) op;
+                        for (Pair<LogicalVariable, Mutable<ILogicalExpression>> gp : group.getGroupByList()) {
+                            if (gp.first != null
+                                    && gp.second.getValue().getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+                                LogicalVariable gv = ((VariableReferenceExpression) gp.second.getValue())
+                                        .getVariableReference();
+                                Iterator<Pair<LogicalVariable, Mutable<ILogicalExpression>>> iter = group.getDecorList()
+                                        .iterator();
+                                while (iter.hasNext()) {
+                                    Pair<LogicalVariable, Mutable<ILogicalExpression>> dp = iter.next();
+                                    if (dp.first == null
+                                            && dp.second.getValue().getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+                                        LogicalVariable dv = ((VariableReferenceExpression) dp.second.getValue())
+                                                .getVariableReference();
+                                        if (dv == gv) {
+                                            // The decor variable is redundant,
+                                            // since it is
+                                            // propagated as a grouping
+                                            // variable.
+                                            EquivalenceClass ec1 = findEquivClass(gv, equivClasses);
+                                            if (ec1 != null) {
+                                                ec1.addMember(gp.first);
+                                                ec1.setVariableRepresentative(gp.first);
+                                            } else {
+                                                List<LogicalVariable> varList = new ArrayList<LogicalVariable>();
+                                                varList.add(gp.first);
+                                                varList.add(gv);
+                                                ec1 = new EquivalenceClass(varList, gp.first);
+                                            }
+                                            iter.remove();
+                                            break;
+                                        }
+                                    }
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        if (modified) {
+            context.computeAndSetTypeEnvironmentForOperator(op);
+        }
+        return new Pair<Boolean, Boolean>(modified, ecChange);
+        */
+        return modified;
+    }
+
+    private boolean replaceProjectVars(ProjectOperator op) throws AlgebricksException {
+        List<LogicalVariable> vars = op.getVariables();
+        int size = vars.size();
+        boolean modified = false;
+        for (int i = 0; i < size; i++) {
+            LogicalVariable var = vars.get(i);
+            List<LogicalVariable> equivalentVars = equivalenceClasses.get(var);
+            if (equivalentVars == null) {
+                continue;
+            }
+            // Replace with representative.
+            LogicalVariable representative = equivalentVars.get(0);
+            if (representative != var) {
+                vars.set(i, equivalentVars.get(0));
+                modified = true;
+            }
+        }
+        return modified;
+    }
+    
+    private class VariableSubstitutionVisitor implements ILogicalExpressionReferenceTransform {
+        @Override
+        public boolean transform(Mutable<ILogicalExpression> exprRef) {
+            ILogicalExpression e = exprRef.getValue();
+            switch (((AbstractLogicalExpression) e).getExpressionTag()) {
+                case VARIABLE: {
+                    // Replace variable references with their equivalent representative in the equivalence class map.
+                    VariableReferenceExpression varRefExpr = (VariableReferenceExpression) e;
+                    LogicalVariable var = varRefExpr.getVariableReference();
+                    List<LogicalVariable> equivalentVars = equivalenceClasses.get(var);
+                    if (equivalentVars == null) {
+                        return false;
+                    }
+                    LogicalVariable representative = equivalentVars.get(0);
+                    if (representative != var) {
+                        varRefExpr.setVariable(representative);
+                        return true;
+                    }
+                    return false;
+                }
+                case FUNCTION_CALL: {
+                    AbstractFunctionCallExpression fce = (AbstractFunctionCallExpression) e;
+                    boolean modified = false;
+                    for (Mutable<ILogicalExpression> arg : fce.getArguments()) {
+                        if (transform(arg)) {
+                            modified = true;
+                        }
+                    }
+                    return modified;
+                }
+                default: {
+                    return false;
+                }
+            }
+        }
+    }
+}