## Sunday Apr 07, 2013

### Introduction

In the final installment in our series on Hive UDFs, we're going to tackle the least intuitive of the three types: the User Defined Aggregating Function.  While they're challenging to implement, UDAFs are necessary if we want functions for which the distinction of map-side v. reduce-side operations are opaque to the user.  If a user is writing a query, most would prefer to focus on the data they're trying to compute, not which part of the plan is running a given function.

The UDAF also provides a valuable opportunity to consider some of the nuances of distributed programming and parallel database operations.  Since each task in a MapReduce job operates in a bit of a vacuum (e.g. Map task A does not know what data Map task B has), a UDAF has to explicitly account for more operational states than a simple UDF.  We'll return to the notion of a simple Moving Average function, but ask yourself: how do we compute a moving average if we don't have state or order around the data?

As before, the code is available on github, but we'll excerpt the important parts here.

### Prefix Sum: Moving Average without State

In order to compute a moving average without state, we're going to need a specialized parallel algorithm.  For moving average, the "trick" is to use a prefix sum, effectively keeping a table of running totals for quick computation (and recomputation) of our moving average.  A full discussion of prefix sums for moving averages is beyond length of a blog post, but John Jenq provides an excellent discussion of the technique as applied to CUDA implementations.

What we'll cover here is the necessary implementation of a pair of classes to store and operate on our prefix sum entry within the UDAF.

`public class PrefixSumMovingAverage {    static class PrefixSumEntry implements Comparable     {        int period;        double value;        double prefixSum;        double subsequenceTotal;        double movingAverage;        public int compareTo(Object other)        {            PrefixSumEntry o = (PrefixSumEntry)other;            if (period < o.period)                return -1;            if (period > o.period)                return 1;            return 0;        }`

}

Here we have the definition of our moving average class and the static inner class which serves as an entry in our table.  What's important here are some of the variables we define for each entry in the table: the time-index or period of the value (its order), the value itself, the prefix sum,  the subsequence total, and the moving average itself.  Every entry in our table requires not just the current value to compute the moving average, but also sum of entries in our moving average window.  It's the pair of these two values which allows prefix sum methods to work their magic.

`//class variables    private int windowSize;    private ArrayList<PrefixSumEntry> entries;        public PrefixSumMovingAverage()    {        windowSize = 0;    }        public void reset()    {        windowSize = 0;        entries = null;    }        public boolean isReady()    {        return (windowSize > 0);    }`

The above are simple initialization routines: a constructor, a method to reset the table, and a boolean method on whether or not the object has a prefix sum table on which to operate.  From here, there are 3 important methods to examine: add, merge, and serialize.  The first is intuitive, as we scan rows in Hive we want to add them to our prefix sum table.  The second are important because of partial aggregation.

We cannot say ahead of time where this UDAF will run, and partial aggregation may be required.  That is, it's entirely possible that some values may run through the UDAF during a map task, but then be passed to a reduce task to be combined with other values.  The serialize method will allow Hive to pass the partial results from the map side to the reduce side.  The merge method allows reducers to combine the results of partial aggregations from the map tasks.

` @SuppressWarnings("unchecked")  public void add(int period, double v)  {    //Add a new entry to the list and update table    PrefixSumEntry e = new PrefixSumEntry();    e.period = period;    e.value = v;    entries.add(e);    // do we need to ensure this is sorted?    //if (needsSorting(entries))    	Collections.sort(entries);    // update the table    // prefixSums first    double prefixSum = 0;    for(int i = 0; i < entries.size(); i++)    {        PrefixSumEntry thisEntry = entries.get(i);        prefixSum += thisEntry.value;        thisEntry.prefixSum = prefixSum;        entries.set(i, thisEntry);    }`

The first part of the add task is simple: we add the element to the list and update our table's prefix sums.

