κ \kappa -Join: Combining Vertex Covers for Parallel Joins Simon Frisk, Austen Fan, Paraschos Koutris Abstract . Significant research effort has been devoted to improving the performance of join processing in the massively parallel computation model, where the goal is to evaluate a query with the minimum possible data transfer between machines. However, it is still an open question to determine the best possible parallel algorithm for any join query. In this paper, we present an algorithm that takes a step forward in this endeavour. Our new algorithm is simple and builds on two existing ideas: data partitioning and the HyperCube primitive. The novelty in our approach comes from a careful choice of the HyperCube shares, which is done as a linear combination of multiple vertex covers. The resulting load with input size n n and p p processors is characterized as n / p 1 / κ n/p^{1/\kappa} , where κ \kappa is a new hypergraph theoretic measure we call the reduced quasi vertex-cover. The new measure matches or improves on all state-of-the-art algorithms and exhibits strong similarities to the edge quasi-packing that describes the worst-case optimal load in one-round algorithms. 1. Introduction The MPC model, or massively parallel computation model , is frequently used to theoretically study algorithms to compute database queries in clusters of processors ( 5 ) . In this model, an algorithm consists of several rounds, where each round consists of exchange of data between processors, followed by local computation. Guided by the observation that performance often is bottlenecked by communication cost and synchronization cost, an algorithm in this model should minimize the number of rounds as well as the load of each round, defined as the maximum amount of data received by any processor in the round. There has been extensive research into understanding the cost of computing a join query in the MPC model, as a function of the query, the input size n , and the number of processors p . Early work on the MPC model focused on algorithms with one round of communication ( 5 ) and input data without skew, and built on the HyperCube algorithm to process joins ( 3 ) . For arbitrary database instances, a tight bound of n/p^{1/\psi^{*}} , where \psi^{*} is the quasi-edge packing, was obtained ( 17 ) . More recent work focused on algorithms where the number of communication steps is constant in n and p . A tight bound of n/p^{1/\rho^{*}} , where \rho^{*} is the fractional edge cover of the query, has been obtained for cyclic queries ( 11 ) and queries over binary relations ( 15 ) . Similar techniques have been used to improve the load on other classes of queries ( 20 ) . The quantity n/p^{1/\rho^{*}} is a known lower bound on all queries ( 17 ) , which builds on a counting argument using the AGM bound ( 4 ) . A higher lower bound was described on the boat query, showing n/p^{1/\rho^{*}} cannot be matched in general ( 11 ) . A recent state-of-the art improvement gave an algorithm matching the best known load on all queries except for the Loomis-Whitney join ( 1 ) . Whereas prior work uses heavy-light partitioning, this more recent work uses a more fine-grained data partitioning. Despite all these research efforts, the general worst-case optimal load remains open. Our Contributions In this paper, we present a new join algorithm, called \kappa -Join, establishing an upper bound of \tilde{O}(n/p^{1/\kappa}) on the load required to compute a join query in the MPC model, where \tilde{O} hides a polylogarithmic factor in n,p . Here, \kappa is a graph-theoretic quantity defined over the hypergraph of the query, which we call the reduced quasi vertex-cover . Our algorithm is relatively simple, but builds on several key ideas not found in previous work. The definition of \kappa bears strong similarities to the edge quasi-packing \psi^{*} , which describes the worst-case optimal load achievable with one-round algorithms in the MPC model. For a join query described by a hypergraph \mathcal{H}=(V,E) , the edge quasi-packing is defined as \psi^{*}:=\max_{S\subseteq V}\tau^{*}(\mathcal{H}[S]) , where \tau^{*}(\mathcal{H}[S]) denotes the value of the minimum vertex cover on the subhypergraph induced by the vertex set S . Similarly, the new measure \kappa is defined as \max_{S\subseteq V}\textsf{red}(\tau^{*}(\mathcal{H}[S])) , meaning the only difference is that any relation that is contained in another relation in \mathcal{H}[S] is removed before finding the minimum vertex cover. In addition, we present some arguments on why we believe that the derived upper bound of \tilde{O}(n/p^{1/\kappa}) might be optimal. Even though we do not show a tight lower bound for all queries, we provide a concrete worst-case instance construction that we conjecture to lead to it. Technical Overview Our algorithm builds on several concepts that exist in previous work, but also integrates multiple new key insights. A central primitive in the MPC model is the HyperCube algorithm. Many algorithms in previous work have the following overarching approach ( 1 ; 17 ; 15 ) . First, the input data is partitioned based on the degrees of different values, and the query is then computed in parallel for each partition. For each partition, certain join attributes, called heavy , may have high degree. Each possible tuple t_{H} over the heavy variables gets assigned a dedicated set of machines, which compute the part of the output where the heavy variables have values t_{H} . The query is often computed using some semijoins and then invoking HyperCube. Our algorithm also starts by performing data partitioning, but we perform a very fine-grained partitioning, which gives us precise control over the degrees occurring in each partition. To compute the join for a fixed data partition, our approach is quite different from previous work. We first identify and perform some binary joins that only grow the intermediate result size by a small factor. We then invoke the HyperCube algorithm on the intermediate results, instead of on the input relations. The shares used in the HyperCube algorithm are picked as a linear combination of vertex covers for different subqueries, each vertex cover corresponding to a hypergraph \textsf{red}(\mathcal{H}[S]) for some subset S\subseteq V . Comparison to State of the Art Our algorithm improves upon the state-of-the-art algorithm, known as PAC ( 1 ) , in two major ways. First, we prove that our algorithm achieves a load that is always at least as good as PAC, and other algorithms from previous work ( 1 ; 20 ; 15 ; 11 ) . Furthermore, there is at least one class of queries, the Loomis-Whitney joins, where our algorithm gives a strict improvement. A fundamental reason for this is that previous algorithms allocate to each heavy tuple a dedicated set of machines, an approach we argue cannot work in general. Second, the load of the PAC algorithm is n/p^{1/\gamma} , where \gamma is the PAC -number. The PAC -number has a complex definition, where given a query Q it is non-trivial to determine what the PAC -number of Q is, and if a candidate PAC -number is known, it is very hard to determine if a better one is possible. Furthermore, a lot of the complexity in the definition of \gamma is inherited into the algorithm. In contrast, our algorithm has the load n/p^{1/\kappa} , where \kappa has a straight-forward hypergraph-theoretic definition and can be computed with a mixed integer-linear-program. Our algorithm is also simpler, removing many of the different cases in the PAC -algorithm. Other Related Work Our algorithm uses partitioning, which is a central building block in worst-case optimal join algorithms in the RAM model ( 18 ; 19 ; 21 ) . The PANDA algorithm uses a fine-grained partitioning where degrees in each partition are uniformized ( 16 ) , similar to our algorithm. An early paper used a partitioning method similar to what we do in this paper ( 14 ) . This work studied distributed joins in a different model than the MPC model, and the load depended on OUT , which can be much more expensive in the worst case. The Yannakakis algorithm ( 22 ) can be applied in the context of the MPC model to compute acyclic queries with load O((IN+OUT)/p) ( 2 ) . This has been improved to O((IN+\sqrt{IN\cdot OUT})/p) ( 13 ) , in work that studied upper and lower bounds on instance and output optimal evaluation. A related line of work generalized the MPC model to optimize query processing with respect to the topology of the compute cluster ( 9 ; 6 ; 10 ; 8 ) . Finally, there has also been progress on implementing ideas from theoretical MPC research into concrete systems ( 7 ; 23 ; 24 ) . Paper Organization The paper is organized as follows. In Section 2 , we give preliminary definitions. In Section 3 , we define the new measure \kappa , the reduced quasi vertex-cover . In Section 4 , we give an upper bound showing how to compute a join query with load \tilde{O}(n/p^{1/\kappa}) . In Section 5 , we discuss lower bounds and tightness of our result, establishing a path for future research to find what the best worst-case optimal load is. 2. Preliminaries A relation R with schema \textsf{vars}(R) is a set of tuples, where each tuple maps each variable in \textsf{vars}(R) to an element of the domain \mathbf{dom} . We will use x,y,z,\dots to denote variables. A natural join query Q can be defined as a set of relations, denoted as \Join_{i}R_{i} . We will use \textsf{vars}(Q) to denote the variables that occur across all relations in Q . The input size of a query is defined as the total number of tuples across all relations. We will assume that Q has no self-joins, i.e., no relations can repeat in the query. This assumption is w.l.o.g. for any upper bound, since we can simply create a copy of the repeated relation. We will also assume w.l.o.g. that no two relations can have the same schema. Hypergraphs and Measures We can now associate with each natural join query Q a hypergraph \mathcal{H}=(V,E) such that V=\textsf{vars}(Q) and E=\{\textsf{vars}(R)\mid R\in Q\} . For S\subseteq V , we define \mathcal{H}[S] to be the vertex-induced subgraph of \mathcal{H} , i.e., the hypergraph \mathcal{H}^{\prime} with vertex set S and edge set \{S\cap e\mid e\in E,e\cap S\neq\emptyset\} . Definition 2.1 (Reduced Hypergraph). Let \mathcal{H} be a hypergraph. The reduced hypergraph, denoted \textsf{red}(\mathcal{H}) , is a hypergraph (V,E^{\prime}) , where E^{\prime}\subseteq E is a subset obtained by removing any edge e\in E such that there is another e^{\prime}\in E with e\subseteq e^{\prime} . In combinatorics, a clutter or Sperner family is a pair (V,E) , where V is a set and E is a set of subsets of V , such that for no e,e^{\prime}\in E , is e\subseteq e^{\prime} . A reduced query forms a Sperner family. Definition 2.2 (Edge Packing & Covering). Let \mathcal{H}=(V,E) be a hypergraph. Let \mathbf{u} be a (non-negative) weight assignment on the hyperedges E . Then, \mathbf{u} is a: • fractional edge packing (or matching) if for every vertex v\in V , \sum_{v\in e}u_{e}\leq 1 . The total weight of the maximum fractional edge packing is denoted by \tau^{*}(\mathcal{H}) . • fractional edge covering if for every vertex v\in V , \sum_{v\in e}u_{e}\geq 1 . The total weight of the maximum fractional edge covering is denoted by \rho^{*}(\mathcal{H}) . In general, there is no relationship between the two quantities. We will also be interested in fractional vertex covers of a hypergraph \mathcal{H} : these are weight assignments \mathbf{v} on the vertices V such that for every hyperedge e\in E , \sum_{v\in e}\mathbf{v}_{v}\geq 1 . By the duality principle in linear programming, the total weight of the minimum fractional vertex cover is equal to \tau^{*}(\mathcal{H}) . The MPC Model The MPC model, or Massively Parallel Computation model , is a theoretical model to analyze the cost of distributed algorithms. It uses a cluster of p machines, and the input, whose size is n , is initially partitioned across the machines, with each machine storing n/p data in local memory. The computation is synchronous and proceeds in r rounds, where each round consists of message passing between the machines, and computation on data in local memory. By the end of the algorithm, we require that union of the output across each machine forms the desired output. The cost of an algorithm is modeled as the number of rounds r and the maximum data size L that any machine receives in any round. An ideal MPC algorithm works in a constant number of rounds and achieves linear load, i.e., L=O(n/p) . We are interested in using the MPC model to analyze join processing, and in particular we focus in the regime where the number of rounds r is constant in n and p , but may depend on the query. We will also work in the regime where n\gg p , i.e., the data size is much bigger than the number of processors (we will specify the exact requirement in each theorem statement). Given a hypergraph \mathcal{H} , our main question is: what is the smallest exponent \epsilon(\mathcal{H}) such that for every natural join query Q with hypergraph \mathcal{H} and input size at most n , we can compute its output in constant rounds and load O(n/p^{\epsilon(\mathcal{H})}) ? This is what we call a worst-case optimal setting, since the goal is to match the cost of the worst-behaved instance with size \leq n . 3. A New Hypergraph Measure for MPC In this section, we define our new measure of the hypergraph of a join query. Definition 3.1. Let \mathcal{H}=(V,E) be a hypergraph. The reduced quasi vertex-cover is defined as \kappa(\mathcal{H}):=\max_{S\subseteq V}\tau^{*}(\textsf{red}(\mathcal{H}[S])). In other words, to compute \kappa we need to find the largest \tau^{*} of any vertex-induced sub-hypergraph, after we reduce it. The last part is critical to the definition of \kappa , since otherwise we would obtain \psi^{*}(\mathcal{H})=\max_{S\subseteq V}\tau^{*}(\mathcal{H}[S]) , the quasi-edge packing of \mathcal{H} . In Appendix A , we show how \kappa(\mathcal{H}) can be calculated by expressing it as the objective of a mixed integer linear program. Example 0. Consider the hypergraph \mathcal{H}_{1} with hyperedges \{\{x,y\},\{y,z\}\} . Then, \tau^{*}(\mathcal{H}_{1})=1 , but \tau^{*}(\mathcal{H}_{1}[\{x,z\}])=2 . Hence, \kappa(\mathcal{H}_{1})=2 . Example 0. Consider the hypergraph \mathcal{H}_{3}^{\dagger} with the following hyperedges: \{\{x_{1},x_{2},x_{3},z\},\{y_{1},y_{2},y_{3},z\},\{x_{1},y_{1},z\},\{x_{2},y_{2},z\},\{x_{3},y_{3},z\}\} x_{1} x_{2} x_{3} y_{1} y_{2} y_{3} z Figure 1 . Visualization of the Hypergraph \mathcal{H}_{3}^{\dagger} Here, \kappa(\mathcal{H}_{3}^{\dagger})=3 , which is achieved by the subset of variables S=\{x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\} , since \mathcal{H}_{3}^{\dagger}[S] is precisely the boat query ( 11 ) with \tau^{*}=3 . Example 0. Finally, consider the hypergraph K_{k} corresponding to the k -clique query. In this case, \kappa(K_{k})=k/2 . It is useful to compare this to \psi^{*}(K_{k})=k-1 . Whenever it is clear from the context, we will use \kappa instead of \kappa(\mathcal{H}) . Lemma 3.5. Let \mathcal{H}=(V,E) be a hypergraph with connected components \mathcal{H}_{1}=(V_{1},E_{1}),\dots,\mathcal{H}_{t}=(V_{t},E_{t}) . Then, \kappa(\mathcal{H})=\sum_{i=1}^{t}\kappa(\mathcal{H}_{i}) . Proof. Let S_{1}\subseteq V_{1},\dots,S_{t}\subseteq V_{t} be the sets that maximize \tau^{*}(\textsf{red}(\mathcal{H}_{1}[S_{1}])),\dots,\tau^{*}(\textsf{red}(\mathcal{H}_{t}[S_{t}])) respectively. We claim that the S\subseteq V that maximizes \tau^{*}(\textsf{red}(\mathcal{H}[S])) is S=S_{1}\cup\dots\cup S_{t} . Indeed, if there exists another S^{\prime}\neq S where \tau^{*}(\textsf{red}(\mathcal{H}[S^{\prime}]))>\tau^{*}(\textsf{red}(\mathcal{H}[S])) , there there has to exist some i\in\{1,\dots,t\} such that S_{i} does not maximize \tau^{*}(\textsf{red}(\mathcal{H}_{I}[S_{i}])) . ∎ We next connect the newly defined measure to existing hypergraph quantities. Lemma 3.6. For any hypergraph \mathcal{H}=(V,E) : (1) \kappa(\mathcal{H})\geq\tau^{*}(\textsf{red}(\mathcal{H})); (2) \kappa(\mathcal{H})\geq\rho^{*}(\textsf{red}(\mathcal{H}))=\rho^{*}(\mathcal{H}); (3) \kappa(\mathcal{H})\leq\psi^{*}(\mathcal{H}). Next, we give some Lemmas that allow us to compare \kappa to quantities used to characterize the load of algorithms from previous work. This helps us establish that the load n/p^{\kappa(\mathcal{H})} is at least as good as previous work. Lemma 3.7. For any acyclic hypergraph \mathcal{H} , \kappa(\mathcal{H})=\rho^{*}(\mathcal{H}) . Lemma 3.8. For any hypergraph \mathcal{H} , where \alpha is the maximum arity among hyperedges, \rho^{*}(\mathcal{H})\leq\kappa(\mathcal{H})\leq\frac{\alpha}{2}\rho^{*}(\mathcal{H}) . The above implies that a hypergraph \mathcal{H} with binary relations has \kappa(\mathcal{H})=\rho^{*}(\mathcal{H}) . Additionally, for all hypergraphs, \kappa\leq\frac{\alpha\phi}{2} , where \phi is the generalized fractional vertex packing from previous work ( 20 ) , since \phi\geq\rho . We can also compare \kappa to the quantity PAC ( 1 ) . The proof of this lemma is given in Appendix E . Lemma 3.9. For any hypergraph \mathcal{H} , \kappa(\mathcal{H})\leq\textsf{PAC}(\mathcal{H}) In Appendix B , we discuss a case when \kappa is strictly lower than PAC . Finally, we consider whether \kappa is equal to the maximum of \rho^{*}(\mathcal{H}),\tau^{*}(\mathcal{H}) . We answer this in the negative with the following family of counterexamples. For any integer k>0 , consider the hypergraph \mathcal{H}_{k}^{\dagger} with vertex set \{x_{1},\dots,x_{k},y_{1},\dots,y_{k},z\} and the following set of hyperedges: \{\{x_{1},x_{2},\dots,x_{k},z\},\{y_{1},y_{2},\dots,y_{k},z\},\{x_{1},y_{1},z\},\{x_{2},y_{2},z\},\dots,\{x_{k},y_{k},z\}\} \mathcal{H}_{k}^{\dagger} is the the generalized boat join ( 11 ) where we have added a variable z to every hyperedge. \mathcal{H}_{3}^{\dagger} is visualized in Example 3.3 . Proposition 3.10. For the hypergraph \mathcal{H}_{k}^{\dagger} , k>0 , we have: (1) \rho^{*}(\mathcal{H}_{k}^{\dagger})=2; (2) \tau^{*}(\mathcal{H}_{k}^{\dagger})=1; (3) \kappa(\mathcal{H}_{k}^{\dagger})=k. Hence, there exists a family of hypergraphs where \kappa grows asymptotically larger w.r.t. \max\{\rho^{*},\tau^{*}\} . 4. Upper Bound In this section, we present a new MPC algorithm that achieves a \tilde{O}(n/p^{1/\kappa}) load. 4.1. A Partitioning Step Let R be a relational instance with schema \textsf{vars}(R) . Let X,Y\subseteq\textsf{vars}(R) be two subsets of variables. Let \mathbf{y} be a tuple over Y . Define \deg_{R}(X\mid Y=\mathbf{y}):=|\pi_{X}(\sigma_{Y=\mathbf{y}}R)|. Furthermore, define \deg_{R}(X\mid Y):=\max_{\mathbf{y}}\deg_{R}(X|Y=\mathbf{y}) . For convenience, we will sometimes use the shorthand notation \deg_{R}(X)=\deg_{R}(\textsf{vars}(R)\mid X) . Next, we define a type of constraint. This constraint is similar to the property we get in a uniformized instance, where we would replace the inequalities below with equalities. Definition 4.1. A constraint set for a relation R is a total function \sigma:\mathcal{P}(\textsf{vars}(R))\rightarrow\mathbb{R}^{\geq 0} . Definition 4.2. We say that a relational instance R satisfies a constraint set \sigma if for every pair of subsets X\subseteq Y\subseteq\textsf{vars}(R) it holds: \deg_{R}(Y\mid X)\leq 2\frac{\sigma(X)}{\sigma(Y)}. Below we see a partitioning method for a relation R . Let \mathcal{S}\subseteq\mathcal{P}(\textsf{vars}(R)) be an ordered set of subsets that is sorted in increasing order of cardinality. Algorithm 1 Partitioning Procedure 1: function Partition ( R:\text{relational instance},\mathcal{S}:\text{remaining sets }\subseteq\mathcal{P}(\textsf{vars}(R)) ) 2: if \mathcal{S}=\emptyset then return R 3: U\leftarrow\text{first item in }\mathcal{S} 4: \forall i\in[\log n]:R^{i}\leftarrow\sigma_{U\in\{u|\deg_{R}(U=u)\in[2^{i-1},2^{i}]\}}R 5: return \bigcup_{i\in[\log n]}\textsc{Partition}(R^{i},\mathcal{S}-\{U\}) In the above, some partitions may be empty, if the constraints are picked in an incompatible way. Such partitions can be disregarded. Lemma 4.3. Let \mathcal{R} be the output of Algorithm 1 when it runs with input a relation R of size n and \mathcal{S}=\mathcal{P}(\textsf{vars}(R)) . Then, (1) |\mathcal{R}|\leq\log^{|\mathcal{P}(\textsf{vars}(R))|}n ; (2) every instance T\in\mathcal{R} satisfies a constraint set \sigma_{T} with \sigma_{T}(\emptyset)=n and \sigma_{T}(\textsf{vars}(R))=1 . Proof. We show both items of this lemma in sequence. 1) In each step, we create at most \log n subinstances, and the algorithm runs recursively for at most |\mathcal{P}(\textsf{vars}(R))| steps. 2) We will construct the constraint set for any subinstance following the recursive process. Consider the step where the algorithm partitions on some set U\subseteq\textsf{vars}(R) : then, for the subinstance R^{i} , we will pick \sigma(U)=2^{i} . Observe that during the first step, when U=\emptyset , all tuples fall in the subinstance with the largest value, hence \sigma(\emptyset)=n . During the last step, when U=\textsf{vars}(R) , all degrees are 1 and hence every subinstance will set \sigma(\textsf{vars}(R))=1 . It remains to show that the desired inequality holds for any subinstance T\in\mathcal{R} and every X\subseteq Y\subseteq\textsf{vars}(R) . Indeed, consider the step of the algorithm just after R was partitioned on Y . Let \mathbf{x} be any tuple over X . For any tuple \mathbf{y} over Y where \pi_{X}(\mathbf{y})=\mathbf{x} , since we just partitioned using Y , \deg_{R}(\textsf{vars}(R)\mid Y=\mathbf{y})\geq\sigma(Y)/2 . Thus, we can write: \deg_{R}(\textsf{vars}(R)\mid X=\mathbf{x})=\sum_{\mathbf{y}\in Y|\pi_{X}(\mathbf{y})=\mathbf{x}}\deg_{R}(\textsf{vars}(R)\mid Y=\mathbf{y})\geq\frac{\sigma_{R}(Y)}{2}\cdot\deg_{R}(Y\mid X=\mathbf{x}). We now claim that \deg_{R}(\textsf{vars}(R)\mid X=\mathbf{x})\leq\sigma_{R}(X) . This holds since the inequality \deg_{R}(\textsf{vars}(R)\mid X=\mathbf{x})\leq\sigma_{R}(X) holds right after we partitioned on X , and when we repartition the degree can only grow smaller. Reorganizing we obtain: \deg_{R}(Y\mid X=\mathbf{x})\leq 2\frac{\sigma_{R}(X)}{\sigma_{R}(Y)}. Finally, observe that this inequality will hold after Algorithm 1 has completed, since the degree can only become smaller by removing tuples during repartitioning. ∎ Suppose we are given a query Q . Let \Sigma=\{\sigma_{R}\}_{R\in Q} be a set of constraint sets, one for each relation R in the query. We will say that Q is \Sigma -uniformized if every relation R in Q satisfies the constraint set \sigma_{R}\in\Sigma . Lemma 4.3 tells us that for any input instance, we can create polylogarithmically many subinstances such that each one is \Sigma -uniformized for some chosen \Sigma . Thus, from here on we will focus on a \Sigma -uniformized query Q . Partitioning in the MPC model We finally describe how to perform Algorithm 1 in the MPC model. We will do this with a number of rounds which is constant in n and p , and load O(n/p) . We will use the well known primitive sum-by-key to do this, which is described in previous work ( 12 ) . Proposition 4.4. Let R be a relation with n tuples stored on p machines, where each tuple t is associated with a key \textsf{key}(t) . sum-by-key computes, for each key \bar{k} , the total number \textsf{count}(\bar{k}) of tuples t where \textsf{key}(t)=\bar{k} . Afterwards, if a machine stores tuple t , it also knows \textsf{count}(\textsf{key}(t)) . sum-by-key can be implemented in O(1) rounds with load n/p , assuming n>p^{1+\epsilon} for some small constant \epsilon>0 . We can now perform each step in Algorithm 1 by performing sum-by-key , where for a subset U of the variables, the key of a tuple t is \pi_{U}t . When the machines have \textsf{count}(\textsf{key}(t)) for each tuple t they store, they can locally decide which partition t fits in. 4.2. Vertex Weight Mappings We define a vertex weight mapping of a query Q with hypergraph \mathcal{H}=(V,E) to be a function v:V\rightarrow\mathbb{R}_{\geq 0} . Definition 4.5. Let \mathbf{v} be a vertex weight mapping of a \Sigma -uniformized query Q with hypergraph \mathcal{H} . For a relation R in Q of size n and U\subseteq\textsf{vars}(R) , we say that U is: • light in R if \sigma_{R}(U)<\frac{n}{p^{\sum_{i\in U}v_{i}}} ; • heavy in R if \sigma_{R}(U)\geq\frac{n}{p^{\sum_{i\in U}v_{i}}} ; • consistent in R if \sigma_{R}(U)\leq\frac{n}{p^{\sum_{i\in U}v_{i}}} . Notice that the difference between light and consistent is merely strictness of the inequality. We can also view consistent as being light or heavy with equality. This will be useful later on. The above definition and Lemma 4.3 tells us that for a light U in R , the degree of U in R is bounded as \deg_{R}(U)\leq 2\sigma_{R}(U)<{n}/{p^{\sum_{i\in U}v_{i}}} . In addition, for any relation R , the empty set is always heavy but consistent, and \textsf{vars}(R) is always light. For readers familiar with previous work, we note that we will often normalize our vertex weight mappings for convenience. This means we will often have terms on the form n/p^{v_{x}} , instead of n/p^{v_{x}/\sum_{x}v_{x}} as in some previous work. Definition 4.6 (Consistent Vertex Weight Mapping). Let Q be a \Sigma -uniformized query, and \mathbf{v} be a vertex weight mapping of Q . We say that \mathbf{v} is consistent with Q if for every R\in Q and every U\subseteq\textsf{vars}(R) , U is consistent in R . Our goal is to use HyperCube with shares picked using a consistent weight mapping, because then there are no values that can individually break the load requirement. Consistency means that the allocated shares are not too big - as shares increase, the heavy thresholds decrease. This means there is some point when the shares can become too big. Later, we will also need that the shares are not too small, so the load is not too high. Definition 4.7 (Heavy Sets). Let Q be a \Sigma -uniformized query, and \mathbf{v} be a vertex weight mapping of Q . We denote by \mathcal{U}[{\mathbf{v}}]=\{(U,R)\mid U\subseteq\textsf{vars}(R)\text{ and }U\text{ is heavy in }R\} the collection of all heavy sets in Q , and by H[\mathbf{v}]=\bigcup_{(U,R)\in\mathcal{U}[{\mathbf{v}}]}U the set of all variables that occur in some heavy set. Constructing Good Vertex Weight Mappings In this part, we will show a simple procedure that picks a suitable vertex weight mapping for our algorithm. We introduce the following notation: for any U\subseteq V , let \mathbf{v}^{*}_{U} be a minimum vertex cover of \textsf{red}(\mathcal{H}[U]) . Definition 4.8. Consider the vector space \Psi=\mathbb{R}^{|\mathcal{P}(V)|} . Let \mathbf{V}:\Psi\rightarrow\mathbb{R}^{|V|} be the function that maps (\psi_{U})_{U\in\mathcal{P}(V)}\in\Psi to \sum_{U\in\mathcal{P}(V)}\psi_{U}\mathbf{v}^{*}_{U} . For some \psi=(\psi_{U})_{U\in\mathcal{P}(V)}\in\Psi , we denote by |\psi|_{1}=\sum_{U\in\mathcal{P}(V)}\psi_{U} , in the standard way. We are interested in finding vectors \psi\in\Psi where |\psi|_{1}\leq 1 and \psi_{U}\geq 0 for all U . Each such vector can be thought of as describing a way to pick shares for a HyperCube partitioning with at most p machines, by assigning to variable x a share p^{\mathbf{V}_{x}(\psi)/\Delta} , for some parameter \Delta\geq|\mathbf{V}(\psi)|_{1} . In other words, we pick share exponents as linear combinations of minimum vertex covers, and \psi is the coefficient vector descibing the linear combination. The following algorithm describes how we pick the linear combination \psi\in\Psi . Algorithm 2 Procedure to Construct \psi 1: function Construct ( Q:\Sigma\text{-uniformized instance},\Delta\in\mathbb{R}_{\geq 0} ) 2: \psi\leftarrow\mathbf{0} 3: while |\psi|_{1}<1 and H[\mathbf{V}(\psi)/\Delta]\neq V do 4: {L}\leftarrow V\setminus{H}[\mathbf{V}(\psi)/\Delta] 5: \psi_{L}\leftarrow\max_{\delta\in(0,1-|\psi|_{1}]}\delta such that Q is consistent with (\mathbf{V}(\psi)+\delta\cdot\mathbf{v}^{*}_{L})/\Delta 6: return \psi Example 0. Consider the triangle query, whose hypergraph \mathcal{H}_{\Delta} has hyperedges R=\{X,Y\},S=\{Y,Z\},T=\{Z,X\} . Consider a fixed \Sigma -uniformized instance where X has p^{1/6} different values, and Y and Z each have n/p^{1/6} values. R and T are product instances, and S has n tuples, where the degrees at both Y and Z are at most n/p . We visualize the instance below. R S T X \vdots p^{1/6} Y \vdots n/p^{1/6} Z \vdots n/p^{1/6} Figure 2 . Visualization of the instance Let \Delta=3/2 . Algorithm 2 will do the following: In the first iteration, we use the vertex cover \mathbf{v}_{XYZ}=(0.5,0.5,0.5) , and \psi_{XYZ}=1/2 . This gives \deg_{R}(\textsf{vars}(R)|X)=n/p^{1/6}=n/p^{(\mathbf{v}^{*}_{XYZ})_{X}\psi_{XYZ}/\Delta} , meaning \{X\} is heavy but consistent in both R and T . In the second iteration, we use the vertex cover \mathbf{v}^{*}_{YZ}=(0,0.5,0.5) , with \psi_{YZ}=1/2 . In total, we get the vertex weight mapping given by the following linear combination \mathbf{V}(\psi)=\frac{1}{2}(0.5,0.5,0.5)+\frac{1}{2}(0,0.5,0.5)=(0.25,0.5,0.5). We first show that the Algorithm 2 will always terminate and return some vector \psi . Lemma 4.10. Algorithm 2 always terminates. Proof. We claim that as long as |\psi|_{1}<1 , at each iteration the set of heavy variables H[\mathbf{V}(\psi)] increases by at least one variable. Indeed, if this was not true, it would be possible to pick a larger value of \delta . Therefore, the maximum number of iterations is |V| . ∎ Lemma 4.11. Let Q be a \Sigma -uniformized query with hypergraph \mathcal{H}=(V,E) . Let \psi be the vector returned from Algorithm 2 . Then, (1) |\psi|_{1}\leq 1 ; (2) the vertex weight mapping \mathbf{V}(\psi)/\Delta is consistent with Q ; (3) |\mathbf{V}(\psi)|_{1}\leq\kappa(\mathcal{H}) . Proof. We separately prove the items in the lemma. (1) This follows directly from the termination condition of the while loop. (2) We inductively argue that before and after each iteration, \mathbf{V}(\psi)/\Delta is consistent w.r.t. Q . Before the first iteration, this is true because \mathbf{V}(\psi)=\mathbf{0} , so for every U,R , we have \sigma_{R}(U)\leq n/p^{0}=n , which always holds. Next, consider any iteration of the loop. Note that we always can pick a non-zero \delta>0 , since for every subset U that includes some variable outside of H[\mathbf{V}(\psi)/\Delta] , \sigma_{R}(U)\Delta . By picking \Delta=\kappa , we achieve the best worst-case bound. Another, more fine-grained method, would be to minimize \Delta by doing binary search, finding the \Delta such that |\mathbf{V}(\psi)|_{1}=\Delta . This way, some instances, or partitions within instances, may obtain a better load than n/p^{1/\kappa} . We will denote by \mathbf{v}=\mathbf{V}(\psi)/\Delta , where v_{i}=\mathbf{V}_{i}(\psi)/\Delta . 4.3. One Key Lemma Let us fix a \Sigma -uniformized query Q with constraint sets \Sigma=\{\sigma_{R}\}_{R} , and a consistent weight mapping \mathbf{v} as chosen by the algorithm above. We define the heavy relation : R_{H}=\Join_{(U,R)\in\mathcal{U}}\pi_{U}(R). The heavy relation R_{H} has variables H[\mathbf{v}] . The next important lemma shows that R_{H} also behaves in a (somewhat) uniformized way. Lemma 4.13. For any X\subseteq H , we have \deg_{R_{H}}(H\mid X)\leq 2^{|H|}p^{\sum_{i\in H-X}v_{i}} . Proof. Consider any ordering (U_{1},R_{1}),\dots,(U_{k},R_{k}) of the elements in the set \mathcal{U} . Let H_{0}=\emptyset , and H_{j}=\bigcup_{i=1}^{j}U_{i} for j=1,\dots,k . Note that H_{k}=H . We will inductively show that for every j=0,\dots,k , we have \deg_{R_{H}}(H_{j}\cup X\mid X)\leq 2^{j}p^{\sum_{i\in H_{j}-X}v_{i}} . In the base case j=0 , the statement is true since \deg_{R_{H}}(X\mid X)=1 . For the inductive case j\geq 1 , \displaystyle\deg_{R_{H}}(H_{j}\cup X|X) \displaystyle\leq\deg_{R_{H}}(H_{j-1}\cup X|X)\deg_{R_{j}}(U_{j}|U_{j}\cap(H_{j-1}\cup X)) \displaystyle\leq 2^{j-1}p^{\sum_{i\in H_{j-1}-X}v_{i}}\deg_{R_{j}}(U_{j}|U_{j}\cap(H_{j-1}\cup X)) (Inductive Assumption) \displaystyle\leq 2^{j}p^{\sum_{i\in H_{j-1}-X}v_{i}}\cdot\frac{\sigma_{R_{j}}(U_{j}\cap(H_{j-1}\cup X))}{\sigma_{R_{j}}(U_{j})} (Definition 4.2 ) \displaystyle\leq 2^{j}p^{\sum_{i\in H_{j-1}-X}v_{i}}\frac{n}{p^{\sum_{i\in U_{j}\cap(H_{j-1}\cup X)}v_{i}}}\frac{p^{\sum_{i\in U_{j}}v_{i}}}{n} (Consistency, Definition 4.5 ) \displaystyle=2^{j}p^{\sum_{i\in H_{j}-X}v_{i}} This concludes the proof. ∎ 4.4. The \kappa -Join Algorithm The algorithm has 4 phases. The first phase uses O(1) rounds, the remaing three phases need 4 rounds. We first give some intuition behind the algorithm, and then describe it more precisely. Intuition Because we picked \mathbf{v} as a consistent weight mapping, there are no sets that are heavy with a strict inequality (see Definition 4.5 ). Our main concern is then that there may be relations that are not "covered" by \mathbf{v} , which means that if we apply HyperCube directly, the load will be too high. To solve this problem, for such a relation R that is not "covered", we can create an intermediate relation R^{\dagger} , by effectively joining R with another relation S , which is the guard. This intermediate relation turns out to have a cardinality that grows very little compared to the input size, but it is guaranteed to be "covered". We can therefore directly use HyperCube on all these intermediate relations, which solves the query. From a technical perspective, we do not just join R with its guard S , but instead with the heavy relation R_{H} . In fact, we may not need to use the whole relation R_{H} for all R , but it never hurts to do so. We discuss this further later. 1-Preprocessing Partition the input using Algorithm 1 . The remainder of the algorithm runs in parallel for each \Sigma -uniformized query Q . Use Algorithm 2 with \Delta=\kappa(\mathcal{H}) to find a consistent vertex weight mapping \mathbf{v}=\mathbf{V}(\psi)/\Delta . 2-Broadcasting Heavy Sets For every (U,R)\in\mathcal{U}[{\mathbf{v}}] , broadcast \pi_{U}R to all machines. The heavy relation R_{H}=\Join_{(U,R)\in\mathcal{U}}\pi_{U}(R) can now locally be computed in each machine. 3-Semijoins In parallel, for every relation R\in Q , do the following: • If \textsf{vars}(R)\setminus H[\mathbf{v}]\neq\emptyset , let S be the relation that guards R . Compute the join R^{\dagger}\leftarrow(S\Join R_{H})\lJoin R using p machines • If \textsf{vars}(R)\setminus H[\mathbf{v}]=\emptyset , compute the semijoin R^{\dagger}\leftarrow R_{H}\ltimes R using p machines 4-HyperCube Perform HyperCube partitioning on every intermediate relation R^{\dagger} using the share p^{v_{x}} for variable x . Example 0. We now continue Example 4.9 . The heavy sets are here \mathcal{U}[\mathbf{v}]=\{(\{X\},R),(\{X\},S)\} . Broadcasting Heavy Sets: We broadcast the heavy sets to all machines, after which each machine can compute the heavy relation R_{H} (which only has variable X ). Semijoins: We will compute two intermediate relations, both with variables X,Y,Z . These are (T\bowtie R_{H})\ltimes R , and (T\bowtie R_{H})\ltimes S . The intermediate results are at most np^{1/6} , since there are only p^{1/6} values on X . HyperCube: We finally intersect the two intermediate relations with hypercube partitioning. We notice that the algorithm we get for the triangle query in the example is very similar to the one previously described ( 17 ) . Also, note that the algorithm above only uses p^{1.25/1.5}

