An Evaluation of Buffer Management Strategies for Relational Database Systems.

Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141
  author    = {Hong-Tai Chou and
               David J. DeWitt},
  editor    = {Alain Pirotte and
               Yannis Vassiliou},
  title     = {An Evaluation of Buffer Management Strategies for Relational
               Database Systems},
  booktitle = {VLDB'85, Proceedings of 11th International Conference on Very
               Large Data Bases, August 21-23, 1985, Stockholm, Sweden},
  publisher = {Morgan Kaufmann},
  year      = {1985},
  pages     = {127-141},
  ee        = {db/conf/vldb/ChouD85.html},
  crossref  = {DBLP:conf/vldb/85},
  bibsource = {DBLP,}


In this paper we present a new algorithm, DBMIN, for managing the buffer pool of a relational database manaegememt system. DBMIN is based on a new model of relational query behavior, the query locality set model (QLSM). Like the hot set model, the QLSM has an advantage over the stochastic models due to its ability to predict future reference hehavior. However, the QLSM avoids the potential problems of the hot set model by separating the modeling of referr- ence bahavior from any particular buffer management algorithm.After introducing the QLSM and describing the DBMIN algorithm, we present a performance evaluation methodology for evaluating buffer manage- ment algorithms in a multiuser environment. This methodology employed a hybrid model that comhines features of both trace driven and distribution driven simulation models. Using this model the performance of the DBMIN algorithm in a multiuser environment is compared with that of the hot set algorithm and four more traditional buffer replacement algorithms.

