PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
multirangetypes_selfuncs.c
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * multirangetypes_selfuncs.c
4 * Functions for selectivity estimation of multirange operators
5 *
6 * Estimates are based on histograms of lower and upper bounds, and the
7 * fraction of empty multiranges.
8 *
9 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
10 * Portions Copyright (c) 1994, Regents of the University of California
11 *
12 *
13 * IDENTIFICATION
14 * src/backend/utils/adt/multirangetypes_selfuncs.c
15 *
16 *-------------------------------------------------------------------------
17 */
18#include "postgres.h"
19
20#include <math.h>
21
22#include "access/htup_details.h"
23#include "catalog/pg_operator.h"
25#include "utils/float.h"
26#include "utils/fmgrprotos.h"
27#include "utils/lsyscache.h"
29#include "utils/rangetypes.h"
30#include "utils/selfuncs.h"
31#include "utils/typcache.h"
32
33static double calc_multirangesel(TypeCacheEntry *typcache,
34 VariableStatData *vardata,
35 const MultirangeType *constval, Oid operator);
36static double default_multirange_selectivity(Oid operator);
37static double calc_hist_selectivity(TypeCacheEntry *typcache,
38 VariableStatData *vardata,
39 const MultirangeType *constval,
40 Oid operator);
41static double calc_hist_selectivity_scalar(TypeCacheEntry *typcache,
42 const RangeBound *constbound,
43 const RangeBound *hist,
44 int hist_nvalues, bool equal);
45static int rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value,
46 const RangeBound *hist, int hist_length, bool equal);
47static float8 get_position(TypeCacheEntry *typcache, const RangeBound *value,
48 const RangeBound *hist1, const RangeBound *hist2);
49static float8 get_len_position(double value, double hist1, double hist2);
50static float8 get_distance(TypeCacheEntry *typcache, const RangeBound *bound1,
51 const RangeBound *bound2);
52static int length_hist_bsearch(Datum *length_hist_values,
53 int length_hist_nvalues, double value,
54 bool equal);
55static double calc_length_hist_frac(Datum *length_hist_values,
56 int length_hist_nvalues, double length1,
57 double length2, bool equal);
59 const RangeBound *lower,
61 const RangeBound *hist_lower,
62 int hist_nvalues,
63 Datum *length_hist_values,
64 int length_hist_nvalues);
66 const RangeBound *lower,
67 const RangeBound *upper,
68 const RangeBound *hist_lower,
69 int hist_nvalues,
70 Datum *length_hist_values,
71 int length_hist_nvalues);
72
73/*
74 * Returns a default selectivity estimate for given operator, when we don't
75 * have statistics or cannot use them for some reason.
76 */
77static double
79{
80 switch (operator)
81 {
82 case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
83 case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
84 case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
85 return 0.01;
86
87 case OID_RANGE_CONTAINS_MULTIRANGE_OP:
88 case OID_RANGE_MULTIRANGE_CONTAINED_OP:
89 case OID_MULTIRANGE_CONTAINS_RANGE_OP:
90 case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
91 case OID_MULTIRANGE_RANGE_CONTAINED_OP:
92 case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
93 return 0.005;
94
95 case OID_MULTIRANGE_CONTAINS_ELEM_OP:
96 case OID_MULTIRANGE_ELEM_CONTAINED_OP:
97
98 /*
99 * "multirange @> elem" is more or less identical to a scalar
100 * inequality "A >= b AND A <= c".
101 */
103
104 case OID_MULTIRANGE_LESS_OP:
105 case OID_MULTIRANGE_LESS_EQUAL_OP:
106 case OID_MULTIRANGE_GREATER_OP:
107 case OID_MULTIRANGE_GREATER_EQUAL_OP:
108 case OID_MULTIRANGE_LEFT_RANGE_OP:
109 case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
110 case OID_RANGE_LEFT_MULTIRANGE_OP:
111 case OID_MULTIRANGE_RIGHT_RANGE_OP:
112 case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
113 case OID_RANGE_RIGHT_MULTIRANGE_OP:
114 case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
115 case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
116 case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
117 case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
118 case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
119 case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
120 /* these are similar to regular scalar inequalities */
121 return DEFAULT_INEQ_SEL;
122
123 default:
124
125 /*
126 * all multirange operators should be handled above, but just in
127 * case
128 */
129 return 0.01;
130 }
131}
132
133/*
134 * multirangesel -- restriction selectivity for multirange operators
135 */
136Datum
138{
140 Oid operator = PG_GETARG_OID(1);
142 int varRelid = PG_GETARG_INT32(3);
143 VariableStatData vardata;
144 Node *other;
145 bool varonleft;
146 Selectivity selec;
147 TypeCacheEntry *typcache = NULL;
148 MultirangeType *constmultirange = NULL;
149 RangeType *constrange = NULL;
150
151 /*
152 * If expression is not (variable op something) or (something op
153 * variable), then punt and return a default estimate.
154 */
155 if (!get_restriction_variable(root, args, varRelid,
156 &vardata, &other, &varonleft))
158
159 /*
160 * Can't do anything useful if the something is not a constant, either.
161 */
162 if (!IsA(other, Const))
163 {
164 ReleaseVariableStats(vardata);
166 }
167
168 /*
169 * All the multirange operators are strict, so we can cope with a NULL
170 * constant right away.
171 */
172 if (((Const *) other)->constisnull)
173 {
174 ReleaseVariableStats(vardata);
175 PG_RETURN_FLOAT8(0.0);
176 }
177
178 /*
179 * If var is on the right, commute the operator, so that we can assume the
180 * var is on the left in what follows.
181 */
182 if (!varonleft)
183 {
184 /* we have other Op var, commute to make var Op other */
185 operator = get_commutator(operator);
186 if (!operator)
187 {
188 /* Use default selectivity (should we raise an error instead?) */
189 ReleaseVariableStats(vardata);
191 }
192 }
193
194 /*
195 * OK, there's a Var and a Const we're dealing with here. We need the
196 * Const to be of same multirange type as the column, else we can't do
197 * anything useful. (Such cases will likely fail at runtime, but here we'd
198 * rather just return a default estimate.)
199 *
200 * If the operator is "multirange @> element", the constant should be of
201 * the element type of the multirange column. Convert it to a multirange
202 * that includes only that single point, so that we don't need special
203 * handling for that in what follows.
204 */
205 if (operator == OID_MULTIRANGE_CONTAINS_ELEM_OP)
206 {
207 typcache = multirange_get_typcache(fcinfo, vardata.vartype);
208
209 if (((Const *) other)->consttype == typcache->rngtype->rngelemtype->type_id)
210 {
212 upper;
213
214 lower.inclusive = true;
215 lower.val = ((Const *) other)->constvalue;
216 lower.infinite = false;
217 lower.lower = true;
218 upper.inclusive = true;
219 upper.val = ((Const *) other)->constvalue;
220 upper.infinite = false;
221 upper.lower = false;
222 constrange = range_serialize(typcache->rngtype, &lower, &upper,
223 false, NULL);
224 constmultirange = make_multirange(typcache->type_id, typcache->rngtype,
225 1, &constrange);
226 }
227 }
228 else if (operator == OID_RANGE_MULTIRANGE_CONTAINED_OP ||
229 operator == OID_MULTIRANGE_CONTAINS_RANGE_OP ||
230 operator == OID_MULTIRANGE_OVERLAPS_RANGE_OP ||
231 operator == OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP ||
232 operator == OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP ||
233 operator == OID_MULTIRANGE_LEFT_RANGE_OP ||
234 operator == OID_MULTIRANGE_RIGHT_RANGE_OP)
235 {
236 /*
237 * Promote a range in "multirange OP range" just like we do an element
238 * in "multirange OP element".
239 */
240 typcache = multirange_get_typcache(fcinfo, vardata.vartype);
241 if (((Const *) other)->consttype == typcache->rngtype->type_id)
242 {
243 constrange = DatumGetRangeTypeP(((Const *) other)->constvalue);
244 constmultirange = make_multirange(typcache->type_id, typcache->rngtype,
245 1, &constrange);
246 }
247 }
248 else if (operator == OID_RANGE_OVERLAPS_MULTIRANGE_OP ||
249 operator == OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP ||
250 operator == OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP ||
251 operator == OID_RANGE_LEFT_MULTIRANGE_OP ||
252 operator == OID_RANGE_RIGHT_MULTIRANGE_OP ||
253 operator == OID_RANGE_CONTAINS_MULTIRANGE_OP ||
254 operator == OID_MULTIRANGE_ELEM_CONTAINED_OP ||
255 operator == OID_MULTIRANGE_RANGE_CONTAINED_OP)
256 {
257 /*
258 * Here, the Var is the elem/range, not the multirange. For now we
259 * just punt and return the default estimate. In future we could
260 * disassemble the multirange constant to do something more
261 * intelligent.
262 */
263 }
264 else if (((Const *) other)->consttype == vardata.vartype)
265 {
266 /* Both sides are the same multirange type */
267 typcache = multirange_get_typcache(fcinfo, vardata.vartype);
268
269 constmultirange = DatumGetMultirangeTypeP(((Const *) other)->constvalue);
270 }
271
272 /*
273 * If we got a valid constant on one side of the operator, proceed to
274 * estimate using statistics. Otherwise punt and return a default constant
275 * estimate. Note that calc_multirangesel need not handle
276 * OID_MULTIRANGE_*_CONTAINED_OP.
277 */
278 if (constmultirange)
279 selec = calc_multirangesel(typcache, &vardata, constmultirange, operator);
280 else
281 selec = default_multirange_selectivity(operator);
282
283 ReleaseVariableStats(vardata);
284
285 CLAMP_PROBABILITY(selec);
286
287 PG_RETURN_FLOAT8((float8) selec);
288}
289
290static double
292 const MultirangeType *constval, Oid operator)
293{
294 double hist_selec;
295 double selec;
296 float4 empty_frac,
297 null_frac;
298
299 /*
300 * First look up the fraction of NULLs and empty multiranges from
301 * pg_statistic.
302 */
303 if (HeapTupleIsValid(vardata->statsTuple))
304 {
305 Form_pg_statistic stats;
306 AttStatsSlot sslot;
307
308 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
309 null_frac = stats->stanullfrac;
310
311 /* Try to get fraction of empty multiranges */
312 if (get_attstatsslot(&sslot, vardata->statsTuple,
313 STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM,
316 {
317 if (sslot.nnumbers != 1)
318 elog(ERROR, "invalid empty fraction statistic"); /* shouldn't happen */
319 empty_frac = sslot.numbers[0];
320 free_attstatsslot(&sslot);
321 }
322 else
323 {
324 /* No empty fraction statistic. Assume no empty ranges. */
325 empty_frac = 0.0;
326 }
327 }
328 else
329 {
330 /*
331 * No stats are available. Follow through the calculations below
332 * anyway, assuming no NULLs and no empty multiranges. This still
333 * allows us to give a better-than-nothing estimate based on whether
334 * the constant is an empty multirange or not.
335 */
336 null_frac = 0.0;
337 empty_frac = 0.0;
338 }
339
340 if (MultirangeIsEmpty(constval))
341 {
342 /*
343 * An empty multirange matches all multiranges, all empty multiranges,
344 * or nothing, depending on the operator
345 */
346 switch (operator)
347 {
348 /* these return false if either argument is empty */
349 case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
350 case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
351 case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
352 case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
353 case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
354 case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
355 case OID_MULTIRANGE_LEFT_RANGE_OP:
356 case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
357 case OID_MULTIRANGE_RIGHT_RANGE_OP:
358 case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
359 /* nothing is less than an empty multirange */
360 case OID_MULTIRANGE_LESS_OP:
361 selec = 0.0;
362 break;
363
364 /*
365 * only empty multiranges can be contained by an empty
366 * multirange
367 */
368 case OID_RANGE_MULTIRANGE_CONTAINED_OP:
369 case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
370 /* only empty ranges are <= an empty multirange */
371 case OID_MULTIRANGE_LESS_EQUAL_OP:
372 selec = empty_frac;
373 break;
374
375 /* everything contains an empty multirange */
376 case OID_MULTIRANGE_CONTAINS_RANGE_OP:
377 case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
378 /* everything is >= an empty multirange */
379 case OID_MULTIRANGE_GREATER_EQUAL_OP:
380 selec = 1.0;
381 break;
382
383 /* all non-empty multiranges are > an empty multirange */
384 case OID_MULTIRANGE_GREATER_OP:
385 selec = 1.0 - empty_frac;
386 break;
387
388 /* an element cannot be empty */
389 case OID_MULTIRANGE_CONTAINS_ELEM_OP:
390
391 /* filtered out by multirangesel() */
392 case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
393 case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
394 case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
395 case OID_RANGE_LEFT_MULTIRANGE_OP:
396 case OID_RANGE_RIGHT_MULTIRANGE_OP:
397 case OID_RANGE_CONTAINS_MULTIRANGE_OP:
398 case OID_MULTIRANGE_ELEM_CONTAINED_OP:
399 case OID_MULTIRANGE_RANGE_CONTAINED_OP:
400
401 default:
402 elog(ERROR, "unexpected operator %u", operator);
403 selec = 0.0; /* keep compiler quiet */
404 break;
405 }
406 }
407 else
408 {
409 /*
410 * Calculate selectivity using bound histograms. If that fails for
411 * some reason, e.g no histogram in pg_statistic, use the default
412 * constant estimate for the fraction of non-empty values. This is
413 * still somewhat better than just returning the default estimate,
414 * because this still takes into account the fraction of empty and
415 * NULL tuples, if we had statistics for them.
416 */
417 hist_selec = calc_hist_selectivity(typcache, vardata, constval,
418 operator);
419 if (hist_selec < 0.0)
420 hist_selec = default_multirange_selectivity(operator);
421
422 /*
423 * Now merge the results for the empty multiranges and histogram
424 * calculations, realizing that the histogram covers only the
425 * non-null, non-empty values.
426 */
427 if (operator == OID_RANGE_MULTIRANGE_CONTAINED_OP ||
428 operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
429 {
430 /* empty is contained by anything non-empty */
431 selec = (1.0 - empty_frac) * hist_selec + empty_frac;
432 }
433 else
434 {
435 /* with any other operator, empty Op non-empty matches nothing */
436 selec = (1.0 - empty_frac) * hist_selec;
437 }
438 }
439
440 /* all multirange operators are strict */
441 selec *= (1.0 - null_frac);
442
443 /* result should be in range, but make sure... */
444 CLAMP_PROBABILITY(selec);
445
446 return selec;
447}
448
449/*
450 * Calculate multirange operator selectivity using histograms of multirange bounds.
451 *
452 * This estimate is for the portion of values that are not empty and not
453 * NULL.
454 */
455static double
457 const MultirangeType *constval, Oid operator)
458{
459 TypeCacheEntry *rng_typcache = typcache->rngtype;
460 AttStatsSlot hslot;
461 AttStatsSlot lslot;
462 int nhist;
463 RangeBound *hist_lower;
464 RangeBound *hist_upper;
465 int i;
466 RangeBound const_lower;
467 RangeBound const_upper;
468 RangeBound tmp;
469 double hist_selec;
470
471 /* Can't use the histogram with insecure multirange support functions */
473 rng_typcache->rng_cmp_proc_finfo.fn_oid))
474 return -1;
475 if (OidIsValid(rng_typcache->rng_subdiff_finfo.fn_oid) &&
477 rng_typcache->rng_subdiff_finfo.fn_oid))
478 return -1;
479
480 /* Try to get histogram of ranges */
481 if (!(HeapTupleIsValid(vardata->statsTuple) &&
482 get_attstatsslot(&hslot, vardata->statsTuple,
483 STATISTIC_KIND_BOUNDS_HISTOGRAM, InvalidOid,
485 return -1.0;
486
487 /* check that it's a histogram, not just a dummy entry */
488 if (hslot.nvalues < 2)
489 {
490 free_attstatsslot(&hslot);
491 return -1.0;
492 }
493
494 /*
495 * Convert histogram of ranges into histograms of its lower and upper
496 * bounds.
497 */
498 nhist = hslot.nvalues;
499 hist_lower = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
500 hist_upper = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
501 for (i = 0; i < nhist; i++)
502 {
503 bool empty;
504
505 range_deserialize(rng_typcache, DatumGetRangeTypeP(hslot.values[i]),
506 &hist_lower[i], &hist_upper[i], &empty);
507 /* The histogram should not contain any empty ranges */
508 if (empty)
509 elog(ERROR, "bounds histogram contains an empty range");
510 }
511
512 /* @> and @< also need a histogram of range lengths */
513 if (operator == OID_MULTIRANGE_CONTAINS_RANGE_OP ||
514 operator == OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP ||
515 operator == OID_MULTIRANGE_RANGE_CONTAINED_OP ||
516 operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
517 {
518 if (!(HeapTupleIsValid(vardata->statsTuple) &&
519 get_attstatsslot(&lslot, vardata->statsTuple,
520 STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM,
523 {
524 free_attstatsslot(&hslot);
525 return -1.0;
526 }
527
528 /* check that it's a histogram, not just a dummy entry */
529 if (lslot.nvalues < 2)
530 {
531 free_attstatsslot(&lslot);
532 free_attstatsslot(&hslot);
533 return -1.0;
534 }
535 }
536 else
537 memset(&lslot, 0, sizeof(lslot));
538
539 /* Extract the bounds of the constant value. */
540 Assert(constval->rangeCount > 0);
541 multirange_get_bounds(rng_typcache, constval, 0,
542 &const_lower, &tmp);
543 multirange_get_bounds(rng_typcache, constval, constval->rangeCount - 1,
544 &tmp, &const_upper);
545
546 /*
547 * Calculate selectivity comparing the lower or upper bound of the
548 * constant with the histogram of lower or upper bounds.
549 */
550 switch (operator)
551 {
552 case OID_MULTIRANGE_LESS_OP:
553
554 /*
555 * The regular b-tree comparison operators (<, <=, >, >=) compare
556 * the lower bounds first, and the upper bounds for values with
557 * equal lower bounds. Estimate that by comparing the lower bounds
558 * only. This gives a fairly accurate estimate assuming there
559 * aren't many rows with a lower bound equal to the constant's
560 * lower bound.
561 */
562 hist_selec =
563 calc_hist_selectivity_scalar(rng_typcache, &const_lower,
564 hist_lower, nhist, false);
565 break;
566
567 case OID_MULTIRANGE_LESS_EQUAL_OP:
568 hist_selec =
569 calc_hist_selectivity_scalar(rng_typcache, &const_lower,
570 hist_lower, nhist, true);
571 break;
572
573 case OID_MULTIRANGE_GREATER_OP:
574 hist_selec =
575 1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
576 hist_lower, nhist, false);
577 break;
578
579 case OID_MULTIRANGE_GREATER_EQUAL_OP:
580 hist_selec =
581 1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
582 hist_lower, nhist, true);
583 break;
584
585 case OID_MULTIRANGE_LEFT_RANGE_OP:
586 case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
587 /* var << const when upper(var) < lower(const) */
588 hist_selec =
589 calc_hist_selectivity_scalar(rng_typcache, &const_lower,
590 hist_upper, nhist, false);
591 break;
592
593 case OID_MULTIRANGE_RIGHT_RANGE_OP:
594 case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
595 /* var >> const when lower(var) > upper(const) */
596 hist_selec =
597 1 - calc_hist_selectivity_scalar(rng_typcache, &const_upper,
598 hist_lower, nhist, true);
599 break;
600
601 case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
602 case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
603 /* compare lower bounds */
604 hist_selec =
605 1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
606 hist_lower, nhist, false);
607 break;
608
609 case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
610 case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
611 /* compare upper bounds */
612 hist_selec =
613 calc_hist_selectivity_scalar(rng_typcache, &const_upper,
614 hist_upper, nhist, true);
615 break;
616
617 case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
618 case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
619 case OID_MULTIRANGE_CONTAINS_ELEM_OP:
620
621 /*
622 * A && B <=> NOT (A << B OR A >> B).
623 *
624 * Since A << B and A >> B are mutually exclusive events we can
625 * sum their probabilities to find probability of (A << B OR A >>
626 * B).
627 *
628 * "multirange @> elem" is equivalent to "multirange &&
629 * {[elem,elem]}". The caller already constructed the singular
630 * range from the element constant, so just treat it the same as
631 * &&.
632 */
633 hist_selec =
634 calc_hist_selectivity_scalar(rng_typcache,
635 &const_lower, hist_upper,
636 nhist, false);
637 hist_selec +=
638 (1.0 - calc_hist_selectivity_scalar(rng_typcache,
639 &const_upper, hist_lower,
640 nhist, true));
641 hist_selec = 1.0 - hist_selec;
642 break;
643
644 case OID_MULTIRANGE_CONTAINS_RANGE_OP:
645 case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
646 hist_selec =
647 calc_hist_selectivity_contains(rng_typcache, &const_lower,
648 &const_upper, hist_lower, nhist,
649 lslot.values, lslot.nvalues);
650 break;
651
652 case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
653 case OID_RANGE_MULTIRANGE_CONTAINED_OP:
654 if (const_lower.infinite)
655 {
656 /*
657 * Lower bound no longer matters. Just estimate the fraction
658 * with an upper bound <= const upper bound
659 */
660 hist_selec =
661 calc_hist_selectivity_scalar(rng_typcache, &const_upper,
662 hist_upper, nhist, true);
663 }
664 else if (const_upper.infinite)
665 {
666 hist_selec =
667 1.0 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
668 hist_lower, nhist, false);
669 }
670 else
671 {
672 hist_selec =
673 calc_hist_selectivity_contained(rng_typcache, &const_lower,
674 &const_upper, hist_lower, nhist,
675 lslot.values, lslot.nvalues);
676 }
677 break;
678
679 /* filtered out by multirangesel() */
680 case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
681 case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
682 case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
683 case OID_RANGE_LEFT_MULTIRANGE_OP:
684 case OID_RANGE_RIGHT_MULTIRANGE_OP:
685 case OID_RANGE_CONTAINS_MULTIRANGE_OP:
686 case OID_MULTIRANGE_ELEM_CONTAINED_OP:
687 case OID_MULTIRANGE_RANGE_CONTAINED_OP:
688
689 default:
690 elog(ERROR, "unknown multirange operator %u", operator);
691 hist_selec = -1.0; /* keep compiler quiet */
692 break;
693 }
694
695 free_attstatsslot(&lslot);
696 free_attstatsslot(&hslot);
697
698 return hist_selec;
699}
700
701
702/*
703 * Look up the fraction of values less than (or equal, if 'equal' argument
704 * is true) a given const in a histogram of range bounds.
705 */
706static double
708 const RangeBound *hist, int hist_nvalues, bool equal)
709{
710 Selectivity selec;
711 int index;
712
713 /*
714 * Find the histogram bin the given constant falls into. Estimate
715 * selectivity as the number of preceding whole bins.
716 */
717 index = rbound_bsearch(typcache, constbound, hist, hist_nvalues, equal);
718 selec = (Selectivity) (Max(index, 0)) / (Selectivity) (hist_nvalues - 1);
719
720 /* Adjust using linear interpolation within the bin */
721 if (index >= 0 && index < hist_nvalues - 1)
722 selec += get_position(typcache, constbound, &hist[index],
723 &hist[index + 1]) / (Selectivity) (hist_nvalues - 1);
724
725 return selec;
726}
727
728/*
729 * Binary search on an array of range bounds. Returns greatest index of range
730 * bound in array which is less(less or equal) than given range bound. If all
731 * range bounds in array are greater or equal(greater) than given range bound,
732 * return -1. When "equal" flag is set conditions in brackets are used.
733 *
734 * This function is used in scalar operator selectivity estimation. Another
735 * goal of this function is to find a histogram bin where to stop
736 * interpolation of portion of bounds which are less than or equal to given bound.
737 */
738static int
740 int hist_length, bool equal)
741{
742 int lower = -1,
743 upper = hist_length - 1,
744 cmp,
745 middle;
746
747 while (lower < upper)
748 {
749 middle = (lower + upper + 1) / 2;
750 cmp = range_cmp_bounds(typcache, &hist[middle], value);
751
752 if (cmp < 0 || (equal && cmp == 0))
753 lower = middle;
754 else
755 upper = middle - 1;
756 }
757 return lower;
758}
759
760
761/*
762 * Binary search on length histogram. Returns greatest index of range length in
763 * histogram which is less than (less than or equal) the given length value. If
764 * all lengths in the histogram are greater than (greater than or equal) the
765 * given length, returns -1.
766 */
767static int
768length_hist_bsearch(Datum *length_hist_values, int length_hist_nvalues,
769 double value, bool equal)
770{
771 int lower = -1,
772 upper = length_hist_nvalues - 1,
773 middle;
774
775 while (lower < upper)
776 {
777 double middleval;
778
779 middle = (lower + upper + 1) / 2;
780
781 middleval = DatumGetFloat8(length_hist_values[middle]);
782 if (middleval < value || (equal && middleval <= value))
783 lower = middle;
784 else
785 upper = middle - 1;
786 }
787 return lower;
788}
789
790/*
791 * Get relative position of value in histogram bin in [0,1] range.
792 */
793static float8
794get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1,
795 const RangeBound *hist2)
796{
797 bool has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
798 float8 position;
799
800 if (!hist1->infinite && !hist2->infinite)
801 {
802 float8 bin_width;
803
804 /*
805 * Both bounds are finite. Assuming the subtype's comparison function
806 * works sanely, the value must be finite, too, because it lies
807 * somewhere between the bounds. If it doesn't, arbitrarily return
808 * 0.5.
809 */
810 if (value->infinite)
811 return 0.5;
812
813 /* Can't interpolate without subdiff function */
814 if (!has_subdiff)
815 return 0.5;
816
817 /* Calculate relative position using subdiff function. */
819 typcache->rng_collation,
820 hist2->val,
821 hist1->val));
822 if (isnan(bin_width) || bin_width <= 0.0)
823 return 0.5; /* punt for NaN or zero-width bin */
824
826 typcache->rng_collation,
827 value->val,
828 hist1->val))
829 / bin_width;
830
831 if (isnan(position))
832 return 0.5; /* punt for NaN from subdiff, Inf/Inf, etc */
833
834 /* Relative position must be in [0,1] range */
835 position = Max(position, 0.0);
836 position = Min(position, 1.0);
837 return position;
838 }
839 else if (hist1->infinite && !hist2->infinite)
840 {
841 /*
842 * Lower bin boundary is -infinite, upper is finite. If the value is
843 * -infinite, return 0.0 to indicate it's equal to the lower bound.
844 * Otherwise return 1.0 to indicate it's infinitely far from the lower
845 * bound.
846 */
847 return ((value->infinite && value->lower) ? 0.0 : 1.0);
848 }
849 else if (!hist1->infinite && hist2->infinite)
850 {
851 /* same as above, but in reverse */
852 return ((value->infinite && !value->lower) ? 1.0 : 0.0);
853 }
854 else
855 {
856 /*
857 * If both bin boundaries are infinite, they should be equal to each
858 * other, and the value should also be infinite and equal to both
859 * bounds. (But don't Assert that, to avoid crashing if a user creates
860 * a datatype with a broken comparison function).
861 *
862 * Assume the value to lie in the middle of the infinite bounds.
863 */
864 return 0.5;
865 }
866}
867
868
869/*
870 * Get relative position of value in a length histogram bin in [0,1] range.
871 */
872static double
873get_len_position(double value, double hist1, double hist2)
874{
875 if (!isinf(hist1) && !isinf(hist2))
876 {
877 /*
878 * Both bounds are finite. The value should be finite too, because it
879 * lies somewhere between the bounds. If it doesn't, just return
880 * something.
881 */
882 if (isinf(value))
883 return 0.5;
884
885 return 1.0 - (hist2 - value) / (hist2 - hist1);
886 }
887 else if (isinf(hist1) && !isinf(hist2))
888 {
889 /*
890 * Lower bin boundary is -infinite, upper is finite. Return 1.0 to
891 * indicate the value is infinitely far from the lower bound.
892 */
893 return 1.0;
894 }
895 else if (isinf(hist1) && isinf(hist2))
896 {
897 /* same as above, but in reverse */
898 return 0.0;
899 }
900 else
901 {
902 /*
903 * If both bin boundaries are infinite, they should be equal to each
904 * other, and the value should also be infinite and equal to both
905 * bounds. (But don't Assert that, to avoid crashing unnecessarily if
906 * the caller messes up)
907 *
908 * Assume the value to lie in the middle of the infinite bounds.
909 */
910 return 0.5;
911 }
912}
913
914/*
915 * Measure distance between two range bounds.
916 */
917static float8
918get_distance(TypeCacheEntry *typcache, const RangeBound *bound1, const RangeBound *bound2)
919{
920 bool has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
921
922 if (!bound1->infinite && !bound2->infinite)
923 {
924 /*
925 * Neither bound is infinite, use subdiff function or return default
926 * value of 1.0 if no subdiff is available.
927 */
928 if (has_subdiff)
929 {
930 float8 res;
931
933 typcache->rng_collation,
934 bound2->val,
935 bound1->val));
936 /* Reject possible NaN result, also negative result */
937 if (isnan(res) || res < 0.0)
938 return 1.0;
939 else
940 return res;
941 }
942 else
943 return 1.0;
944 }
945 else if (bound1->infinite && bound2->infinite)
946 {
947 /* Both bounds are infinite */
948 if (bound1->lower == bound2->lower)
949 return 0.0;
950 else
951 return get_float8_infinity();
952 }
953 else
954 {
955 /* One bound is infinite, the other is not */
956 return get_float8_infinity();
957 }
958}
959
960/*
961 * Calculate the average of function P(x), in the interval [length1, length2],
962 * where P(x) is the fraction of tuples with length < x (or length <= x if
963 * 'equal' is true).
964 */
965static double
966calc_length_hist_frac(Datum *length_hist_values, int length_hist_nvalues,
967 double length1, double length2, bool equal)
968{
969 double frac;
970 double A,
971 B,
972 PA,
973 PB;
974 double pos;
975 int i;
976 double area;
977
978 Assert(length2 >= length1);
979
980 if (length2 < 0.0)
981 return 0.0; /* shouldn't happen, but doesn't hurt to check */
982
983 /* All lengths in the table are <= infinite. */
984 if (isinf(length2) && equal)
985 return 1.0;
986
987 /*----------
988 * The average of a function between A and B can be calculated by the
989 * formula:
990 *
991 * B
992 * 1 /
993 * ------- | P(x)dx
994 * B - A /
995 * A
996 *
997 * The geometrical interpretation of the integral is the area under the
998 * graph of P(x). P(x) is defined by the length histogram. We calculate
999 * the area in a piecewise fashion, iterating through the length histogram
1000 * bins. Each bin is a trapezoid:
1001 *
1002 * P(x2)
1003 * /|
1004 * / |
1005 * P(x1)/ |
1006 * | |
1007 * | |
1008 * ---+---+--
1009 * x1 x2
1010 *
1011 * where x1 and x2 are the boundaries of the current histogram, and P(x1)
1012 * and P(x1) are the cumulative fraction of tuples at the boundaries.
1013 *
1014 * The area of each trapezoid is 1/2 * (P(x2) + P(x1)) * (x2 - x1)
1015 *
1016 * The first bin contains the lower bound passed by the caller, so we
1017 * use linear interpolation between the previous and next histogram bin
1018 * boundary to calculate P(x1). Likewise for the last bin: we use linear
1019 * interpolation to calculate P(x2). For the bins in between, x1 and x2
1020 * lie on histogram bin boundaries, so P(x1) and P(x2) are simply:
1021 * P(x1) = (bin index) / (number of bins)
1022 * P(x2) = (bin index + 1 / (number of bins)
1023 */
1024
1025 /* First bin, the one that contains lower bound */
1026 i = length_hist_bsearch(length_hist_values, length_hist_nvalues, length1, equal);
1027 if (i >= length_hist_nvalues - 1)
1028 return 1.0;
1029
1030 if (i < 0)
1031 {
1032 i = 0;
1033 pos = 0.0;
1034 }
1035 else
1036 {
1037 /* interpolate length1's position in the bin */
1038 pos = get_len_position(length1,
1039 DatumGetFloat8(length_hist_values[i]),
1040 DatumGetFloat8(length_hist_values[i + 1]));
1041 }
1042 PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
1043 B = length1;
1044
1045 /*
1046 * In the degenerate case that length1 == length2, simply return
1047 * P(length1). This is not merely an optimization: if length1 == length2,
1048 * we'd divide by zero later on.
1049 */
1050 if (length2 == length1)
1051 return PB;
1052
1053 /*
1054 * Loop through all the bins, until we hit the last bin, the one that
1055 * contains the upper bound. (if lower and upper bounds are in the same
1056 * bin, this falls out immediately)
1057 */
1058 area = 0.0;
1059 for (; i < length_hist_nvalues - 1; i++)
1060 {
1061 double bin_upper = DatumGetFloat8(length_hist_values[i + 1]);
1062
1063 /* check if we've reached the last bin */
1064 if (!(bin_upper < length2 || (equal && bin_upper <= length2)))
1065 break;
1066
1067 /* the upper bound of previous bin is the lower bound of this bin */
1068 A = B;
1069 PA = PB;
1070
1071 B = bin_upper;
1072 PB = (double) i / (double) (length_hist_nvalues - 1);
1073
1074 /*
1075 * Add the area of this trapezoid to the total. The point of the
1076 * if-check is to avoid NaN, in the corner case that PA == PB == 0,
1077 * and B - A == Inf. The area of a zero-height trapezoid (PA == PB ==
1078 * 0) is zero, regardless of the width (B - A).
1079 */
1080 if (PA > 0 || PB > 0)
1081 area += 0.5 * (PB + PA) * (B - A);
1082 }
1083
1084 /* Last bin */
1085 A = B;
1086 PA = PB;
1087
1088 B = length2; /* last bin ends at the query upper bound */
1089 if (i >= length_hist_nvalues - 1)
1090 pos = 0.0;
1091 else
1092 {
1093 if (DatumGetFloat8(length_hist_values[i]) == DatumGetFloat8(length_hist_values[i + 1]))
1094 pos = 0.0;
1095 else
1096 pos = get_len_position(length2,
1097 DatumGetFloat8(length_hist_values[i]),
1098 DatumGetFloat8(length_hist_values[i + 1]));
1099 }
1100 PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
1101
1102 if (PA > 0 || PB > 0)
1103 area += 0.5 * (PB + PA) * (B - A);
1104
1105 /*
1106 * Ok, we have calculated the area, ie. the integral. Divide by width to
1107 * get the requested average.
1108 *
1109 * Avoid NaN arising from infinite / infinite. This happens at least if
1110 * length2 is infinite. It's not clear what the correct value would be in
1111 * that case, so 0.5 seems as good as any value.
1112 */
1113 if (isinf(area) && isinf(length2))
1114 frac = 0.5;
1115 else
1116 frac = area / (length2 - length1);
1117
1118 return frac;
1119}
1120
1121/*
1122 * Calculate selectivity of "var <@ const" operator, ie. estimate the fraction
1123 * of multiranges that fall within the constant lower and upper bounds. This uses
1124 * the histograms of range lower bounds and range lengths, on the assumption
1125 * that the range lengths are independent of the lower bounds.
1126 *
1127 * The caller has already checked that constant lower and upper bounds are
1128 * finite.
1129 */
1130static double
1133 const RangeBound *hist_lower, int hist_nvalues,
1134 Datum *length_hist_values, int length_hist_nvalues)
1135{
1136 int i,
1137 upper_index;
1138 float8 prev_dist;
1139 double bin_width;
1140 double upper_bin_width;
1141 double sum_frac;
1142
1143 /*
1144 * Begin by finding the bin containing the upper bound, in the lower bound
1145 * histogram. Any range with a lower bound > constant upper bound can't
1146 * match, ie. there are no matches in bins greater than upper_index.
1147 */
1148 upper->inclusive = !upper->inclusive;
1149 upper->lower = true;
1150 upper_index = rbound_bsearch(typcache, upper, hist_lower, hist_nvalues,
1151 false);
1152
1153 /*
1154 * If the upper bound value is below the histogram's lower limit, there
1155 * are no matches.
1156 */
1157 if (upper_index < 0)
1158 return 0.0;
1159
1160 /*
1161 * If the upper bound value is at or beyond the histogram's upper limit,
1162 * start our loop at the last actual bin, as though the upper bound were
1163 * within that bin; get_position will clamp its result to 1.0 anyway.
1164 * (This corresponds to assuming that the data population above the
1165 * histogram's upper limit is empty, exactly like what we just assumed for
1166 * the lower limit.)
1167 */
1168 upper_index = Min(upper_index, hist_nvalues - 2);
1169
1170 /*
1171 * Calculate upper_bin_width, ie. the fraction of the (upper_index,
1172 * upper_index + 1) bin which is greater than upper bound of query range
1173 * using linear interpolation of subdiff function.
1174 */
1175 upper_bin_width = get_position(typcache, upper,
1176 &hist_lower[upper_index],
1177 &hist_lower[upper_index + 1]);
1178
1179 /*
1180 * In the loop, dist and prev_dist are the distance of the "current" bin's
1181 * lower and upper bounds from the constant upper bound.
1182 *
1183 * bin_width represents the width of the current bin. Normally it is 1.0,
1184 * meaning a full width bin, but can be less in the corner cases: start
1185 * and end of the loop. We start with bin_width = upper_bin_width, because
1186 * we begin at the bin containing the upper bound.
1187 */
1188 prev_dist = 0.0;
1189 bin_width = upper_bin_width;
1190
1191 sum_frac = 0.0;
1192 for (i = upper_index; i >= 0; i--)
1193 {
1194 double dist;
1195 double length_hist_frac;
1196 bool final_bin = false;
1197
1198 /*
1199 * dist -- distance from upper bound of query range to lower bound of
1200 * the current bin in the lower bound histogram. Or to the lower bound
1201 * of the constant range, if this is the final bin, containing the
1202 * constant lower bound.
1203 */
1204 if (range_cmp_bounds(typcache, &hist_lower[i], lower) < 0)
1205 {
1206 dist = get_distance(typcache, lower, upper);
1207
1208 /*
1209 * Subtract from bin_width the portion of this bin that we want to
1210 * ignore.
1211 */
1212 bin_width -= get_position(typcache, lower, &hist_lower[i],
1213 &hist_lower[i + 1]);
1214 if (bin_width < 0.0)
1215 bin_width = 0.0;
1216 final_bin = true;
1217 }
1218 else
1219 dist = get_distance(typcache, &hist_lower[i], upper);
1220
1221 /*
1222 * Estimate the fraction of tuples in this bin that are narrow enough
1223 * to not exceed the distance to the upper bound of the query range.
1224 */
1225 length_hist_frac = calc_length_hist_frac(length_hist_values,
1226 length_hist_nvalues,
1227 prev_dist, dist, true);
1228
1229 /*
1230 * Add the fraction of tuples in this bin, with a suitable length, to
1231 * the total.
1232 */
1233 sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
1234
1235 if (final_bin)
1236 break;
1237
1238 bin_width = 1.0;
1239 prev_dist = dist;
1240 }
1241
1242 return sum_frac;
1243}
1244
1245/*
1246 * Calculate selectivity of "var @> const" operator, ie. estimate the fraction
1247 * of multiranges that contain the constant lower and upper bounds. This uses
1248 * the histograms of range lower bounds and range lengths, on the assumption
1249 * that the range lengths are independent of the lower bounds.
1250 */
1251static double
1253 const RangeBound *lower, const RangeBound *upper,
1254 const RangeBound *hist_lower, int hist_nvalues,
1255 Datum *length_hist_values, int length_hist_nvalues)
1256{
1257 int i,
1258 lower_index;
1259 double bin_width,
1260 lower_bin_width;
1261 double sum_frac;
1262 float8 prev_dist;
1263
1264 /* Find the bin containing the lower bound of query range. */
1265 lower_index = rbound_bsearch(typcache, lower, hist_lower, hist_nvalues,
1266 true);
1267
1268 /*
1269 * If the lower bound value is below the histogram's lower limit, there
1270 * are no matches.
1271 */
1272 if (lower_index < 0)
1273 return 0.0;
1274
1275 /*
1276 * If the lower bound value is at or beyond the histogram's upper limit,
1277 * start our loop at the last actual bin, as though the upper bound were
1278 * within that bin; get_position will clamp its result to 1.0 anyway.
1279 * (This corresponds to assuming that the data population above the
1280 * histogram's upper limit is empty, exactly like what we just assumed for
1281 * the lower limit.)
1282 */
1283 lower_index = Min(lower_index, hist_nvalues - 2);
1284
1285 /*
1286 * Calculate lower_bin_width, ie. the fraction of the of (lower_index,
1287 * lower_index + 1) bin which is greater than lower bound of query range
1288 * using linear interpolation of subdiff function.
1289 */
1290 lower_bin_width = get_position(typcache, lower, &hist_lower[lower_index],
1291 &hist_lower[lower_index + 1]);
1292
1293 /*
1294 * Loop through all the lower bound bins, smaller than the query lower
1295 * bound. In the loop, dist and prev_dist are the distance of the
1296 * "current" bin's lower and upper bounds from the constant upper bound.
1297 * We begin from query lower bound, and walk backwards, so the first bin's
1298 * upper bound is the query lower bound, and its distance to the query
1299 * upper bound is the length of the query range.
1300 *
1301 * bin_width represents the width of the current bin. Normally it is 1.0,
1302 * meaning a full width bin, except for the first bin, which is only
1303 * counted up to the constant lower bound.
1304 */
1305 prev_dist = get_distance(typcache, lower, upper);
1306 sum_frac = 0.0;
1307 bin_width = lower_bin_width;
1308 for (i = lower_index; i >= 0; i--)
1309 {
1310 float8 dist;
1311 double length_hist_frac;
1312
1313 /*
1314 * dist -- distance from upper bound of query range to current value
1315 * of lower bound histogram or lower bound of query range (if we've
1316 * reach it).
1317 */
1318 dist = get_distance(typcache, &hist_lower[i], upper);
1319
1320 /*
1321 * Get average fraction of length histogram which covers intervals
1322 * longer than (or equal to) distance to upper bound of query range.
1323 */
1324 length_hist_frac =
1325 1.0 - calc_length_hist_frac(length_hist_values,
1326 length_hist_nvalues,
1327 prev_dist, dist, false);
1328
1329 sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
1330
1331 bin_width = 1.0;
1332 prev_dist = dist;
1333 }
1334
1335 return sum_frac;
1336}
#define Min(x, y)
Definition: c.h:958
#define Max(x, y)
Definition: c.h:952
#define Assert(condition)
Definition: c.h:812
double float8
Definition: c.h:584
float float4
Definition: c.h:583
#define OidIsValid(objectId)
Definition: c.h:729
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
static float8 get_float8_infinity(void)
Definition: float.h:94
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1149
#define PG_GETARG_OID(n)
Definition: fmgr.h:275
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
#define GETSTRUCT(TUP)
Definition: htup_details.h:653
static struct @161 value
int i
Definition: isn.c:72
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3344
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3234
Oid get_commutator(Oid opno)
Definition: lsyscache.c:1509
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
#define ATTSTATSSLOT_VALUES
Definition: lsyscache.h:42
void * palloc(Size size)
Definition: mcxt.c:1317
MultirangeType * make_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges)
void multirange_get_bounds(TypeCacheEntry *rangetyp, const MultirangeType *multirange, uint32 i, RangeBound *lower, RangeBound *upper)
TypeCacheEntry * multirange_get_typcache(FunctionCallInfo fcinfo, Oid mltrngtypid)
#define MultirangeIsEmpty(mr)
static MultirangeType * DatumGetMultirangeTypeP(Datum X)
static double calc_length_hist_frac(Datum *length_hist_values, int length_hist_nvalues, double length1, double length2, bool equal)
static double calc_hist_selectivity_contained(TypeCacheEntry *typcache, const RangeBound *lower, RangeBound *upper, const RangeBound *hist_lower, int hist_nvalues, Datum *length_hist_values, int length_hist_nvalues)
static float8 get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1, const RangeBound *hist2)
static double calc_hist_selectivity_scalar(TypeCacheEntry *typcache, const RangeBound *constbound, const RangeBound *hist, int hist_nvalues, bool equal)
static double calc_hist_selectivity_contains(TypeCacheEntry *typcache, const RangeBound *lower, const RangeBound *upper, const RangeBound *hist_lower, int hist_nvalues, Datum *length_hist_values, int length_hist_nvalues)
static double calc_multirangesel(TypeCacheEntry *typcache, VariableStatData *vardata, const MultirangeType *constval, Oid operator)
static int length_hist_bsearch(Datum *length_hist_values, int length_hist_nvalues, double value, bool equal)
static int rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist, int hist_length, bool equal)
static double calc_hist_selectivity(TypeCacheEntry *typcache, VariableStatData *vardata, const MultirangeType *constval, Oid operator)
static double default_multirange_selectivity(Oid operator)
static float8 get_len_position(double value, double hist1, double hist2)
Datum multirangesel(PG_FUNCTION_ARGS)
static float8 get_distance(TypeCacheEntry *typcache, const RangeBound *bound1, const RangeBound *bound2)
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
double Selectivity
Definition: nodes.h:250
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
FormData_pg_statistic * Form_pg_statistic
Definition: pg_statistic.h:135
uintptr_t Datum
Definition: postgres.h:64
static float8 DatumGetFloat8(Datum X)
Definition: postgres.h:494
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
tree ctl root
Definition: radixtree.h:1888
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:2016
RangeType * range_serialize(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty, struct Node *escontext)
Definition: rangetypes.c:1727
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1856
static RangeType * DatumGetRangeTypeP(Datum X)
Definition: rangetypes.h:73
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
bool get_restriction_variable(PlannerInfo *root, List *args, int varRelid, VariableStatData *vardata, Node **other, bool *varonleft)
Definition: selfuncs.c:4894
bool statistic_proc_security_check(VariableStatData *vardata, Oid func_oid)
Definition: selfuncs.c:5746
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:99
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
#define DEFAULT_MULTIRANGE_INEQ_SEL
Definition: selfuncs.h:43
#define DEFAULT_INEQ_SEL
Definition: selfuncs.h:37
Datum * values
Definition: lsyscache.h:53
float4 * numbers
Definition: lsyscache.h:56
int nnumbers
Definition: lsyscache.h:57
Oid fn_oid
Definition: fmgr.h:59
Definition: pg_list.h:54
Definition: nodes.h:129
bool lower
Definition: rangetypes.h:66
bool infinite
Definition: rangetypes.h:64
Datum val
Definition: rangetypes.h:63
FmgrInfo rng_cmp_proc_finfo
Definition: typcache.h:101
Oid rng_collation
Definition: typcache.h:100
struct TypeCacheEntry * rngelemtype
Definition: typcache.h:98
struct TypeCacheEntry * rngtype
Definition: typcache.h:108
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:103
HeapTuple statsTuple
Definition: selfuncs.h:89
Definition: type.h:96