Line data Source code
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 : */
15 : #include "postgres.h"
16 :
17 : #include <math.h>
18 :
19 : #include "access/detoast.h"
20 : #include "access/genam.h"
21 : #include "access/multixact.h"
22 : #include "access/relation.h"
23 : #include "access/table.h"
24 : #include "access/tableam.h"
25 : #include "access/transam.h"
26 : #include "access/tupconvert.h"
27 : #include "access/visibilitymap.h"
28 : #include "access/xact.h"
29 : #include "catalog/index.h"
30 : #include "catalog/indexing.h"
31 : #include "catalog/pg_inherits.h"
32 : #include "commands/dbcommands.h"
33 : #include "commands/progress.h"
34 : #include "commands/tablecmds.h"
35 : #include "commands/vacuum.h"
36 : #include "common/pg_prng.h"
37 : #include "executor/executor.h"
38 : #include "foreign/fdwapi.h"
39 : #include "miscadmin.h"
40 : #include "nodes/nodeFuncs.h"
41 : #include "parser/parse_oper.h"
42 : #include "parser/parse_relation.h"
43 : #include "pgstat.h"
44 : #include "statistics/extended_stats_internal.h"
45 : #include "statistics/statistics.h"
46 : #include "storage/bufmgr.h"
47 : #include "storage/procarray.h"
48 : #include "utils/attoptcache.h"
49 : #include "utils/datum.h"
50 : #include "utils/guc.h"
51 : #include "utils/lsyscache.h"
52 : #include "utils/memutils.h"
53 : #include "utils/pg_rusage.h"
54 : #include "utils/sampling.h"
55 : #include "utils/sortsupport.h"
56 : #include "utils/syscache.h"
57 : #include "utils/timestamp.h"
58 :
59 :
60 : /* Per-index data for ANALYZE */
61 : typedef struct AnlIndexData
62 : {
63 : IndexInfo *indexInfo; /* BuildIndexInfo result */
64 : double tupleFract; /* fraction of rows for partial index */
65 : VacAttrStats **vacattrstats; /* index attrs to analyze */
66 : int attr_cnt;
67 : } AnlIndexData;
68 :
69 :
70 : /* Default statistics target (GUC parameter) */
71 : int default_statistics_target = 100;
72 :
73 : /* A few variables that don't seem worth passing around as parameters */
74 : static MemoryContext anl_context = NULL;
75 : static BufferAccessStrategy vac_strategy;
76 :
77 :
78 : static void do_analyze_rel(Relation onerel,
79 : VacuumParams *params, List *va_cols,
80 : AcquireSampleRowsFunc acquirefunc, BlockNumber relpages,
81 : bool inh, bool in_outer_xact, int elevel);
82 : static void compute_index_stats(Relation onerel, double totalrows,
83 : AnlIndexData *indexdata, int nindexes,
84 : HeapTuple *rows, int numrows,
85 : MemoryContext col_context);
86 : static VacAttrStats *examine_attribute(Relation onerel, int attnum,
87 : Node *index_expr);
88 : static int acquire_sample_rows(Relation onerel, int elevel,
89 : HeapTuple *rows, int targrows,
90 : double *totalrows, double *totaldeadrows);
91 : static int compare_rows(const void *a, const void *b, void *arg);
92 : static int acquire_inherited_sample_rows(Relation onerel, int elevel,
93 : HeapTuple *rows, int targrows,
94 : double *totalrows, double *totaldeadrows);
95 : static void update_attstats(Oid relid, bool inh,
96 : int natts, VacAttrStats **vacattrstats);
97 : static Datum std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
98 : static Datum ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
99 :
100 :
101 : /*
102 : * analyze_rel() -- analyze one relation
103 : *
104 : * relid identifies the relation to analyze. If relation is supplied, use
105 : * the name therein for reporting any failure to open/lock the rel; do not
106 : * use it once we've successfully opened the rel, since it might be stale.
107 : */
108 : void
109 13610 : analyze_rel(Oid relid, RangeVar *relation,
110 : VacuumParams *params, List *va_cols, bool in_outer_xact,
111 : BufferAccessStrategy bstrategy)
112 : {
113 : Relation onerel;
114 : int elevel;
115 13610 : AcquireSampleRowsFunc acquirefunc = NULL;
116 13610 : BlockNumber relpages = 0;
117 :
118 : /* Select logging level */
119 13610 : if (params->options & VACOPT_VERBOSE)
120 0 : elevel = INFO;
121 : else
122 13610 : elevel = DEBUG2;
123 :
124 : /* Set up static variables */
125 13610 : vac_strategy = bstrategy;
126 :
127 : /*
128 : * Check for user-requested abort.
129 : */
130 13610 : CHECK_FOR_INTERRUPTS();
131 :
132 : /*
133 : * Open the relation, getting ShareUpdateExclusiveLock to ensure that two
134 : * ANALYZEs don't run on it concurrently. (This also locks out a
135 : * concurrent VACUUM, which doesn't matter much at the moment but might
136 : * matter if we ever try to accumulate stats on dead tuples.) If the rel
137 : * has been dropped since we last saw it, we don't need to process it.
138 : *
139 : * Make sure to generate only logs for ANALYZE in this case.
140 : */
141 13610 : onerel = vacuum_open_relation(relid, relation, params->options & ~(VACOPT_VACUUM),
142 13610 : params->log_min_duration >= 0,
143 : ShareUpdateExclusiveLock);
144 :
145 : /* leave if relation could not be opened or locked */
146 13610 : if (!onerel)
147 180 : return;
148 :
149 : /*
150 : * Check if relation needs to be skipped based on privileges. This check
151 : * happens also when building the relation list to analyze for a manual
152 : * operation, and needs to be done additionally here as ANALYZE could
153 : * happen across multiple transactions where privileges could have changed
154 : * in-between. Make sure to generate only logs for ANALYZE in this case.
155 : */
156 13602 : if (!vacuum_is_permitted_for_relation(RelationGetRelid(onerel),
157 : onerel->rd_rel,
158 13602 : params->options & ~VACOPT_VACUUM))
159 : {
160 36 : relation_close(onerel, ShareUpdateExclusiveLock);
161 36 : return;
162 : }
163 :
164 : /*
165 : * Silently ignore tables that are temp tables of other backends ---
166 : * trying to analyze these is rather pointless, since their contents are
167 : * probably not up-to-date on disk. (We don't throw a warning here; it
168 : * would just lead to chatter during a database-wide ANALYZE.)
169 : */
170 13566 : if (RELATION_IS_OTHER_TEMP(onerel))
171 : {
172 0 : relation_close(onerel, ShareUpdateExclusiveLock);
173 0 : return;
174 : }
175 :
176 : /*
177 : * We can ANALYZE any table except pg_statistic. See update_attstats
178 : */
179 13566 : if (RelationGetRelid(onerel) == StatisticRelationId)
180 : {
181 136 : relation_close(onerel, ShareUpdateExclusiveLock);
182 136 : return;
183 : }
184 :
185 : /*
186 : * Check that it's of an analyzable relkind, and set up appropriately.
187 : */
188 13430 : if (onerel->rd_rel->relkind == RELKIND_RELATION ||
189 760 : onerel->rd_rel->relkind == RELKIND_MATVIEW)
190 : {
191 : /* Regular table, so we'll use the regular row acquisition function */
192 12670 : acquirefunc = acquire_sample_rows;
193 : /* Also get regular table's size */
194 12670 : relpages = RelationGetNumberOfBlocks(onerel);
195 : }
196 760 : else if (onerel->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
197 : {
198 : /*
199 : * For a foreign table, call the FDW's hook function to see whether it
200 : * supports analysis.
201 : */
202 : FdwRoutine *fdwroutine;
203 56 : bool ok = false;
204 :
205 56 : fdwroutine = GetFdwRoutineForRelation(onerel, false);
206 :
207 56 : if (fdwroutine->AnalyzeForeignTable != NULL)
208 56 : ok = fdwroutine->AnalyzeForeignTable(onerel,
209 : &acquirefunc,
210 : &relpages);
211 :
212 56 : if (!ok)
213 : {
214 0 : ereport(WARNING,
215 : (errmsg("skipping \"%s\" --- cannot analyze this foreign table",
216 : RelationGetRelationName(onerel))));
217 0 : relation_close(onerel, ShareUpdateExclusiveLock);
218 0 : return;
219 : }
220 : }
221 704 : else if (onerel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
222 : {
223 : /*
224 : * For partitioned tables, we want to do the recursive ANALYZE below.
225 : */
226 : }
227 : else
228 : {
229 : /* No need for a WARNING if we already complained during VACUUM */
230 0 : if (!(params->options & VACOPT_VACUUM))
231 0 : ereport(WARNING,
232 : (errmsg("skipping \"%s\" --- cannot analyze non-tables or special system tables",
233 : RelationGetRelationName(onerel))));
234 0 : relation_close(onerel, ShareUpdateExclusiveLock);
235 0 : return;
236 : }
237 :
238 : /*
239 : * OK, let's do it. First, initialize progress reporting.
240 : */
241 13430 : pgstat_progress_start_command(PROGRESS_COMMAND_ANALYZE,
242 : RelationGetRelid(onerel));
243 :
244 : /*
245 : * Do the normal non-recursive ANALYZE. We can skip this for partitioned
246 : * tables, which don't contain any rows.
247 : */
248 13430 : if (onerel->rd_rel->relkind != RELKIND_PARTITIONED_TABLE)
249 12726 : do_analyze_rel(onerel, params, va_cols, acquirefunc,
250 : relpages, false, in_outer_xact, elevel);
251 :
252 : /*
253 : * If there are child tables, do recursive ANALYZE.
254 : */
255 13390 : if (onerel->rd_rel->relhassubclass)
256 810 : do_analyze_rel(onerel, params, va_cols, acquirefunc, relpages,
257 : true, in_outer_xact, elevel);
258 :
259 : /*
260 : * Close source relation now, but keep lock so that no one deletes it
261 : * before we commit. (If someone did, they'd fail to clean up the entries
262 : * we made in pg_statistic. Also, releasing the lock before commit would
263 : * expose us to concurrent-update failures in update_attstats.)
264 : */
265 13372 : relation_close(onerel, NoLock);
266 :
267 13372 : pgstat_progress_end_command();
268 : }
269 :
270 : /*
271 : * do_analyze_rel() -- analyze one relation, recursively or not
272 : *
273 : * Note that "acquirefunc" is only relevant for the non-inherited case.
274 : * For the inherited case, acquire_inherited_sample_rows() determines the
275 : * appropriate acquirefunc for each child table.
276 : */
277 : static void
278 13536 : do_analyze_rel(Relation onerel, VacuumParams *params,
279 : List *va_cols, AcquireSampleRowsFunc acquirefunc,
280 : BlockNumber relpages, bool inh, bool in_outer_xact,
281 : int elevel)
282 : {
283 : int attr_cnt,
284 : tcnt,
285 : i,
286 : ind;
287 : Relation *Irel;
288 : int nindexes;
289 : bool verbose,
290 : instrument,
291 : hasindex;
292 : VacAttrStats **vacattrstats;
293 : AnlIndexData *indexdata;
294 : int targrows,
295 : numrows,
296 : minrows;
297 : double totalrows,
298 : totaldeadrows;
299 : HeapTuple *rows;
300 : PGRUsage ru0;
301 13536 : TimestampTz starttime = 0;
302 : MemoryContext caller_context;
303 : Oid save_userid;
304 : int save_sec_context;
305 : int save_nestlevel;
306 13536 : WalUsage startwalusage = pgWalUsage;
307 13536 : BufferUsage startbufferusage = pgBufferUsage;
308 : BufferUsage bufferusage;
309 13536 : PgStat_Counter startreadtime = 0;
310 13536 : PgStat_Counter startwritetime = 0;
311 :
312 13536 : verbose = (params->options & VACOPT_VERBOSE) != 0;
313 13782 : instrument = (verbose || (AmAutoVacuumWorkerProcess() &&
314 246 : params->log_min_duration >= 0));
315 13536 : if (inh)
316 810 : ereport(elevel,
317 : (errmsg("analyzing \"%s.%s\" inheritance tree",
318 : get_namespace_name(RelationGetNamespace(onerel)),
319 : RelationGetRelationName(onerel))));
320 : else
321 12726 : ereport(elevel,
322 : (errmsg("analyzing \"%s.%s\"",
323 : get_namespace_name(RelationGetNamespace(onerel)),
324 : RelationGetRelationName(onerel))));
325 :
326 : /*
327 : * Set up a working context so that we can easily free whatever junk gets
328 : * created.
329 : */
330 13536 : anl_context = AllocSetContextCreate(CurrentMemoryContext,
331 : "Analyze",
332 : ALLOCSET_DEFAULT_SIZES);
333 13536 : caller_context = MemoryContextSwitchTo(anl_context);
334 :
335 : /*
336 : * Switch to the table owner's userid, so that any index functions are run
337 : * as that user. Also lock down security-restricted operations and
338 : * arrange to make GUC variable changes local to this command.
339 : */
340 13536 : GetUserIdAndSecContext(&save_userid, &save_sec_context);
341 13536 : SetUserIdAndSecContext(onerel->rd_rel->relowner,
342 : save_sec_context | SECURITY_RESTRICTED_OPERATION);
343 13536 : save_nestlevel = NewGUCNestLevel();
344 13536 : RestrictSearchPath();
345 :
346 : /*
347 : * measure elapsed time if called with verbose or if autovacuum logging
348 : * requires it
349 : */
350 13536 : if (instrument)
351 : {
352 246 : if (track_io_timing)
353 : {
354 0 : startreadtime = pgStatBlockReadTime;
355 0 : startwritetime = pgStatBlockWriteTime;
356 : }
357 :
358 246 : pg_rusage_init(&ru0);
359 246 : starttime = GetCurrentTimestamp();
360 : }
361 :
362 : /*
363 : * Determine which columns to analyze
364 : *
365 : * Note that system attributes are never analyzed, so we just reject them
366 : * at the lookup stage. We also reject duplicate column mentions. (We
367 : * could alternatively ignore duplicates, but analyzing a column twice
368 : * won't work; we'd end up making a conflicting update in pg_statistic.)
369 : */
370 13536 : if (va_cols != NIL)
371 : {
372 100 : Bitmapset *unique_cols = NULL;
373 : ListCell *le;
374 :
375 100 : vacattrstats = (VacAttrStats **) palloc(list_length(va_cols) *
376 : sizeof(VacAttrStats *));
377 100 : tcnt = 0;
378 182 : foreach(le, va_cols)
379 : {
380 132 : char *col = strVal(lfirst(le));
381 :
382 132 : i = attnameAttNum(onerel, col, false);
383 132 : if (i == InvalidAttrNumber)
384 38 : ereport(ERROR,
385 : (errcode(ERRCODE_UNDEFINED_COLUMN),
386 : errmsg("column \"%s\" of relation \"%s\" does not exist",
387 : col, RelationGetRelationName(onerel))));
388 94 : if (bms_is_member(i, unique_cols))
389 12 : ereport(ERROR,
390 : (errcode(ERRCODE_DUPLICATE_COLUMN),
391 : errmsg("column \"%s\" of relation \"%s\" appears more than once",
392 : col, RelationGetRelationName(onerel))));
393 82 : unique_cols = bms_add_member(unique_cols, i);
394 :
395 82 : vacattrstats[tcnt] = examine_attribute(onerel, i, NULL);
396 82 : if (vacattrstats[tcnt] != NULL)
397 82 : tcnt++;
398 : }
399 50 : attr_cnt = tcnt;
400 : }
401 : else
402 : {
403 13436 : attr_cnt = onerel->rd_att->natts;
404 : vacattrstats = (VacAttrStats **)
405 13436 : palloc(attr_cnt * sizeof(VacAttrStats *));
406 13436 : tcnt = 0;
407 108470 : for (i = 1; i <= attr_cnt; i++)
408 : {
409 95034 : vacattrstats[tcnt] = examine_attribute(onerel, i, NULL);
410 95034 : if (vacattrstats[tcnt] != NULL)
411 95022 : tcnt++;
412 : }
413 13436 : attr_cnt = tcnt;
414 : }
415 :
416 : /*
417 : * Open all indexes of the relation, and see if there are any analyzable
418 : * columns in the indexes. We do not analyze index columns if there was
419 : * an explicit column list in the ANALYZE command, however.
420 : *
421 : * If we are doing a recursive scan, we don't want to touch the parent's
422 : * indexes at all. If we're processing a partitioned table, we need to
423 : * know if there are any indexes, but we don't want to process them.
424 : */
425 13486 : if (onerel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
426 : {
427 686 : List *idxs = RelationGetIndexList(onerel);
428 :
429 686 : Irel = NULL;
430 686 : nindexes = 0;
431 686 : hasindex = idxs != NIL;
432 686 : list_free(idxs);
433 : }
434 12800 : else if (!inh)
435 : {
436 12694 : vac_open_indexes(onerel, AccessShareLock, &nindexes, &Irel);
437 12694 : hasindex = nindexes > 0;
438 : }
439 : else
440 : {
441 106 : Irel = NULL;
442 106 : nindexes = 0;
443 106 : hasindex = false;
444 : }
445 13486 : indexdata = NULL;
446 13486 : if (nindexes > 0)
447 : {
448 9750 : indexdata = (AnlIndexData *) palloc0(nindexes * sizeof(AnlIndexData));
449 28056 : for (ind = 0; ind < nindexes; ind++)
450 : {
451 18306 : AnlIndexData *thisdata = &indexdata[ind];
452 : IndexInfo *indexInfo;
453 :
454 18306 : thisdata->indexInfo = indexInfo = BuildIndexInfo(Irel[ind]);
455 18306 : thisdata->tupleFract = 1.0; /* fix later if partial */
456 18306 : if (indexInfo->ii_Expressions != NIL && va_cols == NIL)
457 : {
458 72 : ListCell *indexpr_item = list_head(indexInfo->ii_Expressions);
459 :
460 72 : thisdata->vacattrstats = (VacAttrStats **)
461 72 : palloc(indexInfo->ii_NumIndexAttrs * sizeof(VacAttrStats *));
462 72 : tcnt = 0;
463 144 : for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
464 : {
465 72 : int keycol = indexInfo->ii_IndexAttrNumbers[i];
466 :
467 72 : if (keycol == 0)
468 : {
469 : /* Found an index expression */
470 : Node *indexkey;
471 :
472 72 : if (indexpr_item == NULL) /* shouldn't happen */
473 0 : elog(ERROR, "too few entries in indexprs list");
474 72 : indexkey = (Node *) lfirst(indexpr_item);
475 72 : indexpr_item = lnext(indexInfo->ii_Expressions,
476 : indexpr_item);
477 144 : thisdata->vacattrstats[tcnt] =
478 72 : examine_attribute(Irel[ind], i + 1, indexkey);
479 72 : if (thisdata->vacattrstats[tcnt] != NULL)
480 72 : tcnt++;
481 : }
482 : }
483 72 : thisdata->attr_cnt = tcnt;
484 : }
485 : }
486 : }
487 :
488 : /*
489 : * Determine how many rows we need to sample, using the worst case from
490 : * all analyzable columns. We use a lower bound of 100 rows to avoid
491 : * possible overflow in Vitter's algorithm. (Note: that will also be the
492 : * target in the corner case where there are no analyzable columns.)
493 : */
494 13486 : targrows = 100;
495 108566 : for (i = 0; i < attr_cnt; i++)
496 : {
497 95080 : if (targrows < vacattrstats[i]->minrows)
498 13450 : targrows = vacattrstats[i]->minrows;
499 : }
500 31792 : for (ind = 0; ind < nindexes; ind++)
501 : {
502 18306 : AnlIndexData *thisdata = &indexdata[ind];
503 :
504 18378 : for (i = 0; i < thisdata->attr_cnt; i++)
505 : {
506 72 : if (targrows < thisdata->vacattrstats[i]->minrows)
507 0 : targrows = thisdata->vacattrstats[i]->minrows;
508 : }
509 : }
510 :
511 : /*
512 : * Look at extended statistics objects too, as those may define custom
513 : * statistics target. So we may need to sample more rows and then build
514 : * the statistics with enough detail.
515 : */
516 13486 : minrows = ComputeExtStatisticsRows(onerel, attr_cnt, vacattrstats);
517 :
518 13486 : if (targrows < minrows)
519 0 : targrows = minrows;
520 :
521 : /*
522 : * Acquire the sample rows
523 : */
524 13486 : rows = (HeapTuple *) palloc(targrows * sizeof(HeapTuple));
525 13486 : pgstat_progress_update_param(PROGRESS_ANALYZE_PHASE,
526 : inh ? PROGRESS_ANALYZE_PHASE_ACQUIRE_SAMPLE_ROWS_INH :
527 : PROGRESS_ANALYZE_PHASE_ACQUIRE_SAMPLE_ROWS);
528 13486 : if (inh)
529 792 : numrows = acquire_inherited_sample_rows(onerel, elevel,
530 : rows, targrows,
531 : &totalrows, &totaldeadrows);
532 : else
533 12694 : numrows = (*acquirefunc) (onerel, elevel,
534 : rows, targrows,
535 : &totalrows, &totaldeadrows);
536 :
537 : /*
538 : * Compute the statistics. Temporary results during the calculations for
539 : * each column are stored in a child context. The calc routines are
540 : * responsible to make sure that whatever they store into the VacAttrStats
541 : * structure is allocated in anl_context.
542 : */
543 13484 : if (numrows > 0)
544 : {
545 : MemoryContext col_context,
546 : old_context;
547 :
548 9198 : pgstat_progress_update_param(PROGRESS_ANALYZE_PHASE,
549 : PROGRESS_ANALYZE_PHASE_COMPUTE_STATS);
550 :
551 9198 : col_context = AllocSetContextCreate(anl_context,
552 : "Analyze Column",
553 : ALLOCSET_DEFAULT_SIZES);
554 9198 : old_context = MemoryContextSwitchTo(col_context);
555 :
556 79196 : for (i = 0; i < attr_cnt; i++)
557 : {
558 69998 : VacAttrStats *stats = vacattrstats[i];
559 : AttributeOpts *aopt;
560 :
561 69998 : stats->rows = rows;
562 69998 : stats->tupDesc = onerel->rd_att;
563 69998 : stats->compute_stats(stats,
564 : std_fetch_func,
565 : numrows,
566 : totalrows);
567 :
568 : /*
569 : * If the appropriate flavor of the n_distinct option is
570 : * specified, override with the corresponding value.
571 : */
572 69998 : aopt = get_attribute_options(onerel->rd_id, stats->tupattnum);
573 69998 : if (aopt != NULL)
574 : {
575 : float8 n_distinct;
576 :
577 6 : n_distinct = inh ? aopt->n_distinct_inherited : aopt->n_distinct;
578 6 : if (n_distinct != 0.0)
579 6 : stats->stadistinct = n_distinct;
580 : }
581 :
582 69998 : MemoryContextReset(col_context);
583 : }
584 :
585 9198 : if (nindexes > 0)
586 5732 : compute_index_stats(onerel, totalrows,
587 : indexdata, nindexes,
588 : rows, numrows,
589 : col_context);
590 :
591 9192 : MemoryContextSwitchTo(old_context);
592 9192 : MemoryContextDelete(col_context);
593 :
594 : /*
595 : * Emit the completed stats rows into pg_statistic, replacing any
596 : * previous statistics for the target columns. (If there are stats in
597 : * pg_statistic for columns we didn't process, we leave them alone.)
598 : */
599 9192 : update_attstats(RelationGetRelid(onerel), inh,
600 : attr_cnt, vacattrstats);
601 :
602 20322 : for (ind = 0; ind < nindexes; ind++)
603 : {
604 11130 : AnlIndexData *thisdata = &indexdata[ind];
605 :
606 11130 : update_attstats(RelationGetRelid(Irel[ind]), false,
607 : thisdata->attr_cnt, thisdata->vacattrstats);
608 : }
609 :
610 : /* Build extended statistics (if there are any). */
611 9192 : BuildRelationExtStatistics(onerel, inh, totalrows, numrows, rows,
612 : attr_cnt, vacattrstats);
613 : }
614 :
615 13478 : pgstat_progress_update_param(PROGRESS_ANALYZE_PHASE,
616 : PROGRESS_ANALYZE_PHASE_FINALIZE_ANALYZE);
617 :
618 : /*
619 : * Update pages/tuples stats in pg_class ... but not if we're doing
620 : * inherited stats.
621 : *
622 : * We assume that VACUUM hasn't set pg_class.reltuples already, even
623 : * during a VACUUM ANALYZE. Although VACUUM often updates pg_class,
624 : * exceptions exist. A "VACUUM (ANALYZE, INDEX_CLEANUP OFF)" command will
625 : * never update pg_class entries for index relations. It's also possible
626 : * that an individual index's pg_class entry won't be updated during
627 : * VACUUM if the index AM returns NULL from its amvacuumcleanup() routine.
628 : */
629 13478 : if (!inh)
630 : {
631 : BlockNumber relallvisible;
632 :
633 12686 : if (RELKIND_HAS_STORAGE(onerel->rd_rel->relkind))
634 12632 : visibilitymap_count(onerel, &relallvisible, NULL);
635 : else
636 54 : relallvisible = 0;
637 :
638 : /*
639 : * Update pg_class for table relation. CCI first, in case acquirefunc
640 : * updated pg_class.
641 : */
642 12686 : CommandCounterIncrement();
643 12686 : vac_update_relstats(onerel,
644 : relpages,
645 : totalrows,
646 : relallvisible,
647 : hasindex,
648 : InvalidTransactionId,
649 : InvalidMultiXactId,
650 : NULL, NULL,
651 : in_outer_xact);
652 :
653 : /* Same for indexes */
654 30980 : for (ind = 0; ind < nindexes; ind++)
655 : {
656 18294 : AnlIndexData *thisdata = &indexdata[ind];
657 : double totalindexrows;
658 :
659 18294 : totalindexrows = ceil(thisdata->tupleFract * totalrows);
660 18294 : vac_update_relstats(Irel[ind],
661 18294 : RelationGetNumberOfBlocks(Irel[ind]),
662 : totalindexrows,
663 : 0,
664 : false,
665 : InvalidTransactionId,
666 : InvalidMultiXactId,
667 : NULL, NULL,
668 : in_outer_xact);
669 : }
670 : }
671 792 : else if (onerel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
672 : {
673 : /*
674 : * Partitioned tables don't have storage, so we don't set any fields
675 : * in their pg_class entries except for reltuples and relhasindex.
676 : */
677 686 : CommandCounterIncrement();
678 686 : vac_update_relstats(onerel, -1, totalrows,
679 : 0, hasindex, InvalidTransactionId,
680 : InvalidMultiXactId,
681 : NULL, NULL,
682 : in_outer_xact);
683 : }
684 :
685 : /*
686 : * Now report ANALYZE to the cumulative stats system. For regular tables,
687 : * we do it only if not doing inherited stats. For partitioned tables, we
688 : * only do it for inherited stats. (We're never called for not-inherited
689 : * stats on partitioned tables anyway.)
690 : *
691 : * Reset the changes_since_analyze counter only if we analyzed all
692 : * columns; otherwise, there is still work for auto-analyze to do.
693 : */
694 13478 : if (!inh)
695 12686 : pgstat_report_analyze(onerel, totalrows, totaldeadrows,
696 : (va_cols == NIL));
697 792 : else if (onerel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
698 686 : pgstat_report_analyze(onerel, 0, 0, (va_cols == NIL));
699 :
700 : /*
701 : * If this isn't part of VACUUM ANALYZE, let index AMs do cleanup.
702 : *
703 : * Note that most index AMs perform a no-op as a matter of policy for
704 : * amvacuumcleanup() when called in ANALYZE-only mode. The only exception
705 : * among core index AMs is GIN/ginvacuumcleanup().
706 : */
707 13478 : if (!(params->options & VACOPT_VACUUM))
708 : {
709 28100 : for (ind = 0; ind < nindexes; ind++)
710 : {
711 : IndexBulkDeleteResult *stats;
712 : IndexVacuumInfo ivinfo;
713 :
714 16126 : ivinfo.index = Irel[ind];
715 16126 : ivinfo.heaprel = onerel;
716 16126 : ivinfo.analyze_only = true;
717 16126 : ivinfo.estimated_count = true;
718 16126 : ivinfo.message_level = elevel;
719 16126 : ivinfo.num_heap_tuples = onerel->rd_rel->reltuples;
720 16126 : ivinfo.strategy = vac_strategy;
721 :
722 16126 : stats = index_vacuum_cleanup(&ivinfo, NULL);
723 :
724 16126 : if (stats)
725 0 : pfree(stats);
726 : }
727 : }
728 :
729 : /* Done with indexes */
730 13478 : vac_close_indexes(nindexes, Irel, NoLock);
731 :
732 : /* Log the action if appropriate */
733 13478 : if (instrument)
734 : {
735 246 : TimestampTz endtime = GetCurrentTimestamp();
736 :
737 326 : if (verbose || params->log_min_duration == 0 ||
738 80 : TimestampDifferenceExceeds(starttime, endtime,
739 : params->log_min_duration))
740 : {
741 : long delay_in_ms;
742 : WalUsage walusage;
743 166 : double read_rate = 0;
744 166 : double write_rate = 0;
745 : char *msgfmt;
746 : StringInfoData buf;
747 : int64 total_blks_hit;
748 : int64 total_blks_read;
749 : int64 total_blks_dirtied;
750 :
751 166 : memset(&bufferusage, 0, sizeof(BufferUsage));
752 166 : BufferUsageAccumDiff(&bufferusage, &pgBufferUsage, &startbufferusage);
753 166 : memset(&walusage, 0, sizeof(WalUsage));
754 166 : WalUsageAccumDiff(&walusage, &pgWalUsage, &startwalusage);
755 :
756 166 : total_blks_hit = bufferusage.shared_blks_hit +
757 166 : bufferusage.local_blks_hit;
758 166 : total_blks_read = bufferusage.shared_blks_read +
759 166 : bufferusage.local_blks_read;
760 166 : total_blks_dirtied = bufferusage.shared_blks_dirtied +
761 166 : bufferusage.local_blks_dirtied;
762 :
763 : /*
764 : * We do not expect an analyze to take > 25 days and it simplifies
765 : * things a bit to use TimestampDifferenceMilliseconds.
766 : */
767 166 : delay_in_ms = TimestampDifferenceMilliseconds(starttime, endtime);
768 :
769 : /*
770 : * Note that we are reporting these read/write rates in the same
771 : * manner as VACUUM does, which means that while the 'average read
772 : * rate' here actually corresponds to page misses and resulting
773 : * reads which are also picked up by track_io_timing, if enabled,
774 : * the 'average write rate' is actually talking about the rate of
775 : * pages being dirtied, not being written out, so it's typical to
776 : * have a non-zero 'avg write rate' while I/O timings only reports
777 : * reads.
778 : *
779 : * It's not clear that an ANALYZE will ever result in
780 : * FlushBuffer() being called, but we track and support reporting
781 : * on I/O write time in case that changes as it's practically free
782 : * to do so anyway.
783 : */
784 :
785 166 : if (delay_in_ms > 0)
786 : {
787 166 : read_rate = (double) BLCKSZ * total_blks_read /
788 166 : (1024 * 1024) / (delay_in_ms / 1000.0);
789 166 : write_rate = (double) BLCKSZ * total_blks_dirtied /
790 166 : (1024 * 1024) / (delay_in_ms / 1000.0);
791 : }
792 :
793 : /*
794 : * We split this up so we don't emit empty I/O timing values when
795 : * track_io_timing isn't enabled.
796 : */
797 :
798 166 : initStringInfo(&buf);
799 :
800 166 : if (AmAutoVacuumWorkerProcess())
801 166 : msgfmt = _("automatic analyze of table \"%s.%s.%s\"\n");
802 : else
803 0 : msgfmt = _("finished analyzing table \"%s.%s.%s\"\n");
804 :
805 166 : appendStringInfo(&buf, msgfmt,
806 : get_database_name(MyDatabaseId),
807 166 : get_namespace_name(RelationGetNamespace(onerel)),
808 166 : RelationGetRelationName(onerel));
809 166 : if (track_io_timing)
810 : {
811 0 : double read_ms = (double) (pgStatBlockReadTime - startreadtime) / 1000;
812 0 : double write_ms = (double) (pgStatBlockWriteTime - startwritetime) / 1000;
813 :
814 0 : appendStringInfo(&buf, _("I/O timings: read: %.3f ms, write: %.3f ms\n"),
815 : read_ms, write_ms);
816 : }
817 166 : appendStringInfo(&buf, _("avg read rate: %.3f MB/s, avg write rate: %.3f MB/s\n"),
818 : read_rate, write_rate);
819 166 : appendStringInfo(&buf, _("buffer usage: %lld hits, %lld reads, %lld dirtied\n"),
820 : (long long) total_blks_hit,
821 : (long long) total_blks_read,
822 : (long long) total_blks_dirtied);
823 166 : appendStringInfo(&buf,
824 166 : _("WAL usage: %lld records, %lld full page images, %llu bytes\n"),
825 166 : (long long) walusage.wal_records,
826 166 : (long long) walusage.wal_fpi,
827 166 : (unsigned long long) walusage.wal_bytes);
828 166 : appendStringInfo(&buf, _("system usage: %s"), pg_rusage_show(&ru0));
829 :
830 166 : ereport(verbose ? INFO : LOG,
831 : (errmsg_internal("%s", buf.data)));
832 :
833 166 : pfree(buf.data);
834 : }
835 : }
836 :
837 : /* Roll back any GUC changes executed by index functions */
838 13478 : AtEOXact_GUC(false, save_nestlevel);
839 :
840 : /* Restore userid and security context */
841 13478 : SetUserIdAndSecContext(save_userid, save_sec_context);
842 :
843 : /* Restore current context and release memory */
844 13478 : MemoryContextSwitchTo(caller_context);
845 13478 : MemoryContextDelete(anl_context);
846 13478 : anl_context = NULL;
847 13478 : }
848 :
849 : /*
850 : * Compute statistics about indexes of a relation
851 : */
852 : static void
853 5732 : compute_index_stats(Relation onerel, double totalrows,
854 : AnlIndexData *indexdata, int nindexes,
855 : HeapTuple *rows, int numrows,
856 : MemoryContext col_context)
857 : {
858 : MemoryContext ind_context,
859 : old_context;
860 : Datum values[INDEX_MAX_KEYS];
861 : bool isnull[INDEX_MAX_KEYS];
862 : int ind,
863 : i;
864 :
865 5732 : ind_context = AllocSetContextCreate(anl_context,
866 : "Analyze Index",
867 : ALLOCSET_DEFAULT_SIZES);
868 5732 : old_context = MemoryContextSwitchTo(ind_context);
869 :
870 16868 : for (ind = 0; ind < nindexes; ind++)
871 : {
872 11142 : AnlIndexData *thisdata = &indexdata[ind];
873 11142 : IndexInfo *indexInfo = thisdata->indexInfo;
874 11142 : int attr_cnt = thisdata->attr_cnt;
875 : TupleTableSlot *slot;
876 : EState *estate;
877 : ExprContext *econtext;
878 : ExprState *predicate;
879 : Datum *exprvals;
880 : bool *exprnulls;
881 : int numindexrows,
882 : tcnt,
883 : rowno;
884 : double totalindexrows;
885 :
886 : /* Ignore index if no columns to analyze and not partial */
887 11142 : if (attr_cnt == 0 && indexInfo->ii_Predicate == NIL)
888 11032 : continue;
889 :
890 : /*
891 : * Need an EState for evaluation of index expressions and
892 : * partial-index predicates. Create it in the per-index context to be
893 : * sure it gets cleaned up at the bottom of the loop.
894 : */
895 110 : estate = CreateExecutorState();
896 110 : econtext = GetPerTupleExprContext(estate);
897 : /* Need a slot to hold the current heap tuple, too */
898 110 : slot = MakeSingleTupleTableSlot(RelationGetDescr(onerel),
899 : &TTSOpsHeapTuple);
900 :
901 : /* Arrange for econtext's scan tuple to be the tuple under test */
902 110 : econtext->ecxt_scantuple = slot;
903 :
904 : /* Set up execution state for predicate. */
905 110 : predicate = ExecPrepareQual(indexInfo->ii_Predicate, estate);
906 :
907 : /* Compute and save index expression values */
908 110 : exprvals = (Datum *) palloc(numrows * attr_cnt * sizeof(Datum));
909 110 : exprnulls = (bool *) palloc(numrows * attr_cnt * sizeof(bool));
910 110 : numindexrows = 0;
911 110 : tcnt = 0;
912 94660 : for (rowno = 0; rowno < numrows; rowno++)
913 : {
914 94556 : HeapTuple heapTuple = rows[rowno];
915 :
916 94556 : vacuum_delay_point();
917 :
918 : /*
919 : * Reset the per-tuple context each time, to reclaim any cruft
920 : * left behind by evaluating the predicate or index expressions.
921 : */
922 94556 : ResetExprContext(econtext);
923 :
924 : /* Set up for predicate or expression evaluation */
925 94556 : ExecStoreHeapTuple(heapTuple, slot, false);
926 :
927 : /* If index is partial, check predicate */
928 94556 : if (predicate != NULL)
929 : {
930 20066 : if (!ExecQual(predicate, econtext))
931 19328 : continue;
932 : }
933 75228 : numindexrows++;
934 :
935 75228 : if (attr_cnt > 0)
936 : {
937 : /*
938 : * Evaluate the index row to compute expression values. We
939 : * could do this by hand, but FormIndexDatum is convenient.
940 : */
941 74490 : FormIndexDatum(indexInfo,
942 : slot,
943 : estate,
944 : values,
945 : isnull);
946 :
947 : /*
948 : * Save just the columns we care about. We copy the values
949 : * into ind_context from the estate's per-tuple context.
950 : */
951 148968 : for (i = 0; i < attr_cnt; i++)
952 : {
953 74484 : VacAttrStats *stats = thisdata->vacattrstats[i];
954 74484 : int attnum = stats->tupattnum;
955 :
956 74484 : if (isnull[attnum - 1])
957 : {
958 6 : exprvals[tcnt] = (Datum) 0;
959 6 : exprnulls[tcnt] = true;
960 : }
961 : else
962 : {
963 148956 : exprvals[tcnt] = datumCopy(values[attnum - 1],
964 74478 : stats->attrtype->typbyval,
965 74478 : stats->attrtype->typlen);
966 74478 : exprnulls[tcnt] = false;
967 : }
968 74484 : tcnt++;
969 : }
970 : }
971 : }
972 :
973 : /*
974 : * Having counted the number of rows that pass the predicate in the
975 : * sample, we can estimate the total number of rows in the index.
976 : */
977 104 : thisdata->tupleFract = (double) numindexrows / (double) numrows;
978 104 : totalindexrows = ceil(thisdata->tupleFract * totalrows);
979 :
980 : /*
981 : * Now we can compute the statistics for the expression columns.
982 : */
983 104 : if (numindexrows > 0)
984 : {
985 96 : MemoryContextSwitchTo(col_context);
986 156 : for (i = 0; i < attr_cnt; i++)
987 : {
988 60 : VacAttrStats *stats = thisdata->vacattrstats[i];
989 :
990 60 : stats->exprvals = exprvals + i;
991 60 : stats->exprnulls = exprnulls + i;
992 60 : stats->rowstride = attr_cnt;
993 60 : stats->compute_stats(stats,
994 : ind_fetch_func,
995 : numindexrows,
996 : totalindexrows);
997 :
998 60 : MemoryContextReset(col_context);
999 : }
1000 : }
1001 :
1002 : /* And clean up */
1003 104 : MemoryContextSwitchTo(ind_context);
1004 :
1005 104 : ExecDropSingleTupleTableSlot(slot);
1006 104 : FreeExecutorState(estate);
1007 104 : MemoryContextReset(ind_context);
1008 : }
1009 :
1010 5726 : MemoryContextSwitchTo(old_context);
1011 5726 : MemoryContextDelete(ind_context);
1012 5726 : }
1013 :
1014 : /*
1015 : * examine_attribute -- pre-analysis of a single column
1016 : *
1017 : * Determine whether the column is analyzable; if so, create and initialize
1018 : * a VacAttrStats struct for it. If not, return NULL.
1019 : *
1020 : * If index_expr isn't NULL, then we're trying to analyze an expression index,
1021 : * and index_expr is the expression tree representing the column's data.
1022 : */
1023 : static VacAttrStats *
1024 95188 : examine_attribute(Relation onerel, int attnum, Node *index_expr)
1025 : {
1026 95188 : Form_pg_attribute attr = TupleDescAttr(onerel->rd_att, attnum - 1);
1027 : int attstattarget;
1028 : HeapTuple atttuple;
1029 : Datum dat;
1030 : bool isnull;
1031 : HeapTuple typtuple;
1032 : VacAttrStats *stats;
1033 : int i;
1034 : bool ok;
1035 :
1036 : /* Never analyze dropped columns */
1037 95188 : if (attr->attisdropped)
1038 6 : return NULL;
1039 :
1040 : /*
1041 : * Get attstattarget value. Set to -1 if null. (Analyze functions expect
1042 : * -1 to mean use default_statistics_target; see for example
1043 : * std_typanalyze.)
1044 : */
1045 95182 : atttuple = SearchSysCache2(ATTNUM, ObjectIdGetDatum(RelationGetRelid(onerel)), Int16GetDatum(attnum));
1046 95182 : if (!HeapTupleIsValid(atttuple))
1047 0 : elog(ERROR, "cache lookup failed for attribute %d of relation %u",
1048 : attnum, RelationGetRelid(onerel));
1049 95182 : dat = SysCacheGetAttr(ATTNUM, atttuple, Anum_pg_attribute_attstattarget, &isnull);
1050 95182 : attstattarget = isnull ? -1 : DatumGetInt16(dat);
1051 95182 : ReleaseSysCache(atttuple);
1052 :
1053 : /* Don't analyze column if user has specified not to */
1054 95182 : if (attstattarget == 0)
1055 6 : return NULL;
1056 :
1057 : /*
1058 : * Create the VacAttrStats struct.
1059 : */
1060 95176 : stats = (VacAttrStats *) palloc0(sizeof(VacAttrStats));
1061 95176 : stats->attstattarget = attstattarget;
1062 :
1063 : /*
1064 : * When analyzing an expression index, believe the expression tree's type
1065 : * not the column datatype --- the latter might be the opckeytype storage
1066 : * type of the opclass, which is not interesting for our purposes. (Note:
1067 : * if we did anything with non-expression index columns, we'd need to
1068 : * figure out where to get the correct type info from, but for now that's
1069 : * not a problem.) It's not clear whether anyone will care about the
1070 : * typmod, but we store that too just in case.
1071 : */
1072 95176 : if (index_expr)
1073 : {
1074 72 : stats->attrtypid = exprType(index_expr);
1075 72 : stats->attrtypmod = exprTypmod(index_expr);
1076 :
1077 : /*
1078 : * If a collation has been specified for the index column, use that in
1079 : * preference to anything else; but if not, fall back to whatever we
1080 : * can get from the expression.
1081 : */
1082 72 : if (OidIsValid(onerel->rd_indcollation[attnum - 1]))
1083 12 : stats->attrcollid = onerel->rd_indcollation[attnum - 1];
1084 : else
1085 60 : stats->attrcollid = exprCollation(index_expr);
1086 : }
1087 : else
1088 : {
1089 95104 : stats->attrtypid = attr->atttypid;
1090 95104 : stats->attrtypmod = attr->atttypmod;
1091 95104 : stats->attrcollid = attr->attcollation;
1092 : }
1093 :
1094 95176 : typtuple = SearchSysCacheCopy1(TYPEOID,
1095 : ObjectIdGetDatum(stats->attrtypid));
1096 95176 : if (!HeapTupleIsValid(typtuple))
1097 0 : elog(ERROR, "cache lookup failed for type %u", stats->attrtypid);
1098 95176 : stats->attrtype = (Form_pg_type) GETSTRUCT(typtuple);
1099 95176 : stats->anl_context = anl_context;
1100 95176 : stats->tupattnum = attnum;
1101 :
1102 : /*
1103 : * The fields describing the stats->stavalues[n] element types default to
1104 : * the type of the data being analyzed, but the type-specific typanalyze
1105 : * function can change them if it wants to store something else.
1106 : */
1107 571056 : for (i = 0; i < STATISTIC_NUM_SLOTS; i++)
1108 : {
1109 475880 : stats->statypid[i] = stats->attrtypid;
1110 475880 : stats->statyplen[i] = stats->attrtype->typlen;
1111 475880 : stats->statypbyval[i] = stats->attrtype->typbyval;
1112 475880 : stats->statypalign[i] = stats->attrtype->typalign;
1113 : }
1114 :
1115 : /*
1116 : * Call the type-specific typanalyze function. If none is specified, use
1117 : * std_typanalyze().
1118 : */
1119 95176 : if (OidIsValid(stats->attrtype->typanalyze))
1120 6112 : ok = DatumGetBool(OidFunctionCall1(stats->attrtype->typanalyze,
1121 : PointerGetDatum(stats)));
1122 : else
1123 89064 : ok = std_typanalyze(stats);
1124 :
1125 95176 : if (!ok || stats->compute_stats == NULL || stats->minrows <= 0)
1126 : {
1127 0 : heap_freetuple(typtuple);
1128 0 : pfree(stats);
1129 0 : return NULL;
1130 : }
1131 :
1132 95176 : return stats;
1133 : }
1134 :
1135 : /*
1136 : * Read stream callback returning the next BlockNumber as chosen by the
1137 : * BlockSampling algorithm.
1138 : */
1139 : static BlockNumber
1140 127058 : block_sampling_read_stream_next(ReadStream *stream,
1141 : void *callback_private_data,
1142 : void *per_buffer_data)
1143 : {
1144 127058 : BlockSamplerData *bs = callback_private_data;
1145 :
1146 127058 : return BlockSampler_HasMore(bs) ? BlockSampler_Next(bs) : InvalidBlockNumber;
1147 : }
1148 :
1149 : /*
1150 : * acquire_sample_rows -- acquire a random sample of rows from the table
1151 : *
1152 : * Selected rows are returned in the caller-allocated array rows[], which
1153 : * must have at least targrows entries.
1154 : * The actual number of rows selected is returned as the function result.
1155 : * We also estimate the total numbers of live and dead rows in the table,
1156 : * and return them into *totalrows and *totaldeadrows, respectively.
1157 : *
1158 : * The returned list of tuples is in order by physical position in the table.
1159 : * (We will rely on this later to derive correlation estimates.)
1160 : *
1161 : * As of May 2004 we use a new two-stage method: Stage one selects up
1162 : * to targrows random blocks (or all blocks, if there aren't so many).
1163 : * Stage two scans these blocks and uses the Vitter algorithm to create
1164 : * a random sample of targrows rows (or less, if there are less in the
1165 : * sample of blocks). The two stages are executed simultaneously: each
1166 : * block is processed as soon as stage one returns its number and while
1167 : * the rows are read stage two controls which ones are to be inserted
1168 : * into the sample.
1169 : *
1170 : * Although every row has an equal chance of ending up in the final
1171 : * sample, this sampling method is not perfect: not every possible
1172 : * sample has an equal chance of being selected. For large relations
1173 : * the number of different blocks represented by the sample tends to be
1174 : * too small. We can live with that for now. Improvements are welcome.
1175 : *
1176 : * An important property of this sampling method is that because we do
1177 : * look at a statistically unbiased set of blocks, we should get
1178 : * unbiased estimates of the average numbers of live and dead rows per
1179 : * block. The previous sampling method put too much credence in the row
1180 : * density near the start of the table.
1181 : */
1182 : static int
1183 14514 : acquire_sample_rows(Relation onerel, int elevel,
1184 : HeapTuple *rows, int targrows,
1185 : double *totalrows, double *totaldeadrows)
1186 : {
1187 14514 : int numrows = 0; /* # rows now in reservoir */
1188 14514 : double samplerows = 0; /* total # rows collected */
1189 14514 : double liverows = 0; /* # live rows seen */
1190 14514 : double deadrows = 0; /* # dead rows seen */
1191 14514 : double rowstoskip = -1; /* -1 means not set yet */
1192 : uint32 randseed; /* Seed for block sampler(s) */
1193 : BlockNumber totalblocks;
1194 : TransactionId OldestXmin;
1195 : BlockSamplerData bs;
1196 : ReservoirStateData rstate;
1197 : TupleTableSlot *slot;
1198 : TableScanDesc scan;
1199 : BlockNumber nblocks;
1200 14514 : BlockNumber blksdone = 0;
1201 : ReadStream *stream;
1202 :
1203 : Assert(targrows > 0);
1204 :
1205 14514 : totalblocks = RelationGetNumberOfBlocks(onerel);
1206 :
1207 : /* Need a cutoff xmin for HeapTupleSatisfiesVacuum */
1208 14514 : OldestXmin = GetOldestNonRemovableTransactionId(onerel);
1209 :
1210 : /* Prepare for sampling block numbers */
1211 14514 : randseed = pg_prng_uint32(&pg_global_prng_state);
1212 14514 : nblocks = BlockSampler_Init(&bs, totalblocks, targrows, randseed);
1213 :
1214 : /* Report sampling block numbers */
1215 14514 : pgstat_progress_update_param(PROGRESS_ANALYZE_BLOCKS_TOTAL,
1216 : nblocks);
1217 :
1218 : /* Prepare for sampling rows */
1219 14514 : reservoir_init_selection_state(&rstate, targrows);
1220 :
1221 14514 : scan = table_beginscan_analyze(onerel);
1222 14514 : slot = table_slot_create(onerel, NULL);
1223 :
1224 14514 : stream = read_stream_begin_relation(READ_STREAM_MAINTENANCE,
1225 : vac_strategy,
1226 : scan->rs_rd,
1227 : MAIN_FORKNUM,
1228 : block_sampling_read_stream_next,
1229 : &bs,
1230 : 0);
1231 :
1232 : /* Outer loop over blocks to sample */
1233 127058 : while (table_scan_analyze_next_block(scan, stream))
1234 : {
1235 112544 : vacuum_delay_point();
1236 :
1237 9012872 : while (table_scan_analyze_next_tuple(scan, OldestXmin, &liverows, &deadrows, slot))
1238 : {
1239 : /*
1240 : * The first targrows sample rows are simply copied into the
1241 : * reservoir. Then we start replacing tuples in the sample until
1242 : * we reach the end of the relation. This algorithm is from Jeff
1243 : * Vitter's paper (see full citation in utils/misc/sampling.c). It
1244 : * works by repeatedly computing the number of tuples to skip
1245 : * before selecting a tuple, which replaces a randomly chosen
1246 : * element of the reservoir (current set of tuples). At all times
1247 : * the reservoir is a true random sample of the tuples we've
1248 : * passed over so far, so when we fall off the end of the relation
1249 : * we're done.
1250 : */
1251 8900328 : if (numrows < targrows)
1252 8650144 : rows[numrows++] = ExecCopySlotHeapTuple(slot);
1253 : else
1254 : {
1255 : /*
1256 : * t in Vitter's paper is the number of records already
1257 : * processed. If we need to compute a new S value, we must
1258 : * use the not-yet-incremented value of samplerows as t.
1259 : */
1260 250184 : if (rowstoskip < 0)
1261 114570 : rowstoskip = reservoir_get_next_S(&rstate, samplerows, targrows);
1262 :
1263 250184 : if (rowstoskip <= 0)
1264 : {
1265 : /*
1266 : * Found a suitable tuple, so save it, replacing one old
1267 : * tuple at random
1268 : */
1269 114514 : int k = (int) (targrows * sampler_random_fract(&rstate.randstate));
1270 :
1271 : Assert(k >= 0 && k < targrows);
1272 114514 : heap_freetuple(rows[k]);
1273 114514 : rows[k] = ExecCopySlotHeapTuple(slot);
1274 : }
1275 :
1276 250184 : rowstoskip -= 1;
1277 : }
1278 :
1279 8900328 : samplerows += 1;
1280 : }
1281 :
1282 112544 : pgstat_progress_update_param(PROGRESS_ANALYZE_BLOCKS_DONE,
1283 : ++blksdone);
1284 : }
1285 :
1286 14514 : read_stream_end(stream);
1287 :
1288 14514 : ExecDropSingleTupleTableSlot(slot);
1289 14514 : table_endscan(scan);
1290 :
1291 : /*
1292 : * If we didn't find as many tuples as we wanted then we're done. No sort
1293 : * is needed, since they're already in order.
1294 : *
1295 : * Otherwise we need to sort the collected tuples by position
1296 : * (itempointer). It's not worth worrying about corner cases where the
1297 : * tuples are already sorted.
1298 : */
1299 14514 : if (numrows == targrows)
1300 162 : qsort_interruptible(rows, numrows, sizeof(HeapTuple),
1301 : compare_rows, NULL);
1302 :
1303 : /*
1304 : * Estimate total numbers of live and dead rows in relation, extrapolating
1305 : * on the assumption that the average tuple density in pages we didn't
1306 : * scan is the same as in the pages we did scan. Since what we scanned is
1307 : * a random sample of the pages in the relation, this should be a good
1308 : * assumption.
1309 : */
1310 14514 : if (bs.m > 0)
1311 : {
1312 10306 : *totalrows = floor((liverows / bs.m) * totalblocks + 0.5);
1313 10306 : *totaldeadrows = floor((deadrows / bs.m) * totalblocks + 0.5);
1314 : }
1315 : else
1316 : {
1317 4208 : *totalrows = 0.0;
1318 4208 : *totaldeadrows = 0.0;
1319 : }
1320 :
1321 : /*
1322 : * Emit some interesting relation info
1323 : */
1324 14514 : ereport(elevel,
1325 : (errmsg("\"%s\": scanned %d of %u pages, "
1326 : "containing %.0f live rows and %.0f dead rows; "
1327 : "%d rows in sample, %.0f estimated total rows",
1328 : RelationGetRelationName(onerel),
1329 : bs.m, totalblocks,
1330 : liverows, deadrows,
1331 : numrows, *totalrows)));
1332 :
1333 14514 : return numrows;
1334 : }
1335 :
1336 : /*
1337 : * Comparator for sorting rows[] array
1338 : */
1339 : static int
1340 4022922 : compare_rows(const void *a, const void *b, void *arg)
1341 : {
1342 4022922 : HeapTuple ha = *(const HeapTuple *) a;
1343 4022922 : HeapTuple hb = *(const HeapTuple *) b;
1344 4022922 : BlockNumber ba = ItemPointerGetBlockNumber(&ha->t_self);
1345 4022922 : OffsetNumber oa = ItemPointerGetOffsetNumber(&ha->t_self);
1346 4022922 : BlockNumber bb = ItemPointerGetBlockNumber(&hb->t_self);
1347 4022922 : OffsetNumber ob = ItemPointerGetOffsetNumber(&hb->t_self);
1348 :
1349 4022922 : if (ba < bb)
1350 905368 : return -1;
1351 3117554 : if (ba > bb)
1352 845094 : return 1;
1353 2272460 : if (oa < ob)
1354 1528458 : return -1;
1355 744002 : if (oa > ob)
1356 744002 : return 1;
1357 0 : return 0;
1358 : }
1359 :
1360 :
1361 : /*
1362 : * acquire_inherited_sample_rows -- acquire sample rows from inheritance tree
1363 : *
1364 : * This has the same API as acquire_sample_rows, except that rows are
1365 : * collected from all inheritance children as well as the specified table.
1366 : * We fail and return zero if there are no inheritance children, or if all
1367 : * children are foreign tables that don't support ANALYZE.
1368 : */
1369 : static int
1370 792 : acquire_inherited_sample_rows(Relation onerel, int elevel,
1371 : HeapTuple *rows, int targrows,
1372 : double *totalrows, double *totaldeadrows)
1373 : {
1374 : List *tableOIDs;
1375 : Relation *rels;
1376 : AcquireSampleRowsFunc *acquirefuncs;
1377 : double *relblocks;
1378 : double totalblocks;
1379 : int numrows,
1380 : nrels,
1381 : i;
1382 : ListCell *lc;
1383 : bool has_child;
1384 :
1385 : /* Initialize output parameters to zero now, in case we exit early */
1386 792 : *totalrows = 0;
1387 792 : *totaldeadrows = 0;
1388 :
1389 : /*
1390 : * Find all members of inheritance set. We only need AccessShareLock on
1391 : * the children.
1392 : */
1393 : tableOIDs =
1394 792 : find_all_inheritors(RelationGetRelid(onerel), AccessShareLock, NULL);
1395 :
1396 : /*
1397 : * Check that there's at least one descendant, else fail. This could
1398 : * happen despite analyze_rel's relhassubclass check, if table once had a
1399 : * child but no longer does. In that case, we can clear the
1400 : * relhassubclass field so as not to make the same mistake again later.
1401 : * (This is safe because we hold ShareUpdateExclusiveLock.)
1402 : */
1403 792 : if (list_length(tableOIDs) < 2)
1404 : {
1405 : /* CCI because we already updated the pg_class row in this command */
1406 14 : CommandCounterIncrement();
1407 14 : SetRelationHasSubclass(RelationGetRelid(onerel), false);
1408 14 : ereport(elevel,
1409 : (errmsg("skipping analyze of \"%s.%s\" inheritance tree --- this inheritance tree contains no child tables",
1410 : get_namespace_name(RelationGetNamespace(onerel)),
1411 : RelationGetRelationName(onerel))));
1412 14 : return 0;
1413 : }
1414 :
1415 : /*
1416 : * Identify acquirefuncs to use, and count blocks in all the relations.
1417 : * The result could overflow BlockNumber, so we use double arithmetic.
1418 : */
1419 778 : rels = (Relation *) palloc(list_length(tableOIDs) * sizeof(Relation));
1420 : acquirefuncs = (AcquireSampleRowsFunc *)
1421 778 : palloc(list_length(tableOIDs) * sizeof(AcquireSampleRowsFunc));
1422 778 : relblocks = (double *) palloc(list_length(tableOIDs) * sizeof(double));
1423 778 : totalblocks = 0;
1424 778 : nrels = 0;
1425 778 : has_child = false;
1426 3584 : foreach(lc, tableOIDs)
1427 : {
1428 2806 : Oid childOID = lfirst_oid(lc);
1429 : Relation childrel;
1430 2806 : AcquireSampleRowsFunc acquirefunc = NULL;
1431 2806 : BlockNumber relpages = 0;
1432 :
1433 : /* We already got the needed lock */
1434 2806 : childrel = table_open(childOID, NoLock);
1435 :
1436 : /* Ignore if temp table of another backend */
1437 2806 : if (RELATION_IS_OTHER_TEMP(childrel))
1438 : {
1439 : /* ... but release the lock on it */
1440 : Assert(childrel != onerel);
1441 0 : table_close(childrel, AccessShareLock);
1442 746 : continue;
1443 : }
1444 :
1445 : /* Check table type (MATVIEW can't happen, but might as well allow) */
1446 2806 : if (childrel->rd_rel->relkind == RELKIND_RELATION ||
1447 776 : childrel->rd_rel->relkind == RELKIND_MATVIEW)
1448 : {
1449 : /* Regular table, so use the regular row acquisition function */
1450 2030 : acquirefunc = acquire_sample_rows;
1451 2030 : relpages = RelationGetNumberOfBlocks(childrel);
1452 : }
1453 776 : else if (childrel->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
1454 : {
1455 : /*
1456 : * For a foreign table, call the FDW's hook function to see
1457 : * whether it supports analysis.
1458 : */
1459 : FdwRoutine *fdwroutine;
1460 30 : bool ok = false;
1461 :
1462 30 : fdwroutine = GetFdwRoutineForRelation(childrel, false);
1463 :
1464 30 : if (fdwroutine->AnalyzeForeignTable != NULL)
1465 30 : ok = fdwroutine->AnalyzeForeignTable(childrel,
1466 : &acquirefunc,
1467 : &relpages);
1468 :
1469 30 : if (!ok)
1470 : {
1471 : /* ignore, but release the lock on it */
1472 : Assert(childrel != onerel);
1473 0 : table_close(childrel, AccessShareLock);
1474 0 : continue;
1475 : }
1476 : }
1477 : else
1478 : {
1479 : /*
1480 : * ignore, but release the lock on it. don't try to unlock the
1481 : * passed-in relation
1482 : */
1483 : Assert(childrel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE);
1484 746 : if (childrel != onerel)
1485 66 : table_close(childrel, AccessShareLock);
1486 : else
1487 680 : table_close(childrel, NoLock);
1488 746 : continue;
1489 : }
1490 :
1491 : /* OK, we'll process this child */
1492 2060 : has_child = true;
1493 2060 : rels[nrels] = childrel;
1494 2060 : acquirefuncs[nrels] = acquirefunc;
1495 2060 : relblocks[nrels] = (double) relpages;
1496 2060 : totalblocks += (double) relpages;
1497 2060 : nrels++;
1498 : }
1499 :
1500 : /*
1501 : * If we don't have at least one child table to consider, fail. If the
1502 : * relation is a partitioned table, it's not counted as a child table.
1503 : */
1504 778 : if (!has_child)
1505 : {
1506 0 : ereport(elevel,
1507 : (errmsg("skipping analyze of \"%s.%s\" inheritance tree --- this inheritance tree contains no analyzable child tables",
1508 : get_namespace_name(RelationGetNamespace(onerel)),
1509 : RelationGetRelationName(onerel))));
1510 0 : return 0;
1511 : }
1512 :
1513 : /*
1514 : * Now sample rows from each relation, proportionally to its fraction of
1515 : * the total block count. (This might be less than desirable if the child
1516 : * rels have radically different free-space percentages, but it's not
1517 : * clear that it's worth working harder.)
1518 : */
1519 778 : pgstat_progress_update_param(PROGRESS_ANALYZE_CHILD_TABLES_TOTAL,
1520 : nrels);
1521 778 : numrows = 0;
1522 2838 : for (i = 0; i < nrels; i++)
1523 : {
1524 2060 : Relation childrel = rels[i];
1525 2060 : AcquireSampleRowsFunc acquirefunc = acquirefuncs[i];
1526 2060 : double childblocks = relblocks[i];
1527 :
1528 : /*
1529 : * Report progress. The sampling function will normally report blocks
1530 : * done/total, but we need to reset them to 0 here, so that they don't
1531 : * show an old value until that.
1532 : */
1533 : {
1534 2060 : const int progress_index[] = {
1535 : PROGRESS_ANALYZE_CURRENT_CHILD_TABLE_RELID,
1536 : PROGRESS_ANALYZE_BLOCKS_DONE,
1537 : PROGRESS_ANALYZE_BLOCKS_TOTAL
1538 : };
1539 2060 : const int64 progress_vals[] = {
1540 2060 : RelationGetRelid(childrel),
1541 : 0,
1542 : 0,
1543 : };
1544 :
1545 2060 : pgstat_progress_update_multi_param(3, progress_index, progress_vals);
1546 : }
1547 :
1548 2060 : if (childblocks > 0)
1549 : {
1550 : int childtargrows;
1551 :
1552 1906 : childtargrows = (int) rint(targrows * childblocks / totalblocks);
1553 : /* Make sure we don't overrun due to roundoff error */
1554 1906 : childtargrows = Min(childtargrows, targrows - numrows);
1555 1906 : if (childtargrows > 0)
1556 : {
1557 : int childrows;
1558 : double trows,
1559 : tdrows;
1560 :
1561 : /* Fetch a random sample of the child's rows */
1562 1906 : childrows = (*acquirefunc) (childrel, elevel,
1563 1906 : rows + numrows, childtargrows,
1564 : &trows, &tdrows);
1565 :
1566 : /* We may need to convert from child's rowtype to parent's */
1567 1906 : if (childrows > 0 &&
1568 1906 : !equalRowTypes(RelationGetDescr(childrel),
1569 : RelationGetDescr(onerel)))
1570 : {
1571 : TupleConversionMap *map;
1572 :
1573 1826 : map = convert_tuples_by_name(RelationGetDescr(childrel),
1574 : RelationGetDescr(onerel));
1575 1826 : if (map != NULL)
1576 : {
1577 : int j;
1578 :
1579 106448 : for (j = 0; j < childrows; j++)
1580 : {
1581 : HeapTuple newtup;
1582 :
1583 106318 : newtup = execute_attr_map_tuple(rows[numrows + j], map);
1584 106318 : heap_freetuple(rows[numrows + j]);
1585 106318 : rows[numrows + j] = newtup;
1586 : }
1587 130 : free_conversion_map(map);
1588 : }
1589 : }
1590 :
1591 : /* And add to counts */
1592 1906 : numrows += childrows;
1593 1906 : *totalrows += trows;
1594 1906 : *totaldeadrows += tdrows;
1595 : }
1596 : }
1597 :
1598 : /*
1599 : * Note: we cannot release the child-table locks, since we may have
1600 : * pointers to their TOAST tables in the sampled rows.
1601 : */
1602 2060 : table_close(childrel, NoLock);
1603 2060 : pgstat_progress_update_param(PROGRESS_ANALYZE_CHILD_TABLES_DONE,
1604 2060 : i + 1);
1605 : }
1606 :
1607 778 : return numrows;
1608 : }
1609 :
1610 :
1611 : /*
1612 : * update_attstats() -- update attribute statistics for one relation
1613 : *
1614 : * Statistics are stored in several places: the pg_class row for the
1615 : * relation has stats about the whole relation, and there is a
1616 : * pg_statistic row for each (non-system) attribute that has ever
1617 : * been analyzed. The pg_class values are updated by VACUUM, not here.
1618 : *
1619 : * pg_statistic rows are just added or updated normally. This means
1620 : * that pg_statistic will probably contain some deleted rows at the
1621 : * completion of a vacuum cycle, unless it happens to get vacuumed last.
1622 : *
1623 : * To keep things simple, we punt for pg_statistic, and don't try
1624 : * to compute or store rows for pg_statistic itself in pg_statistic.
1625 : * This could possibly be made to work, but it's not worth the trouble.
1626 : * Note analyze_rel() has seen to it that we won't come here when
1627 : * vacuuming pg_statistic itself.
1628 : *
1629 : * Note: there would be a race condition here if two backends could
1630 : * ANALYZE the same table concurrently. Presently, we lock that out
1631 : * by taking a self-exclusive lock on the relation in analyze_rel().
1632 : */
1633 : static void
1634 20322 : update_attstats(Oid relid, bool inh, int natts, VacAttrStats **vacattrstats)
1635 : {
1636 : Relation sd;
1637 : int attno;
1638 20322 : CatalogIndexState indstate = NULL;
1639 :
1640 20322 : if (natts <= 0)
1641 11082 : return; /* nothing to do */
1642 :
1643 9240 : sd = table_open(StatisticRelationId, RowExclusiveLock);
1644 :
1645 79298 : for (attno = 0; attno < natts; attno++)
1646 : {
1647 70058 : VacAttrStats *stats = vacattrstats[attno];
1648 : HeapTuple stup,
1649 : oldtup;
1650 : int i,
1651 : k,
1652 : n;
1653 : Datum values[Natts_pg_statistic];
1654 : bool nulls[Natts_pg_statistic];
1655 : bool replaces[Natts_pg_statistic];
1656 :
1657 : /* Ignore attr if we weren't able to collect stats */
1658 70058 : if (!stats->stats_valid)
1659 6 : continue;
1660 :
1661 : /*
1662 : * Construct a new pg_statistic tuple
1663 : */
1664 2241664 : for (i = 0; i < Natts_pg_statistic; ++i)
1665 : {
1666 2171612 : nulls[i] = false;
1667 2171612 : replaces[i] = true;
1668 : }
1669 :
1670 70052 : values[Anum_pg_statistic_starelid - 1] = ObjectIdGetDatum(relid);
1671 70052 : values[Anum_pg_statistic_staattnum - 1] = Int16GetDatum(stats->tupattnum);
1672 70052 : values[Anum_pg_statistic_stainherit - 1] = BoolGetDatum(inh);
1673 70052 : values[Anum_pg_statistic_stanullfrac - 1] = Float4GetDatum(stats->stanullfrac);
1674 70052 : values[Anum_pg_statistic_stawidth - 1] = Int32GetDatum(stats->stawidth);
1675 70052 : values[Anum_pg_statistic_stadistinct - 1] = Float4GetDatum(stats->stadistinct);
1676 70052 : i = Anum_pg_statistic_stakind1 - 1;
1677 420312 : for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1678 : {
1679 350260 : values[i++] = Int16GetDatum(stats->stakind[k]); /* stakindN */
1680 : }
1681 70052 : i = Anum_pg_statistic_staop1 - 1;
1682 420312 : for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1683 : {
1684 350260 : values[i++] = ObjectIdGetDatum(stats->staop[k]); /* staopN */
1685 : }
1686 70052 : i = Anum_pg_statistic_stacoll1 - 1;
1687 420312 : for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1688 : {
1689 350260 : values[i++] = ObjectIdGetDatum(stats->stacoll[k]); /* stacollN */
1690 : }
1691 70052 : i = Anum_pg_statistic_stanumbers1 - 1;
1692 420312 : for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1693 : {
1694 350260 : int nnum = stats->numnumbers[k];
1695 :
1696 350260 : if (nnum > 0)
1697 : {
1698 108532 : Datum *numdatums = (Datum *) palloc(nnum * sizeof(Datum));
1699 : ArrayType *arry;
1700 :
1701 885298 : for (n = 0; n < nnum; n++)
1702 776766 : numdatums[n] = Float4GetDatum(stats->stanumbers[k][n]);
1703 108532 : arry = construct_array_builtin(numdatums, nnum, FLOAT4OID);
1704 108532 : values[i++] = PointerGetDatum(arry); /* stanumbersN */
1705 : }
1706 : else
1707 : {
1708 241728 : nulls[i] = true;
1709 241728 : values[i++] = (Datum) 0;
1710 : }
1711 : }
1712 70052 : i = Anum_pg_statistic_stavalues1 - 1;
1713 420312 : for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1714 : {
1715 350260 : if (stats->numvalues[k] > 0)
1716 : {
1717 : ArrayType *arry;
1718 :
1719 76422 : arry = construct_array(stats->stavalues[k],
1720 : stats->numvalues[k],
1721 : stats->statypid[k],
1722 76422 : stats->statyplen[k],
1723 76422 : stats->statypbyval[k],
1724 76422 : stats->statypalign[k]);
1725 76422 : values[i++] = PointerGetDatum(arry); /* stavaluesN */
1726 : }
1727 : else
1728 : {
1729 273838 : nulls[i] = true;
1730 273838 : values[i++] = (Datum) 0;
1731 : }
1732 : }
1733 :
1734 : /* Is there already a pg_statistic tuple for this attribute? */
1735 140104 : oldtup = SearchSysCache3(STATRELATTINH,
1736 : ObjectIdGetDatum(relid),
1737 70052 : Int16GetDatum(stats->tupattnum),
1738 : BoolGetDatum(inh));
1739 :
1740 : /* Open index information when we know we need it */
1741 70052 : if (indstate == NULL)
1742 9234 : indstate = CatalogOpenIndexes(sd);
1743 :
1744 70052 : if (HeapTupleIsValid(oldtup))
1745 : {
1746 : /* Yes, replace it */
1747 27708 : stup = heap_modify_tuple(oldtup,
1748 : RelationGetDescr(sd),
1749 : values,
1750 : nulls,
1751 : replaces);
1752 27708 : ReleaseSysCache(oldtup);
1753 27708 : CatalogTupleUpdateWithInfo(sd, &stup->t_self, stup, indstate);
1754 : }
1755 : else
1756 : {
1757 : /* No, insert new tuple */
1758 42344 : stup = heap_form_tuple(RelationGetDescr(sd), values, nulls);
1759 42344 : CatalogTupleInsertWithInfo(sd, stup, indstate);
1760 : }
1761 :
1762 70052 : heap_freetuple(stup);
1763 : }
1764 :
1765 9240 : if (indstate != NULL)
1766 9234 : CatalogCloseIndexes(indstate);
1767 9240 : table_close(sd, RowExclusiveLock);
1768 : }
1769 :
1770 : /*
1771 : * Standard fetch function for use by compute_stats subroutines.
1772 : *
1773 : * This exists to provide some insulation between compute_stats routines
1774 : * and the actual storage of the sample data.
1775 : */
1776 : static Datum
1777 66213754 : std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull)
1778 : {
1779 66213754 : int attnum = stats->tupattnum;
1780 66213754 : HeapTuple tuple = stats->rows[rownum];
1781 66213754 : TupleDesc tupDesc = stats->tupDesc;
1782 :
1783 66213754 : return heap_getattr(tuple, attnum, tupDesc, isNull);
1784 : }
1785 :
1786 : /*
1787 : * Fetch function for analyzing index expressions.
1788 : *
1789 : * We have not bothered to construct index tuples, instead the data is
1790 : * just in Datum arrays.
1791 : */
1792 : static Datum
1793 74484 : ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull)
1794 : {
1795 : int i;
1796 :
1797 : /* exprvals and exprnulls are already offset for proper column */
1798 74484 : i = rownum * stats->rowstride;
1799 74484 : *isNull = stats->exprnulls[i];
1800 74484 : return stats->exprvals[i];
1801 : }
1802 :
1803 :
1804 : /*==========================================================================
1805 : *
1806 : * Code below this point represents the "standard" type-specific statistics
1807 : * analysis algorithms. This code can be replaced on a per-data-type basis
1808 : * by setting a nonzero value in pg_type.typanalyze.
1809 : *
1810 : *==========================================================================
1811 : */
1812 :
1813 :
1814 : /*
1815 : * To avoid consuming too much memory during analysis and/or too much space
1816 : * in the resulting pg_statistic rows, we ignore varlena datums that are wider
1817 : * than WIDTH_THRESHOLD (after detoasting!). This is legitimate for MCV
1818 : * and distinct-value calculations since a wide value is unlikely to be
1819 : * duplicated at all, much less be a most-common value. For the same reason,
1820 : * ignoring wide values will not affect our estimates of histogram bin
1821 : * boundaries very much.
1822 : */
1823 : #define WIDTH_THRESHOLD 1024
1824 :
1825 : #define swapInt(a,b) do {int _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1826 : #define swapDatum(a,b) do {Datum _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1827 :
1828 : /*
1829 : * Extra information used by the default analysis routines
1830 : */
1831 : typedef struct
1832 : {
1833 : int count; /* # of duplicates */
1834 : int first; /* values[] index of first occurrence */
1835 : } ScalarMCVItem;
1836 :
1837 : typedef struct
1838 : {
1839 : SortSupport ssup;
1840 : int *tupnoLink;
1841 : } CompareScalarsContext;
1842 :
1843 :
1844 : static void compute_trivial_stats(VacAttrStatsP stats,
1845 : AnalyzeAttrFetchFunc fetchfunc,
1846 : int samplerows,
1847 : double totalrows);
1848 : static void compute_distinct_stats(VacAttrStatsP stats,
1849 : AnalyzeAttrFetchFunc fetchfunc,
1850 : int samplerows,
1851 : double totalrows);
1852 : static void compute_scalar_stats(VacAttrStatsP stats,
1853 : AnalyzeAttrFetchFunc fetchfunc,
1854 : int samplerows,
1855 : double totalrows);
1856 : static int compare_scalars(const void *a, const void *b, void *arg);
1857 : static int compare_mcvs(const void *a, const void *b, void *arg);
1858 : static int analyze_mcv_list(int *mcv_counts,
1859 : int num_mcv,
1860 : double stadistinct,
1861 : double stanullfrac,
1862 : int samplerows,
1863 : double totalrows);
1864 :
1865 :
1866 : /*
1867 : * std_typanalyze -- the default type-specific typanalyze function
1868 : */
1869 : bool
1870 96340 : std_typanalyze(VacAttrStats *stats)
1871 : {
1872 : Oid ltopr;
1873 : Oid eqopr;
1874 : StdAnalyzeData *mystats;
1875 :
1876 : /* If the attstattarget column is negative, use the default value */
1877 96340 : if (stats->attstattarget < 0)
1878 95734 : stats->attstattarget = default_statistics_target;
1879 :
1880 : /* Look for default "<" and "=" operators for column's type */
1881 96340 : get_sort_group_operators(stats->attrtypid,
1882 : false, false, false,
1883 : <opr, &eqopr, NULL,
1884 : NULL);
1885 :
1886 : /* Save the operator info for compute_stats routines */
1887 96340 : mystats = (StdAnalyzeData *) palloc(sizeof(StdAnalyzeData));
1888 96340 : mystats->eqopr = eqopr;
1889 96340 : mystats->eqfunc = OidIsValid(eqopr) ? get_opcode(eqopr) : InvalidOid;
1890 96340 : mystats->ltopr = ltopr;
1891 96340 : stats->extra_data = mystats;
1892 :
1893 : /*
1894 : * Determine which standard statistics algorithm to use
1895 : */
1896 96340 : if (OidIsValid(eqopr) && OidIsValid(ltopr))
1897 : {
1898 : /* Seems to be a scalar datatype */
1899 93404 : stats->compute_stats = compute_scalar_stats;
1900 : /*--------------------
1901 : * The following choice of minrows is based on the paper
1902 : * "Random sampling for histogram construction: how much is enough?"
1903 : * by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in
1904 : * Proceedings of ACM SIGMOD International Conference on Management
1905 : * of Data, 1998, Pages 436-447. Their Corollary 1 to Theorem 5
1906 : * says that for table size n, histogram size k, maximum relative
1907 : * error in bin size f, and error probability gamma, the minimum
1908 : * random sample size is
1909 : * r = 4 * k * ln(2*n/gamma) / f^2
1910 : * Taking f = 0.5, gamma = 0.01, n = 10^6 rows, we obtain
1911 : * r = 305.82 * k
1912 : * Note that because of the log function, the dependence on n is
1913 : * quite weak; even at n = 10^12, a 300*k sample gives <= 0.66
1914 : * bin size error with probability 0.99. So there's no real need to
1915 : * scale for n, which is a good thing because we don't necessarily
1916 : * know it at this point.
1917 : *--------------------
1918 : */
1919 93404 : stats->minrows = 300 * stats->attstattarget;
1920 : }
1921 2936 : else if (OidIsValid(eqopr))
1922 : {
1923 : /* We can still recognize distinct values */
1924 2530 : stats->compute_stats = compute_distinct_stats;
1925 : /* Might as well use the same minrows as above */
1926 2530 : stats->minrows = 300 * stats->attstattarget;
1927 : }
1928 : else
1929 : {
1930 : /* Can't do much but the trivial stuff */
1931 406 : stats->compute_stats = compute_trivial_stats;
1932 : /* Might as well use the same minrows as above */
1933 406 : stats->minrows = 300 * stats->attstattarget;
1934 : }
1935 :
1936 96340 : return true;
1937 : }
1938 :
1939 :
1940 : /*
1941 : * compute_trivial_stats() -- compute very basic column statistics
1942 : *
1943 : * We use this when we cannot find a hash "=" operator for the datatype.
1944 : *
1945 : * We determine the fraction of non-null rows and the average datum width.
1946 : */
1947 : static void
1948 270 : compute_trivial_stats(VacAttrStatsP stats,
1949 : AnalyzeAttrFetchFunc fetchfunc,
1950 : int samplerows,
1951 : double totalrows)
1952 : {
1953 : int i;
1954 270 : int null_cnt = 0;
1955 270 : int nonnull_cnt = 0;
1956 270 : double total_width = 0;
1957 540 : bool is_varlena = (!stats->attrtype->typbyval &&
1958 270 : stats->attrtype->typlen == -1);
1959 540 : bool is_varwidth = (!stats->attrtype->typbyval &&
1960 270 : stats->attrtype->typlen < 0);
1961 :
1962 745290 : for (i = 0; i < samplerows; i++)
1963 : {
1964 : Datum value;
1965 : bool isnull;
1966 :
1967 745020 : vacuum_delay_point();
1968 :
1969 745020 : value = fetchfunc(stats, i, &isnull);
1970 :
1971 : /* Check for null/nonnull */
1972 745020 : if (isnull)
1973 : {
1974 478124 : null_cnt++;
1975 478124 : continue;
1976 : }
1977 266896 : nonnull_cnt++;
1978 :
1979 : /*
1980 : * If it's a variable-width field, add up widths for average width
1981 : * calculation. Note that if the value is toasted, we use the toasted
1982 : * width. We don't bother with this calculation if it's a fixed-width
1983 : * type.
1984 : */
1985 266896 : if (is_varlena)
1986 : {
1987 34312 : total_width += VARSIZE_ANY(DatumGetPointer(value));
1988 : }
1989 232584 : else if (is_varwidth)
1990 : {
1991 : /* must be cstring */
1992 0 : total_width += strlen(DatumGetCString(value)) + 1;
1993 : }
1994 : }
1995 :
1996 : /* We can only compute average width if we found some non-null values. */
1997 270 : if (nonnull_cnt > 0)
1998 : {
1999 122 : stats->stats_valid = true;
2000 : /* Do the simple null-frac and width stats */
2001 122 : stats->stanullfrac = (double) null_cnt / (double) samplerows;
2002 122 : if (is_varwidth)
2003 56 : stats->stawidth = total_width / (double) nonnull_cnt;
2004 : else
2005 66 : stats->stawidth = stats->attrtype->typlen;
2006 122 : stats->stadistinct = 0.0; /* "unknown" */
2007 : }
2008 148 : else if (null_cnt > 0)
2009 : {
2010 : /* We found only nulls; assume the column is entirely null */
2011 148 : stats->stats_valid = true;
2012 148 : stats->stanullfrac = 1.0;
2013 148 : if (is_varwidth)
2014 148 : stats->stawidth = 0; /* "unknown" */
2015 : else
2016 0 : stats->stawidth = stats->attrtype->typlen;
2017 148 : stats->stadistinct = 0.0; /* "unknown" */
2018 : }
2019 270 : }
2020 :
2021 :
2022 : /*
2023 : * compute_distinct_stats() -- compute column statistics including ndistinct
2024 : *
2025 : * We use this when we can find only an "=" operator for the datatype.
2026 : *
2027 : * We determine the fraction of non-null rows, the average width, the
2028 : * most common values, and the (estimated) number of distinct values.
2029 : *
2030 : * The most common values are determined by brute force: we keep a list
2031 : * of previously seen values, ordered by number of times seen, as we scan
2032 : * the samples. A newly seen value is inserted just after the last
2033 : * multiply-seen value, causing the bottommost (oldest) singly-seen value
2034 : * to drop off the list. The accuracy of this method, and also its cost,
2035 : * depend mainly on the length of the list we are willing to keep.
2036 : */
2037 : static void
2038 1850 : compute_distinct_stats(VacAttrStatsP stats,
2039 : AnalyzeAttrFetchFunc fetchfunc,
2040 : int samplerows,
2041 : double totalrows)
2042 : {
2043 : int i;
2044 1850 : int null_cnt = 0;
2045 1850 : int nonnull_cnt = 0;
2046 1850 : int toowide_cnt = 0;
2047 1850 : double total_width = 0;
2048 3128 : bool is_varlena = (!stats->attrtype->typbyval &&
2049 1278 : stats->attrtype->typlen == -1);
2050 3128 : bool is_varwidth = (!stats->attrtype->typbyval &&
2051 1278 : stats->attrtype->typlen < 0);
2052 : FmgrInfo f_cmpeq;
2053 : typedef struct
2054 : {
2055 : Datum value;
2056 : int count;
2057 : } TrackItem;
2058 : TrackItem *track;
2059 : int track_cnt,
2060 : track_max;
2061 1850 : int num_mcv = stats->attstattarget;
2062 1850 : StdAnalyzeData *mystats = (StdAnalyzeData *) stats->extra_data;
2063 :
2064 : /*
2065 : * We track up to 2*n values for an n-element MCV list; but at least 10
2066 : */
2067 1850 : track_max = 2 * num_mcv;
2068 1850 : if (track_max < 10)
2069 78 : track_max = 10;
2070 1850 : track = (TrackItem *) palloc(track_max * sizeof(TrackItem));
2071 1850 : track_cnt = 0;
2072 :
2073 1850 : fmgr_info(mystats->eqfunc, &f_cmpeq);
2074 :
2075 1237754 : for (i = 0; i < samplerows; i++)
2076 : {
2077 : Datum value;
2078 : bool isnull;
2079 : bool match;
2080 : int firstcount1,
2081 : j;
2082 :
2083 1235904 : vacuum_delay_point();
2084 :
2085 1235904 : value = fetchfunc(stats, i, &isnull);
2086 :
2087 : /* Check for null/nonnull */
2088 1235904 : if (isnull)
2089 : {
2090 1031330 : null_cnt++;
2091 1031330 : continue;
2092 : }
2093 204574 : nonnull_cnt++;
2094 :
2095 : /*
2096 : * If it's a variable-width field, add up widths for average width
2097 : * calculation. Note that if the value is toasted, we use the toasted
2098 : * width. We don't bother with this calculation if it's a fixed-width
2099 : * type.
2100 : */
2101 204574 : if (is_varlena)
2102 : {
2103 74566 : total_width += VARSIZE_ANY(DatumGetPointer(value));
2104 :
2105 : /*
2106 : * If the value is toasted, we want to detoast it just once to
2107 : * avoid repeated detoastings and resultant excess memory usage
2108 : * during the comparisons. Also, check to see if the value is
2109 : * excessively wide, and if so don't detoast at all --- just
2110 : * ignore the value.
2111 : */
2112 74566 : if (toast_raw_datum_size(value) > WIDTH_THRESHOLD)
2113 : {
2114 0 : toowide_cnt++;
2115 0 : continue;
2116 : }
2117 74566 : value = PointerGetDatum(PG_DETOAST_DATUM(value));
2118 : }
2119 130008 : else if (is_varwidth)
2120 : {
2121 : /* must be cstring */
2122 0 : total_width += strlen(DatumGetCString(value)) + 1;
2123 : }
2124 :
2125 : /*
2126 : * See if the value matches anything we're already tracking.
2127 : */
2128 204574 : match = false;
2129 204574 : firstcount1 = track_cnt;
2130 433964 : for (j = 0; j < track_cnt; j++)
2131 : {
2132 428750 : if (DatumGetBool(FunctionCall2Coll(&f_cmpeq,
2133 : stats->attrcollid,
2134 428750 : value, track[j].value)))
2135 : {
2136 199360 : match = true;
2137 199360 : break;
2138 : }
2139 229390 : if (j < firstcount1 && track[j].count == 1)
2140 3168 : firstcount1 = j;
2141 : }
2142 :
2143 204574 : if (match)
2144 : {
2145 : /* Found a match */
2146 199360 : track[j].count++;
2147 : /* This value may now need to "bubble up" in the track list */
2148 207540 : while (j > 0 && track[j].count > track[j - 1].count)
2149 : {
2150 8180 : swapDatum(track[j].value, track[j - 1].value);
2151 8180 : swapInt(track[j].count, track[j - 1].count);
2152 8180 : j--;
2153 : }
2154 : }
2155 : else
2156 : {
2157 : /* No match. Insert at head of count-1 list */
2158 5214 : if (track_cnt < track_max)
2159 4830 : track_cnt++;
2160 75516 : for (j = track_cnt - 1; j > firstcount1; j--)
2161 : {
2162 70302 : track[j].value = track[j - 1].value;
2163 70302 : track[j].count = track[j - 1].count;
2164 : }
2165 5214 : if (firstcount1 < track_cnt)
2166 : {
2167 5214 : track[firstcount1].value = value;
2168 5214 : track[firstcount1].count = 1;
2169 : }
2170 : }
2171 : }
2172 :
2173 : /* We can only compute real stats if we found some non-null values. */
2174 1850 : if (nonnull_cnt > 0)
2175 : {
2176 : int nmultiple,
2177 : summultiple;
2178 :
2179 1342 : stats->stats_valid = true;
2180 : /* Do the simple null-frac and width stats */
2181 1342 : stats->stanullfrac = (double) null_cnt / (double) samplerows;
2182 1342 : if (is_varwidth)
2183 770 : stats->stawidth = total_width / (double) nonnull_cnt;
2184 : else
2185 572 : stats->stawidth = stats->attrtype->typlen;
2186 :
2187 : /* Count the number of values we found multiple times */
2188 1342 : summultiple = 0;
2189 4978 : for (nmultiple = 0; nmultiple < track_cnt; nmultiple++)
2190 : {
2191 4324 : if (track[nmultiple].count == 1)
2192 688 : break;
2193 3636 : summultiple += track[nmultiple].count;
2194 : }
2195 :
2196 1342 : if (nmultiple == 0)
2197 : {
2198 : /*
2199 : * If we found no repeated non-null values, assume it's a unique
2200 : * column; but be sure to discount for any nulls we found.
2201 : */
2202 178 : stats->stadistinct = -1.0 * (1.0 - stats->stanullfrac);
2203 : }
2204 1164 : else if (track_cnt < track_max && toowide_cnt == 0 &&
2205 : nmultiple == track_cnt)
2206 : {
2207 : /*
2208 : * Our track list includes every value in the sample, and every
2209 : * value appeared more than once. Assume the column has just
2210 : * these values. (This case is meant to address columns with
2211 : * small, fixed sets of possible values, such as boolean or enum
2212 : * columns. If there are any values that appear just once in the
2213 : * sample, including too-wide values, we should assume that that's
2214 : * not what we're dealing with.)
2215 : */
2216 654 : stats->stadistinct = track_cnt;
2217 : }
2218 : else
2219 : {
2220 : /*----------
2221 : * Estimate the number of distinct values using the estimator
2222 : * proposed by Haas and Stokes in IBM Research Report RJ 10025:
2223 : * n*d / (n - f1 + f1*n/N)
2224 : * where f1 is the number of distinct values that occurred
2225 : * exactly once in our sample of n rows (from a total of N),
2226 : * and d is the total number of distinct values in the sample.
2227 : * This is their Duj1 estimator; the other estimators they
2228 : * recommend are considerably more complex, and are numerically
2229 : * very unstable when n is much smaller than N.
2230 : *
2231 : * In this calculation, we consider only non-nulls. We used to
2232 : * include rows with null values in the n and N counts, but that
2233 : * leads to inaccurate answers in columns with many nulls, and
2234 : * it's intuitively bogus anyway considering the desired result is
2235 : * the number of distinct non-null values.
2236 : *
2237 : * We assume (not very reliably!) that all the multiply-occurring
2238 : * values are reflected in the final track[] list, and the other
2239 : * nonnull values all appeared but once. (XXX this usually
2240 : * results in a drastic overestimate of ndistinct. Can we do
2241 : * any better?)
2242 : *----------
2243 : */
2244 510 : int f1 = nonnull_cnt - summultiple;
2245 510 : int d = f1 + nmultiple;
2246 510 : double n = samplerows - null_cnt;
2247 510 : double N = totalrows * (1.0 - stats->stanullfrac);
2248 : double stadistinct;
2249 :
2250 : /* N == 0 shouldn't happen, but just in case ... */
2251 510 : if (N > 0)
2252 510 : stadistinct = (n * d) / ((n - f1) + f1 * n / N);
2253 : else
2254 0 : stadistinct = 0;
2255 :
2256 : /* Clamp to sane range in case of roundoff error */
2257 510 : if (stadistinct < d)
2258 144 : stadistinct = d;
2259 510 : if (stadistinct > N)
2260 0 : stadistinct = N;
2261 : /* And round to integer */
2262 510 : stats->stadistinct = floor(stadistinct + 0.5);
2263 : }
2264 :
2265 : /*
2266 : * If we estimated the number of distinct values at more than 10% of
2267 : * the total row count (a very arbitrary limit), then assume that
2268 : * stadistinct should scale with the row count rather than be a fixed
2269 : * value.
2270 : */
2271 1342 : if (stats->stadistinct > 0.1 * totalrows)
2272 288 : stats->stadistinct = -(stats->stadistinct / totalrows);
2273 :
2274 : /*
2275 : * Decide how many values are worth storing as most-common values. If
2276 : * we are able to generate a complete MCV list (all the values in the
2277 : * sample will fit, and we think these are all the ones in the table),
2278 : * then do so. Otherwise, store only those values that are
2279 : * significantly more common than the values not in the list.
2280 : *
2281 : * Note: the first of these cases is meant to address columns with
2282 : * small, fixed sets of possible values, such as boolean or enum
2283 : * columns. If we can *completely* represent the column population by
2284 : * an MCV list that will fit into the stats target, then we should do
2285 : * so and thus provide the planner with complete information. But if
2286 : * the MCV list is not complete, it's generally worth being more
2287 : * selective, and not just filling it all the way up to the stats
2288 : * target.
2289 : */
2290 1342 : if (track_cnt < track_max && toowide_cnt == 0 &&
2291 1334 : stats->stadistinct > 0 &&
2292 : track_cnt <= num_mcv)
2293 : {
2294 : /* Track list includes all values seen, and all will fit */
2295 850 : num_mcv = track_cnt;
2296 : }
2297 : else
2298 : {
2299 : int *mcv_counts;
2300 :
2301 : /* Incomplete list; decide how many values are worth keeping */
2302 492 : if (num_mcv > track_cnt)
2303 434 : num_mcv = track_cnt;
2304 :
2305 492 : if (num_mcv > 0)
2306 : {
2307 492 : mcv_counts = (int *) palloc(num_mcv * sizeof(int));
2308 1324 : for (i = 0; i < num_mcv; i++)
2309 832 : mcv_counts[i] = track[i].count;
2310 :
2311 492 : num_mcv = analyze_mcv_list(mcv_counts, num_mcv,
2312 492 : stats->stadistinct,
2313 492 : stats->stanullfrac,
2314 : samplerows, totalrows);
2315 : }
2316 : }
2317 :
2318 : /* Generate MCV slot entry */
2319 1342 : if (num_mcv > 0)
2320 : {
2321 : MemoryContext old_context;
2322 : Datum *mcv_values;
2323 : float4 *mcv_freqs;
2324 :
2325 : /* Must copy the target values into anl_context */
2326 1334 : old_context = MemoryContextSwitchTo(stats->anl_context);
2327 1334 : mcv_values = (Datum *) palloc(num_mcv * sizeof(Datum));
2328 1334 : mcv_freqs = (float4 *) palloc(num_mcv * sizeof(float4));
2329 5860 : for (i = 0; i < num_mcv; i++)
2330 : {
2331 9052 : mcv_values[i] = datumCopy(track[i].value,
2332 4526 : stats->attrtype->typbyval,
2333 4526 : stats->attrtype->typlen);
2334 4526 : mcv_freqs[i] = (double) track[i].count / (double) samplerows;
2335 : }
2336 1334 : MemoryContextSwitchTo(old_context);
2337 :
2338 1334 : stats->stakind[0] = STATISTIC_KIND_MCV;
2339 1334 : stats->staop[0] = mystats->eqopr;
2340 1334 : stats->stacoll[0] = stats->attrcollid;
2341 1334 : stats->stanumbers[0] = mcv_freqs;
2342 1334 : stats->numnumbers[0] = num_mcv;
2343 1334 : stats->stavalues[0] = mcv_values;
2344 1334 : stats->numvalues[0] = num_mcv;
2345 :
2346 : /*
2347 : * Accept the defaults for stats->statypid and others. They have
2348 : * been set before we were called (see vacuum.h)
2349 : */
2350 : }
2351 : }
2352 508 : else if (null_cnt > 0)
2353 : {
2354 : /* We found only nulls; assume the column is entirely null */
2355 508 : stats->stats_valid = true;
2356 508 : stats->stanullfrac = 1.0;
2357 508 : if (is_varwidth)
2358 508 : stats->stawidth = 0; /* "unknown" */
2359 : else
2360 0 : stats->stawidth = stats->attrtype->typlen;
2361 508 : stats->stadistinct = 0.0; /* "unknown" */
2362 : }
2363 :
2364 : /* We don't need to bother cleaning up any of our temporary palloc's */
2365 1850 : }
2366 :
2367 :
2368 : /*
2369 : * compute_scalar_stats() -- compute column statistics
2370 : *
2371 : * We use this when we can find "=" and "<" operators for the datatype.
2372 : *
2373 : * We determine the fraction of non-null rows, the average width, the
2374 : * most common values, the (estimated) number of distinct values, the
2375 : * distribution histogram, and the correlation of physical to logical order.
2376 : *
2377 : * The desired stats can be determined fairly easily after sorting the
2378 : * data values into order.
2379 : */
2380 : static void
2381 68202 : compute_scalar_stats(VacAttrStatsP stats,
2382 : AnalyzeAttrFetchFunc fetchfunc,
2383 : int samplerows,
2384 : double totalrows)
2385 : {
2386 : int i;
2387 68202 : int null_cnt = 0;
2388 68202 : int nonnull_cnt = 0;
2389 68202 : int toowide_cnt = 0;
2390 68202 : double total_width = 0;
2391 85124 : bool is_varlena = (!stats->attrtype->typbyval &&
2392 16922 : stats->attrtype->typlen == -1);
2393 85124 : bool is_varwidth = (!stats->attrtype->typbyval &&
2394 16922 : stats->attrtype->typlen < 0);
2395 : double corr_xysum;
2396 : SortSupportData ssup;
2397 : ScalarItem *values;
2398 68202 : int values_cnt = 0;
2399 : int *tupnoLink;
2400 : ScalarMCVItem *track;
2401 68202 : int track_cnt = 0;
2402 68202 : int num_mcv = stats->attstattarget;
2403 68202 : int num_bins = stats->attstattarget;
2404 68202 : StdAnalyzeData *mystats = (StdAnalyzeData *) stats->extra_data;
2405 :
2406 68202 : values = (ScalarItem *) palloc(samplerows * sizeof(ScalarItem));
2407 68202 : tupnoLink = (int *) palloc(samplerows * sizeof(int));
2408 68202 : track = (ScalarMCVItem *) palloc(num_mcv * sizeof(ScalarMCVItem));
2409 :
2410 68202 : memset(&ssup, 0, sizeof(ssup));
2411 68202 : ssup.ssup_cxt = CurrentMemoryContext;
2412 68202 : ssup.ssup_collation = stats->attrcollid;
2413 68202 : ssup.ssup_nulls_first = false;
2414 :
2415 : /*
2416 : * For now, don't perform abbreviated key conversion, because full values
2417 : * are required for MCV slot generation. Supporting that optimization
2418 : * would necessitate teaching compare_scalars() to call a tie-breaker.
2419 : */
2420 68202 : ssup.abbreviate = false;
2421 :
2422 68202 : PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);
2423 :
2424 : /* Initial scan to find sortable values */
2425 60645228 : for (i = 0; i < samplerows; i++)
2426 : {
2427 : Datum value;
2428 : bool isnull;
2429 :
2430 60577026 : vacuum_delay_point();
2431 :
2432 60577026 : value = fetchfunc(stats, i, &isnull);
2433 :
2434 : /* Check for null/nonnull */
2435 60577026 : if (isnull)
2436 : {
2437 8090454 : null_cnt++;
2438 8119558 : continue;
2439 : }
2440 52486572 : nonnull_cnt++;
2441 :
2442 : /*
2443 : * If it's a variable-width field, add up widths for average width
2444 : * calculation. Note that if the value is toasted, we use the toasted
2445 : * width. We don't bother with this calculation if it's a fixed-width
2446 : * type.
2447 : */
2448 52486572 : if (is_varlena)
2449 : {
2450 6289318 : total_width += VARSIZE_ANY(DatumGetPointer(value));
2451 :
2452 : /*
2453 : * If the value is toasted, we want to detoast it just once to
2454 : * avoid repeated detoastings and resultant excess memory usage
2455 : * during the comparisons. Also, check to see if the value is
2456 : * excessively wide, and if so don't detoast at all --- just
2457 : * ignore the value.
2458 : */
2459 6289318 : if (toast_raw_datum_size(value) > WIDTH_THRESHOLD)
2460 : {
2461 29104 : toowide_cnt++;
2462 29104 : continue;
2463 : }
2464 6260214 : value = PointerGetDatum(PG_DETOAST_DATUM(value));
2465 : }
2466 46197254 : else if (is_varwidth)
2467 : {
2468 : /* must be cstring */
2469 0 : total_width += strlen(DatumGetCString(value)) + 1;
2470 : }
2471 :
2472 : /* Add it to the list to be sorted */
2473 52457468 : values[values_cnt].value = value;
2474 52457468 : values[values_cnt].tupno = values_cnt;
2475 52457468 : tupnoLink[values_cnt] = values_cnt;
2476 52457468 : values_cnt++;
2477 : }
2478 :
2479 : /* We can only compute real stats if we found some sortable values. */
2480 68202 : if (values_cnt > 0)
2481 : {
2482 : int ndistinct, /* # distinct values in sample */
2483 : nmultiple, /* # that appear multiple times */
2484 : num_hist,
2485 : dups_cnt;
2486 63582 : int slot_idx = 0;
2487 : CompareScalarsContext cxt;
2488 :
2489 : /* Sort the collected values */
2490 63582 : cxt.ssup = &ssup;
2491 63582 : cxt.tupnoLink = tupnoLink;
2492 63582 : qsort_interruptible(values, values_cnt, sizeof(ScalarItem),
2493 : compare_scalars, &cxt);
2494 :
2495 : /*
2496 : * Now scan the values in order, find the most common ones, and also
2497 : * accumulate ordering-correlation statistics.
2498 : *
2499 : * To determine which are most common, we first have to count the
2500 : * number of duplicates of each value. The duplicates are adjacent in
2501 : * the sorted list, so a brute-force approach is to compare successive
2502 : * datum values until we find two that are not equal. However, that
2503 : * requires N-1 invocations of the datum comparison routine, which are
2504 : * completely redundant with work that was done during the sort. (The
2505 : * sort algorithm must at some point have compared each pair of items
2506 : * that are adjacent in the sorted order; otherwise it could not know
2507 : * that it's ordered the pair correctly.) We exploit this by having
2508 : * compare_scalars remember the highest tupno index that each
2509 : * ScalarItem has been found equal to. At the end of the sort, a
2510 : * ScalarItem's tupnoLink will still point to itself if and only if it
2511 : * is the last item of its group of duplicates (since the group will
2512 : * be ordered by tupno).
2513 : */
2514 63582 : corr_xysum = 0;
2515 63582 : ndistinct = 0;
2516 63582 : nmultiple = 0;
2517 63582 : dups_cnt = 0;
2518 52521050 : for (i = 0; i < values_cnt; i++)
2519 : {
2520 52457468 : int tupno = values[i].tupno;
2521 :
2522 52457468 : corr_xysum += ((double) i) * ((double) tupno);
2523 52457468 : dups_cnt++;
2524 52457468 : if (tupnoLink[tupno] == tupno)
2525 : {
2526 : /* Reached end of duplicates of this value */
2527 10922398 : ndistinct++;
2528 10922398 : if (dups_cnt > 1)
2529 : {
2530 915536 : nmultiple++;
2531 915536 : if (track_cnt < num_mcv ||
2532 370492 : dups_cnt > track[track_cnt - 1].count)
2533 : {
2534 : /*
2535 : * Found a new item for the mcv list; find its
2536 : * position, bubbling down old items if needed. Loop
2537 : * invariant is that j points at an empty/ replaceable
2538 : * slot.
2539 : */
2540 : int j;
2541 :
2542 624424 : if (track_cnt < num_mcv)
2543 545044 : track_cnt++;
2544 8166864 : for (j = track_cnt - 1; j > 0; j--)
2545 : {
2546 8096878 : if (dups_cnt <= track[j - 1].count)
2547 554438 : break;
2548 7542440 : track[j].count = track[j - 1].count;
2549 7542440 : track[j].first = track[j - 1].first;
2550 : }
2551 624424 : track[j].count = dups_cnt;
2552 624424 : track[j].first = i + 1 - dups_cnt;
2553 : }
2554 : }
2555 10922398 : dups_cnt = 0;
2556 : }
2557 : }
2558 :
2559 63582 : stats->stats_valid = true;
2560 : /* Do the simple null-frac and width stats */
2561 63582 : stats->stanullfrac = (double) null_cnt / (double) samplerows;
2562 63582 : if (is_varwidth)
2563 9458 : stats->stawidth = total_width / (double) nonnull_cnt;
2564 : else
2565 54124 : stats->stawidth = stats->attrtype->typlen;
2566 :
2567 63582 : if (nmultiple == 0)
2568 : {
2569 : /*
2570 : * If we found no repeated non-null values, assume it's a unique
2571 : * column; but be sure to discount for any nulls we found.
2572 : */
2573 17104 : stats->stadistinct = -1.0 * (1.0 - stats->stanullfrac);
2574 : }
2575 46478 : else if (toowide_cnt == 0 && nmultiple == ndistinct)
2576 : {
2577 : /*
2578 : * Every value in the sample appeared more than once. Assume the
2579 : * column has just these values. (This case is meant to address
2580 : * columns with small, fixed sets of possible values, such as
2581 : * boolean or enum columns. If there are any values that appear
2582 : * just once in the sample, including too-wide values, we should
2583 : * assume that that's not what we're dealing with.)
2584 : */
2585 28688 : stats->stadistinct = ndistinct;
2586 : }
2587 : else
2588 : {
2589 : /*----------
2590 : * Estimate the number of distinct values using the estimator
2591 : * proposed by Haas and Stokes in IBM Research Report RJ 10025:
2592 : * n*d / (n - f1 + f1*n/N)
2593 : * where f1 is the number of distinct values that occurred
2594 : * exactly once in our sample of n rows (from a total of N),
2595 : * and d is the total number of distinct values in the sample.
2596 : * This is their Duj1 estimator; the other estimators they
2597 : * recommend are considerably more complex, and are numerically
2598 : * very unstable when n is much smaller than N.
2599 : *
2600 : * In this calculation, we consider only non-nulls. We used to
2601 : * include rows with null values in the n and N counts, but that
2602 : * leads to inaccurate answers in columns with many nulls, and
2603 : * it's intuitively bogus anyway considering the desired result is
2604 : * the number of distinct non-null values.
2605 : *
2606 : * Overwidth values are assumed to have been distinct.
2607 : *----------
2608 : */
2609 17790 : int f1 = ndistinct - nmultiple + toowide_cnt;
2610 17790 : int d = f1 + nmultiple;
2611 17790 : double n = samplerows - null_cnt;
2612 17790 : double N = totalrows * (1.0 - stats->stanullfrac);
2613 : double stadistinct;
2614 :
2615 : /* N == 0 shouldn't happen, but just in case ... */
2616 17790 : if (N > 0)
2617 17790 : stadistinct = (n * d) / ((n - f1) + f1 * n / N);
2618 : else
2619 0 : stadistinct = 0;
2620 :
2621 : /* Clamp to sane range in case of roundoff error */
2622 17790 : if (stadistinct < d)
2623 564 : stadistinct = d;
2624 17790 : if (stadistinct > N)
2625 0 : stadistinct = N;
2626 : /* And round to integer */
2627 17790 : stats->stadistinct = floor(stadistinct + 0.5);
2628 : }
2629 :
2630 : /*
2631 : * If we estimated the number of distinct values at more than 10% of
2632 : * the total row count (a very arbitrary limit), then assume that
2633 : * stadistinct should scale with the row count rather than be a fixed
2634 : * value.
2635 : */
2636 63582 : if (stats->stadistinct > 0.1 * totalrows)
2637 13164 : stats->stadistinct = -(stats->stadistinct / totalrows);
2638 :
2639 : /*
2640 : * Decide how many values are worth storing as most-common values. If
2641 : * we are able to generate a complete MCV list (all the values in the
2642 : * sample will fit, and we think these are all the ones in the table),
2643 : * then do so. Otherwise, store only those values that are
2644 : * significantly more common than the values not in the list.
2645 : *
2646 : * Note: the first of these cases is meant to address columns with
2647 : * small, fixed sets of possible values, such as boolean or enum
2648 : * columns. If we can *completely* represent the column population by
2649 : * an MCV list that will fit into the stats target, then we should do
2650 : * so and thus provide the planner with complete information. But if
2651 : * the MCV list is not complete, it's generally worth being more
2652 : * selective, and not just filling it all the way up to the stats
2653 : * target.
2654 : */
2655 63582 : if (track_cnt == ndistinct && toowide_cnt == 0 &&
2656 28050 : stats->stadistinct > 0 &&
2657 : track_cnt <= num_mcv)
2658 : {
2659 : /* Track list includes all values seen, and all will fit */
2660 25100 : num_mcv = track_cnt;
2661 : }
2662 : else
2663 : {
2664 : int *mcv_counts;
2665 :
2666 : /* Incomplete list; decide how many values are worth keeping */
2667 38482 : if (num_mcv > track_cnt)
2668 35024 : num_mcv = track_cnt;
2669 :
2670 38482 : if (num_mcv > 0)
2671 : {
2672 21378 : mcv_counts = (int *) palloc(num_mcv * sizeof(int));
2673 429514 : for (i = 0; i < num_mcv; i++)
2674 408136 : mcv_counts[i] = track[i].count;
2675 :
2676 21378 : num_mcv = analyze_mcv_list(mcv_counts, num_mcv,
2677 21378 : stats->stadistinct,
2678 21378 : stats->stanullfrac,
2679 : samplerows, totalrows);
2680 : }
2681 : }
2682 :
2683 : /* Generate MCV slot entry */
2684 63582 : if (num_mcv > 0)
2685 : {
2686 : MemoryContext old_context;
2687 : Datum *mcv_values;
2688 : float4 *mcv_freqs;
2689 :
2690 : /* Must copy the target values into anl_context */
2691 46428 : old_context = MemoryContextSwitchTo(stats->anl_context);
2692 46428 : mcv_values = (Datum *) palloc(num_mcv * sizeof(Datum));
2693 46428 : mcv_freqs = (float4 *) palloc(num_mcv * sizeof(float4));
2694 591252 : for (i = 0; i < num_mcv; i++)
2695 : {
2696 1089648 : mcv_values[i] = datumCopy(values[track[i].first].value,
2697 544824 : stats->attrtype->typbyval,
2698 544824 : stats->attrtype->typlen);
2699 544824 : mcv_freqs[i] = (double) track[i].count / (double) samplerows;
2700 : }
2701 46428 : MemoryContextSwitchTo(old_context);
2702 :
2703 46428 : stats->stakind[slot_idx] = STATISTIC_KIND_MCV;
2704 46428 : stats->staop[slot_idx] = mystats->eqopr;
2705 46428 : stats->stacoll[slot_idx] = stats->attrcollid;
2706 46428 : stats->stanumbers[slot_idx] = mcv_freqs;
2707 46428 : stats->numnumbers[slot_idx] = num_mcv;
2708 46428 : stats->stavalues[slot_idx] = mcv_values;
2709 46428 : stats->numvalues[slot_idx] = num_mcv;
2710 :
2711 : /*
2712 : * Accept the defaults for stats->statypid and others. They have
2713 : * been set before we were called (see vacuum.h)
2714 : */
2715 46428 : slot_idx++;
2716 : }
2717 :
2718 : /*
2719 : * Generate a histogram slot entry if there are at least two distinct
2720 : * values not accounted for in the MCV list. (This ensures the
2721 : * histogram won't collapse to empty or a singleton.)
2722 : */
2723 63582 : num_hist = ndistinct - num_mcv;
2724 63582 : if (num_hist > num_bins)
2725 10656 : num_hist = num_bins + 1;
2726 63582 : if (num_hist >= 2)
2727 : {
2728 : MemoryContext old_context;
2729 : Datum *hist_values;
2730 : int nvals;
2731 : int pos,
2732 : posfrac,
2733 : delta,
2734 : deltafrac;
2735 :
2736 : /* Sort the MCV items into position order to speed next loop */
2737 28108 : qsort_interruptible(track, num_mcv, sizeof(ScalarMCVItem),
2738 : compare_mcvs, NULL);
2739 :
2740 : /*
2741 : * Collapse out the MCV items from the values[] array.
2742 : *
2743 : * Note we destroy the values[] array here... but we don't need it
2744 : * for anything more. We do, however, still need values_cnt.
2745 : * nvals will be the number of remaining entries in values[].
2746 : */
2747 28108 : if (num_mcv > 0)
2748 : {
2749 : int src,
2750 : dest;
2751 : int j;
2752 :
2753 14828 : src = dest = 0;
2754 14828 : j = 0; /* index of next interesting MCV item */
2755 526674 : while (src < values_cnt)
2756 : {
2757 : int ncopy;
2758 :
2759 511846 : if (j < num_mcv)
2760 : {
2761 500448 : int first = track[j].first;
2762 :
2763 500448 : if (src >= first)
2764 : {
2765 : /* advance past this MCV item */
2766 365106 : src = first + track[j].count;
2767 365106 : j++;
2768 365106 : continue;
2769 : }
2770 135342 : ncopy = first - src;
2771 : }
2772 : else
2773 11398 : ncopy = values_cnt - src;
2774 146740 : memmove(&values[dest], &values[src],
2775 : ncopy * sizeof(ScalarItem));
2776 146740 : src += ncopy;
2777 146740 : dest += ncopy;
2778 : }
2779 14828 : nvals = dest;
2780 : }
2781 : else
2782 13280 : nvals = values_cnt;
2783 : Assert(nvals >= num_hist);
2784 :
2785 : /* Must copy the target values into anl_context */
2786 28108 : old_context = MemoryContextSwitchTo(stats->anl_context);
2787 28108 : hist_values = (Datum *) palloc(num_hist * sizeof(Datum));
2788 :
2789 : /*
2790 : * The object of this loop is to copy the first and last values[]
2791 : * entries along with evenly-spaced values in between. So the
2792 : * i'th value is values[(i * (nvals - 1)) / (num_hist - 1)]. But
2793 : * computing that subscript directly risks integer overflow when
2794 : * the stats target is more than a couple thousand. Instead we
2795 : * add (nvals - 1) / (num_hist - 1) to pos at each step, tracking
2796 : * the integral and fractional parts of the sum separately.
2797 : */
2798 28108 : delta = (nvals - 1) / (num_hist - 1);
2799 28108 : deltafrac = (nvals - 1) % (num_hist - 1);
2800 28108 : pos = posfrac = 0;
2801 :
2802 1499726 : for (i = 0; i < num_hist; i++)
2803 : {
2804 2943236 : hist_values[i] = datumCopy(values[pos].value,
2805 1471618 : stats->attrtype->typbyval,
2806 1471618 : stats->attrtype->typlen);
2807 1471618 : pos += delta;
2808 1471618 : posfrac += deltafrac;
2809 1471618 : if (posfrac >= (num_hist - 1))
2810 : {
2811 : /* fractional part exceeds 1, carry to integer part */
2812 486968 : pos++;
2813 486968 : posfrac -= (num_hist - 1);
2814 : }
2815 : }
2816 :
2817 28108 : MemoryContextSwitchTo(old_context);
2818 :
2819 28108 : stats->stakind[slot_idx] = STATISTIC_KIND_HISTOGRAM;
2820 28108 : stats->staop[slot_idx] = mystats->ltopr;
2821 28108 : stats->stacoll[slot_idx] = stats->attrcollid;
2822 28108 : stats->stavalues[slot_idx] = hist_values;
2823 28108 : stats->numvalues[slot_idx] = num_hist;
2824 :
2825 : /*
2826 : * Accept the defaults for stats->statypid and others. They have
2827 : * been set before we were called (see vacuum.h)
2828 : */
2829 28108 : slot_idx++;
2830 : }
2831 :
2832 : /* Generate a correlation entry if there are multiple values */
2833 63582 : if (values_cnt > 1)
2834 : {
2835 : MemoryContext old_context;
2836 : float4 *corrs;
2837 : double corr_xsum,
2838 : corr_x2sum;
2839 :
2840 : /* Must copy the target values into anl_context */
2841 59708 : old_context = MemoryContextSwitchTo(stats->anl_context);
2842 59708 : corrs = (float4 *) palloc(sizeof(float4));
2843 59708 : MemoryContextSwitchTo(old_context);
2844 :
2845 : /*----------
2846 : * Since we know the x and y value sets are both
2847 : * 0, 1, ..., values_cnt-1
2848 : * we have sum(x) = sum(y) =
2849 : * (values_cnt-1)*values_cnt / 2
2850 : * and sum(x^2) = sum(y^2) =
2851 : * (values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
2852 : *----------
2853 : */
2854 59708 : corr_xsum = ((double) (values_cnt - 1)) *
2855 59708 : ((double) values_cnt) / 2.0;
2856 59708 : corr_x2sum = ((double) (values_cnt - 1)) *
2857 59708 : ((double) values_cnt) * (double) (2 * values_cnt - 1) / 6.0;
2858 :
2859 : /* And the correlation coefficient reduces to */
2860 59708 : corrs[0] = (values_cnt * corr_xysum - corr_xsum * corr_xsum) /
2861 59708 : (values_cnt * corr_x2sum - corr_xsum * corr_xsum);
2862 :
2863 59708 : stats->stakind[slot_idx] = STATISTIC_KIND_CORRELATION;
2864 59708 : stats->staop[slot_idx] = mystats->ltopr;
2865 59708 : stats->stacoll[slot_idx] = stats->attrcollid;
2866 59708 : stats->stanumbers[slot_idx] = corrs;
2867 59708 : stats->numnumbers[slot_idx] = 1;
2868 59708 : slot_idx++;
2869 : }
2870 : }
2871 4620 : else if (nonnull_cnt > 0)
2872 : {
2873 : /* We found some non-null values, but they were all too wide */
2874 : Assert(nonnull_cnt == toowide_cnt);
2875 284 : stats->stats_valid = true;
2876 : /* Do the simple null-frac and width stats */
2877 284 : stats->stanullfrac = (double) null_cnt / (double) samplerows;
2878 284 : if (is_varwidth)
2879 284 : stats->stawidth = total_width / (double) nonnull_cnt;
2880 : else
2881 0 : stats->stawidth = stats->attrtype->typlen;
2882 : /* Assume all too-wide values are distinct, so it's a unique column */
2883 284 : stats->stadistinct = -1.0 * (1.0 - stats->stanullfrac);
2884 : }
2885 4336 : else if (null_cnt > 0)
2886 : {
2887 : /* We found only nulls; assume the column is entirely null */
2888 4336 : stats->stats_valid = true;
2889 4336 : stats->stanullfrac = 1.0;
2890 4336 : if (is_varwidth)
2891 3756 : stats->stawidth = 0; /* "unknown" */
2892 : else
2893 580 : stats->stawidth = stats->attrtype->typlen;
2894 4336 : stats->stadistinct = 0.0; /* "unknown" */
2895 : }
2896 :
2897 : /* We don't need to bother cleaning up any of our temporary palloc's */
2898 68202 : }
2899 :
2900 : /*
2901 : * Comparator for sorting ScalarItems
2902 : *
2903 : * Aside from sorting the items, we update the tupnoLink[] array
2904 : * whenever two ScalarItems are found to contain equal datums. The array
2905 : * is indexed by tupno; for each ScalarItem, it contains the highest
2906 : * tupno that that item's datum has been found to be equal to. This allows
2907 : * us to avoid additional comparisons in compute_scalar_stats().
2908 : */
2909 : static int
2910 480226756 : compare_scalars(const void *a, const void *b, void *arg)
2911 : {
2912 480226756 : Datum da = ((const ScalarItem *) a)->value;
2913 480226756 : int ta = ((const ScalarItem *) a)->tupno;
2914 480226756 : Datum db = ((const ScalarItem *) b)->value;
2915 480226756 : int tb = ((const ScalarItem *) b)->tupno;
2916 480226756 : CompareScalarsContext *cxt = (CompareScalarsContext *) arg;
2917 : int compare;
2918 :
2919 480226756 : compare = ApplySortComparator(da, false, db, false, cxt->ssup);
2920 480226756 : if (compare != 0)
2921 183360548 : return compare;
2922 :
2923 : /*
2924 : * The two datums are equal, so update cxt->tupnoLink[].
2925 : */
2926 296866208 : if (cxt->tupnoLink[ta] < tb)
2927 43331228 : cxt->tupnoLink[ta] = tb;
2928 296866208 : if (cxt->tupnoLink[tb] < ta)
2929 3027492 : cxt->tupnoLink[tb] = ta;
2930 :
2931 : /*
2932 : * For equal datums, sort by tupno
2933 : */
2934 296866208 : return ta - tb;
2935 : }
2936 :
2937 : /*
2938 : * Comparator for sorting ScalarMCVItems by position
2939 : */
2940 : static int
2941 1882594 : compare_mcvs(const void *a, const void *b, void *arg)
2942 : {
2943 1882594 : int da = ((const ScalarMCVItem *) a)->first;
2944 1882594 : int db = ((const ScalarMCVItem *) b)->first;
2945 :
2946 1882594 : return da - db;
2947 : }
2948 :
2949 : /*
2950 : * Analyze the list of common values in the sample and decide how many are
2951 : * worth storing in the table's MCV list.
2952 : *
2953 : * mcv_counts is assumed to be a list of the counts of the most common values
2954 : * seen in the sample, starting with the most common. The return value is the
2955 : * number that are significantly more common than the values not in the list,
2956 : * and which are therefore deemed worth storing in the table's MCV list.
2957 : */
2958 : static int
2959 21870 : analyze_mcv_list(int *mcv_counts,
2960 : int num_mcv,
2961 : double stadistinct,
2962 : double stanullfrac,
2963 : int samplerows,
2964 : double totalrows)
2965 : {
2966 : double ndistinct_table;
2967 : double sumcount;
2968 : int i;
2969 :
2970 : /*
2971 : * If the entire table was sampled, keep the whole list. This also
2972 : * protects us against division by zero in the code below.
2973 : */
2974 21870 : if (samplerows == totalrows || totalrows <= 1.0)
2975 21028 : return num_mcv;
2976 :
2977 : /* Re-extract the estimated number of distinct nonnull values in table */
2978 842 : ndistinct_table = stadistinct;
2979 842 : if (ndistinct_table < 0)
2980 158 : ndistinct_table = -ndistinct_table * totalrows;
2981 :
2982 : /*
2983 : * Exclude the least common values from the MCV list, if they are not
2984 : * significantly more common than the estimated selectivity they would
2985 : * have if they weren't in the list. All non-MCV values are assumed to be
2986 : * equally common, after taking into account the frequencies of all the
2987 : * values in the MCV list and the number of nulls (c.f. eqsel()).
2988 : *
2989 : * Here sumcount tracks the total count of all but the last (least common)
2990 : * value in the MCV list, allowing us to determine the effect of excluding
2991 : * that value from the list.
2992 : *
2993 : * Note that we deliberately do this by removing values from the full
2994 : * list, rather than starting with an empty list and adding values,
2995 : * because the latter approach can fail to add any values if all the most
2996 : * common values have around the same frequency and make up the majority
2997 : * of the table, so that the overall average frequency of all values is
2998 : * roughly the same as that of the common values. This would lead to any
2999 : * uncommon values being significantly overestimated.
3000 : */
3001 842 : sumcount = 0.0;
3002 1796 : for (i = 0; i < num_mcv - 1; i++)
3003 954 : sumcount += mcv_counts[i];
3004 :
3005 1012 : while (num_mcv > 0)
3006 : {
3007 : double selec,
3008 : otherdistinct,
3009 : N,
3010 : n,
3011 : K,
3012 : variance,
3013 : stddev;
3014 :
3015 : /*
3016 : * Estimated selectivity the least common value would have if it
3017 : * wasn't in the MCV list (c.f. eqsel()).
3018 : */
3019 1012 : selec = 1.0 - sumcount / samplerows - stanullfrac;
3020 1012 : if (selec < 0.0)
3021 0 : selec = 0.0;
3022 1012 : if (selec > 1.0)
3023 0 : selec = 1.0;
3024 1012 : otherdistinct = ndistinct_table - (num_mcv - 1);
3025 1012 : if (otherdistinct > 1)
3026 1012 : selec /= otherdistinct;
3027 :
3028 : /*
3029 : * If the value is kept in the MCV list, its population frequency is
3030 : * assumed to equal its sample frequency. We use the lower end of a
3031 : * textbook continuity-corrected Wald-type confidence interval to
3032 : * determine if that is significantly more common than the non-MCV
3033 : * frequency --- specifically we assume the population frequency is
3034 : * highly likely to be within around 2 standard errors of the sample
3035 : * frequency, which equates to an interval of 2 standard deviations
3036 : * either side of the sample count, plus an additional 0.5 for the
3037 : * continuity correction. Since we are sampling without replacement,
3038 : * this is a hypergeometric distribution.
3039 : *
3040 : * XXX: Empirically, this approach seems to work quite well, but it
3041 : * may be worth considering more advanced techniques for estimating
3042 : * the confidence interval of the hypergeometric distribution.
3043 : */
3044 1012 : N = totalrows;
3045 1012 : n = samplerows;
3046 1012 : K = N * mcv_counts[num_mcv - 1] / n;
3047 1012 : variance = n * K * (N - K) * (N - n) / (N * N * (N - 1));
3048 1012 : stddev = sqrt(variance);
3049 :
3050 1012 : if (mcv_counts[num_mcv - 1] > selec * samplerows + 2 * stddev + 0.5)
3051 : {
3052 : /*
3053 : * The value is significantly more common than the non-MCV
3054 : * selectivity would suggest. Keep it, and all the other more
3055 : * common values in the list.
3056 : */
3057 784 : break;
3058 : }
3059 : else
3060 : {
3061 : /* Discard this value and consider the next least common value */
3062 228 : num_mcv--;
3063 228 : if (num_mcv == 0)
3064 58 : break;
3065 170 : sumcount -= mcv_counts[num_mcv - 1];
3066 : }
3067 : }
3068 842 : return num_mcv;
3069 : }
|
