ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Buffer management in relational database systems
Full text pdf formatPdf (1.97 MB)
Source ACM Transactions on Database Systems (TODS) archive
Volume 11 ,  Issue 4  (December 1986) table of contents
Pages: 473 - 498  
Year of Publication: 1986
ISSN:0362-5915
Authors
Giovanni Maria Sacco  Univ. of Torino, Turin, Italy
Mario Schkolnick  IBM T. J. Watson Research Center, Yorktown Heights, NY
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 6,   Downloads (12 Months): 190,   Citation Count: 37
Additional Information:

abstract   references   cited by   index terms   review   collaborative colleagues   peer to peer  

Tools and Actions: Review this Article  
Save this Article to a Binder    Display Formats: BibTex  EndNote ACM Ref   
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/7239.7336
What is a DOI?

ABSTRACT

The hot-set model, characterizing the buffer requirements of relational queries, is presented. This model allows the system to determine the optimal buffer space to be allocated to a query; it can also be used by the query optimizer to derive efficient execution plans accounting for the available buffer space, and by a query scheduler to prevent thrashing. The hot-set model is compared with the working-set model. A simulation study is presented.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976  [doi>10.1145/320455.320457]
 
2
BAYER, R. Database system design for high performance. In Information Processing 83, Mason, Ed. Elsevier North-Holland, New York, 1983, 147-155.
 
3
BAYER, R., AND MCCREIGHT, C. Organization and maintenance of large ordered indexes. Acta Inf. I, 3 (1972), 173-189.
4
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 Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981  [doi>10.1145/319628.319650]
 
5
BLASGEN, M. W., AND ESWARAN, K.P. Storage access in relational databases. IBM Syst. J. 16 (1977).
6
Haran Boral , David J DeWitt, A methodology for database system performance evaluation, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
 
7
CHAMBERLIN, D. Do, ET AL. Sequel 2: A unified approach to data definition, manipulation, and control. IBM J. Res. Dev. 20, 6 (1976).
 
8
CHOU, H., AND DEWITT, D.J. An evaluation of buffer management strategies for relational database systems. In Proceedings of the l Ith Conference on Very Large Data Bases (Stockholm, 1985), 127-141.
9
S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984  [doi>10.1145/329.318578]
10
E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970  [doi>10.1145/362384.362685]
 
11
Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
12
Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979  [doi>10.1145/356770.356776]
13
Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968  [doi>10.1145/363095.363141]
14
Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984  [doi>10.1145/1994.2022]
15
Wolfgang Effelsberg , Mary E. S. Loomis, Logical, internal, and physical reference behavior in CODASYL database systems, ACM Transactions on Database Systems (TODS), v.9 n.2, p.187-213, June 1984  [doi>10.1145/329.331]
 
16
FERNANDEZ, E. B., ET AL. Effect of replacement algorithms on a paged buffer database system. IBM J. Res. Dev. 22, 2 (1978), 185-196.
 
17
GHANEM, M.Z. Dynamic partitioning of the main memory using the working set concept. IBM J. Res. Dev. {1975), 445-450.
 
18
Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
 
19
KAPLAN, J. Buffer management policies in a database system. M.S. thesis, Univ. of California, Berkeley, 1980.
20
Won Kim, A new way to compute the product and join of relations, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California  [doi>10.1145/582250.582278]
 
21
Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
22
Tomás Lang , Christopher Wood , Eduardo B. Fernández, Database buffer paging in virtual storage systems, ACM Transactions on Database Systems (TODS), v.2 n.4, p.339-351, Dec. 1977  [doi>10.1145/320576.320585]
23
Raymond A. Lorie, Physical integrity in a large segmented database, ACM Transactions on Database Systems (TODS), v.2 n.1, p.91-104, March 1977  [doi>10.1145/320521.320540]
24
W. S. Luk, On estimating block accesses in database organizations, Communications of the ACM, v.26 n.11, p.945-947, Nov. 1983  [doi>10.1145/182.358456]
 
25
MATTSON, R. L., ET AL. Evaluation strategies for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
 
