Browse Prior Art Database

Efficient Buffer Replacement Technique With Improved Fairness for Read And Update References

IP.com Disclosure Number: IPCOM000119266D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 131K

Publishing Venue

IBM

Related People

Narang, IS: AUTHOR [+2]

Abstract

This article describes a buffer management method which can improve the overall database management system throughput by increasing the buffer hit ratio for frequently referenced or updated pages.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 48% of the total text.

Efficient Buffer Replacement Technique With Improved Fairness for
Read And Update References

      This article describes a buffer management method which
can improve the overall database management system throughput by
increasing the buffer hit ratio for frequently referenced or updated
pages.

      To improve buffer hit ratio for frequently referenced pages,
the Least Recently Used (LRU) algorithm is normally used for buffer
replacement.  As explained in (*), a page is kept on two chains which
are manipulated by the LRU algorithm: Chain 1 accounts for the read
reference and is called the LRU-Chain; Chain 2 accounts for the
update reference and is called the Changed-Page-Chain (CPC).  The CPC
is a subset of the LRU-chain.  A page is always stolen from the
LRU-chain.  This invention improves the fairness for keeping a page
in the bufferpool based on the read and the update operations in the
following ways:
1.   When a changed page has a read reference, it is put at the
bottom of the LRU-chain, i.e., it becomes least stealable.  This
provides fairness for the read reference of a changed page.
2.   When a changed page becomes clean (e.g., by writing the memory
version of the updated page to disk) and the page is not in the
LRU-chain, then the page becomes the best candidate for steal, i.e.,
it is put on the top of the LRU-chain.  This is explained by
discussing the steal operation:  a page is stolen from the top of the
LRU-chain.  However, if the top page is changed, it is non-stealable
and is dequeued from the LRU-chain.  When this page becomes clean, it
is put on the top of the LRU-chain.  This provides fairness because
the dequeued page was least referenced (read or update).
3.   When a changed page has an update reference (i.e., updated
again), it is put at the bottom of the CPC and at the bottom of
the LRU-chain.  This accounts for an update operation as a read
reference and an update reference.  The reason an update should be
counted as a read reference is to manipulate the LRU chain and,
hence, avoid stealing a frequently updated page when it becomes
clean.

      ASSUMPTIONS For simplicity, we assume that a database
management system maintains a single buffer pool LRU-chain and a
single Changed-Page-Chain (CPC).  However, this invention can also be
applied to database management systems that maintain multiple CPCs.

      METHOD
READ OPERATION
Page is not cached
1.   Steal Operation:
      a.   If the buffer on the top of the LRU-chain is
           changed, then dequeue it from the LRU-chain.
           Continue with the next page until an unchanged
           page is found.
           Changed pages on top of the LRU chain indicate
           that those pages are not being referenced/updated
           for a long period of time.
      b.   Steal the unchanged page from the top of the
           LRU-chain.  Assign...