Re: No merge sort?

On Thu, Mar 13, 2003 at 10:30:27PM -0500, Tom Lane wrote:
> The idea is you look at the index to make a list of main-table tuple
> positions you are interested in, which you represent compactly as a
> compressed bitmap. (There is some finagling needed because PG actually
> uses block/line number rather than a pure tuple number to identify
> tuples, but you can fake it with a reasonably small amount of overhead.)
> Then you can combine multiple index inputs by ANDing or ORing bitmaps
> (the OR case applies to your example). Finally, you traverse the heap,
> accessing the desired rows in heap-location order. This loses in terms
> of producing presorted output --- but it often saves enough in I/O costs
> to more than justify doing the sort in memory.

And it loses bigtime in the case of LIMIT. If the unlimited query
returns 4,000 records and I only want 20, you're retrieving 200x too
much data from disk.

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me