Information Technology Reference
In-Depth Information
substituted for the old structure, and the space occupied by the old structure is
deallocated. The problem here, as in online index construction, is how to capture
the updates made by transactions to the old structure when the construction of the
new structure is in progress.
One solution is to use a technique reminiscent to maintaining a
remote backup
copy
of a database (to be discussed in Sect.
13.8
). The solution outlined below is
based on unloading the data from the structure to be reorganized, reloading the data
in reorganized form into a
shadow copy
, applying the log to bring the shadow copy
up to date so as to reflect the updates by transactions into the original copy, and
substituting the shadow copy atomically for the original copy. The method applies
to the reorganization of both sparse primary B-trees and dense secondary B-tree
indexes.
The online reorganization of the primary B-tree for relation r.X;V/ consists of
the following steps (assuming that no secondary indexes exist on r ):
1. Record the current tail (
LSN
) of the log.
2. Initialize an empty sparse B-tree structure, the shadow copy.
3. Scan the tuples in the leaf pages of the original B-tree of relation r and upload
the tuples into the shadow copy using several system transactions with bulk-
insert actions; no locks on the tuples are acquired by these transactions.
4. Perform a system transaction that scans the log forward, starting from the
recorded
LSN
, and, at every logged update action (I , D, W , I
1
, D
1
, W
1
)
on r encountered, applies the logical action to the shadow copy, skipping any
log records for structure modifications encountered.
5. Record the current tail (
LSN
) of the log.
6. U-lock r .
7. Repeat step 4.
8. X-lock r .
9. Write-latch the system-catalog page q that contains the primary-index informa-
tion for r .
10. Abort all transactions that are waiting for a lock on r .
11. Make the primary-index information in page q to point to the shadow copy.
12. Unlatch q. Unlock r .
The update-mode lock (U lock) on r acquired in step 6 quiesces updates and thus
ends the accumulation of further log records; so step 7 will capture any updates
that arrive after performing step 4 for the first time. The U lock also suspends
the granting of all further IS or S locks on r . As each transaction must protect its
updates by commit-duration X locks, the U lock on r is granted only after all the
transactions that have updated the original B-tree of r have committed (or completed
their rollback). Finally X-locking r in step 8 quiesces all scans of the original B-tree
of r by transactions that run at an isolation level higher than 1
ı
.
It is necessary to abort every transaction that is waiting for a lock on r in step 10,
even though the locks requested are logical and hence readily appropriate to the new
structure of r as well. If a lock on r were granted to a transaction that has located the
target of its action by traversing the old structure of r before being forced to wait
