Re: Possible performance improvement: buffer replacement policy

Tom, did we ever test this? I think we did and found that it was the
same or worse, right?

> Those of you with long memories may recall a benchmark that Edmund Mergl
> drew our attention to back in May '99. That test showed extremely slow
> performance for updating a table with many indexes (about 20). At the
> time, it seemed the problem was due to bad performance of btree with
> many equal keys, so I thought I'd go back and retry the benchmark after
> this latest round of btree hackery.
>
> The good news is that btree itself seems to be pretty well fixed; the
> bad news is that the benchmark is still slow for large numbers of rows.
> The problem is I/O: the CPU mostly sits idle waiting for the disk.
> As best I can tell, the difficulty is that the working set of pages
> needed to update this many indexes is too large compared to the number
> of disk buffers Postgres is using. (I was running with -B 1000 and
> looking at behavior for a 100000-row test table. This gave me a table
> size of 3876 pages, plus 11526 pages in 20 indexes.)
>
> Of course, there's only so much we can do when the number of buffers
> is too small, but I still started to wonder if we are using the buffers
> as effectively as we can. Some tracing showed that most of the pages
> of the indexes were being read and written multiple times within a
> single UPDATE query, while most of the pages of the table proper were
> fetched and written only once. That says we're not using the buffers
> as well as we could; the index pages are not being kept in memory when
> they should be. In a query like this, we should displace main-table
> pages sooner to allow keeping more index pages in cache --- but with
> the simple LRU replacement method we use, once a page has been loaded
> it will stay in cache for at least the next NBuffers (-B) page
> references, no matter what. With a large NBuffers that's a long time.
>
> I've come across an interesting article:
> The LRU-K Page Replacement Algorithm For Database Disk Buffering
> Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum
> Proceedings of the 1993 ACM SIGMOD international conference
> on Management of Data, May 1993
> (If you subscribe to the ACM digital library, you can get a PDF of this
> from there.) This article argues that standard LRU buffer management is
> inherently not great for database caches, and that it's much better to
> replace pages on the basis of time since the K'th most recent reference,
> not just time since the most recent one. K=2 is enough to get most of
> the benefit. The big win is that you are measuring an actual page
> interreference time (between the last two references) and not just
> dealing with a lower-bound guess on the interreference time. Frequently
> used pages are thus much more likely to stay in cache.
>
> It looks like it wouldn't take too much work to replace shared buffers
> on the basis of LRU-2 instead of LRU, so I'm thinking about trying it.
>
> Has anyone looked into this area? Is there a better method to try?
>
> regards, tom lane
>

--
Bruce Momjian | http://candle.pha.pa.us
pgman(at)candle(dot)pha(dot)pa(dot)us | (610) 853-3000
+ If your life is a hard drive, | 830 Blythe Avenue
+ Christ can be your backup. | Drexel Hill, Pennsylvania 19026