` // now do the subsequence totals and moving averages    for(int i = 0; i < entries.size(); i++)    {        double subsequenceTotal;        double movingAverage;        PrefixSumEntry thisEntry = entries.get(i);        PrefixSumEntry backEntry = null;        if (i >= windowSize)            backEntry = entries.get(i-windowSize);        if (backEntry != null)        {            subsequenceTotal = thisEntry.prefixSum - backEntry.prefixSum;                    }        else        {            subsequenceTotal = thisEntry.prefixSum;        }        movingAverage = subsequenceTotal/(double)windowSize;	thisEntry.subsequenceTotal = subsequenceTotal;	thisEntry.movingAverage = movingAverage;	entries.set(i, thisEntry);`

}

In the second half of the add function, we compute our moving averages based on the prefix sums.  It's here you can see the hinge on which the algorithm swings: thisEntry.prefixSum - backEntry.prefixSum -- that offset between the current table entry and it's nth predecessor makes the whole thing work.

`public ArrayList<DoubleWritable> serialize()  {    ArrayList<DoubleWritable> result = new ArrayList<DoubleWritable>();        result.add(new DoubleWritable(windowSize));    if (entries != null)    {        for (PrefixSumEntry i : entries)        {            result.add(new DoubleWritable(i.period));            result.add(new DoubleWritable(i.value));        }    }    return result;`

}

The serialize method needs to package the results of our algorithm to pass to another instance of the same algorithm, and it needs to do so in a type that Hadoop can serialize.  In the case of a method like sum, this would be relatively simple: we would only need to pass the sum up to this point.  However, because we cannot be certain whether this instance of our algorithm has seen all the values, or seen them in the correct order, we actually need to serialize the whole table.  To do this, we create a list ofDoubleWritables, pack the window size at its head, and then each period and value.  This gives us a structure that's easy to unpack and merge with other lists with the same construction.

` @SuppressWarnings("unchecked")  public void merge(List<DoubleWritable> other)  {    if (other == null)        return;        // if this is an empty buffer, just copy in other    // but deserialize the list    if (windowSize == 0)    {        windowSize = (int)other.get(0).get();        entries = new ArrayList<PrefixSumEntry>();        // we're serialized as period, value, period, value        for (int i = 1; i < other.size(); i+=2)        {            PrefixSumEntry e = new PrefixSumEntry();            e.period = (int)other.get(i).get();            e.value = other.get(i+1).get();            entries.add(e);        }`

}

Merging results is perhaps the most complicated thing we need to handle.  First, we check the case in which there was no partial result passed -- just return and continue.  Second, we check to see if this instance of PrefixSumMovingAverage already has a table.  If it doesn't, we can simply unpack the serialized result and treat it as our window.

`   // if we already have a buffer, we need to add these entries    else    {        // we're serialized as period, value, period, value        for (int i = 1; i < other.size(); i+=2)        {            PrefixSumEntry e = new PrefixSumEntry();            e.period = (int)other.get(i).get();            e.value = other.get(i+1).get();            entries.add(e);        }`

}

The third case is the non-trivial one: if this instance has a table and receives a serialized table, we must merge them together.  Consider a Reduce task: as it receives outputs from multiple Map tasks, it needs to merge all of them together to form a larger table.  Thus, merge will be called many times to add these results and reassemble a larger time series.

`// sort and recompute    Collections.sort(entries);    // update the table    // prefixSums first    double prefixSum = 0;    for(int i = 0; i < entries.size(); i++)    {        PrefixSumEntry thisEntry = entries.get(i);        prefixSum += thisEntry.value;        thisEntry.prefixSum = prefixSum;        entries.set(i, thisEntry);`

}

This part should look familiar, it's just like the add method.  Now that we have new entries in our table, we need to sort by period and recompute the moving averages.  In fact, the rest of the merge method is exactly like the add method, so we might consider putting sorting and recomputing in a separate method.

### Orchestrating Partial Aggregation

We've got a clever little algorithm for computing moving average in parallel, but Hive can't do anything with it unless we create a UDAF that understands how to use our algorithm.  At this point, we need to start writing some real UDAF code.  As before, we extend a generic class, in this case GenericUDAFEvaluator.

