ACM SIGMOD Anthology VLDB dblp.uni-trier.de

2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm.

Theodore Johnson, Dennis Shasha: 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994: 439-450
@inproceedings{DBLP:conf/vldb/JohnsonS94,
  author    = {Theodore Johnson and
               Dennis Shasha},
  editor    = {Jorge B. Bocca and
               Matthias Jarke and
               Carlo Zaniolo},
  title     = {2Q: A Low Overhead High Performance Buffer Management Replacement
               Algorithm},
  booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
               Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
  publisher = {Morgan Kaufmann},
  year      = {1994},
  isbn      = {1-55860-153-8},
  pages     = {439-450},
  ee        = {db/conf/vldb/vldb94-439.html},
  crossref  = {DBLP:conf/vldb/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In a path-breaking paper last year Pat and Betty O'Neil and Gerhard Weikum proposed a self-tuning improvement to the Least Recently Used (LRU) buffer management algorithm [OOW93]. Their improvement is called LRU/k and advocates giving priority to buffer pages based on the kth most recent access. (The standard LRU algorithm is denoted LRU/1 according to this terminology.) If P1's kth most recent access is more recent than P2's, then P1 will be replaced after P2. Intuitively, LRU/k for k > 1 is a good strategy, because it gives low priority to pages that have been scanned or to pages that belong to a big randomly accessed file (e.g., the account file in TPC/A). They found that LRU/2 achieves most of the advantage of their method.

The one problem of LRU/2 is the processor overhead to implement it. In contrast to LRU, each page access requires log N work to manipulate a priority queue where N is the number of pages in the buffer.

Question: is there a low overhead way (constant overhead per access as in LRU) to achieve similar page replacement performance to LRU/2?

Answer: Yes.

Our "Two Queue" algorithm (hereafter 2Q) has constant time overhead, performs as well as LRU/2, and requires no tuning. These results hold for real (DB2 commercial, Swiss bank) traces as well as simulated ones. Based on these experiments, we estimate that 2Q will provide a few percent improvement over LRU without increasing the overhead by more than a constant additive factor.

Copyright © 1994 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 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.): VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile. Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Rafael Alonso, Daniel Barbará, Hector Garcia-Molina: Data Caching Issues in an Information Retrieval System. ACM Trans. Database Syst. 15(3): 359-384(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
...
[3]
Chee Yong Chan, Beng Chin Ooi, Hongjun Lu: Extensible Buffer Management of Indexes. VLDB 1992: 444-454 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Ellis E. Chang, Randy H. Katz: Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS. SIGMOD Conference 1989: 348-357 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Edward G. Coffman Jr., Peter J. Denning: Operating Systems Theory. Prentice-Hall 1973
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Asit Dan, Donald F. Towsley: An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Rajiv Jauhari, Michael J. Carey, Miron Livny: Priority-Hints: An Algorithm for Priority-Based Buffer Management. VLDB 1990: 708-721 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Victor F. Nicola, Asit Dan, Daniel M. Dias: Analysis of the Generalized Clock Buffer Replacement Scheme for Database Transaction Processing. SIGMETRICS 1992: 35-46 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
...
[17]
John T. Robinson, Murthy V. Devarakonda: Data Cache Management Using Frequency-Based Replacement. SIGMETRICS 1990: 134-142 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Daniel Dominic Sleator, Robert Endre Tarjan: Amortized Efficiency of List Update and Paging Rules. Commun. ACM 28(2): 202-208(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Philip S. Yu, Douglas W. Cornell: Optimal Buffer Allocation in A Multi-Query Environment. ICDE 1991: 622-631 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:04 2010 by Michael Ley (ley@uni-trier.de)