
> This topic seems to come up a lot.  Is there something we are missing in
> the FAQ?

Most of the reports we seem to see are the usual, "but the seq scan is actually 
faster" case. Daniel actually has a case where the optimizer chooses a bad plan.

The difficulty seems to be, that the optimizer cooses a correct plan for an idle
system, but with his workload the index path would be far better (2 vs 4 Minutes).

This is one of the main problems of the current optimizer which imho rather 
aggressively chooses seq scans over index scans. During high load this does 
not pay off. My preference would actually be a way to make the optimizer
choose a plan that causes minimal workload, and not shortest runtime 
(which will obviously only be fast with low overall workload)
The reasoning behind this is, that during low workload your response times
will be good enough with a "bad" plan, but during high workload your response 
times will be best with a plan that produces the least additional workload.

Andreas

Fri, 11 Jan 2002 12:46:42 +0100
"Zeugswetter Andreas SB SD" <ZeugswetterA@spardat.at>
Re: again on index usage
"Zeugswetter Andreas SB SD" <ZeugswetterA@spardat.at> writes:
> My preference would actually be a way to make the optimizer
> choose a plan that causes minimal workload, and not shortest runtime 

?? I am not sure that I see the difference.

What I think you are saying is that when there's lots of competing work,
seqscans have less advantage over indexscans because the
sequential-access locality advantage is lost when the disk drive has to
go off and service some other request.  If that's the mechanism, I think
that the appropriate answer is just to reduce random_page_cost.  It's
true that the current default of 4.0 was chosen using measurements on
otherwise-unloaded systems.  If you assume that the system is (a) too
busy to do read-aheads for you, and (b) has to move the disk arm to
service other requests between each of your requests, then it's not
clear that sequential reads have any performance advantage at all :-(.
I don't think I'd go as far as to lower random_page_cost to 1.0, but
certainly there's a case for using an intermediate value.

			regards, tom lane

Fri, 11 Jan 2002 11:34:07 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: again on index usage 
Zeugswetter Andreas SB SD wrote:


> This is one of the main problems of the current optimizer which imho rather 
> aggressively chooses seq scans over index scans. During high load this does 
> not pay off.


Bingo ... dragging huge tables through the buffer cache via a sequential 
scan guarantees that a) the next query sequentially scanning the same 
table will have to read every block again (if the table's longer than 
available PG and OS cache) b) on a high-concurrency system other queries 
end up doing extra I/O, too.

Oracle partially mitigates the second effect by refusing to trash its 
entire buffer cache on any given sequential scan.  Or so I've been told 
by people who know Oracle well.  A repeat of the sequential scan will 
still have to reread the entire table but that's true anyway if the 
table's at least one block longer than available cache.

Of course, Oracle picks sequential scans in horribly and obviously wrong 
cases as well.  On one project over the summer I had a query Oracle 
refused to use an available index on until I told it to do so explictly, 
and when I did it sped up by a factor of about 100.

All optimizers will fail miserably for certain queries and datasets.

-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org


Fri, 11 Jan 2002 08:41:11 -0800
Don Baccus <dhogaza@pacifier.com>
Re: again on index usage
Don Baccus wrote:
> Zeugswetter Andreas SB SD wrote:
> 
> 
> > This is one of the main problems of the current optimizer which imho rather 
> > aggressively chooses seq scans over index scans. During high load this does 
> > not pay off.
> 
> 
> Bingo ... dragging huge tables through the buffer cache via a sequential 
> scan guarantees that a) the next query sequentially scanning the same 
> table will have to read every block again (if the table's longer than 
> available PG and OS cache) b) on a high-concurrency system other queries 
> end up doing extra I/O, too.
> 
> Oracle partially mitigates the second effect by refusing to trash its 
> entire buffer cache on any given sequential scan.  Or so I've been told 
> by people who know Oracle well.  A repeat of the sequential scan will 
> still have to reread the entire table but that's true anyway if the 
> table's at least one block longer than available cache.

That is on our TODO list, at least.

-- 
  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

Fri, 11 Jan 2002 11:42:43 -0500 (EST)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: again on index usage
Bruce Momjian wrote:


