PAC: Computing Join Queries with Semi-Covers

An increased and growing interest in large-scale data processing has triggered a demand for specialized algorithms that thrive in massively parallel shared-nothing systems. To answer the question of how to efficiently compute join queries in this setting, a rich line of research has emerged specifically for the Massively Parallel Communication (MPC) model. In the MPC model, algorithms are executed in rounds, with each round consisting of a synchronized communication phase and a separate local computation phase. The main cost measure is the load of the algorithm, defined as the maximum number of messages received by any server in any round. We study worst-case optimal algorithms for the join query evaluation problem in the constant-round MPC model. In the single-round variant of the MPC model, the worst-case optimal load for this problem is well understood and algorithms exist that guarantee this load for any join query. In the constant-round variant of the MPC model, queries can often be computed with a lower load compared to the single-round variant, but the worst-case optimal load is only known for specific classes of queries, including the graph-like join queries and the acyclic join queries. Each of these classes has its own associated algorithms to achieve the worst-case optimal load, and these algorithms rely on very different techniques that are specific to the class. In this paper, we propose a new, unified constant-round MPC algorithm for computing join queries. This algorithm is correct for every join query and preserves the worst-case optimal load for many queries, particularly all join queries that are acyclic or graph-like. Additionaly, the algorithm is shown to be worst-case optimal for a new class of cyclic queries.