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}
}
BibTeX

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 ... BibTeX

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) BibTeX
[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 BibTeX
[Bayer & McCreight 1972]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[Biliris 1992]
Alexandros Biliris: The Performance of Three Database Storage Structures for Managing Large Objects. SIGMOD Conference 1992: 276-285 BibTeX
[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) BibTeX
[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 BibTeX
[Cattell & Skeen 1992]
R. G. G. Cattell, J. Skeen: Object Operations Benchmark. ACM Trans. Database Syst. 17(1): 1-31(1992) BibTeX
[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) BibTeX
[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 BibTeX
[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 BibTeX
[Edelson 1992]
Daniel R. Edelson: Smart Pointers: They're Smart, But They're Not Pointers. C++ Conference 1992: 1-20 BibTeX
[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) BibTeX
[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 BibTeX
[Gruber et al. 1992]
...
[Hosking & Moss 1991]
Antony L. Hosking, J. Eliot B. Moss: Towards Compile-Time Optimizations for Persistence. POS 1990: 17-27 BibTeX
[Hosking & Moss 1993]
Antony L. Hosking, J. Eliot B. Moss: Object Fault Handling for Persistent Programming Languages: A Performance Evaluation. OOPSLA 1993: 288-303 BibTeX
[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) BibTeX
[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) BibTeX
[Kemper & Kossman 1994]
Alfons Kemper, Donald Kossmann: Dual-Buffering Strategies in Object Bases. VLDB 1994: 427-438 BibTeX
[Kemper & Moerklotte 1992]
Alfons Kemper, Guido Moerkotte: Access Support Relations: An Indexing Method for Object Bases. Inf. Syst. 17(2): 117-145(1992) BibTeX
[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 BibTeX
[Kemper & Moerkotte 1992]
Alfons Kemper, Guido Moerkotte, Michael Steinbrunn: Optimizing Boolean Expressions in Object-Bases. VLDB 1992: 79-90 BibTeX
[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 BibTeX
[Khoshafian & Copeland 1986]
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 BibTeX
[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 BibTeX
[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) BibTeX
[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) BibTeX
[Maier & Stein 1987]
...
[McAuliffe & Solomon 1995]
Mark L. McAuliffe, Marvin H. Solomon: A Trace-Based Simulation of Pointer Swizzling Techniques. ICDE 1995: 52-61 BibTeX
[Morel & Renvoise 1979]
Etienne Morel, Claude Renvoise: Global Optimization by Suppression of Partial Redundancies. Commun. ACM 22(2): 96-103(1979) BibTeX
[Moss 1990]
J. Eliot B. Moss: Design of the Mneme Persistent Object Store. ACM Trans. Inf. Syst. 8(2): 103-139(1990) BibTeX
[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) BibTeX
[Moss & Sinofsky 1988]
J. Eliot B. Moss, Steven Sinofsky: Managing Persistent Data with Mneme: Designing a Reliable, Shared Object Interface. OODBS 1988: 298-316 BibTeX
[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 BibTeX
[Rosenberg et al. 1990]
...
[Roussopoulos & Delis 1991]
Nick Roussopoulos, Alex Delis: Modern Client-Server DBMS Architectures. SIGMOD Record 20(3): 52-61(1991) BibTeX
[Russel et al. 1994]
Gordon Russel, Paul Shaw, W. Paul Cockshott: DAIS: An Object-Addressed Processor Cache. POS 1994: 374-386 BibTeX
[Schuh et al. 1990]
Daniel T. Schuh, Michael J. Carey, David J. DeWitt: Persistence in E Revisited - Implementation Experiences. POS 1990: 345-359 BibTeX
[Shekita & Zwilling 1990]
Eugene J. Shekita, Michael J. Zwilling: Cricket: A Mapped, Persistent Object Store. POS 1990: 89-102 BibTeX
[Singhal et al. 1992]
Vivek Singhal, Sheetal V. Kakkad, Paul R. Wilson: Texas: An Efficient, Portable Persistent Store. POS 1992: 11-33 BibTeX
[Suzuki et al. 1994]
Shinji Suzuki, Masaru Kitsuregawa, Mikio Takagi: An Efficient Pointer Swizzling Method for Navigation Intensive Applications. POS 1994: 79-95 BibTeX
[Tsangaris & Naughton 1991]
Manolis M. Tsangaris, Jeffrey F. Naughton: A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991: 12-21 BibTeX
[Vaughan & Dearle 1992]
Francis Vaughan, Alan Dearle: Supporting Large Persistent Stores using Conventional Hardware. POS 1992: 34-53 BibTeX
[Velez et al. 1989]
Fernando Vélez, Guy Bernard, Vineeta Darnis: The O2 Object Manager: an Overview. VLDB 1989: 357-366 BibTeX
[White & DeWitt 1994]
Seth J. White, David J. DeWitt: QuickStore: A High Performance Mapped Object Store. SIGMOD Conference 1994: 395-406 BibTeX
[White & DeWitt 1992]
Seth J. White, David J. DeWitt: A Performance Study of Alternative Object Faulting and Pointer Swizzling Strategies. VLDB 1992: 419-431 BibTeX
[Wilson 1991]
...
[Wilson & Kakkad 1992]
...
[Winslett 1993]
...

Referenced by

  1. Laura M. Haas, Donald Kossmann, Ioana Ursu: Loading a Cache with Query Results. VLDB 1999: 351-362
  2. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  3. Alfons Kemper, Donald Kossmann: Adaptable Pointer Swizzling Strategies in Object Bases: Design, Realization, and Quantitative Analysis. VLDB J. 4(3): 519-566(1995)
  4. Malcolm P. Atkinson, Ronald Morrison: Orthogonally Persistent Object Systems. VLDB J. 4(3): 319-401(1995)
  5. Mark L. McAuliffe, Marvin H. Solomon: A Trace-Based Simulation of Pointer Swizzling Techniques. ICDE 1995: 52-61
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:25 2009