>>Oracle partially mitigates the second effect by refusing to trash its 
>>entire buffer cache on any given sequential scan.  Or so I've been told 
>>by people who know Oracle well.  A repeat of the sequential scan will 
>>still have to reread the entire table but that's true anyway if the 
>>table's at least one block longer than available cache.
>>
> 
> That is on our TODO list, at least.


I didn't realize this, it's good news.  (I don't follow PG development 
closely these days).

BTW overall I think the cost-estimating portion of the PG optimizer does 
about as well as Oracle's.   Oracle is a lot smarter about doing 
transformations of certain types of queries (turning "scalar in (select 
...)" into something akin to an "exists") but of course this has nothing 
to do with estimating the cost of index vs. sequential scans.


-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org


Fri, 11 Jan 2002 09:01:46 -0800
Don Baccus <dhogaza@pacifier.com>
Re: again on index usage
>>>Tom Lane said:
 > "Zeugswetter Andreas SB SD" <ZeugswetterA@spardat.at> writes:
 > > My preference would actually be a way to make the optimizer
 > > choose a plan that causes minimal workload, and not shortest runtime 
 > 
 > ?? I am not sure that I see the difference.

There can be difference only if the optimizer takes into account already 
executing plans (by other backends).

 > What I think you are saying is that when there's lots of competing work,
 > seqscans have less advantage over indexscans because the
 > sequential-access locality advantage is lost when the disk drive has to
 > go off and service some other request.

This is exactly my point. The primary goal of the optimizer in my opinion 
should be to avoid trashing. :-) Now, it is not easy to figure out when the 
system starts trashing - at least not a portable way I can think of 
immediately.

 > I don't think I'd go as far as to lower random_page_cost to 1.0, but
 > certainly there's a case for using an intermediate value.

The question is: how does one find the proper value? That is, is it possible to design planner benchmarking utility to aid in tuning Postgres? One that does not execute single query and optimize on idle system.

Daniel


Fri, 11 Jan 2002 19:05:45 +0200
Daniel Kalchev <daniel@digsys.bg>
Re: again on index usage 
On Fri, Jan 11, 2002 at 11:42:43AM -0500, Bruce Momjian wrote:
> Don Baccus wrote:
> > Zeugswetter Andreas SB SD wrote:
> > 
> > 
> > > This is one of the main problems of the current optimizer which imho rather 
> > > aggressively chooses seq scans over index scans. During high load this does 
> > > not pay off.
> > 
> > 
> > Bingo ... dragging huge tables through the buffer cache via a sequential 
> > scan guarantees that a) the next query sequentially scanning the same 
> > table will have to read every block again (if the table's longer than 
> > available PG and OS cache) b) on a high-concurrency system other queries 
> > end up doing extra I/O, too.
> > 
> > Oracle partially mitigates the second effect by refusing to trash its 
> > entire buffer cache on any given sequential scan.  Or so I've been told 
> > by people who know Oracle well.  A repeat of the sequential scan will 
> > still have to reread the entire table but that's true anyway if the 
> > table's at least one block longer than available cache.
> 
> That is on our TODO list, at least.
> 

Hmm, on Linux this sort of behavior (skip the pg buffers for sequential
scans) would have interesting load senstive behavior: since Linux uses
all not-otherwise in use RAM as buffer cache, if you've got a low-load
system, even very large tables will be cached. Once other processes start
competing for RAM, your buffers go away. Bruce, what does xBSD do?

I like it, since anything that needs to be sensitive to system wide
information, like the total load on the machine, should be handled by
the system, not a particular app.

Ross

Fri, 11 Jan 2002 11:22:09 -0600
"Ross J. Reedstrom" <reedstrm@rice.edu>
Re: again on index usage
Daniel Kalchev <daniel@digsys.bg> writes:
>>> I don't think I'd go as far as to lower random_page_cost to 1.0, but
>>> certainly there's a case for using an intermediate value.

> The question is: how does one find the proper value? That is, is it
> possible to design planner benchmarking utility to aid in tuning
> Postgres?

