twitter/scalding — pull request #758 by avibryant (2014-01-27 06:49:55+00:00)
Title: First sketch at a sketch join

Note: no test yet.

This join is appropriate where you have a larged, skewed left hand side that you want to join to a small right hand side: for example, joining page views against pages where the most popular pages each make up a significant fraction the total. It builds a CountMinSketch of the keys in the left hand side, then uses that to decide how many replicas of each item in the right side to produce, then does a normal join.

The semantics are similar to hash joins: you have to go directly from ````(TypedPipe[K,V],TypedPipe[K,V2])```` to some ````TypedPipe[K,R]````, with no guarantee of ever seeing the entirety of a group at once (and in fact, we reuse the hashInner2 and hashLeft2 joiner functions).

Rough usage:

````scala
left
.groupBy{_.foo}
.sketch
.join(right.groupBy{_.bar})
.withReducers(20)
.values
````