Copyright © 1985 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Alain Pirotte, Yannis Vassiliou (Eds.): VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden. Morgan Kaufmann 1985
Contents BibTeX


Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
Haran Boral, David J. DeWitt: A Methodology for Database System Performance Evaluation. SIGMOD Conference 1984: 176-185 BibTeX
Hong-Tai Chou, David J. DeWitt, Randy H. Katz, Anthony C. Klug: Design and Implementation of the Wisconsin Storage System. Softw., Pract. Exper. 15(10): 943-962(1985) BibTeX
David J. DeWitt, Raphael A. Finkel, Marvin H. Solomon: The Crystal Multicomputer: Design and Implementation Experience. IEEE Trans. Software Eng. 13(8): 953-966(1987) BibTeX
Peter J. Denning, Kevin C. Kahn, Jacques Leroudier, Dominique Potier, Rajan Suri: Optimal Multiprogramming. Acta Inf. 7: 197-216(1976) BibTeX
Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) BibTeX
Eduardo B. Fernández, Tomás Lang, Christopher Wood: Effect of Replacement Algorithms on a Paged Buffer Database System. IBM J. Res. Dev. 22(2): 185-196(1978) BibTeX
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
Holger Opderbeck, Wesley W. Chu: Performance of the Page Fault Frequency Replacement Algorithm in a Multiprogramming Environment. IFIP Congress 1974: 235-241 BibTeX
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
Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986) BibTeX
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
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) BibTeX
Michael Stonebraker, John Woodfill, Jeff Ranstrom, Marguerite C. Murphy, Marc Meyer, Eric Allman: Performance Enhancements to a Relational Database System. ACM Trans. Database Syst. 8(2): 167-185(1983) BibTeX
William G. Tuel Jr.: An Analysis of Buffer Paging in Virtual Storage Systems. IBM J. Res. Dev. 20(5): 518-520(1976) BibTeX
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(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. Cheng Hian Goh, Beng Chin Ooi, D. Sim, Kian-Lee Tan: GHOST: Fine Granularity Buffering of Indexes. VLDB 1999: 339-350
  3. Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: A Highly Effective Partition Selection Policy for Object Database Garbage Collection. IEEE Trans. Knowl. Data Eng. 10(1): 153-172(1998)
  4. Binto George, Jayant R. Haritsa: Secure Buffering in Firm Real-Time Database Systems. VLDB 1998: 464-475
  5. Jun Rao, Kenneth A. Ross: Reusing Invariants: A New Strategy for Correlated Queries. SIGMOD Conference 1998: 37-48
  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. 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
  8. Thin-Fong Tsuei, Allan Packer, Keng-Tai Ko: Database Buffer Size Investigation for OLTP Workloads (Experience Paper). SIGMOD Conference 1997: 112-122
  9. Silvio Salza, Massimiliano Renzetti: A Modeling Tool for Workload Analysis and Performance Tuning of Parallel Database Applications. ADBIS 1997: 152-161
  10. Peter Scheuermann, Junho Shim, Radek Vingralek: WATCHMAN : A Data Warehouse Intelligent Cache Manager. VLDB 1996: 51-62
  11. Sunita Sarawagi, Michael Stonebraker: Reordering Query Execution in Tertiary Memory Databases. VLDB 1996: 156-167
  12. Kurt P. Brown, Michael J. Carey, Miron Livny: Goal-Oriented Buffer Management Revisited. SIGMOD Conference 1996: 353-364
  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. Nick Roussopoulos, Chung-Min Chen, Stephen Kelley, Alex Delis, Yannis Papakonstantinou: The ADMS Project: View R Us. IEEE Data Eng. Bull. 18(2): 19-28(1995)
  15. Kun-Lung Wu, Philip S. Yu, Jen-Yao Chung, James Z. Teng: A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System. VLDB 1995: 100-109
  16. 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
  17. Theodore W. Leung: Scheduling Resource Usage in Object-Oriented Queries. DBPL 1995: 9
  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. Jonathan E. Cook, Alexander L. Wolf, Benjamin G. Zorn: Partition Selection Policies in Object Database Garbage Collection. SIGMOD Conference 1994: 371-382
  21. Kun-Lung Wu, Philip S. Yu, James Z. Teng: Data Placement and Buffer Management for Concurrent Mergesorts with Parallel Prefetching. ICDE 1994: 418-427
  22. Philip S. Yu, Douglas W. Cornell: Buffer Management Based on Return on Consumption in a Multi-Query Environment. VLDB J. 2(1): 1-37(1993)
  23. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  24. Manish Mehta, David J. DeWitt: Dynamic Memory Allocation for Multiple-Query Workloads. VLDB 1993: 354-367
  25. Chung-Min Chen, Nick Roussopoulos: Adaptive Database Buffer Allocation Using Query Feedback. VLDB 1993: 342-353
  26. Kurt P. Brown, Michael J. Carey, Miron Livny: Managing Memory to Meet Multiclass Workload Response Time Goals. VLDB 1993: 328-341
  27. 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
  28. Asit Dan, Philip S. Yu, Jen-Yao Chung: Database Access Characterization for Buffer Hit Prediction. ICDE 1993: 134-143
  29. 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
  30. Axel Mönkeberg, Gerhard Weikum: Performance Evaluation of an Adaptive and Robust Load Control Method for the Avoidance of Data-Contention Thrashing. VLDB 1992: 432-443
  31. Alex Delis, Nick Roussopoulos: Performance and Scalability of Client-Server Database Architectures. VLDB 1992: 610-623
  32. Chee Yong Chan, Beng Chin Ooi, Hongjun Lu: Extensible Buffer Management of Indexes. VLDB 1992: 444-454
  33. Anant Jhingran, Pratap Khedkar: Analysis of Recovery in a Database System Using a Write-Ahead Log Protocol. SIGMOD Conference 1992: 175-184
  34. Mark Palmer, Stanley B. Zdonik: Fido: A Cache That Learns to Fetch. VLDB 1991: 255-264
  35. Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274
  36. Michael Stonebraker: Managing Persistent Objects in a Multi-Level Store. SIGMOD Conference 1991: 2-11
  37. Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396
  38. Le Gruenwald, Margaret H. Eich: MMDB Reload Algorithms. SIGMOD Conference 1991: 397-405
  39. Philip S. Yu, Douglas W. Cornell: Optimal Buffer Allocation in A Multi-Query Environment. ICDE 1991: 622-631
  40. Marguerite C. Murphy, Ming-Chien Shan: Execution Plan Balancing. ICDE 1991: 698-706
  41. Pyung-Chul Kim, Hwan-Ik Choi, Yoon-Joon Lee, Myung-Joon Kim: Design and Implementation of the Multiuser Index-based Data Access System. DASFAA 1991: 156-164
  42. Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990)
  43. Rajiv Jauhari, Michael J. Carey, Miron Livny: Priority-Hints: An Algorithm for Priority-Based Buffer Management. VLDB 1990: 708-721
  44. Michael J. Carey, Sanjay Krishnamurthi, Miron Livny: Load Control for Locking: The 'Half-and-Half' Approach. PODS 1990: 72-84
  45. Hongjun Lu, Kian-Lee Tan: Buffer and Load Balancing in Locally Distributed Database Systems. ICDE 1990: 545-552
  46. 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)
  47. Jaideep Srivastava, Jack S. Eddy Tan, Vincent Y. Lum: TBSAM: An Access Method for Efficient Processing of Statistical Queries. IEEE Trans. Knowl. Data Eng. 1(4): 414-423(1989)
  48. Douglas W. Cornell, Philip S. Yu: Integration of Buffer Management and Query Optimization in Relational Database Environment. VLDB 1989: 247-255
  49. Michael J. Carey, Rajiv Jauhari, Miron Livny: Priority in DBMS Resource Scheduling. VLDB 1989: 397-410
  50. Ignacio R. Casas, Kenneth C. Sevcik: A Buffer Management Model For Use In Predicting Overall Database System Performance. ICDE 1989: 463-469
  51. Giovanni Maria Sacco: Index Access with a Finite Buffer. VLDB 1987: 301-309
  52. Timos K. Sellis: Efficiently Supporting Procedures in Relational Database Systems. SIGMOD Conference 1987: 278-291
  53. James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409
  54. Joel E. Richardson, Michael J. Carey: Programming Constructs for Database System Implementation in EXODUS. SIGMOD Conference 1987: 208-219
  55. Masaru Kitsuregawa, Miyuki Nakano, Lilian Harada, Mikio Takagi: Functional Disk System for Relational Database. ICDE 1987: 88-95
  56. Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)
  57. Louiqa Raschid, Stanley Y. W. Su: A Parallel Processing Strategy for Evaluating Recursive Queries. VLDB 1986: 412-419
  58. Robert B. Hagmann: An Observation on Database Buffering Performance Metrics. VLDB 1986: 289-293
  59. 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
  60. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
  61. Stanley Y. W. Su, Krishna P. Mikkilineni, Raymond A. Liuzzi, Yuan-Chieh Chow: A Distributed Query Processing Strategy Using Decomposition, Pipelining and Intermediate Result Sharing Techniques. ICDE 1986: 94-102
  62. George P. Copeland, Setrag Khoshafian, Marc G. Smith, Patrick Valduriez: Buffering Schemes for Permanent Data. ICDE 1986: 214-221
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:27 2009