On the optimal nesting order for computing N-relational joins

Reviewer: Frederick Neil Springsteel

This work concerns certain algorithmic questions about efficient information retrieval in database management. This clearly written, original research addresses the specific question of minimizing the total page fetches needed to evaluate typical queries about a relational database. The approach is based on the well-known “nested loops method” of iterative evaluation and improves upon it by adding heuristics and by solving special cases. The chief contributions of this compact article are: (1)A new data structure to guide the nested loops method: the “query graph.” (2)A crucial formula for the expected number of page accesses in an evaluation. (3)A proof that minimizing this expected number is an intractable (NP-complet- e) problem. (4)A heuristic algorithm for finding an optimal nesting order for the N relations referenced in a query: it runs in cubic time if ties do not occur among successors. (5)For the special case where the given query is a “tree query,” a chain-merging algorithm which minimizes the expected number of page fetches and which takes at most 0( N*Nlog N) time. Clearly, this paper advances the state of the theory of nested loops methods, especially by its efficient algorithms (see (4) and (5) above). However, its several derivations of probabilistic formulas, culminating in (2) above, are based on some convenient assumptions which may not apply in practice. For example, in a given query Q = P 1 & P 2 & . . . & P m, the predicates { P j} are assumed to be independent in the sense that none is implied by the others. Subset conditions violate this. Also, to use the papers algorithms one would have to precompute numbers critical to their formulas: the “selectivity factor” of each join predicate P j = R i.a op R j.b, i.e., the expected fraction of all tuple pairs from the two relations which satisfy P j. Means and estimated costs of finding these factors are not given. Moreover, the critical hypothesis is made that the values of the attributes a,b from each relation are uniformly distributed. As the authors note, this is strictly impossible in a relational database, which has nonrepeated tuples, but it is an approximation often made in the literature [1].