Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * array_typanalyze.c
4 : * Functions for gathering statistics from array columns
5 : *
6 : * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
7 : * Portions Copyright (c) 1994, Regents of the University of California
8 : *
9 : *
10 : * IDENTIFICATION
11 : * src/backend/utils/adt/array_typanalyze.c
12 : *
13 : *-------------------------------------------------------------------------
14 : */
15 : #include "postgres.h"
16 :
17 : #include "access/tuptoaster.h"
18 : #include "commands/vacuum.h"
19 : #include "utils/array.h"
20 : #include "utils/builtins.h"
21 : #include "utils/datum.h"
22 : #include "utils/lsyscache.h"
23 : #include "utils/typcache.h"
24 :
25 :
26 : /*
27 : * To avoid consuming too much memory, IO and CPU load during analysis, and/or
28 : * too much space in the resulting pg_statistic rows, we ignore arrays that
29 : * are wider than ARRAY_WIDTH_THRESHOLD (after detoasting!). Note that this
30 : * number is considerably more than the similar WIDTH_THRESHOLD limit used
31 : * in analyze.c's standard typanalyze code.
32 : */
33 : #define ARRAY_WIDTH_THRESHOLD 0x10000
34 :
35 : /* Extra data for compute_array_stats function */
36 : typedef struct
37 : {
38 : /* Information about array element type */
39 : Oid type_id; /* element type's OID */
40 : Oid eq_opr; /* default equality operator's OID */
41 : Oid coll_id; /* collation to use */
42 : bool typbyval; /* physical properties of element type */
43 : int16 typlen;
44 : char typalign;
45 :
46 : /*
47 : * Lookup data for element type's comparison and hash functions (these are
48 : * in the type's typcache entry, which we expect to remain valid over the
49 : * lifespan of the ANALYZE run)
50 : */
51 : FmgrInfo *cmp;
52 : FmgrInfo *hash;
53 :
54 : /* Saved state from std_typanalyze() */
55 : AnalyzeAttrComputeStatsFunc std_compute_stats;
56 : void *std_extra_data;
57 : } ArrayAnalyzeExtraData;
58 :
59 : /*
60 : * While compute_array_stats is running, we keep a pointer to the extra data
61 : * here for use by assorted subroutines. compute_array_stats doesn't
62 : * currently need to be re-entrant, so avoiding this is not worth the extra
63 : * notational cruft that would be needed.
64 : */
65 : static ArrayAnalyzeExtraData *array_extra_data;
66 :
67 : /* A hash table entry for the Lossy Counting algorithm */
68 : typedef struct
69 : {
70 : Datum key; /* This is 'e' from the LC algorithm. */
71 : int frequency; /* This is 'f'. */
72 : int delta; /* And this is 'delta'. */
73 : int last_container; /* For de-duplication of array elements. */
74 : } TrackItem;
75 :
76 : /* A hash table entry for distinct-elements counts */
77 : typedef struct
78 : {
79 : int count; /* Count of distinct elements in an array */
80 : int frequency; /* Number of arrays seen with this count */
81 : } DECountItem;
82 :
83 : static void compute_array_stats(VacAttrStats *stats,
84 : AnalyzeAttrFetchFunc fetchfunc, int samplerows, double totalrows);
85 : static void prune_element_hashtable(HTAB *elements_tab, int b_current);
86 : static uint32 element_hash(const void *key, Size keysize);
87 : static int element_match(const void *key1, const void *key2, Size keysize);
88 : static int element_compare(const void *key1, const void *key2);
89 : static int trackitem_compare_frequencies_desc(const void *e1, const void *e2);
90 : static int trackitem_compare_element(const void *e1, const void *e2);
91 : static int countitem_compare_count(const void *e1, const void *e2);
92 :
93 :
94 : /*
95 : * array_typanalyze -- typanalyze function for array columns
96 : */
97 : Datum
98 16172 : array_typanalyze(PG_FUNCTION_ARGS)
99 : {
100 16172 : VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
101 : Oid element_typeid;
102 : TypeCacheEntry *typentry;
103 : ArrayAnalyzeExtraData *extra_data;
104 :
105 : /*
106 : * Call the standard typanalyze function. It may fail to find needed
107 : * operators, in which case we also can't do anything, so just fail.
108 : */
109 16172 : if (!std_typanalyze(stats))
110 0 : PG_RETURN_BOOL(false);
111 :
112 : /*
113 : * Check attribute data type is a varlena array (or a domain over one).
114 : */
115 16172 : element_typeid = get_base_element_type(stats->attrtypid);
116 16172 : if (!OidIsValid(element_typeid))
117 0 : elog(ERROR, "array_typanalyze was invoked for non-array type %u",
118 : stats->attrtypid);
119 :
120 : /*
121 : * Gather information about the element type. If we fail to find
122 : * something, return leaving the state from std_typanalyze() in place.
123 : */
124 16172 : typentry = lookup_type_cache(element_typeid,
125 : TYPECACHE_EQ_OPR |
126 : TYPECACHE_CMP_PROC_FINFO |
127 : TYPECACHE_HASH_PROC_FINFO);
128 :
129 32344 : if (!OidIsValid(typentry->eq_opr) ||
130 26754 : !OidIsValid(typentry->cmp_proc_finfo.fn_oid) ||
131 10582 : !OidIsValid(typentry->hash_proc_finfo.fn_oid))
132 5590 : PG_RETURN_BOOL(true);
133 :
134 : /* Store our findings for use by compute_array_stats() */
135 10582 : extra_data = (ArrayAnalyzeExtraData *) palloc(sizeof(ArrayAnalyzeExtraData));
136 10582 : extra_data->type_id = typentry->type_id;
137 10582 : extra_data->eq_opr = typentry->eq_opr;
138 10582 : extra_data->coll_id = stats->attrcollid; /* collation we should use */
139 10582 : extra_data->typbyval = typentry->typbyval;
140 10582 : extra_data->typlen = typentry->typlen;
141 10582 : extra_data->typalign = typentry->typalign;
142 10582 : extra_data->cmp = &typentry->cmp_proc_finfo;
143 10582 : extra_data->hash = &typentry->hash_proc_finfo;
144 :
145 : /* Save old compute_stats and extra_data for scalar statistics ... */
146 10582 : extra_data->std_compute_stats = stats->compute_stats;
147 10582 : extra_data->std_extra_data = stats->extra_data;
148 :
149 : /* ... and replace with our info */
150 10582 : stats->compute_stats = compute_array_stats;
151 10582 : stats->extra_data = extra_data;
152 :
153 : /*
154 : * Note we leave stats->minrows set as std_typanalyze set it. Should it
155 : * be increased for array analysis purposes?
156 : */
157 :
158 10582 : PG_RETURN_BOOL(true);
159 : }
160 :
161 : /*
162 : * compute_array_stats() -- compute statistics for an array column
163 : *
164 : * This function computes statistics useful for determining selectivity of
165 : * the array operators <@, &&, and @>. It is invoked by ANALYZE via the
166 : * compute_stats hook after sample rows have been collected.
167 : *
168 : * We also invoke the standard compute_stats function, which will compute
169 : * "scalar" statistics relevant to the btree-style array comparison operators.
170 : * However, exact duplicates of an entire array may be rare despite many
171 : * arrays sharing individual elements. This especially afflicts long arrays,
172 : * which are also liable to lack all scalar statistics due to the low
173 : * WIDTH_THRESHOLD used in analyze.c. So, in addition to the standard stats,
174 : * we find the most common array elements and compute a histogram of distinct
175 : * element counts.
176 : *
177 : * The algorithm used is Lossy Counting, as proposed in the paper "Approximate
178 : * frequency counts over data streams" by G. S. Manku and R. Motwani, in
179 : * Proceedings of the 28th International Conference on Very Large Data Bases,
180 : * Hong Kong, China, August 2002, section 4.2. The paper is available at
181 : * http://www.vldb.org/conf/2002/S10P03.pdf
182 : *
183 : * The Lossy Counting (aka LC) algorithm goes like this:
184 : * Let s be the threshold frequency for an item (the minimum frequency we
185 : * are interested in) and epsilon the error margin for the frequency. Let D
186 : * be a set of triples (e, f, delta), where e is an element value, f is that
187 : * element's frequency (actually, its current occurrence count) and delta is
188 : * the maximum error in f. We start with D empty and process the elements in
189 : * batches of size w. (The batch size is also known as "bucket size" and is
190 : * equal to 1/epsilon.) Let the current batch number be b_current, starting
191 : * with 1. For each element e we either increment its f count, if it's
192 : * already in D, or insert a new triple into D with values (e, 1, b_current
193 : * - 1). After processing each batch we prune D, by removing from it all
194 : * elements with f + delta <= b_current. After the algorithm finishes we
195 : * suppress all elements from D that do not satisfy f >= (s - epsilon) * N,
196 : * where N is the total number of elements in the input. We emit the
197 : * remaining elements with estimated frequency f/N. The LC paper proves
198 : * that this algorithm finds all elements with true frequency at least s,
199 : * and that no frequency is overestimated or is underestimated by more than
200 : * epsilon. Furthermore, given reasonable assumptions about the input
201 : * distribution, the required table size is no more than about 7 times w.
202 : *
203 : * In the absence of a principled basis for other particular values, we
204 : * follow ts_typanalyze() and use parameters s = 0.07/K, epsilon = s/10.
205 : * But we leave out the correction for stopwords, which do not apply to
206 : * arrays. These parameters give bucket width w = K/0.007 and maximum
207 : * expected hashtable size of about 1000 * K.
208 : *
209 : * Elements may repeat within an array. Since duplicates do not change the
210 : * behavior of <@, && or @>, we want to count each element only once per
211 : * array. Therefore, we store in the finished pg_statistic entry each
212 : * element's frequency as the fraction of all non-null rows that contain it.
213 : * We divide the raw counts by nonnull_cnt to get those figures.
214 : */
215 : static void
216 7072 : compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
217 : int samplerows, double totalrows)
218 : {
219 : ArrayAnalyzeExtraData *extra_data;
220 : int num_mcelem;
221 7072 : int null_cnt = 0;
222 7072 : int null_elem_cnt = 0;
223 7072 : int analyzed_rows = 0;
224 :
225 : /* This is D from the LC algorithm. */
226 : HTAB *elements_tab;
227 : HASHCTL elem_hash_ctl;
228 : HASH_SEQ_STATUS scan_status;
229 :
230 : /* This is the current bucket number from the LC algorithm */
231 : int b_current;
232 :
233 : /* This is 'w' from the LC algorithm */
234 : int bucket_width;
235 : int array_no;
236 : int64 element_no;
237 : TrackItem *item;
238 : int slot_idx;
239 : HTAB *count_tab;
240 : HASHCTL count_hash_ctl;
241 : DECountItem *count_item;
242 :
243 7072 : extra_data = (ArrayAnalyzeExtraData *) stats->extra_data;
244 :
245 : /*
246 : * Invoke analyze.c's standard analysis function to create scalar-style
247 : * stats for the column. It will expect its own extra_data pointer, so
248 : * temporarily install that.
249 : */
250 7072 : stats->extra_data = extra_data->std_extra_data;
251 7072 : extra_data->std_compute_stats(stats, fetchfunc, samplerows, totalrows);
252 7072 : stats->extra_data = extra_data;
253 :
254 : /*
255 : * Set up static pointer for use by subroutines. We wait till here in
256 : * case std_compute_stats somehow recursively invokes us (probably not
257 : * possible, but ...)
258 : */
259 7072 : array_extra_data = extra_data;
260 :
261 : /*
262 : * We want statistics_target * 10 elements in the MCELEM array. This
263 : * multiplier is pretty arbitrary, but is meant to reflect the fact that
264 : * the number of individual elements tracked in pg_statistic ought to be
265 : * more than the number of values for a simple scalar column.
266 : */
267 7072 : num_mcelem = stats->attr->attstattarget * 10;
268 :
269 : /*
270 : * We set bucket width equal to num_mcelem / 0.007 as per the comment
271 : * above.
272 : */
273 7072 : bucket_width = num_mcelem * 1000 / 7;
274 :
275 : /*
276 : * Create the hashtable. It will be in local memory, so we don't need to
277 : * worry about overflowing the initial size. Also we don't need to pay any
278 : * attention to locking and memory management.
279 : */
280 7072 : MemSet(&elem_hash_ctl, 0, sizeof(elem_hash_ctl));
281 7072 : elem_hash_ctl.keysize = sizeof(Datum);
282 7072 : elem_hash_ctl.entrysize = sizeof(TrackItem);
283 7072 : elem_hash_ctl.hash = element_hash;
284 7072 : elem_hash_ctl.match = element_match;
285 7072 : elem_hash_ctl.hcxt = CurrentMemoryContext;
286 7072 : elements_tab = hash_create("Analyzed elements table",
287 : num_mcelem,
288 : &elem_hash_ctl,
289 : HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
290 :
291 : /* hashtable for array distinct elements counts */
292 7072 : MemSet(&count_hash_ctl, 0, sizeof(count_hash_ctl));
293 7072 : count_hash_ctl.keysize = sizeof(int);
294 7072 : count_hash_ctl.entrysize = sizeof(DECountItem);
295 7072 : count_hash_ctl.hcxt = CurrentMemoryContext;
296 7072 : count_tab = hash_create("Array distinct element count table",
297 : 64,
298 : &count_hash_ctl,
299 : HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
300 :
301 : /* Initialize counters. */
302 7072 : b_current = 1;
303 7072 : element_no = 0;
304 :
305 : /* Loop over the arrays. */
306 8455746 : for (array_no = 0; array_no < samplerows; array_no++)
307 : {
308 : Datum value;
309 : bool isnull;
310 : ArrayType *array;
311 : int num_elems;
312 : Datum *elem_values;
313 : bool *elem_nulls;
314 : bool null_present;
315 : int j;
316 8448674 : int64 prev_element_no = element_no;
317 : int distinct_count;
318 : bool count_item_found;
319 :
320 8448674 : vacuum_delay_point();
321 :
322 8448674 : value = fetchfunc(stats, array_no, &isnull);
323 8448674 : if (isnull)
324 : {
325 : /* array is null, just count that */
326 8141952 : null_cnt++;
327 16283904 : continue;
328 : }
329 :
330 : /* Skip too-large values. */
331 306722 : if (toast_raw_datum_size(value) > ARRAY_WIDTH_THRESHOLD)
332 0 : continue;
333 : else
334 306722 : analyzed_rows++;
335 :
336 : /*
337 : * Now detoast the array if needed, and deconstruct into datums.
338 : */
339 306722 : array = DatumGetArrayTypeP(value);
340 :
341 : Assert(ARR_ELEMTYPE(array) == extra_data->type_id);
342 920166 : deconstruct_array(array,
343 : extra_data->type_id,
344 306722 : extra_data->typlen,
345 306722 : extra_data->typbyval,
346 306722 : extra_data->typalign,
347 : &elem_values, &elem_nulls, &num_elems);
348 :
349 : /*
350 : * We loop through the elements in the array and add them to our
351 : * tracking hashtable.
352 : */
353 306722 : null_present = false;
354 1511128 : for (j = 0; j < num_elems; j++)
355 : {
356 : Datum elem_value;
357 : bool found;
358 :
359 : /* No null element processing other than flag setting here */
360 1204406 : if (elem_nulls[j])
361 : {
362 58 : null_present = true;
363 230818 : continue;
364 : }
365 :
366 : /* Lookup current element in hashtable, adding it if new */
367 1204348 : elem_value = elem_values[j];
368 1204348 : item = (TrackItem *) hash_search(elements_tab,
369 : (const void *) &elem_value,
370 : HASH_ENTER, &found);
371 :
372 1204348 : if (found)
373 : {
374 : /* The element value is already on the tracking list */
375 :
376 : /*
377 : * The operators we assist ignore duplicate array elements, so
378 : * count a given distinct element only once per array.
379 : */
380 1043416 : if (item->last_container == array_no)
381 230702 : continue;
382 :
383 812714 : item->frequency++;
384 812714 : item->last_container = array_no;
385 : }
386 : else
387 : {
388 : /* Initialize new tracking list element */
389 :
390 : /*
391 : * If element type is pass-by-reference, we must copy it into
392 : * palloc'd space, so that we can release the array below. (We
393 : * do this so that the space needed for element values is
394 : * limited by the size of the hashtable; if we kept all the
395 : * array values around, it could be much more.)
396 : */
397 321864 : item->key = datumCopy(elem_value,
398 160932 : extra_data->typbyval,
399 160932 : extra_data->typlen);
400 :
401 160932 : item->frequency = 1;
402 160932 : item->delta = b_current - 1;
403 160932 : item->last_container = array_no;
404 : }
405 :
406 : /* element_no is the number of elements processed (ie N) */
407 973646 : element_no++;
408 :
409 : /* We prune the D structure after processing each bucket */
410 973646 : if (element_no % bucket_width == 0)
411 : {
412 0 : prune_element_hashtable(elements_tab, b_current);
413 0 : b_current++;
414 : }
415 : }
416 :
417 : /* Count null element presence once per array. */
418 306722 : if (null_present)
419 52 : null_elem_cnt++;
420 :
421 : /* Update frequency of the particular array distinct element count. */
422 306722 : distinct_count = (int) (element_no - prev_element_no);
423 306722 : count_item = (DECountItem *) hash_search(count_tab, &distinct_count,
424 : HASH_ENTER,
425 : &count_item_found);
426 :
427 306722 : if (count_item_found)
428 294380 : count_item->frequency++;
429 : else
430 12342 : count_item->frequency = 1;
431 :
432 : /* Free memory allocated while detoasting. */
433 306722 : if (PointerGetDatum(array) != value)
434 251732 : pfree(array);
435 306722 : pfree(elem_values);
436 306722 : pfree(elem_nulls);
437 : }
438 :
439 : /* Skip pg_statistic slots occupied by standard statistics */
440 7072 : slot_idx = 0;
441 19040 : while (slot_idx < STATISTIC_NUM_SLOTS && stats->stakind[slot_idx] != 0)
442 4896 : slot_idx++;
443 7072 : if (slot_idx > STATISTIC_NUM_SLOTS - 2)
444 0 : elog(ERROR, "insufficient pg_statistic slots for array stats");
445 :
446 : /* We can only compute real stats if we found some non-null values. */
447 7072 : if (analyzed_rows > 0)
448 : {
449 1902 : int nonnull_cnt = analyzed_rows;
450 : int count_items_count;
451 : int i;
452 : TrackItem **sort_table;
453 : int track_len;
454 : int64 cutoff_freq;
455 : int64 minfreq,
456 : maxfreq;
457 :
458 : /*
459 : * We assume the standard stats code already took care of setting
460 : * stats_valid, stanullfrac, stawidth, stadistinct. We'd have to
461 : * re-compute those values if we wanted to not store the standard
462 : * stats.
463 : */
464 :
465 : /*
466 : * Construct an array of the interesting hashtable items, that is,
467 : * those meeting the cutoff frequency (s - epsilon)*N. Also identify
468 : * the minimum and maximum frequencies among these items.
469 : *
470 : * Since epsilon = s/10 and bucket_width = 1/epsilon, the cutoff
471 : * frequency is 9*N / bucket_width.
472 : */
473 1902 : cutoff_freq = 9 * element_no / bucket_width;
474 :
475 1902 : i = hash_get_num_entries(elements_tab); /* surely enough space */
476 1902 : sort_table = (TrackItem **) palloc(sizeof(TrackItem *) * i);
477 :
478 1902 : hash_seq_init(&scan_status, elements_tab);
479 1902 : track_len = 0;
480 1902 : minfreq = element_no;
481 1902 : maxfreq = 0;
482 164736 : while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
483 : {
484 160932 : if (item->frequency > cutoff_freq)
485 : {
486 157746 : sort_table[track_len++] = item;
487 157746 : minfreq = Min(minfreq, item->frequency);
488 157746 : maxfreq = Max(maxfreq, item->frequency);
489 : }
490 : }
491 : Assert(track_len <= i);
492 :
493 : /* emit some statistics for debug purposes */
494 1902 : elog(DEBUG3, "compute_array_stats: target # mces = %d, "
495 : "bucket width = %d, "
496 : "# elements = " INT64_FORMAT ", hashtable size = %d, "
497 : "usable entries = %d",
498 : num_mcelem, bucket_width, element_no, i, track_len);
499 :
500 : /*
501 : * If we obtained more elements than we really want, get rid of those
502 : * with least frequencies. The easiest way is to qsort the array into
503 : * descending frequency order and truncate the array.
504 : */
505 1902 : if (num_mcelem < track_len)
506 : {
507 74 : qsort(sort_table, track_len, sizeof(TrackItem *),
508 : trackitem_compare_frequencies_desc);
509 : /* reset minfreq to the smallest frequency we're keeping */
510 74 : minfreq = sort_table[num_mcelem - 1]->frequency;
511 : }
512 : else
513 1828 : num_mcelem = track_len;
514 :
515 : /* Generate MCELEM slot entry */
516 1902 : if (num_mcelem > 0)
517 : {
518 : MemoryContext old_context;
519 : Datum *mcelem_values;
520 : float4 *mcelem_freqs;
521 :
522 : /*
523 : * We want to store statistics sorted on the element value using
524 : * the element type's default comparison function. This permits
525 : * fast binary searches in selectivity estimation functions.
526 : */
527 1902 : qsort(sort_table, num_mcelem, sizeof(TrackItem *),
528 : trackitem_compare_element);
529 :
530 : /* Must copy the target values into anl_context */
531 1902 : old_context = MemoryContextSwitchTo(stats->anl_context);
532 :
533 : /*
534 : * We sorted statistics on the element value, but we want to be
535 : * able to find the minimal and maximal frequencies without going
536 : * through all the values. We also want the frequency of null
537 : * elements. Store these three values at the end of mcelem_freqs.
538 : */
539 1902 : mcelem_values = (Datum *) palloc(num_mcelem * sizeof(Datum));
540 1902 : mcelem_freqs = (float4 *) palloc((num_mcelem + 3) * sizeof(float4));
541 :
542 : /*
543 : * See comments above about use of nonnull_cnt as the divisor for
544 : * the final frequency estimates.
545 : */
546 153104 : for (i = 0; i < num_mcelem; i++)
547 : {
548 151202 : TrackItem *item = sort_table[i];
549 :
550 453606 : mcelem_values[i] = datumCopy(item->key,
551 151202 : extra_data->typbyval,
552 151202 : extra_data->typlen);
553 302404 : mcelem_freqs[i] = (double) item->frequency /
554 151202 : (double) nonnull_cnt;
555 : }
556 1902 : mcelem_freqs[i++] = (double) minfreq / (double) nonnull_cnt;
557 1902 : mcelem_freqs[i++] = (double) maxfreq / (double) nonnull_cnt;
558 1902 : mcelem_freqs[i++] = (double) null_elem_cnt / (double) nonnull_cnt;
559 :
560 1902 : MemoryContextSwitchTo(old_context);
561 :
562 1902 : stats->stakind[slot_idx] = STATISTIC_KIND_MCELEM;
563 1902 : stats->staop[slot_idx] = extra_data->eq_opr;
564 1902 : stats->stacoll[slot_idx] = extra_data->coll_id;
565 1902 : stats->stanumbers[slot_idx] = mcelem_freqs;
566 : /* See above comment about extra stanumber entries */
567 1902 : stats->numnumbers[slot_idx] = num_mcelem + 3;
568 1902 : stats->stavalues[slot_idx] = mcelem_values;
569 1902 : stats->numvalues[slot_idx] = num_mcelem;
570 : /* We are storing values of element type */
571 1902 : stats->statypid[slot_idx] = extra_data->type_id;
572 1902 : stats->statyplen[slot_idx] = extra_data->typlen;
573 1902 : stats->statypbyval[slot_idx] = extra_data->typbyval;
574 1902 : stats->statypalign[slot_idx] = extra_data->typalign;
575 1902 : slot_idx++;
576 : }
577 :
578 : /* Generate DECHIST slot entry */
579 1902 : count_items_count = hash_get_num_entries(count_tab);
580 1902 : if (count_items_count > 0)
581 : {
582 1902 : int num_hist = stats->attr->attstattarget;
583 : DECountItem **sorted_count_items;
584 : int j;
585 : int delta;
586 : int64 frac;
587 : float4 *hist;
588 :
589 : /* num_hist must be at least 2 for the loop below to work */
590 1902 : num_hist = Max(num_hist, 2);
591 :
592 : /*
593 : * Create an array of DECountItem pointers, and sort them into
594 : * increasing count order.
595 : */
596 1902 : sorted_count_items = (DECountItem **)
597 1902 : palloc(sizeof(DECountItem *) * count_items_count);
598 1902 : hash_seq_init(&scan_status, count_tab);
599 1902 : j = 0;
600 16146 : while ((count_item = (DECountItem *) hash_seq_search(&scan_status)) != NULL)
601 : {
602 12342 : sorted_count_items[j++] = count_item;
603 : }
604 1902 : qsort(sorted_count_items, count_items_count,
605 : sizeof(DECountItem *), countitem_compare_count);
606 :
607 : /*
608 : * Prepare to fill stanumbers with the histogram, followed by the
609 : * average count. This array must be stored in anl_context.
610 : */
611 1902 : hist = (float4 *)
612 1902 : MemoryContextAlloc(stats->anl_context,
613 1902 : sizeof(float4) * (num_hist + 1));
614 1902 : hist[num_hist] = (double) element_no / (double) nonnull_cnt;
615 :
616 : /*----------
617 : * Construct the histogram of distinct-element counts (DECs).
618 : *
619 : * The object of this loop is to copy the min and max DECs to
620 : * hist[0] and hist[num_hist - 1], along with evenly-spaced DECs
621 : * in between (where "evenly-spaced" is with reference to the
622 : * whole input population of arrays). If we had a complete sorted
623 : * array of DECs, one per analyzed row, the i'th hist value would
624 : * come from DECs[i * (analyzed_rows - 1) / (num_hist - 1)]
625 : * (compare the histogram-making loop in compute_scalar_stats()).
626 : * But instead of that we have the sorted_count_items[] array,
627 : * which holds unique DEC values with their frequencies (that is,
628 : * a run-length-compressed version of the full array). So we
629 : * control advancing through sorted_count_items[] with the
630 : * variable "frac", which is defined as (x - y) * (num_hist - 1),
631 : * where x is the index in the notional DECs array corresponding
632 : * to the start of the next sorted_count_items[] element's run,
633 : * and y is the index in DECs from which we should take the next
634 : * histogram value. We have to advance whenever x <= y, that is
635 : * frac <= 0. The x component is the sum of the frequencies seen
636 : * so far (up through the current sorted_count_items[] element),
637 : * and of course y * (num_hist - 1) = i * (analyzed_rows - 1),
638 : * per the subscript calculation above. (The subscript calculation
639 : * implies dropping any fractional part of y; in this formulation
640 : * that's handled by not advancing until frac reaches 1.)
641 : *
642 : * Even though frac has a bounded range, it could overflow int32
643 : * when working with very large statistics targets, so we do that
644 : * math in int64.
645 : *----------
646 : */
647 1902 : delta = analyzed_rows - 1;
648 1902 : j = 0; /* current index in sorted_count_items */
649 : /* Initialize frac for sorted_count_items[0]; y is initially 0 */
650 1902 : frac = (int64) sorted_count_items[0]->frequency * (num_hist - 1);
651 166158 : for (i = 0; i < num_hist; i++)
652 : {
653 338952 : while (frac <= 0)
654 : {
655 : /* Advance, and update x component of frac */
656 10440 : j++;
657 10440 : frac += (int64) sorted_count_items[j]->frequency * (num_hist - 1);
658 : }
659 164256 : hist[i] = sorted_count_items[j]->count;
660 164256 : frac -= delta; /* update y for upcoming i increment */
661 : }
662 : Assert(j == count_items_count - 1);
663 :
664 1902 : stats->stakind[slot_idx] = STATISTIC_KIND_DECHIST;
665 1902 : stats->staop[slot_idx] = extra_data->eq_opr;
666 1902 : stats->stacoll[slot_idx] = extra_data->coll_id;
667 1902 : stats->stanumbers[slot_idx] = hist;
668 1902 : stats->numnumbers[slot_idx] = num_hist + 1;
669 1902 : slot_idx++;
670 : }
671 : }
672 :
673 : /*
674 : * We don't need to bother cleaning up any of our temporary palloc's. The
675 : * hashtable should also go away, as it used a child memory context.
676 : */
677 7072 : }
678 :
679 : /*
680 : * A function to prune the D structure from the Lossy Counting algorithm.
681 : * Consult compute_tsvector_stats() for wider explanation.
682 : */
683 : static void
684 0 : prune_element_hashtable(HTAB *elements_tab, int b_current)
685 : {
686 : HASH_SEQ_STATUS scan_status;
687 : TrackItem *item;
688 :
689 0 : hash_seq_init(&scan_status, elements_tab);
690 0 : while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
691 : {
692 0 : if (item->frequency + item->delta <= b_current)
693 : {
694 0 : Datum value = item->key;
695 :
696 0 : if (hash_search(elements_tab, (const void *) &item->key,
697 : HASH_REMOVE, NULL) == NULL)
698 0 : elog(ERROR, "hash table corrupted");
699 : /* We should free memory if element is not passed by value */
700 0 : if (!array_extra_data->typbyval)
701 0 : pfree(DatumGetPointer(value));
702 : }
703 : }
704 0 : }
705 :
706 : /*
707 : * Hash function for elements.
708 : *
709 : * We use the element type's default hash opclass, and the column collation
710 : * if the type is collation-sensitive.
711 : */
712 : static uint32
713 1204348 : element_hash(const void *key, Size keysize)
714 : {
715 1204348 : Datum d = *((const Datum *) key);
716 : Datum h;
717 :
718 1204348 : h = FunctionCall1Coll(array_extra_data->hash,
719 1204348 : array_extra_data->coll_id,
720 : d);
721 1204348 : return DatumGetUInt32(h);
722 : }
723 :
724 : /*
725 : * Matching function for elements, to be used in hashtable lookups.
726 : */
727 : static int
728 1046184 : element_match(const void *key1, const void *key2, Size keysize)
729 : {
730 : /* The keysize parameter is superfluous here */
731 1046184 : return element_compare(key1, key2);
732 : }
733 :
734 : /*
735 : * Comparison function for elements.
736 : *
737 : * We use the element type's default btree opclass, and the column collation
738 : * if the type is collation-sensitive.
739 : *
740 : * XXX consider using SortSupport infrastructure
741 : */
742 : static int
743 2300804 : element_compare(const void *key1, const void *key2)
744 : {
745 2300804 : Datum d1 = *((const Datum *) key1);
746 2300804 : Datum d2 = *((const Datum *) key2);
747 : Datum c;
748 :
749 2300804 : c = FunctionCall2Coll(array_extra_data->cmp,
750 2300804 : array_extra_data->coll_id,
751 : d1, d2);
752 2300804 : return DatumGetInt32(c);
753 : }
754 :
755 : /*
756 : * qsort() comparator for sorting TrackItems by frequencies (descending sort)
757 : */
758 : static int
759 17912 : trackitem_compare_frequencies_desc(const void *e1, const void *e2)
760 : {
761 17912 : const TrackItem *const *t1 = (const TrackItem *const *) e1;
762 17912 : const TrackItem *const *t2 = (const TrackItem *const *) e2;
763 :
764 17912 : return (*t2)->frequency - (*t1)->frequency;
765 : }
766 :
767 : /*
768 : * qsort() comparator for sorting TrackItems by element values
769 : */
770 : static int
771 1254620 : trackitem_compare_element(const void *e1, const void *e2)
772 : {
773 1254620 : const TrackItem *const *t1 = (const TrackItem *const *) e1;
774 1254620 : const TrackItem *const *t2 = (const TrackItem *const *) e2;
775 :
776 1254620 : return element_compare(&(*t1)->key, &(*t2)->key);
777 : }
778 :
779 : /*
780 : * qsort() comparator for sorting DECountItems by count
781 : */
782 : static int
783 36676 : countitem_compare_count(const void *e1, const void *e2)
784 : {
785 36676 : const DECountItem *const *t1 = (const DECountItem *const *) e1;
786 36676 : const DECountItem *const *t2 = (const DECountItem *const *) e2;
787 :
788 36676 : if ((*t1)->count < (*t2)->count)
789 15210 : return -1;
790 21466 : else if ((*t1)->count == (*t2)->count)
791 0 : return 0;
792 : else
793 21466 : return 1;
794 : }
|
