| blob | d2a1aaf154a3bd48ab0dcd5da9aba833a18d7b15 |
1 /*-------------------------------------------------------------------------
2 *
3 * analyze.c
4 * the Postgres statistics generator
5 *
6 * Portions Copyright (c) 1996-2009, 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 * If update_reltuples is true, we update reltuples and relpages columns
106 * in pg_class. Caller should pass false if we're part of VACUUM ANALYZE,
107 * and the VACUUM didn't skip any pages. We only have an approximate count,
108 * so we don't want to overwrite the accurate values already inserted by the
109 * VACUUM in that case. VACUUM always scans all indexes, however, so the
110 * pg_class entries for indexes are never updated if we're part of VACUUM
111 * ANALYZE.
112 */
113 void
116 {
117 Relation onerel;
119 tcnt,
120 i,
121 ind;
129 numrows;
131 totaldeadrows;
133 PGRUsage ru0;
135 Oid save_userid;
140 else
145 /*
146 * Use the current context for storing analysis info. vacuum.c ensures
147 * that this context will be cleared when I return, thus releasing the
148 * memory allocated here.
149 */
152 /*
153 * Check for user-requested abort. Note we want this to be inside a
154 * transaction, so xact.c doesn't issue useless WARNING.
155 */
158 /*
159 * Open the relation, getting ShareUpdateExclusiveLock to ensure that two
160 * ANALYZEs don't run on it concurrently. (This also locks out a
161 * concurrent VACUUM, which doesn't matter much at the moment but might
162 * matter if we ever try to accumulate stats on dead tuples.) If the rel
163 * has been dropped since we last saw it, we don't need to process it.
164 */
169 /*
170 * Check permissions --- this should match vacuum's check!
171 */
174 {
175 /* No need for a WARNING if we already complained during VACUUM */
177 {
186 else
190 }
193 }
195 /*
196 * Check that it's a plain table; we used to do this in get_rel_oids() but
197 * seems safer to check after we've locked the relation.
198 */
200 {
201 /* No need for a WARNING if we already complained during VACUUM */
208 }
210 /*
211 * Silently ignore tables that are temp tables of other backends ---
212 * trying to analyze these is rather pointless, since their contents are
213 * probably not up-to-date on disk. (We don't throw a warning here; it
214 * would just lead to chatter during a database-wide ANALYZE.)
215 */
217 {
220 }
222 /*
223 * We can ANALYZE any table except pg_statistic. See update_attstats
224 */
226 {
229 }
236 /*
237 * Switch to the table owner's userid, so that any index functions are run
238 * as that user.
239 */
243 /* let others know what I'm doing */
248 /* measure elapsed time iff autovacuum logging requires it */
250 {
254 }
256 /*
257 * Determine which columns to analyze
258 *
259 * Note that system attributes are never analyzed.
260 */
262 {
269 {
280 tcnt++;
281 }
283 }
284 else
285 {
291 {
294 tcnt++;
295 }
297 }
299 /*
300 * Open all indexes of the relation, and see if there are any analyzable
301 * columns in the indexes. We do not analyze index columns if there was
302 * an explicit column list in the ANALYZE command, however.
303 */
309 {
312 {
319 {
326 {
330 {
331 /* Found an index expression */
339 /*
340 * Can't analyze if the opclass uses a storage type
341 * different from the expression result type. We'd get
342 * confused because the type shown in pg_attribute for
343 * the index column doesn't match what we are getting
344 * from the expression. Perhaps this can be fixed
345 * someday, but for now, punt.
346 */
354 {
355 tcnt++;
357 }
358 }
359 }
361 }
362 }
363 }
365 /*
366 * Quit if no analyzable columns and no pg_class update needed.
367 */
371 /*
372 * Determine how many rows we need to sample, using the worst case from
373 * all analyzable columns. We use a lower bound of 100 rows to avoid
374 * possible overflow in Vitter's algorithm.
375 */
378 {
381 }
383 {
387 {
390 }
391 }
393 /*
394 * Acquire the sample rows
395 */
400 /*
401 * Compute the statistics. Temporary results during the calculations for
402 * each column are stored in a child context. The calc routines are
403 * responsible to make sure that whatever they store into the VacAttrStats
404 * structure is allocated in anl_context.
405 */
407 {
408 MemoryContext col_context,
409 old_context;
413 ALLOCSET_DEFAULT_MINSIZE,
414 ALLOCSET_DEFAULT_INITSIZE,
415 ALLOCSET_DEFAULT_MAXSIZE);
419 {
425 std_fetch_func,
426 numrows,
427 totalrows);
429 }
435 col_context);
440 /*
441 * Emit the completed stats rows into pg_statistic, replacing any
442 * previous statistics for the target columns. (If there are stats in
443 * pg_statistic for columns we didn't process, we leave them alone.)
444 */
448 {
453 }
454 }
456 /*
457 * Update pages/tuples stats in pg_class.
458 */
460 {
464 /* report results to the stats collector, too */
466 }
468 /*
469 * Same for indexes. Vacuum always scans all indexes, so if we're part of
470 * VACUUM ANALYZE, don't overwrite the accurate count already inserted by
471 * VACUUM.
472 */
474 {
476 {
484 }
485 }
487 /* We skip to here if there were no analyzable columns */
488 cleanup:
490 /* If this isn't part of VACUUM ANALYZE, let index AMs do cleanup */
492 {
494 {
496 IndexVacuumInfo ivinfo;
510 }
511 }
513 /* Done with indexes */
516 /*
517 * Close source relation now, but keep lock so that no one deletes it
518 * before we commit. (If someone did, they'd fail to clean up the entries
519 * we made in pg_statistic. Also, releasing the lock before commit would
520 * expose us to concurrent-update failures in update_attstats.)
521 */
524 /* Log the action if appropriate */
526 {
529 Log_autovacuum_min_duration))
536 }
538 /*
539 * Reset my PGPROC flag. Note: we need this here, and not in vacuum_rel,
540 * because the vacuum flag is cleared by the end-of-xact code.
541 */
546 /* Restore userid */
548 }
550 /*
551 * Compute statistics about indexes of a relation
552 */
553 static void
557 MemoryContext col_context)
558 {
559 MemoryContext ind_context,
560 old_context;
564 i;
568 ALLOCSET_DEFAULT_MINSIZE,
569 ALLOCSET_DEFAULT_INITSIZE,
570 ALLOCSET_DEFAULT_MAXSIZE);
574 {
585 tcnt,
586 rowno;
589 /* Ignore index if no columns to analyze and not partial */
593 /*
594 * Need an EState for evaluation of index expressions and
595 * partial-index predicates. Create it in the per-index context to be
596 * sure it gets cleaned up at the bottom of the loop.
597 */
600 /* Need a slot to hold the current heap tuple, too */
603 /* Arrange for econtext's scan tuple to be the tuple under test */
606 /* Set up execution state for predicate. */
609 estate);
611 /* Compute and save index expression values */
617 {
620 /* Set up for predicate or expression evaluation */
623 /* If index is partial, check predicate */
625 {
628 }
629 numindexrows++;
632 {
633 /*
634 * Evaluate the index row to compute expression values. We
635 * could do this by hand, but FormIndexDatum is convenient.
636 */
638 slot,
639 estate,
640 values,
641 isnull);
643 /*
644 * Save just the columns we care about.
645 */
647 {
653 tcnt++;
654 }
655 }
656 }
658 /*
659 * Having counted the number of rows that pass the predicate in the
660 * sample, we can estimate the total number of rows in the index.
661 */
665 /*
666 * Now we can compute the statistics for the expression columns.
667 */
669 {
672 {
679 ind_fetch_func,
680 numindexrows,
681 totalindexrows);
683 }
684 }
686 /* And clean up */
692 }
696 }
698 /*
699 * examine_attribute -- pre-analysis of a single column
700 *
701 * Determine whether the column is analyzable; if so, create and initialize
702 * a VacAttrStats struct for it. If not, return NULL.
703 */
706 {
708 HeapTuple typtuple;
713 /* Never analyze dropped columns */
717 /* Don't analyze column if user has specified not to */
721 /*
722 * Create the VacAttrStats struct. Note that we only have a copy of the
723 * fixed fields of the pg_attribute tuple.
724 */
739 /*
740 * The fields describing the stats->stavalues[n] element types default to
741 * the type of the field being analyzed, but the type-specific typanalyze
742 * function can change them if it wants to store something else.
743 */
745 {
750 }
752 /*
753 * Call the type-specific typanalyze function. If none is specified, use
754 * std_typanalyze().
755 */
759 else
763 {
768 }
771 }
773 /*
774 * BlockSampler_Init -- prepare for random sampling of blocknumbers
775 *
776 * BlockSampler is used for stage one of our new two-stage tuple
777 * sampling mechanism as discussed on pgsql-hackers 2004-04-02 (subject
778 * "Large DB"). It selects a random sample of samplesize blocks out of
779 * the nblocks blocks in the table. If the table has less than
780 * samplesize blocks, all blocks are selected.
781 *
782 * Since we know the total number of blocks in advance, we can use the
783 * straightforward Algorithm S from Knuth 3.4.2, rather than Vitter's
784 * algorithm.
785 */
786 static void
788 {
791 /*
792 * If we decide to reduce samplesize for tables that have less or not much
793 * more than samplesize blocks, here is the place to do it.
794 */
798 }
800 static bool
802 {
804 }
806 static BlockNumber
808 {
817 {
818 /* need all the rest */
821 }
823 /*----------
824 * It is not obvious that this code matches Knuth's Algorithm S.
825 * Knuth says to skip the current block with probability 1 - k/K.
826 * If we are to skip, we should advance t (hence decrease K), and
827 * repeat the same probabilistic test for the next block. The naive
828 * implementation thus requires a random_fract() call for each block
829 * number. But we can reduce this to one random_fract() call per
830 * selected block, by noting that each time the while-test succeeds,
831 * we can reinterpret V as a uniform random number in the range 0 to p.
832 * Therefore, instead of choosing a new V, we just adjust p to be
833 * the appropriate fraction of its former value, and our next loop
834 * makes the appropriate probabilistic test.
835 *
836 * We have initially K > k > 0. If the loop reduces K to equal k,
837 * the next while-test must fail since p will become exactly zero
838 * (we assume there will not be roundoff error in the division).
839 * (Note: Knuth suggests a "<=" loop condition, but we use "<" just
840 * to be doubly sure about roundoff error.) Therefore K cannot become
841 * less than k, which means that we cannot fail to select enough blocks.
842 *----------
843 */
847 {
848 /* skip */
852 /* adjust p to be new cutoff point in reduced range */
854 }
856 /* select */
859 }
861 /*
862 * acquire_sample_rows -- acquire a random sample of rows from the table
863 *
864 * As of May 2004 we use a new two-stage method: Stage one selects up
865 * to targrows random blocks (or all blocks, if there aren't so many).
866 * Stage two scans these blocks and uses the Vitter algorithm to create
867 * a random sample of targrows rows (or less, if there are less in the
868 * sample of blocks). The two stages are executed simultaneously: each
869 * block is processed as soon as stage one returns its number and while
870 * the rows are read stage two controls which ones are to be inserted
871 * into the sample.
872 *
873 * Although every row has an equal chance of ending up in the final
874 * sample, this sampling method is not perfect: not every possible
875 * sample has an equal chance of being selected. For large relations
876 * the number of different blocks represented by the sample tends to be
877 * too small. We can live with that for now. Improvements are welcome.
878 *
879 * We also estimate the total numbers of live and dead rows in the table,
880 * and return them into *totalrows and *totaldeadrows, respectively.
881 *
882 * An important property of this sampling method is that because we do
883 * look at a statistically unbiased set of blocks, we should get
884 * unbiased estimates of the average numbers of live and dead rows per
885 * block. The previous sampling method put too much credence in the row
886 * density near the start of the table.
887 *
888 * The returned list of tuples is in order by physical position in the table.
889 * (We will rely on this later to derive correlation estimates.)
890 */
891 static int
894 {
900 BlockNumber totalblocks;
901 TransactionId OldestXmin;
902 BlockSamplerData bs;
909 /* Need a cutoff xmin for HeapTupleSatisfiesVacuum */
912 /* Prepare for sampling block numbers */
914 /* Prepare for sampling rows */
917 /* Outer loop over blocks to sample */
919 {
921 Buffer targbuffer;
922 Page targpage;
923 OffsetNumber targoffset,
924 maxoffset;
928 /*
929 * We must maintain a pin on the target page's buffer to ensure that
930 * the maxoffset value stays good (else concurrent VACUUM might delete
931 * tuples out from under us). Hence, pin the page until we are done
932 * looking at it. We also choose to hold sharelock on the buffer
933 * throughout --- we could release and re-acquire sharelock for each
934 * tuple, but since we aren't doing much work per tuple, the extra
935 * lock traffic is probably better avoided.
936 */
943 /* Inner loop over all tuples on the selected page */
945 {
946 ItemId itemid;
947 HeapTupleData targtuple;
952 /*
953 * We ignore unused and redirect line pointers. DEAD line
954 * pointers should be counted as dead, because we need vacuum to
955 * run to get rid of them. Note that this rule agrees with the
956 * way that heap_page_prune() counts things.
957 */
959 {
963 }
971 OldestXmin,
972 targbuffer))
973 {
981 /* Count dead and recently-dead rows */
987 /*
988 * Insert-in-progress rows are not counted. We assume
989 * that when the inserting transaction commits or aborts,
990 * it will send a stats message to increment the proper
991 * count. This works right only if that transaction ends
992 * after we finish analyzing the table; if things happen
993 * in the other order, its stats update will be
994 * overwritten by ours. However, the error will be large
995 * only if the other transaction runs long enough to
996 * insert many tuples, so assuming it will finish after us
997 * is the safer option.
998 *
999 * A special case is that the inserting transaction might
1000 * be our own. In this case we should count and sample
1001 * the row, to accommodate users who load a table and
1002 * analyze it in one transaction. (pgstat_report_analyze
1003 * has to adjust the numbers we send to the stats
1004 * collector to make this come out right.)
1005 */
1007 {
1010 }
1015 /*
1016 * We count delete-in-progress rows as still live, using
1017 * the same reasoning given above; but we don't bother to
1018 * include them in the sample.
1019 *
1020 * If the delete was done by our own transaction, however,
1021 * we must count the row as dead to make
1022 * pgstat_report_analyze's stats adjustments come out
1023 * right. (Note: this works out properly when the row was
1024 * both inserted and deleted in our xact.)
1025 */
1028 else
1035 }
1038 {
1039 /*
1040 * The first targrows sample rows are simply copied into the
1041 * reservoir. Then we start replacing tuples in the sample
1042 * until we reach the end of the relation. This algorithm is
1043 * from Jeff Vitter's paper (see full citation below). It
1044 * works by repeatedly computing the number of tuples to skip
1045 * before selecting a tuple, which replaces a randomly chosen
1046 * element of the reservoir (current set of tuples). At all
1047 * times the reservoir is a true random sample of the tuples
1048 * we've passed over so far, so when we fall off the end of
1049 * the relation we're done.
1050 */
1053 else
1054 {
1055 /*
1056 * t in Vitter's paper is the number of records already
1057 * processed. If we need to compute a new S value, we
1058 * must use the not-yet-incremented value of samplerows as
1059 * t.
1060 */
1065 {
1066 /*
1067 * Found a suitable tuple, so save it, replacing one
1068 * old tuple at random
1069 */
1075 }
1078 }
1081 }
1082 }
1084 /* Now release the lock and pin on the page */
1086 }
1088 /*
1089 * If we didn't find as many tuples as we wanted then we're done. No sort
1090 * is needed, since they're already in order.
1091 *
1092 * Otherwise we need to sort the collected tuples by position
1093 * (itempointer). It's not worth worrying about corner cases where the
1094 * tuples are already sorted.
1095 */
1099 /*
1100 * Estimate total numbers of rows in relation.
1101 */
1103 {
1106 }
1107 else
1108 {
1111 }
1113 /*
1114 * Emit some interesting relation info
1115 */
1118 "containing %.0f live rows and %.0f dead rows; "
1126 }
1128 /* Select a random value R uniformly distributed in (0 - 1) */
1129 static double
1131 {
1133 }
1135 /*
1136 * These two routines embody Algorithm Z from "Random sampling with a
1137 * reservoir" by Jeffrey S. Vitter, in ACM Trans. Math. Softw. 11, 1
1138 * (Mar. 1985), Pages 37-57. Vitter describes his algorithm in terms
1139 * of the count S of records to skip before processing another record.
1140 * It is computed primarily based on t, the number of records already read.
1141 * The only extra state needed between calls is W, a random state variable.
1142 *
1143 * init_selection_state computes the initial W value.
1144 *
1145 * Given that we've already read t records (t >= n), get_next_S
1146 * determines the number of records to skip before the next record is
1147 * processed.
1148 */
1149 static double
1151 {
1152 /* Initial value of W (for use when Algorithm Z is first applied) */
1154 }
1156 static double
1158 {
1161 /* The magic constant here is T from Vitter's paper */
1163 {
1164 /* Process records using Algorithm X until t is large enough */
1166 quot;
1171 /* Note: "num" in Vitter's code is always equal to t - n */
1173 /* Find min S satisfying (4.1) */
1175 {
1179 }
1180 }
1181 else
1182 {
1183 /* Now apply Algorithm Z */
1188 {
1190 numer_lim,
1191 denom;
1193 X,
1194 lhs,
1195 rhs,
1196 y,
1197 tmp;
1199 /* Generate U and X */
1203 /* Test if U <= h(S)/cg(X) in the manner of (6.3) */
1208 {
1211 }
1212 /* Test if U <= f(S)/cg(X) */
1215 {
1218 }
1219 else
1220 {
1223 }
1225 {
1228 }
1232 }
1234 }
1236 }
1238 /*
1239 * qsort comparator for sorting rows[] array
1240 */
1241 static int
1243 {
1260 }
1263 /*
1264 * update_attstats() -- update attribute statistics for one relation
1265 *
1266 * Statistics are stored in several places: the pg_class row for the
1267 * relation has stats about the whole relation, and there is a
1268 * pg_statistic row for each (non-system) attribute that has ever
1269 * been analyzed. The pg_class values are updated by VACUUM, not here.
1270 *
1271 * pg_statistic rows are just added or updated normally. This means
1272 * that pg_statistic will probably contain some deleted rows at the
1273 * completion of a vacuum cycle, unless it happens to get vacuumed last.
1274 *
1275 * To keep things simple, we punt for pg_statistic, and don't try
1276 * to compute or store rows for pg_statistic itself in pg_statistic.
1277 * This could possibly be made to work, but it's not worth the trouble.
1278 * Note analyze_rel() has seen to it that we won't come here when
1279 * vacuuming pg_statistic itself.
1280 *
1281 * Note: there would be a race condition here if two backends could
1282 * ANALYZE the same table concurrently. Presently, we lock that out
1283 * by taking a self-exclusive lock on the relation in analyze_rel().
1284 */
1285 static void
1287 {
1288 Relation sd;
1297 {
1299 HeapTuple stup,
1300 oldtup;
1302 k,
1303 n;
1308 /* Ignore attr if we weren't able to collect stats */
1312 /*
1313 * Construct a new pg_statistic tuple
1314 */
1316 {
1319 }
1328 {
1330 }
1332 {
1334 }
1336 {
1340 {
1346 /* XXX knows more than it should about type float4: */
1348 FLOAT4OID,
1351 }
1352 else
1353 {
1356 }
1357 }
1359 {
1361 {
1371 }
1372 else
1373 {
1376 }
1377 }
1379 /* Is there already a pg_statistic tuple for this attribute? */
1386 {
1387 /* Yes, replace it */
1390 values,
1391 nulls,
1392 replaces);
1395 }
1396 else
1397 {
1398 /* No, insert new tuple */
1401 }
1403 /* update indexes too */
1407 }
1410 }
1412 /*
1413 * Standard fetch function for use by compute_stats subroutines.
1414 *
1415 * This exists to provide some insulation between compute_stats routines
1416 * and the actual storage of the sample data.
1417 */
1418 static Datum
1420 {
1426 }
1428 /*
1429 * Fetch function for analyzing index expressions.
1430 *
1431 * We have not bothered to construct index tuples, instead the data is
1432 * just in Datum arrays.
1433 */
1434 static Datum
1436 {
1439 /* exprvals and exprnulls are already offset for proper column */
1443 }
1446 /*==========================================================================
1447 *
1448 * Code below this point represents the "standard" type-specific statistics
1449 * analysis algorithms. This code can be replaced on a per-data-type basis
1450 * by setting a nonzero value in pg_type.typanalyze.
1451 *
1452 *==========================================================================
1453 */
1456 /*
1457 * To avoid consuming too much memory during analysis and/or too much space
1458 * in the resulting pg_statistic rows, we ignore varlena datums that are wider
1459 * than WIDTH_THRESHOLD (after detoasting!). This is legitimate for MCV
1460 * and distinct-value calculations since a wide value is unlikely to be
1461 * duplicated at all, much less be a most-common value. For the same reason,
1462 * ignoring wide values will not affect our estimates of histogram bin
1463 * boundaries very much.
1464 */
1465 #define WIDTH_THRESHOLD 1024
1467 #define swapInt(a,b) do {int _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1468 #define swapDatum(a,b) do {Datum _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1470 /*
1471 * Extra information used by the default analysis routines
1472 */
1474 {
1481 {
1487 {
1493 {
1501 AnalyzeAttrFetchFunc fetchfunc,
1505 AnalyzeAttrFetchFunc fetchfunc,
1512 /*
1513 * std_typanalyze -- the default type-specific typanalyze function
1514 */
1515 static bool
1517 {
1519 Oid ltopr;
1520 Oid eqopr;
1523 /* If the attstattarget column is negative, use the default value */
1524 /* NB: it is okay to scribble on stats->attr since it's a copy */
1528 /* Look for default "<" and "=" operators for column's type */
1533 /* If column has no "=" operator, we can't do much of anything */
1537 /* Save the operator info for compute_stats routines */
1544 /*
1545 * Determine which standard statistics algorithm to use
1546 */
1548 {
1549 /* Seems to be a scalar datatype */
1551 /*--------------------
1552 * The following choice of minrows is based on the paper
1553 * "Random sampling for histogram construction: how much is enough?"
1554 * by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in
1555 * Proceedings of ACM SIGMOD International Conference on Management
1556 * of Data, 1998, Pages 436-447. Their Corollary 1 to Theorem 5
1557 * says that for table size n, histogram size k, maximum relative
1558 * error in bin size f, and error probability gamma, the minimum
1559 * random sample size is
1560 * r = 4 * k * ln(2*n/gamma) / f^2
1561 * Taking f = 0.5, gamma = 0.01, n = 10^6 rows, we obtain
1562 * r = 305.82 * k
1563 * Note that because of the log function, the dependence on n is
1564 * quite weak; even at n = 10^12, a 300*k sample gives <= 0.66
1565 * bin size error with probability 0.99. So there's no real need to
1566 * scale for n, which is a good thing because we don't necessarily
1567 * know it at this point.
1568 *--------------------
1569 */
1571 }
1572 else
1573 {
1574 /* Can't do much but the minimal stuff */
1576 /* Might as well use the same minrows as above */
1578 }
1581 }
1583 /*
1584 * compute_minimal_stats() -- compute minimal column statistics
1585 *
1586 * We use this when we can find only an "=" operator for the datatype.
1587 *
1588 * We determine the fraction of non-null rows, the average width, the
1589 * most common values, and the (estimated) number of distinct values.
1590 *
1591 * The most common values are determined by brute force: we keep a list
1592 * of previously seen values, ordered by number of times seen, as we scan
1593 * the samples. A newly seen value is inserted just after the last
1594 * multiply-seen value, causing the bottommost (oldest) singly-seen value
1595 * to drop off the list. The accuracy of this method, and also its cost,
1596 * depend mainly on the length of the list we are willing to keep.
1597 */
1598 static void
1600 AnalyzeAttrFetchFunc fetchfunc,
1603 {
1613 FmgrInfo f_cmpeq;
1615 {
1616 Datum value;
1621 track_max;
1625 /*
1626 * We track up to 2*n values for an n-element MCV list; but at least 10
1627 */
1637 {
1638 Datum value;
1642 j;
1648 /* Check for null/nonnull */
1650 {
1651 null_cnt++;
1653 }
1654 nonnull_cnt++;
1656 /*
1657 * If it's a variable-width field, add up widths for average width
1658 * calculation. Note that if the value is toasted, we use the toasted
1659 * width. We don't bother with this calculation if it's a fixed-width
1660 * type.
1661 */
1663 {
1666 /*
1667 * If the value is toasted, we want to detoast it just once to
1668 * avoid repeated detoastings and resultant excess memory usage
1669 * during the comparisons. Also, check to see if the value is
1670 * excessively wide, and if so don't detoast at all --- just
1671 * ignore the value.
1672 */
1674 {
1675 toowide_cnt++;
1677 }
1679 }
1681 {
1682 /* must be cstring */
1684 }
1686 /*
1687 * See if the value matches anything we're already tracking.
1688 */
1692 {
1694 {
1697 }
1700 }
1703 {
1704 /* Found a match */
1706 /* This value may now need to "bubble up" in the track list */
1708 {
1711 j--;
1712 }
1713 }
1714 else
1715 {
1716 /* No match. Insert at head of count-1 list */
1718 track_cnt++;
1720 {
1723 }
1725 {
1728 }
1729 }
1730 }
1732 /* We can only compute real stats if we found some non-null values. */
1734 {
1736 summultiple;
1739 /* Do the simple null-frac and width stats */
1743 else
1746 /* Count the number of values we found multiple times */
1749 {
1753 }
1756 {
1757 /* If we found no repeated values, assume it's a unique column */
1759 }
1762 {
1763 /*
1764 * Our track list includes every value in the sample, and every
1765 * value appeared more than once. Assume the column has just
1766 * these values.
1767 */
1769 }
1770 else
1771 {
1772 /*----------
1773 * Estimate the number of distinct values using the estimator
1774 * proposed by Haas and Stokes in IBM Research Report RJ 10025:
1775 * n*d / (n - f1 + f1*n/N)
1776 * where f1 is the number of distinct values that occurred
1777 * exactly once in our sample of n rows (from a total of N),
1778 * and d is the total number of distinct values in the sample.
1779 * This is their Duj1 estimator; the other estimators they
1780 * recommend are considerably more complex, and are numerically
1781 * very unstable when n is much smaller than N.
1782 *
1783 * We assume (not very reliably!) that all the multiply-occurring
1784 * values are reflected in the final track[] list, and the other
1785 * nonnull values all appeared but once. (XXX this usually
1786 * results in a drastic overestimate of ndistinct. Can we do
1787 * any better?)
1788 *----------
1789 */
1793 denom,
1794 stadistinct;
1802 /* Clamp to sane range in case of roundoff error */
1808 }
1810 /*
1811 * If we estimated the number of distinct values at more than 10% of
1812 * the total row count (a very arbitrary limit), then assume that
1813 * stadistinct should scale with the row count rather than be a fixed
1814 * value.
1815 */
1819 /*
1820 * Decide how many values are worth storing as most-common values. If
1821 * we are able to generate a complete MCV list (all the values in the
1822 * sample will fit, and we think these are all the ones in the table),
1823 * then do so. Otherwise, store only those values that are
1824 * significantly more common than the (estimated) average. We set the
1825 * threshold rather arbitrarily at 25% more than average, with at
1826 * least 2 instances in the sample.
1827 */
1831 {
1832 /* Track list includes all values seen, and all will fit */
1834 }
1835 else
1836 {
1839 mincount;
1843 /* estimate # of occurrences in sample of a typical value */
1845 /* set minimum threshold count to store a value */
1852 {
1854 {
1857 }
1858 }
1859 }
1861 /* Generate MCV slot entry */
1863 {
1864 MemoryContext old_context;
1868 /* Must copy the target values into anl_context */
1873 {
1878 }
1888 /*
1889 * Accept the defaults for stats->statypid and others. They have
1890 * been set before we were called (see vacuum.h)
1891 */
1892 }
1893 }
1895 {
1896 /* We found only nulls; assume the column is entirely null */
1901 else
1904 }
1906 /* We don't need to bother cleaning up any of our temporary palloc's */
1907 }
1910 /*
1911 * compute_scalar_stats() -- compute column statistics
1912 *
1913 * We use this when we can find "=" and "<" operators for the datatype.
1914 *
1915 * We determine the fraction of non-null rows, the average width, the
1916 * most common values, the (estimated) number of distinct values, the
1917 * distribution histogram, and the correlation of physical to logical order.
1918 *
1919 * The desired stats can be determined fairly easily after sorting the
1920 * data values into order.
1921 */
1922 static void
1924 AnalyzeAttrFetchFunc fetchfunc,
1927 {
1938 Oid cmpFn;
1940 FmgrInfo f_cmpfn;
1957 /* Initial scan to find sortable values */
1959 {
1960 Datum value;
1967 /* Check for null/nonnull */
1969 {
1970 null_cnt++;
1972 }
1973 nonnull_cnt++;
1975 /*
1976 * If it's a variable-width field, add up widths for average width
1977 * calculation. Note that if the value is toasted, we use the toasted
1978 * width. We don't bother with this calculation if it's a fixed-width
1979 * type.
1980 */
1982 {
1985 /*
1986 * If the value is toasted, we want to detoast it just once to
1987 * avoid repeated detoastings and resultant excess memory usage
1988 * during the comparisons. Also, check to see if the value is
1989 * excessively wide, and if so don't detoast at all --- just
1990 * ignore the value.
1991 */
1993 {
1994 toowide_cnt++;
1996 }
1998 }
2000 {
2001 /* must be cstring */
2003 }
2005 /* Add it to the list to be sorted */
2009 values_cnt++;
2010 }
2012 /* We can only compute real stats if we found some sortable values. */
2014 {
2017 num_hist,
2018 dups_cnt;
2020 CompareScalarsContext cxt;
2022 /* Sort the collected values */
2029 /*
2030 * Now scan the values in order, find the most common ones, and also
2031 * accumulate ordering-correlation statistics.
2032 *
2033 * To determine which are most common, we first have to count the
2034 * number of duplicates of each value. The duplicates are adjacent in
2035 * the sorted list, so a brute-force approach is to compare successive
2036 * datum values until we find two that are not equal. However, that
2037 * requires N-1 invocations of the datum comparison routine, which are
2038 * completely redundant with work that was done during the sort. (The
2039 * sort algorithm must at some point have compared each pair of items
2040 * that are adjacent in the sorted order; otherwise it could not know
2041 * that it's ordered the pair correctly.) We exploit this by having
2042 * compare_scalars remember the highest tupno index that each
2043 * ScalarItem has been found equal to. At the end of the sort, a
2044 * ScalarItem's tupnoLink will still point to itself if and only if it
2045 * is the last item of its group of duplicates (since the group will
2046 * be ordered by tupno).
2047 */
2053 {
2057 dups_cnt++;
2059 {
2060 /* Reached end of duplicates of this value */
2061 ndistinct++;
2063 {
2064 nmultiple++;
2067 {
2068 /*
2069 * Found a new item for the mcv list; find its
2070 * position, bubbling down old items if needed. Loop
2071 * invariant is that j points at an empty/ replaceable
2072 * slot.
2073 */
2077 track_cnt++;
2079 {
2084 }
2087 }
2088 }
2090 }
2091 }
2094 /* Do the simple null-frac and width stats */
2098 else
2102 {
2103 /* If we found no repeated values, assume it's a unique column */
2105 }
2107 {
2108 /*
2109 * Every value in the sample appeared more than once. Assume the
2110 * column has just these values.
2111 */
2113 }
2114 else
2115 {
2116 /*----------
2117 * Estimate the number of distinct values using the estimator
2118 * proposed by Haas and Stokes in IBM Research Report RJ 10025:
2119 * n*d / (n - f1 + f1*n/N)
2120 * where f1 is the number of distinct values that occurred
2121 * exactly once in our sample of n rows (from a total of N),
2122 * and d is the total number of distinct values in the sample.
2123 * This is their Duj1 estimator; the other estimators they
2124 * recommend are considerably more complex, and are numerically
2125 * very unstable when n is much smaller than N.
2126 *
2127 * Overwidth values are assumed to have been distinct.
2128 *----------
2129 */
2133 denom,
2134 stadistinct;
2142 /* Clamp to sane range in case of roundoff error */
2148 }
2150 /*
2151 * If we estimated the number of distinct values at more than 10% of
2152 * the total row count (a very arbitrary limit), then assume that
2153 * stadistinct should scale with the row count rather than be a fixed
2154 * value.
2155 */
2159 /*
2160 * Decide how many values are worth storing as most-common values. If
2161 * we are able to generate a complete MCV list (all the values in the
2162 * sample will fit, and we think these are all the ones in the table),
2163 * then do so. Otherwise, store only those values that are
2164 * significantly more common than the (estimated) average. We set the
2165 * threshold rather arbitrarily at 25% more than average, with at
2166 * least 2 instances in the sample. Also, we won't suppress values
2167 * that have a frequency of at least 1/K where K is the intended
2168 * number of histogram bins; such values might otherwise cause us to
2169 * emit duplicate histogram bin boundaries. (We might end up with
2170 * duplicate histogram entries anyway, if the distribution is skewed;
2171 * but we prefer to treat such values as MCVs if at all possible.)
2172 */
2176 {
2177 /* Track list includes all values seen, and all will fit */
2179 }
2180 else
2181 {
2184 mincount,
2185 maxmincount;
2189 /* estimate # of occurrences in sample of a typical value */
2191 /* set minimum threshold count to store a value */
2195 /* don't let threshold exceed 1/K, however */
2202 {
2204 {
2207 }
2208 }
2209 }
2211 /* Generate MCV slot entry */
2213 {
2214 MemoryContext old_context;
2218 /* Must copy the target values into anl_context */
2223 {
2228 }
2238 /*
2239 * Accept the defaults for stats->statypid and others. They have
2240 * been set before we were called (see vacuum.h)
2241 */
2242 slot_idx++;
2243 }
2245 /*
2246 * Generate a histogram slot entry if there are at least two distinct
2247 * values not accounted for in the MCV list. (This ensures the
2248 * histogram won't collapse to empty or a singleton.)
2249 */
2254 {
2255 MemoryContext old_context;
2259 posfrac,
2260 delta,
2261 deltafrac;
2263 /* Sort the MCV items into position order to speed next loop */
2267 /*
2268 * Collapse out the MCV items from the values[] array.
2269 *
2270 * Note we destroy the values[] array here... but we don't need it
2271 * for anything more. We do, however, still need values_cnt.
2272 * nvals will be the number of remaining entries in values[].
2273 */
2275 {
2277 dest;
2283 {
2287 {
2291 {
2292 /* advance past this MCV item */
2294 j++;
2296 }
2298 }
2299 else
2305 }
2307 }
2308 else
2312 /* Must copy the target values into anl_context */
2316 /*
2317 * The object of this loop is to copy the first and last values[]
2318 * entries along with evenly-spaced values in between. So the
2319 * i'th value is values[(i * (nvals - 1)) / (num_hist - 1)]. But
2320 * computing that subscript directly risks integer overflow when
2321 * the stats target is more than a couple thousand. Instead we
2322 * add (nvals - 1) / (num_hist - 1) to pos at each step, tracking
2323 * the integral and fractional parts of the sum separately.
2324 */
2330 {
2337 {
2338 /* fractional part exceeds 1, carry to integer part */
2339 pos++;
2341 }
2342 }
2351 /*
2352 * Accept the defaults for stats->statypid and others. They have
2353 * been set before we were called (see vacuum.h)
2354 */
2355 slot_idx++;
2356 }
2358 /* Generate a correlation entry if there are multiple values */
2360 {
2361 MemoryContext old_context;
2364 corr_x2sum;
2366 /* Must copy the target values into anl_context */
2371 /*----------
2372 * Since we know the x and y value sets are both
2373 * 0, 1, ..., values_cnt-1
2374 * we have sum(x) = sum(y) =
2375 * (values_cnt-1)*values_cnt / 2
2376 * and sum(x^2) = sum(y^2) =
2377 * (values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
2378 *----------
2379 */
2385 /* And the correlation coefficient reduces to */
2393 slot_idx++;
2394 }
2395 }
2397 {
2398 /* We found only nulls; assume the column is entirely null */
2403 else
2406 }
2408 /* We don't need to bother cleaning up any of our temporary palloc's */
2409 }
2411 /*
2412 * qsort_arg comparator for sorting ScalarItems
2413 *
2414 * Aside from sorting the items, we update the tupnoLink[] array
2415 * whenever two ScalarItems are found to contain equal datums. The array
2416 * is indexed by tupno; for each ScalarItem, it contains the highest
2417 * tupno that that item's datum has been found to be equal to. This allows
2418 * us to avoid additional comparisons in compute_scalar_stats().
2419 */
2420 static int
2422 {
2428 int32 compare;
2435 /*
2436 * The two datums are equal, so update cxt->tupnoLink[].
2437 */
2443 /*
2444 * For equal datums, sort by tupno
2445 */
2447 }
2449 /*
2450 * qsort comparator for sorting ScalarMCVItems by position
2451 */
2452 static int
2454 {
2459 }