Browse Prior Art Database

Dynamic Hash Table Expansion/ ,Contraction Technique

IP.com Disclosure Number: IPCOM000107275D
Original Publication Date: 1992-Feb-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 89K

Publishing Venue

IBM

Related People

Haderle, DJ: AUTHOR [+4]

Abstract

This invention provides a method for dynamically modifying the dimension of a hash table, with a minimal impact on any processes which are concurrently accessing it. For a database management system, hashing is an efficient method of locating a page in a buffer pool. The proper dimension of the hash table is a function of the buffer pool size. Therefore, if the buffer pool can be expanded dynamically, it is desirable to also expand the hash table in order to avoid long hash synonym chains. Similarly, if the buffer pool is contracted dynamically, it is desirable to also contract the hash table in order to free unneeded storage.

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

Dynamic Hash Table Expansion/ ,Contraction Technique

       This invention provides a method for dynamically
modifying the dimension of a hash table, with a minimal impact on any
processes which are concurrently accessing it.  For a database
management system, hashing is an efficient method of locating a page
in a buffer pool.  The proper dimension of the hash table is a
function of the buffer pool size. Therefore, if the buffer pool can
be expanded dynamically, it is desirable to also expand the hash
table in order to avoid long hash synonym chains.  Similarly, if the
buffer pool is contracted dynamically, it is desirable to also
contract the hash table in order to free unneeded storage. Since the
expansion and contraction can take place concurrently with
applications accessing data in the buffer pool, the hash table
expansion/contraction should be made as transparent to these
applications as possible.

      Previously, the changing of a hash table's dimension could only
be accomplished by blocking access to it during the rebuilding
process, or by completely stopping and restarting the database
system.  Either of these methods cause an unacceptable interruption
in database access.

      The present invention calls for creating a new (larger or
smaller) hash table and migrates entries from the old table to the
new one.  By carefully choosing the dimension of the new table, a
one-to-many (in the case of expansion) or many-to-one (in the case of
contraction) relationship can be guaranteed between the hash classes
for a given object in the old and new tables.  For example, assuming
that the hash class for a database page is determined by taking the
remainder after dividing the page number by the hash table dimension,
it can be seen that if the dimension of the new hash table is some
multiple "n" of the old hash table's dimension, then all entries
belonging to a given hash class in the old table will map to a set
of "n" classes in the new table.  Similarly, if the new hash table
dimension is some integral factor "m" of the old hash table's
dimension, then there will be a set of "m" hash classes in the old
table which will map to a single hash class in the new table.

      It is assumed that access to the hash classes is controlled by
a set o...