| blob | 7d2cd24997292a0865cee0d51b7762e98d96590a |
1 /*-------------------------------------------------------------------------
2 *
3 * analyze.c
4 * the Postgres statistics generator
5 *
6 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/commands/analyze.c
12 *
13 *-------------------------------------------------------------------------
14 */
17 #include <math.h>
62 /* Per-index data for ANALYZE */
64 {
72 /* Default statistics target (GUC parameter) */
75 /* A few variables that don't seem worth passing around as parameters */
87 MemoryContext col_context);
103 /*
104 * analyze_rel() -- analyze one relation
105 *
106 * relid identifies the relation to analyze. If relation is supplied, use
107 * the name therein for reporting any failure to open/lock the rel; do not
108 * use it once we've successfully opened the rel, since it might be stale.
109 */
110 void
113 BufferAccessStrategy bstrategy)
114 {
115 Relation onerel;
120 /* Select logging level */
123 else
126 /* Set up static variables */
129 /*
130 * Check for user-requested abort.
131 */
134 /*
135 * Open the relation, getting ShareUpdateExclusiveLock to ensure that two
136 * ANALYZEs don't run on it concurrently. (This also locks out a
137 * concurrent VACUUM, which doesn't matter much at the moment but might
138 * matter if we ever try to accumulate stats on dead tuples.) If the rel
139 * has been dropped since we last saw it, we don't need to process it.
140 *
141 * Make sure to generate only logs for ANALYZE in this case.
142 */
145 ShareUpdateExclusiveLock);
147 /* leave if relation could not be opened or locked */
151 /*
152 * Check if relation needs to be skipped based on privileges. This check
153 * happens also when building the relation list to analyze for a manual
154 * operation, and needs to be done additionally here as ANALYZE could
155 * happen across multiple transactions where privileges could have changed
156 * in-between. Make sure to generate only logs for ANALYZE in this case.
157 */
161 {
164 }
166 /*
167 * Silently ignore tables that are temp tables of other backends ---
168 * trying to analyze these is rather pointless, since their contents are
169 * probably not up-to-date on disk. (We don't throw a warning here; it
170 * would just lead to chatter during a database-wide ANALYZE.)
171 */
173 {
176 }
178 /*
179 * We can ANALYZE any table except pg_statistic. See update_attstats
180 */
182 {
185 }
187 /*
188 * Check that it's of an analyzable relkind, and set up appropriately.
189 */
192 {
193 /* Regular table, so we'll use the regular row acquisition function */
195 /* Also get regular table's size */
197 }
199 {
200 /*
201 * For a foreign table, call the FDW's hook function to see whether it
202 * supports analysis.
203 */
215 {
221 }
222 }
224 {
225 /*
226 * For partitioned tables, we want to do the recursive ANALYZE below.
227 */
228 }
229 else
230 {
231 /* No need for a WARNING if we already complained during VACUUM */
238 }
240 /*
241 * OK, let's do it. First, initialize progress reporting.
242 */
246 /*
247 * Do the normal non-recursive ANALYZE. We can skip this for partitioned
248 * tables, which don't contain any rows.
249 */
254 /*
255 * If there are child tables, do recursive ANALYZE.
256 */
261 /*
262 * Close source relation now, but keep lock so that no one deletes it
263 * before we commit. (If someone did, they'd fail to clean up the entries
264 * we made in pg_statistic. Also, releasing the lock before commit would
265 * expose us to concurrent-update failures in update_attstats.)
266 */
270 }
272 /*
273 * do_analyze_rel() -- analyze one relation, recursively or not
274 *
275 * Note that "acquirefunc" is only relevant for the non-inherited case.
276 * For the inherited case, acquire_inherited_sample_rows() determines the
277 * appropriate acquirefunc for each child table.
278 */
279 static void
284 {
286 tcnt,
287 i,
288 ind;
295 numrows,
296 minrows;
298 totaldeadrows;
300 PGRUsage ru0;
302 MemoryContext caller_context;
303 Oid save_userid;
317 else
323 /*
324 * Set up a working context so that we can easily free whatever junk gets
325 * created.
326 */
329 ALLOCSET_DEFAULT_SIZES);
332 /*
333 * Switch to the table owner's userid, so that any index functions are run
334 * as that user. Also lock down security-restricted operations and
335 * arrange to make GUC variable changes local to this command.
336 */
343 /* measure elapsed time iff autovacuum logging requires it */
345 {
347 {
350 }
354 }
356 /*
357 * Determine which columns to analyze
358 *
359 * Note that system attributes are never analyzed, so we just reject them
360 * at the lookup stage. We also reject duplicate column mentions. (We
361 * could alternatively ignore duplicates, but analyzing a column twice
362 * won't work; we'd end up making a conflicting update in pg_statistic.)
363 */
365 {
373 {
391 tcnt++;
392 }
394 }
395 else
396 {
402 {
405 tcnt++;
406 }
408 }
410 /*
411 * Open all indexes of the relation, and see if there are any analyzable
412 * columns in the indexes. We do not analyze index columns if there was
413 * an explicit column list in the ANALYZE command, however.
414 *
415 * If we are doing a recursive scan, we don't want to touch the parent's
416 * indexes at all. If we're processing a partitioned table, we need to
417 * know if there are any indexes, but we don't want to process them.
418 */
420 {
427 }
429 {
432 }
433 else
434 {
438 }
441 {
444 {
451 {
458 {
462 {
463 /* Found an index expression */
470 indexpr_item);
474 tcnt++;
475 }
476 }
478 }
479 }
480 }
482 /*
483 * Determine how many rows we need to sample, using the worst case from
484 * all analyzable columns. We use a lower bound of 100 rows to avoid
485 * possible overflow in Vitter's algorithm. (Note: that will also be the
486 * target in the corner case where there are no analyzable columns.)
487 */
490 {
493 }
495 {
499 {
502 }
503 }
505 /*
506 * Look at extended statistics objects too, as those may define custom
507 * statistics target. So we may need to sample more rows and then build
508 * the statistics with enough detail.
509 */
515 /*
516 * Acquire the sample rows
517 */
521 PROGRESS_ANALYZE_PHASE_ACQUIRE_SAMPLE_ROWS);
526 else
531 /*
532 * Compute the statistics. Temporary results during the calculations for
533 * each column are stored in a child context. The calc routines are
534 * responsible to make sure that whatever they store into the VacAttrStats
535 * structure is allocated in anl_context.
536 */
538 {
539 MemoryContext col_context,
540 old_context;
543 PROGRESS_ANALYZE_PHASE_COMPUTE_STATS);
547 ALLOCSET_DEFAULT_SIZES);
551 {
558 std_fetch_func,
559 numrows,
560 totalrows);
562 /*
563 * If the appropriate flavor of the n_distinct option is
564 * specified, override with the corresponding value.
565 */
568 {
569 float8 n_distinct;
574 }
577 }
583 col_context);
588 /*
589 * Emit the completed stats rows into pg_statistic, replacing any
590 * previous statistics for the target columns. (If there are stats in
591 * pg_statistic for columns we didn't process, we leave them alone.)
592 */
597 {
602 }
604 /* Build extended statistics (if there are any). */
607 }
610 PROGRESS_ANALYZE_PHASE_FINALIZE_ANALYZE);
612 /*
613 * Update pages/tuples stats in pg_class ... but not if we're doing
614 * inherited stats.
615 *
616 * We assume that VACUUM hasn't set pg_class.reltuples already, even
617 * during a VACUUM ANALYZE. Although VACUUM often updates pg_class,
618 * exceptions exist. A "VACUUM (ANALYZE, INDEX_CLEANUP OFF)" command will
619 * never update pg_class entries for index relations. It's also possible
620 * that an individual index's pg_class entry won't be updated during
621 * VACUUM if the index AM returns NULL from its amvacuumcleanup() routine.
622 */
624 {
625 BlockNumber relallvisible;
629 else
632 /* Update pg_class for table relation */
634 relpages,
635 totalrows,
636 relallvisible,
637 hasindex,
638 InvalidTransactionId,
639 InvalidMultiXactId,
641 in_outer_xact);
643 /* Same for indexes */
645 {
652 totalindexrows,
655 InvalidTransactionId,
656 InvalidMultiXactId,
658 in_outer_xact);
659 }
660 }
662 {
663 /*
664 * Partitioned tables don't have storage, so we don't set any fields
665 * in their pg_class entries except for reltuples and relhasindex.
666 */
669 InvalidMultiXactId,
671 in_outer_xact);
672 }
674 /*
675 * Now report ANALYZE to the cumulative stats system. For regular tables,
676 * we do it only if not doing inherited stats. For partitioned tables, we
677 * only do it for inherited stats. (We're never called for not-inherited
678 * stats on partitioned tables anyway.)
679 *
680 * Reset the changes_since_analyze counter only if we analyzed all
681 * columns; otherwise, there is still work for auto-analyze to do.
682 */
689 /*
690 * If this isn't part of VACUUM ANALYZE, let index AMs do cleanup.
691 *
692 * Note that most index AMs perform a no-op as a matter of policy for
693 * amvacuumcleanup() when called in ANALYZE-only mode. The only exception
694 * among core index AMs is GIN/ginvacuumcleanup().
695 */
697 {
699 {
701 IndexVacuumInfo ivinfo;
715 }
716 }
718 /* Done with indexes */
721 /* Log the action if appropriate */
723 {
729 {
733 StringInfoData buf;
735 /*
736 * Calculate the difference in the Page Hit/Miss/Dirty that
737 * happened as part of the analyze by subtracting out the
738 * pre-analyze values which we saved above.
739 */
744 /*
745 * We do not expect an analyze to take > 25 days and it simplifies
746 * things a bit to use TimestampDifferenceMilliseconds.
747 */
750 /*
751 * Note that we are reporting these read/write rates in the same
752 * manner as VACUUM does, which means that while the 'average read
753 * rate' here actually corresponds to page misses and resulting
754 * reads which are also picked up by track_io_timing, if enabled,
755 * the 'average write rate' is actually talking about the rate of
756 * pages being dirtied, not being written out, so it's typical to
757 * have a non-zero 'avg write rate' while I/O timings only reports
758 * reads.
759 *
760 * It's not clear that an ANALYZE will ever result in
761 * FlushBuffer() being called, but we track and support reporting
762 * on I/O write time in case that changes as it's practically free
763 * to do so anyway.
764 */
767 {
772 }
774 /*
775 * We split this up so we don't emit empty I/O timing values when
776 * track_io_timing isn't enabled.
777 */
785 {
791 }
804 }
805 }
807 /* Roll back any GUC changes executed by index functions */
810 /* Restore userid and security context */
813 /* Restore current context and release memory */
817 }
819 /*
820 * Compute statistics about indexes of a relation
821 */
822 static void
826 MemoryContext col_context)
827 {
828 MemoryContext ind_context,
829 old_context;
833 i;
837 ALLOCSET_DEFAULT_SIZES);
841 {
852 tcnt,
853 rowno;
856 /* Ignore index if no columns to analyze and not partial */
860 /*
861 * Need an EState for evaluation of index expressions and
862 * partial-index predicates. Create it in the per-index context to be
863 * sure it gets cleaned up at the bottom of the loop.
864 */
867 /* Need a slot to hold the current heap tuple, too */
871 /* Arrange for econtext's scan tuple to be the tuple under test */
874 /* Set up execution state for predicate. */
877 /* Compute and save index expression values */
883 {
888 /*
889 * Reset the per-tuple context each time, to reclaim any cruft
890 * left behind by evaluating the predicate or index expressions.
891 */
894 /* Set up for predicate or expression evaluation */
897 /* If index is partial, check predicate */
899 {
902 }
903 numindexrows++;
906 {
907 /*
908 * Evaluate the index row to compute expression values. We
909 * could do this by hand, but FormIndexDatum is convenient.
910 */
912 slot,
913 estate,
914 values,
915 isnull);
917 /*
918 * Save just the columns we care about. We copy the values
919 * into ind_context from the estate's per-tuple context.
920 */
922 {
927 {
930 }
931 else
932 {
937 }
938 tcnt++;
939 }
940 }
941 }
943 /*
944 * Having counted the number of rows that pass the predicate in the
945 * sample, we can estimate the total number of rows in the index.
946 */
950 /*
951 * Now we can compute the statistics for the expression columns.
952 */
954 {
957 {
964 ind_fetch_func,
965 numindexrows,
966 totalindexrows);
969 }
970 }
972 /* And clean up */
978 }
982 }
984 /*
985 * examine_attribute -- pre-analysis of a single column
986 *
987 * Determine whether the column is analyzable; if so, create and initialize
988 * a VacAttrStats struct for it. If not, return NULL.
989 *
990 * If index_expr isn't NULL, then we're trying to analyze an expression index,
991 * and index_expr is the expression tree representing the column's data.
992 */
995 {
998 HeapTuple atttuple;
999 Datum dat;
1001 HeapTuple typtuple;
1006 /* Never analyze dropped columns */
1010 /*
1011 * Get attstattarget value. Set to -1 if null. (Analyze functions expect
1012 * -1 to mean use default_statistics_target; see for example
1013 * std_typanalyze.)
1014 */
1015 atttuple = SearchSysCache2(ATTNUM, ObjectIdGetDatum(RelationGetRelid(onerel)), Int16GetDatum(attnum));
1023 /* Don't analyze column if user has specified not to */
1027 /*
1028 * Create the VacAttrStats struct.
1029 */
1033 /*
1034 * When analyzing an expression index, believe the expression tree's type
1035 * not the column datatype --- the latter might be the opckeytype storage
1036 * type of the opclass, which is not interesting for our purposes. (Note:
1037 * if we did anything with non-expression index columns, we'd need to
1038 * figure out where to get the correct type info from, but for now that's
1039 * not a problem.) It's not clear whether anyone will care about the
1040 * typmod, but we store that too just in case.
1041 */
1043 {
1047 /*
1048 * If a collation has been specified for the index column, use that in
1049 * preference to anything else; but if not, fall back to whatever we
1050 * can get from the expression.
1051 */
1054 else
1056 }
1057 else
1058 {
1062 }
1072 /*
1073 * The fields describing the stats->stavalues[n] element types default to
1074 * the type of the data being analyzed, but the type-specific typanalyze
1075 * function can change them if it wants to store something else.
1076 */
1078 {
1083 }
1085 /*
1086 * Call the type-specific typanalyze function. If none is specified, use
1087 * std_typanalyze().
1088 */
1092 else
1096 {
1100 }
1103 }
1105 /*
1106 * Read stream callback returning the next BlockNumber as chosen by the
1107 * BlockSampling algorithm.
1108 */
1109 static BlockNumber
1113 {
1117 }
1119 /*
1120 * acquire_sample_rows -- acquire a random sample of rows from the table
1121 *
1122 * Selected rows are returned in the caller-allocated array rows[], which
1123 * must have at least targrows entries.
1124 * The actual number of rows selected is returned as the function result.
1125 * We also estimate the total numbers of live and dead rows in the table,
1126 * and return them into *totalrows and *totaldeadrows, respectively.
1127 *
1128 * The returned list of tuples is in order by physical position in the table.
1129 * (We will rely on this later to derive correlation estimates.)
1130 *
1131 * As of May 2004 we use a new two-stage method: Stage one selects up
1132 * to targrows random blocks (or all blocks, if there aren't so many).
1133 * Stage two scans these blocks and uses the Vitter algorithm to create
1134 * a random sample of targrows rows (or less, if there are less in the
1135 * sample of blocks). The two stages are executed simultaneously: each
1136 * block is processed as soon as stage one returns its number and while
1137 * the rows are read stage two controls which ones are to be inserted
1138 * into the sample.
1139 *
1140 * Although every row has an equal chance of ending up in the final
1141 * sample, this sampling method is not perfect: not every possible
1142 * sample has an equal chance of being selected. For large relations
1143 * the number of different blocks represented by the sample tends to be
1144 * too small. We can live with that for now. Improvements are welcome.
1145 *
1146 * An important property of this sampling method is that because we do
1147 * look at a statistically unbiased set of blocks, we should get
1148 * unbiased estimates of the average numbers of live and dead rows per
1149 * block. The previous sampling method put too much credence in the row
1150 * density near the start of the table.
1151 */
1152 static int
1156 {
1163 BlockNumber totalblocks;
1164 TransactionId OldestXmin;
1165 BlockSamplerData bs;
1166 ReservoirStateData rstate;
1168 TableScanDesc scan;
1169 BlockNumber nblocks;
1177 /* Need a cutoff xmin for HeapTupleSatisfiesVacuum */
1180 /* Prepare for sampling block numbers */
1184 /* Report sampling block numbers */
1186 nblocks);
1188 /* Prepare for sampling rows */
1195 vac_strategy,
1197 MAIN_FORKNUM,
1198 block_sampling_read_stream_next,
1202 /* Outer loop over blocks to sample */
1204 {
1208 {
1209 /*
1210 * The first targrows sample rows are simply copied into the
1211 * reservoir. Then we start replacing tuples in the sample until
1212 * we reach the end of the relation. This algorithm is from Jeff
1213 * Vitter's paper (see full citation in utils/misc/sampling.c). It
1214 * works by repeatedly computing the number of tuples to skip
1215 * before selecting a tuple, which replaces a randomly chosen
1216 * element of the reservoir (current set of tuples). At all times
1217 * the reservoir is a true random sample of the tuples we've
1218 * passed over so far, so when we fall off the end of the relation
1219 * we're done.
1220 */
1223 else
1224 {
1225 /*
1226 * t in Vitter's paper is the number of records already
1227 * processed. If we need to compute a new S value, we must
1228 * use the not-yet-incremented value of samplerows as t.
1229 */
1234 {
1235 /*
1236 * Found a suitable tuple, so save it, replacing one old
1237 * tuple at random
1238 */
1244 }
1247 }
1250 }
1254 }
1261 /*
1262 * If we didn't find as many tuples as we wanted then we're done. No sort
1263 * is needed, since they're already in order.
1264 *
1265 * Otherwise we need to sort the collected tuples by position
1266 * (itempointer). It's not worth worrying about corner cases where the
1267 * tuples are already sorted.
1268 */
1273 /*
1274 * Estimate total numbers of live and dead rows in relation, extrapolating
1275 * on the assumption that the average tuple density in pages we didn't
1276 * scan is the same as in the pages we did scan. Since what we scanned is
1277 * a random sample of the pages in the relation, this should be a good
1278 * assumption.
1279 */
1281 {
1284 }
1285 else
1286 {
1289 }
1291 /*
1292 * Emit some interesting relation info
1293 */
1296 "containing %.0f live rows and %.0f dead rows; "
1304 }
1306 /*
1307 * Comparator for sorting rows[] array
1308 */
1309 static int
1311 {
1328 }
1331 /*
1332 * acquire_inherited_sample_rows -- acquire sample rows from inheritance tree
1333 *
1334 * This has the same API as acquire_sample_rows, except that rows are
1335 * collected from all inheritance children as well as the specified table.
1336 * We fail and return zero if there are no inheritance children, or if all
1337 * children are foreign tables that don't support ANALYZE.
1338 */
1339 static int
1343 {
1350 nrels,
1351 i;
1355 /* Initialize output parameters to zero now, in case we exit early */
1359 /*
1360 * Find all members of inheritance set. We only need AccessShareLock on
1361 * the children.
1362 */
1363 tableOIDs =
1366 /*
1367 * Check that there's at least one descendant, else fail. This could
1368 * happen despite analyze_rel's relhassubclass check, if table once had a
1369 * child but no longer does. In that case, we can clear the
1370 * relhassubclass field so as not to make the same mistake again later.
1371 * (This is safe because we hold ShareUpdateExclusiveLock.)
1372 */
1374 {
1375 /* CCI because we already updated the pg_class row in this command */
1379 (errmsg("skipping analyze of \"%s.%s\" inheritance tree --- this inheritance tree contains no child tables",
1383 }
1385 /*
1386 * Identify acquirefuncs to use, and count blocks in all the relations.
1387 * The result could overflow BlockNumber, so we use double arithmetic.
1388 */
1397 {
1399 Relation childrel;
1403 /* We already got the needed lock */
1406 /* Ignore if temp table of another backend */
1408 {
1409 /* ... but release the lock on it */
1413 }
1415 /* Check table type (MATVIEW can't happen, but might as well allow) */
1418 {
1419 /* Regular table, so use the regular row acquisition function */
1422 }
1424 {
1425 /*
1426 * For a foreign table, call the FDW's hook function to see
1427 * whether it supports analysis.
1428 */
1440 {
1441 /* ignore, but release the lock on it */
1445 }
1446 }
1447 else
1448 {
1449 /*
1450 * ignore, but release the lock on it. don't try to unlock the
1451 * passed-in relation
1452 */
1456 else
1459 }
1461 /* OK, we'll process this child */
1467 nrels++;
1468 }
1470 /*
1471 * If we don't have at least one child table to consider, fail. If the
1472 * relation is a partitioned table, it's not counted as a child table.
1473 */
1475 {
1477 (errmsg("skipping analyze of \"%s.%s\" inheritance tree --- this inheritance tree contains no analyzable child tables",
1481 }
1483 /*
1484 * Now sample rows from each relation, proportionally to its fraction of
1485 * the total block count. (This might be less than desirable if the child
1486 * rels have radically different free-space percentages, but it's not
1487 * clear that it's worth working harder.)
1488 */
1490 nrels);
1493 {
1498 /*
1499 * Report progress. The sampling function will normally report blocks
1500 * done/total, but we need to reset them to 0 here, so that they don't
1501 * show an old value until that.
1502 */
1503 {
1505 PROGRESS_ANALYZE_CURRENT_CHILD_TABLE_RELID,
1506 PROGRESS_ANALYZE_BLOCKS_DONE,
1507 PROGRESS_ANALYZE_BLOCKS_TOTAL
1508 };
1513 };
1516 }
1519 {
1523 /* Make sure we don't overrun due to roundoff error */
1526 {
1529 tdrows;
1531 /* Fetch a random sample of the child's rows */
1536 /* We may need to convert from child's rowtype to parent's */
1540 {
1546 {
1550 {
1551 HeapTuple newtup;
1556 }
1558 }
1559 }
1561 /* And add to counts */
1565 }
1566 }
1568 /*
1569 * Note: we cannot release the child-table locks, since we may have
1570 * pointers to their TOAST tables in the sampled rows.
1571 */
1575 }
1578 }
1581 /*
1582 * update_attstats() -- update attribute statistics for one relation
1583 *
1584 * Statistics are stored in several places: the pg_class row for the
1585 * relation has stats about the whole relation, and there is a
1586 * pg_statistic row for each (non-system) attribute that has ever
1587 * been analyzed. The pg_class values are updated by VACUUM, not here.
1588 *
1589 * pg_statistic rows are just added or updated normally. This means
1590 * that pg_statistic will probably contain some deleted rows at the
1591 * completion of a vacuum cycle, unless it happens to get vacuumed last.
1592 *
1593 * To keep things simple, we punt for pg_statistic, and don't try
1594 * to compute or store rows for pg_statistic itself in pg_statistic.
1595 * This could possibly be made to work, but it's not worth the trouble.
1596 * Note analyze_rel() has seen to it that we won't come here when
1597 * vacuuming pg_statistic itself.
1598 *
1599 * Note: there would be a race condition here if two backends could
1600 * ANALYZE the same table concurrently. Presently, we lock that out
1601 * by taking a self-exclusive lock on the relation in analyze_rel().
1602 */
1603 static void
1605 {
1606 Relation sd;
1616 {
1618 HeapTuple stup,
1619 oldtup;
1621 k,
1622 n;
1627 /* Ignore attr if we weren't able to collect stats */
1631 /*
1632 * Construct a new pg_statistic tuple
1633 */
1635 {
1638 }
1648 {
1650 }
1653 {
1655 }
1658 {
1660 }
1663 {
1667 {
1675 }
1676 else
1677 {
1680 }
1681 }
1684 {
1686 {
1696 }
1697 else
1698 {
1701 }
1702 }
1704 /* Is there already a pg_statistic tuple for this attribute? */
1710 /* Open index information when we know we need it */
1715 {
1716 /* Yes, replace it */
1719 values,
1720 nulls,
1721 replaces);
1724 }
1725 else
1726 {
1727 /* No, insert new tuple */
1730 }
1733 }
1738 }
1740 /*
1741 * Standard fetch function for use by compute_stats subroutines.
1742 *
1743 * This exists to provide some insulation between compute_stats routines
1744 * and the actual storage of the sample data.
1745 */
1746 static Datum
1748 {
1754 }
1756 /*
1757 * Fetch function for analyzing index expressions.
1758 *
1759 * We have not bothered to construct index tuples, instead the data is
1760 * just in Datum arrays.
1761 */
1762 static Datum
1764 {
1767 /* exprvals and exprnulls are already offset for proper column */
1771 }
1774 /*==========================================================================
1775 *
1776 * Code below this point represents the "standard" type-specific statistics
1777 * analysis algorithms. This code can be replaced on a per-data-type basis
1778 * by setting a nonzero value in pg_type.typanalyze.
1779 *
1780 *==========================================================================
1781 */
1784 /*
1785 * To avoid consuming too much memory during analysis and/or too much space
1786 * in the resulting pg_statistic rows, we ignore varlena datums that are wider
1787 * than WIDTH_THRESHOLD (after detoasting!). This is legitimate for MCV
1788 * and distinct-value calculations since a wide value is unlikely to be
1789 * duplicated at all, much less be a most-common value. For the same reason,
1790 * ignoring wide values will not affect our estimates of histogram bin
1791 * boundaries very much.
1792 */
1793 #define WIDTH_THRESHOLD 1024
1795 #define swapInt(a,b) do {int _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1796 #define swapDatum(a,b) do {Datum _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1798 /*
1799 * Extra information used by the default analysis routines
1800 */
1802 {
1808 {
1809 SortSupport ssup;
1815 AnalyzeAttrFetchFunc fetchfunc,
1819 AnalyzeAttrFetchFunc fetchfunc,
1823 AnalyzeAttrFetchFunc fetchfunc,
1836 /*
1837 * std_typanalyze -- the default type-specific typanalyze function
1838 */
1839 bool
1841 {
1842 Oid ltopr;
1843 Oid eqopr;
1846 /* If the attstattarget column is negative, use the default value */
1850 /* Look for default "<" and "=" operators for column's type */
1854 NULL);
1856 /* Save the operator info for compute_stats routines */
1863 /*
1864 * Determine which standard statistics algorithm to use
1865 */
1867 {
1868 /* Seems to be a scalar datatype */
1870 /*--------------------
1871 * The following choice of minrows is based on the paper
1872 * "Random sampling for histogram construction: how much is enough?"
1873 * by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in
1874 * Proceedings of ACM SIGMOD International Conference on Management
1875 * of Data, 1998, Pages 436-447. Their Corollary 1 to Theorem 5
1876 * says that for table size n, histogram size k, maximum relative
1877 * error in bin size f, and error probability gamma, the minimum
1878 * random sample size is
1879 * r = 4 * k * ln(2*n/gamma) / f^2
1880 * Taking f = 0.5, gamma = 0.01, n = 10^6 rows, we obtain
1881 * r = 305.82 * k
1882 * Note that because of the log function, the dependence on n is
1883 * quite weak; even at n = 10^12, a 300*k sample gives <= 0.66
1884 * bin size error with probability 0.99. So there's no real need to
1885 * scale for n, which is a good thing because we don't necessarily
1886 * know it at this point.
1887 *--------------------
1888 */
1890 }
1892 {
1893 /* We can still recognize distinct values */
1895 /* Might as well use the same minrows as above */
1897 }
1898 else
1899 {
1900 /* Can't do much but the trivial stuff */
1902 /* Might as well use the same minrows as above */
1904 }
1907 }
1910 /*
1911 * compute_trivial_stats() -- compute very basic column statistics
1912 *
1913 * We use this when we cannot find a hash "=" operator for the datatype.
1914 *
1915 * We determine the fraction of non-null rows and the average datum width.
1916 */
1917 static void
1919 AnalyzeAttrFetchFunc fetchfunc,
1922 {
1933 {
1934 Datum value;
1941 /* Check for null/nonnull */
1943 {
1944 null_cnt++;
1946 }
1947 nonnull_cnt++;
1949 /*
1950 * If it's a variable-width field, add up widths for average width
1951 * calculation. Note that if the value is toasted, we use the toasted
1952 * width. We don't bother with this calculation if it's a fixed-width
1953 * type.
1954 */
1956 {
1958 }
1960 {
1961 /* must be cstring */
1963 }
1964 }
1966 /* We can only compute average width if we found some non-null values. */
1968 {
1970 /* Do the simple null-frac and width stats */
1974 else
1977 }
1979 {
1980 /* We found only nulls; assume the column is entirely null */
1985 else
1988 }
1989 }
1992 /*
1993 * compute_distinct_stats() -- compute column statistics including ndistinct
1994 *
1995 * We use this when we can find only an "=" operator for the datatype.
1996 *
1997 * We determine the fraction of non-null rows, the average width, the
1998 * most common values, and the (estimated) number of distinct values.
1999 *
2000 * The most common values are determined by brute force: we keep a list
2001 * of previously seen values, ordered by number of times seen, as we scan
2002 * the samples. A newly seen value is inserted just after the last
2003 * multiply-seen value, causing the bottommost (oldest) singly-seen value
2004 * to drop off the list. The accuracy of this method, and also its cost,
2005 * depend mainly on the length of the list we are willing to keep.
2006 */
2007 static void
2009 AnalyzeAttrFetchFunc fetchfunc,
2012 {
2022 FmgrInfo f_cmpeq;
2024 {
2025 Datum value;
2030 track_max;
2034 /*
2035 * We track up to 2*n values for an n-element MCV list; but at least 10
2036 */
2046 {
2047 Datum value;
2051 j;
2057 /* Check for null/nonnull */
2059 {
2060 null_cnt++;
2062 }
2063 nonnull_cnt++;
2065 /*
2066 * If it's a variable-width field, add up widths for average width
2067 * calculation. Note that if the value is toasted, we use the toasted
2068 * width. We don't bother with this calculation if it's a fixed-width
2069 * type.
2070 */
2072 {
2075 /*
2076 * If the value is toasted, we want to detoast it just once to
2077 * avoid repeated detoastings and resultant excess memory usage
2078 * during the comparisons. Also, check to see if the value is
2079 * excessively wide, and if so don't detoast at all --- just
2080 * ignore the value.
2081 */
2083 {
2084 toowide_cnt++;
2086 }
2088 }
2090 {
2091 /* must be cstring */
2093 }
2095 /*
2096 * See if the value matches anything we're already tracking.
2097 */
2101 {
2105 {
2108 }
2111 }
2114 {
2115 /* Found a match */
2117 /* This value may now need to "bubble up" in the track list */
2119 {
2122 j--;
2123 }
2124 }
2125 else
2126 {
2127 /* No match. Insert at head of count-1 list */
2129 track_cnt++;
2131 {
2134 }
2136 {
2139 }
2140 }
2141 }
2143 /* We can only compute real stats if we found some non-null values. */
2145 {
2147 summultiple;
2150 /* Do the simple null-frac and width stats */
2154 else
2157 /* Count the number of values we found multiple times */
2160 {
2164 }
2167 {
2168 /*
2169 * If we found no repeated non-null values, assume it's a unique
2170 * column; but be sure to discount for any nulls we found.
2171 */
2173 }
2176 {
2177 /*
2178 * Our track list includes every value in the sample, and every
2179 * value appeared more than once. Assume the column has just
2180 * these values. (This case is meant to address columns with
2181 * small, fixed sets of possible values, such as boolean or enum
2182 * columns. If there are any values that appear just once in the
2183 * sample, including too-wide values, we should assume that that's
2184 * not what we're dealing with.)
2185 */
2187 }
2188 else
2189 {
2190 /*----------
2191 * Estimate the number of distinct values using the estimator
2192 * proposed by Haas and Stokes in IBM Research Report RJ 10025:
2193 * n*d / (n - f1 + f1*n/N)
2194 * where f1 is the number of distinct values that occurred
2195 * exactly once in our sample of n rows (from a total of N),
2196 * and d is the total number of distinct values in the sample.
2197 * This is their Duj1 estimator; the other estimators they
2198 * recommend are considerably more complex, and are numerically
2199 * very unstable when n is much smaller than N.
2200 *
2201 * In this calculation, we consider only non-nulls. We used to
2202 * include rows with null values in the n and N counts, but that
2203 * leads to inaccurate answers in columns with many nulls, and
2204 * it's intuitively bogus anyway considering the desired result is
2205 * the number of distinct non-null values.
2206 *
2207 * We assume (not very reliably!) that all the multiply-occurring
2208 * values are reflected in the final track[] list, and the other
2209 * nonnull values all appeared but once. (XXX this usually
2210 * results in a drastic overestimate of ndistinct. Can we do
2211 * any better?)
2212 *----------
2213 */
2220 /* N == 0 shouldn't happen, but just in case ... */
2223 else
2226 /* Clamp to sane range in case of roundoff error */
2231 /* And round to integer */
2233 }
2235 /*
2236 * If we estimated the number of distinct values at more than 10% of
2237 * the total row count (a very arbitrary limit), then assume that
2238 * stadistinct should scale with the row count rather than be a fixed
2239 * value.
2240 */
2244 /*
2245 * Decide how many values are worth storing as most-common values. If
2246 * we are able to generate a complete MCV list (all the values in the
2247 * sample will fit, and we think these are all the ones in the table),
2248 * then do so. Otherwise, store only those values that are
2249 * significantly more common than the values not in the list.
2250 *
2251 * Note: the first of these cases is meant to address columns with
2252 * small, fixed sets of possible values, such as boolean or enum
2253 * columns. If we can *completely* represent the column population by
2254 * an MCV list that will fit into the stats target, then we should do
2255 * so and thus provide the planner with complete information. But if
2256 * the MCV list is not complete, it's generally worth being more
2257 * selective, and not just filling it all the way up to the stats
2258 * target.
2259 */
2263 {
2264 /* Track list includes all values seen, and all will fit */
2266 }
2267 else
2268 {
2271 /* Incomplete list; decide how many values are worth keeping */
2276 {
2285 }
2286 }
2288 /* Generate MCV slot entry */
2290 {
2291 MemoryContext old_context;
2295 /* Must copy the target values into anl_context */
2300 {
2305 }
2316 /*
2317 * Accept the defaults for stats->statypid and others. They have
2318 * been set before we were called (see vacuum.h)
2319 */
2320 }
2321 }
2323 {
2324 /* We found only nulls; assume the column is entirely null */
2329 else
2332 }
2334 /* We don't need to bother cleaning up any of our temporary palloc's */
2335 }
2338 /*
2339 * compute_scalar_stats() -- compute column statistics
2340 *
2341 * We use this when we can find "=" and "<" operators for the datatype.
2342 *
2343 * We determine the fraction of non-null rows, the average width, the
2344 * most common values, the (estimated) number of distinct values, the
2345 * distribution histogram, and the correlation of physical to logical order.
2346 *
2347 * The desired stats can be determined fairly easily after sorting the
2348 * data values into order.
2349 */
2350 static void
2352 AnalyzeAttrFetchFunc fetchfunc,
2355 {
2366 SortSupportData ssup;
2385 /*
2386 * For now, don't perform abbreviated key conversion, because full values
2387 * are required for MCV slot generation. Supporting that optimization
2388 * would necessitate teaching compare_scalars() to call a tie-breaker.
2389 */
2394 /* Initial scan to find sortable values */
2396 {
2397 Datum value;
2404 /* Check for null/nonnull */
2406 {
2407 null_cnt++;
2409 }
2410 nonnull_cnt++;
2412 /*
2413 * If it's a variable-width field, add up widths for average width
2414 * calculation. Note that if the value is toasted, we use the toasted
2415 * width. We don't bother with this calculation if it's a fixed-width
2416 * type.
2417 */
2419 {
2422 /*
2423 * If the value is toasted, we want to detoast it just once to
2424 * avoid repeated detoastings and resultant excess memory usage
2425 * during the comparisons. Also, check to see if the value is
2426 * excessively wide, and if so don't detoast at all --- just
2427 * ignore the value.
2428 */
2430 {
2431 toowide_cnt++;
2433 }
2435 }
2437 {
2438 /* must be cstring */
2440 }
2442 /* Add it to the list to be sorted */
2446 values_cnt++;
2447 }
2449 /* We can only compute real stats if we found some sortable values. */
2451 {
2454 num_hist,
2455 dups_cnt;
2457 CompareScalarsContext cxt;
2459 /* Sort the collected values */
2465 /*
2466 * Now scan the values in order, find the most common ones, and also
2467 * accumulate ordering-correlation statistics.
2468 *
2469 * To determine which are most common, we first have to count the
2470 * number of duplicates of each value. The duplicates are adjacent in
2471 * the sorted list, so a brute-force approach is to compare successive
2472 * datum values until we find two that are not equal. However, that
2473 * requires N-1 invocations of the datum comparison routine, which are
2474 * completely redundant with work that was done during the sort. (The
2475 * sort algorithm must at some point have compared each pair of items
2476 * that are adjacent in the sorted order; otherwise it could not know
2477 * that it's ordered the pair correctly.) We exploit this by having
2478 * compare_scalars remember the highest tupno index that each
2479 * ScalarItem has been found equal to. At the end of the sort, a
2480 * ScalarItem's tupnoLink will still point to itself if and only if it
2481 * is the last item of its group of duplicates (since the group will
2482 * be ordered by tupno).
2483 */
2489 {
2493 dups_cnt++;
2495 {
2496 /* Reached end of duplicates of this value */
2497 ndistinct++;
2499 {
2500 nmultiple++;
2503 {
2504 /*
2505 * Found a new item for the mcv list; find its
2506 * position, bubbling down old items if needed. Loop
2507 * invariant is that j points at an empty/ replaceable
2508 * slot.
2509 */
2513 track_cnt++;
2515 {
2520 }
2523 }
2524 }
2526 }
2527 }
2530 /* Do the simple null-frac and width stats */
2534 else
2538 {
2539 /*
2540 * If we found no repeated non-null values, assume it's a unique
2541 * column; but be sure to discount for any nulls we found.
2542 */
2544 }
2546 {
2547 /*
2548 * Every value in the sample appeared more than once. Assume the
2549 * column has just these values. (This case is meant to address
2550 * columns with small, fixed sets of possible values, such as
2551 * boolean or enum columns. If there are any values that appear
2552 * just once in the sample, including too-wide values, we should
2553 * assume that that's not what we're dealing with.)
2554 */
2556 }
2557 else
2558 {
2559 /*----------
2560 * Estimate the number of distinct values using the estimator
2561 * proposed by Haas and Stokes in IBM Research Report RJ 10025:
2562 * n*d / (n - f1 + f1*n/N)
2563 * where f1 is the number of distinct values that occurred
2564 * exactly once in our sample of n rows (from a total of N),
2565 * and d is the total number of distinct values in the sample.
2566 * This is their Duj1 estimator; the other estimators they
2567 * recommend are considerably more complex, and are numerically
2568 * very unstable when n is much smaller than N.
2569 *
2570 * In this calculation, we consider only non-nulls. We used to
2571 * include rows with null values in the n and N counts, but that
2572 * leads to inaccurate answers in columns with many nulls, and
2573 * it's intuitively bogus anyway considering the desired result is
2574 * the number of distinct non-null values.
2575 *
2576 * Overwidth values are assumed to have been distinct.
2577 *----------
2578 */
2585 /* N == 0 shouldn't happen, but just in case ... */
2588 else
2591 /* Clamp to sane range in case of roundoff error */
2596 /* And round to integer */
2598 }
2600 /*
2601 * If we estimated the number of distinct values at more than 10% of
2602 * the total row count (a very arbitrary limit), then assume that
2603 * stadistinct should scale with the row count rather than be a fixed
2604 * value.
2605 */
2609 /*
2610 * Decide how many values are worth storing as most-common values. If
2611 * we are able to generate a complete MCV list (all the values in the
2612 * sample will fit, and we think these are all the ones in the table),
2613 * then do so. Otherwise, store only those values that are
2614 * significantly more common than the values not in the list.
2615 *
2616 * Note: the first of these cases is meant to address columns with
2617 * small, fixed sets of possible values, such as boolean or enum
2618 * columns. If we can *completely* represent the column population by
2619 * an MCV list that will fit into the stats target, then we should do
2620 * so and thus provide the planner with complete information. But if
2621 * the MCV list is not complete, it's generally worth being more
2622 * selective, and not just filling it all the way up to the stats
2623 * target.
2624 */
2628 {
2629 /* Track list includes all values seen, and all will fit */
2631 }
2632 else
2633 {
2636 /* Incomplete list; decide how many values are worth keeping */
2641 {
2650 }
2651 }
2653 /* Generate MCV slot entry */
2655 {
2656 MemoryContext old_context;
2660 /* Must copy the target values into anl_context */
2665 {
2670 }
2681 /*
2682 * Accept the defaults for stats->statypid and others. They have
2683 * been set before we were called (see vacuum.h)
2684 */
2685 slot_idx++;
2686 }
2688 /*
2689 * Generate a histogram slot entry if there are at least two distinct
2690 * values not accounted for in the MCV list. (This ensures the
2691 * histogram won't collapse to empty or a singleton.)
2692 */
2697 {
2698 MemoryContext old_context;
2702 posfrac,
2703 delta,
2704 deltafrac;
2706 /* Sort the MCV items into position order to speed next loop */
2710 /*
2711 * Collapse out the MCV items from the values[] array.
2712 *
2713 * Note we destroy the values[] array here... but we don't need it
2714 * for anything more. We do, however, still need values_cnt.
2715 * nvals will be the number of remaining entries in values[].
2716 */
2718 {
2720 dest;
2726 {
2730 {
2734 {
2735 /* advance past this MCV item */
2737 j++;
2739 }
2741 }
2742 else
2748 }
2750 }
2751 else
2755 /* Must copy the target values into anl_context */
2759 /*
2760 * The object of this loop is to copy the first and last values[]
2761 * entries along with evenly-spaced values in between. So the
2762 * i'th value is values[(i * (nvals - 1)) / (num_hist - 1)]. But
2763 * computing that subscript directly risks integer overflow when
2764 * the stats target is more than a couple thousand. Instead we
2765 * add (nvals - 1) / (num_hist - 1) to pos at each step, tracking
2766 * the integral and fractional parts of the sum separately.
2767 */
2773 {
2780 {
2781 /* fractional part exceeds 1, carry to integer part */
2782 pos++;
2784 }
2785 }
2795 /*
2796 * Accept the defaults for stats->statypid and others. They have
2797 * been set before we were called (see vacuum.h)
2798 */
2799 slot_idx++;
2800 }
2802 /* Generate a correlation entry if there are multiple values */
2804 {
2805 MemoryContext old_context;
2808 corr_x2sum;
2810 /* Must copy the target values into anl_context */
2815 /*----------
2816 * Since we know the x and y value sets are both
2817 * 0, 1, ..., values_cnt-1
2818 * we have sum(x) = sum(y) =
2819 * (values_cnt-1)*values_cnt / 2
2820 * and sum(x^2) = sum(y^2) =
2821 * (values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
2822 *----------
2823 */
2829 /* And the correlation coefficient reduces to */
2838 slot_idx++;
2839 }
2840 }
2842 {
2843 /* We found some non-null values, but they were all too wide */
2846 /* Do the simple null-frac and width stats */
2850 else
2852 /* Assume all too-wide values are distinct, so it's a unique column */
2854 }
2856 {
2857 /* We found only nulls; assume the column is entirely null */
2862 else
2865 }
2867 /* We don't need to bother cleaning up any of our temporary palloc's */
2868 }
2870 /*
2871 * Comparator for sorting ScalarItems
2872 *
2873 * Aside from sorting the items, we update the tupnoLink[] array
2874 * whenever two ScalarItems are found to contain equal datums. The array
2875 * is indexed by tupno; for each ScalarItem, it contains the highest
2876 * tupno that that item's datum has been found to be equal to. This allows
2877 * us to avoid additional comparisons in compute_scalar_stats().
2878 */
2879 static int
2881 {
2893 /*
2894 * The two datums are equal, so update cxt->tupnoLink[].
2895 */
2901 /*
2902 * For equal datums, sort by tupno
2903 */
2905 }
2907 /*
2908 * Comparator for sorting ScalarMCVItems by position
2909 */
2910 static int
2912 {
2917 }
2919 /*
2920 * Analyze the list of common values in the sample and decide how many are
2921 * worth storing in the table's MCV list.
2922 *
2923 * mcv_counts is assumed to be a list of the counts of the most common values
2924 * seen in the sample, starting with the most common. The return value is the
2925 * number that are significantly more common than the values not in the list,
2926 * and which are therefore deemed worth storing in the table's MCV list.
2927 */
2928 static int
2935 {
2940 /*
2941 * If the entire table was sampled, keep the whole list. This also
2942 * protects us against division by zero in the code below.
2943 */
2947 /* Re-extract the estimated number of distinct nonnull values in table */
2952 /*
2953 * Exclude the least common values from the MCV list, if they are not
2954 * significantly more common than the estimated selectivity they would
2955 * have if they weren't in the list. All non-MCV values are assumed to be
2956 * equally common, after taking into account the frequencies of all the
2957 * values in the MCV list and the number of nulls (c.f. eqsel()).
2958 *
2959 * Here sumcount tracks the total count of all but the last (least common)
2960 * value in the MCV list, allowing us to determine the effect of excluding
2961 * that value from the list.
2962 *
2963 * Note that we deliberately do this by removing values from the full
2964 * list, rather than starting with an empty list and adding values,
2965 * because the latter approach can fail to add any values if all the most
2966 * common values have around the same frequency and make up the majority
2967 * of the table, so that the overall average frequency of all values is
2968 * roughly the same as that of the common values. This would lead to any
2969 * uncommon values being significantly overestimated.
2970 */
2976 {
2978 otherdistinct,
2979 N,
2980 n,
2981 K,
2982 variance,
2983 stddev;
2985 /*
2986 * Estimated selectivity the least common value would have if it
2987 * wasn't in the MCV list (c.f. eqsel()).
2988 */
2998 /*
2999 * If the value is kept in the MCV list, its population frequency is
3000 * assumed to equal its sample frequency. We use the lower end of a
3001 * textbook continuity-corrected Wald-type confidence interval to
3002 * determine if that is significantly more common than the non-MCV
3003 * frequency --- specifically we assume the population frequency is
3004 * highly likely to be within around 2 standard errors of the sample
3005 * frequency, which equates to an interval of 2 standard deviations
3006 * either side of the sample count, plus an additional 0.5 for the
3007 * continuity correction. Since we are sampling without replacement,
3008 * this is a hypergeometric distribution.
3009 *
3010 * XXX: Empirically, this approach seems to work quite well, but it
3011 * may be worth considering more advanced techniques for estimating
3012 * the confidence interval of the hypergeometric distribution.
3013 */
3021 {
3022 /*
3023 * The value is significantly more common than the non-MCV
3024 * selectivity would suggest. Keep it, and all the other more
3025 * common values in the list.
3026 */
3028 }
3029 else
3030 {
3031 /* Discard this value and consider the next least common value */
3032 num_mcv--;
3036 }
3037 }
3039 }