PostgreSQL Source Code  git master
mcv.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * mcv.c
4  * POSTGRES multivariate MCV lists
5  *
6  *
7  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * IDENTIFICATION
11  * src/backend/statistics/mcv.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include <math.h>
18 
19 #include "access/htup_details.h"
20 #include "catalog/pg_collation.h"
23 #include "fmgr.h"
24 #include "funcapi.h"
25 #include "nodes/nodeFuncs.h"
26 #include "optimizer/clauses.h"
28 #include "statistics/statistics.h"
29 #include "utils/array.h"
30 #include "utils/builtins.h"
31 #include "utils/bytea.h"
32 #include "utils/fmgroids.h"
33 #include "utils/fmgrprotos.h"
34 #include "utils/lsyscache.h"
35 #include "utils/selfuncs.h"
36 #include "utils/syscache.h"
37 #include "utils/typcache.h"
38 
39 /*
40  * Computes size of a serialized MCV item, depending on the number of
41  * dimensions (columns) the statistic is defined on. The datum values are
42  * stored in a separate array (deduplicated, to minimize the size), and
43  * so the serialized items only store uint16 indexes into that array.
44  *
45  * Each serialized item stores (in this order):
46  *
47  * - indexes to values (ndim * sizeof(uint16))
48  * - null flags (ndim * sizeof(bool))
49  * - frequency (sizeof(double))
50  * - base_frequency (sizeof(double))
51  *
52  * There is no alignment padding within an MCV item.
53  * So in total each MCV item requires this many bytes:
54  *
55  * ndim * (sizeof(uint16) + sizeof(bool)) + 2 * sizeof(double)
56  */
57 #define ITEM_SIZE(ndims) \
58  ((ndims) * (sizeof(uint16) + sizeof(bool)) + 2 * sizeof(double))
59 
60 /*
61  * Used to compute size of serialized MCV list representation.
62  */
63 #define MinSizeOfMCVList \
64  (VARHDRSZ + sizeof(uint32) * 3 + sizeof(AttrNumber))
65 
66 /*
67  * Size of the serialized MCV list, excluding the space needed for
68  * deduplicated per-dimension values. The macro is meant to be used
69  * when it's not yet safe to access the serialized info about amount
70  * of data for each column.
71  */
72 #define SizeOfMCVList(ndims,nitems) \
73  ((MinSizeOfMCVList + sizeof(Oid) * (ndims)) + \
74  ((ndims) * sizeof(DimensionInfo)) + \
75  ((nitems) * ITEM_SIZE(ndims)))
76 
77 static MultiSortSupport build_mss(VacAttrStats **stats, int numattrs);
78 
79 static SortItem *build_distinct_groups(int numrows, SortItem *items,
80  MultiSortSupport mss, int *ndistinct);
81 
82 static SortItem **build_column_frequencies(SortItem *groups, int ngroups,
83  MultiSortSupport mss, int *ncounts);
84 
85 static int count_distinct_groups(int numrows, SortItem *items,
86  MultiSortSupport mss);
87 
88 /*
89  * Compute new value for bitmap item, considering whether it's used for
90  * clauses connected by AND/OR.
91  */
92 #define RESULT_MERGE(value, is_or, match) \
93  ((is_or) ? ((value) || (match)) : ((value) && (match)))
94 
95 /*
96  * When processing a list of clauses, the bitmap item may get set to a value
97  * such that additional clauses can't change it. For example, when processing
98  * a list of clauses connected to AND, as soon as the item gets set to 'false'
99  * then it'll remain like that. Similarly clauses connected by OR and 'true'.
100  *
101  * Returns true when the value in the bitmap can't change no matter how the
102  * remaining clauses are evaluated.
103  */
104 #define RESULT_IS_FINAL(value, is_or) ((is_or) ? (value) : (!(value)))
105 
106 /*
107  * get_mincount_for_mcv_list
108  * Determine the minimum number of times a value needs to appear in
109  * the sample for it to be included in the MCV list.
110  *
111  * We want to keep only values that appear sufficiently often in the
112  * sample that it is reasonable to extrapolate their sample frequencies to
113  * the entire table. We do this by placing an upper bound on the relative
114  * standard error of the sample frequency, so that any estimates the
115  * planner generates from the MCV statistics can be expected to be
116  * reasonably accurate.
117  *
118  * Since we are sampling without replacement, the sample frequency of a
119  * particular value is described by a hypergeometric distribution. A
120  * common rule of thumb when estimating errors in this situation is to
121  * require at least 10 instances of the value in the sample, in which case
122  * the distribution can be approximated by a normal distribution, and
123  * standard error analysis techniques can be applied. Given a sample size
124  * of n, a population size of N, and a sample frequency of p=cnt/n, the
125  * standard error of the proportion p is given by
126  * SE = sqrt(p*(1-p)/n) * sqrt((N-n)/(N-1))
127  * where the second term is the finite population correction. To get
128  * reasonably accurate planner estimates, we impose an upper bound on the
129  * relative standard error of 20% -- i.e., SE/p < 0.2. This 20% relative
130  * error bound is fairly arbitrary, but has been found empirically to work
131  * well. Rearranging this formula gives a lower bound on the number of
132  * instances of the value seen:
133  * cnt > n*(N-n) / (N-n+0.04*n*(N-1))
134  * This bound is at most 25, and approaches 0 as n approaches 0 or N. The
135  * case where n approaches 0 cannot happen in practice, since the sample
136  * size is at least 300. The case where n approaches N corresponds to
137  * sampling the whole the table, in which case it is reasonable to keep
138  * the whole MCV list (have no lower bound), so it makes sense to apply
139  * this formula for all inputs, even though the above derivation is
140  * technically only valid when the right hand side is at least around 10.
141  *
142  * An alternative way to look at this formula is as follows -- assume that
143  * the number of instances of the value seen scales up to the entire
144  * table, so that the population count is K=N*cnt/n. Then the distribution
145  * in the sample is a hypergeometric distribution parameterised by N, n
146  * and K, and the bound above is mathematically equivalent to demanding
147  * that the standard deviation of that distribution is less than 20% of
148  * its mean. Thus the relative errors in any planner estimates produced
149  * from the MCV statistics are likely to be not too large.
150  */
151 static double
152 get_mincount_for_mcv_list(int samplerows, double totalrows)
153 {
154  double n = samplerows;
155  double N = totalrows;
156  double numer,
157  denom;
158 
159  numer = n * (N - n);
160  denom = N - n + 0.04 * n * (N - 1);
161 
162  /* Guard against division by zero (possible if n = N = 1) */
163  if (denom == 0.0)
164  return 0.0;
165 
166  return numer / denom;
167 }
168 
169 /*
170  * Builds MCV list from the set of sampled rows.
171  *
172  * The algorithm is quite simple:
173  *
174  * (1) sort the data (default collation, '<' for the data type)
175  *
176  * (2) count distinct groups, decide how many to keep
177  *
178  * (3) build the MCV list using the threshold determined in (2)
179  *
180  * (4) remove rows represented by the MCV from the sample
181  *
182  */
183 MCVList *
184 statext_mcv_build(int numrows, HeapTuple *rows, Bitmapset *attrs,
185  VacAttrStats **stats, double totalrows, int stattarget)
186 {
187  int i,
188  numattrs,
189  ngroups,
190  nitems;
191  AttrNumber *attnums;
192  double mincount;
193  SortItem *items;
194  SortItem *groups;
195  MCVList *mcvlist = NULL;
196  MultiSortSupport mss;
197 
198  attnums = build_attnums_array(attrs, &numattrs);
199 
200  /* comparator for all the columns */
201  mss = build_mss(stats, numattrs);
202 
203  /* sort the rows */
204  items = build_sorted_items(numrows, &nitems, rows, stats[0]->tupDesc,
205  mss, numattrs, attnums);
206 
207  if (!items)
208  return NULL;
209 
210  /* transform the sorted rows into groups (sorted by frequency) */
211  groups = build_distinct_groups(nitems, items, mss, &ngroups);
212 
213  /*
214  * Maximum number of MCV items to store, based on the statistics target we
215  * computed for the statistics object (from target set for the object
216  * itself, attributes and the system default). In any case, we can't keep
217  * more groups than we have available.
218  */
219  nitems = stattarget;
220  if (nitems > ngroups)
221  nitems = ngroups;
222 
223  /*
224  * Decide how many items to keep in the MCV list. We can't use the same
225  * algorithm as per-column MCV lists, because that only considers the
226  * actual group frequency - but we're primarily interested in how the
227  * actual frequency differs from the base frequency (product of simple
228  * per-column frequencies, as if the columns were independent).
229  *
230  * Using the same algorithm might exclude items that are close to the
231  * "average" frequency of the sample. But that does not say whether the
232  * observed frequency is close to the base frequency or not. We also need
233  * to consider unexpectedly uncommon items (again, compared to the base
234  * frequency), and the single-column algorithm does not have to.
235  *
236  * We simply decide how many items to keep by computing minimum count
237  * using get_mincount_for_mcv_list() and then keep all items that seem to
238  * be more common than that.
239  */
240  mincount = get_mincount_for_mcv_list(numrows, totalrows);
241 
242  /*
243  * Walk the groups until we find the first group with a count below the
244  * mincount threshold (the index of that group is the number of groups we
245  * want to keep).
246  */
247  for (i = 0; i < nitems; i++)
248  {
249  if (groups[i].count < mincount)
250  {
251  nitems = i;
252  break;
253  }
254  }
255 
256  /*
257  * At this point we know the number of items for the MCV list. There might
258  * be none (for uniform distribution with many groups), and in that case
259  * there will be no MCV list. Otherwise construct the MCV list.
260  */
261  if (nitems > 0)
262  {
263  int j;
264  SortItem key;
265  MultiSortSupport tmp;
266 
267  /* frequencies for values in each attribute */
268  SortItem **freqs;
269  int *nfreqs;
270 
271  /* used to search values */
273  + sizeof(SortSupportData));
274 
275  /* compute frequencies for values in each column */
276  nfreqs = (int *) palloc0(sizeof(int) * numattrs);
277  freqs = build_column_frequencies(groups, ngroups, mss, nfreqs);
278 
279  /*
280  * Allocate the MCV list structure, set the global parameters.
281  */
282  mcvlist = (MCVList *) palloc0(offsetof(MCVList, items) +
283  sizeof(MCVItem) * nitems);
284 
285  mcvlist->magic = STATS_MCV_MAGIC;
286  mcvlist->type = STATS_MCV_TYPE_BASIC;
287  mcvlist->ndimensions = numattrs;
288  mcvlist->nitems = nitems;
289 
290  /* store info about data type OIDs */
291  for (i = 0; i < numattrs; i++)
292  mcvlist->types[i] = stats[i]->attrtypid;
293 
294  /* Copy the first chunk of groups into the result. */
295  for (i = 0; i < nitems; i++)
296  {
297  /* just pointer to the proper place in the list */
298  MCVItem *item = &mcvlist->items[i];
299 
300  item->values = (Datum *) palloc(sizeof(Datum) * numattrs);
301  item->isnull = (bool *) palloc(sizeof(bool) * numattrs);
302 
303  /* copy values for the group */
304  memcpy(item->values, groups[i].values, sizeof(Datum) * numattrs);
305  memcpy(item->isnull, groups[i].isnull, sizeof(bool) * numattrs);
306 
307  /* groups should be sorted by frequency in descending order */
308  Assert((i == 0) || (groups[i - 1].count >= groups[i].count));
309 
310  /* group frequency */
311  item->frequency = (double) groups[i].count / numrows;
312 
313  /* base frequency, if the attributes were independent */
314  item->base_frequency = 1.0;
315  for (j = 0; j < numattrs; j++)
316  {
317  SortItem *freq;
318 
319  /* single dimension */
320  tmp->ndims = 1;
321  tmp->ssup[0] = mss->ssup[j];
322 
323  /* fill search key */
324  key.values = &groups[i].values[j];
325  key.isnull = &groups[i].isnull[j];
326 
327  freq = (SortItem *) bsearch_arg(&key, freqs[j], nfreqs[j],
328  sizeof(SortItem),
329  multi_sort_compare, tmp);
330 
331  item->base_frequency *= ((double) freq->count) / numrows;
332  }
333  }
334 
335  pfree(nfreqs);
336  pfree(freqs);
337  }
338 
339  pfree(items);
340  pfree(groups);
341 
342  return mcvlist;
343 }
344 
345 /*
346  * build_mss
347  * build MultiSortSupport for the attributes passed in attrs
348  */
349 static MultiSortSupport
350 build_mss(VacAttrStats **stats, int numattrs)
351 {
352  int i;
353 
354  /* Sort by multiple columns (using array of SortSupport) */
355  MultiSortSupport mss = multi_sort_init(numattrs);
356 
357  /* prepare the sort functions for all the attributes */
358  for (i = 0; i < numattrs; i++)
359  {
360  VacAttrStats *colstat = stats[i];
362 
363  type = lookup_type_cache(colstat->attrtypid, TYPECACHE_LT_OPR);
364  if (type->lt_opr == InvalidOid) /* shouldn't happen */
365  elog(ERROR, "cache lookup failed for ordering operator for type %u",
366  colstat->attrtypid);
367 
368  multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
369  }
370 
371  return mss;
372 }
373 
374 /*
375  * count_distinct_groups
376  * count distinct combinations of SortItems in the array
377  *
378  * The array is assumed to be sorted according to the MultiSortSupport.
379  */
380 static int
382 {
383  int i;
384  int ndistinct;
385 
386  ndistinct = 1;
387  for (i = 1; i < numrows; i++)
388  {
389  /* make sure the array really is sorted */
390  Assert(multi_sort_compare(&items[i], &items[i - 1], mss) >= 0);
391 
392  if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
393  ndistinct += 1;
394  }
395 
396  return ndistinct;
397 }
398 
399 /*
400  * compare_sort_item_count
401  * comparator for sorting items by count (frequencies) in descending order
402  */
403 static int
404 compare_sort_item_count(const void *a, const void *b)
405 {
406  SortItem *ia = (SortItem *) a;
407  SortItem *ib = (SortItem *) b;
408 
409  if (ia->count == ib->count)
410  return 0;
411  else if (ia->count > ib->count)
412  return -1;
413 
414  return 1;
415 }
416 
417 /*
418  * build_distinct_groups
419  * build an array of SortItems for distinct groups and counts matching items
420  *
421  * The input array is assumed to be sorted
422  */
423 static SortItem *
425  int *ndistinct)
426 {
427  int i,
428  j;
429  int ngroups = count_distinct_groups(numrows, items, mss);
430 
431  SortItem *groups = (SortItem *) palloc(ngroups * sizeof(SortItem));
432 
433  j = 0;
434  groups[0] = items[0];
435  groups[0].count = 1;
436 
437  for (i = 1; i < numrows; i++)
438  {
439  /* Assume sorted in ascending order. */
440  Assert(multi_sort_compare(&items[i], &items[i - 1], mss) >= 0);
441 
442  /* New distinct group detected. */
443  if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
444  {
445  groups[++j] = items[i];
446  groups[j].count = 0;
447  }
448 
449  groups[j].count++;
450  }
451 
452  /* ensure we filled the expected number of distinct groups */
453  Assert(j + 1 == ngroups);
454 
455  /* Sort the distinct groups by frequency (in descending order). */
456  pg_qsort((void *) groups, ngroups, sizeof(SortItem),
458 
459  *ndistinct = ngroups;
460  return groups;
461 }
462 
463 /* compare sort items (single dimension) */
464 static int
465 sort_item_compare(const void *a, const void *b, void *arg)
466 {
467  SortSupport ssup = (SortSupport) arg;
468  SortItem *ia = (SortItem *) a;
469  SortItem *ib = (SortItem *) b;
470 
471  return ApplySortComparator(ia->values[0], ia->isnull[0],
472  ib->values[0], ib->isnull[0],
473  ssup);
474 }
475 
476 /*
477  * build_column_frequencies
478  * compute frequencies of values in each column
479  *
480  * This returns an array of SortItems for each attribute the MCV is built
481  * on, with a frequency (number of occurrences) for each value. This is
482  * then used to compute "base" frequency of MCV items.
483  *
484  * All the memory is allocated in a single chunk, so that a single pfree
485  * is enough to release it. We do not allocate space for values/isnull
486  * arrays in the SortItems, because we can simply point into the input
487  * groups directly.
488  */
489 static SortItem **
490 build_column_frequencies(SortItem *groups, int ngroups,
491  MultiSortSupport mss, int *ncounts)
492 {
493  int i,
494  dim;
495  SortItem **result;
496  char *ptr;
497 
498  Assert(groups);
499  Assert(ncounts);
500 
501  /* allocate arrays for all columns as a single chunk */
502  ptr = palloc(MAXALIGN(sizeof(SortItem *) * mss->ndims) +
503  mss->ndims * MAXALIGN(sizeof(SortItem) * ngroups));
504 
505  /* initial array of pointers */
506  result = (SortItem **) ptr;
507  ptr += MAXALIGN(sizeof(SortItem *) * mss->ndims);
508 
509  for (dim = 0; dim < mss->ndims; dim++)
510  {
511  SortSupport ssup = &mss->ssup[dim];
512 
513  /* array of values for a single column */
514  result[dim] = (SortItem *) ptr;
515  ptr += MAXALIGN(sizeof(SortItem) * ngroups);
516 
517  /* extract data for the dimension */
518  for (i = 0; i < ngroups; i++)
519  {
520  /* point into the input groups */
521  result[dim][i].values = &groups[i].values[dim];
522  result[dim][i].isnull = &groups[i].isnull[dim];
523  result[dim][i].count = groups[i].count;
524  }
525 
526  /* sort the values, deduplicate */
527  qsort_arg((void *) result[dim], ngroups, sizeof(SortItem),
528  sort_item_compare, ssup);
529 
530  /*
531  * Identify distinct values, compute frequency (there might be
532  * multiple MCV items containing this value, so we need to sum counts
533  * from all of them.
534  */
535  ncounts[dim] = 1;
536  for (i = 1; i < ngroups; i++)
537  {
538  if (sort_item_compare(&result[dim][i - 1], &result[dim][i], ssup) == 0)
539  {
540  result[dim][ncounts[dim] - 1].count += result[dim][i].count;
541  continue;
542  }
543 
544  result[dim][ncounts[dim]] = result[dim][i];
545 
546  ncounts[dim]++;
547  }
548  }
549 
550  return result;
551 }
552 
553 /*
554  * statext_mcv_load
555  * Load the MCV list for the indicated pg_statistic_ext tuple
556  */
557 MCVList *
559 {
560  MCVList *result;
561  bool isnull;
562  Datum mcvlist;
564 
565  if (!HeapTupleIsValid(htup))
566  elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
567 
568  mcvlist = SysCacheGetAttr(STATEXTDATASTXOID, htup,
569  Anum_pg_statistic_ext_data_stxdmcv, &isnull);
570 
571  if (isnull)
572  elog(ERROR,
573  "requested statistic kind \"%c\" is not yet built for statistics object %u",
574  STATS_EXT_DEPENDENCIES, mvoid);
575 
576  result = statext_mcv_deserialize(DatumGetByteaP(mcvlist));
577 
578  ReleaseSysCache(htup);
579 
580  return result;
581 }
582 
583 
584 /*
585  * statext_mcv_serialize
586  * Serialize MCV list into a pg_mcv_list value.
587  *
588  * The MCV items may include values of various data types, and it's reasonable
589  * to expect redundancy (values for a given attribute, repeated for multiple
590  * MCV list items). So we deduplicate the values into arrays, and then replace
591  * the values by indexes into those arrays.
592  *
593  * The overall structure of the serialized representation looks like this:
594  *
595  * +---------------+----------------+---------------------+-------+
596  * | header fields | dimension info | deduplicated values | items |
597  * +---------------+----------------+---------------------+-------+
598  *
599  * Where dimension info stores information about type of K-th attribute (e.g.
600  * typlen, typbyval and length of deduplicated values). Deduplicated values
601  * store deduplicated values for each attribute. And items store the actual
602  * MCV list items, with values replaced by indexes into the arrays.
603  *
604  * When serializing the items, we use uint16 indexes. The number of MCV items
605  * is limited by the statistics target (which is capped to 10k at the moment).
606  * We might increase this to 65k and still fit into uint16, so there's a bit of
607  * slack. Furthermore, this limit is on the number of distinct values per column,
608  * and we usually have few of those (and various combinations of them for the
609  * those MCV list). So uint16 seems fine for now.
610  *
611  * We don't really expect the serialization to save as much space as for
612  * histograms, as we are not doing any bucket splits (which is the source
613  * of high redundancy in histograms).
614  *
615  * TODO: Consider packing boolean flags (NULL) for each item into a single char
616  * (or a longer type) instead of using an array of bool items.
617  */
618 bytea *
620 {
621  int i;
622  int dim;
623  int ndims = mcvlist->ndimensions;
624 
625  SortSupport ssup;
626  DimensionInfo *info;
627 
628  Size total_length;
629 
630  /* serialized items (indexes into arrays, etc.) */
631  bytea *raw;
632  char *ptr;
633  char *endptr PG_USED_FOR_ASSERTS_ONLY;
634 
635  /* values per dimension (and number of non-NULL values) */
636  Datum **values = (Datum **) palloc0(sizeof(Datum *) * ndims);
637  int *counts = (int *) palloc0(sizeof(int) * ndims);
638 
639  /*
640  * We'll include some rudimentary information about the attribute types
641  * (length, by-val flag), so that we don't have to look them up while
642  * deserializating the MCV list (we already have the type OID in the
643  * header). This is safe, because when changing type of the attribute the
644  * statistics gets dropped automatically. We need to store the info about
645  * the arrays of deduplicated values anyway.
646  */
647  info = (DimensionInfo *) palloc0(sizeof(DimensionInfo) * ndims);
648 
649  /* sort support data for all attributes included in the MCV list */
650  ssup = (SortSupport) palloc0(sizeof(SortSupportData) * ndims);
651 
652  /* collect and deduplicate values for each dimension (attribute) */
653  for (dim = 0; dim < ndims; dim++)
654  {
655  int ndistinct;
656  TypeCacheEntry *typentry;
657 
658  /*
659  * Lookup the LT operator (can't get it from stats extra_data, as we
660  * don't know how to interpret that - scalar vs. array etc.).
661  */
662  typentry = lookup_type_cache(stats[dim]->attrtypid, TYPECACHE_LT_OPR);
663 
664  /* copy important info about the data type (length, by-value) */
665  info[dim].typlen = stats[dim]->attrtype->typlen;
666  info[dim].typbyval = stats[dim]->attrtype->typbyval;
667 
668  /* allocate space for values in the attribute and collect them */
669  values[dim] = (Datum *) palloc0(sizeof(Datum) * mcvlist->nitems);
670 
671  for (i = 0; i < mcvlist->nitems; i++)
672  {
673  /* skip NULL values - we don't need to deduplicate those */
674  if (mcvlist->items[i].isnull[dim])
675  continue;
676 
677  /* append the value at the end */
678  values[dim][counts[dim]] = mcvlist->items[i].values[dim];
679  counts[dim] += 1;
680  }
681 
682  /* if there are just NULL values in this dimension, we're done */
683  if (counts[dim] == 0)
684  continue;
685 
686  /* sort and deduplicate the data */
687  ssup[dim].ssup_cxt = CurrentMemoryContext;
688  ssup[dim].ssup_collation = stats[dim]->attrcollid;
689  ssup[dim].ssup_nulls_first = false;
690 
691  PrepareSortSupportFromOrderingOp(typentry->lt_opr, &ssup[dim]);
692 
693  qsort_arg(values[dim], counts[dim], sizeof(Datum),
694  compare_scalars_simple, &ssup[dim]);
695 
696  /*
697  * Walk through the array and eliminate duplicate values, but keep the
698  * ordering (so that we can do bsearch later). We know there's at
699  * least one item as (counts[dim] != 0), so we can skip the first
700  * element.
701  */
702  ndistinct = 1; /* number of distinct values */
703  for (i = 1; i < counts[dim]; i++)
704  {
705  /* expect sorted array */
706  Assert(compare_datums_simple(values[dim][i - 1], values[dim][i], &ssup[dim]) <= 0);
707 
708  /* if the value is the same as the previous one, we can skip it */
709  if (!compare_datums_simple(values[dim][i - 1], values[dim][i], &ssup[dim]))
710  continue;
711 
712  values[dim][ndistinct] = values[dim][i];
713  ndistinct += 1;
714  }
715 
716  /* we must not exceed PG_UINT16_MAX, as we use uint16 indexes */
717  Assert(ndistinct <= PG_UINT16_MAX);
718 
719  /*
720  * Store additional info about the attribute - number of deduplicated
721  * values, and also size of the serialized data. For fixed-length data
722  * types this is trivial to compute, for varwidth types we need to
723  * actually walk the array and sum the sizes.
724  */
725  info[dim].nvalues = ndistinct;
726 
727  if (info[dim].typbyval) /* by-value data types */
728  {
729  info[dim].nbytes = info[dim].nvalues * info[dim].typlen;
730 
731  /*
732  * We copy the data into the MCV item during deserialization, so
733  * we don't need to allocate any extra space.
734  */
735  info[dim].nbytes_aligned = 0;
736  }
737  else if (info[dim].typlen > 0) /* fixed-length by-ref */
738  {
739  /*
740  * We don't care about alignment in the serialized data, so we
741  * pack the data as much as possible. But we also track how much
742  * data will be needed after deserialization, and in that case we
743  * need to account for alignment of each item.
744  *
745  * Note: As the items are fixed-length, we could easily compute
746  * this during deserialization, but we do it here anyway.
747  */
748  info[dim].nbytes = info[dim].nvalues * info[dim].typlen;
749  info[dim].nbytes_aligned = info[dim].nvalues * MAXALIGN(info[dim].typlen);
750  }
751  else if (info[dim].typlen == -1) /* varlena */
752  {
753  info[dim].nbytes = 0;
754  info[dim].nbytes_aligned = 0;
755  for (i = 0; i < info[dim].nvalues; i++)
756  {
757  Size len;
758 
759  /*
760  * For varlena values, we detoast the values and store the
761  * length and data separately. We don't bother with alignment
762  * here, which means that during deserialization we need to
763  * copy the fields and only access the copies.
764  */
765  values[dim][i] = PointerGetDatum(PG_DETOAST_DATUM(values[dim][i]));
766 
767  /* serialized length (uint32 length + data) */
768  len = VARSIZE_ANY_EXHDR(values[dim][i]);
769  info[dim].nbytes += sizeof(uint32); /* length */
770  info[dim].nbytes += len; /* value (no header) */
771 
772  /*
773  * During deserialization we'll build regular varlena values
774  * with full headers, and we need to align them properly.
775  */
776  info[dim].nbytes_aligned += MAXALIGN(VARHDRSZ + len);
777  }
778  }
779  else if (info[dim].typlen == -2) /* cstring */
780  {
781  info[dim].nbytes = 0;
782  info[dim].nbytes_aligned = 0;
783  for (i = 0; i < info[dim].nvalues; i++)
784  {
785  Size len;
786 
787  /*
788  * For cstring, we do similar thing as for varlena - first we
789  * store the length as uint32 and then the data. We don't care
790  * about alignment, which means that during deserialization we
791  * need to copy the fields and only access the copies.
792  */
793 
794  /* c-strings include terminator, so +1 byte */
795  len = strlen(DatumGetCString(values[dim][i])) + 1;
796  info[dim].nbytes += sizeof(uint32); /* length */
797  info[dim].nbytes += len; /* value */
798 
799  /* space needed for properly aligned deserialized copies */
800  info[dim].nbytes_aligned += MAXALIGN(len);
801  }
802  }
803 
804  /* we know (count>0) so there must be some data */
805  Assert(info[dim].nbytes > 0);
806  }
807 
808  /*
809  * Now we can finally compute how much space we'll actually need for the
810  * whole serialized MCV list (varlena header, MCV header, dimension info
811  * for each attribute, deduplicated values and items).
812  */
813  total_length = (3 * sizeof(uint32)) /* magic + type + nitems */
814  + sizeof(AttrNumber) /* ndimensions */
815  + (ndims * sizeof(Oid)); /* attribute types */
816 
817  /* dimension info */
818  total_length += ndims * sizeof(DimensionInfo);
819 
820  /* add space for the arrays of deduplicated values */
821  for (i = 0; i < ndims; i++)
822  total_length += info[i].nbytes;
823 
824  /*
825  * And finally account for the items (those are fixed-length, thanks to
826  * replacing values with uint16 indexes into the deduplicated arrays).
827  */
828  total_length += mcvlist->nitems * ITEM_SIZE(dim);
829 
830  /*
831  * Allocate space for the whole serialized MCV list (we'll skip bytes, so
832  * we set them to zero to make the result more compressible).
833  */
834  raw = (bytea *) palloc0(VARHDRSZ + total_length);
835  SET_VARSIZE(raw, VARHDRSZ + total_length);
836 
837  ptr = VARDATA(raw);
838  endptr = ptr + total_length;
839 
840  /* copy the MCV list header fields, one by one */
841  memcpy(ptr, &mcvlist->magic, sizeof(uint32));
842  ptr += sizeof(uint32);
843 
844  memcpy(ptr, &mcvlist->type, sizeof(uint32));
845  ptr += sizeof(uint32);
846 
847  memcpy(ptr, &mcvlist->nitems, sizeof(uint32));
848  ptr += sizeof(uint32);
849 
850  memcpy(ptr, &mcvlist->ndimensions, sizeof(AttrNumber));
851  ptr += sizeof(AttrNumber);
852 
853  memcpy(ptr, mcvlist->types, sizeof(Oid) * ndims);
854  ptr += (sizeof(Oid) * ndims);
855 
856  /* store information about the attributes (data amounts, ...) */
857  memcpy(ptr, info, sizeof(DimensionInfo) * ndims);
858  ptr += sizeof(DimensionInfo) * ndims;
859 
860  /* Copy the deduplicated values for all attributes to the output. */
861  for (dim = 0; dim < ndims; dim++)
862  {
863  /* remember the starting point for Asserts later */
864  char *start PG_USED_FOR_ASSERTS_ONLY = ptr;
865 
866  for (i = 0; i < info[dim].nvalues; i++)
867  {
868  Datum value = values[dim][i];
869 
870  if (info[dim].typbyval) /* passed by value */
871  {
872  Datum tmp;
873 
874  /*
875  * For values passed by value, we need to copy just the
876  * significant bytes - we can't use memcpy directly, as that
877  * assumes little endian behavior. store_att_byval does
878  * almost what we need, but it requires properly aligned
879  * buffer - the output buffer does not guarantee that. So we
880  * simply use a local Datum variable (which guarantees proper
881  * alignment), and then copy the value from it.
882  */
883  store_att_byval(&tmp, value, info[dim].typlen);
884 
885  memcpy(ptr, &tmp, info[dim].typlen);
886  ptr += info[dim].typlen;
887  }
888  else if (info[dim].typlen > 0) /* passed by reference */
889  {
890  /* no special alignment needed, treated as char array */
891  memcpy(ptr, DatumGetPointer(value), info[dim].typlen);
892  ptr += info[dim].typlen;
893  }
894  else if (info[dim].typlen == -1) /* varlena */
895  {
897 
898  /* copy the length */
899  memcpy(ptr, &len, sizeof(uint32));
900  ptr += sizeof(uint32);
901 
902  /* data from the varlena value (without the header) */
903  memcpy(ptr, VARDATA_ANY(DatumGetPointer(value)), len);
904  ptr += len;
905  }
906  else if (info[dim].typlen == -2) /* cstring */
907  {
908  uint32 len = (uint32) strlen(DatumGetCString(value)) + 1;
909 
910  /* copy the length */
911  memcpy(ptr, &len, sizeof(uint32));
912  ptr += sizeof(uint32);
913 
914  /* value */
915  memcpy(ptr, DatumGetCString(value), len);
916  ptr += len;
917  }
918 
919  /* no underflows or overflows */
920  Assert((ptr > start) && ((ptr - start) <= info[dim].nbytes));
921  }
922 
923  /* we should get exactly nbytes of data for this dimension */
924  Assert((ptr - start) == info[dim].nbytes);
925  }
926 
927  /* Serialize the items, with uint16 indexes instead of the values. */
928  for (i = 0; i < mcvlist->nitems; i++)
929  {
930  MCVItem *mcvitem = &mcvlist->items[i];
931 
932  /* don't write beyond the allocated space */
933  Assert(ptr <= (endptr - ITEM_SIZE(dim)));
934 
935  /* copy NULL and frequency flags into the serialized MCV */
936  memcpy(ptr, mcvitem->isnull, sizeof(bool) * ndims);
937  ptr += sizeof(bool) * ndims;
938 
939  memcpy(ptr, &mcvitem->frequency, sizeof(double));
940  ptr += sizeof(double);
941 
942  memcpy(ptr, &mcvitem->base_frequency, sizeof(double));
943  ptr += sizeof(double);
944 
945  /* store the indexes last */
946  for (dim = 0; dim < ndims; dim++)
947  {
948  uint16 index = 0;
949  Datum *value;
950 
951  /* do the lookup only for non-NULL values */
952  if (!mcvitem->isnull[dim])
953  {
954  value = (Datum *) bsearch_arg(&mcvitem->values[dim], values[dim],
955  info[dim].nvalues, sizeof(Datum),
956  compare_scalars_simple, &ssup[dim]);
957 
958  Assert(value != NULL); /* serialization or deduplication
959  * error */
960 
961  /* compute index within the deduplicated array */
962  index = (uint16) (value - values[dim]);
963 
964  /* check the index is within expected bounds */
965  Assert(index < info[dim].nvalues);
966  }
967 
968  /* copy the index into the serialized MCV */
969  memcpy(ptr, &index, sizeof(uint16));
970  ptr += sizeof(uint16);
971  }
972 
973  /* make sure we don't overflow the allocated value */
974  Assert(ptr <= endptr);
975  }
976 
977  /* at this point we expect to match the total_length exactly */
978  Assert(ptr == endptr);
979 
980  pfree(values);
981  pfree(counts);
982 
983  return raw;
984 }
985 
986 /*
987  * statext_mcv_deserialize
988  * Reads serialized MCV list into MCVList structure.
989  *
990  * All the memory needed by the MCV list is allocated as a single chunk, so
991  * it's possible to simply pfree() it at once.
992  */
993 MCVList *
995 {
996  int dim,
997  i;
998  Size expected_size;
999  MCVList *mcvlist;
1000  char *raw;
1001  char *ptr;
1002  char *endptr PG_USED_FOR_ASSERTS_ONLY;
1003 
1004  int ndims,
1005  nitems;
1006  DimensionInfo *info = NULL;
1007 
1008  /* local allocation buffer (used only for deserialization) */
1009  Datum **map = NULL;
1010 
1011  /* MCV list */
1012  Size mcvlen;
1013 
1014  /* buffer used for the result */
1015  Size datalen;
1016  char *dataptr;
1017  char *valuesptr;
1018  char *isnullptr;
1019 
1020  if (data == NULL)
1021  return NULL;
1022 
1023  /*
1024  * We can't possibly deserialize a MCV list if there's not even a complete
1025  * header. We need an explicit formula here, because we serialize the
1026  * header fields one by one, so we need to ignore struct alignment.
1027  */
1028  if (VARSIZE_ANY(data) < MinSizeOfMCVList)
1029  elog(ERROR, "invalid MCV size %zd (expected at least %zu)",
1030  VARSIZE_ANY(data), MinSizeOfMCVList);
1031 
1032  /* read the MCV list header */
1033  mcvlist = (MCVList *) palloc0(offsetof(MCVList, items));
1034 
1035  /* pointer to the data part (skip the varlena header) */
1036  raw = (char *) data;
1037  ptr = VARDATA_ANY(raw);
1038  endptr = (char *) raw + VARSIZE_ANY(data);
1039 
1040  /* get the header and perform further sanity checks */
1041  memcpy(&mcvlist->magic, ptr, sizeof(uint32));
1042  ptr += sizeof(uint32);
1043 
1044  memcpy(&mcvlist->type, ptr, sizeof(uint32));
1045  ptr += sizeof(uint32);
1046 
1047  memcpy(&mcvlist->nitems, ptr, sizeof(uint32));
1048  ptr += sizeof(uint32);
1049 
1050  memcpy(&mcvlist->ndimensions, ptr, sizeof(AttrNumber));
1051  ptr += sizeof(AttrNumber);
1052 
1053  if (mcvlist->magic != STATS_MCV_MAGIC)
1054  elog(ERROR, "invalid MCV magic %u (expected %u)",
1055  mcvlist->magic, STATS_MCV_MAGIC);
1056 
1057  if (mcvlist->type != STATS_MCV_TYPE_BASIC)
1058  elog(ERROR, "invalid MCV type %u (expected %u)",
1059  mcvlist->type, STATS_MCV_TYPE_BASIC);
1060 
1061  if (mcvlist->ndimensions == 0)
1062  elog(ERROR, "invalid zero-length dimension array in MCVList");
1063  else if ((mcvlist->ndimensions > STATS_MAX_DIMENSIONS) ||
1064  (mcvlist->ndimensions < 0))
1065  elog(ERROR, "invalid length (%d) dimension array in MCVList",
1066  mcvlist->ndimensions);
1067 
1068  if (mcvlist->nitems == 0)
1069  elog(ERROR, "invalid zero-length item array in MCVList");
1070  else if (mcvlist->nitems > STATS_MCVLIST_MAX_ITEMS)
1071  elog(ERROR, "invalid length (%u) item array in MCVList",
1072  mcvlist->nitems);
1073 
1074  nitems = mcvlist->nitems;
1075  ndims = mcvlist->ndimensions;
1076 
1077  /*
1078  * Check amount of data including DimensionInfo for all dimensions and
1079  * also the serialized items (including uint16 indexes). Also, walk
1080  * through the dimension information and add it to the sum.
1081  */
1082  expected_size = SizeOfMCVList(ndims, nitems);
1083 
1084  /*
1085  * Check that we have at least the dimension and info records, along with
1086  * the items. We don't know the size of the serialized values yet. We need
1087  * to do this check first, before accessing the dimension info.
1088  */
1089  if (VARSIZE_ANY(data) < expected_size)
1090  elog(ERROR, "invalid MCV size %zd (expected %zu)",
1091  VARSIZE_ANY(data), expected_size);
1092 
1093  /* Now copy the array of type Oids. */
1094  memcpy(mcvlist->types, ptr, sizeof(Oid) * ndims);
1095  ptr += (sizeof(Oid) * ndims);
1096 
1097  /* Now it's safe to access the dimension info. */
1098  info = palloc(ndims * sizeof(DimensionInfo));
1099 
1100  memcpy(info, ptr, ndims * sizeof(DimensionInfo));
1101  ptr += (ndims * sizeof(DimensionInfo));
1102 
1103  /* account for the value arrays */
1104  for (dim = 0; dim < ndims; dim++)
1105  {
1106  /*
1107  * XXX I wonder if we can/should rely on asserts here. Maybe those
1108  * checks should be done every time?
1109  */
1110  Assert(info[dim].nvalues >= 0);
1111  Assert(info[dim].nbytes >= 0);
1112 
1113  expected_size += info[dim].nbytes;
1114  }
1115 
1116  /*
1117  * Now we know the total expected MCV size, including all the pieces
1118  * (header, dimension info. items and deduplicated data). So do the final
1119  * check on size.
1120  */
1121  if (VARSIZE_ANY(data) != expected_size)
1122  elog(ERROR, "invalid MCV size %zd (expected %zu)",
1123  VARSIZE_ANY(data), expected_size);
1124 
1125  /*
1126  * We need an array of Datum values for each dimension, so that we can
1127  * easily translate the uint16 indexes later. We also need a top-level
1128  * array of pointers to those per-dimension arrays.
1129  *
1130  * While allocating the arrays for dimensions, compute how much space we
1131  * need for a copy of the by-ref data, as we can't simply point to the
1132  * original values (it might go away).
1133  */
1134  datalen = 0; /* space for by-ref data */
1135  map = (Datum **) palloc(ndims * sizeof(Datum *));
1136 
1137  for (dim = 0; dim < ndims; dim++)
1138  {
1139  map[dim] = (Datum *) palloc(sizeof(Datum) * info[dim].nvalues);
1140 
1141  /* space needed for a copy of data for by-ref types */
1142  datalen += info[dim].nbytes_aligned;
1143  }
1144 
1145  /*
1146  * Now resize the MCV list so that the allocation includes all the data.
1147  *
1148  * Allocate space for a copy of the data, as we can't simply reference the
1149  * serialized data - it's not aligned properly, and it may disappear while
1150  * we're still using the MCV list, e.g. due to catcache release.
1151  *
1152  * We do care about alignment here, because we will allocate all the
1153  * pieces at once, but then use pointers to different parts.
1154  */
1155  mcvlen = MAXALIGN(offsetof(MCVList, items) + (sizeof(MCVItem) * nitems));
1156 
1157  /* arrays of values and isnull flags for all MCV items */
1158  mcvlen += nitems * MAXALIGN(sizeof(Datum) * ndims);
1159  mcvlen += nitems * MAXALIGN(sizeof(bool) * ndims);
1160 
1161  /* we don't quite need to align this, but it makes some asserts easier */
1162  mcvlen += MAXALIGN(datalen);
1163 
1164  /* now resize the deserialized MCV list, and compute pointers to parts */
1165  mcvlist = repalloc(mcvlist, mcvlen);
1166 
1167  /* pointer to the beginning of values/isnull arrays */
1168  valuesptr = (char *) mcvlist
1169  + MAXALIGN(offsetof(MCVList, items) + (sizeof(MCVItem) * nitems));
1170 
1171  isnullptr = valuesptr + (nitems * MAXALIGN(sizeof(Datum) * ndims));
1172 
1173  dataptr = isnullptr + (nitems * MAXALIGN(sizeof(bool) * ndims));
1174 
1175  /*
1176  * Build mapping (index => value) for translating the serialized data into
1177  * the in-memory representation.
1178  */
1179  for (dim = 0; dim < ndims; dim++)
1180  {
1181  /* remember start position in the input array */
1182  char *start PG_USED_FOR_ASSERTS_ONLY = ptr;
1183 
1184  if (info[dim].typbyval)
1185  {
1186  /* for by-val types we simply copy data into the mapping */
1187  for (i = 0; i < info[dim].nvalues; i++)
1188  {
1189  Datum v = 0;
1190 
1191  memcpy(&v, ptr, info[dim].typlen);
1192  ptr += info[dim].typlen;
1193 
1194  map[dim][i] = fetch_att(&v, true, info[dim].typlen);
1195 
1196  /* no under/overflow of input array */
1197  Assert(ptr <= (start + info[dim].nbytes));
1198  }
1199  }
1200  else
1201  {
1202  /* for by-ref types we need to also make a copy of the data */
1203 
1204  /* passed by reference, but fixed length (name, tid, ...) */
1205  if (info[dim].typlen > 0)
1206  {
1207  for (i = 0; i < info[dim].nvalues; i++)
1208  {
1209  memcpy(dataptr, ptr, info[dim].typlen);
1210  ptr += info[dim].typlen;
1211 
1212  /* just point into the array */
1213  map[dim][i] = PointerGetDatum(dataptr);
1214  dataptr += MAXALIGN(info[dim].typlen);
1215  }
1216  }
1217  else if (info[dim].typlen == -1)
1218  {
1219  /* varlena */
1220  for (i = 0; i < info[dim].nvalues; i++)
1221  {
1222  uint32 len;
1223 
1224  /* read the uint32 length */
1225  memcpy(&len, ptr, sizeof(uint32));
1226  ptr += sizeof(uint32);
1227 
1228  /* the length is data-only */
1229  SET_VARSIZE(dataptr, len + VARHDRSZ);
1230  memcpy(VARDATA(dataptr), ptr, len);
1231  ptr += len;
1232 
1233  /* just point into the array */
1234  map[dim][i] = PointerGetDatum(dataptr);
1235 
1236  /* skip to place of the next deserialized value */
1237  dataptr += MAXALIGN(len + VARHDRSZ);
1238  }
1239  }
1240  else if (info[dim].typlen == -2)
1241  {
1242  /* cstring */
1243  for (i = 0; i < info[dim].nvalues; i++)
1244  {
1245  uint32 len;
1246 
1247  memcpy(&len, ptr, sizeof(uint32));
1248  ptr += sizeof(uint32);
1249 
1250  memcpy(dataptr, ptr, len);
1251  ptr += len;
1252 
1253  /* just point into the array */
1254  map[dim][i] = PointerGetDatum(dataptr);
1255  dataptr += MAXALIGN(len);
1256  }
1257  }
1258 
1259  /* no under/overflow of input array */
1260  Assert(ptr <= (start + info[dim].nbytes));
1261 
1262  /* no overflow of the output mcv value */
1263  Assert(dataptr <= ((char *) mcvlist + mcvlen));
1264  }
1265 
1266  /* check we consumed input data for this dimension exactly */
1267  Assert(ptr == (start + info[dim].nbytes));
1268  }
1269 
1270  /* we should have also filled the MCV list exactly */
1271  Assert(dataptr == ((char *) mcvlist + mcvlen));
1272 
1273  /* deserialize the MCV items and translate the indexes to Datums */
1274  for (i = 0; i < nitems; i++)
1275  {
1276  MCVItem *item = &mcvlist->items[i];
1277 
1278  item->values = (Datum *) valuesptr;
1279  valuesptr += MAXALIGN(sizeof(Datum) * ndims);
1280 
1281  item->isnull = (bool *) isnullptr;
1282  isnullptr += MAXALIGN(sizeof(bool) * ndims);
1283 
1284  memcpy(item->isnull, ptr, sizeof(bool) * ndims);
1285  ptr += sizeof(bool) * ndims;
1286 
1287  memcpy(&item->frequency, ptr, sizeof(double));
1288  ptr += sizeof(double);
1289 
1290  memcpy(&item->base_frequency, ptr, sizeof(double));
1291  ptr += sizeof(double);
1292 
1293  /* finally translate the indexes (for non-NULL only) */
1294  for (dim = 0; dim < ndims; dim++)
1295  {
1296  uint16 index;
1297 
1298  memcpy(&index, ptr, sizeof(uint16));
1299  ptr += sizeof(uint16);
1300 
1301  if (item->isnull[dim])
1302  continue;
1303 
1304  item->values[dim] = map[dim][index];
1305  }
1306 
1307  /* check we're not overflowing the input */
1308  Assert(ptr <= endptr);
1309  }
1310 
1311  /* check that we processed all the data */
1312  Assert(ptr == endptr);
1313 
1314  /* release the buffers used for mapping */
1315  for (dim = 0; dim < ndims; dim++)
1316  pfree(map[dim]);
1317 
1318  pfree(map);
1319 
1320  return mcvlist;
1321 }
1322 
1323 /*
1324  * SRF with details about buckets of a histogram:
1325  *
1326  * - item ID (0...nitems)
1327  * - values (string array)
1328  * - nulls only (boolean array)
1329  * - frequency (double precision)
1330  * - base_frequency (double precision)
1331  *
1332  * The input is the OID of the statistics, and there are no rows returned if
1333  * the statistics contains no histogram.
1334  */
1335 Datum
1337 {
1338  FuncCallContext *funcctx;
1339 
1340  /* stuff done only on the first call of the function */
1341  if (SRF_IS_FIRSTCALL())
1342  {
1343  MemoryContext oldcontext;
1344  MCVList *mcvlist;
1345  TupleDesc tupdesc;
1346 
1347  /* create a function context for cross-call persistence */
1348  funcctx = SRF_FIRSTCALL_INIT();
1349 
1350  /* switch to memory context appropriate for multiple function calls */
1351  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
1352 
1354 
1355  funcctx->user_fctx = mcvlist;
1356 
1357  /* total number of tuples to be returned */
1358  funcctx->max_calls = 0;
1359  if (funcctx->user_fctx != NULL)
1360  funcctx->max_calls = mcvlist->nitems;
1361 
1362  /* Build a tuple descriptor for our result type */
1363  if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
1364  ereport(ERROR,
1365  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1366  errmsg("function returning record called in context "
1367  "that cannot accept type record")));
1368  tupdesc = BlessTupleDesc(tupdesc);
1369 
1370  /*
1371  * generate attribute metadata needed later to produce tuples from raw
1372  * C strings
1373  */
1374  funcctx->attinmeta = TupleDescGetAttInMetadata(tupdesc);
1375 
1376  MemoryContextSwitchTo(oldcontext);
1377  }
1378 
1379  /* stuff done on every call of the function */
1380  funcctx = SRF_PERCALL_SETUP();
1381 
1382  if (funcctx->call_cntr < funcctx->max_calls) /* do when there is more
1383  * left to send */
1384  {
1385  Datum values[5];
1386  bool nulls[5];
1387  HeapTuple tuple;
1388  Datum result;
1389  ArrayBuildState *astate_values = NULL;
1390  ArrayBuildState *astate_nulls = NULL;
1391 
1392  int i;
1393  MCVList *mcvlist;
1394  MCVItem *item;
1395 
1396  mcvlist = (MCVList *) funcctx->user_fctx;
1397 
1398  Assert(funcctx->call_cntr < mcvlist->nitems);
1399 
1400  item = &mcvlist->items[funcctx->call_cntr];
1401 
1402  for (i = 0; i < mcvlist->ndimensions; i++)
1403  {
1404 
1405  astate_nulls = accumArrayResult(astate_nulls,
1406  BoolGetDatum(item->isnull[i]),
1407  false,
1408  BOOLOID,
1410 
1411  if (!item->isnull[i])
1412  {
1413  bool isvarlena;
1414  Oid outfunc;
1415  FmgrInfo fmgrinfo;
1416  Datum val;
1417  text *txt;
1418 
1419  /* lookup output func for the type */
1420  getTypeOutputInfo(mcvlist->types[i], &outfunc, &isvarlena);
1421  fmgr_info(outfunc, &fmgrinfo);
1422 
1423  val = FunctionCall1(&fmgrinfo, item->values[i]);
1424  txt = cstring_to_text(DatumGetPointer(val));
1425 
1426  astate_values = accumArrayResult(astate_values,
1427  PointerGetDatum(txt),
1428  false,
1429  TEXTOID,
1431  }
1432  else
1433  astate_values = accumArrayResult(astate_values,
1434  (Datum) 0,
1435  true,
1436  TEXTOID,
1438  }
1439 
1440  values[0] = Int32GetDatum(funcctx->call_cntr);
1441  values[1] = PointerGetDatum(makeArrayResult(astate_values, CurrentMemoryContext));
1442  values[2] = PointerGetDatum(makeArrayResult(astate_nulls, CurrentMemoryContext));
1443  values[3] = Float8GetDatum(item->frequency);
1444  values[4] = Float8GetDatum(item->base_frequency);
1445 
1446  /* no NULLs in the tuple */
1447  memset(nulls, 0, sizeof(nulls));
1448 
1449  /* build a tuple */
1450  tuple = heap_form_tuple(funcctx->attinmeta->tupdesc, values, nulls);
1451 
1452  /* make the tuple into a datum */
1453  result = HeapTupleGetDatum(tuple);
1454 
1455  SRF_RETURN_NEXT(funcctx, result);
1456  }
1457  else /* do when there is no more left */
1458  {
1459  SRF_RETURN_DONE(funcctx);
1460  }
1461 }
1462 
1463 /*
1464  * pg_mcv_list_in - input routine for type pg_mcv_list.
1465  *
1466  * pg_mcv_list is real enough to be a table column, but it has no operations
1467  * of its own, and disallows input too
1468  */
1469 Datum
1471 {
1472  /*
1473  * pg_mcv_list stores the data in binary form and parsing text input is
1474  * not needed, so disallow this.
1475  */
1476  ereport(ERROR,
1477  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1478  errmsg("cannot accept a value of type %s", "pg_mcv_list")));
1479 
1480  PG_RETURN_VOID(); /* keep compiler quiet */
1481 }
1482 
1483 
1484 /*
1485  * pg_mcv_list_out - output routine for type pg_mcv_list.
1486  *
1487  * MCV lists are serialized into a bytea value, so we simply call byteaout()
1488  * to serialize the value into text. But it'd be nice to serialize that into
1489  * a meaningful representation (e.g. for inspection by people).
1490  *
1491  * XXX This should probably return something meaningful, similar to what
1492  * pg_dependencies_out does. Not sure how to deal with the deduplicated
1493  * values, though - do we want to expand that or not?
1494  */
1495 Datum
1497 {
1498  return byteaout(fcinfo);
1499 }
1500 
1501 /*
1502  * pg_mcv_list_recv - binary input routine for type pg_mcv_list.
1503  */
1504 Datum
1506 {
1507  ereport(ERROR,
1508  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1509  errmsg("cannot accept a value of type %s", "pg_mcv_list")));
1510 
1511  PG_RETURN_VOID(); /* keep compiler quiet */
1512 }
1513 
1514 /*
1515  * pg_mcv_list_send - binary output routine for type pg_mcv_list.
1516  *
1517  * MCV lists are serialized in a bytea value (although the type is named
1518  * differently), so let's just send that.
1519  */
1520 Datum
1522 {
1523  return byteasend(fcinfo);
1524 }
1525 
1526 /*
1527  * mcv_get_match_bitmap
1528  * Evaluate clauses using the MCV list, and update the match bitmap.
1529  *
1530  * A match bitmap keeps match/mismatch status for each MCV item, and we
1531  * update it based on additional clauses. We also use it to skip items
1532  * that can't possibly match (e.g. item marked as "mismatch" can't change
1533  * to "match" when evaluating AND clause list).
1534  *
1535  * The function also returns a flag indicating whether there was an
1536  * equality condition for all attributes, the minimum frequency in the MCV
1537  * list, and a total MCV frequency (sum of frequencies for all items).
1538  *
1539  * XXX Currently the match bitmap uses a bool for each MCV item, which is
1540  * somewhat wasteful as we could do with just a single bit, thus reducing
1541  * the size to ~1/8. It would also allow us to combine bitmaps simply using
1542  * & and |, which should be faster than min/max. The bitmaps are fairly
1543  * small, though (thanks to the cap on the MCV list size).
1544  */
1545 static bool *
1547  Bitmapset *keys, MCVList *mcvlist, bool is_or)
1548 {
1549  int i;
1550  ListCell *l;
1551  bool *matches;
1552 
1553  /* The bitmap may be partially built. */
1554  Assert(clauses != NIL);
1555  Assert(list_length(clauses) >= 1);
1556  Assert(mcvlist != NULL);
1557  Assert(mcvlist->nitems > 0);
1558  Assert(mcvlist->nitems <= STATS_MCVLIST_MAX_ITEMS);
1559 
1560  matches = palloc(sizeof(bool) * mcvlist->nitems);
1561  memset(matches, (is_or) ? false : true,
1562  sizeof(bool) * mcvlist->nitems);
1563 
1564  /*
1565  * Loop through the list of clauses, and for each of them evaluate all the
1566  * MCV items not yet eliminated by the preceding clauses.
1567  */
1568  foreach(l, clauses)
1569  {
1570  Node *clause = (Node *) lfirst(l);
1571 
1572  /* if it's a RestrictInfo, then extract the clause */
1573  if (IsA(clause, RestrictInfo))
1574  clause = (Node *) ((RestrictInfo *) clause)->clause;
1575 
1576  /*
1577  * Handle the various types of clauses - OpClause, NullTest and
1578  * AND/OR/NOT
1579  */
1580  if (is_opclause(clause))
1581  {
1582  OpExpr *expr = (OpExpr *) clause;
1583  FmgrInfo opproc;
1584 
1585  /* valid only after examine_clause_args returns true */
1586  Var *var;
1587  Const *cst;
1588  bool varonleft;
1589 
1590  fmgr_info(get_opcode(expr->opno), &opproc);
1591 
1592  /* extract the var and const from the expression */
1593  if (examine_clause_args(expr->args, &var, &cst, &varonleft))
1594  {
1595  int idx;
1596 
1597  /* match the attribute to a dimension of the statistic */
1598  idx = bms_member_index(keys, var->varattno);
1599 
1600  /*
1601  * Walk through the MCV items and evaluate the current clause.
1602  * We can skip items that were already ruled out, and
1603  * terminate if there are no remaining MCV items that might
1604  * possibly match.
1605  */
1606  for (i = 0; i < mcvlist->nitems; i++)
1607  {
1608  bool match = true;
1609  MCVItem *item = &mcvlist->items[i];
1610 
1611  /*
1612  * When the MCV item or the Const value is NULL we can
1613  * treat this as a mismatch. We must not call the operator
1614  * because of strictness.
1615  */
1616  if (item->isnull[idx] || cst->constisnull)
1617  {
1618  matches[i] = RESULT_MERGE(matches[i], is_or, false);
1619  continue;
1620  }
1621 
1622  /*
1623  * Skip MCV items that can't change result in the bitmap.
1624  * Once the value gets false for AND-lists, or true for
1625  * OR-lists, we don't need to look at more clauses.
1626  */
1627  if (RESULT_IS_FINAL(matches[i], is_or))
1628  continue;
1629 
1630  /*
1631  * First check whether the constant is below the lower
1632  * boundary (in that case we can skip the bucket, because
1633  * there's no overlap).
1634  *
1635  * We don't store collations used to build the statistics,
1636  * but we can use the collation for the attribute itself,
1637  * as stored in varcollid. We do reset the statistics
1638  * after a type change (including collation change), so
1639  * this is OK. We may need to relax this after allowing
1640  * extended statistics on expressions.
1641  */
1642  if (varonleft)
1643  match = DatumGetBool(FunctionCall2Coll(&opproc,
1644  var->varcollid,
1645  item->values[idx],
1646  cst->constvalue));
1647  else
1648  match = DatumGetBool(FunctionCall2Coll(&opproc,
1649  var->varcollid,
1650  cst->constvalue,
1651  item->values[idx]));
1652 
1653  /* update the match bitmap with the result */
1654  matches[i] = RESULT_MERGE(matches[i], is_or, match);
1655  }
1656  }
1657  }
1658  else if (IsA(clause, ScalarArrayOpExpr))
1659  {
1660  ScalarArrayOpExpr *expr = (ScalarArrayOpExpr *) clause;
1661  FmgrInfo opproc;
1662 
1663  /* valid only after examine_clause_args returns true */
1664  Var *var;
1665  Const *cst;
1666  bool varonleft;
1667 
1668  fmgr_info(get_opcode(expr->opno), &opproc);
1669 
1670  /* extract the var and const from the expression */
1671  if (examine_clause_args(expr->args, &var, &cst, &varonleft))
1672  {
1673  int idx;
1674 
1675  ArrayType *arrayval;
1676  int16 elmlen;
1677  bool elmbyval;
1678  char elmalign;
1679  int num_elems;
1680  Datum *elem_values;
1681  bool *elem_nulls;
1682 
1683  /* ScalarArrayOpExpr has the Var always on the left */
1684  Assert(varonleft);
1685 
1686  if (!cst->constisnull)
1687  {
1688  arrayval = DatumGetArrayTypeP(cst->constvalue);
1690  &elmlen, &elmbyval, &elmalign);
1691  deconstruct_array(arrayval,
1692  ARR_ELEMTYPE(arrayval),
1693  elmlen, elmbyval, elmalign,
1694  &elem_values, &elem_nulls, &num_elems);
1695  }
1696 
1697  /* match the attribute to a dimension of the statistic */
1698  idx = bms_member_index(keys, var->varattno);
1699 
1700  /*
1701  * Walk through the MCV items and evaluate the current clause.
1702  * We can skip items that were already ruled out, and
1703  * terminate if there are no remaining MCV items that might
1704  * possibly match.
1705  */
1706  for (i = 0; i < mcvlist->nitems; i++)
1707  {
1708  int j;
1709  bool match = (expr->useOr ? false : true);
1710  MCVItem *item = &mcvlist->items[i];
1711 
1712  /*
1713  * When the MCV item or the Const value is NULL we can
1714  * treat this as a mismatch. We must not call the operator
1715  * because of strictness.
1716  */
1717  if (item->isnull[idx] || cst->constisnull)
1718  {
1719  matches[i] = RESULT_MERGE(matches[i], is_or, false);
1720  continue;
1721  }
1722 
1723  /*
1724  * Skip MCV items that can't change result in the bitmap.
1725  * Once the value gets false for AND-lists, or true for
1726  * OR-lists, we don't need to look at more clauses.
1727  */
1728  if (RESULT_IS_FINAL(matches[i], is_or))
1729  continue;
1730 
1731  for (j = 0; j < num_elems; j++)
1732  {
1733  Datum elem_value = elem_values[j];
1734  bool elem_isnull = elem_nulls[j];
1735  bool elem_match;
1736 
1737  /* NULL values always evaluate as not matching. */
1738  if (elem_isnull)
1739  {
1740  match = RESULT_MERGE(match, expr->useOr, false);
1741  continue;
1742  }
1743 
1744  /*
1745  * Stop evaluating the array elements once we reach
1746  * match value that can't change - ALL() is the same
1747  * as AND-list, ANY() is the same as OR-list.
1748  */
1749  if (RESULT_IS_FINAL(match, expr->useOr))
1750  break;
1751 
1752  elem_match = DatumGetBool(FunctionCall2Coll(&opproc,
1753  var->varcollid,
1754  item->values[idx],
1755  elem_value));
1756 
1757  match = RESULT_MERGE(match, expr->useOr, elem_match);
1758  }
1759 
1760  /* update the match bitmap with the result */
1761  matches[i] = RESULT_MERGE(matches[i], is_or, match);
1762  }
1763  }
1764  }
1765  else if (IsA(clause, NullTest))
1766  {
1767  NullTest *expr = (NullTest *) clause;
1768  Var *var = (Var *) (expr->arg);
1769 
1770  /* match the attribute to a dimension of the statistic */
1771  int idx = bms_member_index(keys, var->varattno);
1772 
1773  /*
1774  * Walk through the MCV items and evaluate the current clause. We
1775  * can skip items that were already ruled out, and terminate if
1776  * there are no remaining MCV items that might possibly match.
1777  */
1778  for (i = 0; i < mcvlist->nitems; i++)
1779  {
1780  bool match = false; /* assume mismatch */
1781  MCVItem *item = &mcvlist->items[i];
1782 
1783  /* if the clause mismatches the MCV item, update the bitmap */
1784  switch (expr->nulltesttype)
1785  {
1786  case IS_NULL:
1787  match = (item->isnull[idx]) ? true : match;
1788  break;
1789 
1790  case IS_NOT_NULL:
1791  match = (!item->isnull[idx]) ? true : match;
1792  break;
1793  }
1794 
1795  /* now, update the match bitmap, depending on OR/AND type */
1796  matches[i] = RESULT_MERGE(matches[i], is_or, match);
1797  }
1798  }
1799  else if (is_orclause(clause) || is_andclause(clause))
1800  {
1801  /* AND/OR clause, with all subclauses being compatible */
1802 
1803  int i;
1804  BoolExpr *bool_clause = ((BoolExpr *) clause);
1805  List *bool_clauses = bool_clause->args;
1806 
1807  /* match/mismatch bitmap for each MCV item */
1808  bool *bool_matches = NULL;
1809 
1810  Assert(bool_clauses != NIL);
1811  Assert(list_length(bool_clauses) >= 2);
1812 
1813  /* build the match bitmap for the OR-clauses */
1814  bool_matches = mcv_get_match_bitmap(root, bool_clauses, keys,
1815  mcvlist, is_orclause(clause));
1816 
1817  /*
1818  * Merge the bitmap produced by mcv_get_match_bitmap into the
1819  * current one. We need to consider if we're evaluating AND or OR
1820  * condition when merging the results.
1821  */
1822  for (i = 0; i < mcvlist->nitems; i++)
1823  matches[i] = RESULT_MERGE(matches[i], is_or, bool_matches[i]);
1824 
1825  pfree(bool_matches);
1826  }
1827  else if (is_notclause(clause))
1828  {
1829  /* NOT clause, with all subclauses compatible */
1830 
1831  int i;
1832  BoolExpr *not_clause = ((BoolExpr *) clause);
1833  List *not_args = not_clause->args;
1834 
1835  /* match/mismatch bitmap for each MCV item */
1836  bool *not_matches = NULL;
1837 
1838  Assert(not_args != NIL);
1839  Assert(list_length(not_args) == 1);
1840 
1841  /* build the match bitmap for the NOT-clause */
1842  not_matches = mcv_get_match_bitmap(root, not_args, keys,
1843  mcvlist, false);
1844 
1845  /*
1846  * Merge the bitmap produced by mcv_get_match_bitmap into the
1847  * current one. We're handling a NOT clause, so invert the result
1848  * before merging it into the global bitmap.
1849  */
1850  for (i = 0; i < mcvlist->nitems; i++)
1851  matches[i] = RESULT_MERGE(matches[i], is_or, !not_matches[i]);
1852 
1853  pfree(not_matches);
1854  }
1855  else if (IsA(clause, Var))
1856  {
1857  /* Var (has to be a boolean Var, possibly from below NOT) */
1858 
1859  Var *var = (Var *) (clause);
1860 
1861  /* match the attribute to a dimension of the statistic */
1862  int idx = bms_member_index(keys, var->varattno);
1863 
1864  Assert(var->vartype == BOOLOID);
1865 
1866  /*
1867  * Walk through the MCV items and evaluate the current clause. We
1868  * can skip items that were already ruled out, and terminate if
1869  * there are no remaining MCV items that might possibly match.
1870  */
1871  for (i = 0; i < mcvlist->nitems; i++)
1872  {
1873  MCVItem *item = &mcvlist->items[i];
1874  bool match = false;
1875 
1876  /* if the item is NULL, it's a mismatch */
1877  if (!item->isnull[idx] && DatumGetBool(item->values[idx]))
1878  match = true;
1879 
1880  /* update the result bitmap */
1881  matches[i] = RESULT_MERGE(matches[i], is_or, match);
1882  }
1883  }
1884  else
1885  elog(ERROR, "unknown clause type: %d", clause->type);
1886  }
1887 
1888  return matches;
1889 }
1890 
1891 
1892 /*
1893  * mcv_combine_selectivities
1894  * Combine per-column and multi-column MCV selectivity estimates.
1895  *
1896  * simple_sel is a "simple" selectivity estimate (produced without using any
1897  * extended statistics, essentially assuming independence of columns/clauses).
1898  *
1899  * mcv_sel and mcv_basesel are sums of the frequencies and base frequencies of
1900  * all matching MCV items. The difference (mcv_sel - mcv_basesel) is then
1901  * essentially interpreted as a correction to be added to simple_sel, as
1902  * described below.
1903  *
1904  * mcv_totalsel is the sum of the frequencies of all MCV items (not just the
1905  * matching ones). This is used as an upper bound on the portion of the
1906  * selectivity estimates not covered by the MCV statistics.
1907  *
1908  * Note: While simple and base selectivities are defined in a quite similar
1909  * way, the values are computed differently and are not therefore equal. The
1910  * simple selectivity is computed as a product of per-clause estimates, while
1911  * the base selectivity is computed by adding up base frequencies of matching
1912  * items of the multi-column MCV list. So the values may differ for two main
1913  * reasons - (a) the MCV list may not cover 100% of the data and (b) some of
1914  * the MCV items did not match the estimated clauses.
1915  *
1916  * As both (a) and (b) reduce the base selectivity value, it generally holds
1917  * that (simple_sel >= mcv_basesel). If the MCV list covers all the data, the
1918  * values may be equal.
1919  *
1920  * So, other_sel = (simple_sel - mcv_basesel) is an estimate for the part not
1921  * covered by the MCV list, and (mcv_sel - mcv_basesel) may be seen as a
1922  * correction for the part covered by the MCV list. Those two statements are
1923  * actually equivalent.
1924  */
1927  Selectivity mcv_sel,
1928  Selectivity mcv_basesel,
1929  Selectivity mcv_totalsel)
1930 {
1931  Selectivity other_sel;
1932  Selectivity sel;
1933 
1934  /* estimated selectivity of values not covered by MCV matches */
1935  other_sel = simple_sel - mcv_basesel;
1936  CLAMP_PROBABILITY(other_sel);
1937 
1938  /* this non-MCV selectivity cannot exceed 1 - mcv_totalsel */
1939  if (other_sel > 1.0 - mcv_totalsel)
1940  other_sel = 1.0 - mcv_totalsel;
1941 
1942  /* overall selectivity is the sum of the MCV and non-MCV parts */
1943  sel = mcv_sel + other_sel;
1944  CLAMP_PROBABILITY(sel);
1945 
1946  return sel;
1947 }
1948 
1949 
1950 /*
1951  * mcv_clauselist_selectivity
1952  * Use MCV statistics to estimate the selectivity of an implicitly-ANDed
1953  * list of clauses.
1954  *
1955  * This determines which MCV items match every clause in the list and returns
1956  * the sum of the frequencies of those items.
1957  *
1958  * In addition, it returns the sum of the base frequencies of each of those
1959  * items (that is the sum of the selectivities that each item would have if
1960  * the columns were independent of one another), and the total selectivity of
1961  * all the MCV items (not just the matching ones). These are expected to be
1962  * used together with a "simple" selectivity estimate (one based only on
1963  * per-column statistics) to produce an overall selectivity estimate that
1964  * makes use of both per-column and multi-column statistics --- see
1965  * mcv_combine_selectivities().
1966  */
1969  List *clauses, int varRelid,
1970  JoinType jointype, SpecialJoinInfo *sjinfo,
1971  RelOptInfo *rel,
1972  Selectivity *basesel, Selectivity *totalsel)
1973 {
1974  int i;
1975  MCVList *mcv;
1976  Selectivity s = 0.0;
1977 
1978  /* match/mismatch bitmap for each MCV item */
1979  bool *matches = NULL;
1980 
1981  /* load the MCV list stored in the statistics object */
1982  mcv = statext_mcv_load(stat->statOid);
1983 
1984  /* build a match bitmap for the clauses */
1985  matches = mcv_get_match_bitmap(root, clauses, stat->keys, mcv, false);
1986 
1987  /* sum frequencies for all the matching MCV items */
1988  *basesel = 0.0;
1989  *totalsel = 0.0;
1990  for (i = 0; i < mcv->nitems; i++)
1991  {
1992  *totalsel += mcv->items[i].frequency;
1993 
1994  if (matches[i] != false)
1995  {
1996  *basesel += mcv->items[i].base_frequency;
1997  s += mcv->items[i].frequency;
1998  }
1999  }
2000 
2001  return s;
2002 }
2003 
2004 
2005 /*
2006  * mcv_clause_selectivity_or
2007  * Use MCV statistics to estimate the selectivity of a clause that
2008  * appears in an ORed list of clauses.
2009  *
2010  * As with mcv_clauselist_selectivity() this determines which MCV items match
2011  * the clause and returns both the sum of the frequencies and the sum of the
2012  * base frequencies of those items, as well as the sum of the frequencies of
2013  * all MCV items (not just the matching ones) so that this information can be
2014  * used by mcv_combine_selectivities() to produce a selectivity estimate that
2015  * makes use of both per-column and multi-column statistics.
2016  *
2017  * Additionally, we return information to help compute the overall selectivity
2018  * of the ORed list of clauses assumed to contain this clause. This function
2019  * is intended to be called for each clause in the ORed list of clauses,
2020  * allowing the overall selectivity to be computed using the following
2021  * algorithm:
2022  *
2023  * Suppose P[n] = P(C[1] OR C[2] OR ... OR C[n]) is the combined selectivity
2024  * of the first n clauses in the list. Then the combined selectivity taking
2025  * into account the next clause C[n+1] can be written as
2026  *
2027  * P[n+1] = P[n] + P(C[n+1]) - P((C[1] OR ... OR C[n]) AND C[n+1])
2028  *
2029  * The final term above represents the overlap between the clauses examined so
2030  * far and the (n+1)'th clause. To estimate its selectivity, we track the
2031  * match bitmap for the ORed list of clauses examined so far and examine its
2032  * intersection with the match bitmap for the (n+1)'th clause.
2033  *
2034  * We then also return the sums of the MCV item frequencies and base
2035  * frequencies for the match bitmap intersection corresponding to the overlap
2036  * term above, so that they can be combined with a simple selectivity estimate
2037  * for that term.
2038  *
2039  * The parameter "or_matches" is an in/out parameter tracking the match bitmap
2040  * for the clauses examined so far. The caller is expected to set it to NULL
2041  * the first time it calls this function.
2042  */
2045  MCVList *mcv, Node *clause, bool **or_matches,
2046  Selectivity *basesel, Selectivity *overlap_mcvsel,
2047  Selectivity *overlap_basesel, Selectivity *totalsel)
2048 {
2049  Selectivity s = 0.0;
2050  bool *new_matches;
2051  int i;
2052 
2053  /* build the OR-matches bitmap, if not built already */
2054  if (*or_matches == NULL)
2055  *or_matches = palloc0(sizeof(bool) * mcv->nitems);
2056 
2057  /* build the match bitmap for the new clause */
2058  new_matches = mcv_get_match_bitmap(root, list_make1(clause), stat->keys,
2059  mcv, false);
2060 
2061  /*
2062  * Sum the frequencies for all the MCV items matching this clause and also
2063  * those matching the overlap between this clause and any of the preceding
2064  * clauses as described above.
2065  */
2066  *basesel = 0.0;
2067  *overlap_mcvsel = 0.0;
2068  *overlap_basesel = 0.0;
2069  *totalsel = 0.0;
2070  for (i = 0; i < mcv->nitems; i++)
2071  {
2072  *totalsel += mcv->items[i].frequency;
2073 
2074  if (new_matches[i])
2075  {
2076  s += mcv->items[i].frequency;
2077  *basesel += mcv->items[i].base_frequency;
2078 
2079  if ((*or_matches)[i])
2080  {
2081  *overlap_mcvsel += mcv->items[i].frequency;
2082  *overlap_basesel += mcv->items[i].base_frequency;
2083  }
2084  }
2085 
2086  /* update the OR-matches bitmap for the next clause */
2087  (*or_matches)[i] = (*or_matches)[i] || new_matches[i];
2088  }
2089 
2090  pfree(new_matches);
2091 
2092  return s;
2093 }
Datum constvalue
Definition: primnodes.h:214
static SortItem * build_distinct_groups(int numrows, SortItem *items, MultiSortSupport mss, int *ndistinct)
Definition: mcv.c:424
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
uint32 nitems
Definition: statistics.h:90
uint64 call_cntr
Definition: funcapi.h:65
signed short int16
Definition: c.h:428
static SortItem ** build_column_frequencies(SortItem *groups, int ngroups, MultiSortSupport mss, int *ncounts)
Definition: mcv.c:490
Datum pg_stats_ext_mcvlist_items(PG_FUNCTION_ARGS)
Definition: mcv.c:1336
Datum byteaout(PG_FUNCTION_ARGS)
Definition: varlena.c:393
bool ssup_nulls_first
Definition: sortsupport.h:75
#define NIL
Definition: pg_list.h:65
Definition: fmgr.h:56
MCVList * statext_mcv_build(int numrows, HeapTuple *rows, Bitmapset *attrs, VacAttrStats **stats, double totalrows, int stattarget)
Definition: mcv.c:184
#define IsA(nodeptr, _type_)
Definition: nodes.h:584
TypeFuncClass get_call_result_type(FunctionCallInfo fcinfo, Oid *resultTypeId, TupleDesc *resultTupleDesc)
Definition: funcapi.c:207
void getTypeOutputInfo(Oid type, Oid *typOutput, bool *typIsVarlena)
Definition: lsyscache.c:2854
#define VARDATA_ANY(PTR)
Definition: postgres.h:348
#define VARDATA(PTR)
Definition: postgres.h:302
void * bsearch_arg(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *, void *), void *arg)
Oid types[STATS_MAX_DIMENSIONS]
Definition: statistics.h:92
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:106
MCVList * statext_mcv_deserialize(bytea *data)
Definition: mcv.c:994
#define SRF_IS_FIRSTCALL()
Definition: funcapi.h:294
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
Definition: lsyscache.c:2218
#define PointerGetDatum(X)
Definition: postgres.h:556
Datum pg_mcv_list_in(PG_FUNCTION_ARGS)
Definition: mcv.c:1470
#define VARHDRSZ
Definition: c.h:627
static MultiSortSupport build_mss(VacAttrStats **stats, int numattrs)
Definition: mcv.c:350
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:135
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:97
SortItem * build_sorted_items(int numrows, int *nitems, HeapTuple *rows, TupleDesc tdesc, MultiSortSupport mss, int numattrs, AttrNumber *attnums)
#define MinSizeOfMCVList
Definition: mcv.c:63
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Definition: nodes.h:533
struct DimensionInfo DimensionInfo
uint32 magic
Definition: statistics.h:88
int errcode(int sqlerrcode)
Definition: elog.c:694
AttrNumber varattno
Definition: primnodes.h:186
static int compare_sort_item_count(const void *a, const void *b)
Definition: mcv.c:404
AttrNumber ndimensions
Definition: statistics.h:91
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:259
#define false
Definition: c.h:399
struct MCVItem MCVItem
HeapTuple heap_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: heaptuple.c:1020
Datum * values
Definition: statistics.h:82
double Selectivity
Definition: nodes.h:666
MCVItem items[FLEXIBLE_ARRAY_MEMBER]
Definition: statistics.h:93
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1151
unsigned int Oid
Definition: postgres_ext.h:31
Definition: primnodes.h:181
static double get_mincount_for_mcv_list(int samplerows, double totalrows)
Definition: mcv.c:152
#define SRF_PERCALL_SETUP()
Definition: funcapi.h:298
static bool * mcv_get_match_bitmap(PlannerInfo *root, List *clauses, Bitmapset *keys, MCVList *mcvlist, bool is_or)
Definition: mcv.c:1546
Datum Float8GetDatum(float8 X)
Definition: fmgr.c:1709
JoinType
Definition: nodes.h:700
Definition: type.h:89
static struct @141 value
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
#define list_make1(x1)
Definition: pg_list.h:206
#define SRF_RETURN_NEXT(_funcctx, _result)
Definition: funcapi.h:300
#define PG_GETARG_BYTEA_P(n)
Definition: fmgr.h:335
unsigned short uint16
Definition: c.h:440
void pfree(void *pointer)
Definition: mcxt.c:1057
Oid attrtypid
Definition: vacuum.h:124
SortSupportData ssup[FLEXIBLE_ARRAY_MEMBER]
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:45
#define PG_UINT16_MAX
Definition: c.h:522
#define DatumGetCString(X)
Definition: postgres.h:566
void multi_sort_add_dimension(MultiSortSupport mss, int sortdim, Oid oper, Oid collation)
Oid vartype
Definition: primnodes.h:188
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:126
MemoryContext ssup_cxt
Definition: sortsupport.h:66
Expr * arg
Definition: primnodes.h:1243
#define DatumGetByteaP(X)
Definition: fmgr.h:331
bytea * statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
Definition: mcv.c:619
#define RESULT_MERGE(value, is_or, match)
Definition: mcv.c:92
TupleDesc BlessTupleDesc(TupleDesc tupdesc)
Definition: execTuples.c:2052
NodeTag type
Definition: nodes.h:535
AttrNumber * build_attnums_array(Bitmapset *attrs, int *numattrs)
AttInMetadata * attinmeta
Definition: funcapi.h:91
Selectivity mcv_combine_selectivities(Selectivity simple_sel, Selectivity mcv_sel, Selectivity mcv_basesel, Selectivity mcv_totalsel)
Definition: mcv.c:1926
TupleDesc tupdesc
Definition: funcapi.h:38
#define DatumGetBool(X)
Definition: postgres.h:393
bool examine_clause_args(List *args, Var **varp, Const **cstp, bool *varonleftp)
int bms_member_index(Bitmapset *a, int x)
Definition: bitmapset.c:453
int compare_scalars_simple(const void *a, const void *b, void *arg)
unsigned int uint32
Definition: c.h:441
#define RESULT_IS_FINAL(value, is_or)
Definition: mcv.c:104
#define SizeOfMCVList(ndims, nitems)
Definition: mcv.c:72
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
MCVList * statext_mcv_load(Oid mvoid)
Definition: mcv.c:558
Datum makeArrayResult(ArrayBuildState *astate, MemoryContext rcontext)
Definition: arrayfuncs.c:5149
uint32 type
Definition: statistics.h:89
MultiSortSupport multi_sort_init(int ndims)
static int sort_item_compare(const void *a, const void *b, void *arg)
Definition: mcv.c:465
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Datum byteasend(PG_FUNCTION_ARGS)
Definition: varlena.c:499
#define STATS_MCV_TYPE_BASIC
Definition: statistics.h:66
struct SortSupportData SortSupportData
HeapTuple SearchSysCache1(int cacheId, Datum key1)
Definition: syscache.c:1127
static bool is_notclause(const void *clause)
Definition: nodeFuncs.h:115
int compare_datums_simple(Datum a, Datum b, SortSupport ssup)
#define store_att_byval(T, newdatum, attlen)
Definition: tupmacs.h:226
void * palloc0(Size size)
Definition: mcxt.c:981
uintptr_t Datum
Definition: postgres.h:367
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1175
Datum SysCacheGetAttr(int cacheId, HeapTuple tup, AttrNumber attributeNumber, bool *isNull)
Definition: syscache.c:1388
#define STATS_MCVLIST_MAX_ITEMS
Definition: statistics.h:69
AttInMetadata * TupleDescGetAttInMetadata(TupleDesc tupdesc)
Definition: execTuples.c:2067
NullTestType nulltesttype
Definition: primnodes.h:1244
#define VARSIZE_ANY(PTR)
Definition: postgres.h:335
#define BoolGetDatum(X)
Definition: postgres.h:402
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:338
#define InvalidOid
Definition: postgres_ext.h:36
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1256
#define ITEM_SIZE(ndims)
Definition: mcv.c:57
#define ereport(elevel,...)
Definition: elog.h:155
#define PG_RETURN_VOID()
Definition: fmgr.h:349
text * cstring_to_text(const char *s)
Definition: varlena.c:189
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
double base_frequency
Definition: statistics.h:80
#define STATS_MCV_MAGIC
Definition: statistics.h:65
int multi_sort_compare(const void *a, const void *b, void *arg)
MemoryContext multi_call_memory_ctx
Definition: funcapi.h:101
size_t Size
Definition: c.h:540
void pg_qsort(void *base, size_t nel, size_t elsize, int(*cmp)(const void *, const void *))
static int list_length(const List *l)
Definition: pg_list.h:149
#define MAXALIGN(LEN)
Definition: c.h:757
#define HeapTupleGetDatum(tuple)
Definition: funcapi.h:221
Datum pg_mcv_list_send(PG_FUNCTION_ARGS)
Definition: mcv.c:1521
Oid attrcollid
Definition: vacuum.h:127
List * args
Definition: primnodes.h:604
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1070
#define DatumGetPointer(X)
Definition: postgres.h:549
bool * isnull
Definition: statistics.h:81
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3488
static Datum values[MAXATTR]
Definition: bootstrap.c:165
ArrayBuildState * accumArrayResult(ArrayBuildState *astate, Datum dvalue, bool disnull, Oid element_type, MemoryContext rcontext)
Definition: arrayfuncs.c:5085
#define Int32GetDatum(X)
Definition: postgres.h:479
Bitmapset * keys
Definition: pathnodes.h:925
void * user_fctx
Definition: funcapi.h:82
Form_pg_type attrtype
Definition: vacuum.h:126
#define STATS_MAX_DIMENSIONS
Definition: statistics.h:19
#define VARSIZE_ANY_EXHDR(PTR)
Definition: postgres.h:341
void * palloc(Size size)
Definition: mcxt.c:950
int errmsg(const char *fmt,...)
Definition: elog.c:905
#define fetch_att(T, attbyval, attlen)
Definition: tupmacs.h:75
#define elog(elevel,...)
Definition: elog.h:227
int i
#define FunctionCall1(flinfo, arg1)
Definition: fmgr.h:644
#define TYPECACHE_LT_OPR
Definition: typcache.h:137
Oid varcollid
Definition: primnodes.h:190
Selectivity mcv_clauselist_selectivity(PlannerInfo *root, StatisticExtInfo *stat, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Selectivity *basesel, Selectivity *totalsel)
Definition: mcv.c:1968
void * arg
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:240
Definition: c.h:621
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
MultiSortSupportData * MultiSortSupport
Datum pg_mcv_list_out(PG_FUNCTION_ARGS)
Definition: mcv.c:1496
Oid opno
Definition: primnodes.h:537
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:329
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:66
List * args
Definition: primnodes.h:543
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
static int count_distinct_groups(int numrows, SortItem *items, MultiSortSupport mss)
Definition: mcv.c:381
Datum pg_mcv_list_recv(PG_FUNCTION_ARGS)
Definition: mcv.c:1505
Definition: pg_list.h:50
#define ARR_ELEMTYPE(a)
Definition: array.h:285
int16 AttrNumber
Definition: attnum.h:21
long val
Definition: informix.c:664
bool constisnull
Definition: primnodes.h:215
#define offsetof(type, field)
Definition: c.h:727
uint64 max_calls
Definition: funcapi.h:74
#define SRF_RETURN_DONE(_funcctx)
Definition: funcapi.h:318
double frequency
Definition: statistics.h:79
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:155
unsigned char bool
Definition: c.h:391
Selectivity mcv_clause_selectivity_or(PlannerInfo *root, StatisticExtInfo *stat, MCVList *mcv, Node *clause, bool **or_matches, Selectivity *basesel, Selectivity *overlap_mcvsel, Selectivity *overlap_basesel, Selectivity *totalsel)
Definition: mcv.c:2044
#define DatumGetArrayTypeP(X)
Definition: array.h:254
#define SRF_FIRSTCALL_INIT()
Definition: funcapi.h:296