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