Minimum cost selection of secondary indexes for formatted files

ABSTRACT

Secondary indexes are often used in database management systems for secondary key retrieval. Although their use can improve retrieval time significantly, the cost of index maintenance and storage increases the overhead of the file processing application. The optimal set of indexed secondary keys for a particular application depends on a number of application dependent factors. In this paper a cost function is developed for the evaluation of candidate indexing choices and applied to the optimization of index selection. Factors accounted for include file size, the relative rates of retrieval and maintenance and the distribution of retrieval and maintenance over the candidate keys, index structure, and system charging rates. Among the results demonstrated are the increased effectiveness of secondary indexes for large files, the effect of the relative rates of retrieval and maintenance, the greater cost of allowing for arbitrarily formulated queries, and the impact on cost of the use of different index structures.

REFERENCES

• 1: Henry Dwight Anderson, Optimal selection of secondary-indexes in data-base management systems., 1973
• 2: BOOKMAN, P.J. Make your users pay the price. Computer Decisions 4 (Sept. 1972), 28-31.
• 3: 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]
• 4: CODASYL SYSTEMS COMMITTEE. A survey of generalized data base management systems. ACM, New York, May 1969.
• 5: CORPORATE Codasyl Systems Committee, Introduction to “feature analysis of generalized data base management systems”, Communications of the ACM, v.14 n.5, p.308-318, May 1971 [doi>10.1145/362588.362590]
• 6: DELOBEL, C. Determination of an optimal set of secondary keys for formatted files. ONLINE 72, Int. Symp. and Exhib. of Online Interactive Comptng, Brunel U., Uxbridge, England, Sept. 1972.
• 7: IBM System/370 Model 155 Functional Characteristics. GA22-6942-1, IBM Corp., White Plains, N.Y., 1971.
• 8: JONES, W.J. Syracuse University Computing Center charges. Document C64-0495, Syracuse U. Comptng. Ctr. Inform. SET., Syracuse U., Syracuse, N.Y., Feb. 1972.
• 9: KING~ W.F. On the Selection of indices for a file. IBM Res. Rep. RJ 1341, IBM Res. Lab., San Jose, Calif., Jan. 1974.
• 10: KNUTtt, D.E. The Art of Computer Programming, Vol. 3: Searching and Sorting. Addison Wesley, Reading, Mass., 1973.
• 11: Thomas C. Lowe, The Influence of Data Base Characteristics and Usage on Direct Access File Organization, Journal of the ACM (JACM), v.15 n.4, p.535-548, Oct. 1968 [doi>10.1145/321479.321482]
• 12: Vincent Y. Lum , Huei Ling, An optimization problem on the selection of secondary keys, Proceedings of the 1971 26th annual conference, p.349-356, January 1971 [doi>10.1145/800184.810505]
• 13: V. Y. Lum, Multi-attribute retrieval with combined indexes, Communications of the ACM, v.13 n.11, p.660-665, Nov 1970 [doi>10.1145/362790.362794]
• 14: Michael Stonebraker, Retrieval efficiency using combined indices, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.243-256, January 1972 [doi>10.1145/800295.811493]
• 15: WEBB, D.A. Evaluation of hash coding systems. Ph.D. Th., SIS Dept., Syracuse U., Syracuse, N.Y., Aug. 1972.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Design, Management

Keywords:
Boolean query, access methods, access path, cost function, data management, database, file design, file organization, inverted file, inverted index, maintenance, optimization, retrieval, secondary index, secondary key, secondary key access