Anti-Caching

  • Mark each tuple as cold or hot, move cold tuples to cold storage
    • 8 byte overhead per tuple
    • cannot move indexes to cold storage

Siberia

  • Classify each tuple as cold or hot
  • Indexes only cover hot tuples
  • Bloom filter to access cold tuples
    • complex

Swapping

  • No overhead (hardware support)
    • database lose control

Hardware-assisted Access Tracking

  • Modify OS kernel => still has control over page eviction
    • Cannot handle index structures

Building Blocks

Pointer Swizzling

  • Traditional buffer manager:
    • always use page identifier
    • lookup hash table to find page
  • Swizzling
    • Use virtual address directly if in memory
    • Use page identifier for disk

Efficient Page Replacement

  • Traditional:
    • LRU, Second chance
  • New:
    • Randomly select 10% of page, put into a queue, mark as cooling
    • If access, back to hot
    • If reach to queue front, evict

Leanstore

  • Use a global lock to protect cooling and in-flight I/O data structures
  • FIFO Queue: Might be a FIFO linked list, hash table points to entry in queue
  • I/O: acquire global lock -> acquire OS I/O frame lock -> release global lcok
  • Traditional:
    • Lock per page
    • Reading page acquire a lock, so other thread will not swap it out
  • New epoch-based:
    • Global epoch regularly increase
    • thread set local epoch to global before reading
    • Check min(all local epoch) before evicting a page

Comments

  • HDD/SSD