Bruno Wolff III <bruno@wolff.to> writes:
> Greg Stark <gsstark@mit.edu> wrote:
>> where postgres won't bother with the index since it will be slower than just
>> resorting the entire table.
> Using an index to do an order by is an order N operation. Doing a sort
> is an order N log N operation. For large values of N, a index will be
> faster.
Unfortunately not ... the constant factors are such that the index
solution isn't very competitive at large N, unless the table is already
well ordered (ie clustered). The sort code is a lot better at avoiding
random-seeks-all-over-the-disk syndrome.
I suppose your argument is good as N goes to infinity, but for
real-world cases we don't seem to reach the asymptotic regime.
regards, tom lane