I was researching on cache replacement strategy as well. 2Q has one
disadvantage see this exellent paper:
http://www.almaden.ibm.com/cs/people/dmodha/#ARC see the paper
"ARC: A Self-Tuning, Low Overhead Replacement Cache" for theory and "One
Up on LRU" for implementation details. ARC requires no tuning and can
switch fast between chaging patterns. Best of all is it is resistant to a
"sequential scan" pattern. and i think it's even easier to implement then
2q :) 

does pgbench test with relatively large sequential scans?

 


Tue, 24 Jun 2003 12:13:51 +0200 (MEST)
xoror@infuse.org
lru cache replacement
On Tue, 24 Jun 2003 xoror@infuse.org wrote:

> I was researching on cache replacement strategy as well. 2Q has one
> disadvantage see this exellent paper:
> http://www.almaden.ibm.com/cs/people/dmodha/#ARC see the paper
> "ARC: A Self-Tuning, Low Overhead Replacement Cache" for theory and "One
> Up on LRU" for implementation details. ARC requires no tuning and can
> switch fast between chaging patterns. Best of all is it is resistant to a
> "sequential scan" pattern. and i think it's even easier to implement then
> 2q :) 
> 
> does pgbench test with relatively large sequential scans?
> 

BTW, i'm also willing to implement ARC for pgsql if you guys also think
it's a better algoritm. We will no longer have to tweak parameters like
Kin, Kout. ARC also uses 2 buffers like 2q.  


Tue, 24 Jun 2003 13:13:27 +0200 (MEST)
xoror@infuse.org
Re: lru cache replacement
xoror,

On Tue, 24 Jun 2003 12:13:51 +0200 (MEST)
xoror@infuse.org wrote:

> I was researching on cache replacement strategy as well. 2Q has one
> disadvantage see this exellent paper:
> http://www.almaden.ibm.com/cs/people/dmodha/#ARC see the paper
> "ARC: A Self-Tuning, Low Overhead Replacement Cache" for theory and "One
> Up on LRU" for implementation details. ARC requires no tuning and can
> switch fast between chaging patterns. Best of all is it is resistant to a
> "sequential scan" pattern. and i think it's even easier to implement then
> 2q :) 

Thanks for your information. I check the paper and implement it by Java for
testing.

> does pgbench test with relatively large sequential scans?

Probably no. 

-- 
Yutaka tanida <yutaka@nonsensecorner.com>
http://www.nonsensecorner.com/


Tue, 24 Jun 2003 21:23:10 +0900
Yutaka tanida <yutaka@nonsensecorner.com>
Re: lru cache replacement
Yutaka tanida <yutaka@nonsensecorner.com> writes:
> xoror@infuse.org wrote:
>> does pgbench test with relatively large sequential scans?

> Probably no. 

pgbench tries to avoid any seqscans at all, I believe, so it wouldn't be
very useful for testing a method that's mainly intended to prevent
seqscans from blowing out the cache.

I tried to implement LRU-2 awhile ago, and got discouraged when I
couldn't see any performance improvement.  But I was using pgbench as
the test case, and failed to think about its lack of seqscans.

We could probably resurrect that code for comparison to 2Q, if anyone
can devise more interesting benchmark cases to test.

BTW, when you were running your test case, what shared_buffers did you
use?

			regards, tom lane

Tue, 24 Jun 2003 10:27:09 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: lru cache replacement 
> Yutaka tanida <yutaka@nonsensecorner.com> writes:
> > xoror@infuse.org wrote:
> >> does pgbench test with relatively large sequential scans?
> 
> > Probably no. 
> 
> pgbench tries to avoid any seqscans at all, I believe, so it wouldn't be
> very useful for testing a method that's mainly intended to prevent
> seqscans from blowing out the cache.
> 
> I tried to implement LRU-2 awhile ago, and got discouraged when I
> couldn't see any performance improvement.  But I was using pgbench as
> the test case, and failed to think about its lack of seqscans.
> 
> We could probably resurrect that code for comparison to 2Q, if anyone
> can devise more interesting benchmark cases to test.
> 
> BTW, when you were running your test case, what shared_buffers did you
> use?

It's very easy to test sequencial scans using pgbench: just drop the
index from account table. I am using this technique to generate heavy
loads.
--
Tatsuo Ishii

