Information Technology Reference
In-Depth Information
Algorithm 11.1
Scan the relation and extract the index records
allocate space for a main-memory priority queue indexed by the secondary key
F ;{set of identifiers of files created to store sorted bulks}
acquire a short-duration S lock on the relation
declare in the system catalog that the secondary index is under construction
Cursor
1 {a shared variable for scanning the primary-key space}
release the short-duration S lock on the relation
while
Cursor
< 1
do
find-page-for-bulk-read
.p; p
0
;
Cursor
;1/
V f.y;x;p/j .x; y;
v
/ in page pg
if
the priority queue cannot accommodate jVj new elements
then
f create a file for the next bulk
F F [ffg
pull all the records from the priority queue and write them to file f
flush file f
log
.n;h
checkpoint-index-extract
;F;
Cursor
i/
end if
push the records in V to the priority queue
if
p
0
D p
then
Cursor
1
else
Cursor
the least primary key x in p
0
end if
unlatch-and-unfix
.p; p
0
/
end while
f create a file for the last bulk
F F [ffg
pull all the records from the priority queue and write them to file f
flush file f
log
.n;h
checkpoint-index-extract
;F;
Cursor
i/
11.5
Concurrent Updates by Transactions
During index-record extraction, it may happen that transactions insert, delete, or
write tuples in the already scanned portion of the relation, that is, tuples with primary
key less than
Cursor
. Those updates are missed by the scan, while inserts, deletes,
and writes done on the not-yet-scanned portion of the relation (containing tuples
with primary key
Cursor
) are captured by the scan.
The updates done on the scanned portion of the relation could be captured from
the log, by remembering the
LSN
of the begin-transaction log record written for
the index constructor. However, an easier and more efficient solution is obtained
by using a
side file
to store the updates by transactions done after the start of the
index construction on the scanned portion of the relation. After the relation has
been scanned and the index records thus extracted have been inserted into the index
