Buffer-block Replacement Policies

similar to cache replacement policies

LRU

• replace the block that was used last
• the past is a predictor of the future
• can be really bad sometimes

for each tuple tr of r:
    for each tuple ts of s:
        if ts == tr:
            do something

Typically, a mixed strategy with some hints on replacement is provided by the query optimiser

Toss-Immediate

done with a block? get rid of it.

MRU

Keep track of the most recently used block. When the buffer is full, get rid of it.

Speculation

The buffer manager may speculate the next request by looking at usage statistics. It may pre-emptively store that block in the buffer.