You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pig.apache.org by ol...@apache.org on 2009/07/30 02:30:26 UTC

svn commit: r799141 [1/2] - in /hadoop/pig/trunk: ./ src/org/apache/pig/ src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/ src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/partitioners/ src/org/apache/pig/backend/hadoop/...

Author: olga
Date: Thu Jul 30 00:30:25 2009
New Revision: 799141

URL: http://svn.apache.org/viewvc?rev=799141&view=rev
Log:
PIG-792: skew join implementation (sriranjan via olgan)

Added:
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/partitioners/SkewedPartitioner.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POPartitionRearrange.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSkewedJoin.java
    hadoop/pig/trunk/src/org/apache/pig/impl/builtin/PartitionSkewedKeys.java
    hadoop/pig/trunk/src/org/apache/pig/impl/builtin/TupleSize.java
    hadoop/pig/trunk/src/org/apache/pig/impl/io/NullablePartitionWritable.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/LOJoin.java
    hadoop/pig/trunk/test/org/apache/pig/test/TestSkewedJoin.java
Modified:
    hadoop/pig/trunk/CHANGES.txt
    hadoop/pig/trunk/src/org/apache/pig/PigServer.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/JobControlCompiler.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceLauncher.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceOper.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PhyPlanSetter.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapBase.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapReduce.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/SampleOptimizer.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/DotPOPrinter.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhysicalPlan.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PlanPrinter.java
    hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/util/MapRedUtil.java
    hadoop/pig/trunk/src/org/apache/pig/builtin/PigStorage.java
    hadoop/pig/trunk/src/org/apache/pig/data/DataType.java
    hadoop/pig/trunk/src/org/apache/pig/impl/builtin/RandomSampleLoader.java
    hadoop/pig/trunk/src/org/apache/pig/impl/io/FileLocalizer.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/DotLOPrinter.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/LOPrinter.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/LOVisitor.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/PlanSetter.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/ProjectStarTranslator.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/optimizer/LogicalTransformer.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/optimizer/OpLimitOptimizer.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/optimizer/SchemaRemover.java
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/parser/QueryParser.jjt
    hadoop/pig/trunk/src/org/apache/pig/impl/logicalLayer/validators/TypeCheckingVisitor.java

Modified: hadoop/pig/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/CHANGES.txt?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/CHANGES.txt (original)
+++ hadoop/pig/trunk/CHANGES.txt Thu Jul 30 00:30:25 2009
@@ -40,6 +40,8 @@
 
 OPTIMIZATIONS
 
+PIG-792: skew join implementation (sriranjan via olgan)
+
 BUG FIXES
 
     PIG-773: Empty complex constants (empty bag, empty tuple and empty map)

Modified: hadoop/pig/trunk/src/org/apache/pig/PigServer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/PigServer.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/PigServer.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/PigServer.java Thu Jul 30 00:30:25 2009
@@ -54,6 +54,7 @@
 import org.apache.pig.impl.logicalLayer.FrontendException;
 import org.apache.pig.impl.logicalLayer.LOCogroup;
 import org.apache.pig.impl.logicalLayer.LOFRJoin;
+import org.apache.pig.impl.logicalLayer.LOJoin;
 import org.apache.pig.impl.logicalLayer.LOLoad;
 import org.apache.pig.impl.logicalLayer.LOPrinter;
 import org.apache.pig.impl.logicalLayer.LogicalOperator;
@@ -1148,8 +1149,6 @@
                             lp.removeAndReconnectMultiSucc(load);
                             
                             List<LogicalOperator> succs = lp.getSuccessors(load);
-                            
-
                         } else {
                             try {
                                 store.getPlan().connect(store, load);

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/JobControlCompiler.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/JobControlCompiler.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/JobControlCompiler.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/JobControlCompiler.java Thu Jul 30 00:30:25 2009
@@ -48,6 +48,7 @@
 import org.apache.pig.backend.executionengine.ExecException;
 import org.apache.pig.backend.hadoop.HDataType;
 import org.apache.pig.backend.hadoop.executionengine.mapReduceLayer.partitioners.WeightedRangePartitioner;
+import org.apache.pig.backend.hadoop.executionengine.mapReduceLayer.partitioners.SkewedPartitioner;
 import org.apache.pig.backend.hadoop.executionengine.mapReduceLayer.plans.MROperPlan;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.PhysicalOperator;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.plans.PhysicalPlan;
@@ -62,6 +63,7 @@
 import org.apache.pig.impl.io.FileLocalizer;
 import org.apache.pig.impl.io.FileSpec;
 import org.apache.pig.impl.io.NullableBytesWritable;
+import org.apache.pig.impl.io.NullablePartitionWritable;
 import org.apache.pig.impl.io.NullableDoubleWritable;
 import org.apache.pig.impl.io.NullableFloatWritable;
 import org.apache.pig.impl.io.NullableIntWritable;
@@ -173,10 +175,12 @@
         for (FileStatus fstat: fs.listStatus(p)) {
             Path src = fstat.getPath();
             if (fstat.isDir()) {
+		log.info("mkdir: "+src);
                 fs.mkdirs(removePart(src, rem));
                 moveResults(fstat.getPath(), rem, fs);
             } else {
                 Path dst = removePart(src, rem);
+		log.info("mv: "+src+" "+dst);
                 fs.rename(src,dst);
             }
         }
@@ -511,6 +515,13 @@
                 }
             }
             
+            if (mro.isSkewedJoin()) {
+            	jobConf.set("pig.keyDistFile", mro.getSkewedJoinPartitionFile());
+            	jobConf.setPartitionerClass(SkewedPartitioner.class);
+            	jobConf.setMapperClass(PigMapReduce.MapWithPartitionIndex.class);
+				jobConf.setMapOutputKeyClass(NullablePartitionWritable.class);
+            }
+            
             Job job = new Job(jobConf);
             jobStoreMap.put(job,new Pair(storeLocations, tmpLocation));
             return job;

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MRCompiler.java Thu Jul 30 00:30:25 2009
@@ -37,6 +37,8 @@
 import org.apache.pig.data.DataType;
 import org.apache.pig.impl.PigContext;
 import org.apache.pig.impl.builtin.FindQuantiles;
+import org.apache.pig.impl.builtin.TupleSize;
+import org.apache.pig.impl.builtin.PartitionSkewedKeys;
 import org.apache.pig.impl.builtin.RandomSampleLoader;
 import org.apache.pig.impl.io.FileLocalizer;
 import org.apache.pig.impl.io.FileSpec;
@@ -61,8 +63,10 @@
 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;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POPackageLite;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POPartitionRearrange;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POPackage;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POSkewedJoin;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POSort;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POSplit;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POStore;
@@ -77,6 +81,7 @@
 import org.apache.pig.impl.plan.PlanException;
 import org.apache.pig.impl.plan.VisitorException;
 import org.apache.pig.impl.plan.CompilationMessageCollector.MessageType;
+import org.apache.pig.impl.util.MultiMap;
 import org.apache.pig.impl.util.Pair;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.util.PlanHelper;
 
@@ -345,8 +350,13 @@
         //Now we have the inputs compiled. Do something
         //with the input oper op.
         op.visit(this);
-        if(op.getRequestedParallelism() > curMROp.requestedParallelism)
-            curMROp.requestedParallelism = op.getRequestedParallelism();
+        if(op.getRequestedParallelism() > curMROp.requestedParallelism ) {
+        	// we don't want to change prallelism for skewed join due to sampling
+        	// and pre-allocated reducers for skewed keys
+        	if (!curMROp.isSkewedJoin()) {
+        		curMROp.requestedParallelism = op.getRequestedParallelism();
+        	}
+        }
         compiledInputs = prevCompInp;
     }
     
@@ -1045,6 +1055,165 @@
             throw new MRCompilerException(msg, errCode, PigException.BUG, e);
         }
     }