`  public static class GenericUDAFMovingAverageEvaluator extends GenericUDAFEvaluator {                    // input inspectors for PARTIAL1 and COMPLETE        private PrimitiveObjectInspector periodOI;        private PrimitiveObjectInspector inputOI;        private PrimitiveObjectInspector windowSizeOI;                // input inspectors for PARTIAL2 and FINAL        // list for MAs and one for residuals        private StandardListObjectInspector loi;`

As in the case of a UDTF, we create ObjectInspectors to handle type checking.  However, notice that we have inspectors for different states: PARTIAL1, PARTIAL2, COMPLETE, and FINAL.  These correspond to the different states in which our UDAF may be executing.  Since our serialized prefix sum table isn't the same input type as the values our add method takes, we need different type checking for each.

` @Override        public ObjectInspector init(Mode m, ObjectInspector[] parameters) throws HiveException {                    super.init(m, parameters);                        // initialize input inspectors            if (m == Mode.PARTIAL1 || m == Mode.COMPLETE)            {                assert(parameters.length == 3);                periodOI = (PrimitiveObjectInspector) parameters[0];                inputOI = (PrimitiveObjectInspector) parameters[1];                windowSizeOI = (PrimitiveObjectInspector) parameters[2];            }`

Here's the beginning of our overrided initialization function.  We check the parameters for two modes, PARTIAL1 and COMPLETE.  Here we assume that the arguments to our UDAF are the same as the user passes in a query: the period, the input, and the size of the window.  If the UDAF instance is consuming the results of our partial aggregation, we need a different ObjectInspector.  Specifically, this one:

`else            {                loi = (StandardListObjectInspector) parameters[0];`

}

Similar to the UDTF, we also need type checking on the output types -- but for both partial and full aggregation. In the case of partial aggregation, we're returning lists of DoubleWritables:

`              // init output object inspectors            if (m == Mode.PARTIAL1 || m == Mode.PARTIAL2) {                // The output of a partial aggregation is a list of doubles representing the                // moving average being constructed.                // the first element in the list will be the window size                //                 return ObjectInspectorFactory.getStandardListObjectInspector(                    PrimitiveObjectInspectorFactory.writableDoubleObjectInspector);`

}

But in the case of FINAL or COMPLETE, we're dealing with the types that will be returned to the Hive user, so we need to return a different output.  We're going to return a list of structs that contain the period, moving average, and residuals (since they're cheap to compute).

```else {                // The output of FINAL and COMPLETE is a full aggregation, which is a                // list of DoubleWritable structs that represent the final histogram as                // (x,y) pairs of bin centers and heights.                                ArrayList<ObjectInspector> foi = new ArrayList<ObjectInspector>();                foi.add(PrimitiveObjectInspectorFactory.writableDoubleObjectInspector);                foi.add(PrimitiveObjectInspectorFactory.writableDoubleObjectInspector);		foi.add(PrimitiveObjectInspectorFactory.writableDoubleObjectInspector);                ArrayList<String> fname = new ArrayList<String>();                fname.add("period");                fname.add("moving_average");		fname.add("residual");
return ObjectInspectorFactory.getStandardListObjectInspector(                 ObjectInspectorFactory.getStandardStructObjectInspector(fname, foi) );```

}

Next come methods to control what happens when a Map or Reduce task is finished with its data.  In the case of partial aggregation, we need to serialize the data.  In the case of full aggregation, we need to package the result for Hive users.

