You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pig.apache.org by da...@apache.org on 2009/12/04 01:25:59 UTC

svn commit: r887013 [2/4] - in /hadoop/pig/branches/branch-0.6: ./ src/org/apache/pig/ src/org/apache/pig/backend/executionengine/ src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/ src/org/apache/pig/backend/hadoop/executionengine/physi...

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLimit.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLimit.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLimit.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLimit.java Fri Dec  4 00:25:57 2009
@@ -163,7 +163,10 @@
     }
     
     @Override
-    public List<RequiredFields> getRelevantInputs(int output, int column) {
+    public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        
         if (output!=0)
             return null;
 

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLoad.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLoad.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLoad.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOLoad.java Fri Dec  4 00:25:57 2009
@@ -25,6 +25,8 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.TreeSet;
+
 import org.apache.pig.ExecType;
 import org.apache.pig.LoadFunc;
 import org.apache.pig.PigException;
@@ -36,6 +38,7 @@
 import org.apache.pig.impl.plan.ProjectionMap;
 import org.apache.pig.impl.plan.RequiredFields;
 import org.apache.pig.impl.plan.VisitorException;
+import org.apache.pig.impl.plan.optimizer.OptimizerException;
 import org.apache.pig.impl.util.MultiMap;
 import org.apache.pig.impl.util.Pair;
 import org.apache.pig.impl.util.WrappedIOException;
@@ -57,6 +60,7 @@
     private ExecType mExecType;
     private static Log log = LogFactory.getLog(LOLoad.class);
     private Schema mDeterminedSchema = null;
+    private LoadFunc.RequiredFieldList requiredFieldList;
 
     /**
      * @param plan
@@ -85,10 +89,13 @@
         mStorage = storage;
         mExecType = execType;
         this.splittable = splittable;
+        // Generate a psudo alias. Since in the following script, we do not have alias for LOLoad, however, alias is required.
+        // a = foreach (load '1') generate b0;
+        this.mAlias = ""+key.getId();
 
          try { 
              mLoadFunc = (LoadFunc)
-                  PigContext.instantiateFuncFromSpec(inputFileSpec.getFuncSpec()); 
+                  PigContext.instantiateFuncFromSpec(inputFileSpec.getFuncSpec());
         }catch (ClassCastException cce) {
             log.error(inputFileSpec.getFuncSpec() + " should implement the LoadFunc interface.");
             throw WrappedIOException.wrap(cce);
@@ -145,6 +152,9 @@
                 }
 
                 if(null == mDeterminedSchema) {
+                    // Zebra loader determineSchema method depends on this signature
+                    if (mStorage!=null)
+                        mStorage.getConfiguration().setProperty("pig.loader.signature", mAlias);
                     mSchema = mLoadFunc.determineSchema(mSchemaFile, mExecType, mStorage);
                     mDeterminedSchema  = mSchema;
                 }
@@ -253,6 +263,9 @@
             }
         } else {
             try {
+                // Zebra loader determineSchema method depends on this signature
+                if (mStorage!=null)
+                    mStorage.getConfiguration().setProperty("pig.loader.signature", mAlias);
                 inputSchema = mLoadFunc.determineSchema(mSchemaFile, mExecType, mStorage);
             } catch (IOException ioe) {
                 mProjectionMap = null;
@@ -294,7 +307,10 @@
     }
 
     @Override
-    public List<RequiredFields> getRelevantInputs(int output, int column) {
+    public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        
         if (output!=0)
             return null;
         
@@ -312,5 +328,70 @@
         result.add(new RequiredFields(true));
         return result;
     }
+    
+    public LoadFunc.RequiredFieldResponse fieldsToRead(LoadFunc.RequiredFieldList requiredFieldList) throws FrontendException
+    {
+        LoadFunc.RequiredFieldResponse response = new LoadFunc.RequiredFieldResponse(false);
+        if (mSchema == null)
+            return response;
+        
+        if (requiredFieldList.isAllFieldsRequired())
+            return response;
+        
+        if (requiredFieldList.getFields()==null)
+        {
+            return response;
+        }
+        
+        this.requiredFieldList = requiredFieldList;
+        response = mLoadFunc.fieldsToRead(requiredFieldList);
+        
+        if (!response.getRequiredFieldResponse())
+            return response;
+        
+        // Change LOLoad schema to reflect this pruning
+        TreeSet<Integer> prunedIndexSet = new TreeSet<Integer>();
+        for (int i=0;i<mSchema.size();i++)
+            prunedIndexSet.add(i);
 
+        for (int i=0;i<requiredFieldList.getFields().size();i++)
+        {
+            LoadFunc.RequiredField requiredField = requiredFieldList.getFields().get(i); 
+            if (requiredField.getIndex()>=0)
+                prunedIndexSet.remove(requiredField.getIndex());
+            else
+            {
+                
+                try {
+                    int index = mSchema.getPosition(requiredField.getAlias());
+                    if (index>0)
+                        prunedIndexSet.remove(index);
+                } catch (FrontendException e) {
+                    return new LoadFunc.RequiredFieldResponse(false);
+                }
+                
+            }
+        }
+        
+        Integer index;
+        while ((index = prunedIndexSet.pollLast())!=null)
+            mSchema.getFields().remove(index.intValue());
+        
+        mIsProjectionMapComputed = false;
+        getProjectionMap();
+        return response;
+
+    }
+
+    @Override
+    public boolean pruneColumns(List<Pair<Integer, Integer>> columns)
+            throws FrontendException {
+        throw new FrontendException("Not implemented");
+    }
+    
+    public LoadFunc.RequiredFieldList getRequiredFieldList()
+    {
+        return requiredFieldList;
+    }
+    
 }

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSort.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSort.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSort.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSort.java Fri Dec  4 00:25:57 2009
@@ -339,7 +339,10 @@
     }
     
     @Override
-    public List<RequiredFields> getRelevantInputs(int output, int column) {
+    public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        
         if (output!=0)
             return null;
         
@@ -359,4 +362,39 @@
         result.add(new RequiredFields(inputList));
         return result;
     }
+    
+    @Override
+    public boolean pruneColumns(List<Pair<Integer, Integer>> columns)
+            throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        if (mSchema == null) {
+            log
+                    .warn("Cannot prune columns in sort, no schema information found");
+            return false;
+        }
+
+        List<LogicalOperator> predecessors = mPlan.getPredecessors(this);
+
+        if (predecessors == null)
+            return false;
+
+        for (Pair<Integer, Integer> column : columns) {
+            if (column.first != 0) {
+                int errCode = 2191;
+                throw new FrontendException(
+                        "Sort only take 1 input, cannot prune input with index "
+                                + column.first, errCode, PigException.BUG);
+            }
+            if (column.second < 0) {
+                int errCode = 2192;
+                throw new FrontendException("Column to prune does not exist", errCode, PigException.BUG);
+            }
+            for (LogicalPlan plan : mSortColPlans) {
+                pruneColumnInPlan(plan, column.second);
+            }
+        }
+        super.pruneColumns(columns);;
+        return true;
+    }
 }

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplit.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplit.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplit.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplit.java Fri Dec  4 00:25:57 2009
@@ -185,7 +185,10 @@
    }
    
    @Override
-   public List<RequiredFields> getRelevantInputs(int output, int column) {
+   public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+       if (!mIsSchemaComputed)
+           getSchema();
+       
        if (output<0)
            return null;
        
@@ -204,8 +207,10 @@
                return null;
        }
        
+       ArrayList<Pair<Integer, Integer>> inputList = new ArrayList<Pair<Integer, Integer>>();
+       inputList.add(new Pair<Integer, Integer>(0, column));
        List<RequiredFields> result = new ArrayList<RequiredFields>();
-       result.add(new RequiredFields(false, true));
+       result.add(new RequiredFields(inputList));
        return result;
    }
 

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplitOutput.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplitOutput.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplitOutput.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOSplitOutput.java Fri Dec  4 00:25:57 2009
@@ -26,6 +26,8 @@
 import java.util.Map;
 import java.util.Set;
 
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
 import org.apache.pig.PigException;
 import org.apache.pig.impl.logicalLayer.LogicalOperator;
 import org.apache.pig.impl.logicalLayer.schema.Schema;
@@ -45,6 +47,7 @@
 
     protected int mIndex;
     private LogicalPlan mCondPlan;
+    private static Log log = LogFactory.getLog(LOSplitOutput.class);
     
     /**
      * @param plan
@@ -240,7 +243,10 @@
         //split output
     }
     @Override
-    public List<RequiredFields> getRelevantInputs(int output, int column) {
+    public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        
         if (output!=0)
             return null;
 
@@ -260,4 +266,32 @@
         result.add(new RequiredFields(inputList));
         return result;
     }
+    
+    @Override
+    public boolean pruneColumns(List<Pair<Integer, Integer>> columns)
+            throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        if (mSchema == null) {
+            log.warn("Cannot prune columns in splitoutput, no schema information found");
+            return false;
+        }
+
+        for (Pair<Integer, Integer> column : columns) {
+            if (column.first != 0) {
+                int errCode = 2191;
+                throw new FrontendException(
+                        "Splitoutput only take 1 input, cannot prune input with index "
+                                + column.first, errCode, PigException.BUG);
+            }
+            if (column.second < 0) {
+                int errCode = 2192;
+                throw new FrontendException("Column to prune does not exist", errCode, PigException.BUG);
+            }
+
+            pruneColumnInPlan(mCondPlan, column.second);
+        }
+        super.pruneColumns(columns);
+        return true;
+    }
 }

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStore.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStore.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStore.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStore.java Fri Dec  4 00:25:57 2009
@@ -177,7 +177,10 @@
     }
     
     @Override
-    public List<RequiredFields> getRelevantInputs(int output, int column) {
+    public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        
         if (output!=0)
             return null;
         

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStream.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStream.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStream.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOStream.java Fri Dec  4 00:25:57 2009
@@ -238,7 +238,10 @@
     }
     
     @Override
-    public List<RequiredFields> getRelevantInputs(int output, int column) {
+    public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        
         if (output!=0)
             return null;
 

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOUnion.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOUnion.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOUnion.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/LOUnion.java Fri Dec  4 00:25:57 2009
@@ -41,6 +41,8 @@
 
     private static final long serialVersionUID = 2L;
     private static Log log = LogFactory.getLog(LOUnion.class);
+    
+    List<Pair<Integer, Integer>> stagingPrunedColumns = new ArrayList<Pair<Integer, Integer>>(); 
 
     /**
      * @param plan
@@ -206,7 +208,10 @@
     }
 
     @Override
-    public List<RequiredFields> getRelevantInputs(int output, int column) {
+    public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException {
+        if (!mIsSchemaComputed)
+            getSchema();
+        
         if (output!=0)
             return null;
 
@@ -236,4 +241,23 @@
         return result;
     }
 
+    public boolean pruneColumns(List<Pair<Integer, Integer>> columns)
+        throws FrontendException {
+        stagingPrunedColumns.addAll(columns);
+        boolean allPruned = true;
+        for (Pair<Integer, Integer>pair : columns)
+        {
+            for (int i=0;i<mPlan.getPredecessors(this).size();i++)
+            {
+                if (!stagingPrunedColumns.contains(new Pair<Integer, Integer>(i, pair.second)))
+                    allPruned = false;
+            }
+        }
+        if (allPruned)
+        {
+            super.pruneColumns(columns);
+            return true;
+        }
+        return false;
+    }
 }

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/RelationalOperator.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/RelationalOperator.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/RelationalOperator.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/RelationalOperator.java Fri Dec  4 00:25:57 2009
@@ -19,9 +19,12 @@
 
 import java.util.List;
 
+import org.apache.pig.PigException;
 import org.apache.pig.impl.plan.OperatorKey;
 import org.apache.pig.impl.plan.ProjectionMap;
 import org.apache.pig.impl.plan.RequiredFields;
+import org.apache.pig.impl.plan.VisitorException;
+import org.apache.pig.impl.util.Pair;
 
 public abstract class RelationalOperator extends LogicalOperator {
     private static final long serialVersionUID = 2L;
@@ -140,7 +143,38 @@
      * @param column output column
      * @return List of relevant input columns. null if Pig cannot determine relevant inputs or any error occurs
      */
-    abstract public List<RequiredFields> getRelevantInputs(int output, int column); 
+    abstract public List<RequiredFields> getRelevantInputs(int output, int column) throws FrontendException; 
 
+    public boolean pruneColumns(List<Pair<Integer, Integer>> columns)
+            throws FrontendException {
+        unsetSchema();
+        getSchema();
+        mIsProjectionMapComputed = false;
+        getProjectionMap();
+        return true;
+    }
 
+    public void pruneColumnInPlan(LogicalPlan plan, int column)
+            throws FrontendException {
+        TopLevelProjectFinder projectFinder = new TopLevelProjectFinder(plan);
+        try {
+            projectFinder.visit();
+        } catch (VisitorException ve) {
+            int errCode = 2196;
+            throw new FrontendException("Exception when traversing inner plan",
+                    errCode, PigException.BUG, ve);
+        }
+        for (LOProject loProject : projectFinder.getProjectSet()) {
+            if (loProject.isStar()) {
+                int errCode = 2197;
+                throw new FrontendException(
+                        "Cannot drop column which require *", errCode,
+                        PigException.BUG);
+            }
+            int col = loProject.getCol();
+            if (column < col) {
+                loProject.getProjection().set(0, col - 1);
+            }
+        }
+    }
 }

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/ImplicitSplitInserter.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/ImplicitSplitInserter.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/ImplicitSplitInserter.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/ImplicitSplitInserter.java Fri Dec  4 00:25:57 2009
@@ -37,7 +37,7 @@
 public class ImplicitSplitInserter extends LogicalTransformer {
 
     public ImplicitSplitInserter(LogicalPlan plan) {
-        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+        super(plan);
     }
 
     @Override

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java Fri Dec  4 00:25:57 2009
@@ -31,6 +31,7 @@
 import org.apache.pig.impl.logicalLayer.LOStream;
 import org.apache.pig.impl.logicalLayer.LogicalOperator;
 import org.apache.pig.impl.logicalLayer.LogicalPlan;
+import org.apache.pig.impl.logicalLayer.RelationalOperator;
 import org.apache.pig.impl.plan.NodeIdGenerator;
 import org.apache.pig.impl.plan.OperatorKey;
 import org.apache.pig.impl.plan.VisitorException;
@@ -46,6 +47,7 @@
     private static NodeIdGenerator nodeIdGen = NodeIdGenerator.getGenerator();
     
     private Set<String> mRulesOff = null;
+    private Rule<LogicalOperator, LogicalPlan> pruneRule;
 
     public LogicalOptimizer(LogicalPlan plan) {
         this(plan, ExecType.MAPREDUCE);
@@ -148,19 +150,33 @@
             rule = new Rule<LogicalOperator, LogicalPlan>(rulePlan,
                     new PushDownForeachFlatten(plan), "PushDownForeachFlatten");
             checkAndAddRule(rule);
+            
+            // Prune column up wherever possible
+            rulePlan = new RulePlan();
+            RuleOperator rulePruneColumnsOperator = new RuleOperator(RelationalOperator.class, RuleOperator.NodeType.ANY_NODE,
+                    new OperatorKey(SCOPE, nodeIdGen.getNextNodeId(SCOPE)));
+            rulePlan.add(rulePruneColumnsOperator);
+            pruneRule = new Rule<LogicalOperator, LogicalPlan>(rulePlan,
+                    new PruneColumns(plan), "PruneColumns", Rule.WalkerAlgo.ReverseDependencyOrderWalker);
         }
         
     }
 
