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