You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pig.apache.org by ga...@apache.org on 2008/07/25 05:20:07 UTC

svn commit: r679651 - in /incubator/pig/branches/types: src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/ src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/ src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/p...

Author: gates
Date: Thu Jul 24 20:20:06 2008
New Revision: 679651

URL: http://svn.apache.org/viewvc?rev=679651&view=rev
Log:
PIG-171 Daniel's limit patch.  Thanks Daniel for all your hard work on this.


Added:
    incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POLimit.java
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOLimit.java
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java
    incubator/pig/branches/types/test/org/apache/pig/test/OpLimitOptimizerPrinter.java
    incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan1.dot
    incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan2.dot
    incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan3.dot
    incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan4.dot
    incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan5.dot
    incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan6.dot
    incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/Limit.gld
    incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/LimitedSort.gld
    incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/MRC17.gld
Modified:
    incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java
    incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java
    incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java
    incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSort.java
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOSort.java
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOVisitor.java
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/QueryParser.jjt
    incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/grammar
    incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/PlanOptimizer.java
    incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/Rule.java
    incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java
    incubator/pig/branches/types/test/org/apache/pig/test/TestEvalPipeline.java
    incubator/pig/branches/types/test/org/apache/pig/test/TestLogToPhyCompiler.java
    incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalOptimizer.java
    incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalPlanBuilder.java
    incubator/pig/branches/types/test/org/apache/pig/test/TestMRCompiler.java
    incubator/pig/branches/types/test/org/apache/pig/test/utils/GenPhyOp.java

Modified: incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java Thu Jul 24 20:20:06 2008
@@ -51,6 +51,7 @@
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.PODistinct;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POFilter;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POGlobalRearrange;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLimit;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLoad;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLocalRearrange;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POPackage;
@@ -617,6 +618,80 @@
         }
     }
     
+    public void visitLimit(POLimit op) throws VisitorException{
+        try{
+        	
+            MapReduceOper mro = compiledInputs[0];
+            if (!mro.isMapDone()) {
+            	// if map plan is open, add a limit for optimization, eventually we
+            	// will add another limit to reduce plan
+                mro.mapPlan.addAsLeaf(op);
+                mro.setMapDone(true);
+                
+                if (mro.reducePlan.isEmpty())
+                {
+                	PhysicalPlan ep = new PhysicalPlan();
+                    POProject prjStar = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+                    prjStar.setResultType(DataType.TUPLE);
+                    prjStar.setStar(true);
+                    ep.add(prjStar);
+                    
+                    List<PhysicalPlan> eps = new ArrayList<PhysicalPlan>();
+                    eps.add(ep);
+                    
+                    POLocalRearrange lr = new POLocalRearrange(new OperatorKey(scope,nig.getNextNodeId(scope)));
+                    lr.setIndex(0);
+                    lr.setKeyType(DataType.TUPLE);
+                    lr.setPlans(eps);
+                    lr.setResultType(DataType.TUPLE);
+                    mro.mapPlan.addAsLeaf(lr);
+                    
+                	POPackage pkg = new POPackage(new OperatorKey(scope,nig.getNextNodeId(scope)));
+                    pkg.setKeyType(DataType.TUPLE);
+                    pkg.setNumInps(1);
+                    boolean[] inner = {false};
+                    pkg.setInner(inner);
+                    mro.reducePlan.add(pkg);
+                    
+                    POLimit pLimit2 = new POLimit(new OperatorKey(scope,nig.getNextNodeId(scope)));
+        	    	pLimit2.setLimit(op.getLimit());
+                    mro.reducePlan.addAsLeaf(pLimit2);
+                    
+                    List<PhysicalPlan> eps1 = new ArrayList<PhysicalPlan>();
+                    List<Boolean> flat1 = new ArrayList<Boolean>();
+                    PhysicalPlan ep1 = new PhysicalPlan();
+                    POProject prj1 = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+                    prj1.setResultType(DataType.TUPLE);
+                    prj1.setStar(false);
+                    prj1.setColumn(0);
+                    prj1.setOverloaded(false);
+                    ep1.add(prj1);
+                    eps1.add(ep1);
+                    flat1.add(false);
+                    POForEach nfe1 = new POForEach(new OperatorKey(scope, nig
+                            .getNextNodeId(scope)), op.getRequestedParallelism(), eps1,
+                            flat1);
+                    nfe1.setResultType(DataType.BAG);
+                    curMROp.reducePlan.addAsLeaf(nfe1);
+                }
+                else
+                {
+                	log.warn("Something in the reduce plan while map plan is not done. Something wrong!");
+                }
+            } else if (mro.isMapDone() && !mro.isReduceDone()) {
+            	// limit should add into reduce reduce function
+                mro.reducePlan.addAsLeaf(op);
+            } else {
+                log.warn("Both map and reduce phases have been done. This is unexpected while compiling!");
+            }
+            curMROp = mro;
+        }catch(Exception e){
+            VisitorException pe = new VisitorException(e.getMessage());
+            pe.initCause(e);
+            throw pe;
+        }
+    }
+
     public void visitLocalRearrange(POLocalRearrange op) throws VisitorException {
         try{
             nonBlocking(op);
@@ -744,7 +819,7 @@
             int rp = op.getRequestedParallelism();
             int[] fields = getSortCols(op);
             MapReduceOper quant = getQuantileJob(op, mro, fSpec, quantFile, rp, fields);
-            curMROp = getSortJob(quant, fSpec, quantFile, rp, fields);
+            curMROp = getSortJob(quant, fSpec, quantFile, rp, fields, op.getLimit());
             if(op.isUDFComparatorUsed){
                 curMROp.UDFs.add(op.getMSortFunc().getFuncSpec().toString());
             }
@@ -775,7 +850,8 @@
             FileSpec lFile,
             FileSpec quantFile,
             int rp,
-            int[] fields) throws PlanException{
+            int[] fields,
+            long limit) throws PlanException{
         MapReduceOper mro = startNew(lFile, quantJob);
         mro.setQuantFile(quantFile.getFileName());
         mro.setGlobalSort(true);
@@ -814,6 +890,55 @@
         
         mro.setMapDone(true);
         
+        if (limit!=-1)
+        {
+        	POPackage pkg_c = new POPackage(new OperatorKey(scope,nig.getNextNodeId(scope)));
+        	pkg_c.setKeyType((fields.length>1) ? DataType.TUPLE : DataType.BYTEARRAY);
+            pkg_c.setNumInps(1);
+            //pkg.setResultType(DataType.TUPLE);
+            boolean[] inner = {false};
+            pkg_c.setInner(inner);
+            mro.combinePlan.add(pkg_c);
+        	
+            List<PhysicalPlan> eps_c1 = new ArrayList<PhysicalPlan>();
+            List<Boolean> flat_c1 = new ArrayList<Boolean>();
+            PhysicalPlan ep_c1 = new PhysicalPlan();
+            POProject prj_c1 = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+            prj_c1.setColumn(1);
+            prj_c1.setOverloaded(false);
+            prj_c1.setResultType(DataType.BAG);
+            ep_c1.add(prj_c1);
+            eps_c1.add(ep_c1);
+            flat_c1.add(true);
+            POForEach fe_c1 = new POForEach(new OperatorKey(scope,nig.getNextNodeId(scope)), 
+            		-1, eps_c1, flat_c1);
+            fe_c1.setResultType(DataType.TUPLE);
+            mro.combinePlan.addAsLeaf(fe_c1);
+            
+            
+            POLimit pLimit = new POLimit(new OperatorKey(scope,nig.getNextNodeId(scope)));
+        	pLimit.setLimit(limit);
+        	mro.combinePlan.addAsLeaf(pLimit);
+            
+            List<PhysicalPlan> eps_c2 = new ArrayList<PhysicalPlan>();
+            for (int i : fields) {
+	            PhysicalPlan ep_c2 = new PhysicalPlan();
+	            POProject prj_c2 = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+	            prj_c2.setColumn(i);
+	            prj_c2.setOverloaded(false);
+	            prj_c2.setResultType(DataType.BYTEARRAY);
+	            ep_c2.add(prj_c2);
+	            eps_c2.add(ep_c2);
+	        }
+        
+	        POLocalRearrange lr_c2 = new POLocalRearrange(new OperatorKey(scope,nig.getNextNodeId(scope)));
+	        lr_c2.setIndex(0);
+	        lr_c2.setKeyType((fields.length>1) ? DataType.TUPLE : DataType.BYTEARRAY);
+	        lr_c2.setPlans(eps_c2);
+	        lr_c2.setResultType(DataType.TUPLE);
+	        mro.combinePlan.addAsLeaf(lr_c2);
+        }
+        
         POPackage pkg = new POPackage(new OperatorKey(scope,nig.getNextNodeId(scope)));
         pkg.setKeyType((fields == null || fields.length>1) ? DataType.TUPLE : DataType.BYTEARRAY);
         pkg.setNumInps(1);
@@ -834,6 +959,14 @@
         POForEach nfe1 = new POForEach(new OperatorKey(scope,nig.getNextNodeId(scope)),-1,eps2,flattened);
         mro.reducePlan.add(nfe1);
         mro.reducePlan.connect(pkg, nfe1);
+        
+        if (limit!=-1)
+        {
+	        POLimit pLimit2 = new POLimit(new OperatorKey(scope,nig.getNextNodeId(scope)));
+	    	pLimit2.setLimit(limit);
+	    	mro.reducePlan.addAsLeaf(pLimit2);
+        }
+
 //        ep1.add(innGen);
         return mro;
     }

Modified: incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java Thu Jul 24 20:20:06 2008
@@ -714,6 +714,7 @@
                     .getNextNodeId(scope)), s.getRequestedParallelism(), null,
                     sortPlans, s.getAscendingCols(), comparator);
         }
