ACM SIGMOD Anthology TODS dblp.uni-trier.de

Principles of Database Buffer Management.

Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984)
@article{DBLP:journals/tods/EffelsbergH84,
  author    = {Wolfgang Effelsberg and
               Theo H{\"a}rder},
  title     = {Principles of Database  Buffer Management},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {4},
  year      = {1984},
  pages     = {560-595},
  ee        = {http://doi.acm.org/10.1145/1994.2022, db/journals/tods/EffelsbergH84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper discusses the implementation of a database buffer manager as a component of a DBMS. The interface between calling components of higher system layers and the buffer manager is described; the principal differences between virtual memory paging and database buffer management are outlined; the notion of referencing versus addressing of database pages is introduced; and the concept of fixing pages in the buffer to prevent uncontrolled replacement is explained.

Three basic tasks have to be performed by the buffer manager: buffer search, allocation of frames to concurrent transactions, and page replacement. For each of these tasks, implementation alternatives are discussed and illustrated by examples from a performance evaluation project of a CODASYL DBMS.

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Özalp Babaoglu, William N. Joy: Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits. SOSP 1981: 78-86 BibTeX
[2]
Laszlo A. Belady: A Study of Replacement Algorithms for Virtual-Storage Computer. IBM Systems Journal 5(2): 78-101(1966) BibTeX
[3]
Richard S. Brice, Stephen W. Sherman: An Extension of the Performance of a Database Manager in a Virtual Memory System Using Partially Locked Virtual Buffers. ACM Trans. Database Syst. 2(2): 196-207(1977) BibTeX
[4]
Richard W. Carr, John L. Hennessy: WSClock - A Simple and Effective Algorithm for Virtual Memory Management. SOSP 1981: 87-95 BibTeX
[5]
...
[6]
Peter J. Denning: The Working Set Model for Program Behaviour. Commun. ACM 11(5): 323-333(1968) BibTeX
[7]
...
[8]
Peter J. Denning: Working Sets Past and Present. IEEE Trans. Software Eng. 6(1): 64-84(1980) BibTeX
[9]
...
[10]
...
[11]
...
[12]
...
[13]
...
[14]
Tomás Lang, Christopher Wood, Eduardo B. Fernández: Database Buffer Paging in Virtual Storage Systems. ACM Trans. Database Syst. 2(4): 339-351(1977) BibTeX
[15]
Richard L. Mattson, Jan Gecsei, Donald R. Slutz, Irving L. Traiger: Evaluation Techniques for Storage Hierarchies. IBM Systems Journal 9(2): 78-117(1970) BibTeX
[16]
...
[17]
Juan Rodriguez-Rosell, Jean-Pierre Dupuy: The Design, Implementation, and Evaluation of a Working Set Dispatcher. Commun. ACM 16(4): 247-253(1973) BibTeX
[18]
...
[19]
Giovanni Maria Sacco, Mario Schkolnick: A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model. VLDB 1982: 257-262 BibTeX
[20]
Stephen W. Sherman, Richard S. Brice: Performance of a Database Manager in a Virtual Memory System. ACM Trans. Database Syst. 1(4): 317-343(1976) BibTeX
[21]
Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978) BibTeX
[22]
...
[23]
...
[24]
Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) BibTeX
[25]
William G. Tuel Jr.: An Analysis of Buffer Paging in Virtual Storage Systems. IBM J. Res. Dev. 20(5): 518-520(1976) BibTeX
[26]
Rollins Turner, William D. Strecker: Use of the LRU Stack Depth Distribution for Simulation of Paging Behavior. Commun. ACM 20(11): 795-798(1977) BibTeX

Referenced by

  1. Binto George, Jayant R. Haritsa: Secure Bufering in Firm Real-Time Database Systems. VLDB J. 8(3-4): 178-198(2000)
  2. Gerhard Weikum, Arnd Christian König, Achim Kraiss, Markus Sinnwell: Towards Self-Tuning Memory Management for Data Servers. IEEE Data Eng. Bull. 22(2): 3-11(1999)
  3. Cheng Hian Goh, Beng Chin Ooi, D. Sim, Kian-Lee Tan: GHOST: Fine Granularity Buffering of Indexes. VLDB 1999: 339-350
  4. Harald Schöning: The ADABAS Buffer Pool Manager. VLDB 1998: 675-679
  5. Binto George, Jayant R. Haritsa: Secure Buffering in Firm Real-Time Database Systems. VLDB 1998: 464-475
  6. Björn Þór Jónsson, Michael J. Franklin, Divesh Srivastava: Interaction of Query Evaluation and Buffer Management for Information Retrieval. SIGMOD Conference 1998: 118-129
  7. Boris Y. L. Chan, Antonio Si, Hong Va Leong: Cache Management for Mobile Databases: Design and Evaluation. ICDE 1998: 54-63
  8. Ling Feng, Hongjun Lu, Y. C. Tay, Anthony K. H. Tung: Buffer Management in Distributed Database Systems: A Data Mining Based Approach. EDBT 1998: 246-260
  9. Thin-Fong Tsuei, Allan Packer, Keng-Tai Ko: Database Buffer Size Investigation for OLTP Workloads (Experience Paper). SIGMOD Conference 1997: 112-122
  10. Kian-Lee Tan, Beng Chin Ooi, Tat-Seng Chua: On Video-on-Demand sSrvers with Hierarchical Storage. DASFAA 1997: 491-500
  11. Piotr Krzyzagórski, Tadeusz Morzy: Two Phase Locking-Based Algorithm with Partial Abort for Firm Deadline Real-Time Database Systems. ADBIS 1997: 40-46
  12. Peter Scheuermann, Junho Shim, Radek Vingralek: WATCHMAN : A Data Warehouse Intelligent Cache Manager. VLDB 1996: 51-62
  13. Asit Dan, Philip S. Yu, Jen-Yao Chung: Characterization of Database Access Pattern for Analytic Prediction of Buffer Hit Probability. VLDB J. 4(1): 127-154(1995)
  14. Frank Moser, Achim Kraiss, Wolfgang Klas: L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS. VLDB 1995: 275-286
  15. Alexandros Biliris, Euthimios Panagos: A High Performance Configurable Storage Manager. ICDE 1995: 35-43
  16. Theodore W. Leung: Scheduling Resource Usage in Object-Oriented Queries. DBPL 1995: 9
  17. Mohan Kamath, Krithi Ramamritham, Donald F. Towsley: Continuous Media Sharing in Multimedia Database Systems. DASFAA 1995: 79-86
  18. Alfons Kemper, Donald Kossmann: Dual-Buffering Strategies in Object Bases. VLDB 1994: 427-438
  19. Theodore Johnson, Dennis Shasha: 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994: 439-450
  20. Erhard Rahm: Empirical Performance Evaluation of Concurrency and Coherency Control Protocols for Database Sharing Systems. ACM Trans. Database Syst. 18(2): 333-377(1993)
  21. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  22. Chung-Min Chen, Nick Roussopoulos: Adaptive Database Buffer Allocation Using Query Feedback. VLDB 1993: 342-353
  23. Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum: The LRU-K Page Replacement Algorithm For Database Disk Buffering. SIGMOD Conference 1993: 297-306
  24. Asit Dan, Philip S. Yu, Jen-Yao Chung: Database Access Characterization for Buffer Hit Prediction. ICDE 1993: 134-143
  25. Hanxiong Chen, Jeffrey Xu Yu, Kazunori Yamaguchi, Hiroyuki Kitagawa, Nobuo Ohbo, Yuzuru Fujiwara: LRU-S: A New Buffer Allocation Approach for OODBMS. DASFAA 1993: 73-80
  26. 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)
  27. Chee Yong Chan, Beng Chin Ooi, Hongjun Lu: Extensible Buffer Management of Indexes. VLDB 1992: 444-454
  28. Alexandros Biliris: The Performance of Three Database Storage Structures for Managing Large Objects. SIGMOD Conference 1992: 276-285
  29. Antoine N. Mourad, W. Kent Fuchs, Daniel G. Saab: Database Recovery Using Redundant Disk Arrays. ICDE 1992: 176-183
  30. Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274
  31. Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396
  32. Marguerite C. Murphy, Ming-Chien Shan: Execution Plan Balancing. ICDE 1991: 698-706
  33. Won Kim, Jorge F. Garza, Nat Ballou, Darrell Woelk: Architecture of the ORION Next-Generation Database System. IEEE Trans. Knowl. Data Eng. 2(1): 109-124(1990)
  34. Rajiv Jauhari, Michael J. Carey, Miron Livny: Priority-Hints: An Algorithm for Priority-Based Buffer Management. VLDB 1990: 708-721
  35. Lothar F. Mackert, Guy M. Lohman: Index Scans Using a Finite LRU Buffer: A Validated I/O Model. ACM Trans. Database Syst. 14(3): 401-424(1989)
  36. Michael J. Carey, Rajiv Jauhari, Miron Livny: Priority in DBMS Resource Scheduling. VLDB 1989: 397-410
  37. Salvatore Orlando, V. Perri, S. Scrivano, Witold Staniszkis: Database Analyzer and Predictor - An Overview. ICDE 1989: 625-634
  38. Ignacio R. Casas, Kenneth C. Sevcik: A Buffer Management Model For Use In Predicting Overall Database System Performance. ICDE 1989: 463-469
  39. C. Salgado, N. Le Than, E. Vittori, J. T. Dong, G. Mopolo, Serge Miranda: The Physical Machine of NICEBD, an Object Oriented DBMS. DASFAA 1989: 359-366
  40. Andrea Sikeler: VAR-PAGE-LRU A Buffer Replacement Algorithm Supporting Different Page Sizes. EDBT 1988: 336-351
  41. Giovanni Maria Sacco: Index Access with a Finite Buffer. VLDB 1987: 301-309
  42. Theo Härder, Klaus Meyer-Wegener, Bernhard Mitschang, Andrea Sikeler: PRIMA - a DBMS Prototype Supporting Engineering Applications. VLDB 1987: 433-442
  43. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  44. Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
  45. Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)
  46. Hartmut Wedekind, Georg Zörntlein: Prefetching in Realtime Database Applications. SIGMOD Conference 1986: 215-226
  47. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
  48. George P. Copeland, Setrag Khoshafian, Marc G. Smith, Patrick Valduriez: Buffering Schemes for Permanent Data. ICDE 1986: 214-221
  49. Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141
  50. Andreas Reuter: Performance Analysis of Recovery Techniques. ACM Trans. Database Syst. 9(4): 526-559(1984)
  51. Wolfgang Effelsberg, Mary E. S. Loomis: Logical, Internal, and Physical Reference Behavior in CODASYL Database Systems. ACM Trans. Database Syst. 9(2): 187-213(1984)
  52. Peter Peinl, Andreas Reuter: Empirical Comparison of Database Concurrency Schemes. VLDB 1983: 97-108
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:55 2008