Storage management methods for object database systems
Mark L. McAuliffe, Marvin H. Solomon, Michael J. Carey · 1997
This thesis addresses two important storage management problems seen in the emerging generation of object-oriented database systems. It has three parts. The first part describes a new storage management architecture that was designed and implemented to support the work presented in the second and third parts of the thesis. This architecture covers many of the important aspects of storage management needed to support files and indices in a multi-user environment. The second part of this thesis examines the problem of storage management in unstructured heap files, a major component of which is the object placement problem, the problem of choosing the page onto which to place a newly-created record or object. We survey object placement algorithms found in current database systems and demonstrate, through an implementation-based performance study, that these algorithms have serious performance deficiencies in the areas of CPU and main-memory overhead, I/O performance, or disk space utilization. To address these shortcomings, we present a new algorithm called HY$(n,u)$ and demonstrate experimentally that this new algorithm gives excellent runtime performance and space utilization across a wide variety of workloads. The third part of this thesis considers the problem of delivering effective clustering tools to users of object-oriented database systems. The work presented here differs from earlier work in clustering in that it emphasizes on-line methods for building and maintaining object clusters. We begin by examining current on-line clustering methods and showing that they can be ineffective or difficult to use, and may sacrifice disk space utilization for clustering. We then introduce a new clustering architecture based on variable-size clusters or Vclusters. Vclusters are a simple and effective clustering mechanism that can be used either directly by application programmers or as the underlying storage mechanism for an automatic clustering subsystem. We describe two algorithms for implementing Vclusters and we present results from an implementation-based performance study that compares Vclusters against clustering mechanisms commonly found in existing commercial and experimental object-oriented database systems. Our results show that Vclusters are capable of delivering excellent clustering and space utilization at a reasonable runtime cost for a wide variety of workloads.