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

@inproceedings{DBLP:conf/vldb/EicklerGK95,
  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, http://dblp.uni-trier.de}
}

Abstract

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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

References

[Ahn93]: Ilsoo Ahn: Filtered Hashing. FODO 1993: 85-100
[AK89]: Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173
[BM72]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[BR90]: Alfred L. Brown, John Rosenberg: Persistent Object Stores: An Implementation Technique. POS 1990: 199-212
[CDF+94]: 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
[Chu92]: Soon Myoung Chung: Indexed Extendible Hashing. Inf. Process. Lett. 44(1): 1-6(1992)
[COL92]: Chee Yong Chan, Beng Chin Ooi, Hongjun Lu: Extensible Buffer Management of Indexes. VLDB 1992: 444-454
[Com79]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[DSZ90]: 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
[ED88]: Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
[FNPS79]: 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)
[GKKM93]: Carsten Andreas Gerlhof, Alfons Kemper, Christoph Kilger, Guido Moerkotte: Partition-Based Clustering in Object Bases: From Theory to Practice. FODO 1993: 301-316
[GR93]: Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents
[HZ87]: 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)
[Ita93]: ...
[KC86]: Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416
[KM94]: Alfons Kemper, Guido Moerkotte: Object-Oriented Database Management: Applications in Engineering and Computer Science. Prentice-Hall 1994, ISBN 0-13-629239-9
Contents
[KSW92]: ...
[KW94]: Alan Kaplan, Jack C. Wileden: Conch: Experimenting with Enhanced Name Management for Persistent Object Systems. POS 1994: 318-331
[Lar88a]: Per-Åke Larson: Dynamic Hash Tables. Commun. ACM 31(4): 446-457(1988)
[Lar88b]: Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)
[Lit80]: Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223
[Lit88]: Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29
[MGH+94]: 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
[MHL+92]: 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)
[ML92]: C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380
[Moc87]: ...
[Moh92]: C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252
[MS87]: ...
[Oto88]: Ekow J. Otoo: Linearizing the Directory Growth in Order Preserving Extendible Hashing. ICDE 1988: 580-588
[SO92]: Mark Sullivan, Michael A. Olson: An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System. ICDE 1992: 293-300
[Sun93]: ...
[Wat81]: Richard W. Watson: Identifiers (Naming) in Distributed Systems. Advanced Course: Distributed Systems 1980: 191-210
[WB94]: David L. Wells, José A. Blakeley: Distribution and Persistence in the Open Object-Oriented Database System. IWDOM 1992: 50-56
[WW90]: Ifor Williams, Mario Wolczko: An Object-Based Memory Architecture. POS 1990: 114-130