PostgreSQL Source Code  git master
extended_stats.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * extended_stats.c
4  * POSTGRES extended statistics
5  *
6  * Generic code supporting statistics objects created via CREATE STATISTICS.
7  *
8  *
9  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
10  * Portions Copyright (c) 1994, Regents of the University of California
11  *
12  * IDENTIFICATION
13  * src/backend/statistics/extended_stats.c
14  *
15  *-------------------------------------------------------------------------
16  */
17 #include "postgres.h"
18 
19 #include "access/detoast.h"
20 #include "access/genam.h"
21 #include "access/htup_details.h"
22 #include "access/table.h"
23 #include "catalog/indexing.h"
24 #include "catalog/pg_collation.h"
27 #include "miscadmin.h"
28 #include "nodes/nodeFuncs.h"
29 #include "optimizer/clauses.h"
30 #include "optimizer/optimizer.h"
31 #include "postmaster/autovacuum.h"
33 #include "statistics/statistics.h"
34 #include "utils/array.h"
35 #include "utils/builtins.h"
36 #include "utils/fmgroids.h"
37 #include "utils/lsyscache.h"
38 #include "utils/memutils.h"
39 #include "utils/rel.h"
40 #include "utils/selfuncs.h"
41 #include "utils/syscache.h"
42 
43 /*
44  * To avoid consuming too much memory during analysis and/or too much space
45  * in the resulting pg_statistic rows, we ignore varlena datums that are wider
46  * than WIDTH_THRESHOLD (after detoasting!). This is legitimate for MCV
47  * and distinct-value calculations since a wide value is unlikely to be
48  * duplicated at all, much less be a most-common value. For the same reason,
49  * ignoring wide values will not affect our estimates of histogram bin
50  * boundaries very much.
51  */
52 #define WIDTH_THRESHOLD 1024
53 
54 /*
55  * Used internally to refer to an individual statistics object, i.e.,
56  * a pg_statistic_ext entry.
57  */
58 typedef struct StatExtEntry
59 {
60  Oid statOid; /* OID of pg_statistic_ext entry */
61  char *schema; /* statistics object's schema */
62  char *name; /* statistics object's name */
63  Bitmapset *columns; /* attribute numbers covered by the object */
64  List *types; /* 'char' list of enabled statistic kinds */
65  int stattarget; /* statistics target (-1 for default) */
66 } StatExtEntry;
67 
68 
69 static List *fetch_statentries_for_relation(Relation pg_statext, Oid relid);
71  int nvacatts, VacAttrStats **vacatts);
72 static void statext_store(Oid relid,
73  MVNDistinct *ndistinct, MVDependencies *dependencies,
74  MCVList *mcv, VacAttrStats **stats);
76  int natts, VacAttrStats **stats);
77 
78 /*
79  * Compute requested extended stats, using the rows sampled for the plain
80  * (single-column) stats.
81  *
82  * This fetches a list of stats types from pg_statistic_ext, computes the
83  * requested stats, and serializes them back into the catalog.
84  */
85 void
86 BuildRelationExtStatistics(Relation onerel, double totalrows,
87  int numrows, HeapTuple *rows,
88  int natts, VacAttrStats **vacattrstats)
89 {
90  Relation pg_stext;
91  ListCell *lc;
92  List *stats;
93  MemoryContext cxt;
94  MemoryContext oldcxt;
95 
97  "BuildRelationExtStatistics",
99  oldcxt = MemoryContextSwitchTo(cxt);
100 
101  pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
102  stats = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
103 
104  foreach(lc, stats)
105  {
107  MVNDistinct *ndistinct = NULL;
108  MVDependencies *dependencies = NULL;
109  MCVList *mcv = NULL;
110  VacAttrStats **stats;
111  ListCell *lc2;
112  int stattarget;
113 
114  /*
115  * Check if we can build these stats based on the column analyzed. If
116  * not, report this fact (except in autovacuum) and move on.
117  */
118  stats = lookup_var_attr_stats(onerel, stat->columns,
119  natts, vacattrstats);
120  if (!stats)
121  {
124  (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
125  errmsg("statistics object \"%s.%s\" could not be computed for relation \"%s.%s\"",
126  stat->schema, stat->name,
127  get_namespace_name(onerel->rd_rel->relnamespace),
128  RelationGetRelationName(onerel)),
129  errtable(onerel)));
130  continue;
131  }
132 
133  /* check allowed number of dimensions */
134  Assert(bms_num_members(stat->columns) >= 2 &&
136 
137  /* compute statistics target for this statistics */
138  stattarget = statext_compute_stattarget(stat->stattarget,
139  bms_num_members(stat->columns),
140  stats);
141 
142  /*
143  * Don't rebuild statistics objects with statistics target set to 0 (we
144  * just leave the existing values around, just like we do for regular
145  * per-column statistics).
146  */
147  if (stattarget == 0)
148  continue;
149 
150  /* compute statistic of each requested type */
151  foreach(lc2, stat->types)
152  {
153  char t = (char) lfirst_int(lc2);
154 
155  if (t == STATS_EXT_NDISTINCT)
156  ndistinct = statext_ndistinct_build(totalrows, numrows, rows,
157  stat->columns, stats);
158  else if (t == STATS_EXT_DEPENDENCIES)
159  dependencies = statext_dependencies_build(numrows, rows,
160  stat->columns, stats);
161  else if (t == STATS_EXT_MCV)
162  mcv = statext_mcv_build(numrows, rows, stat->columns, stats,
163  totalrows, stattarget);
164  }
165 
166  /* store the statistics in the catalog */
167  statext_store(stat->statOid, ndistinct, dependencies, mcv, stats);
168  }
169 
170  table_close(pg_stext, RowExclusiveLock);
171 
172  MemoryContextSwitchTo(oldcxt);
173  MemoryContextDelete(cxt);
174 }
175 
176 /*
177  * ComputeExtStatisticsRows
178  * Compute number of rows required by extended statistics on a table.
179  *
180  * Computes number of rows we need to sample to build extended statistics on a
181  * table. This only looks at statistics we can actually build - for example
182  * when analyzing only some of the columns, this will skip statistics objects
183  * that would require additional columns.
184  *
185  * See statext_compute_stattarget for details about how we compute statistics
186  * target for a statistics objects (from the object target, attribute targets
187  * and default statistics target).
188  */
189 int
191  int natts, VacAttrStats **vacattrstats)
192 {
193  Relation pg_stext;
194  ListCell *lc;
195  List *lstats;
196  MemoryContext cxt;
197  MemoryContext oldcxt;
198  int result = 0;
199 
201  "ComputeExtStatisticsRows",
203  oldcxt = MemoryContextSwitchTo(cxt);
204 
205  pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
206  lstats = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
207 
208  foreach(lc, lstats)
209  {
211  int stattarget = stat->stattarget;
212  VacAttrStats **stats;
213  int nattrs = bms_num_members(stat->columns);
214 
215  /*
216  * Check if we can build this statistics object based on the columns
217  * analyzed. If not, ignore it (don't report anything, we'll do that
218  * during the actual build BuildRelationExtStatistics).
219  */
220  stats = lookup_var_attr_stats(onerel, stat->columns,
221  natts, vacattrstats);
222 
223  if (!stats)
224  continue;
225 
226  /*
227  * Compute statistics target, based on what's set for the statistic
228  * object itself, and for its attributes.
229  */
230  stattarget = statext_compute_stattarget(stat->stattarget,
231  nattrs, stats);
232 
233  /* Use the largest value for all statistics objects. */
234  if (stattarget > result)
235  result = stattarget;
236  }
237 
238  table_close(pg_stext, RowExclusiveLock);
239 
240  MemoryContextSwitchTo(oldcxt);
241  MemoryContextDelete(cxt);
242 
243  /* compute sample size based on the statistics target */
244  return (300 * result);
245 }
246 
247 /*
248  * statext_compute_stattarget
249  * compute statistics target for an extended statistic
250  *
251  * When computing target for extended statistics objects, we consider three
252  * places where the target may be set - the statistics object itself,
253  * attributes the statistics is defined on, and then the default statistics
254  * target.
255  *
256  * First we look at what's set for the statistics object itself, using the
257  * ALTER STATISTICS ... SET STATISTICS command. If we find a valid value
258  * there (i.e. not -1) we're done. Otherwise we look at targets set for any
259  * of the attributes the statistic is defined on, and if there are columns
260  * with defined target, we use the maximum value. We do this mostly for
261  * backwards compatibility, because this is what we did before having
262  * statistics target for extended statistics.
263  *
264  * And finally, if we still don't have a statistics target, we use the value
265  * set in default_statistics_target.
266  */
267 static int
269 {
270  int i;
271 
272  /*
273  * If there's statistics target set for the statistics object, use it.
274  * It may be set to 0 which disables building of that statistic.
275  */
276  if (stattarget >= 0)
277  return stattarget;
278 
279  /*
280  * The target for the statistics object is set to -1, in which case we
281  * look at the maximum target set for any of the attributes the object
282  * is defined on.
283  */
284  for (i = 0; i < nattrs; i++)
285  {
286  /* keep the maximmum statistics target */
287  if (stats[i]->attr->attstattarget > stattarget)
288  stattarget = stats[i]->attr->attstattarget;
289  }
290 
291  /*
292  * If the value is still negative (so neither the statistics object nor
293  * any of the columns have custom statistics target set), use the global
294  * default target.
295  */
296  if (stattarget < 0)
297  stattarget = default_statistics_target;
298 
299  /* As this point we should have a valid statistics target. */
300  Assert((stattarget >= 0) && (stattarget <= 10000));
301 
302  return stattarget;
303 }
304 
305 /*
306  * statext_is_kind_built
307  * Is this stat kind built in the given pg_statistic_ext_data tuple?
308  */
309 bool
311 {
313 
314  switch (type)
315  {
316  case STATS_EXT_NDISTINCT:
317  attnum = Anum_pg_statistic_ext_data_stxdndistinct;
318  break;
319 
320  case STATS_EXT_DEPENDENCIES:
321  attnum = Anum_pg_statistic_ext_data_stxddependencies;
322  break;
323 
324  case STATS_EXT_MCV:
325  attnum = Anum_pg_statistic_ext_data_stxdmcv;
326  break;
327 
328  default:
329  elog(ERROR, "unexpected statistics type requested: %d", type);
330  }
331 
332  return !heap_attisnull(htup, attnum, NULL);
333 }
334 
335 /*
336  * Return a list (of StatExtEntry) of statistics objects for the given relation.
337  */
338 static List *
340 {
341  SysScanDesc scan;
342  ScanKeyData skey;
343  HeapTuple htup;
344  List *result = NIL;
345 
346  /*
347  * Prepare to scan pg_statistic_ext for entries having stxrelid = this
348  * rel.
349  */
350  ScanKeyInit(&skey,
351  Anum_pg_statistic_ext_stxrelid,
352  BTEqualStrategyNumber, F_OIDEQ,
353  ObjectIdGetDatum(relid));
354 
355  scan = systable_beginscan(pg_statext, StatisticExtRelidIndexId, true,
356  NULL, 1, &skey);
357 
358  while (HeapTupleIsValid(htup = systable_getnext(scan)))
359  {
360  StatExtEntry *entry;
361  Datum datum;
362  bool isnull;
363  int i;
364  ArrayType *arr;
365  char *enabled;
366  Form_pg_statistic_ext staForm;
367 
368  entry = palloc0(sizeof(StatExtEntry));
369  staForm = (Form_pg_statistic_ext) GETSTRUCT(htup);
370  entry->statOid = staForm->oid;
371  entry->schema = get_namespace_name(staForm->stxnamespace);
372  entry->name = pstrdup(NameStr(staForm->stxname));
373  entry->stattarget = staForm->stxstattarget;
374  for (i = 0; i < staForm->stxkeys.dim1; i++)
375  {
376  entry->columns = bms_add_member(entry->columns,
377  staForm->stxkeys.values[i]);
378  }
379 
380  /* decode the stxkind char array into a list of chars */
381  datum = SysCacheGetAttr(STATEXTOID, htup,
382  Anum_pg_statistic_ext_stxkind, &isnull);
383  Assert(!isnull);
384  arr = DatumGetArrayTypeP(datum);
385  if (ARR_NDIM(arr) != 1 ||
386  ARR_HASNULL(arr) ||
387  ARR_ELEMTYPE(arr) != CHAROID)
388  elog(ERROR, "stxkind is not a 1-D char array");
389  enabled = (char *) ARR_DATA_PTR(arr);
390  for (i = 0; i < ARR_DIMS(arr)[0]; i++)
391  {
392  Assert((enabled[i] == STATS_EXT_NDISTINCT) ||
393  (enabled[i] == STATS_EXT_DEPENDENCIES) ||
394  (enabled[i] == STATS_EXT_MCV));
395  entry->types = lappend_int(entry->types, (int) enabled[i]);
396  }
397 
398  result = lappend(result, entry);
399  }
400 
401  systable_endscan(scan);
402 
403  return result;
404 }
405 
406 /*
407  * Using 'vacatts' of size 'nvacatts' as input data, return a newly built
408  * VacAttrStats array which includes only the items corresponding to
409  * attributes indicated by 'stxkeys'. If we don't have all of the per column
410  * stats available to compute the extended stats, then we return NULL to indicate
411  * to the caller that the stats should not be built.
412  */
413 static VacAttrStats **
415  int nvacatts, VacAttrStats **vacatts)
416 {
417  int i = 0;
418  int x = -1;
419  VacAttrStats **stats;
420 
421  stats = (VacAttrStats **)
422  palloc(bms_num_members(attrs) * sizeof(VacAttrStats *));
423 
424  /* lookup VacAttrStats info for the requested columns (same attnum) */
425  while ((x = bms_next_member(attrs, x)) >= 0)
426  {
427  int j;
428 
429  stats[i] = NULL;
430  for (j = 0; j < nvacatts; j++)
431  {
432  if (x == vacatts[j]->tupattnum)
433  {
434  stats[i] = vacatts[j];
435  break;
436  }
437  }
438 
439  if (!stats[i])
440  {
441  /*
442  * Looks like stats were not gathered for one of the columns
443  * required. We'll be unable to build the extended stats without
444  * this column.
445  */
446  pfree(stats);
447  return NULL;
448  }
449 
450  /*
451  * Sanity check that the column is not dropped - stats should have
452  * been removed in this case.
453  */
454  Assert(!stats[i]->attr->attisdropped);
455 
456  i++;
457  }
458 
459  return stats;
460 }
461 
462 /*
463  * statext_store
464  * Serializes the statistics and stores them into the pg_statistic_ext_data
465  * tuple.
466  */
467 static void
469  MVNDistinct *ndistinct, MVDependencies *dependencies,
470  MCVList *mcv, VacAttrStats **stats)
471 {
472  HeapTuple stup,
473  oldtup;
474  Datum values[Natts_pg_statistic_ext_data];
475  bool nulls[Natts_pg_statistic_ext_data];
476  bool replaces[Natts_pg_statistic_ext_data];
477  Relation pg_stextdata;
478 
479  memset(nulls, true, sizeof(nulls));
480  memset(replaces, false, sizeof(replaces));
481  memset(values, 0, sizeof(values));
482 
483  /*
484  * Construct a new pg_statistic_ext_data tuple, replacing the calculated
485  * stats.
486  */
487  if (ndistinct != NULL)
488  {
489  bytea *data = statext_ndistinct_serialize(ndistinct);
490 
491  nulls[Anum_pg_statistic_ext_data_stxdndistinct - 1] = (data == NULL);
492  values[Anum_pg_statistic_ext_data_stxdndistinct - 1] = PointerGetDatum(data);
493  }
494 
495  if (dependencies != NULL)
496  {
497  bytea *data = statext_dependencies_serialize(dependencies);
498 
499  nulls[Anum_pg_statistic_ext_data_stxddependencies - 1] = (data == NULL);
500  values[Anum_pg_statistic_ext_data_stxddependencies - 1] = PointerGetDatum(data);
501  }
502  if (mcv != NULL)
503  {
504  bytea *data = statext_mcv_serialize(mcv, stats);
505 
506  nulls[Anum_pg_statistic_ext_data_stxdmcv - 1] = (data == NULL);
507  values[Anum_pg_statistic_ext_data_stxdmcv - 1] = PointerGetDatum(data);
508  }
509 
510  /* always replace the value (either by bytea or NULL) */
511  replaces[Anum_pg_statistic_ext_data_stxdndistinct - 1] = true;
512  replaces[Anum_pg_statistic_ext_data_stxddependencies - 1] = true;
513  replaces[Anum_pg_statistic_ext_data_stxdmcv - 1] = true;
514 
515  /* there should already be a pg_statistic_ext_data tuple */
517  if (!HeapTupleIsValid(oldtup))
518  elog(ERROR, "cache lookup failed for statistics object %u", statOid);
519 
520  /* replace it */
521  pg_stextdata = table_open(StatisticExtDataRelationId, RowExclusiveLock);
522 
523  stup = heap_modify_tuple(oldtup,
524  RelationGetDescr(pg_stextdata),
525  values,
526  nulls,
527  replaces);
528  ReleaseSysCache(oldtup);
529  CatalogTupleUpdate(pg_stextdata, &stup->t_self, stup);
530 
531  heap_freetuple(stup);
532 
533  table_close(pg_stextdata, RowExclusiveLock);
534 }
535 
536 /* initialize multi-dimensional sort */
538 multi_sort_init(int ndims)
539 {
540  MultiSortSupport mss;
541 
542  Assert(ndims >= 2);
543 
545  + sizeof(SortSupportData) * ndims);
546 
547  mss->ndims = ndims;
548 
549  return mss;
550 }
551 
552 /*
553  * Prepare sort support info using the given sort operator and collation
554  * at the position 'sortdim'
555  */
556 void
558  Oid oper, Oid collation)
559 {
560  SortSupport ssup = &mss->ssup[sortdim];
561 
563  ssup->ssup_collation = collation;
564  ssup->ssup_nulls_first = false;
565 
567 }
568 
569 /* compare all the dimensions in the selected order */
570 int
571 multi_sort_compare(const void *a, const void *b, void *arg)
572 {
574  SortItem *ia = (SortItem *) a;
575  SortItem *ib = (SortItem *) b;
576  int i;
577 
578  for (i = 0; i < mss->ndims; i++)
579  {
580  int compare;
581 
582  compare = ApplySortComparator(ia->values[i], ia->isnull[i],
583  ib->values[i], ib->isnull[i],
584  &mss->ssup[i]);
585 
586  if (compare != 0)
587  return compare;
588  }
589 
590  /* equal by default */
591  return 0;
592 }
593 
594 /* compare selected dimension */
595 int
596 multi_sort_compare_dim(int dim, const SortItem *a, const SortItem *b,
597  MultiSortSupport mss)
598 {
599  return ApplySortComparator(a->values[dim], a->isnull[dim],
600  b->values[dim], b->isnull[dim],
601  &mss->ssup[dim]);
602 }
603 
604 int
605 multi_sort_compare_dims(int start, int end,
606  const SortItem *a, const SortItem *b,
607  MultiSortSupport mss)
608 {
609  int dim;
610 
611  for (dim = start; dim <= end; dim++)
612  {
613  int r = ApplySortComparator(a->values[dim], a->isnull[dim],
614  b->values[dim], b->isnull[dim],
615  &mss->ssup[dim]);
616 
617  if (r != 0)
618  return r;
619  }
620 
621  return 0;
622 }
623 
624 int
625 compare_scalars_simple(const void *a, const void *b, void *arg)
626 {
627  return compare_datums_simple(*(Datum *) a,
628  *(Datum *) b,
629  (SortSupport) arg);
630 }
631 
632 int
634 {
635  return ApplySortComparator(a, false, b, false, ssup);
636 }
637 
638 /* simple counterpart to qsort_arg */
639 void *
640 bsearch_arg(const void *key, const void *base, size_t nmemb, size_t size,
641  int (*compar) (const void *, const void *, void *),
642  void *arg)
643 {
644  size_t l,
645  u,
646  idx;
647  const void *p;
648  int comparison;
649 
650  l = 0;
651  u = nmemb;
652  while (l < u)
653  {
654  idx = (l + u) / 2;
655  p = (void *) (((const char *) base) + (idx * size));
656  comparison = (*compar) (key, p, arg);
657 
658  if (comparison < 0)
659  u = idx;
660  else if (comparison > 0)
661  l = idx + 1;
662  else
663  return (void *) p;
664  }
665 
666  return NULL;
667 }
668 
669 /*
670  * build_attnums_array
671  * Transforms a bitmap into an array of AttrNumber values.
672  *
673  * This is used for extended statistics only, so all the attribute must be
674  * user-defined. That means offsetting by FirstLowInvalidHeapAttributeNumber
675  * is not necessary here (and when querying the bitmap).
676  */
677 AttrNumber *
678 build_attnums_array(Bitmapset *attrs, int *numattrs)
679 {
680  int i,
681  j;
682  AttrNumber *attnums;
683  int num = bms_num_members(attrs);
684 
685  if (numattrs)
686  *numattrs = num;
687 
688  /* build attnums from the bitmapset */
689  attnums = (AttrNumber *) palloc(sizeof(AttrNumber) * num);
690  i = 0;
691  j = -1;
692  while ((j = bms_next_member(attrs, j)) >= 0)
693  {
694  /*
695  * Make sure the bitmap contains only user-defined attributes. As
696  * bitmaps can't contain negative values, this can be violated in two
697  * ways. Firstly, the bitmap might contain 0 as a member, and secondly
698  * the integer value might be larger than MaxAttrNumber.
699  */
701  Assert(j <= MaxAttrNumber);
702 
703  attnums[i++] = (AttrNumber) j;
704 
705  /* protect against overflows */
706  Assert(i <= num);
707  }
708 
709  return attnums;
710 }
711 
712 /*
713  * build_sorted_items
714  * build a sorted array of SortItem with values from rows
715  *
716  * Note: All the memory is allocated in a single chunk, so that the caller
717  * can simply pfree the return value to release all of it.
718  */
719 SortItem *
720 build_sorted_items(int numrows, int *nitems, HeapTuple *rows, TupleDesc tdesc,
721  MultiSortSupport mss, int numattrs, AttrNumber *attnums)
722 {
723  int i,
724  j,
725  len,
726  idx;
727  int nvalues = numrows * numattrs;
728 
729  SortItem *items;
730  Datum *values;
731  bool *isnull;
732  char *ptr;
733 
734  /* Compute the total amount of memory we need (both items and values). */
735  len = numrows * sizeof(SortItem) + nvalues * (sizeof(Datum) + sizeof(bool));
736 
737  /* Allocate the memory and split it into the pieces. */
738  ptr = palloc0(len);
739 
740  /* items to sort */
741  items = (SortItem *) ptr;
742  ptr += numrows * sizeof(SortItem);
743 
744  /* values and null flags */
745  values = (Datum *) ptr;
746  ptr += nvalues * sizeof(Datum);
747 
748  isnull = (bool *) ptr;
749  ptr += nvalues * sizeof(bool);
750 
751  /* make sure we consumed the whole buffer exactly */
752  Assert((ptr - (char *) items) == len);
753 
754  /* fix the pointers to Datum and bool arrays */
755  idx = 0;
756  for (i = 0; i < numrows; i++)
757  {
758  bool toowide = false;
759 
760  items[idx].values = &values[idx * numattrs];
761  items[idx].isnull = &isnull[idx * numattrs];
762 
763  /* load the values/null flags from sample rows */
764  for (j = 0; j < numattrs; j++)
765  {
766  Datum value;
767  bool isnull;
768 
769  value = heap_getattr(rows[i], attnums[j], tdesc, &isnull);
770 
771  /*
772  * If this is a varlena value, check if it's too wide and if yes
773  * then skip the whole item. Otherwise detoast the value.
774  *
775  * XXX It may happen that we've already detoasted some preceding
776  * values for the current item. We don't bother to cleanup those
777  * on the assumption that those are small (below WIDTH_THRESHOLD)
778  * and will be discarded at the end of analyze.
779  */
780  if ((!isnull) &&
781  (TupleDescAttr(tdesc, attnums[j] - 1)->attlen == -1))
782  {
784  {
785  toowide = true;
786  break;
787  }
788 
789  value = PointerGetDatum(PG_DETOAST_DATUM(value));
790  }
791 
792  items[idx].values[j] = value;
793  items[idx].isnull[j] = isnull;
794  }
795 
796  if (toowide)
797  continue;
798 
799  idx++;
800  }
801 
802  /* store the actual number of items (ignoring the too-wide ones) */
803  *nitems = idx;
804 
805  /* all items were too wide */
806  if (idx == 0)
807  {
808  /* everything is allocated as a single chunk */
809  pfree(items);
810  return NULL;
811  }
812 
813  /* do the sort, using the multi-sort */
814  qsort_arg((void *) items, idx, sizeof(SortItem),
815  multi_sort_compare, mss);
816 
817  return items;
818 }
819 
820 /*
821  * has_stats_of_kind
822  * Check whether the list contains statistic of a given kind
823  */
824 bool
825 has_stats_of_kind(List *stats, char requiredkind)
826 {
827  ListCell *l;
828 
829  foreach(l, stats)
830  {
832 
833  if (stat->kind == requiredkind)
834  return true;
835  }
836 
837  return false;
838 }
839 
840 /*
841  * choose_best_statistics
842  * Look for and return statistics with the specified 'requiredkind' which
843  * have keys that match at least two of the given attnums. Return NULL if
844  * there's no match.
845  *
846  * The current selection criteria is very simple - we choose the statistics
847  * object referencing the most attributes in covered (and still unestimated
848  * clauses), breaking ties in favor of objects with fewer keys overall.
849  *
850  * The clause_attnums is an array of bitmaps, storing attnums for individual
851  * clauses. A NULL element means the clause is either incompatible or already
852  * estimated.
853  *
854  * XXX If multiple statistics objects tie on both criteria, then which object
855  * is chosen depends on the order that they appear in the stats list. Perhaps
856  * further tiebreakers are needed.
857  */
859 choose_best_statistics(List *stats, char requiredkind,
860  Bitmapset **clause_attnums, int nclauses)
861 {
862  ListCell *lc;
863  StatisticExtInfo *best_match = NULL;
864  int best_num_matched = 2; /* goal #1: maximize */
865  int best_match_keys = (STATS_MAX_DIMENSIONS + 1); /* goal #2: minimize */
866 
867  foreach(lc, stats)
868  {
869  int i;
870  StatisticExtInfo *info = (StatisticExtInfo *) lfirst(lc);
871  Bitmapset *matched = NULL;
872  int num_matched;
873  int numkeys;
874 
875  /* skip statistics that are not of the correct type */
876  if (info->kind != requiredkind)
877  continue;
878 
879  /*
880  * Collect attributes in remaining (unestimated) clauses fully covered
881  * by this statistic object.
882  */
883  for (i = 0; i < nclauses; i++)
884  {
885  /* ignore incompatible/estimated clauses */
886  if (!clause_attnums[i])
887  continue;
888 
889  /* ignore clauses that are not covered by this object */
890  if (!bms_is_subset(clause_attnums[i], info->keys))
891  continue;
892 
893  matched = bms_add_members(matched, clause_attnums[i]);
894  }
895 
896  num_matched = bms_num_members(matched);
897  bms_free(matched);
898 
899  /*
900  * save the actual number of keys in the stats so that we can choose
901  * the narrowest stats with the most matching keys.
902  */
903  numkeys = bms_num_members(info->keys);
904 
905  /*
906  * Use this object when it increases the number of matched clauses or
907  * when it matches the same number of attributes but these stats have
908  * fewer keys than any previous match.
909  */
910  if (num_matched > best_num_matched ||
911  (num_matched == best_num_matched && numkeys < best_match_keys))
912  {
913  best_match = info;
914  best_num_matched = num_matched;
915  best_match_keys = numkeys;
916  }
917  }
918 
919  return best_match;
920 }
921 
922 /*
923  * statext_is_compatible_clause_internal
924  * Determines if the clause is compatible with MCV lists.
925  *
926  * Does the heavy lifting of actually inspecting the clauses for
927  * statext_is_compatible_clause. It needs to be split like this because
928  * of recursion. The attnums bitmap is an input/output parameter collecting
929  * attribute numbers from all compatible clauses (recursively).
930  */
931 static bool
933  Index relid, Bitmapset **attnums)
934 {
935  /* Look inside any binary-compatible relabeling (as in examine_variable) */
936  if (IsA(clause, RelabelType))
937  clause = (Node *) ((RelabelType *) clause)->arg;
938 
939  /* plain Var references (boolean Vars or recursive checks) */
940  if (IsA(clause, Var))
941  {
942  Var *var = (Var *) clause;
943 
944  /* Ensure var is from the correct relation */
945  if (var->varno != relid)
946  return false;
947 
948  /* we also better ensure the Var is from the current level */
949  if (var->varlevelsup > 0)
950  return false;
951 
952  /* Also skip system attributes (we don't allow stats on those). */
954  return false;
955 
956  *attnums = bms_add_member(*attnums, var->varattno);
957 
958  return true;
959  }
960 
961  /* (Var op Const) or (Const op Var) */
962  if (is_opclause(clause))
963  {
964  RangeTblEntry *rte = root->simple_rte_array[relid];
965  OpExpr *expr = (OpExpr *) clause;
966  Var *var;
967 
968  /* Only expressions with two arguments are considered compatible. */
969  if (list_length(expr->args) != 2)
970  return false;
971 
972  /* Check if the expression the right shape (one Var, one Const) */
973  if (!examine_opclause_expression(expr, &var, NULL, NULL))
974  return false;
975 
976  /*
977  * If it's not one of the supported operators ("=", "<", ">", etc.),
978  * just ignore the clause, as it's not compatible with MCV lists.
979  *
980  * This uses the function for estimating selectivity, not the operator
981  * directly (a bit awkward, but well ...).
982  */
983  switch (get_oprrest(expr->opno))
984  {
985  case F_EQSEL:
986  case F_NEQSEL:
987  case F_SCALARLTSEL:
988  case F_SCALARLESEL:
989  case F_SCALARGTSEL:
990  case F_SCALARGESEL:
991  /* supported, will continue with inspection of the Var */
992  break;
993 
994  default:
995  /* other estimators are considered unknown/unsupported */
996  return false;
997  }
998 
999  /*
1000  * If there are any securityQuals on the RTE from security barrier
1001  * views or RLS policies, then the user may not have access to all the
1002  * table's data, and we must check that the operator is leak-proof.
1003  *
1004  * If the operator is leaky, then we must ignore this clause for the
1005  * purposes of estimating with MCV lists, otherwise the operator might
1006  * reveal values from the MCV list that the user doesn't have
1007  * permission to see.
1008  */
1009  if (rte->securityQuals != NIL &&
1011  return false;
1012 
1013  return statext_is_compatible_clause_internal(root, (Node *) var,
1014  relid, attnums);
1015  }
1016 
1017  /* AND/OR/NOT clause */
1018  if (is_andclause(clause) ||
1019  is_orclause(clause) ||
1020  is_notclause(clause))
1021  {
1022  /*
1023  * AND/OR/NOT-clauses are supported if all sub-clauses are supported
1024  *
1025  * Perhaps we could improve this by handling mixed cases, when some of
1026  * the clauses are supported and some are not. Selectivity for the
1027  * supported subclauses would be computed using extended statistics,
1028  * and the remaining clauses would be estimated using the traditional
1029  * algorithm (product of selectivities).
1030  *
1031  * It however seems overly complex, and in a way we already do that
1032  * because if we reject the whole clause as unsupported here, it will
1033  * be eventually passed to clauselist_selectivity() which does exactly
1034  * this (split into supported/unsupported clauses etc).
1035  */
1036  BoolExpr *expr = (BoolExpr *) clause;
1037  ListCell *lc;
1038 
1039  foreach(lc, expr->args)
1040  {
1041  /*
1042  * Had we found incompatible clause in the arguments, treat the
1043  * whole clause as incompatible.
1044  */
1046  (Node *) lfirst(lc),
1047  relid, attnums))
1048  return false;
1049  }
1050 
1051  return true;
1052  }
1053 
1054  /* Var IS NULL */
1055  if (IsA(clause, NullTest))
1056  {
1057  NullTest *nt = (NullTest *) clause;
1058 
1059  /*
1060  * Only simple (Var IS NULL) expressions supported for now. Maybe we
1061  * could use examine_variable to fix this?
1062  */
1063  if (!IsA(nt->arg, Var))
1064  return false;
1065 
1066  return statext_is_compatible_clause_internal(root, (Node *) (nt->arg),
1067  relid, attnums);
1068  }
1069 
1070  return false;
1071 }
1072 
1073 /*
1074  * statext_is_compatible_clause
1075  * Determines if the clause is compatible with MCV lists.
1076  *
1077  * Currently, we only support three types of clauses:
1078  *
1079  * (a) OpExprs of the form (Var op Const), or (Const op Var), where the op
1080  * is one of ("=", "<", ">", ">=", "<=")
1081  *
1082  * (b) (Var IS [NOT] NULL)
1083  *
1084  * (c) combinations using AND/OR/NOT
1085  *
1086  * In the future, the range of supported clauses may be expanded to more
1087  * complex cases, for example (Var op Var).
1088  */
1089 static bool
1091  Bitmapset **attnums)
1092 {
1093  RangeTblEntry *rte = root->simple_rte_array[relid];
1094  RestrictInfo *rinfo = (RestrictInfo *) clause;
1095  Oid userid;
1096 
1097  if (!IsA(rinfo, RestrictInfo))
1098  return false;
1099 
1100  /* Pseudoconstants are not really interesting here. */
1101  if (rinfo->pseudoconstant)
1102  return false;
1103 
1104  /* clauses referencing multiple varnos are incompatible */
1106  return false;
1107 
1108  /* Check the clause and determine what attributes it references. */
1109  if (!statext_is_compatible_clause_internal(root, (Node *) rinfo->clause,
1110  relid, attnums))
1111  return false;
1112 
1113  /*
1114  * Check that the user has permission to read all these attributes. Use
1115  * checkAsUser if it's set, in case we're accessing the table via a view.
1116  */
1117  userid = rte->checkAsUser ? rte->checkAsUser : GetUserId();
1118 
1119  if (pg_class_aclcheck(rte->relid, userid, ACL_SELECT) != ACLCHECK_OK)
1120  {
1121  /* Don't have table privilege, must check individual columns */
1122  if (bms_is_member(InvalidAttrNumber, *attnums))
1123  {
1124  /* Have a whole-row reference, must have access to all columns */
1125  if (pg_attribute_aclcheck_all(rte->relid, userid, ACL_SELECT,
1127  return false;
1128  }
1129  else
1130  {
1131  /* Check the columns referenced by the clause */
1132  int attnum = -1;
1133 
1134  while ((attnum = bms_next_member(*attnums, attnum)) >= 0)
1135  {
1136  if (pg_attribute_aclcheck(rte->relid, attnum, userid,
1137  ACL_SELECT) != ACLCHECK_OK)
1138  return false;
1139  }
1140  }
1141  }
1142 
1143  /* If we reach here, the clause is OK */
1144  return true;
1145 }
1146 
1147 /*
1148  * statext_mcv_clauselist_selectivity
1149  * Estimate clauses using the best multi-column statistics.
1150  *
1151  * Selects the best extended (multi-column) statistic on a table (measured by
1152  * the number of attributes extracted from the clauses and covered by it), and
1153  * computes the selectivity for the supplied clauses.
1154  *
1155  * One of the main challenges with using MCV lists is how to extrapolate the
1156  * estimate to the data not covered by the MCV list. To do that, we compute
1157  * not only the "MCV selectivity" (selectivities for MCV items matching the
1158  * supplied clauses), but also a couple of derived selectivities:
1159  *
1160  * - simple selectivity: Computed without extended statistic, i.e. as if the
1161  * columns/clauses were independent
1162  *
1163  * - base selectivity: Similar to simple selectivity, but is computed using
1164  * the extended statistic by adding up the base frequencies (that we compute
1165  * and store for each MCV item) of matching MCV items.
1166  *
1167  * - total selectivity: Selectivity covered by the whole MCV list.
1168  *
1169  * - other selectivity: A selectivity estimate for data not covered by the MCV
1170  * list (i.e. satisfying the clauses, but not common enough to make it into
1171  * the MCV list)
1172  *
1173  * Note: While simple and base selectivities are defined in a quite similar
1174  * way, the values are computed differently and are not therefore equal. The
1175  * simple selectivity is computed as a product of per-clause estimates, while
1176  * the base selectivity is computed by adding up base frequencies of matching
1177  * items of the multi-column MCV list. So the values may differ for two main
1178  * reasons - (a) the MCV list may not cover 100% of the data and (b) some of
1179  * the MCV items did not match the estimated clauses.
1180  *
1181  * As both (a) and (b) reduce the base selectivity value, it generally holds
1182  * that (simple_selectivity >= base_selectivity). If the MCV list covers all
1183  * the data, the values may be equal.
1184  *
1185  * So, (simple_selectivity - base_selectivity) is an estimate for the part
1186  * not covered by the MCV list, and (mcv_selectivity - base_selectivity) may
1187  * be seen as a correction for the part covered by the MCV list. Those two
1188  * statements are actually equivalent.
1189  *
1190  * Note: Due to rounding errors and minor differences in how the estimates
1191  * are computed, the inequality may not always hold. Which is why we clamp
1192  * the selectivities to prevent strange estimate (negative etc.).
1193  *
1194  * 'estimatedclauses' is an input/output parameter. We set bits for the
1195  * 0-based 'clauses' indexes we estimate for and also skip clause items that
1196  * already have a bit set.
1197  *
1198  * XXX If we were to use multiple statistics, this is where it would happen.
1199  * We would simply repeat this on a loop on the "remaining" clauses, possibly
1200  * using the already estimated clauses as conditions (and combining the values
1201  * using conditional probability formula).
1202  */
1203 static Selectivity
1205  JoinType jointype, SpecialJoinInfo *sjinfo,
1206  RelOptInfo *rel, Bitmapset **estimatedclauses)
1207 {
1208  ListCell *l;
1209  Bitmapset **list_attnums;
1210  int listidx;
1212  List *stat_clauses;
1213  Selectivity simple_sel,
1214  mcv_sel,
1215  mcv_basesel,
1216  mcv_totalsel,
1217  other_sel,
1218  sel;
1219 
1220  /* check if there's any stats that might be useful for us. */
1221  if (!has_stats_of_kind(rel->statlist, STATS_EXT_MCV))
1222  return 1.0;
1223 
1224  list_attnums = (Bitmapset **) palloc(sizeof(Bitmapset *) *
1225  list_length(clauses));
1226 
1227  /*
1228  * Pre-process the clauses list to extract the attnums seen in each item.
1229  * We need to determine if there's any clauses which will be useful for
1230  * selectivity estimations with extended stats. Along the way we'll record
1231  * all of the attnums for each clause in a list which we'll reference
1232  * later so we don't need to repeat the same work again. We'll also keep
1233  * track of all attnums seen.
1234  *
1235  * We also skip clauses that we already estimated using different types of
1236  * statistics (we treat them as incompatible).
1237  */
1238  listidx = 0;
1239  foreach(l, clauses)
1240  {
1241  Node *clause = (Node *) lfirst(l);
1242  Bitmapset *attnums = NULL;
1243 
1244  if (!bms_is_member(listidx, *estimatedclauses) &&
1245  statext_is_compatible_clause(root, clause, rel->relid, &attnums))
1246  list_attnums[listidx] = attnums;
1247  else
1248  list_attnums[listidx] = NULL;
1249 
1250  listidx++;
1251  }
1252 
1253  /* find the best suited statistics object for these attnums */
1254  stat = choose_best_statistics(rel->statlist, STATS_EXT_MCV,
1255  list_attnums, list_length(clauses));
1256 
1257  /* if no matching stats could be found then we've nothing to do */
1258  if (!stat)
1259  return 1.0;
1260 
1261  /* Ensure choose_best_statistics produced an expected stats type. */
1262  Assert(stat->kind == STATS_EXT_MCV);
1263 
1264  /* now filter the clauses to be estimated using the selected MCV */
1265  stat_clauses = NIL;
1266 
1267  listidx = 0;
1268  foreach(l, clauses)
1269  {
1270  /*
1271  * If the clause is compatible with the selected statistics, mark it
1272  * as estimated and add it to the list to estimate.
1273  */
1274  if (list_attnums[listidx] != NULL &&
1275  bms_is_subset(list_attnums[listidx], stat->keys))
1276  {
1277  stat_clauses = lappend(stat_clauses, (Node *) lfirst(l));
1278  *estimatedclauses = bms_add_member(*estimatedclauses, listidx);
1279  }
1280 
1281  listidx++;
1282  }
1283 
1284  /*
1285  * First compute "simple" selectivity, i.e. without the extended
1286  * statistics, and essentially assuming independence of the
1287  * columns/clauses. We'll then use the various selectivities computed from
1288  * MCV list to improve it.
1289  */
1290  simple_sel = clauselist_selectivity_simple(root, stat_clauses, varRelid,
1291  jointype, sjinfo, NULL);
1292 
1293  /*
1294  * Now compute the multi-column estimate from the MCV list, along with the
1295  * other selectivities (base & total selectivity).
1296  */
1297  mcv_sel = mcv_clauselist_selectivity(root, stat, stat_clauses, varRelid,
1298  jointype, sjinfo, rel,
1299  &mcv_basesel, &mcv_totalsel);
1300 
1301  /* Estimated selectivity of values not covered by MCV matches */
1302  other_sel = simple_sel - mcv_basesel;
1303  CLAMP_PROBABILITY(other_sel);
1304 
1305  /* The non-MCV selectivity can't exceed the 1 - mcv_totalsel. */
1306  if (other_sel > 1.0 - mcv_totalsel)
1307  other_sel = 1.0 - mcv_totalsel;
1308 
1309  /* Overall selectivity is the combination of MCV and non-MCV estimates. */
1310  sel = mcv_sel + other_sel;
1311  CLAMP_PROBABILITY(sel);
1312 
1313  return sel;
1314 }
1315 
1316 /*
1317  * statext_clauselist_selectivity
1318  * Estimate clauses using the best multi-column statistics.
1319  */
1321 statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
1322  JoinType jointype, SpecialJoinInfo *sjinfo,
1323  RelOptInfo *rel, Bitmapset **estimatedclauses)
1324 {
1325  Selectivity sel;
1326 
1327  /* First, try estimating clauses using a multivariate MCV list. */
1328  sel = statext_mcv_clauselist_selectivity(root, clauses, varRelid, jointype,
1329  sjinfo, rel, estimatedclauses);
1330 
1331  /*
1332  * Then, apply functional dependencies on the remaining clauses by calling
1333  * dependencies_clauselist_selectivity. Pass 'estimatedclauses' so the
1334  * function can properly skip clauses already estimated above.
1335  *
1336  * The reasoning for applying dependencies last is that the more complex
1337  * stats can track more complex correlations between the attributes, and
1338  * so may be considered more reliable.
1339  *
1340  * For example, MCV list can give us an exact selectivity for values in
1341  * two columns, while functional dependencies can only provide information
1342  * about the overall strength of the dependency.
1343  */
1344  sel *= dependencies_clauselist_selectivity(root, clauses, varRelid,
1345  jointype, sjinfo, rel,
1346  estimatedclauses);
1347 
1348  return sel;
1349 }
1350 
1351 /*
1352  * examine_opclause_expression
1353  * Split expression into Var and Const parts.
1354  *
1355  * Attempts to match the arguments to either (Var op Const) or (Const op Var),
1356  * possibly with a RelabelType on top. When the expression matches this form,
1357  * returns true, otherwise returns false.
1358  *
1359  * Optionally returns pointers to the extracted Var/Const nodes, when passed
1360  * non-null pointers (varp, cstp and varonleftp). The varonleftp flag specifies
1361  * on which side of the operator we found the Var node.
1362  */
1363 bool
1364 examine_opclause_expression(OpExpr *expr, Var **varp, Const **cstp, bool *varonleftp)
1365 {
1366  Var *var;
1367  Const *cst;
1368  bool varonleft;
1369  Node *leftop,
1370  *rightop;
1371 
1372  /* enforced by statext_is_compatible_clause_internal */
1373  Assert(list_length(expr->args) == 2);
1374 
1375  leftop = linitial(expr->args);
1376  rightop = lsecond(expr->args);
1377 
1378  /* strip RelabelType from either side of the expression */
1379  if (IsA(leftop, RelabelType))
1380  leftop = (Node *) ((RelabelType *) leftop)->arg;
1381 
1382  if (IsA(rightop, RelabelType))
1383  rightop = (Node *) ((RelabelType *) rightop)->arg;
1384 
1385  if (IsA(leftop, Var) && IsA(rightop, Const))
1386  {
1387  var = (Var *) leftop;
1388  cst = (Const *) rightop;
1389  varonleft = true;
1390  }
1391  else if (IsA(leftop, Const) && IsA(rightop, Var))
1392  {
1393  var = (Var *) rightop;
1394  cst = (Const *) leftop;
1395  varonleft = false;
1396  }
1397  else
1398  return false;
1399 
1400  /* return pointers to the extracted parts if requested */
1401  if (varp)
1402  *varp = var;
1403 
1404  if (cstp)
1405  *cstp = cst;
1406 
1407  if (varonleftp)
1408  *varonleftp = varonleft;
1409 
1410  return true;
1411 }
bool ssup_nulls_first
Definition: sortsupport.h:75
#define NIL
Definition: pg_list.h:65
Selectivity dependencies_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Bitmapset **estimatedclauses)
Definition: dependencies.c:941
int ComputeExtStatisticsRows(Relation onerel, int natts, VacAttrStats **vacattrstats)
bool get_func_leakproof(Oid funcid)
Definition: lsyscache.c:1639
MCVList * statext_mcv_build(int numrows, HeapTuple *rows, Bitmapset *attrs, VacAttrStats **stats, double totalrows, int stattarget)
Definition: mcv.c:183
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
#define AllocSetContextCreate
Definition: memutils.h:170
List * statlist
Definition: pathnodes.h:681
void table_close(Relation relation, LOCKMODE lockmode)
Definition: table.c:133
Index varlevelsup
Definition: primnodes.h:177
void systable_endscan(SysScanDesc sysscan)
Definition: genam.c:525
#define GETSTRUCT(TUP)
Definition: htup_details.h:655
void * bsearch_arg(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *, void *), void *arg)
AclResult pg_attribute_aclcheck(Oid table_oid, AttrNumber attnum, Oid roleid, AclMode mode)
Definition: aclchk.c:4515
#define RelationGetDescr(relation)
Definition: rel.h:448
Oid GetUserId(void)
Definition: miscinit.c:380
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:103
#define MaxAttrNumber
Definition: attnum.h:24
#define PointerGetDatum(X)
Definition: postgres.h:556
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:92
List * securityQuals
Definition: parsenodes.h:1102
char * pstrdup(const char *in)
Definition: mcxt.c:1186
Relids clause_relids
Definition: pathnodes.h:1960
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1043
bool pseudoconstant
Definition: pathnodes.h:1953
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
static int statext_compute_stattarget(int stattarget, int natts, VacAttrStats **stats)
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:94
SortItem * build_sorted_items(int numrows, int *nitems, HeapTuple *rows, TupleDesc tdesc, MultiSortSupport mss, int numattrs, AttrNumber *attnums)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
static struct @145 value
#define AttrNumberIsForUserDefinedAttr(attributeNumber)
Definition: attnum.h:41
Definition: nodes.h:525
int multi_sort_compare_dims(int start, int end, const SortItem *a, const SortItem *b, MultiSortSupport mss)
int errcode(int sqlerrcode)
Definition: elog.c:608
AttrNumber varattno
Definition: primnodes.h:172
bool heap_attisnull(HeapTuple tup, int attnum, TupleDesc tupleDesc)
Definition: heaptuple.c:359
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:263
bool statext_is_kind_built(HeapTuple htup, char type)
double Selectivity
Definition: nodes.h:658
static List * fetch_statentries_for_relation(Relation pg_statext, Oid relid)
Form_pg_class rd_rel
Definition: rel.h:83
void heap_freetuple(HeapTuple htup)
Definition: heaptuple.c:1338
unsigned int Oid
Definition: postgres_ext.h:31
#define StatisticExtRelidIndexId
Definition: indexing.h:238
Definition: primnodes.h:167
SysScanDesc systable_beginscan(Relation heapRelation, Oid indexId, bool indexOK, Snapshot snapshot, int nkeys, ScanKey key)
Definition: genam.c:352
Selectivity clauselist_selectivity_simple(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, Bitmapset *estimatedclauses)
Definition: clausesel.c:150
#define lsecond(l)
Definition: pg_list.h:200
Form_pg_attribute attr
Definition: vacuum.h:85
JoinType
Definition: nodes.h:692
Bitmapset * columns
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
HeapTuple systable_getnext(SysScanDesc sysscan)
Definition: genam.c:444
void pfree(void *pointer)
Definition: mcxt.c:1056
#define linitial(l)
Definition: pg_list.h:195
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
SortSupportData ssup[FLEXIBLE_ARRAY_MEMBER]
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
void multi_sort_add_dimension(MultiSortSupport mss, int sortdim, Oid oper, Oid collation)
#define lfirst_int(lc)
Definition: pg_list.h:191
#define ARR_DIMS(a)
Definition: array.h:282
MemoryContext ssup_cxt
Definition: sortsupport.h:66
static Selectivity statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Bitmapset **estimatedclauses)
Expr * arg
Definition: primnodes.h:1205
ItemPointerData t_self
Definition: htup.h:65
void BuildRelationExtStatistics(Relation onerel, double totalrows, int numrows, HeapTuple *rows, int natts, VacAttrStats **vacattrstats)
bytea * statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
Definition: mcv.c:618
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:192
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:646
#define ARR_DATA_PTR(a)
Definition: array.h:310
char * get_namespace_name(Oid nspid)
Definition: lsyscache.c:3094
int multi_sort_compare_dim(int dim, const SortItem *a, const SortItem *b, MultiSortSupport mss)
AttrNumber * build_attnums_array(Bitmapset *attrs, int *numattrs)
#define RowExclusiveLock
Definition: lockdefs.h:38
#define RelationGetRelationName(relation)
Definition: rel.h:456
int compare_scalars_simple(const void *a, const void *b, void *arg)
#define ARR_HASNULL(a)
Definition: array.h:279
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
Selectivity statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Bitmapset **estimatedclauses)
Size toast_raw_datum_size(Datum value)
Definition: detoast.c:806
bool IsAutoVacuumWorkerProcess(void)
Definition: autovacuum.c:3281
#define ereport(elevel, rest)
Definition: elog.h:141
MultiSortSupport multi_sort_init(int ndims)
List * lappend_int(List *list, int datum)
Definition: list.c:340
Index relid
Definition: pathnodes.h:671
List * lappend(List *list, void *datum)
Definition: list.c:322
RangeTblEntry ** simple_rte_array
Definition: pathnodes.h:211
Expr * clause
Definition: pathnodes.h:1945
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
int16 attlen
Definition: pg_attribute.h:64
#define WARNING
Definition: elog.h:40
Index varno
Definition: primnodes.h:170
#define heap_getattr(tup, attnum, tupleDesc, isnull)
Definition: htup_details.h:762
#define stat(a, b)
Definition: win32_port.h:255
struct SortSupportData SortSupportData
HeapTuple SearchSysCache1(int cacheId, Datum key1)
Definition: syscache.c:1116
static bool is_notclause(const void *clause)
Definition: nodeFuncs.h:112
int compare_datums_simple(Datum a, Datum b, SortSupport ssup)
RegProcedure get_oprrest(Oid opno)
Definition: lsyscache.c:1359
MVDependencies * statext_dependencies_build(int numrows, HeapTuple *rows, Bitmapset *attrs, VacAttrStats **stats)
Definition: dependencies.c:357
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:672
void * palloc0(Size size)
Definition: mcxt.c:980
uintptr_t Datum
Definition: postgres.h:367
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1164
#define ACL_SELECT
Definition: parsenodes.h:75
struct SortItem SortItem
Datum SysCacheGetAttr(int cacheId, HeapTuple tup, AttrNumber attributeNumber, bool *isNull)
Definition: syscache.c:1377
bytea * statext_ndistinct_serialize(MVNDistinct *ndistinct)
Definition: mvdistinct.c:171
#define WIDTH_THRESHOLD
struct StatExtEntry StatExtEntry
unsigned int Index
Definition: c.h:476
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1092
int16 attnum
Definition: pg_attribute.h:79
MVNDistinct * statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows, Bitmapset *attrs, VacAttrStats **stats)
Definition: mvdistinct.c:86
void bms_free(Bitmapset *a)
Definition: bitmapset.c:208
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
#define Assert(condition)
Definition: c.h:739
#define lfirst(lc)
Definition: pg_list.h:190
int multi_sort_compare(const void *a, const void *b, void *arg)
AclResult pg_attribute_aclcheck_all(Oid table_oid, Oid roleid, AclMode mode, AclMaskHow how)
Definition: aclchk.c:4544
void CatalogTupleUpdate(Relation heapRel, ItemPointer otid, HeapTuple tup)
Definition: indexing.c:224
static int list_length(const List *l)
Definition: pg_list.h:169
static bool statext_is_compatible_clause(PlannerInfo *root, Node *clause, Index relid, Bitmapset **attnums)
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:736
#define ARR_NDIM(a)
Definition: array.h:278
List * args
Definition: primnodes.h:569
#define InvalidAttrNumber
Definition: attnum.h:23
AclResult pg_class_aclcheck(Oid table_oid, Oid roleid, AclMode mode)
Definition: aclchk.c:4629
static void statext_store(Oid relid, MVNDistinct *ndistinct, MVDependencies *dependencies, MCVList *mcv, VacAttrStats **stats)
static Datum values[MAXATTR]
Definition: bootstrap.c:167
static bool statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause, Index relid, Bitmapset **attnums)
Bitmapset * keys
Definition: pathnodes.h:887
#define STATS_MAX_DIMENSIONS
Definition: statistics.h:19
void * palloc(Size size)
Definition: mcxt.c:949
int errmsg(const char *fmt,...)
Definition: elog.c:822
bytea * statext_dependencies_serialize(MVDependencies *dependencies)
Definition: dependencies.c:446
#define elog(elevel,...)
Definition: elog.h:228
int i
#define NameStr(name)
Definition: c.h:616
void ScanKeyInit(ScanKey entry, AttrNumber attributeNumber, StrategyNumber strategy, RegProcedure procedure, Datum argument)
Definition: scankey.c:76
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:1794
void * arg
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:235
Definition: c.h:556
MultiSortSupportData * MultiSortSupport
Oid opno
Definition: primnodes.h:502
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:63
bool examine_opclause_expression(OpExpr *expr, Var **varp, Const **cstp, bool *varonleftp)
List * args
Definition: primnodes.h:508
Operator oper(ParseState *pstate, List *opname, Oid ltypeId, Oid rtypeId, bool noError, int location)
Definition: parse_oper.c:377
Relation table_open(Oid relationId, LOCKMODE lockmode)
Definition: table.c:39
HeapTuple heap_modify_tuple(HeapTuple tuple, TupleDesc tupleDesc, Datum *replValues, bool *replIsnull, bool *doReplace)
Definition: heaptuple.c:1113
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
Definition: pg_list.h:50
int errtable(Relation rel)
Definition: relcache.c:5218
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:427
bool has_stats_of_kind(List *stats, char requiredkind)
#define ARR_ELEMTYPE(a)
Definition: array.h:280
static VacAttrStats ** lookup_var_attr_stats(Relation rel, Bitmapset *attrs, int nvacatts, VacAttrStats **vacatts)
int16 AttrNumber
Definition: attnum.h:21
#define RelationGetRelid(relation)
Definition: rel.h:422
#define BTEqualStrategyNumber
Definition: stratnum.h:31
#define offsetof(type, field)
Definition: c.h:662
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:793
int default_statistics_target
Definition: analyze.c:80
FormData_pg_statistic_ext * Form_pg_statistic_ext
StatisticExtInfo * choose_best_statistics(List *stats, char requiredkind, Bitmapset **clause_attnums, int nclauses)
unsigned char bool
Definition: c.h:309
#define DatumGetArrayTypeP(X)
Definition: array.h:249