Principles of database buffer management

ABSTRACT

This paper discusses the implementation of a database buffer manager as a component of a DBMS. The interface between calling components of higher system layers and the buffer manager is described; the principal differences between virtual memory paging and database buffer management are outlined; the notion of referencing versus addressing of database pages is introduced; and the concept of fixing pages in the buffer to prevent uncontrolled replacement is explained. Three basic tasks have to be performed by the buffer manager: buffer search, allocation of frames to concurrent transactions, and page replacement. For each of these tasks, implementation alternatives are discussed and illustrated by examples from a performance evaluation project of a CODASYL DBMS.

REFERENCES

• 1: Özalp Babaoglu , William Joy, Converting a swap-based system to do paging in an architecture lacking page-referenced bits, Proceedings of the eighth ACM symposium on Operating systems principles, p.78-86, December 14-16, 1981, Pacific Grove, California, United States
• 2: BELADY, L.A. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 2 (1966), 78-101.
• 3: Richard S. Brice , Stephen W. Sherman, An extension of the performance of a database manager in a virtual memory system using partially locked virtual buffers, ACM Transactions on Database Systems (TODS), v.2 n.2, p.196-207, June 1977 [doi>10.1145/320544.320556]
• 4: Richard W. Carr , John L. Hennessy, WSCLOCK—a simple and effective algorithm for virtual memory management, Proceedings of the eighth ACM symposium on Operating systems principles, p.87-95, December 14-16, 1981, Pacific Grove, California, United States
• 5: CHU, W.W., AND OPDERBECK, H. Program behavior and the page fault frequency replacement algorithm. Computer 9, 11 (1976), 29-38.
• 6: 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]
• 7: DENNING, P.J. Thrashing: Its causes and prevention. In AFIPS Conference Proceedings, Vol. 33, FJCC, 1968, 915-922.
• 8: DENNING, P.J. Working sets past and present. IEEE Trans. Softw. Eng. SE-6, 1 (1980), 64-84.
• 9: EFFELSBERG, W. Buffer management in database systems. Dissertation, Fachbereich Informatik, Technische Hochschule Darmstadt, 1981, (in German).
• 10: FERNANDEZ, E.B., LANG, T., AND WOOD, C. Effect of replacement algorithms on a paged buffer database system. IBM J. Res. DeF. 22, 2 (1978), 185-196.
• 11: FERRARI, D. The improvement of program behavior. Computer 9, 11 (1976), 39-47.
• 12: HA~RDER, T. Embedding a database system in an operating system environment. In Datenbanktechnologie, J. Niedereichholz, Ed. Proceedings II/79 of the German Chapter of the ACM, Teubner-Verlag, Stuttgart, 1979, 9-24, (in German).
• 13: HOWARD, J.H. Virtual memory buffering, IBM Res. Rep., San Jose, Calif., 1980, (in preparation).
• 14: 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]
• 15: MATTSON, R.L., GECSEX, J., SLUTZ, D.R,, AND TRAIGER, I.L. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
• 16: REXTER, A. A study of buffer management policies for data management systems. Tech. Summary Rep. No. 1619, Mathematics Research Center, Univ. of Wisconsin, Madison, Mar. 1976.
• 17: Juan Rodriguez-Rosell , Jean-Pierre Dupuy, The design, implementation, and evaluation of a working set dispatcher, Communications of the ACM, v.16 n.4, p.247-253, April 1973 [doi>10.1145/362003.362032]
• 18: RODRIGUEZ-ROSELL, J. Empirical data reference behavior in database systems. Computer 9, 11 (1976), 9-13.
• 19: 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
• 20: Stephen W. Sherman , Richard S. Brice, Performance of a database manager in a virtual memory system, ACM Transactions on Database Systems (TODS), v.1 n.4, p.317-343, Dec. 1976 [doi>10.1145/320493.320494]
• 21: Alan Jay Smith, Sequentiality and prefetching in database systems, ACM Transactions on Database Systems (TODS), v.3 n.3, p.223-247, Sept. 1978 [doi>10.1145/320263.320276]
• 22: SPIRN, J. Distance string models for program behavior. Computer 9, 11 (1976), 14-20.
• 23: SPIRN, J.R., AND DENNING, P.J. Experiments with program locality. In AFIPS Con/erence Proceedings, Vol. 41, FJCC, 1972, 611-621.
• 24: 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]
• 25: TUEL, W.G. An analysis of buffer paging in virtual storage systems. IBM J. Res. DeF. 20, 5 (1976), 518-520.
• 26: Rollins Turner , Bill Strecker, Use of the LRU stack depth distribution for simulation of paging behavior, Communications of the ACM, v.20 n.11, p.795-798, Nov. 1977 [doi>10.1145/359863.359868]

INDEX TERMS

Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Storage hierarchies

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design