Browse Prior Art Database

Rollback Index Recovery for Algorithm for Recovery and Isolation Exploiting Semantics for Index Management

IP.com Disclosure Number: IPCOM000117514D
Original Publication Date: 1996-Mar-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 155K

Publishing Venue

IBM

Related People

Levine, FE: AUTHOR

Abstract

The guarantee of rollback using a Write Ahead Logging (WAL) protocol entails the reserving of logging space required to log the undo (which, with the exception of index updates is less than or equal to the space required for the original transaction). This disclosure identifies a solution for indexes, portions of which were implemented in the OS/2* Extended Edition Database Manager, which was ported to the RISC System/6000* as DB2/6000.

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

Rollback Index Recovery for Algorithm for Recovery and Isolation
Exploiting Semantics for Index Management

      The guarantee of rollback using a Write Ahead Logging (WAL)
protocol entails the reserving of logging space required to log the
undo (which, with the exception of index updates is less than or
equal to the space required for the original transaction).  This
disclosure identifies a solution for indexes, portions of which were
implemented in the OS/2* Extended Edition Database Manager, which was
ported to the RISC System/6000* as DB2/6000.

      Updates for data records for changes to a database are
written to a log (during forward processing of transactions) prior to
actually writing the data on disk.  In order to guarantee rollback,
there is always enough space reserved in the log to allow the
required log updates during the rollback of transactions during both
normal undo processing and restart undo processing.  Typically, the
updates performed during a partial or total rollback are logged using
Compensation Log Records (CLRs).  The CLRs always take less than or
equal to the number of bytes required for normal forward processing.
Thus one can always guarantee the ability to rollback data records by
reserving as much space for rollback as required for normal
processing.  Using the algorithms in Algorithm for Recovery and
Isolation Exploiting Semantics for Index Management (ARIES/IM),
during rollback, there can be node deletions or node splits that did
not occur in the original transaction.  This fact means that there
may be more log space required during the undo phase than during the
original transaction.  This implies that the normal approach of
reserving as much space for the undo as the normal forward processing
log record is not sufficient to guarantee enough log space for index
rollback.  In addition, reserving space within the index nodes
themselves for rollback can significantly reduce the fan out factor
(keys per node) and can even lead to the condition, where no more
keys can be added because no more space is available, that is, all
space on a single node is reserved for rollback.

      Within the original index nodes, no space should be reserved
for rollback.  The keys are packed and the nodes are split and
combined or deleted as per normal (system dependent) index
algorithms.  There are multiple ways to handling the logging and the
index space required  required during undo.  The following describes
some basic approaches to  support this function.

      With index updates, there are two types of log records, those
that are related to the key and those that are related to the index
itself, the Structure Modification Operation (SMO), that is, the page
splits or page deletions.  The undo log records of the keys
themselves are handled by the CLRs and the space required for them
are less than or equal to that required for forward operations.  It
is only the SMOs that require special handlin...