Index selection in a self-adaptive data base management system

ABSTRACT

We address the problem of automatically adjusting the physical organization of a data base to optimize its performance as its access requirements change. We describe the principles of the automatic index selection facility of a prototype self-adaptive data base management system that is currently under development. The importance of accurate usage model acquisition and data characteristics estimation is stressed. The statistics gathering mechanisms that are being incorporated into our prototype system are discussed. Exponential smoothing techniques are used for averaging statistics observed over different periods of time in order to predict future characteristics. An heuristic algorithm for selecting indices to match projected access requirements is presented. The cost model on which the decision procedure is based is flexible enough to incorporate the overhead costs of index creation, index storage and application program recompilation.

REFERENCES

• 1: James Martin, Computer Database Organization, 2nd Ed, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 2: 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]
• 3: James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]
• 4: P. C. Yue, C. K. Wong, "Storage Cost Considerations in Secondary Index Selection", International Journal of Computer and Information Sciences, Vol. 4, No. 4, 1975.
• 5: 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]
• 6: R. Bayer, E. McCreight, "Organization and Maintenance of Large Ordered Indexes", Acta Informatica, Vol. 1, Fasc. 3, 1972.
• 7: Morton M. Astrahan , Donald D. Chamberlin, Implementation of a structured English query language, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500088]
• 8: C. L. Liu, "Introduction to Combinatorial Mathematics" McGraw-Hill Book Company, 1968.
• 9: R. G. Brown, "Statistical Forecasting for Inventory Control", McGraw-Hill Book Company, 1959.
• 10: R. G. Brown, "Smoothing, Forecasting and Prediction of Discrete Time Series", Prentice Hall Inc., Englewood Cliffs, New Jersey, 1962.
• 11: M. Schkolnick, "The Optimal Selection of Secondary Indices For Files", Research Report, Department of Computer Science, Carnegie-Mellon University, Nov., 1974.
• 12: A. A. Kuehn, M. J. Hamburger, "A Heuristic Program for Locating Warehouses", Management Science, Vol. 9, No. 4, July, 1963.
• 13: R. C. Meier, W. T. Newell, H. L. Pazer, "Simulation in Business and Economics", Prentice Hall Inc., Englewood Cliffs, New Jersey, 1963.
• 14: J. H. G. Farley, S. A. Schuster, "Query Execution and Index Selection for Relational Data Bases", Technical Report CSRG-53, University of Toronto, Mar., 1975.
• 15: G. D. Held, "Storage Structures for Relational Data Base Management Systems", Memorandum No. ERL-M533, University of California, Berkeley, Aug., 1975.
• 16: M. Stonebraker, "The Choice of Partial Inversions and Combined Indices", International Journal of Computer and Information Sciences, Vol. 3, No. 2, 1974.
• 17: W. F. King, "On the Selection of Indices for a File", IBM Research RJ 1341, San Jose, Jan., 1974.