Buffer replacement policies

1. 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).
2. LRU is acceptable in operating systems, however, a database system is able to predict future references more accurately.
3. Consider processing of the relational algebra expression

   

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

    aaaaaaaaaaaa¯for each tuple b of borrower do
   
   		 		 for each tuple c of customer do
   
   		 		 		 if b[cname] = c[cname]
   
   		 		 		 then begin
   
   		 		 		 		 let x be a tuple defined as follows:
   
   		 		 		 		 x[cname]:= b[cname]
   
   		 		 		 		 x[loan#]:= b[loan#]
   
   		 		 		 		 x[street]:= c[street]
   
   		 		 		 		 x[city]:= c[city]
   
   		 		 		 		 include tuple x as part of result of 
   		borrow    customer
   
   		 		 		 end
   
   		 		 end
   
   		 end
   
   

5. Assume that the two relations in this example are stored in different files.
   • Once a tuple of borrower 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 main memory, even though it 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 is unpinned, becoming the most recently used block.
6. 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 main memory unless necessary.
   • File indices are also frequently used, and should generally be in main memory.
   • No single strategy is known that handles all possible scenarios well.
   • Many database systems use LRU, despite of its faults.
   • Concurrency and recovery may need other buffer management strategies, such as delayed buffer-out or forced output.