Re: LIMIT Optimization

On Sat, Jan 26, 2002 at 11:19:21PM -0500, Bruce Momjian wrote:
> Tom Lane wrote:
> > Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us> writes:
> > > I am confused. I thought we already did optimization for LIMIT that
> > > assumed you only wanted a few values. Is there something we are missing
> > > there?
> >
> > Yeah, he was proposing an alternative implementation of sorting that
> > would win in a scenario like
> >
> > SELECT ... ORDER BY foo LIMIT <something small>
> >
> > If you have an index on foo then there's no problem, but if you're
> > forced to do an explicit sort then the system does a complete sort
> > before you can get any data out. If the limit is small enough you
> > can instead do a one-pass "select top N" scan.
> >
> > Note that this is only workable in the non-cursor case, where you
> > know the limit for sure.
>
> Oh, boy, so we would scan through and grab the top X value from the
> table without a sort. Interesting. Add to TODO:
>
> Allow ORDER BY ... LIMIT to select top values without sort or index

Note that it's not as big a win as one might think at first, since you
stil have to scan the entire table to make sure that last tuple isn't
in the LIMIT in the sort order. Big (potential) savingings in sort space
storage, however. And you're O(N) compares, rather than anything larger.

Ross