PostgreSQL Source Code: src/backend/statistics/mvdistinct.c Source File

PostgreSQL Source Code git master
mvdistinct.c
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * mvdistinct.c
4 * POSTGRES multivariate ndistinct coefficients
5 *
6 * Estimating number of groups in a combination of columns (e.g. for GROUP BY)
7 * is tricky, and the estimation error is often significant.
8
9 * The multivariate ndistinct coefficients address this by storing ndistinct
10 * estimates for combinations of the user-specified columns. So for example
11 * given a statistics object on three columns (a,b,c), this module estimates
12 * and stores n-distinct for (a,b), (a,c), (b,c) and (a,b,c). The per-column
13 * estimates are already available in pg_statistic.
14 *
15 *
16 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
17 * Portions Copyright (c) 1994, Regents of the University of California
18 *
19 * IDENTIFICATION
20 * src/backend/statistics/mvdistinct.c
21 *
22 *-------------------------------------------------------------------------
23 */
24#include "postgres.h"
25
26#include <math.h>
27
28#include "catalog/pg_statistic_ext.h"
29#include "catalog/pg_statistic_ext_data.h"
30#include "lib/stringinfo.h"
31#include "statistics/extended_stats_internal.h"
32#include "statistics/statistics.h"
33#include "utils/fmgrprotos.h"
34#include "utils/syscache.h"
35#include "utils/typcache.h"
36#include "varatt.h"
37
38static double ndistinct_for_combination(double totalrows, StatsBuildData *data,
39 int k, int *combination);
40static double estimate_ndistinct(double totalrows, int numrows, int d, int f1);
41static int n_choose_k(int n, int k);
42static int num_combinations(int n);
43
44/* size of the struct header fields (magic, type, nitems) */
45 #define SizeOfHeader (3 * sizeof(uint32))
46
47/* size of a serialized ndistinct item (coefficient, natts, atts) */
48 #define SizeOfItem(natts) \
49 (sizeof(double) + sizeof(int) + (natts) * sizeof(AttrNumber))
50
51/* minimal size of a ndistinct item (with two attributes) */
52 #define MinSizeOfItem SizeOfItem(2)
53
54/* minimal size of mvndistinct, when all items are minimal */
55 #define MinSizeOfItems(nitems) \
56 (SizeOfHeader + (nitems) * MinSizeOfItem)
57
58/* Combination generator API */
59
60/* internal state for generator of k-combinations of n elements */
61 typedef struct CombinationGenerator
62{
63 int k; /* size of the combination */
64 int n; /* total number of elements */
65 int current; /* index of the next combination to return */
66 int ncombinations; /* number of combinations (size of array) */
67 int *combinations; /* array of pre-built combinations */
68 } CombinationGenerator;
69
70static CombinationGenerator *generator_init(int n, int k);
71static void generator_free(CombinationGenerator *state);
72static int *generator_next(CombinationGenerator *state);
73static void generate_combinations(CombinationGenerator *state);
74
75
76/*
77 * statext_ndistinct_build
78 * Compute ndistinct coefficient for the combination of attributes.
79 *
80 * This computes the ndistinct estimate using the same estimator used
81 * in analyze.c and then computes the coefficient.
82 *
83 * To handle expressions easily, we treat them as system attributes with
84 * negative attnums, and offset everything by number of expressions to
85 * allow using Bitmapsets.
86 */
87MVNDistinct *
88 statext_ndistinct_build(double totalrows, StatsBuildData *data)
89{
90 MVNDistinct *result;
91 int k;
92 int itemcnt;
93 int numattrs = data->nattnums;
94 int numcombs = num_combinations(numattrs);
95
96 result = palloc(offsetof(MVNDistinct, items) +
97 numcombs * sizeof(MVNDistinctItem));
98 result->magic = STATS_NDISTINCT_MAGIC;
99 result->type = STATS_NDISTINCT_TYPE_BASIC;
100 result->nitems = numcombs;
101
102 itemcnt = 0;
103 for (k = 2; k <= numattrs; k++)
104 {
105 int *combination;
106 CombinationGenerator *generator;
107
108 /* generate combinations of K out of N elements */
109 generator = generator_init(numattrs, k);
110
111 while ((combination = generator_next(generator)))
112 {
113 MVNDistinctItem *item = &result->items[itemcnt];
114 int j;
115
116 item->attributes = palloc(sizeof(AttrNumber) * k);
117 item->nattributes = k;
118
119 /* translate the indexes to attnums */
120 for (j = 0; j < k; j++)
121 {
122 item->attributes[j] = data->attnums[combination[j]];
123
124 Assert(AttributeNumberIsValid(item->attributes[j]));
125 }
126
127 item->ndistinct =
128 ndistinct_for_combination(totalrows, data, k, combination);
129
130 itemcnt++;
131 Assert(itemcnt <= result->nitems);
132 }
133
134 generator_free(generator);
135 }
136
137 /* must consume exactly the whole output array */
138 Assert(itemcnt == result->nitems);
139
140 return result;
141}
142
143/*
144 * statext_ndistinct_load
145 * Load the ndistinct value for the indicated pg_statistic_ext tuple
146 */
147MVNDistinct *
148 statext_ndistinct_load(Oid mvoid, bool inh)
149{
150 MVNDistinct *result;
151 bool isnull;
152 Datum ndist;
153 HeapTuple htup;
154
155 htup = SearchSysCache2(STATEXTDATASTXOID,
156 ObjectIdGetDatum(mvoid), BoolGetDatum(inh));
157 if (!HeapTupleIsValid(htup))
158 elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
159
160 ndist = SysCacheGetAttr(STATEXTDATASTXOID, htup,
161 Anum_pg_statistic_ext_data_stxdndistinct, &isnull);
162 if (isnull)
163 elog(ERROR,
164 "requested statistics kind \"%c\" is not yet built for statistics object %u",
165 STATS_EXT_NDISTINCT, mvoid);
166
167 result = statext_ndistinct_deserialize(DatumGetByteaPP(ndist));
168
169 ReleaseSysCache(htup);
170
171 return result;
172}
173
174/*
175 * statext_ndistinct_serialize
176 * serialize ndistinct to the on-disk bytea format
177 */
178bytea *
179 statext_ndistinct_serialize(MVNDistinct *ndistinct)
180{
181 int i;
182 bytea *output;
183 char *tmp;
184 Size len;
185
186 Assert(ndistinct->magic == STATS_NDISTINCT_MAGIC);
187 Assert(ndistinct->type == STATS_NDISTINCT_TYPE_BASIC);
188
189 /*
190 * Base size is size of scalar fields in the struct, plus one base struct
191 * for each item, including number of items for each.
192 */
193 len = VARHDRSZ + SizeOfHeader;
194
195 /* and also include space for the actual attribute numbers */
196 for (i = 0; i < ndistinct->nitems; i++)
197 {
198 int nmembers;
199
200 nmembers = ndistinct->items[i].nattributes;
201 Assert(nmembers >= 2);
202
203 len += SizeOfItem(nmembers);
204 }
205
206 output = (bytea *) palloc(len);
207 SET_VARSIZE(output, len);
208
209 tmp = VARDATA(output);
210
211 /* Store the base struct values (magic, type, nitems) */
212 memcpy(tmp, &ndistinct->magic, sizeof(uint32));
213 tmp += sizeof(uint32);
214 memcpy(tmp, &ndistinct->type, sizeof(uint32));
215 tmp += sizeof(uint32);
216 memcpy(tmp, &ndistinct->nitems, sizeof(uint32));
217 tmp += sizeof(uint32);
218
219 /*
220 * store number of attributes and attribute numbers for each entry
221 */
222 for (i = 0; i < ndistinct->nitems; i++)
223 {
224 MVNDistinctItem item = ndistinct->items[i];
225 int nmembers = item.nattributes;
226
227 memcpy(tmp, &item.ndistinct, sizeof(double));
228 tmp += sizeof(double);
229 memcpy(tmp, &nmembers, sizeof(int));
230 tmp += sizeof(int);
231
232 memcpy(tmp, item.attributes, sizeof(AttrNumber) * nmembers);
233 tmp += nmembers * sizeof(AttrNumber);
234
235 /* protect against overflows */
236 Assert(tmp <= ((char *) output + len));
237 }
238
239 /* check we used exactly the expected space */
240 Assert(tmp == ((char *) output + len));
241
242 return output;
243}
244
245/*
246 * statext_ndistinct_deserialize
247 * Read an on-disk bytea format MVNDistinct to in-memory format
248 */
249MVNDistinct *
250 statext_ndistinct_deserialize(bytea *data)
251{
252 int i;
253 Size minimum_size;
254 MVNDistinct ndist;
255 MVNDistinct *ndistinct;
256 char *tmp;
257
258 if (data == NULL)
259 return NULL;
260
261 /* we expect at least the basic fields of MVNDistinct struct */
262 if (VARSIZE_ANY_EXHDR(data) < SizeOfHeader)
263 elog(ERROR, "invalid MVNDistinct size %zu (expected at least %zu)",
264 VARSIZE_ANY_EXHDR(data), SizeOfHeader);
265
266 /* initialize pointer to the data part (skip the varlena header) */
267 tmp = VARDATA_ANY(data);
268
269 /* read the header fields and perform basic sanity checks */
270 memcpy(&ndist.magic, tmp, sizeof(uint32));
271 tmp += sizeof(uint32);
272 memcpy(&ndist.type, tmp, sizeof(uint32));
273 tmp += sizeof(uint32);
274 memcpy(&ndist.nitems, tmp, sizeof(uint32));
275 tmp += sizeof(uint32);
276
277 if (ndist.magic != STATS_NDISTINCT_MAGIC)
278 elog(ERROR, "invalid ndistinct magic %08x (expected %08x)",
279 ndist.magic, STATS_NDISTINCT_MAGIC);
280 if (ndist.type != STATS_NDISTINCT_TYPE_BASIC)
281 elog(ERROR, "invalid ndistinct type %d (expected %d)",
282 ndist.type, STATS_NDISTINCT_TYPE_BASIC);
283 if (ndist.nitems == 0)
284 elog(ERROR, "invalid zero-length item array in MVNDistinct");
285
286 /* what minimum bytea size do we expect for those parameters */
287 minimum_size = MinSizeOfItems(ndist.nitems);
288 if (VARSIZE_ANY_EXHDR(data) < minimum_size)
289 elog(ERROR, "invalid MVNDistinct size %zu (expected at least %zu)",
290 VARSIZE_ANY_EXHDR(data), minimum_size);
291
292 /*
293 * Allocate space for the ndistinct items (no space for each item's
294 * attnos: those live in bitmapsets allocated separately)
295 */
296 ndistinct = palloc0(MAXALIGN(offsetof(MVNDistinct, items)) +
297 (ndist.nitems * sizeof(MVNDistinctItem)));
298 ndistinct->magic = ndist.magic;
299 ndistinct->type = ndist.type;
300 ndistinct->nitems = ndist.nitems;
301
302 for (i = 0; i < ndistinct->nitems; i++)
303 {
304 MVNDistinctItem *item = &ndistinct->items[i];
305
306 /* ndistinct value */
307 memcpy(&item->ndistinct, tmp, sizeof(double));
308 tmp += sizeof(double);
309
310 /* number of attributes */
311 memcpy(&item->nattributes, tmp, sizeof(int));
312 tmp += sizeof(int);
313 Assert((item->nattributes >= 2) && (item->nattributes <= STATS_MAX_DIMENSIONS));
314
315 item->attributes
316 = (AttrNumber *) palloc(item->nattributes * sizeof(AttrNumber));
317
318 memcpy(item->attributes, tmp, sizeof(AttrNumber) * item->nattributes);
319 tmp += sizeof(AttrNumber) * item->nattributes;
320
321 /* still within the bytea */
322 Assert(tmp <= ((char *) data + VARSIZE_ANY(data)));
323 }
324
325 /* we should have consumed the whole bytea exactly */
326 Assert(tmp == ((char *) data + VARSIZE_ANY(data)));
327
328 return ndistinct;
329}
330
331/*
332 * pg_ndistinct_in
333 * input routine for type pg_ndistinct
334 *
335 * pg_ndistinct is real enough to be a table column, but it has no
336 * operations of its own, and disallows input (just like pg_node_tree).
337 */
338Datum
339 pg_ndistinct_in(PG_FUNCTION_ARGS)
340{
341 ereport(ERROR,
342 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
343 errmsg("cannot accept a value of type %s", "pg_ndistinct")));
344
345 PG_RETURN_VOID(); /* keep compiler quiet */
346}
347
348/*
349 * pg_ndistinct
350 * output routine for type pg_ndistinct
351 *
352 * Produces a human-readable representation of the value.
353 */
354Datum
355 pg_ndistinct_out(PG_FUNCTION_ARGS)
356{
357 bytea *data = PG_GETARG_BYTEA_PP(0);
358 MVNDistinct *ndist = statext_ndistinct_deserialize(data);
359 int i;
360 StringInfoData str;
361
362 initStringInfo(&str);
363 appendStringInfoChar(&str, '{');
364
365 for (i = 0; i < ndist->nitems; i++)
366 {
367 int j;
368 MVNDistinctItem item = ndist->items[i];
369
370 if (i > 0)
371 appendStringInfoString(&str, ", ");
372
373 for (j = 0; j < item.nattributes; j++)
374 {
375 AttrNumber attnum = item.attributes[j];
376
377 appendStringInfo(&str, "%s%d", (j == 0) ? "\"" : ", ", attnum);
378 }
379 appendStringInfo(&str, "\": %d", (int) item.ndistinct);
380 }
381
382 appendStringInfoChar(&str, '}');
383
384 PG_RETURN_CSTRING(str.data);
385}
386
387/*
388 * pg_ndistinct_recv
389 * binary input routine for type pg_ndistinct
390 */
391Datum
392 pg_ndistinct_recv(PG_FUNCTION_ARGS)
393{
394 ereport(ERROR,
395 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
396 errmsg("cannot accept a value of type %s", "pg_ndistinct")));
397
398 PG_RETURN_VOID(); /* keep compiler quiet */
399}
400
401/*
402 * pg_ndistinct_send
403 * binary output routine for type pg_ndistinct
404 *
405 * n-distinct is serialized into a bytea value, so let's send that.
406 */
407Datum
408 pg_ndistinct_send(PG_FUNCTION_ARGS)
409{
410 return byteasend(fcinfo);
411}
412
413/*
414 * ndistinct_for_combination
415 * Estimates number of distinct values in a combination of columns.
416 *
417 * This uses the same ndistinct estimator as compute_scalar_stats() in
418 * ANALYZE, i.e.,
419 * n*d / (n - f1 + f1*n/N)
420 *
421 * except that instead of values in a single column we are dealing with
422 * combination of multiple columns.
423 */
424static double
425 ndistinct_for_combination(double totalrows, StatsBuildData *data,
426 int k, int *combination)
427{
428 int i,
429 j;
430 int f1,
431 cnt,
432 d;
433 bool *isnull;
434 Datum *values;
435 SortItem *items;
436 MultiSortSupport mss;
437 int numrows = data->numrows;
438
439 mss = multi_sort_init(k);
440
441 /*
442 * In order to determine the number of distinct elements, create separate
443 * values[]/isnull[] arrays with all the data we have, then sort them
444 * using the specified column combination as dimensions. We could try to
445 * sort in place, but it'd probably be more complex and bug-prone.
446 */
447 items = (SortItem *) palloc(numrows * sizeof(SortItem));
448 values = (Datum *) palloc0(sizeof(Datum) * numrows * k);
449 isnull = (bool *) palloc0(sizeof(bool) * numrows * k);
450
451 for (i = 0; i < numrows; i++)
452 {
453 items[i].values = &values[i * k];
454 items[i].isnull = &isnull[i * k];
455 }
456
457 /*
458 * For each dimension, set up sort-support and fill in the values from the
459 * sample data.
460 *
461 * We use the column data types' default sort operators and collations;
462 * perhaps at some point it'd be worth using column-specific collations?
463 */
464 for (i = 0; i < k; i++)
465 {
466 Oid typid;
467 TypeCacheEntry *type;
468 Oid collid = InvalidOid;
469 VacAttrStats *colstat = data->stats[combination[i]];
470
471 typid = colstat->attrtypid;
472 collid = colstat->attrcollid;
473
474 type = lookup_type_cache(typid, TYPECACHE_LT_OPR);
475 if (type->lt_opr == InvalidOid) /* shouldn't happen */
476 elog(ERROR, "cache lookup failed for ordering operator for type %u",
477 typid);
478
479 /* prepare the sort function for this dimension */
480 multi_sort_add_dimension(mss, i, type->lt_opr, collid);
481
482 /* accumulate all the data for this dimension into the arrays */
483 for (j = 0; j < numrows; j++)
484 {
485 items[j].values[i] = data->values[combination[i]][j];
486 items[j].isnull[i] = data->nulls[combination[i]][j];
487 }
488 }
489
490 /* We can sort the array now ... */
491 qsort_interruptible(items, numrows, sizeof(SortItem),
492 multi_sort_compare, mss);
493
494 /* ... and count the number of distinct combinations */
495
496 f1 = 0;
497 cnt = 1;
498 d = 1;
499 for (i = 1; i < numrows; i++)
500 {
501 if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
502 {
503 if (cnt == 1)
504 f1 += 1;
505
506 d++;
507 cnt = 0;
508 }
509
510 cnt += 1;
511 }
512
513 if (cnt == 1)
514 f1 += 1;
515
516 return estimate_ndistinct(totalrows, numrows, d, f1);
517}
518
519/* The Duj1 estimator (already used in analyze.c). */
520static double
521 estimate_ndistinct(double totalrows, int numrows, int d, int f1)
522{
523 double numer,
524 denom,
525 ndistinct;
526
527 numer = (double) numrows * (double) d;
528
529 denom = (double) (numrows - f1) +
530 (double) f1 * (double) numrows / totalrows;
531
532 ndistinct = numer / denom;
533
534 /* Clamp to sane range in case of roundoff error */
535 if (ndistinct < (double) d)
536 ndistinct = (double) d;
537
538 if (ndistinct > totalrows)
539 ndistinct = totalrows;
540
541 return floor(ndistinct + 0.5);
542}
543
544/*
545 * n_choose_k
546 * computes binomial coefficients using an algorithm that is both
547 * efficient and prevents overflows
548 */
549static int
550 n_choose_k(int n, int k)
551{
552 int d,
553 r;
554
555 Assert((k > 0) && (n >= k));
556
557 /* use symmetry of the binomial coefficients */
558 k = Min(k, n - k);
559
560 r = 1;
561 for (d = 1; d <= k; ++d)
562 {
563 r *= n--;
564 r /= d;
565 }
566
567 return r;
568}
569
570/*
571 * num_combinations
572 * number of combinations, excluding single-value combinations
573 */
574static int
575 num_combinations(int n)
576{
577 return (1 << n) - (n + 1);
578}
579
580/*
581 * generator_init
582 * initialize the generator of combinations
583 *
584 * The generator produces combinations of K elements in the interval (0..N).
585 * We prebuild all the combinations in this method, which is simpler than
586 * generating them on the fly.
587 */
588static CombinationGenerator *
589 generator_init(int n, int k)
590{
591 CombinationGenerator *state;
592
593 Assert((n >= k) && (k > 0));
594
595 /* allocate the generator state as a single chunk of memory */
596 state = (CombinationGenerator *) palloc(sizeof(CombinationGenerator));
597
598 state->ncombinations = n_choose_k(n, k);
599
600 /* pre-allocate space for all combinations */
601 state->combinations = (int *) palloc(sizeof(int) * k * state->ncombinations);
602
603 state->current = 0;
604 state->k = k;
605 state->n = n;
606
607 /* now actually pre-generate all the combinations of K elements */
608 generate_combinations(state);
609
610 /* make sure we got the expected number of combinations */
611 Assert(state->current == state->ncombinations);
612
613 /* reset the number, so we start with the first one */
614 state->current = 0;
615
616 return state;
617}
618
619/*
620 * generator_next
621 * returns the next combination from the prebuilt list
622 *
623 * Returns a combination of K array indexes (0 .. N), as specified to
624 * generator_init), or NULL when there are no more combination.
625 */
626static int *
627 generator_next(CombinationGenerator *state)
628{
629 if (state->current == state->ncombinations)
630 return NULL;
631
632 return &state->combinations[state->k * state->current++];
633}
634
635/*
636 * generator_free
637 * free the internal state of the generator
638 *
639 * Releases the generator internal state (pre-built combinations).
640 */
641static void
642 generator_free(CombinationGenerator *state)
643{
644 pfree(state->combinations);
645 pfree(state);
646}
647
648/*
649 * generate_combinations_recurse
650 * given a prefix, generate all possible combinations
651 *
652 * Given a prefix (first few elements of the combination), generate following
653 * elements recursively. We generate the combinations in lexicographic order,
654 * which eliminates permutations of the same combination.
655 */
656static void
657 generate_combinations_recurse(CombinationGenerator *state,
658 int index, int start, int *current)
659{
660 /* If we haven't filled all the elements, simply recurse. */
661 if (index < state->k)
662 {
663 int i;
664
665 /*
666 * The values have to be in ascending order, so make sure we start
667 * with the value passed by parameter.
668 */
669
670 for (i = start; i < state->n; i++)
671 {
672 current[index] = i;
673 generate_combinations_recurse(state, (index + 1), (i + 1), current);
674 }
675
676 return;
677 }
678 else
679 {
680 /* we got a valid combination, add it to the array */
681 memcpy(&state->combinations[(state->k * state->current)],
682 current, state->k * sizeof(int));
683 state->current++;
684 }
685}
686
687/*
688 * generate_combinations
689 * generate all k-combinations of N elements
690 */
691static void
692 generate_combinations(CombinationGenerator *state)
693{
694 int *current = (int *) palloc0(sizeof(int) * state->k);
695
696 generate_combinations_recurse(state, 0, 0, current);
697
698 pfree(current);
699}
int16 AttrNumber
Definition: attnum.h:21
#define AttributeNumberIsValid(attributeNumber)
Definition: attnum.h:34
static Datum values[MAXATTR]
Definition: bootstrap.c:153
Datum byteasend(PG_FUNCTION_ARGS)
Definition: bytea.c:363
#define Min(x, y)
Definition: c.h:1003
#define MAXALIGN(LEN)
Definition: c.h:810
#define VARHDRSZ
Definition: c.h:697
uint32_t uint32
Definition: c.h:538
size_t Size
Definition: c.h:610
Oid collid
Definition: collationcmds.c:700
int errcode(int sqlerrcode)
Definition: elog.c:854
int errmsg(const char *fmt,...)
Definition: elog.c:1071
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
#define ereport(elevel,...)
Definition: elog.h:150
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)
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_BYTEA_PP(n)
Definition: fmgr.h:308
#define DatumGetByteaPP(X)
Definition: fmgr.h:291
#define PG_RETURN_CSTRING(x)
Definition: fmgr.h:362
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
Assert(PointerIsAligned(start, uint64))
return str start
const char * str
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
#define nitems(x)
Definition: indent.h:31
FILE * output
j
int j
Definition: isn.c:78
i
int i
Definition: isn.c:77
void pfree(void *pointer)
Definition: mcxt.c:1594
void * palloc0(Size size)
Definition: mcxt.c:1395
void * palloc(Size size)
Definition: mcxt.c:1365
Datum pg_ndistinct_out(PG_FUNCTION_ARGS)
Definition: mvdistinct.c:355
static int n_choose_k(int n, int k)
Definition: mvdistinct.c:550
#define SizeOfHeader
Definition: mvdistinct.c:45
Datum pg_ndistinct_in(PG_FUNCTION_ARGS)
Definition: mvdistinct.c:339
struct CombinationGenerator CombinationGenerator
static double estimate_ndistinct(double totalrows, int numrows, int d, int f1)
Definition: mvdistinct.c:521
static void generate_combinations_recurse(CombinationGenerator *state, int index, int start, int *current)
Definition: mvdistinct.c:657
Datum pg_ndistinct_recv(PG_FUNCTION_ARGS)
Definition: mvdistinct.c:392
MVNDistinct * statext_ndistinct_deserialize(bytea *data)
Definition: mvdistinct.c:250
static double ndistinct_for_combination(double totalrows, StatsBuildData *data, int k, int *combination)
Definition: mvdistinct.c:425
bytea * statext_ndistinct_serialize(MVNDistinct *ndistinct)
Definition: mvdistinct.c:179
static void generate_combinations(CombinationGenerator *state)
Definition: mvdistinct.c:692
MVNDistinct * statext_ndistinct_load(Oid mvoid, bool inh)
Definition: mvdistinct.c:148
static int num_combinations(int n)
Definition: mvdistinct.c:575
MVNDistinct * statext_ndistinct_build(double totalrows, StatsBuildData *data)
Definition: mvdistinct.c:88
#define SizeOfItem(natts)
Definition: mvdistinct.c:48
static void generator_free(CombinationGenerator *state)
Definition: mvdistinct.c:642
static CombinationGenerator * generator_init(int n, int k)
Definition: mvdistinct.c:589
Datum pg_ndistinct_send(PG_FUNCTION_ARGS)
Definition: mvdistinct.c:408
#define MinSizeOfItems(nitems)
Definition: mvdistinct.c:55
static int * generator_next(CombinationGenerator *state)
Definition: mvdistinct.c:627
int16 attnum
Definition: pg_attribute.h:74
const void size_t len
const void * data
void qsort_interruptible(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
static Datum BoolGetDatum(bool X)
Definition: postgres.h:112
static Datum ObjectIdGetDatum(Oid X)
Definition: postgres.h:262
uint64_t Datum
Definition: postgres.h:70
#define InvalidOid
Definition: postgres_ext.h:37
unsigned int Oid
Definition: postgres_ext.h:32
int f1[ARRAY_SIZE]
Definition: sql-declare.c:113
#define STATS_NDISTINCT_MAGIC
Definition: statistics.h:22
#define STATS_NDISTINCT_TYPE_BASIC
Definition: statistics.h:23
#define STATS_MAX_DIMENSIONS
Definition: statistics.h:19
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:145
void appendStringInfoString(StringInfo str, const char *s)
Definition: stringinfo.c:230
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:242
void initStringInfo(StringInfo str)
Definition: stringinfo.c:97
int nattributes
Definition: statistics.h:29
double ndistinct
Definition: statistics.h:28
AttrNumber * attributes
Definition: statistics.h:30
uint32 nitems
Definition: statistics.h:38
uint32 type
Definition: statistics.h:37
uint32 magic
Definition: statistics.h:36
MVNDistinctItem items[FLEXIBLE_ARRAY_MEMBER]
Definition: statistics.h:39
Oid attrtypid
Definition: vacuum.h:126
Oid attrcollid
Definition: vacuum.h:129
Definition: type.h:96
Definition: regguts.h:323
Definition: c.h:692
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:264
Datum SysCacheGetAttr(int cacheId, HeapTuple tup, AttrNumber attributeNumber, bool *isNull)
Definition: syscache.c:595
HeapTuple SearchSysCache2(int cacheId, Datum key1, Datum key2)
Definition: syscache.c:230
static ItemArray items
Definition: test_tidstore.c:48
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:386
#define TYPECACHE_LT_OPR
Definition: typcache.h:139
static Size VARSIZE_ANY(const void *PTR)
Definition: varatt.h:460
static Size VARSIZE_ANY_EXHDR(const void *PTR)
Definition: varatt.h:472
static char * VARDATA(const void *PTR)
Definition: varatt.h:305
static char * VARDATA_ANY(const void *PTR)
Definition: varatt.h:486
static void SET_VARSIZE(void *PTR, Size len)
Definition: varatt.h:432
const char * type

AltStyle によって変換されたページ (->オリジナル) /