+        sort.setLimit(s.getLimit());
         // sort.setRequestedParallelism(s.getType());
         LogToPhyMap.put(s, sort);
         currentPlan.add(sort);
@@ -993,6 +994,24 @@
         }
 
     }
+    @Override
+    public void visit(LOLimit limit) throws VisitorException {
+            String scope = limit.getOperatorKey().scope;
+            POLimit poLimit = new POLimit(new OperatorKey(scope, nodeGen.getNextNodeId(scope)), limit.getRequestedParallelism());
+            poLimit.setResultType(limit.getType());
+            poLimit.setLimit(limit.getLimit());
+            currentPlan.add(poLimit);
+            LogToPhyMap.put(limit, poLimit);
+
+            List<LogicalOperator> op = limit.getPlan().getPredecessors(limit);
+
+            PhysicalOperator from = LogToPhyMap.get(op.get(0));
+            try {
+                    currentPlan.connect(from, poLimit);
+            } catch (PlanException e) {
+                    log.error("Invalid physical operators in the physical plan" + e.getMessage());
+            }
+    }
 
     @Override
     public void visit(LOUnion op) throws VisitorException {

Modified: incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java Thu Jul 24 20:20:06 2008
@@ -47,6 +47,7 @@
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.PODistinct;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POFilter;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POGlobalRearrange;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLimit;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLoad;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLocalRearrange;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POPackage;
@@ -235,4 +236,9 @@
         // TODO Auto-generated method stub
         
     }
+    
+    public void visitLimit(POLimit lim) throws VisitorException{
+        //do nothing
+    }
+
 }

Added: incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POLimit.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POLimit.java?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POLimit.java (added)
+++ incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POLimit.java Thu Jul 24 20:20:06 2008
@@ -0,0 +1,101 @@
+package org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators;
+
+import java.util.List;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.pig.backend.executionengine.ExecException;
+import org.apache.pig.data.DataType;
+import org.apache.pig.data.Tuple;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.POStatus;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.PhysicalOperator;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.Result;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.expressionOperators.ComparisonOperator;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.plans.PhyPlanVisitor;
+import org.apache.pig.impl.plan.OperatorKey;
+import org.apache.pig.impl.plan.VisitorException;
+
+public class POLimit extends PhysicalOperator {
+	   /**
+     * 
+     */
+    private static final long serialVersionUID = 1L;
+
+    private Log log = LogFactory.getLog(getClass());
+
+    // Counts for outputs processed
+    private long soFar = 0;
+    
+    // Number of limited outputs
+    long mLimit;
+
+    public POLimit(OperatorKey k) {
+        this(k, -1, null);
+    }
+
+    public POLimit(OperatorKey k, int rp) {
+        this(k, rp, null);
+    }
+
+    public POLimit(OperatorKey k, List<PhysicalOperator> inputs) {
+        this(k, -1, inputs);
+    }
+
+    public POLimit(OperatorKey k, int rp, List<PhysicalOperator> inputs) {
+        super(k, rp, inputs);
+    }
+    
+    public void setLimit(long limit)
+    {
+    	mLimit = limit;
+    }
+    
+    public long getLimit()
+    {
+    	return mLimit;
+    }
+
+    /**
+     * Counts the number of tuples processed into static variable soFar, if the number of tuples processed reach the 
+     * limit, return EOP; Otherwise, return the tuple 
+     */
+    @Override
+    public Result getNext(Tuple t) throws ExecException {
+        Result res = null;
+        Result inp = null;
+        while (true) {
+            inp = processInput();
+            if (inp.returnStatus == POStatus.STATUS_EOP
+                    || inp.returnStatus == POStatus.STATUS_ERR)
+                break;
+            
+            if (soFar>=mLimit)
+            	inp.returnStatus = POStatus.STATUS_EOP;
+            
+            soFar++;
+            break;
+        }
+
+        return inp;
+    }
+
+    @Override
+    public String name() {
+        return "Limit - " + mKey.toString();
+    }
+
+    @Override
+    public boolean supportsMultipleInputs() {
+        return false;
+    }
+
+    @Override
+    public boolean supportsMultipleOutputs() {
+        return false;
+    }
+
+    @Override
+    public void visit(PhyPlanVisitor v) throws VisitorException {
+        v.visitLimit(this);
+    }
+}

Modified: incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSort.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSort.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSort.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSort.java Thu Jul 24 20:20:06 2008
@@ -69,6 +69,7 @@
 	private Comparator<Tuple> mComparator;
 
 	private boolean inputsAccumulated = false;
+	private long limit;
 	public boolean isUDFComparatorUsed = false;
 	private DataBag sortedBag;
 	transient Iterator<Tuple> it;
@@ -79,6 +80,7 @@
 		//this.mSortCols = mSortCols;
 		this.sortPlans = sortPlans;
 		this.mAscCols = mAscCols;
+        this.limit = -1;
 		this.mSortFunc = mSortFunc;
 		if (mSortFunc == null) {
             mComparator = new SortComparator();
@@ -311,5 +313,20 @@
     public List<Boolean> getMAscCols() {
         return mAscCols;
     }
+    
+    public void setLimit(long l)
+    {
+    	limit = l;
+    }
+    
+    public long getLimit()
+    {
+    	return limit;
+    }
+    
+    public boolean isLimited()
+    {
+    	return (limit!=-1);
+    }
 
 }