26
OBERMARK, R. Global deadlock detection algorithms. IBM Res. Rep. RJ2845, 1980.
27
David D. Redell , Yogen K. Dalal , Thomas R. Horsley , Hugh C. Lauer , William C. Lynch , Paul R. McJones , Hal G. Murray , Stephen C. Purcell, Pilot: an operating system for a personal computer, Communications of the ACM, v.23 n.2, p.81-92, Feb. 1980  [doi>10.1145/358818.358822]
 
28
SAcco, G.M. Fragmentation: A technique for efficient query processing. TR 20/11/82, Dip. Informatica, Univ. of Torino, Turin, Nov. 20, 1982 (revised: Aug. 26, 1983).
29
Giovanni Maria Sacco, Fragmentation: a technique for efficient query processing, ACM Transactions on Database Systems (TODS), v.11 n.2, p.113-133, June 1986  [doi>10.1145/5922.5638]
 
30
SACCO, G. M., AND BALBO, G. On the estimation of join result cardinalities. TR 24/2/83, Dip. Informatica, Univ. Torino, Turin, Feb. 24, 1983.
 
31
Giovanni Maria Sacco , Mario Schkolnick, A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model, Proceedings of the 8th International Conference on Very Large Data Bases, p.257-262, September 08-10, 1982
 
32
SACCO, G. M., AND SCHKOLNICK, M. Thrashing reduction in demand accessing of a data base through an LRU paging buffer pool. U.S. Patent 4.422.145, Dec. 20, 1983.
33
P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts  [doi>10.1145/582095.582099]
34
Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976  [doi>10.1145/320473.320476]
35
Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981  [doi>10.1145/358699.358703]
36
Kyu-Young Whang , Gio Wiederhold , Daniel Sagalowicz, Estimating block accesses in database organizations: a closed noniterative formula, Communications of the ACM, v.26 n.11, p.940-944, Nov. 1983  [doi>10.1145/182.358452]
37
S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977  [doi>10.1145/359461.359475]

CITED BY  37
 
Giovanni Maria Sacco , Mario Schkolnick, A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model, Proceedings of the 8th International Conference on Very Large Data Bases, p.257-262, September 08-10, 1982
 
D. W. Cornell , Ph.S. Yu, Integration of buffer management and query optimization in relational database environment, Proceedings of the 15th international conference on Very large data bases, p.247-255, July 1989, Amsterdam, The Netherlands
 
Giovanni Maria Sacco, Index Access with a Finite Buffer, Proceedings of the 13th International Conference on Very Large Data Bases, p.301-309, September 01-04, 1987
 
Rajiv Jauhari , Michael J. Carey , Miron Livny, Priority-Hints: An Algorithm for Priority-Based Buffer Management, Proceedings of the 16th International Conference on Very Large Data Bases, p.708-721, August 13-16, 1990
 
Raymond Ng , Christos Faloutsos , Timos Sellis, Flexible and Adaptable Buffer Management Techniques for Database Management Systems, IEEE Transactions on Computers, v.44 n.4, p.546-560, April 1995
 
F. Fotouhi , S. Pramanik, Optimal Secondary Storage Access Sequence for Performing Relational Join, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.318-328, September 1989
Kun-Lung Wu , Philip S. Yu , James Z. Teng, Performance comparison of thrashing control policies for concurrent Mergesorts with parallel prefetching, ACM SIGMETRICS Performance Evaluation Review, v.21 n.1, p.171-182, June 1993
 
Philip S. Yu , Douglas W. Cornell, Buffer management based on return on consumption in a multi-query environment, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.1-38, January 1993
Michael J. Carey , Sanjay Krishnamurthi , Miron Livny, Load control for locking: the “half-and-half” approach, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.72-84, April 02-04, 1990, Nashville, Tennessee, United States
 
Chung-Min Chen , Nick Roussopoulos, Adaptive Database Buffer Allocation Using Query Feedback, Proceedings of the 19th International Conference on Very Large Data Bases, p.342-353, August 24-27, 1993
 
Kun-Lung Wu , Philip S. Yu , Jen-Yao Chung , James Z. Teng, Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System, Distributed and Parallel Databases, v.8 n.3, p.279-296, July 2000
Victor F. Nicola , Asit Dan , Daniel M. Dias, Analysis of the generalized clock buffer replacement scheme for database transaction processing, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.35-46, June 1992
 
