GYM: A Multiround Join Algorithm In MapReduce And Its Analysis

We study the problem of computing the join of n relations in mul-tiple rounds of MapReduce. We introduce a distributed and gen-eralized version of Yannakakis’s algorithm, called GYM. GYM takes as input any generalized hypertree decomposition (GHD) of a query of width w and depth d, and computes the query in O(d+log(n)) rounds andO(n (IN w+OUT)2 M) communication cost, where M is the memory available per machine in the cluster and IN and OUT are the sizes of input and output of the query, respec-tively. M is assumed to be IN 1 , for some constant > 1. Using GYM we achieve two main results: (1) Every width-w query can be computed in O(n) rounds of MapReduce with O(n (IN w+OUT)2