The trouble is that getting trustworthy numbers requires huge test
cases, because you have to swamp out the effects of the kernel's own
buffer caching.  I spent about a week running 24-hour-constant-disk-
banging experiments when I came up with the 4.0 number we use now,
and even then I didn't feel that I had a really solid range of test
cases to back it up.

My advice to you is just to drop it to 2.0 and see if you like the plans
you get any better.

			regards, tom lane

Fri, 11 Jan 2002 12:42:40 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: again on index usage 
Ross J. Reedstrom wrote:


> Hmm, on Linux this sort of behavior (skip the pg buffers for sequential
> scans) would have interesting load senstive behavior: since Linux uses
> all not-otherwise in use RAM as buffer cache, if you've got a low-load
> system, even very large tables will be cached. Once other processes start
> competing for RAM, your buffers go away. Bruce, what does xBSD do?


For people who run dedicated database services simply not using pg 
buffers for sequential scans is probably too simplistic.  Assuming one 
allocates a very large pg buffer space, as I tend to do.  Remember that 
shuffling data between a pg buffer and OS cache buffer takes cycles, and 
modern machines tend to be starved for memory bandwidth - perhaps 
another reason why Oracle requested and got writes that bypass the OS 
cache entirely?  This bypasses the byte-shuffling.

Of course, Oracle's preferred approach is to have you set up your OS 
environment so that Oracle pretty much eats the machine.  They tell you 
to set SHMAX to 4GB in the installation docs, for instance, then the 
installer by default will configure Oracle to use about 1/3 of your 
available RAM for its buffer cache.  Books on tuning generally tell you 
that's far too low.

Anyway, I've been told that Oracle's approach is more along the lines of 
"don't cache sequential scans that eat up more than N% of our own cache 
space".

Then shorter tables still get fully cached when sequentially scanned, 
while humongous tables don't wipe out the cache causing dirty pages to 
be flushed to the platter and other concurrent processes to do file I/O 
reads because everything but the huge table's disappeared.

Someone in an earlier post mentioned "thrashing" and that's what 
dragging a table bigger than cache causes on busy systems.


> 
> I like it, since anything that needs to be sensitive to system wide
> information, like the total load on the machine, should be handled by
> the system, not a particular app.
> 
> Ross
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 6: Have you searched our list archives?
> 
> http://archives.postgresql.org
> 
> .
> 
> 



-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org


Fri, 11 Jan 2002 10:23:27 -0800
Don Baccus <dhogaza@pacifier.com>
Re: again on index usage
Daniel Kalchev wrote:
> >>>Tom Lane said:
>  > "Zeugswetter Andreas SB SD" <ZeugswetterA@spardat.at> writes:
>  > > My preference would actually be a way to make the optimizer
>  > > choose a plan that causes minimal workload, and not shortest runtime 
>  > 
>  > ?? I am not sure that I see the difference.
> 
> There can be difference only if the optimizer takes into account already 
> executing plans (by other backends).
> 
>  > What I think you are saying is that when there's lots of competing work,
>  > seqscans have less advantage over indexscans because the
>  > sequential-access locality advantage is lost when the disk drive has to
>  > go off and service some other request.
> 
> This is exactly my point. The primary goal of the optimizer in my opinion 
> should be to avoid trashing. :-) Now, it is not easy to figure out when the 
> system starts trashing - at least not a portable way I can think of 
> immediately.

I have always felt some feedback mechanism from the executor back to the
optimizer was required but I was never sure quite how to implement it.

-- 
  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

Fri, 11 Jan 2002 13:24:20 -0500 (EST)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: again on index usage
> > That is on our TODO list, at least.
> > 
> 
> Hmm, on Linux this sort of behavior (skip the pg buffers for sequential
> scans) would have interesting load senstive behavior: since Linux uses
> all not-otherwise in use RAM as buffer cache, if you've got a low-load
> system, even very large tables will be cached. Once other processes start
> competing for RAM, your buffers go away. Bruce, what does xBSD do?

FreeBSD does, NetBSD will soon, not sure about the others.  I believe
NetBSD will be tunable because page cache vs. i/o cache is not always
best done with a FIFO setup.

