src/backend/utils/adt/array_typanalyze.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * array_typanalyze.c
   4  *        Functions for gathering statistics from array columns
   5  *
   6  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/utils/adt/array_typanalyze.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "access/detoast.h"
  18 #include "commands/vacuum.h"
  19 #include "utils/array.h"
  20 #include "utils/datum.h"
  21 #include "utils/fmgrprotos.h"
  22 #include "utils/lsyscache.h"
  23 #include "utils/typcache.h"
  24
  25
  26 /*
  27  * To avoid consuming too much memory, IO and CPU load during analysis, and/or
  28  * too much space in the resulting pg_statistic rows, we ignore arrays that
  29  * are wider than ARRAY_WIDTH_THRESHOLD (after detoasting!).  Note that this
  30  * number is considerably more than the similar WIDTH_THRESHOLD limit used
  31  * in analyze.c's standard typanalyze code.
  32  */
  33 #define ARRAY_WIDTH_THRESHOLD 0x10000
  34
  35 /* Extra data for compute_array_stats function */
  36 typedef struct
  37 {
  38         /* Information about array element type */
  39         Oid                     type_id;                /* element type's OID */
  40         Oid                     eq_opr;                 /* default equality operator's OID */
  41         Oid                     coll_id;                /* collation to use */
  42         bool            typbyval;               /* physical properties of element type */
  43         int16           typlen;
  44         char            typalign;
  45
  46         /*
  47          * Lookup data for element type's comparison and hash functions (these are
  48          * in the type's typcache entry, which we expect to remain valid over the
  49          * lifespan of the ANALYZE run)
  50          */
  51         FmgrInfo   *cmp;
  52         FmgrInfo   *hash;
  53
  54         /* Saved state from std_typanalyze() */
  55         AnalyzeAttrComputeStatsFunc std_compute_stats;
  56         void       *std_extra_data;
  57 } ArrayAnalyzeExtraData;
  58
  59 /*
  60  * While compute_array_stats is running, we keep a pointer to the extra data
  61  * here for use by assorted subroutines.  compute_array_stats doesn't
  62  * currently need to be re-entrant, so avoiding this is not worth the extra
  63  * notational cruft that would be needed.
  64  */
  65 static ArrayAnalyzeExtraData *array_extra_data;
  66
  67 /* A hash table entry for the Lossy Counting algorithm */
  68 typedef struct
  69 {
  70         Datum           key;                    /* This is 'e' from the LC algorithm. */
  71         int                     frequency;              /* This is 'f'. */
  72         int                     delta;                  /* And this is 'delta'. */
  73         int                     last_container; /* For de-duplication of array elements. */
  74 } TrackItem;
  75
  76 /* A hash table entry for distinct-elements counts */
  77 typedef struct
  78 {
  79         int                     count;                  /* Count of distinct elements in an array */
  80         int                     frequency;              /* Number of arrays seen with this count */
  81 } DECountItem;
  82
  83 static void compute_array_stats(VacAttrStats *stats,
  84                                                                 AnalyzeAttrFetchFunc fetchfunc, int samplerows, double totalrows);
  85 static void prune_element_hashtable(HTAB *elements_tab, int b_current);
  86 static uint32 element_hash(const void *key, Size keysize);
  87 static int      element_match(const void *key1, const void *key2, Size keysize);
  88 static int      element_compare(const void *key1, const void *key2);
  89 static int      trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg);
  90 static int      trackitem_compare_element(const void *e1, const void *e2, void *arg);
  91 static int      countitem_compare_count(const void *e1, const void *e2, void *arg);
  92
  93
  94 /*
  95  * array_typanalyze -- typanalyze function for array columns
  96  */
  97 Datum
  98 array_typanalyze(PG_FUNCTION_ARGS)
  99 {
 100         VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
 101         Oid                     element_typeid;
 102         TypeCacheEntry *typentry;
 103         ArrayAnalyzeExtraData *extra_data;
 104
 105         /*
 106          * Call the standard typanalyze function.  It may fail to find needed
 107          * operators, in which case we also can't do anything, so just fail.
 108          */
 109         if (!std_typanalyze(stats))
 110                 PG_RETURN_BOOL(false);
 111
 112         /*
 113          * Check attribute data type is a varlena array (or a domain over one).
 114          */
 115         element_typeid = get_base_element_type(stats->attrtypid);
 116         if (!OidIsValid(element_typeid))
 117                 elog(ERROR, "array_typanalyze was invoked for non-array type %u",
 118                          stats->attrtypid);
 119
 120         /*
 121          * Gather information about the element type.  If we fail to find
 122          * something, return leaving the state from std_typanalyze() in place.
 123          */
 124         typentry = lookup_type_cache(element_typeid,
 125                                                                  TYPECACHE_EQ_OPR |
 126                                                                  TYPECACHE_CMP_PROC_FINFO |
 127                                                                  TYPECACHE_HASH_PROC_FINFO);
 128
 129         if (!OidIsValid(typentry->eq_opr) ||
 130                 !OidIsValid(typentry->cmp_proc_finfo.fn_oid) ||
 131                 !OidIsValid(typentry->hash_proc_finfo.fn_oid))
 132                 PG_RETURN_BOOL(true);
 133
 134         /* Store our findings for use by compute_array_stats() */
 135         extra_data = (ArrayAnalyzeExtraData *) palloc(sizeof(ArrayAnalyzeExtraData));
 136         extra_data->type_id = typentry->type_id;
 137         extra_data->eq_opr = typentry->eq_opr;
 138         extra_data->coll_id = stats->attrcollid;        /* collation we should use */
 139         extra_data->typbyval = typentry->typbyval;
 140         extra_data->typlen = typentry->typlen;
 141         extra_data->typalign = typentry->typalign;
 142         extra_data->cmp = &typentry->cmp_proc_finfo;
 143         extra_data->hash = &typentry->hash_proc_finfo;
 144
 145         /* Save old compute_stats and extra_data for scalar statistics ... */
 146         extra_data->std_compute_stats = stats->compute_stats;
 147         extra_data->std_extra_data = stats->extra_data;
 148
 149         /* ... and replace with our info */
 150         stats->compute_stats = compute_array_stats;
 151         stats->extra_data = extra_data;
 152
 153         /*
 154          * Note we leave stats->minrows set as std_typanalyze set it.  Should it
 155          * be increased for array analysis purposes?
 156          */
 157
 158         PG_RETURN_BOOL(true);
 159 }
 160
 161 /*
 162  * compute_array_stats() -- compute statistics for an array column
 163  *
 164  * This function computes statistics useful for determining selectivity of
 165  * the array operators <@, &&, and @>.  It is invoked by ANALYZE via the
 166  * compute_stats hook after sample rows have been collected.
 167  *
 168  * We also invoke the standard compute_stats function, which will compute
 169  * "scalar" statistics relevant to the btree-style array comparison operators.
 170  * However, exact duplicates of an entire array may be rare despite many
 171  * arrays sharing individual elements.  This especially afflicts long arrays,
 172  * which are also liable to lack all scalar statistics due to the low
 173  * WIDTH_THRESHOLD used in analyze.c.  So, in addition to the standard stats,
 174  * we find the most common array elements and compute a histogram of distinct
 175  * element counts.
 176  *
 177  * The algorithm used is Lossy Counting, as proposed in the paper "Approximate
 178  * frequency counts over data streams" by G. S. Manku and R. Motwani, in
 179  * Proceedings of the 28th International Conference on Very Large Data Bases,
 180  * Hong Kong, China, August 2002, section 4.2. The paper is available at
 181  * http://www.vldb.org/conf/2002/S10P03.pdf
 182  *
 183  * The Lossy Counting (aka LC) algorithm goes like this:
 184  * Let s be the threshold frequency for an item (the minimum frequency we
 185  * are interested in) and epsilon the error margin for the frequency. Let D
 186  * be a set of triples (e, f, delta), where e is an element value, f is that
 187  * element's frequency (actually, its current occurrence count) and delta is
 188  * the maximum error in f. We start with D empty and process the elements in
 189  * batches of size w. (The batch size is also known as "bucket size" and is
 190  * equal to 1/epsilon.) Let the current batch number be b_current, starting
 191  * with 1. For each element e we either increment its f count, if it's
 192  * already in D, or insert a new triple into D with values (e, 1, b_current
 193  * - 1). After processing each batch we prune D, by removing from it all
 194  * elements with f + delta <= b_current.  After the algorithm finishes we
 195  * suppress all elements from D that do not satisfy f >= (s - epsilon) * N,
 196  * where N is the total number of elements in the input.  We emit the
 197  * remaining elements with estimated frequency f/N.  The LC paper proves
 198  * that this algorithm finds all elements with true frequency at least s,
 199  * and that no frequency is overestimated or is underestimated by more than
 200  * epsilon.  Furthermore, given reasonable assumptions about the input
 201  * distribution, the required table size is no more than about 7 times w.
 202  *
 203  * In the absence of a principled basis for other particular values, we
 204  * follow ts_typanalyze() and use parameters s = 0.07/K, epsilon = s/10.
 205  * But we leave out the correction for stopwords, which do not apply to
 206  * arrays.  These parameters give bucket width w = K/0.007 and maximum
 207  * expected hashtable size of about 1000 * K.
 208  *
 209  * Elements may repeat within an array.  Since duplicates do not change the
 210  * behavior of <@, && or @>, we want to count each element only once per
 211  * array.  Therefore, we store in the finished pg_statistic entry each
 212  * element's frequency as the fraction of all non-null rows that contain it.
 213  * We divide the raw counts by nonnull_cnt to get those figures.
 214  */
 215 static void
 216 compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 217                                         int samplerows, double totalrows)
 218 {
 219         ArrayAnalyzeExtraData *extra_data;
 220         int                     num_mcelem;
 221         int                     null_elem_cnt = 0;
 222         int                     analyzed_rows = 0;
 223
 224         /* This is D from the LC algorithm. */
 225         HTAB       *elements_tab;
 226         HASHCTL         elem_hash_ctl;
 227         HASH_SEQ_STATUS scan_status;
 228
 229         /* This is the current bucket number from the LC algorithm */
 230         int                     b_current;
 231
 232         /* This is 'w' from the LC algorithm */
 233         int                     bucket_width;
 234         int                     array_no;
 235         int64           element_no;
 236         TrackItem  *item;
 237         int                     slot_idx;
 238         HTAB       *count_tab;
 239         HASHCTL         count_hash_ctl;
 240         DECountItem *count_item;
 241
 242         extra_data = (ArrayAnalyzeExtraData *) stats->extra_data;
 243
 244         /*
 245          * Invoke analyze.c's standard analysis function to create scalar-style
 246          * stats for the column.  It will expect its own extra_data pointer, so
 247          * temporarily install that.
 248          */
 249         stats->extra_data = extra_data->std_extra_data;
 250         extra_data->std_compute_stats(stats, fetchfunc, samplerows, totalrows);
 251         stats->extra_data = extra_data;
 252
 253         /*
 254          * Set up static pointer for use by subroutines.  We wait till here in
 255          * case std_compute_stats somehow recursively invokes us (probably not
 256          * possible, but ...)
 257          */
 258         array_extra_data = extra_data;
 259
 260         /*
 261          * We want statistics_target * 10 elements in the MCELEM array. This
 262          * multiplier is pretty arbitrary, but is meant to reflect the fact that
 263          * the number of individual elements tracked in pg_statistic ought to be
 264          * more than the number of values for a simple scalar column.
 265          */
 266         num_mcelem = stats->attstattarget * 10;
 267
 268         /*
 269          * We set bucket width equal to num_mcelem / 0.007 as per the comment
 270          * above.
 271          */
 272         bucket_width = num_mcelem * 1000 / 7;
 273
 274         /*
 275          * Create the hashtable. It will be in local memory, so we don't need to
 276          * worry about overflowing the initial size. Also we don't need to pay any
 277          * attention to locking and memory management.
 278          */
 279         elem_hash_ctl.keysize = sizeof(Datum);
 280         elem_hash_ctl.entrysize = sizeof(TrackItem);
 281         elem_hash_ctl.hash = element_hash;
 282         elem_hash_ctl.match = element_match;
 283         elem_hash_ctl.hcxt = CurrentMemoryContext;
 284         elements_tab = hash_create("Analyzed elements table",
 285                                                            num_mcelem,
 286                                                            &elem_hash_ctl,
 287                                                            HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
 288
 289         /* hashtable for array distinct elements counts */
 290         count_hash_ctl.keysize = sizeof(int);
 291         count_hash_ctl.entrysize = sizeof(DECountItem);
 292         count_hash_ctl.hcxt = CurrentMemoryContext;
 293         count_tab = hash_create("Array distinct element count table",
 294                                                         64,
 295                                                         &count_hash_ctl,
 296                                                         HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
 297
 298         /* Initialize counters. */
 299         b_current = 1;
 300         element_no = 0;
 301
 302         /* Loop over the arrays. */
 303         for (array_no = 0; array_no < samplerows; array_no++)
 304         {
 305                 Datum           value;
 306                 bool            isnull;
 307                 ArrayType  *array;
 308                 int                     num_elems;
 309                 Datum      *elem_values;
 310                 bool       *elem_nulls;
 311                 bool            null_present;
 312                 int                     j;
 313                 int64           prev_element_no = element_no;
 314                 int                     distinct_count;
 315                 bool            count_item_found;
 316
 317                 vacuum_delay_point();
 318
 319                 value = fetchfunc(stats, array_no, &isnull);
 320                 if (isnull)
 321                 {
 322                         /* ignore arrays that are null overall */
 323                         continue;
 324                 }
 325
 326                 /* Skip too-large values. */
 327                 if (toast_raw_datum_size(value) > ARRAY_WIDTH_THRESHOLD)
 328                         continue;
 329                 else
 330                         analyzed_rows++;
 331
 332                 /*
 333                  * Now detoast the array if needed, and deconstruct into datums.
 334                  */
 335                 array = DatumGetArrayTypeP(value);
 336
 337                 Assert(ARR_ELEMTYPE(array) == extra_data->type_id);
 338                 deconstruct_array(array,
 339                                                   extra_data->type_id,
 340                                                   extra_data->typlen,
 341                                                   extra_data->typbyval,
 342                                                   extra_data->typalign,
 343                                                   &elem_values, &elem_nulls, &num_elems);
 344
 345                 /*
 346                  * We loop through the elements in the array and add them to our
 347                  * tracking hashtable.
 348                  */
 349                 null_present = false;
 350                 for (j = 0; j < num_elems; j++)
 351                 {
 352                         Datum           elem_value;
 353                         bool            found;
 354
 355                         /* No null element processing other than flag setting here */
 356                         if (elem_nulls[j])
 357                         {
 358                                 null_present = true;
 359                                 continue;
 360                         }
 361
 362                         /* Lookup current element in hashtable, adding it if new */
 363                         elem_value = elem_values[j];
 364                         item = (TrackItem *) hash_search(elements_tab,
 365                                                                                          &elem_value,
 366                                                                                          HASH_ENTER, &found);
 367
 368                         if (found)
 369                         {
 370                                 /* The element value is already on the tracking list */
 371
 372                                 /*
 373                                  * The operators we assist ignore duplicate array elements, so
 374                                  * count a given distinct element only once per array.
 375                                  */
 376                                 if (item->last_container == array_no)
 377                                         continue;
 378
 379                                 item->frequency++;
 380                                 item->last_container = array_no;
 381                         }
 382                         else
 383                         {
 384                                 /* Initialize new tracking list element */
 385
 386                                 /*
 387                                  * If element type is pass-by-reference, we must copy it into
 388                                  * palloc'd space, so that we can release the array below. (We
 389                                  * do this so that the space needed for element values is
 390                                  * limited by the size of the hashtable; if we kept all the
 391                                  * array values around, it could be much more.)
 392                                  */
 393                                 item->key = datumCopy(elem_value,
 394                                                                           extra_data->typbyval,
 395                                                                           extra_data->typlen);
 396
 397                                 item->frequency = 1;
 398                                 item->delta = b_current - 1;
 399                                 item->last_container = array_no;
 400                         }
 401
 402                         /* element_no is the number of elements processed (ie N) */
 403                         element_no++;
 404
 405                         /* We prune the D structure after processing each bucket */
 406                         if (element_no % bucket_width == 0)
 407                         {
 408                                 prune_element_hashtable(elements_tab, b_current);
 409                                 b_current++;
 410                         }
 411                 }
 412
 413                 /* Count null element presence once per array. */
 414                 if (null_present)
 415                         null_elem_cnt++;
 416
 417                 /* Update frequency of the particular array distinct element count. */
 418                 distinct_count = (int) (element_no - prev_element_no);
 419                 count_item = (DECountItem *) hash_search(count_tab, &distinct_count,
 420                                                                                                  HASH_ENTER,
 421                                                                                                  &count_item_found);
 422
 423                 if (count_item_found)
 424                         count_item->frequency++;
 425                 else
 426                         count_item->frequency = 1;
 427
 428                 /* Free memory allocated while detoasting. */
 429                 if (PointerGetDatum(array) != value)
 430                         pfree(array);
 431                 pfree(elem_values);
 432                 pfree(elem_nulls);
 433         }
 434
 435         /* Skip pg_statistic slots occupied by standard statistics */
 436         slot_idx = 0;
 437         while (slot_idx < STATISTIC_NUM_SLOTS && stats->stakind[slot_idx] != 0)
 438                 slot_idx++;
 439         if (slot_idx > STATISTIC_NUM_SLOTS - 2)
 440                 elog(ERROR, "insufficient pg_statistic slots for array stats");
 441
 442         /* We can only compute real stats if we found some non-null values. */
 443         if (analyzed_rows > 0)
 444         {
 445                 int                     nonnull_cnt = analyzed_rows;
 446                 int                     count_items_count;
 447                 int                     i;
 448                 TrackItem **sort_table;
 449                 int                     track_len;
 450                 int64           cutoff_freq;
 451                 int64           minfreq,
 452                                         maxfreq;
 453
 454                 /*
 455                  * We assume the standard stats code already took care of setting
 456                  * stats_valid, stanullfrac, stawidth, stadistinct.  We'd have to
 457                  * re-compute those values if we wanted to not store the standard
 458                  * stats.
 459                  */
 460
 461                 /*
 462                  * Construct an array of the interesting hashtable items, that is,
 463                  * those meeting the cutoff frequency (s - epsilon)*N.  Also identify
 464                  * the minimum and maximum frequencies among these items.
 465                  *
 466                  * Since epsilon = s/10 and bucket_width = 1/epsilon, the cutoff
 467                  * frequency is 9*N / bucket_width.
 468                  */
 469                 cutoff_freq = 9 * element_no / bucket_width;
 470
 471                 i = hash_get_num_entries(elements_tab); /* surely enough space */
 472                 sort_table = (TrackItem **) palloc(sizeof(TrackItem *) * i);
 473
 474                 hash_seq_init(&scan_status, elements_tab);
 475                 track_len = 0;
 476                 minfreq = element_no;
 477                 maxfreq = 0;
 478                 while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
 479                 {
 480                         if (item->frequency > cutoff_freq)
 481                         {
 482                                 sort_table[track_len++] = item;
 483                                 minfreq = Min(minfreq, item->frequency);
 484                                 maxfreq = Max(maxfreq, item->frequency);
 485                         }
 486                 }
 487                 Assert(track_len <= i);
 488
 489                 /* emit some statistics for debug purposes */
 490                 elog(DEBUG3, "compute_array_stats: target # mces = %d, "
 491                          "bucket width = %d, "
 492                          "# elements = " INT64_FORMAT ", hashtable size = %d, "
 493                          "usable entries = %d",
 494                          num_mcelem, bucket_width, element_no, i, track_len);
 495
 496                 /*
 497                  * If we obtained more elements than we really want, get rid of those
 498                  * with least frequencies.  The easiest way is to qsort the array into
 499                  * descending frequency order and truncate the array.
 500                  */
 501                 if (num_mcelem < track_len)
 502                 {
 503                         qsort_interruptible(sort_table, track_len, sizeof(TrackItem *),
 504                                                                 trackitem_compare_frequencies_desc, NULL);
 505                         /* reset minfreq to the smallest frequency we're keeping */
 506                         minfreq = sort_table[num_mcelem - 1]->frequency;
 507                 }
 508                 else
 509                         num_mcelem = track_len;
 510
 511                 /* Generate MCELEM slot entry */
 512                 if (num_mcelem > 0)
 513                 {
 514                         MemoryContext old_context;
 515                         Datum      *mcelem_values;
 516                         float4     *mcelem_freqs;
 517
 518                         /*
 519                          * We want to store statistics sorted on the element value using
 520                          * the element type's default comparison function.  This permits
 521                          * fast binary searches in selectivity estimation functions.
 522                          */
 523                         qsort_interruptible(sort_table, num_mcelem, sizeof(TrackItem *),
 524                                                                 trackitem_compare_element, NULL);
 525
 526                         /* Must copy the target values into anl_context */
 527                         old_context = MemoryContextSwitchTo(stats->anl_context);
 528
 529                         /*
 530                          * We sorted statistics on the element value, but we want to be
 531                          * able to find the minimal and maximal frequencies without going
 532                          * through all the values.  We also want the frequency of null
 533                          * elements.  Store these three values at the end of mcelem_freqs.
 534                          */
 535                         mcelem_values = (Datum *) palloc(num_mcelem * sizeof(Datum));
 536                         mcelem_freqs = (float4 *) palloc((num_mcelem + 3) * sizeof(float4));
 537
 538                         /*
 539                          * See comments above about use of nonnull_cnt as the divisor for
 540                          * the final frequency estimates.
 541                          */
 542                         for (i = 0; i < num_mcelem; i++)
 543                         {
 544                                 TrackItem  *titem = sort_table[i];
 545
 546                                 mcelem_values[i] = datumCopy(titem->key,
 547                                                                                          extra_data->typbyval,
 548                                                                                          extra_data->typlen);
 549                                 mcelem_freqs[i] = (double) titem->frequency /
 550                                         (double) nonnull_cnt;
 551                         }
 552                         mcelem_freqs[i++] = (double) minfreq / (double) nonnull_cnt;
 553                         mcelem_freqs[i++] = (double) maxfreq / (double) nonnull_cnt;
 554                         mcelem_freqs[i++] = (double) null_elem_cnt / (double) nonnull_cnt;
 555
 556                         MemoryContextSwitchTo(old_context);
 557
 558                         stats->stakind[slot_idx] = STATISTIC_KIND_MCELEM;
 559                         stats->staop[slot_idx] = extra_data->eq_opr;
 560                         stats->stacoll[slot_idx] = extra_data->coll_id;
 561                         stats->stanumbers[slot_idx] = mcelem_freqs;
 562                         /* See above comment about extra stanumber entries */
 563                         stats->numnumbers[slot_idx] = num_mcelem + 3;
 564                         stats->stavalues[slot_idx] = mcelem_values;
 565                         stats->numvalues[slot_idx] = num_mcelem;
 566                         /* We are storing values of element type */
 567                         stats->statypid[slot_idx] = extra_data->type_id;
 568                         stats->statyplen[slot_idx] = extra_data->typlen;
 569                         stats->statypbyval[slot_idx] = extra_data->typbyval;
 570                         stats->statypalign[slot_idx] = extra_data->typalign;
 571                         slot_idx++;
 572                 }
 573
 574                 /* Generate DECHIST slot entry */
 575                 count_items_count = hash_get_num_entries(count_tab);
 576                 if (count_items_count > 0)
 577                 {
 578                         int                     num_hist = stats->attstattarget;
 579                         DECountItem **sorted_count_items;
 580                         int                     j;
 581                         int                     delta;
 582                         int64           frac;
 583                         float4     *hist;
 584
 585                         /* num_hist must be at least 2 for the loop below to work */
 586                         num_hist = Max(num_hist, 2);
 587
 588                         /*
 589                          * Create an array of DECountItem pointers, and sort them into
 590                          * increasing count order.
 591                          */
 592                         sorted_count_items = (DECountItem **)
 593                                 palloc(sizeof(DECountItem *) * count_items_count);
 594                         hash_seq_init(&scan_status, count_tab);
 595                         j = 0;
 596                         while ((count_item = (DECountItem *) hash_seq_search(&scan_status)) != NULL)
 597                         {
 598                                 sorted_count_items[j++] = count_item;
 599                         }
 600                         qsort_interruptible(sorted_count_items, count_items_count,
 601                                                                 sizeof(DECountItem *),
 602                                                                 countitem_compare_count, NULL);
 603
 604                         /*
 605                          * Prepare to fill stanumbers with the histogram, followed by the
 606                          * average count.  This array must be stored in anl_context.
 607                          */
 608                         hist = (float4 *)
 609                                 MemoryContextAlloc(stats->anl_context,
 610                                                                    sizeof(float4) * (num_hist + 1));
 611                         hist[num_hist] = (double) element_no / (double) nonnull_cnt;
 612
 613                         /*----------
 614                          * Construct the histogram of distinct-element counts (DECs).
 615                          *
 616                          * The object of this loop is to copy the min and max DECs to
 617                          * hist[0] and hist[num_hist - 1], along with evenly-spaced DECs
 618                          * in between (where "evenly-spaced" is with reference to the
 619                          * whole input population of arrays).  If we had a complete sorted
 620                          * array of DECs, one per analyzed row, the i'th hist value would
 621                          * come from DECs[i * (analyzed_rows - 1) / (num_hist - 1)]
 622                          * (compare the histogram-making loop in compute_scalar_stats()).
 623                          * But instead of that we have the sorted_count_items[] array,
 624                          * which holds unique DEC values with their frequencies (that is,
 625                          * a run-length-compressed version of the full array).  So we
 626                          * control advancing through sorted_count_items[] with the
 627                          * variable "frac", which is defined as (x - y) * (num_hist - 1),
 628                          * where x is the index in the notional DECs array corresponding
 629                          * to the start of the next sorted_count_items[] element's run,
 630                          * and y is the index in DECs from which we should take the next
 631                          * histogram value.  We have to advance whenever x <= y, that is
 632                          * frac <= 0.  The x component is the sum of the frequencies seen
 633                          * so far (up through the current sorted_count_items[] element),
 634                          * and of course y * (num_hist - 1) = i * (analyzed_rows - 1),
 635                          * per the subscript calculation above.  (The subscript calculation
 636                          * implies dropping any fractional part of y; in this formulation
 637                          * that's handled by not advancing until frac reaches 1.)
 638                          *
 639                          * Even though frac has a bounded range, it could overflow int32
 640                          * when working with very large statistics targets, so we do that
 641                          * math in int64.
 642                          *----------
 643                          */
 644                         delta = analyzed_rows - 1;
 645                         j = 0;                          /* current index in sorted_count_items */
 646                         /* Initialize frac for sorted_count_items[0]; y is initially 0 */
 647                         frac = (int64) sorted_count_items[0]->frequency * (num_hist - 1);
 648                         for (i = 0; i < num_hist; i++)
 649                         {
 650                                 while (frac <= 0)
 651                                 {
 652                                         /* Advance, and update x component of frac */
 653                                         j++;
 654                                         frac += (int64) sorted_count_items[j]->frequency * (num_hist - 1);
 655                                 }
 656                                 hist[i] = sorted_count_items[j]->count;
 657                                 frac -= delta;  /* update y for upcoming i increment */
 658                         }
 659                         Assert(j == count_items_count - 1);
 660
 661                         stats->stakind[slot_idx] = STATISTIC_KIND_DECHIST;
 662                         stats->staop[slot_idx] = extra_data->eq_opr;
 663                         stats->stacoll[slot_idx] = extra_data->coll_id;
 664                         stats->stanumbers[slot_idx] = hist;
 665                         stats->numnumbers[slot_idx] = num_hist + 1;
 666                         slot_idx++;
 667                 }
 668         }
 669
 670         /*
 671          * We don't need to bother cleaning up any of our temporary palloc's. The
 672          * hashtable should also go away, as it used a child memory context.
 673          */
 674 }
 675
 676 /*
 677  * A function to prune the D structure from the Lossy Counting algorithm.
 678  * Consult compute_tsvector_stats() for wider explanation.
 679  */
 680 static void
 681 prune_element_hashtable(HTAB *elements_tab, int b_current)
 682 {
 683         HASH_SEQ_STATUS scan_status;
 684         TrackItem  *item;
 685
 686         hash_seq_init(&scan_status, elements_tab);
 687         while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
 688         {
 689                 if (item->frequency + item->delta <= b_current)
 690                 {
 691                         Datum           value = item->key;
 692
 693                         if (hash_search(elements_tab, &item->key,
 694                                                         HASH_REMOVE, NULL) == NULL)
 695                                 elog(ERROR, "hash table corrupted");
 696                         /* We should free memory if element is not passed by value */
 697                         if (!array_extra_data->typbyval)
 698                                 pfree(DatumGetPointer(value));
 699                 }
 700         }
 701 }
 702
 703 /*
 704  * Hash function for elements.
 705  *
 706  * We use the element type's default hash opclass, and the column collation
 707  * if the type is collation-sensitive.
 708  */
 709 static uint32
 710 element_hash(const void *key, Size keysize)
 711 {
 712         Datum           d = *((const Datum *) key);
 713         Datum           h;
 714
 715         h = FunctionCall1Coll(array_extra_data->hash,
 716                                                   array_extra_data->coll_id,
 717                                                   d);
 718         return DatumGetUInt32(h);
 719 }
 720
 721 /*
 722  * Matching function for elements, to be used in hashtable lookups.
 723  */
 724 static int
 725 element_match(const void *key1, const void *key2, Size keysize)
 726 {
 727         /* The keysize parameter is superfluous here */
 728         return element_compare(key1, key2);
 729 }
 730
 731 /*
 732  * Comparison function for elements.
 733  *
 734  * We use the element type's default btree opclass, and the column collation
 735  * if the type is collation-sensitive.
 736  *
 737  * XXX consider using SortSupport infrastructure
 738  */
 739 static int
 740 element_compare(const void *key1, const void *key2)
 741 {
 742         Datum           d1 = *((const Datum *) key1);
 743         Datum           d2 = *((const Datum *) key2);
 744         Datum           c;
 745
 746         c = FunctionCall2Coll(array_extra_data->cmp,
 747                                                   array_extra_data->coll_id,
 748                                                   d1, d2);
 749         return DatumGetInt32(c);
 750 }
 751
 752 /*
 753  * Comparator for sorting TrackItems by frequencies (descending sort)
 754  */
 755 static int
 756 trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg)
 757 {
 758         const TrackItem *const *t1 = (const TrackItem *const *) e1;
 759         const TrackItem *const *t2 = (const TrackItem *const *) e2;
 760
 761         return (*t2)->frequency - (*t1)->frequency;
 762 }
 763
 764 /*
 765  * Comparator for sorting TrackItems by element values
 766  */
 767 static int
 768 trackitem_compare_element(const void *e1, const void *e2, void *arg)
 769 {
 770         const TrackItem *const *t1 = (const TrackItem *const *) e1;
 771         const TrackItem *const *t2 = (const TrackItem *const *) e2;
 772
 773         return element_compare(&(*t1)->key, &(*t2)->key);
 774 }
 775
 776 /*
 777  * Comparator for sorting DECountItems by count
 778  */
 779 static int
 780 countitem_compare_count(const void *e1, const void *e2, void *arg)
 781 {
 782         const DECountItem *const *t1 = (const DECountItem *const *) e1;
 783         const DECountItem *const *t2 = (const DECountItem *const *) e2;
 784
 785         if ((*t1)->count < (*t2)->count)
 786                 return -1;
 787         else if ((*t1)->count == (*t2)->count)
 788                 return 0;
 789         else
 790                 return 1;
 791 }