Re: No merge sort?

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. The index can produce "time" sorted data for
each "id" in linear time, and the merge sort can merge them in linear
time. Also, the existing system insists on loading _all_ candidate rows
whereas this method can benefit from the limit.

If you don't want to code it, I will. I need it for the livejournal
mysql->postgresql transition. (No, mysql doesn't do it right either.)
But a few pointers to the right places to look in the code would be
helpful.

> 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?

--
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