Also, when we pull from the kernel cache we have to read into our shared
buffers;  much faster than disk i/o but slower than if they were already
in the cache.  For me the idea of doing non-cached sequential scans came
from a Solaris internals book I was reading.  I think it will be
possible to mark large sequential scan buffer i/o with lower priority
caching that may help performance.  However, if others are also doing
sequential scans of the same table _only_, our normal caching may be
best.  As you can see, this gets quite complicated and I am doubtful
there will be a general solution to this problem --- more of a feedback
loop may be the best bet --- determine which sequential scans are wiping
the cache with little other purpose and start not caching them.

-- 
  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

Fri, 11 Jan 2002 13:30:53 -0500 (EST)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: again on index usage
Tom Lane wrote:
> What I think you are saying is that when there's lots of competing work,
> seqscans have less advantage over indexscans because the
> sequential-access locality advantage is lost when the disk drive has to
> go off and service some other request.  If that's the mechanism, I think
> that the appropriate answer is just to reduce random_page_cost.  It's
> true that the current default of 4.0 was chosen using measurements on
> otherwise-unloaded systems.  If you assume that the system is (a) too
> busy to do read-aheads for you, and (b) has to move the disk arm to
> service other requests between each of your requests, then it's not
> clear that sequential reads have any performance advantage at all :-(.
> I don't think I'd go as far as to lower random_page_cost to 1.0, but
> certainly there's a case for using an intermediate value.

It is even more interesting than simple sequential vs random scan
thinking. Depending on the maker of the drive, even an unloaded system
will move the head randomly. Modern drives have almost no resemblance to
their predecessors. Sectors are mapped however the OEM sees fit. A
numerically sequential read from a hard disk may have the drive heads
bouncing all over the disk because the internal configuration of the
disk has almost nothing to do with the external representation.

Think about a RAID device. What does a sequential scan mean to a RAID
system? Very little depending on how the image is constructed. Storage
devices are now black boxes. The only predictable advantage a
"sequential scan" can have on a modern computer is OS level caching.

Fri, 11 Jan 2002 13:58:09 -0500
mlw <markw@mohawksoft.com>
Re: again on index usage
mlw <markw@mohawksoft.com> writes:
> ... Storage
> devices are now black boxes. The only predictable advantage a
> "sequential scan" can have on a modern computer is OS level caching.

You mean read-ahead.  True enough, but that "only advantage" is very
significant.  The 4.0 number did not come out of the air, it came
from actual measurements.

I think the real point in this thread is that measurements on an idle
system might not extrapolate very well to measurements on a heavily
loaded system.  I can see the point, but I don't really have time to
investigate it right now.  I'd be willing to reduce the default value of
random_page_cost to something around 2, if someone can come up with
experimental evidence justifying it ...

			regards, tom lane

Fri, 11 Jan 2002 14:09:21 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: again on index usage 
Bruce Momjian wrote:


> 
> I have always felt some feedback mechanism from the executor back to the
> optimizer was required but I was never sure quite how to implement it.


The folks at DEC (rdb???) wrote a paper on it a long time ago (duh, back 
when DEC existed).   I ran across it in the Tuft's library about a year 
ago, back when my girlfriend was in grad school.


-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org


Fri, 11 Jan 2002 11:29:32 -0800
Don Baccus <dhogaza@pacifier.com>
Re: again on index usage
Bruce Momjian wrote:


> Also, when we pull from the kernel cache we have to read into our shared
> buffers;  much faster than disk i/o but slower than if they were already
> in the cache.


Yes ... this is one reason why folks like Oracle want to be able to 
bypass the kernel cache.

>  For me the idea of doing non-cached sequential scans came
> from a Solaris internals book I was reading.  I think it will be
> possible to mark large sequential scan buffer i/o with lower priority
> caching that may help performance.  However, if others are also doing
> sequential scans of the same table _only_, our normal caching may be
> best.  As you can see, this gets quite complicated and I am doubtful
> there will be a general solution to this problem --- more of a feedback
> loop may be the best bet --- determine which sequential scans are wiping
> the cache with little other purpose and start not caching them.


It would be interesting to learn more about the actual hueristic Oracle 
uses (straight percents of the buffer cache?  Something based on 
concurrency?  I have no idea).  The Oracle folks have got tons and tons 
of data on real-world big, busy db installations to draw from when they 
investigate such things.



-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org


Fri, 11 Jan 2002 11:42:38 -0800
Don Baccus <dhogaza@pacifier.com>
Re: again on index usage
>>>Tom Lane said:
 > mlw <markw@mohawksoft.com> writes:
 > > ... Storage
 > > devices are now black boxes. The only predictable advantage a
 > > "sequential scan" can have on a modern computer is OS level caching.
 > 
 > You mean read-ahead.  True enough, but that "only advantage" is very
 > significant.  The 4.0 number did not come out of the air, it came
 > from actual measurements.

On what OS? Linux? Windows? BSD? OSF/1? System V? All these differ 
significantly in how buffer cache is managed. For example, the BSD 'soft 
updates' will not penalize large directory updates, but not do any good for 
sequential reads (considering what was said already about modern disks). SCSI 
tag queueing will significantly improve raw disk reads ('sequential' again) 
because of the low overhead of host<->SCSI subsystem communication - any 
decent SCSI host adapter will do bus-master DMA, without the interference of 
the processor (simplified as much as to illustrate it :). Todays IDE drives on 
PC hardware don't do that! Which is not to say that only SCSI drive 
controllers are intelligent enough - I still remember an older Motorola VME 
based UNIX system (that now can only server the purpose of coffee table :), 
where an MFM controller board had all the intelligence of the SCSI subsystem, 
although it operated with 'dump' MFM disks. So many examples can be given here.

 > I think the real point in this thread is that measurements on an idle
 > system might not extrapolate very well to measurements on a heavily
 > loaded system.  I can see the point, but I don't really have time to
 > investigate it right now.  I'd be willing to reduce the default value of
 > random_page_cost to something around 2, if someone can come up with
 > experimental evidence justifying it ...

Agreed. My preference would be, that if you have reasonable enough test data, 
that can be shared, many people on different platforms can run performance 
tests and come up with an array of recommended values for their particular 
OS/hardware configuration. I believe these two items are most significant for 
the tuning of an installation.

Daniel Kalchev


Sat, 12 Jan 2002 13:51:23 +0200
Daniel Kalchev <daniel@digsys.bg>
Re: again on index usage 
Don Baccus wrote:
> 
> Zeugswetter Andreas SB SD wrote:
> 
> > This is one of the main problems of the current optimizer which imho rather
> > aggressively chooses seq scans over index scans. During high load this does
> > not pay off.
> 
> Bingo ... dragging huge tables through the buffer cache via a sequential
> scan guarantees that a) the next query sequentially scanning the same
> table will have to read every block again (if the table's longer than
> available PG and OS cache) b) on a high-concurrency system other queries
> end up doing extra I/O, too.
> 
> Oracle partially mitigates the second effect by refusing to trash its
> entire buffer cache on any given sequential scan.  Or so I've been told
> by people who know Oracle well.  A repeat of the sequential scan will
> still have to reread the entire table but that's true anyway if the
> table's at least one block longer than available cache.

One radical way to get better-than-average cache behaviour in such 
pathologigal casescases would be to discard a _random_ page instead of 
LRU page (perhaps tuned to not not select from 1/N of pages on that are
MRU)

-------------
Hannu

Sat, 12 Jan 2002 17:08:24 +0200
Hannu Krosing <hannu@tm.ee>
Re: again on index usage
Hannu Krosing wrote:


> One radical way to get better-than-average cache behaviour in such 
> pathologigal casescases would be to discard a _random_ page instead of 
> LRU page (perhaps tuned to not not select from 1/N of pages on that are
> MRU)


Yep, that's one of the ways to improve performance when the same table's 
being scanned sequentially multiple times, or where different queries 
sometimes scan it sequentially, other times by index.  MRU would help if 
you're constantly doing sequential scans.

So would flipping the scan order depending on what's in the cache :)

But none of these would mitigate the effects on other concurrent queries 
that don't query the large table at all.



-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org


Sat, 12 Jan 2002 07:44:29 -0800
Don Baccus <dhogaza@pacifier.com>
Re: again on index usage