Re: No merge sort?

Taral <taral(at)taral(dot)net> writes:
> On Thu, Mar 13, 2003 at 04:28:34PM -0500, Tom Lane wrote:
>> Seems like a waste of effort to me. I find this example less than
>> compelling --- the case that could be sped up is quite narrow,
>> and the potential performance gain not all that large. (A sort
>> is a sort however you slice it, with O(N log N) runtime...)

> Actually, it's O(N) time.

Only if you assume a fixed number of input streams.

>> Also, the direction we'd likely be going in in future is to merge
>> multiple indexscans using bitmap techniques, so that the output
>> ordering of the scans couldn't be counted on anyway.

> I don't understand this. What do these bitmap techniques do?

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.

regards, tom lane