From: | Greg Stark <gsstark(at)mit(dot)edu> |
---|---|
To: | Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com> |
Cc: | Hitoshi Harada <umi(dot)tanuki(at)gmail(dot)com>, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, David Fetter <david(at)fetter(dot)org>, PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: wip: functions median and percentile |
Date: | 2010-10-04 16:14:06 |
Message-ID: | AANLkTikF_zQdz0x49muKgabAYk7dAQvnY=OY1TwfEV3o@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers pgsql-rrreviewers |
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.
--
greg
From | Date | Subject | |
---|---|---|---|
Next Message | Greg Stark | 2010-10-04 16:20:06 | Re: Adding getrusage profiling data to EXPLAIN output |
Previous Message | Tom Lane | 2010-10-04 15:23:53 | Re: OUTER keyword |
From | Date | Subject | |
---|---|---|---|
Next Message | Robert Haas | 2010-10-04 17:22:39 | Re: wip: functions median and percentile |
Previous Message | Fujii Masao | 2010-10-04 13:48:29 | Re: Review: Patch for Synchronous Replication |