Avoiding Cartesian products for multiple joins

ABSTRACT

Computing the natural join of a set of relations is an important operation in relational database systems. The ordering of joins determines to a large extent the computation time of the join. Since the number of possible orderings could be very large, query optimizers first reduce the search space by using various heuristics and then try to select an optimal ordering of joins. Avoiding Cartesian products is a common heuristic for reducing the search space, but it cannot guarantee optimal ordering in its search space, because the cheapest Cartesian-product-free (CPF for short) ordering could be significantly worse than an optimal non-CPF ordering by a factor of an arbitrarily large number. In this paper, we use programs consisting of joins, semijoins, and projections for computing the join of some relations, and we introduce a novel algorithm that derives programs from CPF orderings of joins. We show that there exists a CPF ordering from which our algorithm derives a program whose cost is within a constant factor of the cost of an optimal ordering. Thus, our result demonstrates the effectiveness of avoiding Cartesian products as a heuristic for restricting the search space of orderings of joins.

REFERENCES

• 1: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• 2: BERNSTEIN, P. A., AND GOODMAN, N. 1981. The power of natural semijoins. SIAM J. Comput. 10, 4 (Nov.) 751-771.
• 3: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 4: GOODMAN, N., AND SHMUELI, O. 1984. The tree projection theorem and relational query processing. J. Comput. Syst. Sci. 28, 1 (Feb.), 60-79.
• 5: Yehoshua Sagiv , Oded Shmueli, Solving queries by tree projections, ACM Transactions on Database Systems (TODS), v.18 n.3, p.487-511, Sept. 1993 [doi>10.1145/155271.155277]
• 6: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 7: David E. Smith , Michael R. Genesereth, Ordering conjunctive queries, Artificial Intelligence, v.26 n.2, p.171-215, May 1985 [doi>10.1016/0004-3702(85)90028-1]
• 8: Arun Swami , Anoop Gupta, Optimization of large join queries, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.8-17, June 01-03, 1988, Chicago, Illinois, United States
• 9: A. Swami, Optimization of large join queries: combining heuristics and combinatorial techniques, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.367-376, June 1989, Portland, Oregon, United States
• 10: Y. C. Tay, On the optimality of strategies for multiple join, Journal of the ACM (JACM), v.40 n.5, p.1067-1086, Nov. 1993 [doi>10.1145/174147.174151]
• 11: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 12: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 13: YANNAKAKIS, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the International Conference on Very Large Data Bases (Cannes, France, Sept. 9-11). ACM, New York, pp. 82-94.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

General Terms:
Algorithms, Languages, Theory

Keywords:
Cartesian product, database scheme, join expression tree, join strategy, optimality, semijoin