Information Technology Reference
In-Depth Information
n
5
Wh
S;
tree-height-increase
;p
1
;p
0
1
; 65; p
0
1
;s
1
;V
1
;V
2
;3;n
4
i
,
n
6
Wh
S;
insert-index-record
;p
0
1
; 25; p
0
3
;n
5
i
,
n
7
Wh
S;
commit-smo
i
,
where S is the identifier of the system-generated structure-modification transaction
and the sets V
1
, V
2
, V
3
,andV
4
are as in Example
8.7
. When the commit log record
for the structure modification (
commit-smo
) has been written, the modification is
regarded as committed and the latches are released.
On the contrary, assume that a process failure or a system crash occurs and
that in recovery it is found that log records up to and including the one with
LSN
n
4
have survived on the log disk. Obviously, after performing the redo pass,
the modifications logged with
LSN
s n
4
, n
3
,andn
2
must be undone in the undo pass,
so that the following log records are written:
n
5
Wh
S;
abort-smo
i
,
n
6
Wh
S;
undo-insert-index-record
;p
3
;12;n
3
i
,
n
7
Wh
S;
undo-page-split
;p
3
; 25; p
0
3
;s
2
;V
3
;n
2
i
,
n
8
Wh
S;
undo-page-split
;p
6
;12;p
0
6
;s
3
;V
4
;n
1
i
,
n
9
Wh
S;
commit-smo
i
.
To accomplish this, the pages mentioned in the log records are write-latched, and
the inverse modifications of the logged modifications are performed. Naturally, this
is possible only if the page contents are exactly in the states in which they were left
by the modifications.
t
To make physical undo possible, while a structure-modification transaction
is rolling forward, other processes must be prevented from updating the mod-
ified pages until the structure-modification transaction commits. A safe way to
accomplish this is to retain read latches on the modified pages until the structure-
modification transaction commits.
Example 8.16
In Example
8.15
, B-tree pages are latched as follows:
1. Pages p
1
, p
3
,andp
6
are write-latched (in this order).
2. The split of p
6
:pagep
0
6
is write-latched.
3. The write latches of p
6
and p
0
6
are downgraded to read latches.
4. The split of p
3
:pagep
0
3
is write-latched.
5. The insertion into p
3
of the index record .12; p
0
6
/.
6. The write latches of p
3
and p
0
3
are downgraded to read latches.
7. The tree-height increase: pages p
0
1
and p
0
1
are write-latched.
8. The insertion into p
0
1
of the index record .25; p
0
3
/.
9. The commit of the structure modification: all the latches are released.
Observe that we have to first write-latch all the pages on the insertion path that need
modification, because we have to keep all the modified pages at least read-latched
until the commit of the entire sequence of splits (to make possible the rollback of
the modification), and in the same time we have to obey the rule that pages must be
latched in the first-parent-then-child order and that we cannot upgrade read latches
to write latches (to prevent undetectable deadlocks).
t
