I have thought of a few new TODO performance items:

1)  Someone at O'Reilly suggested that we order our duplicate index
entries by tid so if we are hitting the heap for lots of duplicates, the
hits will be on sequential pages.  Seems like a nice idea.

2)  After Tatsuo's report of running 1000 backends on pgbench and from a
Solaris report, I think we should have a queue of backends waiting for a
spinlock, rather than having them sleep and try again.  This is
particularly important for multi-processor machines.

3)  I am reading the Solaris Internals book and there is mention of a
"free behind" capability with large sequential scans.  When a large
sequential scan happens that would wipe out all the old cache entries,
the kernel detects this and places its previous pages first on the free
list.  For out code, if we do a sequential scan of a table that is
larger than our buffer cache size, I think we should detect this and do
the same.  See http://techdocs.postgresql.org for my performance paper
for an example.

New TODO entries are:

	* Order duplicate index entries by tid
	* Add queue of backends waiting for spinlock
	* Add free-behind capability for large sequential scans

I will modify them with any comments people have.

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

Mon, 30 Jul 2001 12:49:57 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Performance TODO items
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> New TODO entries are:
> 	* Add queue of backends waiting for spinlock

I already see:

* Create spinlock sleepers queue so everyone doesn't wake up at once


BTW, I agree with Vadim's opinion that we should add a new type of lock
(intermediate between spinlocks and lockmanager locks) rather than try
to add new semantics onto spinlocks.  For example, it'd be very nice to
distinguish read-only and read-write access in this new kind of lock,
but we can't expect spinlocks to be able to do that.

			regards, tom lane

Mon, 30 Jul 2001 15:24:01 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Performance TODO items 
> 3)  I am reading the Solaris Internals book and there is mention of a
> "free behind" capability with large sequential scans.  When a large
> sequential scan happens that would wipe out all the old cache entries,
> the kernel detects this and places its previous pages first
> on the free list.  For out code, if we do a sequential scan of a table
> that is larger than our buffer cache size, I think we should detect
> this and do the same.  See http://techdocs.postgresql.org for my
> performance paper for an example.
>
> New TODO entries are:
>
> 	* Order duplicate index entries by tid
> 	* Add queue of backends waiting for spinlock
> 	* Add free-behind capability for large sequential scans

So why do we cache sequetially-read pages?  Or at least not have an
option to control it?

Oracle (to the best of my knowledge) does NOT cache pages read by a
sequential index scan for at least two reasons/assumptions (two being
all that I can recall):

1. Caching pages for sequential scans over sufficiently large tables
will just cycle the cache.  The pages that will be cached at the end of
the query will be the last N pages of the table, so when the same
sequential query is run again, the scan from the beginning of the table
will start flushing the oldest cached pages which are more than likely
going to be the ones that will be needed at the end of the scan, etc,
etc.  In a multi-user environment, the effect is worse.

2. Concurrent or consective queries in a dynamic database will not
generate plans that use the same sequential scans, so they will tend to
thrash the cache.

Now there are some databases where the same general queries are run time
after time and caching the pages from sequential scans does make sense,
but in larger, enterprise-type systems, indices are created to help
speed up the most used queries and the sequential cache entries only
serve to clutter the cache and flush the useful pages.

Is there any way that caching pages read in by a sequential scan could
be made a configurable-option?

Any chance someone could run pgbench on a test system set up to not
cache sequential reads?

Darren


Mon, 30 Jul 2001 15:32:50 -0400
"Darren King" <darrenk@insightdist.com>
RE: Performance TODO items
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > New TODO entries are:
> > 	* Add queue of backends waiting for spinlock
> 
> I already see:
> 
> * Create spinlock sleepers queue so everyone doesn't wake up at once

That is an old copy of the TODO.  I reworded it.  You will only see this
now:

	* Improve spinlock code, perhaps with OS semaphores, sleeper queue, or
	  spining to obtain lock on multi-cpu systems

> BTW, I agree with Vadim's opinion that we should add a new type of lock
> (intermediate between spinlocks and lockmanager locks) rather than try
> to add new semantics onto spinlocks.  For example, it'd be very nice to
> distinguish read-only and read-write access in this new kind of lock,
> but we can't expect spinlocks to be able to do that.

Yes, I agree too.  On a uniprocessor machine, if I can't get the
spinlock, I want to yield the cpu, ideally for less than 10ms.  On a
multi-cpu machine, if the lock is held by another CPU and that process
is running, we want to spin waiting for the lock to free.   If not, we
can sleep.  We basically need some more sophisticated semantics around
these locks, or move to OS semaphores.

