Information Technology Reference
In-Depth Information
In case (4), because the short-duration S lock acquired by the index constructor at
the start of the extraction process ensures that the construction of the index cannot
begin while transactions that have updated the relation are still active, the index
must still be unavailable and not in construction when the transaction rolls back
the insertion. Therefore, no index-specific actions need be done, and the transaction
proceeds to undo the insertion of the tuple.
The index-specific action to be done in the case of deleting a tuple from the
relation are analogous to those for inserting a tuple. We leave the details as an
exercise (see the Problems section).
11.6
Populating the Index
When the index constructor has completed the index-record extraction process,
it begins populating the index with the records written into the files f
2
F .A
straightforward solution is to use a bulk insertion algorithm similar to but simpler
than that used in the procedure
bulk-insert
(Algorithm
10.2
). Now that the records
in each file f are already in sorted order, no sorting needs to be done. Moreover, no
locks need to be acquired for protecting the index, because it is only visible to the
index constructor.
We assume that a sorted bulk f of index records is inserted to the dense B-
tree index with the call
index-bulk-insert
.T; f / (Algorithm
11.3
), where T is the
identifier of the system transaction created in whose name the bulk insert is logged,
using redo-undo log records.
We use one transaction per bulk so as to make a failed index population
restartable. The call
find-page-for-index-bulk-insert
.p; y
0
;x
0
;p
0
;y;x;p/,whichis
very similar to the call
find-page-for-bulk-insert
.p;h;p
0
;x;p/ in Algorithm
10.2
,
is used to determine the leaf page p of the secondary index that covers key .y; x/,
the high key .y
0
;x
0
/ of p,andthepagep
0
next to p (if any), write-latching p,and
read-latching p
0
. The call also arranges, with appropriate structure modifications,
that page p has room at least for the record .y;x;p/.Ifnonextpagep
0
exists (i.e.,
.y
0
;x
0
/
D
.
1
;
1
/), then p
0
D
p. The call
insert-index-bulk-into-page
.T;p;S/,
similar to
insert-bulk-into-page
.T;p;S/ (Algorithm
10.4
), is used to insert the
records in S into the write-latched leaf page p of the secondary index and to log
the insertions with redo-undo log records.
Algorithm
11.4
first populates the index by inserting the bulks f
2
F and then
processes the side file by scanning it from the beginning to the end. For restartability,
at the start of the population, the set F of file identifiers is logged, and after the
commit of each bulk insertion of a bulk f , the file identifier f is logged. The
insertion of the bulks in f
2
F is performed by k concurrent process threads each
inserting a subset F
i
of the bulks in F , i
D
1;:::;n,wherek is a chosen degree of
concurrency.
