Hey all,

I am trying to figure out the best way to approach some joining/merging
computation in a map-reduce / hbase framework.  I have the following large
timeseries datasets (key/value pairs keyed and sorted by time):

Events1:
t1, event1_value1
t3, event1_value2,
...

Event2:
t2, event2_value1
t3, event2_value2,
t4, event2_value3,
....

Currently, I am just storing these as flat files in HDFS but I have no
problems throwing them into HBase tables.  I am trying to do an operation
like the following: for every event in Events2, find and join with the event
that immediately precedes (timestamp <=) this event in table Events1.

This operation would result in something like:

JoinedEvents:
t2, events2_value1, events1_value1
t3, events2_value2, events1_value2
t4, events2_value3, events1_value2

etc.

What is the best way to go about this in Hadoop?

Thanks in advance for the help.

I don't know if it's the best way, but it's *a* way:

1. Map: take dataset A and build a sparse index into it (first
timestamp in every split will do).  Reduce: Write the pairs
(timestamp, offset) into a lookup file.

2. Map: every mapper works on a chunk of B; load in the lookup file
from step one (it may make sense to use something like Distributed
Cache to prep your nodes and avoid contention on this small file), and
for every timestamp, find the largest timestamp in the lookup that is
smaller than the timestamp from B. Seek to the corresponding offset in
A. Scan forward from that point until you see the timestamp >= the one
in B. The previous record has your answer. Get the next record from B,
repeat (you can choose to keep scanning from where you are in A, or
use the index to jump if there is a big gap between B's timestamps).

This is essentially how Pig does its skewed join, with some simplifications.

-Dmitriy

On Wed, Nov 4, 2009 at 11:53 AM, Calvin <[EMAIL PROTECTED]> wrote:
> Hey all,
> I am trying to figure out the best way to approach some joining/merging
> computation in a map-reduce / hbase framework.  I have the following large
> timeseries datasets (key/value pairs keyed and sorted by time):
> Events1:
> t1, event1_value1
> t3, event1_value2,
> ...
> Event2:
> t2, event2_value1
> t3, event2_value2,
> t4, event2_value3,
> ....
> Currently, I am just storing these as flat files in HDFS but I have no
> problems throwing them into HBase tables.  I am trying to do an operation
> like the following: for every event in Events2, find and join with the event
> that immediately precedes (timestamp <=) this event in table Events1.
> This operation would result in something like:
> JoinedEvents:
> t2, events2_value1, events1_value1
> t3, events2_value2, events1_value2
> t4, events2_value3, events1_value2
> etc.
> What is the best way to go about this in Hadoop?
> Thanks in advance for the help.

> This is essentially how Pig does its skewed join, with some simplifications.

Um, I meant merge join :-).

org.apache.hadoop.mapred.join in hadoop 19

On Wed, Nov 4, 2009 at 10:20 AM, Dmitriy Ryaboy <[EMAIL PROTECTED]> wrote:

> > This is essentially how Pig does its skewed join, with some
> simplifications.
>
> Um, I meant merge join :-).
>

--
Pro Hadoop, a book to guide you from beginner to hadoop mastery,
http://www.amazon.com/dp/1430219424?tag=jewlerymall
www.prohadoopbook.com a community for Hadoop Professionals

Jason,

I am not sure that the join package would work in this particular case.

The javadoc says "Given a set of sorted datasets keyed with the same
class and yielding equal partitions, it is possible to effect a join
of those datasets prior to the map" -- Calvin's datasets are not
necessarily equally partitioned.

Moreover, mapred.join assumes equijoins (equality can be modified by
providing a key comparator).  Calvin's use case is "join to the record
before the equal record" which requires more context than a Comparator
sees. Are you suggesting that one could use a custom JoinRecordReader?
I suspect even so, there is the edge problem -- if timestamps of first
records on a given partition are equal, you want to fetch the last
record of the previous partition.

-Dmitriy

On Thu, Nov 5, 2009 at 6:20 AM, Jason Venner <[EMAIL PROTECTED]> wrote:
> org.apache.hadoop.mapred.join in hadoop 19
>
> On Wed, Nov 4, 2009 at 10:20 AM, Dmitriy Ryaboy <[EMAIL PROTECTED]> wrote:
>>
>> > This is essentially how Pig does its skewed join, with some
>> > simplifications.
>>
>> Um, I meant merge join :-).
>
>
>
> --
> Pro Hadoop, a book to guide you from beginner to hadoop mastery,
> http://www.amazon.com/dp/1430219424?tag=jewlerymall
> www.prohadoopbook.com a community for Hadoop Professionals
>