Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Scheme for Reduced Logging for Forward-Recoverable Databases

IP.com Disclosure Number: IPCOM000112391D
Original Publication Date: 1994-May-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 6 page(s) / 219K

Publishing Venue

IBM

Related People

Bezviner, DE: AUTHOR [+2]

Abstract

As described in RJ-6649-REV, "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging", some database managers use a two-pass databae restart method (redo, undo), skipping an analysis pass. Compensation log records are written during the undo pass. To guarantee rollback of transactions, some log space is reserved for these compensation log records.

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

Scheme for Reduced Logging for Forward-Recoverable Databases

      As described in RJ-6649-REV, "ARIES: A Transaction Recovery
Method Supporting Fine-Granularity Locking and Partial Rollbacks
Using Write-Ahead Logging", some database managers use a two-pass
databae restart method (redo, undo), skipping an analysis pass.
Compensation log records are written during the undo pass.  To
guarantee rollback of transactions, some log space is reserved for
these compensation log records.

      Sometimes an index structure must be modified during an undo
pass.  Log records for this are very large, up to 2000+ bytes (size
of half a page+) each.  The problem with this approach is twofold:
first, it requires a potentially enormous amount of disk space, and
second, it increases the chance of not being able to rollback a
transaction.

      The problem cannot be completely avoided; some extra logging
must be done to allow for forward recovery.  However, by defining two
log record types (described later), the log record size can be
reduced from approxi- mately 2000 bytes to approximately 100 bytes.

      The remainder of this disclosure has 5 sections.  First, a
brief overview of how index splits are currently handled in some DBMs
Second, new log records required for this disclosure are identified.
Third, the various classes of recovery scenarios that must be handled
are discussed.  Fourth, new or changed processingrequired to
implement this disclosure is described.  Finally, this disclosure's
advantages are summarized.

This section briefly describes how index splits are currently
handled.

      Log records for index B+ tree node splits are written within a
"backout free interval"; once the interval completes, no log records
within the interval will ever be undone.  These log records will be
undone, however, if the backout free interval did not complete suc-
cessfully.

      When undoing a Delete Key operation, a node split might be
required in order to reinsert the deleted key.  The backout free
interval contain- ing this split during Undo is, in effect, a
Compensation Log Record (CLR).  There is the possibility that a split
occurring during Undo will not complete successfully (e.g., system
crash), thus the log records within the backout free interval are
written as forward log records.  If a crash occurs before the
interval is completed successfully, they will be undone during
recovery.  The original Delete Key operation is then undone.  The
reinsertion of this key will cause a split, as it did before the
crash.  The split should be able to complete and recovery can then
continue.

      Node splits occurring during undo (or during forward
processing, for that matter) are unpredictable.  Thus, during forward
processing, there is no way to calculate the amount of reserved space
that will be required for node splits that might occur during Undo.
Since log space that was reserved for undoing other log records
ca...