```  @Override    public Object terminatePartial(AggregationBuffer agg) throws HiveException {      // return an ArrayList where the first parameter is the window size      MaAgg myagg = (MaAgg) agg;      return myagg.prefixSum.serialize();    }
@Override    public Object terminate(AggregationBuffer agg) throws HiveException {      // final return value goes here      MaAgg myagg = (MaAgg) agg;            if (myagg.prefixSum.tableSize() < 1)      {        return null;      }            else      {        ArrayList<DoubleWritable[]> result = new ArrayList<DoubleWritable[]>();        for (int i = 0; i < myagg.prefixSum.tableSize(); i++)        {	    double residual = myagg.prefixSum.getEntry(i).value - myagg.prefixSum.getEntry(i).movingAverage;
DoubleWritable[] entry = new DoubleWritable[3];            entry[0] = new DoubleWritable(myagg.prefixSum.getEntry(i).period);            entry[1] = new DoubleWritable(myagg.prefixSum.getEntry(i).movingAverage);	    entry[2] = new DoubleWritable(residual);            result.add(entry);        }                return result;      }      ```

}

We also need to provide instruction on how Hive should merge the results of partial aggregation.  Fortunately, we already handled this in our PrefixSumMovingAverage class, so we can just call that.

`@SuppressWarnings("unchecked")    @Override    public void merge(AggregationBuffer agg, Object partial) throws HiveException {        // if we're merging two separate sets we're creating one table that's doubly long                if (partial != null)        {            MaAgg myagg = (MaAgg) agg;            List<DoubleWritable> partialMovingAverage = (List<DoubleWritable>) loi.getList(partial);            myagg.prefixSum.merge(partialMovingAverage);        }`

}

Of course, merging and serializing isn't very useful unless the UDAF has logic for iterating over values.  The iterate method handles this and -- as one would expect -- relies entirely on thePrefixSumMovingAverage class we created.

```@Override    public void iterate(AggregationBuffer agg, Object[] parameters) throws HiveException {          assert (parameters.length == 3);            if (parameters[0] == null || parameters[1] == null || parameters[2] == null)      {        return;      }            MaAgg myagg = (MaAgg) agg;            // Parse out the window size just once if we haven't done so before.  We need a window of at least 1,      // otherwise there's no window.      if (!myagg.prefixSum.isReady())      {        int windowSize = PrimitiveObjectInspectorUtils.getInt(parameters[2], windowSizeOI);        if (windowSize < 1)        {            throw new HiveException(getClass().getSimpleName() + " needs a window size >= 1");        }        myagg.prefixSum.allocate(windowSize);      }            //Add the current data point and compute the average
int p = PrimitiveObjectInspectorUtils.getInt(parameters[0], inputOI);      double v = PrimitiveObjectInspectorUtils.getDouble(parameters[1], inputOI);      myagg.prefixSum.add(p,v);      ```

}

### Aggregation Buffers: Connecting Algorithms with Execution

One might notice that the code for our UDAF references an object of type AggregationBuffer quite a lot.  This is because the AggregationBuffer is the interface which allows us to connect our custom PrefixSumMovingAverage class to Hive's execution framework.  While it doesn't constitute a great deal of code, it's glue that binds our logic to Hive's execution framework.  We implement it as such:

``` // Aggregation buffer definition and manipulation methods     static class MaAgg implements AggregationBuffer {        PrefixSumMovingAverage prefixSum;    };
@Override    public AggregationBuffer getNewAggregationBuffer() throws HiveException {      MaAgg result = new MaAgg();      reset(result);      return result;```

}

### Using the UDAF

The goal of a good UDAF is that, no matter how complicated it was for us to implement, it's that it be simple for our users.  For all that code and parallel thinking, usage of the UDAF is very straightforward:

`ADD JAR /mnt/shared/hive_udfs/dist/lib/moving_average_udf.jar;CREATE TEMPORARY FUNCTION moving_avg AS 'com.oracle.hadoop.hive.ql.udf.generic.GenericUDAFMovingAverage'; #get the moving average for a single tail numberSELECT TailNum,moving_avg(timestring, delay, 4) FROM ts_example WHERE TailNum='N967CA' GROUP BY TailNum LIMIT 100;`

Here we're applying the UDAF to get the moving average of arrival delay from a particular flight.  It's a really simple query for all that work we did underneath.  We can do a bit more and leverage Hive's abilities to handle complex types as columns, here's a query which creates a table of timeseries as arrays.

