Buffer Management

Buffer Management Strategies (berkeley.edu)

Algorithm

Domain Separation Algorithms

  • Categorize pages into different domains
    • e.g. one domain for non-leaf b-tree one for leaf
  • Limitation
    • Static: Can’t dynamic adjust domain, (importance might be different for different queries)
    • Split into 2 domains
      • a new domain A page and all page in domain A might be more important than any page in domain B, yet it will replace a page in domain A
    • Does not prevent interference among competing users
    • Need separate mechanism to prevent thrashing

“New” Algorithm

  • Buffer pool is subdivided and allocated on a per-relation basis
  • Each active relation assigned a resident set that is initially empty, resident sets of relations are linked in a priority list.
  • MRU within each relation

Hot Set Algorithm

  • Hot set
    • e.g. nested-loop join: inner relation’s page counts + 1
  • Each query is provided a fixed amount of buffer predicted by a hot set model
  • Assume LRU (bad?)

DBMIN

Query Locality Set Model

  • Predictable page reference pattern
    • Sequential References
      • Straight Sequential: Every page scanned once (e.g. select)
      • Clustered Sequential: Some scan might go back (e.g. merge join)
      • Looping sequential: e.g. nested-loop join (might want to use MRU)
    • Random References
      • Independent Random: random
      • Clustered Random: Similar to Clustered Sequential, but the inner relations is “random”
    • Hierarchical References
      • Straight Hierarchical: Go from root to leaf and get one tuple
      • H/SS H/CS: If the leaf is Clustered/Straight Sequential
      • Looping Hierarchical: Root will be used more frequently

DBMIN algorithm

  • Per file instance:
    • $l$: desired locality set size
    • $r$: actual locality set size
    • replacement policy
  • When a page requested:
    1. If found in global table and locality set => update statistics
    2. If found in memory not in locality set
      • Update locality set
      • Replace page using replacement policy (does not actually swap out)
    3. Not in memory
      • read from disk, proceed to (2)
  • Design different buffer management strategy for each type of reference pattern

Questions:

  • Simulation
  • The locality set size and the replacement policy for each file instance were manually determined