Added: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOLimit.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOLimit.java?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOLimit.java (added)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOLimit.java Thu Jul 24 20:20:06 2008
@@ -0,0 +1,88 @@
+package org.apache.pig.impl.logicalLayer;
+
+import org.apache.pig.data.DataType;
+import org.apache.pig.impl.logicalLayer.parser.QueryParser;
+import org.apache.pig.impl.logicalLayer.schema.Schema;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLimit;
+import org.apache.pig.impl.plan.OperatorKey;
+import org.apache.pig.impl.plan.VisitorException;
+
+public class LOLimit extends LogicalOperator {
+    private static final long serialVersionUID = 2L;
+    private LogicalOperator mInput;
+    private long mLimit;
+    /**
+     * 
+     * @param plan
+     *            Logical plan this operator is a part of.
+     * @param k
+     *            Operator key to assign to this node.
+     * @param limit
+     *            Number of limited outputs
+     * @param input
+     *            the input that needs to limit
+     */
+
+    public LOLimit(LogicalPlan plan, OperatorKey k,
+            long limit, LogicalOperator input) {
+        super(plan, k);
+        mLimit = limit;
+        mInput = input;
+    }
+
+    public LogicalOperator getInput() {
+        return mInput;
+    }
+
+    public long getLimit() {
+        return mLimit;
+    }
+
+    public void setLimit(long limit) {
+    	mLimit = limit;
+    }
+    @Override
+    public Schema getSchema() throws FrontendException {
+        if (!mIsSchemaComputed) {
+            try {
+                mSchema = mInput.getSchema();
+                mIsSchemaComputed = true;
+            } catch (FrontendException ioe) {
+                mSchema = null;
+                mIsSchemaComputed = false;
+                throw ioe;
+            }
+        }
+        return mSchema;
+    }
+
+    @Override
+    public String name() {
+        return "Limit (" + mLimit + ") " + mKey.scope + "-" + mKey.id;
+    }
+
+    @Override
+    public boolean supportsMultipleInputs() {
+        return false;
+    }
+
+    @Override
+    public boolean supportsMultipleOutputs() {
+        return false;
+    }
+
+    @Override
+    public void visit(LOVisitor v) throws VisitorException {
+        v.visit(this);
+    }
+
+    @Override
+    public byte getType() {
+        return DataType.BAG ;
+    }
+    
+    public LOLimit duplicate()
+    {
+    	return new LOLimit(mPlan, OperatorKey.genOpKey(mKey.scope), mLimit, mInput);
+    }
+}

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOSort.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOSort.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOSort.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOSort.java Thu Jul 24 20:20:06 2008
@@ -38,6 +38,7 @@
     private List<Boolean> mAscCols;
     private FuncSpec mSortFunc;
     private boolean mIsStar = false;
+    private long limit;
     private List<LogicalPlan> mSortColPlans;
     private static Log log = LogFactory.getLog(LOSort.class);
 
@@ -65,6 +66,7 @@
         mSortColPlans = sortColPlans;
         mAscCols = ascCols;
         mSortFunc = sortFunc;
+        limit = -1;
     }
 
     public LogicalOperator getInput() {
@@ -95,6 +97,21 @@
         mIsStar = b;
     }
 
+    public void setLimit(long l)
+    {
+    	limit = l;
+    }
+    
+    public long getLimit()
+    {
+    	return limit;
+    }
+    
+    public boolean isLimited()
+    {
+    	return (limit!=-1);
+    }
+
     @Override
     public String name() {
         return "SORT " + mKey.scope + "-" + mKey.id;

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOVisitor.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOVisitor.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOVisitor.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/LOVisitor.java Thu Jul 24 20:20:06 2008
@@ -170,6 +170,10 @@
         }
     }
 
+    protected void visit(LOLimit limOp) throws VisitorException {
+        return;
+    }
+
     /**
      * 
      * @param filter

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalOptimizer.java Thu Jul 24 20:20:06 2008
@@ -45,7 +45,14 @@
         required.add(true);
         mRules.add(new Rule(nodes, edges, required,
             new TypeCastInserter(plan)));
-
+        
+        nodes = new ArrayList<String>(1);
+        edges = new HashMap<Integer, Integer>();
+        required = new ArrayList<Boolean>(1);
+        nodes.add("org.apache.pig.impl.logicalLayer.LOLimit");
+        required.add(true);
+        mRules.add(new Rule(nodes, edges, required,
+                new OpLimitOptimizer(plan)));
     }
 
 }

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java Thu Jul 24 20:20:06 2008
@@ -207,5 +207,71 @@
         insertBetween(after, newNode, successors.get(0), projectionMapping);
     }
 
+    /**
+     * Remove a node in the middle of a linear chain. This includes removing the node 
+     * from the plan and reconnect the nodes before and after the node as well as rebuilding
+     * all of the schemas. This node should have one and only one predecessor and zero or one 
+     * successor
+     * @param nodeToRemove Node to remove
+     * @param projectionMapping A map that defines how projections in after
+     * relate to projections in nodeToRemove.  Keys are the projection offsets in
+     * after, values are the new offsets in nodeToRemove.  If this field is null,
+     * then it will be assumed that the mapping is 1-1.
+     * @throws VisitorException, FrontendException
+     */
+    protected void removeFromChain(
+            LogicalOperator nodeToRemove,
+            Map<Integer, Integer> projectionMapping)
+            throws VisitorException, FrontendException {
+    	
+    	List<LogicalOperator> afterNodes = mPlan.getPredecessors(nodeToRemove);
+    	if (afterNodes.size()!=1)
+    		throw new RuntimeException("removeFromChain only valid to remove " + 
+            	"node has one predecessor.");
+    	List<LogicalOperator> beforeNodes = mPlan.getSuccessors(nodeToRemove);
+    	if (beforeNodes!=null && beforeNodes.size()!=1)
+    		throw new RuntimeException("removeFromChain only valid to remove " + 
+        		"node has one successor.");
+    	
+    	// Get after and before node
+    	LogicalOperator after = mPlan.getPredecessors(nodeToRemove).get(0);
+    	LogicalOperator before = null;
+    	if (beforeNodes!=null)
+    		before = mPlan.getSuccessors(nodeToRemove).get(0);
+    	
+        // Remove nodeToRemove from plan
+    	mPlan.remove(nodeToRemove);
+    	if (before!=null)
+    	{
+	    	// Shortcut nodeToRemove.
+	        mPlan.connect(after, before);
+	
+	        // Visit all the inner plans of before and change their projects to
+	        // connect to after instead of nodeToRemove.
+	        // Find right inner plan(s) to visit
+	        List<LogicalPlan> plans = new ArrayList<LogicalPlan>();
+	        if (before instanceof LOCogroup) {
+	            plans.addAll((((LOCogroup)before).getGroupByPlans()).values());
+	        } else if (before instanceof LOSort) {
+	            plans.addAll(((LOSort)before).getSortColPlans());
+	        } else if (before instanceof LOFilter) {
+	            plans.add(((LOFilter)before).getComparisonPlan());
+	        } else if (before instanceof LOSplitOutput) {
+	            plans.add(((LOSplitOutput)before).getConditionPlan());
+	        } else if (before instanceof LOForEach) {
+	            plans.addAll(((LOForEach)before).getForEachPlans());
+	        }
+	        
+	        for (LogicalPlan lp : plans) {
+	            ProjectFixerUpper pfu =
+	                new ProjectFixerUpper(lp, after, projectionMapping);
+	            pfu.visit();
+	        }
+	
+    	}
 
+    	// Now rebuild the schemas
+        // rebuildSchemas();
+    }
+    
 }

