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.
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 
,
SIGMOD Record 22(2),
June 1993
Contents
[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)
- [ADU]
- Alfred V. Aho, Peter J. Denning, Jeffrey D. Ullman:
Principles of Optimal Page Replacement.
J. ACM 18(1): 80-93(1971)
- [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
- [CHOUDEW]
- Hong-Tai Chou, David J. DeWitt:
An Evaluation of Buffer Management Strategies for Relational Database Systems.
VLDB 1985: 127-141
- [CKS]
- ...
- [COL]
- Chee Yong Chan, Beng Chin Ooi, Hongjun Lu:
Extensible Buffer Management of Indexes.
VLDB 1992: 444-454
- [COFFDENN]
- Edward G. Coffman Jr., Peter J. Denning:
Operating Systems Theory.
Prentice-Hall 1973
- [DANTOWS]
- Asit Dan, Donald F. Towsley:
An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes.
SIGMETRICS 1990: 143-152
- [DENNING]
- Peter J. Denning:
The Working Set Model for Program Behaviour.
Commun. ACM 11(5): 323-333(1968)
- [EFFEHAER]
- Wolfgang Effelsberg, Theo Härder:
Principles of Database Buffer Management.
ACM Trans. Database Syst. 9(4): 560-595(1984)
- [FNS]
- Christos Faloutsos, Raymond T. Ng, Timos K. Sellis:
Predictive Load Control for Flexible Buffer Allocation.
VLDB 1991: 265-274
- [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
- [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)
- [JCL]
- Rajiv Jauhari, Michael J. Carey, Miron Livny:
Priority-Hints: An Algorithm for Priority-Based Buffer Management.
VLDB 1990: 708-721
- [KNUTH]
- Donald E. Knuth:
The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley 1973, ISBN 0-201-03803-X
- [NFS]
- Raymond T. Ng, Christos Faloutsos, Timos K. Sellis:
Flexible Buffer Allocation Based on Marginal Gains.
SIGMOD Conference 1991: 387-396
- [OOW]
- ...
- [PAZDO]
- Mark Palmer, Stanley B. Zdonik:
Fido: A Cache That Learns to Fetch.
VLDB 1991: 255-264
- [REITER]
- ...
- [ROBDEV]
- John T. Robinson, Murthy V. Devarakonda:
Data Cache Management Using Frequency-Based Replacement.
SIGMETRICS 1990: 134-142
- [SACSCH]
- Giovanni Maria Sacco, Mario Schkolnick:
Buffer Management in Relational Database Systems.
ACM Trans. Database Syst. 11(4): 473-498(1986)
- [SHASHA]
- Dennis Shasha:
Database Tuning - A Principled Approach.
Prentice-Hall 1992, ISBN 0-13-205246-6
Contents - [STON]
- Michael Stonebraker:
Operating System Support for Database Management.
Commun. ACM 24(7): 412-418(1981)
- [TENGGUM]
- James Z. Teng, Robert A. Gumaer:
Managing IBM Database 2 Buffers to Maximize Performance.
IBM Systems Journal 23(2): 211-218(1984)
- [TPC-A]
- ...
- [YUCORN]
- Philip S. Yu, Douglas W. Cornell:
Optimal Buffer Allocation in A Multi-Query Environment.
ICDE 1991: 622-631
Copyright © Fri Mar 12 17:21:30 2010
by Michael Ley (ley@uni-trier.de)
