Age Owner Branch data TLA 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-2024, 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 : :
38 : : static double ndistinct_for_combination(double totalrows, StatsBuildData *data,
39 : : int k, int *combination);
40 : : static double estimate_ndistinct(double totalrows, int numrows, int d, int f1);
41 : : static int n_choose_k(int n, int k);
42 : : static 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 : :
70 : : static CombinationGenerator *generator_init(int n, int k);
71 : : static void generator_free(CombinationGenerator *state);
72 : : static int *generator_next(CombinationGenerator *state);
73 : : static 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 : : */
87 : : MVNDistinct *
1115 tomas.vondra@postgre 88 :CBC 78 : statext_ndistinct_build(double totalrows, StatsBuildData *data)
89 : : {
90 : : MVNDistinct *result;
91 : : int k;
92 : : int itemcnt;
93 : 78 : int numattrs = data->nattnums;
2578 alvherre@alvh.no-ip. 94 : 78 : int numcombs = num_combinations(numattrs);
95 : :
96 : 78 : result = palloc(offsetof(MVNDistinct, items) +
97 : 78 : numcombs * sizeof(MVNDistinctItem));
98 : 78 : result->magic = STATS_NDISTINCT_MAGIC;
99 : 78 : result->type = STATS_NDISTINCT_TYPE_BASIC;
100 : 78 : result->nitems = numcombs;
101 : :
102 : 78 : itemcnt = 0;
103 [ + + ]: 198 : for (k = 2; k <= numattrs; k++)
104 : : {
105 : : int *combination;
106 : : CombinationGenerator *generator;
107 : :
108 : : /* generate combinations of K out of N elements */
109 : 120 : generator = generator_init(numattrs, k);
110 : :
111 [ + + ]: 372 : while ((combination = generator_next(generator)))
112 : : {
113 : 252 : MVNDistinctItem *item = &result->items[itemcnt];
114 : : int j;
115 : :
1115 tomas.vondra@postgre 116 : 252 : item->attributes = palloc(sizeof(AttrNumber) * k);
117 : 252 : item->nattributes = k;
118 : :
119 : : /* translate the indexes to attnums */
2578 alvherre@alvh.no-ip. 120 [ + + ]: 846 : for (j = 0; j < k; j++)
121 : : {
1115 tomas.vondra@postgre 122 : 594 : item->attributes[j] = data->attnums[combination[j]];
123 : :
124 [ - + ]: 594 : Assert(AttributeNumberIsValid(item->attributes[j]));
125 : : }
126 : :
2578 alvherre@alvh.no-ip. 127 : 252 : item->ndistinct =
1115 tomas.vondra@postgre 128 : 252 : ndistinct_for_combination(totalrows, data, k, combination);
129 : :
2578 alvherre@alvh.no-ip. 130 : 252 : itemcnt++;
131 [ - + ]: 252 : Assert(itemcnt <= result->nitems);
132 : : }
133 : :
134 : 120 : generator_free(generator);
135 : : }
136 : :
137 : : /* must consume exactly the whole output array */
138 [ - + ]: 78 : Assert(itemcnt == result->nitems);
139 : :
140 : 78 : return result;
141 : : }
142 : :
143 : : /*
144 : : * statext_ndistinct_load
145 : : * Load the ndistinct value for the indicated pg_statistic_ext tuple
146 : : */
147 : : MVNDistinct *
819 tomas.vondra@postgre 148 : 201 : statext_ndistinct_load(Oid mvoid, bool inh)
149 : : {
150 : : MVNDistinct *result;
151 : : bool isnull;
152 : : Datum ndist;
153 : : HeapTuple htup;
154 : :
155 : 201 : htup = SearchSysCache2(STATEXTDATASTXOID,
156 : : ObjectIdGetDatum(mvoid), BoolGetDatum(inh));
2174 tgl@sss.pgh.pa.us 157 [ - + ]: 201 : if (!HeapTupleIsValid(htup))
2527 tgl@sss.pgh.pa.us 158 [ # # ]:UBC 0 : elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
159 : :
1767 tomas.vondra@postgre 160 :CBC 201 : ndist = SysCacheGetAttr(STATEXTDATASTXOID, htup,
161 : : Anum_pg_statistic_ext_data_stxdndistinct, &isnull);
2578 alvherre@alvh.no-ip. 162 [ - + ]: 201 : if (isnull)
2578 alvherre@alvh.no-ip. 163 [ # # ]:UBC 0 : elog(ERROR,
164 : : "requested statistics kind \"%c\" is not yet built for statistics object %u",
165 : : STATS_EXT_NDISTINCT, mvoid);
166 : :
2174 tgl@sss.pgh.pa.us 167 :CBC 201 : result = statext_ndistinct_deserialize(DatumGetByteaPP(ndist));
168 : :
2578 alvherre@alvh.no-ip. 169 : 201 : ReleaseSysCache(htup);
170 : :
2174 tgl@sss.pgh.pa.us 171 : 201 : return result;
172 : : }
173 : :
174 : : /*
175 : : * statext_ndistinct_serialize
176 : : * serialize ndistinct to the on-disk bytea format
177 : : */
178 : : bytea *
2578 alvherre@alvh.no-ip. 179 : 78 : statext_ndistinct_serialize(MVNDistinct *ndistinct)
180 : : {
181 : : int i;
182 : : bytea *output;
183 : : char *tmp;
184 : : Size len;
185 : :
186 [ - + ]: 78 : Assert(ndistinct->magic == STATS_NDISTINCT_MAGIC);
187 [ - + ]: 78 : 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 : : */
1820 tomas.vondra@postgre 193 : 78 : len = VARHDRSZ + SizeOfHeader;
194 : :
195 : : /* and also include space for the actual attribute numbers */
2578 alvherre@alvh.no-ip. 196 [ + + ]: 330 : for (i = 0; i < ndistinct->nitems; i++)
197 : : {
198 : : int nmembers;
199 : :
1115 tomas.vondra@postgre 200 : 252 : nmembers = ndistinct->items[i].nattributes;
2578 alvherre@alvh.no-ip. 201 [ - + ]: 252 : Assert(nmembers >= 2);
202 : :
1820 tomas.vondra@postgre 203 : 252 : len += SizeOfItem(nmembers);
204 : : }
205 : :
2578 alvherre@alvh.no-ip. 206 : 78 : output = (bytea *) palloc(len);
207 : 78 : SET_VARSIZE(output, len);
208 : :
209 : 78 : tmp = VARDATA(output);
210 : :
211 : : /* Store the base struct values (magic, type, nitems) */
2575 212 : 78 : memcpy(tmp, &ndistinct->magic, sizeof(uint32));
213 : 78 : tmp += sizeof(uint32);
214 : 78 : memcpy(tmp, &ndistinct->type, sizeof(uint32));
215 : 78 : tmp += sizeof(uint32);
216 : 78 : memcpy(tmp, &ndistinct->nitems, sizeof(uint32));
217 : 78 : tmp += sizeof(uint32);
218 : :
219 : : /*
220 : : * store number of attributes and attribute numbers for each entry
221 : : */
2578 222 [ + + ]: 330 : for (i = 0; i < ndistinct->nitems; i++)
223 : : {
224 : 252 : MVNDistinctItem item = ndistinct->items[i];
1115 tomas.vondra@postgre 225 : 252 : int nmembers = item.nattributes;
226 : :
2578 alvherre@alvh.no-ip. 227 : 252 : memcpy(tmp, &item.ndistinct, sizeof(double));
228 : 252 : tmp += sizeof(double);
229 : 252 : memcpy(tmp, &nmembers, sizeof(int));
230 : 252 : tmp += sizeof(int);
231 : :
1115 tomas.vondra@postgre 232 : 252 : memcpy(tmp, item.attributes, sizeof(AttrNumber) * nmembers);
233 : 252 : tmp += nmembers * sizeof(AttrNumber);
234 : :
235 : : /* protect against overflows */
2578 alvherre@alvh.no-ip. 236 [ - + ]: 252 : Assert(tmp <= ((char *) output + len));
237 : : }
238 : :
239 : : /* check we used exactly the expected space */
1820 tomas.vondra@postgre 240 [ - + ]: 78 : Assert(tmp == ((char *) output + len));
241 : :
2578 alvherre@alvh.no-ip. 242 : 78 : return output;
243 : : }
244 : :
245 : : /*
246 : : * statext_ndistinct_deserialize
247 : : * Read an on-disk bytea format MVNDistinct to in-memory format
248 : : */
249 : : MVNDistinct *
250 : 213 : statext_ndistinct_deserialize(bytea *data)
251 : : {
252 : : int i;
253 : : Size minimum_size;
254 : : MVNDistinct ndist;
255 : : MVNDistinct *ndistinct;
256 : : char *tmp;
257 : :
258 [ - + ]: 213 : if (data == NULL)
2578 alvherre@alvh.no-ip. 259 :UBC 0 : return NULL;
260 : :
261 : : /* we expect at least the basic fields of MVNDistinct struct */
1820 tomas.vondra@postgre 262 [ - + - - :CBC 213 : if (VARSIZE_ANY_EXHDR(data) < SizeOfHeader)
- - - - +
+ - + ]
415 peter@eisentraut.org 263 [ # # # # :UBC 0 : 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) */
2578 alvherre@alvh.no-ip. 267 [ + + ]:CBC 213 : tmp = VARDATA_ANY(data);
268 : :
269 : : /* read the header fields and perform basic sanity checks */
2575 270 : 213 : memcpy(&ndist.magic, tmp, sizeof(uint32));
271 : 213 : tmp += sizeof(uint32);
272 : 213 : memcpy(&ndist.type, tmp, sizeof(uint32));
273 : 213 : tmp += sizeof(uint32);
274 : 213 : memcpy(&ndist.nitems, tmp, sizeof(uint32));
275 : 213 : tmp += sizeof(uint32);
276 : :
277 [ - + ]: 213 : if (ndist.magic != STATS_NDISTINCT_MAGIC)
1781 tomas.vondra@postgre 278 [ # # ]:UBC 0 : elog(ERROR, "invalid ndistinct magic %08x (expected %08x)",
279 : : ndist.magic, STATS_NDISTINCT_MAGIC);
2575 alvherre@alvh.no-ip. 280 [ - + ]:CBC 213 : if (ndist.type != STATS_NDISTINCT_TYPE_BASIC)
1781 tomas.vondra@postgre 281 [ # # ]:UBC 0 : elog(ERROR, "invalid ndistinct type %d (expected %d)",
282 : : ndist.type, STATS_NDISTINCT_TYPE_BASIC);
2575 alvherre@alvh.no-ip. 283 [ - + ]:CBC 213 : if (ndist.nitems == 0)
1781 tomas.vondra@postgre 284 [ # # ]:UBC 0 : elog(ERROR, "invalid zero-length item array in MVNDistinct");
285 : :
286 : : /* what minimum bytea size do we expect for those parameters */
1820 tomas.vondra@postgre 287 :CBC 213 : minimum_size = MinSizeOfItems(ndist.nitems);
2575 alvherre@alvh.no-ip. 288 [ - + - - : 213 : if (VARSIZE_ANY_EXHDR(data) < minimum_size)
- - - - +
+ - + ]
415 peter@eisentraut.org 289 [ # # # # :UBC 0 : 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 : : */
1820 tomas.vondra@postgre 296 :CBC 213 : ndistinct = palloc0(MAXALIGN(offsetof(MVNDistinct, items)) +
2575 alvherre@alvh.no-ip. 297 : 213 : (ndist.nitems * sizeof(MVNDistinctItem)));
298 : 213 : ndistinct->magic = ndist.magic;
299 : 213 : ndistinct->type = ndist.type;
300 : 213 : ndistinct->nitems = ndist.nitems;
301 : :
2578 302 [ + + ]: 1155 : for (i = 0; i < ndistinct->nitems; i++)
303 : : {
304 : 942 : MVNDistinctItem *item = &ndistinct->items[i];
305 : :
306 : : /* ndistinct value */
307 : 942 : memcpy(&item->ndistinct, tmp, sizeof(double));
308 : 942 : tmp += sizeof(double);
309 : :
310 : : /* number of attributes */
1115 tomas.vondra@postgre 311 : 942 : memcpy(&item->nattributes, tmp, sizeof(int));
2578 alvherre@alvh.no-ip. 312 : 942 : tmp += sizeof(int);
1115 tomas.vondra@postgre 313 [ + - - + ]: 942 : Assert((item->nattributes >= 2) && (item->nattributes <= STATS_MAX_DIMENSIONS));
314 : :
315 : : item->attributes
316 : 942 : = (AttrNumber *) palloc(item->nattributes * sizeof(AttrNumber));
317 : :
318 : 942 : memcpy(item->attributes, tmp, sizeof(AttrNumber) * item->nattributes);
319 : 942 : tmp += sizeof(AttrNumber) * item->nattributes;
320 : :
321 : : /* still within the bytea */
2578 alvherre@alvh.no-ip. 322 [ - + - - : 942 : Assert(tmp <= ((char *) data + VARSIZE_ANY(data)));
- - - - +
+ - + ]
323 : : }
324 : :
325 : : /* we should have consumed the whole bytea exactly */
326 [ - + - - : 213 : Assert(tmp == ((char *) data + VARSIZE_ANY(data)));
- - - - +
+ - + ]
327 : :
328 : 213 : 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 : : */
338 : : Datum
2578 alvherre@alvh.no-ip. 339 :UBC 0 : pg_ndistinct_in(PG_FUNCTION_ARGS)
340 : : {
341 [ # # ]: 0 : 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 : : */
354 : : Datum
2578 alvherre@alvh.no-ip. 355 :CBC 12 : pg_ndistinct_out(PG_FUNCTION_ARGS)
356 : : {
357 : 12 : bytea *data = PG_GETARG_BYTEA_PP(0);
358 : 12 : MVNDistinct *ndist = statext_ndistinct_deserialize(data);
359 : : int i;
360 : : StringInfoData str;
361 : :
362 : 12 : initStringInfo(&str);
2539 363 : 12 : appendStringInfoChar(&str, '{');
364 : :
2578 365 [ + + ]: 60 : for (i = 0; i < ndist->nitems; i++)
366 : : {
367 : : int j;
368 : 48 : MVNDistinctItem item = ndist->items[i];
369 : :
370 [ + + ]: 48 : if (i > 0)
371 : 36 : appendStringInfoString(&str, ", ");
372 : :
1115 tomas.vondra@postgre 373 [ + + ]: 156 : for (j = 0; j < item.nattributes; j++)
374 : : {
375 : 108 : AttrNumber attnum = item.attributes[j];
376 : :
377 [ + + ]: 108 : appendStringInfo(&str, "%s%d", (j == 0) ? "\"" : ", ", attnum);
378 : : }
2539 alvherre@alvh.no-ip. 379 : 48 : appendStringInfo(&str, "\": %d", (int) item.ndistinct);
380 : : }
381 : :
382 : 12 : appendStringInfoChar(&str, '}');
383 : :
2578 384 : 12 : PG_RETURN_CSTRING(str.data);
385 : : }
386 : :
387 : : /*
388 : : * pg_ndistinct_recv
389 : : * binary input routine for type pg_ndistinct
390 : : */
391 : : Datum
2578 alvherre@alvh.no-ip. 392 :UBC 0 : pg_ndistinct_recv(PG_FUNCTION_ARGS)
393 : : {
394 [ # # ]: 0 : 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 : : */
407 : : Datum
408 : 0 : pg_ndistinct_send(PG_FUNCTION_ARGS)
409 : : {
410 : 0 : 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 : : */
424 : : static double
1115 tomas.vondra@postgre 425 :CBC 252 : 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 : 252 : int numrows = data->numrows;
438 : :
2578 alvherre@alvh.no-ip. 439 : 252 : 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 : 252 : items = (SortItem *) palloc(numrows * sizeof(SortItem));
448 : 252 : values = (Datum *) palloc0(sizeof(Datum) * numrows * k);
449 : 252 : isnull = (bool *) palloc0(sizeof(bool) * numrows * k);
450 : :
451 [ + + ]: 241752 : for (i = 0; i < numrows; i++)
452 : : {
453 : 241500 : items[i].values = &values[i * k];
454 : 241500 : 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 [ + + ]: 846 : for (i = 0; i < k; i++)
465 : : {
466 : : Oid typid;
467 : : TypeCacheEntry *type;
1115 tomas.vondra@postgre 468 : 594 : Oid collid = InvalidOid;
469 : 594 : VacAttrStats *colstat = data->stats[combination[i]];
470 : :
471 : 594 : typid = colstat->attrtypid;
472 : 594 : collid = colstat->attrcollid;
473 : :
474 : 594 : type = lookup_type_cache(typid, TYPECACHE_LT_OPR);
2524 bruce@momjian.us 475 [ - + ]: 594 : if (type->lt_opr == InvalidOid) /* shouldn't happen */
2578 alvherre@alvh.no-ip. 476 [ # # ]:UBC 0 : elog(ERROR, "cache lookup failed for ordering operator for type %u",
477 : : typid);
478 : :
479 : : /* prepare the sort function for this dimension */
1115 tomas.vondra@postgre 480 :CBC 594 : multi_sort_add_dimension(mss, i, type->lt_opr, collid);
481 : :
482 : : /* accumulate all the data for this dimension into the arrays */
2578 alvherre@alvh.no-ip. 483 [ + + ]: 573591 : for (j = 0; j < numrows; j++)
484 : : {
1115 tomas.vondra@postgre 485 : 572997 : items[j].values[i] = data->values[combination[i]][j];
486 : 572997 : items[j].isnull[i] = data->nulls[combination[i]][j];
487 : : }
488 : : }
489 : :
490 : : /* We can sort the array now ... */
432 peter@eisentraut.org 491 : 252 : qsort_interruptible(items, numrows, sizeof(SortItem),
492 : : multi_sort_compare, mss);
493 : :
494 : : /* ... and count the number of distinct combinations */
495 : :
2578 alvherre@alvh.no-ip. 496 : 252 : f1 = 0;
497 : 252 : cnt = 1;
498 : 252 : d = 1;
499 [ + + ]: 241500 : for (i = 1; i < numrows; i++)
500 : : {
501 [ + + ]: 241248 : if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0)
502 : : {
503 [ + + ]: 23343 : if (cnt == 1)
504 : 12909 : f1 += 1;
505 : :
506 : 23343 : d++;
507 : 23343 : cnt = 0;
508 : : }
509 : :
510 : 241248 : cnt += 1;
511 : : }
512 : :
513 [ + + ]: 252 : if (cnt == 1)
514 : 45 : f1 += 1;
515 : :
516 : 252 : return estimate_ndistinct(totalrows, numrows, d, f1);
517 : : }
518 : :
519 : : /* The Duj1 estimator (already used in analyze.c). */
520 : : static double
521 : 252 : estimate_ndistinct(double totalrows, int numrows, int d, int f1)
522 : : {
523 : : double numer,
524 : : denom,
525 : : ndistinct;
526 : :
2489 tgl@sss.pgh.pa.us 527 : 252 : numer = (double) numrows * (double) d;
528 : :
2578 alvherre@alvh.no-ip. 529 : 252 : denom = (double) (numrows - f1) +
2489 tgl@sss.pgh.pa.us 530 : 252 : (double) f1 * (double) numrows / totalrows;
531 : :
2578 alvherre@alvh.no-ip. 532 : 252 : ndistinct = numer / denom;
533 : :
534 : : /* Clamp to sane range in case of roundoff error */
535 [ - + ]: 252 : if (ndistinct < (double) d)
2578 alvherre@alvh.no-ip. 536 :UBC 0 : ndistinct = (double) d;
537 : :
2578 alvherre@alvh.no-ip. 538 [ - + ]:CBC 252 : if (ndistinct > totalrows)
2578 alvherre@alvh.no-ip. 539 :UBC 0 : ndistinct = totalrows;
540 : :
2578 alvherre@alvh.no-ip. 541 :CBC 252 : 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 : : */
549 : : static int
550 : 120 : n_choose_k(int n, int k)
551 : : {
552 : : int d,
553 : : r;
554 : :
555 [ + - - + ]: 120 : Assert((k > 0) && (n >= k));
556 : :
557 : : /* use symmetry of the binomial coefficients */
558 : 120 : k = Min(k, n - k);
559 : :
560 : 120 : r = 1;
561 [ + + ]: 174 : for (d = 1; d <= k; ++d)
562 : : {
563 : 54 : r *= n--;
564 : 54 : r /= d;
565 : : }
566 : :
567 : 120 : return r;
568 : : }
569 : :
570 : : /*
571 : : * num_combinations
572 : : * number of combinations, excluding single-value combinations
573 : : */
574 : : static int
575 : 78 : num_combinations(int n)
576 : : {
1467 drowley@postgresql.o 577 : 78 : 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 : : */
588 : : static CombinationGenerator *
2578 alvherre@alvh.no-ip. 589 : 120 : generator_init(int n, int k)
590 : : {
591 : : CombinationGenerator *state;
592 : :
593 [ + - - + ]: 120 : Assert((n >= k) && (k > 0));
594 : :
595 : : /* allocate the generator state as a single chunk of memory */
596 : 120 : state = (CombinationGenerator *) palloc(sizeof(CombinationGenerator));
597 : :
598 : 120 : state->ncombinations = n_choose_k(n, k);
599 : :
600 : : /* pre-allocate space for all combinations */
601 : 120 : state->combinations = (int *) palloc(sizeof(int) * k * state->ncombinations);
602 : :
603 : 120 : state->current = 0;
604 : 120 : state->k = k;
605 : 120 : state->n = n;
606 : :
607 : : /* now actually pre-generate all the combinations of K elements */
608 : 120 : generate_combinations(state);
609 : :
610 : : /* make sure we got the expected number of combinations */
611 [ - + ]: 120 : Assert(state->current == state->ncombinations);
612 : :
613 : : /* reset the number, so we start with the first one */
614 : 120 : state->current = 0;
615 : :
616 : 120 : 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 : : */
626 : : static int *
627 : 372 : generator_next(CombinationGenerator *state)
628 : : {
629 [ + + ]: 372 : if (state->current == state->ncombinations)
630 : 120 : return NULL;
631 : :
632 : 252 : 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 : : */
641 : : static void
642 : 120 : generator_free(CombinationGenerator *state)
643 : : {
644 : 120 : pfree(state->combinations);
645 : 120 : pfree(state);
646 : 120 : }
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 : : */
656 : : static void
657 : 966 : 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 [ + + ]: 966 : 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 [ + + ]: 1560 : for (i = start; i < state->n; i++)
671 : : {
672 : 846 : current[index] = i;
673 : 846 : generate_combinations_recurse(state, (index + 1), (i + 1), current);
674 : : }
675 : :
676 : 714 : return;
677 : : }
678 : : else
679 : : {
680 : : /* we got a valid combination, add it to the array */
681 : 252 : memcpy(&state->combinations[(state->k * state->current)],
682 : 252 : current, state->k * sizeof(int));
683 : 252 : state->current++;
684 : : }
685 : : }
686 : :
687 : : /*
688 : : * generate_combinations
689 : : * generate all k-combinations of N elements
690 : : */
691 : : static void
692 : 120 : generate_combinations(CombinationGenerator *state)
693 : : {
2524 bruce@momjian.us 694 : 120 : int *current = (int *) palloc0(sizeof(int) * state->k);
695 : :
2578 alvherre@alvh.no-ip. 696 : 120 : generate_combinations_recurse(state, 0, 0, current);
697 : :
698 : 120 : pfree(current);
699 : 120 : }
|