Added: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java (added)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java Thu Jul 24 20:20:06 2008
@@ -0,0 +1,205 @@
+/*
+ * 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.List;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.pig.impl.logicalLayer.FrontendException;
+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.LOLimit;
+import org.apache.pig.impl.logicalLayer.LOLoad;
+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.LOUnion;
+import org.apache.pig.impl.logicalLayer.LogicalOperator;
+import org.apache.pig.impl.logicalLayer.LogicalPlan;
+import org.apache.pig.impl.plan.DepthFirstWalker;
+import org.apache.pig.impl.plan.VisitorException;
+import org.apache.pig.impl.plan.optimizer.OptimizerException;
+
+/**
+ * A visitor to discover if any schema has been specified for a file being
+ * loaded.  If so, a projection will be injected into the plan to cast the
+ * data being loaded to the appropriate types.  The optimizer can then come
+ * along and move those casts as far down as possible, or in some cases remove
+ * them altogether.  This visitor does not handle finding the schemas for the 
+ * file, that has already been done as part of parsing.
+ *
+ */
+public class OpLimitOptimizer extends LogicalTransformer {
+
+    private static final Log log = LogFactory.getLog(OpLimitOptimizer.class);
+
+    public OpLimitOptimizer(LogicalPlan plan) {
+        super(plan, new DepthFirstWalker<LogicalOperator, LogicalPlan>(plan));
+    }
+
+    @Override
+    public boolean check(List<LogicalOperator> nodes) throws OptimizerException {
+        LogicalOperator lo = nodes.get(0);
+        if (lo == null || !(lo instanceof LOLimit)) {
+            throw new RuntimeException("Expected limit, got " +
+                lo.getClass().getName());
+        }
+
+        return true;
+    }
+
+    @Override
+    public void transform(List<LogicalOperator> nodes) throws OptimizerException {
+        LogicalOperator lo = nodes.get(0);
+        if (lo == null || !(lo instanceof LOLimit)) {
+            throw new RuntimeException("Expected load, got " +
+                lo.getClass().getName());
+        }
+
+        LOLimit limit = (LOLimit)lo;
+        
+        processNode(limit);
+    }
+    
+    // We recursively optimize a LOLimit, until one of the following conditions occurs:
+    //   1. LOLimit can not move up
+    //   2. LOLimit merged into another LOSort or another LOLimit
+    // If we duplicate a LOLimit, then we leave the old LOLimit unmoved, 
+    //    and recursively optimize the new LOLimit
+    public void processNode(LOLimit limit) throws OptimizerException
+    {
+    	List<LogicalOperator> predecessors = mPlan.getPredecessors(limit);
+        if (predecessors.size()!=1)
+        	throw new OptimizerException("Limit have zero or more than one inputs");
+        LogicalOperator predecessor = predecessors.get(0);
+        
+        // Limit cannot be pushed up
+        if (predecessor instanceof LOCogroup || predecessor instanceof LOFilter ||
+        		predecessor instanceof LOLoad || predecessor instanceof LOSplit ||
+        		predecessor instanceof LOSplitOutput)
+        {
+        	return;
+        }
+        // Limit can be pushed in front of ForEach if it does not have a flatten
+        else if (predecessor instanceof LOForEach)
+        {
+        	LOForEach loForEach = (LOForEach)predecessor;
+        	List<Boolean> mFlatten = loForEach.getFlatten();
+        	boolean hasFlatten = false;
+        	for (Boolean b:mFlatten)
+        		if (b.equals(true)) hasFlatten = true;
+        	
+        	// We can safely move LOLimit up
+        	if (!hasFlatten)
+        	{
+				// Get operator before LOFilter
+				LogicalOperator prepredecessor = mPlan.getPredecessors(predecessor).get(0);
+				if (prepredecessor!=null)
+				{
+						try {
+							removeFromChain(limit, null);
+							insertBetween(prepredecessor, limit, predecessor, null);
+							
+						} catch (Exception e) {
+							throw new OptimizerException("Can not move LOLimit up", e);
+						}
+				}
+				else
+				{
+					throw new OptimizerException("LOFilter should have one input");
+				}
+        	}
+        	// we can move LOLimit even further, recursively optimize LOLimit
+        	processNode(limit);
+        }
+        // Limit can be duplicated, and the new instance pushed in front of an operator for the following operators 
+        // (that is, if you have X->limit, you can transform that to limit->X->limit):
+        else if (predecessor instanceof LOCross || predecessor instanceof LODistinct ||
+        		predecessor instanceof LOForEach || predecessor instanceof LOUnion)
+        {
+        	LOLimit newLimit = null;
+			// Process the predecessors with only one input. LOForEach should now have at least
+			// one flaten
+			if (predecessor instanceof LODistinct || predecessor instanceof LOForEach)
+			{
+				LogicalOperator prepredecessor = mPlan.getPredecessors(predecessor).get(0);
+				try {
+					newLimit = limit.duplicate();
+					insertBetween(prepredecessor, newLimit, predecessor, null);
+				} catch (Exception e) {
+					throw new OptimizerException("Can not insert LOLimit clone", e);
+				}
+				// we can move the new LOLimit even further, recursively optimize LOLimit
+				processNode(newLimit);
+			}
+			// Now comes predecessors with multiple inputs
+			else if (predecessor instanceof LOCross || predecessor instanceof LOUnion)
+			{
+				List<LogicalOperator> nodesToProcess = new ArrayList<LogicalOperator>();
+				for (LogicalOperator prepredecessor:mPlan.getPredecessors(predecessor))
+					nodesToProcess.add(prepredecessor);
+				for (LogicalOperator prepredecessor:nodesToProcess)
+				{
+					try {
+						newLimit = (LOLimit)limit.duplicate();
+						insertBetween(prepredecessor, newLimit, predecessor, null);
+					} catch (Exception e) {
+						throw new OptimizerException("Can not insert LOLimit clone", e);
+					}
+					// we can move the new LOLimit even further, recursively optimize LOLimit
+					processNode(newLimit);
+				}
+			}
+        }
+        // Limit can be merged into LOSort, result a "limited sort"
+        else if (predecessor instanceof LOSort)
+        {
+        	LOSort sort = (LOSort)predecessor;
+        	if (sort.getLimit()==-1)
+        		sort.setLimit(limit.getLimit());
+        	else
+        	    sort.setLimit(sort.getLimit()<limit.getLimit()?sort.getLimit():limit.getLimit());
+        	try {
+				removeFromChain(limit, null);
+			} catch (Exception e) {
+				throw new OptimizerException("Can not remove LOLimit after LOSort", e);
+			}
+        }
+        // Limit is merged into another LOLimit
+        else if (predecessor instanceof LOLimit)
+        {
+        	LOLimit beforeLimit = (LOLimit)predecessor;
+        	beforeLimit.setLimit(beforeLimit.getLimit()<limit.getLimit()?beforeLimit.getLimit():limit.getLimit());
+        	try {
+				removeFromChain(limit, null);
+			} catch (Exception e) {
+				throw new OptimizerException("Can not remove LOLimit after LOLimit", e);
+			}
+        }
+        else
+        	throw new OptimizerException("Move LOLimit in front of " + predecessor.getClass() + " is not implemented");
+    }
+}
+
+ 

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/QueryParser.jjt
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/QueryParser.jjt?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/QueryParser.jjt (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/QueryParser.jjt Thu Jul 24 20:20:06 2008
@@ -536,6 +536,7 @@
 TOKEN : { <MAP : "map"> }
 TOKEN : { <IS : "is"> }
 TOKEN : { <NULL : "null"> }
+TOKEN : { <LIMIT : "limit"> }
 
 TOKEN:
 {
@@ -729,6 +730,7 @@
 	(<LOAD> op = LoadClause(lp) [<AS> (LOOKAHEAD(2) "(" schema = TupleSchema() ")" {op.setSchema(schema); op.setCanonicalNames(); log.debug("Load as schema()");schema.printAliases();} | fs = AtomSchema() {schema = new Schema(fs); op.setSchema(schema); log.debug("Load as atomschema()");schema.printAliases();}) ])
 |	((<GROUP> | <COGROUP>) op = CogroupClause(lp))
 |	(<FILTER> op = FilterClause(lp))
+|   (<LIMIT> op = LimitClause(lp))
 |   (<ORDER> op = OrderClause(lp))
 |	(<DISTINCT> op = NestedExpr(lp) 
 	{
@@ -835,6 +837,31 @@
 	}
 }
 
+LogicalOperator LimitClause(LogicalPlan lp):
+{
+        LogicalOperator input;
+        Token t;
+        log.trace("Entering LimitClause");
+}
+{
+        (
+        input = NestedExpr(lp) {log.debug("Filter input: " + input);}
+         t = <INTEGER>
+         )
+        {
+                long l = Integer.parseInt(t.image);
+                LogicalOperator limit = new LOLimit(lp, new OperatorKey(scope, getNextId()), l, input);
+                addAlias(input.getAlias(), input);
+                lp.add(limit);
+                log.debug("Added operator " + limit.getClass().getName() + " to the logical plan");
+
+                lp.connect(input, limit);
+                log.debug("Connected alias " + input.getAlias() + " operator " + input.getClass().getName() + " to operator " + limit.getClass().getName() +" in the logical plan");
+
+                log.trace("Exiting LimitClause");
+                return limit;
+        }
+}
 
 ExpressionOperator PCond(Schema over, Map<String, LogicalOperator> specs, LogicalPlan lp, LogicalOperator input) : 
 {
@@ -1173,6 +1200,8 @@
 	ArrayList<Boolean> ascOrder = new ArrayList<Boolean>(); 
 	boolean asc = true; 
 	String funcName = null; 
+	long limit=-1;
+	Token t1;
 	log.trace("Entering OrderClause");
 }
 {
@@ -1200,7 +1229,8 @@
 			}
 		}	
 	)
