Re: wip: functions median and percentile

On Mon, Oct 4, 2010 at 2:58 AM, Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com> wrote:
> That requires a new sort for each row. I generated this with a minor
> tweak to Pavel's patch to just restart the tuplesort each time (the
> "quick-fix" solution). The problem is that performance really sucks,
> because it is an O(n^2 log(n)) algorithm.

Maybe that's OK. If you're doing repeated median operations on large
data sets, perhaps you should expect that to be slow. I bet that
people who want to use this as a window function will want one median
per group, not n medians per group; and it doesn't seem like a good
idea to say - we're not going to let you use this as a window function
AT ALL because you might decide to do something that will be really
slow. You can always hit ^C if you get tired of waiting. This seems
like it's very far from being the most important thing for us to
optimize, though of course it's great if we can.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company