Hi Stuart, It seems to me like you have a few options.
Option 1: Just use a lot of RAM. Unless you really expect many millions of entries on both sides of the join, you might be able to get away with buffering despite its inefficiency. Option 2: Use LocalDirAllocator to find some local storage to spill all of the left table's records to disk in a MapFile format. Then as you iterate over the right table, do lookups in the MapFile. This is really the same as option 1, except that you're using disk as an extension of RAM. Option 3: Convert this to a map-side merge join. Basically what you need to do is sort both tables by the join key, and partition them with the same partitioner into the same number of columns. This way you have an equal number of part-NNNNN files for both tables, and within each part-NNNNN file they're ordered by join key. In each map task, you open both tableA/part-N and tableB/part-N and do a sequential merge to perform the join. I believe the CompositeInputFormat class helps with this, though I've never used it. Option 4: Perform the join in several passes. Whichever table is smaller, break into pieces that fit in RAM. Unless my relational algebra is off, A JOIN B = A JOIN (B1 UNION B2) = (A JOIN B1 UNION A JOIN B2) if B = B1 UNION B2. Hope that helps -Todd On Thu, May 28, 2009 at 5:02 AM, Stuart White <stuart.whi...@gmail.com>wrote: > I need to do a reduce-side join of two datasets. It's a many-to-many > join; that is, each dataset can can multiple records with any given > key. > > Every description of a reduce-side join I've seen involves > constructing your keys out of your mapper such that records from one > dataset will be presented to the reducers before records from the > second dataset. I should "hold on" to the value from the one dataset > and remember it as I iterate across the values from the second > dataset. > > This seems like it only works well for one-to-many joins (when one of > your datasets will only have a single record with any given key). > This scales well because you're only remembering one value. > > In a many-to-many join, if you apply this same algorithm, you'll need > to remember all values from one dataset, which of course will be > problematic (and won't scale) when dealing with large datasets with > large numbers of records with the same keys. > > Does an efficient algorithm exist for a many-to-many reduce-side join? >
