Index Access with a Finite Buffer.

@inproceedings{DBLP:conf/vldb/Sacco87,
  author    = {Giovanni Maria Sacco},
  editor    = {Peter M. Stocker and
               William Kent and
               Peter Hammersley},
  title     = {Index Access with a Finite Buffer},
  booktitle = {VLDB'87, Proceedings of 13th International Conference on Very
               Large Data Bases, September 1-4, 1987, Brighton, England},
  publisher = {Morgan Kaufmann},
  year      = {1987},
  isbn      = {0-934613-46-X},
  pages     = {301-309},
  ee        = {db/conf/vldb/Sacco87.html},
  crossref  = {DBLP:conf/vldb/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A buffer is a main-memory area used to reduce access to disks. The buffer holds pages from secondary storage files. A process requesting a page causes a fault if the page is not in the buffer: the requested page is read into the buffer. If no buffer space is available, a page in the buffer is replaced by the requested one.

The solution of many relational queries (e.g. joins) require the repeated access of a relation through a unique clustered index. The fault rate of such queries as a function of the available buffer size is analyzed. A B-tree structure is assumed, but the results presented here carry over to most other hierarchical index structures.

It is shown that the LRU replacement strategy, commonly used with this type of access, is not the best strategy. Two alternative strategies, ILRU and OLRU, are proposed. ILRU is shown to be always better than LRU, especially for small buffer sizes and independently of the probability of page references. OLRU is proved to be optimal under the assumption of a uniform distribution of page reference densities. The behaviour of LRU and OLRU under distributions that violate this assumption (such as Zipfian distributions) is discussed.

Copyright © 1987 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/vldb7588 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

[BAYE72]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)

[BERN81]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)

[CHOU85]

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

[COME79]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)

[EFFE84]

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

[FRAN74]

Peter A. Franaszek, T. J. Wagner: Some Distribution-Free Aspects of Paging Algorithm Performance. J. ACM 21(1): 31-39(1974)

[KNUT73]

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

[IJBE85]

Alle IJbema, Henk M. Blanken: Estimating Bucket Accesses: A Practical Approach. ICDE 1986: 30-37

[MATT70]

...

[SACC82]

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

[SACC83]

...

[SACC86]

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

[WHAN83]

Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula. Commun. ACM 26(11): 940-944(1983)

[YAO77]

S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)

[ZIPF49]

George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949