Information Technology Reference
In-Depth Information
When every structure modification can be logged in its entirety with a single log
record, the
WA L
protocol guarantees that after the redo pass of recovery, the physical
database is consistent (and the logical database action-consistent) and there is never
any need to roll back any unfinished structure modifications. Recall that we require
that all the pages involved in the modification be kept simultaneously write-latched
during the modification. Then it is sufficient that the log record for the modification
is redo only.
This suggests that we define all structure modifications in such a way that this
property is maintained. As the principle of latching requires that any process thread
may keep only a small number of pages latched simultaneously, this means that
in the case of a balanced tree-like index such as a B-tree, a structure modification
must be defined to involve only a small fixed number of pages (typically from two
adjacent levels of the tree) and still having the property of retaining the physical
consistency of the index.
However, there exist implementations of structure modifications that involve
several levels of a B-tree index and are logged using several (redo-undo) log records
(each involving two adjacent levels of the tree), where the pages involved in the
modification of one level may be unlatched and stolen from the buffer before
the modifications at the other levels are completed. Such a multi-level redo-undo
modification may need to be undone, when the entire modification has not been
completed before the crash.
There are problems with redo-undo structure modifications. A structure modifi-
cation is a physical operation, meaning that undoing such an operation must also
be physical. Therefore undoings of structure modifications cannot be mixed with
logical undoings of transactions' actions. One solution is to implement the undo
pass of restart recovery in two backward scans of the log: in the first scan, the
unfinished structure modifications are undone, thus bringing the physical database
into a consistent state, and then in the second scan the active transactions are rolled
back.
In the
ARIES/KVL
and
ARIES/IM
locking and index management methods
designed to work with
ARIES
, a structure modification involving multiple levels
of a B-tree, such as a sequence of page splits or merges, can be left unfinished in
the event of a system crash and must be undone in the undo pass of restart recovery.
However, the undo pass is still implemented by a single backward scan of the log.
During normal transaction processing, a special
tree latch
is used to ensure that only
a single structure modification can be running at a time. This in turn guarantees in
the undo pass the correctness of the search path for any tuple update that must be
undone logically.
The handling of structure modifications on B-trees is treated in more detail in
Chap.
8
.
