Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * array_typanalyze.c
4 : : * Functions for gathering statistics from array columns
5 : : *
6 : : * Portions Copyright (c) 1996-2025, 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/detoast.h"
18 : : #include "commands/vacuum.h"
19 : : #include "utils/array.h"
20 : : #include "utils/datum.h"
21 : : #include "utils/fmgrprotos.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, void *arg);
90 : : static int trackitem_compare_element(const void *e1, const void *e2, void *arg);
91 : : static int countitem_compare_count(const void *e1, const void *e2, void *arg);
92 : :
93 : :
94 : : /*
95 : : * array_typanalyze -- typanalyze function for array columns
96 : : */
97 : : Datum
4987 tgl@sss.pgh.pa.us 98 :CBC 3757 : array_typanalyze(PG_FUNCTION_ARGS)
99 : : {
100 : 3757 : 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 [ - + ]: 3757 : if (!std_typanalyze(stats))
4987 tgl@sss.pgh.pa.us 110 :UBC 0 : PG_RETURN_BOOL(false);
111 : :
112 : : /*
113 : : * Check attribute data type is a varlena array (or a domain over one).
114 : : */
4788 tgl@sss.pgh.pa.us 115 :CBC 3757 : element_typeid = get_base_element_type(stats->attrtypid);
116 [ - + ]: 3757 : if (!OidIsValid(element_typeid))
4987 tgl@sss.pgh.pa.us 117 [ # # ]:UBC 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 : : */
4987 tgl@sss.pgh.pa.us 124 :CBC 3757 : typentry = lookup_type_cache(element_typeid,
125 : : TYPECACHE_EQ_OPR |
126 : : TYPECACHE_CMP_PROC_FINFO |
127 : : TYPECACHE_HASH_PROC_FINFO);
128 : :
129 [ + + ]: 3757 : if (!OidIsValid(typentry->eq_opr) ||
130 [ + + ]: 3670 : !OidIsValid(typentry->cmp_proc_finfo.fn_oid) ||
131 [ - + ]: 2457 : !OidIsValid(typentry->hash_proc_finfo.fn_oid))
132 : 1300 : PG_RETURN_BOOL(true);
133 : :
134 : : /* Store our findings for use by compute_array_stats() */
135 : 2457 : extra_data = (ArrayAnalyzeExtraData *) palloc(sizeof(ArrayAnalyzeExtraData));
136 : 2457 : extra_data->type_id = typentry->type_id;
137 : 2457 : extra_data->eq_opr = typentry->eq_opr;
2510 138 : 2457 : extra_data->coll_id = stats->attrcollid; /* collation we should use */
4987 139 : 2457 : extra_data->typbyval = typentry->typbyval;
140 : 2457 : extra_data->typlen = typentry->typlen;
141 : 2457 : extra_data->typalign = typentry->typalign;
142 : 2457 : extra_data->cmp = &typentry->cmp_proc_finfo;
143 : 2457 : extra_data->hash = &typentry->hash_proc_finfo;
144 : :
145 : : /* Save old compute_stats and extra_data for scalar statistics ... */
146 : 2457 : extra_data->std_compute_stats = stats->compute_stats;
147 : 2457 : extra_data->std_extra_data = stats->extra_data;
148 : :
149 : : /* ... and replace with our info */
150 : 2457 : stats->compute_stats = compute_array_stats;
151 : 2457 : 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 : 2457 : 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 : 1695 : compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
217 : : int samplerows, double totalrows)
218 : : {
219 : : ArrayAnalyzeExtraData *extra_data;
220 : : int num_mcelem;
221 : 1695 : int null_elem_cnt = 0;
222 : 1695 : int analyzed_rows = 0;
223 : :
224 : : /* This is D from the LC algorithm. */
225 : : HTAB *elements_tab;
226 : : HASHCTL elem_hash_ctl;
227 : : HASH_SEQ_STATUS scan_status;
228 : :
229 : : /* This is the current bucket number from the LC algorithm */
230 : : int b_current;
231 : :
232 : : /* This is 'w' from the LC algorithm */
233 : : int bucket_width;
234 : : int array_no;
235 : : int64 element_no;
236 : : TrackItem *item;
237 : : int slot_idx;
238 : : HTAB *count_tab;
239 : : HASHCTL count_hash_ctl;
240 : : DECountItem *count_item;
241 : :
242 : 1695 : extra_data = (ArrayAnalyzeExtraData *) stats->extra_data;
243 : :
244 : : /*
245 : : * Invoke analyze.c's standard analysis function to create scalar-style
246 : : * stats for the column. It will expect its own extra_data pointer, so
247 : : * temporarily install that.
248 : : */
249 : 1695 : stats->extra_data = extra_data->std_extra_data;
2973 peter_e@gmx.net 250 : 1695 : extra_data->std_compute_stats(stats, fetchfunc, samplerows, totalrows);
4987 tgl@sss.pgh.pa.us 251 : 1695 : stats->extra_data = extra_data;
252 : :
253 : : /*
254 : : * Set up static pointer for use by subroutines. We wait till here in
255 : : * case std_compute_stats somehow recursively invokes us (probably not
256 : : * possible, but ...)
257 : : */
258 : 1695 : array_extra_data = extra_data;
259 : :
260 : : /*
261 : : * We want statistics_target * 10 elements in the MCELEM array. This
262 : : * multiplier is pretty arbitrary, but is meant to reflect the fact that
263 : : * the number of individual elements tracked in pg_statistic ought to be
264 : : * more than the number of values for a simple scalar column.
265 : : */
848 peter@eisentraut.org 266 : 1695 : num_mcelem = stats->attstattarget * 10;
267 : :
268 : : /*
269 : : * We set bucket width equal to num_mcelem / 0.007 as per the comment
270 : : * above.
271 : : */
4987 tgl@sss.pgh.pa.us 272 : 1695 : bucket_width = num_mcelem * 1000 / 7;
273 : :
274 : : /*
275 : : * Create the hashtable. It will be in local memory, so we don't need to
276 : : * worry about overflowing the initial size. Also we don't need to pay any
277 : : * attention to locking and memory management.
278 : : */
279 : 1695 : elem_hash_ctl.keysize = sizeof(Datum);
280 : 1695 : elem_hash_ctl.entrysize = sizeof(TrackItem);
281 : 1695 : elem_hash_ctl.hash = element_hash;
282 : 1695 : elem_hash_ctl.match = element_match;
283 : 1695 : elem_hash_ctl.hcxt = CurrentMemoryContext;
284 : 1695 : elements_tab = hash_create("Analyzed elements table",
285 : : num_mcelem,
286 : : &elem_hash_ctl,
287 : : HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
288 : :
289 : : /* hashtable for array distinct elements counts */
290 : 1695 : count_hash_ctl.keysize = sizeof(int);
291 : 1695 : count_hash_ctl.entrysize = sizeof(DECountItem);
292 : 1695 : count_hash_ctl.hcxt = CurrentMemoryContext;
293 : 1695 : count_tab = hash_create("Array distinct element count table",
294 : : 64,
295 : : &count_hash_ctl,
296 : : HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
297 : :
298 : : /* Initialize counters. */
299 : 1695 : b_current = 1;
300 : 1695 : element_no = 0;
301 : :
302 : : /* Loop over the arrays. */
303 [ + + ]: 2592756 : for (array_no = 0; array_no < samplerows; array_no++)
304 : : {
305 : : Datum value;
306 : : bool isnull;
307 : : ArrayType *array;
308 : : int num_elems;
309 : : Datum *elem_values;
310 : : bool *elem_nulls;
311 : : bool null_present;
312 : : int j;
313 : 2591061 : int64 prev_element_no = element_no;
314 : : int distinct_count;
315 : : bool count_item_found;
316 : :
259 nathan@postgresql.or 317 : 2591061 : vacuum_delay_point(true);
318 : :
4987 tgl@sss.pgh.pa.us 319 : 2591061 : value = fetchfunc(stats, array_no, &isnull);
320 [ + + ]: 2591061 : if (isnull)
321 : : {
322 : : /* ignore arrays that are null overall */
323 : 2308196 : continue;
324 : : }
325 : :
326 : : /* Skip too-large values. */
327 [ - + ]: 282865 : if (toast_raw_datum_size(value) > ARRAY_WIDTH_THRESHOLD)
4987 tgl@sss.pgh.pa.us 328 :UBC 0 : continue;
329 : : else
4987 tgl@sss.pgh.pa.us 330 :CBC 282865 : analyzed_rows++;
331 : :
332 : : /*
333 : : * Now detoast the array if needed, and deconstruct into datums.
334 : : */
335 : 282865 : array = DatumGetArrayTypeP(value);
336 : :
337 [ - + ]: 282865 : Assert(ARR_ELEMTYPE(array) == extra_data->type_id);
338 : 282865 : deconstruct_array(array,
339 : : extra_data->type_id,
340 : 282865 : extra_data->typlen,
341 : 282865 : extra_data->typbyval,
342 : 282865 : extra_data->typalign,
343 : : &elem_values, &elem_nulls, &num_elems);
344 : :
345 : : /*
346 : : * We loop through the elements in the array and add them to our
347 : : * tracking hashtable.
348 : : */
349 : 282865 : null_present = false;
350 [ + + ]: 1112448 : for (j = 0; j < num_elems; j++)
351 : : {
352 : : Datum elem_value;
353 : : bool found;
354 : :
355 : : /* No null element processing other than flag setting here */
356 [ + + ]: 829583 : if (elem_nulls[j])
357 : : {
358 : 24 : null_present = true;
359 : 78017 : continue;
360 : : }
361 : :
362 : : /* Lookup current element in hashtable, adding it if new */
363 : 829559 : elem_value = elem_values[j];
364 : 829559 : item = (TrackItem *) hash_search(elements_tab,
365 : : &elem_value,
366 : : HASH_ENTER, &found);
367 : :
368 [ + + ]: 829559 : if (found)
369 : : {
370 : : /* The element value is already on the tracking list */
371 : :
372 : : /*
373 : : * The operators we assist ignore duplicate array elements, so
374 : : * count a given distinct element only once per array.
375 : : */
376 [ + + ]: 656717 : if (item->last_container == array_no)
377 : 77993 : continue;
378 : :
379 : 578724 : item->frequency++;
380 : 578724 : item->last_container = array_no;
381 : : }
382 : : else
383 : : {
384 : : /* Initialize new tracking list element */
385 : :
386 : : /*
387 : : * If element type is pass-by-reference, we must copy it into
388 : : * palloc'd space, so that we can release the array below. (We
389 : : * do this so that the space needed for element values is
390 : : * limited by the size of the hashtable; if we kept all the
391 : : * array values around, it could be much more.)
392 : : */
393 : 345684 : item->key = datumCopy(elem_value,
394 : 172842 : extra_data->typbyval,
395 : 172842 : extra_data->typlen);
396 : :
397 : 172842 : item->frequency = 1;
398 : 172842 : item->delta = b_current - 1;
399 : 172842 : item->last_container = array_no;
400 : : }
401 : :
402 : : /* element_no is the number of elements processed (ie N) */
403 : 751566 : element_no++;
404 : :
405 : : /* We prune the D structure after processing each bucket */
406 [ - + ]: 751566 : if (element_no % bucket_width == 0)
407 : : {
4987 tgl@sss.pgh.pa.us 408 :UBC 0 : prune_element_hashtable(elements_tab, b_current);
409 : 0 : b_current++;
410 : : }
411 : : }
412 : :
413 : : /* Count null element presence once per array. */
4987 tgl@sss.pgh.pa.us 414 [ + + ]:CBC 282865 : if (null_present)
415 : 24 : null_elem_cnt++;
416 : :
417 : : /* Update frequency of the particular array distinct element count. */
418 : 282865 : distinct_count = (int) (element_no - prev_element_no);
419 : 282865 : count_item = (DECountItem *) hash_search(count_tab, &distinct_count,
420 : : HASH_ENTER,
421 : : &count_item_found);
422 : :
423 [ + + ]: 282865 : if (count_item_found)
424 : 279358 : count_item->frequency++;
425 : : else
426 : 3507 : count_item->frequency = 1;
427 : :
428 : : /* Free memory allocated while detoasting. */
429 [ + + ]: 282865 : if (PointerGetDatum(array) != value)
430 : 264708 : pfree(array);
431 : 282865 : pfree(elem_values);
432 : 282865 : pfree(elem_nulls);
433 : : }
434 : :
435 : : /* Skip pg_statistic slots occupied by standard statistics */
436 : 1695 : slot_idx = 0;
437 [ + - + + ]: 3125 : while (slot_idx < STATISTIC_NUM_SLOTS && stats->stakind[slot_idx] != 0)
438 : 1430 : slot_idx++;
439 [ - + ]: 1695 : if (slot_idx > STATISTIC_NUM_SLOTS - 2)
4987 tgl@sss.pgh.pa.us 440 [ # # ]:UBC 0 : elog(ERROR, "insufficient pg_statistic slots for array stats");
441 : :
442 : : /* We can only compute real stats if we found some non-null values. */
4987 tgl@sss.pgh.pa.us 443 [ + + ]:CBC 1695 : if (analyzed_rows > 0)
444 : : {
445 : 537 : int nonnull_cnt = analyzed_rows;
446 : : int count_items_count;
447 : : int i;
448 : : TrackItem **sort_table;
449 : : int track_len;
450 : : int64 cutoff_freq;
451 : : int64 minfreq,
452 : : maxfreq;
453 : :
454 : : /*
455 : : * We assume the standard stats code already took care of setting
456 : : * stats_valid, stanullfrac, stawidth, stadistinct. We'd have to
457 : : * re-compute those values if we wanted to not store the standard
458 : : * stats.
459 : : */
460 : :
461 : : /*
462 : : * Construct an array of the interesting hashtable items, that is,
463 : : * those meeting the cutoff frequency (s - epsilon)*N. Also identify
464 : : * the maximum frequency among these items.
465 : : *
466 : : * Since epsilon = s/10 and bucket_width = 1/epsilon, the cutoff
467 : : * frequency is 9*N / bucket_width.
468 : : */
469 : 537 : cutoff_freq = 9 * element_no / bucket_width;
470 : :
471 : 537 : i = hash_get_num_entries(elements_tab); /* surely enough space */
472 : 537 : sort_table = (TrackItem **) palloc(sizeof(TrackItem *) * i);
473 : :
474 : 537 : hash_seq_init(&scan_status, elements_tab);
475 : 537 : track_len = 0;
476 : 537 : maxfreq = 0;
477 [ + + ]: 173916 : while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
478 : : {
479 [ + + ]: 172842 : if (item->frequency > cutoff_freq)
480 : : {
481 : 64692 : sort_table[track_len++] = item;
482 : 64692 : maxfreq = Max(maxfreq, item->frequency);
483 : : }
484 : : }
485 [ - + ]: 537 : Assert(track_len <= i);
486 : :
487 : : /* emit some statistics for debug purposes */
488 [ - + ]: 537 : elog(DEBUG3, "compute_array_stats: target # mces = %d, "
489 : : "bucket width = %d, "
490 : : "# elements = " INT64_FORMAT ", hashtable size = %d, "
491 : : "usable entries = %d",
492 : : num_mcelem, bucket_width, element_no, i, track_len);
493 : :
494 : : /*
495 : : * If we obtained more elements than we really want, get rid of those
496 : : * with least frequencies. The easiest way is to qsort the array into
497 : : * descending frequency order and truncate the array.
498 : : *
499 : : * If we did not find more elements than we want, then it is safe to
500 : : * assume that the stored MCE array will contain every element with
501 : : * frequency above the cutoff. In that case, rather than storing the
502 : : * smallest frequency we are keeping, we want to store the minimum
503 : : * frequency that would have been accepted as a valid MCE. The
504 : : * selectivity functions can assume that that is an upper bound on the
505 : : * frequency of elements not present in the array.
506 : : *
507 : : * If we found no candidate MCEs at all, we still want to record the
508 : : * cutoff frequency, since it's still valid to assume that no element
509 : : * has frequency more than that.
510 : : */
511 [ + + ]: 537 : if (num_mcelem < track_len)
512 : : {
1204 513 : 14 : qsort_interruptible(sort_table, track_len, sizeof(TrackItem *),
514 : : trackitem_compare_frequencies_desc, NULL);
515 : : /* set minfreq to the smallest frequency we're keeping */
4987 516 : 14 : minfreq = sort_table[num_mcelem - 1]->frequency;
517 : : }
518 : : else
519 : : {
520 : 523 : num_mcelem = track_len;
521 : : /* set minfreq to the minimum frequency above the cutoff */
38 tgl@sss.pgh.pa.us 522 :GNC 523 : minfreq = cutoff_freq + 1;
523 : : /* ensure maxfreq is nonzero, too */
524 [ - + ]: 523 : if (track_len == 0)
38 tgl@sss.pgh.pa.us 525 :UNC 0 : maxfreq = minfreq;
526 : : }
527 : :
528 : : /* Generate MCELEM slot entry */
38 tgl@sss.pgh.pa.us 529 [ + - ]:GNC 537 : if (num_mcelem >= 0)
530 : : {
531 : : MemoryContext old_context;
532 : : Datum *mcelem_values;
533 : : float4 *mcelem_freqs;
534 : :
535 : : /*
536 : : * We want to store statistics sorted on the element value using
537 : : * the element type's default comparison function. This permits
538 : : * fast binary searches in selectivity estimation functions.
539 : : */
1204 tgl@sss.pgh.pa.us 540 :CBC 537 : qsort_interruptible(sort_table, num_mcelem, sizeof(TrackItem *),
541 : : trackitem_compare_element, NULL);
542 : :
543 : : /* Must copy the target values into anl_context */
4987 544 : 537 : old_context = MemoryContextSwitchTo(stats->anl_context);
545 : :
546 : : /*
547 : : * We sorted statistics on the element value, but we want to be
548 : : * able to find the minimal and maximal frequencies without going
549 : : * through all the values. We also want the frequency of null
550 : : * elements. Store these three values at the end of mcelem_freqs.
551 : : */
552 : 537 : mcelem_values = (Datum *) palloc(num_mcelem * sizeof(Datum));
553 : 537 : mcelem_freqs = (float4 *) palloc((num_mcelem + 3) * sizeof(float4));
554 : :
555 : : /*
556 : : * See comments above about use of nonnull_cnt as the divisor for
557 : : * the final frequency estimates.
558 : : */
559 [ + + ]: 58114 : for (i = 0; i < num_mcelem; i++)
560 : : {
1119 drowley@postgresql.o 561 : 57577 : TrackItem *titem = sort_table[i];
562 : :
563 : 115154 : mcelem_values[i] = datumCopy(titem->key,
4987 tgl@sss.pgh.pa.us 564 : 57577 : extra_data->typbyval,
565 : 57577 : extra_data->typlen);
1119 drowley@postgresql.o 566 : 57577 : mcelem_freqs[i] = (double) titem->frequency /
4987 tgl@sss.pgh.pa.us 567 : 57577 : (double) nonnull_cnt;
568 : : }
569 : 537 : mcelem_freqs[i++] = (double) minfreq / (double) nonnull_cnt;
570 : 537 : mcelem_freqs[i++] = (double) maxfreq / (double) nonnull_cnt;
571 : 537 : mcelem_freqs[i++] = (double) null_elem_cnt / (double) nonnull_cnt;
572 : :
573 : 537 : MemoryContextSwitchTo(old_context);
574 : :
575 : 537 : stats->stakind[slot_idx] = STATISTIC_KIND_MCELEM;
576 : 537 : stats->staop[slot_idx] = extra_data->eq_opr;
2510 577 : 537 : stats->stacoll[slot_idx] = extra_data->coll_id;
4987 578 : 537 : stats->stanumbers[slot_idx] = mcelem_freqs;
579 : : /* See above comment about extra stanumber entries */
580 : 537 : stats->numnumbers[slot_idx] = num_mcelem + 3;
581 : 537 : stats->stavalues[slot_idx] = mcelem_values;
582 : 537 : stats->numvalues[slot_idx] = num_mcelem;
583 : : /* We are storing values of element type */
584 : 537 : stats->statypid[slot_idx] = extra_data->type_id;
585 : 537 : stats->statyplen[slot_idx] = extra_data->typlen;
586 : 537 : stats->statypbyval[slot_idx] = extra_data->typbyval;
587 : 537 : stats->statypalign[slot_idx] = extra_data->typalign;
588 : 537 : slot_idx++;
589 : : }
590 : :
591 : : /* Generate DECHIST slot entry */
592 : 537 : count_items_count = hash_get_num_entries(count_tab);
593 [ + - ]: 537 : if (count_items_count > 0)
594 : : {
848 peter@eisentraut.org 595 : 537 : int num_hist = stats->attstattarget;
596 : : DECountItem **sorted_count_items;
597 : : int j;
598 : : int delta;
599 : : int64 frac;
600 : : float4 *hist;
601 : :
602 : : /* num_hist must be at least 2 for the loop below to work */
4987 tgl@sss.pgh.pa.us 603 : 537 : num_hist = Max(num_hist, 2);
604 : :
605 : : /*
606 : : * Create an array of DECountItem pointers, and sort them into
607 : : * increasing count order.
608 : : */
609 : : sorted_count_items = (DECountItem **)
610 : 537 : palloc(sizeof(DECountItem *) * count_items_count);
611 : 537 : hash_seq_init(&scan_status, count_tab);
4986 612 : 537 : j = 0;
4987 613 [ + + ]: 4044 : while ((count_item = (DECountItem *) hash_seq_search(&scan_status)) != NULL)
614 : : {
4986 615 : 3507 : sorted_count_items[j++] = count_item;
616 : : }
1204 617 : 537 : qsort_interruptible(sorted_count_items, count_items_count,
618 : : sizeof(DECountItem *),
619 : : countitem_compare_count, NULL);
620 : :
621 : : /*
622 : : * Prepare to fill stanumbers with the histogram, followed by the
623 : : * average count. This array must be stored in anl_context.
624 : : */
625 : : hist = (float4 *)
4987 626 : 537 : MemoryContextAlloc(stats->anl_context,
627 : 537 : sizeof(float4) * (num_hist + 1));
628 : 537 : hist[num_hist] = (double) element_no / (double) nonnull_cnt;
629 : :
630 : : /*----------
631 : : * Construct the histogram of distinct-element counts (DECs).
632 : : *
633 : : * The object of this loop is to copy the min and max DECs to
634 : : * hist[0] and hist[num_hist - 1], along with evenly-spaced DECs
635 : : * in between (where "evenly-spaced" is with reference to the
636 : : * whole input population of arrays). If we had a complete sorted
637 : : * array of DECs, one per analyzed row, the i'th hist value would
638 : : * come from DECs[i * (analyzed_rows - 1) / (num_hist - 1)]
639 : : * (compare the histogram-making loop in compute_scalar_stats()).
640 : : * But instead of that we have the sorted_count_items[] array,
641 : : * which holds unique DEC values with their frequencies (that is,
642 : : * a run-length-compressed version of the full array). So we
643 : : * control advancing through sorted_count_items[] with the
644 : : * variable "frac", which is defined as (x - y) * (num_hist - 1),
645 : : * where x is the index in the notional DECs array corresponding
646 : : * to the start of the next sorted_count_items[] element's run,
647 : : * and y is the index in DECs from which we should take the next
648 : : * histogram value. We have to advance whenever x <= y, that is
649 : : * frac <= 0. The x component is the sum of the frequencies seen
650 : : * so far (up through the current sorted_count_items[] element),
651 : : * and of course y * (num_hist - 1) = i * (analyzed_rows - 1),
652 : : * per the subscript calculation above. (The subscript calculation
653 : : * implies dropping any fractional part of y; in this formulation
654 : : * that's handled by not advancing until frac reaches 1.)
655 : : *
656 : : * Even though frac has a bounded range, it could overflow int32
657 : : * when working with very large statistics targets, so we do that
658 : : * math in int64.
659 : : *----------
660 : : */
661 : 537 : delta = analyzed_rows - 1;
4986 662 : 537 : j = 0; /* current index in sorted_count_items */
663 : : /* Initialize frac for sorted_count_items[0]; y is initially 0 */
664 : 537 : frac = (int64) sorted_count_items[0]->frequency * (num_hist - 1);
4987 665 [ + + ]: 51417 : for (i = 0; i < num_hist; i++)
666 : : {
667 [ + + ]: 53850 : while (frac <= 0)
668 : : {
669 : : /* Advance, and update x component of frac */
4986 670 : 2970 : j++;
671 : 2970 : frac += (int64) sorted_count_items[j]->frequency * (num_hist - 1);
672 : : }
673 : 50880 : hist[i] = sorted_count_items[j]->count;
4888 bruce@momjian.us 674 : 50880 : frac -= delta; /* update y for upcoming i increment */
675 : : }
4986 tgl@sss.pgh.pa.us 676 [ - + ]: 537 : Assert(j == count_items_count - 1);
677 : :
4987 678 : 537 : stats->stakind[slot_idx] = STATISTIC_KIND_DECHIST;
679 : 537 : stats->staop[slot_idx] = extra_data->eq_opr;
2510 680 : 537 : stats->stacoll[slot_idx] = extra_data->coll_id;
4987 681 : 537 : stats->stanumbers[slot_idx] = hist;
682 : 537 : stats->numnumbers[slot_idx] = num_hist + 1;
683 : 537 : slot_idx++;
684 : : }
685 : : }
686 : :
687 : : /*
688 : : * We don't need to bother cleaning up any of our temporary palloc's. The
689 : : * hashtable should also go away, as it used a child memory context.
690 : : */
691 : 1695 : }
692 : :
693 : : /*
694 : : * A function to prune the D structure from the Lossy Counting algorithm.
695 : : * Consult compute_tsvector_stats() for wider explanation.
696 : : */
697 : : static void
4987 tgl@sss.pgh.pa.us 698 :UBC 0 : prune_element_hashtable(HTAB *elements_tab, int b_current)
699 : : {
700 : : HASH_SEQ_STATUS scan_status;
701 : : TrackItem *item;
702 : :
703 : 0 : hash_seq_init(&scan_status, elements_tab);
704 [ # # ]: 0 : while ((item = (TrackItem *) hash_seq_search(&scan_status)) != NULL)
705 : : {
706 [ # # ]: 0 : if (item->frequency + item->delta <= b_current)
707 : : {
708 : 0 : Datum value = item->key;
709 : :
995 peter@eisentraut.org 710 [ # # ]: 0 : if (hash_search(elements_tab, &item->key,
711 : : HASH_REMOVE, NULL) == NULL)
4987 tgl@sss.pgh.pa.us 712 [ # # ]: 0 : elog(ERROR, "hash table corrupted");
713 : : /* We should free memory if element is not passed by value */
714 [ # # ]: 0 : if (!array_extra_data->typbyval)
715 : 0 : pfree(DatumGetPointer(value));
716 : : }
717 : : }
718 : 0 : }
719 : :
720 : : /*
721 : : * Hash function for elements.
722 : : *
723 : : * We use the element type's default hash opclass, and the column collation
724 : : * if the type is collation-sensitive.
725 : : */
726 : : static uint32
4987 tgl@sss.pgh.pa.us 727 :CBC 829559 : element_hash(const void *key, Size keysize)
728 : : {
729 : 829559 : Datum d = *((const Datum *) key);
730 : : Datum h;
731 : :
2510 732 : 829559 : h = FunctionCall1Coll(array_extra_data->hash,
733 : 829559 : array_extra_data->coll_id,
734 : : d);
4987 735 : 829559 : return DatumGetUInt32(h);
736 : : }
737 : :
738 : : /*
739 : : * Matching function for elements, to be used in hashtable lookups.
740 : : */
741 : : static int
742 : 657614 : element_match(const void *key1, const void *key2, Size keysize)
743 : : {
744 : : /* The keysize parameter is superfluous here */
745 : 657614 : return element_compare(key1, key2);
746 : : }
747 : :
748 : : /*
749 : : * Comparison function for elements.
750 : : *
751 : : * We use the element type's default btree opclass, and the column collation
752 : : * if the type is collation-sensitive.
753 : : *
754 : : * XXX consider using SortSupport infrastructure
755 : : */
756 : : static int
757 : 1161891 : element_compare(const void *key1, const void *key2)
758 : : {
759 : 1161891 : Datum d1 = *((const Datum *) key1);
760 : 1161891 : Datum d2 = *((const Datum *) key2);
761 : : Datum c;
762 : :
2510 763 : 1161891 : c = FunctionCall2Coll(array_extra_data->cmp,
764 : 1161891 : array_extra_data->coll_id,
765 : : d1, d2);
4987 766 : 1161891 : return DatumGetInt32(c);
767 : : }
768 : :
769 : : /*
770 : : * Comparator for sorting TrackItems by frequencies (descending sort)
771 : : */
772 : : static int
1204 773 : 17594 : trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg)
774 : : {
3051 775 : 17594 : const TrackItem *const *t1 = (const TrackItem *const *) e1;
776 : 17594 : const TrackItem *const *t2 = (const TrackItem *const *) e2;
777 : :
4987 778 : 17594 : return (*t2)->frequency - (*t1)->frequency;
779 : : }
780 : :
781 : : /*
782 : : * Comparator for sorting TrackItems by element values
783 : : */
784 : : static int
1204 785 : 504277 : trackitem_compare_element(const void *e1, const void *e2, void *arg)
786 : : {
3051 787 : 504277 : const TrackItem *const *t1 = (const TrackItem *const *) e1;
788 : 504277 : const TrackItem *const *t2 = (const TrackItem *const *) e2;
789 : :
4987 790 : 504277 : return element_compare(&(*t1)->key, &(*t2)->key);
791 : : }
792 : :
793 : : /*
794 : : * Comparator for sorting DECountItems by count
795 : : */
796 : : static int
1204 797 : 10656 : countitem_compare_count(const void *e1, const void *e2, void *arg)
798 : : {
3051 799 : 10656 : const DECountItem *const *t1 = (const DECountItem *const *) e1;
800 : 10656 : const DECountItem *const *t2 = (const DECountItem *const *) e2;
801 : :
4987 802 [ + + ]: 10656 : if ((*t1)->count < (*t2)->count)
803 : 5069 : return -1;
804 [ - + ]: 5587 : else if ((*t1)->count == (*t2)->count)
4987 tgl@sss.pgh.pa.us 805 :UBC 0 : return 0;
806 : : else
4987 tgl@sss.pgh.pa.us 807 :CBC 5587 : return 1;
808 : : }
|
