A heuristic approach to attribute partitioning

ABSTRACT

One technique that is sometimes employed to enhance the performance of a database management system is known as attribute partitioning. This is the process of dividing the attributes of a file into separately stored subfiles. By storing together those attributes that are frequently requested together by transactions, and by separating those that are not, attribute partitioning can reduce the number of pages that are transferred from secondary storage to primary memory in the processing of a transaction.The goal of this work is to design mechanisms that can automatically select a near-optimal attribute partition of a file's attributes, based on the usage pattern of the file and on the characteristics of the data in the file. The approach taken to this problem is based on the use of an accurate partition evaluator and of a heuristic that guides a search through the large space of possible partitions. The heuristics propose a small set of promising partitions to submit for detailed analysis. The evaluator assigns a figure of merit to any proposed partition that reflects the cost that would be incurred in processing the transactions in the usage pattern if the file were partitioned in the proposed way.We have implemented an evaluator for a particular model database system and have developed a heuristic search technique. A series of experiments has demonstrated the accuracy and efficiency of this heuristic.

REFERENCES

• 1: Alsberg P. A., "Space and Time Savings through Large Data Base Compression and Dynamic Restructuring", Proceedings of the IEEE, Vol. 63, No. 8, August 1975.
• 2: Jair M. Babad, A record and file partitioning model, Communications of the ACM, v.20 n.1, p.22-31, Jan. 1977 [doi>10.1145/359367.359418]
• 3: Batory, D. S., "On Searching Transposed Files", Proceedings of the International Conference on Very Large Data Bases, 1978.
• 4: Benner F. H., "On Designing Generalized File Records for Management Information Systems", Proceedings of the Fall Joint Computer Conference, 1967.
• 5: Belford, G. G., "Dynamic Data Clustering and Partitioning", CAC *162, Center for Advanced Computation, Research in Network Data Management and Resource Sharing, University of Illinois at Urbana-Champaign, May 1975.
• 6: Blasgen, M. W., and Eswaran, K. P., "On the Evaluation of Queries in a Relational Data Base System", Computer Science Department, IBM Research Laboratory, San Jose, Calif., 1976.
• 7: A. Y. Chan, INDEX SELECTION IN A SELF-ADAPTIVE RELATIONAL DATA BASE MANAGEMENT SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 8: Day, R. H., "An Optimal Extracting from a Multiple File Data Storage System: An Application of Integer Programming," Operations Research, 13, 3 (May 1956) 482--494.
• 9: Dearnley, P., "Model of a Self-organizing Data Management System", Computer Journal Vol. 17, No. 1, Feb. 1974.
• 10: Mark J. Eisner , Dennis G. Severance, Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases, Journal of the ACM (JACM), v.23 n.4, p.619-635, Oct. 1976 [doi>10.1145/321978.321982]
• 11: Golden, B. L., "A Statistical Approach to the Travelling Salesman Problem", Networks, Vol. 7, 1977.
• 12: 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.
• 13: Hammer, M. M., and Chan, A. Y., "Acquisition and Utilization of Access Patterns in Relational Data Base Implementation", Pattern Recognition and Artificial Intelligence (editor Chen, C. H.), Academic Press, 1976.
• 14: Hammer, M. M., "Self-adaptive Automatic Data Base Design", Proceedings of National Computer Conference, Dallas, Texas, June 1977.
• 15: Hammer, M. M., and Chan, A. Y., "A Statistical Inference Approach to the Validation of Database Design Heuristics", forthcoming memorandum.
• 16: Jeffrey Alan Hoffer, A clustering approach to the generation of subfiles for the design of a computer data base., 1975
• 17: Hoffer, J. A., and Severance, D. G., "The Use of Cluster Analysis in Physical Data Base Design", Proceedings of International Conference on Very Large Data Bases, Framingham MA, Sept. 1975.
• 18: Kennedy, S. R., "A File Partitioning Model", California Institute of Technology Information Science Technical Report 2, May 1972.
• 19: Kennedy, S. R., "The Use of Access Frequencies in Data Base Organization", Ph. D. Dissertation, The Wharton School, University of Pennsylvania (May 1973), 155pp.
• 20: Salvatore T. March , Dennis G. Serverance, The determination of efficient record segmentations and blocking factors for shared data files, ACM Transactions on Database Systems (TODS), v.2 n.3, p.279-296, Sept. 1977 [doi>10.1145/320557.320574]
• 21: McCormick, W. T., Jr., Schweitzer, P. J., and White, T. W., "Problem Decomposition and Data Reorganization by a Clustering Technique", Operations Research, 20, 4 (July 1972), 741--751.
• 22: B. Niamir, ATTRIBUTE PARTITIONING IN A SELF-ADAPTIVE RELATIONAL DATA BASE SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 23: Niamir, B., and Chan, A. Y., "On Estimating the Cost of Accessing Records in Blocked Database Organizations", MIT Laboratory for Computer Science, forthcoming Technical Memorandum.
• 24: Osman, I. M., "The Partitioning of a Data Base into Supplies Matching User's Queries", Computer Centre, University of Khartoum, Sudan.
• 25: A clustering algorithm for hierarchical structures, ACM Transactions on Database Systems (TODS), v.2 n.1, p.27-44, March 1977 [doi>10.1145/320521.320531]
• 26: Seppälä, Y., "Definition of Extraction Files and Their Optimization by Zero-One Programming," BIT, 7, 3 (1967) 206--215.
• 27: Stocker, P. M., and Dearnley, P. A., "Self-organizing Data Management Systems", Computer Journal 16, 2 (May 1973).
• 28: Wang, L., "Simultaneous File Partitioning and Index Selection in a Self-adaptive Data Base Management System", MIT Laboratory for Computer Science, Data Base Systems Group unpublished report, August 1978.
• 29: Waters, S. J., "Hit Ratios", the Computer Journal, Volume 19, No. 1, April 1976.
• 30: 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]
• 31: Yue, P. C., and Wong, C. K., "On the Optimal Properties of a Partition Algorithm", IBM Research Report, RC 3797, March 30, 1972.