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

Re: wip: functions median and percentile

From: Greg Stark <gsstark(at)mit(dot)edu>
To: Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>
Cc: PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org>, David Fetter <david(at)fetter(dot)org>
Subject: Re: wip: functions median and percentile
Date: 2010-08-19 14:50:23
Message-ID: AANLkTikSw+8M36zWaxr+o7jgj4KizeTxXQYt54mcaXgs@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-rrreviewers
On Thu, Aug 19, 2010 at 11:59 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com> wrote:
> I am sending a prototype implementation of functions median and
> percentile. This implementation is very simple and I moved it to
> contrib for this moment - it is more easy maintainable. Later I'll
> move it to core.

So if the entire result set fits in memory it would be nice to use the
O(n) Quickselect algorithm -- which would only be a small change to
the existing Quicksort code -- instead of sorting the entire set. That
should be possible both for percentile() and median(). It would be
good to generalize the tuplesort api sufficiently so that you can
implement this as a contrib module even if we eventually decide to
integrate it in core. It's probably worth having two copies of the
sort code, one for Quickselect and one for Quicksort just for speed,
though I suppose it's worth benchmarking.

But I'm not aware of a generalization of tapesort to allow O(n)
selection with the sequential i/o properties of tapesort. It would be
especially interesting, probably more so than the in-memory case.

-- 
greg

In response to

Responses

pgsql-hackers by date

Next:From: Robert HaasDate: 2010-08-19 15:08:25
Subject: Re: Re: [COMMITTERS] pgsql: Coerce 'unknown' type parameters to the right type in the
Previous:From: Quan ZongliangDate: 2010-08-19 14:24:54
Subject: Re: Fw: patch for pg_ctl.c to add windows service start-type

pgsql-rrreviewers by date

Next:From: Tom LaneDate: 2010-08-19 15:33:13
Subject: Re: wip: functions median and percentile
Previous:From: Pavel StehuleDate: 2010-08-19 10:59:33
Subject: wip: functions median and percentile

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