Re: Optimize ORDER BY ... LIMIT

On Fri, Sep 15, 2006 at 08:22:50PM +0100, Gregory Stark wrote:
> But just in case it's not clear for anyone the usual use case for
> this paging results on a web page. As much as I normally try to
> convince people they don't want to do it that way they usually do
> end up with it implemented using limit/offset. And Postgres
> currently is absolutely *awful* at running those queries.

I'm curious, as I may be such an offender. What alternatives exist?

I think you mean the concept of showing a page of information that
you can navigate forwards and backwards a page, or select a range.

What alternatives to limit/offset exist? If there are thousands or
more results, I have trouble with an idea that the entire results
should be queried, and cached, displaying only a fraction.

I think most or all of the times I do this, an index is available,
so perhaps that is why I don't find this issue problematic?

For implementation, I think something simple is best:

- limit X offset Y

This means keeping a set of X+Y tuples as follows:

1) If set of X+Y tuples still has room, insert using a binary search
that retains the ordering characteristics that would be had if
limit/offset had not been used.

2) If the row is less than the X+Y'th tuple, remove the X+Y'th
tuple from the set, and insert the row as per 1).

3) Ignore the tuple.

At the end, you return from the set starting at Y+1, and ending at Y+X.

If X+Y tuples would take up too much memory, this plan should be
skipped, and the general routines used instead.

Cheers,
mark

--
mark(at)mielke(dot)cc / markm(at)ncf(dot)ca / markm(at)nortel(dot)com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/