LIMIT/SORT optimization

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.






--
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com