Estimate average and median efficiently in Postgres?
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.)