| blob | d96b7666f08d9ac74cccf05851fa8fd8fc2d4948 |
1 /*-------------------------------------------------------------------------
2 *
3 * analyze.c
4 * the Postgres statistics generator
5 *
6 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * $PostgreSQL$
12 *
13 *-------------------------------------------------------------------------
14 */
17 #include <math.h>
49 /* Data structure for Algorithm S from Knuth 3.4.2 */
51 {
59 /* Per-index data for ANALYZE */
61 {
69 /* Default statistics target (GUC parameter) */
72 /* A few variables that don't seem worth passing around as parameters */
87 MemoryContext col_context);
102 /*
103 * analyze_rel() -- analyze one relation
104 */
105 void
107 BufferAccessStrategy bstrategy)
108 {
109 Relation onerel;
111 tcnt,
112 i,
113 ind;
121 numrows;
123 totaldeadrows;
125 PGRUsage ru0;
127 Oid save_userid;
132 else
137 /*
138 * Use the current context for storing analysis info. vacuum.c ensures
139 * that this context will be cleared when I return, thus releasing the
140 * memory allocated here.
141 */
144 /*
145 * Check for user-requested abort. Note we want this to be inside a
146 * transaction, so xact.c doesn't issue useless WARNING.
147 */
150 /*
151 * Open the relation, getting ShareUpdateExclusiveLock to ensure that two
152 * ANALYZEs don't run on it concurrently. (This also locks out a
153 * concurrent VACUUM, which doesn't matter much at the moment but might
154 * matter if we ever try to accumulate stats on dead tuples.) If the rel
155 * has been dropped since we last saw it, we don't need to process it.
156 */
161 /*
162 * Check permissions --- this should match vacuum's check!
163 */
166 {
167 /* No need for a WARNING if we already complained during VACUUM */
169 {
178 else
182 }
185 }
187 /*
188 * Check that it's a plain table; we used to do this in get_rel_oids() but
189 * seems safer to check after we've locked the relation.
190 */
192 {
193 /* No need for a WARNING if we already complained during VACUUM */
200 }
202 /*
203 * Silently ignore tables that are temp tables of other backends ---
204 * trying to analyze these is rather pointless, since their contents are
205 * probably not up-to-date on disk. (We don't throw a warning here; it
206 * would just lead to chatter during a database-wide ANALYZE.)
207 */
209 {
212 }
214 /*
215 * We can ANALYZE any table except pg_statistic. See update_attstats
216 */
218 {
221 }
228 /*
229 * Switch to the table owner's userid, so that any index functions are
230 * run as that user.
231 */
235 /* let others know what I'm doing */
240 /* measure elapsed time iff autovacuum logging requires it */
242 {
246 }
248 /*
249 * Determine which columns to analyze
250 *
251 * Note that system attributes are never analyzed.
252 */
254 {
261 {
272 tcnt++;
273 }
275 }
276 else
277 {
283 {
286 tcnt++;
287 }
289 }
291 /*
292 * Open all indexes of the relation, and see if there are any analyzable
293 * columns in the indexes. We do not analyze index columns if there was
294 * an explicit column list in the ANALYZE command, however.
295 */
301 {
304 {
311 {
318 {
322 {
323 /* Found an index expression */
331 /*
332 * Can't analyze if the opclass uses a storage type
333 * different from the expression result type. We'd get
334 * confused because the type shown in pg_attribute for
335 * the index column doesn't match what we are getting
336 * from the expression. Perhaps this can be fixed
337 * someday, but for now, punt.
338 */
346 {
347 tcnt++;
349 }
350 }
351 }
353 }
354 }
355 }
357 /*
358 * Quit if no analyzable columns
359 */
361 {
362 /*
363 * We report that the table is empty; this is just so that the
364 * autovacuum code doesn't go nuts trying to get stats about a
365 * zero-column table.
366 */
370 }
372 /*
373 * Determine how many rows we need to sample, using the worst case from
374 * all analyzable columns. We use a lower bound of 100 rows to avoid
375 * possible overflow in Vitter's algorithm.
376 */
379 {
382 }
384 {
388 {
391 }
392 }
394 /*
395 * Acquire the sample rows
396 */
401 /*
402 * Compute the statistics. Temporary results during the calculations for
403 * each column are stored in a child context. The calc routines are
404 * responsible to make sure that whatever they store into the VacAttrStats
405 * structure is allocated in anl_context.
406 */
408 {
409 MemoryContext col_context,
410 old_context;
414 ALLOCSET_DEFAULT_MINSIZE,
415 ALLOCSET_DEFAULT_INITSIZE,
416 ALLOCSET_DEFAULT_MAXSIZE);
420 {
426 std_fetch_func,
427 numrows,
428 totalrows);
430 }
436 col_context);
441 /*
442 * Emit the completed stats rows into pg_statistic, replacing any
443 * previous statistics for the target columns. (If there are stats in
444 * pg_statistic for columns we didn't process, we leave them alone.)
445 */
449 {
454 }
455 }
457 /*
458 * If we are running a standalone ANALYZE, update pages/tuples stats in
459 * pg_class. We know the accurate page count from the smgr, but only an
460 * approximate number of tuples; therefore, if we are part of VACUUM
461 * ANALYZE do *not* overwrite the accurate count already inserted by
462 * VACUUM. The same consideration applies to indexes.
463 */
465 {
469 InvalidTransactionId);
472 {
480 InvalidTransactionId);
481 }
483 /* report results to the stats collector, too */
485 }
487 /* We skip to here if there were no analyzable columns */
488 cleanup:
490 /* Done with indexes */
493 /*
494 * Close source relation now, but keep lock so that no one deletes it
495 * before we commit. (If someone did, they'd fail to clean up the entries
496 * we made in pg_statistic. Also, releasing the lock before commit would
497 * expose us to concurrent-update failures in update_attstats.)
498 */
501 /* Log the action if appropriate */
503 {
506 Log_autovacuum_min_duration))
513 }
515 /*
516 * Reset my PGPROC flag. Note: we need this here, and not in vacuum_rel,
517 * because the vacuum flag is cleared by the end-of-xact code.
518 */
523 /* Restore userid */
525 }
527 /*
528 * Compute statistics about indexes of a relation
529 */
530 static void
534 MemoryContext col_context)
535 {
536 MemoryContext ind_context,
537 old_context;
541 i;
545 ALLOCSET_DEFAULT_MINSIZE,
546 ALLOCSET_DEFAULT_INITSIZE,
547 ALLOCSET_DEFAULT_MAXSIZE);
551 {
562 tcnt,
563 rowno;
566 /* Ignore index if no columns to analyze and not partial */
570 /*
571 * Need an EState for evaluation of index expressions and
572 * partial-index predicates. Create it in the per-index context to be
573 * sure it gets cleaned up at the bottom of the loop.
574 */
577 /* Need a slot to hold the current heap tuple, too */
580 /* Arrange for econtext's scan tuple to be the tuple under test */
583 /* Set up execution state for predicate. */
586 estate);
588 /* Compute and save index expression values */
594 {
597 /* Set up for predicate or expression evaluation */
600 /* If index is partial, check predicate */
602 {
605 }
606 numindexrows++;
609 {
610 /*
611 * Evaluate the index row to compute expression values. We
612 * could do this by hand, but FormIndexDatum is convenient.
613 */
615 slot,
616 estate,
617 values,
618 isnull);
620 /*
621 * Save just the columns we care about.
622 */
624 {
630 tcnt++;
631 }
632 }
633 }
635 /*
636 * Having counted the number of rows that pass the predicate in the
637 * sample, we can estimate the total number of rows in the index.
638 */
642 /*
643 * Now we can compute the statistics for the expression columns.
644 */
646 {
649 {
656 ind_fetch_func,
657 numindexrows,
658 totalindexrows);
660 }
661 }
663 /* And clean up */
669 }
673 }
675 /*
676 * examine_attribute -- pre-analysis of a single column
677 *
678 * Determine whether the column is analyzable; if so, create and initialize
679 * a VacAttrStats struct for it. If not, return NULL.
680 */
683 {
685 HeapTuple typtuple;
690 /* Never analyze dropped columns */
694 /* Don't analyze column if user has specified not to */
698 /*
699 * Create the VacAttrStats struct.
700 */
715 /*
716 * The fields describing the stats->stavalues[n] element types default
717 * to the type of the field being analyzed, but the type-specific
718 * typanalyze function can change them if it wants to store something
719 * else.
720 */
722 {
727 }
729 /*
730 * Call the type-specific typanalyze function. If none is specified, use
731 * std_typanalyze().
732 */
736 else
740 {
745 }
748 }
750 /*
751 * BlockSampler_Init -- prepare for random sampling of blocknumbers
752 *
753 * BlockSampler is used for stage one of our new two-stage tuple
754 * sampling mechanism as discussed on pgsql-hackers 2004-04-02 (subject
755 * "Large DB"). It selects a random sample of samplesize blocks out of
756 * the nblocks blocks in the table. If the table has less than
757 * samplesize blocks, all blocks are selected.
758 *
759 * Since we know the total number of blocks in advance, we can use the
760 * straightforward Algorithm S from Knuth 3.4.2, rather than Vitter's
761 * algorithm.
762 */
763 static void
765 {
768 /*
769 * If we decide to reduce samplesize for tables that have less or not much
770 * more than samplesize blocks, here is the place to do it.
771 */
775 }
777 static bool
779 {
781 }
783 static BlockNumber
785 {
794 {
795 /* need all the rest */
798 }
800 /*----------
801 * It is not obvious that this code matches Knuth's Algorithm S.
802 * Knuth says to skip the current block with probability 1 - k/K.
803 * If we are to skip, we should advance t (hence decrease K), and
804 * repeat the same probabilistic test for the next block. The naive
805 * implementation thus requires a random_fract() call for each block
806 * number. But we can reduce this to one random_fract() call per
807 * selected block, by noting that each time the while-test succeeds,
808 * we can reinterpret V as a uniform random number in the range 0 to p.
809 * Therefore, instead of choosing a new V, we just adjust p to be
810 * the appropriate fraction of its former value, and our next loop
811 * makes the appropriate probabilistic test.
812 *
813 * We have initially K > k > 0. If the loop reduces K to equal k,
814 * the next while-test must fail since p will become exactly zero
815 * (we assume there will not be roundoff error in the division).
816 * (Note: Knuth suggests a "<=" loop condition, but we use "<" just
817 * to be doubly sure about roundoff error.) Therefore K cannot become
818 * less than k, which means that we cannot fail to select enough blocks.
819 *----------
820 */
824 {
825 /* skip */
829 /* adjust p to be new cutoff point in reduced range */
831 }
833 /* select */
836 }
838 /*
839 * acquire_sample_rows -- acquire a random sample of rows from the table
840 *
841 * As of May 2004 we use a new two-stage method: Stage one selects up
842 * to targrows random blocks (or all blocks, if there aren't so many).
843 * Stage two scans these blocks and uses the Vitter algorithm to create
844 * a random sample of targrows rows (or less, if there are less in the
845 * sample of blocks). The two stages are executed simultaneously: each
846 * block is processed as soon as stage one returns its number and while
847 * the rows are read stage two controls which ones are to be inserted
848 * into the sample.
849 *
850 * Although every row has an equal chance of ending up in the final
851 * sample, this sampling method is not perfect: not every possible
852 * sample has an equal chance of being selected. For large relations
853 * the number of different blocks represented by the sample tends to be
854 * too small. We can live with that for now. Improvements are welcome.
855 *
856 * We also estimate the total numbers of live and dead rows in the table,
857 * and return them into *totalrows and *totaldeadrows, respectively.
858 *
859 * An important property of this sampling method is that because we do
860 * look at a statistically unbiased set of blocks, we should get
861 * unbiased estimates of the average numbers of live and dead rows per
862 * block. The previous sampling method put too much credence in the row
863 * density near the start of the table.
864 *
865 * The returned list of tuples is in order by physical position in the table.
866 * (We will rely on this later to derive correlation estimates.)
867 */
868 static int
871 {
877 BlockNumber totalblocks;
878 TransactionId OldestXmin;
879 BlockSamplerData bs;
886 /* Need a cutoff xmin for HeapTupleSatisfiesVacuum */
889 /* Prepare for sampling block numbers */
891 /* Prepare for sampling rows */
894 /* Outer loop over blocks to sample */
896 {
898 Buffer targbuffer;
899 Page targpage;
900 OffsetNumber targoffset,
901 maxoffset;
905 /*
906 * We must maintain a pin on the target page's buffer to ensure that
907 * the maxoffset value stays good (else concurrent VACUUM might delete
908 * tuples out from under us). Hence, pin the page until we are done
909 * looking at it. We also choose to hold sharelock on the buffer
910 * throughout --- we could release and re-acquire sharelock for
911 * each tuple, but since we aren't doing much work per tuple, the
912 * extra lock traffic is probably better avoided.
913 */
919 /* Inner loop over all tuples on the selected page */
921 {
922 ItemId itemid;
923 HeapTupleData targtuple;
928 /*
929 * We ignore unused and redirect line pointers. DEAD line
930 * pointers should be counted as dead, because we need vacuum
931 * to run to get rid of them. Note that this rule agrees with
932 * the way that heap_page_prune() counts things.
933 */
935 {
939 }
947 OldestXmin,
948 targbuffer))
949 {
957 /* Count dead and recently-dead rows */
962 /*
963 * Insert-in-progress rows are not counted. We assume
964 * that when the inserting transaction commits or aborts,
965 * it will send a stats message to increment the proper
966 * count. This works right only if that transaction ends
967 * after we finish analyzing the table; if things happen
968 * in the other order, its stats update will be
969 * overwritten by ours. However, the error will be
970 * large only if the other transaction runs long enough
971 * to insert many tuples, so assuming it will finish
972 * after us is the safer option.
973 *
974 * A special case is that the inserting transaction might
975 * be our own. In this case we should count and sample
976 * the row, to accommodate users who load a table and
977 * analyze it in one transaction. (pgstat_report_analyze
978 * has to adjust the numbers we send to the stats collector
979 * to make this come out right.)
980 */
982 {
985 }
989 /*
990 * We count delete-in-progress rows as still live, using
991 * the same reasoning given above; but we don't bother to
992 * include them in the sample.
993 *
994 * If the delete was done by our own transaction, however,
995 * we must count the row as dead to make
996 * pgstat_report_analyze's stats adjustments come out
997 * right. (Note: this works out properly when the row
998 * was both inserted and deleted in our xact.)
999 */
1002 else
1009 }
1012 {
1013 /*
1014 * The first targrows sample rows are simply copied into the
1015 * reservoir. Then we start replacing tuples in the sample
1016 * until we reach the end of the relation. This algorithm is
1017 * from Jeff Vitter's paper (see full citation below). It
1018 * works by repeatedly computing the number of tuples to skip
1019 * before selecting a tuple, which replaces a randomly chosen
1020 * element of the reservoir (current set of tuples). At all
1021 * times the reservoir is a true random sample of the tuples
1022 * we've passed over so far, so when we fall off the end of
1023 * the relation we're done.
1024 */
1027 else
1028 {
1029 /*
1030 * t in Vitter's paper is the number of records already
1031 * processed. If we need to compute a new S value, we
1032 * must use the not-yet-incremented value of samplerows
1033 * as t.
1034 */
1039 {
1040 /*
1041 * Found a suitable tuple, so save it, replacing one
1042 * old tuple at random
1043 */
1049 }
1052 }
1055 }
1056 }
1058 /* Now release the lock and pin on the page */
1060 }
1062 /*
1063 * If we didn't find as many tuples as we wanted then we're done. No sort
1064 * is needed, since they're already in order.
1065 *
1066 * Otherwise we need to sort the collected tuples by position
1067 * (itempointer). It's not worth worrying about corner cases where the
1068 * tuples are already sorted.
1069 */
1073 /*
1074 * Estimate total numbers of rows in relation.
1075 */
1077 {
1080 }
1081 else
1082 {
1085 }
1087 /*
1088 * Emit some interesting relation info
1089 */
1092 "containing %.0f live rows and %.0f dead rows; "
1100 }
1102 /* Select a random value R uniformly distributed in (0 - 1) */
1103 static double
1105 {
1107 }
1109 /*
1110 * These two routines embody Algorithm Z from "Random sampling with a
1111 * reservoir" by Jeffrey S. Vitter, in ACM Trans. Math. Softw. 11, 1
1112 * (Mar. 1985), Pages 37-57. Vitter describes his algorithm in terms
1113 * of the count S of records to skip before processing another record.
1114 * It is computed primarily based on t, the number of records already read.
1115 * The only extra state needed between calls is W, a random state variable.
1116 *
1117 * init_selection_state computes the initial W value.
1118 *
1119 * Given that we've already read t records (t >= n), get_next_S
1120 * determines the number of records to skip before the next record is
1121 * processed.
1122 */
1123 static double
1125 {
1126 /* Initial value of W (for use when Algorithm Z is first applied) */
1128 }
1130 static double
1132 {
1135 /* The magic constant here is T from Vitter's paper */
1137 {
1138 /* Process records using Algorithm X until t is large enough */
1140 quot;
1145 /* Note: "num" in Vitter's code is always equal to t - n */
1147 /* Find min S satisfying (4.1) */
1149 {
1153 }
1154 }
1155 else
1156 {
1157 /* Now apply Algorithm Z */
1162 {
1164 numer_lim,
1165 denom;
1167 X,
1168 lhs,
1169 rhs,
1170 y,
1171 tmp;
1173 /* Generate U and X */
1177 /* Test if U <= h(S)/cg(X) in the manner of (6.3) */
1182 {
1185 }
1186 /* Test if U <= f(S)/cg(X) */
1189 {
1192 }
1193 else
1194 {
1197 }
1199 {
1202 }
1206 }
1208 }
1210 }
1212 /*
1213 * qsort comparator for sorting rows[] array
1214 */
1215 static int
1217 {
1234 }
1237 /*
1238 * update_attstats() -- update attribute statistics for one relation
1239 *
1240 * Statistics are stored in several places: the pg_class row for the
1241 * relation has stats about the whole relation, and there is a
1242 * pg_statistic row for each (non-system) attribute that has ever
1243 * been analyzed. The pg_class values are updated by VACUUM, not here.
1244 *
1245 * pg_statistic rows are just added or updated normally. This means
1246 * that pg_statistic will probably contain some deleted rows at the
1247 * completion of a vacuum cycle, unless it happens to get vacuumed last.
1248 *
1249 * To keep things simple, we punt for pg_statistic, and don't try
1250 * to compute or store rows for pg_statistic itself in pg_statistic.
1251 * This could possibly be made to work, but it's not worth the trouble.
1252 * Note analyze_rel() has seen to it that we won't come here when
1253 * vacuuming pg_statistic itself.
1254 *
1255 * Note: there would be a race condition here if two backends could
1256 * ANALYZE the same table concurrently. Presently, we lock that out
1257 * by taking a self-exclusive lock on the relation in analyze_rel().
1258 */
1259 static void
1261 {
1262 Relation sd;
1271 {
1273 HeapTuple stup,
1274 oldtup;
1276 k,
1277 n;
1282 /* Ignore attr if we weren't able to collect stats */
1286 /*
1287 * Construct a new pg_statistic tuple
1288 */
1290 {
1293 }
1302 {
1304 }
1306 {
1308 }
1310 {
1314 {
1320 /* XXX knows more than it should about type float4: */
1322 FLOAT4OID,
1325 }
1326 else
1327 {
1330 }
1331 }
1333 {
1335 {
1345 }
1346 else
1347 {
1350 }
1351 }
1353 /* Is there already a pg_statistic tuple for this attribute? */
1360 {
1361 /* Yes, replace it */
1364 values,
1365 nulls,
1366 replaces);
1369 }
1370 else
1371 {
1372 /* No, insert new tuple */
1375 }
1377 /* update indexes too */
1381 }
1384 }
1386 /*
1387 * Standard fetch function for use by compute_stats subroutines.
1388 *
1389 * This exists to provide some insulation between compute_stats routines
1390 * and the actual storage of the sample data.
1391 */
1392 static Datum
1394 {
1400 }
1402 /*
1403 * Fetch function for analyzing index expressions.
1404 *
1405 * We have not bothered to construct index tuples, instead the data is
1406 * just in Datum arrays.
1407 */
1408 static Datum
1410 {
1413 /* exprvals and exprnulls are already offset for proper column */
1417 }
1420 /*==========================================================================
1421 *
1422 * Code below this point represents the "standard" type-specific statistics
1423 * analysis algorithms. This code can be replaced on a per-data-type basis
1424 * by setting a nonzero value in pg_type.typanalyze.
1425 *
1426 *==========================================================================
1427 */
1430 /*
1431 * To avoid consuming too much memory during analysis and/or too much space
1432 * in the resulting pg_statistic rows, we ignore varlena datums that are wider
1433 * than WIDTH_THRESHOLD (after detoasting!). This is legitimate for MCV
1434 * and distinct-value calculations since a wide value is unlikely to be
1435 * duplicated at all, much less be a most-common value. For the same reason,
1436 * ignoring wide values will not affect our estimates of histogram bin
1437 * boundaries very much.
1438 */
1439 #define WIDTH_THRESHOLD 1024
1441 #define swapInt(a,b) do {int _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1442 #define swapDatum(a,b) do {Datum _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1444 /*
1445 * Extra information used by the default analysis routines
1446 */
1448 {
1455 {
1461 {
1467 {
1475 AnalyzeAttrFetchFunc fetchfunc,
1479 AnalyzeAttrFetchFunc fetchfunc,
1486 /*
1487 * std_typanalyze -- the default type-specific typanalyze function
1488 */
1489 static bool
1491 {
1493 Oid ltopr;
1494 Oid eqopr;
1497 /* If the attstattarget column is negative, use the default value */
1498 /* NB: it is okay to scribble on stats->attr since it's a copy */
1502 /* Look for default "<" and "=" operators for column's type */
1507 /* If column has no "=" operator, we can't do much of anything */
1511 /* Save the operator info for compute_stats routines */
1518 /*
1519 * Determine which standard statistics algorithm to use
1520 */
1522 {
1523 /* Seems to be a scalar datatype */
1525 /*--------------------
1526 * The following choice of minrows is based on the paper
1527 * "Random sampling for histogram construction: how much is enough?"
1528 * by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in
1529 * Proceedings of ACM SIGMOD International Conference on Management
1530 * of Data, 1998, Pages 436-447. Their Corollary 1 to Theorem 5
1531 * says that for table size n, histogram size k, maximum relative
1532 * error in bin size f, and error probability gamma, the minimum
1533 * random sample size is
1534 * r = 4 * k * ln(2*n/gamma) / f^2
1535 * Taking f = 0.5, gamma = 0.01, n = 1 million rows, we obtain
1536 * r = 305.82 * k
1537 * Note that because of the log function, the dependence on n is
1538 * quite weak; even at n = 1 billion, a 300*k sample gives <= 0.59
1539 * bin size error with probability 0.99. So there's no real need to
1540 * scale for n, which is a good thing because we don't necessarily
1541 * know it at this point.
1542 *--------------------
1543 */
1545 }
1546 else
1547 {
1548 /* Can't do much but the minimal stuff */
1550 /* Might as well use the same minrows as above */
1552 }
1555 }
1557 /*
1558 * compute_minimal_stats() -- compute minimal column statistics
1559 *
1560 * We use this when we can find only an "=" operator for the datatype.
1561 *
1562 * We determine the fraction of non-null rows, the average width, the
1563 * most common values, and the (estimated) number of distinct values.
1564 *
1565 * The most common values are determined by brute force: we keep a list
1566 * of previously seen values, ordered by number of times seen, as we scan
1567 * the samples. A newly seen value is inserted just after the last
1568 * multiply-seen value, causing the bottommost (oldest) singly-seen value
1569 * to drop off the list. The accuracy of this method, and also its cost,
1570 * depend mainly on the length of the list we are willing to keep.
1571 */
1572 static void
1574 AnalyzeAttrFetchFunc fetchfunc,
1577 {
1587 FmgrInfo f_cmpeq;
1589 {
1590 Datum value;
1595 track_max;
1599 /*
1600 * We track up to 2*n values for an n-element MCV list; but at least 10
1601 */
1611 {
1612 Datum value;
1616 j;
1622 /* Check for null/nonnull */
1624 {
1625 null_cnt++;
1627 }
1628 nonnull_cnt++;
1630 /*
1631 * If it's a variable-width field, add up widths for average width
1632 * calculation. Note that if the value is toasted, we use the toasted
1633 * width. We don't bother with this calculation if it's a fixed-width
1634 * type.
1635 */
1637 {
1640 /*
1641 * If the value is toasted, we want to detoast it just once to
1642 * avoid repeated detoastings and resultant excess memory usage
1643 * during the comparisons. Also, check to see if the value is
1644 * excessively wide, and if so don't detoast at all --- just
1645 * ignore the value.
1646 */
1648 {
1649 toowide_cnt++;
1651 }
1653 }
1655 {
1656 /* must be cstring */
1658 }
1660 /*
1661 * See if the value matches anything we're already tracking.
1662 */
1666 {
1668 {
1671 }
1674 }
1677 {
1678 /* Found a match */
1680 /* This value may now need to "bubble up" in the track list */
1682 {
1685 j--;
1686 }
1687 }
1688 else
1689 {
1690 /* No match. Insert at head of count-1 list */
1692 track_cnt++;
1694 {
1697 }
1699 {
1702 }
1703 }
1704 }
1706 /* We can only compute real stats if we found some non-null values. */
1708 {
1710 summultiple;
1713 /* Do the simple null-frac and width stats */
1717 else
1720 /* Count the number of values we found multiple times */
1723 {
1727 }
1730 {
1731 /* If we found no repeated values, assume it's a unique column */
1733 }
1736 {
1737 /*
1738 * Our track list includes every value in the sample, and every
1739 * value appeared more than once. Assume the column has just
1740 * these values.
1741 */
1743 }
1744 else
1745 {
1746 /*----------
1747 * Estimate the number of distinct values using the estimator
1748 * proposed by Haas and Stokes in IBM Research Report RJ 10025:
1749 * n*d / (n - f1 + f1*n/N)
1750 * where f1 is the number of distinct values that occurred
1751 * exactly once in our sample of n rows (from a total of N),
1752 * and d is the total number of distinct values in the sample.
1753 * This is their Duj1 estimator; the other estimators they
1754 * recommend are considerably more complex, and are numerically
1755 * very unstable when n is much smaller than N.
1756 *
1757 * We assume (not very reliably!) that all the multiply-occurring
1758 * values are reflected in the final track[] list, and the other
1759 * nonnull values all appeared but once. (XXX this usually
1760 * results in a drastic overestimate of ndistinct. Can we do
1761 * any better?)
1762 *----------
1763 */
1767 denom,
1768 stadistinct;
1776 /* Clamp to sane range in case of roundoff error */
1782 }
1784 /*
1785 * If we estimated the number of distinct values at more than 10% of
1786 * the total row count (a very arbitrary limit), then assume that
1787 * stadistinct should scale with the row count rather than be a fixed
1788 * value.
1789 */
1793 /*
1794 * Decide how many values are worth storing as most-common values. If
1795 * we are able to generate a complete MCV list (all the values in the
1796 * sample will fit, and we think these are all the ones in the table),
1797 * then do so. Otherwise, store only those values that are
1798 * significantly more common than the (estimated) average. We set the
1799 * threshold rather arbitrarily at 25% more than average, with at
1800 * least 2 instances in the sample.
1801 */
1805 {
1806 /* Track list includes all values seen, and all will fit */
1808 }
1809 else
1810 {
1813 mincount;
1817 /* estimate # of occurrences in sample of a typical value */
1819 /* set minimum threshold count to store a value */
1826 {
1828 {
1831 }
1832 }
1833 }
1835 /* Generate MCV slot entry */
1837 {
1838 MemoryContext old_context;
1842 /* Must copy the target values into anl_context */
1847 {
1852 }
1861 /*
1862 * Accept the defaults for stats->statypid and others.
1863 * They have been set before we were called (see vacuum.h)
1864 */
1865 }
1866 }
1868 {
1869 /* We found only nulls; assume the column is entirely null */
1874 else
1877 }
1879 /* We don't need to bother cleaning up any of our temporary palloc's */
1880 }
1883 /*
1884 * compute_scalar_stats() -- compute column statistics
1885 *
1886 * We use this when we can find "=" and "<" operators for the datatype.
1887 *
1888 * We determine the fraction of non-null rows, the average width, the
1889 * most common values, the (estimated) number of distinct values, the
1890 * distribution histogram, and the correlation of physical to logical order.
1891 *
1892 * The desired stats can be determined fairly easily after sorting the
1893 * data values into order.
1894 */
1895 static void
1897 AnalyzeAttrFetchFunc fetchfunc,
1900 {
1911 Oid cmpFn;
1913 FmgrInfo f_cmpfn;
1930 /* Initial scan to find sortable values */
1932 {
1933 Datum value;
1940 /* Check for null/nonnull */
1942 {
1943 null_cnt++;
1945 }
1946 nonnull_cnt++;
1948 /*
1949 * If it's a variable-width field, add up widths for average width
1950 * calculation. Note that if the value is toasted, we use the toasted
1951 * width. We don't bother with this calculation if it's a fixed-width
1952 * type.
1953 */
1955 {
1958 /*
1959 * If the value is toasted, we want to detoast it just once to
1960 * avoid repeated detoastings and resultant excess memory usage
1961 * during the comparisons. Also, check to see if the value is
1962 * excessively wide, and if so don't detoast at all --- just
1963 * ignore the value.
1964 */
1966 {
1967 toowide_cnt++;
1969 }
1971 }
1973 {
1974 /* must be cstring */
1976 }
1978 /* Add it to the list to be sorted */
1982 values_cnt++;
1983 }
1985 /* We can only compute real stats if we found some sortable values. */
1987 {
1990 num_hist,
1991 dups_cnt;
1993 CompareScalarsContext cxt;
1995 /* Sort the collected values */
2002 /*
2003 * Now scan the values in order, find the most common ones, and also
2004 * accumulate ordering-correlation statistics.
2005 *
2006 * To determine which are most common, we first have to count the
2007 * number of duplicates of each value. The duplicates are adjacent in
2008 * the sorted list, so a brute-force approach is to compare successive
2009 * datum values until we find two that are not equal. However, that
2010 * requires N-1 invocations of the datum comparison routine, which are
2011 * completely redundant with work that was done during the sort. (The
2012 * sort algorithm must at some point have compared each pair of items
2013 * that are adjacent in the sorted order; otherwise it could not know
2014 * that it's ordered the pair correctly.) We exploit this by having
2015 * compare_scalars remember the highest tupno index that each
2016 * ScalarItem has been found equal to. At the end of the sort, a
2017 * ScalarItem's tupnoLink will still point to itself if and only if it
2018 * is the last item of its group of duplicates (since the group will
2019 * be ordered by tupno).
2020 */
2026 {
2030 dups_cnt++;
2032 {
2033 /* Reached end of duplicates of this value */
2034 ndistinct++;
2036 {
2037 nmultiple++;
2040 {
2041 /*
2042 * Found a new item for the mcv list; find its
2043 * position, bubbling down old items if needed. Loop
2044 * invariant is that j points at an empty/ replaceable
2045 * slot.
2046 */
2050 track_cnt++;
2052 {
2057 }
2060 }
2061 }
2063 }
2064 }
2067 /* Do the simple null-frac and width stats */
2071 else
2075 {
2076 /* If we found no repeated values, assume it's a unique column */
2078 }
2080 {
2081 /*
2082 * Every value in the sample appeared more than once. Assume the
2083 * column has just these values.
2084 */
2086 }
2087 else
2088 {
2089 /*----------
2090 * Estimate the number of distinct values using the estimator
2091 * proposed by Haas and Stokes in IBM Research Report RJ 10025:
2092 * n*d / (n - f1 + f1*n/N)
2093 * where f1 is the number of distinct values that occurred
2094 * exactly once in our sample of n rows (from a total of N),
2095 * and d is the total number of distinct values in the sample.
2096 * This is their Duj1 estimator; the other estimators they
2097 * recommend are considerably more complex, and are numerically
2098 * very unstable when n is much smaller than N.
2099 *
2100 * Overwidth values are assumed to have been distinct.
2101 *----------
2102 */
2106 denom,
2107 stadistinct;
2115 /* Clamp to sane range in case of roundoff error */
2121 }
2123 /*
2124 * If we estimated the number of distinct values at more than 10% of
2125 * the total row count (a very arbitrary limit), then assume that
2126 * stadistinct should scale with the row count rather than be a fixed
2127 * value.
2128 */
2132 /*
2133 * Decide how many values are worth storing as most-common values. If
2134 * we are able to generate a complete MCV list (all the values in the
2135 * sample will fit, and we think these are all the ones in the table),
2136 * then do so. Otherwise, store only those values that are
2137 * significantly more common than the (estimated) average. We set the
2138 * threshold rather arbitrarily at 25% more than average, with at
2139 * least 2 instances in the sample. Also, we won't suppress values
2140 * that have a frequency of at least 1/K where K is the intended
2141 * number of histogram bins; such values might otherwise cause us to
2142 * emit duplicate histogram bin boundaries.
2143 */
2147 {
2148 /* Track list includes all values seen, and all will fit */
2150 }
2151 else
2152 {
2155 mincount,
2156 maxmincount;
2160 /* estimate # of occurrences in sample of a typical value */
2162 /* set minimum threshold count to store a value */
2166 /* don't let threshold exceed 1/K, however */
2173 {
2175 {
2178 }
2179 }
2180 }
2182 /* Generate MCV slot entry */
2184 {
2185 MemoryContext old_context;
2189 /* Must copy the target values into anl_context */
2194 {
2199 }
2208 /*
2209 * Accept the defaults for stats->statypid and others.
2210 * They have been set before we were called (see vacuum.h)
2211 */
2212 slot_idx++;
2213 }
2215 /*
2216 * Generate a histogram slot entry if there are at least two distinct
2217 * values not accounted for in the MCV list. (This ensures the
2218 * histogram won't collapse to empty or a singleton.)
2219 */
2224 {
2225 MemoryContext old_context;
2229 /* Sort the MCV items into position order to speed next loop */
2233 /*
2234 * Collapse out the MCV items from the values[] array.
2235 *
2236 * Note we destroy the values[] array here... but we don't need it
2237 * for anything more. We do, however, still need values_cnt.
2238 * nvals will be the number of remaining entries in values[].
2239 */
2241 {
2243 dest;
2249 {
2253 {
2257 {
2258 /* advance past this MCV item */
2260 j++;
2262 }
2264 }
2265 else
2271 }
2273 }
2274 else
2278 /* Must copy the target values into anl_context */
2282 {
2289 }
2296 /*
2297 * Accept the defaults for stats->statypid and others.
2298 * They have been set before we were called (see vacuum.h)
2299 */
2300 slot_idx++;
2301 }
2303 /* Generate a correlation entry if there are multiple values */
2305 {
2306 MemoryContext old_context;
2309 corr_x2sum;
2311 /* Must copy the target values into anl_context */
2316 /*----------
2317 * Since we know the x and y value sets are both
2318 * 0, 1, ..., values_cnt-1
2319 * we have sum(x) = sum(y) =
2320 * (values_cnt-1)*values_cnt / 2
2321 * and sum(x^2) = sum(y^2) =
2322 * (values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
2323 *----------
2324 */
2330 /* And the correlation coefficient reduces to */
2338 slot_idx++;
2339 }
2340 }
2342 {
2343 /* We found only nulls; assume the column is entirely null */
2348 else
2351 }
2353 /* We don't need to bother cleaning up any of our temporary palloc's */
2354 }
2356 /*
2357 * qsort_arg comparator for sorting ScalarItems
2358 *
2359 * Aside from sorting the items, we update the tupnoLink[] array
2360 * whenever two ScalarItems are found to contain equal datums. The array
2361 * is indexed by tupno; for each ScalarItem, it contains the highest
2362 * tupno that that item's datum has been found to be equal to. This allows
2363 * us to avoid additional comparisons in compute_scalar_stats().
2364 */
2365 static int
2367 {
2373 int32 compare;
2380 /*
2381 * The two datums are equal, so update cxt->tupnoLink[].
2382 */
2388 /*
2389 * For equal datums, sort by tupno
2390 */
2392 }
2394 /*
2395 * qsort comparator for sorting ScalarMCVItems by position
2396 */
2397 static int
2399 {
2404 }