The difficulty of optimum index selection

ABSTRACT

Given a file on a secondary store in which each record has several attributes, it is usually advantageous to build an index mechanism to decrease the cost of conducting transactions to the file. The problem of selecting attributes over which to index has been studied in the context of various storage structures and access assumptions. One algorithm to make an optimum index selection requires 2k steps in the worst case, where k is the number of attributes in the file. We examine the question of whether a more efficient algorithm might exist and show that even under a simple cost criterion the problem is computationally difficult in a precise sense. Our results extend directly to other related problems where the cost of the index depends on fixed values which are assigned to each attribute. Some practical implications are discussed.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BLEIER, R. E., AND VORHAUS, A. H. File organization in the SCD time shared data management (TDMS) system. Information Processing 68, North-Holland Pub. Co., Amsterdam, 1969, pp. 1245-1252.
• 3: R. G. Casey, Design of tree structures for efficient querying, Communications of the ACM, v.16 n.9, p.549-556, Sept. 1973 [doi>10.1145/362342.362353]
• 4: 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]
• 5: KARP, R. Reducibility among combinatorial problems. In Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-103.
• 6: KINC, W. On the selection of indices for a file. Rep. RJ 1341, IBM Res. Ctr., San Jose, Calif., Jan. 1974.
• 7: 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]
• 8: 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]
• 9: PALERMO, F. A quantitative approach to the selection of secondary indexes. Rep. RJ 730, IBM Res. Ctr., San Jose, Calif., july 1970.
• 10: SCHKOLNICK, M. The optimal selection of secondary indices for fries. Inform. Syst. 1, 4 (1975), 141-146.
• 11: STONESRAKER, M. The choice of partial inversions and combined indices. Int. J. Comptr. and Inform. Sci. 3, 2 (June 1974), 167-188.

INDEX TERMS

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

General Terms:
Design

Keywords:
attribute selection, complexity, index selection, secondary index