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