Module 1 · Storage

Episode 8 Replacement Policies

10 min · SQL · Postgres

Title card of Episode 8: Replacement Policies

▶ This video is coming to YouTube soon.

Which page should a full buffer pool evict? This episode runs FIFO, LRU, Clock and LRU-K on the same requests, shows one sequential scan flushing an LRU cache, and then opens up Postgres: usage counts from 0 to 5, a sweeping clock hand, and the 32-frame ring that keeps a 46 MB scan from flooding shared buffers.

Chapters

  1. 0:00Intro
  2. 0:15One scan, and the cache is gone
  3. 0:34FIFO throws out the hottest page
  4. 1:12LRU: evict the least recently used
  5. 1:48Clock: one bit instead of a list
  6. 2:44Sequential flooding
  7. 3:33LRU-K: count the second-to-last use
  8. 4:21One workload, every policy
  9. 4:59Postgres: the clock sweep
  10. 5:57Postgres: a ring for big scans
  11. 6:46The code: clock sweep
  12. 7:14Proof: usage counts stop at 5
  13. 7:39Proof: a 46 MB scan through 32 frames
  14. 8:28Trade-offs
  15. 9:03Recap
  16. 9:32Next: Lab: I Deleted Half the Table and It Got Bigger