Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering

This paper presents a simulation-based performance analysis of a concurrent file reorganization algorithm. We examine the effect on throughput of a) buffer size, b) degree of reorganization, c) write probability of transactions, d) multiprogramming level, and e) degree of clustered transactions. The problem of file reorganization that we consider involves altering the placement of records on pages of a secondary storage device. In addition, we want this reorganization to be done in place, i.e., using the file’s original storage space for the newly reorganized file. Our approach is appropriate for a non-in-place reorganization as well. The motivation for such a physical change, i.e., record clustering, is to improve the database system’s performance, i.e., minimizing the number of page accesses made in answering a set of queries. There are numerous record clustering algorithms, but they usually do not solve the entire problem, i.e., they do not specify how to efficiently reorganize the file to reflect the clustering assignment that they determine. In previous work, we have presented an algorithm that is a companion to general record clustering algorithms, i.e., it actually transforms the file. In this work we show through simulation that our algorithm, when run concurrently with user transactions, provides an acceptable level of overall database system performance.