You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mrql.apache.org by fe...@apache.org on 2013/08/27 14:27:49 UTC

[11/21] MRQL-2: Mavenize MRQL

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/BSP/BSPPlan.java
----------------------------------------------------------------------
diff --git a/src/main/java/BSP/BSPPlan.java b/src/main/java/BSP/BSPPlan.java
new file mode 100644
index 0000000..7252628
--- /dev/null
+++ b/src/main/java/BSP/BSPPlan.java
@@ -0,0 +1,501 @@
+/**
+ * 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.mrql;
+
+import org.apache.mrql.gen.*;
+import java.io.*;
+import java.util.Arrays;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hama.bsp.*;
+import org.apache.hama.bsp.sync.SyncException;
+import org.apache.hama.HamaConfiguration;
+import org.apache.hadoop.conf.Configuration;
+
+
+/** Evaluate a BSP plan using Hama */
+final public class BSPPlan extends Plan {
+
+    final static Configuration getConfiguration ( BSPJob job ) {
+	return job.getConf();   // use job.getConfiguration() for Hama 0.6.0
+    }
+
+    /** The BSP evaluator */
+    final static class BSPop extends BSP<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> {
+	final static MRContainer null_key = new MRContainer(new MR_byte(0));
+	// special message for sub-sync()
+	final static MRData more_to_come = new MR_sync();
+	final static MRData more_supersteps = new MR_more_bsp_steps();
+
+	private int source_num;
+	private Function superstep_fnc;      // superstep function
+	private MRData state;                // BSP state
+	private boolean orderp;              // will output be ordered?
+	private MRData source;               // BSP input
+	private Function acc_fnc;            // aggregator
+	private MRData acc_result;           // aggregation result
+	private static String[] all_peer_names;   // all BSP peer names
+	private static BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer>[] all_peers;   // all BSP peers
+	// a master peer that coordinates and collects results of partial aggregations
+	private String masterTask;
+	// buffer for received messages -- regularly in a vector, but can be spilled in a local file
+	Bag msg_cache;
+	// the cache that holds all local data in memory
+	Tuple local_cache;
+
+	private static BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> getPeer ( String name ) {
+	    for ( int i = 0; i < all_peer_names.length; i++ )
+		if (all_peer_names[i].equals(name))
+		    return all_peers[i];
+	    throw new Error("Unknown peer: "+name);
+	}
+
+	private static void setPeer ( BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer ) {
+	    String name = peer.getPeerName();
+	    for ( int i = 0; i < all_peer_names.length; i++ )
+		if (all_peer_names[i].equals(name))
+		    all_peers[i] = peer;
+	}
+
+	/** shuffle values to BSP peers based on uniform hashing on key */
+	private static String shuffle ( MRData key ) {
+	    return all_peer_names[Math.abs(key.hashCode()) % all_peer_names.length];
+	}
+
+	/** to exit a BSP loop, all peers must agree to exit (this is used in BSPTranslate.bspSimplify) */
+	public static MR_bool synchronize ( MR_string peerName, MR_bool mr_exit ) {
+	    return synchronize(getPeer(peerName.get()),mr_exit);
+	}
+
+	/** to exit a BSP loop, all peers must agree to exit (this is used in BSPTranslate.bspSimplify) */
+	public static MR_bool synchronize ( BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer, MR_bool mr_exit ) {
+	    if (!Config.hadoop_mode)
+		return mr_exit;
+	    // shortcut: if we know for sure that all peers want to exit/continue, we don't have to poll
+	    if (mr_exit == SystemFunctions.bsp_true_value          // must be ==, not equals
+		|| mr_exit == SystemFunctions.bsp_false_value)
+		return mr_exit;
+	    try {
+		// this case is only used for checking the exit condition of repeat/closure
+		boolean exit = mr_exit.get();
+		if (all_peer_names.length <= 1)
+		    return (exit) ? SystemFunctions.bsp_true_value : SystemFunctions.bsp_false_value;
+		if (!exit)
+		    // this peer is not ready to exit, so no peer should exit
+		    for ( String p: peer.getAllPeerNames() )
+			peer.send(p,new MRContainer(more_supersteps));
+		peer.sync();
+		// now exit is true if no peer sent a "more_supersteps" message
+		exit = peer.getNumCurrentMessages() == 0;
+		peer.clear();
+		return (exit) ? SystemFunctions.bsp_true_value : SystemFunctions.bsp_false_value;
+	    } catch (Exception ex) {
+		throw new Error(ex);
+	    }
+	}
+
+	/** collect a bag from all peers by distributing the local copy s */
+	public static Bag distribute ( MR_string peerName, Bag s ) {
+	    BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer = getPeer(peerName.get());
+	    if (!Config.hadoop_mode)
+		return s;
+	    try {
+		for ( MRData e: s )
+		    for ( String p: all_peer_names )
+			peer.send(p,new MRContainer(e));
+		peer.sync();
+		MRContainer msg;
+		Bag res = new Bag();
+		while ((msg = peer.getCurrentMessage()) != null)
+		    if (!res.contains(msg.data()))
+			res.add(msg.data());
+		peer.clear();
+		return res;
+	    } catch (Exception ex) {
+		throw new Error(ex);
+	    }
+	}
+
+	private void readLocalSources ( BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer )
+	        throws IOException {
+	    MRContainer key = new MRContainer();
+	    MRContainer value = new MRContainer();
+	    while (peer.readNext(key,value)) {
+		Tuple p = (Tuple)(value.data());
+		((Bag)local_cache.get(((MR_int)p.first()).get())).add(p.second());
+	    }
+	}
+
+	private void writeLocalResult ( Bag result,
+					BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer )
+	        throws IOException {
+	    MRContainer key = new MRContainer();
+	    MRContainer value = new MRContainer();
+	    for ( MRData v: result )
+		if (orderp) {       // prepare for sorting
+		    Tuple t = (Tuple)v;
+		    key.set(t.get(1));
+		    value.set(t.get(0));
+		    peer.write(key,value);
+		} else {
+		    value.set(v);
+		    peer.write(null_key,value);
+		}
+	}
+
+	/** receive messages from other peers */
+	private void receive_messages ( final BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer )
+	        throws IOException, SyncException, InterruptedException {
+	    if (Config.bsp_msg_size <= 0) {    // no buffering
+		msg_cache = new Bag(new BagIterator() {
+			MRContainer msg;
+			public boolean hasNext () {
+			    try {
+				return (msg = peer.getCurrentMessage()) != null;
+			    } catch (Exception ex) {
+				throw new Error(ex);
+			    }
+			} 
+			public MRData next () {
+			    return msg.data();
+			}
+		    });
+	    } else {
+		boolean expect_more = false;   // are we expecting more incoming messages?
+		do {
+		    // just in case this peer did a regular-sync() before the others did a sub-sync()
+		    expect_more = false;
+		    MRContainer msg;
+		    // cache the received messages
+		    while ((msg = peer.getCurrentMessage()) != null)
+			// if at least one peer sends a more_to_come message, then expect_more
+			if (msg.data().equals(more_to_come))
+			    expect_more = true;
+			else msg_cache.add(msg.data());
+		    if (expect_more)
+			peer.sync();   // sub-sync()
+		} while (expect_more);
+	    }
+	}
+
+	/** send the messages produced by a superstep to peers and then receive the replies */
+	private void send_messages ( Bag msgs,
+				     BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer )
+	        throws IOException, SyncException, InterruptedException {
+	    int size = 0;
+	    if (Config.bsp_msg_size > 0)
+		msg_cache.clear();
+	    for ( MRData m: msgs ) {
+		Tuple t = (Tuple)m;
+		// if there are too many messages to send, then sub-sync()
+		if ( Config.bsp_msg_size > 0 && size++ > Config.bsp_msg_size ) {
+		    // tell all peers that there is more to come after sync
+		    for ( String p: all_peer_names )
+			if (!peer.getPeerName().equals(p))
+			    peer.send(p,new MRContainer(more_to_come));
+		    peer.sync();  // sub-sync()
+		    size = 0;
+		    MRContainer msg;
+		    // cache the received messages
+		    while ((msg = peer.getCurrentMessage()) != null)
+			if (!msg.data().equals(more_to_come))
+			    msg_cache.add(msg.data());
+		};
+		// suffle messages based on key; needs new MRContainer object
+		peer.send(shuffle(t.get(0)),new MRContainer(t.get(1)));
+	    };
+	    peer.sync();   // regular-sync()
+	    receive_messages(peer);
+	}
+
+	@Override
+	public void bsp ( BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer )
+	       throws IOException, SyncException, InterruptedException {
+	    final Tuple stepin = new Tuple(4);
+	    stepin.set(3,new MR_string(peer.getPeerName()));
+	    Tuple result;
+	    boolean skip = false;
+	    String tabs = "";
+	    int step = 0;
+	    boolean exit;
+	    readLocalSources(peer);
+	    setPeer(peer);
+	    do {
+		if (!skip)
+		    step++;
+		if (!skip && Config.trace_execution) {
+		    tabs = Interpreter.tabs(Interpreter.tab_count);
+		    System.err.println(tabs+"  Superstep "+step+" ["+peer.getPeerName()+"]:");
+		    System.err.println(tabs+"      messages ["+peer.getPeerName()+"]: "+msg_cache);
+		    System.err.println(tabs+"      state ["+peer.getPeerName()+"]: "+state);
+		    for ( int i = 0; i < local_cache.size(); i++)
+			if (local_cache.get(i) instanceof Bag && ((Bag)local_cache.get(i)).size() > 0)
+			    System.out.println(tabs+"      cache ["+peer.getPeerName()+"] "+i+": "+local_cache.get(i));
+		};
+		stepin.set(0,local_cache);
+		stepin.set(1,msg_cache);
+		stepin.set(2,state);
+		// evaluate one superstep
+		result = (Tuple)superstep_fnc.eval(stepin);
+		Bag msgs = (Bag)result.get(0);
+		exit = ((MR_bool)result.get(2)).get();
+		state = result.get(1);
+		// shortcuts: if we know for sure that all peers want to exit/continue
+		if (result.get(2) == SystemFunctions.bsp_true_value) {  // must be ==, not equals
+		    peer.sync();
+		    if (Config.trace_execution)
+			System.err.println(tabs+"      result ["+peer.getPeerName()+"]: "+result);
+		    break;
+		};
+		if (result.get(2) == SystemFunctions.bsp_false_value) {
+		    if (Config.trace_execution)
+			System.err.println(tabs+"      result ["+peer.getPeerName()+"]: "+result);
+		    send_messages(msgs,peer);
+		    skip = false;
+		    continue;
+		};
+		// shortcut: skip is true when NONE of the peers sent any messages
+		skip = (msgs == SystemFunctions.bsp_empty_bag);  // must be ==, not equals
+		if (skip)
+		    continue;
+		if (Config.trace_execution)
+		    System.err.println(tabs+"      result ["+peer.getPeerName()+"]: "+result);
+		exit = synchronize(peer,(MR_bool)result.get(2)).get();
+		send_messages(msgs,peer);
+	    } while (!exit);
+	    if (acc_result == null) {
+		// the BSP result is a bag that needs to be dumped to the HDFS
+		writeLocalResult((Bag)(local_cache.get(source_num)),peer);
+		// if there more results, dump them to HDFS
+		final MR_long key = new MR_long(0);
+		final MRContainer key_container = new MRContainer(key);
+		final MRContainer data_container = new MRContainer(new MR_int(0));
+		int loc = 0;
+		while ( loc < all_peer_names.length && peer.getPeerName().equals(all_peer_names[loc]) )
+		    loc++;
+		Configuration conf = peer.getConfiguration();
+		String[] out_paths = conf.get("mrql.output.paths").split(",");
+		for ( int i = 1; i < out_paths.length; i++ ) {
+		    String[] s = out_paths[i].split(":");
+		    int out_num = Integer.parseInt(s[0]);
+		    Path path = new Path(s[1]+"/peer"+loc);
+		    FileSystem fs = path.getFileSystem(conf);
+		    SequenceFile.Writer writer
+			= new SequenceFile.Writer(fs,conf,path,
+						  MRContainer.class,MRContainer.class);
+		    long count = 0;
+		    for ( MRData e: (Bag)(local_cache.get(out_num)) ) {
+			key.set(count++);
+			data_container.set(e);
+			writer.append(key_container,data_container);
+		    };
+		    writer.close();
+		};
+	    } else {
+		// the BSP result is an aggregation:
+		//     send the partial results to the master peer
+		peer.send(masterTask,new MRContainer(local_cache.get(source_num)));
+		peer.sync();
+		if (peer.getPeerName().equals(masterTask)) {
+		    // only the master peer collects the partial aggregations
+		    MRContainer msg;
+		    while ((msg = peer.getCurrentMessage()) != null)
+			acc_result = acc_fnc.eval(new Tuple(acc_result,msg.data()));
+		    // write the final aggregation result
+		    peer.write(null_key,new MRContainer(acc_result));
+	       }
+	    }
+	}
+
+	@Override
+	@SuppressWarnings("unchecked")
+	public void setup ( BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer ) {
+	    try {
+		super.setup(peer);
+		Configuration conf = peer.getConfiguration();
+		Config.read(conf);
+		if (Plan.conf == null)
+		    Plan.conf = conf;
+		all_peer_names = peer.getAllPeerNames();
+		all_peers = new BSPPeerImpl[all_peer_names.length];
+		Arrays.sort(all_peer_names);  // is this necessary?
+		source_num = conf.getInt("mrql.output.tag",0);
+		Tree code = Tree.parse(conf.get("mrql.superstep"));
+		superstep_fnc = functional_argument(conf,code);
+		code = Tree.parse(conf.get("mrql.initial.state"));
+		state = Interpreter.evalE(code);
+		if (conf.get("mrql.zero") != null && !conf.get("mrql.zero").equals("")) {
+		    code = Tree.parse(conf.get("mrql.zero"));
+		    acc_result = Interpreter.evalE(code);
+		    code = Tree.parse(conf.get("mrql.accumulator"));
+		    acc_fnc = functional_argument(conf,code);
+		} else acc_result = null;
+		orderp = conf.getBoolean("mrql.orderp",false);
+		masterTask = all_peer_names[peer.getNumPeers()/2];
+		msg_cache = new Bag(1000);
+		local_cache = new Tuple(max_input_files);
+		for ( int i = 0; i < max_input_files; i++ )
+		    local_cache.set(i,new Bag());
+	    } catch (Exception e) {
+		e.printStackTrace();
+		throw new Error("Cannot setup the Hama BSP job: "+e);
+	    }
+	}
+
+	@Override
+	public void cleanup ( BSPPeer<MRContainer,MRContainer,MRContainer,MRContainer,MRContainer> peer ) throws IOException {
+	    if (!Config.local_mode)
+		clean();
+	    local_cache = null;
+	    super.cleanup(peer);
+	}
+    }
+
+    /** set Hama's min split size and number of BSP tasks (doesn't work with Hama 0.6.0) */
+    public static void setupSplits ( BSPJob job, DataSet ds ) throws IOException {
+	long[] sizes = new long[ds.source.size()];
+	if (sizes.length > Config.nodes)
+	    throw new Error("Cannot distribute "+sizes.length+" files over "+Config.nodes+" BSP tasks");
+	for ( int i = 0; i < sizes.length; i++ )
+	    sizes[i] = ds.source.get(i).size(Plan.conf);
+	long total_size = 0;
+	for ( long size: sizes )
+	    total_size += size;
+	long split_size = Math.max(total_size/Config.nodes,100000);
+	int tasks = 0;
+	do {  // adjust split_size
+	    tasks = 0;
+	    for ( long size: sizes )
+		tasks += (int)Math.ceil(size/(double)split_size);
+	    if (tasks > Config.nodes)
+		split_size = (long)Math.ceil((double)split_size*1.01);
+	} while (tasks > Config.nodes);
+	job.setNumBspTask(tasks);
+	System.err.println("*** Using "+tasks+" BSP tasks (out of a max "+Config.nodes+")."
+			   +" Each task will handle about "+Math.min(total_size/Config.nodes,split_size)
+			   +" bytes of input data.");
+	job.set("bsp.min.split.size",Long.toString(split_size));
+    }
+
+    /** Evaluate a BSP operation that returns a DataSet
+     * @param source_nums   output tags
+     * @param superstep     the superstep function
+     * @param init_state    initial state
+     * @param orderp        do we need to order the result?
+     * @param source        input dataset
+     * @return a new data source that contains the result
+     */
+    public final static MRData BSP ( int[] source_nums, // output tags
+				     Tree superstep,    // superstep function
+				     Tree init_state,   // initial state
+				     boolean orderp,    // do we need to order the result?
+				     DataSet source     // input dataset
+				     ) throws Exception {
+	String[] newpaths = new String[source_nums.length];
+	newpaths[0] = new_path(conf);
+	conf.set("mrql.output.paths",source_nums[0]+":"+newpaths[0]);
+	for ( int i = 1; i < source_nums.length; i++ ) {
+	    newpaths[i] = new_path(conf);
+	    Path path = new Path(newpaths[1]);
+	    FileSystem fs = path.getFileSystem(conf);
+	    fs.mkdirs(path);
+	    conf.set("mrql.output.paths",conf.get("mrql.output.paths")+","+source_nums[i]+":"+newpaths[i]);
+	};
+	conf.set("mrql.superstep",superstep.toString());
+	conf.set("mrql.initial.state",init_state.toString());
+	conf.set("mrql.zero","");
+	conf.setInt("mrql.output.tag",source_nums[0]);
+	conf.setBoolean("mrql.orderp",orderp);
+	BSPJob job = new BSPJob((HamaConfiguration)conf,BSPop.class);
+	setupSplits(job,source);
+	job.setJobName(newpaths[0]);
+	distribute_compiled_arguments(getConfiguration(job));
+	job.setBspClass(BSPop.class);
+	Path outpath = new Path(newpaths[0]);
+	job.setOutputPath(outpath);
+	job.setOutputKeyClass(MRContainer.class);
+	job.setOutputValueClass(MRContainer.class);
+	job.setOutputFormat(SequenceFileOutputFormat.class);
+	job.setInputFormat(MultipleBSPInput.class);
+	FileInputFormat.setInputPaths(job,source.merge());
+	job.waitForCompletion(true);
+	if (source_nums.length == 1) {
+	    BinaryDataSource ds = new BinaryDataSource(source_nums[0],newpaths[0],conf);
+	    ds.to_be_merged = orderp;
+	    return new MR_dataset(new DataSet(ds,0,3));
+	} else {
+	    MRData[] s = new MRData[source_nums.length];
+	    for ( int i = 0; i < source_nums.length; i++ ) {
+		BinaryDataSource ds = new BinaryDataSource(source_nums[i],newpaths[i],conf);
+		ds.to_be_merged = orderp;
+		s[i] = new MR_dataset(new DataSet(ds,0,3));
+	    };
+	    return new Tuple(s);
+	}
+    }
+
+    /** Evaluate a BSP operation that aggregates the results
+     * @param source_nums   output tags
+     * @param superstep     the superstep function
+     * @param init_state    initial state
+     * @param acc_fnc       accumulator function
+     * @param zero          zero value for the accumulator
+     * @param source        input dataset
+     * @return the aggregation result
+     */
+    public final static MRData BSPaggregate ( int source_num,   // output tag
+					      Tree superstep,   // superstep function
+					      Tree init_state,  // initial state
+					      Tree acc_fnc,     // accumulator function
+					      Tree zero,        // zero value for the accumulator
+					      DataSet source    // input dataset
+					      ) throws Exception {
+	String newpath = new_path(conf);
+	conf.set("mrql.superstep",superstep.toString());
+	conf.set("mrql.initial.state",init_state.toString());
+	conf.set("mrql.accumulator",acc_fnc.toString());
+	conf.set("mrql.zero",zero.toString());
+	conf.setInt("mrql.output.tag",source_num);
+	conf.setBoolean("mrql.orderp",false);
+	BSPJob job = new BSPJob((HamaConfiguration)conf,BSPop.class);
+	setupSplits(job,source);
+	job.setJobName(newpath);
+	distribute_compiled_arguments(getConfiguration(job));
+	job.setBspClass(BSPop.class);
+	Path outpath = new Path(newpath);
+	job.setOutputPath(outpath);
+	job.setOutputKeyClass(MRContainer.class);
+	job.setOutputValueClass(MRContainer.class);
+	job.setOutputFormat(SequenceFileOutputFormat.class);
+	job.setInputFormat(MultipleBSPInput.class);
+	FileInputFormat.setInputPaths(job,source.merge());
+	job.waitForCompletion(true);
+	FileSystem fs = outpath.getFileSystem(conf);
+	FileStatus[] files = fs.listStatus(outpath);
+	for ( int i = 0; i < files.length; i++ ) {
+	    SequenceFile.Reader sreader = new SequenceFile.Reader(fs,files[i].getPath(),conf);
+	    MRContainer key = new MRContainer();
+	    MRContainer value = new MRContainer();
+	    sreader.next(key,value);
+	    sreader.close();
+	    if (value.data() != null)
+		return value.data();
+	};
+	return null;
+    }
+ }

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/BSP/BinaryInputFormat.java
----------------------------------------------------------------------
diff --git a/src/main/java/BSP/BinaryInputFormat.java b/src/main/java/BSP/BinaryInputFormat.java
new file mode 100644
index 0000000..27f62ee
--- /dev/null
+++ b/src/main/java/BSP/BinaryInputFormat.java
@@ -0,0 +1,60 @@
+/**
+ * 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.mrql;
+
+import org.apache.mrql.gen.Trees;
+import java.io.*;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hama.bsp.*;
+import org.apache.hama.HamaConfiguration;
+
+
+/** Input format for hadoop sequence files */
+final public class BinaryInputFormat extends MRQLFileInputFormat {
+    public static class BinaryInputRecordReader extends SequenceFileRecordReader<MRContainer,MRContainer> {
+	final MRContainer result = new MRContainer();
+	final MRData source_num_data;
+	final int source_number;
+
+	public BinaryInputRecordReader ( FileSplit split,
+					 BSPJob job,
+					 int source_number ) throws IOException {
+	    super(BSPPlan.getConfiguration(job),split);
+	    this.source_number = source_number;
+	    source_num_data = new MR_int(source_number);
+	}
+
+	@Override
+	public synchronized boolean next ( MRContainer key, MRContainer value ) throws IOException {
+		boolean b = super.next(key,result);
+		value.set(new Tuple(source_num_data,result.data()));
+		return b;
+	}
+    }
+
+    public RecordReader<MRContainer,MRContainer>
+	      getRecordReader ( InputSplit split,
+				BSPJob job ) throws IOException {
+	Configuration conf = BSPPlan.getConfiguration(job);
+	String path = ((FileSplit)split).getPath().toString();
+	BinaryDataSource ds = (BinaryDataSource)DataSource.get(path,conf);
+	return new BinaryInputRecordReader((FileSplit)split,job,ds.source_num);
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/BSP/Evaluator.gen
----------------------------------------------------------------------
diff --git a/src/main/java/BSP/Evaluator.gen b/src/main/java/BSP/Evaluator.gen
new file mode 100644
index 0000000..f3e594d
--- /dev/null
+++ b/src/main/java/BSP/Evaluator.gen
@@ -0,0 +1,224 @@
+/**
+ * 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.mrql;
+
+import org.apache.mrql.gen.*;
+import java.io.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hama.HamaConfiguration;
+
+
+/** Evaluate a physical plan in BSP mode using Hama */
+final public class Evaluator extends Interpreter {
+
+    /** initialize the BSP evaluator */
+    final static void init ( Configuration conf ) {
+	Config.bsp_mode = true;
+	if (Config.hadoop_mode)
+            if (Config.local_mode) {
+                conf.set("bsp.master.address","local");
+                conf.set("hama.zookeeper.quorum","localhost");
+                conf.setInt("bsp.local.tasks.maximum",Config.nodes);
+                conf.set("fs.default.name","file:///");
+            } else {
+                conf.set("bsp.master.address",System.getenv("BSP_MASTER_ADDRESS"));
+                conf.set("hama.zookeeper.quorum",System.getenv("HAMA_ZOOKEEPER_QUORUM"));
+                conf.setInt("bsp.local.tasks.maximum",Config.nodes);
+                conf.set("fs.default.name",System.getenv("FS_DEFAULT_NAME"));
+            }
+    }
+
+    final static void initialize_query () {
+    }
+
+    /** shutdown the BSP evaluator */
+    final static void shutdown ( Configuration conf ) {
+    }
+
+    final static Configuration new_configuration () {
+	return new HamaConfiguration();
+    }
+
+    public static MR_bool synchronize ( MR_string peerName, MR_bool mr_exit ) {
+        if (Config.hadoop_mode)
+            return BSPPlan.BSPop.synchronize(peerName,mr_exit);
+        else return mr_exit;
+    }
+
+    public static Bag distribute ( MR_string peerName, Bag s ) {
+        if (Config.hadoop_mode)
+            return BSPPlan.BSPop.distribute(peerName,s);
+        else return s;
+    }
+
+    /** Evaluate MRQL physical operators using BSP
+     * @param e the physical plan
+     * @param env contains bindings fro variables to values (MRData)
+     * @return a DataSet (stored in HDFS)
+     */
+    final static MRData bsp ( Tree plan, Environment env ) throws Exception {
+	match plan {
+	case BSP(tuple(...ns),`superstep,`init_state,`o,...S):
+	    int[] os = new int[ns.length()];
+	    for ( int i = 0; i < os.length; i++ )
+		os[i] = (int)((LongLeaf)ns.nth(i)).value();
+	    DataSet ds = eval(S.head(),env);
+	    for ( Tree s: S.tail() )
+		ds.merge(eval(s,env));
+	    return BSPPlan.BSP(os,
+			       closure(superstep,env),
+			       init_state,
+			       o.equals(#<true>),
+			       ds);
+	case BSP(`n,`superstep,`init_state,`o,...S):
+	    DataSet ds = eval(S.head(),env);
+	    for ( Tree s: S.tail() )
+		ds.merge(eval(s,env));
+	    return BSPPlan.BSP(new int[]{(int)((LongLeaf)n).value()},
+			       closure(superstep,env),
+			       init_state,
+			       o.equals(#<true>),
+			       ds);
+	}
+	throw new Error("Cannot perform the BSP plan: "+plan);
+    }
+
+    /** The Aggregate physical operator
+     * @param acc_fnc  the accumulator function from (T,T) to T
+     * @param zero  the zero element of type T
+     * @param plan the plan that constructs the dataset that contains the bag of values {T}
+     * @param env contains bindings fro variables to values (MRData)
+     * @returns the aggregation result of type T
+     */
+    final static MRData aggregate ( Tree acc_fnc,
+				    Tree zero,
+				    Tree plan,
+				    Environment env ) throws Exception {
+	match plan {
+	case BSP(`n,`superstep,`init_state,`o,...S):
+	    DataSet ds = eval(S.head(),env,"-");
+	    for ( Tree s: S.tail() )
+		ds.merge(eval(s,env,"-"));
+	    return BSPPlan.BSPaggregate((int)((LongLeaf)n).value(),
+					closure(superstep,env),
+					init_state,
+					closure(acc_fnc,env),
+					zero,
+					ds);
+	}
+	throw new Error("Cannot perform the aggregation: "+plan);
+    }
+
+    final static Tuple loop ( Tree e, Environment env ) {
+	throw new Error("The BSP Loop was supposed to be translated to a BSP task");
+    }
+
+    final static DataSet eval ( final Tree e,
+				final Environment env,
+				final String counter ) {
+	return eval(e,env);
+    }
+
+    /** Evaluate MRQL BSP physical operators using Hama (returns a DataSet)
+     *   and print tracing info
+     * @param e the physical plan
+     * @param env contains bindings fro variables to values (MRData)
+     * @return a DataSet (stored in HDFS)
+     */
+    final static DataSet eval ( final Tree e, final Environment env ) {
+	if (Config.trace_execution) {
+	    tab_count += 3;
+	    System.out.println(tabs(tab_count)+print_query(e));
+	};
+	DataSet res = evalD(e,env);
+	if (Config.trace_execution) 
+	    try {
+		System.out.println(tabs(tab_count)
+				   +"-> "+Plan.collect(res,false));
+		tab_count -= 3;
+	    } catch (Exception ex) {
+		throw new Error("Cannot collect the operator output: "+e);
+	    };
+	return res;
+    }
+
+    /** Evaluate MRQL BSP physical operators using Hama (returns a DataSet)
+     * @param e the physical plan
+     * @param env contains bindings fro variables to values (MRData)
+     * @return a DataSet (stored in HDFS)
+     */
+    final static DataSet evalD ( final Tree e, final Environment env ) {
+	try {
+	    match e {
+	    case BSPSource(`n,BinarySource(`file,_)):
+		return Plan.binarySource((int)((LongLeaf)n).value(),file.stringValue());
+	    case BSPSource(`n,ParsedSource(`parser,`file,...args)):
+		Class<? extends Parser> p = DataSource.parserDirectory.get(parser.toString());
+		if (p == null)
+		    throw new Error("Unknown parser: "+parser);
+		return Plan.parsedSource((int)((LongLeaf)n).value(),
+					 p,((MR_string)evalE(file,env)).get(),args);
+	    case BSPSource(`n,Generator(`min,`max,`size)):
+		return Plan.generator((int)((LongLeaf)n).value(),
+				      ((MR_long)evalE(min,env)).get(),
+				      ((MR_long)evalE(max,env)).get(),
+				      ((MR_long)evalE(size,env)).get());
+	    case Merge(`x,`y):
+		return Plan.merge(eval(x,env),eval(y,env));
+	    case Dump(`s):
+		return Plan.fileCache((Bag)evalE(s,env));
+	    case apply(`f,`arg):
+		if (!f.is_variable())
+		    return ((MR_dataset)evalF(f,env).eval(evalE(arg))).dataset();
+		MRData fnc = variable_lookup(f.toString(),global_env);
+		if (fnc == null)
+		    throw new Error("Unknown function: "+f);
+		MRData t = evalE(arg,env);
+		if (!(t instanceof Tuple))
+		    throw new Error("Expected a tuple in function application: "+t);
+		return ((MR_dataset)((Lambda)fnc).lambda().eval(t)).dataset();
+	    case `v:
+		if (!v.is_variable())
+		    fail;
+		MRData x = variable_lookup(v.toString(),env);
+		if (x != null)
+		    if (x instanceof MR_dataset)
+			return ((MR_dataset)x).dataset();
+		x = variable_lookup(v.toString(),global_env);
+		if (x != null)
+		    if (x instanceof MR_dataset)
+			return ((MR_dataset)x).dataset();
+		throw new Error("Variable "+v+" is not bound");
+	    };
+	    MRData d = bsp(e,env);
+	    if (d instanceof MR_dataset)
+		return ((MR_dataset)d).dataset();
+	    throw new Error("Cannot evaluate the BSP plan: "+e);
+	} catch (Error msg) {
+	    if (!Config.trace)
+		throw new Error(msg.getMessage());
+	    System.err.println(msg.getMessage());
+	    throw new Error("Evaluation error in: "+print_query(e));
+	} catch (Exception ex) {
+	    System.err.println(ex.getMessage());
+	    ex.printStackTrace();
+	    throw new Error("Evaluation error in: "+print_query(e));
+	}
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/BSP/GeneratorInputFormat.java
----------------------------------------------------------------------
diff --git a/src/main/java/BSP/GeneratorInputFormat.java b/src/main/java/BSP/GeneratorInputFormat.java
new file mode 100644
index 0000000..cb13a83
--- /dev/null
+++ b/src/main/java/BSP/GeneratorInputFormat.java
@@ -0,0 +1,89 @@
+/**
+ * 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.mrql;
+
+import org.apache.mrql.gen.Trees;
+import java.io.*;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hama.bsp.*;
+
+
+/** the FileInputFormat for data generators: it creates HDFS files, where each file contains
+ *  an (offset,size) pair that generates the range of values [offset,offset+size] */
+final public class GeneratorInputFormat extends MRQLFileInputFormat {
+    public static class GeneratorRecordReader implements RecordReader<MRContainer,MRContainer> {
+	final long offset;
+	final long size;
+	final int source_number;
+	final MRData source_num_data;
+	long index;
+	SequenceFile.Reader reader;
+
+	public GeneratorRecordReader ( FileSplit split,
+				       int source_number,
+				       BSPJob job ) throws IOException {
+	    Configuration conf = BSPPlan.getConfiguration(job);
+	    Path path = split.getPath();
+	    FileSystem fs = path.getFileSystem(conf);
+	    reader = new SequenceFile.Reader(path.getFileSystem(conf),path,conf);
+	    MRContainer key = new MRContainer();
+	    MRContainer value = new MRContainer();
+	    reader.next(key,value);
+	    offset = ((MR_long)((Tuple)(value.data())).first()).get();
+	    size = ((MR_long)((Tuple)(value.data())).second()).get();
+	    this.source_number = source_number;
+	    source_num_data = new MR_int(source_number);
+	    index = -1;
+	}
+
+	public MRContainer createKey () {
+	    return new MRContainer(null);
+	}
+
+	public MRContainer createValue () {
+	    return new MRContainer(null);
+	}
+
+	public boolean next ( MRContainer key, MRContainer value ) throws IOException {
+	    index++;
+	    value.set(new Tuple(source_num_data,new MR_long(offset+index)));
+	    key.set(new MR_long(index));
+	    return index < size;
+	}
+
+	public long getPos () throws IOException { return index; }
+
+	public void close () throws IOException { reader.close(); }
+
+	public float getProgress () throws IOException {
+	    return index / (float)size;
+	}
+
+	public void initialize ( InputSplit split, TaskAttemptContext context ) throws IOException { }
+    }
+
+    public RecordReader<MRContainer,MRContainer>
+	        getRecordReader ( InputSplit split, BSPJob job ) throws IOException {
+	Configuration conf = BSPPlan.getConfiguration(job);
+	String path = ((FileSplit)split).getPath().toString();
+	GeneratorDataSource ds = (GeneratorDataSource)DataSource.get(path,conf);
+	return new GeneratorRecordReader((FileSplit)split,ds.source_num,job);
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/BSP/MRQLFileInputFormat.java
----------------------------------------------------------------------
diff --git a/src/main/java/BSP/MRQLFileInputFormat.java b/src/main/java/BSP/MRQLFileInputFormat.java
new file mode 100644
index 0000000..c7a7abf
--- /dev/null
+++ b/src/main/java/BSP/MRQLFileInputFormat.java
@@ -0,0 +1,107 @@
+/**
+ * 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.mrql;
+
+import java.io.*;
+import java.util.Iterator;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hama.bsp.*;
+import org.apache.hama.HamaConfiguration;
+
+
+/** A superclass for all MRQL FileInputFormats */
+abstract public class MRQLFileInputFormat extends FileInputFormat<MRContainer,MRContainer> {
+    public MRQLFileInputFormat () {}
+
+    /** record reader for map-reduce */
+    abstract public RecordReader<MRContainer,MRContainer>
+	getRecordReader ( InputSplit split, BSPJob job ) throws IOException;
+
+    /** materialize the input file into a memory Bag */
+    public Bag materialize ( final Path file ) throws Exception {
+	final BSPJob job = new BSPJob((HamaConfiguration)Plan.conf,MRQLFileInputFormat.class);
+	job.setInputPath(file);
+	final InputSplit[] splits = getSplits(job,1);
+	final RecordReader<MRContainer,MRContainer> rd = getRecordReader(splits[0],job);
+	return new Bag(new BagIterator () {
+		RecordReader<MRContainer,MRContainer> reader = rd;
+		MRContainer key = reader.createKey();
+		MRContainer value = reader.createKey();
+		int i = 0;
+		public boolean hasNext () {
+		    try {
+			if (reader.next(key,value))
+			    return true;
+			do {
+			    if (++i >= splits.length)
+				return false;
+			    reader.close();
+			    reader = getRecordReader(splits[i],job);
+			} while (!reader.next(key,value));
+			return true;
+		    } catch (IOException e) {
+			throw new Error("Cannot collect values from an intermediate result");
+		    }
+		}
+		public MRData next () {
+		    return value.data();
+		}
+	    });
+    }
+
+    /** materialize the entire dataset into a Bag
+     * @param x the DataSet in HDFS to collect values from
+     * @param strip true if you want to stripout the source id (used in BSP sources)
+     * @return the Bag that contains the collected values
+     */
+    public final static Bag collect ( final DataSet x, boolean strip ) throws Exception {
+	Bag res = new Bag();
+	for ( DataSource s: x.source )
+	    if (s.to_be_merged)
+		res = res.union(Plan.merge(s));
+	    else {
+		Path path = new Path(s.path);
+		final FileSystem fs = path.getFileSystem(Plan.conf);
+		final FileStatus[] ds
+		    = fs.listStatus(path,
+				    new PathFilter () {
+			                public boolean accept ( Path path ) {
+					    return !path.getName().startsWith("_");
+					}
+				    });
+		Bag b = new Bag();
+		for ( FileStatus st: ds )
+		    b = b.union(s.inputFormat.newInstance().materialize(st.getPath()));
+		if (strip) {
+		    // remove source_num
+		    final Iterator<MRData> iter = b.iterator();
+		    b = new Bag(new BagIterator() {
+			    public boolean hasNext () {
+				return iter.hasNext();
+			    }
+			    public MRData next () {
+				return ((Tuple)iter.next()).get(1);
+			    }
+			});
+		};
+		res = res.union(b);
+	    };
+	return res;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/BSP/MultipleBSPInput.java
----------------------------------------------------------------------
diff --git a/src/main/java/BSP/MultipleBSPInput.java b/src/main/java/BSP/MultipleBSPInput.java
new file mode 100644
index 0000000..67f08f9
--- /dev/null
+++ b/src/main/java/BSP/MultipleBSPInput.java
@@ -0,0 +1,49 @@
+/**
+ * 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.mrql;
+
+import org.apache.mrql.gen.Trees;
+import java.io.*;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hama.bsp.*;
+
+
+/** A FileInputFormat for multiple files, where each file may be associated with
+ *   a different FileInputFormat */
+final public class MultipleBSPInput extends MRQLFileInputFormat {
+    public RecordReader<MRContainer,MRContainer>
+	      getRecordReader ( InputSplit split, BSPJob job ) throws IOException {
+	String path = ((FileSplit)split).getPath().toString();
+	Configuration conf = BSPPlan.getConfiguration(job);
+	DataSource ds = DataSource.get(path,conf);
+	Plan.conf = conf;
+	if (ds instanceof ParsedDataSource)
+	    return new ParsedInputFormat.ParsedRecordReader((FileSplit)split,
+							    job,
+							    ((ParsedDataSource)ds).parser,
+							    ds.source_num,
+							    (Trees)((ParsedDataSource)ds).args);
+	else if (ds instanceof BinaryDataSource)
+	    return new BinaryInputFormat.BinaryInputRecordReader((FileSplit)split,job,ds.source_num);
+	else if (ds instanceof GeneratorDataSource)
+	    return new GeneratorInputFormat.GeneratorRecordReader((FileSplit)split,ds.source_num,job);
+	else throw new Error("Unknown data source: "+ds+" for path "+path);
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/BSP/ParsedInputFormat.java
----------------------------------------------------------------------
diff --git a/src/main/java/BSP/ParsedInputFormat.java b/src/main/java/BSP/ParsedInputFormat.java
new file mode 100644
index 0000000..d7bc3f8
--- /dev/null
+++ b/src/main/java/BSP/ParsedInputFormat.java
@@ -0,0 +1,102 @@
+/**
+ * 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.mrql;
+
+import org.apache.mrql.gen.Trees;
+import java.io.*;
+import java.util.Iterator;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hama.bsp.*;
+
+
+/** A FileInputFormat for text files (CVS, XML, JSON, ...) */
+final public class ParsedInputFormat extends MRQLFileInputFormat {
+    public static class ParsedRecordReader implements RecordReader<MRContainer,MRContainer> {
+	final FSDataInputStream fsin;
+	final long start;
+	final long end;
+	final int source_number;
+	final MRData source_num_data;
+	Iterator<MRData> result;
+	Parser parser;
+
+	public ParsedRecordReader ( FileSplit split,
+				    BSPJob job,
+				    Class<? extends Parser> parser_class,
+				    int source_number,
+				    Trees args ) throws IOException {
+	    Configuration conf = BSPPlan.getConfiguration(job);
+	    start = split.getStart();
+	    end = start + split.getLength();
+	    Path file = split.getPath();
+	    FileSystem fs = file.getFileSystem(conf);
+	    fsin = fs.open(split.getPath());
+	    try {
+		parser = parser_class.newInstance();
+	    } catch (Exception ex) {
+		throw new Error("Unrecognized parser:"+parser_class);
+	    };
+	    this.source_number = source_number;
+	    source_num_data = new MR_int(source_number);
+	    parser.initialize(args);
+	    parser.open(fsin,start,end);
+	    result = null;
+	}
+
+        public MRContainer createKey () {
+	    return new MRContainer();
+	}
+
+	public MRContainer createValue () {
+	    return new MRContainer();
+	}
+
+	public synchronized boolean next ( MRContainer key, MRContainer value ) throws IOException {
+	    while (result == null || !result.hasNext()) {
+		String s = parser.slice();
+		if (s == null)
+		    return false;
+		result = parser.parse(s).iterator();
+	    };
+	    value.set(new Tuple(source_num_data,(MRData)result.next()));
+	    key.set(new MR_long(fsin.getPos()));
+	    return true;
+	}
+
+	public synchronized long getPos () throws IOException { return fsin.getPos(); }
+
+	public synchronized void close () throws IOException { fsin.close(); }
+
+	public float getProgress () throws IOException {
+	    if (end == start)
+		return 0.0f;
+	    else return Math.min(1.0f, (getPos() - start) / (float)(end - start));
+	}
+    }
+
+    public RecordReader<MRContainer,MRContainer>
+	      getRecordReader ( InputSplit split,
+				BSPJob job ) throws IOException {
+	Configuration conf = BSPPlan.getConfiguration(job);
+	String path = ((FileSplit)split).getPath().toString();
+	ParsedDataSource ds = (ParsedDataSource)DataSource.get(path,conf);
+	return new ParsedRecordReader((FileSplit)split,job,ds.parser,ds.source_num,(Trees)ds.args);
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/MapReduce/BinaryInputFormat.java
----------------------------------------------------------------------
diff --git a/src/main/java/MapReduce/BinaryInputFormat.java b/src/main/java/MapReduce/BinaryInputFormat.java
new file mode 100644
index 0000000..2a5ad52
--- /dev/null
+++ b/src/main/java/MapReduce/BinaryInputFormat.java
@@ -0,0 +1,80 @@
+/**
+ * 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.mrql;
+
+import java.io.*;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.mapreduce.RecordReader;
+import org.apache.hadoop.mapreduce.InputSplit;
+import org.apache.hadoop.mapreduce.TaskAttemptContext;
+import org.apache.hadoop.mapreduce.lib.input.SequenceFileInputFormat;
+
+
+/** Input format for hadoop sequence files */
+final public class BinaryInputFormat extends MRQLFileInputFormat {
+    final static SequenceFileInputFormat<MRContainer,MRContainer> inputFormat
+	                       = new SequenceFileInputFormat<MRContainer,MRContainer>();
+
+    public RecordReader<MRContainer,MRContainer>
+	      createRecordReader ( InputSplit split,
+				   TaskAttemptContext context ) throws IOException, InterruptedException {
+	return inputFormat.createRecordReader(split,context);
+    }
+
+    /** collect the data from multiple sequence files at the path directory into a Bag
+     * @param path the path directory
+     * @return a Bag that contains all data
+     */
+    public Bag materialize ( final Path path ) throws IOException {
+	final FileSystem fs = path.getFileSystem(Plan.conf);
+	final FileStatus[] ds
+	           = fs.listStatus(path,
+				   new PathFilter () {
+				       public boolean accept ( Path path ) {
+					   return !path.getName().startsWith("_");
+				       }
+				   });
+	if (ds.length > 0)
+	    return new Bag(new BagIterator () {
+		    SequenceFile.Reader reader = new SequenceFile.Reader(fs,ds[0].getPath(),Plan.conf);
+		    MRContainer key = new MRContainer(new MR_int(0));
+		    MRContainer value = new MRContainer(new MR_int(0));
+		    int i = 1;
+		    public boolean hasNext () {
+			try {
+			    if (reader.next(key,value))
+				return true;
+			    do {
+				if (i >= ds.length)
+				    return false;
+				reader.close();
+				reader = new SequenceFile.Reader(fs,ds[i++].getPath(),Plan.conf);
+			    } while (!reader.next(key,value));
+			    return true;
+			} catch (IOException e) {
+			    throw new Error("Cannot collect values from an intermediate result");
+			}
+		    }
+		    public MRData next () {
+			return value.data();
+		    }
+		});
+	return new Bag();
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/MapReduce/CrossProductOperation.java
----------------------------------------------------------------------
diff --git a/src/main/java/MapReduce/CrossProductOperation.java b/src/main/java/MapReduce/CrossProductOperation.java
new file mode 100644
index 0000000..78b313e
--- /dev/null
+++ b/src/main/java/MapReduce/CrossProductOperation.java
@@ -0,0 +1,235 @@
+/**
+ * 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.mrql;
+
+import org.apache.mrql.gen.*;
+import java.io.*;
+import java.net.URI;
+import java.util.List;
+import java.util.Vector;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.mapreduce.*;
+import org.apache.hadoop.mapreduce.lib.input.MultipleInputs;
+import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
+import org.apache.hadoop.mapreduce.lib.output.SequenceFileOutputFormat;
+import org.apache.hadoop.filecache.DistributedCache;
+
+
+/** The CrossProduct physical operation (similar to block-nested loop) */
+final public class CrossProductOperation extends MapReducePlan {
+
+    /** The mapper for the CrossProduct operation */
+    private final static class crossProductMapper extends Mapper<MRContainer,MRContainer,MRContainer,MRContainer> {
+	private static String counter;       // a Hadoop user-defined counter used in the repeat operation
+	private static Function reduce_fnc;  // the reduce function
+	private static Function map_fnc;     // the mapper function
+	private static DataSet cached_dataset;
+	private final static List<MRData> outer
+	    = new Vector<MRData>(Config.map_cache_size);  // fix-size cache for the outer
+	private static int index;
+	private static MRContainer last_key;
+	private static URI[] uris;
+	private static Path[] local_paths;
+	private static Function acc_fnc;     // aggregator
+	private static MRData result;        // aggregation result
+	private static Tuple pair = new Tuple(2);
+	private static MRContainer container = new MRContainer(new MR_int(0));
+
+	private void write ( MRContainer key, MRData value, Context context )
+	             throws IOException, InterruptedException {
+	    if (result != null) {  // aggregation
+		pair.set(0,result);
+		pair.set(1,value);
+		result = acc_fnc.eval(pair);
+	    } else if (counter.equals("-")) {
+		container.set(value);
+		context.write(key,container);
+	    } else {     // increment the repetition counter if the repeat condition is true
+		Tuple t = (Tuple)value;
+		if (((MR_bool)t.second()).get())
+		    context.getCounter("mrql",counter).increment(1);
+		container.set(t.first());
+		context.write(key,container);
+	    }
+	}
+
+	@Override
+	public void map ( MRContainer key, MRContainer value, Context context )
+	            throws IOException, InterruptedException {
+	    try {
+		last_key = key;
+		for ( MRData x: (Bag)map_fnc.eval(value.data()) )
+		    if (index++ == Config.map_cache_size) {
+			for ( MRData y: cached_data(context.getConfiguration()) ) {
+			    pair.set(1,y);
+			    for ( MRData z: outer ) {
+				pair.set(0,z);
+				for ( MRData v: (Bag)reduce_fnc.eval(pair) )
+				    write(key,v,context);
+			    }
+			};
+			index = 0;
+			outer.clear();
+		    } else outer.add(x);
+	    } catch (Exception e) {
+		throw new Error("Cannot perform the crossProduct: "+e);
+	    }
+	}
+
+	protected Bag cached_data ( final Configuration conf ) {
+	    try {
+		Bag res = new Bag();
+		final FileSystem fs = FileSystem.getLocal(conf);
+		for ( int i = 0; i < local_paths.length; i++ ) {
+		    // hadoop 0.20.2 distributed cache doesn't work in stand-alone
+		    final Path path = (conf.get("mapred.job.tracker").equals("local"))
+			              ? new Path(uris[i].toString())
+			              : local_paths[i];
+		    if (path.getName().endsWith(".jar"))
+			continue;
+		    res = res.union(new Bag(new BagIterator () {
+			    final SequenceFile.Reader reader = new SequenceFile.Reader(fs,path,conf);
+			    final MRContainer key = new MRContainer(new MR_int(0));
+			    final MRContainer value = new MRContainer(new MR_int(0));
+			    public boolean hasNext () {
+				try {
+				    boolean done = reader.next(key,value);
+				    if (!done)
+					reader.close();
+				    return done;
+				} catch (IOException e) {
+				    throw new Error("Cannot collect values from distributed cache");
+				}
+			    }
+			    public MRData next () {
+				return value.data();
+			    }
+			}));
+		};
+		return res;
+	    } catch (Exception e) {
+		throw new Error("Cannot setup the cross product: "+e);
+	    }
+	}
+
+	@Override
+	protected void setup ( Context context ) throws IOException,InterruptedException {
+	    super.setup(context);
+	    try {
+		Configuration conf = context.getConfiguration();
+		Config.read(conf);
+		if (Plan.conf == null)
+		    Plan.conf = conf;
+		Tree code = Tree.parse(conf.get("mrql.reducer"));
+		reduce_fnc = functional_argument(conf,code);
+		code = Tree.parse(conf.get("mrql.mapper"));
+		map_fnc = functional_argument(conf,code);
+		if (conf.get("mrql.zero") != null) {
+		    code = Tree.parse(conf.get("mrql.zero"));
+		    result = Interpreter.evalE(code);
+		    code = Tree.parse(conf.get("mrql.accumulator"));
+		    acc_fnc = functional_argument(conf,code);
+		} else result = null;
+		counter = conf.get("mrql.counter");
+		uris = DistributedCache.getCacheFiles(conf);
+		local_paths = DistributedCache.getLocalCacheFiles(conf);
+		index = 0;
+	    } catch (Exception e) {
+		throw new Error("Cannot setup the crossProduct: "+e);
+	    }
+	}
+
+	@Override
+	protected void cleanup ( Context context ) throws IOException,InterruptedException {
+	    if (index > 0)
+		try {
+		    for ( MRData y: cached_data(context.getConfiguration()) ) {
+			pair.set(1,y);
+			for ( MRData z: outer ) {
+			    pair.set(0,z);
+			    for ( MRData v: (Bag)reduce_fnc.eval(pair) )
+				write(last_key,v,context);
+			}
+		    };
+		} catch (Exception e) {
+		    throw new Error("Cannot cleanup the crossProduct: "+e);
+		};
+	    index = 0;
+	    outer.clear();
+	    if (result != null)  // emit the result of aggregation
+		context.write(new MRContainer(new MR_int(0)),new MRContainer(result));
+	    super.cleanup(context);
+	}
+    }
+
+    /** The CrossProduct physical operator (similar to block-nested loop)
+     * @param mx              left mapper
+     * @param my              right mapper
+     * @param reduce_fnc      reducer
+     * @param acc_fnc         optional accumulator function
+     * @param zero            optional the zero value for the accumulator
+     * @param X               the left source
+     * @param Y               the right source (stored in distributed cache)
+     * @param stop_counter    optional counter used in repeat operation
+     * @return a new data source that contains the result
+     */
+    public final static DataSet crossProduct ( Tree mx,              // left mapper
+					       Tree my,              // right mapper
+					       Tree reduce_fnc,      // reducer
+					       Tree acc_fnc,         // optional accumulator function
+					       Tree zero,            // optional the zero value for the accumulator
+					       DataSet X,            // the left source
+					       DataSet Y,            // the right source (stored in distributed cache)
+					       String stop_counter ) // optional counter used in repeat operation
+                                 throws Exception {
+	DataSet ds = MapOperation.cMap(my,null,null,Y,"-");
+	String newpath = new_path(conf);
+	conf.set("mrql.reducer",reduce_fnc.toString());
+	conf.set("mrql.mapper",mx.toString());
+	if (zero != null) {
+	    conf.set("mrql.accumulator",acc_fnc.toString());
+	    conf.set("mrql.zero",zero.toString());
+	    conf.set("mapred.min.split.size","268435456");
+	} else conf.set("mrql.zero","");
+	conf.set("mrql.counter",stop_counter);
+	Job job = new Job(conf,newpath);
+	distribute_compiled_arguments(job.getConfiguration());
+	job.setJarByClass(MapReducePlan.class);
+	job.setOutputKeyClass(MRContainer.class);
+	job.setOutputValueClass(MRContainer.class);
+	job.setOutputFormatClass(SequenceFileOutputFormat.class);
+	PathFilter pf = new PathFilter () { public boolean accept ( Path path ) {
+	                                        return !path.getName().startsWith("_");
+	                                    } };
+	for (DataSource p: ds.source) {
+	    Path path = new Path(p.path);
+	    for ( FileStatus s: path.getFileSystem(conf).listStatus(path,pf) )
+		DistributedCache.addCacheFile(s.getPath().toUri(),job.getConfiguration());
+	};
+	for (DataSource p: X.source)
+	    MultipleInputs.addInputPath(job,new Path(p.path),p.inputFormat,crossProductMapper.class);
+	FileOutputFormat.setOutputPath(job,new Path(newpath));
+	job.setNumReduceTasks(0);
+	job.waitForCompletion(true);
+	long c = (stop_counter.equals("-")) ? 0
+	         : job.getCounters().findCounter("mrql",stop_counter).getValue();
+	return new DataSet(new BinaryDataSource(newpath,conf),c,outputRecords(job));
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/MapReduce/Evaluator.gen
----------------------------------------------------------------------
diff --git a/src/main/java/MapReduce/Evaluator.gen b/src/main/java/MapReduce/Evaluator.gen
new file mode 100644
index 0000000..cb2d50f
--- /dev/null
+++ b/src/main/java/MapReduce/Evaluator.gen
@@ -0,0 +1,296 @@
+/**
+ * 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, softwar	if (hadoop)e
+ * 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.mrql;
+
+import java_cup.runtime.*;
+import org.apache.mrql.gen.*;
+import java.util.*;
+import java.io.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+
+
+/** Evaluates physical plans in Hadoop MapReduce mode */
+final public class Evaluator extends Interpreter {
+
+    /** initialize the MapReduce evaluator */
+    final static void init ( Configuration conf ) {
+	Config.map_reduce_mode = true;
+	if (Config.hadoop_mode)
+            if (Config.local_mode) {
+                conf.set("mapred.job.tracker","local");
+                conf.set("fs.default.name","file:///");
+            } else {
+                conf.set("mapred.job.tracker",System.getenv("MAPRED_JOB_TRACKER"));
+                conf.set("fs.default.name",System.getenv("FS_DEFAULT_NAME"));
+            }
+    }
+
+    /** shutdown the MapReduce evaluator */
+    final static void shutdown ( Configuration conf ) {
+    }
+
+    final static void initialize_query () {
+    }
+
+    final static Configuration new_configuration () {
+	return new Configuration();
+    }
+
+    public static MR_bool synchronize ( MR_string peerName, MR_bool mr_exit ) {
+	throw new Error("You can only synchronize BSP tasks");
+    }
+
+    public static Bag distribute ( MR_string peerName, Bag s ) {
+	throw new Error("You can only distribute bags among BSP tasks");
+    }
+
+    final static Bag collect ( final DataSet x ) throws Exception {
+	return MapReducePlan.collect(x);
+    }
+
+    final static MRData bsp ( Tree plan, Environment env ) throws Exception {
+	throw new Error("You can not run a BSP task in Map-Reduce mode");
+    }
+
+    /** The Aggregate physical operator
+     * @param acc_fnc  the accumulator function from (T,T) to T
+     * @param zero  the zero element of type T
+     * @param plan the plan that constructs the dataset that contains the bag of values {T}
+     * @param env contains bindings fro variables to values (MRData)
+     * @returns the aggregation result of type T
+     */
+    final static MRData aggregate ( Tree acc_fnc,
+				    Tree zero,
+				    Tree plan,
+				    Environment env ) throws Exception {
+	return MapReducePlan.aggregate(acc_fnc,zero,eval(plan,env,"-"));
+    }
+
+    /** Evaluate a loop a fixed # of times */
+    final static Tuple loop ( Tree e, Environment env ) throws Exception {
+	match e {
+	case Loop(lambda(tuple(...vs),tuple(...bs)),tuple(...ss),`num):
+	    int limit = ((MR_int)evalE(num,env)).get();
+	    MR_dataset[] s = new MR_dataset[vs.length()];
+	    for ( int i = 0; i < vs.length(); i++ )
+		s[i] = new MR_dataset(eval(ss.nth(i),env,"-"));
+	    for ( int n = 0; n < limit; n++ ) {
+		Environment nenv = env;
+		for ( int i = 0; i < vs.length(); i ++ )
+		    nenv = new Environment(vs.nth(i).toString(),s[i],nenv);
+		for ( int i = 0; i < vs.length(); i ++ )
+		    s[i] = new MR_dataset(eval(bs.nth(i),nenv,"-"));
+	    };
+	    return new Tuple(s);
+	};
+	throw new Error("Wrong Loop format");
+    }
+
+    /** Evaluate an MRQL physical plan using Hadoop and print tracing info
+     * @param e the physical plan
+     * @param env contains bindings fro variables to values (MRData)
+     * @param tne name of the counter used in loops
+     * @return a DataSet (stored in HDFS)
+     */
+    final static DataSet eval ( final Tree e,
+				final Environment env,
+				final String counter ) {
+	if (Config.trace_execution) {
+	    tab_count += 3;
+	    System.out.println(tabs(tab_count)+print_query(e));
+	};
+	DataSet res = evalD(e,env,counter);
+	if (Config.trace_execution) 
+	    try {
+		System.out.println(tabs(tab_count)
+				   +"-> "+MapReducePlan.collect(res));
+		tab_count -= 3;
+	    } catch (Exception ex) {
+		throw new Error("Cannot collect the operator output: "+e);
+	    };
+	return res;
+    }
+
+    /** Evaluate MRQL physical operators using Hadoop
+     * @param e the physical plan
+     * @param env contains bindings fro variables to values (MRData)
+     * @param tne name of the counter used in loops
+     * @return a DataSet (stored in HDFS)
+     */
+    final static DataSet evalD ( final Tree e,
+				 final Environment env,
+				 final String counter ) {
+	try {
+	    match e {
+	    case cMap(`f,`s):
+		return MapOperation.cMap(closure(f,env),null,null,eval(s,env,"-"),counter);
+	    case AggregateMap(`f,`acc,`zero,`s):
+		return MapOperation.cMap(closure(f,env),closure(acc,env),
+					 (zero.equals(#<null>))?null:zero,
+					 eval(s,env,"-"),counter);
+	    case MapReduce(`m,`r,`s,`o):
+		return MapReduceOperation.mapReduce(closure(m,env),#<null>,closure(r,env),
+						    null,null,
+						    eval(s,env,"-"),
+						    Config.nodes,counter,
+						    o.equals(#<true>));
+	    case MapAggregateReduce(`m,`r,`acc,`zero,`s,`o):
+		return MapReduceOperation.mapReduce(closure(m,env),null,closure(r,env),
+						    closure(acc,env),
+						    (zero.equals(#<null>))?null:zero,
+						    eval(s,env,"-"),
+						    Config.nodes,counter,
+						    o.equals(#<true>));
+	    case MapCombineReduce(`m,`c,`r,`s,`o):
+		return MapReduceOperation.mapReduce(closure(m,env),closure(c,env),closure(r,env),
+						    null,null,
+						    eval(s,env,"-"),
+						    Config.nodes,counter,
+						    o.equals(#<true>));
+	    case CrossProduct(`mx,`my,`r,`x,`y):
+		return CrossProductOperation.crossProduct(closure(mx,env),closure(my,env),closure(r,env),
+							  null,null,
+							  eval(x,env,"-"),
+							  eval(y,env,"-"),
+							  counter);
+	    case CrossAggregateProduct(`mx,`my,`r,`acc,`zero,`x,`y):
+		return CrossProductOperation.crossProduct(closure(mx,env),closure(my,env),closure(r,env),
+							  closure(acc,env),
+							  (zero.equals(#<null>))?null:zero,
+							  eval(x,env,"-"),
+							  eval(y,env,"-"),
+							  counter);
+	    case MapReduce2(`mx,`my,`r,`x,`y,`o):
+		return eval(#<MapAggregateReduce2(`mx,`my,`r,null,null,`x,`y,`o)>,env,counter);
+	    case MapCombineReduce2(`mx,`my,`c,`r,`x,`y,`o):
+		return JoinOperation.mapReduce2(closure(mx,env),closure(my,env),
+						closure(c,env),
+						closure(r,env),
+						null,null,
+						eval(x,env,"-"),
+						eval(y,env,"-"),
+						Config.nodes,counter,
+						o.equals(#<true>));
+	    case MapAggregateReduce2(`mx,`my,`r,`acc,`zero,`x,`y,`o):
+		return JoinOperation.mapReduce2(closure(mx,env),closure(my,env),
+						null,
+						closure(r,env),closure(acc,env),
+						(zero.equals(#<null>))?null:zero,
+						eval(x,env,"-"),
+						eval(y,env,"-"),
+						Config.nodes,counter,
+						o.equals(#<true>));
+	    case GroupByJoin(`kx,`ky,`gx,`gy,`mp,`c,`r,`x,`y,`o):
+		DataSet X = eval(x,env,"-");
+		DataSet Y = eval(y,env,"-");
+		int n = (int)Math.ceil(X.size(MapReducePlan.conf)/10000.0/Math.sqrt((float)Config.mapjoin_size));
+		int m = (int)Math.ceil(Y.size(MapReducePlan.conf)/10000.0/Math.sqrt((float)Config.mapjoin_size));
+		System.err.println("*** Using a groupBy join on a "+n+"*"+m+" grid of partitions");
+		return GroupByJoinPlan.groupByJoin(closure(kx,env),closure(ky,env),
+						   closure(gx,env),closure(gy,env),
+						   closure(mp,env),closure(c,env),closure(r,env),
+						   X,Y,
+						   Config.nodes,
+						   n,m,counter);
+	    case MapJoin(`mx,`my,`r,`x,`y):
+		return MapJoinOperation.mapJoin(closure(mx,env),closure(my,env),closure(r,env),
+						null,null,
+						eval(x,env,"-"),
+						eval(y,env,"-"),
+						counter);
+	    case MapAggregateJoin(`mx,`my,`r,`acc,`zero,`x,`y):
+		return MapJoinOperation.mapJoin(closure(mx,env),closure(my,env),closure(r,env),
+						closure(acc,env),
+						(zero.equals(#<null>))?null:zero,
+						eval(x,env,"-"),
+						eval(y,env,"-"),
+						counter);
+	    case BinarySource(`file,_):
+		return Plan.binarySource(file.stringValue());
+	    case ParsedSource(`parser,`file,...args):
+		Class<? extends Parser> p = DataSource.parserDirectory.get(parser.toString());
+		if (p == null)
+		    throw new Error("Unknown parser: "+parser);
+		return Plan.parsedSource(p,((MR_string)evalE(file,env)).get(),args);
+	    case Merge(`x,`y):
+		return Plan.merge(eval(x,env,"-"),eval(y,env,"-"));
+	    case Repeat(lambda(`v,`b),`s,`n):
+		final String nm = v.toString();
+		final Tree body = b;
+		Function loop_fnc = new Function () {
+			public MRData eval ( MRData s ) {
+			    return new MR_dataset(Evaluator.eval(body,new Environment(nm,s,env),nm));
+			}; };
+		return MapReducePlan.repeat(loop_fnc,eval(s,env,"-"),((MR_int)evalE(n,env)).get());
+	    case Closure(lambda(`v,`b),`s,`n):
+		final String nm = v.toString();
+		final Tree body = b;
+		Function loop_fnc = new Function () {
+			public MRData eval ( MRData s ) {
+			    return new MR_dataset(Evaluator.eval(body,new Environment(nm,s,env),"-"));
+			}; };
+		return MapReducePlan.closure(loop_fnc,eval(s,env,"-"),((MR_int)evalE(n,env)).get());
+	    case Generator(`min,`max,`size):
+		return Plan.generator(((MR_long)evalE(min,env)).get(),
+				      ((MR_long)evalE(max,env)).get(),
+				      ((MR_long)evalE(size,env)).get());
+	    case let(`v,`u,`body):
+		return eval(body,new Environment(v.toString(),evalE(u,env),env),"-");
+	    case Let(`v,`u,`body):
+		return eval(body,new Environment(v.toString(),new MR_dataset(eval(u,env,"-")),env),"-");
+	    case If(`c,`x,`y):
+		if (((MR_bool)evalE(c,env)).get())
+		    return eval(x,env,"-");
+		else return eval(y,env,"-");
+	    case apply(`f,`arg):
+		if (!f.is_variable())
+		    return ((MR_dataset)evalF(f,env).eval(evalE(arg))).dataset();
+		MRData fnc = variable_lookup(f.toString(),global_env);
+		if (fnc == null)
+		    throw new Error("Unknown function: "+f);
+		MRData t = evalE(arg,env);
+		if (!(t instanceof Tuple))
+		    throw new Error("Expected a tuple in function application: "+t);
+		return ((MR_dataset)((Lambda)fnc).lambda().eval(t)).dataset();
+	    case `v:
+		if (!v.is_variable())
+		    fail;
+		MRData x = variable_lookup(v.toString(),env);
+		if (x != null)
+		    if (x instanceof MR_dataset)
+			return ((MR_dataset)x).dataset();
+		x = variable_lookup(v.toString(),global_env);
+		if (x != null)
+		    if (x instanceof MR_dataset)
+			return ((MR_dataset)x).dataset();
+		throw new Error("Variable "+v+" is not bound");
+	    };
+	    throw new Error("Cannot evaluate the map-reduce plan: "+e);
+	} catch (Error msg) {
+	    if (!Config.trace)
+		throw new Error(msg.getMessage());
+	    System.err.println(msg.getMessage());
+	    throw new Error("Evaluation error in: "+print_query(e));
+	} catch (Exception ex) {
+	    System.err.println(ex.getMessage());
+	    ex.printStackTrace();
+	    throw new Error("Evaluation error in: "+print_query(e));
+	}
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mrql/blob/f5e66d20/src/main/java/MapReduce/GeneratorInputFormat.java
----------------------------------------------------------------------
diff --git a/src/main/java/MapReduce/GeneratorInputFormat.java b/src/main/java/MapReduce/GeneratorInputFormat.java
new file mode 100644
index 0000000..86f461a
--- /dev/null
+++ b/src/main/java/MapReduce/GeneratorInputFormat.java
@@ -0,0 +1,114 @@
+/**
+ * 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.mrql;
+
+import java.io.*;
+import java.util.Iterator;
+import org.apache.hadoop.fs.*;
+import org.apache.hadoop.io.*;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.mapreduce.InputSplit;
+import org.apache.hadoop.mapreduce.TaskAttemptContext;
+import org.apache.hadoop.mapreduce.RecordReader;
+import org.apache.hadoop.mapreduce.lib.input.FileSplit;
+
+
+/** the FileInputFormat for data generators: it creates HDFS files, where each file contains
+ *  an (offset,size) pair that generates the range of values [offset,offset+size] */
+final public class GeneratorInputFormat extends MRQLFileInputFormat {
+    public static class GeneratorRecordReader extends RecordReader<MRContainer,MRContainer> {
+	final long offset;
+	final long size;
+	long index;
+	SequenceFile.Reader reader;
+
+	public GeneratorRecordReader ( FileSplit split,
+				       TaskAttemptContext context ) throws IOException {
+	    Configuration conf = context.getConfiguration();
+	    Path path = split.getPath();
+	    FileSystem fs = path.getFileSystem(conf);
+	    reader = new SequenceFile.Reader(path.getFileSystem(conf),path,conf);
+	    MRContainer key = new MRContainer();
+	    MRContainer value = new MRContainer();
+	    reader.next(key,value);
+	    offset = ((MR_long)((Tuple)(value.data())).first()).get();
+	    size = ((MR_long)((Tuple)(value.data())).second()).get();
+	    index = -1;
+	}
+
+	public boolean nextKeyValue () throws IOException {
+	    index++;
+	    return index < size;
+	}
+
+        public MRContainer getCurrentKey () throws IOException {
+	    return new MRContainer(new MR_long(index));
+	}
+
+	public MRContainer getCurrentValue () throws IOException {
+	    return new MRContainer(new MR_long(offset+index));
+	}
+
+	public void close () throws IOException { reader.close(); }
+
+	public float getProgress () throws IOException {
+	    return index / (float)size;
+	}
+
+	public void initialize ( InputSplit split, TaskAttemptContext context ) throws IOException { }
+    }
+
+    public RecordReader<MRContainer,MRContainer>
+	      createRecordReader ( InputSplit split, TaskAttemptContext context ) throws IOException {
+	return new GeneratorRecordReader((FileSplit)split,context);
+    }
+
+    /** Insert all results from the generators stored in path into a Bag.
+     *  The Bag is lazily constructed.
+     * @param path the path directory that contains the generator data (offset,size)
+     * @return a Bag that contains all data
+     */
+    Bag materialize ( final Path path ) throws IOException {
+	Configuration conf = Plan.conf;
+	FileSystem fs = path.getFileSystem(conf);
+	final SequenceFile.Reader reader = new SequenceFile.Reader(path.getFileSystem(conf),path,conf);
+	final MRContainer key = new MRContainer();
+	final MRContainer value = new MRContainer();
+	return new Bag(new BagIterator () {
+		long offset = 0;
+		long size = 0;
+		long i = 0;
+		public boolean hasNext () {
+		    if (++i >= offset+size)
+			try {
+			    if (!reader.next(key,value))
+				return false;
+			    offset = ((MR_long)((Tuple)(value.data())).first()).get();
+			    size = ((MR_long)((Tuple)(value.data())).second()).get();
+			    i = offset;
+			} catch (IOException e) {
+			    throw new Error("Cannot collect values from a generator");
+			};
+		    return true;
+		}
+		public MRData next () {
+		    return new MR_long(i);
+		}
+	    });
+    }
+}