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