1/*-------------------------------------------------------------------------
4 * POSTGRES multivariate MCV lists
7 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/statistics/mcv.c
13 *-------------------------------------------------------------------------
29#include "utils/fmgrprotos.h"
36 * Computes size of a serialized MCV item, depending on the number of
37 * dimensions (columns) the statistic is defined on. The datum values are
38 * stored in a separate array (deduplicated, to minimize the size), and
39 * so the serialized items only store uint16 indexes into that array.
41 * Each serialized item stores (in this order):
43 * - indexes to values (ndim * sizeof(uint16))
44 * - null flags (ndim * sizeof(bool))
45 * - frequency (sizeof(double))
46 * - base_frequency (sizeof(double))
48 * There is no alignment padding within an MCV item.
49 * So in total each MCV item requires this many bytes:
51 * ndim * (sizeof(uint16) + sizeof(bool)) + 2 * sizeof(double)
53 #define ITEM_SIZE(ndims) \
54 ((ndims) * (sizeof(uint16) + sizeof(bool)) + 2 * sizeof(double))
57 * Used to compute size of serialized MCV list representation.
59 #define MinSizeOfMCVList \
60 (VARHDRSZ + sizeof(uint32) * 3 + sizeof(AttrNumber))
63 * Size of the serialized MCV list, excluding the space needed for
64 * deduplicated per-dimension values. The macro is meant to be used
65 * when it's not yet safe to access the serialized info about amount
66 * of data for each column.
68 #define SizeOfMCVList(ndims,nitems) \
69 ((MinSizeOfMCVList + sizeof(Oid) * (ndims)) + \
70 ((ndims) * sizeof(DimensionInfo)) + \
71 ((nitems) * ITEM_SIZE(ndims)))
85 * Compute new value for bitmap item, considering whether it's used for
86 * clauses connected by AND/OR.
88 #define RESULT_MERGE(value, is_or, match) \
89 ((is_or) ? ((value) || (match)) : ((value) && (match)))
92 * When processing a list of clauses, the bitmap item may get set to a value
93 * such that additional clauses can't change it. For example, when processing
94 * a list of clauses connected to AND, as soon as the item gets set to 'false'
95 * then it'll remain like that. Similarly clauses connected by OR and 'true'.
97 * Returns true when the value in the bitmap can't change no matter how the
98 * remaining clauses are evaluated.
100 #define RESULT_IS_FINAL(value, is_or) ((is_or) ? (value) : (!(value)))
103 * get_mincount_for_mcv_list
104 * Determine the minimum number of times a value needs to appear in
105 * the sample for it to be included in the MCV list.
107 * We want to keep only values that appear sufficiently often in the
108 * sample that it is reasonable to extrapolate their sample frequencies to
109 * the entire table. We do this by placing an upper bound on the relative
110 * standard error of the sample frequency, so that any estimates the
111 * planner generates from the MCV statistics can be expected to be
112 * reasonably accurate.
114 * Since we are sampling without replacement, the sample frequency of a
115 * particular value is described by a hypergeometric distribution. A
116 * common rule of thumb when estimating errors in this situation is to
117 * require at least 10 instances of the value in the sample, in which case
118 * the distribution can be approximated by a normal distribution, and
119 * standard error analysis techniques can be applied. Given a sample size
120 * of n, a population size of N, and a sample frequency of p=cnt/n, the
121 * standard error of the proportion p is given by
122 * SE = sqrt(p*(1-p)/n) * sqrt((N-n)/(N-1))
123 * where the second term is the finite population correction. To get
124 * reasonably accurate planner estimates, we impose an upper bound on the
125 * relative standard error of 20% -- i.e., SE/p < 0.2. This 20% relative
126 * error bound is fairly arbitrary, but has been found empirically to work
127 * well. Rearranging this formula gives a lower bound on the number of
128 * instances of the value seen:
129 * cnt > n*(N-n) / (N-n+0.04*n*(N-1))
130 * This bound is at most 25, and approaches 0 as n approaches 0 or N. The
131 * case where n approaches 0 cannot happen in practice, since the sample
132 * size is at least 300. The case where n approaches N corresponds to
133 * sampling the whole table, in which case it is reasonable to keep
134 * the whole MCV list (have no lower bound), so it makes sense to apply
135 * this formula for all inputs, even though the above derivation is
136 * technically only valid when the right hand side is at least around 10.
138 * An alternative way to look at this formula is as follows -- assume that
139 * the number of instances of the value seen scales up to the entire
140 * table, so that the population count is K=N*cnt/n. Then the distribution
141 * in the sample is a hypergeometric distribution parameterised by N, n
142 * and K, and the bound above is mathematically equivalent to demanding
143 * that the standard deviation of that distribution is less than 20% of
144 * its mean. Thus the relative errors in any planner estimates produced
145 * from the MCV statistics are likely to be not too large.
150 double n = samplerows;
151 double N = totalrows;
156 denom = N - n + 0.04 * n * (N - 1);
158 /* Guard against division by zero (possible if n = N = 1) */
162 return numer / denom;
166 * Builds MCV list from the set of sampled rows.
168 * The algorithm is quite simple:
170 * (1) sort the data (default collation, '<' for the data type)
172 * (2) count distinct groups, decide how many to keep
174 * (3) build the MCV list using the threshold determined in (2)
176 * (4) remove rows represented by the MCV from the sample
193 /* comparator for all the columns */
203 /* for convenience */
204 numattrs =
data->nattnums;
205 numrows =
data->numrows;
207 /* transform the sorted rows into groups (sorted by frequency) */
211 * The maximum number of MCV items to store, based on the statistics
212 * target we computed for the statistics object (from the target set for
213 * the object itself, attributes and the system default). In any case, we
214 * can't keep more groups than we have available.
221 * Decide how many items to keep in the MCV list. We can't use the same
222 * algorithm as per-column MCV lists, because that only considers the
223 * actual group frequency - but we're primarily interested in how the
224 * actual frequency differs from the base frequency (product of simple
225 * per-column frequencies, as if the columns were independent).
227 * Using the same algorithm might exclude items that are close to the
228 * "average" frequency of the sample. But that does not say whether the
229 * observed frequency is close to the base frequency or not. We also need
230 * to consider unexpectedly uncommon items (again, compared to the base
231 * frequency), and the single-column algorithm does not have to.
233 * We simply decide how many items to keep by computing the minimum count
234 * using get_mincount_for_mcv_list() and then keep all items that seem to
235 * be more common than that.
240 * Walk the groups until we find the first group with a count below the
241 * mincount threshold (the index of that group is the number of groups we
246 if (groups[
i].count < mincount)
254 * At this point, we know the number of items for the MCV list. There
255 * might be none (for uniform distribution with many groups), and in that
256 * case, there will be no MCV list. Otherwise, construct the MCV list.
264 /* frequencies for values in each attribute */
268 /* used to search values */
272 /* compute frequencies for values in each column */
273 nfreqs = (
int *)
palloc0(
sizeof(
int) * numattrs);
277 * Allocate the MCV list structure, set the global parameters.
287 /* store info about data type OIDs */
288 for (
i = 0;
i < numattrs;
i++)
291 /* Copy the first chunk of groups into the result. */
294 /* just point to the proper place in the list */
298 item->
isnull = (
bool *)
palloc(
sizeof(
bool) * numattrs);
300 /* copy values for the group */
302 memcpy(item->
isnull, groups[
i].
isnull,
sizeof(
bool) * numattrs);
304 /* groups should be sorted by frequency in descending order */
305 Assert((
i == 0) || (groups[
i - 1].count >= groups[
i].count));
307 /* group frequency */
308 item->
frequency = (double) groups[
i].count / numrows;
310 /* base frequency, if the attributes were independent */
312 for (
j = 0;
j < numattrs;
j++)
316 /* single dimension */
320 /* fill search key */
344 * Build a MultiSortSupport for the given StatsBuildData.
350 int numattrs =
data->nattnums;
352 /* Sort by multiple columns (using array of SortSupport) */
355 /* prepare the sort functions for all the attributes */
356 for (
i = 0;
i < numattrs;
i++)
363 elog(
ERROR,
"cache lookup failed for ordering operator for type %u",
373 * count_distinct_groups
374 * Count distinct combinations of SortItems in the array.
376 * The array is assumed to be sorted according to the MultiSortSupport.
385 for (
i = 1;
i < numrows;
i++)
387 /* make sure the array really is sorted */
398 * compare_sort_item_count
399 * Comparator for sorting items by count (frequencies) in descending
417 * build_distinct_groups
418 * Build an array of SortItems for distinct groups and counts matching
421 * The 'items' array is assumed to be sorted.
434 groups[0] =
items[0];
437 for (
i = 1;
i < numrows;
i++)
439 /* Assume sorted in ascending order. */
442 /* New distinct group detected. */
452 /* ensure we filled the expected number of distinct groups */
455 /* Sort the distinct groups by frequency (in descending order). */
459 *ndistinct = ngroups;
463/* compare sort items (single dimension) */
477 * build_column_frequencies
478 * Compute frequencies of values in each column.
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.
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
501 /* allocate arrays for all columns as a single chunk */
505 /* initial array of pointers */
509 for (dim = 0; dim < mss->
ndims; dim++)
513 /* array of values for a single column */
517 /* extract data for the dimension */
518 for (
i = 0;
i < ngroups;
i++)
520 /* point into the input groups */
526 /* sort the values, deduplicate */
531 * Identify distinct values, compute frequency (there might be
532 * multiple MCV items containing this value, so we need to sum counts
536 for (
i = 1;
i < ngroups;
i++)
540 result[dim][ncounts[dim] - 1].
count += result[dim][
i].
count;
544 result[dim][ncounts[dim]] = result[dim][
i];
555 * Load the MCV list for the indicated pg_statistic_ext_data tuple.
567 elog(
ERROR,
"cache lookup failed for statistics object %u", mvoid);
570 Anum_pg_statistic_ext_data_stxdmcv, &isnull);
574 "requested statistics kind \"%c\" is not yet built for statistics object %u",
575 STATS_EXT_MCV, mvoid);
586 * statext_mcv_serialize
587 * Serialize MCV list into a pg_mcv_list value.
589 * The MCV items may include values of various data types, and it's reasonable
590 * to expect redundancy (values for a given attribute, repeated for multiple
591 * MCV list items). So we deduplicate the values into arrays, and then replace
592 * the values by indexes into those arrays.
594 * The overall structure of the serialized representation looks like this:
596 * +---------------+----------------+---------------------+-------+
597 * | header fields | dimension info | deduplicated values | items |
598 * +---------------+----------------+---------------------+-------+
600 * Where dimension info stores information about the type of the K-th
601 * attribute (e.g. typlen, typbyval and length of deduplicated values).
602 * Deduplicated values store deduplicated values for each attribute. And
603 * items store the actual MCV list items, with values replaced by indexes into
606 * When serializing the items, we use uint16 indexes. The number of MCV items
607 * is limited by the statistics target (which is capped to 10k at the moment).
608 * We might increase this to 65k and still fit into uint16, so there's a bit of
609 * slack. Furthermore, this limit is on the number of distinct values per column,
610 * and we usually have few of those (and various combinations of them for the
611 * those MCV list). So uint16 seems fine for now.
613 * We don't really expect the serialization to save as much space as for
614 * histograms, as we are not doing any bucket splits (which is the source
615 * of high redundancy in histograms).
617 * TODO: Consider packing boolean flags (NULL) for each item into a single char
618 * (or a longer type) instead of using an array of bool items.
632 /* serialized items (indexes into arrays, etc.) */
637 /* values per dimension (and number of non-NULL values) */
639 int *counts = (
int *)
palloc0(
sizeof(
int) * ndims);
642 * We'll include some rudimentary information about the attribute types
643 * (length, by-val flag), so that we don't have to look them up while
644 * deserializing the MCV list (we already have the type OID in the
645 * header). This is safe because when changing the type of the attribute
646 * the statistics gets dropped automatically. We need to store the info
647 * about the arrays of deduplicated values anyway.
651 /* sort support data for all attributes included in the MCV list */
654 /* collect and deduplicate values for each dimension (attribute) */
655 for (dim = 0; dim < ndims; dim++)
661 * Lookup the LT operator (can't get it from stats extra_data, as we
662 * don't know how to interpret that - scalar vs. array etc.).
666 /* copy important info about the data type (length, by-value) */
670 /* allocate space for values in the attribute and collect them */
675 /* skip NULL values - we don't need to deduplicate those */
679 /* append the value at the end */
684 /* if there are just NULL values in this dimension, we're done */
685 if (counts[dim] == 0)
688 /* sort and deduplicate the data */
699 * Walk through the array and eliminate duplicate values, but keep the
700 * ordering (so that we can do a binary search later). We know there's
701 * at least one item as (counts[dim] != 0), so we can skip the first
704 ndistinct = 1;
/* number of distinct values */
705 for (
i = 1;
i < counts[dim];
i++)
707 /* expect sorted array */
710 /* if the value is the same as the previous one, we can skip it */
718 /* we must not exceed PG_UINT16_MAX, as we use uint16 indexes */
722 * Store additional info about the attribute - number of deduplicated
723 * values, and also size of the serialized data. For fixed-length data
724 * types this is trivial to compute, for varwidth types we need to
725 * actually walk the array and sum the sizes.
729 if (info[dim].typbyval)
/* by-value data types */
734 * We copy the data into the MCV item during deserialization, so
735 * we don't need to allocate any extra space.
739 else if (info[dim].typlen > 0)
/* fixed-length by-ref */
742 * We don't care about alignment in the serialized data, so we
743 * pack the data as much as possible. But we also track how much
744 * data will be needed after deserialization, and in that case we
745 * need to account for alignment of each item.
747 * Note: As the items are fixed-length, we could easily compute
748 * this during deserialization, but we do it here anyway.
753 else if (info[dim].typlen == -1)
/* varlena */
762 * For varlena values, we detoast the values and store the
763 * length and data separately. We don't bother with alignment
764 * here, which means that during deserialization we need to
765 * copy the fields and only access the copies.
769 /* serialized length (uint32 length + data) */
772 info[dim].
nbytes +=
len;
/* value (no header) */
775 * During deserialization we'll build regular varlena values
776 * with full headers, and we need to align them properly.
781 else if (info[dim].typlen == -2)
/* cstring */
790 * cstring is handled similar to varlena - first we store the
791 * length as uint32 and then the data. We don't care about
792 * alignment, which means that during deserialization we need
793 * to copy the fields and only access the copies.
796 /* c-strings include terminator, so +1 byte */
801 /* space needed for properly aligned deserialized copies */
806 /* we know (count>0) so there must be some data */
807 Assert(info[dim].nbytes > 0);
811 * Now we can finally compute how much space we'll actually need for the
812 * whole serialized MCV list (varlena header, MCV header, dimension info
813 * for each attribute, deduplicated values and items).
815 total_length = (3 *
sizeof(
uint32))
/* magic + type + nitems */
817 + (ndims *
sizeof(
Oid));
/* attribute types */
822 /* add space for the arrays of deduplicated values */
823 for (
i = 0;
i < ndims;
i++)
824 total_length += info[
i].nbytes;
827 * And finally account for the items (those are fixed-length, thanks to
828 * replacing values with uint16 indexes into the deduplicated arrays).
833 * Allocate space for the whole serialized MCV list (we'll skip bytes, so
834 * we set them to zero to make the result more compressible).
840 endptr = ptr + total_length;
842 /* copy the MCV list header fields, one by one */
855 memcpy(ptr, mcvlist->
types,
sizeof(
Oid) * ndims);
856 ptr += (
sizeof(
Oid) * ndims);
858 /* store information about the attributes (data amounts, ...) */
862 /* Copy the deduplicated values for all attributes to the output. */
863 for (dim = 0; dim < ndims; dim++)
865 /* remember the starting point for Asserts later */
872 if (info[dim].typbyval)
/* passed by value */
877 * For byval types, we need to copy just the significant bytes
878 * - we can't use memcpy directly, as that assumes
879 * little-endian behavior. store_att_byval does almost what
880 * we need, but it requires a properly aligned buffer - the
881 * output buffer does not guarantee that. So we simply use a
882 * local Datum variable (which guarantees proper alignment),
883 * and then copy the value from it.
887 memcpy(ptr, &tmp, info[dim].typlen);
890 else if (info[dim].typlen > 0)
/* passed by reference */
892 /* no special alignment needed, treated as char array */
896 else if (info[dim].typlen == -1)
/* varlena */
900 /* copy the length */
904 /* data from the varlena value (without the header) */
908 else if (info[dim].typlen == -2)
/* cstring */
912 /* copy the length */
921 /* no underflows or overflows */
925 /* we should get exactly nbytes of data for this dimension */
929 /* Serialize the items, with uint16 indexes instead of the values. */
934 /* don't write beyond the allocated space */
937 /* copy NULL and frequency flags into the serialized MCV */
938 memcpy(ptr, mcvitem->
isnull,
sizeof(
bool) * ndims);
939 ptr +=
sizeof(bool) * ndims;
941 memcpy(ptr, &mcvitem->
frequency,
sizeof(
double));
942 ptr +=
sizeof(double);
945 ptr +=
sizeof(double);
947 /* store the indexes last */
948 for (dim = 0; dim < ndims; dim++)
953 /* do the lookup only for non-NULL values */
954 if (!mcvitem->
isnull[dim])
960 Assert(
value != NULL);
/* serialization or deduplication
963 /* compute index within the deduplicated array */
966 /* check the index is within expected bounds */
970 /* copy the index into the serialized MCV */
975 /* make sure we don't overflow the allocated value */
979 /* at this point we expect to match the total_length exactly */
989 * statext_mcv_deserialize
990 * Reads serialized MCV list into MCVList structure.
992 * All the memory needed by the MCV list is allocated as a single chunk, so
993 * it's possible to simply pfree() it at once.
1010 /* local allocation buffer (used only for deserialization) */
1016 /* buffer used for the result */
1026 * We can't possibly deserialize a MCV list if there's not even a complete
1027 * header. We need an explicit formula here, because we serialize the
1028 * header fields one by one, so we need to ignore struct alignment.
1031 elog(
ERROR,
"invalid MCV size %zu (expected at least %zu)",
1034 /* read the MCV list header */
1037 /* pointer to the data part (skip the varlena header) */
1038 raw = (
char *)
data;
1042 /* get the header and perform further sanity checks */
1056 elog(
ERROR,
"invalid MCV magic %u (expected %u)",
1060 elog(
ERROR,
"invalid MCV type %u (expected %u)",
1064 elog(
ERROR,
"invalid zero-length dimension array in MCVList");
1067 elog(
ERROR,
"invalid length (%d) dimension array in MCVList",
1070 if (mcvlist->
nitems == 0)
1071 elog(
ERROR,
"invalid zero-length item array in MCVList");
1073 elog(
ERROR,
"invalid length (%u) item array in MCVList",
1080 * Check amount of data including DimensionInfo for all dimensions and
1081 * also the serialized items (including uint16 indexes). Also, walk
1082 * through the dimension information and add it to the sum.
1087 * Check that we have at least the dimension and info records, along with
1088 * the items. We don't know the size of the serialized values yet. We need
1089 * to do this check first, before accessing the dimension info.
1092 elog(
ERROR,
"invalid MCV size %zu (expected %zu)",
1095 /* Now copy the array of type Oids. */
1096 memcpy(mcvlist->
types, ptr,
sizeof(
Oid) * ndims);
1097 ptr += (
sizeof(
Oid) * ndims);
1099 /* Now it's safe to access the dimension info. */
1105 /* account for the value arrays */
1106 for (dim = 0; dim < ndims; dim++)
1109 * XXX I wonder if we can/should rely on asserts here. Maybe those
1110 * checks should be done every time?
1112 Assert(info[dim].nvalues >= 0);
1113 Assert(info[dim].nbytes >= 0);
1115 expected_size += info[dim].
nbytes;
1119 * Now we know the total expected MCV size, including all the pieces
1120 * (header, dimension info. items and deduplicated data). So do the final
1124 elog(
ERROR,
"invalid MCV size %zu (expected %zu)",
1128 * We need an array of Datum values for each dimension, so that we can
1129 * easily translate the uint16 indexes later. We also need a top-level
1130 * array of pointers to those per-dimension arrays.
1132 * While allocating the arrays for dimensions, compute how much space we
1133 * need for a copy of the by-ref data, as we can't simply point to the
1134 * original values (it might go away).
1136 datalen = 0;
/* space for by-ref data */
1139 for (dim = 0; dim < ndims; dim++)
1143 /* space needed for a copy of data for by-ref types */
1148 * Now resize the MCV list so that the allocation includes all the data.
1150 * Allocate space for a copy of the data, as we can't simply reference the
1151 * serialized data - it's not aligned properly, and it may disappear while
1152 * we're still using the MCV list, e.g. due to catcache release.
1154 * We do care about alignment here, because we will allocate all the
1155 * pieces at once, but then use pointers to different parts.
1159 /* arrays of values and isnull flags for all MCV items */
1163 /* we don't quite need to align this, but it makes some asserts easier */
1166 /* now resize the deserialized MCV list, and compute pointers to parts */
1167 mcvlist =
repalloc(mcvlist, mcvlen);
1169 /* pointer to the beginning of values/isnull arrays */
1170 valuesptr = (
char *) mcvlist
1178 * Build mapping (index => value) for translating the serialized data into
1179 * the in-memory representation.
1181 for (dim = 0; dim < ndims; dim++)
1183 /* remember start position in the input array */
1186 if (info[dim].typbyval)
1188 /* for by-val types we simply copy data into the mapping */
1193 memcpy(&v, ptr, info[dim].typlen);
1196 map[dim][
i] =
fetch_att(&v,
true, info[dim].typlen);
1198 /* no under/overflow of input array */
1204 /* for by-ref types we need to also make a copy of the data */
1206 /* passed by reference, but fixed length (name, tid, ...) */
1207 if (info[dim].typlen > 0)
1211 memcpy(dataptr, ptr, info[dim].typlen);
1214 /* just point into the array */
1216 dataptr +=
MAXALIGN(info[dim].typlen);
1219 else if (info[dim].typlen == -1)
1226 /* read the uint32 length */
1230 /* the length is data-only */
1235 /* just point into the array */
1238 /* skip to place of the next deserialized value */
1242 else if (info[dim].typlen == -2)
1252 memcpy(dataptr, ptr,
len);
1255 /* just point into the array */
1261 /* no under/overflow of input array */
1264 /* no overflow of the output mcv value */
1265 Assert(dataptr <= ((
char *) mcvlist + mcvlen));
1268 /* check we consumed input data for this dimension exactly */
1272 /* we should have also filled the MCV list exactly */
1273 Assert(dataptr == ((
char *) mcvlist + mcvlen));
1275 /* deserialize the MCV items and translate the indexes to Datums */
1283 item->
isnull = (
bool *) isnullptr;
1284 isnullptr +=
MAXALIGN(
sizeof(
bool) * ndims);
1286 memcpy(item->
isnull, ptr,
sizeof(
bool) * ndims);
1287 ptr +=
sizeof(bool) * ndims;
1289 memcpy(&item->
frequency, ptr,
sizeof(
double));
1290 ptr +=
sizeof(double);
1293 ptr +=
sizeof(double);
1295 /* finally translate the indexes (for non-NULL only) */
1296 for (dim = 0; dim < ndims; dim++)
1309 /* check we're not overflowing the input */
1313 /* check that we processed all the data */
1316 /* release the buffers used for mapping */
1317 for (dim = 0; dim < ndims; dim++)
1326 * SRF with details about buckets of a histogram:
1328 * - item ID (0...nitems)
1329 * - values (string array)
1330 * - nulls only (boolean array)
1331 * - frequency (double precision)
1332 * - base_frequency (double precision)
1334 * The input is the OID of the statistics, and there are no rows returned if
1335 * the statistics contains no histogram.
1342 /* stuff done only on the first call of the function */
1349 /* create a function context for cross-call persistence */
1352 /* switch to memory context appropriate for multiple function calls */
1359 /* total number of tuples to be returned */
1364 /* Build a tuple descriptor for our result type */
1367 (
errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1368 errmsg(
"function returning record called in context "
1369 "that cannot accept type record")));
1373 * generate attribute metadata needed later to produce tuples from raw
1381 /* stuff done on every call of the function */
1421 /* lookup output func for the type */
1448 /* no NULLs in the tuple */
1449 memset(nulls, 0,
sizeof(nulls));
1454 /* make the tuple into a datum */
1459 else /* do when there is no more left */
1466 * pg_mcv_list_in - input routine for type pg_mcv_list.
1468 * pg_mcv_list is real enough to be a table column, but it has no operations
1469 * of its own, and disallows input too
1475 * pg_mcv_list stores the data in binary form and parsing text input is
1476 * not needed, so disallow this.
1479 (
errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1480 errmsg(
"cannot accept a value of type %s",
"pg_mcv_list")));
1487 * pg_mcv_list_out - output routine for type pg_mcv_list.
1489 * MCV lists are serialized into a bytea value, so we simply call byteaout()
1490 * to serialize the value into text. But it'd be nice to serialize that into
1491 * a meaningful representation (e.g. for inspection by people).
1493 * XXX This should probably return something meaningful, similar to what
1494 * pg_dependencies_out does. Not sure how to deal with the deduplicated
1495 * values, though - do we want to expand that or not?
1504 * pg_mcv_list_recv - binary input routine for type pg_mcv_list.
1510 (
errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1511 errmsg(
"cannot accept a value of type %s",
"pg_mcv_list")));
1517 * pg_mcv_list_send - binary output routine for type pg_mcv_list.
1519 * MCV lists are serialized in a bytea value (although the type is named
1520 * differently), so let's just send that.
1529 * match the attribute/expression to a dimension of the statistic
1531 * Returns the zero-based index of the matching statistics dimension.
1532 * Optionally determines the collation.
1541 /* simple Var, so just lookup using varattno */
1545 *
collid = var->varcollid;
1550 elog(
ERROR,
"variable not found in statistics object");
1554 /* expression - lookup in stats expressions */
1560 /* expressions are stored after the simple columns */
1566 if (
equal(expr, stat_expr))
1573 elog(
ERROR,
"expression not found in statistics object");
1580 * mcv_get_match_bitmap
1581 * Evaluate clauses using the MCV list, and update the match bitmap.
1583 * A match bitmap keeps match/mismatch status for each MCV item, and we
1584 * update it based on additional clauses. We also use it to skip items
1585 * that can't possibly match (e.g. item marked as "mismatch" can't change
1586 * to "match" when evaluating AND clause list).
1588 * The function also returns a flag indicating whether there was an
1589 * equality condition for all attributes, the minimum frequency in the MCV
1590 * list, and a total MCV frequency (sum of frequencies for all items).
1592 * XXX Currently the match bitmap uses a bool for each MCV item, which is
1593 * somewhat wasteful as we could do with just a single bit, thus reducing
1594 * the size to ~1/8. It would also allow us to combine bitmaps simply using
1595 * & and |, which should be faster than min/max. The bitmaps are fairly
1596 * small, though (thanks to the cap on the MCV list size).
1606 /* The bitmap may be partially built. */
1613 memset(matches, !is_or,
sizeof(
bool) * mcvlist->
nitems);
1616 * Loop through the list of clauses, and for each of them evaluate all the
1617 * MCV items not yet eliminated by the preceding clauses.
1623 /* if it's a RestrictInfo, then extract the clause */
1628 * Handle the various types of clauses - OpClause, NullTest and
1636 /* valid only after examine_opclause_args returns true */
1645 /* extract the var/expr and const from the expression */
1649 /* match the attribute/expression to a dimension of the statistic */
1653 * Walk through the MCV items and evaluate the current clause. We
1654 * can skip items that were already ruled out, and terminate if
1655 * there are no remaining MCV items that might possibly match.
1657 for (
int i = 0;
i < mcvlist->
nitems;
i++)
1665 * When the MCV item or the Const value is NULL we can treat
1666 * this as a mismatch. We must not call the operator because
1669 if (item->
isnull[
idx] || cst->constisnull)
1676 * Skip MCV items that can't change result in the bitmap. Once
1677 * the value gets false for AND-lists, or true for OR-lists,
1678 * we don't need to look at more clauses.
1684 * First check whether the constant is below the lower
1685 * boundary (in that case we can skip the bucket, because
1686 * there's no overlap).
1688 * We don't store collations used to build the statistics, but
1689 * we can use the collation for the attribute itself, as
1690 * stored in varcollid. We do reset the statistics after a
1691 * type change (including collation change), so this is OK.
1692 * For expressions, we use the collation extracted from the
1693 * expression itself.
1706 /* update the match bitmap with the result */
1715 /* valid only after examine_opclause_args returns true */
1722 /* array evaluation */
1733 /* extract the var/expr and const from the expression */
1737 /* We expect Var on left */
1742 * Deconstruct the array constant, unless it's NULL (we'll cover
1745 if (!cst->constisnull)
1749 &elmlen, &elmbyval, &elmalign);
1752 elmlen, elmbyval, elmalign,
1753 &elem_values, &elem_nulls, &num_elems);
1756 /* match the attribute/expression to a dimension of the statistic */
1760 * Walk through the MCV items and evaluate the current clause. We
1761 * can skip items that were already ruled out, and terminate if
1762 * there are no remaining MCV items that might possibly match.
1764 for (
int i = 0;
i < mcvlist->
nitems;
i++)
1767 bool match = !expr->
useOr;
1771 * When the MCV item or the Const value is NULL we can treat
1772 * this as a mismatch. We must not call the operator because
1775 if (item->
isnull[
idx] || cst->constisnull)
1782 * Skip MCV items that can't change result in the bitmap. Once
1783 * the value gets false for AND-lists, or true for OR-lists,
1784 * we don't need to look at more clauses.
1789 for (
j = 0;
j < num_elems;
j++)
1791 Datum elem_value = elem_values[
j];
1792 bool elem_isnull = elem_nulls[
j];
1795 /* NULL values always evaluate as not matching. */
1803 * Stop evaluating the array elements once we reach a
1804 * matching value that can't change - ALL() is the same as
1805 * AND-list, ANY() is the same as OR-list.
1818 /* update the match bitmap with the result */
1827 /* match the attribute/expression to a dimension of the statistic */
1831 * Walk through the MCV items and evaluate the current clause. We
1832 * can skip items that were already ruled out, and terminate if
1833 * there are no remaining MCV items that might possibly match.
1835 for (
int i = 0;
i < mcvlist->
nitems;
i++)
1837 bool match =
false;
/* assume mismatch */
1840 /* if the clause mismatches the MCV item, update the bitmap */
1844 match = (item->
isnull[
idx]) ?
true : match;
1848 match = (!item->
isnull[
idx]) ?
true : match;
1852 /* now, update the match bitmap, depending on OR/AND type */
1858 /* AND/OR clause, with all subclauses being compatible */
1862 List *bool_clauses = bool_clause->
args;
1864 /* match/mismatch bitmap for each MCV item */
1865 bool *bool_matches = NULL;
1870 /* build the match bitmap for the OR-clauses */
1875 * Merge the bitmap produced by mcv_get_match_bitmap into the
1876 * current one. We need to consider if we're evaluating AND or OR
1877 * condition when merging the results.
1882 pfree(bool_matches);
1886 /* NOT clause, with all subclauses compatible */
1892 /* match/mismatch bitmap for each MCV item */
1893 bool *not_matches = NULL;
1898 /* build the match bitmap for the NOT-clause */
1903 * Merge the bitmap produced by mcv_get_match_bitmap into the
1904 * current one. We're handling a NOT clause, so invert the result
1905 * before merging it into the global bitmap.
1912 else if (
IsA(clause,
Var))
1914 /* Var (has to be a boolean Var, possibly from below NOT) */
1916 Var *var = (
Var *) (clause);
1918 /* match the attribute to a dimension of the statistic */
1921 Assert(var->vartype == BOOLOID);
1924 * Walk through the MCV items and evaluate the current clause. We
1925 * can skip items that were already ruled out, and terminate if
1926 * there are no remaining MCV items that might possibly match.
1928 for (
int i = 0;
i < mcvlist->
nitems;
i++)
1933 /* if the item is NULL, it's a mismatch */
1937 /* update the result bitmap */
1943 /* Otherwise, it must be a bare boolean-returning expression */
1946 /* match the expression to a dimension of the statistic */
1950 * Walk through the MCV items and evaluate the current clause. We
1951 * can skip items that were already ruled out, and terminate if
1952 * there are no remaining MCV items that might possibly match.
1954 for (
int i = 0;
i < mcvlist->
nitems;
i++)
1959 /* "match" just means it's bool TRUE */
1962 /* now, update the match bitmap, depending on OR/AND type */
1973 * mcv_combine_selectivities
1974 * Combine per-column and multi-column MCV selectivity estimates.
1976 * simple_sel is a "simple" selectivity estimate (produced without using any
1977 * extended statistics, essentially assuming independence of columns/clauses).
1979 * mcv_sel and mcv_basesel are sums of the frequencies and base frequencies of
1980 * all matching MCV items. The difference (mcv_sel - mcv_basesel) is then
1981 * essentially interpreted as a correction to be added to simple_sel, as
1984 * mcv_totalsel is the sum of the frequencies of all MCV items (not just the
1985 * matching ones). This is used as an upper bound on the portion of the
1986 * selectivity estimates not covered by the MCV statistics.
1988 * Note: While simple and base selectivities are defined in a quite similar
1989 * way, the values are computed differently and are not therefore equal. The
1990 * simple selectivity is computed as a product of per-clause estimates, while
1991 * the base selectivity is computed by adding up base frequencies of matching
1992 * items of the multi-column MCV list. So the values may differ for two main
1993 * reasons - (a) the MCV list may not cover 100% of the data and (b) some of
1994 * the MCV items did not match the estimated clauses.
1996 * As both (a) and (b) reduce the base selectivity value, it generally holds
1997 * that (simple_sel >= mcv_basesel). If the MCV list covers all the data, the
1998 * values may be equal.
2000 * So, other_sel = (simple_sel - mcv_basesel) is an estimate for the part not
2001 * covered by the MCV list, and (mcv_sel - mcv_basesel) may be seen as a
2002 * correction for the part covered by the MCV list. Those two statements are
2003 * actually equivalent.
2014 /* estimated selectivity of values not covered by MCV matches */
2015 other_sel = simple_sel - mcv_basesel;
2018 /* this non-MCV selectivity cannot exceed 1 - mcv_totalsel */
2019 if (other_sel > 1.0 - mcv_totalsel)
2020 other_sel = 1.0 - mcv_totalsel;
2022 /* overall selectivity is the sum of the MCV and non-MCV parts */
2023 sel = mcv_sel + other_sel;
2031 * mcv_clauselist_selectivity
2032 * Use MCV statistics to estimate the selectivity of an implicitly-ANDed
2035 * This determines which MCV items match every clause in the list and returns
2036 * the sum of the frequencies of those items.
2038 * In addition, it returns the sum of the base frequencies of each of those
2039 * items (that is the sum of the selectivities that each item would have if
2040 * the columns were independent of one another), and the total selectivity of
2041 * all the MCV items (not just the matching ones). These are expected to be
2042 * used together with a "simple" selectivity estimate (one based only on
2043 * per-column statistics) to produce an overall selectivity estimate that
2044 * makes use of both per-column and multi-column statistics --- see
2045 * mcv_combine_selectivities().
2049 List *clauses,
int varRelid,
2059 /* match/mismatch bitmap for each MCV item */
2060 bool *matches = NULL;
2062 /* load the MCV list stored in the statistics object */
2065 /* build a match bitmap for the clauses */
2069 /* sum frequencies for all the matching MCV items */
2076 if (matches[
i] !=
false)
2088 * mcv_clause_selectivity_or
2089 * Use MCV statistics to estimate the selectivity of a clause that
2090 * appears in an ORed list of clauses.
2092 * As with mcv_clauselist_selectivity() this determines which MCV items match
2093 * the clause and returns both the sum of the frequencies and the sum of the
2094 * base frequencies of those items, as well as the sum of the frequencies of
2095 * all MCV items (not just the matching ones) so that this information can be
2096 * used by mcv_combine_selectivities() to produce a selectivity estimate that
2097 * makes use of both per-column and multi-column statistics.
2099 * Additionally, we return information to help compute the overall selectivity
2100 * of the ORed list of clauses assumed to contain this clause. This function
2101 * is intended to be called for each clause in the ORed list of clauses,
2102 * allowing the overall selectivity to be computed using the following
2105 * Suppose P[n] = P(C[1] OR C[2] OR ... OR C[n]) is the combined selectivity
2106 * of the first n clauses in the list. Then the combined selectivity taking
2107 * into account the next clause C[n+1] can be written as
2109 * P[n+1] = P[n] + P(C[n+1]) - P((C[1] OR ... OR C[n]) AND C[n+1])
2111 * The final term above represents the overlap between the clauses examined so
2112 * far and the (n+1)'th clause. To estimate its selectivity, we track the
2113 * match bitmap for the ORed list of clauses examined so far and examine its
2114 * intersection with the match bitmap for the (n+1)'th clause.
2116 * We then also return the sums of the MCV item frequencies and base
2117 * frequencies for the match bitmap intersection corresponding to the overlap
2118 * term above, so that they can be combined with a simple selectivity estimate
2121 * The parameter "or_matches" is an in/out parameter tracking the match bitmap
2122 * for the clauses examined so far. The caller is expected to set it to NULL
2123 * the first time it calls this function.
2135 /* build the OR-matches bitmap, if not built already */
2136 if (*or_matches == NULL)
2139 /* build the match bitmap for the new clause */
2141 stat->exprs, mcv,
false);
2144 * Sum the frequencies for all the MCV items matching this clause and also
2145 * those matching the overlap between this clause and any of the preceding
2146 * clauses as described above.
2149 *overlap_mcvsel = 0.0;
2150 *overlap_basesel = 0.0;
2161 if ((*or_matches)[
i])
2168 /* update the OR-matches bitmap for the next clause */
2169 (*or_matches)[
i] = (*or_matches)[
i] || new_matches[
i];
Datum idx(PG_FUNCTION_ARGS)
#define DatumGetArrayTypeP(X)
ArrayBuildState * accumArrayResult(ArrayBuildState *astate, Datum dvalue, bool disnull, Oid element_type, MemoryContext rcontext)
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Datum makeArrayResult(ArrayBuildState *astate, MemoryContext rcontext)
int bms_num_members(const Bitmapset *a)
int bms_member_index(Bitmapset *a, int x)
static Datum values[MAXATTR]
Datum byteaout(PG_FUNCTION_ARGS)
Datum byteasend(PG_FUNCTION_ARGS)
#define PG_USED_FOR_ASSERTS_ONLY
int errcode(int sqlerrcode)
int errmsg(const char *fmt,...)
#define ereport(elevel,...)
bool equal(const void *a, const void *b)
TupleDesc BlessTupleDesc(TupleDesc tupdesc)
AttInMetadata * TupleDescGetAttInMetadata(TupleDesc tupdesc)
int compare_scalars_simple(const void *a, const void *b, void *arg)
int compare_datums_simple(Datum a, Datum b, SortSupport ssup)
SortItem * build_sorted_items(StatsBuildData *data, int *nitems, MultiSortSupport mss, int numattrs, AttrNumber *attnums)
int multi_sort_compare(const void *a, const void *b, void *arg)
MultiSortSupport multi_sort_init(int ndims)
void multi_sort_add_dimension(MultiSortSupport mss, int sortdim, Oid oper, Oid collation)
bool examine_opclause_args(List *args, Node **exprp, Const **cstp, bool *expronleftp)
MultiSortSupportData * MultiSortSupport
struct DimensionInfo DimensionInfo
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
void fmgr_info(Oid functionId, FmgrInfo *finfo)
#define PG_DETOAST_DATUM(datum)
#define FunctionCall1(flinfo, arg1)
#define PG_GETARG_BYTEA_P(n)
#define DatumGetByteaP(X)
TypeFuncClass get_call_result_type(FunctionCallInfo fcinfo, Oid *resultTypeId, TupleDesc *resultTupleDesc)
#define SRF_IS_FIRSTCALL()
#define SRF_PERCALL_SETUP()
#define SRF_RETURN_NEXT(_funcctx, _result)
#define SRF_FIRSTCALL_INIT()
static Datum HeapTupleGetDatum(const HeapTupleData *tuple)
#define SRF_RETURN_DONE(_funcctx)
Assert(PointerIsAligned(start, uint64))
HeapTuple heap_form_tuple(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull)
#define HeapTupleIsValid(tuple)
void getTypeOutputInfo(Oid type, Oid *typOutput, bool *typIsVarlena)
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
RegProcedure get_opcode(Oid opno)
Datum pg_stats_ext_mcvlist_items(PG_FUNCTION_ARGS)
Datum pg_mcv_list_in(PG_FUNCTION_ARGS)
MCVList * statext_mcv_deserialize(bytea *data)
Selectivity mcv_clauselist_selectivity(PlannerInfo *root, StatisticExtInfo *stat, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, RelOptInfo *rel, Selectivity *basesel, Selectivity *totalsel)
static MultiSortSupport build_mss(StatsBuildData *data)
static int compare_sort_item_count(const void *a, const void *b, void *arg)
MCVList * statext_mcv_load(Oid mvoid, bool inh)
Datum pg_mcv_list_out(PG_FUNCTION_ARGS)
static int count_distinct_groups(int numrows, SortItem *items, MultiSortSupport mss)
Datum pg_mcv_list_send(PG_FUNCTION_ARGS)
#define SizeOfMCVList(ndims, nitems)
static bool * mcv_get_match_bitmap(PlannerInfo *root, List *clauses, Bitmapset *keys, List *exprs, MCVList *mcvlist, bool is_or)
#define RESULT_MERGE(value, is_or, match)
static double get_mincount_for_mcv_list(int samplerows, double totalrows)
Selectivity mcv_combine_selectivities(Selectivity simple_sel, Selectivity mcv_sel, Selectivity mcv_basesel, Selectivity mcv_totalsel)
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)
#define RESULT_IS_FINAL(value, is_or)
static int mcv_match_expression(Node *expr, Bitmapset *keys, List *exprs, Oid *collid)
MCVList * statext_mcv_build(StatsBuildData *data, double totalrows, int stattarget)
Datum pg_mcv_list_recv(PG_FUNCTION_ARGS)
static int sort_item_compare(const void *a, const void *b, void *arg)
static SortItem ** build_column_frequencies(SortItem *groups, int ngroups, MultiSortSupport mss, int *ncounts)
bytea * statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
static SortItem * build_distinct_groups(int numrows, SortItem *items, MultiSortSupport mss, int *ndistinct)
void * repalloc(void *pointer, Size size)
void pfree(void *pointer)
void * palloc0(Size size)
MemoryContext CurrentMemoryContext
Oid exprCollation(const Node *expr)
static bool is_andclause(const void *clause)
static bool is_orclause(const void *clause)
static bool is_opclause(const void *clause)
static bool is_notclause(const void *clause)
#define IsA(nodeptr, _type_)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
static int list_length(const List *l)
void * bsearch_arg(const void *key, const void *base0, size_t nmemb, size_t size, int(*compar)(const void *, const void *, void *), void *arg)
void qsort_interruptible(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
static bool DatumGetBool(Datum X)
static Datum PointerGetDatum(const void *X)
static Datum BoolGetDatum(bool X)
static Datum ObjectIdGetDatum(Oid X)
static char * DatumGetCString(Datum X)
static Pointer DatumGetPointer(Datum X)
static Datum Float8GetDatum(float8 X)
static Datum Int32GetDatum(int32 X)
#define CLAMP_PROBABILITY(p)
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
struct SortSupportData SortSupportData
struct SortSupportData * SortSupport
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
#define STATS_MCV_TYPE_BASIC
#define STATS_MCVLIST_MAX_ITEMS
#define STATS_MAX_DIMENSIONS
AttInMetadata * attinmeta
MemoryContext multi_call_memory_ctx
MCVItem items[FLEXIBLE_ARRAY_MEMBER]
Oid types[STATS_MAX_DIMENSIONS]
SortSupportData ssup[FLEXIBLE_ARRAY_MEMBER]
NullTestType nulltesttype
void ReleaseSysCache(HeapTuple tuple)
Datum SysCacheGetAttr(int cacheId, HeapTuple tup, AttrNumber attributeNumber, bool *isNull)
HeapTuple SearchSysCache2(int cacheId, Datum key1, Datum key2)
static Datum fetch_att(const void *T, bool attbyval, int attlen)
static void store_att_byval(void *T, Datum newdatum, int attlen)
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
static Size VARSIZE_ANY(const void *PTR)
static Size VARSIZE_ANY_EXHDR(const void *PTR)
static char * VARDATA(const void *PTR)
static char * VARDATA_ANY(const void *PTR)
static void SET_VARSIZE(void *PTR, Size len)
text * cstring_to_text(const char *s)