Information Technology Reference
In-Depth Information
10.3
Bulk Reading
The call
bulk-read
.T; s
X
;s
XV
/ (Algorithm
10.1
) implements the bulk-read action
RŒs
X
;s
XV
for transaction T . For simplicity, we consider only closed ranges Œ
z
1
;
z
2
.
As with the single-tuple read action (Algorithm
6.6
), we assume that a saved path
is maintained. With bulk actions this is all the more important because such actions
usually touch many tuples in the same leaf page.
The idea is to process the key ranges of s
X
in ascending key order and for each
range to traverse to the leaf page that covers the lower bound of the range, to read
from the page all the tuples that belong to the range, and then to move to the next
leaf page until the upper bound of the range is reached. In processing a range Œ
z
1
;
z
2
,
the variable
z
takes
z
1
as its initial value and, after reading from the leaf page that
covers
z
all tuples .x;
v
/ with
z
x
z
2
, advances to the key y next to the greatest
key read (Fig.
10.1
).
The call
find-page-for-bulk-read
.p; p
0
;
z
;
z
2
/ is used to traverse the B-tree to the
leaf page p that covers key
z
and to the leaf page p
0
that covers
high-key
.p/.The
call returns with the pages p and p
0
read-latched. Page p
0
is determined only if
z
2
high-key
.p/; otherwise, the call returns with p
0
D
p. The algorithm for
find-page-
for-bulk-read
.p; p
0
;
z
;
z
2
/ is similar to that for
find-page-for-fetch
.p; p
0
;
z
;
both
/
(Algorithm
7.4
) with
both
D
true.
Before the B-tree traversal for a range Œ
z
1
;
z
2
is started, the smallest partition
fragment that covers the keys
z
1
and
z
2
is S-locked and the containing fragments
are IS-locked, for commit duration. The locks on the next keys are acquired,
using conditional locking, as the keys are encountered during the left-to-right
scan of the tuples in the range. In the algorithm,
keys
.p/ denotes the set of keys
of tuples in leaf page p and
keys
.S / denotes the set of keys of tuples in tuple
set S .
Fig. 10.1
Bulk-reading
tuples .x;
v
/ with keys x in
the range Œ
z
1
;
z
2
. The least
key y greater than
z
2
is in the
next page p
0
