Re: Optimize ORDER BY ... LIMIT

2006/9/16, Gregory Stark <stark(at)enterprisedb(dot)com>:

> Alvaro Herrera <alvherre(at)commandprompt(dot)com> writes:
>
> > I don't know if this is the same thing you are talking about, but Oleg
> > talked to me on the conference about "partial sort", which AFAICS it's
> > about the same thing you are talking about. I think Teodor submitted a
> > patch to implement it, which was rejected because of not being general
> > enough.
>
> Oof, you have a long memory. Oleg does reference such a thing in his 2002 post
> that ended up resulting in the TODO item. I can't find the original patch but
> I doubt any patch against 7.1 is going to be all that helpful in understanding
> what to do today.
>
> I'm also confused how he only saw a factor of 6 improvement in reading the top
> 100 out of a million. I would expect much better.

For example, consider the case in which 6 passes are needed to do the
full sort. Then, for a "partial sort", at least the first of these
passes has to be fully executed, because one needs to read at least
all the data once to find the "top n".

greetings,
Nicolas

--
Nicolas Barbier
http://www.gnu.org/philosophy/no-word-attachments.html