Re: [HACKERS] Solution for LIMIT cost estimation

At 11:53 AM 2/13/00 -0500, Tom Lane wrote:
>Chris <chris(at)bitmead(dot)com> writes:
>> Could it _ever_ be faster to sort the tuples when there is already an
>> index that can provide them in sorted order?
>
>Yes --- in fact usually, for large tables. Once your table gets too
>big for the disk cache to be effective, indexscan performance approaches
>one random-access page fetch per tuple. Sort performance behaves more
>or less as p*log(p) accesses for p pages; and a far larger proportion

>of those accesses are sequential than in the indexscan case. So the
>sort will win if you have more than log(p) tuples per page. Do the
>arithmetic...
>
>The optimizer's job would be far simpler if no-brainer rules like
>"indexscan is always better" worked.

Yet the optimizer currently takes the no-brainer point-of-view that
"indexscan is slow for tables much larger than the disk cache, therefore
treat all tables as though they're much larger than the disk cache".

The name of the game in the production database world is to do
everything possible to avoid a RAM bottleneck, while the point
of view PG is taking seems to be that RAM is always a bottleneck.

This presumption is far too pessimistic.

- Don Baccus, Portland OR <dhogaza(at)pacifier(dot)com>
Nature photos, on-line guides, Pacific Northwest
Rare Bird Alert Service and other goodies at
http://donb.photo.net.