  We study three-way joins on MapReduce. Joins are very useful in a multitude
of applications from data integration and traversing social networks, to mining
graphs and automata-based constructions. However, joins are expensive, even for
moderate data sets; we need efficient algorithms to perform distributed
computation of joins using clusters of many machines. MapReduce has become an
increasingly popular distributed computing system and programming paradigm. We
consider a state-of-the-art MapReduce multi-way join algorithm by Afrati and
Ullman and show when it is appropriate for use on very large data sets. By
providing a detailed experimental study, we demonstrate that this algorithm
scales much better than what is suggested by the original paper. However, if
the join result needs to be summarized or aggregated, as opposed to being only
enumerated, then the aggregation step can be integrated into a cascade of
two-way joins, making it more efficient than the other algorithm, and thus
becomes the preferred solution.