-    (
+	(<LIMIT> t1 = <INTEGER> { limit = Integer.parseInt(t1.image);})?
+	(
         <USING>  funcName = QualifiedFunction()
     )?
 
@@ -1209,6 +1239,7 @@
 		LOSort sort = new LOSort(lp, new OperatorKey(scope, getNextId()), sortColPlans, ascOrder, 
 		                          (funcName != null ? new FuncSpec(funcName) : null));
 		sort.setStar(star);
+		sort.setLimit(limit);
 		lp.add(sort);
 		log.debug("Added operator " + sort.getClass().getName() + " to the logical plan");
 		

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/grammar
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/grammar?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/grammar (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/logicalLayer/parser/grammar Thu Jul 24 20:20:06 2008
@@ -2,7 +2,7 @@
 
 <expr> := [<alias> "="] <baseexpr> ["PARALLEL" <integer>]
 
-<baseexpr> := <alias> | "LOAD" <loadclause> | "EVAL" <evalclause> | "FILTER" <filterclause> | ["CO"]"GROUP" <cogroupclause> | "CROSS" <nestedexprs> | "UNION" <nestedexprs> | "(" <baseexpr> ")"
+<baseexpr> := <alias> | "LOAD" <loadclause> | "EVAL" <evalclause> | "FILTER" <filterclause> | ["CO"]"GROUP" <cogroupclause> | "CROSS" <nestedexprs> | "UNION" <nestedexprs> | "LIMIT" <limitclause> |"(" <baseexpr> ")"
 
 <nestedexpr> := <alias> | "("<expr>")"
 
@@ -30,6 +30,8 @@
 
 <filterclause> := "FILTER" <filter> "OVER" <nestedexpr>
 
+<limitclause> := "LIMIT" <nestedexpr> <integer>
+
 <filter> := <cond> "?" [<simpleproj> ":" <simpleproj>]
 
 <cond> := <basecond> | <cond> "AND" <cond> | <cond> "OR" <cond> | "NOT" <cond> | "("<cond>")"

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/PlanOptimizer.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/PlanOptimizer.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/PlanOptimizer.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/PlanOptimizer.java Thu Jul 24 20:20:06 2008
@@ -57,10 +57,13 @@
             if (matcher.match(rule)) {
                 // It matches the pattern.  Now check if the transformer
                 // approves as well.
-                List<O> matches = matcher.getMatches();
-                if (rule.transformer.check(matches)) {
-                    // The transformer approves.
-                    rule.transformer.transform(matches);
+                List<List<O>> matches = matcher.getAllMatches();
+                for (List<O> match:matches)
+                {
+	                if (rule.transformer.check(match)) {
+	                    // The transformer approves.
+	                    rule.transformer.transform(match);
+	                }
                 }
             }
         }

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/Rule.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/Rule.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/Rule.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/Rule.java Thu Jul 24 20:20:06 2008
@@ -36,10 +36,12 @@
  */
 public class Rule<O extends Operator, P extends OperatorPlan<O>> {
 
+	public enum WalkerAlgo {DepthFirstWalker, DependencyOrderWalker};
     public List<String> nodes;
     public Map<Integer, Integer> edges;
     public List<Boolean> required;
     public Transformer<O, P> transformer;
+    public WalkerAlgo algo;
 
     /**
      * @param n List of node types to look for.
@@ -48,14 +50,23 @@
      * @param r List of boolean indicating whether given nodes are
      * required for the pattern to match.
      * @param t Transformer to apply if the rule matches.
+     * @param al Walker algorithm to find rule match within the plan.
      */
     public Rule(List<String> n,
                 Map<Integer, Integer> e, 
                 List<Boolean> r,
-                Transformer<O, P> t) {
+                Transformer<O, P> t, WalkerAlgo al) {
         nodes = n;
         edges = e;
         required = r;
         transformer = t;
+        algo = al;
+    }
+    
+    public Rule(List<String> n,
+                Map<Integer, Integer> e, 
+                List<Boolean> r,
+                Transformer<O, P> t) {
+    	this(n, e, r, t, WalkerAlgo.DependencyOrderWalker);
     }
 }

Modified: incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java (original)
+++ incubator/pig/branches/types/src/org/apache/pig/impl/plan/optimizer/RuleMatcher.java Thu Jul 24 20:20:06 2008
@@ -18,12 +18,18 @@
 package org.apache.pig.impl.plan.optimizer;
 
 import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
 import java.util.Iterator;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
+import java.util.Queue;
+import java.util.Set;
 
 import org.apache.pig.impl.plan.Operator;
 import org.apache.pig.impl.plan.OperatorPlan;
+import org.apache.pig.impl.plan.VisitorException;
 
 /**
  * RuleMatcher contains the logic to determine whether a given rule matches.
@@ -35,31 +41,103 @@
 public class RuleMatcher<O extends Operator, P extends OperatorPlan<O>> {
 
     private Rule<O, P> mRule;
-    private List<O> mMatches;
+    private List<O> mMatch;
+    private List<List<O>> mMatches = new ArrayList<List<O>>();
     private P mPlan; // for convience.
+    Set<O> seen = new HashSet<O>();
 
     /**
-     * Test a rule to see if it matches the current plan.
+     * Test a rule to see if it matches the current plan. Save all matched nodes using BFS
      * @param rule Rule to test for a match.
      * @return true if the plan matches.
      */
     public boolean match(Rule<O, P> rule) {
         mRule = rule;
-        int sz = mRule.nodes.size();
-        mMatches = new ArrayList<O>(sz);
+        
         mPlan = mRule.transformer.getPlan();
-        // Add sufficient slots in the matches array
-        for (int i = 0; i < sz; i++) mMatches.add(null);
-        return beginMatch(mPlan.getRoots());
+        mMatches.clear();
+        
+        if (mRule.algo == Rule.WalkerAlgo.DependencyOrderWalker)
+        	DependencyOrderWalker();
+        else if (mRule.algo == Rule.WalkerAlgo.DepthFirstWalker)
+        	DepthFirstWalker();        
+        
+        return (mMatches.size()!=0);
+    }
+    
+    private void DependencyOrderWalker()
+    {
+        List<O> fifo = new ArrayList<O>();
+        Set<O> seen = new HashSet<O>();
+        List<O> leaves = mPlan.getLeaves();
+        if (leaves == null) return;
+        for (O op : leaves) {
+        	BFSDoAllPredecessors(op, seen, fifo);
+        }
+
+        for (O op: fifo) {
+        	if (beginMatch(op))
+			{
+        		mMatches.add(mMatch);
+			}
+        }
+    }
+    
+    private void BFSDoAllPredecessors(O node, Set<O> seen, Collection<O> fifo)  {
+		if (!seen.contains(node)) {
+		// We haven't seen this one before.
+		Collection<O> preds = mPlan.getPredecessors(node);
+		if (preds != null && preds.size() > 0) {
+		// Do all our predecessors before ourself
+			for (O op : preds) {
+				BFSDoAllPredecessors(op, seen, fifo);
+			}
+		}
+		// Now do ourself
+		seen.add(node);
+		fifo.add(node);
+		}
+    }
+    
+    private void DepthFirstWalker()
+    {
+    	Set<O> seen = new HashSet<O>();
+        DFSVisit(null, mPlan.getRoots(), seen);
+    }
+    
+    private void DFSVisit(O node, Collection<O> successors,Set<O> seen)
+    {
+        if (successors == null) return;
+        for (O suc : successors) {
+            if (seen.add(suc)) {
+            	if (beginMatch(suc))
+            		mMatches.add(mMatch);
+                Collection<O> newSuccessors = mPlan.getSuccessors(suc);
+                DFSVisit(suc, newSuccessors, seen);
+            }
+        }
     }
 
     /**
-     * @return a list that with the instances of nodes that matched the
+     * @return first occurrence of matched list of nodes that with the instances of nodes that matched the
      * pattern defined by
      * the rule.  The nodes will be in the vector in the order they are
      * specified in the rule.
      */
     List<O> getMatches() {
+        if (mMatches.size()>=1)
+            return mMatches.get(0);
+        return null;
+
+    }
+
+    /**
+     * @return all occurrences of matches. lists of nodes that with the instances of nodes that matched the
+     * pattern defined by
+     * the rule.  The nodes will be in the vector in the order they are
+     * specified in the rule.
+     */
+    List<List<O>> getAllMatches() {
         return mMatches;
     }
 
@@ -74,29 +152,28 @@
      *     pattern of 2->1 is not.
      *
      */
-    private boolean beginMatch(List<O> nodes) {
-        if (nodes == null) return false;
-        for (O op : nodes) {
-            List<O> successors = new ArrayList<O>();
-            if (op.getClass().getName().equals(mRule.nodes.get(0))) {
-                mMatches.set(0, op);
-                // Follow the edge to see the next node we should be looking for.
-                Integer nextOpNum = mRule.edges.get(0);
-                if (nextOpNum == null) {
-                    // This was looking for a single node
-                    return true;
-                }
-                successors = mPlan.getSuccessors(op);
-                if (successors == null) return false;
-                for (O successorOp : successors) {
-                    if (continueMatch(successorOp, nextOpNum)) return true;
-                }
-            }
-
-            // That node didn't match.  Go to this nodes successors and see if
-            // any of them match.
-            successors = mPlan.getSuccessors(op);
-            if (beginMatch(successors)) return true;
+    private boolean beginMatch(O node) {
+        if (node == null) return false;
+        
+        int sz = mRule.nodes.size();
+        mMatch = new ArrayList<O>(sz);
+        // Add sufficient slots in the matches array
+        for (int i = 0; i < sz; i++) mMatch.add(null);
+        
+        List<O> successors = new ArrayList<O>();
+        if (node.getClass().getName().equals(mRule.nodes.get(0))) {
+            mMatch.set(0, node);
+            // Follow the edge to see the next node we should be looking for.
+            Integer nextOpNum = mRule.edges.get(0);
+            if (nextOpNum == null) {
+                // This was looking for a single node
+                return true;
+            }
+            successors = mPlan.getSuccessors(node);
+            if (successors == null) return false;
+            for (O successorOp : successors) {
+                if (continueMatch(successorOp, nextOpNum)) return true;
+            }
         }
         // If we get here we haven't found it.
         return false;
@@ -104,7 +181,7 @@
 
     private boolean continueMatch(O current, Integer nodeNumber) {
         if (current.getClass().getName() == mRule.nodes.get(nodeNumber)) {
-            mMatches.set(nodeNumber, current);
+            mMatch.set(nodeNumber, current);
 
             // Follow the edge to see the next node we should be looking for.
             Integer nextOpNum = mRule.edges.get(nodeNumber);
@@ -133,7 +210,7 @@
         // We can arrive here either because we didn't match at this node or
         // further down the line.  One way or another we need to remove ourselves
         // from the match vector and return false.
-        mMatches.set(nodeNumber, null);
+        mMatch.set(nodeNumber, null);
         return false;
     }
 

Added: incubator/pig/branches/types/test/org/apache/pig/test/OpLimitOptimizerPrinter.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/OpLimitOptimizerPrinter.java?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/OpLimitOptimizerPrinter.java (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/OpLimitOptimizerPrinter.java Thu Jul 24 20:20:06 2008
@@ -0,0 +1,175 @@
+/*
+ * 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.test;
+
+import java.util.Iterator;
+import java.util.List;
+import java.util.ArrayList;
+
+import org.apache.pig.data.DataType;
+import org.apache.pig.impl.logicalLayer.*;
+import org.apache.pig.impl.logicalLayer.parser.ParseException ;
+import org.apache.pig.impl.logicalLayer.schema.Schema;
+import org.apache.pig.impl.plan.* ;
+
+/**
+ * This class transforms LogicalPlan to its textual representation
+ *
+ */
+public class OpLimitOptimizerPrinter extends LOVisitor {
+    
+    private StringBuilder sb = null ;
+    
+    public OpLimitOptimizerPrinter(LogicalPlan plan) {
+        super(plan, new DependencyOrderWalker<LogicalOperator, LogicalPlan>(plan));
+        sb = new StringBuilder() ;
+    }
+
+    protected void visit(LogicalOperator op) {
+    	appendEdges(op);
+    }
+    
+    protected void visit(ExpressionOperator op) {
+    	appendEdges(op);
+    }
+    
+    protected void visit(BinaryExpressionOperator op) {
+    	appendEdges(op);
+    }
+    
+    protected void visit(UnaryExpressionOperator op) {               
+    	appendEdges(op);
+    }
+    
+    protected void visit(LOCogroup op) throws VisitorException {
+    	appendEdges(op);
+    }
+    
+    protected void visit(LOForEach op) throws VisitorException {
+        appendOp(op) ;
+    	boolean hasFlatten = false;
+    	List<Boolean> mFlatten = op.getFlatten();
+
+    	for (Boolean b:mFlatten)
+    		if (b.equals(true)) hasFlatten = true;
+
+    	if (hasFlatten)
+    		sb.append(" [hasflat=\"true\"]");
+    	else
+    		sb.append(" [hasflat=\"false\"]");
+        sb.append(";\n");
+        appendEdges(op);
+    }
+    
+    protected void visit(LOSort op) {
+        appendOp(op) ;
+        sb.append(" [limit=\""+op.getLimit()+"\"]");
+        sb.append(";\n");
+        appendEdges(op);
+    }
+    
+    protected void visit(LOFilter op) throws VisitorException {
+    	appendEdges(op);
+    }
+    
+    protected void visit(LOSplit op) {
+    	appendEdges(op);
+    }
+    
+    protected void visit(LOUserFunc op) {
+        appendEdges(op);
+    }
+    
+    protected void visit(LOBinCond op) {
+        appendEdges(op);
+    }
+
+    protected void visit(LOCross op) {
+        appendEdges(op);
+    }
+    
+    protected void visit(LOUnion op) {
+        appendEdges(op);
+    }
+    
+    protected void visit(LOCast op) { 
+        appendEdges(op);
+    }
+      
+    protected void visit(LOLoad op) { 
+        appendEdges(op);
+    }
+    
+    protected void visit(LOStore op) {   
+        appendEdges(op);
+    }
+    
+    protected void visit(LOConst op) {  
+        appendEdges(op);
+    }
+
+    protected void visit(LORegexp op) {
+        appendEdges(op);
+    }
+
+    protected void visit(LOProject op) {
+        appendEdges(op);
+    }
+
+    protected void visit(LODistinct op) {
+        appendEdges(op);
+    }
+    
+    protected void visit(LOLimit op) {
+        appendOp(op) ;
+        sb.append(" [limit=\""+op.getLimit()+"\"]");
+        sb.append(";\n");
+        appendEdges(op);
+    }
+
+
+    private void appendOp(LogicalOperator op)  {
+        sb.append("    "+op.getClass().getSimpleName()+op.getOperatorKey().getId()) ;
+
+    }
+    
+    private void appendEdges(LogicalOperator op)
+    {
+        List<LogicalOperator> list = mCurrentWalker.getPlan().getSuccessors(op) ;
+
+		if (list!=null) {
+			for(LogicalOperator tmp: list) {         
+			    sb.append("    "+op.getClass().getSimpleName()+op.getOperatorKey().getId()+" -> ");
+			    sb.append(tmp.getClass().getSimpleName()+tmp.getOperatorKey().getId()+";\n");
+		    }
+		}
+    }
+    
+    /***
+     * This method has to be called after the visit is totally finished only
+     */
+    public String printToString() {
+        try {
+            visit() ;
+        }
+        catch(VisitorException vse) {
+            throw new AssertionError("Error while transforming type graph to text") ;
+        }
+        return sb.toString() ;
+    }
+}

Modified: incubator/pig/branches/types/test/org/apache/pig/test/TestEvalPipeline.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/TestEvalPipeline.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/TestEvalPipeline.java (original)
+++ incubator/pig/branches/types/test/org/apache/pig/test/TestEvalPipeline.java Thu Jul 24 20:20:06 2008
@@ -380,4 +380,29 @@
         assertEquals(LOOP_COUNT, numIdentity);
     }
 
+    public void testLimit() throws Exception{
+        int LOOP_COUNT = 20;
+        File tmpFile = File.createTempFile("test", "txt");
+        PrintStream ps = new PrintStream(new FileOutputStream(tmpFile));
+        Random r = new Random();
+        for(int i = 0; i < LOOP_COUNT; i++) {
+            ps.println(i);
+        }
+        ps.close();
+
+        String tmpOutputFile = FileLocalizer.getTemporaryPath(null, 
+        pigServer.getPigContext()).toString();
+        pigServer.registerQuery("A = LOAD 'file:" + tmpFile + "';");
+        pigServer.registerQuery("B = limit A 5;");
+        Iterator<Tuple> iter = pigServer.openIterator("B");
+        if(!iter.hasNext()) fail("No output found");
+        int numIdentity = 0;
+        while(iter.hasNext()){
+            Tuple t = iter.next();
+            ++numIdentity;
+        }
+        assertEquals(5, numIdentity);
+    }
+
+
 }

Modified: incubator/pig/branches/types/test/org/apache/pig/test/TestLogToPhyCompiler.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/TestLogToPhyCompiler.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/TestLogToPhyCompiler.java (original)
+++ incubator/pig/branches/types/test/org/apache/pig/test/TestLogToPhyCompiler.java Thu Jul 24 20:20:06 2008
@@ -479,6 +479,55 @@
     	
     }
 
+    @Test
+    public void testLimit() throws VisitorException, IOException {
+        String query = "limit (load 'a') 5;";
+        LogicalPlan plan = buildPlan(query);
+        PhysicalPlan pp = buildPhysicalPlan(plan);
+
+        int MAX_SIZE = 100000;
+        ByteArrayOutputStream baos = new ByteArrayOutputStream();
+        pp.explain(baos);
+        String compiledPlan = baos.toString();
+        FileInputStream fis = new FileInputStream("test/org/apache/pig/test/data/GoldenFiles/Limit.gld");
+        byte[] b = new byte[MAX_SIZE];
+        int len = fis.read(b);
+        String goldenPlan = new String(b, 0, len);
+
+
+        System.out.println();
+        System.out.println(compiledPlan);
+        System.out.println("-------------");
+
+        //System.out.println(compiledPlan.compareTo(goldenPlan)==0);
+        assertEquals(true, compiledPlan.compareTo(goldenPlan) == 0);
+    }
+
+    @Test
+    public void testLimitedSort() throws VisitorException, IOException {
+        String query = "Order (load 'a') by $0 limit 5;";
+        LogicalPlan plan = buildPlan(query);
+        PhysicalPlan pp = buildPhysicalPlan(plan);
+
+        int MAX_SIZE = 100000;
+        ByteArrayOutputStream baos = new ByteArrayOutputStream();
+        pp.explain(baos);
+        String compiledPlan = baos.toString();
+        FileInputStream fis = new FileInputStream("test/org/apache/pig/test/data/GoldenFiles/LimitedSort.gld");
+        byte[] b = new byte[MAX_SIZE];
+        int len = fis.read(b);
+        String goldenPlan = new String(b, 0, len);
+
+
+        System.out.println();
+        System.out.println(compiledPlan);
+        System.out.println("-------------");
+
+        //System.out.println(compiledPlan.compareTo(goldenPlan)==0);
+        assertEquals(true, compiledPlan.compareTo(goldenPlan) == 0);
+    }
+
+    
     /*@Test
     public void testUserFunc() throws VisitorException {
     	String query = "foreach (group (load 'file:ABCD') all) generate " + COUNT.class.getName() + "($1) ;";

Modified: incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalOptimizer.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalOptimizer.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalOptimizer.java (original)
+++ incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalOptimizer.java Thu Jul 24 20:20:06 2008
@@ -17,9 +17,16 @@
  */
 package org.apache.pig.test;
 
+import java.io.BufferedReader;
+import java.io.FileInputStream;
+import java.io.FileNotFoundException;
+import java.io.FileReader;
+import java.io.IOException;
+
 import org.apache.pig.impl.logicalLayer.*;
 import org.apache.pig.impl.logicalLayer.optimizer.*;
 import org.apache.pig.test.utils.LogicalPlanTester;
+import org.apache.pig.test.utils.TypeCheckingTestUtil;
 
 import org.junit.Test;
 import org.junit.Before;
@@ -31,14 +38,41 @@
 public class TestLogicalOptimizer extends junit.framework.TestCase {
 
     final String FILE_BASE_LOCATION = "test/org/apache/pig/test/data/DotFiles/" ;
+    static final int MAX_SIZE = 100000;
 
     LogicalPlanTester planTester = new LogicalPlanTester() ;
 
+    /*
     @Before
     public void setUp() {
         planTester.reset();
-    }
+    }*/
 
+    public static String printLimitGraph(LogicalPlan plan) {
+    	OpLimitOptimizerPrinter printer = new OpLimitOptimizerPrinter(plan) ;
+        String rep = "digraph graph1 {\n";
+    	rep = rep + printer.printToString() ;
+    	rep = rep + "}";
+        return rep;
+    }
+    
+    public static void optimizePlan(LogicalPlan plan) throws Exception
+    {
+        LogicalOptimizer optimizer = new LogicalOptimizer(plan);
+        optimizer.optimize();
+    }
+    
+    void compareWithGoldenFile(LogicalPlan plan, String filename) throws Exception
+    {
+        FileInputStream fis = new FileInputStream(filename);
+        byte[] b = new byte[MAX_SIZE];
+        int len = fis.read(b);
+        String goldenPlan = new String(b, 0, len);
+        
+		String actualPlan = printLimitGraph(plan);		
+		assertEquals(goldenPlan, actualPlan);
+    }
+    
     @Test
     public void testTypeCastInsertion() throws Exception {
         planTester.buildPlan("A = load 'myfile' as (p:int, q:long, r:float, "
@@ -48,5 +82,67 @@
         planTester.typeCheckAgainstDotFile(plan, FILE_BASE_LOCATION +
             "optplan1.dot", true);
     }
+    
+    @Test
+    // Merget limit into sort
+	public void testOPLimit1Optimizer() throws Exception {
+	    planTester.buildPlan("A = load 'myfile';");
+	    planTester.buildPlan("B = order A by $0;");
+	    LogicalPlan plan = planTester.buildPlan("C = limit B 100;");
+	    optimizePlan(plan);
+	    compareWithGoldenFile(plan, FILE_BASE_LOCATION + "optlimitplan1.dot");
+	}
+
+	@Test
+	// Merge limit into limit
+	public void testOPLimit2Optimizer() throws Exception {
+	    planTester.buildPlan("A = load 'myfile';");
+	    planTester.buildPlan("B = limit A 10;");
+	    LogicalPlan plan = planTester.buildPlan("C = limit B 100;");
+	    optimizePlan(plan);
+	    compareWithGoldenFile(plan, FILE_BASE_LOCATION + "optlimitplan2.dot");
+	}
+
+	@Test
+	// Duplicate limit with two inputs
+	public void testOPLimit3Optimizer() throws Exception {
+	    planTester.buildPlan("A = load 'myfile1';");
+	    planTester.buildPlan("B = load 'myfile2';");
+	    planTester.buildPlan("C = cross A, B;");
+	    LogicalPlan plan = planTester.buildPlan("D = limit C 100;");
+	    optimizePlan(plan);
+	    compareWithGoldenFile(plan, FILE_BASE_LOCATION + "optlimitplan3.dot");
+	}
+
+	@Test
+	// Duplicte limit with one input
+	public void testOPLimit4Optimizer() throws Exception {
+	    planTester.buildPlan("A = load 'myfile1';");
+	    planTester.buildPlan("B = distinct A;");
+	    LogicalPlan plan = planTester.buildPlan("C = limit B 100;");
+	    optimizePlan(plan);
+	    compareWithGoldenFile(plan, FILE_BASE_LOCATION + "optlimitplan4.dot");
+	}
+
+	@Test
+	// Move limit up
+    public void testOPLimit5Optimizer() throws Exception {
+        planTester.buildPlan("A = load 'myfile1';");
+        planTester.buildPlan("B = foreach A generate $0;");
+        LogicalPlan plan = planTester.buildPlan("C = limit B 100;");
+        optimizePlan(plan);
+        compareWithGoldenFile(plan, FILE_BASE_LOCATION + "optlimitplan5.dot");
+    }
+	
+    @Test
+    // Multiple LOLimit
+	public void testOPLimit6Optimizer() throws Exception {
+	    planTester.buildPlan("A = load 'myfile';");
+	    planTester.buildPlan("B = limit A 50;");
+	    planTester.buildPlan("C = limit B 20;");
+	    LogicalPlan plan = planTester.buildPlan("D = limit C 100;");
+	    optimizePlan(plan);
+	    compareWithGoldenFile(plan, FILE_BASE_LOCATION + "optlimitplan6.dot");
+	}
 }
 

Modified: incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalPlanBuilder.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalPlanBuilder.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalPlanBuilder.java (original)
+++ incubator/pig/branches/types/test/org/apache/pig/test/TestLogicalPlanBuilder.java Thu Jul 24 20:20:06 2008
@@ -880,6 +880,17 @@
     }
 
     @Test
+    public void testQuery77() {
+        buildPlan("limit (load 'a') 100;");
+    }
+    
+    @Test
+    public void testQuery78() {
+        buildPlan("a = load 'a';");
+        buildPlan("b = order a by $0 limit 100;");
+    }
+    
+    @Test
     public void testQuery75() {
         buildPlan("a = union (load 'a'), (load 'b'), (load 'c');");
         buildPlan("b = foreach a {generate $0;} parallel 10;");

Modified: incubator/pig/branches/types/test/org/apache/pig/test/TestMRCompiler.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/TestMRCompiler.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/TestMRCompiler.java (original)
+++ incubator/pig/branches/types/test/org/apache/pig/test/TestMRCompiler.java Thu Jul 24 20:20:06 2008
@@ -776,6 +776,23 @@
         run(php, "test/org/apache/pig/test/data/GoldenFiles/MRC16.gld");
     }
     
+    public void testLimit() throws Exception {
+        PhysicalPlan php = new PhysicalPlan();
+
+        POLoad lC = GenPhyOp.topLoadOp();
+        php.add(lC);
+
+        POLimit op = new POLimit(new OperatorKey("", r.nextLong()),
+                -1, null);
+
+        php.add(op);
+        php.connect(lC, op);
+
+        POStore st = GenPhyOp.topStoreOp();
+        php.addAsLeaf(st);
+        run(php, "test/org/apache/pig/test/data/GoldenFiles/MRC17.gld");
+    }
+    
     public static class WeirdComparator extends ComparisonFunc {
 
         @Override

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan1.dot
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan1.dot?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan1.dot (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan1.dot Thu Jul 24 20:20:06 2008
@@ -0,0 +1,4 @@
+digraph graph1 {
+    LOLoad18 -> LOSort20;
+    LOSort20 [limit="100"];
+}
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan2.dot
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan2.dot?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan2.dot (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan2.dot Thu Jul 24 20:20:06 2008
@@ -0,0 +1,4 @@
+digraph graph1 {
+    LOLoad22 -> LOLimit23;
+    LOLimit23 [limit="10"];
+}
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan3.dot
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan3.dot?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan3.dot (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan3.dot Thu Jul 24 20:20:06 2008
@@ -0,0 +1,10 @@
+digraph graph1 {
+    LOLoad25 -> LOLimit29;
+    LOLimit29 [limit="100"];
+    LOLimit29 -> LOCross27;
+    LOLoad26 -> LOLimit30;
+    LOLimit30 [limit="100"];
+    LOLimit30 -> LOCross27;
+    LOCross27 -> LOLimit28;
+    LOLimit28 [limit="100"];
+}
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan4.dot
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan4.dot?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan4.dot (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan4.dot Thu Jul 24 20:20:06 2008
@@ -0,0 +1,7 @@
+digraph graph1 {
+    LOLoad31 -> LOLimit34;
+    LOLimit34 [limit="100"];
+    LOLimit34 -> LODistinct32;
+    LODistinct32 -> LOLimit33;
+    LOLimit33 [limit="100"];
+}
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan5.dot
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan5.dot?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan5.dot (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan5.dot Thu Jul 24 20:20:06 2008
@@ -0,0 +1,6 @@
+digraph graph1 {
+    LOLoad35 -> LOLimit39;
+    LOLimit39 [limit="100"];
+    LOLimit39 -> LOForEach38;
+    LOForEach38 [hasflat="false"];
+}
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan6.dot
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan6.dot?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan6.dot (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/DotFiles/optlimitplan6.dot Thu Jul 24 20:20:06 2008
@@ -0,0 +1,4 @@
+digraph graph1 {
+    LOLoad40 -> LOLimit41;
+    LOLimit41 [limit="20"];
+}
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/Limit.gld
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/Limit.gld?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/Limit.gld (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/Limit.gld Thu Jul 24 20:20:06 2008
@@ -0,0 +1,3 @@
+Limit - Test-Plan-Builder-224
+|
+|---Load(a:org.apache.pig.builtin.PigStorage()) - Test-Plan-Builder-223
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/LimitedSort.gld
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/LimitedSort.gld?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/LimitedSort.gld (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/LimitedSort.gld Thu Jul 24 20:20:06 2008
@@ -0,0 +1,5 @@
+POSort[bag] - Test-Plan-Builder-230
+|   |
+|   Project[bytearray][0] - Test-Plan-Builder-229
+|
+|---Load(a:org.apache.pig.builtin.PigStorage()) - Test-Plan-Builder-228
\ No newline at end of file

Added: incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/MRC17.gld
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/MRC17.gld?rev=679651&view=auto
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/MRC17.gld (added)
+++ incubator/pig/branches/types/test/org/apache/pig/test/data/GoldenFiles/MRC17.gld Thu Jul 24 20:20:06 2008
@@ -0,0 +1,17 @@
+MapReduce(-1) - -184:
+|   Store(DummyFil:DummyLdr) - -6079615556647418436
+|   |
+|   |---New For Each(false)[bag] - -189
+|       |   |
+|       |   Project[tuple][0] - -188
+|       |
+|       |---Limit - --982263781809208816
+|           |
+|           |---Package[tuple]{tuple} - -187
+|   Local Rearrange[tuple]{tuple} - -186
+|   |   |
+|   |   Project[tuple][*] - -185
+|   |
+|   |---Limit - --982263781809208816
+|       |
+|       |---Load(DummyFil:DummyLdr) - -8219725798912083822
\ No newline at end of file

Modified: incubator/pig/branches/types/test/org/apache/pig/test/utils/GenPhyOp.java
URL: http://svn.apache.org/viewvc/incubator/pig/branches/types/test/org/apache/pig/test/utils/GenPhyOp.java?rev=679651&r1=679650&r2=679651&view=diff
==============================================================================
--- incubator/pig/branches/types/test/org/apache/pig/test/utils/GenPhyOp.java (original)
+++ incubator/pig/branches/types/test/org/apache/pig/test/utils/GenPhyOp.java Thu Jul 24 20:20:06 2008
@@ -584,6 +584,11 @@
         POFilter ret = new POFilter(new OperatorKey("", r.nextLong()), ops);
         return ret;
     }
+    
+    public static POLimit topLimitOp() {
+        POLimit ret = new POLimit(new OperatorKey("", r.nextLong()));
+        return ret;
+    }
 
     public static POFilter topFilterOpWithExPlan(int lhsVal, int rhsVal)
             throws ExecException, PlanException {