On Sun, Oct 3, 2010 at 11:58 PM, Dean Rasheed <dean.a.rash...@gmail.com> wrote: > The problem is that performance really sucks, > because it is an O(n^2 log(n)) algorithm. I don't see an easy way > around that without significant new infrastructure, as Greg describes, > or a completely different algorithm.
Resorting for each record would be O(n^2 log(n)). If you use Quickselect it would be O(n^2) because each selection would be O(n). But then we could get O(n^2) by just doing insertion-sort. The problem with both these algorithms is that I don't see how to do it on-disk. Maybe there would be some way to do insertion-sort on disk by keeping a buffer in-memory holding the last n records inserted and whenever the in-memory buffer fills do a merge against the data on disk to spill it. But that's a lot of special-case machinery. Personally I think if we need it to handle sorted aggregates over window functions it's worth it to carry it if someone feels like writing it. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
