To: Charlie Savage <cfis@interserv.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: Index Scan Costs versus Sort 
In-reply-to: <dl0nk3$9lg$1@news.hub.org> 
References: <dkvu9b$305t$1@news.hub.org> <10461.1131645881@sss.pgh.pa.us>
	<437398E3.2020900@interserv.com> <dl0nk3$9lg$1@news.hub.org>
Comments: In-reply-to Charlie Savage <cfis@interserv.com>
	message dated "Thu, 10 Nov 2005 17:11:48 -0700"
Date: Thu, 10 Nov 2005 19:32:46 -0500
Message-ID: <13275.1131669166@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Charlie Savage <cfis@interserv.com> writes:
> Out of curiosity, how much longer would an index_scan expected to be 
> versus a seq scan?  I was under the impression it would be about a facto 
> of 4, or is that not usually the case?

No, it can easily be dozens or even hundreds of times worse, in the
worst case.  The factor of 4 you are thinking of is the random_page_cost
which is the assumed ratio between the cost of randomly fetching a page
and the cost of fetching it in a sequential scan of the whole table.
Not only is the sequential scan fetch normally much cheaper (due to less
seeking and the kernel probably catching on and doing read-ahead), but
if there are N tuples on a page then a seqscan reads them all with one
page fetch.  In the worst case an indexscan might fetch the page from
disk N separate times, if all its tuples are far apart in the index
order.  This is all on top of the extra cost to read the index itself,
too.

The planner's estimate of 50x higher cost is not out of line for small
tuples (large N) and a badly-out-of-order table.  What's puzzling is
that you seem to be getting near best-case behavior in what does not
seem to be a best-case scenario for an indexscan.

			regards, tom lane