An important problem faced by many database management systems is the "online object placement problem"--the problem of choosing a disk page to hold a newly allocated object. In the absence of clustering criteria, the goal is to maximize storage utilization. For main-memory based systems, simple heuristics exist that provide reasonable space utilization in the worst case and excellent utilization in typical cases. However, the storage management problem for databases includes significant additional challenges, such as minimizing I/O traffic, coping with crash recovery, and gracefully integrating space management with locking and logging.We survey several object placement algorithms, including techniques that can be found in commercial and research database systems. We then present a new object placement algorithm that we have designed for use in Shore, an object-oriented database system under development at the University of Wisconsin--Madison. Finally, we present results from a series of experiments involving actual Shore implementations of some of these algorithms. Our results show that while current object placement algorithms have serious performance deficiencies, including excessive CPU or main memory overhead, I/O traffic, or poor disk utilization, our new algorithm consistently excellent performance in all of these areas.

Persistent object-oriented applications that traverse large object graphs can improve their performance by caching objects in main memory while they are being used. While caching offers large performance benefits, the techniques used to locate these cached objects in memory can still impede the application's performance. We present the results of a trace-based simulation study of pointer swizzling techniques (techniques for reducing the cost of access to cached objects). We used traces derived from actual persistent programs to find a class of swizzling techniques that performs well, yet permits changes to the contents of in-memory object caches over the lifetime of an application. Our study demonstrates the superiority of a class of techniques known as "indirect swizzling" for a variety of workloads and system configurations.>

SHORE (Scalable Heterogeneous Object REpository) is a persistent object system under development at the University of Wisconsin. SHORE represents a merger of object-oriented database and file system technologies. In this paper we give the goals and motivation for SHORE, and describe how SHORE provides features of both technologies. We also describe some novel aspects of the SHORE architecture, including a symmetric peer-to-peer server architecture, server customization through an extensible value-added server facility, and support for scalability on multiprocessor systems. An initial version of SHORE is already operational, and we expect a release of Version 1 in mid-1994.