You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pig.apache.org by ga...@apache.org on 2009/08/12 00:27:47 UTC

svn commit: r803312 [3/16] - in /hadoop/pig/trunk: ./ contrib/zebra/ contrib/zebra/docs/ contrib/zebra/src/ contrib/zebra/src/java/ contrib/zebra/src/java/org/ contrib/zebra/src/java/org/apache/ contrib/zebra/src/java/org/apache/hadoop/ contrib/zebra/s...

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/BasicTableOutputFormat.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/BasicTableOutputFormat.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/BasicTableOutputFormat.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/BasicTableOutputFormat.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,340 @@
+/**
+ * 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.hadoop.zebra.mapred;
+
+import java.io.IOException;
+
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.BytesWritable;
+import org.apache.hadoop.mapred.JobConf;
+import org.apache.hadoop.mapred.OutputFormat;
+import org.apache.hadoop.mapred.RecordWriter;
+import org.apache.hadoop.mapred.Reporter;
+import org.apache.hadoop.util.Progressable;
+import org.apache.hadoop.zebra.io.BasicTable;
+import org.apache.hadoop.zebra.io.TableInserter;
+import org.apache.hadoop.zebra.types.ParseException;
+import org.apache.hadoop.zebra.types.Partition;
+import org.apache.hadoop.zebra.types.Schema;
+import org.apache.pig.data.Tuple;
+
+/**
+ * {@link org.apache.hadoop.mapred.OutputFormat} class for creating a
+ * BasicTable.
+ * 
+ * Usage Example:
+ * <p>
+ * In the main program, add the following code.
+ * 
+ * <pre>
+ * jobConf.setOutputFormat(BasicTableOutputFormat.class);
+ * Path outPath = new Path(&quot;path/to/the/BasicTable&quot;);
+ * BasicTableOutputFormat.setOutputPath(jobConf, outPath);
+ * BasicTableOutputFormat.setSchema(jobConf, &quot;Name, Age, Salary, BonusPct&quot;);
+ * </pre>
+ * 
+ * The above code does the following things:
+ * <UL>
+ * <LI>Set the output format class to BasicTableOutputFormat.
+ * <LI>Set the path to the BasicTable to be created.
+ * <LI>Set the schema of the BasicTable to be created. In this case, the
+ * to-be-created BasicTable contains three columns with names "Name", "Age",
+ * "Salary", "BonusPct".
+ * </UL>
+ * The user Reducer code (or similarly Mapper code if it is a Map-only job)
+ * should look like the following:
+ * 
+ * <pre>
+ * static class MyReduceClass implements Reducer&lt;K, V, BytesWritable, Tuple&gt; {
+ *   // keep the tuple object for reuse.
+ *   Tuple outRow;
+ *   // indices of various fields in the output Tuple.
+ *   int idxName, idxAge, idxSalary, idxBonusPct;
+ * 
+ *   &#064;Override
+ *   public void configure(JobConf job) {
+ *     Schema outSchema = BasicTableOutputFormat.getSchema(job);
+ *     // create a tuple that conforms to the output schema.
+ *     outRow = TypesUtils.createTuple(outSchema);
+ *     // determine the field indices.
+ *     idxName = outSchema.getColumnIndex(&quot;Name&quot;);
+ *     idxAge = outSchema.getColumnIndex(&quot;Age&quot;);
+ *     idxSalary = outSchema.getColumnIndex(&quot;Salary&quot;);
+ *     idxBonusPct = outSchema.getColumnIndex(&quot;BonusPct&quot;);
+ *   }
+ * 
+ *   &#064;Override
+ *   public void reduce(K key, Iterator&lt;V&gt; values,
+ *       OutputCollector&lt;BytesWritable, Tuple&gt; output, Reporter reporter)
+ *       throws IOException {
+ *     String name;
+ *     int age;
+ *     int salary;
+ *     double bonusPct;
+ *     // ... Determine the value of the individual fields of the row to be inserted.
+ *     try {
+ *       outTuple.set(idxName, name);
+ *       outTuple.set(idxAge, new Integer(age));
+ *       outTuple.set(idxSalary, new Integer(salary));
+ *       outTuple.set(idxBonusPct, new Double(bonusPct));
+ *       output.collect(new BytesWritable(name.getBytes()), outTuple);
+ *     }
+ *     catch (ExecException e) {
+ *       // should never happen
+ *     }
+ *   }
+ * 
+ *   &#064;Override
+ *   public void close() throws IOException {
+ *     // no-op
+ *   }
+ * 
+ * }
+ * </pre>
+ */
+public class BasicTableOutputFormat implements
+    OutputFormat<BytesWritable, Tuple> {
+  private static final String OUTPUT_PATH = "mapred.lib.table.output.dir";
+  private static final String OUTPUT_SCHEMA = "mapred.lib.table.output.schema";
+  private static final String OUTPUT_STORAGEHINT =
+      "mapred.lib.table.output.storagehint";
+  private static final String OUTPUT_SORTED = "mapred.lib.table.output.sorted";
+
+  /**
+   * Set the output path of the BasicTable in JobConf
+   * 
+   * @param conf
+   *          The JobConf object.
+   * @param path
+   *          The output path to the table. The path must either not existent,
+   *          or must be an empty directory.
+   */
+  public static void setOutputPath(JobConf conf, Path path) {
+    conf.set(OUTPUT_PATH, path.toString());
+  }
+
+  /**
+   * Get the output path of the BasicTable from JobConf
+   * 
+   * @param conf
+   *          job conf
+   * @return The output path.
+   */
+  public static Path getOutputPath(JobConf conf) {
+    String path = conf.get(OUTPUT_PATH);
+    return (path == null) ? null : new Path(path);
+  }
+
+  /**
+   * Set the table schema in JobConf
+   * 
+   * @param conf
+   *          The JobConf object.
+   * @param schema
+   *          The schema of the BasicTable to be created. For the initial
+   *          implementation, the schema string is simply a comma separated list
+   *          of column names, such as "Col1, Col2, Col3".
+   * 
+   * @see Schema#Schema(String)
+   */
+  public static void setSchema(JobConf conf, String schema)
+      throws ParseException {
+    conf.set(OUTPUT_SCHEMA, Schema.normalize(schema));
+  }
+
+  /**
+   * Get the table schema in JobConf.
+   * 
+   * @param conf
+   *          The JobConf object.
+   * @return The output schema of the BasicTable. If the schema is not defined
+   *         in the conf object at the time of the call, null will be returned.
+   */
+  public static Schema getSchema(JobConf conf) throws ParseException {
+    String schema = conf.get(OUTPUT_SCHEMA);
+    if (schema == null) {
+      return null;
+    }
+    schema = schema.replaceAll(";", ",");
+    return new Schema(schema);
+  }
+
+  /**
+   * Set the table storage hint in JobConf, should be called after setSchema is
+   * called.
+   * 
+   * @param conf
+   *          The JobConf object.
+   * @param storehint
+   *          The storage hint of the BasicTable to be created. The format would
+   *          be like "[f1, f2.subfld]; [f3, f4]".
+   * 
+   * @see Schema#Schema(String)
+   */
+  public static void setStorageHint(JobConf conf, String storehint)
+      throws ParseException, IOException {
+    String schema = conf.get(OUTPUT_SCHEMA);
+
+    if (schema == null)
+      throw new ParseException("Schema has not been set");
+
+    // for sanity check purpose only
+    Partition partition = new Partition(schema, storehint);
+
+    conf.set(OUTPUT_STORAGEHINT, storehint);
+  }
+
+  /**
+   * Get the table storage hint in JobConf.
+   * 
+   * @param conf
+   *          The JobConf object.
+   * @return The storage hint of the BasicTable. If the storage hint is not
+   *         defined in the conf object at the time of the call, an empty string
+   *         will be returned.
+   */
+  public static String getStorageHint(JobConf conf) throws ParseException {
+    String storehint = conf.get(OUTPUT_STORAGEHINT);
+    return storehint == null ? "" : storehint;
+  }
+
+  /**
+   * Set sorted-ness of the table. It is disabled now (by making it package
+   * private). So only unsorted BasicTables may be created for now.
+   * 
+   * TODO: must also allow users to specify customized comparator.
+   */
+  public static void setSorted(JobConf conf, boolean sorted) {
+    conf.setBoolean(OUTPUT_SORTED, sorted);
+  }
+
+  /**
+   * Is the table to be created should be sorted? It is disabled now (by making
+   * it package private).
+   */
+  static boolean getSorted(JobConf conf) {
+    return conf.getBoolean(OUTPUT_SORTED, false);
+  }
+
+  /**
+   * Get the output table as specified in JobConf. It is useful for applications
+   * to add more meta data after all rows have been added to the table.
+   * Currently it is disabled (by setting it to package private).
+   * 
+   * @param conf
+   *          The JobConf object.
+   * @return The output BasicTable.Writer object.
+   * @throws IOException
+   */
+  public static BasicTable.Writer getOutput(JobConf conf) throws IOException {
+    String path = conf.get(OUTPUT_PATH);
+    if (path == null) {
+      throw new IllegalArgumentException("Cannot find output path");
+    }
+    return new BasicTable.Writer(new Path(path), conf);
+  }
+
+  /**
+   * Note: we perform the Initialization of the table here. So we expect this to
+   * be called before
+   * {@link BasicTableOutputFormat#getRecordWriter(FileSystem, JobConf, String, Progressable)}
+   * 
+   * @see OutputFormat#checkOutputSpecs(FileSystem, JobConf)
+   */
+  @Override
+  public void checkOutputSpecs(FileSystem ignored, JobConf conf)
+      throws IOException {
+    String path = conf.get(OUTPUT_PATH);
+    if (path == null) {
+      throw new IllegalArgumentException("Cannot find output path");
+    }
+
+    String schema = conf.get(OUTPUT_SCHEMA);
+    if (schema == null) {
+      throw new IllegalArgumentException("Cannot find output schema");
+    }
+    String storehint;
+    try {
+      storehint = getStorageHint(conf);
+    }
+    catch (ParseException e) {
+      throw new IOException(e);
+    }
+    BasicTable.Writer writer =
+        new BasicTable.Writer(new Path(path), schema, storehint,
+            getSorted(conf), conf); // will
+
+    writer.finish();
+  }
+
+  /**
+   * @see OutputFormat#getRecordWriter(FileSystem, JobConf, String,
+   *      Progressable)
+   */
+  @Override
+  public RecordWriter<BytesWritable, Tuple> getRecordWriter(FileSystem ignored,
+      JobConf conf, String name, Progressable progress) throws IOException {
+    String path = conf.get(OUTPUT_PATH);
+    if (path == null) {
+      throw new IllegalArgumentException("Cannot find output path");
+    }
+
+    return new TableRecordWriter(path, name, conf, progress);
+  }
+
+  /**
+   * Close the output BasicTable, No more rows can be added into the table. A
+   * BasicTable is not visible for reading until it is "closed". This call is
+   * required for sorted TFile, but not required for unsorted TFile.
+   * 
+   * @param conf
+   *          The JobConf object.
+   * @throws IOException
+   */
+  static void close(JobConf conf) throws IOException {
+    BasicTable.Writer table = getOutput(conf);
+    table.close();
+  }
+}
+
+/**
+ * Adaptor class for BasicTable RecordWriter.
+ */
+class TableRecordWriter implements RecordWriter<BytesWritable, Tuple> {
+  private final TableInserter inserter;
+  private final Progressable progress;
+
+  public TableRecordWriter(String path, String name, JobConf conf,
+      Progressable progress) throws IOException {
+    BasicTable.Writer writer = new BasicTable.Writer(new Path(path), conf);
+    this.inserter = writer.getInserter(name, true);
+    this.progress = progress;
+  }
+
+  @Override
+  public void close(Reporter reporter) throws IOException {
+    inserter.close();
+    reporter.progress();
+  }
+
+  @Override
+  public void write(BytesWritable key, Tuple value) throws IOException {
+    inserter.insert(key, value);
+    progress.progress();
+  }
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CachedTableScanner.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CachedTableScanner.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CachedTableScanner.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CachedTableScanner.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,160 @@
+/**
+ * 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.hadoop.zebra.mapred;
+
+import java.io.Closeable;
+import java.io.IOException;
+
+import org.apache.hadoop.io.BytesWritable;
+import org.apache.hadoop.zebra.io.TableScanner;
+import org.apache.hadoop.zebra.types.Projection;
+import org.apache.hadoop.zebra.types.Schema;
+import org.apache.hadoop.zebra.types.TypesUtils;
+import org.apache.pig.data.Tuple;
+
+/**
+ * Utility class for those interested in writing their own TableExpr classes.
+ * This class encapsulates a regular table scanner and changes the way how keys
+ * and rows are accessed (with an internal cache).
+ */
+final class CachedTableScanner implements Closeable {
+  private BytesWritable key;
+  private Tuple row;
+  private boolean keyReady;
+  private boolean rowReady;
+  private TableScanner scanner;
+
+  /**
+   * Constructor
+   * 
+   * @param scanner
+   *          The scanner to be encapsulated
+   * @throws IOException 
+   */
+  public CachedTableScanner(TableScanner scanner) throws IOException {
+    key = new BytesWritable();
+    row = TypesUtils.createTuple(Projection.getNumColumns(scanner.getProjection()));
+    keyReady = false;
+    rowReady = false;
+    this.scanner = scanner;
+  }
+
+  /**
+   * Get the key at cursor.
+   * 
+   * @return The key at cursor
+   * @throws IOException
+   */
+  public BytesWritable getKey() throws IOException {
+    if (!keyReady) {
+      scanner.getKey(key);
+      keyReady = true;
+    }
+    return key;
+  }
+
+  /**
+   * Get the value (Tuple) at cursor.
+   * 
+   * @return the value at cursor.
+   * @throws IOException
+   */
+  public Tuple getValue() throws IOException {
+    if (!rowReady) {
+      scanner.getValue(row);
+      rowReady = true;
+    }
+    return row;
+  }
+
+  /**
+   * Seek to a row whose key is greater than or equal to the input key.
+   * 
+   * @param inKey
+   *          the input key.
+   * @return true if an exact matching key is found. false otherwise.
+   * @throws IOException
+   */
+  public boolean seekTo(BytesWritable inKey) throws IOException {
+    boolean ret = scanner.seekTo(inKey);
+    reset();
+    return ret;
+  }
+
+  /**
+   * Advance the cursor.
+   * 
+   * @return whether the cursor actually moves.
+   * @throws IOException
+   */
+  public boolean advance() throws IOException {
+    boolean ret = scanner.advance();
+    reset();
+    return ret;
+  }
+
+  private void reset() throws IOException {
+    row = TypesUtils.createTuple(Projection.getNumColumns(scanner.getProjection()));
+    keyReady = false;
+    rowReady = false;
+  }
+
+  /**
+   * Is cursor at end?
+   * 
+   * @return Whether cursor is at the end.
+   * @throws IOException
+   */
+  public boolean atEnd() throws IOException {
+    return scanner.atEnd();
+  }
+
+  /**
+   * Get the schema of the tuples returned from this scanner.
+   * 
+   * @return The schema of the tuples returned from this scanner.
+   */
+  public String getProjection() {
+    return scanner.getProjection();
+  }
+  
+  /**
+   * Get the projected schema
+   * @return The projected schema
+   */
+  public Schema getSchema() {
+    return scanner.getSchema();
+  }
+
+  /**
+   * Seek to the end of the scanner.
+   * 
+   * @throws IOException
+   */
+  public void seekToEnd() throws IOException {
+    reset();
+    scanner.seekToEnd();
+  }
+
+  /**
+   * Close the scanner, release all resources.
+   */
+  @Override
+  public void close() throws IOException {
+    scanner.close();
+  }
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CompositeTableExpr.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CompositeTableExpr.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CompositeTableExpr.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/CompositeTableExpr.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,305 @@
+/**
+ * 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.hadoop.zebra.mapred;
+
+import java.io.IOException;
+import java.io.PrintStream;
+import java.io.StringReader;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+
+
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.zebra.io.BasicTable;
+import org.apache.hadoop.zebra.types.ParseException;
+import org.apache.hadoop.zebra.types.Schema;
+
+
+/**
+ * An intermediate class to build concrete composite table expression classes.
+ * Lengthy names are chosen to avoid naming conflicts.
+ */
+abstract class CompositeTableExpr extends TableExpr {
+  public final static int INDENT_UNIT = 2;
+  protected ArrayList<TableExpr> composite;
+
+  protected CompositeTableExpr() {
+    composite = new ArrayList<TableExpr>();
+  }
+
+  protected CompositeTableExpr(int n) {
+    composite = new ArrayList<TableExpr>(n);
+    for (int i = 0; i < n; ++i) {
+      composite.add(null);
+    }
+  }
+
+  protected CompositeTableExpr addCompositeTable(TableExpr expr) {
+    composite.add(expr);
+    return this;
+  }
+
+  protected CompositeTableExpr addCompositeTables(TableExpr[] exprs) {
+    composite.ensureCapacity(composite.size() + exprs.length);
+    for (TableExpr expr : exprs) {
+      composite.add(expr);
+    }
+    return this;
+  }
+
+  protected CompositeTableExpr addCompositeTables(
+      Collection<? extends TableExpr> exprs) {
+    composite.addAll(exprs);
+    return this;
+  }
+
+  protected CompositeTableExpr setCompositeTable(int i, TableExpr expr) {
+    composite.set(i, expr);
+    return this;
+  }
+
+  protected List<TableExpr> getCompositeTables() {
+    return composite;
+  }
+
+  protected TableExpr getCompositeTable(int i) {
+    TableExpr expr = composite.get(i);
+    if (expr == null) {
+      throw new RuntimeException("Incomplete Nary expression");
+    }
+
+    return expr;
+  }
+
+  @Override
+  protected CompositeTableExpr decodeParam(StringReader in) throws IOException {
+    composite.clear();
+    int n = TableExprUtils.decodeInt(in);
+    composite.ensureCapacity(n);
+    for (int i = 0; i < n; ++i) {
+      TableExpr expr = TableExpr.parse(in);
+      composite.add(expr);
+    }
+
+    return this;
+  }
+
+  @Override
+  protected CompositeTableExpr encodeParam(StringBuilder out) {
+    int n = composite.size();
+    TableExprUtils.encodeInt(out, n);
+    for (int i = 0; i < composite.size(); ++i) {
+      getCompositeTable(i).encode(out);
+    }
+
+    return this;
+  }
+
+  @Override
+  public List<LeafTableInfo> getLeafTables(String projection) {
+    ArrayList<LeafTableInfo> ret = new ArrayList<LeafTableInfo>();
+
+    int n = composite.size();
+    for (int i = 0; i < n; ++i) {
+      ret.addAll(getCompositeTable(i).getLeafTables(projection));
+    }
+
+    return ret;
+  }
+
+  protected static class RowMappingEntry {
+    final int rowIndex;
+    final int fieldIndex;
+
+    public RowMappingEntry(int ri, int fi) {
+      rowIndex = ri;
+      fieldIndex = fi;
+    }
+
+    public int getRowIndex() {
+      return rowIndex;
+    }
+
+    public int getFieldIndex() {
+      return fieldIndex;
+    }
+  }
+
+  protected static class InferredProjection {
+    /**
+     * projections on each table in the composite. It should be of the same
+     * dimension as composite.
+     */
+    final Schema[] subProjections;
+
+    /**
+     * The actual (adjusted) input projection.
+     */
+    final Schema projection;
+
+    /**
+     * For each column in the input projection, what is the corresponding sub
+     * table (row index) and the corresponding projected column (field index).
+     */
+    final RowMappingEntry[] colMapping;
+
+    InferredProjection(List<String>[] subProj, String[] proj,
+        Map<String, RowMappingEntry> colMap) throws ParseException {
+      subProjections = new Schema[subProj.length];
+      for (int i = 0; i < subProj.length; ++i) {
+        List<String> subProjection = subProj[i];
+        subProjections[i] =
+            new Schema(subProjection.toArray(new String[subProjection.size()]));
+      }
+      
+      projection = new Schema(proj);
+      
+      this.colMapping = new RowMappingEntry[proj.length];
+      
+      for (int i = 0; i < proj.length; ++i) {
+        colMapping[i] = colMap.get(proj[i]);
+      }
+    }
+
+    public Schema[] getSubProjections() {
+      return subProjections;
+    }
+
+    public RowMappingEntry[] getColMapping() {
+      return colMapping;
+    }
+
+    public Schema getProjection() {
+      return projection;
+    }
+  }
+
+  /**
+   * Given the input projection, infer the projections that should be applied on
+   * individual table in the composite.
+   * 
+   * @param projection
+   *          The expected projection
+   * @return The inferred projection with other information.
+   * @throws IOException
+   */
+  @SuppressWarnings("unchecked")
+  protected InferredProjection inferProjection(String projection,
+      Configuration conf)
+      throws IOException, ParseException {
+    int n = composite.size();
+    ArrayList<String>[] subProjections = new ArrayList[n];
+    for (int i = 0; i < n; ++i) {
+      subProjections[i] = new ArrayList<String>();
+    }
+    
+    String[] columns;
+    LinkedHashMap<String, Integer> colNameMap =
+        new LinkedHashMap<String, Integer>();
+    TreeMap<String, RowMappingEntry> colMapping =
+        new TreeMap<String, RowMappingEntry>();
+
+    /**
+     * Create a collection of all column names and the corresponding index to
+     * the composite.
+     */
+    for (int i = 0; i < n; ++i) {
+      String[] cols = getCompositeTable(i).getSchema(conf).getColumns();
+      for (int j = 0; j < cols.length; ++j) {
+        if (colNameMap.get(cols[j]) != null) {
+          colNameMap.put(cols[j], -1); // special marking on duplicated names.
+        }
+        else {
+          colNameMap.put(cols[j], i);
+        }
+      }
+    }
+
+    if (projection == null) {
+      Set<String> keySet = colNameMap.keySet();
+      columns = keySet.toArray(new String[keySet.size()]);
+    }
+    else {
+      columns = projection.trim().split(Schema.COLUMN_DELIMITER);
+    }
+
+    for (int i = 0; i < columns.length; ++i) {
+      String col = columns[i];
+
+      if (colMapping.get(col) != null) {
+        throw new IllegalArgumentException(
+            "Duplicate column names in projection");
+      }
+
+      Integer rowIndex = colNameMap.get(col);
+      if (rowIndex == null) {
+        colMapping.put(col, null);
+      }
+      else {
+        if (rowIndex < 0) {
+          // The column name appears in more than one table in composite.
+          throw new RuntimeException("Ambiguous column in projection: "
+              + col);
+        }
+        subProjections[rowIndex].add(columns[i]);
+        colMapping.put(col, new RowMappingEntry(rowIndex,
+            subProjections[rowIndex].size() - 1));
+      }
+    }
+
+    return new InferredProjection(subProjections, columns, colMapping);
+  }
+
+  @Override
+  public Schema getSchema(Configuration conf) throws IOException {
+    Schema result = new Schema();
+    for (Iterator<TableExpr> it = composite.iterator(); it.hasNext();) {
+      TableExpr e = it.next();
+      try {
+        result.unionSchema(e.getSchema(conf));
+      } catch (ParseException exc) {
+        throw new IOException("Schema parsing failed :"+exc.getMessage());
+      }
+    }
+    return result;
+  }
+  
+  @Override
+  public boolean sortedSplitCapable() {
+    for (Iterator<TableExpr> it = composite.iterator(); it.hasNext();) {
+      TableExpr e = it.next();
+      if (!e.sortedSplitCapable()) return false;
+    }
+
+    return true;
+  }
+  
+  @Override
+  protected void dumpInfo(PrintStream ps, Configuration conf, int indent) throws IOException
+  {
+    for (Iterator<TableExpr> it = composite.iterator(); it.hasNext();) {
+      TableExpr e = it.next();
+      e.dumpInfo(ps, conf, indent+INDENT_UNIT);
+    }
+  }
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/NullScanner.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/NullScanner.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/NullScanner.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/NullScanner.java Tue Aug 11 22:27:44 2009
@@ -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.hadoop.zebra.mapred;
+
+import java.io.EOFException;
+import java.io.IOException;
+
+import org.apache.hadoop.io.BytesWritable;
+import org.apache.hadoop.zebra.io.TableScanner;
+import org.apache.hadoop.zebra.types.ParseException;
+import org.apache.hadoop.zebra.types.Projection;
+import org.apache.hadoop.zebra.types.Schema;
+import org.apache.pig.data.Tuple;
+
+/**
+ * A scanner that contains no rows.
+ */
+class NullScanner implements TableScanner {
+  String projection;
+
+  public NullScanner(String projection) {
+    this.projection = projection;
+  }
+  
+  @Override
+  public boolean advance() throws IOException {
+    return false;
+  }
+
+  @Override
+  public boolean atEnd() throws IOException {
+    return true;
+  }
+
+  @Override
+  public String getProjection() {
+    return projection;
+  }
+  
+  @Override
+  public Schema getSchema() {
+    Schema result;
+    try {
+       result = Projection.toSchema(projection);
+    } catch (ParseException e) {
+      throw new AssertionError("Invalid Projection: "+e.getMessage());
+    }
+    return result;
+  }
+
+  @Override
+  public void getKey(BytesWritable key) throws IOException {
+    throw new EOFException("No more rows to read");
+  }
+
+  @Override
+  public void getValue(Tuple row) throws IOException {
+    throw new EOFException("No more rows to read");
+  }
+
+  @Override
+  public boolean seekTo(BytesWritable key) throws IOException {
+    return false;
+  }
+
+  @Override
+  public void seekToEnd() throws IOException {
+    // Do nothing
+  }
+
+  @Override
+  public void close() throws IOException {
+    // Do nothing
+  }
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExpr.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExpr.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExpr.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExpr.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,215 @@
+/**
+ * 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.hadoop.zebra.mapred;
+
+import java.io.IOException;
+import java.io.StringReader;
+import java.io.PrintStream;
+import java.util.List;
+
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.BytesWritable;
+import org.apache.hadoop.zebra.io.BasicTable;
+import org.apache.hadoop.zebra.io.TableScanner;
+import org.apache.hadoop.zebra.types.ParseException;
+import org.apache.hadoop.zebra.types.Projection;
+import org.apache.hadoop.zebra.types.Schema;
+
+/**
+ * Table Expression - expression to describe an input table.
+ */
+abstract class TableExpr {
+  /**
+   * Factory method to create a TableExpr from a string.
+   * 
+   * @param in
+   *          The string stream that is pointed at the beginning of the table
+   *          expression string to be parsed.
+   * @return The instantiated TableExpr object. The string stream will move past
+   *         the table expression string.
+   * @throws IOException
+   */
+  @SuppressWarnings("unchecked")
+  public static TableExpr parse(StringReader in) throws IOException {
+    String clsName = TableExprUtils.decodeString(in);
+    try {
+      Class<? extends TableExpr> tblExprCls =
+          (Class<? extends TableExpr>) Class.forName(clsName);
+      return tblExprCls.newInstance().decodeParam(in);
+    }
+    catch (Exception e) {
+      throw new RuntimeException("Failed to load class: " + e.toString());
+    }
+  }
+
+  /**
+   * Encode the expression to a string stream.
+   * 
+   * @param out
+   *          The string stream that we should encode the expression into.
+   */
+  public final void encode(StringBuilder out) {
+    TableExprUtils.encodeString(out, getClass().getName());
+    encodeParam(out);
+  }
+
+  /**
+   * Decode the parameters of the expression from the input stream.
+   * 
+   * @param in
+   *          The string stream that is pointed at the beginning of the encoded
+   *          parameters.
+   * @return Reference to itself, and the TableExpr that has its parameters set
+   *         from the string stream. The string stream will move past the
+   *         encoded parameters for this expression.
+   */
+  protected abstract TableExpr decodeParam(StringReader in) throws IOException;
+
+  /**
+   * Encode the parameters of the expression into the string stream.
+   * 
+   * @param out
+   *          The string stream that we write encoded parameters into.
+   * @return Reference to itself,
+   */
+  protected abstract TableExpr encodeParam(StringBuilder out);
+
+  /**
+   * Get a TableScanner from the TableExpr object. This method only needs to be
+   * implemented by table expressions that support sorted split.
+   * 
+   * @param begin
+   *          the Begin key (inclusive). Can be null, meaning starting from the
+   *          first row of the table.
+   * @param end
+   *          the End key (exclusive). Can be null, meaning scan to the last row
+   *          of the table.
+   * @param projection
+   *          The projection schema. It should never be null.
+   * @see Schema
+   * @return A TableScanner object.
+   */
+  @SuppressWarnings("unused")
+  public TableScanner getScanner(BytesWritable begin,
+      BytesWritable end, String projection, Configuration conf)
+      throws IOException {
+    return null;
+  }
+
+  /**
+   * Get a scanner with an unsorted split.
+   * 
+   * @param split
+   *          The range split.
+   * @param projection
+   *          The projection schema. It should never be null.
+   * @param conf
+   *          The configuration
+   * @return A table scanner.
+   * @throws IOException
+   */
+  public TableScanner getScanner(UnsortedTableSplit split, String projection,
+      Configuration conf) throws IOException, ParseException {
+    BasicTable.Reader reader =
+        new BasicTable.Reader(new Path(split.getPath()), conf);
+    reader.setProjection(projection);
+    return reader.getScanner(split.getSplit(), true);
+  }
+  
+  /**
+   * A leaf table corresponds to a materialized table. It is represented by the
+   * path to the BasicTable and the projection.
+   */
+  public static final class LeafTableInfo {
+    private final Path path;
+    private final String projection;
+
+    public LeafTableInfo(Path path, String projection) {
+      this.path = path;
+      this.projection = projection;
+    }
+
+    public Path getPath() {
+      return path;
+    }
+
+    public String getProjection() {
+      return projection;
+    }
+  }
+
+  /**
+   * Get the information of all leaf tables that will be accessed by this table
+   * expression.
+   * 
+   * @param projection
+   *          The projection that is applied to the table expression.
+   */
+  public abstract List<LeafTableInfo> getLeafTables(
+      String projection);
+
+  /**
+   * Get the schema of the table.
+   * 
+   * @param conf
+   *          The configuration object.
+   */
+  public abstract Schema getSchema(Configuration conf) throws IOException;
+
+  /**
+   * Does this expression requires sorted split? If yes, we require all
+   * underlying BasicTables to be sorted and we split by key sampling. If this
+   * method returns true, we expect sortedSplitCapable() also return true.
+   * 
+   * @return Whether this expression may only be split by key.
+   */
+  public boolean sortedSplitRequired() {
+    return false;
+  }
+
+  /**
+   * Is this expression capable of sorted split? If false, getScanner() should
+   * return null; otherwise, getScanner() should return a valid Scanner object.
+   * 
+   * This function should be overridden by sub classes that is capable of sorted
+   * split. Note that this method should not perform any actual I/O operation,
+   * such as checking whether the leaf tables (BasicTables) is in fact sorted or
+   * not. When this method returns true, while at least one of the leaf tables
+   * is not sorted, an {@link IOException} will be thrown in split generation
+   * time.
+   * 
+   * @return Whether the "table view" represented by the expression is sorted
+   *         and is thus splittable by key (sorted split).
+   */
+  public boolean sortedSplitCapable() {
+    return false;
+  }
+
+  /**
+   * dump table info
+   */
+  public final void dumpInfo(PrintStream ps, Configuration conf) throws IOException
+  {
+    dumpInfo(ps, conf, 0);
+  }
+  
+  /**
+   * dump table info with indent
+   */
+  protected abstract void dumpInfo(PrintStream ps, Configuration conf, int indent) throws IOException;
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExprUtils.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExprUtils.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExprUtils.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableExprUtils.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,116 @@
+/**
+ * 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.hadoop.zebra.mapred;
+
+import java.io.IOException;
+import java.io.StringReader;
+
+/**
+ * Utility methods for people interested in writing their own TableExpr classes.
+ */
+class TableExprUtils {
+  private TableExprUtils() {
+    // prevent instantiation
+  }
+
+  /**
+   * Encode a string into a StringBuilder.
+   * 
+   * @param out
+   *          output string builder.
+   * @param s
+   *          String to be encoded
+   */
+  public static void encodeString(StringBuilder out, String s) {
+    if (s == null) {
+      encodeInt(out, null);
+      return;
+    }
+    
+    encodeInt(out, s.length());
+    out.append(s);
+  }
+  
+  /**
+   * Decode a string previously encoded through encodeString.
+   * 
+   * @param in
+   *          The input StringReader.
+   * @return The decoded string object.
+   * @throws IOException
+   */
+  public static String decodeString(StringReader in) throws IOException {
+    Integer len = decodeInt(in);
+    if (len == null) {
+      return null;
+    }
+
+    char[] chars = new char[len];
+    in.read(chars);
+    return new String(chars);
+  }
+  
+  public static void encodeLong(StringBuilder out, Long l) {
+    if (l != null) {
+      out.append(l);
+    }
+    out.append(':');
+  }
+
+  public static Long decodeLong(StringReader in) throws IOException {
+    int c = in.read();
+    if (c == ':') {
+      return null;
+    }
+    if (Character.isDigit(c) == false) {
+      throw new IllegalArgumentException("Bad encoded string");
+    }
+    StringBuilder sb = new StringBuilder();
+    sb.append((char) c);
+
+    boolean colonSeen = false;
+    while ((c = in.read()) != -1) {
+      if (c == ':') {
+        colonSeen = true;
+        break;
+      }
+      if (!Character.isDigit(c)) {
+        break;
+      }
+      sb.append((char) c);
+    }
+    if (colonSeen == false) {
+      throw new IllegalArgumentException("Bad encoded string");
+    }
+    return new Long(sb.toString());
+  }
+  
+  public static void encodeInt(StringBuilder out, Integer i) {
+    if (i == null) {
+      encodeLong(out, null);
+    }
+    else {
+      encodeLong(out, (long) i.intValue());
+    }
+  }
+
+  public static Integer decodeInt(StringReader in) throws IOException {
+    Long l = decodeLong(in);
+    if (l == null) return null;
+    return (int) l.longValue();
+  }
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableInputFormat.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableInputFormat.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableInputFormat.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableInputFormat.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,722 @@
+/**
+ * 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.hadoop.zebra.mapred;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.io.StringReader;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.BytesWritable;
+import org.apache.hadoop.io.WritableUtils;
+import org.apache.hadoop.io.file.tfile.RawComparable;
+import org.apache.hadoop.mapred.InputFormat;
+import org.apache.hadoop.mapred.InputSplit;
+import org.apache.hadoop.mapred.JobConf;
+import org.apache.hadoop.mapred.RecordReader;
+import org.apache.hadoop.mapred.Reporter;
+import org.apache.hadoop.zebra.io.BasicTable;
+import org.apache.hadoop.zebra.io.BasicTableStatus;
+import org.apache.hadoop.zebra.io.BlockDistribution;
+import org.apache.hadoop.zebra.io.KeyDistribution;
+import org.apache.hadoop.zebra.io.TableScanner;
+import org.apache.hadoop.zebra.io.BasicTable.Reader;
+import org.apache.hadoop.zebra.io.BasicTable.Reader.RangeSplit;
+import org.apache.hadoop.zebra.mapred.TableExpr.LeafTableInfo;
+import org.apache.hadoop.zebra.types.ParseException;
+import org.apache.hadoop.zebra.types.Projection;
+import org.apache.hadoop.zebra.types.Schema;
+import org.apache.hadoop.zebra.types.TypesUtils;
+import org.apache.pig.data.DataBag;
+import org.apache.pig.data.DataByteArray;
+import org.apache.pig.data.Tuple;
+
+/**
+ * {@link org.apache.hadoop.mapred.InputFormat} class for reading one or more
+ * BasicTables.
+ * 
+ * Usage Example:
+ * <p>
+ * In the main program, add the following code.
+ * 
+ * <pre>
+ * jobConf.setInputFormat(TableInputFormat.class);
+ * TableInputFormat.setInputPaths(jobConf, new Path(&quot;path/to/table1&quot;, new Path(&quot;path/to/table2&quot;);
+ * TableInputFormat.setProjection(jobConf, &quot;Name, Salary, BonusPct&quot;);
+ * </pre>
+ * 
+ * The above code does the following things:
+ * <UL>
+ * <LI>Set the input format class to TableInputFormat.
+ * <LI>Set the paths to the BasicTables to be consumed by user's Mapper code.
+ * <LI>Set the projection on the input tables. In this case, the Mapper code is
+ * only interested in three fields: "Name", "Salary", "BonusPct". "Salary"
+ * (perhaps for the purpose of calculating the person's total payout). If no
+ * project is specified, then all columns from the input tables will be
+ * retrieved. If input tables have different schemas, then the input contains
+ * the union of all columns from all the input tables. Absent fields will be
+ * left as nul in the input tuple.
+ * </UL>
+ * The user Mapper code should look like the following:
+ * 
+ * <pre>
+ * static class MyMapClass implements Mapper&lt;BytesWritable, Tuple, K, V&gt; {
+ *   // keep the tuple object for reuse.
+ *   // indices of various fields in the input Tuple.
+ *   int idxName, idxSalary, idxBonusPct;
+ * 
+ *   &#064;Override
+ *   public void configure(JobConf job) {
+ *     Schema projection = TableInputFormat.getProjection(job);
+ *     // determine the field indices.
+ *     idxName = projection.getColumnIndex(&quot;Name&quot;);
+ *     idxSalary = projection.getColumnIndex(&quot;Salary&quot;);
+ *     idxBonusPct = projection.getColumnIndex(&quot;BonusPct&quot;);
+ *   }
+ * 
+ *   &#064;Override
+ *   public void map(BytesWritable key, Tuple value, OutputCollector&lt;K, V&gt; output,
+ *       Reporter reporter) throws IOException {
+ *     try {
+ *       String name = (String) value.get(idxName);
+ *       int salary = (Integer) value.get(idxSalary);
+ *       double bonusPct = (Double) value.get(idxBonusPct);
+ *       // do something with the input data
+ *     } catch (ExecException e) {
+ *       e.printStackTrace();
+ *     }
+ *   }
+ * 
+ *   &#064;Override
+ *   public void close() throws IOException {
+ *     // no-op
+ *   }
+ * }
+ * </pre>
+ * 
+ * A little bit more explanation on the PIG {@link Tuple} objects. A Tuple is an
+ * ordered list of PIG datum objects. The permitted PIG datum types can be
+ * categorized as Scalar types and Composite types.
+ * <p>
+ * Supported Scalar types include seven native Java types: Boolean, Byte,
+ * Integer, Long, Float, Double, String, as well as one PIG class called
+ * {@link DataByteArray} that represents type-less byte array.
+ * <p>
+ * Supported Composite types include:
+ * <UL>
+ * <LI>{@link Map} : It is the same as Java Map class, with the additional
+ * restriction that the key-type must be one of the scalar types PIG recognizes,
+ * and the value-type any of the scaler or composite types PIG understands.
+ * <LI>{@link DataBag} : A DataBag is a collection of Tuples.
+ * <LI>{@link Tuple} : Yes, Tuple itself can be a datum in another Tuple.
+ * </UL>
+ */
+public class TableInputFormat implements InputFormat<BytesWritable, Tuple> {
+  private static final String INPUT_EXPR = "mapred.lib.table.input.expr";
+  private static final String INPUT_PROJ = "mapred.lib.table.input.projection";
+
+  /**
+   * Set the paths to the input table.
+   * 
+   * @param conf
+   *          JobConf object.
+   * @param paths
+   *          one or more paths to BasicTables. The InputFormat class will
+   *          produce splits on the "union" of these BasicTables.
+   */
+  public static void setInputPaths(JobConf conf, Path... paths) {
+    if (paths.length < 1) {
+      throw new IllegalArgumentException("Requring at least one input path");
+    }
+    if (paths.length == 1) {
+      setInputExpr(conf, new BasicTableExpr(paths[0]));
+    }
+    else {
+      TableUnionExpr expr = new TableUnionExpr();
+      for (Path path : paths) {
+        expr.add(new BasicTableExpr(path));
+      }
+      setInputExpr(conf, expr);
+    }
+  }
+
+  /**
+   * Set the input expression in the JobConf object.
+   * 
+   * @param conf
+   *          JobConf object.
+   * @param expr
+   *          The input table expression.
+   */
+  static void setInputExpr(JobConf conf, TableExpr expr) {
+    StringBuilder out = new StringBuilder();
+    expr.encode(out);
+    conf.set(INPUT_EXPR, out.toString());
+  }
+
+  static TableExpr getInputExpr(JobConf conf) throws IOException {
+    String expr = conf.get(INPUT_EXPR);
+    if (expr == null) {
+      throw new IllegalArgumentException("Input expression not defined.");
+    }
+    StringReader in = new StringReader(expr);
+    return TableExpr.parse(in);
+  }
+
+  /**
+   * Set the input projection in the JobConf object.
+   * 
+   * @param conf
+   *          JobConf object.
+   * @param projection
+   *          A common separated list of column names. If we want select all
+   *          columns, pass projection==null. The syntax of the projection
+   *          conforms to the {@link Schema} string.
+   * @see Schema#Schema(String)
+   */
+  public static void setProjection(JobConf conf, String projection) throws ParseException{
+    conf.set(INPUT_PROJ, Schema.normalize(projection));
+  }
+
+  /**
+   * Get the projection from the JobConf
+   * 
+   * @param conf
+   *          The JobConf object
+   * @return The projection schema. If projection has not been defined, or is
+   *         not known at this time, null will be returned. Note that by the time
+   *         when this method is called in Mapper code, the projection must
+   *         already be known.
+   * @throws IOException
+   */
+  public static String getProjection(JobConf conf) throws IOException, ParseException {
+    String strProj = conf.get(INPUT_PROJ);
+    // TODO: need to be revisited
+    if (strProj != null) return strProj;
+    TableExpr expr = getInputExpr(conf);
+    if (expr != null) {
+      return expr.getSchema(conf).toProjectionString();
+    }
+    return null;
+  }
+  
+  /**
+   * @see InputFormat#getRecordReader(InputSplit, JobConf, Reporter)
+   */
+  @Override
+  public RecordReader<BytesWritable, Tuple> getRecordReader(InputSplit split,
+      JobConf conf, Reporter reporter) throws IOException {
+    TableExpr expr = getInputExpr(conf);
+    if (expr == null) {
+      throw new IOException("Table expression not defined");
+    }
+    String strProj = conf.get(INPUT_PROJ);
+    String projection = null;
+    try {
+      if (strProj == null) {
+        projection = expr.getSchema(conf).toProjectionString();
+        TableInputFormat.setProjection(conf, projection);
+      } else {
+        projection = strProj;
+      }
+    } catch (ParseException e) {
+    	throw new IOException("Projection parsing failed : "+e.getMessage());
+    }
+    try {
+      return new TableRecordReader(expr, projection, split, conf);
+    } catch (ParseException e) {
+    	throw new IOException("Projection parsing faile : "+e.getMessage());
+    }
+  }
+
+  private static InputSplit[] getSortedSplits(JobConf conf, int numSplits,
+      TableExpr expr, List<BasicTable.Reader> readers,
+      List<BasicTableStatus> status) throws IOException {
+    if (expr.sortedSplitRequired() && !expr.sortedSplitCapable()) {
+      throw new IOException("Unable to created sorted splits");
+    }
+
+    long totalBytes = 0;
+    for (Iterator<BasicTableStatus> it = status.iterator(); it.hasNext();) {
+      BasicTableStatus s = it.next();
+      totalBytes += s.getSize();
+    }
+
+    long maxSplits = totalBytes / getMinSplitSize(conf);
+
+    if (numSplits > maxSplits) {
+      numSplits = -1;
+    }
+
+    ArrayList<InputSplit> splits = new ArrayList<InputSplit>();
+
+    for (Iterator<BasicTable.Reader> it = readers.iterator(); it.hasNext();) {
+      BasicTable.Reader reader = it.next();
+      if (!reader.isSorted()) {
+        throw new IOException("Attempting sorted split on unsorted table");
+      }
+    }
+
+    if (numSplits == 1) {
+      BlockDistribution bd = null;
+      for (Iterator<BasicTable.Reader> it = readers.iterator(); it.hasNext();) {
+        BasicTable.Reader reader = it.next();
+        bd = BlockDistribution.sum(bd, reader.getBlockDistribution(null));
+      }
+      
+      if (bd == null) {
+        // should never happen.
+        return new InputSplit[0];
+      }
+      
+      SortedTableSplit split = new SortedTableSplit(null, null, bd, conf);
+      return new InputSplit[] { split };
+    }
+    
+    // TODO: Does it make sense to interleave keys for all leaf tables if
+    // numSplits <= 0 ?
+    int nLeaves = readers.size();
+    KeyDistribution keyDistri = null;
+    for (int i = 0; i < nLeaves; ++i) {
+      KeyDistribution btKeyDistri =
+          readers.get(i).getKeyDistribution(
+              (numSplits <= 0) ? -1 :
+              Math.max(numSplits * 5 / nLeaves, numSplits));
+      keyDistri = KeyDistribution.sum(keyDistri, btKeyDistri);
+    }
+    
+    if (keyDistri == null) {
+      // should never happen.
+      return new InputSplit[0];
+    }
+    
+    if (numSplits > 0) {
+      keyDistri.resize(numSplits);
+    }
+    
+    RawComparable[] rawKeys = keyDistri.getKeys();
+    BytesWritable[] keys = new BytesWritable[rawKeys.length];
+    for (int i=0; i<keys.length; ++i) {
+      RawComparable rawKey = rawKeys[i];
+      keys[i] = new BytesWritable();
+      keys[i].setSize(rawKey.size());
+      System.arraycopy(rawKey.buffer(), rawKey.offset(), keys[i].get(), 0,
+          rawKey.size());
+    }
+    
+    // TODO: Should we change to RawComparable to avoid the creation of
+    // BytesWritables?
+    for (int i = 0; i < keys.length; ++i) {
+      BytesWritable begin = (i == 0) ? null : keys[i - 1];
+      BytesWritable end = (i == keys.length - 1) ? null : keys[i];
+      BlockDistribution bd = keyDistri.getBlockDistribution(keys[i]);
+      SortedTableSplit split = new SortedTableSplit(begin, end, bd, conf);
+      splits.add(split);
+    }
+    return splits.toArray(new InputSplit[splits.size()]);
+  }
+  
+  static long getMinSplitSize(JobConf conf) {
+    return conf.getLong("table.input.split.minSize", 1 * 1024 * 1024L);
+  }
+
+  /**
+   * Set the minimum split size.
+   * 
+   * @param conf
+   *          The job conf object.
+   * @param minSize
+   *          Minimum size.
+   */
+  public static void setMinSplitSize(JobConf conf, long minSize) {
+    conf.setLong("table.input.split.minSize", minSize);
+  }
+  
+  private static InputSplit[] getUnsortedSplits(JobConf conf, int numSplits,
+      TableExpr expr, List<BasicTable.Reader> readers,
+      List<BasicTableStatus> status) throws IOException {
+    long totalBytes = 0;
+    for (Iterator<BasicTableStatus> it = status.iterator(); it.hasNext();) {
+      BasicTableStatus s = it.next();
+      totalBytes += s.getSize();
+    }
+
+    long maxSplits = totalBytes / getMinSplitSize(conf);
+
+    if (numSplits > maxSplits) {
+      numSplits = -1;
+    }
+
+    ArrayList<InputSplit> ret = new ArrayList<InputSplit>();;
+    if (numSplits <= 0) {
+      for (int i = 0; i < readers.size(); ++i) {
+        BasicTable.Reader reader = readers.get(i);
+        List<RangeSplit> subSplits = reader.rangeSplit(-1);
+        for (Iterator<RangeSplit> it = subSplits.iterator(); it.hasNext();) {
+          UnsortedTableSplit split =
+              new UnsortedTableSplit(reader, it.next(), conf);
+          ret.add(split);
+        }
+      }
+    } else {
+      long goalSize = totalBytes / numSplits;
+
+      double SPLIT_SLOP = 1.1;
+      for (int i = 0; i < readers.size(); ++i) {
+        BasicTable.Reader reader = readers.get(i);
+        BasicTableStatus s = status.get(i);
+        int nSplits =
+            (int) ((s.getSize() + goalSize * (2 - SPLIT_SLOP)) / goalSize);
+        if (nSplits > 1) {
+          List<RangeSplit> subSplits = reader.rangeSplit(nSplits);
+          for (Iterator<RangeSplit> it = subSplits.iterator(); it.hasNext();) {
+            UnsortedTableSplit split =
+                new UnsortedTableSplit(reader, it.next(), conf);
+            ret.add(split);
+          }
+        } else {
+          UnsortedTableSplit split = new UnsortedTableSplit(reader, null, conf);
+          ret.add(split);
+        }
+      }
+    }
+
+    return ret.toArray(new InputSplit[ret.size()]);
+  }
+
+  /**
+   * @see InputFormat#getSplits(JobConf, int)
+   */
+  @Override
+  public InputSplit[] getSplits(JobConf conf, int numSplits)
+      throws IOException {
+    TableExpr expr = getInputExpr(conf);
+    if (expr.sortedSplitRequired() && !expr.sortedSplitCapable()) {
+      throw new IOException("Unable to created sorted splits");
+    }
+    
+    String projection;
+    try {
+      projection = getProjection(conf);
+    } catch (ParseException e) {
+    	throw new IOException("getProjection failed : "+e.getMessage());
+    }
+    List<LeafTableInfo> leaves = expr.getLeafTables(projection);
+    int nLeaves = leaves.size();
+    ArrayList<BasicTable.Reader> readers =
+        new ArrayList<BasicTable.Reader>(nLeaves);
+    ArrayList<BasicTableStatus> status =
+        new ArrayList<BasicTableStatus>(nLeaves);
+
+    try {
+      for (Iterator<LeafTableInfo> it = leaves.iterator(); it.hasNext();) {
+        LeafTableInfo leaf = it.next();
+        BasicTable.Reader reader =
+          new BasicTable.Reader(leaf.getPath(), conf);
+        reader.setProjection(leaf.getProjection());
+        BasicTableStatus s = reader.getStatus();
+        if ((s.getRows() != 0) && (s.getSize() > 0)) {
+          // skipping empty tables.
+          // getRows() may return -1 to indicate unknown row numbers.
+          readers.add(reader);
+          status.add(s);
+        } else {
+          reader.close();
+        }
+      }
+      
+      if (readers.isEmpty()) {
+        return new InputSplit[0];
+      }
+      
+      if (expr.sortedSplitRequired()) {
+        return getSortedSplits(conf, numSplits, expr, readers, status);
+      }
+      return getUnsortedSplits(conf, numSplits, expr, readers, status);
+    } catch (ParseException e) {
+    	throw new IOException("Projection parsing failed : "+e.getMessage());
+    }
+    finally {
+      for (Iterator<BasicTable.Reader> it = readers.iterator(); it.hasNext();) {
+        try {
+          it.next().close();
+        }
+        catch (Exception e) {
+          // trap errors.
+          // TODO: log the error here.
+        }
+      }
+    }
+  }
+
+  @Deprecated
+  public synchronized void validateInput(JobConf conf) throws IOException {
+    // Validating imports by opening all Tables.
+    TableExpr expr = getInputExpr(conf);
+    try {
+      String projection = getProjection(conf);
+      List<LeafTableInfo> leaves = expr.getLeafTables(projection);
+      Iterator<LeafTableInfo> iterator = leaves.iterator();
+      while (iterator.hasNext()) {
+        LeafTableInfo leaf = iterator.next();
+        BasicTable.Reader reader =
+            new BasicTable.Reader(leaf.getPath(), conf);
+        reader.setProjection(projection);
+        reader.close();
+      }
+    } catch (ParseException e) {
+    	throw new IOException("Projection parsing failed : "+e.getMessage());
+    }
+  }
+}
+
+/**
+ * Adaptor class for sorted InputSplit for table.
+ */
+class SortedTableSplit implements InputSplit {
+  BytesWritable begin = null, end = null;
+  
+  String[] hosts;
+  long length = 1;
+
+  public SortedTableSplit()
+  {
+    // no-op for Writable construction
+  }
+  
+  public SortedTableSplit(BytesWritable begin, BytesWritable end,
+      BlockDistribution bd, JobConf conf) {
+    if (begin != null) {
+      this.begin = new BytesWritable();
+      this.begin.set(begin.get(), 0, begin.getSize());
+    }
+    if (end != null) {
+      this.end = new BytesWritable();
+      this.end.set(end.get(), 0, end.getSize());
+    }
+    
+    if (bd != null) {
+      length = bd.getLength();
+      hosts =
+        bd.getHosts(conf.getInt("mapred.lib.table.input.nlocation", 5));
+    }
+  }
+  
+  @Override
+  public long getLength() throws IOException {
+    return length;
+  }
+
+  @Override
+  public String[] getLocations() throws IOException {
+    return hosts;
+  }
+
+  @Override
+  public void readFields(DataInput in) throws IOException {
+    begin = end = null;
+    int bool = WritableUtils.readVInt(in);
+    if (bool == 1) {
+      begin.readFields(in);
+    }
+    bool = WritableUtils.readVInt(in);
+    if (bool == 1) {
+      end.readFields(in);
+    }
+  }
+
+  @Override
+  public void write(DataOutput out) throws IOException {
+    if (begin == null) {
+      WritableUtils.writeVInt(out, 0);
+    }
+    else {
+      WritableUtils.writeVInt(out, 1);
+      begin.write(out);
+    }
+    if (end == null) {
+      WritableUtils.writeVInt(out, 0);
+    }
+    else {
+      WritableUtils.writeVInt(out, 1);
+      end.write(out);
+    }
+  }
+  
+  public BytesWritable getBegin() {
+    return begin;
+  }
+
+  public BytesWritable getEnd() {
+    return end;
+  }
+}
+
+/**
+ * Adaptor class for unsorted InputSplit for table.
+ */
+class UnsortedTableSplit implements InputSplit {
+  String path = null;
+  RangeSplit split = null;
+  String[] hosts = null;
+  long length = 1;
+
+  public UnsortedTableSplit(Reader reader, RangeSplit split, JobConf conf)
+      throws IOException {
+    this.path = reader.getPath();
+    this.split = split;
+    BlockDistribution dataDist = reader.getBlockDistribution(split);
+    if (dataDist != null) {
+      length = dataDist.getLength();
+      hosts =
+          dataDist.getHosts(conf.getInt("mapred.lib.table.input.nlocation", 5));
+    }
+  }
+  
+  public UnsortedTableSplit() {
+    // no-op for Writable construction
+  }
+  
+  @Override
+  public long getLength() throws IOException {
+    return length;
+  }
+
+  @Override
+  public String[] getLocations() throws IOException {
+    return hosts;
+  }
+
+  @Override
+  public void readFields(DataInput in) throws IOException {
+    path = WritableUtils.readString(in);
+    int bool = WritableUtils.readVInt(in);
+    if (bool == 1) {
+      if (split == null) split = new RangeSplit();
+      split.readFields(in);
+    }
+    else {
+      split = null;
+    }
+    hosts = WritableUtils.readStringArray(in);
+    length = WritableUtils.readVLong(in);
+
+  }
+
+  @Override
+  public void write(DataOutput out) throws IOException {
+    WritableUtils.writeString(out, path);
+    if (split == null) {
+      WritableUtils.writeVInt(out, 0);
+    }
+    else {
+      WritableUtils.writeVInt(out, 1);
+      split.write(out);
+    }
+    WritableUtils.writeStringArray(out, hosts);
+    WritableUtils.writeVLong(out, length);
+  }
+
+  public String getPath() {
+    return path;
+  }
+  
+  public RangeSplit getSplit() {
+    return split;
+  }
+}
+
+/**
+ * Adaptor class to implement RecordReader on top of Scanner.
+ */
+class TableRecordReader implements RecordReader<BytesWritable, Tuple> {
+  private final TableScanner scanner;
+  private long count = 0;
+
+  /**
+   * 
+   * @param expr
+   * @param projection
+   *          projection schema. Should never be null.
+   * @param split
+   * @param conf
+   * @throws IOException
+   */
+  public TableRecordReader(TableExpr expr, String projection,
+      InputSplit split,
+      JobConf conf) throws IOException, ParseException {
+    if (expr.sortedSplitRequired()) {
+      SortedTableSplit tblSplit = (SortedTableSplit) split;
+      scanner =
+          expr.getScanner(tblSplit.getBegin(), tblSplit.getEnd(), projection,
+              conf);
+    }
+    else {
+      UnsortedTableSplit tblSplit = (UnsortedTableSplit) split;
+      scanner = expr.getScanner(tblSplit, projection, conf);
+    }
+  }
+  
+  @Override
+  public void close() throws IOException {
+    scanner.close();
+  }
+
+  @Override
+  public BytesWritable createKey() {
+    return new BytesWritable();
+  }
+
+  @Override
+  public Tuple createValue() {
+    try {
+      return TypesUtils.createTuple(Projection.getNumColumns(scanner.getProjection()));
+    }
+    catch (IOException e) {
+      // TODO Auto-generated catch block
+      e.printStackTrace();
+    }
+    return null;
+  }
+
+  @Override
+  public long getPos() throws IOException {
+    return count;
+  }
+
+  @Override
+  public float getProgress() throws IOException {
+    return (float) ((scanner.atEnd()) ? 1.0 : 0);
+  }
+
+  @Override
+  public boolean next(BytesWritable key, Tuple value) throws IOException {
+    if (scanner.atEnd()) {
+      return false;
+    }
+    scanner.getKey(key);
+    scanner.getValue(value);
+    scanner.advance();
+    ++count;
+    return true;
+  }
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableUnionExpr.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableUnionExpr.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableUnionExpr.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/TableUnionExpr.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,281 @@
+/**
+ * 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.hadoop.zebra.mapred;
+
+import java.io.EOFException;
+import java.io.IOException;
+import java.io.StringReader;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.concurrent.PriorityBlockingQueue;
+
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.io.BytesWritable;
+import org.apache.hadoop.zebra.io.BasicTable;
+import org.apache.hadoop.zebra.io.BasicTableStatus;
+import org.apache.hadoop.zebra.io.TableScanner;
+import org.apache.hadoop.zebra.types.ParseException;
+import org.apache.hadoop.zebra.types.Projection;
+import org.apache.hadoop.zebra.types.Schema;
+import org.apache.pig.data.Tuple;
+
+/**
+ * Table expression supporting a union of BasicTables.
+ * 
+ * @see <a href="doc-files/examples/ReadTableUnion.java">Usage example for
+ *      UnionTableExpr</a>
+ */
+class TableUnionExpr extends CompositeTableExpr {
+  /**
+   * Add another BasicTable into the table-union.
+   * 
+   * @param expr
+   *          The expression for the BasicTable to be added.
+   * @return self.
+   */
+  public TableUnionExpr add(BasicTableExpr expr) {
+    super.addCompositeTable(expr);
+    return this;
+  }
+
+  /**
+   * Add an array of BasicTables into the table-union.
+   * 
+   * @param exprs
+   *          the expressions representing the BasicTables to be added.
+   * @return self.
+   */
+  public TableUnionExpr add(BasicTableExpr[] exprs) {
+    super.addCompositeTables(exprs);
+    return this;
+  }
+
+  /**
+   * Add a Collection of BasicTables into the table-union.
+   * 
+   * @param exprs
+   *          the expressions representing the BasicTables to be added.
+   * @return self.
+   */
+  public TableUnionExpr add(Collection<? extends BasicTableExpr> exprs) {
+    super.addCompositeTables(exprs);
+    return this;
+  }
+  
+  @Override
+  protected TableUnionExpr decodeParam(StringReader in) throws IOException {
+    super.decodeParam(in);
+    int n = composite.size();
+    for (int i = 0; i < n; ++i) {
+      if (!(composite.get(i) instanceof BasicTableExpr)) {
+        throw new RuntimeException("Not a BasicTableExpr");
+      }
+    }
+    return this;
+  }
+
+  @Override
+  protected TableUnionExpr encodeParam(StringBuilder out) {
+    super.encodeParam(out);
+    return this;
+  }
+
+  @Override
+  public TableScanner getScanner(BytesWritable begin, BytesWritable end,
+      String projection, Configuration conf) throws IOException {
+    int n = composite.size();
+    if (n==0) {
+      throw new IllegalArgumentException("Union of 0 table");
+    }
+    ArrayList<BasicTable.Reader> readers = new ArrayList<BasicTable.Reader>(n);
+    final ArrayList<BasicTableStatus> status =
+        new ArrayList<BasicTableStatus>(n);
+    for (int i = 0; i < n; ++i) {
+      BasicTableExpr expr = (BasicTableExpr) composite.get(i);
+      BasicTable.Reader reader =
+          new BasicTable.Reader(expr.getPath(), conf);
+      readers.add(reader);
+      status.add(reader.getStatus());
+    }
+
+    String actualProjection = projection;
+    if (actualProjection == null) {
+      // Perform a union on all column names.
+      LinkedHashSet<String> colNameSet = new LinkedHashSet<String>();
+      for (int i = 0; i < n; ++i) {
+        String[] cols = readers.get(i).getSchema().getColumns();
+        for (String col : cols) {
+          colNameSet.add(col);
+        }
+      }
+
+      actualProjection = 
+          Projection.getProjectionStr(colNameSet.toArray(new String[colNameSet.size()]));
+    }
+    
+    ArrayList<TableScanner> scanners = new ArrayList<TableScanner>(n);
+    try {
+      for (int i=0; i<n; ++i) {
+        BasicTable.Reader reader = readers.get(i);
+        reader.setProjection(actualProjection);
+        TableScanner scanner = readers.get(i).getScanner(begin, end, true);
+        if (!scanner.atEnd()) {
+          scanners.add(scanner);
+        }
+        else {
+          scanner.close();
+        }
+      }
+    } catch (ParseException e) {
+    	throw new IOException("Projection parsing failed : "+e.getMessage());
+    }
+    
+    if (scanners.isEmpty()) {
+      return new NullScanner(actualProjection);
+    }
+
+    return new SortedTableUnionScanner(scanners);
+  }
+}
+
+/**
+ * Union scanner.
+ */
+class SortedTableUnionScanner implements TableScanner {
+  CachedTableScanner[] scanners;
+  PriorityBlockingQueue<CachedTableScanner> queue;
+  boolean synced = false;
+
+  SortedTableUnionScanner(List<TableScanner> scanners) throws IOException {
+    if (scanners.isEmpty()) {
+      throw new IllegalArgumentException("Zero-sized table union");
+    }
+    this.scanners = new CachedTableScanner[scanners.size()];
+    queue =
+        new PriorityBlockingQueue<CachedTableScanner>(scanners.size(),
+            new Comparator<CachedTableScanner>() {
+
+              @Override
+              public int compare(CachedTableScanner o1, CachedTableScanner o2) {
+                try {
+                  return o1.getKey().compareTo(o2.getKey());
+                }
+                catch (IOException e) {
+                  throw new RuntimeException("IOException: " + e.toString());
+                }
+              }
+
+            });
+    
+    for (int i = 0; i < this.scanners.length; ++i) {
+      TableScanner scanner = scanners.get(i);
+      this.scanners[i] = new CachedTableScanner(scanner);
+    }
+  }
+  
+
+  private void sync() throws IOException {
+    if (synced == false) {
+      queue.clear();
+      for (int i = 0; i < scanners.length; ++i) {
+        if (!scanners[i].atEnd()) {
+          queue.add(scanners[i]);
+        }
+      }
+      synced = true;
+    }
+  }
+  
+  @Override
+  public boolean advance() throws IOException {
+    sync();
+    CachedTableScanner scanner = queue.poll();
+    if (scanner != null) {
+      scanner.advance();
+      if (!scanner.atEnd()) {
+        queue.add(scanner);
+      }
+      return true;
+    }
+    return false;
+  }
+
+  @Override
+  public boolean atEnd() throws IOException {
+    sync();
+    return queue.isEmpty();
+  }
+
+  @Override
+  public String getProjection() {
+    return scanners[0].getProjection();
+  }
+  
+  @Override
+  public Schema getSchema() {
+    return scanners[0].getSchema();
+  }
+
+  @Override
+  public void getKey(BytesWritable key) throws IOException {
+    if (atEnd()) {
+      throw new EOFException("No more rows to read");
+    }
+    
+    CachedTableScanner scanner = queue.poll();
+    key.set(scanner.getKey());
+  }
+
+  @Override
+  public void getValue(Tuple row) throws IOException {
+    if (atEnd()) {
+      throw new EOFException("No more rows to read");
+    }
+    
+    CachedTableScanner scanner = queue.poll();
+    row.reference(scanner.getValue());
+  }
+
+  @Override
+  public boolean seekTo(BytesWritable key) throws IOException {
+    boolean rv = false;
+    for (CachedTableScanner scanner : scanners) {
+      rv = rv || scanner.seekTo(key);
+    }
+    synced = false;
+    return rv;
+  }
+
+  @Override
+  public void seekToEnd() throws IOException {
+    for (CachedTableScanner scanner : scanners) {
+      scanner.seekToEnd();
+    }
+    synced = false;
+  }
+
+  @Override
+  public void close() throws IOException {
+    for (CachedTableScanner scanner : scanners) {
+      scanner.close();
+    }
+    queue.clear();
+  }
+}

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/package-info.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/package-info.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/package-info.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/mapred/package-info.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,24 @@
+/**
+ * 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.
+ */
+
+/**
+ * Providing {@link org.apache.hadoop.mapred.InputFormat} and
+ * {@link org.apache.hadoop.mapred.OutputFormat} adaptor classes for Hadoop
+ * Table.
+ */
+package org.apache.hadoop.zebra.mapred;
+

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/package-info.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/package-info.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/package-info.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/package-info.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,68 @@
+/**
+ * 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.
+ */
+
+/**
+ * Hadoop Table - tabular data storage for Hadoop MapReduce and PIG.
+ * <p>
+ * Hadoop Table provides tabular-type data storage for <a
+ * href="http://hadoop.apache.org/core/docs/current/mapred_tutorial.html">Hadoop
+ * MapReduce Framework</a>. It is also planned to allow Table to be closely
+ * integrated with <a href="http://wiki.apache.org/pig/FrontPage">PIG</a>.
+ * <p>
+ * For this release, the basic construct of HadoopTable is called
+ * {@link org.apache.hadoop.zebra.io.BasicTable}. A BasicTable is a create-once,
+ * read-only kind of persisten data storage entity. A BasicTable contains zero
+ * or more keyed rows.
+ * <p>
+ * The API uses Hadoop {@link org.apache.hadoop.io.BytesWritable} objects to
+ * represent row keys, and PIG {@link org.apache.pig.data.Tuple} objects to
+ * represent rows.
+ * <p>
+ * Each BasicTable maintains a {@link org.apache.hadoop.zebra.types.Schema} ,
+ * which, for this release, is nothing but a collection of column names. Given a
+ * schema, we can deduce the integer index of a particular column, and use it to
+ * extract (get) the desired datum from PIG Tuple object (which only allows
+ * index-based access).
+ * <p>
+ * Typically, applications use
+ * {@link org.apache.hadoop.zebra.mapred.BasicTableOutputFormat} (which implements
+ * the Hadoop {@link org.apache.hadoop.mapred.OutputFormat} interface) to create
+ * BasicTables through MapReduce. And they use
+ * {@link org.apache.hadoop.zebra.mapred.TableInputFormat} (which implements the
+ * Hadoop {@link org.apache.hadoop.mapred.InputFormat} to feed the data as their
+ * MapReduce input.
+ * <p>
+ * The API is structured in three packages:
+ * <UL>
+ * <LI> {@link org.apache.hadoop.zebra.mapred} : The MapReduce layer. It contains
+ * two classes: BasicTableOutputFormat for creating BasicTable; and
+ * TableInputFormat for readding table.
+ * 
+ * <LI> {@link org.apache.hadoop.zebra.types} : Miscellaneous facilities that handle
+ * column types and tuple serializations. Currently, it is a place holder that
+ * redirects to PIG serialization. There is no type information being managed by
+ * Table for individual columns.
+ *
+ * <LI> org.apache.hadoop.zebra.io : This is the internal IO layer. It deals 
+ * with the physical storage (files) management of BasicTable. It also provides
+ * facilities to help MapReduce layer create splits, such as partitioning
+ * BasicTables for reading and reporting data block placement distributions
+ * based on range-partitions or key-partitions.
+ * </UL>
+ */
+package org.apache.hadoop.zebra;
+

Added: hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/pig/SchemaConverter.java
URL: http://svn.apache.org/viewvc/hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/pig/SchemaConverter.java?rev=803312&view=auto
==============================================================================
--- hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/pig/SchemaConverter.java (added)
+++ hadoop/pig/trunk/contrib/zebra/src/java/org/apache/hadoop/zebra/pig/SchemaConverter.java Tue Aug 11 22:27:44 2009
@@ -0,0 +1,120 @@
+/**
+ * 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.hadoop.zebra.pig;
+
+import java.util.Iterator;
+
+import org.apache.hadoop.zebra.types.ParseException;
+import org.apache.pig.data.DataType;
+import org.apache.pig.impl.logicalLayer.FrontendException;
+import org.apache.pig.impl.logicalLayer.schema.Schema;
+import org.apache.pig.impl.logicalLayer.schema.Schema.FieldSchema;
+
+/**
+ * A simple schema converter that only understands three field types.
+ */
+class SchemaConverter {
+  enum FieldSchemaMaker {
+    SimpleField("SF_") {
+      @Override
+      FieldSchema toFieldSchema(String name) {
+        return new FieldSchema(name, DataType.BYTEARRAY);
+      }
+    },
+
+    MapField("MF_") {
+      @Override
+      FieldSchema toFieldSchema(String name) {
+        // TODO: how to convey key and value types?
+        return new FieldSchema(name, DataType.MAP);
+      }
+    },
+
+    MapListField("MLF_") {
+      @Override
+      FieldSchema toFieldSchema(String name) throws FrontendException {
+        Schema tupleSchema = new Schema();
+        tupleSchema.add(MapField.toFieldSchema(null));
+        tupleSchema.setTwoLevelAccessRequired(true);
+        return new FieldSchema(name, tupleSchema, DataType.BAG);
+      }
+    };
+
+    private String prefix;
+
+    FieldSchemaMaker(String prefix) {
+      this.prefix = prefix;
+    }
+
+    abstract FieldSchema toFieldSchema(String name) throws FrontendException;
+
+    public static FieldSchema makeFieldSchema(String colname)
+        throws FrontendException {
+      for (FieldSchemaMaker e : FieldSchemaMaker.values()) {
+        if (colname.startsWith(e.prefix)) {
+          return e.toFieldSchema(colname.substring(e.prefix.length()));
+        }
+      }
+      throw new FrontendException("Cannot determine type from column name");
+    }
+    
+    public static String makeColumnName(FieldSchema fs)
+        throws FrontendException {
+      if (fs.alias == null) {
+        throw new FrontendException("No alias provided for field schema");
+      }
+      for (FieldSchemaMaker e : FieldSchemaMaker.values()) {
+        FieldSchema expected = e.toFieldSchema("dummy");
+        if (FieldSchema.equals(fs, expected, false, true)) {
+          return e.prefix + fs.alias;
+        }
+      }
+      throw new FrontendException("Unsupported field schema");
+    }
+  }
+  
+  public static Schema toPigSchema(
+      org.apache.hadoop.zebra.types.Schema tschema)
+      throws FrontendException {
+    Schema ret = new Schema();
+    for (String col : tschema.getColumns()) {
+    	org.apache.hadoop.zebra.types.Schema.ColumnSchema columnSchema = 
+    		tschema.getColumn(col);
+			if (columnSchema != null) {
+        ret.add(new FieldSchema(col, columnSchema.type.pigDataType()));
+			} else {
+				ret.add(new FieldSchema(null, null));
+			}
+    }
+    
+    return ret;
+  }
+
+  public static org.apache.hadoop.zebra.types.Schema fromPigSchema(
+      Schema pschema) throws FrontendException, ParseException {
+    String[] colnames = new String[pschema.size()];
+    int i = 0;
+    for (Iterator<FieldSchema> it = pschema.getFields().iterator(); it
+        .hasNext(); ++i) {
+      FieldSchema fs = it.next();
+      colnames[i] = FieldSchemaMaker.makeColumnName(fs);
+    }
+    return new org.apache.hadoop.zebra.types.Schema(colnames);
+  }
+}