`#create a set of moving averages for every plane starting with N#Note: this UDAF blows up unpleasantly in heap; there will be data volumes for which you need to throw#excessive amounts of memory at the problemCREATE TABLE moving_averages AS SELECT TailNum, moving_avg(timestring, delay, 4) as timeseries FROM ts_example `

WHERE TailNum LIKE 'N%' GROUP BY TailNum;

### Summary

We've covered all manner of UDFs: from simple class extensions which can be written very easily, to very complicated UDAFs which require us to think about distributed execution and plan orchestration done by query engines.  With any luck, the discussion has provided you with the confidence to go out and implement your own UDFs -- or at least pay some attention to the complexities of the ones in use every day.

## Thursday Apr 04, 2013

### Introduction

In our ongoing series of posts explaining the in's and out's of Hive User Defined Functions, we're starting with the simplest case.  Of the three little UDFs, today's entry built a straw house: simple, easy to put together, but limited in applicability.  We'll walk through important parts of the code, but you can grab the whole source from github here.

### Extending UDF

The first few lines of interest are very straightforward:

`@Description(name = "moving_avg", value = "_FUNC_(x, n) - Returns the moving mean of a set of numbers over a window of n observations")@UDFType(deterministic = false, stateful = true)`

public class UDFSimpleMovingAverage extends UDF

We're extending the UDF class with some decoration.  The decoration is important for usability and functionality.  The description decorator allows us to give the Hive some information to show users about how to use our UDF and what it's method signature will be.  The UDFType decoration tells Hive what sort of behavior to expect from our function.

A deterministic UDF will always return the same output given a particular input.  A square-root computing UDF will always return the same square root for 4, so we can say it is deterministic; a call to get the system time would not be.  The stateful annotation of the UDFType decoration is relatively new to Hive (e.g., CDH4 and above).  The stateful directive allows Hive to keep some static variables available across rows.  The simplest example of this is a "row-sequence," which maintains a static counter which increments with each row processed.

Since square-root and row-counting aren't terribly interesting, we'll use the stateful annotation to build a simple moving average function.  We'll return to the notion of a moving average later when we build a UDAF, so as to compare the two approaches.

`private DoubleWritable result = new DoubleWritable();  private static ArrayDeque<Double> window;  int windowSize;    public UDFSimpleMovingAverage() {    result.set(0);`

}

The above code is basic initialization.  We make a double in which to hold the result, but it needs to be of class DoubleWritable so that MapReduce can properly serialize the data.  We use a deque to hold our sliding window, and we need to keep track of the window's size.  Finally, we implement a constructor for the UDF class.

` public DoubleWritable evaluate(DoubleWritable v, IntWritable n) {    double sum = 0.0;    double moving_average;    double residual;    if (window == null)    {        window = new ArrayDeque<Double>();`

}

Here's the meat of the class: the evaluate method.  This method will be called on each row by the map tasks.  For any given row, we can't say whether or not our sliding window exists, so we initialize it if it's null.

`//slide the window    if (window.size() == n.get())        window.pop();                window.addLast(new Double(v.get()));                // compute the average    for (Iterator<Double> i = window.iterator(); i.hasNext();)`

sum += i.next().doubleValue();

Here we deal with the deque and compute the sum of the window's elements.  Deques are essentially double-ended queues, so they make excellent sliding windows.  If the window is full, we pop the oldest element and add the current value.

`moving_average = sum/window.size();    result.set(moving_average);`

return result;

Computing the moving average without weighting is simply dividing the sum of our window by its size.  We then set that value in our Writable variable and return it.  The value is then emitted as part of the map task executing the UDF function.

### Going Further

The stateful annotation made it simple for us to compute a moving average since we could keep the deque static.  However, how would we compute a moving average if there was no notion of state between Hadoop tasks? At the end of the series we'll examine a UDAF that does this, but the algorithm ends up being much different.  In the meantime, I challenge the reader to think about what sort of approach is needed to compute the window.