research-article

Flexible and Adaptable Buffer Management Techniques for Database Management Systems

Authors:

Christos Faloutsos,

Timos SellisAuthors Info & Claims

IEEE Transactions on Computers, Volume 44, Issue 4

Pages 546 - 560

https://doi.org/10.1109/12.376169

Published: 01 April 1995 Publication History

Abstract

The problem of buffer management in database management systems is concerned with the efficient main memory allocation and management for answering database queries. Previous works on buffer allocation are based either exclusively on the availability of buffers at runtime or on the access patterns of queries. In this paper, we first propose a unified approach for buffer allocation in which both of these considerations are taken into account. Our approach is based on the notion of marginal gains which specify the expected reduction in page faults by allocating extra buffers to a query. Then, we extend this approach to support adaptable buffer allocation. An adaptable buffer allocation algorithm automatically optimizes itself for the specific query workload. To achieve this adaptability, we propose using run-time information, such as the load of the system, in buffer allocation decisions. Our approach is to use a simple queuing model to predict whether a buffer allocation will improve the performance of the system. Thus, this paper provides a more theoretical basis for buffer allocation. Simulation results show that our methods based on marginal gains and our predictive methods consistently outperform existing allocation strategies. In addition, the predictive methods have the added advantage of adjusting their allocation to changing workloads.

References

[1]

A.F. Cardenas, “Analysis and performance of inverted data base structures,” Comm. of the ACM, vol. 18, no. 5, 1975.

Digital Library

[2]

H. Chou, “Buffer management of database systems,” Computer Sciences Technical Report 597, Univ. of Wisconsin, Madison, 1985.

[3]

H. Chou and D. DeWitt, “An evaluation of buffer management strategies forrelational database systems,” Proc. 11<sup>th</sup> Int’l Conf. Very Large Data Bases, 1985.

[4]

S. Christodoulakis, “Implication of certain assumptions in data baseperformance evaluation,” ACM Trans. Database Systems, vol. 9, no. 2, 1984.

Digital Library

[5]

D. Cornell and P. Yu, “Integration of buffer management and queryoptimization in relational database environment,” Proc. 15<sup>th</sup> Int’l Conf.Very Large Data Bases, 1989.

Digital Library

[6]

W. Effelsberg and T. Haerder, “Principles of Database Buffer Management,” ACM Trans. Database Systems, vol. 9, no. 4, 1984.

Digital Library

[7]

C. Faloutsos, R. Ng, and T. Sellis,., “Predictive load control for Flexiblebuffer allocation,” Proc. 17<sup>th</sup> Int’l Conf. Very Large Data Bases, pp. 265-274, 1991.

Digital Library

[8]

J. Kaplan, “Buffer management policies in a database environment,” Master thesis, Univ. of California, Berkeley, 1980.

[9]

E. Kauder, History of Marginal Utility Theory, Princeton, NJ: Princeton Univ. Press, 1965.

[10]

T. Lang, C. Wood, and E. Fernandez, “Database buffer paging in virtualstorage systems,” ACM Trans. Database Systems, vol. 2, no. 4, 1977.

Digital Library

[11]

R. Mattson, J. Gecsei, D. Slutz, and I. Traiger, “Evaluation techniques forstorage hierarchies,” IBM Systems Journal, vol. 9, no. 2, 1970.

Digital Library

[12]

R. Ng, C. Faloutsos, and T. Sellis, “Flexible buffer allocation based onmarginal gains,” Proc. ACM SIGMOD Int’l Conf., Management of Data, pp. 387-396, 1991.

Digital Library

[13]

G. Sacca and M. Schkolnick, “A mechanism for managing the buffer pool in arelational database system using the hot set model,” Proc. Eighth Int’l Conf. Very Large Data Bases, 1982.

Digital Library

[14]

G. Sacca and M. Schkolnick, “Buffer Management in Relational Database Systems,” ACM Trans. Database Systems, vol. 11, no. 4, 1986.

Digital Library

[15]

S. Sherman and R. Brice, “Performance of a database manager in a virtualmemory system,” ACM Trans. Database Systems, vol. 1, no. 4, 1976.

Digital Library

[16]

M. Stonebraker, E. Wong, and P. Kreps, “The design and implementation of INGRES,” ACM Trans. Database Systems, vol. 1, no. 3, 1976.

Digital Library

[17]

K.S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer ScienceApplications, Englewood Cliffs, NJ: Prentice Hall, Inc., 1982.