Tue, 24 Jun 2003 23:59:34 +0900 (JST)
Tatsuo Ishii <t-ishii@sra.co.jp>
Re: lru cache replacement 
On Tue, 24 Jun 2003, Tom Lane wrote:

> Yutaka tanida <yutaka@nonsensecorner.com> writes:
> > xoror@infuse.org wrote:
> >> does pgbench test with relatively large sequential scans?
> 
> > Probably no. 
> 
> pgbench tries to avoid any seqscans at all, I believe, so it wouldn't be
> very useful for testing a method that's mainly intended to prevent
> seqscans from blowing out the cache.
> 
> I tried to implement LRU-2 awhile ago, and got discouraged when I
> couldn't see any performance improvement.  But I was using pgbench as
> the test case, and failed to think about its lack of seqscans.

Yes , lru-2 will behave like LRU under 'normal' load. it will detect
sequential scans and adapt to it. I think that was why you didn't
see any substantial gain in cache hits. though I think ARC does a better
job. LRU-2 also has logaritmic complexity overhead.

The ARC guys have tested with real traces from a Db of a large insurrance
company and the results were quite encouraging. (a lot of other traces
where examined as well)
 
> We could probably resurrect that code for comparison to 2Q, if anyone
> can devise more interesting benchmark cases to test.

As i stated before, i'm willing to implement ARC and to see how they all
compare. 




Tue, 24 Jun 2003 17:12:23 +0200 (MEST)
xoror@infuse.org
Re: lru cache replacement 

On Tue, 24 Jun 2003 10:27:09 -0400
Tom Lane <tgl@sss.pgh.pa.us> wrote:

> I tried to implement LRU-2 awhile ago, and got discouraged when I
> couldn't see any performance improvement.  But I was using pgbench as
> the test case, and failed to think about its lack of seqscans.

How about cache hit rate?

> BTW, when you were running your test case, what shared_buffers did you
> use?

I use 16,64,256 and 4096.


---
Yutaka tanida<yutaka@hi-net.zaq.ne.jp>


Wed, 25 Jun 2003 00:35:42 +0900
Yutaka tanida <yutaka@hi-net.zaq.ne.jp>
Re: lru cache replacement 

On Tue, 24 Jun 2003 10:27:09 -0400
Tom Lane <tgl@sss.pgh.pa.us> wrote:

> I tried to implement LRU-2 awhile ago, and got discouraged when I
> couldn't see any performance improvement.  But I was using pgbench as
> the test case, and failed to think about its lack of seqscans.

How about cache hit rate?

> BTW, when you were running your test case, what shared_buffers did you
> use?

I use 16,64,256 and 4096.


---
Yutaka tanida<yutaka@hi-net.zaq.ne.jp>


Wed, 25 Jun 2003 00:43:56 +0900
Yutaka tanida <yutaka@nonsensecorner.com>
Re: lru cache replacement 

On Wed, 25 Jun 2003 00:43:56 +0900
Yutaka tanida <yutaka@nonsensecorner.com> wrote:

> > BTW, when you were running your test case, what shared_buffers did you
> > use?
> 
> I use 16,64,256 and 4096.

I missed.  My shown result(+4% cache hit rate) is shared_buffers=64.

---
Yutaka tanida<yutaka@hi-net.zaq.ne.jp>
謎のWebsite http://www.nonsensecorner.com/


Wed, 25 Jun 2003 01:29:24 +0900
Yutaka tanida <yutaka@nonsensecorner.com>
Re: lru cache replacement 
xoror@infuse.org wrote:
> > I tried to implement LRU-2 awhile ago, and got discouraged when I
> > couldn't see any performance improvement.  But I was using pgbench as
> > the test case, and failed to think about its lack of seqscans.
> 
> Yes , lru-2 will behave like LRU under 'normal' load. it will detect
> sequential scans and adapt to it. I think that was why you didn't
> see any substantial gain in cache hits. though I think ARC does a better
> job. LRU-2 also has logaritmic complexity overhead.
> 
> The ARC guys have tested with real traces from a Db of a large insurrance
> company and the results were quite encouraging. (a lot of other traces
> where examined as well)
>  
> > We could probably resurrect that code for comparison to 2Q, if anyone
> > can devise more interesting benchmark cases to test.
> 
> As i stated before, i'm willing to implement ARC and to see how they all
> compare. 

Great.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Sat, 28 Jun 2003 23:37:03 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: lru cache replacement