Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a new algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a natural join query in terms of the sizes of the individual relations in the body of the query. These bounds, however, are not constructive: they rely on Shearer's entropy inequality, which is information-theoretic. Thus, the previous results leave open the question of whether there exist algorithms whose runtimes achieve these optimal bounds. An answer to this question may be interesting to database practice, as we show in this article that any project-join style plans, such as ones typically employed in a relational database management system, are asymptotically slower than the optimal for some queries. We present an algorithm whose runtime is worst-case optimal for all natural join queries. Our result may be of independent interest, as our algorithm also yields a constructive proof of the general fractional cover bound by Atserias, Grohe, and Marx without using Shearer's inequality. This bound implies two famous inequalities in geometry: the Loomis-Whitney inequality and its generalization, the Bollobás-Thomason inequality. Hence, our results algorithmically prove these inequalities as well. Finally, we discuss how our algorithm can be used to evaluate full conjunctive queries optimally, to compute a relaxed notion of joins and to optimally (in the worst-case) enumerate all induced copies of a fixed subgraph inside of a given large graph. Additional Key Words and Phrases: Join Algorithms, fractional cover bound, Loomis-Whitney inequality, Bollobás-Thomason inequality A preliminary version of this article was presented at PODS'12 as Reference [62] . We thank Georg Gottlob for sending us a full version of his work [30] . We thank XuanLong Nguyen for introducing us to the Loomis-Whitney inequality. We thank Dung Nguyen for catching some errors in the earlier statement of our algorithm. We thank the anonymous PODS'12 and JACM referees for many helpful comments that have greatly improved the presentation of the article. query size, such an instance-optimal result in terms of data-complexity is still unattainable unless W[1] = RFPT. (See Section 7.2 for details.) Consequently, we formulate and solve an easier problem: Optimal Worst-case Join Evaluation Problem (Optimal Join Problem). Given a fixed database schemaR = {R j (Ā j )} j ∈[m] and an m-tuple of integersN = (N 1 , . . . , N m ) . Let q be the natural join query joining the relations inR and let I (N ) be the set of all instances such that |R I j | = N j for j = 1, . . . ,m. Then, the worst-case optimal join evaluation problem is to evaluate q in time Since any algorithm to produce q(I ) requires time at least |q(I )|, an algorithm that solves the above problem would have an optimal worst-case data-complexity. Implicitly, variants of optimal join problem has been studied for over three decades: a modern relational database management system (RDBMS) uses decades of highly tuned algorithms to efficiently produce query results. Nevertheless, as we shall show in this article, existing join-tree-based query evaluation systems are asymptotically suboptimal-even in the simple example of Equation (1). The main result of this article is a solution to the above problem with f (m, n) = n 2 and д(m, n) = mn. Here, the term f (m, n) · j ∈[m] N j is the pre-processing time, and д(m, n) · sup I ∈I (N ) |q(I )| is the worst-case query evaluation time. In a RDBMS, one computes information, e.g., indexes, offline that may obviate the need to read the entire input relations to produce the output. In a similar spirit, we can extend our results to evaluate any query q in time O (д(m, n) · sup I ∈I (N ) |q(I )|), removing the pre-processing time by precomputing some indices. The first question we need to answer to solve the optimal join problem is to compute exactly the bound sup I ∈I (N ) |q(I )|. Luckily, Grohe and Marx [36] and Atserias, Grohe, and Marx [9] (AGM's results henceforth) derived tight bounds on the number of output tuples of a (natural) join query in terms of the sizes of the input relations. Query output size estimation is also fundamentally important for efficient query processing; these results have generated a great deal of excitement and directly paved the way for our results. To understand the spirit of AGM's results, consider the triangle query example Equation (1), and let q(I ) denote the set of tuples that is output from applying the query to a database instance I . Henceforth, we will drop the superscript I if the input database instance is clear from context. By definition, q(I ) is the set of triples of constants (a, b, c) such that R(ab), S (bc), and T (ac) are in I . Our goal is to bound the number of tuples returned by q on I , denoted by |q(I )|, in terms of |R|, |S |, and |T |. For simplicity, let us consider the case when |R| = |S | = |T | = N . A straightforward bound is |q(I )| ≤ N 3 . One can obtain a better bound by noticing that any pair-wise join (say R S) will contain q(I ) in it as R and S together contain all attributes (or they "cover" all the attributes). This leads to the bound |q(I )| ≤ N 2 . AGM showed that one can get a better upper bound of |q(I )| ≤ N 3/2 by generalizing the notion of cover to a so-called "fractional cover" (see Section 3). Moreover, this estimate is tight in the sense that for infinitely many values of N , one can find a database instance I that for which |q(I )| = N 3/2 . These non-trivial estimates are exciting to database researchers as they offer previously unknown, nontrivial methods to estimate the cardinality of a query result-a fundamental problem
In contrast to worst-case optimal join algorithms REF , our guarantees are probabilistic and refer to optimal execution time (not worst-case result sizes).
Worst-case Optimal Join Algorithms
JACM
Computer Science Mathematics