Re: No merge sort?

From: Taral <taral(at)taral(dot)net>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: Re: No merge sort?
Date: 2003-03-14 01:58:14
Message-ID: 20030314015814.GA2981@taral.net
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Christopher Kings-Lynne 2003-03-14 02:00:22 Re: SQL99 ARRAY support proposal
Previous Message Partho Bhowmick 2003-03-14 01:27:54 Regular expressions in PostgreSQL