Browse Prior Art Database

Index Recovery Method for Transactions Performing Load Operations

IP.com Disclosure Number: IPCOM000115762D
Original Publication Date: 1995-Jun-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 112K

Publishing Venue

IBM

Related People

Lockwood, DP: AUTHOR [+3]

Abstract

A great amount of time is spent by transactions that have exclusive access to an index and insert sequences of entries (key + record identifier) greater than the maximum entry in the index. For brevity, let us call these types of transactions load tasks. The time needed to complete load tasks is proportional to the number of entries to be inserted. It is not uncommon for load tasks to take several hours. In the event of a failure, all of this time may be lost and additional time needed to recover and/or rebuild the index to a prior point of consistency, at which time the task may be restarted. This disclosure presents a new logging scheme which reduces the logging space and time, improves recovery performance, and allows such a task to be resumed.

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

Index Recovery Method for Transactions Performing Load Operations

      A great amount of time is spent by transactions that have
exclusive access to an index and insert sequences of entries (key +
record identifier) greater than the maximum entry in the index.  For
brevity, let us call these types of transactions load tasks.  The
time needed to complete load tasks is proportional to the number of
entries to be inserted.  It is not uncommon for load tasks to take
several hours.  In the event of a failure, all of this time may be
lost and additional time  needed to recover and/or rebuild the index
to a prior point of consistency, at which time the task may be
restarted.  This disclosure presents a new logging scheme which
reduces the logging space and time, improves recovery performance,
and allows such a task to be resumed.

      The basic invention involves a method of establishing
checkpoints, or "points of consistency," during an index load
operation.  The invoker of the load function must decide when and how
often to establish points of consistency.  The decision of how
frequently to establish points of consistency might be based on
elapsed time, number of entries inserted, or number of new pages
allocated since the last point of consistency.  The new method takes
advantage of the fact that all insertions take place at the end of
the index (the right hand side of the index tree).  Because of this,
logging the right hand side of the index tree gives a snapshot of the
index at that point in time.  This involves logging all index pages
(nonleafs and last leaf) necessary to traverse to the greatest entry
in the index.  If no index pages are "lost" (i.e., destroyed or not
stored on DASD), then restoring the right hand side of the index tree
restores the basic structure of the index to what it was at the time
the checkpoint was taken.

      However, there is more to an index than just the basic tree
structure.  Because structure modifications occur during load
operations, page allocations and deallocations must occur in the
space management portion of the index manager.  These changes must
also be undone in the event that we want to rollback to a prior point
of consistency.  This is handled by writing undo log records for all
space map updates (regardless of whether or not the user specified he
wants logging performed for the load operation).  Thus, when rolling
back to a prior point of consistency, all page allocations will be
undone before restoring the right hand side of the tree.

      This method will only work if the implementation of the index
manager or buffer manager can ensure that no index pages are "lost."
If all page allocations are undone and the right hand side of the
tree is restored, but some other loaded pages have been destroyed
within the tree or not stored to DASD, then the index tree will not
be correct/complete.  The simplest solution to this problem is to
force all pages that have bee...