MCV lists for highly skewed distributions

I want to revive a patch I sent couple years ago to the performance list,
as I have seen the issue pop up repeatedly since then.

Original thread is here:
https://www.postgresql.org/message-id/CAK_s-G2tc8r0N3AqPr8fW5QsRQMbZNurgAQ%3D_ME1aaf4vOmnnA%40mail.gmail.com

The problem is that if you have a highly skewed distribution, such as
exponential frequencies, it usually stores too few entries in the MCV list.

For example:

create table foo as select floor(-log(random())/log(2))::int as who from
generate_series(1,10000000);

This will usually store 0 to 5 as MCV with the default stat target[1].
Then value 6 is not stored, and its ~75k repetitions get averaged over the
remaining distinct values. This leads to horrible misplanning for rare
values. For example, who=17 has 37 entries, but is estimated to have
20,000. The correct join for 37 values is often not the correct one for
20,000.

If we stored just a few more values, their inclusion in the MCV would mean
they are depleted from the residual count, correctly lowering the estimate
we would get for very rare values not included in the sample.

So instead of having the threshold of 1.25x the average frequency over all
values, I think we should use 1.25x the average frequency of only those
values not already included in the MCV, as in the attached.

As it is, you can partially overcome the too short MCV list by cranking up
the default statistics target, but this is a weak effect and comes at a
high cost of CPU time. In some of the real distributions I've looked at,
cranking up default statistics target is almost entirely ineffective.

I think that perhaps maxmincount should also use the dynamic
values_cnt_remaining rather than the static one. After all, things
included in the MCV don' get represented in the histogram. When I've seen
planning problems due to skewed distributions I also usually see redundant
values in the histogram boundary list which I think should be in the MCV
list instead. But I have not changed that here, pending discussion.

[1] Occasionally it will store a much longer MCV list, because no values
was sampled exactly once, which triggers a different code path in which all
seen values are put in the MCV and the histogram is NULL. This is not
reliable, as whether the least-sample value is present in the sample once
or twice is pretty brittle.

Cheers,

Jeff