I do not clearly understand the sorting code in PostgreSQL. If I did have a good grasp of it, I would take a go at improving it.
Here are some suggestions of things that I know work really, really well: #1. Two pass merge (none of that silly poly-tape merge goo) #2. Load ONLY the keys that are to be sorted into memory. Use a pointer exchange sort, and do not move the physical rows of data at all. I am pretty sure from this thread that PostgreSQL is not doing #1, and I have no idea if it is doing #2. A useful trick: Since merge is mentioned, I should say something else about merge joins. If you do not have room to load the sorted keys for bsearch, load every kth key (where k is computed by sizeof merge_ram / sizeof key_data). Then, when you have found the block the thing you are looking for by the "kth key bsearch", bsearch that block. Now, maybe PostrgeSQL already uses tricks better than these. I don't know. But if they prove helpful suggestions I will be glad of it. > -----Original Message----- > From: [EMAIL PROTECTED] [mailto:pgsql-hackers- > [EMAIL PROTECTED] On Behalf Of Tom Lane > Sent: Wednesday, March 08, 2006 12:32 PM > To: Jim C. Nasby > Cc: Luke Lonergan; Simon Riggs; pgsql-hackers@postgreSQL.org > Subject: Re: [HACKERS] Merge algorithms for large numbers of "tapes" > > "Jim C. Nasby" <[EMAIL PROTECTED]> writes: > > But do fewer/longer sorted runs translate into not merging back to disk? > > I thought that was controlled by if we had to be able to rewind the > > result set. > > A plain SELECT ... ORDER BY doesn't assume that anymore. It is still > required for some cases such as the input to a merge join, but the > on-the-fly-final-merge code is going to be used a lot more in 8.2 than > it was before. > > regards, tom lane > > ---------------------------(end of broadcast)--------------------------- > TIP 1: if posting/reading through Usenet, please send an appropriate > subscribe-nomail command to [EMAIL PROTECTED] so that your > message can get through to the mailing list cleanly ---------------------------(end of broadcast)--------------------------- TIP 6: explain analyze is your friend
