Estimate average and median efficiently in Postgres?

Question

I have a Postgres database with tables in the billion scale. So any aggregate functions such as count() and avg(), as well as "order by random()" are very time consuming. Postgres has pg_catalog which contains lots of useful statistics (such as the histogram bins in view pg_stats) that describe a database. Is there a way to take advantage of the statistics in pg_catalog to estimate the average and median numbers over a numeric column in a Postgres table?

Answer 1

If an estimate is good enough, then statistical sampling is your friend. I'd probably use a sample size calculator to determine how many rows I need, then write some code to randomly insert that many keys into a table. A join, a function, and you're done.

If you've never done anything like this before, you'll probably want to do some background reading. When I had to do that stuff, I used a handbook from nist.gov. (And you'll probably be surprised at how small a sample you need.)

Answer 2

You can get a reasonable estimate of the median using pg_stats if you set the number of bins to 2. You need to set it low because it is a maximum, and the idea is to force an even number of bins so the middle bound is the middle of the distribution. Set it to 100 and postgres is free to use 99, 97, ... which is not what we want.

create table foo(bar integer);

insert into foo(bar) 
select (random()*1000)::integer from generate_series(1,10000);

alter table foo alter bar set statistics 2;

analyze foo;

select most_common_vals, histogram_bounds from pg_stats where tablename='foo';

 most_common_vals | histogram_bounds
------------------+------------------
 {188,319}        | {0,492,1000}

For the average you can take the average of the mid-points of the histogram bins, in this case having more bins is an advantage:

create table foo(bar integer);
insert into foo(bar) select (random()*1000)::integer from generate_series(1,100);
analyze foo;

select avg(mid_bin)
from( select (lead(bound) over(order by bound)+bound)/2 as mid_bin
      from ( select unnest(h) as bound 
             from ( select histogram_bounds::text::int[] as h 
                    from pg_stats
                    where tablename='foo' ) z) z ) z;

         avg
----------------------
 504.9450549450549451

Note that in either case the result is distorted as the number of elements in most_common_vals increases in step with the number of bins in histogram_bounds and "The values in most_common_vals, if present, are omitted from this histogram calculation." Perhaps you can find a happy medium that works well enough for you for both calculations?