Transaction Rollback and Restart Recovery - Transaction Processing - page 86

Proof By Theorem 4.4 ,the R EDO -LSN value produced by the analysis pass is a
correct LSN value for starting the forward scan of the log in the redo pass. The
claim then follows from the fact that the updates logged with log records with
LSN s greater than or equal to R EDO -LSN up to the end of the log are redone on
the disk versions of pages fetched to the buffer in the original chronological order
of the updates when those updates are missing, and from the fact that the P AGE -
LSN of each page records the LSN of the log record of the last update on the
page.
We also note that the updating of the R EC -LSN s during the redo pass is correct
because R EC -LSN .p/ is only updated when processing a log record for an update
on a currently unmodified page p. Thus we can safely set R EC -LSN .p/
P AGE -LSN .p/ C 1, not violating condition ( 3.1 ).
As each log record for an update action by a transaction describes an entire action
and such was also assumed to be the case with structure modifications, the resulting
database must be action consistent, because the redo pass then performed complete
operations and because the modification on a single page described by the redo-only
log record for a multi-page structure modification can be selectively redone on that
page (as will be shown in Sect. 4.11 ). t

The number of disk accesses performed during the redo pass is usually much less
than the number of disk accesses performed during normal transaction processing
from the timepoint of logging the log record with LSN D R EDO -LSN up to the event
of the system crash. First, during the redo pass, no page is fetched from disk
just for reading, that is, no read-latching is performed. Second, a page is write-
latched only if there is a log record with LSN R EDO -LSN that describes an
update on it. Moreover, thanks to the maintenance of the R EC -LSN values, it may
not be necessary to write-latch and inspect every such page at every logged update
on it.
This can be contrasted with normal transaction processing where an update action
may involve latching several pages, because of the need to locate the target page of
the update via an access path such a B-tree index. As discussed above in Sect. 4.3
(and presented in detail in Chaps. 6 and 7 ), a forward-rolling insert or delete action
may involve several root-to-leaf traversals of a B-tree index, thus implying an
access-path-length that is a multiple of the height of the B-tree. A logical undo
action also involves traversing of the index. Instead, the path-length is only one for
the redoing of a forward-rolling insert or delete action, or an undo-insert or undo-
delete action, given the log record of the action.

4.9 Undo Pass for Do-Redo-Undo Recovery

In the undo pass , forward-rolling transactions are rolled back and the rollback
of backward-rolling transactions is completed. First, every forward-rolling trans-
action T is aborted by performing the call abort .T / (Algorithm 4.2 ), which sets