src/backend/commands/analyze.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * analyze.c
   4  *        the Postgres statistics generator
   5  *
   6  * Portions Copyright (c) 1996-2004, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/commands/analyze.c,v 1.75 2004/08/29 04:12:29 momjian Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include <math.h>
  18
  19 #include "access/heapam.h"
  20 #include "access/tuptoaster.h"
  21 #include "catalog/catalog.h"
  22 #include "catalog/catname.h"
  23 #include "catalog/index.h"
  24 #include "catalog/indexing.h"
  25 #include "catalog/namespace.h"
  26 #include "catalog/pg_operator.h"
  27 #include "commands/vacuum.h"
  28 #include "executor/executor.h"
  29 #include "miscadmin.h"
  30 #include "parser/parse_expr.h"
  31 #include "parser/parse_oper.h"
  32 #include "parser/parse_relation.h"
  33 #include "utils/acl.h"
  34 #include "utils/builtins.h"
  35 #include "utils/datum.h"
  36 #include "utils/fmgroids.h"
  37 #include "utils/lsyscache.h"
  38 #include "utils/syscache.h"
  39 #include "utils/tuplesort.h"
  40
  41
  42 /* Data structure for Algorithm S from Knuth 3.4.2 */
  43 typedef struct
  44 {
  45         BlockNumber     N;                              /* number of blocks, known in advance */
  46         int                     n;                              /* desired sample size */
  47         BlockNumber     t;                              /* current block number */
  48         int                     m;                              /* blocks selected so far */
  49 } BlockSamplerData;
  50 typedef BlockSamplerData *BlockSampler;
  51
  52 /* Per-index data for ANALYZE */
  53 typedef struct AnlIndexData
  54 {
  55         IndexInfo  *indexInfo;          /* BuildIndexInfo result */
  56         double          tupleFract;             /* fraction of rows for partial index */
  57         VacAttrStats **vacattrstats;    /* index attrs to analyze */
  58         int                     attr_cnt;
  59 } AnlIndexData;
  60
  61
  62 /* Default statistics target (GUC parameter) */
  63 int                     default_statistics_target = 10;
  64
  65 static int      elevel = -1;
  66
  67 static MemoryContext anl_context = NULL;
  68
  69
  70 static void BlockSampler_Init(BlockSampler bs, BlockNumber nblocks,
  71                                                           int samplesize);
  72 static bool BlockSampler_HasMore(BlockSampler bs);
  73 static BlockNumber BlockSampler_Next(BlockSampler bs);
  74 static void compute_index_stats(Relation onerel, double totalrows,
  75                                                                 AnlIndexData *indexdata, int nindexes,
  76                                                                 HeapTuple *rows, int numrows,
  77                                                                 MemoryContext col_context);
  78 static VacAttrStats *examine_attribute(Relation onerel, int attnum);
  79 static int acquire_sample_rows(Relation onerel, HeapTuple *rows,
  80                                         int targrows, double *totalrows);
  81 static double random_fract(void);
  82 static double init_selection_state(int n);
  83 static double get_next_S(double t, int n, double *stateptr);
  84 static int      compare_rows(const void *a, const void *b);
  85 static void update_attstats(Oid relid, int natts, VacAttrStats **vacattrstats);
  86 static Datum std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
  87 static Datum ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
  88
  89 static bool std_typanalyze(VacAttrStats *stats);
  90
  91
  92 /*
  93  *      analyze_rel() -- analyze one relation
  94  */
  95 void
  96 analyze_rel(Oid relid, VacuumStmt *vacstmt)
  97 {
  98         Relation        onerel;
  99         int                     attr_cnt,
 100                                 tcnt,
 101                                 i,
 102                                 ind;
 103         Relation   *Irel;
 104         int                     nindexes;
 105         bool            hasindex;
 106         bool            analyzableindex;
 107         VacAttrStats **vacattrstats;
 108         AnlIndexData *indexdata;
 109         int                     targrows,
 110                                 numrows;
 111         double          totalrows;
 112         HeapTuple  *rows;
 113
 114         if (vacstmt->verbose)
 115                 elevel = INFO;
 116         else
 117                 elevel = DEBUG2;
 118
 119         /*
 120          * Use the current context for storing analysis info.  vacuum.c
 121          * ensures that this context will be cleared when I return, thus
 122          * releasing the memory allocated here.
 123          */
 124         anl_context = CurrentMemoryContext;
 125
 126         /*
 127          * Check for user-requested abort.      Note we want this to be inside a
 128          * transaction, so xact.c doesn't issue useless WARNING.
 129          */
 130         CHECK_FOR_INTERRUPTS();
 131
 132         /*
 133          * Race condition -- if the pg_class tuple has gone away since the
 134          * last time we saw it, we don't need to process it.
 135          */
 136         if (!SearchSysCacheExists(RELOID,
 137                                                           ObjectIdGetDatum(relid),
 138                                                           0, 0, 0))
 139                 return;
 140
 141         /*
 142          * Open the class, getting only a read lock on it, and check
 143          * permissions. Permissions check should match vacuum's check!
 144          */
 145         onerel = relation_open(relid, AccessShareLock);
 146
 147         if (!(pg_class_ownercheck(RelationGetRelid(onerel), GetUserId()) ||
 148                   (pg_database_ownercheck(MyDatabaseId, GetUserId()) && !onerel->rd_rel->relisshared)))
 149         {
 150                 /* No need for a WARNING if we already complained during VACUUM */
 151                 if (!vacstmt->vacuum)
 152                         ereport(WARNING,
 153                                         (errmsg("skipping \"%s\" --- only table or database owner can analyze it",
 154                                                         RelationGetRelationName(onerel))));
 155                 relation_close(onerel, AccessShareLock);
 156                 return;
 157         }
 158
 159         /*
 160          * Check that it's a plain table; we used to do this in
 161          * get_rel_oids() but seems safer to check after we've locked the
 162          * relation.
 163          */
 164         if (onerel->rd_rel->relkind != RELKIND_RELATION)
 165         {
 166                 /* No need for a WARNING if we already complained during VACUUM */
 167                 if (!vacstmt->vacuum)
 168                         ereport(WARNING,
 169                                         (errmsg("skipping \"%s\" --- cannot analyze indexes, views, or special system tables",
 170                                                         RelationGetRelationName(onerel))));
 171                 relation_close(onerel, AccessShareLock);
 172                 return;
 173         }
 174
 175         /*
 176          * Silently ignore tables that are temp tables of other backends ---
 177          * trying to analyze these is rather pointless, since their contents
 178          * are probably not up-to-date on disk.  (We don't throw a warning
 179          * here; it would just lead to chatter during a database-wide
 180          * ANALYZE.)
 181          */
 182         if (isOtherTempNamespace(RelationGetNamespace(onerel)))
 183         {
 184                 relation_close(onerel, AccessShareLock);
 185                 return;
 186         }
 187
 188         /*
 189          * We can ANALYZE any table except pg_statistic. See update_attstats
 190          */
 191         if (IsSystemNamespace(RelationGetNamespace(onerel)) &&
 192          strcmp(RelationGetRelationName(onerel), StatisticRelationName) == 0)
 193         {
 194                 relation_close(onerel, AccessShareLock);
 195                 return;
 196         }
 197
 198         ereport(elevel,
 199                         (errmsg("analyzing \"%s.%s\"",
 200                                         get_namespace_name(RelationGetNamespace(onerel)),
 201                                         RelationGetRelationName(onerel))));
 202
 203         /*
 204          * Determine which columns to analyze
 205          *
 206          * Note that system attributes are never analyzed.
 207          */
 208         if (vacstmt->va_cols != NIL)
 209         {
 210                 ListCell   *le;
 211
 212                 vacattrstats = (VacAttrStats **) palloc(list_length(vacstmt->va_cols) *
 213                                                                                                 sizeof(VacAttrStats *));
 214                 tcnt = 0;
 215                 foreach(le, vacstmt->va_cols)
 216                 {
 217                         char       *col = strVal(lfirst(le));
 218
 219                         i = attnameAttNum(onerel, col, false);
 220                         vacattrstats[tcnt] = examine_attribute(onerel, i);
 221                         if (vacattrstats[tcnt] != NULL)
 222                                 tcnt++;
 223                 }
 224                 attr_cnt = tcnt;
 225         }
 226         else
 227         {
 228                 attr_cnt = onerel->rd_att->natts;
 229                 vacattrstats = (VacAttrStats **)
 230                         palloc(attr_cnt * sizeof(VacAttrStats *));
 231                 tcnt = 0;
 232                 for (i = 1; i <= attr_cnt; i++)
 233                 {
 234                         vacattrstats[tcnt] = examine_attribute(onerel, i);
 235                         if (vacattrstats[tcnt] != NULL)
 236                                 tcnt++;
 237                 }
 238                 attr_cnt = tcnt;
 239         }
 240
 241         /*
 242          * Open all indexes of the relation, and see if there are any analyzable
 243          * columns in the indexes.  We do not analyze index columns if there was
 244          * an explicit column list in the ANALYZE command, however.
 245          */
 246         vac_open_indexes(onerel, &nindexes, &Irel);
 247         hasindex = (nindexes > 0);
 248         indexdata = NULL;
 249         analyzableindex = false;
 250         if (hasindex)
 251         {
 252                 indexdata = (AnlIndexData *) palloc0(nindexes * sizeof(AnlIndexData));
 253                 for (ind = 0; ind < nindexes; ind++)
 254                 {
 255                         AnlIndexData *thisdata = &indexdata[ind];
 256                         IndexInfo *indexInfo;
 257
 258                         thisdata->indexInfo = indexInfo = BuildIndexInfo(Irel[ind]);
 259                         thisdata->tupleFract = 1.0;             /* fix later if partial */
 260                         if (indexInfo->ii_Expressions != NIL && vacstmt->va_cols == NIL)
 261                         {
 262                                 ListCell   *indexpr_item = list_head(indexInfo->ii_Expressions);
 263
 264                                 thisdata->vacattrstats = (VacAttrStats **)
 265                                         palloc(indexInfo->ii_NumIndexAttrs * sizeof(VacAttrStats *));
 266                                 tcnt = 0;
 267                                 for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
 268                                 {
 269                                         int                     keycol = indexInfo->ii_KeyAttrNumbers[i];
 270
 271                                         if (keycol == 0)
 272                                         {
 273                                                 /* Found an index expression */
 274                                                 Node       *indexkey;
 275
 276                                                 if (indexpr_item == NULL)       /* shouldn't happen */
 277                                                         elog(ERROR, "too few entries in indexprs list");
 278                                                 indexkey = (Node *) lfirst(indexpr_item);
 279                                                 indexpr_item = lnext(indexpr_item);
 280
 281                                                 /*
 282                                                  * Can't analyze if the opclass uses a storage type
 283                                                  * different from the expression result type.  We'd
 284                                                  * get confused because the type shown in pg_attribute
 285                                                  * for the index column doesn't match what we are
 286                                                  * getting from the expression.  Perhaps this can be
 287                                                  * fixed someday, but for now, punt.
 288                                                  */
 289                                                 if (exprType(indexkey) !=
 290                                                         Irel[ind]->rd_att->attrs[i]->atttypid)
 291                                                         continue;
 292
 293                                                 thisdata->vacattrstats[tcnt] =
 294                                                         examine_attribute(Irel[ind], i+1);
 295                                                 if (thisdata->vacattrstats[tcnt] != NULL)
 296                                                 {
 297                                                         tcnt++;
 298                                                         analyzableindex = true;
 299                                                 }
 300                                         }
 301                                 }
 302                                 thisdata->attr_cnt = tcnt;
 303                         }
 304                 }
 305         }
 306
 307         /*
 308          * Quit if no analyzable columns
 309          */
 310         if (attr_cnt <= 0 && !analyzableindex)
 311         {
 312                 vac_close_indexes(nindexes, Irel);
 313                 relation_close(onerel, AccessShareLock);
 314                 return;
 315         }
 316
 317         /*
 318          * Determine how many rows we need to sample, using the worst case
 319          * from all analyzable columns.  We use a lower bound of 100 rows to
 320          * avoid possible overflow in Vitter's algorithm.
 321          */
 322         targrows = 100;
 323         for (i = 0; i < attr_cnt; i++)
 324         {
 325                 if (targrows < vacattrstats[i]->minrows)
 326                         targrows = vacattrstats[i]->minrows;
 327         }
 328         for (ind = 0; ind < nindexes; ind++)
 329         {
 330                 AnlIndexData *thisdata = &indexdata[ind];
 331
 332                 for (i = 0; i < thisdata->attr_cnt; i++)
 333                 {
 334                         if (targrows < thisdata->vacattrstats[i]->minrows)
 335                                 targrows = thisdata->vacattrstats[i]->minrows;
 336                 }
 337         }
 338
 339         /*
 340          * Acquire the sample rows
 341          */
 342         rows = (HeapTuple *) palloc(targrows * sizeof(HeapTuple));
 343         numrows = acquire_sample_rows(onerel, rows, targrows, &totalrows);
 344
 345         /*
 346          * Compute the statistics.      Temporary results during the calculations
 347          * for each column are stored in a child context.  The calc routines
 348          * are responsible to make sure that whatever they store into the
 349          * VacAttrStats structure is allocated in anl_context.
 350          */
 351         if (numrows > 0)
 352         {
 353                 MemoryContext col_context,
 354                                         old_context;
 355
 356                 col_context = AllocSetContextCreate(anl_context,
 357                                                                                         "Analyze Column",
 358                                                                                         ALLOCSET_DEFAULT_MINSIZE,
 359                                                                                         ALLOCSET_DEFAULT_INITSIZE,
 360                                                                                         ALLOCSET_DEFAULT_MAXSIZE);
 361                 old_context = MemoryContextSwitchTo(col_context);
 362
 363                 for (i = 0; i < attr_cnt; i++)
 364                 {
 365                         VacAttrStats *stats = vacattrstats[i];
 366
 367                         stats->rows = rows;
 368                         stats->tupDesc = onerel->rd_att;
 369                         (*stats->compute_stats) (stats,
 370                                                                          std_fetch_func,
 371                                                                          numrows,
 372                                                                          totalrows);
 373                         MemoryContextResetAndDeleteChildren(col_context);
 374                 }
 375
 376                 if (hasindex)
 377                         compute_index_stats(onerel, totalrows,
 378                                                                 indexdata, nindexes,
 379                                                                 rows, numrows,
 380                                                                 col_context);
 381
 382                 MemoryContextSwitchTo(old_context);
 383                 MemoryContextDelete(col_context);
 384
 385                 /*
 386                  * Emit the completed stats rows into pg_statistic, replacing any
 387                  * previous statistics for the target columns.  (If there are
 388                  * stats in pg_statistic for columns we didn't process, we leave
 389                  * them alone.)
 390                  */
 391                 update_attstats(relid, attr_cnt, vacattrstats);
 392
 393                 for (ind = 0; ind < nindexes; ind++)
 394                 {
 395                         AnlIndexData *thisdata = &indexdata[ind];
 396
 397                         update_attstats(RelationGetRelid(Irel[ind]),
 398                                                         thisdata->attr_cnt, thisdata->vacattrstats);
 399                 }
 400         }
 401
 402         /*
 403          * If we are running a standalone ANALYZE, update pages/tuples stats
 404          * in pg_class.  We know the accurate page count from the smgr,
 405          * but only an approximate number of tuples; therefore, if we are part
 406          * of VACUUM ANALYZE do *not* overwrite the accurate count already
 407          * inserted by VACUUM.  The same consideration applies to indexes.
 408          */
 409         if (!vacstmt->vacuum)
 410         {
 411                 vac_update_relstats(RelationGetRelid(onerel),
 412                                                         RelationGetNumberOfBlocks(onerel),
 413                                                         totalrows,
 414                                                         hasindex);
 415                 for (ind = 0; ind < nindexes; ind++)
 416                 {
 417                         AnlIndexData *thisdata = &indexdata[ind];
 418                         double          totalindexrows;
 419
 420                         totalindexrows = ceil(thisdata->tupleFract * totalrows);
 421                         vac_update_relstats(RelationGetRelid(Irel[ind]),
 422                                                                 RelationGetNumberOfBlocks(Irel[ind]),
 423                                                                 totalindexrows,
 424                                                                 false);
 425                 }
 426         }
 427
 428         /* Done with indexes */
 429         vac_close_indexes(nindexes, Irel);
 430
 431         /*
 432          * Close source relation now, but keep lock so that no one deletes it
 433          * before we commit.  (If someone did, they'd fail to clean up the
 434          * entries we made in pg_statistic.)
 435          */
 436         relation_close(onerel, NoLock);
 437 }
 438
 439 /*
 440  * Compute statistics about indexes of a relation
 441  */
 442 static void
 443 compute_index_stats(Relation onerel, double totalrows,
 444                                         AnlIndexData *indexdata, int nindexes,
 445                                         HeapTuple *rows, int numrows,
 446                                         MemoryContext col_context)
 447 {
 448         MemoryContext ind_context,
 449                 old_context;
 450         TupleDesc       heapDescriptor;
 451         Datum           attdata[INDEX_MAX_KEYS];
 452         char            nulls[INDEX_MAX_KEYS];
 453         int                     ind,
 454                                 i;
 455
 456         heapDescriptor = RelationGetDescr(onerel);
 457
 458         ind_context = AllocSetContextCreate(anl_context,
 459                                                                                 "Analyze Index",
 460                                                                                 ALLOCSET_DEFAULT_MINSIZE,
 461                                                                                 ALLOCSET_DEFAULT_INITSIZE,
 462                                                                                 ALLOCSET_DEFAULT_MAXSIZE);
 463         old_context = MemoryContextSwitchTo(ind_context);
 464
 465         for (ind = 0; ind < nindexes; ind++)
 466         {
 467                 AnlIndexData *thisdata = &indexdata[ind];
 468                 IndexInfo *indexInfo = thisdata->indexInfo;
 469                 int                     attr_cnt = thisdata->attr_cnt;
 470                 TupleTable      tupleTable;
 471                 TupleTableSlot *slot;
 472                 EState     *estate;
 473                 ExprContext *econtext;
 474                 List       *predicate;
 475                 Datum      *exprvals;
 476                 bool       *exprnulls;
 477                 int                     numindexrows,
 478                                         tcnt,
 479                                         rowno;
 480                 double          totalindexrows;
 481
 482                 /* Ignore index if no columns to analyze and not partial */
 483                 if (attr_cnt == 0 && indexInfo->ii_Predicate == NIL)
 484                         continue;
 485
 486                 /*
 487                  * Need an EState for evaluation of index expressions and
 488                  * partial-index predicates.  Create it in the per-index context
 489                  * to be sure it gets cleaned up at the bottom of the loop.
 490                  */
 491                 estate = CreateExecutorState();
 492                 econtext = GetPerTupleExprContext(estate);
 493                 /* Need a slot to hold the current heap tuple, too */
 494                 tupleTable = ExecCreateTupleTable(1);
 495                 slot = ExecAllocTableSlot(tupleTable);
 496                 ExecSetSlotDescriptor(slot, heapDescriptor, false);
 497
 498                 /* Arrange for econtext's scan tuple to be the tuple under test */
 499                 econtext->ecxt_scantuple = slot;
 500
 501                 /* Set up execution state for predicate. */
 502                 predicate = (List *)
 503                         ExecPrepareExpr((Expr *) indexInfo->ii_Predicate,
 504                                                         estate);
 505
 506                 /* Compute and save index expression values */
 507                 exprvals = (Datum *) palloc(numrows * attr_cnt * sizeof(Datum));
 508                 exprnulls = (bool *) palloc(numrows * attr_cnt * sizeof(bool));
 509                 numindexrows = 0;
 510                 tcnt = 0;
 511                 for (rowno = 0; rowno < numrows; rowno++)
 512                 {
 513                         HeapTuple       heapTuple = rows[rowno];
 514
 515                         /* Set up for predicate or expression evaluation */
 516                         ExecStoreTuple(heapTuple, slot, InvalidBuffer, false);
 517
 518                         /* If index is partial, check predicate */
 519                         if (predicate != NIL)
 520                         {
 521                                 if (!ExecQual(predicate, econtext, false))
 522                                         continue;
 523                         }
 524                         numindexrows++;
 525
 526                         if (attr_cnt > 0)
 527                         {
 528                                 /*
 529                                  * Evaluate the index row to compute expression values.
 530                                  * We could do this by hand, but FormIndexDatum is convenient.
 531                                  */
 532                                 FormIndexDatum(indexInfo,
 533                                                            heapTuple,
 534                                                            heapDescriptor,
 535                                                            estate,
 536                                                            attdata,
 537                                                            nulls);
 538                                 /*
 539                                  * Save just the columns we care about.
 540                                  */
 541                                 for (i = 0; i < attr_cnt; i++)
 542                                 {
 543                                         VacAttrStats *stats = thisdata->vacattrstats[i];
 544                                         int     attnum = stats->attr->attnum;
 545
 546                                         exprvals[tcnt] = attdata[attnum-1];
 547                                         exprnulls[tcnt] = (nulls[attnum-1] == 'n');
 548                                         tcnt++;
 549                                 }
 550                         }
 551                 }
 552
 553                 /*
 554                  * Having counted the number of rows that pass the predicate in
 555                  * the sample, we can estimate the total number of rows in the index.
 556                  */
 557                 thisdata->tupleFract = (double) numindexrows / (double) numrows;
 558                 totalindexrows = ceil(thisdata->tupleFract * totalrows);
 559
 560                 /*
 561                  * Now we can compute the statistics for the expression columns.
 562                  */
 563                 if (numindexrows > 0)
 564                 {
 565                         MemoryContextSwitchTo(col_context);
 566                         for (i = 0; i < attr_cnt; i++)
 567                         {
 568                                 VacAttrStats *stats = thisdata->vacattrstats[i];
 569
 570                                 stats->exprvals = exprvals + i;
 571                                 stats->exprnulls = exprnulls + i;
 572                                 stats->rowstride = attr_cnt;
 573                                 (*stats->compute_stats) (stats,
 574                                                                                  ind_fetch_func,
 575                                                                                  numindexrows,
 576                                                                                  totalindexrows);
 577                                 MemoryContextResetAndDeleteChildren(col_context);
 578                         }
 579                 }
 580
 581                 /* And clean up */
 582                 MemoryContextSwitchTo(ind_context);
 583
 584                 ExecDropTupleTable(tupleTable, true);
 585                 FreeExecutorState(estate);
 586                 MemoryContextResetAndDeleteChildren(ind_context);
 587         }
 588
 589         MemoryContextSwitchTo(old_context);
 590         MemoryContextDelete(ind_context);
 591 }
 592
 593 /*
 594  * examine_attribute -- pre-analysis of a single column
 595  *
 596  * Determine whether the column is analyzable; if so, create and initialize
 597  * a VacAttrStats struct for it.  If not, return NULL.
 598  */
 599 static VacAttrStats *
 600 examine_attribute(Relation onerel, int attnum)
 601 {
 602         Form_pg_attribute attr = onerel->rd_att->attrs[attnum - 1];
 603         HeapTuple       typtuple;
 604         VacAttrStats *stats;
 605         bool            ok;
 606
 607         /* Never analyze dropped columns */
 608         if (attr->attisdropped)
 609                 return NULL;
 610
 611         /* Don't analyze column if user has specified not to */
 612         if (attr->attstattarget == 0)
 613                 return NULL;
 614
 615         /*
 616          * Create the VacAttrStats struct.
 617          */
 618         stats = (VacAttrStats *) palloc0(sizeof(VacAttrStats));
 619         stats->attr = (Form_pg_attribute) palloc(ATTRIBUTE_TUPLE_SIZE);
 620         memcpy(stats->attr, attr, ATTRIBUTE_TUPLE_SIZE);
 621         typtuple = SearchSysCache(TYPEOID,
 622                                                           ObjectIdGetDatum(attr->atttypid),
 623                                                           0, 0, 0);
 624         if (!HeapTupleIsValid(typtuple))
 625                 elog(ERROR, "cache lookup failed for type %u", attr->atttypid);
 626         stats->attrtype = (Form_pg_type) palloc(sizeof(FormData_pg_type));
 627         memcpy(stats->attrtype, GETSTRUCT(typtuple), sizeof(FormData_pg_type));
 628         ReleaseSysCache(typtuple);
 629         stats->anl_context = anl_context;
 630         stats->tupattnum = attnum;
 631
 632         /*
 633          * Call the type-specific typanalyze function.  If none is specified,
 634          * use std_typanalyze().
 635          */
 636         if (OidIsValid(stats->attrtype->typanalyze))
 637                 ok = DatumGetBool(OidFunctionCall1(stats->attrtype->typanalyze,
 638                                                                                    PointerGetDatum(stats)));
 639         else
 640                 ok = std_typanalyze(stats);
 641
 642         if (!ok || stats->compute_stats == NULL || stats->minrows <= 0)
 643         {
 644                 pfree(stats->attrtype);
 645                 pfree(stats->attr);
 646                 pfree(stats);
 647                 return NULL;
 648         }
 649
 650         return stats;
 651 }
 652
 653 /*
 654  * BlockSampler_Init -- prepare for random sampling of blocknumbers
 655  *
 656  * BlockSampler is used for stage one of our new two-stage tuple
 657  * sampling mechanism as discussed on pgsql-hackers 2004-04-02 (subject
 658  * "Large DB").  It selects a random sample of samplesize blocks out of
 659  * the nblocks blocks in the table.  If the table has less than
 660  * samplesize blocks, all blocks are selected.
 661  *
 662  * Since we know the total number of blocks in advance, we can use the
 663  * straightforward Algorithm S from Knuth 3.4.2, rather than Vitter's
 664  * algorithm.
 665  */
 666 static void
 667 BlockSampler_Init(BlockSampler bs, BlockNumber nblocks, int samplesize)
 668 {
 669         bs->N = nblocks;                        /* measured table size */
 670         /*
 671          * If we decide to reduce samplesize for tables that have less or
 672          * not much more than samplesize blocks, here is the place to do
 673          * it.
 674          */
 675         bs->n = samplesize;
 676         bs->t = 0;                                      /* blocks scanned so far */
 677         bs->m = 0;                                      /* blocks selected so far */
 678 }
 679
 680 static bool
 681 BlockSampler_HasMore(BlockSampler bs)
 682 {
 683         return (bs->t < bs->N) && (bs->m < bs->n);
 684 }
 685
 686 static BlockNumber
 687 BlockSampler_Next(BlockSampler bs)
 688 {
 689         BlockNumber     K = bs->N - bs->t;              /* remaining blocks */
 690         int                     k = bs->n - bs->m;              /* blocks still to sample */
 691         double          p;                                              /* probability to skip block */
 692         double          V;                                              /* random */
 693
 694         Assert(BlockSampler_HasMore(bs));       /* hence K > 0 and k > 0 */
 695
 696         if ((BlockNumber) k >= K)
 697         {
 698                 /* need all the rest */
 699                 bs->m++;
 700                 return bs->t++;
 701         }
 702
 703         /*----------
 704          * It is not obvious that this code matches Knuth's Algorithm S.
 705          * Knuth says to skip the current block with probability 1 - k/K.
 706          * If we are to skip, we should advance t (hence decrease K), and
 707          * repeat the same probabilistic test for the next block.  The naive
 708          * implementation thus requires a random_fract() call for each block
 709          * number.  But we can reduce this to one random_fract() call per
 710          * selected block, by noting that each time the while-test succeeds,
 711          * we can reinterpret V as a uniform random number in the range 0 to p.
 712          * Therefore, instead of choosing a new V, we just adjust p to be
 713          * the appropriate fraction of its former value, and our next loop
 714          * makes the appropriate probabilistic test.
 715          *
 716          * We have initially K > k > 0.  If the loop reduces K to equal k,
 717          * the next while-test must fail since p will become exactly zero
 718          * (we assume there will not be roundoff error in the division).
 719          * (Note: Knuth suggests a "<=" loop condition, but we use "<" just
 720          * to be doubly sure about roundoff error.)  Therefore K cannot become
 721          * less than k, which means that we cannot fail to select enough blocks.
 722          *----------
 723          */
 724         V = random_fract();
 725         p = 1.0 - (double) k / (double) K;
 726         while (V < p)
 727         {
 728                 /* skip */
 729                 bs->t++;
 730                 K--;                                    /* keep K == N - t */
 731
 732                 /* adjust p to be new cutoff point in reduced range */
 733                 p *= 1.0 - (double) k / (double) K;
 734         }
 735
 736         /* select */
 737         bs->m++;
 738         return bs->t++;
 739 }
 740
 741 /*
 742  * acquire_sample_rows -- acquire a random sample of rows from the table
 743  *
 744  * As of May 2004 we use a new two-stage method:  Stage one selects up
 745  * to targrows random blocks (or all blocks, if there aren't so many).
 746  * Stage two scans these blocks and uses the Vitter algorithm to create
 747  * a random sample of targrows rows (or less, if there are less in the
 748  * sample of blocks).  The two stages are executed simultaneously: each
 749  * block is processed as soon as stage one returns its number and while
 750  * the rows are read stage two controls which ones are to be inserted
 751  * into the sample.
 752  *
 753  * Although every row has an equal chance of ending up in the final
 754  * sample, this sampling method is not perfect: not every possible
 755  * sample has an equal chance of being selected.  For large relations
 756  * the number of different blocks represented by the sample tends to be
 757  * too small.  We can live with that for now.  Improvements are welcome.
 758  *
 759  * We also estimate the total number of rows in the table, and return that
 760  * into *totalrows.  An important property of this sampling method is that
 761  * because we do look at a statistically unbiased set of blocks, we should
 762  * get an unbiased estimate of the average number of live rows per block.
 763  * The previous sampling method put too much credence in the row density near
 764  * the start of the table.
 765  *
 766  * The returned list of tuples is in order by physical position in the table.
 767  * (We will rely on this later to derive correlation estimates.)
 768  */
 769 static int
 770 acquire_sample_rows(Relation onerel, HeapTuple *rows, int targrows,
 771                                         double *totalrows)
 772 {
 773         int                     numrows = 0;                                    /* # rows collected */
 774         double          liverows = 0;                                   /* # rows seen */
 775         double          deadrows = 0;
 776         double          rowstoskip = -1;                                /* -1 means not set yet */
 777         BlockNumber     totalblocks;
 778         BlockSamplerData bs;
 779         double          rstate;
 780
 781         Assert(targrows > 1);
 782
 783         totalblocks = RelationGetNumberOfBlocks(onerel);
 784
 785         /* Prepare for sampling block numbers */
 786         BlockSampler_Init(&bs, totalblocks, targrows);
 787         /* Prepare for sampling rows */
 788         rstate = init_selection_state(targrows);
 789
 790         /* Outer loop over blocks to sample */
 791         while (BlockSampler_HasMore(&bs))
 792         {
 793                 BlockNumber targblock = BlockSampler_Next(&bs);
 794                 Buffer          targbuffer;
 795                 Page            targpage;
 796                 OffsetNumber targoffset,
 797                                         maxoffset;
 798
 799                 vacuum_delay_point();
 800
 801                 /*
 802                  * We must maintain a pin on the target page's buffer to ensure
 803                  * that the maxoffset value stays good (else concurrent VACUUM
 804                  * might delete tuples out from under us).      Hence, pin the page
 805                  * until we are done looking at it.  We don't maintain a lock on
 806                  * the page, so tuples could get added to it, but we ignore such
 807                  * tuples.
 808                  */
 809                 targbuffer = ReadBuffer(onerel, targblock);
 810                 if (!BufferIsValid(targbuffer))
 811                         elog(ERROR, "ReadBuffer failed");
 812                 LockBuffer(targbuffer, BUFFER_LOCK_SHARE);
 813                 targpage = BufferGetPage(targbuffer);
 814                 maxoffset = PageGetMaxOffsetNumber(targpage);
 815                 LockBuffer(targbuffer, BUFFER_LOCK_UNLOCK);
 816
 817                 /* Inner loop over all tuples on the selected page */
 818                 for (targoffset = FirstOffsetNumber; targoffset <= maxoffset; targoffset++)
 819                 {
 820                         HeapTupleData targtuple;
 821                         Buffer          tupbuffer;
 822
 823                         ItemPointerSet(&targtuple.t_self, targblock, targoffset);
 824                         if (heap_fetch(onerel, SnapshotNow, &targtuple, &tupbuffer,
 825                                                    false, NULL))
 826                         {
 827                                 /*
 828                                  * The first targrows live rows are simply copied into the
 829                                  * reservoir.
 830                                  * Then we start replacing tuples in the sample until
 831                                  * we reach the end of the relation.  This algorithm is
 832                                  * from Jeff Vitter's paper (see full citation below).
 833                                  * It works by repeatedly computing the number of tuples
 834                                  * to skip before selecting a tuple, which replaces a
 835                                  * randomly chosen element of the reservoir (current
 836                                  * set of tuples).  At all times the reservoir is a true
 837                                  * random sample of the tuples we've passed over so far,
 838                                  * so when we fall off the end of the relation we're done.
 839                                  */
 840                                 if (numrows < targrows)
 841                                         rows[numrows++] = heap_copytuple(&targtuple);
 842                                 else
 843                                 {
 844                                         /*
 845                                          * t in Vitter's paper is the number of records already
 846                                          * processed.  If we need to compute a new S value, we
 847                                          * must use the not-yet-incremented value of liverows
 848                                          * as t.
 849                                          */
 850                                         if (rowstoskip < 0)
 851                                                 rowstoskip = get_next_S(liverows, targrows, &rstate);
 852
 853                                         if (rowstoskip <= 0)
 854                                         {
 855                                                 /*
 856                                                  * Found a suitable tuple, so save it,
 857                                                  * replacing one old tuple at random
 858                                                  */
 859                                                 int     k = (int) (targrows * random_fract());
 860
 861                                                 Assert(k >= 0 && k < targrows);
 862                                                 heap_freetuple(rows[k]);
 863                                                 rows[k] = heap_copytuple(&targtuple);
 864                                         }
 865
 866                                         rowstoskip -= 1;
 867                                 }
 868
 869                                 /* must release the extra pin acquired by heap_fetch */
 870                                 ReleaseBuffer(tupbuffer);
 871
 872                                 liverows += 1;
 873                         }
 874                         else
 875                         {
 876                                 /*
 877                                  * Count dead rows, but not empty slots.  This information is
 878                                  * currently not used, but it seems likely we'll want it
 879                                  * someday.
 880                                  */
 881                                 if (targtuple.t_data != NULL)
 882                                         deadrows += 1;
 883                         }
 884                 }
 885
 886                 /* Now release the initial pin on the page */
 887                 ReleaseBuffer(targbuffer);
 888         }
 889
 890         /*
 891          * If we didn't find as many tuples as we wanted then we're done.
 892          * No sort is needed, since they're already in order.
 893          *
 894          * Otherwise we need to sort the collected tuples by position
 895          * (itempointer).  It's not worth worrying about corner cases
 896          * where the tuples are already sorted.
 897          */
 898         if (numrows == targrows)
 899                 qsort((void *) rows, numrows, sizeof(HeapTuple), compare_rows);
 900
 901         /*
 902          * Estimate total number of live rows in relation.
 903          */
 904         if (bs.m > 0)
 905                 *totalrows = floor((liverows * totalblocks) / bs.m + 0.5);
 906         else
 907                 *totalrows = 0.0;
 908
 909         /*
 910          * Emit some interesting relation info
 911          */
 912         ereport(elevel,
 913                         (errmsg("\"%s\": scanned %d of %u pages, "
 914                                         "containing %.0f live rows and %.0f dead rows; "
 915                                         "%d rows in sample, %.0f estimated total rows",
 916                                         RelationGetRelationName(onerel),
 917                                         bs.m, totalblocks,
 918                                         liverows, deadrows,
 919                                         numrows, *totalrows)));
 920
 921         return numrows;
 922 }
 923
 924 /* Select a random value R uniformly distributed in 0 < R < 1 */
 925 static double
 926 random_fract(void)
 927 {
 928         long            z;
 929
 930         /* random() can produce endpoint values, try again if so */
 931         do
 932         {
 933                 z = random();
 934         } while (z <= 0 || z >= MAX_RANDOM_VALUE);
 935         return (double) z / (double) MAX_RANDOM_VALUE;
 936 }
 937
 938 /*
 939  * These two routines embody Algorithm Z from "Random sampling with a
 940  * reservoir" by Jeffrey S. Vitter, in ACM Trans. Math. Softw. 11, 1
 941  * (Mar. 1985), Pages 37-57.  Vitter describes his algorithm in terms
 942  * of the count S of records to skip before processing another record.
 943  * It is computed primarily based on t, the number of records already read.
 944  * The only extra state needed between calls is W, a random state variable.
 945  *
 946  * init_selection_state computes the initial W value.
 947  *
 948  * Given that we've already read t records (t >= n), get_next_S
 949  * determines the number of records to skip before the next record is
 950  * processed.
 951  */
 952 static double
 953 init_selection_state(int n)
 954 {
 955         /* Initial value of W (for use when Algorithm Z is first applied) */
 956         return exp(-log(random_fract()) / n);
 957 }
 958
 959 static double
 960 get_next_S(double t, int n, double *stateptr)
 961 {
 962         double          S;
 963
 964         /* The magic constant here is T from Vitter's paper */
 965         if (t <= (22.0 * n))
 966         {
 967                 /* Process records using Algorithm X until t is large enough */
 968                 double          V,
 969                                         quot;
 970
 971                 V = random_fract();             /* Generate V */
 972                 S = 0;
 973                 t += 1;
 974                 /* Note: "num" in Vitter's code is always equal to t - n */
 975                 quot = (t - (double) n) / t;
 976                 /* Find min S satisfying (4.1) */
 977                 while (quot > V)
 978                 {
 979                         S += 1;
 980                         t += 1;
 981                         quot *= (t - (double) n) / t;
 982                 }
 983         }
 984         else
 985         {
 986                 /* Now apply Algorithm Z */
 987                 double          W = *stateptr;
 988                 double          term = t - (double) n + 1;
 989
 990                 for (;;)
 991                 {
 992                         double          numer,
 993                                                 numer_lim,
 994                                                 denom;
 995                         double          U,
 996                                                 X,
 997                                                 lhs,
 998                                                 rhs,
 999                                                 y,
1000                                                 tmp;
1001
1002                         /* Generate U and X */
1003                         U = random_fract();
1004                         X = t * (W - 1.0);
1005                         S = floor(X);           /* S is tentatively set to floor(X) */
1006                         /* Test if U <= h(S)/cg(X) in the manner of (6.3) */
1007                         tmp = (t + 1) / term;
1008                         lhs = exp(log(((U * tmp * tmp) * (term + S)) / (t + X)) / n);
1009                         rhs = (((t + X) / (term + S)) * term) / t;
1010                         if (lhs <= rhs)
1011                         {
1012                                 W = rhs / lhs;
1013                                 break;
1014                         }
1015                         /* Test if U <= f(S)/cg(X) */
1016                         y = (((U * (t + 1)) / term) * (t + S + 1)) / (t + X);
1017                         if ((double) n < S)
1018                         {
1019                                 denom = t;
1020                                 numer_lim = term + S;
1021                         }
1022                         else
1023                         {
1024                                 denom = t - (double) n + S;
1025                                 numer_lim = t + 1;
1026                         }
1027                         for (numer = t + S; numer >= numer_lim; numer -= 1)
1028                         {
1029                                 y *= numer / denom;
1030                                 denom -= 1;
1031                         }
1032                         W = exp(-log(random_fract()) / n);      /* Generate W in advance */
1033                         if (exp(log(y) / n) <= (t + X) / t)
1034                                 break;
1035                 }
1036                 *stateptr = W;
1037         }
1038         return S;
1039 }
1040
1041 /*
1042  * qsort comparator for sorting rows[] array
1043  */
1044 static int
1045 compare_rows(const void *a, const void *b)
1046 {
1047         HeapTuple       ha = *(HeapTuple *) a;
1048         HeapTuple       hb = *(HeapTuple *) b;
1049         BlockNumber ba = ItemPointerGetBlockNumber(&ha->t_self);
1050         OffsetNumber oa = ItemPointerGetOffsetNumber(&ha->t_self);
1051         BlockNumber bb = ItemPointerGetBlockNumber(&hb->t_self);
1052         OffsetNumber ob = ItemPointerGetOffsetNumber(&hb->t_self);
1053
1054         if (ba < bb)
1055                 return -1;
1056         if (ba > bb)
1057                 return 1;
1058         if (oa < ob)
1059                 return -1;
1060         if (oa > ob)
1061                 return 1;
1062         return 0;
1063 }
1064
1065
1066 /*
1067  *      update_attstats() -- update attribute statistics for one relation
1068  *
1069  *              Statistics are stored in several places: the pg_class row for the
1070  *              relation has stats about the whole relation, and there is a
1071  *              pg_statistic row for each (non-system) attribute that has ever
1072  *              been analyzed.  The pg_class values are updated by VACUUM, not here.
1073  *
1074  *              pg_statistic rows are just added or updated normally.  This means
1075  *              that pg_statistic will probably contain some deleted rows at the
1076  *              completion of a vacuum cycle, unless it happens to get vacuumed last.
1077  *
1078  *              To keep things simple, we punt for pg_statistic, and don't try
1079  *              to compute or store rows for pg_statistic itself in pg_statistic.
1080  *              This could possibly be made to work, but it's not worth the trouble.
1081  *              Note analyze_rel() has seen to it that we won't come here when
1082  *              vacuuming pg_statistic itself.
1083  *
1084  *              Note: if two backends concurrently try to analyze the same relation,
1085  *              the second one is likely to fail here with a "tuple concurrently
1086  *              updated" error.  This is slightly annoying, but no real harm is done.
1087  *              We could prevent the problem by using a stronger lock on the
1088  *              relation for ANALYZE (ie, ShareUpdateExclusiveLock instead
1089  *              of AccessShareLock); but that cure seems worse than the disease,
1090  *              especially now that ANALYZE doesn't start a new transaction
1091  *              for each relation.      The lock could be held for a long time...
1092  */
1093 static void
1094 update_attstats(Oid relid, int natts, VacAttrStats **vacattrstats)
1095 {
1096         Relation        sd;
1097         int                     attno;
1098
1099         if (natts <= 0)
1100                 return;                                 /* nothing to do */
1101
1102         sd = heap_openr(StatisticRelationName, RowExclusiveLock);
1103
1104         for (attno = 0; attno < natts; attno++)
1105         {
1106                 VacAttrStats *stats = vacattrstats[attno];
1107                 HeapTuple       stup,
1108                                         oldtup;
1109                 int                     i,
1110                                         k,
1111                                         n;
1112                 Datum           values[Natts_pg_statistic];
1113                 char            nulls[Natts_pg_statistic];
1114                 char            replaces[Natts_pg_statistic];
1115
1116                 /* Ignore attr if we weren't able to collect stats */
1117                 if (!stats->stats_valid)
1118                         continue;
1119
1120                 /*
1121                  * Construct a new pg_statistic tuple
1122                  */
1123                 for (i = 0; i < Natts_pg_statistic; ++i)
1124                 {
1125                         nulls[i] = ' ';
1126                         replaces[i] = 'r';
1127                 }
1128
1129                 i = 0;
1130                 values[i++] = ObjectIdGetDatum(relid);  /* starelid */
1131                 values[i++] = Int16GetDatum(stats->attr->attnum);       /* staattnum */
1132                 values[i++] = Float4GetDatum(stats->stanullfrac);       /* stanullfrac */
1133                 values[i++] = Int32GetDatum(stats->stawidth);   /* stawidth */
1134                 values[i++] = Float4GetDatum(stats->stadistinct);       /* stadistinct */
1135                 for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1136                 {
1137                         values[i++] = Int16GetDatum(stats->stakind[k]);         /* stakindN */
1138                 }
1139                 for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1140                 {
1141                         values[i++] = ObjectIdGetDatum(stats->staop[k]);        /* staopN */
1142                 }
1143                 for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1144                 {
1145                         int                     nnum = stats->numnumbers[k];
1146
1147                         if (nnum > 0)
1148                         {
1149                                 Datum      *numdatums = (Datum *) palloc(nnum * sizeof(Datum));
1150                                 ArrayType  *arry;
1151
1152                                 for (n = 0; n < nnum; n++)
1153                                         numdatums[n] = Float4GetDatum(stats->stanumbers[k][n]);
1154                                 /* XXX knows more than it should about type float4: */
1155                                 arry = construct_array(numdatums, nnum,
1156                                                                            FLOAT4OID,
1157                                                                            sizeof(float4), false, 'i');
1158                                 values[i++] = PointerGetDatum(arry);    /* stanumbersN */
1159                         }
1160                         else
1161                         {
1162                                 nulls[i] = 'n';
1163                                 values[i++] = (Datum) 0;
1164                         }
1165                 }
1166                 for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
1167                 {
1168                         if (stats->numvalues[k] > 0)
1169                         {
1170                                 ArrayType  *arry;
1171
1172                                 arry = construct_array(stats->stavalues[k],
1173                                                                            stats->numvalues[k],
1174                                                                            stats->attr->atttypid,
1175                                                                            stats->attrtype->typlen,
1176                                                                            stats->attrtype->typbyval,
1177                                                                            stats->attrtype->typalign);
1178                                 values[i++] = PointerGetDatum(arry);    /* stavaluesN */
1179                         }
1180                         else
1181                         {
1182                                 nulls[i] = 'n';
1183                                 values[i++] = (Datum) 0;
1184                         }
1185                 }
1186
1187                 /* Is there already a pg_statistic tuple for this attribute? */
1188                 oldtup = SearchSysCache(STATRELATT,
1189                                                                 ObjectIdGetDatum(relid),
1190                                                                 Int16GetDatum(stats->attr->attnum),
1191                                                                 0, 0);
1192
1193                 if (HeapTupleIsValid(oldtup))
1194                 {
1195                         /* Yes, replace it */
1196                         stup = heap_modifytuple(oldtup,
1197                                                                         sd,
1198                                                                         values,
1199                                                                         nulls,
1200                                                                         replaces);
1201                         ReleaseSysCache(oldtup);
1202                         simple_heap_update(sd, &stup->t_self, stup);
1203                 }
1204                 else
1205                 {
1206                         /* No, insert new tuple */
1207                         stup = heap_formtuple(sd->rd_att, values, nulls);
1208                         simple_heap_insert(sd, stup);
1209                 }
1210
1211                 /* update indexes too */
1212                 CatalogUpdateIndexes(sd, stup);
1213
1214                 heap_freetuple(stup);
1215         }
1216
1217         heap_close(sd, RowExclusiveLock);
1218 }
1219
1220 /*
1221  * Standard fetch function for use by compute_stats subroutines.
1222  *
1223  * This exists to provide some insulation between compute_stats routines
1224  * and the actual storage of the sample data.
1225  */
1226 static Datum
1227 std_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull)
1228 {
1229         int                     attnum = stats->tupattnum;
1230         HeapTuple       tuple = stats->rows[rownum];
1231         TupleDesc       tupDesc = stats->tupDesc;
1232
1233         return heap_getattr(tuple, attnum, tupDesc, isNull);
1234 }
1235
1236 /*
1237  * Fetch function for analyzing index expressions.
1238  *
1239  * We have not bothered to construct index tuples, instead the data is
1240  * just in Datum arrays.
1241  */
1242 static Datum
1243 ind_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull)
1244 {
1245         int                     i;
1246
1247         /* exprvals and exprnulls are already offset for proper column */
1248         i = rownum * stats->rowstride;
1249         *isNull = stats->exprnulls[i];
1250         return stats->exprvals[i];
1251 }
1252
1253
1254 /*==========================================================================
1255  *
1256  * Code below this point represents the "standard" type-specific statistics
1257  * analysis algorithms.  This code can be replaced on a per-data-type basis
1258  * by setting a nonzero value in pg_type.typanalyze.
1259  *
1260  *==========================================================================
1261  */
1262
1263
1264 /*
1265  * To avoid consuming too much memory during analysis and/or too much space
1266  * in the resulting pg_statistic rows, we ignore varlena datums that are wider
1267  * than WIDTH_THRESHOLD (after detoasting!).  This is legitimate for MCV
1268  * and distinct-value calculations since a wide value is unlikely to be
1269  * duplicated at all, much less be a most-common value.  For the same reason,
1270  * ignoring wide values will not affect our estimates of histogram bin
1271  * boundaries very much.
1272  */
1273 #define WIDTH_THRESHOLD  1024
1274
1275 #define swapInt(a,b)    do {int _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1276 #define swapDatum(a,b)  do {Datum _tmp; _tmp=a; a=b; b=_tmp;} while(0)
1277
1278 /*
1279  * Extra information used by the default analysis routines
1280  */
1281 typedef struct
1282 {
1283         Oid                     eqopr;                  /* '=' operator for datatype, if any */
1284         Oid                     eqfunc;                 /* and associated function */
1285         Oid                     ltopr;                  /* '<' operator for datatype, if any */
1286 } StdAnalyzeData;
1287
1288 typedef struct
1289 {
1290         Datum           value;                  /* a data value */
1291         int                     tupno;                  /* position index for tuple it came from */
1292 } ScalarItem;
1293
1294 typedef struct
1295 {
1296         int                     count;                  /* # of duplicates */
1297         int                     first;                  /* values[] index of first occurrence */
1298 } ScalarMCVItem;
1299
1300
1301 /* context information for compare_scalars() */
1302 static FmgrInfo *datumCmpFn;
1303 static SortFunctionKind datumCmpFnKind;
1304 static int *datumCmpTupnoLink;
1305
1306
1307 static void compute_minimal_stats(VacAttrStatsP stats,
1308                                                                   AnalyzeAttrFetchFunc fetchfunc,
1309                                                                   int samplerows,
1310                                                                   double totalrows);
1311 static void compute_scalar_stats(VacAttrStatsP stats,
1312                                                                  AnalyzeAttrFetchFunc fetchfunc,
1313                                                                  int samplerows,
1314                                                                  double totalrows);
1315 static int      compare_scalars(const void *a, const void *b);
1316 static int      compare_mcvs(const void *a, const void *b);
1317
1318
1319 /*
1320  * std_typanalyze -- the default type-specific typanalyze function
1321  */
1322 static bool
1323 std_typanalyze(VacAttrStats *stats)
1324 {
1325         Form_pg_attribute attr = stats->attr;
1326         Operator        func_operator;
1327         Oid                     eqopr = InvalidOid;
1328         Oid                     eqfunc = InvalidOid;
1329         Oid                     ltopr = InvalidOid;
1330         StdAnalyzeData *mystats;
1331
1332         /* If the attstattarget column is negative, use the default value */
1333         /* NB: it is okay to scribble on stats->attr since it's a copy */
1334         if (attr->attstattarget < 0)
1335                 attr->attstattarget = default_statistics_target;
1336
1337         /* If column has no "=" operator, we can't do much of anything */
1338         func_operator = equality_oper(attr->atttypid, true);
1339         if (func_operator != NULL)
1340         {
1341                 eqopr = oprid(func_operator);
1342                 eqfunc = oprfuncid(func_operator);
1343                 ReleaseSysCache(func_operator);
1344         }
1345         if (!OidIsValid(eqfunc))
1346                 return false;
1347
1348         /* Is there a "<" operator with suitable semantics? */
1349         func_operator = ordering_oper(attr->atttypid, true);
1350         if (func_operator != NULL)
1351         {
1352                 ltopr = oprid(func_operator);
1353                 ReleaseSysCache(func_operator);
1354         }
1355
1356         /* Save the operator info for compute_stats routines */
1357         mystats = (StdAnalyzeData *) palloc(sizeof(StdAnalyzeData));
1358         mystats->eqopr = eqopr;
1359         mystats->eqfunc = eqfunc;
1360         mystats->ltopr = ltopr;
1361         stats->extra_data = mystats;
1362
1363         /*
1364          * Determine which standard statistics algorithm to use
1365          */
1366         if (OidIsValid(ltopr))
1367         {
1368                 /* Seems to be a scalar datatype */
1369                 stats->compute_stats = compute_scalar_stats;
1370                 /*--------------------
1371                  * The following choice of minrows is based on the paper
1372                  * "Random sampling for histogram construction: how much is enough?"
1373                  * by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in
1374                  * Proceedings of ACM SIGMOD International Conference on Management
1375                  * of Data, 1998, Pages 436-447.  Their Corollary 1 to Theorem 5
1376                  * says that for table size n, histogram size k, maximum relative
1377                  * error in bin size f, and error probability gamma, the minimum
1378                  * random sample size is
1379                  *              r = 4 * k * ln(2*n/gamma) / f^2
1380                  * Taking f = 0.5, gamma = 0.01, n = 1 million rows, we obtain
1381                  *              r = 305.82 * k
1382                  * Note that because of the log function, the dependence on n is
1383                  * quite weak; even at n = 1 billion, a 300*k sample gives <= 0.59
1384                  * bin size error with probability 0.99.  So there's no real need to
1385                  * scale for n, which is a good thing because we don't necessarily
1386                  * know it at this point.
1387                  *--------------------
1388                  */
1389                 stats->minrows = 300 * attr->attstattarget;
1390         }
1391         else
1392         {
1393                 /* Can't do much but the minimal stuff */
1394                 stats->compute_stats = compute_minimal_stats;
1395                 /* Might as well use the same minrows as above */
1396                 stats->minrows = 300 * attr->attstattarget;
1397         }
1398
1399         return true;
1400 }
1401
1402 /*
1403  *      compute_minimal_stats() -- compute minimal column statistics
1404  *
1405  *      We use this when we can find only an "=" operator for the datatype.
1406  *
1407  *      We determine the fraction of non-null rows, the average width, the
1408  *      most common values, and the (estimated) number of distinct values.
1409  *
1410  *      The most common values are determined by brute force: we keep a list
1411  *      of previously seen values, ordered by number of times seen, as we scan
1412  *      the samples.  A newly seen value is inserted just after the last
1413  *      multiply-seen value, causing the bottommost (oldest) singly-seen value
1414  *      to drop off the list.  The accuracy of this method, and also its cost,
1415  *      depend mainly on the length of the list we are willing to keep.
1416  */
1417 static void
1418 compute_minimal_stats(VacAttrStatsP stats,
1419                                           AnalyzeAttrFetchFunc fetchfunc,
1420                                           int samplerows,
1421                                           double totalrows)
1422 {
1423         int                     i;
1424         int                     null_cnt = 0;
1425         int                     nonnull_cnt = 0;
1426         int                     toowide_cnt = 0;
1427         double          total_width = 0;
1428         bool            is_varlena = (!stats->attr->attbyval &&
1429                                                           stats->attr->attlen == -1);
1430         bool            is_varwidth = (!stats->attr->attbyval &&
1431                                                            stats->attr->attlen < 0);
1432         FmgrInfo        f_cmpeq;
1433         typedef struct
1434         {
1435                 Datum           value;
1436                 int                     count;
1437         } TrackItem;
1438         TrackItem  *track;
1439         int                     track_cnt,
1440                                 track_max;
1441         int                     num_mcv = stats->attr->attstattarget;
1442         StdAnalyzeData *mystats = (StdAnalyzeData *) stats->extra_data;
1443
1444         /*
1445          * We track up to 2*n values for an n-element MCV list; but at least
1446          * 10
1447          */
1448         track_max = 2 * num_mcv;
1449         if (track_max < 10)
1450                 track_max = 10;
1451         track = (TrackItem *) palloc(track_max * sizeof(TrackItem));
1452         track_cnt = 0;
1453
1454         fmgr_info(mystats->eqfunc, &f_cmpeq);
1455
1456         for (i = 0; i < samplerows; i++)
1457         {
1458                 Datum           value;
1459                 bool            isnull;
1460                 bool            match;
1461                 int                     firstcount1,
1462                                         j;
1463
1464                 vacuum_delay_point();
1465
1466                 value = fetchfunc(stats, i, &isnull);
1467
1468                 /* Check for null/nonnull */
1469                 if (isnull)
1470                 {
1471                         null_cnt++;
1472                         continue;
1473                 }
1474                 nonnull_cnt++;
1475
1476                 /*
1477                  * If it's a variable-width field, add up widths for average width
1478                  * calculation.  Note that if the value is toasted, we use the
1479                  * toasted width.  We don't bother with this calculation if it's a
1480                  * fixed-width type.
1481                  */
1482                 if (is_varlena)
1483                 {
1484                         total_width += VARSIZE(DatumGetPointer(value));
1485
1486                         /*
1487                          * If the value is toasted, we want to detoast it just once to
1488                          * avoid repeated detoastings and resultant excess memory
1489                          * usage during the comparisons.  Also, check to see if the
1490                          * value is excessively wide, and if so don't detoast at all
1491                          * --- just ignore the value.
1492                          */
1493                         if (toast_raw_datum_size(value) > WIDTH_THRESHOLD)
1494                         {
1495                                 toowide_cnt++;
1496                                 continue;
1497                         }
1498                         value = PointerGetDatum(PG_DETOAST_DATUM(value));
1499                 }
1500                 else if (is_varwidth)
1501                 {
1502                         /* must be cstring */
1503                         total_width += strlen(DatumGetCString(value)) + 1;
1504                 }
1505
1506                 /*
1507                  * See if the value matches anything we're already tracking.
1508                  */
1509                 match = false;
1510                 firstcount1 = track_cnt;
1511                 for (j = 0; j < track_cnt; j++)
1512                 {
1513                         if (DatumGetBool(FunctionCall2(&f_cmpeq, value, track[j].value)))
1514                         {
1515                                 match = true;
1516                                 break;
1517                         }
1518                         if (j < firstcount1 && track[j].count == 1)
1519                                 firstcount1 = j;
1520                 }
1521
1522                 if (match)
1523                 {
1524                         /* Found a match */
1525                         track[j].count++;
1526                         /* This value may now need to "bubble up" in the track list */
1527                         while (j > 0 && track[j].count > track[j - 1].count)
1528                         {
1529                                 swapDatum(track[j].value, track[j - 1].value);
1530                                 swapInt(track[j].count, track[j - 1].count);
1531                                 j--;
1532                         }
1533                 }
1534                 else
1535                 {
1536                         /* No match.  Insert at head of count-1 list */
1537                         if (track_cnt < track_max)
1538                                 track_cnt++;
1539                         for (j = track_cnt - 1; j > firstcount1; j--)
1540                         {
1541                                 track[j].value = track[j - 1].value;
1542                                 track[j].count = track[j - 1].count;
1543                         }
1544                         if (firstcount1 < track_cnt)
1545                         {
1546                                 track[firstcount1].value = value;
1547                                 track[firstcount1].count = 1;
1548                         }
1549                 }
1550         }
1551
1552         /* We can only compute valid stats if we found some non-null values. */
1553         if (nonnull_cnt > 0)
1554         {
1555                 int                     nmultiple,
1556                                         summultiple;
1557
1558                 stats->stats_valid = true;
1559                 /* Do the simple null-frac and width stats */
1560                 stats->stanullfrac = (double) null_cnt / (double) samplerows;
1561                 if (is_varwidth)
1562                         stats->stawidth = total_width / (double) nonnull_cnt;
1563                 else
1564                         stats->stawidth = stats->attrtype->typlen;
1565
1566                 /* Count the number of values we found multiple times */
1567                 summultiple = 0;
1568                 for (nmultiple = 0; nmultiple < track_cnt; nmultiple++)
1569                 {
1570                         if (track[nmultiple].count == 1)
1571                                 break;
1572                         summultiple += track[nmultiple].count;
1573                 }
1574
1575                 if (nmultiple == 0)
1576                 {
1577                         /* If we found no repeated values, assume it's a unique column */
1578                         stats->stadistinct = -1.0;
1579                 }
1580                 else if (track_cnt < track_max && toowide_cnt == 0 &&
1581                                  nmultiple == track_cnt)
1582                 {
1583                         /*
1584                          * Our track list includes every value in the sample, and
1585                          * every value appeared more than once.  Assume the column has
1586                          * just these values.
1587                          */
1588                         stats->stadistinct = track_cnt;
1589                 }
1590                 else
1591                 {
1592                         /*----------
1593                          * Estimate the number of distinct values using the estimator
1594                          * proposed by Haas and Stokes in IBM Research Report RJ 10025:
1595                          *              n*d / (n - f1 + f1*n/N)
1596                          * where f1 is the number of distinct values that occurred
1597                          * exactly once in our sample of n rows (from a total of N),
1598                          * and d is the total number of distinct values in the sample.
1599                          * This is their Duj1 estimator; the other estimators they
1600                          * recommend are considerably more complex, and are numerically
1601                          * very unstable when n is much smaller than N.
1602                          *
1603                          * We assume (not very reliably!) that all the multiply-occurring
1604                          * values are reflected in the final track[] list, and the other
1605                          * nonnull values all appeared but once.  (XXX this usually
1606                          * results in a drastic overestimate of ndistinct.      Can we do
1607                          * any better?)
1608                          *----------
1609                          */
1610                         int                     f1 = nonnull_cnt - summultiple;
1611                         int                     d = f1 + nmultiple;
1612                         double          numer,
1613                                                 denom,
1614                                                 stadistinct;
1615
1616                         numer = (double) samplerows *(double) d;
1617
1618                         denom = (double) (samplerows - f1) +
1619                                 (double) f1 *(double) samplerows / totalrows;
1620
1621                         stadistinct = numer / denom;
1622                         /* Clamp to sane range in case of roundoff error */
1623                         if (stadistinct < (double) d)
1624                                 stadistinct = (double) d;
1625                         if (stadistinct > totalrows)
1626                                 stadistinct = totalrows;
1627                         stats->stadistinct = floor(stadistinct + 0.5);
1628                 }
1629
1630                 /*
1631                  * If we estimated the number of distinct values at more than 10%
1632                  * of the total row count (a very arbitrary limit), then assume
1633                  * that stadistinct should scale with the row count rather than be
1634                  * a fixed value.
1635                  */
1636                 if (stats->stadistinct > 0.1 * totalrows)
1637                         stats->stadistinct = -(stats->stadistinct / totalrows);
1638
1639                 /*
1640                  * Decide how many values are worth storing as most-common values.
1641                  * If we are able to generate a complete MCV list (all the values
1642                  * in the sample will fit, and we think these are all the ones in
1643                  * the table), then do so.      Otherwise, store only those values
1644                  * that are significantly more common than the (estimated)
1645                  * average. We set the threshold rather arbitrarily at 25% more
1646                  * than average, with at least 2 instances in the sample.
1647                  */
1648                 if (track_cnt < track_max && toowide_cnt == 0 &&
1649                         stats->stadistinct > 0 &&
1650                         track_cnt <= num_mcv)
1651                 {
1652                         /* Track list includes all values seen, and all will fit */
1653                         num_mcv = track_cnt;
1654                 }
1655                 else
1656                 {
1657                         double          ndistinct = stats->stadistinct;
1658                         double          avgcount,
1659                                                 mincount;
1660
1661                         if (ndistinct < 0)
1662                                 ndistinct = -ndistinct * totalrows;
1663                         /* estimate # of occurrences in sample of a typical value */
1664                         avgcount = (double) samplerows / ndistinct;
1665                         /* set minimum threshold count to store a value */
1666                         mincount = avgcount * 1.25;
1667                         if (mincount < 2)
1668                                 mincount = 2;
1669                         if (num_mcv > track_cnt)
1670                                 num_mcv = track_cnt;
1671                         for (i = 0; i < num_mcv; i++)
1672                         {
1673                                 if (track[i].count < mincount)
1674                                 {
1675                                         num_mcv = i;
1676                                         break;
1677                                 }
1678                         }
1679                 }
1680
1681                 /* Generate MCV slot entry */
1682                 if (num_mcv > 0)
1683                 {
1684                         MemoryContext old_context;
1685                         Datum      *mcv_values;
1686                         float4     *mcv_freqs;
1687
1688                         /* Must copy the target values into anl_context */
1689                         old_context = MemoryContextSwitchTo(stats->anl_context);
1690                         mcv_values = (Datum *) palloc(num_mcv * sizeof(Datum));
1691                         mcv_freqs = (float4 *) palloc(num_mcv * sizeof(float4));
1692                         for (i = 0; i < num_mcv; i++)
1693                         {
1694                                 mcv_values[i] = datumCopy(track[i].value,
1695                                                                                   stats->attr->attbyval,
1696                                                                                   stats->attr->attlen);
1697                                 mcv_freqs[i] = (double) track[i].count / (double) samplerows;
1698                         }
1699                         MemoryContextSwitchTo(old_context);
1700
1701                         stats->stakind[0] = STATISTIC_KIND_MCV;
1702                         stats->staop[0] = mystats->eqopr;
1703                         stats->stanumbers[0] = mcv_freqs;
1704                         stats->numnumbers[0] = num_mcv;
1705                         stats->stavalues[0] = mcv_values;
1706                         stats->numvalues[0] = num_mcv;
1707                 }
1708         }
1709
1710         /* We don't need to bother cleaning up any of our temporary palloc's */
1711 }
1712
1713
1714 /*
1715  *      compute_scalar_stats() -- compute column statistics
1716  *
1717  *      We use this when we can find "=" and "<" operators for the datatype.
1718  *
1719  *      We determine the fraction of non-null rows, the average width, the
1720  *      most common values, the (estimated) number of distinct values, the
1721  *      distribution histogram, and the correlation of physical to logical order.
1722  *
1723  *      The desired stats can be determined fairly easily after sorting the
1724  *      data values into order.
1725  */
1726 static void
1727 compute_scalar_stats(VacAttrStatsP stats,
1728                                          AnalyzeAttrFetchFunc fetchfunc,
1729                                          int samplerows,
1730                                          double totalrows)
1731 {
1732         int                     i;
1733         int                     null_cnt = 0;
1734         int                     nonnull_cnt = 0;
1735         int                     toowide_cnt = 0;
1736         double          total_width = 0;
1737         bool            is_varlena = (!stats->attr->attbyval &&
1738                                                           stats->attr->attlen == -1);
1739         bool            is_varwidth = (!stats->attr->attbyval &&
1740                                                            stats->attr->attlen < 0);
1741         double          corr_xysum;
1742         RegProcedure cmpFn;
1743         SortFunctionKind cmpFnKind;
1744         FmgrInfo        f_cmpfn;
1745         ScalarItem *values;
1746         int                     values_cnt = 0;
1747         int                *tupnoLink;
1748         ScalarMCVItem *track;
1749         int                     track_cnt = 0;
1750         int                     num_mcv = stats->attr->attstattarget;
1751         int                     num_bins = stats->attr->attstattarget;
1752         StdAnalyzeData *mystats = (StdAnalyzeData *) stats->extra_data;
1753
1754         values = (ScalarItem *) palloc(samplerows * sizeof(ScalarItem));
1755         tupnoLink = (int *) palloc(samplerows * sizeof(int));
1756         track = (ScalarMCVItem *) palloc(num_mcv * sizeof(ScalarMCVItem));
1757
1758         SelectSortFunction(mystats->ltopr, &cmpFn, &cmpFnKind);
1759         fmgr_info(cmpFn, &f_cmpfn);
1760
1761         /* Initial scan to find sortable values */
1762         for (i = 0; i < samplerows; i++)
1763         {
1764                 Datum           value;
1765                 bool            isnull;
1766
1767                 vacuum_delay_point();
1768
1769                 value = fetchfunc(stats, i, &isnull);
1770
1771                 /* Check for null/nonnull */
1772                 if (isnull)
1773                 {
1774                         null_cnt++;
1775                         continue;
1776                 }
1777                 nonnull_cnt++;
1778
1779                 /*
1780                  * If it's a variable-width field, add up widths for average width
1781                  * calculation.  Note that if the value is toasted, we use the
1782                  * toasted width.  We don't bother with this calculation if it's a
1783                  * fixed-width type.
1784                  */
1785                 if (is_varlena)
1786                 {
1787                         total_width += VARSIZE(DatumGetPointer(value));
1788
1789                         /*
1790                          * If the value is toasted, we want to detoast it just once to
1791                          * avoid repeated detoastings and resultant excess memory
1792                          * usage during the comparisons.  Also, check to see if the
1793                          * value is excessively wide, and if so don't detoast at all
1794                          * --- just ignore the value.
1795                          */
1796                         if (toast_raw_datum_size(value) > WIDTH_THRESHOLD)
1797                         {
1798                                 toowide_cnt++;
1799                                 continue;
1800                         }
1801                         value = PointerGetDatum(PG_DETOAST_DATUM(value));
1802                 }
1803                 else if (is_varwidth)
1804                 {
1805                         /* must be cstring */
1806                         total_width += strlen(DatumGetCString(value)) + 1;
1807                 }
1808
1809                 /* Add it to the list to be sorted */
1810                 values[values_cnt].value = value;
1811                 values[values_cnt].tupno = values_cnt;
1812                 tupnoLink[values_cnt] = values_cnt;
1813                 values_cnt++;
1814         }
1815
1816         /* We can only compute valid stats if we found some sortable values. */
1817         if (values_cnt > 0)
1818         {
1819                 int                     ndistinct,      /* # distinct values in sample */
1820                                         nmultiple,      /* # that appear multiple times */
1821                                         num_hist,
1822                                         dups_cnt;
1823                 int                     slot_idx = 0;
1824
1825                 /* Sort the collected values */
1826                 datumCmpFn = &f_cmpfn;
1827                 datumCmpFnKind = cmpFnKind;
1828                 datumCmpTupnoLink = tupnoLink;
1829                 qsort((void *) values, values_cnt,
1830                           sizeof(ScalarItem), compare_scalars);
1831
1832                 /*
1833                  * Now scan the values in order, find the most common ones, and
1834                  * also accumulate ordering-correlation statistics.
1835                  *
1836                  * To determine which are most common, we first have to count the
1837                  * number of duplicates of each value.  The duplicates are
1838                  * adjacent in the sorted list, so a brute-force approach is to
1839                  * compare successive datum values until we find two that are not
1840                  * equal. However, that requires N-1 invocations of the datum
1841                  * comparison routine, which are completely redundant with work
1842                  * that was done during the sort.  (The sort algorithm must at
1843                  * some point have compared each pair of items that are adjacent
1844                  * in the sorted order; otherwise it could not know that it's
1845                  * ordered the pair correctly.) We exploit this by having
1846                  * compare_scalars remember the highest tupno index that each
1847                  * ScalarItem has been found equal to.  At the end of the sort, a
1848                  * ScalarItem's tupnoLink will still point to itself if and only
1849                  * if it is the last item of its group of duplicates (since the
1850                  * group will be ordered by tupno).
1851                  */
1852                 corr_xysum = 0;
1853                 ndistinct = 0;
1854                 nmultiple = 0;
1855                 dups_cnt = 0;
1856                 for (i = 0; i < values_cnt; i++)
1857                 {
1858                         int                     tupno = values[i].tupno;
1859
1860                         corr_xysum += ((double) i) * ((double) tupno);
1861                         dups_cnt++;
1862                         if (tupnoLink[tupno] == tupno)
1863                         {
1864                                 /* Reached end of duplicates of this value */
1865                                 ndistinct++;
1866                                 if (dups_cnt > 1)
1867                                 {
1868                                         nmultiple++;
1869                                         if (track_cnt < num_mcv ||
1870                                                 dups_cnt > track[track_cnt - 1].count)
1871                                         {
1872                                                 /*
1873                                                  * Found a new item for the mcv list; find its
1874                                                  * position, bubbling down old items if needed.
1875                                                  * Loop invariant is that j points at an empty/
1876                                                  * replaceable slot.
1877                                                  */
1878                                                 int                     j;
1879
1880                                                 if (track_cnt < num_mcv)
1881                                                         track_cnt++;
1882                                                 for (j = track_cnt - 1; j > 0; j--)
1883                                                 {
1884                                                         if (dups_cnt <= track[j - 1].count)
1885                                                                 break;
1886                                                         track[j].count = track[j - 1].count;
1887                                                         track[j].first = track[j - 1].first;
1888                                                 }
1889                                                 track[j].count = dups_cnt;
1890                                                 track[j].first = i + 1 - dups_cnt;
1891                                         }
1892                                 }
1893                                 dups_cnt = 0;
1894                         }
1895                 }
1896
1897                 stats->stats_valid = true;
1898                 /* Do the simple null-frac and width stats */
1899                 stats->stanullfrac = (double) null_cnt / (double) samplerows;
1900                 if (is_varwidth)
1901                         stats->stawidth = total_width / (double) nonnull_cnt;
1902                 else
1903                         stats->stawidth = stats->attrtype->typlen;
1904
1905                 if (nmultiple == 0)
1906                 {
1907                         /* If we found no repeated values, assume it's a unique column */
1908                         stats->stadistinct = -1.0;
1909                 }
1910                 else if (toowide_cnt == 0 && nmultiple == ndistinct)
1911                 {
1912                         /*
1913                          * Every value in the sample appeared more than once.  Assume
1914                          * the column has just these values.
1915                          */
1916                         stats->stadistinct = ndistinct;
1917                 }
1918                 else
1919                 {
1920                         /*----------
1921                          * Estimate the number of distinct values using the estimator
1922                          * proposed by Haas and Stokes in IBM Research Report RJ 10025:
1923                          *              n*d / (n - f1 + f1*n/N)
1924                          * where f1 is the number of distinct values that occurred
1925                          * exactly once in our sample of n rows (from a total of N),
1926                          * and d is the total number of distinct values in the sample.
1927                          * This is their Duj1 estimator; the other estimators they
1928                          * recommend are considerably more complex, and are numerically
1929                          * very unstable when n is much smaller than N.
1930                          *
1931                          * Overwidth values are assumed to have been distinct.
1932                          *----------
1933                          */
1934                         int                     f1 = ndistinct - nmultiple + toowide_cnt;
1935                         int                     d = f1 + nmultiple;
1936                         double          numer,
1937                                                 denom,
1938                                                 stadistinct;
1939
1940                         numer = (double) samplerows *(double) d;
1941
1942                         denom = (double) (samplerows - f1) +
1943                                 (double) f1 *(double) samplerows / totalrows;
1944
1945                         stadistinct = numer / denom;
1946                         /* Clamp to sane range in case of roundoff error */
1947                         if (stadistinct < (double) d)
1948                                 stadistinct = (double) d;
1949                         if (stadistinct > totalrows)
1950                                 stadistinct = totalrows;
1951                         stats->stadistinct = floor(stadistinct + 0.5);
1952                 }
1953
1954                 /*
1955                  * If we estimated the number of distinct values at more than 10%
1956                  * of the total row count (a very arbitrary limit), then assume
1957                  * that stadistinct should scale with the row count rather than be
1958                  * a fixed value.
1959                  */
1960                 if (stats->stadistinct > 0.1 * totalrows)
1961                         stats->stadistinct = -(stats->stadistinct / totalrows);
1962
1963                 /*
1964                  * Decide how many values are worth storing as most-common values.
1965                  * If we are able to generate a complete MCV list (all the values
1966                  * in the sample will fit, and we think these are all the ones in
1967                  * the table), then do so.      Otherwise, store only those values
1968                  * that are significantly more common than the (estimated)
1969                  * average. We set the threshold rather arbitrarily at 25% more
1970                  * than average, with at least 2 instances in the sample.  Also,
1971                  * we won't suppress values that have a frequency of at least 1/K
1972                  * where K is the intended number of histogram bins; such values
1973                  * might otherwise cause us to emit duplicate histogram bin
1974                  * boundaries.
1975                  */
1976                 if (track_cnt == ndistinct && toowide_cnt == 0 &&
1977                         stats->stadistinct > 0 &&
1978                         track_cnt <= num_mcv)
1979                 {
1980                         /* Track list includes all values seen, and all will fit */
1981                         num_mcv = track_cnt;
1982                 }
1983                 else
1984                 {
1985                         double          ndistinct = stats->stadistinct;
1986                         double          avgcount,
1987                                                 mincount,
1988                                                 maxmincount;
1989
1990                         if (ndistinct < 0)
1991                                 ndistinct = -ndistinct * totalrows;
1992                         /* estimate # of occurrences in sample of a typical value */
1993                         avgcount = (double) samplerows / ndistinct;
1994                         /* set minimum threshold count to store a value */
1995                         mincount = avgcount * 1.25;
1996                         if (mincount < 2)
1997                                 mincount = 2;
1998                         /* don't let threshold exceed 1/K, however */
1999                         maxmincount = (double) samplerows / (double) num_bins;
2000                         if (mincount > maxmincount)
2001                                 mincount = maxmincount;
2002                         if (num_mcv > track_cnt)
2003                                 num_mcv = track_cnt;
2004                         for (i = 0; i < num_mcv; i++)
2005                         {
2006                                 if (track[i].count < mincount)
2007                                 {
2008                                         num_mcv = i;
2009                                         break;
2010                                 }
2011                         }
2012                 }
2013
2014                 /* Generate MCV slot entry */
2015                 if (num_mcv > 0)
2016                 {
2017                         MemoryContext old_context;
2018                         Datum      *mcv_values;
2019                         float4     *mcv_freqs;
2020
2021                         /* Must copy the target values into anl_context */
2022                         old_context = MemoryContextSwitchTo(stats->anl_context);
2023                         mcv_values = (Datum *) palloc(num_mcv * sizeof(Datum));
2024                         mcv_freqs = (float4 *) palloc(num_mcv * sizeof(float4));
2025                         for (i = 0; i < num_mcv; i++)
2026                         {
2027                                 mcv_values[i] = datumCopy(values[track[i].first].value,
2028                                                                                   stats->attr->attbyval,
2029                                                                                   stats->attr->attlen);
2030                                 mcv_freqs[i] = (double) track[i].count / (double) samplerows;
2031                         }
2032                         MemoryContextSwitchTo(old_context);
2033
2034                         stats->stakind[slot_idx] = STATISTIC_KIND_MCV;
2035                         stats->staop[slot_idx] = mystats->eqopr;
2036                         stats->stanumbers[slot_idx] = mcv_freqs;
2037                         stats->numnumbers[slot_idx] = num_mcv;
2038                         stats->stavalues[slot_idx] = mcv_values;
2039                         stats->numvalues[slot_idx] = num_mcv;
2040                         slot_idx++;
2041                 }
2042
2043                 /*
2044                  * Generate a histogram slot entry if there are at least two
2045                  * distinct values not accounted for in the MCV list.  (This
2046                  * ensures the histogram won't collapse to empty or a singleton.)
2047                  */
2048                 num_hist = ndistinct - num_mcv;
2049                 if (num_hist > num_bins)
2050                         num_hist = num_bins + 1;
2051                 if (num_hist >= 2)
2052                 {
2053                         MemoryContext old_context;
2054                         Datum      *hist_values;
2055                         int                     nvals;
2056
2057                         /* Sort the MCV items into position order to speed next loop */
2058                         qsort((void *) track, num_mcv,
2059                                   sizeof(ScalarMCVItem), compare_mcvs);
2060
2061                         /*
2062                          * Collapse out the MCV items from the values[] array.
2063                          *
2064                          * Note we destroy the values[] array here... but we don't need
2065                          * it for anything more.  We do, however, still need
2066                          * values_cnt. nvals will be the number of remaining entries
2067                          * in values[].
2068                          */
2069                         if (num_mcv > 0)
2070                         {
2071                                 int                     src,
2072                                                         dest;
2073                                 int                     j;
2074
2075                                 src = dest = 0;
2076                                 j = 0;                  /* index of next interesting MCV item */
2077                                 while (src < values_cnt)
2078                                 {
2079                                         int                     ncopy;
2080
2081                                         if (j < num_mcv)
2082                                         {
2083                                                 int                     first = track[j].first;
2084
2085                                                 if (src >= first)
2086                                                 {
2087                                                         /* advance past this MCV item */
2088                                                         src = first + track[j].count;
2089                                                         j++;
2090                                                         continue;
2091                                                 }
2092                                                 ncopy = first - src;
2093                                         }
2094                                         else
2095                                                 ncopy = values_cnt - src;
2096                                         memmove(&values[dest], &values[src],
2097                                                         ncopy * sizeof(ScalarItem));
2098                                         src += ncopy;
2099                                         dest += ncopy;
2100                                 }
2101                                 nvals = dest;
2102                         }
2103                         else
2104                                 nvals = values_cnt;
2105                         Assert(nvals >= num_hist);
2106
2107                         /* Must copy the target values into anl_context */
2108                         old_context = MemoryContextSwitchTo(stats->anl_context);
2109                         hist_values = (Datum *) palloc(num_hist * sizeof(Datum));
2110                         for (i = 0; i < num_hist; i++)
2111                         {
2112                                 int                     pos;
2113
2114                                 pos = (i * (nvals - 1)) / (num_hist - 1);
2115                                 hist_values[i] = datumCopy(values[pos].value,
2116                                                                                    stats->attr->attbyval,
2117                                                                                    stats->attr->attlen);
2118                         }
2119                         MemoryContextSwitchTo(old_context);
2120
2121                         stats->stakind[slot_idx] = STATISTIC_KIND_HISTOGRAM;
2122                         stats->staop[slot_idx] = mystats->ltopr;
2123                         stats->stavalues[slot_idx] = hist_values;
2124                         stats->numvalues[slot_idx] = num_hist;
2125                         slot_idx++;
2126                 }
2127
2128                 /* Generate a correlation entry if there are multiple values */
2129                 if (values_cnt > 1)
2130                 {
2131                         MemoryContext old_context;
2132                         float4     *corrs;
2133                         double          corr_xsum,
2134                                                 corr_x2sum;
2135
2136                         /* Must copy the target values into anl_context */
2137                         old_context = MemoryContextSwitchTo(stats->anl_context);
2138                         corrs = (float4 *) palloc(sizeof(float4));
2139                         MemoryContextSwitchTo(old_context);
2140
2141                         /*----------
2142                          * Since we know the x and y value sets are both
2143                          *              0, 1, ..., values_cnt-1
2144                          * we have sum(x) = sum(y) =
2145                          *              (values_cnt-1)*values_cnt / 2
2146                          * and sum(x^2) = sum(y^2) =
2147                          *              (values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
2148                          *----------
2149                          */
2150                         corr_xsum = ((double) (values_cnt - 1)) *
2151                                 ((double) values_cnt) / 2.0;
2152                         corr_x2sum = ((double) (values_cnt - 1)) *
2153                                 ((double) values_cnt) * (double) (2 * values_cnt - 1) / 6.0;
2154
2155                         /* And the correlation coefficient reduces to */
2156                         corrs[0] = (values_cnt * corr_xysum - corr_xsum * corr_xsum) /
2157                                 (values_cnt * corr_x2sum - corr_xsum * corr_xsum);
2158
2159                         stats->stakind[slot_idx] = STATISTIC_KIND_CORRELATION;
2160                         stats->staop[slot_idx] = mystats->ltopr;
2161                         stats->stanumbers[slot_idx] = corrs;
2162                         stats->numnumbers[slot_idx] = 1;
2163                         slot_idx++;
2164                 }
2165         }
2166
2167         /* We don't need to bother cleaning up any of our temporary palloc's */
2168 }
2169
2170 /*
2171  * qsort comparator for sorting ScalarItems
2172  *
2173  * Aside from sorting the items, we update the datumCmpTupnoLink[] array
2174  * whenever two ScalarItems are found to contain equal datums.  The array
2175  * is indexed by tupno; for each ScalarItem, it contains the highest
2176  * tupno that that item's datum has been found to be equal to.  This allows
2177  * us to avoid additional comparisons in compute_scalar_stats().
2178  */
2179 static int
2180 compare_scalars(const void *a, const void *b)
2181 {
2182         Datum           da = ((ScalarItem *) a)->value;
2183         int                     ta = ((ScalarItem *) a)->tupno;
2184         Datum           db = ((ScalarItem *) b)->value;
2185         int                     tb = ((ScalarItem *) b)->tupno;
2186         int32           compare;
2187
2188         compare = ApplySortFunction(datumCmpFn, datumCmpFnKind,
2189                                                                 da, false, db, false);
2190         if (compare != 0)
2191                 return compare;
2192
2193         /*
2194          * The two datums are equal, so update datumCmpTupnoLink[].
2195          */
2196         if (datumCmpTupnoLink[ta] < tb)
2197                 datumCmpTupnoLink[ta] = tb;
2198         if (datumCmpTupnoLink[tb] < ta)
2199                 datumCmpTupnoLink[tb] = ta;
2200
2201         /*
2202          * For equal datums, sort by tupno
2203          */
2204         return ta - tb;
2205 }
2206
2207 /*
2208  * qsort comparator for sorting ScalarMCVItems by position
2209  */
2210 static int
2211 compare_mcvs(const void *a, const void *b)
2212 {
2213         int                     da = ((ScalarMCVItem *) a)->first;
2214         int                     db = ((ScalarMCVItem *) b)->first;
2215
2216         return da - db;
2217 }