(Starting a new thread so as not to distract review)
On 1/21/18, Dean Rasheed wrote:
> On 21 January 2018 at 07:26, John Naylor wrote:
>> I spent a few hours hacking on this, and it turns out calculating the
>> right number of MCVs taking into account both uniform and highly
>> non-uniform distributions is too delicate a problem for me to solve
>> right now. The logic suggested by Dean Rasheed in [1] always produces
>> no MCVs for a perfectly uniform distribution (which is good), but very
>> often also for other distributions, which is not good. My efforts to
>> tweak that didn't work, so I didn't get as far as adapting it for the
>> problem Jeff is trying to solve.
>
> Hmm, Tom suggested that the test based on the average frequency over
> all values might be too strict because the estimated number of
> distinct values is often too low, so that might explain what you're
> seeing.
In my test tables, I've noticed that our Ndistinct estimator is most
inaccurate for geometric distributions, so that's certainly possible,
but confusingly, it occasionally gave an empty MCV list along with a
histogram with a boundary duplicated 5 times, which I thought I was
guarding against. I'm thinking my implementation of your logic is
flawed somehow. In case you're curious I've attached my rough
(complier warnings and all) test patch.
> It occurs to me that maybe a better test to exclude a value from the
> MCV list would be to demand that its relative standard error not be
> too high. Such a test, in addition to the existing tests, might be
> sufficient to solve the opposite problem of too many values in the MCV
> list, because the real problem there is including a value after having
> seen relatively few occurrences of it in the sample, and thus having a
> wildly inaccurate estimate for it. Setting a bound on the relative
> standard error would mean that we could have a reasonable degree of
> confidence in estimates produced from the sample.
If you don't mind, what would the math look like for that?
-John Naylor
diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c
index 5f21fcb..da21333 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -2318,6 +2318,8 @@ compute_scalar_stats(VacAttrStatsP stats,
int num_mcv = stats->attr->attstattarget;
int num_bins = stats->attr->attstattarget;
StdAnalyzeData *mystats = (StdAnalyzeData *) stats->extra_data;
+ double N,
+n;
values = (ScalarItem *) palloc(samplerows * sizeof(ScalarItem));
tupnoLink = (int *) palloc(samplerows * sizeof(int));
@@ -2525,10 +2527,10 @@ compute_scalar_stats(VacAttrStatsP stats,
*/
int f1 = ndistinct - nmultiple + toowide_cnt;
int d = f1 + nmultiple;
- double n = samplerows - null_cnt;
- double N = totalrows * (1.0 - stats->stanullfrac);
double stadistinct;
+ n = samplerows - null_cnt;
+ N = totalrows * (1.0 - stats->stanullfrac);
/* N == 0 shouldn't happen, but just in case ... */
if (N > 0)
stadistinct = (n * d) / ((n - f1) + f1 * n / N);
@@ -2558,9 +2560,44 @@ compute_scalar_stats(VacAttrStatsP stats,
* we are able to generate a complete MCV list (all the values in the
* sample will fit, and we think these are all the ones in the table),
* then do so. Otherwise, store only those values that are
- * significantly more common than the (estimated) average. We set the
- * threshold rather arbitrarily at 25% more than average, with at
- * least 2 instances in the sample. Also, we won't suppress values
+ * significantly more common than the (estimated) average.
+ *
+ * Note: For this POC patch, the implementation and comments
+ * were copied from an email from Dean Rasheed, which contains further references:
+ * https://www.postgresql.org/message-id/CAEZATCVu9zK0N%3Dnd9ufavabbM8YZiyWYJca0oiE8F31GAY%2B_XA%40mail.gmail.com
+ *
+ * We calculate the threshold from the table and sample sizes.
+
+ * The initial rule of thumb is that the value should occur at
+ * least 10 times in the sample.
+ *
+ * Suppose that N is the population size (total number of rows in the
+ * table), and n is the sample size, and that some particular candidate
+ * value appears x times in the sample. Then the "sample proportion" is
+ * given by p = x/n.
+ *
+ * It is reasonable to treat p as having a normal distribution, which
+ * then allows the margin of error to be analysed using standard
+ * techniques. We calculate the standard error of the sample proportion:
+ *
+ * SE = sqrt(p*(1-p)/n) * sqrt((N-n)/(N-1))
+ *
+ * The second term is a finite population correction. There is a 95%
+ * probability that the total population proportion lies in the range
+ *
+ * [ pmin = p-2*SE, pmax = p+2*SE ]
+ *
+ * If there are Nd distinct values in the table, so that the average
+ * frequency of occurrence of any particular value is 1/Nd, then the test
+ *
+ * pmin > 1/Nd
+ *
+ * would imply that