Logging and Buffering - Transaction Processing - page 61

least-recently-used or LRU page-replacement strategy is often used: when all buffer
frames are allocated, take to disk the page that has been unused for the longest time.
For virtual memory, LRU is a sufficient strategy, because the behavior of all kinds
of programs is difficult to predict. For database pages, however, better strategies
can be used: from the form of an SQL statement, the database management system
can often predict which pages will be needed in executing the statement. The
operating system needs to rely on the past to predict the future, while the database
management system may know something about at least the near future.

Example 3.4 Algorithm 3.4 computes the natural join r ‰ s of relations r.A;B/
and s.B; C /, when the join attribute B is the key of neither relation, the relations
are stored in separate files, and there are no indexes (locking operations have been
left out of the algorithm).

Algorithm 3.4 Computing the natural join r.A;B/ ‰ s.B; C /
for each data page p of r do
fix-and-read-latch .p/
for each data page q of s do
fix-and-read-latch .q/
for each r -tuple t in page p and each s-tuple u in page q do
if t.B/D u .B/ then
output the joined tuple t u
end if
end for
unlatch-and-unfix .q/
end for
unlatch-and-unfix .p/
end for

After page p of r has been used, it is no longer needed. Thus, a good buffering
policy for r 's pages is “toss immediate.” For each page p of r , all pages q of s must
be processed. After a page q has been processed, it is needed only after all other
pages of s have been processed. A good buffering policy for the pages of s is MRU
(most recently used), that is, the opposite of LRU .
Thepageofr that is being processed at a given time is fixed into the buffer during
the processing of s, after which it can be designated to be an MRU page. Thus, MRU
is an optimal strategy for the pages of both r and s. t

Problems

3.1 With physiological logging, what log records are produced by the transactions
of Problem 1.2 . Give the log records produced (a) for the read-write model, (b) the
key-range model. You may assume that no structure modifications occur and that no
other transactions are in progress.