On the optimal nesting order for computing N-relational joins

ABSTRACT

Using the nested loops method, this paper addresses the problem of minimizing the number of page fetches necessary to evaluate a given query to a relational database. We first propose a data structure whereby the number of page fetches required for query evaluation is substantially reduced and then derive a formula for the expected number of page fetches. An optimal solution to our problem is the nesting order of relations in the evaluation program, which minimizes the number of page fetches. Since the minimization of the formula is NP-hard, as shown in the Appendix, we propose a heuristic algorithm which produces a good suboptimal solution in polynomial time. For the special case where the input query is a “tree query,” we present an efficient algorithm for finding an optimal nesting order.

REFERENCES

• 1: ABDEL-WAHAB, H.M., AND KAMDEDA, T. On strictly optimal schedules for the cumulative costoptimal scheduling problem. Computing 24 (1980), 61-86.
• 2: ADACHI, J., SAITO, T., AND INOSE, H. On improving the retrieval efficiency in a database. In Proceedings 20th National Con{erence, Information Society of Japan, 1979, 743-744.
• 3: ADACHI, J., SAITO, T., AND INOSE, H. Optimization of query processing in a database. In Proceedings I981 National Con/erence, IECE of Japan, 1981, 6/57.
• 4: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 5: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 6: BERNSTEIN, P.A., AND GOODMAN, N. Power of natural semijoins. SIAM J. Comput. 10, 4 (Nov. 1981), 751-771.
• 7: Blasgen, M.W., and Eswaran, K.P. Storage and access in relational databases. IBM Syst. J. 16, 4 (1977), 363-377.
• 8: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 9: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 10: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: HAMILTON, P., AND MANUEL T. Relational databases do it more easily. Electronics (Mar. 24, 1981). 102-103.
• 13: KAMBAYASHI, Y., YASUURA, K., IWAMA, K., AND YAJIMA, S. The join operation in hierarchical memories. Unpublished manuscript, Dept. Information Science, Kyoto Univ., Japan, Feb. 1981.
• 14: Won Kim, A new way to compute the product and join of relations, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582278]
• 15: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 16: LAWLER, E.L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. 2 {1978), 75-90.
• 17: MONMA, C.L., AND SIDNEY, J.B. Sequencing with series-parallel precedence constraints. Math Oper. Res. 4 (1979), 215-224.
• 18: PERCHERER, R.M. Efficient exploration of product spaces. In Proceedings ACM-SIGMOD International Conference on Management of Data {1976), 169-177.
• 19: 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]
• 20: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 21: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 22: 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]
• 23: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 24: S. Bing Yao, Optimization of query evaluation algorithms, ACM Transactions on Database Systems (TODS), v.4 n.2, p.133-155, June 1979 [doi>10.1145/320071.320072]
• 25: S. Bing Yao , David DeJong, Evaluation of database access paths, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509273]
• 26: YONG, P-Y. Masters Thesis, Dept. of Computing Science, Simon Fraser Univ., Nov. 1983.
• 27: GELENBE, E., AND GARDY, D. On the size of projections: I. Inf. Process. Lett. 14, 1 (1982), 18- 21.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing; Transaction processing

General Terms:
Algorithms, Performance, Theory