On Sun, Oct 3, 2010 at 11:58 PM, Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)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.
In response to
pgsql-hackers by date
|Next:||From: Greg Stark||Date: 2010-10-04 16:20:06|
|Subject: Re: Adding getrusage profiling data to EXPLAIN output|
|Previous:||From: Tom Lane||Date: 2010-10-04 15:23:53|
|Subject: Re: OUTER keyword |
pgsql-rrreviewers by date
|Next:||From: Robert Haas||Date: 2010-10-04 17:22:39|
|Subject: Re: wip: functions median and percentile|
|Previous:||From: Fujii Masao||Date: 2010-10-04 13:48:29|
|Subject: Re: Review: Patch for Synchronous Replication|