+    
+    public void visitSkewedJoin(POSkewedJoin op) throws VisitorException {
+		try {
+			if (compiledInputs.length != 2) {
+				throw new VisitorException("POSkewedJoin operator has " + compiledInputs.length + " inputs. It should have 2.");
+			}
+			
+			FileSpec fSpec = getTempFileSpec();
+			MapReduceOper mro = compiledInputs[0];
+			POStore str = getStore();
+			str.setSFile(fSpec);
+			if (!mro.isMapDone()) {
+				mro.mapPlan.addAsLeaf(str);
+				mro.setMapDoneSingle(true);
+			} else if (mro.isMapDone() && !mro.isReduceDone()) {
+				mro.reducePlan.addAsLeaf(str);
+				mro.setReduceDone(true);
+			} else {
+				int errCode = 2022;
+				String msg = "Both map and reduce phases have been done. This is unexpected while compiling.";
+				throw new PlanException(msg, errCode, PigException.BUG);
+			}
+			
+			FileSpec partitionFile = getTempFileSpec();
+			int rp = op.getRequestedParallelism();
+			
+			Pair<MapReduceOper, Integer> sampleJobPair = getSkewedJoinSampleJob(op, mro, fSpec, partitionFile, rp);            
+			rp = sampleJobPair.second;
+			
+			// set parallelism of SkewedJoin as the value calculated by sampling job
+			// if "parallel" is specified in join statement, "rp" is equal to that number
+			// if not specified, use the value that sampling process calculated
+			// based on default.
+			op.setRequestedParallelism(rp);
+						
+			// load the temp file for first table as input of join            
+			MapReduceOper[] joinInputs = new MapReduceOper[] {startNew(fSpec, sampleJobPair.first), compiledInputs[1]};            
+			MapReduceOper[] rearrangeOutputs = new MapReduceOper[2];                       
+			
+			compiledInputs = new MapReduceOper[] {joinInputs[0]};
+			// run POLocalRearrange for first join table
+			POLocalRearrange lr = new POLocalRearrange(new OperatorKey(scope,nig.getNextNodeId(scope)), rp);            
+			try {
+				lr.setIndex(0);                
+			} catch (ExecException e) {
+				int errCode = 2058;
+				String msg = "Unable to set index on newly created POLocalRearrange.";
+				throw new PlanException(msg, errCode, PigException.BUG, e);
+			}
+			
+			List<PhysicalOperator> l = plan.getPredecessors(op);
+			MultiMap<PhysicalOperator, PhysicalPlan> joinPlans = op.getJoinPlans();
+			List<PhysicalPlan> groups = (List<PhysicalPlan>)joinPlans.get(l.get(0));
+			// check the type of group keys, if there are more than one field, the key is TUPLE.
+			byte type = DataType.TUPLE;
+			if (groups.size() == 1) {
+				type = groups.get(0).getLeaves().get(0).getResultType();                
+			}               
+			
+			lr.setKeyType(type);            
+			lr.setPlans(groups);
+			lr.setResultType(DataType.TUPLE);
+			
+			lr.visit(this);
+			if(lr.getRequestedParallelism() > curMROp.requestedParallelism)
+				curMROp.requestedParallelism = lr.getRequestedParallelism();
+			rearrangeOutputs[0] = curMROp;
+			
+			compiledInputs = new MapReduceOper[] {joinInputs[1]};       
+			// if the map for current input is already closed, then start a new job
+			if (compiledInputs[0].isMapDone() && !compiledInputs[0].isReduceDone()) {
+				FileSpec f = getTempFileSpec();
+				POStore s = getStore();
+				s.setSFile(f);
+				compiledInputs[0].reducePlan.addAsLeaf(s);
+				compiledInputs[0].setReduceDone(true);
+				compiledInputs[0] = startNew(f, compiledInputs[0]);
+			}     		      
+			
+			// run POPartitionRearrange for second join table
+			lr = new POPartitionRearrange(new OperatorKey(scope,nig.getNextNodeId(scope)), rp);            
+			try {
+				lr.setIndex(1);
+			} catch (ExecException e) {
+				int errCode = 2058;
+				String msg = "Unable to set index on newly created POLocalRearrange.";
+				throw new PlanException(msg, errCode, PigException.BUG, e);
+			}               
+			((POPartitionRearrange)lr).setPartitionFile(partitionFile.getFileName());
+			
+			groups = (List<PhysicalPlan>)joinPlans.get(l.get(1));
+			lr.setPlans(groups);
+			lr.setKeyType(type);            
+			lr.setResultType(DataType.BAG);
+			
+			lr.visit(this);
+			if(lr.getRequestedParallelism() > curMROp.requestedParallelism)
+				curMROp.requestedParallelism = lr.getRequestedParallelism();
+			rearrangeOutputs[1] = curMROp;                     
+			compiledInputs = rearrangeOutputs;
+					   
+			
+			// create POGlobalRearrange
+			POGlobalRearrange gr = new POGlobalRearrange(new OperatorKey(scope,nig.getNextNodeId(scope)), rp);                          
+			gr.setResultType(DataType.TUPLE);
+			gr.visit(this);
+			if(gr.getRequestedParallelism() > curMROp.requestedParallelism)
+				curMROp.requestedParallelism = gr.getRequestedParallelism();
+			compiledInputs = new MapReduceOper[] {curMROp};
+			
+			// create POPakcage
+			POPackage pkg = new POPackage(new OperatorKey(scope,nig.getNextNodeId(scope)), rp);
+			pkg.setKeyType(type);
+			pkg.setResultType(DataType.TUPLE);
+			pkg.setNumInps(2);
+			boolean[] inner = {true, true}; 
+			pkg.setInner(inner);            
+			pkg.visit(this);       
+			compiledInputs = new MapReduceOper[] {curMROp};
+			
+			// create POForEach
+			List<PhysicalPlan> eps = new ArrayList<PhysicalPlan>();
+			List<Boolean> flat = new ArrayList<Boolean>();
+			
+			PhysicalPlan ep = new PhysicalPlan();
+			POProject prj = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+			prj.setColumn(1);
+			prj.setOverloaded(false);
+			prj.setResultType(DataType.BAG);
+			ep.add(prj);
+			eps.add(ep);
+			flat.add(true);
+
+			ep = new PhysicalPlan();
+			prj = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+			prj.setColumn(2);
+			prj.setOverloaded(false);
+			prj.setResultType(DataType.BAG);
+			ep.add(prj);
+			eps.add(ep);
+			flat.add(true);
+
+			POForEach fe = new POForEach(new OperatorKey(scope,nig.getNextNodeId(scope)), -1, eps, flat);
+			fe.setResultType(DataType.TUPLE);
+			
+			fe.visit(this);
+			
+			curMROp.setSkewedJoinPartitionFile(partitionFile.getFileName());
+        }catch(PlanException e) {
+            int errCode = 2034;
+            String msg = "Error compiling operator " + op.getClass().getSimpleName();
+            throw new MRCompilerException(msg, errCode, PigException.BUG, e);
+        }catch(IOException e) {
+            int errCode = 2034;
+            String msg = "Error compiling operator " + op.getClass().getSimpleName();
+            throw new MRCompilerException(msg, errCode, PigException.BUG, e);
+        }
+
+    }
 
     @Override
     public void visitSort(POSort op) throws VisitorException {
@@ -1053,7 +1222,7 @@
             MapReduceOper mro = endSingleInputPlanWithStr(fSpec);
             FileSpec quantFile = getTempFileSpec();
             int rp = op.getRequestedParallelism();
-            Pair<Integer,Byte>[] fields = getSortCols(op);
+            Pair<Integer,Byte>[] fields = getSortCols(op.getSortPlans());
             Pair<MapReduceOper, Integer> quantJobParallelismPair = 
                 getQuantileJob(op, mro, fSpec, quantFile, rp, fields);
             curMROp = getSortJob(op, quantJobParallelismPair.first, fSpec, quantFile, 
@@ -1069,8 +1238,7 @@
         }
     }
     