-    private void checkAndAddRule(Rule<LogicalOperator, LogicalPlan> rule) {
-        if(mRulesOff != null) {
+    private boolean ruleEnabled(Rule<LogicalOperator, LogicalPlan> rule) {
+        if(mRulesOff != null && rule != null) {
             for(String ruleOff: mRulesOff) {
                 String ruleName = rule.getRuleName();
                 if(ruleName == null) continue;
-                if(ruleName.equalsIgnoreCase(ruleOff)) return;
+                if(ruleName.equalsIgnoreCase(ruleOff)) return false;
             }
         }
         mRules.add(rule);
+        return true;
+    }
+    
+    private void checkAndAddRule(Rule<LogicalOperator, LogicalPlan> rule) {
+        if (ruleEnabled(rule))
+            mRules.add(rule);
     }
 
     @Override
@@ -205,5 +221,18 @@
                 }
             }
         } while(sawMatch && ++numIterations < mMaxIterations);
+        if (pruneRule!=null && ruleEnabled(pruneRule))
+        {
+            RuleMatcher<LogicalOperator, LogicalPlan> matcher = new RuleMatcher<LogicalOperator, LogicalPlan>();
+            if (matcher.match(pruneRule)) {
+                List<List<LogicalOperator>> matches = matcher.getAllMatches();
+                for (List<LogicalOperator> match:matches)
+                {
+                    if (pruneRule.getTransformer().check(match)) {
+                        pruneRule.getTransformer().transform(match);
+                    }
+                }
+            }
+        }
     }
 }
