org.apache.hadoop.zebra.pig.comparator

Class KeyGenerator

java.lang.Object

org.apache.hadoop.zebra.pig.comparator.KeyGenerator

public class KeyGenerator
extends Object

Generating binary keys for algorithmic comparators. A user may construct an algorithmic comparator by creating a ComparatorExpr object (through various static methods in this class). She could then create a KeyGenerator object and use it to create binary keys for tuple. The KeyGenerator object can be reused for different tuples that conform to the same schema. Sorting the tuples by the binary key yields the same ordering as sorting by the algorithmic comparator. Basic idea (without optimization):

• define two operations: escape and complement, that takes in a byte array, and outputs a byte array:

   escape(byte[] bytes) {
     for (byte b : bytes) {
       if (b == 0)
         emit(0x1, 0x0);
       else if (b == 1)
         emit(0x1, 0x2);
       else emit(b);
     }
   }
   
   complement(byte[] bytes) {
     for (byte b : bytes) {
       emit(˜b);
     }
   }
   

• find ways to convert primitive types to bytes that compares in the same order as those objects.
• operations:
  • negate(byte[] bytes) == complement(escape(bytes) + 0x0);
  • tuple(byte[] bytes1, byte[] bytes2) == escape(bytes1) + 0x0 + escape(bytes2)
  • bag(byte[] bytes1, byte[] bytes2, ... ) = escape(bytes1) + 0x0 + escape(bytes2) + ...
• optimizations:
  • negate(negate(bytes)) == bytes;
  • tuple(a) == a;
  • tuple(a, tuple(b, c)) == tuple(a, b, c)
  • the actual output would be a concatenation of f1(o1), f2(o2), ..., where o1, o2, are leaf datums in the tuple or 0x0, and fi(oi) is a nested function of escape() and complement() calls.
  • The invariance we want to preserve is that escape(0x1) > escape(escape(0x0)) > escape(0x0) > 0x0. In the basic algorithm, these are escaped as 0x0102, 0x010100, 0x0100, 0x00, and are thus variable length. We can actually collapse nested consecutive calls of escape(escape(...escape(0))...) to escape(i, 0), where i is the level of nesting, and fi may be represented as nested inter-leaved calling of complement(bytes) and escape(i, bytes), where escape (i, 0x0) == 0x01 + (0x01+i) and escape(i, 1) == 0x010xFD. We do limit the total nesting depth by 252, which should be plenty.
  • we can further optimize fi as either escape(i, j, bytes) or complement(escape(i, j, bytes), where i is the level of nesting for escaping 0x0 and 0x1, and j the level of nesting for escaping 0xff and 0xfe.
  • If the binary keys being generated from a certain comparator either compare equal or differ at some byte position, but never the case where one is a prefix of another, then we do not need to add padding 0x0 for negate() or tuple(). This is captured by the method implicitBound() in ComparatorExpr.
  • We figure out how datums should be extracted from a tuple and being escaped only once for any expression, and write to a modified ByteArrayOutputStream in one pass.

TODO Remove the strong dependency with Pig by adding a DatumExtractor interface that allow applications to extract leaf datum from user objects, something like the following:

 interface DatumExtractor {
   Object extract(Object o);
 }
 

And user may do something like this:

 class MyObject {
  int a;
  String b;
 }
 
 ComparatorExpr expr = KeyBuilder.createLeafExpr(new DatumExtractor {
  Object extract(Object o) {
      MyObject obj = (MyObject)o;
      return obj.b;
  } }, DataType.CHARARRAY);
 

TODO Change BagExpr to IteratorExpr, so that it may be used in more general context (any Java collection). TODO Add an ArrayExpr (for Java []).

Constructor Summary

Constructors

Constructor and Description
KeyGenerator(ComparatorExpr expr) Create a key builder that can generate binary keys for the input key expression.

Method Summary

Methods

Modifier and Type	Method and Description
org.apache.hadoop.io.BytesWritable	generateKey(Tuple t) Generate the binary key for the input tuple
void	illustrate(PrintStream ps) Illustrate how the key would be generated from source.
void	reset(ComparatorExpr expr) Reset the key builder for a new expression.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KeyGenerator

public KeyGenerator(ComparatorExpr expr)

Create a key builder that can generate binary keys for the input key expression.

Parameters:

expr - comparator expression

Method Detail

reset

public void reset(ComparatorExpr expr)

Reset the key builder for a new expression.

Parameters:

expr - comparator expression

generateKey

public org.apache.hadoop.io.BytesWritable generateKey(Tuple t)
                                               throws ExecException

Generate the binary key for the input tuple

Parameters:

t - input tuple

Returns:

A BytesWritable containing the binary sorting key for the input tuple.

Throws:

ExecException

illustrate

public void illustrate(PrintStream ps)

Illustrate how the key would be generated from source.

Parameters:

ps - The output print stream.