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