Re: pretty bad n_distinct estimate, causing HashAgg OOM on TPC-H

On Fri, Jun 19, 2015 at 12:27 PM, Tomas Vondra <tomas.vondra@2ndquadrant.com> wrote:

But I think you might be on to something, because I manually collected a random sample with 30k rows (by explicitly generating 30k random TIDs), and I get this:

tpch=# select cnt, count(*) from (select l_orderkey, count(*) AS cnt from lineitem_sample group by 1) foo group by 1;

 cnt | count
-----+-------
   1 | 29998
   2 |     1
(2 rows)


That's quite different compared to what analyze gets, which effectively looks something like this (this is derived from the logs, so not perfectly accurate - I only have f1, ndistinct, nmultiple):

 cnt | count
-----+-------
   1 | 27976
   2 |   976
   3 |    24

Am I wrong or is the sample not that random?

When values in the same block are likely to be equal, then it finds too many duplicates because it too often picks two rows from a single block.

See analysis here:

http://www.postgresql.org/message-id/CAMkU=1wRH_jopyCAyUKbdQY4DWhsx1-1e2s0VVgfrryfXDe2SQ@mail.gmail.com

If we assume all the blocks have the same tuple density, then it is easy to correct this.  But without that assumption of constant tuple density, I don't know how to get a truly random sample while still skipping most of the table.