|
|
|
@inproceedings{DBLP:conf/sigmod/McAuliffeCS96,
author = {Mark L. McAuliffe and
Michael J. Carey and
Marvin H. Solomon},
editor = {H. V. Jagadish and
Inderpal Singh Mumick},
title = {Towards Effective and Efficient Free Space Management},
booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
publisher = {ACM Press},
year = {1996},
pages = {389-400},
ee = {http://doi.acm.org/10.1145/233269.233355, db/conf/sigmod/McAuliffeCS96.html},
crossref = {DBLP:conf/sigmod/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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, and 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 demonstrates excellent performance in all of these areas.
Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
,
SIGMOD Record 25(2),
June 1996