Skip site navigation (1) Skip section navigation (2)

Re: wip: functions median and percentile

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: (view raw, whole thread or download thread mbox)
Lists: pgsql-hackerspgsql-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.


In response to

pgsql-hackers by date

Next:From: Greg StarkDate: 2010-10-04 16:20:06
Subject: Re: Adding getrusage profiling data to EXPLAIN output
Previous:From: Tom LaneDate: 2010-10-04 15:23:53
Subject: Re: OUTER keyword

pgsql-rrreviewers by date

Next:From: Robert HaasDate: 2010-10-04 17:22:39
Subject: Re: wip: functions median and percentile
Previous:From: Fujii MasaoDate: 2010-10-04 13:48:29
Subject: Re: Review: Patch for Synchronous Replication

Privacy Policy | About PostgreSQL
Copyright © 1996-2018 The PostgreSQL Global Development Group