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