Information Technology Reference
In-Depth Information
4.3
Performing the Undo Actions
An undo action by a backward-rolling transaction or by a forward-rolling transaction
that does a partial rollback is performed using as an argument the log record for the
corresponding forward-rolling update action. The undo action o
1
Œ
N
x of an update
action oŒ
N
x is first tried physically, that is, directly on the data page on which the
action oŒ
N
x was performed. The page-id of that page is found in the log record for
oŒ
N
x.Ifsucha
physical undo
is impossible, we resort to a
logical undo
: the execution
of the undo action begins with a search of the database structure in order to locate
the current target page of the action.
When an undo action I
1
Œx;
v
must be performed logically, we assume that the
data page q that currently holds the tuple .x;
v
/ is located and fixed and write-latched
by the call
find-page-for-undo-insert
.q; x/,
which is also assumed to take care of any structure modifications needed. These
arrange that page q will hold a sufficient number of tuples even after the deletion
of .x;
v
/. Similarly, when an undo action D
1
Œx;
v
is performed logically, the
data page q that covers key value x is located and fixed and write-latched by the
call
find-page-for-undo-delete
.q; x;
v
/,
which also takes care of any structure modifications needed to arrange sufficient
space for the tuple .x;
v
/ to be inserted. Implementations for these calls are given
in Chaps.
7
and
8
for the case in which the physical database is a sparse B-tree (see
Sect.
7.6
, in particular).
The call
undo-insert
.n;T;p;x;n
0
/ (Algorithm
4.7
) executes the undo action
I
1
Œx;
v
of an insert action IŒx;
v
that was performed by transaction T on data
page p and logged with
LSN
n. The new value of
U
NDO
-N
EXT
-LSN
.T / becomes n
0
after the undo action. A physical undo is always possible if the
P
AGE
-LSN
of page p
is still equal to the
LSN
found in the log record for IŒx;
v
, because in that case the
contents of the page have not changed in between. On the other hand, even if then
P
AGE
-LSN
has advanced, p may still be the correct target page; this is true when p is
still a data page and contains the tuple .x;
v
/ and a sufficient number of other tuples
so that the page will not underflow when .x;
v
/ is deleted.
Otherwise, page p is unlatched and unfixed, and the call
find-page-for-undo-
insert
.q; x/ is used to locate the correct target page and to perform any structure
modifications (page merges) needed to prevent the target data page from underflow-
ing. Finally, when the correct target page has been found, the tuple .x;
v
/ is deleted,
the deletion is logged with a redo-only log record (
3.12
), and the
P
AGE
-LSN
of the
page and the
U
NDO
-N
EXT
-LSN
of the transaction are updated by the procedure
undo-
insert-onto-page
.T;p;x;n
0
/ (Algorithm
4.8
).