Jeff, can you describe the changes that were made to ANALYZE in v11, please?
I've found that running ANALYZE on v10 on the Join Order Benchmark, using the default statistics target of 100, produces quite unstable results, so I'd be interested to hear what has been improved in v11.
There are two paths the code can take. One if all values which were sampled at all were sampled at least twice, and another if the least-sampled value was sampled exactly once. For some distributions (like exponential-ish or maybe power-law), it is basically a coin flip whether the least-sampled value is seen once, or more than once. If you are seeing instability, it is probably for this reason. That fundamental instability was not addressed in v11.
Once you follow the "something seen exactly once" path, it has to decide how many of the values get represented in the most-common-value list. That is where the change was. The old method said a value had to have an estimated prevalence at least 25% more than the average estimated prevalence to get accepted into the list. The problem is that if there were a few dominant values, it wouldn't be possible for any others to be "over-represented" because those few dominant values dragged the average prevalence up so far nothing else could qualify. What it was changed to was to include a value in the most-common-value list if its overrepresentation was statistically significant given the sample size. The most significant change (from my perspective) is that over-representation is measured not against all values, but only against all values more rare in the sample then the one currently being considered for inclusion into the MCV. The old method basically said "all rare values are the same", while the new method realizes that a rare value present 10,000 times in a billion row table is much different than a rare value present 10 time in a billion row table.
It is possible that this change will fix the instability for you, because it could cause the "seen exactly once" path to generate a MCV list which is close enough in size to the "seen at least twice" path that you won't notice the difference between them anymore. But, it is also possible they will still be different enough in size that it will still appear unstable. It depends on your distribution of values.
