Subject:
2q
From:
Joe Hellerstein <hellerstein@cs.berkeley.edu>
Date:
Wed, 18 Oct 2006 23:48:51 -0700
To:
joeh@cs.berkeley.edu

DBMIN access patterns:
- sequential
- looping sequential
- random
- hierarchical random
- hierarchical random with sequential
- looping hierarchical random with sequential

LRU?  MRU?

Resistence to sequential passes through mem on a mixed workload?  Looping sequential?

DBMIN approach of optimizer hints?

LRU/k: LRU on the k'th-to-last reference.  Idea: reference *frequency* (popularity in time), not reference *recency*.  The higher k is, the better you damp out bursts...

LRU/k overhead: logn heap mgmt.

LRU/k tuning params:
--> Correlated Ref Period: a window on refs.  During window, don't replace, don't count re-refs.
--> Retained Info Period: how long do you remember info on a page after you evict it? 200 secs?

-- 

2Q Intuition:
--> LRU tries to evict cold pages, but may do so with an even colder page that sits in mem for a long time.  I.e. it's too "trusting" of new pages.  Optimistic.
--> LRU-2 will more aggressively kick out "new" pages that turn out to be cold.  Optimistic, but with enforcement.
--> 2Q does the opposite: rather than punish cold pages, it trusts only hot pages.  Pessimistic.

New pages admitted to the A1 Queue: FIFO.  If you get reref'ed while in A1, you are probably hot.
So on re-ref, you go to the Am queue, which is LRU.

Naive 2Q:
if p is on Am: update LRU position
else if p is on A1: move to head of Am.
else
  if freespace, admit p there.
  else if A1 size is too big, evict tail of A1 and put p in that slot
  else if A1 is too small, steal a frame from Am (LRU) and put p there.
  let A1's new location be head of A1 queue.

Hard: Small A1 max size makes it hard to be hot.  Big A1 max size results in small hot set.

Solution 1: All memory is Am, and A1 is a queue of pointers into Am.
Problem: correlated references result in false promotion to hotness.

Solution 2: Partition A1 into A1in and A1out.  A1in is a staging area for correlated refs, which are ignored.  A1out holds the useful stats: first ref of pageIDs that got promoted to Am or evicted.  Allocated buffer with 25% A1in, and Aout big enough to hold IDs for as many pages as 50% of the buffer.  The rest is Am.

Final solution:
if X is in Am: update LRU position
else if X is in A1out
  reclaimfor(X) (i.e. find space for it in A1 or Am if needed)
  add X to Am's LRU
else if X is in A1in // do nothing
else
  reclaimfor(X)
  add X to head of A1in