In fact, can't we sleep on an interruptible system call, and send
signals to processes when we release the lock?  That way we don't have
the 10ms sleep limitation.  One idea is to have a bytes for each backend
in shared memory and have each backend set the bit if it is waiting for
the semaphore.  There would be no contention with multiple backends
registering their sleep at the same time.

We have seen reports of 4-cpu systems having poor performance while the
system is only 12% busy, perhaps because the processes are all sleeping
waiting for the next tick.

I think multi-cpu machines are going to give us new challenges.

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

Mon, 30 Jul 2001 17:10:32 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Performance TODO items
> So why do we cache sequetially-read pages?  Or at least not have an
> option to control it?
> 
> Oracle (to the best of my knowledge) does NOT cache pages read by a
> sequential index scan for at least two reasons/assumptions (two being
> all that I can recall):
> 
> 1. Caching pages for sequential scans over sufficiently large tables
> will just cycle the cache.  The pages that will be cached at the end of
> the query will be the last N pages of the table, so when the same
> sequential query is run again, the scan from the beginning of the table
> will start flushing the oldest cached pages which are more than likely
> going to be the ones that will be needed at the end of the scan, etc,
> etc.  In a multi-user environment, the effect is worse.
> 
> 2. Concurrent or consective queries in a dynamic database will not
> generate plans that use the same sequential scans, so they will tend to
> thrash the cache.
> 
> Now there are some databases where the same general queries are run time
> after time and caching the pages from sequential scans does make sense,
> but in larger, enterprise-type systems, indices are created to help
> speed up the most used queries and the sequential cache entries only
> serve to clutter the cache and flush the useful pages.
> 
> Is there any way that caching pages read in by a sequential scan could
> be made a configurable-option?
> 
> Any chance someone could run pgbench on a test system set up to not
> cache sequential reads?

Yep, that is the issue.  If the whole table fits in the cache, it is
great.  If not, it is useless or worse because it forces out other
pages.  Right now the cache is oldest-out and doesn't know anything
about access patterns.  We would need to get that info passed in the
cache, probably some function parameter.

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

Mon, 30 Jul 2001 17:14:01 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Performance TODO items
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> I have thought of a few new TODO performance items:
> 1)  Someone at O'Reilly suggested that we order our duplicate index
> entries by tid so if we are hitting the heap for lots of duplicates, the
> hits will be on sequential pages.  Seems like a nice idea.

A more general solution is for indexscan to collect up a bunch of TIDs
from the index, sort them in-memory by TID order, and then probe into
the heap with those TIDs.  This is better than the above because you get
nice ordering of the heap accesses across multiple key values, not just
among the tuples with the same key.  (In a unique or near-unique index,
the above idea is nearly worthless.)

In the best case there are few enough TIDs retrieved from the index that
you can just do this once, but even if there are lots of TIDs, it should
be a win to do this in batches of a few thousand TIDs.  Essentially we
decouple indexscans into separate index-access and heap-access phases.

One big problem is that this doesn't interact well with concurrent VACUUM:
our present solution for concurrent VACUUM assumes that indexscans hold
a pin on an index page until they've finished fetching the pointed-to
heap tuples.  Another objection is that we'd have a harder time
implementing the TODO item of marking an indextuple dead when its
associated heaptuple is dead.  Anyone see a way around these problems?

			regards, tom lane

Mon, 30 Jul 2001 17:53:30 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Performance TODO items 
> A more general solution is for indexscan to collect up a bunch of TIDs
> from the index, sort them in-memory by TID order, and then probe into
> the heap with those TIDs.  This is better than the above because you get
> nice ordering of the heap accesses across multiple key values, not just
> among the tuples with the same key.  (In a unique or near-unique index,
> the above idea is nearly worthless.)
> 
> In the best case there are few enough TIDs retrieved from the index that
> you can just do this once, but even if there are lots of TIDs, it should
> be a win to do this in batches of a few thousand TIDs.  Essentially we
> decouple indexscans into separate index-access and heap-access phases.
> 
> One big problem is that this doesn't interact well with concurrent VACUUM:
> our present solution for concurrent VACUUM assumes that indexscans hold
> a pin on an index page until they've finished fetching the pointed-to
> heap tuples.  Another objection is that we'd have a harder time
> implementing the TODO item of marking an indextuple dead when its
> associated heaptuple is dead.  Anyone see a way around these problems?

Interesting.  I figured the cache could keep most pages in such a case. 
I was thinking more of helping file system readahead by requesting the
earlier block first in a mult-block request.  Not sure how valuable that
would be.

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

Mon, 30 Jul 2001 18:11:44 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Performance TODO items