Browse Prior Art Database

Buffer Replacement/Prefetching Scheme for Use in Index Scans

IP.com Disclosure Number: IPCOM000100290D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 92K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

Disclosed is an improved buffer replacement/prefetching scheme for use in relational database index scans. Indexes based on particular keys of a relation are commonly used to retrieve portions of that relation. These indexes are stored in the form of B+ trees. During an index scan, a sequential search is performed through the leaf pages of the index, and the resulting data pages are read into a buffer managed by a least- recently-used (LRU) algorithm. The performance of an index scan depends in large part on the resulting hit ratio achieved in the buffer.

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

Buffer Replacement/Prefetching Scheme for Use in Index Scans

       Disclosed is an improved buffer replacement/prefetching
scheme for use in relational database index scans.  Indexes based on
particular keys of a relation are commonly used to retrieve portions
of that relation.  These indexes are stored in the form of B+ trees.
During an index scan, a sequential search is performed through the
leaf pages of the index, and the resulting data pages are read into a
buffer managed by a least- recently-used (LRU) algorithm.  The
performance of an index scan depends in large part on the resulting
hit ratio achieved in the buffer.

      Belady (1) proposed a buffer replacement algorithm in which, at
any given moment in time, the page replaced is the one which, among
all pages currently in the buffer, will be the page whose next use is
last (a lexicographic tie breaker is used to decide among those pages
that will never be used again).  This algorithm will be denoted by
BO, and it has the nice property that it is provably optimal.  Of
course, it also has the not-so-nice property that it is a lookahead
algorithm; that is, it requires knowledge of the future reference
pattern.  Accordingly, BO has never had any real practical value; it
has primarily served as a lower bound by which to measure LRU and
other non-lookahead algorithms. See Coffman and Denning [2] for
details on LRU, BO, and other buffer replacement algorithms.  Note
that BO is shown to perform appreciably better than LRU.  Simulations
show that for realistic examples the miss rates will be cut by at
least a factor of two.

      Note that index scans are one legitimate example of a situation
in which the future reference pattern of the relation is known
precisely.  As such, BO becomes attractive.  From the computational
point of view, the algorithm can be performed at index creation (or
update) time without appreciable overhead.  From the storage space
point of view, the required information can be stored (in the index
leaf pages themselves in one implementation) without using more than
a minimal amount of space.  The main data that needs to be stored is
the number of the page to be replaced on a miss.  The overhead
involved in managing an LRU buffer can therefore be reduced.
Furthermor...