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