Physical database design for relational databases

ABSTRACT

This paper describes the concepts used in the implementation of DBDSGN, an experimental physical design tool for relational databases developed at the IBM San Jose Research Laboratory. Given a workload for System R (consisting of a set of SQL statements and their execution frequencies), DBDSGN suggests physical configurations for efficient performance. Each configuration consists of a set of indices and an ordering for each table. Workload statements are evaluated only for atomic configurations of indices, which have only one index per table. Costs for any configuration can be obtained from those of the atomic configurations. DBDSGN uses information supplied by the System R optimizer both to determine which columns might be worth indexing and to obtain estimates of the cost of executing statements in different configurations. The tool finds efficient solutions to the index-selection problem; if we assume the cost estimates supplied by the optimizer are the actual execution costs, it finds the optimal solution. Optionally, heuristics can be used to reduce execution time. The approach taken by DBDSGN in solving the index-selection problem for multiple-table statements significantly reduces the complexity of the problem. DBDSGN's principles were used in the Relational Design Tool (RDT), an IBM product based on DBDSGN, which performs design for SQL/DS, a relational system based on System R. System R actually uses DBDSGN's suggested solutions as the tool expects because cost estimates and other necessary information can be obtained from System R using a new SQL statement, the EXPLAIN statement. This illustrates how a system can export a model of its internal assumptions and behavior so that other systems (such as tools) can share this model.

REFERENCES