Kun-Lung Wu , Philip S. Yu , Jen-Yao Chung , James Z. Teng, A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System, Proceedings of the 21th International Conference on Very Large Data Bases, p.100-109, September 11-15, 1995
 
Manish Mehta , David J. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Proceedings of the 19th International Conference on Very Large Data Bases, p.354-367, August 24-27, 1993
 
Pin Lu , Kai Shen, Virtual machine memory access tracing with hypervisor exclusive cache, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-15, June 17-22, 2007, Santa Clara, CA
 
M. J. Carey , R. Jauhari , M. Livny, Priority in DBMS resource scheduling, Proceedings of the 15th international conference on Very large data bases, p.397-410, July 1989, Amsterdam, The Netherlands
 
Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
H. Seok Jeon , Sam H. Noh, A database disk buffer management algorithm based on prefetching, Proceedings of the seventh international conference on Information and knowledge management, p.167-174, November 02-07, 1998, Bethesda, Maryland, United States
 
Chee Yong Chan , Beng Chin Ooi , Hongjun Lu, Extensible Buffer Management of Indexes, Proceedings of the 18th International Conference on Very Large Data Bases, p.444-454, August 23-27, 1992
Giovanni Maria Sacco, Fragmentation: a technique for efficient query processing, ACM Transactions on Database Systems (TODS), v.11 n.2, p.113-133, June 1986
 
Asit Dan , Philip S. Yu , Jen Yao Chung, Characterization of database access pattern for analytic prediction of buffer hit probability, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.1, p.127-154, January 1995
Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, ACM SIGMOD Record, v.22 n.2, p.297-306, June 1, 1993
 
Marcin Zukowski , Sándor Héman , Niels Nes , Peter Boncz, Cooperative scans: dynamic bandwidth sharing in a DBMS, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
 
Hong-Tai Chou , David J. DeWitt, An evaluation of buffer management strategies for relational database systems, Proceedings of the 11th international conference on Very Large Data Bases, p.127-141, August 21-23, 1985, Stockholm, Sweden
Luc Bouganim , Olga Kapitskaia , Patrick Valduriez, Memory-adaptive scheduling for large query execution, Proceedings of the seventh international conference on Information and knowledge management, p.105-115, November 02-07, 1998, Bethesda, Maryland, United States
 
Frank Moser , Achim Kraiss , Wolfgang Klas, L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS, Proceedings of the 21th International Conference on Very Large Data Bases, p.275-286, September 11-15, 1995
Abhay Mehta , Chetan Gupta , Umeshwar Dayal, BI batch manager: a system for managing batch workloads on enterprise data-warehouses, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
Stavros Harizopoulos , Vladislav Shkapenyuk , Anastassia Ailamaki, QPipe: a simultaneously pipelined relational query engine, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
 
Rubao Lee , Minghong Zhou , Huaming Liao, Request Window: an approach to improve throughput of RDBMS-based data integration system by utilizing data sharing across concurrent distributed queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
 
Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993
 
Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001
Nabil Kamel , Roger King, Intelligent database caching through the use of page-answers and page-traces, ACM Transactions on Database Systems (TODS), v.17 n.4, p.601-646, Dec. 1992
 
Asit Dan , Dinkar Sitaram, Multimedia Caching Strategies for Heterogeneous Application and ServerEnvironments, Multimedia Tools and Applications, v.4 n.3, p.279-312, May 1997
 
Leng Goh , Yanfeng Shu , Zhiyong Huang , Chin Ooi, Dynamic buffer management with extensible replacement policies, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.99-120, June 2006
Windsor W. Hsu , Alan Jay Smith , Honesty C. Young, I/O reference behavior of production database workloads and the TPC benchmarks—an analysis at the logical level, ACM Transactions on Database Systems (TODS), v.26 n.1, p.96-143, March 2001
Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992
Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993

INDEX TERMS

Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing


General Terms:
Algorithms, Performance, Theory


REVIEW

"William Campbell McGee : Reviewer"

The main thesis of this paper is that the performance of a relational DBMS can be improved by scheduling queries for execution on the basis of their main memory cache buffer requirements. Queries are traditionally scheduled in order of arrival.   more...

Collaborative Colleagues:
Giovanni Maria Sacco: colleagues
Mario Schkolnick: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player