A Performance Evaluation of OID Mapping Techniques.

André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29
  author    = {Andr{\'e} Eickler and
               Carsten Andreas Gerlhof and
               Donald Kossmann},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {A Performance Evaluation of OID Mapping Techniques},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {18-29},
  ee        = {db/conf/vldb/EicklerGK95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP,}


In this paper, three techniques to implement logical OIDs are thoroughly evaluated: hashing, B-trees and a technique called direct mapping. Among these three techniques, direct mapping is the most robust; it induces at most one page fault to map an OID, and it scales very well to large, rapidly growing databases. Furthermore, the clustering of handles that are used to map logical OIDs is studied. In particular, the performance of B-trees and direct mapping can improve significantly if the handles of objects that are frequently accessed by the same methods are clustered. For direct mapping, two placement policies are compared: linear and matrix clustering.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents BibTeX


Ilsoo Ahn: Filtered Hashing. FODO 1993: 85-100 BibTeX
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
Alfred L. Brown, John Rosenberg: Persistent Object Stores: An Implementation Technique. POS 1990: 199-212 BibTeX
Michael J. Carey, David J. DeWitt, Michael J. Franklin, Nancy E. Hall, Mark L. McAuliffe, Jeffrey F. Naughton, Daniel T. Schuh, Marvin H. Solomon, C. K. Tan, Odysseas G. Tsatalos, Seth J. White, Michael J. Zwilling: Shoring Up Persistent Applications. SIGMOD Conference 1994: 383-394 BibTeX
Soon Myoung Chung: Indexed Extendible Hashing. Inf. Process. Lett. 44(1): 1-6(1992) BibTeX
Chee Yong Chan, Beng Chin Ooi, Hongjun Lu: Extensible Buffer Management of Indexes. VLDB 1992: 444-454 BibTeX
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
Alan Dearle, Gail M. Shaw, Stanley B. Zdonik (Eds.): Implementing Persistent Object Bases, Principles and Practice, Proceedings of the Fourth International Workshop on Persistent Objects, 23-27 September 1990, Martha's Vineyard, MA, USA. Morgan Kaufmann 1990, ISBN 1-55860-168-6
Contents BibTeX
Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988) BibTeX
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX
Carsten Andreas Gerlhof, Alfons Kemper, Christoph Kilger, Guido Moerkotte: Partition-Based Clustering in Object Bases: From Theory to Practice. FODO 1993: 301-316 BibTeX
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
Mark F. Hornick, Stanley B. Zdonik: A Shared, Segmented Memory System for an Object-Oriented Database. ACM Trans. Inf. Syst. 5(1): 70-95(1987) BibTeX
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 BibTeX
Alfons Kemper, Guido Moerkotte: Object-Oriented Database Management: Applications in Engineering and Computer Science. Prentice-Hall 1994, ISBN 0-13-629239-9
Contents BibTeX
Alan Kaplan, Jack C. Wileden: Conch: Experimenting with Enhanced Name Management for Persistent Object Systems. POS 1994: 318-331 BibTeX
Per-Åke Larson: Dynamic Hash Tables. Commun. ACM 31(4): 446-457(1988) BibTeX
Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988) BibTeX
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 BibTeX
James G. Mitchell, Jonathan Gibbons, Graham Hamilton, Peter B. Kessler, Yousef Y. A. Khalidi, Panos Kougiouris, Peter Madany, Michael N. Nelson, Michael L. Powell, Sanjay R. Radia: An Overview of the Spring System. COMPCON 1994: 122-131 BibTeX
C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992) BibTeX
C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380 BibTeX
C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252 BibTeX
Ekow J. Otoo: Linearizing the Directory Growth in Order Preserving Extendible Hashing. ICDE 1988: 580-588 BibTeX
Mark Sullivan, Michael A. Olson: An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System. ICDE 1992: 293-300 BibTeX
Richard W. Watson: Identifiers (Naming) in Distributed Systems. Advanced Course: Distributed Systems 1980: 191-210 BibTeX
David L. Wells, José A. Blakeley: Distribution and Persistence in the Open Object-Oriented Database System. IWDOM 1992: 50-56 BibTeX
Ifor Williams, Mario Wolczko: An Object-Based Memory Architecture. POS 1990: 114-130 BibTeX

Referenced by

  1. Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
  2. Mohana Krishna Lakhamraju, Rajeev Rastogi, S. Seshadri, S. Sudarshan: On-line Reorganization in Object Databases. SIGMOD Conference 2000: 58-69
  3. Kjetil Nørvåg: The Persistent Cache: Improving OID Indexing in Temporal Object-Oriented Database Systems. VLDB 1999: 66-77
  4. Kjetil Nørvåg: Efficient Use of Signatures in Object-Oriented Database Systems. ADBIS 1999: 367-381
  5. Reinhard Braumandl, Jens Claußen, Alfons Kemper: Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases. VLDB 1998: 110-122
  6. André Eickler, Alfons Kemper, Donald Kossmann: Finding Data in the Neighborhood. VLDB 1997: 336-345
  7. Michael Gesmann: A Cost Model for Parallel Navigational Access in Complex-Object DBMSs. DASFAA 1997: 1-10
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:03 2009