1 /*-------------------------------------------------------------------------
4 * Functions for selectivity estimation of array operators
6 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/utils/adt/array_selfuncs.c
13 *-------------------------------------------------------------------------
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"
30 /* Default selectivity constant for "@>" and "<@" operators */
31 #define DEFAULT_CONTAIN_SEL 0.005
33 /* Default selectivity constant for "&&" operator */
34 #define DEFAULT_OVERLAP_SEL 0.01
36 /* Default selectivity for given operator */
37 #define DEFAULT_SEL(operator) \
38 ((operator) == OID_ARRAY_OVERLAP_OP ? \
39 DEFAULT_OVERLAP_SEL : DEFAULT_CONTAIN_SEL)
41 static Selectivity
calc_arraycontsel(VariableStatData
*vardata
, Datum constval
,
42 Oid elemtype
, Oid
operator);
43 static Selectivity
mcelem_array_selec(ArrayType
*array
,
44 TypeCacheEntry
*typentry
,
45 Datum
*mcelem
, int nmcelem
,
46 float4
*numbers
, int nnumbers
,
47 float4
*hist
, int nhist
,
49 static 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
);
53 static 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
);
58 static float *calc_hist(const float4
*hist
, int nhist
, int n
);
59 static float *calc_distr(const float *p
, int n
, int m
, float rest
);
60 static int floor_log2(uint32 n
);
61 static bool find_next_mcelem(Datum
*mcelem
, int nmcelem
, Datum value
,
62 int *index
, TypeCacheEntry
*typentry
);
63 static int element_compare(const void *key1
, const void *key2
, void *arg
);
64 static int float_compare_desc(const void *key1
, const void *key2
);
68 * scalararraysel_containment
69 * Estimate selectivity of ScalarArrayOpExpr via array containment.
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].
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.
79 * Returns selectivity (0..1), or -1 if we fail to estimate selectivity.
82 scalararraysel_containment(PlannerInfo
*root
,
83 Node
*leftop
, Node
*rightop
,
84 Oid elemtype
, bool isEquality
, bool useOr
,
88 VariableStatData vardata
;
90 TypeCacheEntry
*typentry
;
94 * rightop must be a variable, else punt.
96 examine_variable(root
, rightop
, varRelid
, &vardata
);
99 ReleaseVariableStats(vardata
);
104 * leftop must be a constant, else punt.
106 if (!IsA(leftop
, Const
))
108 ReleaseVariableStats(vardata
);
111 if (((Const
*) leftop
)->constisnull
)
113 /* qual can't succeed if null on left */
114 ReleaseVariableStats(vardata
);
115 return (Selectivity
) 0.0;
117 constval
= ((Const
*) leftop
)->constvalue
;
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
))
123 ReleaseVariableStats(vardata
);
126 cmpfunc
= &typentry
->cmp_proc_finfo
;
129 * If the operator is <>, swap ANY/ALL, then invert the result later.
134 /* Get array element stats for var, if available */
135 if (HeapTupleIsValid(vardata
.statsTuple
) &&
136 statistic_proc_security_check(&vardata
, cmpfunc
->fn_oid
))
138 Form_pg_statistic stats
;
142 stats
= (Form_pg_statistic
) GETSTRUCT(vardata
.statsTuple
);
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
))
149 /* For ALL case, also get histogram of distinct-element counts */
151 !get_attstatsslot(&hslot
, vardata
.statsTuple
,
152 STATISTIC_KIND_DECHIST
, InvalidOid
,
153 ATTSTATSSLOT_NUMBERS
))
154 memset(&hslot
, 0, sizeof(hslot
));
157 * For = ANY, estimate as var @> ARRAY[const].
159 * For = ALL, estimate as var <@ ARRAY[const].
162 selec
= mcelem_array_contain_overlap_selec(sslot
.values
,
167 OID_ARRAY_CONTAINS_OP
,
170 selec
= mcelem_array_contained_selec(sslot
.values
,
177 OID_ARRAY_CONTAINED_OP
,
180 free_attstatsslot(&hslot
);
181 free_attstatsslot(&sslot
);
185 /* No most-common-elements info, so do without */
187 selec
= mcelem_array_contain_overlap_selec(NULL
, 0,
190 OID_ARRAY_CONTAINS_OP
,
193 selec
= mcelem_array_contained_selec(NULL
, 0,
197 OID_ARRAY_CONTAINED_OP
,
202 * MCE stats count only non-null rows, so adjust for null rows.
204 selec
*= (1.0 - stats
->stanullfrac
);
208 /* No stats at all, so do without */
210 selec
= mcelem_array_contain_overlap_selec(NULL
, 0,
213 OID_ARRAY_CONTAINS_OP
,
216 selec
= mcelem_array_contained_selec(NULL
, 0,
220 OID_ARRAY_CONTAINED_OP
,
222 /* we assume no nulls here, so no stanullfrac correction */
225 ReleaseVariableStats(vardata
);
228 * If the operator is <>, invert the results.
233 CLAMP_PROBABILITY(selec
);
239 * arraycontsel -- restriction selectivity for array @>, &&, <@ operators
242 arraycontsel(PG_FUNCTION_ARGS
)
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
;
255 * If expression is not (variable op something) or (something op
256 * variable), then punt and return a default estimate.
258 if (!get_restriction_variable(root
, args
, varRelid
,
259 &vardata
, &other
, &varonleft
))
260 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
263 * Can't do anything useful if the something is not a constant, either.
265 if (!IsA(other
, Const
))
267 ReleaseVariableStats(vardata
);
268 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
272 * The "&&", "@>" and "<@" operators are strict, so we can cope with a
273 * NULL constant right away.
275 if (((Const
*) other
)->constisnull
)
277 ReleaseVariableStats(vardata
);
278 PG_RETURN_FLOAT8(0.0);
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.
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
;
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.)
299 element_typeid
= get_base_element_type(((Const
*) other
)->consttype
);
300 if (element_typeid
!= InvalidOid
&&
301 element_typeid
== get_base_element_type(vardata
.vartype
))
303 selec
= calc_arraycontsel(&vardata
, ((Const
*) other
)->constvalue
,
304 element_typeid
, operator);
308 selec
= DEFAULT_SEL(operator);
311 ReleaseVariableStats(vardata
);
313 CLAMP_PROBABILITY(selec
);
315 PG_RETURN_FLOAT8((float8
) selec
);
319 * arraycontjoinsel -- join selectivity for array @>, &&, <@ operators
322 arraycontjoinsel(PG_FUNCTION_ARGS
)
324 /* For the moment this is just a stub */
325 Oid
operator = PG_GETARG_OID(1);
327 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
331 * Calculate selectivity for "arraycolumn @> const", "arraycolumn && const"
332 * or "arraycolumn <@ const" based on the statistics
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().
338 calc_arraycontsel(VariableStatData
*vardata
, Datum constval
,
339 Oid elemtype
, Oid
operator)
342 TypeCacheEntry
*typentry
;
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
;
353 * The caller made sure the const is an array with same element type, so
356 array
= DatumGetArrayTypeP(constval
);
358 if (HeapTupleIsValid(vardata
->statsTuple
) &&
359 statistic_proc_security_check(vardata
, cmpfunc
->fn_oid
))
361 Form_pg_statistic stats
;
365 stats
= (Form_pg_statistic
) GETSTRUCT(vardata
->statsTuple
);
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
))
373 * For "array <@ const" case we also need histogram of distinct
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
));
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
,
389 free_attstatsslot(&hslot
);
390 free_attstatsslot(&sslot
);
394 /* No most-common-elements info, so do without */
395 selec
= mcelem_array_selec(array
, typentry
,
396 NULL
, 0, NULL
, 0, NULL
, 0,
401 * MCE stats count only non-null rows, so adjust for null rows.
403 selec
*= (1.0 - stats
->stanullfrac
);
407 /* No stats at all, so do without */
408 selec
= mcelem_array_selec(array
, typentry
,
409 NULL
, 0, NULL
, 0, NULL
, 0,
411 /* we assume no nulls here, so no stanullfrac correction */
414 /* If constant was toasted, release the copy we made */
415 if (PointerGetDatum(array
) != constval
)
422 * Array selectivity estimation based on most common elements statistics
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.
429 mcelem_array_selec(ArrayType
*array
, TypeCacheEntry
*typentry
,
430 Datum
*mcelem
, int nmcelem
,
431 float4
*numbers
, int nnumbers
,
432 float4
*hist
, int nhist
,
444 * Prepare constant array data for sorting. Sorting lets us find unique
445 * elements and efficiently merge with the MCELEM array.
447 deconstruct_array(array
,
452 &elem_values
, &elem_nulls
, &num_elems
);
454 /* Collapse out any null elements */
456 null_present
= false;
457 for (i
= 0; i
< num_elems
; i
++)
462 elem_values
[nonnull_nitems
++] = elem_values
[i
];
466 * Query "column @> '{anything, null}'" matches nothing. For the other
467 * two operators, presence of a null in the constant can be ignored.
469 if (null_present
&& operator == OID_ARRAY_CONTAINS_OP
)
473 return (Selectivity
) 0.0;
476 /* Sort extracted elements using their default comparison function. */
477 qsort_arg(elem_values
, nonnull_nitems
, sizeof(Datum
),
478 element_compare
, typentry
);
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
,
484 elem_values
, nonnull_nitems
,
486 else if (operator == OID_ARRAY_CONTAINED_OP
)
487 selec
= mcelem_array_contained_selec(mcelem
, nmcelem
,
489 elem_values
, nonnull_nitems
,
494 elog(ERROR
, "arraycontsel called for unrecognized operator %u",
496 selec
= 0.0; /* keep compiler quiet */
505 * Estimate selectivity of "column @> const" and "column && const" based on
506 * most common element statistics. This estimation assumes element
507 * occurrences are independent.
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.
513 * Both the mcelem and array_data arrays are assumed presorted according
514 * to the element type's cmpfunc. Null elements are not present.
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.
522 mcelem_array_contain_overlap_selec(Datum
*mcelem
, int nmcelem
,
523 float4
*numbers
, int nnumbers
,
524 Datum
*array_data
, int nitems
,
525 Oid
operator, TypeCacheEntry
*typentry
)
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
540 if (nnumbers
!= nmcelem
+ 3)
548 /* Grab the lowest observed frequency */
549 minfreq
= numbers
[nmcelem
];
553 /* Without statistics make some default assumptions */
554 minfreq
= 2 * (float4
) DEFAULT_CONTAIN_SEL
;
557 /* Decide whether it is faster to use binary search or not. */
558 if (nitems
* floor_log2((uint32
) nmcelem
) < nmcelem
+ nitems
)
563 if (operator == OID_ARRAY_CONTAINS_OP
)
566 * Initial selectivity for "column @> const" query is 1.0, and it will
567 * be decreased with each element of constant array.
574 * Initial selectivity for "column && const" query is 0.0, and it will
575 * be increased with each element of constant array.
580 /* Scan mcelem and array in parallel. */
582 for (i
= 0; i
< nitems
; i
++)
586 /* Ignore any duplicates in the array data. */
588 element_compare(&array_data
[i
- 1], &array_data
[i
], typentry
) == 0)
591 /* Find the smallest MCELEM >= this array item. */
594 match
= find_next_mcelem(mcelem
, nmcelem
, array_data
[i
],
595 &mcelem_index
, typentry
);
599 while (mcelem_index
< nmcelem
)
601 int cmp
= element_compare(&mcelem
[mcelem_index
],
610 match
= true; /* mcelem is found */
616 if (match
&& numbers
)
618 /* MCELEM matches the array item; use its frequency. */
619 elem_selec
= numbers
[mcelem_index
];
625 * The element is not in MCELEM. Punt, but assume that the
626 * selectivity cannot be more than minfreq / 2.
628 elem_selec
= Min(DEFAULT_CONTAIN_SEL
, minfreq
/ 2);
632 * Update overall selectivity using the current element's selectivity
633 * and an assumption of element occurrence independence.
635 if (operator == OID_ARRAY_CONTAINS_OP
)
638 selec
= selec
+ elem_selec
- selec
* elem_selec
;
640 /* Clamp intermediate results to stay sane despite roundoff error */
641 CLAMP_PROBABILITY(selec
);
648 * Estimate selectivity of "column <@ const" based on most common element
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.
657 * Both the mcelem and array_data arrays are assumed presorted according
658 * to the element type's cmpfunc. Null elements are not present.
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.
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.
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:
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]
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.
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
697 mcelem_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
)
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.
723 if (numbers
== NULL
|| nnumbers
!= nmcelem
+ 3)
724 return DEFAULT_CONTAIN_SEL
;
726 /* Can't do much without a count histogram, either */
727 if (hist
== NULL
|| nhist
< 3)
728 return DEFAULT_CONTAIN_SEL
;
731 * Grab some of the summary statistics that compute_array_stats() stores:
732 * lowest frequency, frequency of null elements, and average distinct
735 minfreq
= numbers
[nmcelem
];
736 nullelem_freq
= numbers
[nmcelem
+ 2];
737 avg_count
= hist
[nhist
- 1];
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.
748 * mult is a multiplier representing estimate of probability that each
749 * mcelem that is not present in constant doesn't occur.
754 * elem_selec is array of estimated frequencies for elements in the
757 elem_selec
= (float *) palloc(sizeof(float) * nitems
);
759 /* Scan mcelem and array in parallel. */
761 for (i
= 0; i
< nitems
; i
++)
765 /* Ignore any duplicates in the array data. */
767 element_compare(&array_data
[i
- 1], &array_data
[i
], typentry
) == 0)
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.
775 while (mcelem_index
< nmcelem
)
777 int cmp
= element_compare(&mcelem
[mcelem_index
],
783 mult
*= (1.0f
- numbers
[mcelem_index
]);
784 rest
-= numbers
[mcelem_index
];
790 match
= true; /* mcelem is found */
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
];
806 * The element is not in MCELEM. Punt, but assume that the
807 * selectivity cannot be more than minfreq / 2.
809 elem_selec
[unique_nitems
] = Min(DEFAULT_CONTAIN_SEL
,
817 * If we handled all constant elements without exhausting the MCELEM
818 * array, finish walking it to complete calculation of "rest" and "mult".
820 while (mcelem_index
< nmcelem
)
822 mult
*= (1.0f
- numbers
[mcelem_index
]);
823 rest
-= numbers
[mcelem_index
];
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".
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.
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.)
856 if ((nmcelem
+ unique_nitems
) > 0 &&
857 unique_nitems
> EFFORT
* nmcelem
/ (nmcelem
+ unique_nitems
))
860 * Use the quadratic formula to solve for largest allowable N. We
861 * have A = 1, B = nmcelem, C = - EFFORT * nmcelem.
863 double b
= (double) nmcelem
;
866 n
= (int) ((sqrt(b
* b
+ 4 * EFFORT
* b
) - b
) / 2);
868 /* Sort, then take just the first n elements */
869 qsort(elem_selec
, unique_nitems
, sizeof(float),
875 * Calculate probabilities of each distinct element count for both mcelems
876 * and constant elements. At this point, assume independent element
879 dist
= calc_distr(elem_selec
, unique_nitems
, unique_nitems
, 0.0f
);
880 mcelem_dist
= calc_distr(numbers
, nmcelem
, unique_nitems
, rest
);
882 /* ignore hist[nhist-1], which is the average not a histogram member */
883 hist_part
= calc_hist(hist
, nhist
- 1, unique_nitems
);
886 for (i
= 0; i
<= unique_nitems
; i
++)
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.
893 if (mcelem_dist
[i
] > 0)
894 selec
+= hist_part
[i
] * mult
* dist
[i
] / mcelem_dist
[i
];
902 /* Take into account occurrence of NULL element. */
903 selec
*= (1.0f
- nullelem_freq
);
905 CLAMP_PROBABILITY(selec
);
911 * Calculate the first n distinct element count probabilities from a
912 * histogram of distinct element counts.
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].
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.
922 calc_hist(const float4
*hist
, int nhist
, int n
)
927 float prev_interval
= 0,
931 hist_part
= (float *) palloc((n
+ 1) * sizeof(float));
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).
938 frac
= 1.0f
/ ((float) (nhist
- 1));
940 for (k
= 0; k
<= n
; k
++)
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.)
950 while (i
< nhist
&& hist
[i
] <= k
)
958 /* k is an exact bound for at least one histogram box. */
961 /* Find length between current histogram value and the next one */
963 next_interval
= hist
[i
] - hist
[i
- 1];
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.
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
;
979 prev_interval
= next_interval
;
983 /* k does not appear as an exact histogram bound. */
984 if (prev_interval
> 0)
985 hist_part
[k
] = frac
/ prev_interval
;
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.
999 * "rest" is the sum of the probabilities of all low-probability events not
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]
1008 * M[i,0] = M[i - 1, 0] * (1 - p[i]) for i > 0.
1011 calc_distr(const float *p
, int n
, int m
, float rest
)
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.
1023 row
= (float *) palloc((m
+ 1) * sizeof(float));
1024 prev_row
= (float *) palloc((m
+ 1) * sizeof(float));
1028 for (i
= 1; i
<= n
; i
++)
1037 /* Calculate next row */
1038 for (j
= 0; j
<= i
&& j
<= m
; j
++)
1043 val
+= prev_row
[j
] * (1.0f
- t
);
1045 val
+= prev_row
[j
- 1] * t
;
1051 * The presence of many distinct rare (not in "p") elements materially
1052 * decreases selectivity. Model their collective occurrence with the
1053 * Poisson distribution.
1055 if (rest
> DEFAULT_CONTAIN_SEL
)
1064 for (i
= 0; i
<= m
; i
++)
1067 /* Value of Poisson distribution for 0 occurrences */
1071 * Calculate convolution of previously computed distribution and the
1072 * Poisson distribution.
1074 for (i
= 0; i
<= m
; i
++)
1076 for (j
= 0; j
<= m
- i
; j
++)
1077 row
[j
+ i
] += prev_row
[j
] * t
;
1079 /* Get Poisson distribution value for (i + 1) occurrences */
1080 t
*= rest
/ (float) (i
+ 1);
1088 /* Fast function for floor value of 2 based logarithm calculation. */
1090 floor_log2(uint32 n
)
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
1131 find_next_mcelem(Datum
*mcelem
, int nmcelem
, Datum value
, int *index
,
1132 TypeCacheEntry
*typentry
)
1142 res
= element_compare(&mcelem
[i
], &value
, typentry
);
1158 * Comparison function for elements.
1160 * We use the element type's default btree opclass, and its default collation
1161 * if the type is collation-sensitive.
1163 * XXX consider using SortSupport infrastructure
1166 element_compare(const void *key1
, const void *key2
, void *arg
)
1168 Datum d1
= *((const Datum
*) key1
);
1169 Datum d2
= *((const Datum
*) key2
);
1170 TypeCacheEntry
*typentry
= (TypeCacheEntry
*) arg
;
1171 FmgrInfo
*cmpfunc
= &typentry
->cmp_proc_finfo
;
1174 c
= FunctionCall2Coll(cmpfunc
, typentry
->typcollation
, d1
, d2
);
1175 return DatumGetInt32(c
);
1179 * Comparison function for sorting floats into descending order.
1182 float_compare_desc(const void *key1
, const void *key2
)
1184 float d1
= *((const float *) key1
);
1185 float d2
= *((const float *) key2
);