1/*-------------------------------------------------------------------------
2 *
3 * array_selfuncs.c
4 * Functions for selectivity estimation of array operators
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_selfuncs.c
12 *
13 *-------------------------------------------------------------------------
14 */
15#include "postgres.h"
16
17#include <math.h>
18
19#include "access/htup_details.h"
20#include "catalog/pg_collation.h"
21#include "catalog/pg_operator.h"
22#include "catalog/pg_statistic.h"
23#include "utils/array.h"
24#include "utils/builtins.h"
25#include "utils/lsyscache.h"
26#include "utils/selfuncs.h"
27#include "utils/typcache.h"
28
29
30/* Default selectivity constant for "@>" and "<@" operators */
31#define DEFAULT_CONTAIN_SEL 0.005
32
33/* Default selectivity constant for "&&" operator */
34#define DEFAULT_OVERLAP_SEL 0.01
35
36/* Default selectivity for given operator */
37#define DEFAULT_SEL(operator) \
38 ((operator) == OID_ARRAY_OVERLAP_OP ? \
39 DEFAULT_OVERLAP_SEL : DEFAULT_CONTAIN_SEL)
40
41static Selectivity calc_arraycontsel(VariableStatData *vardata, Datum constval,
42 Oid elemtype, Oid operator);
43static Selectivity mcelem_array_selec(ArrayType *array,
44 TypeCacheEntry *typentry,
45 Datum *mcelem, int nmcelem,
46 float4 *numbers, int nnumbers,
47 float4 *hist, int nhist,
48 Oid operator);
49static Selectivity mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem,
50 float4 *numbers, int nnumbers,
51 Datum *array_data, int nitems,
52 Oid operator, TypeCacheEntry *typentry);
53static Selectivity mcelem_array_contained_selec(Datum *mcelem, int nmcelem,
54 float4 *numbers, int nnumbers,
55 Datum *array_data, int nitems,
56 float4 *hist, int nhist,
57 Oid operator, TypeCacheEntry *typentry);
58static float *calc_hist(const float4 *hist, int nhist, int n);
59static float *calc_distr(const float *p, int n, int m, float rest);
60static int floor_log2(uint32 n);
61static bool find_next_mcelem(Datum *mcelem, int nmcelem, Datum value,
62 int *index, TypeCacheEntry *typentry);
63static int element_compare(const void *key1, const void *key2, void *arg);
64static int float_compare_desc(const void *key1, const void *key2);
65
66
67/*
68 * scalararraysel_containment
69 * Estimate selectivity of ScalarArrayOpExpr via array containment.
70 *
71 * If we have const =/<> ANY/ALL (array_var) then we can estimate the
72 * selectivity as though this were an array containment operator,
73 * array_var op ARRAY[const].
74 *
75 * scalararraysel() has already verified that the ScalarArrayOpExpr's operator
76 * is the array element type's default equality or inequality operator, and
77 * has aggressively simplified both inputs to constants.
78 *
79 * Returns selectivity (0..1), or -1 if we fail to estimate selectivity.
80 */
81Selectivity
82scalararraysel_containment(PlannerInfo *root,
83 Node *leftop, Node *rightop,
84 Oid elemtype, bool isEquality, bool useOr,
85 int varRelid)
86{
87 Selectivity selec;
88 VariableStatData vardata;
89 Datum constval;
90 TypeCacheEntry *typentry;
91 FmgrInfo *cmpfunc;
92
93 /*
94 * rightop must be a variable, else punt.
95 */
96 examine_variable(root, rightop, varRelid, &vardata);
97 if (!vardata.rel)
98 {
99 ReleaseVariableStats(vardata);
100 return -1.0;
101 }
102
103 /*
104 * leftop must be a constant, else punt.
105 */
106 if (!IsA(leftop, Const))
107 {
108 ReleaseVariableStats(vardata);
109 return -1.0;
110 }
111 if (((Const *) leftop)->constisnull)
112 {
113 /* qual can't succeed if null on left */
114 ReleaseVariableStats(vardata);
115 return (Selectivity) 0.0;
116 }
117 constval = ((Const *) leftop)->constvalue;
118
119 /* Get element type's default comparison function */
120 typentry = lookup_type_cache(elemtype, TYPECACHE_CMP_PROC_FINFO);
121 if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
122 {
123 ReleaseVariableStats(vardata);
124 return -1.0;
125 }
126 cmpfunc = &typentry->cmp_proc_finfo;
127
128 /*
129 * If the operator is <>, swap ANY/ALL, then invert the result later.
130 */
131 if (!isEquality)
132 useOr = !useOr;
133
134 /* Get array element stats for var, if available */
135 if (HeapTupleIsValid(vardata.statsTuple) &&
136 statistic_proc_security_check(&vardata, cmpfunc->fn_oid))
137 {
138 Form_pg_statistic stats;
139 AttStatsSlot sslot;
140 AttStatsSlot hslot;
141
142 stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
143
144 /* MCELEM will be an array of same type as element */
145 if (get_attstatsslot(&sslot, vardata.statsTuple,
146 STATISTIC_KIND_MCELEM, InvalidOid,
147 ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
148 {
149 /* For ALL case, also get histogram of distinct-element counts */
150 if (useOr ||
151 !get_attstatsslot(&hslot, vardata.statsTuple,
152 STATISTIC_KIND_DECHIST, InvalidOid,
153 ATTSTATSSLOT_NUMBERS))
154 memset(&hslot, 0, sizeof(hslot));
155
156 /*
157 * For = ANY, estimate as var @> ARRAY[const].
158 *
159 * For = ALL, estimate as var <@ ARRAY[const].
160 */
161 if (useOr)
162 selec = mcelem_array_contain_overlap_selec(sslot.values,
163 sslot.nvalues,
164 sslot.numbers,
165 sslot.nnumbers,
166 &constval, 1,
167 OID_ARRAY_CONTAINS_OP,
168 typentry);
169 else
170 selec = mcelem_array_contained_selec(sslot.values,
171 sslot.nvalues,
172 sslot.numbers,
173 sslot.nnumbers,
174 &constval, 1,
175 hslot.numbers,
176 hslot.nnumbers,
177 OID_ARRAY_CONTAINED_OP,
178 typentry);
179
180 free_attstatsslot(&hslot);
181 free_attstatsslot(&sslot);
182 }
183 else
184 {
185 /* No most-common-elements info, so do without */
186 if (useOr)
187 selec = mcelem_array_contain_overlap_selec(NULL, 0,
188 NULL, 0,
189 &constval, 1,
190 OID_ARRAY_CONTAINS_OP,
191 typentry);
192 else
193 selec = mcelem_array_contained_selec(NULL, 0,
194 NULL, 0,
195 &constval, 1,
196 NULL, 0,
197 OID_ARRAY_CONTAINED_OP,
198 typentry);
199 }
200
201 /*
202 * MCE stats count only non-null rows, so adjust for null rows.
203 */
204 selec *= (1.0 - stats->stanullfrac);
205 }
206 else
207 {
208 /* No stats at all, so do without */
209 if (useOr)
210 selec = mcelem_array_contain_overlap_selec(NULL, 0,
211 NULL, 0,
212 &constval, 1,
213 OID_ARRAY_CONTAINS_OP,
214 typentry);
215 else
216 selec = mcelem_array_contained_selec(NULL, 0,
217 NULL, 0,
218 &constval, 1,
219 NULL, 0,
220 OID_ARRAY_CONTAINED_OP,
221 typentry);
222 /* we assume no nulls here, so no stanullfrac correction */
223 }
224
225 ReleaseVariableStats(vardata);
226
227 /*
228 * If the operator is <>, invert the results.
229 */
230 if (!isEquality)
231 selec = 1.0 - selec;
232
233 CLAMP_PROBABILITY(selec);
234
235 return selec;
236}
237
238/*
239 * arraycontsel -- restriction selectivity for array @>, &&, <@ operators
240 */
241Datum
242arraycontsel(PG_FUNCTION_ARGS)
243{
244 PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
245 Oid operator = PG_GETARG_OID(1);
246 List *args = (List *) PG_GETARG_POINTER(2);
247 int varRelid = PG_GETARG_INT32(3);
248 VariableStatData vardata;
249 Node *other;
250 bool varonleft;
251 Selectivity selec;
252 Oid element_typeid;
253
254 /*
255 * If expression is not (variable op something) or (something op
256 * variable), then punt and return a default estimate.
257 */
258 if (!get_restriction_variable(root, args, varRelid,
259 &vardata, &other, &varonleft))
260 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
261
262 /*
263 * Can't do anything useful if the something is not a constant, either.
264 */
265 if (!IsA(other, Const))
266 {
267 ReleaseVariableStats(vardata);
268 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
269 }
270
271 /*
272 * The "&&", "@>" and "<@" operators are strict, so we can cope with a
273 * NULL constant right away.
274 */
275 if (((Const *) other)->constisnull)
276 {
277 ReleaseVariableStats(vardata);
278 PG_RETURN_FLOAT8(0.0);
279 }
280
281 /*
282 * If var is on the right, commute the operator, so that we can assume the
283 * var is on the left in what follows.
284 */
285 if (!varonleft)
286 {
287 if (operator == OID_ARRAY_CONTAINS_OP)
288 operator = OID_ARRAY_CONTAINED_OP;
289 else if (operator == OID_ARRAY_CONTAINED_OP)
290 operator = OID_ARRAY_CONTAINS_OP;
291 }
292
293 /*
294 * OK, there's a Var and a Const we're dealing with here. We need the
295 * Const to be an array with same element type as column, else we can't do
296 * anything useful. (Such cases will likely fail at runtime, but here
297 * we'd rather just return a default estimate.)
298 */
299 element_typeid = get_base_element_type(((Const *) other)->consttype);
300 if (element_typeid != InvalidOid &&
301 element_typeid == get_base_element_type(vardata.vartype))
302 {
303 selec = calc_arraycontsel(&vardata, ((Const *) other)->constvalue,
304 element_typeid, operator);
305 }
306 else
307 {
308 selec = DEFAULT_SEL(operator);
309 }
310
311 ReleaseVariableStats(vardata);
312
313 CLAMP_PROBABILITY(selec);
314
315 PG_RETURN_FLOAT8((float8) selec);
316}
317
318/*
319 * arraycontjoinsel -- join selectivity for array @>, &&, <@ operators
320 */
321Datum
322arraycontjoinsel(PG_FUNCTION_ARGS)
323{
324 /* For the moment this is just a stub */
325 Oid operator = PG_GETARG_OID(1);
326
327 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
328}
329
330/*
331 * Calculate selectivity for "arraycolumn @> const", "arraycolumn && const"
332 * or "arraycolumn <@ const" based on the statistics
333 *
334 * This function is mainly responsible for extracting the pg_statistic data
335 * to be used; we then pass the problem on to mcelem_array_selec().
336 */
337static Selectivity
338calc_arraycontsel(VariableStatData *vardata, Datum constval,
339 Oid elemtype, Oid operator)
340{
341 Selectivity selec;
342 TypeCacheEntry *typentry;
343 FmgrInfo *cmpfunc;
344 ArrayType *array;
345
346 /* Get element type's default comparison function */
347 typentry = lookup_type_cache(elemtype, TYPECACHE_CMP_PROC_FINFO);
348 if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
349 return DEFAULT_SEL(operator);
350 cmpfunc = &typentry->cmp_proc_finfo;
351
352 /*
353 * The caller made sure the const is an array with same element type, so
354 * get it now
355 */
356 array = DatumGetArrayTypeP(constval);
357
358 if (HeapTupleIsValid(vardata->statsTuple) &&
359 statistic_proc_security_check(vardata, cmpfunc->fn_oid))
360 {
361 Form_pg_statistic stats;
362 AttStatsSlot sslot;
363 AttStatsSlot hslot;
364
365 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
366
367 /* MCELEM will be an array of same type as column */
368 if (get_attstatsslot(&sslot, vardata->statsTuple,
369 STATISTIC_KIND_MCELEM, InvalidOid,
370 ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
371 {
372 /*
373 * For "array <@ const" case we also need histogram of distinct
374 * element counts.
375 */
376 if (operator != OID_ARRAY_CONTAINED_OP ||
377 !get_attstatsslot(&hslot, vardata->statsTuple,
378 STATISTIC_KIND_DECHIST, InvalidOid,
379 ATTSTATSSLOT_NUMBERS))
380 memset(&hslot, 0, sizeof(hslot));
381
382 /* Use the most-common-elements slot for the array Var. */
383 selec = mcelem_array_selec(array, typentry,
384 sslot.values, sslot.nvalues,
385 sslot.numbers, sslot.nnumbers,
386 hslot.numbers, hslot.nnumbers,
387 operator);
388
389 free_attstatsslot(&hslot);
390 free_attstatsslot(&sslot);
391 }
392 else
393 {
394 /* No most-common-elements info, so do without */
395 selec = mcelem_array_selec(array, typentry,
396 NULL, 0, NULL, 0, NULL, 0,
397 operator);
398 }
399
400 /*
401 * MCE stats count only non-null rows, so adjust for null rows.
402 */
403 selec *= (1.0 - stats->stanullfrac);
404 }
405 else
406 {
407 /* No stats at all, so do without */
408 selec = mcelem_array_selec(array, typentry,
409 NULL, 0, NULL, 0, NULL, 0,
410 operator);
411 /* we assume no nulls here, so no stanullfrac correction */
412 }
413
414 /* If constant was toasted, release the copy we made */
415 if (PointerGetDatum(array) != constval)
416 pfree(array);
417
418 return selec;
419}
420
421/*
422 * Array selectivity estimation based on most common elements statistics
423 *
424 * This function just deconstructs and sorts the array constant's contents,
425 * and then passes the problem on to mcelem_array_contain_overlap_selec or
426 * mcelem_array_contained_selec depending on the operator.
427 */
428static Selectivity
429mcelem_array_selec(ArrayType *array, TypeCacheEntry *typentry,
430 Datum *mcelem, int nmcelem,
431 float4 *numbers, int nnumbers,
432 float4 *hist, int nhist,
433 Oid operator)
434{
435 Selectivity selec;
436 int num_elems;
437 Datum *elem_values;
438 bool *elem_nulls;
439 bool null_present;
440 int nonnull_nitems;
441 int i;
442
443 /*
444 * Prepare constant array data for sorting. Sorting lets us find unique
445 * elements and efficiently merge with the MCELEM array.
446 */
447 deconstruct_array(array,
448 typentry->type_id,
449 typentry->typlen,
450 typentry->typbyval,
451 typentry->typalign,
452 &elem_values, &elem_nulls, &num_elems);
453
454 /* Collapse out any null elements */
455 nonnull_nitems = 0;
456 null_present = false;
457 for (i = 0; i < num_elems; i++)
458 {
459 if (elem_nulls[i])
460 null_present = true;
461 else
462 elem_values[nonnull_nitems++] = elem_values[i];
463 }
464
465 /*
466 * Query "column @> '{anything, null}'" matches nothing. For the other
467 * two operators, presence of a null in the constant can be ignored.
468 */
469 if (null_present && operator == OID_ARRAY_CONTAINS_OP)
470 {
471 pfree(elem_values);
472 pfree(elem_nulls);
473 return (Selectivity) 0.0;
474 }
475
476 /* Sort extracted elements using their default comparison function. */
477 qsort_arg(elem_values, nonnull_nitems, sizeof(Datum),
478 element_compare, typentry);
479
480 /* Separate cases according to operator */
481 if (operator == OID_ARRAY_CONTAINS_OP || operator == OID_ARRAY_OVERLAP_OP)
482 selec = mcelem_array_contain_overlap_selec(mcelem, nmcelem,
483 numbers, nnumbers,
484 elem_values, nonnull_nitems,
485 operator, typentry);
486 else if (operator == OID_ARRAY_CONTAINED_OP)
487 selec = mcelem_array_contained_selec(mcelem, nmcelem,
488 numbers, nnumbers,
489 elem_values, nonnull_nitems,
490 hist, nhist,
491 operator, typentry);
492 else
493 {
494 elog(ERROR, "arraycontsel called for unrecognized operator %u",
495 operator);
496 selec = 0.0; /* keep compiler quiet */
497 }
498
499 pfree(elem_values);
500 pfree(elem_nulls);
501 return selec;
502}
503
504/*
505 * Estimate selectivity of "column @> const" and "column && const" based on
506 * most common element statistics. This estimation assumes element
507 * occurrences are independent.
508 *
509 * mcelem (of length nmcelem) and numbers (of length nnumbers) are from
510 * the array column's MCELEM statistics slot, or are NULL/0 if stats are
511 * not available. array_data (of length nitems) is the constant's elements.
512 *
513 * Both the mcelem and array_data arrays are assumed presorted according
514 * to the element type's cmpfunc. Null elements are not present.
515 *
516 * TODO: this estimate probably could be improved by using the distinct
517 * elements count histogram. For example, excepting the special case of
518 * "column @> '{}'", we can multiply the calculated selectivity by the
519 * fraction of nonempty arrays in the column.
520 */
521static Selectivity
522mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem,
523 float4 *numbers, int nnumbers,
524 Datum *array_data, int nitems,
525 Oid operator, TypeCacheEntry *typentry)
526{
527 Selectivity selec,
528 elem_selec;
529 int mcelem_index,
530 i;
531 bool use_bsearch;
532 float4 minfreq;
533
534 /*
535 * There should be three more Numbers than Values, because the last three
536 * cells should hold minimal and maximal frequency among the non-null
537 * elements, and then the frequency of null elements. Ignore the Numbers
538 * if not right.
539 */
540 if (nnumbers != nmcelem + 3)
541 {
542 numbers = NULL;
543 nnumbers = 0;
544 }
545
546 if (numbers)
547 {
548 /* Grab the lowest observed frequency */
549 minfreq = numbers[nmcelem];
550 }
551 else
552 {
553 /* Without statistics make some default assumptions */
554 minfreq = 2 * (float4) DEFAULT_CONTAIN_SEL;
555 }
556
557 /* Decide whether it is faster to use binary search or not. */
558 if (nitems * floor_log2((uint32) nmcelem) < nmcelem + nitems)
559 use_bsearch = true;
560 else
561 use_bsearch = false;
562
563 if (operator == OID_ARRAY_CONTAINS_OP)
564 {
565 /*
566 * Initial selectivity for "column @> const" query is 1.0, and it will
567 * be decreased with each element of constant array.
568 */
569 selec = 1.0;
570 }
571 else
572 {
573 /*
574 * Initial selectivity for "column && const" query is 0.0, and it will
575 * be increased with each element of constant array.
576 */
577 selec = 0.0;
578 }
579
580 /* Scan mcelem and array in parallel. */
581 mcelem_index = 0;
582 for (i = 0; i < nitems; i++)
583 {
584 bool match = false;
585
586 /* Ignore any duplicates in the array data. */
587 if (i > 0 &&
588 element_compare(&array_data[i - 1], &array_data[i], typentry) == 0)
589 continue;
590
591 /* Find the smallest MCELEM >= this array item. */
592 if (use_bsearch)
593 {
594 match = find_next_mcelem(mcelem, nmcelem, array_data[i],
595 &mcelem_index, typentry);
596 }
597 else
598 {
599 while (mcelem_index < nmcelem)
600 {
601 int cmp = element_compare(&mcelem[mcelem_index],
602 &array_data[i],
603 typentry);
604
605 if (cmp < 0)
606 mcelem_index++;
607 else
608 {
609 if (cmp == 0)
610 match = true; /* mcelem is found */
611 break;
612 }
613 }
614 }
615
616 if (match && numbers)
617 {
618 /* MCELEM matches the array item; use its frequency. */
619 elem_selec = numbers[mcelem_index];
620 mcelem_index++;
621 }
622 else
623 {
624 /*
625 * The element is not in MCELEM. Punt, but assume that the
626 * selectivity cannot be more than minfreq / 2.
627 */
628 elem_selec = Min(DEFAULT_CONTAIN_SEL, minfreq / 2);
629 }
630
631 /*
632 * Update overall selectivity using the current element's selectivity
633 * and an assumption of element occurrence independence.
634 */
635 if (operator == OID_ARRAY_CONTAINS_OP)
636 selec *= elem_selec;
637 else
638 selec = selec + elem_selec - selec * elem_selec;
639
640 /* Clamp intermediate results to stay sane despite roundoff error */
641 CLAMP_PROBABILITY(selec);
642 }
643
644 return selec;
645}
646
647/*
648 * Estimate selectivity of "column <@ const" based on most common element
649 * statistics.
650 *
651 * mcelem (of length nmcelem) and numbers (of length nnumbers) are from
652 * the array column's MCELEM statistics slot, or are NULL/0 if stats are
653 * not available. array_data (of length nitems) is the constant's elements.
654 * hist (of length nhist) is from the array column's DECHIST statistics slot,
655 * or is NULL/0 if those stats are not available.
656 *
657 * Both the mcelem and array_data arrays are assumed presorted according
658 * to the element type's cmpfunc. Null elements are not present.
659 *
660 * Independent element occurrence would imply a particular distribution of
661 * distinct element counts among matching rows. Real data usually falsifies
662 * that assumption. For example, in a set of 11-element integer arrays having
663 * elements in the range [0..10], element occurrences are typically not
664 * independent. If they were, a sufficiently-large set would include all
665 * distinct element counts 0 through 11. We correct for this using the
666 * histogram of distinct element counts.
667 *
668 * In the "column @> const" and "column && const" cases, we usually have a
669 * "const" with low number of elements (otherwise we have selectivity close
670 * to 0 or 1 respectively). That's why the effect of dependence related
671 * to distinct element count distribution is negligible there. In the
672 * "column <@ const" case, number of elements is usually high (otherwise we
673 * have selectivity close to 0). That's why we should do a correction with
674 * the array distinct element count distribution here.
675 *
676 * Using the histogram of distinct element counts produces a different
677 * distribution law than independent occurrences of elements. This
678 * distribution law can be described as follows:
679 *
680 * P(o1, o2, ..., on) = f1^o1 * (1 - f1)^(1 - o1) * f2^o2 *
681 * (1 - f2)^(1 - o2) * ... * fn^on * (1 - fn)^(1 - on) * hist[m] / ind[m]
682 *
683 * where:
684 * o1, o2, ..., on - occurrences of elements 1, 2, ..., n
685 * (1 - occurrence, 0 - no occurrence) in row
686 * f1, f2, ..., fn - frequencies of elements 1, 2, ..., n
687 * (scalar values in [0..1]) according to collected statistics
688 * m = o1 + o2 + ... + on = total number of distinct elements in row
689 * hist[m] - histogram data for occurrence of m elements.
690 * ind[m] - probability of m occurrences from n events assuming their
691 * probabilities to be equal to frequencies of array elements.
692 *
693 * ind[m] = sum(f1^o1 * (1 - f1)^(1 - o1) * f2^o2 * (1 - f2)^(1 - o2) *
694 * ... * fn^on * (1 - fn)^(1 - on), o1, o2, ..., on) | o1 + o2 + .. on = m
695 */
696static Selectivity
697mcelem_array_contained_selec(Datum *mcelem, int nmcelem,
698 float4 *numbers, int nnumbers,
699 Datum *array_data, int nitems,
700 float4 *hist, int nhist,
701 Oid operator, TypeCacheEntry *typentry)
702{
703 int mcelem_index,
704 i,
705 unique_nitems = 0;
706 float selec,
707 minfreq,
708 nullelem_freq;
709 float *dist,
710 *mcelem_dist,
711 *hist_part;
712 float avg_count,
713 mult,
714 rest;
715 float *elem_selec;
716
717 /*
718 * There should be three more Numbers than Values in the MCELEM slot,
719 * because the last three cells should hold minimal and maximal frequency
720 * among the non-null elements, and then the frequency of null elements.
721 * Punt if not right, because we can't do much without the element freqs.
722 */
723 if (numbers == NULL || nnumbers != nmcelem + 3)
724 return DEFAULT_CONTAIN_SEL;
725
726 /* Can't do much without a count histogram, either */
727 if (hist == NULL || nhist < 3)
728 return DEFAULT_CONTAIN_SEL;
729
730 /*
731 * Grab some of the summary statistics that compute_array_stats() stores:
732 * lowest frequency, frequency of null elements, and average distinct
733 * element count.
734 */
735 minfreq = numbers[nmcelem];
736 nullelem_freq = numbers[nmcelem + 2];
737 avg_count = hist[nhist - 1];
738
739 /*
740 * "rest" will be the sum of the frequencies of all elements not
741 * represented in MCELEM. The average distinct element count is the sum
742 * of the frequencies of *all* elements. Begin with that; we will proceed
743 * to subtract the MCELEM frequencies.
744 */
745 rest = avg_count;
746
747 /*
748 * mult is a multiplier representing estimate of probability that each
749 * mcelem that is not present in constant doesn't occur.
750 */
751 mult = 1.0f;
752
753 /*
754 * elem_selec is array of estimated frequencies for elements in the
755 * constant.
756 */
757 elem_selec = (float *) palloc(sizeof(float) * nitems);
758
759 /* Scan mcelem and array in parallel. */
760 mcelem_index = 0;
761 for (i = 0; i < nitems; i++)
762 {
763 bool match = false;
764
765 /* Ignore any duplicates in the array data. */
766 if (i > 0 &&
767 element_compare(&array_data[i - 1], &array_data[i], typentry) == 0)
768 continue;
769
770 /*
771 * Iterate over MCELEM until we find an entry greater than or equal to
772 * this element of the constant. Update "rest" and "mult" for mcelem
773 * entries skipped over.
774 */
775 while (mcelem_index < nmcelem)
776 {
777 int cmp = element_compare(&mcelem[mcelem_index],
778 &array_data[i],
779 typentry);
780
781 if (cmp < 0)
782 {
783 mult *= (1.0f - numbers[mcelem_index]);
784 rest -= numbers[mcelem_index];
785 mcelem_index++;
786 }
787 else
788 {
789 if (cmp == 0)
790 match = true; /* mcelem is found */
791 break;
792 }
793 }
794
795 if (match)
796 {
797 /* MCELEM matches the array item. */
798 elem_selec[unique_nitems] = numbers[mcelem_index];
799 /* "rest" is decremented for all mcelems, matched or not */
800 rest -= numbers[mcelem_index];
801 mcelem_index++;
802 }
803 else
804 {
805 /*
806 * The element is not in MCELEM. Punt, but assume that the
807 * selectivity cannot be more than minfreq / 2.
808 */
809 elem_selec[unique_nitems] = Min(DEFAULT_CONTAIN_SEL,
810 minfreq / 2);
811 }
812
813 unique_nitems++;
814 }
815
816 /*
817 * If we handled all constant elements without exhausting the MCELEM
818 * array, finish walking it to complete calculation of "rest" and "mult".
819 */
820 while (mcelem_index < nmcelem)
821 {
822 mult *= (1.0f - numbers[mcelem_index]);
823 rest -= numbers[mcelem_index];
824 mcelem_index++;
825 }
826
827 /*
828 * The presence of many distinct rare elements materially decreases
829 * selectivity. Use the Poisson distribution to estimate the probability
830 * of a column value having zero occurrences of such elements. See above
831 * for the definition of "rest".
832 */
833 mult *= exp(-rest);
834
835 /*----------
836 * Using the distinct element count histogram requires
837 * O(unique_nitems * (nmcelem + unique_nitems))
838 * operations. Beyond a certain computational cost threshold, it's
839 * reasonable to sacrifice accuracy for decreased planning time. We limit
840 * the number of operations to EFFORT * nmcelem; since nmcelem is limited
841 * by the column's statistics target, the work done is user-controllable.
842 *
843 * If the number of operations would be too large, we can reduce it
844 * without losing all accuracy by reducing unique_nitems and considering
845 * only the most-common elements of the constant array. To make the
846 * results exactly match what we would have gotten with only those
847 * elements to start with, we'd have to remove any discarded elements'
848 * frequencies from "mult", but since this is only an approximation
849 * anyway, we don't bother with that. Therefore it's sufficient to qsort
850 * elem_selec[] and take the largest elements. (They will no longer match
851 * up with the elements of array_data[], but we don't care.)
852 *----------
853 */
854#define EFFORT 100
855
856 if ((nmcelem + unique_nitems) > 0 &&
857 unique_nitems > EFFORT * nmcelem / (nmcelem + unique_nitems))
858 {
859 /*
860 * Use the quadratic formula to solve for largest allowable N. We
861 * have A = 1, B = nmcelem, C = - EFFORT * nmcelem.
862 */
863 double b = (double) nmcelem;
864 int n;
865
866 n = (int) ((sqrt(b * b + 4 * EFFORT * b) - b) / 2);
867
868 /* Sort, then take just the first n elements */
869 qsort(elem_selec, unique_nitems, sizeof(float),
870 float_compare_desc);
871 unique_nitems = n;
872 }
873
874 /*
875 * Calculate probabilities of each distinct element count for both mcelems
876 * and constant elements. At this point, assume independent element
877 * occurrence.
878 */
879 dist = calc_distr(elem_selec, unique_nitems, unique_nitems, 0.0f);
880 mcelem_dist = calc_distr(numbers, nmcelem, unique_nitems, rest);
881
882 /* ignore hist[nhist-1], which is the average not a histogram member */
883 hist_part = calc_hist(hist, nhist - 1, unique_nitems);
884
885 selec = 0.0f;
886 for (i = 0; i <= unique_nitems; i++)
887 {
888 /*
889 * mult * dist[i] / mcelem_dist[i] gives us probability of qual
890 * matching from assumption of independent element occurrence with the
891 * condition that distinct element count = i.
892 */
893 if (mcelem_dist[i] > 0)
894 selec += hist_part[i] * mult * dist[i] / mcelem_dist[i];
895 }
896
897 pfree(dist);
898 pfree(mcelem_dist);
899 pfree(hist_part);
900 pfree(elem_selec);
901
902 /* Take into account occurrence of NULL element. */
903 selec *= (1.0f - nullelem_freq);
904
905 CLAMP_PROBABILITY(selec);
906
907 return selec;
908}
909
910/*
911 * Calculate the first n distinct element count probabilities from a
912 * histogram of distinct element counts.
913 *
914 * Returns a palloc'd array of n+1 entries, with array[k] being the
915 * probability of element count k, k in [0..n].
916 *
917 * We assume that a histogram box with bounds a and b gives 1 / ((b - a + 1) *
918 * (nhist - 1)) probability to each value in (a,b) and an additional half of
919 * that to a and b themselves.
920 */
921static float *
922calc_hist(const float4 *hist, int nhist, int n)
923{
924 float *hist_part;
925 int k,
926 i = 0;
927 float prev_interval = 0,
928 next_interval;
929 float frac;
930
931 hist_part = (float *) palloc((n + 1) * sizeof(float));
932
933 /*
934 * frac is a probability contribution for each interval between histogram
935 * values. We have nhist - 1 intervals, so contribution of each one will
936 * be 1 / (nhist - 1).
937 */
938 frac = 1.0f / ((float) (nhist - 1));
939
940 for (k = 0; k <= n; k++)
941 {
942 int count = 0;
943
944 /*
945 * Count the histogram boundaries equal to k. (Although the histogram
946 * should theoretically contain only exact integers, entries are
947 * floats so there could be roundoff error in large values. Treat any
948 * fractional value as equal to the next larger k.)
949 */
950 while (i < nhist && hist[i] <= k)
951 {
952 count++;
953 i++;
954 }
955
956 if (count > 0)
957 {
958 /* k is an exact bound for at least one histogram box. */
959 float val;
960
961 /* Find length between current histogram value and the next one */
962 if (i < nhist)
963 next_interval = hist[i] - hist[i - 1];
964 else
965 next_interval = 0;
966
967 /*
968 * count - 1 histogram boxes contain k exclusively. They
969 * contribute a total of (count - 1) * frac probability. Also
970 * factor in the partial histogram boxes on either side.
971 */
972 val = (float) (count - 1);
973 if (next_interval > 0)
974 val += 0.5f / next_interval;
975 if (prev_interval > 0)
976 val += 0.5f / prev_interval;
977 hist_part[k] = frac * val;
978
979 prev_interval = next_interval;
980 }
981 else
982 {
983 /* k does not appear as an exact histogram bound. */
984 if (prev_interval > 0)
985 hist_part[k] = frac / prev_interval;
986 else
987 hist_part[k] = 0.0f;
988 }
989 }
990
991 return hist_part;
992}
993
994/*
995 * Consider n independent events with probabilities p[]. This function
996 * calculates probabilities of exact k of events occurrence for k in [0..m].
997 * Returns a palloc'd array of size m+1.
998 *
999 * "rest" is the sum of the probabilities of all low-probability events not
1000 * included in p.
1001 *
1002 * Imagine matrix M of size (n + 1) x (m + 1). Element M[i,j] denotes the
1003 * probability that exactly j of first i events occur. Obviously M[0,0] = 1.
1004 * For any constant j, each increment of i increases the probability iff the
1005 * event occurs. So, by the law of total probability:
1006 * M[i,j] = M[i - 1, j] * (1 - p[i]) + M[i - 1, j - 1] * p[i]
1007 * for i > 0, j > 0.
1008 * M[i,0] = M[i - 1, 0] * (1 - p[i]) for i > 0.
1009 */
1010static float *
1011calc_distr(const float *p, int n, int m, float rest)
1012{
1013 float *row,
1014 *prev_row,
1015 *tmp;
1016 int i,
1017 j;
1018
1019 /*
1020 * Since we return only the last row of the matrix and need only the
1021 * current and previous row for calculations, allocate two rows.
1022 */
1023 row = (float *) palloc((m + 1) * sizeof(float));
1024 prev_row = (float *) palloc((m + 1) * sizeof(float));
1025
1026 /* M[0,0] = 1 */
1027 row[0] = 1.0f;
1028 for (i = 1; i <= n; i++)
1029 {
1030 float t = p[i - 1];
1031
1032 /* Swap rows */
1033 tmp = row;
1034 row = prev_row;
1035 prev_row = tmp;
1036
1037 /* Calculate next row */
1038 for (j = 0; j <= i && j <= m; j++)
1039 {
1040 float val = 0.0f;
1041
1042 if (j < i)
1043 val += prev_row[j] * (1.0f - t);
1044 if (j > 0)
1045 val += prev_row[j - 1] * t;
1046 row[j] = val;
1047 }
1048 }
1049
1050 /*
1051 * The presence of many distinct rare (not in "p") elements materially
1052 * decreases selectivity. Model their collective occurrence with the
1053 * Poisson distribution.
1054 */
1055 if (rest > DEFAULT_CONTAIN_SEL)
1056 {
1057 float t;
1058
1059 /* Swap rows */
1060 tmp = row;
1061 row = prev_row;
1062 prev_row = tmp;
1063
1064 for (i = 0; i <= m; i++)
1065 row[i] = 0.0f;
1066
1067 /* Value of Poisson distribution for 0 occurrences */
1068 t = exp(-rest);
1069
1070 /*
1071 * Calculate convolution of previously computed distribution and the
1072 * Poisson distribution.
1073 */
1074 for (i = 0; i <= m; i++)
1075 {
1076 for (j = 0; j <= m - i; j++)
1077 row[j + i] += prev_row[j] * t;
1078
1079 /* Get Poisson distribution value for (i + 1) occurrences */
1080 t *= rest / (float) (i + 1);
1081 }
1082 }
1083
1084 pfree(prev_row);
1085 return row;
1086}
1087
1088/* Fast function for floor value of 2 based logarithm calculation. */
1089static int
1090floor_log2(uint32 n)
1091{
1092 int logval = 0;
1093
1094 if (n == 0)
1095 return -1;
1096 if (n >= (1 << 16))
1097 {
1098 n >>= 16;
1099 logval += 16;
1100 }
1101 if (n >= (1 << 8))
1102 {
1103 n >>= 8;
1104 logval += 8;
1105 }
1106 if (n >= (1 << 4))
1107 {
1108 n >>= 4;
1109 logval += 4;
1110 }
1111 if (n >= (1 << 2))
1112 {
1113 n >>= 2;
1114 logval += 2;
1115 }
1116 if (n >= (1 << 1))
1117 {
1118 logval += 1;
1119 }
1120 return logval;
1121}
1122
1123/*
1124 * find_next_mcelem binary-searches a most common elements array, starting
1125 * from *index, for the first member >= value. It saves the position of the
1126 * match into *index and returns true if it's an exact match. (Note: we
1127 * assume the mcelem elements are distinct so there can't be more than one
1128 * exact match.)
1129 */
1130static bool
1131find_next_mcelem(Datum *mcelem, int nmcelem, Datum value, int *index,
1132 TypeCacheEntry *typentry)
1133{
1134 int l = *index,
1135 r = nmcelem - 1,
1136 i,
1137 res;
1138
1139 while (l <= r)
1140 {
1141 i = (l + r) / 2;
1142 res = element_compare(&mcelem[i], &value, typentry);
1143 if (res == 0)
1144 {
1145 *index = i;
1146 return true;
1147 }
1148 else if (res < 0)
1149 l = i + 1;
1150 else
1151 r = i - 1;
1152 }
1153 *index = l;
1154 return false;
1155}
1156
1157/*
1158 * Comparison function for elements.
1159 *
1160 * We use the element type's default btree opclass, and its default collation
1161 * if the type is collation-sensitive.
1162 *
1163 * XXX consider using SortSupport infrastructure
1164 */
1165static int
1166element_compare(const void *key1, const void *key2, void *arg)
1167{
1168 Datum d1 = *((const Datum *) key1);
1169 Datum d2 = *((const Datum *) key2);
1170 TypeCacheEntry *typentry = (TypeCacheEntry *) arg;
1171 FmgrInfo *cmpfunc = &typentry->cmp_proc_finfo;
1172 Datum c;
1173
1174 c = FunctionCall2Coll(cmpfunc, typentry->typcollation, d1, d2);
1175 return DatumGetInt32(c);
1176}
1177
1178/*
1179 * Comparison function for sorting floats into descending order.
1180 */
1181static int
1182float_compare_desc(const void *key1, const void *key2)
1183{
1184 float d1 = *((const float *) key1);
1185 float d2 = *((const float *) key2);
1186
1187 if (d1 > d2)
1188 return -1;
1189 else if (d1 < d2)
1190 return 1;
1191 else
1192 return 0;
1193}
1194