\ No newline at end of file

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java Fri Dec  4 00:25:57 2009
@@ -47,9 +47,8 @@
     private final Log log = LogFactory.getLog(getClass());
 
     protected LogicalTransformer(
-            LogicalPlan plan,
-            PlanWalker<LogicalOperator, LogicalPlan> walker) {
-        super(plan, walker);
+            LogicalPlan plan) {
+        super(plan);
     }
 
     /**

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java Fri Dec  4 00:25:57 2009
@@ -58,11 +58,11 @@
     private ExecType mode = ExecType.MAPREDUCE;
 
     public OpLimitOptimizer(LogicalPlan plan) {
-        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+        super(plan);
     }
 
     public OpLimitOptimizer(LogicalPlan plan, ExecType mode) {
-        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+        super(plan);
         this.mode = mode;
     }
 

Added: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PruneColumns.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PruneColumns.java?rev=887013&view=auto
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PruneColumns.java (added)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PruneColumns.java Fri Dec  4 00:25:57 2009
@@ -0,0 +1,783 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *     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 org.apache.pig.impl.logicalLayer.optimizer;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.pig.LoadFunc;
+import org.apache.pig.PigException;
+import org.apache.pig.data.DataType;
+import org.apache.pig.impl.logicalLayer.ColumnPruner;
+import org.apache.pig.impl.logicalLayer.ExpressionOperator;
+import org.apache.pig.impl.logicalLayer.FrontendException;
+import org.apache.pig.impl.logicalLayer.LOCast;
+import org.apache.pig.impl.logicalLayer.LOCogroup;
+import org.apache.pig.impl.logicalLayer.LOCross;
+import org.apache.pig.impl.logicalLayer.LODistinct;
+import org.apache.pig.impl.logicalLayer.LOFilter;
+import org.apache.pig.impl.logicalLayer.LOForEach;
+import org.apache.pig.impl.logicalLayer.LOJoin;
+import org.apache.pig.impl.logicalLayer.LOLoad;
+import org.apache.pig.impl.logicalLayer.LOMapLookup;
+import org.apache.pig.impl.logicalLayer.LOProject;
+import org.apache.pig.impl.logicalLayer.LOSort;
+import org.apache.pig.impl.logicalLayer.LOSplit;
+import org.apache.pig.impl.logicalLayer.LOSplitOutput;
+import org.apache.pig.impl.logicalLayer.LOStore;
+import org.apache.pig.impl.logicalLayer.LOStream;
+import org.apache.pig.impl.logicalLayer.LOUnion;
+import org.apache.pig.impl.logicalLayer.LogicalOperator;
+import org.apache.pig.impl.logicalLayer.LogicalPlan;
+import org.apache.pig.impl.logicalLayer.RelationalOperator;
+import org.apache.pig.impl.logicalLayer.TopLevelProjectFinder;
+import org.apache.pig.impl.plan.DependencyOrderWalker;
+import org.apache.pig.impl.plan.MapKeysInfo;
+import org.apache.pig.impl.plan.NodeIdGenerator;
+import org.apache.pig.impl.plan.OperatorKey;
+import org.apache.pig.impl.plan.RequiredFields;
+import org.apache.pig.impl.plan.VisitorException;
+import org.apache.pig.impl.plan.optimizer.OptimizerException;
+import org.apache.pig.impl.util.Pair;
+
+class RequiredInfo {
+    List<RequiredFields> requiredFieldsList;
+
+    RequiredInfo(List<RequiredFields> requiredFieldsList)
+    {
+        this.requiredFieldsList = requiredFieldsList;
+    }
+}
+
+public class PruneColumns extends LogicalTransformer {
+
+    private static Log log = LogFactory.getLog(PruneColumns.class);
+    Map<RelationalOperator, RequiredInfo> cachedRequiredInfo = new HashMap<RelationalOperator, RequiredInfo>();
+    
+    public PruneColumns(LogicalPlan plan) {
+        super(plan);
+    }
+
+    @Override
+    public boolean check(List<LogicalOperator> nodes) throws OptimizerException {
+        if((nodes == null) || (nodes.size() <= 0)) {
+            int errCode = 2177;
+            String msg = "Cannot retrieve operator from null or empty list.";
+            throw new OptimizerException(msg, errCode, PigException.BUG);
+        }
+        
+        try {
+            LogicalOperator lo = nodes.get(0);
+            if (lo == null) {
+                int errCode = 2178;
+                String msg = "The matching node from the optimizor framework is null";
+                throw new OptimizerException(msg, errCode, PigException.BUG);
+            }
+            if ((lo instanceof LOForEach||lo instanceof LOSplit)&&lo.getSchema()!=null)
+                return true;
+            return false;
+        } catch (Exception e) {
+            int errCode = 2179;
+            String msg = "Error while performing checks to prune columns.";
+            throw new OptimizerException(msg, errCode, PigException.BUG, e);
+        }
+    }
+    
+    @Override
+    // transform will pick every LOForEach and LOSplit
+    public void transform(List<LogicalOperator> nodes)
+            throws OptimizerException {
+        if((nodes == null) || (nodes.size() <= 0)) {
+            int errCode = 2177;
+            String msg = "Cannot retrieve operator from null or empty list.";
+            throw new OptimizerException(msg, errCode, PigException.BUG);
+        }
+        try {
+            LogicalOperator lo = nodes.get(0);
+            if (lo == null || !(lo instanceof LOForEach || lo instanceof LOSplit)) {
+                int errCode = 2178;
+                String msg = "Expected " + LOForEach.class.getSimpleName() + " or " + LOSplit.class.getSimpleName();
+                throw new OptimizerException(msg, errCode, PigException.BUG);
+            }
+
+            // Check if we have saved requiredInfo, if so, we will use that as required output fields for that operator;
+            // Otherwise means we require every output field
+            RequiredInfo requiredOutputInfo = cachedRequiredInfo.get(lo);
+
+            if (requiredOutputInfo==null)
+            {
+                List<RequiredFields> requiredOutputFieldsList = new ArrayList<RequiredFields>();
+                List<LogicalOperator> successors = mPlan.getSuccessors(lo);
+                if (successors==null)
+                {
+                    requiredOutputFieldsList.add(new RequiredFields(true));
+                }
+                else
+                {
+                    // The only case requiredOutputFieldsList more than 1 element is when the current 
+                    // operator is LOSplit
+                    for (int i=0;i<successors.size();i++)
+                    {
+                        requiredOutputFieldsList.add(new RequiredFields(true));
+                    }
+                }
+                requiredOutputInfo = new RequiredInfo(requiredOutputFieldsList);
+            }
+            processNode(lo, requiredOutputInfo);
+        } catch (OptimizerException oe) {
+            throw oe;
+        } catch (Exception e) {
+            int errCode = 2181;
+            String msg = "Unable to prune columns.";
+            throw new OptimizerException(msg, errCode, PigException.BUG, e);
+        }
+    }
+
+    // We recursively collect required fields from forEach from bottom to top, until one of the following conditions occurs:
+    //   1. If we see another LOForEach, we simply stop because optimizor will pick that foreach later and start from there
+    //   2. If we see LOStore, LOStream, LODistinct, we stop, LOStore, LOStream, LODistinct require all fields, we cannot push upward
+    //   3. If we see LOLoad, we set required fields and stop, LOLoad suppose to read only required fields
+    //   4. If we see LOSplit, we save requiredInfo and quit. optimizor will pick that split after all its successors are visited
+    // For all other operators, we recursively call processNode for all its parents
+    // 
+    // Inside processNode, we will collect required input columns from required output columns. Required input/output columns 
+    //     also include required map keys referred by the logical plan beneath. Required input columns come from two sources:
+    //   1. Relevant input fields of required output fields
+    //   2. Required input fields of the logic operator
+    //
+    // lo: logical operator to process
+    // requiredOutputFields: requiredFieldsList below this operator
+    public void processNode(LogicalOperator lo, RequiredInfo requiredOutputInfo) throws OptimizerException
+    {
+        try
+        {
+            if (!(lo instanceof RelationalOperator))
+            {
+                int errCode = 2182;
+                String msg = "Only relational operator can be used in column prune optimization.";
+                throw new OptimizerException(msg, errCode, PigException.BUG);
+            }
+            if (lo.getSchema()==null)
+            {
+                return;
+            }
+            RelationalOperator rlo = (RelationalOperator)lo;
+            List<LogicalOperator> predecessors = (mPlan.getPredecessors(rlo) == null ? null
+                    : new ArrayList<LogicalOperator>(mPlan.getPredecessors(rlo)));
+            
+            // Now we have collected required output fields of LOLoad (include requried map keys).
+            // We need to push these into the loader
+            if (rlo instanceof LOLoad)
+            {
+                // LOLoad has only one output
+                RequiredFields loaderRequiredFields = requiredOutputInfo.requiredFieldsList.get(0);
+                pruneLoader((LOLoad)rlo, loaderRequiredFields);
+                return;
+            }
+            
+            // If the predecessor is one of LOStore/LOStream/LODistinct, we stop to trace up.
+            // We require all input fields. We stop processing here. The optimizer will
+            // pick the next ForEach and start processing from there
+            if (rlo instanceof LOStore || rlo instanceof LOStream || rlo instanceof LODistinct) {
+                return;
+            }
+            
+            // merge requiredOutputFields and process the predecessor
+            if (rlo instanceof LOSplit)
+            {
+                List<RequiredFields> requiredInputFieldsList = new ArrayList<RequiredFields>();
+                RequiredFields requiredFields = new RequiredFields(false);
+                for (RequiredFields rf : requiredOutputInfo.requiredFieldsList)
+                {
+                    if (rf!=null)
+                    {
+                        rf.reIndex(0);
+                        requiredFields.merge(rf);
+                    }
+                }
+                requiredInputFieldsList.add(requiredFields);
+                if (predecessors.get(0) instanceof LOForEach || predecessors.get(0) instanceof LOSplit)
+                    cachedRequiredInfo.put((RelationalOperator)predecessors.get(0), new RequiredInfo(requiredInputFieldsList));
+                else
+                    processNode(predecessors.get(0), new RequiredInfo(requiredInputFieldsList));
+                return;
+            }
+            
+            // Initialize requiredInputFieldsList
+            List<RequiredFields> requiredInputFieldsList = new ArrayList<RequiredFields>(); 
+            for (int i=0;i<predecessors.size();i++)
+                requiredInputFieldsList.add(null);
+            
+            // Map required output columns to required input columns.
+            // We also collect required output map keys into input map keys.
+            // Since we have already processed Split, so every remaining operator
+            // have only one element in requiredOutputFieldList, so we get the first 
+            // element and process
+            RequiredFields requiredOutputFields = requiredOutputInfo.requiredFieldsList.get(0);
+            
+            // needAllFields means we require every individual output column and all map keys of that output.
+            // We convert needAllFields to individual fields here to facilitate further processing
+            if (requiredOutputFields.needAllFields())
+            {
+                List<Pair<Integer, Integer>> outputList = new ArrayList<Pair<Integer, Integer>>(); 
+                for (int j=0;j<rlo.getSchema().size();j++)
+                    outputList.add(new Pair<Integer, Integer>(0, j));
+                requiredOutputFields = new RequiredFields(outputList);
+                for (int i=0;i<requiredOutputFields.size();i++)
+                    requiredOutputFields.setMapKeysInfo(i, new MapKeysInfo(true));
+            }
+            
+            if (requiredOutputFields.getFields()==null)
+            {
+                int errCode = 2184;
+                String msg = "Fields list inside RequiredFields is null.";
+                throw new OptimizerException(msg, errCode, PigException.BUG);
+            }
+            
+            for (int i=0;i<requiredOutputFields.size();i++)
+            {
+                Pair<Integer, Integer> requiredOutputField = requiredOutputFields.getField(i);
+                MapKeysInfo outputMapKeysInfo = requiredOutputFields.getMapKeysInfo(i);
+
+                List<RequiredFields> relevantFieldsList = rlo.getRelevantInputs(requiredOutputField.first, requiredOutputField.second);
+                
+                // We do not have any relevant input fields for this output, continue to next output 
+                if (relevantFieldsList==null)
+                    continue;
+                
+                for (int j=0;j<relevantFieldsList.size();j++)
+                {
+                    RequiredFields relevantFields = relevantFieldsList.get(j);
+                    
+                    if (relevantFields!=null && relevantFields.needAllFields())
+                    {
+                        requiredInputFieldsList.set(j, new RequiredFields(true));
+                        continue;
+                    }
+                    
+                    // Mapping output map keys to input map keys
+                    if (rlo instanceof LOCogroup)
+                    {
+                        if (j!=0 && relevantFields!=null && !relevantFields.needAllFields())
+                        {
+                            for (Pair<Integer, Integer> pair : relevantFields.getFields())
+                                relevantFields.setMapKeysInfo(pair.first, pair.second, 
+                                        new MapKeysInfo(true));
+                        }
+                    }
+                    else if (rlo instanceof LOForEach)
+                    {
+                        // Relay map keys from output to input
+                        LogicalPlan forEachPlan = ((LOForEach)rlo).getRelevantPlan(requiredOutputField.first, requiredOutputField.second);
+                        if (relevantFields.getFields()!=null && relevantFields.getFields().size()!=0)
+                        {
+                            int index = ((LOForEach)rlo).getForEachPlans().indexOf(forEachPlan);
+                            // We check if the field get flattened, if it does, then we do not relay output map keys to input map keys.
+                            // There are two situations:
+                            // 1. input column is tuple, bag, or other simple type, there is no concept of map key, so we do not relay
+                            // 2. input column is map, flatten does not do anything, we can still relay
+                            boolean nonflatten = false;
+                            if (!((LOForEach)rlo).getFlatten().get(index))
+                            {
+                                nonflatten = true;
+                            }
+                            else
+                            {
+                                // Foreach plan is flattened, check if there is only one input for this foreach plan 
+                                // and input schema for that input is not map, if so, it is a dummy flatten 
+                                if (forEachPlan.getRoots().size()==1 && forEachPlan.getRoots().get(0) instanceof LOProject)
+                                {
+                                    LOProject loProj = (LOProject)forEachPlan.getRoots().get(0);
+                                    if (loProj.getExpression().getSchema()!=null &&
+                                            loProj.getExpression().getSchema().getField(loProj.getCol()).type!=DataType.BAG)
+                                        nonflatten = true;
+                                }
+                            }
+                            if (nonflatten && outputMapKeysInfo!=null && isSimpleProjectCast(forEachPlan))
+                            {
+                                Pair<Integer, Integer> inputColumn = relevantFields.getFields().get(0);
+                                relevantFields.setMapKeysInfo(inputColumn.first, inputColumn.second, outputMapKeysInfo);
+                            }
+                        }
+                        
+                        // Collect required map keys in foreach plan here.
+                        // This is the only logical operator that we collect map keys 
+                        // which are introduced by the operator here.
+                        // For all other logical operators, it is attached to required fields
+                        // of that logical operator, will process in required fields processing
+                        // section
+                        for (Pair<Integer, Integer> relevantField : relevantFields.getFields())
+                        {
+                            MapKeysInfo mapKeysInfo = getMapKeysInPlan(forEachPlan, relevantField.second);
+                            relevantFields.mergeMapKeysInfo(0, relevantField.second, mapKeysInfo);
+                        }
+                    }
+                    else
+                    {
+                        // For all other logical operators, we have one output column mapping to one or more input column.
+                        // We copy the output map keys from the output column to the according input column
+                        if (relevantFields!=null && relevantFields.getFields()!=null && outputMapKeysInfo!=null)
+                        {
+                            for (Pair<Integer, Integer> pair : relevantFields.getFields())
+                                relevantFields.setMapKeysInfo(pair.first, pair.second, 
+                                        outputMapKeysInfo);
+                        }
+                    }
+                    
+                    // Now we aggregate the input columns of this output column to the required input columns
+                    if (requiredInputFieldsList.get(j)==null)
+                        requiredInputFieldsList.set(j, relevantFields);
+                    else
+                    {
+                        requiredInputFieldsList.get(j).merge(relevantFields);
+                    }
+                }
+            }
+
+                
+            // Merge with required input fields of this logical operator.
+            // RequiredInputFields come from two sources, one is mapping from required output to input, 
+            // the other is from the operator itself. Here we use getRequiredFields to get the second part,
+            // and merge with the first part
+            List<RequiredFields> requiredFieldsListOfLOOp;
+            
+            // For LOForEach, requiredFields is not really required fields. Here required fields means the input
+            // fields required by the entire output columns, such as filter condition in LOFilter, group columns in LOCoGroup.
+            // For LOForEach, output columns are generated by the foreach plan it belongs to, there is nothing globally required.
+            // So we need to fix the semantic gap here. If the operator is LOForEach, requiredFields is null.
+            // For LOCross/LOUnion, actually we do not require any field here
+            if (rlo instanceof LOForEach || rlo instanceof LOCross || rlo instanceof LOUnion)
+                requiredFieldsListOfLOOp = null;
+            else
+                requiredFieldsListOfLOOp = rlo.getRequiredFields();
+            
+            if (requiredFieldsListOfLOOp!=null)
+            {
+                for (int i=0;i<requiredFieldsListOfLOOp.size();i++)
+                {
+                    RequiredFields requiredFieldsOfLOOp = requiredFieldsListOfLOOp.get(i);
+                    if (requiredInputFieldsList.get(i)==null)
+                        requiredInputFieldsList.set(i, requiredFieldsOfLOOp);
+                    else
+                    {
+                        requiredInputFieldsList.get(i).merge(requiredFieldsOfLOOp);
+                    }
+                }
+                
+                // Collect required map keys of this operator
+                // Cases are:
+                // 1. Single predecessor: LOFilter, LOSplitOutput, LOSort
+                // 2. Multiple predecessors: LOJoin
+                // 3. LOForEach do not have operator-wise required fields, we
+                //    have already processed it
+                // 4. LOCogroup require all map keys (even if we cogroup by a0#'k1', a0 itself will be in bag a
+                //    and we have no way to figure out which keys are referenced for a0. So we do not process it and
+                //    simply require all map keys)
+                // 5. Other operators do not have required fields, no need to process
+                if (rlo instanceof LOFilter || rlo instanceof LOSplitOutput || rlo instanceof LOSort)
+                {
+                    List<LogicalPlan> innerPlans = new ArrayList<LogicalPlan>();
+                    if (rlo instanceof LOFilter)
+                    {
+                        innerPlans.add(((LOFilter)rlo).getComparisonPlan());
+                    }
+                    else if (rlo instanceof LOSplitOutput)
+                    {
+                        innerPlans.add(((LOSplitOutput)rlo).getConditionPlan());
+                    }
+                    else if (rlo instanceof LOSort)
+                    {
+                        innerPlans.addAll(((LOSort)rlo).getSortColPlans());
+                    }
+                    for (LogicalPlan p : innerPlans)
+                    {
+                        for (RequiredFields rf : requiredFieldsListOfLOOp)
+                        {
+                            if (rf.getFields()==null)
+                                continue;
+                            for (Pair<Integer, Integer> pair : rf.getFields())
+                            {
+                                MapKeysInfo mapKeysInfo = getMapKeysInPlan(p, pair.second);
+                                if (mapKeysInfo!=null && !mapKeysInfo.needAllKeys() && mapKeysInfo.getKeys()!=null)
+                                    requiredInputFieldsList.get(0).mergeMapKeysInfo(0, pair.second, 
+                                            mapKeysInfo);
+                            }
+                        }
+                    }
+                }
+                else if (rlo instanceof LOJoin)
+                {
+                    for (int i=0;i<predecessors.size();i++)
+                    {
+                        Collection<LogicalPlan> joinPlans = ((LOJoin)rlo).getJoinPlans().get(predecessors.get(i));
+                        if (joinPlans==null)
+                            continue;
+                        for (LogicalPlan p : joinPlans)
+                        {
+                            RequiredFields rf = requiredFieldsListOfLOOp.get(i);
+                            if (rf.getFields()==null)
+                                continue;
+                            for (Pair<Integer, Integer> pair : rf.getFields())
+                            {
+                                MapKeysInfo mapKeysInfo = getMapKeysInPlan(p, pair.second);
+                                if (mapKeysInfo!=null && !mapKeysInfo.needAllKeys() && mapKeysInfo.getKeys()!=null)
+                                    requiredInputFieldsList.get(i).mergeMapKeysInfo(i, pair.second, 
+                                            mapKeysInfo);
+                            }
+                        }
+                    }
+                }
+            }
+            
+            // Now we finish the current logical operator, we need to process next logical operator. There are two cases:
+            // 1. If the predecessor is LOForEach or LOSplit, we put requiredOutputFieldsList into cache and exit, the optimizer
+            //    will invoke transform() on LOForEach or LOSplit and continue to process
+            // 2. If the predecessor is otherwise, we then recursively collect required fields for the predecessor
+            for (int i=0;i<predecessors.size();i++)
+            {
+            	RelationalOperator predecessor = (RelationalOperator)predecessors.get(i);
+                
+                List<RequiredFields> newRequiredOutputFieldsList = new ArrayList<RequiredFields>();
+            	
+                // In this optimization, we only prune columns and do not change structure of logical plan
+                // So if we do not require anything from the input, we change it to require the first field
+                if (requiredInputFieldsList.get(i)==null || requiredInputFieldsList.get(i).getNeedNoFields())
+                {
+                    List<Pair<Integer, Integer>> dummyFields = new ArrayList<Pair<Integer, Integer>>();
+                    dummyFields.add(new Pair<Integer, Integer>(i, 0));
+                    requiredInputFieldsList.set(i, new RequiredFields(dummyFields));
+                }
+                // For all logical operator with one output, reindex the output to 0
+                if (!(predecessor instanceof LOSplit))
+                {
+                    if (requiredInputFieldsList.get(i)!=null)
+                        requiredInputFieldsList.get(i).reIndex(0);
+                    newRequiredOutputFieldsList.add(requiredInputFieldsList.get(i));
+                }
+            	if (predecessor instanceof LOForEach)
+            	{
+            	    cachedRequiredInfo.put(predecessor, new RequiredInfo(newRequiredOutputFieldsList));
+            	    continue;
+            	}
+            	
+            	if (predecessor instanceof LOSplit)
+            	{
+            	    int outputIndex = mPlan.getSuccessors(predecessor).indexOf(rlo);
+            	    if (outputIndex==-1)
+            	    {
+            	        int errCode = 2186;
+                        String msg = "Cannot locate node from successor";
+                        throw new OptimizerException(msg, errCode, PigException.BUG);
+            	    }
+            	    if (requiredInputFieldsList.get(i)!=null)
+                    {
+            	        requiredInputFieldsList.get(i).reIndex(outputIndex);
+                    }
+            	    if (cachedRequiredInfo.containsKey(predecessor))
+            	        newRequiredOutputFieldsList = cachedRequiredInfo.get(predecessor).requiredFieldsList;
+        	        
+            	    while (newRequiredOutputFieldsList.size()<=outputIndex)
+            	        newRequiredOutputFieldsList.add(null);
+        	        newRequiredOutputFieldsList.set(outputIndex, requiredInputFieldsList.get(i));
+
+            	    cachedRequiredInfo.put(predecessor, new RequiredInfo(newRequiredOutputFieldsList));
+            	    continue;
+            	}
+            	processNode(predecessors.get(i), new RequiredInfo(newRequiredOutputFieldsList));
+            }
+        } catch (FrontendException e) {
+            int errCode = 2185;
+            String msg = "Unable to prune columns when processing node " + lo;
+            throw new OptimizerException(msg, errCode, PigException.BUG, e);
+        }
+    }
+    
+    // Get map keys in an inner plan of a particular input. 
+    private MapKeysInfo getMapKeysInPlan(LogicalPlan plan, int column) throws OptimizerException
+    {
+        // Determine if this foreach/cogroup plan can relate map keys from output columns to input columns.
+        // For criteria of this, see the comment of method isMapKeyRelayableInInnerPlan
+        // If this is true, the reference of the column here does not actually used by the logical operator:
+        // eg: B = foreach A generate a0;
+        //   We relay map key of a0 to B.$0. Appearance of a0 on its own here does not mean we need all map keys of a0
+        //   So once we see this situation, we stop collecting required map keys of this logical operator
+        if (isSimpleProjectCast(plan))
+            return null;
+        
+        boolean requireAll = false;
+        List<String> mapKeys = null;
+        TopLevelProjectFinder projectFinder = new TopLevelProjectFinder(plan);
+        try {
+            projectFinder.visit();
+        } catch (VisitorException ve) {
+            int errCode = 2200;
+            String msg = "Error getting top level project ";
+            throw new OptimizerException(msg, errCode, PigException.BUG, ve);
+        }
+        for (LOProject project : projectFinder.getProjectSet())
+        {
+            if (!project.isStar() && project.getCol()==column)  // LOProject for that column 
+            {
+                List<LogicalOperator> successors = plan.getSuccessors(project);
+                // If there are LOCast(s) in the middle (can only be cast to map, otherwise, there will not be maplookup below)
+                // it is fine, we can ignore LOCast and continue to look for LOMapLookup 
+                while (successors!=null && successors.size()==1 && successors.get(0) instanceof LOCast)
+                {
+                    LOCast cast = (LOCast)successors.get(0);
+                    successors = plan.getSuccessors(cast);
+                }
+                if (successors!=null && successors.size()==1 && successors.get(0) instanceof LOMapLookup)
+                {
+                    LOMapLookup loMapLookup = (LOMapLookup)successors.get(0);
+                    if (loMapLookup.getLookUpKey()!=null)
+                    {
+                        if (mapKeys==null)
+                            mapKeys = new ArrayList<String>();
+                        if (!mapKeys.contains(loMapLookup.getLookUpKey()))
+                            mapKeys.add(loMapLookup.getLookUpKey());
+                    }
+                    requireAll = false;
+                }
+                else
+                {
+                    requireAll = true;
+                }
+            }
+        }
+        return new MapKeysInfo(requireAll, mapKeys);
+    }
+    
+    // Figure if we need to relay output map keys to input map keys. It is used for inner plan for LOForEach
+    // and groupByPlan for LOCogroup
+    // There are several cases:
+    // 1. UDF, we cannot figure out how each input field is used in UDF, so for each input field,
+    //    we require everything
+    // 2. Map constant, which do not requires any data input
+    // 3. BinCond (B = foreach A generate a0==0?a1:a2; when a1, a2 is map)
+    //    This situation is complex. Two branches (a1, a2) is relayed independently, if it relays, then we cannot 
+    //    collect map keys of that branches as the required operator map keys.
+    //    However, it is unlikely that user will refer a map key of that output, we simply say we need all map keys of 
+    //    both map inputs
+    // 4. Cast (B = foreach A generate a0 as (map[]);)
+    //    The only cases we can cast a field to a map is the input field is a map already or the field is a byte array
+    //    If the input field is a byte array, then the input field do not have concept of map keys. So we do not need
+    //    to figure out the map key for this input. If the input field is a map, then this cast is just a 1 to 1 mapping.
+    //    It is case 5
+    // 5. 1 to 1 mapping (B = foreach A generate a0;)
+    // 6. Map resolution (B = foreach A generate a0#'key1' as b0)
+    //    Since we only trace one level map keys, so relay no key (since all the key in the following script refer to b0#'k'
+    //    actually refer to a0#'key1'#'k', we do not relay second level map key 'k'), but require 'key1' for a0
+    // 
+    // Based on the above observation, the algorithm to map output map keys to input map keys are:
+    // 1. If a output column map to multiple input column, then we do not relay this output
+    // 2. Find top level project for that plan, we collect map key only when we have only one input 
+    //    associate with it
+    // 3. Check if the predecessor of the project is null, if not, stop relaying input map keys
+    // 4. Check the successors of that project, if it is not a null or cast, stop relaying input map keys
+    // The qualifying logical plan should takes one project as root, optionally followed by one or more casts:
+    //
+    //      Project
+    //         |
+    //       Cast*
+    private boolean isSimpleProjectCast(LogicalPlan innerPlan) throws OptimizerException
+    {
+        TopLevelProjectFinder projectFinder = new TopLevelProjectFinder(innerPlan);
+        
+        try {
+            projectFinder.visit();
+        } catch (VisitorException ve) {
+            throw new OptimizerException();
+        }
+        boolean relayingMapKeys = false;
+        if (projectFinder.getProjectSet()!=null && projectFinder.getProjectSet().size()==1)
+        {
+            LOProject project = projectFinder.getProjectSet().iterator().next();
+            if (innerPlan.getPredecessors(project)==null)
+            {
+                relayingMapKeys = true;
+                LogicalOperator pred = project;
+                while (innerPlan.getSuccessors(pred)!=null)
+                {
+                    if (innerPlan.getSuccessors(pred).size()!=1)
+                        return false;
+                    if (!(innerPlan.getSuccessors(pred).get(0) instanceof LOCast))
+                    {
+                        return false;
+                    }
+                    pred = innerPlan.getSuccessors(pred).get(0);
+                }
+            }
+            if (relayingMapKeys)
+                return true;
+        }
+        return false;
+    }
+    
+    // Prune fields of LOLoad, and use ColumePruner to prune all the downstream logical operators
+    private void pruneLoader(LOLoad load, RequiredFields loaderRequiredFields) throws FrontendException
+    {
+        LoadFunc.RequiredFieldList requiredFieldList = new LoadFunc.RequiredFieldList(load.getAlias());
+        requiredFieldList.setAllFieldsRequired(false);
+
+        if (loaderRequiredFields==null || loaderRequiredFields.needAllFields())
+            return;
+        for (int i=0;i<loaderRequiredFields.size();i++)
+        {
+            Pair<Integer, Integer> pair = loaderRequiredFields.getField(i);
+            MapKeysInfo mapKeysInfo = loaderRequiredFields.getMapKeysInfo(i);
+            LoadFunc.RequiredField requiredField = new LoadFunc.RequiredField();
+            requiredField.setIndex(pair.second);
+            requiredField.setType(load.getSchema().getField(pair.second).type);
+            if (mapKeysInfo!=null && !mapKeysInfo.needAllKeys())
+            {
+                List<LoadFunc.RequiredField> subFieldList = new ArrayList<LoadFunc.RequiredField>();
+                for (String key : mapKeysInfo.getKeys())
+                {
+                    LoadFunc.RequiredField mapKeyField = new LoadFunc.RequiredField();
+                    mapKeyField.setIndex(-1);
+                    mapKeyField.setType(DataType.UNKNOWN);
+                    mapKeyField.setAlias(key);
+                    subFieldList.add(mapKeyField);
+                }
+                requiredField.setSubFields(subFieldList);
+            }
+            // Sort requiredFieldList, loader expect required field list sorted by index
+            int j=0;
+            while (requiredFieldList.getFields().size()>j && requiredFieldList.getFields().get(j).getIndex()<pair.second)
+                j++;
+            requiredFieldList.getFields().add(j, requiredField);
+        }
+        
+        boolean[] columnRequired = new boolean[load.getSchema().size()];
+        LoadFunc.RequiredFieldResponse response = null;
+        try {
+            response = load.fieldsToRead(requiredFieldList);
+        } catch (FrontendException e) {
+            log.warn("fieldsToRead on "+load+" throw an exception, skip it");
+        }
+        
+        // If the request is not granted, probably the loader support position prune only,
+        // and do not prune map key pruning (such as PigStorage). Drop all map keys (means 
+        // we do not prune map keys) and try again
+        if (response==null || !response.getRequiredFieldResponse())
+        {
+            for (LoadFunc.RequiredField rf : requiredFieldList.getFields())
+            {
+                if (rf.getType() == DataType.MAP)
+                    rf.setSubFields(null);
+            }
+            try {
+                response = load.fieldsToRead(requiredFieldList);
+            } catch (FrontendException e) {
+                log.warn("fieldsToRead on "+load+" throw an exception, skip it");
+            }
+        }
+        
+        // Loader does not support column pruning, insert foreach
+        if (response==null || !response.getRequiredFieldResponse())
+        {
+            Set<Integer> columnsToProject = new TreeSet<Integer>();
+            for (LoadFunc.RequiredField rf : requiredFieldList.getFields())
+                columnsToProject.add(rf.getIndex());
+            
+            ArrayList<Boolean> flattenList = new ArrayList<Boolean>();
+            ArrayList<LogicalPlan> generatePlans = new ArrayList<LogicalPlan>();
+            String scope = load.getOperatorKey().scope;
+            for (int pos : columnsToProject) {
+                LogicalPlan projectPlan = new LogicalPlan();
+                LogicalOperator projectInput = load;
+                ExpressionOperator column = new LOProject(projectPlan, new OperatorKey(scope, NodeIdGenerator.getGenerator().getNextNodeId(scope)), projectInput, pos);
+                flattenList.add(false);
+                projectPlan.add(column);
+                generatePlans.add(projectPlan);
+            }
+            LOForEach forEach = new LOForEach(mPlan, new OperatorKey(scope, NodeIdGenerator.getGenerator().getNextNodeId(scope)), generatePlans, flattenList);
+            LogicalOperator pred = mPlan.getSuccessors(load).get(0);
+            mPlan.add(forEach);
+            mPlan.insertBetween(load, forEach, pred);
+            String message = "Cannot prune " + load.getAlias() + ", " + load.getLoadFunc().getClass().getSimpleName() + " does not support pruning, add foreach";
+            log.info(message);
+        }
+        
+        // We get positive response, begin to prune
+        if (response!=null && response.getRequiredFieldResponse())
+        {
+            for (Pair<Integer, Integer> pair: loaderRequiredFields.getFields())
+                columnRequired[pair.second] = true;
+            
+            List<Pair<Integer, Integer>> pruneList = new ArrayList<Pair<Integer, Integer>>();
+            for (int i=0;i<columnRequired.length;i++)
+            {
+                if (!columnRequired[i])
+                    pruneList.add(new Pair<Integer, Integer>(0, i));
+            }
+
+            StringBuffer message = new StringBuffer();
+            if (pruneList.size()!=0)
+            {
+                ColumnPruner columnPruner = new ColumnPruner(mPlan, load, pruneList, 
+                        new DependencyOrderWalker<LogicalOperator, LogicalPlan>(mPlan));
+                
+                columnPruner.visit();
+
+                message.append("Columns pruned for " + load.getAlias() + ": ");
+                for (int i=0;i<pruneList.size();i++)
+                {
+                    message.append("$"+pruneList.get(i).second);
+                    if (i!=pruneList.size()-1)
+                        message.append(", ");
+                }
+                log.info(message);
+            }
+            else
+                log.info("No column pruned for " + load.getAlias());
+            message = new StringBuffer();;
+            for (LoadFunc.RequiredField rf : requiredFieldList.getFields())
+            {
+                if (rf.getSubFields()!=null)
+                {
+                    message.append("Map key required for " + load.getAlias()+": ");
+                    if (rf.getIndex()!=-1)
+                        message.append("$"+rf.getIndex());
+                    else
+                        message.append(rf.getAlias());
+                    message.append("->[");
+                    for (int i=0;i<rf.getSubFields().size();i++)
+                    {
+                        LoadFunc.RequiredField keyrf = rf.getSubFields().get(i);
+                        message.append(keyrf);
+                        if (i!=rf.getSubFields().size()-1)
+                            message.append(",");
+                    }
+                    message.append("] ");
+                }
+            }
+            if (message.length()!=0)
+                log.info(message);
+            else
+                log.info("No map keys pruned for " + load.getAlias());
+        }
+    }
+}

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushDownForeachFlatten.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushDownForeachFlatten.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushDownForeachFlatten.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushDownForeachFlatten.java Fri Dec  4 00:25:57 2009
@@ -63,7 +63,7 @@
     Map<Integer, Integer> mFlattenedColumnReMap = null;
 
     public PushDownForeachFlatten(LogicalPlan plan) {
-        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+        super(plan);
     }
 
     /**

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushUpFilter.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushUpFilter.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushUpFilter.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/PushUpFilter.java Fri Dec  4 00:25:57 2009
@@ -72,7 +72,7 @@
     private int mPushBeforeInput = -1;
 
     public PushUpFilter(LogicalPlan plan) {
-        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+        super(plan);
     }
 
     /**

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/StreamOptimizer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/StreamOptimizer.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/StreamOptimizer.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/StreamOptimizer.java Fri Dec  4 00:25:57 2009
@@ -59,7 +59,7 @@
     private boolean mOptimizeStore = false;
 
     public StreamOptimizer(LogicalPlan plan, String operatorClassName) {
-        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+        super(plan);
     }
 
     @Override

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/TypeCastInserter.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/TypeCastInserter.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/TypeCastInserter.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/logicalLayer/optimizer/TypeCastInserter.java Fri Dec  4 00:25:57 2009
@@ -55,7 +55,7 @@
     private String operatorClassName;
 
     public TypeCastInserter(LogicalPlan plan, String operatorClassName) {
-        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+        super(plan);
         this.operatorClassName = operatorClassName;
     }
 

Added: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/MapKeysInfo.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/MapKeysInfo.java?rev=887013&view=auto
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/MapKeysInfo.java (added)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/MapKeysInfo.java Fri Dec  4 00:25:57 2009
@@ -0,0 +1,66 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *     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 org.apache.pig.impl.plan;
+
+import java.util.List;
+
+public class MapKeysInfo {
+    List<String> keys;
+    boolean needAllKeys;
+    public MapKeysInfo() {
+        needAllKeys = false;
+        keys = null;
+    }
+    public MapKeysInfo(List<String> keys) {
+        needAllKeys = false;
+        this.keys = keys;
+    }
+    public MapKeysInfo(boolean needAllKeys) {
+        this.needAllKeys = needAllKeys;
+        this.keys = null;
+    }
+    public MapKeysInfo(boolean needAllKeys, List<String> keys) {
+        this.needAllKeys = needAllKeys;
+        this.keys = keys;
+    }
+    public List<String> getKeys()
+    {
+        return keys;
+    }
+    public boolean needAllKeys()
+    {
+        return needAllKeys;
+    }
+    public String toString()
+    {
+        if (needAllKeys)
+            return "Need all keys";
+        if (keys==null)
+            return "Empty";
+        StringBuffer result = new StringBuffer();
+        result.append("[");
+        for (int i=0;i<keys.size();i++)
+        {
+            result.append(keys.get(i));
+            if (i!=keys.size()-1)
+                result.append(",");
+        }
+        result.append("]");
+        return result.toString();
+    }
+}

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/OperatorPlan.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/OperatorPlan.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/OperatorPlan.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/OperatorPlan.java Fri Dec  4 00:25:57 2009
@@ -487,7 +487,7 @@
      * Private method to perform the insertBetween operation with the ability to turn off
      * rewiring operation.
      */