• 1: Henry D. Anderson , P. Bruce Berra, Minimum cost selection of secondary indexes for formatted files, ACM Transactions on Database Systems (TODS), v.2 n.1, p.68-90, March 1977 [doi>10.1145/320521.320537]
• 2: ASTRAHAN, M. M., KIM, W., AND SCHKOLNICK, M. Performance of the System R access path selection mechanism. In Info Processing 80: Proceedings of the IFIP Congress 80 (Tokyo, Oct. 1980), pp. 487-491.
• 3: Morton M. Astrahan , Mario Schkolnick , Kyu-Young Whang, Approximating the number of unique values of an attribute without sorting, Information Systems, v.12 n.1, p.11-15, Jan. 1987 [doi>10.1016/0306-4379(87)90014-7]
• 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: BLASGEN, M. W., ASTRAHAN, M. M., CHAMBERLIN, D. D., GRAY, J. N., KING, W. F., LINDSAY, B. G., LORIE, R. A., MEHL, J. W., PRICE, T. O., PUTZOLU, G. R., SCHKOLNICK, M., SELINGER, P. G., SLUTZ, P. R., STRONG, H. R., TRAIGER, I. L., WADE, B. W., AND YOST, R.A. System R: An architectural overview. IBM Syst. J. 20, 1 (1981), 41-62.
• 6: BONANNO, R., MAIO, D., AND TIBERIO, P. Secondary index selection in relational database physical design. Comput. J. 28, 4 (Aug. 1985), 398-405.
• 7: BONFATTI, F., MAIO, D., AND TIBERIO, P. A separability-based method for secondary index selection in physical database design. In Methodology and Tools/or Data Base Design, S. Ceri, Ed. Elsevier North-Holland, New York, 1983, pp. 148-160.
• 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: CHAMBERLIN, D. D., ASTRAHAN, M. M., ESWARAN, K. P., GRIFFITHS, P. P., LORIE, R. A., MEHL, J. W., REISNER, P., AND WADE, B. W. SEQUEL2: A unified approach to data definition, manipulation and control. IBM J. Res. Dev. 20, 6 (Nov. 1976), 560-575.
• 10: D. D. Chamberlin , M. M. Astrahan , W. F. King , R. A. Lorie , J. W. Mehl , T. G. Price , M. Schkolnick , P. Griffiths Selinger , D. R. Slutz , B. W. Wade , R. A. Yost, Support for repetitive transactions and ad hoc queries in System R, ACM Transactions on Database Systems (TODS), v.6 n.1, p.70-94, March 1981 [doi>10.1145/319540.319550]
• 11: Donald D. Chamberlin , Morton M. Astrahan , Michael W. Blasgen , James N. Gray , W. Frank King , Bruce G. Lindsay , Raymond Lorie , James W. Mehl , Thomas G. Price , Franco Putzolu , Patricia Griffiths Selinger , Mario Schkolnick , Donald R. Slutz , Irving L. Traiger , Bradford W. Wade , Robert A. Yost, A history and evaluation of System R, Communications of the ACM, v.24 n.10, p.632-646, Oct. 1981 [doi>10.1145/358769.358784]
• 12: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 13: Douglas Comer, The difficulty of optimum index selection, ACM Transactions on Database Systems (TODS), v.3 n.4, p.440-445, Dec. 1978 [doi>10.1145/320289.320296]
• 14: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 15: Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States
• 16: Michael Hammer , Arvola Chan, Index selection in a self-adaptive data base management system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 17: HATZOPOULOUS, M., AND KOLLIAS, J.Y. On the selection of a reduced set of indexes. Comput. J. 28, 4 (Aug. 1985), 406-408.
• 18: Paula Hawthorn , Michael Stonebraker, Performance analysis of a relational data base 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.582097]
• 19: IBM. Relational Design Tool--Structured Query Language/Data System. Ref. Man. SH20- 6415-1, IBM, San Jose, Calif., 1985.
• 20: IBM. 8QL-data system application programming. Man. SH24-5018-2, IBM, San Jose, Calif., Aug. 1983.
• 21: IBM. SQL-data system planning and administration. Man. SH24-5014-1, IBM, San Jose, Calif., Aug. 1983.
• 22: IBM SYSTEMS JOURNAL. Database 2. IBM Syst. d. 23, 2 (1984), 98-218.
• 23: IP, M. Y. L., SAXTON, L. V., AND RAGHAVAN, V. V. On the selection of an optimal set of
• 24: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 25: KING, W.F. On the selection of indices for a file. Res. Rep. RJ1641, IBM, San Jose, Calif., Jan. 1974.
• 26: KOLLIAS, J.G. A heuristic approach for determining the optimal degree of file inversion. Inf. Syst. 4, 1 (1979), 307-318.
• 27: Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
• 28: PUTKONEN, A. On the selection of access paths in inverted database organizations, inf. Syst. 4, 3 {1979), 219-225.
• 29: RELATIONAL TECHNOLOGY. An Introduction to INGRES. Realtional Technology. Berkeley Calif., Jan. 1984.
• 30: SCHKOLNICK, M. The optimal selection of secondary indices for files. Inf. Syst. 1 (1975), 141-146.
• 31: SCHKOLNICK, M. A survey of physical database methodologT and techniques. In Proceedings of the Very Large Database Conference (Berlin, Sept. 1978), pp. 474-487.
• 32: SCHKOLN{CK, M., AND TIBERZO, P. Considerations in developing a design tool for a relational DBMS. In Proceedings of the IEEE COMPSAC Con{erence (Chicago, Ill., Nov. 1979). IEEE Press, New York, 1979, pp. 228-235.
• 33: M. Schkolnick , P. Tiberio, Estimating the cost of updates in a relational database, ACM Transactions on Database Systems (TODS), v.10 n.2, p.163-179, June 1985 [doi>10.1145/3857.3863]
• 34: Joachim William Schmidt , M. L. Brodie, Relational Database Systems: Analysis and Comparison, Springer-Verlag New York, Inc., Secaucus, NJ, 1983
• 35: SELINGER, P. G., ASTRAHAN, M. M., CHAMBERLIN, D. D., LORIE, R. A., AND PRICE, T.G. Access (Boston, Mass., May 1979). ACM, New York, 1979, pp. 23-34.
• 36: STONEBRAKER, M. The choice of partial inversions and combined indices. Int. J. Comput. In{. Sci. 3, 2 (June 1974), 167-188.
• 37: 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]
• 38: WHANG, K, J. A physical database design methodology using the property of separability. Rep. STAN-CS-83-968, Computer Science Dept., Stanford Univ., Stanford, Calif., May 1983.
• 39: WHANG, K, Y., WIEDERHOLD, G., AND SAGALOWITZ, D. Separability--An approach to physical database design. IEEE Trans. Comput. 33, 3 (Mar. 1984), 209-222.
• 40: 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]
• 41: YAO, S.B. Database storage structure design. In Proceedings of the Conference on Database Engineering (Amagi, Japan, Nov. 1979). IBM, San Jose, Calif., 1979, pp. 1-22.
• 42: YoussgF!, K._, AND WONG~ E. Query processing in a relational database management, system. In Proceedings of the Very Large Database Conference (Rio de Janeiro, Oct. 1979). pp. 409-417.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Tables**

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

General Terms:
Algorithms, Design, Experimentation, Performance, Theory