Earlier I mentioned I had implemented the limited sort optimization. This kicks in quite frequently on web applications that implement paging. Currently Postgres has to sort the entire data set, often in a disk sort. If the page is early in the result set it's a lot more efficient to just keep the top n records in memory and do a single pass through the result set.
The patch is quite simple and is mostly localized to tuplesort.c which provides a new function to advise it of the maximum necessary. It uses the existing heapsort functionality which makes it easy to keep the top n records by peeking at the top element of the heap and removing it if the new record would displace it. In experimenting I found heap sort about half the speed of quicksort so I made it switch over to heap sort if the input size reached 2x the specified maximum or if it can avoid spilling to disk by switching. The two open issues (which are arguably the same issue) is how to get the information down to the sort node and how to cost the plan. Currently it's a bit of a hack: the Limit node peeks at its child and if it's a sort it calls a special function to provide the limit.
limit-sort.patch.4
Description: Binary data
-- Gregory Stark EnterpriseDB http://www.enterprisedb.com
---------------------------(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
