Logging and Buffering - Transaction Processing - page 48

the checkpoint are redone logically on the database, after which the updates by
active transactions are undone logically.
Modern disk-based database management systems usually employ physiological
logging . Here, the log records are physical in terms of the page and logical in
terms of the tuple. For example, the forward-rolling action IŒx; v performed by
transaction T on leaf page p of a sparse B-tree is logged with
n Wh T; I; p; x; v ;n 0 i ,
where p is the page-id of page p.
In the recovery algorithm that we will present later in the next chapter (the ARIES
algorithm), redo actions are always performed in exactly the order in which they are
recorded in the log, which is also the original execution order of the actions on each
page. Thus, the redo of a physiologically logged action can always be performed
physically , that is, on the page whose page-id is recorded in the log record and
even at the same record position where it was originally performed. Physical redo is
efficient, because the target page can be found directly via the page-id: regardless of
what the physical database structure is, it is not necessary to traverse the structure
in search for the target of the action.
To redo an action IŒx; v logged with n Wh T; I; p; x; v ;n 0 i ,pagep is fixed and
write-latched, the tuple .x; v / is inserted into page p,the P AGE -LSN of p is advanced
to n,andp is unlatched and unfixed. To redo an action DŒx; v logged with n W
h T; D; p; x; v ;n 0 i ,pagep is fixed and write-latched, the tuple with key value x in
page p (which is .x; v /) deleted, the P AGE -LSN is advanced, and p is unlatched and
unfixed.
However, the physical undo of a physiologically logged action is not always
possible. This is because the server-process threads that perform the database
actions of transactions release their write latches on the pages that they modify
immediately after the modification is completed—that is, before the transaction
commits—and they can undo their own actions independently of other transactions.
For example, consider a transaction T that performs the action DŒx; v on a leaf
page p of a B-tree. This action is logged with n Wh T; D; p; x; v ;n 0 i . Next, the
process thread that executes T releases its write latch on p and continues executing
other actions. In the meantime, actions by other transactions fill page p so that there
is no room for more tuples, or alternatively, p overflows and is split in two so that the
newly allocated page p 0 covers the key value x.NowT is still active and wants to
undo the action DŒx; v . The undo action D 1 Œx; v cannot be performed physically
on page p.
When an action cannot be undone physically, logical undo is used. Thus, the
undo of the action DŒx; v is first tried on the original page p: the page is fixed and
write-latched, and if it still covers key value x and there is room left for the tuple
.x; v /, then the tuple is inserted into page p. Otherwise, the action is undone by
executing the undo action D 1 Œx; v logically: the search path for key value x is
traversed from the root page of the tree down to the leaf page p 0 that covers x and
the tuple .x; v / is inserted there.