Efficient Buffer Replacement Technique With Improved Fairness for Read And Update References
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Narang, IS: AUTHOR [+1]
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.
Efficient Buffer Replacement Technique With Improved
Read And Update References
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
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
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
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.
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