-    private void doInsertBetween(
+    public void doInsertBetween(
             E after,
             E newNode,
             E before,

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/RequiredFields.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/RequiredFields.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/RequiredFields.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/RequiredFields.java Fri Dec  4 00:25:57 2009
@@ -28,6 +28,7 @@
  * A struct detailing how a projection is altered by an operator.
  */
 public class RequiredFields {
+    
     /**
      * Quick way for an operator to note that all columns from an input are required.
      */
@@ -46,6 +47,11 @@
      * (0, 2), (0, 3), (0, 1). Note that the order is not guaranteed.
      */
     private List<Pair<Integer, Integer>> mFields;
+    
+    /*
+     * Required map keys information
+     */
+    private List<MapKeysInfo> mMapKeysInfoList;
 
     /**
      * 
@@ -87,10 +93,10 @@
      *            to indicate if this required fields needs no fields from
      *            its input; cannot be true if needAllFields is true
      */
-    private RequiredFields(List<Pair<Integer, Integer>> removedFields,
+    private RequiredFields(List<Pair<Integer, Integer>> fields,
             boolean needAllFields,
             boolean needNoFields) {
-        mFields = removedFields;
+        mFields = fields;
         if(needAllFields && needNoFields) {
             //both cannot be true
             //set both of them to false
@@ -100,6 +106,12 @@
             mNeedAllFields = needAllFields;
             mNeedNoFields = needNoFields;
         }
+        if (mFields!=null)
+        {
+            mMapKeysInfoList = new ArrayList<MapKeysInfo>();
+            for (int i=0;i<mFields.size();i++)
+                mMapKeysInfoList.add(null);
+        }
     }
 
     /**
@@ -109,6 +121,25 @@
     public List<Pair<Integer, Integer>> getFields() {
         return mFields;
     }
+    
+    /**
+     * @param i
+     *         the index of the required field
+     * @return the ith required input column
+     */
+    public Pair<Integer, Integer> getField(int i) {
+        return mFields.get(i);
+    }
+    
+    /**
+     * 
+     * @return the size of required input columns
+     */
+    public int size() {
+        if (mFields==null)
+            return 0;
+        return mFields.size();
+    }
 
     /**
      * 
@@ -117,6 +148,12 @@
      */
     public void setFields(List<Pair<Integer, Integer>> fields) {
         mFields = fields;
+        if (mFields!=null)
+        {
+            mMapKeysInfoList = new ArrayList<MapKeysInfo>();
+            for (int i=0;i<mFields.size();i++)
+                mMapKeysInfoList.add(null);
+        }
     }
 
     /**
@@ -184,4 +221,175 @@
         return sb.toString();
     }
 
+    /**
+     * Merge with RequiredFields r2. Merge both required fields and required map keys 
+     * @param r2
+     *            Required fields to merge
+     */
+    public void merge(RequiredFields r2) {
+        if (r2 == null)
+            return;
+        if (getNeedAllFields())
+            return;
+        if (r2.getNeedAllFields()) {
+            mNeedAllFields = true;
+            return;
+        }
+        if (getNeedNoFields() && !r2.getNeedNoFields()) {
+            mNeedNoFields = false;
+        }
+        if (r2.getFields() == null)
+            return;
+        for (int i=0;i<r2.size();i++) {
+            Pair<Integer, Integer> f = r2.getField(i);
+            MapKeysInfo m = r2.getMapKeysInfo(i);
+            if (mFields == null)
+            {
+                mFields = new ArrayList<Pair<Integer, Integer>>();
+                mMapKeysInfoList = new ArrayList<MapKeysInfo>();
+            }
+            if (!mFields.contains(f)) {
+                mFields.add(f);
+                mMapKeysInfoList.add(m);
+                mNeedNoFields = false;
+            }
+            else
+            {
+                if (m!=null)
+                {
+                    int index = mFields.indexOf(new Pair<Integer, Integer>(f.first, f.second));
+                    MapKeysInfo mapKeys = mMapKeysInfoList.get(index);
+                    if (mapKeys == null)
+                        mapKeys = new MapKeysInfo();
+                    if (m.needAllKeys)
+                    {
+                        mapKeys.needAllKeys = true;
+                        mapKeys.keys = null;
+                    }
+                    else if (mapKeys.keys!=null)
+                    {
+                        if (m.keys!=null)
+                            mapKeys.keys.addAll(m.keys);
+                    }
+                    else
+                    {
+                        mapKeys.keys = m.keys;
+                    }
+                    mMapKeysInfoList.set(index, mapKeys);
+                }
+            }
+        }
+        return;
+    }
+    
+    /**
+     * Set the index of all fields to i  
+     * @param i
+     *            New index to set
+     */
+    public void reIndex(int i)
+    {
+        if (mFields!=null)
+        {
+            for (Pair<Integer, Integer> p:mFields)
+            {
+                p.first = i;
+            }
+        }
+    }
+    
+    /**
+     * Merge another map key into existing required map keys list
+     * @param input
+     *            The input of the field to merge
+     * @param column
+     *            The column of the field to merge
+     * @param key
+     *            The key to merge
+     */
+    public void mergeMapKey(int input, int column, String key)
+    {
+        int index = mFields.indexOf(new Pair<Integer, Integer>(input, column));
+        if (index==-1)
+            return;
+        if (mMapKeysInfoList.get(index)==null)
+            mMapKeysInfoList.set(index, new MapKeysInfo());
+        MapKeysInfo keysInfo = mMapKeysInfoList.get(index);
+        if (keysInfo.needAllKeys)
+            return;
+        if (!keysInfo.keys.contains(key))
+            keysInfo.keys.add(key);
+    }
+    
+    /**
+     * Merge a MapKeysInfo structure to existing required map keys list
+     * @param input
+     *            The input of the field to merge
+     * @param column
+     *            The column of the field to merge
+     * @param mapKeysInfo
+     *            The MapKeysInfo structure to merge
+     */
+    public void mergeMapKeysInfo(int input, int column, MapKeysInfo mapKeysInfo)
+    {
+        if (mapKeysInfo == null)
+            return;
+        int index = mFields.indexOf(new Pair<Integer, Integer>(input, column));
+        if (index==-1)
+            return;
+        if (mMapKeysInfoList.get(index)==null)
+        {
+            mMapKeysInfoList.set(index, mapKeysInfo);
+            return;
+        }
+        if (mapKeysInfo.needAllKeys)
+        {
+            mMapKeysInfoList.get(index).needAllKeys = true;
+            mMapKeysInfoList.get(index).keys = null;
+        }
+        if (mapKeysInfo.keys!=null)
+        {
+            for (String key : mapKeysInfo.keys)
+                mergeMapKey(input, column, key);
+        }
+    }
+    
+    /**
+     * Set a MapKeysInfo structure to the required map keys list
+     * @param input
+     *            The input of the field to set
+     * @param column
+     *            The column of the field to set
+     * @param mapKeysInfo
+     *            The MapKeysInfo structure to set
+     */
+    public void setMapKeysInfo(int input, int column, MapKeysInfo mapKeysInfo)
+    {
+        int index = mFields.indexOf(new Pair<Integer, Integer>(input, column));
+        if (index==-1)
+            return;
+        mMapKeysInfoList.set(index, mapKeysInfo);
+    }
+    
+    /**
+     * Get the ith MapKeysInfo structure 
+     * @param i
+     *            The index of the MapKeysInfo, the index of MapKeysInfo is synchronized with mFields
+     */
+    public MapKeysInfo getMapKeysInfo(int i)
+    {
+        return mMapKeysInfoList.get(i);
+    }
+
+    /**
+     * Set the ith MapKeysInfo structure 
+     * @param i
+     *            The index of the MapKeysInfo, the index of MapKeysInfo is synchronized with mFields
+     * @param mapKeysInfo
+     *            The MapKeysInfo to set
+     */
+    public void setMapKeysInfo(int i, MapKeysInfo mapKeysInfo)
+    {
+        mMapKeysInfoList.set(i, mapKeysInfo);
+    }
 }
\ No newline at end of file

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Rule.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Rule.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Rule.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Rule.java Fri Dec  4 00:25:57 2009
@@ -33,7 +33,7 @@
 public class Rule<O extends Operator, P extends OperatorPlan<O>> {
 
     public enum WalkerAlgo {
-        DepthFirstWalker, DependencyOrderWalker
+        DepthFirstWalker, DependencyOrderWalker, ReverseDependencyOrderWalker
     };
 
     private RulePlan mRulePlan;

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java Fri Dec  4 00:25:57 2009
@@ -74,11 +74,50 @@
         if (mRule.getWalkerAlgo() == Rule.WalkerAlgo.DependencyOrderWalker)
         	DependencyOrderWalker();
         else if (mRule.getWalkerAlgo() == Rule.WalkerAlgo.DepthFirstWalker)
-        	DepthFirstWalker();        
+        	DepthFirstWalker();
+        else if (mRule.getWalkerAlgo() == Rule.WalkerAlgo.ReverseDependencyOrderWalker)
+            ReverseDependencyOrderWalker();
         
         return (mMatches.size()!=0);
     }
     
+    private void ReverseDependencyOrderWalker()
+    {
+        List<O> fifo = new ArrayList<O>();
+        Set<O> seen = new HashSet<O>();
+        List<O> roots = mPlan.getRoots();
+        if (roots == null) return;
+        for (O op : roots) {
+            RDODoAllSuccessors(op, seen, fifo);
+        }
+
+        for (O op: fifo) {
+            if (beginMatch(op))
+            mPrelimMatches.add(mMatch);
+        }
+        
+        if(mPrelimMatches.size() > 0) {
+            processPreliminaryMatches();
+        }
+    }
+        
+    private void RDODoAllSuccessors(O node, Set<O> seen, Collection<O> fifo)
+    {
+        if (!seen.contains(node)) {
+        // We haven't seen this one before.
+             Collection<O> succs = mPlan.getSuccessors(node);
+             if (succs != null && succs.size() > 0) {
+                 // Do all our successors before ourself
+                 for (O op : succs) {
+                     RDODoAllSuccessors(op, seen, fifo);
+                 }
+             }
+             // Now do ourself
+             seen.add(node);
+             fifo.add(node);
+         }
+    }
+    
     private void DependencyOrderWalker()
     {
         List<O> fifo = new ArrayList<O>();

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Transformer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Transformer.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Transformer.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/plan/optimizer/Transformer.java Fri Dec  4 00:25:57 2009
@@ -29,13 +29,14 @@
  * apply to a graph.  This class is a special case of a PlanVisitor,so it
  * can navigate the plan.
  */
-public abstract class Transformer<O extends Operator, P extends OperatorPlan<O>> extends PlanVisitor<O, P> {
+public abstract class Transformer<O extends Operator, P extends OperatorPlan<O>> {
 
+    protected P mPlan;
     /**
      * @param plan OperatorPlan to be optimized.
      */
-    protected Transformer(P plan, PlanWalker<O, P> walker) {
-        super(plan, walker);
+    protected Transformer(P plan) {
+        mPlan = plan;
     }
 
     /**
@@ -67,6 +68,11 @@
      * @throws OptimizerException
      */
     public abstract void reset() throws OptimizerException;
+    
+    public P getPlan()
+    {
+        return mPlan;
+    }
 
 }
 

Modified: hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/util/UDFContext.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/util/UDFContext.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/util/UDFContext.java (original)
+++ hadoop/pig/branches/branch-0.6/src/org/apache/pig/impl/util/UDFContext.java Fri Dec  4 00:25:57 2009
@@ -175,4 +175,7 @@
         return hc;
     }
     
+    public void reset() {
+        udfConfs.clear();
+    }
 }
\ No newline at end of file

Modified: hadoop/pig/branches/branch-0.6/test/org/apache/pig/test/RangeSlicer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/branches/branch-0.6/test/org/apache/pig/test/RangeSlicer.java?rev=887013&r1=887012&r2=887013&view=diff
==============================================================================
--- hadoop/pig/branches/branch-0.6/test/org/apache/pig/test/RangeSlicer.java (original)
+++ hadoop/pig/branches/branch-0.6/test/org/apache/pig/test/RangeSlicer.java Fri Dec  4 00:25:57 2009
@@ -26,11 +26,13 @@
 import org.apache.pig.LoadFunc;
 import org.apache.pig.Slice;
 import org.apache.pig.Slicer;
+import org.apache.pig.LoadFunc.RequiredFieldList;
 import org.apache.pig.backend.datastorage.DataStorage;
 import org.apache.pig.data.DataBag;
 import org.apache.pig.data.Tuple;
 import org.apache.pig.data.TupleFactory;
 import org.apache.pig.impl.io.BufferedPositionedInputStream;
+import org.apache.pig.impl.logicalLayer.FrontendException;
 import org.apache.pig.impl.logicalLayer.schema.Schema;
 
 /**
@@ -206,8 +208,9 @@
     /* (non-Javadoc)
      * @see org.apache.pig.LoadFunc#fieldsToRead(org.apache.pig.impl.logicalLayer.schema.Schema)
      */
-    public void fieldsToRead(Schema schema) {
-        
+    @Override
+    public LoadFunc.RequiredFieldResponse fieldsToRead(RequiredFieldList requiredFieldList) throws FrontendException {
+        return new LoadFunc.RequiredFieldResponse(false);
     }
 
     /* (non-Javadoc)