-    private Pair<Integer, Byte>[] getSortCols(POSort sort) throws PlanException, ExecException {
-        List<PhysicalPlan> plans = sort.getSortPlans();
+    private Pair<Integer, Byte>[] getSortCols(List<PhysicalPlan> plans) throws PlanException, ExecException {
         if(plans!=null){
             Pair[] ret = new Pair[plans.size()]; 
             int i=-1;
@@ -1175,10 +1343,10 @@
         mro.setMapDone(true);
         
         if (limit!=-1) {
-       	    POPackageLite pkg_c = new POPackageLite(new OperatorKey(scope,nig.getNextNodeId(scope)));
-       	    pkg_c.setKeyType((fields.length>1) ? DataType.TUPLE : keyType);
+        	POPackageLite pkg_c = new POPackageLite(new OperatorKey(scope,nig.getNextNodeId(scope)));
+        	pkg_c.setKeyType((fields.length>1) ? DataType.TUPLE : keyType);
             pkg_c.setNumInps(1);
-            //pkg.setResultType(DataType.TUPLE);
+            //pkg.setResultType(DataType.TUPLE);            
             mro.combinePlan.add(pkg_c);
         	
             List<PhysicalPlan> eps_c1 = new ArrayList<PhysicalPlan>();
@@ -1220,7 +1388,7 @@
         POPackageLite pkg = new POPackageLite(new OperatorKey(scope,nig.getNextNodeId(scope)));
         pkg.setKeyType((fields == null || fields.length>1) ? DataType.TUPLE :
             keyType);
-        pkg.setNumInps(1);
+        pkg.setNumInps(1);       
         mro.reducePlan.add(pkg);
         
         PhysicalPlan ep = new PhysicalPlan();
@@ -1255,7 +1423,117 @@
             FileSpec quantFile,
             int rp,
             Pair<Integer,Byte>[] fields) throws PlanException, VisitorException {
-        String[] rslargs = new String[2];
+        
+        POSort sort = new POSort(inpSort.getOperatorKey(), inpSort
+                .getRequestedParallelism(), null, inpSort.getSortPlans(),
+                inpSort.getMAscCols(), inpSort.getMSortFunc());
+    	
+    	// Turn the asc/desc array into an array of strings so that we can pass it
+        // to the FindQuantiles function.
+        List<Boolean> ascCols = inpSort.getMAscCols();
+        String[] ascs = new String[ascCols.size()];
+        for (int i = 0; i < ascCols.size(); i++) ascs[i] = ascCols.get(i).toString();
+        // check if user defined comparator is used in the sort, if so
+        // prepend the name of the comparator as the first fields in the
+        // constructor args array to the FindQuantiles udf
+        String[] ctorArgs = ascs;
+        if(sort.isUDFComparatorUsed) {
+            String userComparatorFuncSpec = sort.getMSortFunc().getFuncSpec().toString();
+            ctorArgs = new String[ascs.length + 1];
+            ctorArgs[0] = USER_COMPARATOR_MARKER + userComparatorFuncSpec;
+            for(int j = 0; j < ascs.length; j++) {
+                ctorArgs[j+1] = ascs[j];
+            }
+        }
+        
+        return getSamplingJob(sort, prevJob, null, lFile, quantFile, rp, null, FindQuantiles.class.getName(), ctorArgs);
+    }
+    
+    /**
+     * Create Sampling job for skewed join.
+     */
+    public Pair<MapReduceOper, Integer> getSkewedJoinSampleJob(POSkewedJoin op, MapReduceOper prevJob, 
+    		FileSpec lFile, FileSpec sampleFile, int rp ) throws PlanException, VisitorException {
+    	    	
+    	MultiMap<PhysicalOperator, PhysicalPlan> joinPlans = op.getJoinPlans();
+    	
+    	List<PhysicalOperator> l = plan.getPredecessors(op);
+    	List<PhysicalPlan> groups = (List<PhysicalPlan>)joinPlans.get(l.get(0));
+    	
+    	
+    	List<Boolean> ascCol = new ArrayList<Boolean>();
+    	for(int i=0; i<groups.size(); i++) {    		    		
+    		ascCol.add(false);
+    	}
+    	
+    	POSort sort = new POSort(op.getOperatorKey(), op.getRequestedParallelism(), null, groups, ascCol, null);
+    	
+    	// set up transform plan to get keys and memory size of input tuples
+    	// it first adds all the plans to get key columns,
+    	List<PhysicalPlan> transformPlans = new ArrayList<PhysicalPlan>(); 
+    	transformPlans.addAll(groups);
+        
+    	// then it adds a column for memory size
+    	POProject prjStar = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+        prjStar.setResultType(DataType.TUPLE);
+        prjStar.setStar(true);            
+        
+        List<PhysicalOperator> ufInps = new ArrayList<PhysicalOperator>();
+        ufInps.add(prjStar);
+        
+    	PhysicalPlan ep = new PhysicalPlan();
+    	POUserFunc uf = new POUserFunc(new OperatorKey(scope,nig.getNextNodeId(scope)), -1, ufInps,
+    	            new FuncSpec(TupleSize.class.getName(), (String[])null));
+    	uf.setResultType(DataType.TUPLE);
+    	ep.add(uf);     
+    	ep.add(prjStar);
+    	ep.connect(prjStar, uf);
+        	
+        transformPlans.add(ep);      
+        
+    	try{    		
+    		// pass configurations to the User Function
+    		String per = pigContext.getProperties().getProperty("pig.skewedjoin.reduce.memusage", "0.5");
+    		String mc = pigContext.getProperties().getProperty("pig.skewedjoin.reduce.maxtuple", "0");
+    		String inputFile = lFile.getFileName();
+    		    		
+    		return getSamplingJob(sort, prevJob, transformPlans, lFile, sampleFile, rp, null, 
+    							PartitionSkewedKeys.class.getName(), new String[]{per, mc, inputFile});
+    	}catch(Exception e) {
+    		throw new PlanException(e);
+    	}
+    }    	 
+  
+  	
+    /**
+     * Create a sampling job to collect statistics by sampling an input file. The sequence of operations is as
+     * following:
+     * <li>Transform input sample tuples into another tuple.</li>
+     * <li>Add an extra field &quot;all&quot; into the tuple </li>
+     * <li>Package all tuples into one bag </li>
+     * <li>Add constant field for number of reducers. </li>
+     * <li>Sorting the bag </li>
+     * <li>Invoke UDF with the number of reducers and the sorted bag.</li>
+     * <li>Data generated by UDF is stored into a file.</li>
+     * 
+     * @param sort  the POSort operator used to sort the bag
+     * @param prevJob  previous job of current sampling job
+     * @param transformPlans  PhysicalPlans to transform input samples
+     * @param lFile  path of input file
+     * @param sampleFile  path of output file
+     * @param rp  configured parallemism
+     * @param sortKeyPlans  PhysicalPlans to be set into POSort operator to get sorting keys
+     * @param udfClassName  the class name of UDF
+     * @param udfArgs   the arguments of UDF
+     * @return pair<mapreduceoper,integer>
+     * @throws PlanException
+     * @throws VisitorException
+     */
+  	protected Pair<MapReduceOper,Integer> getSamplingJob(POSort sort, MapReduceOper prevJob, List<PhysicalPlan> transformPlans,
+  			FileSpec lFile, FileSpec sampleFile, int rp, List<PhysicalPlan> sortKeyPlans, 
+  			String udfClassName, String[] udfArgs ) throws PlanException, VisitorException {
+  		
+  		String[] rslargs = new String[2];
         // RandomSampleLoader expects string version of FuncSpec 
         // as its first constructor argument.
         rslargs[0] = (new FuncSpec(BinStorage.class.getName())).toString();
@@ -1263,38 +1541,52 @@
         FileSpec quantLdFilName = new FileSpec(lFile.getFileName(),
             new FuncSpec(RandomSampleLoader.class.getName(), rslargs));
         MapReduceOper mro = startNew(quantLdFilName, prevJob);
-        POSort sort = new POSort(inpSort.getOperatorKey(), inpSort
-                .getRequestedParallelism(), null, inpSort.getSortPlans(),
-                inpSort.getMAscCols(), inpSort.getMSortFunc());
+       
         if(sort.isUDFComparatorUsed) {
             mro.UDFs.add(sort.getMSortFunc().getFuncSpec().toString());
-        }
-        
+        }        
+    
+        List<Boolean> flat1 = new ArrayList<Boolean>();         
         List<PhysicalPlan> eps1 = new ArrayList<PhysicalPlan>();
-        List<Boolean> flat1 = new ArrayList<Boolean>();
-        // Set up the projections of the key columns 
-        if (fields == null) {
-            PhysicalPlan ep = new PhysicalPlan();
-            POProject prj = new POProject(new OperatorKey(scope,
-                nig.getNextNodeId(scope)));
-            prj.setStar(true);
-            prj.setOverloaded(false);
-            prj.setResultType(DataType.TUPLE);
-            ep.add(prj);
-            eps1.add(ep);
-            flat1.add(true);
-        } else {
-            for (Pair<Integer,Byte> i : fields) {
+        
+        // if transform plans are not specified, project the columns of sorting keys
+        if (transformPlans == null) {        	
+        	Pair<Integer,Byte>[] fields = null;
+            try{
+            	fields = getSortCols(sort.getSortPlans());
+            }catch(Exception e) {
+            	throw new RuntimeException(e);
+            }
+            // Set up the projections of the key columns 
+            if (fields == null) {
                 PhysicalPlan ep = new PhysicalPlan();
-                POProject prj = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
-                prj.setColumn(i.first);
+                POProject prj = new POProject(new OperatorKey(scope,
+                    nig.getNextNodeId(scope)));
+                prj.setStar(true);
                 prj.setOverloaded(false);
-                prj.setResultType(i.second);
+                prj.setResultType(DataType.TUPLE);
                 ep.add(prj);
                 eps1.add(ep);
                 flat1.add(true);
+            } else {
+                for (Pair<Integer,Byte> i : fields) {
+                    PhysicalPlan ep = new PhysicalPlan();
+                    POProject prj = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+                    prj.setColumn(i.first);
+                    prj.setOverloaded(false);
+                    prj.setResultType(i.second);
+                    ep.add(prj);
+                    eps1.add(ep);
+                    flat1.add(true);
+                }
             }
+        }else{
+        	for(int i=0; i<transformPlans.size(); i++) {
+        		eps1.add(transformPlans.get(i));
+        		flat1.add(true);
+        	}
         }
+        
         // This foreach will pick the sort key columns from the RandomSampleLoader output 
         POForEach nfe1 = new POForEach(new OperatorKey(scope,nig.getNextNodeId(scope)),-1,eps1,flat1);
         mro.mapPlan.addAsLeaf(nfe1);
@@ -1345,26 +1637,39 @@
         fe2Plan.add(topPrj);
         
         // the projections which will form sort plans
-        List<PhysicalPlan> nesSortPlanLst = new ArrayList<PhysicalPlan>();
-        if (fields == null) {
-            PhysicalPlan ep = new PhysicalPlan();
-            POProject prj = new POProject(new OperatorKey(scope,
-                nig.getNextNodeId(scope)));
-            prj.setStar(true);
-            prj.setOverloaded(false);
-            prj.setResultType(DataType.TUPLE);
-            ep.add(prj);
-            nesSortPlanLst.add(ep);
-        } else {
-            for (int i=0; i<fields.length;i++) {
+        List<PhysicalPlan> nesSortPlanLst = new ArrayList<PhysicalPlan>();             
+        if (sortKeyPlans != null) {
+        	for(int i=0; i<sortKeyPlans.size(); i++) {        	
+        		nesSortPlanLst.add(sortKeyPlans.get(i));        	
+        	}
+        }else{   
+        	Pair<Integer,Byte>[] fields = null;
+            try{
+            	fields = getSortCols(sort.getSortPlans());
+            }catch(Exception e) {
+            	throw new RuntimeException(e);
+            }
+            // Set up the projections of the key columns 
+            if (fields == null) {
                 PhysicalPlan ep = new PhysicalPlan();
-                POProject prj = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
-                prj.setColumn(i);
+                POProject prj = new POProject(new OperatorKey(scope,
+                    nig.getNextNodeId(scope)));
+                prj.setStar(true);
                 prj.setOverloaded(false);
-                prj.setResultType(fields[i].second);
+                prj.setResultType(DataType.TUPLE);
                 ep.add(prj);
                 nesSortPlanLst.add(ep);
-            }
+            } else {
+                for (int i=0; i<fields.length; i++) {
+                    PhysicalPlan ep = new PhysicalPlan();
+                    POProject prj = new POProject(new OperatorKey(scope,nig.getNextNodeId(scope)));
+                    prj.setColumn(i);
+                    prj.setOverloaded(false);
+                    prj.setResultType(fields[i].second);
+                    ep.add(prj);
+                    nesSortPlanLst.add(ep);
+                }
+            }                       
         }
         
         sort.setSortPlans(nesSortPlanLst);
@@ -1428,26 +1733,9 @@
         
         List<PhysicalOperator> ufInps = new ArrayList<PhysicalOperator>();
         ufInps.add(prjStar4);
-        // Turn the asc/desc array into an array of strings so that we can pass it
-        // to the FindQuantiles function.
-        List<Boolean> ascCols = inpSort.getMAscCols();
-        String[] ascs = new String[ascCols.size()];
-        for (int i = 0; i < ascCols.size(); i++) ascs[i] = ascCols.get(i).toString();
-        // check if user defined comparator is used in the sort, if so
-        // prepend the name of the comparator as the first fields in the
-        // constructor args array to the FindQuantiles udf
-        String[] ctorArgs = ascs;
-        if(sort.isUDFComparatorUsed) {
-            String userComparatorFuncSpec = sort.getMSortFunc().getFuncSpec().toString();
-            ctorArgs = new String[ascs.length + 1];
-            ctorArgs[0] = USER_COMPARATOR_MARKER + userComparatorFuncSpec;
-            for(int j = 0; j < ascs.length; j++) {
-                ctorArgs[j+1] = ascs[j];
-            }
-        }
-        
+      
         POUserFunc uf = new POUserFunc(new OperatorKey(scope,nig.getNextNodeId(scope)), -1, ufInps, 
-            new FuncSpec(FindQuantiles.class.getName(), ctorArgs));
+            new FuncSpec(udfClassName, udfArgs));
         ep4.add(uf);
         ep4.connect(prjStar4, uf);
         
@@ -1461,7 +1749,8 @@
         mro.reducePlan.connect(nfe2, nfe3);
         
         POStore str = getStore();
-        str.setSFile(quantFile);
+        str.setSFile(sampleFile);
+        
         mro.reducePlan.add(str);
         mro.reducePlan.connect(nfe3, str);
         

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceLauncher.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceLauncher.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceLauncher.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceLauncher.java Thu Jul 30 00:30:25 2009
@@ -325,7 +325,7 @@
         // Optimize the jobs that have a load/store only first MR job followed
         // by a sample job.
         SampleOptimizer so = new SampleOptimizer(plan);
-        so.visit();
+        so.visit();            
         
         // optimize key - value handling in package
         POPackageAnnotator pkgAnnotator = new POPackageAnnotator(plan);

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceOper.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceOper.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceOper.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/MapReduceOper.java Thu Jul 30 00:30:25 2009
@@ -21,6 +21,7 @@
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.List;
+import java.util.Properties;
 
 import org.apache.pig.impl.io.FileSpec;
 import org.apache.pig.impl.plan.OperatorKey;
@@ -98,6 +99,7 @@
 
     private String scope;
     
+    
     //Fragment Replicate Join State
     boolean frjoin = false;
     FileSpec[] replFiles = null;
@@ -113,6 +115,13 @@
     // That is, this MROper ends due to a POSPlit operator.
     private boolean splitter = false;
 
+	// Set to true if it is skewed join
+	private boolean skewedJoin = false;
+
+    // Name of the partition file generated by sampling process,
+    // Used by Skewed Join
+	private String skewedJoinPartitionFile;
+
     public MapReduceOper(OperatorKey k) {
         super(k);
         mapPlan = new PhysicalPlan();
@@ -235,6 +244,26 @@
     public boolean isGlobalSort() {
         return globalSort;
     }
+    
+    public boolean isSkewedJoin() {
+    	return (skewedJoinPartitionFile != null);
+    }
+    
+    public void setSkewedJoinPartitionFile(String file) {    	
+    	skewedJoinPartitionFile = file;
+    }
+    
+    public String getSkewedJoinPartitionFile() {
+    	return skewedJoinPartitionFile;
+    }
+
+	public void setSkewedJoin(boolean skJoin) {
+		this.skewedJoin = skJoin;
+	}
+
+	public boolean getSkewedJoin() {
+		return skewedJoin;
+	}
 
     public void setGlobalSort(boolean globalSort) {
         this.globalSort = globalSort;

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PhyPlanSetter.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PhyPlanSetter.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PhyPlanSetter.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PhyPlanSetter.java Thu Jul 30 00:30:25 2009
@@ -250,6 +250,11 @@
     public void visitFRJoin(POFRJoin join) throws VisitorException {
         join.setParentPlan(parent);
     }
+    
+    @Override
+    public void visitSkewedJoin(POSkewedJoin join) throws VisitorException {
+        join.setParentPlan(parent);
+    }   
 
     @Override
     public void visitStream(POStream stream) throws VisitorException {
@@ -273,6 +278,13 @@
         lrfi.setParentPlan(parent);
     }
 
+/*
+    @Override
+    public void visitPartitionRearrange(POPartitionRearrange lrfi) throws VisitorException {
+        super.visitPartitionRearrange(lrfi);
+        lrfi.setParentPlan(parent);
+    }
+*/
     @Override
     public void visitPOOptimizedForEach(POOptimizedForEach optimizedForEach) {
         optimizedForEach.setParentPlan(parent);

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapBase.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapBase.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapBase.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapBase.java Thu Jul 30 00:30:25 2009
@@ -241,7 +241,7 @@
         }
     }
 
-    private void runPipeline(PhysicalOperator leaf) throws IOException, ExecException {
+    protected void runPipeline(PhysicalOperator leaf) throws IOException, ExecException {
         while(true){
             Result res = leaf.getNext(DUMMYTUPLE);
             if(res.returnStatus==POStatus.STATUS_OK){

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapReduce.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapReduce.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapReduce.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/PigMapReduce.java Thu Jul 30 00:30:25 2009
@@ -58,6 +58,9 @@
 import org.apache.pig.impl.util.SpillableMemoryManager;
 import org.apache.pig.impl.util.WrappedIOException;
 
+import org.apache.pig.data.DataBag;
+import org.apache.pig.impl.io.NullablePartitionWritable;
+
 /**
  * This class is the static Mapper &amp; Reducer classes that
  * are used by Pig to execute Pig Map Reduce jobs. Since
@@ -140,6 +143,97 @@
         }
     }
 
+	/**
+	 * Used by Skewed Join
+	 */
+    public static class MapWithPartitionIndex extends Map implements
+            Mapper<Text, Tuple, PigNullableWritable, Writable> {    	
+
+        @Override
+        public void collect(OutputCollector<PigNullableWritable, Writable> oc, Tuple tuple) throws ExecException, IOException {			
+			Byte tupleKeyIdx = 2;
+			Byte tupleValIdx = 3;
+
+            Byte index = (Byte)tuple.get(0);
+			Byte partitionIndex = -1;
+        	// for partitioning table, the partition index isn't present
+			if (tuple.size() == 3) {
+				//super.collect(oc, tuple);
+				//return;
+				tupleKeyIdx--;
+				tupleValIdx--;
+			} else {
+				partitionIndex = (Byte)tuple.get(1);
+			}
+
+            PigNullableWritable key =
+                HDataType.getWritableComparableTypes(tuple.get(tupleKeyIdx), DataType.TUPLE);
+
+			NullablePartitionWritable wrappedKey = new NullablePartitionWritable(key);
+			//key.setIndex(index);
+			//NullableTuple wrappedKey = new NullableTuple((Tuple)tuple);
+
+			NullableTuple val = new NullableTuple((Tuple)tuple.get(tupleValIdx));
+            // Both the key and the value need the index.  The key needs it so
+            // that it can be sorted on the index in addition to the key
+            // value.  The value needs it so that POPackage can properly
+            // assign the tuple to its slot in the projection.
+            wrappedKey.setIndex(index);
+			// set the partition
+			wrappedKey.setPartition(partitionIndex);
+			val.setIndex(index);
+            oc.collect(wrappedKey, val);
+            //oc.collect(key, val);
+        }
+
+		@Override
+		protected void runPipeline(PhysicalOperator leaf) throws IOException, ExecException {			
+			while(true){								
+				Result res = leaf.getNext(DUMMYTUPLE);
+				
+				if(res.returnStatus==POStatus.STATUS_OK){
+					// For POPartitionRearrange, the result is a bag. This operator is used for 
+					// skewed join
+					if (res.result instanceof DataBag) {					
+						Iterator<Tuple> its = ((DataBag)res.result).iterator();
+						while(its.hasNext()) {																
+							collect(outputCollector, its.next());
+						}
+					}else{											
+						collect(outputCollector, (Tuple)res.result);
+					}
+					continue;
+				}
+				
+				if(res.returnStatus==POStatus.STATUS_EOP) {
+					return;
+				}
+				
+				if(res.returnStatus==POStatus.STATUS_NULL)
+					continue;
+				
+				if(res.returnStatus==POStatus.STATUS_ERR){
+					// remember that we had an issue so that in 
+					// close() we can do the right thing
+					errorInMap  = true;
+					// if there is an errmessage use it
+					String errMsg;
+					if(res.result != null) {
+						errMsg = "Received Error while " +
+						"processing the map plan: " + res.result;
+					} else {
+						errMsg = "Received Error while " +
+						"processing the map plan.";
+					}
+						
+					int errCode = 2055;
+					ExecException ee = new ExecException(errMsg, errCode, PigException.BUG);
+					throw ee;
+				}
+			}
+		}
+	}
+
     public static class Reduce extends MapReduceBase
             implements
             Reducer<PigNullableWritable, NullableTuple, PigNullableWritable, Writable> {
@@ -321,7 +415,7 @@
             {
                 Result redRes = leaf.getNext(DUMMYTUPLE);
                 if(redRes.returnStatus==POStatus.STATUS_OK){
-                    outputCollector.collect(null, (Tuple)redRes.result);
+                   	outputCollector.collect(null, (Tuple)redRes.result);
                     continue;
                 }
                 

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/SampleOptimizer.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/SampleOptimizer.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/SampleOptimizer.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/SampleOptimizer.java Thu Jul 30 00:30:25 2009
@@ -29,6 +29,9 @@
 import org.apache.pig.backend.hadoop.executionengine.mapReduceLayer.plans.MROpPlanVisitor;
 import org.apache.pig.backend.hadoop.executionengine.mapReduceLayer.plans.MROperPlan;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.PhysicalOperator;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.expressionOperators.POUserFunc;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.plans.PhysicalPlan;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POForEach;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.POLoad;
 import org.apache.pig.impl.PigContext;
 import org.apache.pig.impl.builtin.RandomSampleLoader;
@@ -179,6 +182,12 @@
         POLoad newLoad = new POLoad(load.getOperatorKey(),load.getRequestedParallelism(), fs, load.isSplittable());
         try {
             mr.mapPlan.replace(load, newLoad);
+            
+            // check if it has PartitionSkewedKeys
+            List<PhysicalOperator> ls = mr.reducePlan.getLeaves();
+            for(PhysicalOperator op: ls) {
+            	scan(mr, op, fs.getFileName());
+            }        
         } catch (PlanException e) {
             throw new VisitorException(e);
         }
@@ -197,4 +206,36 @@
         opsToRemove.add(pred);
     }
 
+    // search for PartionSkewedKeys and update input file name
+    // it is always under a POForEach operator in reduce plan
+    private void scan(MapReduceOper mr, PhysicalOperator op, String fileName) {
+    	
+		if (op instanceof POUserFunc) {
+			if (((POUserFunc)op).getFuncSpec().getClassName().equals(
+					"org.apache.pig.impl.builtin.PartitionSkewedKeys")) {
+				
+				String[] ctorArgs = ((POUserFunc)op).getFuncSpec().getCtorArgs();
+				ctorArgs[2] = fileName;    		
+				return;
+			}
+		}else if (op instanceof POForEach) {
+			List<PhysicalPlan> pl = ((POForEach)op).getInputPlans();
+			for(PhysicalPlan plan: pl) {
+				List<PhysicalOperator> list = plan.getLeaves();
+				for (PhysicalOperator pp: list) {
+					scan(mr, pp, fileName);
+				}
+			}
+		}else{
+			List<PhysicalOperator> preds = mr.reducePlan.getPredecessors(op);
+	    	
+	    	if (preds == null) {
+	    		return;
+	    	}
+	    	
+	    	for(PhysicalOperator p: preds) {	    		    	
+	    		scan(mr, p, fileName);	    		
+	    	}
+		}
+    }
 }

Added: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/partitioners/SkewedPartitioner.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/partitioners/SkewedPartitioner.java?rev=799141&view=auto
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/partitioners/SkewedPartitioner.java (added)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/mapReduceLayer/partitioners/SkewedPartitioner.java Thu Jul 30 00:30:25 2009
@@ -0,0 +1,132 @@
+/*
+ * 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.backend.hadoop.executionengine.mapReduceLayer.partitioners;
+
+
+import java.io.InputStream;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Map.Entry;
+
+import org.apache.hadoop.io.RawComparator;
+import org.apache.hadoop.io.Writable;
+import org.apache.hadoop.mapred.JobConf;
+import org.apache.hadoop.mapred.Partitioner;
+import org.apache.pig.backend.executionengine.ExecException;
+import org.apache.pig.backend.hadoop.HDataType;
+import org.apache.pig.backend.hadoop.datastorage.ConfigurationUtil;
+import org.apache.pig.builtin.BinStorage;
+import org.apache.pig.data.DataBag;
+import org.apache.pig.data.Tuple;
+import org.apache.pig.data.TupleFactory;
+import org.apache.pig.impl.builtin.FindQuantiles;
+import org.apache.pig.impl.io.BufferedPositionedInputStream;
+import org.apache.pig.impl.io.FileLocalizer;
+import org.apache.pig.impl.io.NullableBytesWritable;
+import org.apache.pig.impl.io.NullableDoubleWritable;
+import org.apache.pig.impl.io.NullableFloatWritable;
+import org.apache.pig.impl.io.NullableIntWritable;
+import org.apache.pig.impl.io.NullableLongWritable;
+import org.apache.pig.impl.io.NullableText;
+import org.apache.pig.impl.io.NullableTuple;
+import org.apache.pig.impl.io.PigNullableWritable;
+import org.apache.pig.impl.io.NullablePartitionWritable;
+
+import org.apache.pig.impl.util.Pair;
+import org.apache.pig.data.DefaultTupleFactory;
+import org.apache.pig.data.DataType;
+import org.apache.pig.backend.hadoop.executionengine.util.MapRedUtil;
+
+
+/**
+  * This class is used by skewed join. For the partitioned table, the skewedpartitioner reads the key
+  * distribution data from the sampler file and returns the reducer index in a round robin fashion.
+  * For ex: if the key distribution file contains (k1, 5, 3) as an entry, reducers from 5 to 3 are returned 
+  * in a round robin manner.
+  */ 
+public class SkewedPartitioner implements Partitioner<PigNullableWritable, Writable> {
+	Map<Tuple, Pair<Integer, Integer> > reducerMap = new HashMap<Tuple, Pair<Integer, Integer> >();
+	static Map<Tuple, Integer> currentIndexMap = new HashMap<Tuple, Integer> ();
+	Integer totalReducers;
+
+    public int getPartition(PigNullableWritable wrappedKey, Writable value,
+            int numPartitions) {
+		// for streaming tables, return the partition index blindly
+		if (wrappedKey instanceof NullablePartitionWritable && ((int)((NullablePartitionWritable)wrappedKey).getPartition()) != -1) {
+			return (int) ((NullablePartitionWritable)wrappedKey).getPartition();
+		}
+
+		// for partition table, compute the index based on the sampler output
+		Pair <Integer, Integer> indexes;
+		Integer curIndex = -1;
+		Tuple keyTuple = null;
+		
+		// extract the key from nullablepartitionwritable
+		PigNullableWritable key = ((NullablePartitionWritable) wrappedKey).getKey();
+
+		if (key instanceof NullableTuple) {
+			keyTuple = (Tuple)key.getValueAsPigType();
+		} else {
+			keyTuple = DefaultTupleFactory.getInstance().newTuple(1);
+			try {
+				keyTuple.set(0, key);
+			} catch (ExecException e) {
+				return -1;
+			}
+		}
+
+		indexes = reducerMap.get(keyTuple);
+		// if the reducerMap does not contain the key, do the default hash based partitioning
+		if (indexes == null) {
+			return (Math.abs(keyTuple.hashCode()) % totalReducers);
+		}
+
+		if (currentIndexMap.containsKey(keyTuple)) {
+	    	curIndex = currentIndexMap.get(keyTuple);
+		}
+		
+		if (curIndex >= (indexes.first + indexes.second) || curIndex == -1) {
+			curIndex = indexes.first;
+		} else {
+			curIndex++;
+		}
+		
+		// set it in the map
+		currentIndexMap.put(keyTuple, curIndex);
+		return (curIndex % totalReducers);
+	}
+
+    @SuppressWarnings("unchecked")
+    public void configure(JobConf job) {
+        String keyDistFile = job.get("pig.keyDistFile", "");
+        if (keyDistFile.length() == 0)
+            throw new RuntimeException(this.getClass().getSimpleName() + " used but no key distribution found");
+
+		try {
+			Integer [] redCnt = new Integer[1]; 
+			reducerMap = MapRedUtil.loadPartitionFile(keyDistFile, redCnt, job, DataType.TUPLE);
+			totalReducers = redCnt[0];
+		} catch (Exception e) {
+			throw new RuntimeException(e);
+		}
+	}
+
+}

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/LogToPhyTranslationVisitor.java Thu Jul 30 00:30:25 2009
@@ -55,6 +55,9 @@
 import org.apache.pig.impl.plan.PlanWalker;
 import org.apache.pig.impl.plan.VisitorException;
 
+
+import org.apache.pig.impl.util.MultiMap;
+
 public class LogToPhyTranslationVisitor extends LOVisitor {
 
     protected Map<LogicalOperator, PhysicalOperator> LogToPhyMap;
@@ -720,7 +723,65 @@
         LogToPhyMap.put(cg, poPackage);
     }
     
-    
+	/**
+     * Create the inner plans used to configure the Partition rearrange operators
+     */
+	@Override
+	protected void visit(LOJoin loj) throws VisitorException {
+        List<LogicalOperator> inputs = loj.getInputs();
+        MultiMap<PhysicalOperator, PhysicalPlan> joinPlans = new MultiMap<PhysicalOperator, PhysicalPlan>();
+
+        List<PhysicalOperator> inp = new ArrayList<PhysicalOperator>();
+        for (LogicalOperator op : inputs) {
+			PhysicalOperator physOp = LogToPhyMap.get(op);
+            inp.add(physOp);
+            List<LogicalPlan> plans = (List<LogicalPlan>) loj.getJoinPlans().get(op);
+            
+            List<PhysicalPlan> exprPlans = new ArrayList<PhysicalPlan>();
+            currentPlans.push(currentPlan);
+            for (LogicalPlan lp : plans) {
+                currentPlan = new PhysicalPlan();
+                PlanWalker<LogicalOperator, LogicalPlan> childWalker = mCurrentWalker.spawnChildWalker(lp);
+                pushWalker(childWalker);
+                mCurrentWalker.walk(this);
+                exprPlans.add(currentPlan);
+                popWalker();
+            }
+            currentPlan = currentPlans.pop();
+			joinPlans.put(physOp, exprPlans);
+		}
+
+		// For skewed join, add a local rearrange operator to the plan
+		if (loj.getJoinType() == LOJoin.JOINTYPE.SKEWED) {
+			POSkewedJoin skj;
+			try {
+				String scope = loj.getOperatorKey().scope;
+				skj = new POSkewedJoin(new OperatorKey(scope,nodeGen.getNextNodeId(scope)),loj.getRequestedParallelism(),
+											inp);
+				skj.setJoinPlans(joinPlans);
+			}
+			catch (Exception e) {
+				int errCode = 2015;
+				String msg = "Skewed Join creation failed";
+				throw new LogicalToPhysicalTranslatorException(msg, errCode, PigException.BUG, e);
+			}
+			skj.setResultType(DataType.TUPLE);
+			currentPlan.add(skj);
+
+			for (LogicalOperator op : inputs) {
+				try {
+					currentPlan.connect(LogToPhyMap.get(op), skj);
+				} catch (PlanException e) {
+					int errCode = 2015;
+					String msg = "Invalid physical operators in the physical plan" ;
+					throw new LogicalToPhysicalTranslatorException(msg, errCode, PigException.BUG, e);
+				}
+			}
+			LogToPhyMap.put(loj, skj);
+		}
+	}
+
+
     /**
      * Create the inner plans used to configure the Local Rearrange operators(ppLists)
      * Extract the keytypes and create the POFRJoin operator.

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/DotPOPrinter.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/DotPOPrinter.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/DotPOPrinter.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/DotPOPrinter.java Thu Jul 30 00:30:25 2009
@@ -129,6 +129,13 @@
                 }
             }
         }
+        else if(op instanceof POSkewedJoin) {
+        	POSkewedJoin skewed = (POSkewedJoin)op;
+            Collection<PhysicalPlan> joinPlans = skewed.getJoinPlans().values();
+            if(joinPlans!=null) {
+                plans.addAll(joinPlans);
+            }
+        }
 
         return plans;
     }

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhyPlanVisitor.java Thu Jul 30 00:30:25 2009
@@ -263,6 +263,19 @@
 	
     }
 
+	public void visitSkewedJoin(POSkewedJoin sk) throws VisitorException {
+
+	}
+
+	public void visitPartitionRearrange(POPartitionRearrange pr) throws VisitorException {
+        List<PhysicalPlan> inpPlans = pr.getPlans();
+        for (PhysicalPlan plan : inpPlans) {
+            pushWalker(mCurrentWalker.spawnChildWalker(plan));
+            visit();
+            popWalker();
+        }
+	}
+
     /**
      * @param lrfi
      * @throws VisitorException 

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhysicalPlan.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhysicalPlan.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhysicalPlan.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PhysicalPlan.java Thu Jul 30 00:30:25 2009
@@ -59,8 +59,9 @@
     
     public void attachInput(Tuple t){
         List<PhysicalOperator> roots = getRoots();
-        for (PhysicalOperator operator : roots)
+        for (PhysicalOperator operator : roots) {
             operator.attachInput(t);
+		}
     }
     
     /**

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PlanPrinter.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PlanPrinter.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PlanPrinter.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/plans/PlanPrinter.java Thu Jul 30 00:30:25 2009
@@ -29,12 +29,14 @@
 import java.util.Set;
 
 import org.apache.pig.PigException;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.PhysicalOperator;
 import org.apache.pig.backend.hadoop.executionengine.physicalLayer.relationalOperators.*;
 import org.apache.pig.impl.plan.DepthFirstWalker;
 import org.apache.pig.impl.plan.Operator;
 import org.apache.pig.impl.plan.OperatorPlan;
 import org.apache.pig.impl.plan.PlanVisitor;
 import org.apache.pig.impl.plan.VisitorException;
+import org.apache.pig.impl.util.MultiMap;
 
 public class PlanPrinter<O extends Operator, P extends OperatorPlan<O>> extends
         PlanVisitor<O, P> {
@@ -174,6 +176,15 @@
                 sb.append(planString(list));
               }
           }
+          else if(node instanceof POSkewedJoin){
+              POSkewedJoin skewed = (POSkewedJoin)node;
+              MultiMap<PhysicalOperator, PhysicalPlan> joinPlans = skewed.getJoinPlans();
+              if(joinPlans!=null) {
+            	  List<PhysicalPlan> inner_plans = new ArrayList<PhysicalPlan>();
+            	  inner_plans.addAll(joinPlans.values());                
+                  sb.append(planString(inner_plans));                
+              }
+            }
         }
         
         if (node instanceof POSplit) {

Added: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POPartitionRearrange.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POPartitionRearrange.java?rev=799141&view=auto
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POPartitionRearrange.java (added)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POPartitionRearrange.java Thu Jul 30 00:30:25 2009
@@ -0,0 +1,247 @@
+/*
+ * 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.backend.hadoop.executionengine.physicalLayer.relationalOperators;
+
+import java.io.InputStream;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.HashMap;
+import java.util.Iterator;
+
+
+import org.apache.pig.impl.io.BufferedPositionedInputStream;
+import org.apache.pig.impl.io.FileLocalizer;
+import org.apache.pig.builtin.BinStorage;
+
+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.PhysicalOperator;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.POStatus;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.Result;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.expressionOperators.ExpressionOperator;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.plans.PhyPlanVisitor;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.plans.PhysicalPlan;
+import org.apache.pig.impl.plan.OperatorKey;
+import org.apache.pig.impl.plan.NodeIdGenerator;
+import org.apache.pig.impl.plan.PlanException;
+import org.apache.pig.impl.plan.VisitorException;
+import org.apache.pig.data.BagFactory;
+import org.apache.pig.data.DataBag;
+import org.apache.pig.data.TupleFactory;
+
+import org.apache.pig.impl.io.PigNullableWritable;
+import org.apache.pig.backend.hadoop.HDataType;
+import org.apache.pig.data.DataType;
+import org.apache.pig.impl.util.Pair;
+import org.apache.pig.data.DefaultTupleFactory;
+import org.apache.pig.backend.hadoop.executionengine.util.MapRedUtil;
+
+
+/**
+ * The partition rearrange operator is a part of the skewed join 
+ * implementation. It has an embedded physical plan that
+ * generates tuples of the form (inpKey,reducerIndex,(indxed inp Tuple)).
+ *
+ */
+public class POPartitionRearrange extends POLocalRearrange {
+
+    /**
+     * 
+     */
+    private static final long serialVersionUID = 1L;
+	private String partitionFile;
+	private Integer totalReducers = -1;
+	// ReducerMap will store the tuple, max reducer index & min reducer index
+	private static Map<Object, Pair<Integer, Integer> > reducerMap = new HashMap<Object, Pair<Integer, Integer> >();
+	private boolean loaded;
+
+	protected static final BagFactory mBagFactory = BagFactory.getInstance();
+
+    public POPartitionRearrange(OperatorKey k) {
+        this(k, -1, null);
+    }
+
+    public POPartitionRearrange(OperatorKey k, int rp) {
+        this(k, rp, null);
+    }
+
+    public POPartitionRearrange(OperatorKey k, List<PhysicalOperator> inp) {
+        this(k, -1, inp);
+    }
+
+    public POPartitionRearrange(OperatorKey k, int rp, List<PhysicalOperator> inp) {
+        super(k, rp, inp);
+        index = -1;
+        leafOps = new ArrayList<ExpressionOperator>();
+    }
+
+	/* Returns the name for the partition sampling file */
+	public String getPartitionFile() {
+		return partitionFile;
+	}
+
+	/* Set the partition sampling file */
+	public void setPartitionFile(String file) {
+		partitionFile = file;
+	}
+
+	/* Loads the key distribution file obtained from the sampler */
+	private void loadPartitionFile() throws RuntimeException {
+		try {
+			Integer [] redCnt = new Integer[1]; 
+			reducerMap = MapRedUtil.loadPartitionFile(partitionFile, redCnt, null, DataType.NULL);
+			totalReducers = redCnt[0];
+			loaded = true;
+		} catch (Exception e) {
+			throw new RuntimeException(e);
+		}
+	}
+
+    @Override
+    public String name() {
+        return "Partition rearrange " + "[" + DataType.findTypeName(resultType) +
+            "]" + "{" + DataType.findTypeName(keyType) + "}" + "(" +
+            mIsDistinct + ") - " + mKey.toString();
+    }
+
+    /**
+     * Calls getNext on the generate operator inside the nested
+     * physical plan. Converts the generated tuple into the proper
+     * format, i.e, (key,indexedTuple(value))
+     */
+    @Override
+    public Result getNext(Tuple t) throws ExecException {
+        
+        Result inp = null;
+        Result res = null;
+        
+        // Load the skewed join key partitioning file
+        if (!loaded) {
+        	try {
+        		loadPartitionFile();
+        	} catch (Exception e) {
+        		throw new RuntimeException(e);
+        	}
+        }
+		
+        while (true) {
+            inp = processInput();
+            if (inp.returnStatus == POStatus.STATUS_EOP || inp.returnStatus == POStatus.STATUS_ERR)
+                break;
+            if (inp.returnStatus == POStatus.STATUS_NULL)
+                continue;
+            
+            for (PhysicalPlan ep : plans) {
+                ep.attachInput((Tuple)inp.result);
+            }
+            List<Result> resLst = new ArrayList<Result>();
+            for (ExpressionOperator op : leafOps){
+                
+                switch(op.getResultType()){
+                case DataType.BAG:
+                    res = op.getNext(dummyBag);
+                    break;
+                case DataType.BOOLEAN:
+                    res = op.getNext(dummyBool);
+                    break;
+                case DataType.BYTEARRAY:
+                    res = op.getNext(dummyDBA);
+                    break;
+                case DataType.CHARARRAY:
+                    res = op.getNext(dummyString);
+                    break;
+                case DataType.DOUBLE:
+                    res = op.getNext(dummyDouble);
+                    break;
+                case DataType.FLOAT:
+                    res = op.getNext(dummyFloat);
+                    break;
+                case DataType.INTEGER:
+                    res = op.getNext(dummyInt);
+                    break;
+                case DataType.LONG:
+                    res = op.getNext(dummyLong);
+                    break;
+                case DataType.MAP:
+                    res = op.getNext(dummyMap);
+                    break;
+                case DataType.TUPLE:
+                    res = op.getNext(dummyTuple);
+                    break;
+                }
+                if(res.returnStatus!=POStatus.STATUS_OK)
+                    return new Result();
+                resLst.add(res);
+            }
+            res.result = constructPROutput(resLst,(Tuple)inp.result);
+            
+            return res;
+        }
+        return inp;
+    }
+
+	// Returns bag of tuples 
+    protected DataBag constructPROutput(List<Result> resLst, Tuple value) throws ExecException{
+		Tuple t = super.constructLROutput(resLst, value);
+
+        //Construct key
+        Object key = t.get(1);
+        
+		// Construct an output bag and feed in the tuples
+		DataBag opBag = mBagFactory.newDefaultBag();
+
+		//Put the index, key, and value
+		//in a tuple and return
+		Pair <Integer, Integer> indexes = reducerMap.get(key);	// first -> min, second ->max
+	
+		// For non skewed keys, we set the partition index to be -1
+		if (indexes == null) {
+			indexes = new Pair <Integer, Integer>(-1,0);
+		}
+
+		for (Integer reducerIdx=indexes.first, cnt=0; cnt <= indexes.second; reducerIdx++, cnt++) {
+			if (reducerIdx >= totalReducers) {
+				reducerIdx = 0;
+			}
+			Tuple opTuple = mTupleFactory.newTuple(4);
+			opTuple.set(0, t.get(0));
+			// set the partition index
+			opTuple.set(1, reducerIdx.byteValue());
+			opTuple.set(2, key);
+			opTuple.set(3, t.get(2));
+			
+			opBag.add(opTuple);
+		}
+		
+		return opBag;
+    }
+
+    /**
+     * Make a deep copy of this operator.  
+     * @throws CloneNotSupportedException
+     */
+    @Override
+    public POPartitionRearrange clone() throws CloneNotSupportedException {
+		POPartitionRearrange clone = (POPartitionRearrange) super.clone();
+	    //clone.reducerMap = (HashMap)reducerMap.clone();
+        return clone;
+    }
+
+}

Added: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSkewedJoin.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSkewedJoin.java?rev=799141&view=auto
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSkewedJoin.java (added)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/physicalLayer/relationalOperators/POSkewedJoin.java Thu Jul 30 00:30:25 2009
@@ -0,0 +1,97 @@
+/*
+ * 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.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.hadoop.executionengine.physicalLayer.PhysicalOperator;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.plans.PhyPlanVisitor;
+import org.apache.pig.backend.hadoop.executionengine.physicalLayer.plans.PhysicalPlan;
+import org.apache.pig.data.DataType;
+import org.apache.pig.impl.plan.OperatorKey;
+import org.apache.pig.impl.plan.VisitorException;
+import org.apache.pig.impl.util.MultiMap;
+
+/**
+ * The PhysicalOperator that represents a skewed join. It must have two inputs.
+ * This operator does not do any actually work, it is only a place holder. When it is
+ * translated into MR plan, a POSkewedJoin is translated into a sampling job and a join 
+ * job.
+ * 
+ *
+ */
+public class POSkewedJoin extends PhysicalOperator  {
+
+	
+	private static final long serialVersionUID = 1L;
+	
+	private static Log log = LogFactory.getLog(POSkewedJoin.class);
+	
+	// physical plans to retrive join keys
+	// the key of this <code>MultiMap</code> is the PhysicalOperator that corresponds to an input
+	// the value is a list of <code>PhysicalPlan</code> to retrieve each join key for this input
+    private MultiMap<PhysicalOperator, PhysicalPlan> mJoinPlans;
+
+    public POSkewedJoin(OperatorKey k)  {
+        this(k,-1,null);
+    }
+
+    public POSkewedJoin(OperatorKey k, int rp) {
+        this(k, rp, null);
+    }
+
+    public POSkewedJoin(OperatorKey k, List<PhysicalOperator> inp) {
+        this(k, -1, inp);
+    }
+
+    public POSkewedJoin(OperatorKey k, int rp, List<PhysicalOperator> inp) {
+        super(k,rp,inp);      
+    }
+    
+    public MultiMap<PhysicalOperator, PhysicalPlan> getJoinPlans() {
+    	return mJoinPlans;
+    }
+    
+    public void setJoinPlans(MultiMap<PhysicalOperator, PhysicalPlan> joinPlans) {
+        mJoinPlans = joinPlans;
+    }    
+    
+	@Override
+	public void visit(PhyPlanVisitor v) throws VisitorException {
+		v.visitSkewedJoin(this);
+	}
+
+	@Override
+	public String name() {
+		return "SkewedJoin[" + DataType.findTypeName(resultType) + "]" +" - " + mKey.toString();
+	}
+
+	@Override
+	public boolean supportsMultipleInputs() {		
+		return true;
+	}
+
+	@Override
+	public boolean supportsMultipleOutputs() {	
+		return false;
+	}
+
+}

Modified: hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/util/MapRedUtil.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/util/MapRedUtil.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/util/MapRedUtil.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/backend/hadoop/executionengine/util/MapRedUtil.java Thu Jul 30 00:30:25 2009
@@ -17,6 +17,25 @@
 import org.apache.pig.impl.PigContext;
 import org.apache.pig.impl.util.ObjectSerializer;
 
+import org.apache.pig.impl.io.PigNullableWritable;
+import org.apache.pig.impl.io.NullablePartitionWritable;
+
+import org.apache.pig.impl.util.Pair;
+import org.apache.pig.data.DefaultTupleFactory;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Map.Entry;
+import org.apache.pig.backend.hadoop.HDataType;
+import org.apache.pig.data.Tuple;
+import java.io.InputStream;
+import org.apache.pig.impl.io.BufferedPositionedInputStream;
+import org.apache.pig.impl.io.FileLocalizer;
+import org.apache.pig.builtin.BinStorage;
+import org.apache.pig.data.DataBag;
+import org.apache.pig.backend.hadoop.datastorage.ConfigurationUtil;
+import org.apache.pig.data.DataType;
+
 /**
  * A class of utility static methods to be used in the hadoop map reduce backend
  */
@@ -66,4 +85,77 @@
     public static StoreConfig getStoreConfig(JobConf conf) throws IOException {
         return (StoreConfig) ObjectSerializer.deserialize(conf.get(JobControlCompiler.PIG_STORE_CONFIG));
     }
+
+	/**
+	 * Loads the key distribution sampler file
+     *
+     * @param keyDistFile the name for the distribution file
+     * @param totalReducers gets set to the total number of reducers as found in the dist file
+     * @param job Ref to a jobCong object
+     * @param keyType Type of the key to be stored in the return map. It currently treats Tuple as a special case.
+	 */	
+	@SuppressWarnings("unchecked")
+	public static <E> Map<E, Pair<Integer, Integer> > loadPartitionFile(String keyDistFile,
+								 Integer[] totalReducers, JobConf job, byte keyType) throws IOException {
+
+		Map<E, Pair<Integer, Integer> > reducerMap = new HashMap<E, Pair<Integer, Integer> >();
+		
+		InputStream is;
+		if (job != null) {
+			is = FileLocalizer.openDFSFile(keyDistFile,ConfigurationUtil.toProperties(job));
+		} else {
+			is = FileLocalizer.openDFSFile(keyDistFile);
+		}
+		BinStorage loader = new BinStorage();
+		DataBag partitionList;
+		loader.bindTo(keyDistFile, new BufferedPositionedInputStream(is), 0, Long.MAX_VALUE);
+		Tuple t = loader.getNext();
+		if(t==null) {
+			throw new RuntimeException("Empty samples file");
+		}
+		// The keydist file is structured as (key, min, max)
+		// min, max being the index of the reducers
+		Map<String, Object > distMap = (Map<String, Object>) t.get (0);
+		partitionList = (DataBag) distMap.get("partition.list");
+		totalReducers[0] = Integer.valueOf(""+distMap.get("totalreducers"));
+		Iterator<Tuple> it = partitionList.iterator();
+		while (it.hasNext()) {
+			Tuple idxTuple = it.next();
+			Integer maxIndex = (Integer) idxTuple.get(idxTuple.size() - 1);
+			Integer minIndex = (Integer) idxTuple.get(idxTuple.size() - 2);
+			// Used to replace the maxIndex with the number of reducers
+			if (maxIndex < minIndex) {
+				maxIndex = totalReducers[0] + maxIndex; 
+			}
+			E keyT;
+
+			// if the join is on more than 1 key
+			if (idxTuple.size() > 3) {
+				// remove the last 2 fields of the tuple, i.e: minIndex and maxIndex and store
+				// it in the reducer map
+				Tuple keyTuple = DefaultTupleFactory.getInstance().newTuple();
+				for (int i=0; i < idxTuple.size() - 2; i++) {
+					keyTuple.append(idxTuple.get(i));	
+				}
+				keyT = (E) keyTuple;
+			} else {
+				if (keyType == DataType.TUPLE) {
+					keyT = (E)DefaultTupleFactory.getInstance().newTuple(1);
+					((Tuple)keyT).set(0,idxTuple.get(0));
+				} else {
+					keyT = (E) idxTuple.get(0);
+				}
+			}
+			// number of reducers
+			Integer cnt = 0;
+			if (minIndex < maxIndex) {
+				cnt = maxIndex - minIndex;
+			} else {
+				cnt = totalReducers[0] + maxIndex - minIndex;
+			}
+
+			reducerMap.put(keyT, new Pair(minIndex, cnt));// 1 is added to account for the 0 index
+		}		
+		return reducerMap;
+	}
 }

Modified: hadoop/pig/trunk/src/org/apache/pig/builtin/PigStorage.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/builtin/PigStorage.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/builtin/PigStorage.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/builtin/PigStorage.java Thu Jul 30 00:30:25 2009
@@ -98,12 +98,10 @@
         }
     }
 
-    @Override
     public long getPosition() throws IOException {
         return in.getPosition();
     }
 
-    @Override
     public long skip(long n) throws IOException {
         
         long skipped = in.skip(n-1);
@@ -125,7 +123,8 @@
             // BufferedPositionedInputStream is buffered, so I don't need
             // to buffer.
             int b = in.read();
-
+            prevByte = (byte)b;
+            
             if (b == fieldDel) {
                 readField();
             } else if (b == recordDel) {
@@ -143,7 +142,6 @@
         }
     }
 
-    @Override
     public Tuple getSampledTuple() throws IOException {
        
         if(prevByte == null || prevByte == recordDel) 
@@ -357,7 +355,7 @@
     /* (non-Javadoc)
      * @see org.apache.pig.StoreFunc#getStorePreparationClass()
      */
-    @Override
+   
     public Class getStorePreparationClass() throws IOException {
         // TODO Auto-generated method stub
         return null;

Modified: hadoop/pig/trunk/src/org/apache/pig/data/DataType.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/src/org/apache/pig/data/DataType.java?rev=799141&r1=799140&r2=799141&view=diff
==============================================================================
--- hadoop/pig/trunk/src/org/apache/pig/data/DataType.java (original)
+++ hadoop/pig/trunk/src/org/apache/pig/data/DataType.java Thu Jul 30 00:30:25 2009
@@ -85,7 +85,7 @@
         else if (o instanceof Double) return DOUBLE;
         else if (o instanceof Boolean) return BOOLEAN;
         else if (o instanceof Byte) return BYTE;
-        else return ERROR;
+        else {return ERROR;}
     }
 
     /**