Information Technology Reference
In-Depth Information
If the tuple with key x does not qualify for reading (cases 2 and 4), we unlatch
the pages in P and move to the key next to x, that is, to the versioned tuples with the
least key greater than x, and repeat the checking for that key, and so on. The move
to the key next to x is performed by the procedure call find-pages-for-read .P; > x/.
Note that even if new versioned tuples with keys already scanned may appear, those
tuples must be of versions created by transactions other than T committing after the
start of the read action and hence do not qualify for reading. If no key x is found with
a non-deleted tuple, then by our convention, the tuple . 1 ;0/is returned (case 5).
The call find-pages-for-read .P; z / first performs an optimistic traversal of the
versioned B-tree, so that only the leaf page that covers the key z is accessed and
read-latched. If the page does not contain all of the versioned tuples with the least
key x with x z , then the page is unlatched and a second traversal is performed
that read-latches at each level a set of pages whose subtrees together contain all the
versioned tuples with the least key x with x z . Saved paths are used as in the
B-tree algorithms of Chaps. 7 and 8 . The second traversal saves a path that leads to
the leaf page containing the last versioned tuple with key x, that is, the one with the
greatest transaction identifier.
In analogy with the complexity result stated in Theorem 10.14 for bulk-read
actions, we have:
Theorem 12.13 Assume that a read-only transaction T reading from the database
of version start-time .T / performs a bulk-read action RŒs X ;s XV on a versioned B-
tree with n leaf pages. Let P be the set of leaf pages that contain tuples of any
version with keys in some of the ranges in s X . Then, in the absence of structure
modifications, the complexity bound ( 10.1 ) proved in Sect. 10.7 holds for the total
number of page latchings performed.
Proof The proof is similar to that of Theorem 10.14 . Now for each key x in one of
the scanned ranges in s X , we have to read the entire set of versioned tuples with key
x in order to find out which version to read and to skip over to the next key. Unlike
in Theorem 10.14 , the result holds even if update transactions run concurrently with
the read-only transaction, if only no structure modifications are triggered. Because
a read-only transaction does not acquire or observe any locks, no waits other than
those caused by latching occur between the read-only transaction and the update
transactions. The absence of structure modifications in turn implies that the saved
path maintained for the read-only transaction is not invalidated between two read
actions, except that the changes in leaf-page P AGE -LSN s due to updates may at key-
range borders cause a traversal to be started at one page higher than necessary on
the saved path.
t
To the complexity bound mentioned in the above theorem, we must also add the
number of latchings of the commit-time table and the number of fixings of its pages.
Obviously, as we must eventually purge oldest versions from the B-tree, we must
not allow the commit-time table to grow indefinitely either; we address this question
in the Problems section.
Search WWH ::




Custom Search