88 *
99 *
1010 * IDENTIFICATION
11- * $Header: /cvsroot/pgsql/src/backend/commands/analyze.c,v 1.25 2002/01/06 00:37:44 tgl Exp $
11+ * $Header: /cvsroot/pgsql/src/backend/commands/analyze.c,v 1.26 2002/02/18 16:04:14 tgl Exp $
1212 *
1313 *-------------------------------------------------------------------------
1414 */
@@ -1009,10 +1009,15 @@ compute_minimal_stats(VacAttrStats *stats,
10091009{
10101010/*----------
10111011 * Estimate the number of distinct values using the estimator
1012- * proposed by Chaudhuri et al (see citation above). This is
1013- *sqrt(n/r) * max(f1,1) + f2 + f3 + ...
1014- * where fk is the number of distinct values that occurred
1015- * exactly k times in our sample of r rows (from a total of n).
1012+ * proposed by Haas and Stokes in IBM Research Report RJ 10025:
1013+ *n*d / (n - f1 + f1*n/N)
1014+ * where f1 is the number of distinct values that occurred
1015+ * exactly once in our sample of n rows (from a total of N),
1016+ * and d is the total number of distinct values in the sample.
1017+ * This is their Duj1 estimator; the other estimators they
1018+ * recommend are considerably more complex, and are numerically
1019+ * very unstable when n is much smaller than N.
1020+ *
10161021 * We assume (not very reliably!) that all the multiply-occurring
10171022 * values are reflected in the final track[] list, and the other
10181023 * nonnull values all appeared but once. (XXX this usually
@@ -1021,12 +1026,19 @@ compute_minimal_stats(VacAttrStats *stats,
10211026 *----------
10221027 */
10231028int f1 = nonnull_cnt - summultiple ;
1024- double term1 ;
1025-
1026- if (f1 < 1 )
1027- f1 = 1 ;
1028- term1 = sqrt (totalrows / (double )numrows )* f1 ;
1029- stats -> stadistinct = floor (term1 + nmultiple + 0.5 );
1029+ int d = f1 + nmultiple ;
1030+ double numer ,denom ,stadistinct ;
1031+
1032+ numer = (double )numrows * (double )d ;
1033+ denom = (double ) (numrows - f1 )+
1034+ (double )f1 * (double )numrows /totalrows ;
1035+ stadistinct = numer /denom ;
1036+ /* Clamp to sane range in case of roundoff error */
1037+ if (stadistinct < (double )d )
1038+ stadistinct = (double )d ;
1039+ if (stadistinct > totalrows )
1040+ stadistinct = totalrows ;
1041+ stats -> stadistinct = floor (stadistinct + 0.5 );
10301042}
10311043
10321044/*
@@ -1313,20 +1325,32 @@ compute_scalar_stats(VacAttrStats *stats,
13131325{
13141326/*----------
13151327 * Estimate the number of distinct values using the estimator
1316- * proposed by Chaudhuri et al (see citation above). This is
1317- *sqrt(n/r) * max(f1,1) + f2 + f3 + ...
1318- * where fk is the number of distinct values that occurred
1319- * exactly k times in our sample of r rows (from a total of n).
1328+ * proposed by Haas and Stokes in IBM Research Report RJ 10025:
1329+ *n*d / (n - f1 + f1*n/N)
1330+ * where f1 is the number of distinct values that occurred
1331+ * exactly once in our sample of n rows (from a total of N),
1332+ * and d is the total number of distinct values in the sample.
1333+ * This is their Duj1 estimator; the other estimators they
1334+ * recommend are considerably more complex, and are numerically
1335+ * very unstable when n is much smaller than N.
1336+ *
13201337 * Overwidth values are assumed to have been distinct.
13211338 *----------
13221339 */
13231340int f1 = ndistinct - nmultiple + toowide_cnt ;
1324- double term1 ;
1325-
1326- if (f1 < 1 )
1327- f1 = 1 ;
1328- term1 = sqrt (totalrows / (double )numrows )* f1 ;
1329- stats -> stadistinct = floor (term1 + nmultiple + 0.5 );
1341+ int d = f1 + nmultiple ;
1342+ double numer ,denom ,stadistinct ;
1343+
1344+ numer = (double )numrows * (double )d ;
1345+ denom = (double ) (numrows - f1 )+
1346+ (double )f1 * (double )numrows /totalrows ;
1347+ stadistinct = numer /denom ;
1348+ /* Clamp to sane range in case of roundoff error */
1349+ if (stadistinct < (double )d )
1350+ stadistinct = (double )d ;
1351+ if (stadistinct > totalrows )
1352+ stadistinct = totalrows ;
1353+ stats -> stadistinct = floor (stadistinct + 0.5 );
13301354}
13311355
13321356/*