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

@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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

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)

[2]

...

[3]

Chee Yong Chan, Beng Chin Ooi, Hongjun Lu: Extensible Buffer Management of Indexes. VLDB 1992: 444-454

[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

[5]

Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141

[6]

Edward G. Coffman Jr., Peter J. Denning: Operating Systems Theory. Prentice-Hall 1973

[7]

Asit Dan, Donald F. Towsley: An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152

[8]

Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984)

[9]

Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274

[10]

Rajiv Jauhari, Michael J. Carey, Miron Livny: Priority-Hints: An Algorithm for Priority-Based Buffer Management. VLDB 1990: 708-721

[11]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X

[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)

[13]

Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396

[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

[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

[16]

...

[17]

John T. Robinson, Murthy V. Devarakonda: Data Cache Management Using Frequency-Based Replacement. SIGMETRICS 1990: 134-142

[18]

Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)

[19]

Daniel Dominic Sleator, Robert Endre Tarjan: Amortized Efficiency of List Update and Paging Rules. Commun. ACM 28(2): 202-208(1985)

[20]

Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978)

[21]

Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981)

[22]

James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984)

[23]

Philip S. Yu, Douglas W. Cornell: Optimal Buffer Allocation in A Multi-Query Environment. ICDE 1991: 622-631