ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

The LRU-K Page Replacement Algorithm For Database Disk Buffering.

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
@inproceedings{DBLP:conf/sigmod/ONeilOW93,
  author    = {Elizabeth J. O'Neil and
               Patrick E. O'Neil and
               Gerhard Weikum},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {The LRU-K Page Replacement Algorithm For Database Disk Buffering},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {297-306},
  ee        = {http://doi.acm.org/10.1145/170035.170081, db/conf/sigmod/ONeilOW93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper introduces a new approach to database disk buffering, called the LRU-K method. The basic idea of LRU-K is to keep track of the times of the last K references to popular database pages, using this information to statistcally estimate the interarrival times of references on a page by page basis. Although the LRU-K approach performs optimal statistical inference under relatively standard assumptions, it is faily simple and incurs little bookkeeping overhead. As we demonstrate with simulation experiments, the LRU-K algorithm surpasses conventional buffering algorithms in discriminating between frequently and infrequently referenced pages. In fact, LRU-K can approach the behavior of buffering algorithms in which page sets with known access frequencies are manually assigned to different buffer pools of specifically tuned sizes. Unlike such customized buffering algorithms however, the LRU-K method is self-tuning, and does not rely on external hints about workload characteristics. Furthermore, the LRU-K algorithm adapts in real time to changing patterns of access.

Copyright © 1993 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]

References

[ABG]
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
[ADU]
Alfred V. Aho, Peter J. Denning, Jeffrey D. Ullman: Principles of Optimal Page Replacement. J. ACM 18(1): 80-93(1971) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHAKA]
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
[CHOUDEW]
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
[CKS]
...
[COL]
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
[COFFDENN]
Edward G. Coffman Jr., Peter J. Denning: Operating Systems Theory. Prentice-Hall 1973
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DANTOWS]
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
[DENNING]
Peter J. Denning: The Working Set Model for Program Behaviour. Commun. ACM 11(5): 323-333(1968) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EFFEHAER]
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
[FNS]
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
[GRAYPUT]
Jim Gray, Gianfranco R. Putzolu: The 5 Minute Rule for Trading Memory for Disk Accesses and The 10 Byte Rule for Trading Memory for CPU Time. SIGMOD Conference 1987: 395-398 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HAAS]
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
[JCL]
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
[KNUTH]
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
[NFS]
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
[OOW]
...
[PAZDO]
Mark Palmer, Stanley B. Zdonik: Fido: A Cache That Learns to Fetch. VLDB 1991: 255-264 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[REITER]
...
[ROBDEV]
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
[SACSCH]
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
[SHASHA]
Dennis Shasha: Database Tuning - A Principled Approach. Prentice-Hall 1992, ISBN 0-13-205246-6
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STON]
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
[TENGGUM]
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
[TPC-A]
...
[YUCORN]
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 © Fri Mar 12 17:21:30 2010 by Michael Ley (ley@uni-trier.de)