0 , with hyperedges: \{\{x_{1},x_{2},\dots,x_{k}\},\{y_{1},y_{2},\dots,y_{k}\},\{x_{1},y_{1}\},\{x_{2},y_{2}\},\dots,\{x_{k},y_{k}\}\}. For this class of hypergraphs, the lower bound shown is \Omega(n/p^{1/k}) . Note that \kappa(\mathcal{H}_{k}^{B})=\psi^{*}(\mathcal{H}_{k}^{B})=\tau^{*}(\mathcal{H}_{k}^{B})=k (but \rho^{*}=2 ), hence the lower bound can be matched even by a 1-round MPC algorithm. We show next how to extend the above lower bound to the family of hypergraphs \mathcal{H}_{k}^{\dagger} . For this, we need the following general observation. Lemma 5.3. Let \mathcal{H}=(V,E) be a hypergraph, and S\subseteq V . If \textsf{red}(\mathcal{H}[S]) admits a lower bound of \Omega(n/p^{\epsilon}) , then \mathcal{H} also admits the same lower bound. Observe that \mathcal{H}_{k}^{B}=\mathcal{H}_{k}^{\dagger}[V\setminus\{z\}] . Thus, the \Omega(n/p^{1/k}) lower bound transfers to \mathcal{H}_{k}^{\dagger} , showing that \kappa -Join is optimal for this family of queries as well. Together with Proposition 3.10 , this proves that the worst-case optimal load for join queries cannot be characterized as n/p^{1/\max\{\tau^{*},\rho^{*}\}} . Candidate Lower Bound We now describe a concrete direction towards constructing a matching lower bound. Recall that \kappa(\mathcal{H})=\max_{S\subseteq V}\tau^{*}(\textsf{red}(\mathcal{H}[S])) . Applying Lemma 5.3 , it would suffice to prove a \Omega(n/p^{1/\tau^{*}}) lower bound for every reduced hypergraph. Conjecture 5.4. Let \mathcal{H} be a hypergraph s.t. \mathcal{H}=\textsf{red}(\mathcal{H}) . Then, there exists a query Q with hypergraph \mathcal{H} and input size n s.t. any tuple-based algorithm needs load \Omega(n/p^{1/\tau^{*}}) to compute Q . Proving this conjecture would immediately give a matching \Omega(n/p^{1/\kappa}) lower bound. We should note here that the requirement that \mathcal{H} is reduced is critical; for instance, the conjecture fails for the non-reduced hypergraph with hyperedges \{x\},\{x,y\},\{y\} , for which there is an MPC algorithm with load \tilde{O}(n/p) . Although we could not prove the conjecture, we describe below a candidate family of hard instances. For a query with (reduced) hypergraph \mathcal{H}=(V,E) , let \mathbf{v} be a minimum fractional vertex cover, which has total weight \tau^{*} . A sparse product query is defined as follows: • For a variable x\in V , define N_{x}=\{1,\dots,n^{v_{x}}\} . • For relation R , include each tuple in the cross product \bigtimes_{x\in\textsf{vars}(R)}N_{x} independently with probability P_{R}=n^{1-\sum_{x\in\textsf{vars}(R)}v_{x}}. We call a relation R where P_{R}<1 as sparse , and if P_{R}=1 as dense . Note that with high probability, every relation has size O(n) . Additionally, the expected output of the query is n^{\tau^{*}}\prod_{R\in Q}P_{R} . Finally, if we consider a machine that receives L tuples at most from each relation, then we show in Appendix F that the expected number of outputs it can produce is L^{\tau^{*}}\prod_{R\in Q}P_{R} . The above in-expectation bounds do not suffice to prove the desired lower bound. Instead, we would want them to hold with enough high probability such that there is a non-zero probability of the existence of an instance of sparse relations such that for every possible combination of L tuples a machine can produce O(L^{\tau^{*}}\prod_{R\in Q}P_{R}) results. We leave that as an open problem, that, if resolved, would prove the desired matching lower bound. Specifically, we present in Appendix C a concrete hypergraph for which we do not know how to prove the desired lower bound using the aforementioned sparse product construction. 6. Conclusion In this paper, we presented a new algorithm, \kappa -Join, for computing join queries in the MPC model with load n/p^{1/\kappa} . The algorithm improves upon previous results and is relatively simple. It remains an open problem whether this upper bound is tight, or if there exists another algorithm that can achieve a better load. Appendix A \kappa as a Mixed Integer Linear Program Consider a hypergraph \mathcal{H}=(V,E) . Consider the mixed integer linear program below, where we have a variable w_{j}\in[0,1] for each R\in E , and a variable t_{x}\in\{0,1\} for each x\in V . The variable t_{x} indicates whether variable x is in the set S , so by setting values of t_{x} , we pick a set S . Here, L is some large number. (1) \displaystyle\max \displaystyle\sum_{R\in E}w_{R} \displaystyle s.t.\quad\forall x\in V: \displaystyle\sum_{R:x\in R}w_{R}\leq t_{x}+(1-t_{x})L \displaystyle\forall R\in E: \displaystyle w_{R}\leq\sum_{x\in R}t_{x} \displaystyle\forall U,V\in E,\forall y\in U-V: \displaystyle w_{V}\leq 1+\sum_{x\in V-U}t_{x}-t_{y} \displaystyle\forall x\in V,t_{x}\in\{0,1\}. \displaystyle\forall U\in E,w_{U}\in[0,1]. Lemma A.1. Consider a hypergraph \mathcal{H}=(V,E) , and let S be the variables where t_{x}=1 in ( 1 ). Then the optimal objective to ( 1 ) is \tau^{*}(\textsf{red}(\mathcal{H}[S])) . Proof. The first constraint is the usual edge packing constraint on only the variables that are in S . The second constraint describes that only hyperedges with at least one variable in S can have a non-zero weight. It remains to show that hyperedges that contain a variable in S , but that are removed by the reduce operation, never have any weight, by the third constraint. Suppose that V is a hyperedge that is removed because it is contained in U . If \pi_{S}U=\pi_{S}V , both U and V are kept in the program, which is correct. We focus on the case when U-V\neq\emptyset . In this case, there exists a constraint w_{V}\leq 0 among the third type of constraints. This is because \sum_{x\in V-U}t_{x}=0 since V is reduced into U , and there exists some y\in U-V where y\in S , meaning t_{y}=1 , causing the RHS to be 0 . If V is not reduced into U , then RHS of the third constraint is always at least 1 , since \sum_{x\in V-U}t_{x}\geq 1 . ∎ Theorem A.2. Consider a hypergraph \mathcal{H}=(V,E) . Then, the optimal objective of ( 1 ) w.r.t. \mathcal{H} is \kappa(\mathcal{H}) . Proof. This follows from that ( 1 ) maximizes over all choices on variables t_{x} , x\in V , and applying Lemma A.1 . ∎ Appendix B Allocating Dedicated Machines We here argue that for the Loomis-Whitney query, the approach of directly allocating to each heavy tuple a dedicated set of machines will have a too high load, meaning this approach does not work on this query. Consider the loomis-whitney join, which has as hypergraph \mathcal{H}_{LW} with the following hyperedges S_{1}=\{x,y,z\},S_{2}=\{x,y,w\},S_{3}=\{x,z,w\},S_{4}=\{y,z,w\}. We have the following quantities. Here, the last quantity is the characterization of the load in ( 20 ) , where \alpha is the maximum arity and \phi is the generalized vertex packing. • \rho^{*}(\mathcal{H}_{LW})=4/3 • \tau^{*}(\mathcal{H}_{LW})=4/3 • \psi^{*}(\mathcal{H}_{LW})=2 • \kappa(\mathcal{H}_{LW})=4/3 • \frac{\alpha\phi}{2}=\frac{3\cdot\frac{4}{3}}{2}=2 Instance Consider the following \Sigma -uniformized instance. Let S_{3} (and S_{4} ) be product relations where |\pi_{zw}S_{3}|=|\pi_{zw}S_{4}|=n/p^{1/5} , and |\pi_{x}S_{3}|=|\pi_{y}S_{4}|=p^{1/5} . Let S_{1} (and S_{2} ) be product relations where |\pi_{xy}S_{1}|=|\pi_{xy}S_{2}|=p^{2/5} , and |\pi_{z}S_{1}|=|\pi_{w}S_{2}|=n/p^{2/5} . We cannot solve this with HyperCube in one round, because if we use the vertex cover \left(\frac{1}{3},\frac{1}{3},\frac{1}{3},\frac{1}{3}\right) , \deg_{S_{3}}(x)=n/p^{1/5}>n/p^{(1/3)/(4/3)}=n/p^{1/4} . Dedicated machines Consider an approach that allocates dedicated machines to each heavy tuple. There are p^{2/5} heavy tuples, so some heavy tuple will get at most p^{3/5} machines. This means that for this group to compute the semijoin S_{i}\ltimes t requires load n/p^{3/5} . We fail to match \kappa . Intuitively, the problem is that a relation of size n is too big to be received by a dedicated group. The groups need to "collaborate" in partitioning any input relation. \kappa -Join We can compute this query on this \Sigma -uniformized instance with load n/p^{4/5} by using the following weight mapping \mathbf{v}=\left(\frac{2}{8},\frac{2}{8},\frac{3}{8},\frac{3}{8}\right)=\frac{3}{4}\left(\frac{1}{3},\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)+\frac{1}{4}\left(0,0,\frac{1}{2},\frac{1}{2}\right) We can see that S_{3} (and S_{4} ) are covered by this weight mapping, and even x (or y ) is light in these relations (both the degree and the threshold is n/p^{1/5} ) so we could partition with HyperCube. For S_{1} (and S_{2} ), we cannot do this, since they are not self-guarded. If we instead perform a join (S_{3}\bowtie R_{H})\ltimes S_{1} (and (S_{4}\bowtie R_{H})\ltimes S_{2} ) the output size is at most np^{1/5} . These intermediates can then be repartitioned using HyperCube with load np^{1/5}/p=n/p^{4/5} . Appendix C A Query Demonstrating a \kappa-\rho^{*} Gap Without a Matching Lower Bound Figure 4 presents an example query Q^{\flat} that exhibits a gap between \kappa and \rho^{*} , yet for which we are unable to establish an \Omega(n/p^{1/\kappa}) load lower bound. The query Q^{\flat}=(V,E) contains 12 variables, where V=\{A,B,C,D,E,F\}\cup\{D_{i},E_{i},F_{i}\mid i\in\{1,2\}\} and E=\{\{A,B,C\},\{D,E,F\},\{D,D_{1}\},\{D,D_{2}\},\{D_{1},D_{2}\},\{E,E_{1}\},\{E,E_{2}\},\{E_{1},E_{2}\},\{F,F_{1}\},\{F,F_{2}\},\{F_{1},F_{2}\}\}. We have \kappa(Q^{\flat})=6 , achieved by assigning weight \tfrac{1}{2} to each vertex, and \rho^{*}(Q^{\flat})=5 , achieved by assigning weight 1 to \{A,B,C\} , \{D,E,F\} , \{D_{1},D_{2}\} , \{E_{1},E_{2}\} , and \{F_{1},F_{2}\} . A B C D E F D_{1} D_{2} E_{1} E_{2} F_{1} F_{2} Figure 4. Visualization of Q^{\flat} Appendix D Missing Proofs D.1. Section 3 See 3.6 Proof. From Lemma 3.5 , we can assume w.l.o.g. that \mathcal{H} is connected. 1) This is trivial, since we can pick S=V in the definition of \kappa . 2) First we show that \rho^{*}(\textsf{red}(\mathcal{H}))=\rho^{*}(\mathcal{H}) . Indeed, given a fractional edge cover of \textsf{red}(\mathcal{H}) , we can obtain one for \mathcal{H} with the same weight by assigning 0 weight to the hyperedges removed. For the opposite direction, suppose we have a fractional edge cover \mathbf{u} of \mathcal{H} . For every edge e^{\prime} removed to form \textsf{red}(\mathcal{H}) , let f(e^{\prime}) an edge in \textsf{red}(\mathcal{H}) such that e^{\prime}\subseteq f(e^{\prime}) . We now create an edge cover for \textsf{red}(\mathcal{H}) by assigning to e weight u_{e}+\sum_{e^{\prime}:f(e^{\prime})=e}u_{e^{\prime}} . The total weight remains the same, since the weight of every removed edge is assigned to one edge. It is also an edge cover for \textsf{red}(\mathcal{H}) , since the weight of a removed edge is assigned to an edge that covers at least the same vertices. For a fractional edge cover \mathbf{u}=(u_{j})_{j} of \mathcal{H}=(V,E) , let S_{\mathbf{u}}=\{v\in V\mid\sum_{v\in e}u_{e}=1\} , i.e. the vertices with a tight constraint in the edge cover. Let \mathbf{w} be an optimal fractional edge cover of \mathcal{H} such that S_{\mathbf{w}} is a minimal set (i.e., there is no other optimal fractional edge cover with a strictly smaller number of tight vertices). We will show that \tau^{*}(\textsf{red}(\mathcal{H}[S_{\mathbf{w}}]))\geq\rho^{*}(\mathcal{H}) . This proves the required statement. To show this, consider an edge e that is removed to form \textsf{red}(\mathcal{H}[S_{\mathbf{w}}]) s.t. e\cap S_{\mathbf{w}}=\emptyset . This means that for every v\in e , we have that \sum_{v\in e^{\prime}}w_{e^{\prime}}>1 . If w_{e}>0 , then it would be possible to construct an edge cover \mathbf{w}^{\prime} of smaller weight by reducing {w}_{e} by some \epsilon>0 , a contradiction to the optimality of \mathbf{w} . Hence, any such edge has weight 0. We will construct an edge packing \mathbf{c} for \textsf{red}(\mathcal{H}[S_{\mathbf{w}}]) by assigning to edge e weight c_{e}=w_{e}+\sum_{e^{\prime}:f(e^{\prime})=e}w_{e^{\prime}} . As before, the total weight remains the same. Hence, it suffices to show that it is indeed an edge packing for \textsf{red}(\mathcal{H}[S_{\mathbf{w}}]) . Suppose not; then, there is a vertex v that was tight under \mathbf{w} but \sum_{v\in e}c_{e}>1 . This means that there is an edge e with w_{e}>0 such that it absorbed by at least another edge e^{\prime} with v\in e^{\prime} with weight w_{e^{\prime}}>0 . Moreover, from our above observation and because w_{e}>0 , e must contain at least one tight vertex v^{\prime} that also belongs in e^{\prime} . Now, we can transfer a small \epsilon>0 from w_{e^{\prime}} to w_{e} ; but this means that we will get an edge cover where v becomes non-tight, a contradiction to the minimality of \mathbf{w} . 3) Recall that \kappa(\mathcal{H}):=\max_{S\subseteq V}\tau^{*}(\textsf{red}(\mathcal{H}[S])) , and \psi^{*}(\mathcal{H}):=\max_{S\subseteq V}\tau^{*}(\mathcal{H}[S]) . It suffices to show that for every S\subseteq V , \tau^{*}(\mathcal{H}[S])\geq\tau^{*}(\textsf{red}(\mathcal{H}[S])) . This is true, since viewing these two as linear programs with minimization objectives, moving from \mathcal{H}[S] to \textsf{red}(\mathcal{H}[S]) removes constraints, which can only lower the value of the objective function. ∎ See 3.7 Proof. Assume w.l.o.g. that \mathcal{H} is reduced. We need to show that for every U\subseteq V , we have \tau^{*}(\textsf{red}(\mathcal{H}[U]))\leq\rho^{*}(\mathcal{H}) . We will use the notion of a canonical edge cover from ( 11 ) , which is integral. For this, take a join tree T of \mathcal{H} (such a tree exists because \mathcal{H} is acyclic) and root it at some node. We will say that a variable is disappearing at a node v of T if it does not appear in any node above v . We can now define the canonical cover as follows: visit the nodes of T in some bottom-up order. Start with \mathcal{F}=\emptyset . Whenever we visit a node v of T that contains a disappearing variable not in the current \mathcal{F} , add v to \mathcal{F} . The resulting set \mathcal{F} can be shown to be an edge cover ( 11 ) , and its value will be equal to \rho^{*}(\mathcal{H}) . We will now construct a vertex cover for \textsf{red}(\mathcal{H}[U]) from \mathcal{F} that has total weight \leq|\mathcal{F}| . We do this as follows. For every node v\in\mathcal{F} of the join tree, assign a weight of 1 to the variable in \chi(v)\cap U that disappears as high as possible in the rooted join tree; for the remaining variables, assign a weight of 0. It is easy to see that the total weight we have is at most |\mathcal{F}| . It remains to show that every edge in \textsf{red}(\mathcal{H}[U]) is covered. Indeed, consider any node v in the tree that remains in \textsf{red}(\mathcal{H}[U]) . If v\in\mathcal{F} , we are done, since we will pick one of the variables in \chi(v)\cap U to have weight 1. If v\notin\mathcal{F} , note that there must be a variable x\in\chi(v)\cap U that is disappearing at v ; otherwise, every variable in \chi(v)\cap U would appear also in its parent, which would mean that v would not occur in the reduced hypergraph \textsf{red}(\mathcal{H}[U]) . Since v\notin\mathcal{F} , this means that x must occur in some node u in \mathcal{F} that is below v . Now, for u we chose to put weight of 1 in some variable y that disappears at least as high as x ; this means that y must also appear in v , thus v is covered. ∎ See 3.8 Proof. The first inequality follows from a previous lemma. It remains to show \kappa\leq\frac{\alpha}{2}\rho(\mathcal{H}) . Equivalently, we show that for every S\subseteq V , \tau^{*}(\textsf{red}(\mathcal{H}[S]))\leq\frac{\alpha}{2}\rho^{*}(\mathcal{H}) . Here, in turn, it suffices to prove that there exists a fractional vertex cover \hat{\tau} over \textsf{red}(\mathcal{H}[S]) and a fractional vertex packing \hat{\rho} over \mathcal{H} such that \hat{\tau}\leq\frac{\alpha}{2}\hat{\rho} , since then \tau^{*}(\textsf{red}(\mathcal{H}[S]))\leq\hat{\tau}\leq\frac{\alpha}{2}\hat{\rho}\leq\frac{\alpha}{2}\rho^{*}(\mathcal{H}) Here, the first and last inequalities hold since \hat{\tau} (and \hat{\rho} ) can only be bigger (resp. smaller) than the optimal values. We say that a vertex v in the query \textsf{red}(\mathcal{H}[S]) has a neighbor if there is a hyperedge E\in\textsf{red}(\mathcal{H}[S]) where v\in E and there exists some v^{\prime}\in E where v\neq v^{\prime} . Partition vertices in \textsf{red}(\mathcal{H}[S]) into those that have a neighbor and those that do not. We create the fractional vertex cover \hat{\tau} by assigning weight 1/2 to every vertex with a neighbor, and weight 1 to vertex without a neighbor. Clearly, this creates a vertex cover. We can now create the fractional vertex packing \hat{\rho} by using \hat{\tau} and dividing each assigned weight by \frac{\alpha}{2} . This is a vertex packing since every edge E containing only one v\in S has total weight \frac{2}{\alpha}\leq 1 , and an edge R with r\geq 2 such vertices has total weight \frac{r}{\alpha}\leq 1 . Clearly \hat{\tau}=\frac{\alpha}{2}\hat{\rho} . ∎ See 3.10 Proof. We prove each item of the proposition. 1) The minimum edge cover assings weight 1 on \{x_{1},\dots,x_{k},z\},\{y_{1},\dots,y_{k},z\} . 2) The minimum vertex cover assigns weight 1 on z , and 0 to every other variable. 3) Consider the subset S=\{x_{1},\dots,x_{k},y_{1},\dots,y_{k}\} that only leaves out z . Here, the minimum vertex cover for \textsf{red}(\mathcal{H}_{k}^{\dagger}[S]) is k . ∎ D.2. Section 4 See 4.16 Proof. \Rightarrow ) This follows from that our algorithm is tuple-based, which means a machine only reports t if it stores witnessing input tuples for t . \Leftarrow ) Since we know that the HyperCube algorithm is correct, to prove the other direction, it suffices to show that \Join_{i}R_{i}=\Join_{i}R_{i}^{\dagger} . (1) \Join_{i}R_{i}\supseteq\Join_{i}R_{i}^{\dagger} : Let t^{\dagger} be a tuple in \Join_{i}R_{i}^{\dagger} . For every R_{i}^{\dagger} , there exists a t_{i}^{\dagger} that witnesses t . Then R_{i} has a tuple t_{i}=\pi_{\textsf{vars}(R_{i})}t_{i}^{\dagger} . These tuples cause t^{\dagger} to also be in \Join_{i}R_{i} . (2) \Join_{i}R_{i}\subseteq\Join_{i}R_{i}^{\dagger} : Let t be a tuple in \Join_{i}R_{i} . Then, there exists, a tuple t_{i} in R_{i} that witnesses t , a tuple \hat{t}_{i} in the guard S_{i} of R_{i} (if R_{i} has a guard) that witnesses t , and t_{H}=\pi_{H[\mathbf{v}]}t . R_{i}^{\dagger} then has a tuple t_{i}^{\dagger} , obtained with t_{i},\hat{t}_{i},t_{H} (or t_{i},t_{H} if there is no guard), such that t_{i}^{\dagger} witnesses t , for each relation R_{i}^{\dagger} , causing t to also be in \Join_{i}R_{i}^{\dagger} . ∎ D.3. Section 5 See 5.3 Proof. Consider the query Q^{\prime} with hypergraph \textsf{red}(\mathcal{H}[S]) that achieves the lower bound of \Omega(n/p^{\epsilon}) . We can create a query Q for \mathcal{H} as follows. Every relation R\in Q that is not removed in \textsf{red}(\mathcal{H}[S]) is the same as in Q^{\prime} , with the only difference that any attribute in \textsf{vars}(R)\setminus S has a fixed constant value (of say, 0). If a relation R\in Q is removed \textsf{red}(\mathcal{H}[S]) , then it is absorbed by some relation R^{\prime}\in Q^{\prime} ; in this case, R is the same as the projection of R^{\prime} on \textsf{vars}(R)\setminus S , setting any attribute in \textsf{vars}(R)\setminus S to 0 as before. For query Q , all relations have size at most n , as in Q^{\prime} . It is now easy to see that any tuple-based algorithm that correctly computes Q can be modified to compute Q^{\prime} with exactly the same load. ∎ Appendix E Comparison \kappa and PAC In this section, we will prove that for any query Q , PAC(Q)\geq\kappa(Q) . See 3.9 Proof. Consider any query Q over \mathcal{H} , and let S\subseteq V be the subset of vertices that maximize \tau^{*}(\textsf{red}(\mathcal{H}[S])) . Consider a database instance where all variables outside S only have one value 1 , and on variables in S , we have values 1,\dots,n . Each relation will have all tuples that have value 1 on attributes outside S , and the same value s\in\{1,\dots,n\} on all variables in S . For example, a relation on attributes x,y,z where x\notin S , y,z\in S , we will have tuples (1,1,1),(1,2,2),(1,3,3),\dots,(1,n,n) . Note that the query over this instance can be computed with load n/p , by performing repeated binary joins, since the intermediate sizes do not grow, but we will argue that under the PAC framework, any solution incurs load n/p^{1/\tau^{*}(\textsf{red}(\mathcal{H}[S]))} , which matches \kappa . Note that for this instance, any set A of variables where A\subseteq S , has the configuration C(A)=1 , meaning no A\subseteq S are heavy. Consider the variables in S . These can never be in a patch, since they are not heavy. This leaves us with covering S with either a semi-cover and anchors. We will argue that the total cost of these is at least \tau^{*}(\textsf{red}(\mathcal{H}[S])) . Indeed, consider the following weight vertex weight mapping v : each vertex in S gets the weight f_{x} from the semi-cover. In addition, for an anchor on relation R , we add a total weight 1 to the vertices in R\cap S . PAC requires that every relation R that has some variable in S is either (1) covered by f , (2) reducable into a relation that is covered by f or an anchor or (3) is an anchor. In case 1 and 3, this means that v covers R . In case 2 , R would be left out from \textsf{red}(\mathcal{H}[S]) . Hence, v is a vertex cover over \textsf{red}(\mathcal{H}[S]) . Since every vertex cover has weight at least \tau^{*}(\textsf{red}(\mathcal{H}[S])) , the lemma follows. ∎ Appendix F Lower Bound Lemma F.1. For a query Q , let \mathbf{v}^{*} be an optimal solution to the following linear program. (2) \displaystyle\min_{\mathbf{v}}\sum_{x\in\textsf{vars}(Q)}v_{x} \displaystyle s.t.\quad\forall R\in Q: \displaystyle\sum_{x\in R}v_{x}\geq 1 \displaystyle\forall x: \displaystyle v_{x}\geq 0 Consider now the following linear program (3) \displaystyle\max_{\psi}\sum_{x\in\textsf{vars}(Q)}\psi_{x} \displaystyle s.t.\quad\forall R\text{ where }\sum_{x\in R}v_{x}=1: \displaystyle\sum_{x\in R}\psi_{x}\leq 1 \displaystyle\forall x|v_{x}=0: \displaystyle\psi_{x}\leq 0 \displaystyle\forall x: \displaystyle\psi_{x}\geq 0 Then, the optimal solution \mathbf{v}^{*} in the first LP is also optimal in the second LP. Proof. \mathbf{v}^{*} is feasible in LP 3 since LP 3 does not have a constraint \sum_{x\in R}\psi_{x}\leq 1 for x where \sum_{x\in R}v_{x}>1 . Suppose for contradiction that \mathbf{v}^{*} is not optimal in LP 3 . Then, there exist a vector \Delta such that \mathbf{v}^{*}+\Delta is a better solution. We claim that then, for some \epsilon>0 , \mathbf{v}^{*}-\epsilon\Delta is a solution to LP 2 . To show this, we will argue that all constraints are satisfied. First, for any R where LP 2 has a tight constraint, \sum_{x\in R}\Delta_{x}\leq 0 , so the corresponding constraint in LP 2 is satisfied. For any R such the constraint in LP 2 is slack, then there exists an \epsilon such that \sum_{x\in R}(v_{x}-\epsilon\Delta_{x})\geq 1 . Lastly, we argue that the constraints v_{x}\geq 0 are satisfied, even if \Delta_{x}\geq 0 . We know that if v_{x}=0 , then \Delta_{x}=0 . If v_{x}>0 , then we can pick \epsilon sufficiently small such that v_{x}-\epsilon\Delta_{x}\geq 0 . Notice that \mathbf{v}^{*}-\epsilon\Delta is a lower vertex cover than \mathbf{v}^{*} . This is a contradiction, since \mathbf{v}^{*} was picked because it is the smallest vertex cover. ∎ Lemma F.2. Let Q be a sparse product query with a reduced hypergraph \mathcal{H} . Consider a machine which is permitted to load L tuples from each relation. Then, in expectation (over the randomness of the sparse relations) the number of tuples the machine will produce is at most L^{\tau^{*}(\mathcal{H})}\prod_{R\in Q}P_{R} Proof. For each of the deterministic relations, we can load at most L tuples. This means that the maximal number of output tuples that can be produced is given by \displaystyle\max_{\Psi}\prod_{x\in\textsf{vars}(Q)}\Psi_{x} \displaystyle s.t.\quad \displaystyle\forall R|\sum_{x\in R}v_{x}=1:\prod_{x\in R}\Psi_{i}\leq L \displaystyle\forall x:\Psi_{x}\leq n^{v_{x}} By taking the logarithm with base L , we get the following linear program, which is a vertex packing problem \displaystyle\max_{\psi}\sum_{x\in\textsf{vars}(Q)}\psi_{x} \displaystyle s.t.\quad \displaystyle\forall R\text{ where }\sum_{x\in R}v_{x}=1:\sum_{x\in R}\psi_{x}\leq 1 \displaystyle\forall x:\psi_{x}\leq v_{x}\log_{L}n Note that \log_{L}n>1 since L