On Fri, 2002-05-31 at 01:16, Josh Burdick wrote:
> BUG: this isn't properly set up to deal with multiple users.
> For example, if A computes a median, then B could read the data
> from the median_tmp table.  Possibly you could fiddle with
> transaction isolation levels, or add a user field to median_tmp,
> or something else complicated, to prevent this, but for now I'm
> not worrying about this.

You could just use temp tables and indexes - they are local to
connection .

create TEMP sequence median_id;
create TEMP table median_tmp (
  median_id int,
  x float4
);

---------------
Hannu



31 May 2002 01:16:41 +0500
Hannu Krosing <hannu@tm.ee>
Re: finding medians
    At the end of this message is some code I used to find medians.
    It's kind of a hack, but approximately works, and is intended as a 
somewhat awkward stopgap for people who need to use medians.  It 
illustrates the limitations of the current aggregate function setup, 
which works so nicely for avg() and stddev().
    I don't have any good solutions.  I tried using a float4[] to store 
each element as it's added, but I couldn't get array updates working in 
PL/PgSQL, so that didn't help.
    Perhaps aggregate functions could be passed an array?  Or a cursor, 
pointing at the first line?  I'm not sure.

    Anyways, perhaps it'll be helpful.
    Josh

-- 
Josh Burdick
jburdick@gradient.cis.upenn.edu
http://www.cis.upenn.edu/~jburdick



/* Implementing median-finding in "pure Postgres."  Does this by
copying data to a temporary table.

   A weakness of this code is that it uses sorting, instead of
Hoare's linear-time median algorithm.  Presumably sorting is
implemented so efficiently that it'll be faster than anything
written in PL/PgSQL.  (Although Hoare's algorithm implemented
in C would be faster than either.)

   BUG: this isn't properly set up to deal with multiple users.
For example, if A computes a median, then B could read the data
from the median_tmp table.  Possibly you could fiddle with
transaction isolation levels, or add a user field to median_tmp,
or something else complicated, to prevent this, but for now I'm
not worrying about this.

   Written by Josh Burdick (jburdick@gradient.cis.upenn.edu).
Anyone can use this under the same license as Postgres.

   20020524, jtb: started. */

drop aggregate median(float4);
drop table median_tmp;
drop sequence median_id;
drop index median_tmp_median_id;
drop function median_sfunc_float4(bigint, float4);
drop function median_finalfunc_float4(bigint);

create sequence median_id;
create table median_tmp (
  median_id int,
  x float4
);
create index median_tmp_median_id on median_tmp(median_id);

create function median_sfunc_float4
(bigint, float4) returns bigint as '

insert into median_tmp
values (case when $1 = 0 then nextval(''median_id'') else $1 end, $2);

select currval(''median_id'');

' language 'SQL';

create function median_finalfunc_float4
(bigint) returns float4 as '
declare

i bigint;
n bigint;
c refcursor;
m float4;
m1 float4;

begin

n := (select count(*) from median_tmp where median_id = $1);

open c for select x from median_tmp where median_id = $1 order by x;

for i in 1..((n+1)/2) loop
  fetch c into m;
end loop;

/* if n is even, fetch the next value, and average the two */
if (n % int8(2) = int8(0)) then
  fetch c into m1;
  m := (m + m1) / 2;
end if;

delete from median_tmp where median_id = $1;

return m;

end
' language 'plpgsql';

create aggregate median (
  basetype = float4,
  stype = bigint,
  initcond = 0,
  sfunc = median_sfunc_float4,
  finalfunc = median_finalfunc_float4
);







Thu, 30 May 2002 16:16:43 -0400
Josh Burdick <jburdick@gradient.cis.upenn.edu>
finding medians
Josh,

>     At the end of this message is some code I used to find medians.
>     It's kind of a hack, but approximately works, and is intended as a 
> somewhat awkward stopgap for people who need to use medians.  It 
> illustrates the limitations of the current aggregate function setup, 
> which works so nicely for avg() and stddev().

Actually, finding the median is one of the classic SQL problems.  You can't do 
it without 2 passes through the data set, disallowing the use of traditional 
aggregate functions.  Joe Celko has half a chapter devoted to various methods 
of finding the median.

Can I talk you into submitting your code to Techdocs?  I'd love to have it 
somewhere where it won't get buried in the mailing list archives.

-- 
-Josh Berkus


Thu, 30 May 2002 13:30:09 -0700
Josh Berkus <josh@agliodbs.com>
Re: finding medians
Josh Burdick <jburdick@gradient.cis.upenn.edu> writes:
> illustrates the limitations of the current aggregate function setup, 
> which works so nicely for avg() and stddev().
>     I don't have any good solutions.  I tried using a float4[] to store 
> each element as it's added, but I couldn't get array updates working in 
> PL/PgSQL, so that didn't help.
>     Perhaps aggregate functions could be passed an array?  Or a cursor, 
> pointing at the first line?  I'm not sure.

I don't think that would help.  The real problem here is the amount of
internal storage needed.  AFAIK there are no exact algorithms for finding
the median that require less than O(N) workspace for N input items.
Your "hack" with a temporary table is not a bad approach if you want to
work for large N.

There are algorithms out there for finding approximate medians using
limited workspace; it might be reasonable to transform one of these into
a Postgres aggregate function.

			regards, tom lane

Thu, 30 May 2002 17:45:53 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: finding medians 