ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Adaptable Pointer Swizzling Strategies in Object Bases: Design, Realization, and Quantitative Analysis.

Alfons Kemper, Donald Kossmann: Adaptable Pointer Swizzling Strategies in Object Bases: Design, Realization, and Quantitative Analysis. VLDB J. 4(3): 519-566(1995)
@article{DBLP:journals/vldb/KemperK95,
  author    = {Alfons Kemper and
               Donald Kossmann},
  title     = {Adaptable Pointer Swizzling Strategies in Object Bases: Design,
               Realization, and Quantitative Analysis},
  journal   = {VLDB J.},
  volume    = {4},
  number    = {3},
  year      = {1995},
  pages     = {519-566},
  ee        = {db/journals/vldb/KemperK95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this article, different techniques for "pointer swizzling" are classified and evaluated for optimizing the access to main-memory resident persistent objects. To speed up the access along inter-object references, the persistent pointers in the form of unique object identifiers (OIDs) are transformed (swizzled) into main-memory pointers (addresses). Pointer swizzling techniques can be divided into two classes: (1) those that allow replacement of swizzled objects from the buffer before the end of an application program, and (2) those that rule out the displacement of swizzled objects. The first class (i.e., techniques that take "precautions" for the replacement of swizzled objects) has not yet been thoroughly investigated. Four different pointer swizzling techniques allowing object replacement are investigated and compared with the performance of an object manager employing no pointer swizzling. The extensive quantitative evaluation - only part of which could be presented in this article - demonstrate that there is no one superior pointer swizzling strategy for all application profiles. Therefore, an adaptable object base run-time system is devised that employs the full range of pointer swizzling strategies, depending on the application profile characteristics that are determined by, for example, monitoring in combination with sampling, user specifications, and/or program analysis.

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.

Key Words

Pointer swizzling, object-oriented database systems, performance evaluation.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

References

[Atkinson et al. 1983]
Malcolm P. Atkinson, Kenneth Chisholm, W. Paul Cockshott, Richard Marshall: Algorithms for a Persistent Heap. Softw., Pract. Exper. 13(3): 259-271(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bancilhon et al. 1988]
François Bancilhon, Gilles Barbedette, Véronique Benzaken, Claude Delobel, Sophie Gamerman, Christophe Lécluse, Patrick Pfeffer, Philippe Richard, Fernando Vélez: The Design and Implementation of O2, an Object-Oriented Database Systems. OODBS 1988: 1-32 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bayer & McCreight 1972]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Biliris 1992]
Alexandros Biliris: The Performance of Three Database Storage Structures for Managing Large Objects. SIGMOD Conference 1992: 276-285 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bruns et al. 1992]
Kai Bruns, Christoph Kilger, Donald Kossmann, Guido Moerkotte, Hans-Dirk Walter, Andreas Zachmann: Objekte in multiplen Repräsentationen. Datenbank Rundbrief 10: 39-40(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Carey et al. 1986]
Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cattell & Skeen 1992]
R. G. G. Cattell, J. Skeen: Object Operations Benchmark. ACM Trans. Database Syst. 17(1): 1-31(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cockshott et al. 1984]
W. Paul Cockshott, Malcolm P. Atkinson, Kenneth Chisholm, Peter J. Bailey, Ronald Morrison: Persistent Object Management System. Softw., Pract. Exper. 14(1): 49-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cockshott & Foulk 1990]
...
[Dan et al. 1993]
Asit Dan, Philip S. Yu, Jen-Yao Chung: Database Access Characterization for Buffer Hit Prediction. ICDE 1993: 134-143 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DeWitt et al. 1990]
David J. DeWitt, Philippe Futtersack, David Maier, Fernando Vélez: A Study of Three Alternative Workstation-Server Architectures for Object Oriented Database Systems. VLDB 1990: 107-121 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Edelson 1992]
Daniel R. Edelson: Smart Pointers: They're Smart, But They're Not Pointers. C++ Conference 1992: 1-20 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fagin et al. 1979]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gerlhof et al. 1992]
...
[Gerlhof et al. 1993]
Carsten Andreas Gerlhof, Alfons Kemper, Christoph Kilger, Guido Moerkotte: Partition-Based Clustering in Object Bases: From Theory to Practice. FODO 1993: 301-316 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gruber et al. 1992]
...
[Hosking & Moss 1991]
Antony L. Hosking, J. Eliot B. Moss: Towards Compile-Time Optimizations for Persistence. POS 1990: 17-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hosking & Moss 1993]
Antony L. Hosking, J. Eliot B. Moss: Object Fault Handling for Persistent Programming Languages: A Performance Evaluation. OOPSLA 1993: 288-303 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kaehler & Krasner 1983]
...
[Kemper et al. 1994]
Alfons Kemper, Christoph Kilger, Guido Moerkotte: Function Materialization in Object Bases: Design, Realization, and Evaluation. IEEE Trans. Knowl. Data Eng. 6(4): 587-608(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kemper & Kossman 1993]
Alfons Kemper, Donald Kossmann: Adaptable Pointer Swizzling Strategies in Object Bases: Design, Realization, and Quantitative Analysis. VLDB J. 4(3): 519-566(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kemper & Kossman 1994]
Alfons Kemper, Donald Kossmann: Dual-Buffering Strategies in Object Bases. VLDB 1994: 427-438 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kemper & Moerklotte 1992]
Alfons Kemper, Guido Moerkotte: Access Support Relations: An Indexing Method for Object Bases. Inf. Syst. 17(2): 117-145(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kemper & Moerkotte 1994]
Alfons Kemper, Guido Moerkotte: Object-Oriented Database Management: Applications in Engineering and Computer Science. Prentice-Hall 1994, ISBN 0-13-629239-9
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kemper & Moerkotte 1992]
Alfons Kemper, Guido Moerkotte, Michael Steinbrunn: Optimizing Boolean Expressions in Object-Bases. VLDB 1992: 79-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kemper et al. 1991]
Alfons Kemper, Guido Moerkotte, Hans-Dirk Walter, Andreas Zachmann: GOM: A Strongly Typed Persistent Object Model With Polymorphism. BTW 1991: 198-217 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Khoshafian & Copeland 1986]
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kim et al. 1988]
Won Kim, Nat Ballou, Hong-Tai Chou, Jorge F. Garza, Darrell Woelk, Jay Banerjee: Integrating an Object-Oriented Programming System with a Database System. OOPSLA 1988: 142-152 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Koch & Rosenberg 1990]
...
[Kossmann 1991]
...
[Kossmann et al. 1993]
...
[Kotulla 1992]
...
[Lamb et al. 1991]
Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb: The ObjectStore Database System. Commun. ACM 34(10): 50-63(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Larson 1988]
Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Maier & Stein 1987]
...
[McAuliffe & Solomon 1995]
Mark L. McAuliffe, Marvin H. Solomon: A Trace-Based Simulation of Pointer Swizzling Techniques. ICDE 1995: 52-61 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Morel & Renvoise 1979]
Etienne Morel, Claude Renvoise: Global Optimization by Suppression of Partial Redundancies. Commun. ACM 22(2): 96-103(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Moss 1990]
J. Eliot B. Moss: Design of the Mneme Persistent Object Store. ACM Trans. Inf. Syst. 8(2): 103-139(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Moss 1992]
J. Eliot B. Moss: Working with Persistent Objects: To Swizzle or Not to Swizzle. IEEE Trans. Software Eng. 18(8): 657-673(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Moss & Sinofsky 1988]
J. Eliot B. Moss, Steven Sinofsky: Managing Persistent Data with Mneme: Designing a Reliable, Shared Object Interface. OODBS 1988: 298-316 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Munro et al. 1994]
David S. Munro, Richard C. H. Connor, Ronald Morrison, S. Scheuerl, David W. Stemple: Concurrent Shadow Paging in the Flask Architecture. POS 1994: 16-42 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rosenberg et al. 1990]
...
[Roussopoulos & Delis 1991]
Nick Roussopoulos, Alex Delis: Modern Client-Server DBMS Architectures. SIGMOD Record 20(3): 52-61(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Russel et al. 1994]
Gordon Russel, Paul Shaw, W. Paul Cockshott: DAIS: An Object-Addressed Processor Cache. POS 1994: 374-386 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Schuh et al. 1990]
Daniel T. Schuh, Michael J. Carey, David J. DeWitt: Persistence in E Revisited - Implementation Experiences. POS 1990: 345-359 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shekita & Zwilling 1990]
Eugene J. Shekita, Michael J. Zwilling: Cricket: A Mapped, Persistent Object Store. POS 1990: 89-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Singhal et al. 1992]
Vivek Singhal, Sheetal V. Kakkad, Paul R. Wilson: Texas: An Efficient, Portable Persistent Store. POS 1992: 11-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Suzuki et al. 1994]
Shinji Suzuki, Masaru Kitsuregawa, Mikio Takagi: An Efficient Pointer Swizzling Method for Navigation Intensive Applications. POS 1994: 79-95 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tsangaris & Naughton 1991]
Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vaughan & Dearle 1992]
Francis Vaughan, Alan Dearle: Supporting Large Persistent Stores using Conventional Hardware. POS 1992: 34-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Velez et al. 1989]
Fernando Vélez, Guy Bernard, Vineeta Darnis: The O2 Object Manager: an Overview. VLDB 1989: 357-366 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[White & DeWitt 1994]
Seth J. White, David J. DeWitt: QuickStore: A High Performance Mapped Object Store. SIGMOD Conference 1994: 395-406 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[White & DeWitt 1992]
Seth J. White, David J. DeWitt: A Performance Study of Alternative Object Faulting and Pointer Swizzling Strategies. VLDB 1992: 419-431 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wilson 1991]
...
[Wilson & Kakkad 1992]
...
[Winslett 1993]
...

Copyright © Fri Mar 12 17:34:25 2010 by Michael Ley (ley@uni-trier.de)