Browse Prior Art Database

Use of Secondary Address Stack and Multiple Insertion Points for Database Buffer Management under Least Recently Used Policy

IP.com Disclosure Number: IPCOM000105383D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 135K

Publishing Venue

IBM

Related People

Dan, A: AUTHOR [+3]

Abstract

Disclosed is a method for improving the performance of the LRU buffer replacement policy under an IRM workload consisting of multiple disjoint data sets where the relative frequency of access of the data sets is unknown. This is achieved by dynamically adjusting the insertion points in the LRU stack for different data sets. A secondary address stack is used to gather statistics in order to determine the relative hotness of different database relations and indices (data types) which is used to control the LRU buffer insertion points for different data types. The secondary stack is also used to handle skewed access within each data type.

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

Use of Secondary Address Stack and Multiple Insertion Points for Database Buffer Management under Least Recently Used Policy

      Disclosed is a method for improving the performance of the LRU
buffer replacement policy under an IRM workload consisting of
multiple disjoint data sets where the relative frequency of access of
the data sets is unknown.  This is achieved by dynamically adjusting
the insertion points in the LRU stack for different data sets.  A
secondary address stack is used to gather statistics in order to
determine the relative hotness of different database relations and
indices (data types) which is used to control the LRU buffer
insertion points for different data types.  The secondary stack is
also used to handle skewed access within each data type.

      In a relational database there are several relations and
indices (data types) and they are accessed with different
frequencies.  Furthermore, access within a data type may not be
uniform.  The access frequencies to different data types may change
dynamically.  In the basic LRU policy, when a data granule is not
found in the LRU stack, it is brought in and inserted at the top of
the stack.  The basic problem with this approach is that infrequently
accessed data (cold data) is also inserted at the top of the LRU
stack, pushing down all other data granules including hot data.  This
is the cause for degradation of performance of the LRU policy as
compared to that of optimal buffer allocation.  Another invention
discloses improvement of the performance of the LRU policy by
inserting colder data at a lower point in the LRU stack as compared
to the insertion pointers of hot data types.  Specifically, the hit
ratio under the basic LRU policy is first measured, and the data
types are ordered by decreasing buffer hit ratio.  Based on this
ordering, the LRU buffer insertion point of each data type is moved
lower down in the LRU stack, starting with the coldest data type,
until a terminating condition is met.  This process is repeated for
the next coldest data type, and so on.  The terminating condition is
that the push down rate at the insertion point is the same as the hit
rate for the portion of the buffer below the insertion point.

      The above procedure works well when the access frequencies do
not change with time.  A change in the access frequencies may cause a
change in the ordering of data types in terms of their hotness, and
therefore their insertion points would need to be reordered.
However, a change in hotness may not be detected under the previous
scheme because the location of the pointer affects the hit ratio of
that data type.  In fact, there is a trade-off between the degree of
discrimination between data types (by different insertion points) and
the ability to respond to dynamic changes.  Additionally, the above
disclosure assumes uniform access within a data type.  The method
presented here can handle both dynamic changes in access...