Buffer Management

1. • We need to use disk storage for the database, and to transfer blocks of data between MM and disk.
   • We also want to minimize the number of such transfers, as they are time-consuming.
   • One way is to keep as many blocks as possible in MM.
   • Usually, we cannot keep all blocks in MM, so we need to manage the allocation of available MM space.
   • The buffer is the part of MM available for storage of copies of disk blocks.
   • The subsystem responsible for the allocation of buffer space is called the buffer manager.
   • The buffer manager handles all requests for blocks of the database.
   • If the block is already in MM, the address in MM is given to the requestor.
   • If not, the buffer manager must read the block in from disk (possibly displacing some other block if the buffer is full) and then pass the address in MM to the requestor.
2. The buffer manager must use some sophisticated techniques in order to provide good service:
   • Replacement Strategy - When there is no room left in the buffer, some block must be removed to make way for the new one. Typical operating system memory management schemes use a ``least recently used'' (LRU) method. (Simply remove the block least recently referenced.) This can be improved upon for database applications.
   • Pinned Blocks - For the database to be able to recover from crashes, we need to restrict times when a block maybe written back to disk. A block not allowed to be written is said to be pinned. Many operating systems do not provide support for pinned blocks, and such a feature is essential if a database is to be ``crash resistant''.
   • Forced Output of Blocks - Sometimes it is necessary to write a block back to disk even though its buffer space is not needed. (Called the forced output of a block.) This is due to the fact that MM contents (and thus the buffer) are lost in a crash, while disk data usually survives.
3. Replacement Strategy: Goal is minimization of accesses to disk. Generally it is hard to predict which blocks will be referenced. So operating systems use the history of past references as a guide to prediction.
   • General Assumption: Blocks referenced recently are likely to be used again.
   • Therefore: if we need space, throw out the least recently referenced block. (LRU replacement scheme)
4. LRU is acceptable in operating systems, however, a database system is able to predict future references more accurately.

5. Consider processing of the relational algebra expression

   

6. Further, assume the strategy to process this request is given by the following pseudo-code:

   

7. Assume that the two relations in this example are stored in different files.
   • Once a tuple of borrow has been processed it is not needed again.
   • Therefore, once processing of an entire block of tuples is finished, that block is not needed in MM.

   • Note that this block has been used very recently.
   • Buffer manager should free the space occupied by a borrow block as soon as it is processed.

   • This strategy is called toss-immediate.
   • Consider blocks containing customer tuples.

   • Every block of customer tuples must be examined once for every tuple of the borrow relation.
   • When processing of a customer block is completed, it will not be used again until all other customer blocks have been processed.

   • This means the most recently used (MRU) block will be the last block to be re-referenced, and the least recently used will be referenced next.
   • This is the opposite of LRU assumptions.
   • So for inner block, use MRU strategy - if a customer block must be removed from the buffer, choose MRU block.

   • For MRU strategy, the system must pin the customer block currently being processed until the last tuple has been processed.
   • Then it may be unpinned, becoming the most recently used block.
8. The buffer manager may also use statistical information regarding the probability that a request will reference a particular relation.
   • The data dictionary is the most frequently-used part of the database.
   • It should, therefore, not be removed from MM unless necessary.

   • File indices (Chapter 8) are also frequently used, and should generally be in MM.
   • No single strategy is known that handles all possible scenarios well.

   • Many database systems use LRU, with all its faults.
   • Other factors enter with concurrent users, where requests may be delayed to ensure integrity of the database.