Digital Library

[18]

S. Yao, “Approximating block accesses in database organizations,” Comm. of the ACM, vol. 20, no. 4, 1977.

Digital Library

Cited By

Lee EBahn H(2014)Caching Strategies for High-Performance Storage MediaACM Transactions on Storage10.1145/263369110:3(1-22)Online publication date: 7-Aug-2014
https://dl.acm.org/doi/10.1145/2633691
Schmidt KBächle S(2012)Low-overhead decision support for dynamic buffer reallocationComputer Science - Research and Development10.1007/s00450-011-0175-z27:1(29-43)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s00450-011-0175-z
Tran DHuynh PTay YTung A(2008)A new approach to dynamic self-tuning of database buffersACM Transactions on Storage10.1145/1353452.13534554:1(1-25)Online publication date: 28-May-2008
https://dl.acm.org/doi/10.1145/1353452.1353455
Show More Cited By

Recommendations

An optimal lower bound for buffer management in multi-queue switches
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value ...
High-speed buffer management for 40 Gb/s-based photonic packet switches

We develop a method of high-speed buffer management for output-buffered photonic packet switches. The use of optical fiber delay lines is a promising solution to constructing optical buffers. The buffer manager determines packet delays in the fiber ...
Comparison-Based Buffer Management in QoS Switches

The following online problem arises in network devices, e.g., switches, with quality of service (QoS) guarantees. In each time step, an arbitrary number of packets arrive at a single buffer and only one packet can be transmitted. The differentiated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 44, Issue 4

April 1995

131 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © Copyright © 1995 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 April 1995

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee EBahn H(2014)Caching Strategies for High-Performance Storage MediaACM Transactions on Storage10.1145/263369110:3(1-22)Online publication date: 7-Aug-2014
https://dl.acm.org/doi/10.1145/2633691
Schmidt KBächle S(2012)Low-overhead decision support for dynamic buffer reallocationComputer Science - Research and Development10.1007/s00450-011-0175-z27:1(29-43)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s00450-011-0175-z
Tran DHuynh PTay YTung A(2008)A new approach to dynamic self-tuning of database buffersACM Transactions on Storage10.1145/1353452.13534554:1(1-25)Online publication date: 28-May-2008
https://dl.acm.org/doi/10.1145/1353452.1353455
Gniady CButt AHu Y(2004)Program-counter-based pattern classification in buffer cachingProceedings of the 6th conference on Symposium on Operating Systems Design & Implementation - Volume 610.5555/1251254.1251281(27-27)Online publication date: 6-Dec-2004
https://dl.acm.org/doi/10.5555/1251254.1251281
Doyle RChase JAsad OJin WVahdat A(2003)Model-based resource provisioning in a web service utilityProceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems - Volume 410.5555/1251460.1251465(5-5)Online publication date: 26-Mar-2003
https://dl.acm.org/doi/10.5555/1251460.1251465
Choi JNoh SMin SHa ECho Y(2002)Design, Implementation, and Performance Evaluation of a Detection-Based Adaptive Block Replacement SchemeIEEE Transactions on Computers10.1109/TC.2002.101769951:7(793-800)Online publication date: 1-Jul-2002
https://dl.acm.org/doi/10.1109/TC.2002.1017699
Lee DChoi JKim JNoh SMin SCho YKim C(2001)LRFUIEEE Transactions on Computers10.1109/TC.2001.97057350:12(1352-1361)Online publication date: 1-Dec-2001
https://dl.acm.org/doi/10.1109/TC.2001.970573
Leung HFeng LLi Q(2000)Analysis of Distributed Database Access Histories for Buffer AllocationProceedings of the First International Conference on Web Information Systems Engineering (WISE'00)-Volume 2 - Volume 210.5555/882512.885418Online publication date: 19-Jun-2000
https://dl.acm.org/doi/10.5555/882512.885418
Wang WBunt R(2000)Simulating DB2 buffer pool managementProceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research10.5555/782034.782047Online publication date: 13-Nov-2000
https://dl.acm.org/doi/10.5555/782034.782047
Kim JChoi JKim JNoh SMin SCho YKim C(2000)A low-overhead high-performance unified buffer management scheme that exploits sequential and looping referencesProceedings of the 4th conference on Symposium on Operating System Design & Implementation - Volume 410.5555/1251229.1251238Online publication date: 22-Oct-2000
https://dl.acm.org/doi/10.5555/1251229.1251238
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents