PostgreSQL Source Code  git master
multirangetypes_selfuncs.c File Reference
#include "postgres.h"
#include <math.h>
#include "access/htup_details.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_statistic.h"
#include "catalog/pg_type.h"
#include "utils/float.h"
#include "utils/fmgrprotos.h"
#include "utils/lsyscache.h"
#include "utils/rangetypes.h"
#include "utils/multirangetypes.h"
#include "utils/selfuncs.h"
#include "utils/typcache.h"
Include dependency graph for multirangetypes_selfuncs.c:

Go to the source code of this file.

Functions

static double calc_multirangesel (TypeCacheEntry *typcache, VariableStatData *vardata, const MultirangeType *constval, Oid operator)
 
static double default_multirange_selectivity (Oid operator)
 
static double calc_hist_selectivity (TypeCacheEntry *typcache, VariableStatData *vardata, const MultirangeType *constval, Oid operator)
 
static double calc_hist_selectivity_scalar (TypeCacheEntry *typcache, const RangeBound *constbound, const RangeBound *hist, int hist_nvalues, bool equal)
 
static int rbound_bsearch (TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist, int hist_length, bool equal)
 
static float8 get_position (TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1, const RangeBound *hist2)
 
static float8 get_len_position (double value, double hist1, double hist2)
 
static float8 get_distance (TypeCacheEntry *typcache, const RangeBound *bound1, const RangeBound *bound2)
 
static int length_hist_bsearch (Datum *length_hist_values, int length_hist_nvalues, double value, bool equal)
 
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 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)
 
Datum multirangesel (PG_FUNCTION_ARGS)
 

Function Documentation

◆ calc_hist_selectivity()

static double calc_hist_selectivity ( TypeCacheEntry typcache,
VariableStatData vardata,
const MultirangeType constval,
Oid  operator 
)
static

Definition at line 449 of file multirangetypes_selfuncs.c.

References Assert, ATTSTATSSLOT_VALUES, calc_hist_selectivity_contained(), calc_hist_selectivity_contains(), calc_hist_selectivity_scalar(), DatumGetRangeTypeP, elog, ERROR, FmgrInfo::fn_oid, free_attstatsslot(), get_attstatsslot(), HeapTupleIsValid, i, RangeBound::infinite, InvalidOid, multirange_get_bounds(), AttStatsSlot::nvalues, OidIsValid, palloc(), range_deserialize(), MultirangeType::rangeCount, TypeCacheEntry::rng_cmp_proc_finfo, TypeCacheEntry::rng_subdiff_finfo, TypeCacheEntry::rngtype, statistic_proc_security_check(), VariableStatData::statsTuple, and AttStatsSlot::values.

Referenced by calc_multirangesel().

451 {
452  TypeCacheEntry *rng_typcache = typcache->rngtype;
453  AttStatsSlot hslot;
454  AttStatsSlot lslot;
455  int nhist;
456  RangeBound *hist_lower;
457  RangeBound *hist_upper;
458  int i;
459  RangeBound const_lower;
460  RangeBound const_upper;
461  RangeBound tmp;
462  double hist_selec;
463 
464  /* Can't use the histogram with insecure multirange support functions */
465  if (!statistic_proc_security_check(vardata,
466  rng_typcache->rng_cmp_proc_finfo.fn_oid))
467  return -1;
468  if (OidIsValid(rng_typcache->rng_subdiff_finfo.fn_oid) &&
470  rng_typcache->rng_subdiff_finfo.fn_oid))
471  return -1;
472 
473  /* Try to get histogram of ranges */
474  if (!(HeapTupleIsValid(vardata->statsTuple) &&
475  get_attstatsslot(&hslot, vardata->statsTuple,
476  STATISTIC_KIND_BOUNDS_HISTOGRAM, InvalidOid,
478  return -1.0;
479 
480  /* check that it's a histogram, not just a dummy entry */
481  if (hslot.nvalues < 2)
482  {
483  free_attstatsslot(&hslot);
484  return -1.0;
485  }
486 
487  /*
488  * Convert histogram of ranges into histograms of its lower and upper
489  * bounds.
490  */
491  nhist = hslot.nvalues;
492  hist_lower = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
493  hist_upper = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
494  for (i = 0; i < nhist; i++)
495  {
496  bool empty;
497 
498  range_deserialize(rng_typcache, DatumGetRangeTypeP(hslot.values[i]),
499  &hist_lower[i], &hist_upper[i], &empty);
500  /* The histogram should not contain any empty ranges */
501  if (empty)
502  elog(ERROR, "bounds histogram contains an empty range");
503  }
504 
505  /* @> and @< also need a histogram of range lengths */
506  if (operator == OID_MULTIRANGE_CONTAINS_RANGE_OP ||
507  operator == OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP ||
508  operator == OID_MULTIRANGE_RANGE_CONTAINED_OP ||
509  operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
510  {
511  if (!(HeapTupleIsValid(vardata->statsTuple) &&
512  get_attstatsslot(&lslot, vardata->statsTuple,
513  STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM,
514  InvalidOid,
516  {
517  free_attstatsslot(&hslot);
518  return -1.0;
519  }
520 
521  /* check that it's a histogram, not just a dummy entry */
522  if (lslot.nvalues < 2)
523  {
524  free_attstatsslot(&lslot);
525  free_attstatsslot(&hslot);
526  return -1.0;
527  }
528  }
529  else
530  memset(&lslot, 0, sizeof(lslot));
531 
532  /* Extract the bounds of the constant value. */
533  Assert(constval->rangeCount > 0);
534  multirange_get_bounds(rng_typcache, constval, 0,
535  &const_lower, &tmp);
536  multirange_get_bounds(rng_typcache, constval, constval->rangeCount - 1,
537  &tmp, &const_upper);
538 
539  /*
540  * Calculate selectivity comparing the lower or upper bound of the
541  * constant with the histogram of lower or upper bounds.
542  */
543  switch (operator)
544  {
545  case OID_MULTIRANGE_LESS_OP:
546 
547  /*
548  * The regular b-tree comparison operators (<, <=, >, >=) compare
549  * the lower bounds first, and the upper bounds for values with
550  * equal lower bounds. Estimate that by comparing the lower bounds
551  * only. This gives a fairly accurate estimate assuming there
552  * aren't many rows with a lower bound equal to the constant's
553  * lower bound.
554  */
555  hist_selec =
556  calc_hist_selectivity_scalar(rng_typcache, &const_lower,
557  hist_lower, nhist, false);
558  break;
559 
560  case OID_MULTIRANGE_LESS_EQUAL_OP:
561  hist_selec =
562  calc_hist_selectivity_scalar(rng_typcache, &const_lower,
563  hist_lower, nhist, true);
564  break;
565 
566  case OID_MULTIRANGE_GREATER_OP:
567  hist_selec =
568  1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
569  hist_lower, nhist, false);
570  break;
571 
572  case OID_MULTIRANGE_GREATER_EQUAL_OP:
573  hist_selec =
574  1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
575  hist_lower, nhist, true);
576  break;
577 
578  case OID_RANGE_LEFT_MULTIRANGE_OP:
579  case OID_MULTIRANGE_LEFT_RANGE_OP:
580  case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
581  /* var << const when upper(var) < lower(const) */
582  hist_selec =
583  calc_hist_selectivity_scalar(rng_typcache, &const_lower,
584  hist_upper, nhist, false);
585  break;
586 
587  case OID_RANGE_RIGHT_MULTIRANGE_OP:
588  case OID_MULTIRANGE_RIGHT_RANGE_OP:
589  case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
590  /* var >> const when lower(var) > upper(const) */
591  hist_selec =
592  1 - calc_hist_selectivity_scalar(rng_typcache, &const_upper,
593  hist_lower, nhist, true);
594  break;
595 
596  case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
597  case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
598  case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
599  /* compare lower bounds */
600  hist_selec =
601  1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
602  hist_lower, nhist, false);
603  break;
604 
605  case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
606  case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
607  case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
608  /* compare upper bounds */
609  hist_selec =
610  calc_hist_selectivity_scalar(rng_typcache, &const_upper,
611  hist_upper, nhist, true);
612  break;
613 
614  case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
615  case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
616  case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
617  case OID_MULTIRANGE_CONTAINS_ELEM_OP:
618 
619  /*
620  * A && B <=> NOT (A << B OR A >> B).
621  *
622  * Since A << B and A >> B are mutually exclusive events we can
623  * sum their probabilities to find probability of (A << B OR A >>
624  * B).
625  *
626  * "multirange @> elem" is equivalent to "multirange &&
627  * {[elem,elem]}". The caller already constructed the singular
628  * range from the element constant, so just treat it the same as
629  * &&.
630  */
631  hist_selec =
632  calc_hist_selectivity_scalar(rng_typcache,
633  &const_lower, hist_upper,
634  nhist, false);
635  hist_selec +=
636  (1.0 - calc_hist_selectivity_scalar(rng_typcache,
637  &const_upper, hist_lower,
638  nhist, true));
639  hist_selec = 1.0 - hist_selec;
640  break;
641 
642  case OID_MULTIRANGE_CONTAINS_RANGE_OP:
643  case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
644  hist_selec =
645  calc_hist_selectivity_contains(rng_typcache, &const_lower,
646  &const_upper, hist_lower, nhist,
647  lslot.values, lslot.nvalues);
648  break;
649 
650  case OID_MULTIRANGE_RANGE_CONTAINED_OP:
651  case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
652  case OID_RANGE_MULTIRANGE_CONTAINED_OP:
653  if (const_lower.infinite)
654  {
655  /*
656  * Lower bound no longer matters. Just estimate the fraction
657  * with an upper bound <= const upper bound
658  */
659  hist_selec =
660  calc_hist_selectivity_scalar(rng_typcache, &const_upper,
661  hist_upper, nhist, true);
662  }
663  else if (const_upper.infinite)
664  {
665  hist_selec =
666  1.0 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
667  hist_lower, nhist, false);
668  }
669  else
670  {
671  hist_selec =
672  calc_hist_selectivity_contained(rng_typcache, &const_lower,
673  &const_upper, hist_lower, nhist,
674  lslot.values, lslot.nvalues);
675  }
676  break;
677 
678  default:
679  elog(ERROR, "unknown multirange operator %u", operator);
680  hist_selec = -1.0; /* keep compiler quiet */
681  break;
682  }
683 
684  free_attstatsslot(&lslot);
685  free_attstatsslot(&hslot);
686 
687  return hist_selec;
688 }
FmgrInfo rng_cmp_proc_finfo
Definition: typcache.h:100
#define ATTSTATSSLOT_VALUES
Definition: lsyscache.h:42
HeapTuple statsTuple
Definition: selfuncs.h:91
bool statistic_proc_security_check(VariableStatData *vardata, Oid func_oid)
Definition: selfuncs.c:5598
#define OidIsValid(objectId)
Definition: c.h:710
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:102
#define ERROR
Definition: elog.h:46
static double calc_hist_selectivity_scalar(TypeCacheEntry *typcache, const RangeBound *constbound, const RangeBound *hist, int hist_nvalues, bool equal)
void multirange_get_bounds(TypeCacheEntry *rangetyp, const MultirangeType *multirange, uint32 i, RangeBound *lower, RangeBound *upper)
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)
#define InvalidOid
Definition: postgres_ext.h:36
Oid fn_oid
Definition: fmgr.h:59
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3177
#define Assert(condition)
Definition: c.h:804
Datum * values
Definition: lsyscache.h:53
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:73
bool infinite
Definition: rangetypes.h:65
struct TypeCacheEntry * rngtype
Definition: typcache.h:107
static Ranges * range_deserialize(int maxvalues, SerializedRanges *range)
void * palloc(Size size)
Definition: mcxt.c:1062
#define elog(elevel,...)
Definition: elog.h:232
int i
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)
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3294

◆ calc_hist_selectivity_contained()

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

Definition at line 1120 of file multirangetypes_selfuncs.c.

References calc_length_hist_frac(), get_distance(), get_position(), i, RangeBound::inclusive, RangeBound::lower, Min, range_cmp_bounds(), and rbound_bsearch().

Referenced by calc_hist_selectivity().

1124 {
1125  int i,
1126  upper_index;
1127  float8 prev_dist;
1128  double bin_width;
1129  double upper_bin_width;
1130  double sum_frac;
1131 
1132  /*
1133  * Begin by finding the bin containing the upper bound, in the lower bound
1134  * histogram. Any range with a lower bound > constant upper bound can't
1135  * match, ie. there are no matches in bins greater than upper_index.
1136  */
1137  upper->inclusive = !upper->inclusive;
1138  upper->lower = true;
1139  upper_index = rbound_bsearch(typcache, upper, hist_lower, hist_nvalues,
1140  false);
1141 
1142  /*
1143  * If the upper bound value is below the histogram's lower limit, there
1144  * are no matches.
1145  */
1146  if (upper_index < 0)
1147  return 0.0;
1148 
1149  /*
1150  * If the upper bound value is at or beyond the histogram's upper limit,
1151  * start our loop at the last actual bin, as though the upper bound were
1152  * within that bin; get_position will clamp its result to 1.0 anyway.
1153  * (This corresponds to assuming that the data population above the
1154  * histogram's upper limit is empty, exactly like what we just assumed for
1155  * the lower limit.)
1156  */
1157  upper_index = Min(upper_index, hist_nvalues - 2);
1158 
1159  /*
1160  * Calculate upper_bin_width, ie. the fraction of the (upper_index,
1161  * upper_index + 1) bin which is greater than upper bound of query range
1162  * using linear interpolation of subdiff function.
1163  */
1164  upper_bin_width = get_position(typcache, upper,
1165  &hist_lower[upper_index],
1166  &hist_lower[upper_index + 1]);
1167 
1168  /*
1169  * In the loop, dist and prev_dist are the distance of the "current" bin's
1170  * lower and upper bounds from the constant upper bound.
1171  *
1172  * bin_width represents the width of the current bin. Normally it is 1.0,
1173  * meaning a full width bin, but can be less in the corner cases: start
1174  * and end of the loop. We start with bin_width = upper_bin_width, because
1175  * we begin at the bin containing the upper bound.
1176  */
1177  prev_dist = 0.0;
1178  bin_width = upper_bin_width;
1179 
1180  sum_frac = 0.0;
1181  for (i = upper_index; i >= 0; i--)
1182  {
1183  double dist;
1184  double length_hist_frac;
1185  bool final_bin = false;
1186 
1187  /*
1188  * dist -- distance from upper bound of query range to lower bound of
1189  * the current bin in the lower bound histogram. Or to the lower bound
1190  * of the constant range, if this is the final bin, containing the
1191  * constant lower bound.
1192  */
1193  if (range_cmp_bounds(typcache, &hist_lower[i], lower) < 0)
1194  {
1195  dist = get_distance(typcache, lower, upper);
1196 
1197  /*
1198  * Subtract from bin_width the portion of this bin that we want to
1199  * ignore.
1200  */
1201  bin_width -= get_position(typcache, lower, &hist_lower[i],
1202  &hist_lower[i + 1]);
1203  if (bin_width < 0.0)
1204  bin_width = 0.0;
1205  final_bin = true;
1206  }
1207  else
1208  dist = get_distance(typcache, &hist_lower[i], upper);
1209 
1210  /*
1211  * Estimate the fraction of tuples in this bin that are narrow enough
1212  * to not exceed the distance to the upper bound of the query range.
1213  */
1214  length_hist_frac = calc_length_hist_frac(length_hist_values,
1215  length_hist_nvalues,
1216  prev_dist, dist, true);
1217 
1218  /*
1219  * Add the fraction of tuples in this bin, with a suitable length, to
1220  * the total.
1221  */
1222  sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
1223 
1224  if (final_bin)
1225  break;
1226 
1227  bin_width = 1.0;
1228  prev_dist = dist;
1229  }
1230 
1231  return sum_frac;
1232 }
static float8 get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1, const RangeBound *hist2)
#define Min(x, y)
Definition: c.h:986
static double calc_length_hist_frac(Datum *length_hist_values, int length_hist_nvalues, double length1, double length2, bool equal)
bool inclusive
Definition: rangetypes.h:66
double float8
Definition: c.h:565
static float8 get_distance(TypeCacheEntry *typcache, const RangeBound *bound1, const RangeBound *bound2)
bool lower
Definition: rangetypes.h:67
static int rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist, int hist_length, bool equal)
int i
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1924

◆ calc_hist_selectivity_contains()

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

Definition at line 1241 of file multirangetypes_selfuncs.c.

References calc_length_hist_frac(), get_distance(), get_position(), i, Min, and rbound_bsearch().

Referenced by calc_hist_selectivity().

1245 {
1246  int i,
1247  lower_index;
1248  double bin_width,
1249  lower_bin_width;
1250  double sum_frac;
1251  float8 prev_dist;
1252 
1253  /* Find the bin containing the lower bound of query range. */
1254  lower_index = rbound_bsearch(typcache, lower, hist_lower, hist_nvalues,
1255  true);
1256 
1257  /*
1258  * If the lower bound value is below the histogram's lower limit, there
1259  * are no matches.
1260  */
1261  if (lower_index < 0)
1262  return 0.0;
1263 
1264  /*
1265  * If the lower bound value is at or beyond the histogram's upper limit,
1266  * start our loop at the last actual bin, as though the upper bound were
1267  * within that bin; get_position will clamp its result to 1.0 anyway.
1268  * (This corresponds to assuming that the data population above the
1269  * histogram's upper limit is empty, exactly like what we just assumed for
1270  * the lower limit.)
1271  */
1272  lower_index = Min(lower_index, hist_nvalues - 2);
1273 
1274  /*
1275  * Calculate lower_bin_width, ie. the fraction of the of (lower_index,
1276  * lower_index + 1) bin which is greater than lower bound of query range
1277  * using linear interpolation of subdiff function.
1278  */
1279  lower_bin_width = get_position(typcache, lower, &hist_lower[lower_index],
1280  &hist_lower[lower_index + 1]);
1281 
1282  /*
1283  * Loop through all the lower bound bins, smaller than the query lower
1284  * bound. In the loop, dist and prev_dist are the distance of the
1285  * "current" bin's lower and upper bounds from the constant upper bound.
1286  * We begin from query lower bound, and walk backwards, so the first bin's
1287  * upper bound is the query lower bound, and its distance to the query
1288  * upper bound is the length of the query range.
1289  *
1290  * bin_width represents the width of the current bin. Normally it is 1.0,
1291  * meaning a full width bin, except for the first bin, which is only
1292  * counted up to the constant lower bound.
1293  */
1294  prev_dist = get_distance(typcache, lower, upper);
1295  sum_frac = 0.0;
1296  bin_width = lower_bin_width;
1297  for (i = lower_index; i >= 0; i--)
1298  {
1299  float8 dist;
1300  double length_hist_frac;
1301 
1302  /*
1303  * dist -- distance from upper bound of query range to current value
1304  * of lower bound histogram or lower bound of query range (if we've
1305  * reach it).
1306  */
1307  dist = get_distance(typcache, &hist_lower[i], upper);
1308 
1309  /*
1310  * Get average fraction of length histogram which covers intervals
1311  * longer than (or equal to) distance to upper bound of query range.
1312  */
1313  length_hist_frac =
1314  1.0 - calc_length_hist_frac(length_hist_values,
1315  length_hist_nvalues,
1316  prev_dist, dist, false);
1317 
1318  sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
1319 
1320  bin_width = 1.0;
1321  prev_dist = dist;
1322  }
1323 
1324  return sum_frac;
1325 }
static float8 get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1, const RangeBound *hist2)
#define Min(x, y)
Definition: c.h:986
static double calc_length_hist_frac(Datum *length_hist_values, int length_hist_nvalues, double length1, double length2, bool equal)
double float8
Definition: c.h:565
static float8 get_distance(TypeCacheEntry *typcache, const RangeBound *bound1, const RangeBound *bound2)
static int rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist, int hist_length, bool equal)
int i

◆ calc_hist_selectivity_scalar()

static double calc_hist_selectivity_scalar ( TypeCacheEntry typcache,
const RangeBound constbound,
const RangeBound hist,
int  hist_nvalues,
bool  equal 
)
static

Definition at line 696 of file multirangetypes_selfuncs.c.

References get_position(), Max, and rbound_bsearch().

Referenced by calc_hist_selectivity().

698 {
699  Selectivity selec;
700  int index;
701 
702  /*
703  * Find the histogram bin the given constant falls into. Estimate
704  * selectivity as the number of preceding whole bins.
705  */
706  index = rbound_bsearch(typcache, constbound, hist, hist_nvalues, equal);
707  selec = (Selectivity) (Max(index, 0)) / (Selectivity) (hist_nvalues - 1);
708 
709  /* Adjust using linear interpolation within the bin */
710  if (index >= 0 && index < hist_nvalues - 1)
711  selec += get_position(typcache, constbound, &hist[index],
712  &hist[index + 1]) / (Selectivity) (hist_nvalues - 1);
713 
714  return selec;
715 }
static float8 get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1, const RangeBound *hist2)
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3113
double Selectivity
Definition: nodes.h:672
Definition: type.h:89
static int rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist, int hist_length, bool equal)
#define Max(x, y)
Definition: c.h:980

◆ calc_length_hist_frac()

static double calc_length_hist_frac ( Datum length_hist_values,
int  length_hist_nvalues,
double  length1,
double  length2,
bool  equal 
)
static

Definition at line 955 of file multirangetypes_selfuncs.c.

References Assert, DatumGetFloat8, get_len_position(), i, and length_hist_bsearch().

Referenced by calc_hist_selectivity_contained(), and calc_hist_selectivity_contains().

957 {
958  double frac;
959  double A,
960  B,
961  PA,
962  PB;
963  double pos;
964  int i;
965  double area;
966 
967  Assert(length2 >= length1);
968 
969  if (length2 < 0.0)
970  return 0.0; /* shouldn't happen, but doesn't hurt to check */
971 
972  /* All lengths in the table are <= infinite. */
973  if (isinf(length2) && equal)
974  return 1.0;
975 
976  /*----------
977  * The average of a function between A and B can be calculated by the
978  * formula:
979  *
980  * B
981  * 1 /
982  * ------- | P(x)dx
983  * B - A /
984  * A
985  *
986  * The geometrical interpretation of the integral is the area under the
987  * graph of P(x). P(x) is defined by the length histogram. We calculate
988  * the area in a piecewise fashion, iterating through the length histogram
989  * bins. Each bin is a trapezoid:
990  *
991  * P(x2)
992  * /|
993  * / |
994  * P(x1)/ |
995  * | |
996  * | |
997  * ---+---+--
998  * x1 x2
999  *
1000  * where x1 and x2 are the boundaries of the current histogram, and P(x1)
1001  * and P(x1) are the cumulative fraction of tuples at the boundaries.
1002  *
1003  * The area of each trapezoid is 1/2 * (P(x2) + P(x1)) * (x2 - x1)
1004  *
1005  * The first bin contains the lower bound passed by the caller, so we
1006  * use linear interpolation between the previous and next histogram bin
1007  * boundary to calculate P(x1). Likewise for the last bin: we use linear
1008  * interpolation to calculate P(x2). For the bins in between, x1 and x2
1009  * lie on histogram bin boundaries, so P(x1) and P(x2) are simply:
1010  * P(x1) = (bin index) / (number of bins)
1011  * P(x2) = (bin index + 1 / (number of bins)
1012  */
1013 
1014  /* First bin, the one that contains lower bound */
1015  i = length_hist_bsearch(length_hist_values, length_hist_nvalues, length1, equal);
1016  if (i >= length_hist_nvalues - 1)
1017  return 1.0;
1018 
1019  if (i < 0)
1020  {
1021  i = 0;
1022  pos = 0.0;
1023  }
1024  else
1025  {
1026  /* interpolate length1's position in the bin */
1027  pos = get_len_position(length1,
1028  DatumGetFloat8(length_hist_values[i]),
1029  DatumGetFloat8(length_hist_values[i + 1]));
1030  }
1031  PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
1032  B = length1;
1033 
1034  /*
1035  * In the degenerate case that length1 == length2, simply return
1036  * P(length1). This is not merely an optimization: if length1 == length2,
1037  * we'd divide by zero later on.
1038  */
1039  if (length2 == length1)
1040  return PB;
1041 
1042  /*
1043  * Loop through all the bins, until we hit the last bin, the one that
1044  * contains the upper bound. (if lower and upper bounds are in the same
1045  * bin, this falls out immediately)
1046  */
1047  area = 0.0;
1048  for (; i < length_hist_nvalues - 1; i++)
1049  {
1050  double bin_upper = DatumGetFloat8(length_hist_values[i + 1]);
1051 
1052  /* check if we've reached the last bin */
1053  if (!(bin_upper < length2 || (equal && bin_upper <= length2)))
1054  break;
1055 
1056  /* the upper bound of previous bin is the lower bound of this bin */
1057  A = B;
1058  PA = PB;
1059 
1060  B = bin_upper;
1061  PB = (double) i / (double) (length_hist_nvalues - 1);
1062 
1063  /*
1064  * Add the area of this trapezoid to the total. The point of the
1065  * if-check is to avoid NaN, in the corner case that PA == PB == 0,
1066  * and B - A == Inf. The area of a zero-height trapezoid (PA == PB ==
1067  * 0) is zero, regardless of the width (B - A).
1068  */
1069  if (PA > 0 || PB > 0)
1070  area += 0.5 * (PB + PA) * (B - A);
1071  }
1072 
1073  /* Last bin */
1074  A = B;
1075  PA = PB;
1076 
1077  B = length2; /* last bin ends at the query upper bound */
1078  if (i >= length_hist_nvalues - 1)
1079  pos = 0.0;
1080  else
1081  {
1082  if (DatumGetFloat8(length_hist_values[i]) == DatumGetFloat8(length_hist_values[i + 1]))
1083  pos = 0.0;
1084  else
1085  pos = get_len_position(length2,
1086  DatumGetFloat8(length_hist_values[i]),
1087  DatumGetFloat8(length_hist_values[i + 1]));
1088  }
1089  PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
1090 
1091  if (PA > 0 || PB > 0)
1092  area += 0.5 * (PB + PA) * (B - A);
1093 
1094  /*
1095  * Ok, we have calculated the area, ie. the integral. Divide by width to
1096  * get the requested average.
1097  *
1098  * Avoid NaN arising from infinite / infinite. This happens at least if
1099  * length2 is infinite. It's not clear what the correct value would be in
1100  * that case, so 0.5 seems as good as any value.
1101  */
1102  if (isinf(area) && isinf(length2))
1103  frac = 0.5;
1104  else
1105  frac = area / (length2 - length1);
1106 
1107  return frac;
1108 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3113
#define DatumGetFloat8(X)
Definition: postgres.h:758
#define Assert(condition)
Definition: c.h:804
int i
static int length_hist_bsearch(Datum *length_hist_values, int length_hist_nvalues, double value, bool equal)
static float8 get_len_position(double value, double hist1, double hist2)

◆ calc_multirangesel()

static double calc_multirangesel ( TypeCacheEntry typcache,
VariableStatData vardata,
const MultirangeType constval,
Oid  operator 
)
static

Definition at line 292 of file multirangetypes_selfuncs.c.

References ATTSTATSSLOT_NUMBERS, calc_hist_selectivity(), CLAMP_PROBABILITY, default_multirange_selectivity(), elog, ERROR, free_attstatsslot(), get_attstatsslot(), GETSTRUCT, HeapTupleIsValid, InvalidOid, MultirangeIsEmpty, AttStatsSlot::nnumbers, AttStatsSlot::numbers, and VariableStatData::statsTuple.

Referenced by multirangesel().

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_RANGE_OVERLAPS_MULTIRANGE_OP:
351  case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
352  case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
353  case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
354  case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
355  case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
356  case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
357  case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
358  case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
359  case OID_MULTIRANGE_LEFT_MULTIRANGE_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_MULTIRANGE_RANGE_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_ELEM_CONTAINED_OP:
392  case OID_MULTIRANGE_CONTAINS_ELEM_OP:
393  default:
394  elog(ERROR, "unexpected operator %u", operator);
395  selec = 0.0; /* keep compiler quiet */
396  break;
397  }
398  }
399  else
400  {
401  /*
402  * Calculate selectivity using bound histograms. If that fails for
403  * some reason, e.g no histogram in pg_statistic, use the default
404  * constant estimate for the fraction of non-empty values. This is
405  * still somewhat better than just returning the default estimate,
406  * because this still takes into account the fraction of empty and
407  * NULL tuples, if we had statistics for them.
408  */
409  hist_selec = calc_hist_selectivity(typcache, vardata, constval,
410  operator);
411  if (hist_selec < 0.0)
412  hist_selec = default_multirange_selectivity(operator);
413 
414  /*
415  * Now merge the results for the empty multiranges and histogram
416  * calculations, realizing that the histogram covers only the
417  * non-null, non-empty values.
418  */
419  if (operator == OID_MULTIRANGE_ELEM_CONTAINED_OP ||
420  operator == OID_MULTIRANGE_RANGE_CONTAINED_OP ||
421  operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
422  {
423  /* empty is contained by anything non-empty */
424  selec = (1.0 - empty_frac) * hist_selec + empty_frac;
425  }
426  else
427  {
428  /* with any other operator, empty Op non-empty matches nothing */
429  selec = (1.0 - empty_frac) * hist_selec;
430  }
431  }
432 
433  /* all multirange operators are strict */
434  selec *= (1.0 - null_frac);
435 
436  /* result should be in range, but make sure... */
437  CLAMP_PROBABILITY(selec);
438 
439  return selec;
440 }
#define GETSTRUCT(TUP)
Definition: htup_details.h:654
HeapTuple statsTuple
Definition: selfuncs.h:91
int nnumbers
Definition: lsyscache.h:57
static double calc_hist_selectivity(TypeCacheEntry *typcache, VariableStatData *vardata, const MultirangeType *constval, Oid operator)
FormData_pg_statistic * Form_pg_statistic
Definition: pg_statistic.h:135
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:43
#define ERROR
Definition: elog.h:46
float4 * numbers
Definition: lsyscache.h:56
static double default_multirange_selectivity(Oid operator)
float float4
Definition: c.h:564
#define InvalidOid
Definition: postgres_ext.h:36
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:3177
#define MultirangeIsEmpty(mr)
#define elog(elevel,...)
Definition: elog.h:232
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3294

◆ default_multirange_selectivity()

static double default_multirange_selectivity ( Oid  operator)
static

Definition at line 80 of file multirangetypes_selfuncs.c.

References DEFAULT_INEQ_SEL, and DEFAULT_MULTIRANGE_INEQ_SEL.

Referenced by calc_multirangesel(), and multirangesel().

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 }
#define DEFAULT_INEQ_SEL
Definition: selfuncs.h:37
#define DEFAULT_MULTIRANGE_INEQ_SEL
Definition: selfuncs.h:43

◆ get_distance()

static float8 get_distance ( TypeCacheEntry typcache,
const RangeBound bound1,
const RangeBound bound2 
)
static

Definition at line 907 of file multirangetypes_selfuncs.c.

References DatumGetFloat8, FmgrInfo::fn_oid, FunctionCall2Coll(), get_float8_infinity(), RangeBound::infinite, RangeBound::lower, OidIsValid, TypeCacheEntry::rng_collation, TypeCacheEntry::rng_subdiff_finfo, and RangeBound::val.

Referenced by calc_hist_selectivity_contained(), and calc_hist_selectivity_contains().

908 {
909  bool has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
910 
911  if (!bound1->infinite && !bound2->infinite)
912  {
913  /*
914  * Neither bound is infinite, use subdiff function or return default
915  * value of 1.0 if no subdiff is available.
916  */
917  if (has_subdiff)
918  {
919  float8 res;
920 
922  typcache->rng_collation,
923  bound2->val,
924  bound1->val));
925  /* Reject possible NaN result, also negative result */
926  if (isnan(res) || res < 0.0)
927  return 1.0;
928  else
929  return res;
930  }
931  else
932  return 1.0;
933  }
934  else if (bound1->infinite && bound2->infinite)
935  {
936  /* Both bounds are infinite */
937  if (bound1->lower == bound2->lower)
938  return 0.0;
939  else
940  return get_float8_infinity();
941  }
942  else
943  {
944  /* One bound is infinite, the other is not */
945  return get_float8_infinity();
946  }
947 }
static float8 get_float8_infinity(void)
Definition: float.h:93
Datum val
Definition: rangetypes.h:64
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1148
#define OidIsValid(objectId)
Definition: c.h:710
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:102
double float8
Definition: c.h:565
bool lower
Definition: rangetypes.h:67
#define DatumGetFloat8(X)
Definition: postgres.h:758
Oid fn_oid
Definition: fmgr.h:59
bool infinite
Definition: rangetypes.h:65
Oid rng_collation
Definition: typcache.h:99

◆ get_len_position()

static double get_len_position ( double  value,
double  hist1,
double  hist2 
)
static

Definition at line 862 of file multirangetypes_selfuncs.c.

References value.

Referenced by calc_length_hist_frac().

863 {
864  if (!isinf(hist1) && !isinf(hist2))
865  {
866  /*
867  * Both bounds are finite. The value should be finite too, because it
868  * lies somewhere between the bounds. If it doesn't, just return
869  * something.
870  */
871  if (isinf(value))
872  return 0.5;
873 
874  return 1.0 - (hist2 - value) / (hist2 - hist1);
875  }
876  else if (isinf(hist1) && !isinf(hist2))
877  {
878  /*
879  * Lower bin boundary is -infinite, upper is finite. Return 1.0 to
880  * indicate the value is infinitely far from the lower bound.
881  */
882  return 1.0;
883  }
884  else if (isinf(hist1) && isinf(hist2))
885  {
886  /* same as above, but in reverse */
887  return 0.0;
888  }
889  else
890  {
891  /*
892  * If both bin boundaries are infinite, they should be equal to each
893  * other, and the value should also be infinite and equal to both
894  * bounds. (But don't Assert that, to avoid crashing unnecessarily if
895  * the caller messes up)
896  *
897  * Assume the value to lie in the middle of the infinite bounds.
898  */
899  return 0.5;
900  }
901 }
static struct @142 value

◆ get_position()

static float8 get_position ( TypeCacheEntry typcache,
const RangeBound value,
const RangeBound hist1,
const RangeBound hist2 
)
static

Definition at line 783 of file multirangetypes_selfuncs.c.

References DatumGetFloat8, FmgrInfo::fn_oid, FunctionCall2Coll(), RangeBound::infinite, RangeBound::lower, Max, Min, OidIsValid, TypeCacheEntry::rng_collation, TypeCacheEntry::rng_subdiff_finfo, and RangeBound::val.

Referenced by calc_hist_selectivity_contained(), calc_hist_selectivity_contains(), and calc_hist_selectivity_scalar().

785 {
786  bool has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
787  float8 position;
788 
789  if (!hist1->infinite && !hist2->infinite)
790  {
791  float8 bin_width;
792 
793  /*
794  * Both bounds are finite. Assuming the subtype's comparison function
795  * works sanely, the value must be finite, too, because it lies
796  * somewhere between the bounds. If it doesn't, arbitrarily return
797  * 0.5.
798  */
799  if (value->infinite)
800  return 0.5;
801 
802  /* Can't interpolate without subdiff function */
803  if (!has_subdiff)
804  return 0.5;
805 
806  /* Calculate relative position using subdiff function. */
807  bin_width = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
808  typcache->rng_collation,
809  hist2->val,
810  hist1->val));
811  if (isnan(bin_width) || bin_width <= 0.0)
812  return 0.5; /* punt for NaN or zero-width bin */
813 
814  position = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
815  typcache->rng_collation,
816  value->val,
817  hist1->val))
818  / bin_width;
819 
820  if (isnan(position))
821  return 0.5; /* punt for NaN from subdiff, Inf/Inf, etc */
822 
823  /* Relative position must be in [0,1] range */
824  position = Max(position, 0.0);
825  position = Min(position, 1.0);
826  return position;
827  }
828  else if (hist1->infinite && !hist2->infinite)
829  {
830  /*
831  * Lower bin boundary is -infinite, upper is finite. If the value is
832  * -infinite, return 0.0 to indicate it's equal to the lower bound.
833  * Otherwise return 1.0 to indicate it's infinitely far from the lower
834  * bound.
835  */
836  return ((value->infinite && value->lower) ? 0.0 : 1.0);
837  }
838  else if (!hist1->infinite && hist2->infinite)
839  {
840  /* same as above, but in reverse */
841  return ((value->infinite && !value->lower) ? 1.0 : 0.0);
842  }
843  else
844  {
845  /*
846  * If both bin boundaries are infinite, they should be equal to each
847  * other, and the value should also be infinite and equal to both
848  * bounds. (But don't Assert that, to avoid crashing if a user creates
849  * a datatype with a broken comparison function).
850  *
851  * Assume the value to lie in the middle of the infinite bounds.
852  */
853  return 0.5;
854  }
855 }
#define Min(x, y)
Definition: c.h:986
Datum val
Definition: rangetypes.h:64
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1148
#define OidIsValid(objectId)
Definition: c.h:710
FmgrInfo rng_subdiff_finfo
Definition: typcache.h:102
double float8
Definition: c.h:565
bool lower
Definition: rangetypes.h:67
#define DatumGetFloat8(X)
Definition: postgres.h:758
Oid fn_oid
Definition: fmgr.h:59
#define Max(x, y)
Definition: c.h:980
bool infinite
Definition: rangetypes.h:65
Oid rng_collation
Definition: typcache.h:99

◆ length_hist_bsearch()

static int length_hist_bsearch ( Datum length_hist_values,
int  length_hist_nvalues,
double  value,
bool  equal 
)
static

Definition at line 757 of file multirangetypes_selfuncs.c.

References DatumGetFloat8, lower(), and upper().

Referenced by calc_length_hist_frac().

759 {
760  int lower = -1,
761  upper = length_hist_nvalues - 1,
762  middle;
763 
764  while (lower < upper)
765  {
766  double middleval;
767 
768  middle = (lower + upper + 1) / 2;
769 
770  middleval = DatumGetFloat8(length_hist_values[middle]);
771  if (middleval < value || (equal && middleval <= value))
772  lower = middle;
773  else
774  upper = middle - 1;
775  }
776  return lower;
777 }
static struct @142 value
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3113
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:46
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:77
#define DatumGetFloat8(X)
Definition: postgres.h:758

◆ multirangesel()

Datum multirangesel ( PG_FUNCTION_ARGS  )

Definition at line 139 of file multirangetypes_selfuncs.c.

References generate_unaccent_rules::args, calc_multirangesel(), CLAMP_PROBABILITY, DatumGetMultirangeTypeP, DatumGetRangeTypeP, default_multirange_selectivity(), get_commutator(), get_restriction_variable(), RangeBound::inclusive, RangeBound::infinite, IsA, lower(), RangeBound::lower, make_multirange(), multirange_get_typcache(), PG_GETARG_INT32, PG_GETARG_OID, PG_GETARG_POINTER, PG_RETURN_FLOAT8, range_serialize(), ReleaseVariableStats, TypeCacheEntry::rngelemtype, TypeCacheEntry::rngtype, TypeCacheEntry::type_id, upper(), RangeBound::val, and VariableStatData::vartype.

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, false);
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 }
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define IsA(nodeptr, _type_)
Definition: nodes.h:590
Oid get_commutator(Oid opno)
Definition: lsyscache.c:1480
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:46
bool get_restriction_variable(PlannerInfo *root, List *args, int varRelid, VariableStatData *vardata, Node **other, bool *varonleft)
Definition: selfuncs.c:4825
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
Datum val
Definition: rangetypes.h:64
Definition: nodes.h:539
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
double Selectivity
Definition: nodes.h:672
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:77
unsigned int Oid
Definition: postgres_ext.h:31
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:63
bool inclusive
Definition: rangetypes.h:66
double float8
Definition: c.h:565
#define DatumGetMultirangeTypeP(X)
TypeCacheEntry * multirange_get_typcache(FunctionCallInfo fcinfo, Oid mltrngtypid)
#define PG_GETARG_OID(n)
Definition: fmgr.h:275
static double default_multirange_selectivity(Oid operator)
bool lower
Definition: rangetypes.h:67
struct TypeCacheEntry * rngelemtype
Definition: typcache.h:98
static double calc_multirangesel(TypeCacheEntry *typcache, VariableStatData *vardata, const MultirangeType *constval, Oid operator)
MultirangeType * make_multirange(Oid mltrngtypoid, TypeCacheEntry *rangetyp, int32 range_count, RangeType **ranges)
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:73
bool infinite
Definition: rangetypes.h:65
struct TypeCacheEntry * rngtype
Definition: typcache.h:107
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:101
static SerializedRanges * range_serialize(Ranges *range)
Definition: pg_list.h:50

◆ rbound_bsearch()

static int rbound_bsearch ( TypeCacheEntry typcache,
const RangeBound value,
const RangeBound hist,
int  hist_length,
bool  equal 
)
static

Definition at line 728 of file multirangetypes_selfuncs.c.

References cmp(), lower(), range_cmp_bounds(), and upper().

Referenced by calc_hist_selectivity_contained(), calc_hist_selectivity_contains(), and calc_hist_selectivity_scalar().

730 {
731  int lower = -1,
732  upper = hist_length - 1,
733  cmp,
734  middle;
735 
736  while (lower < upper)
737  {
738  middle = (lower + upper + 1) / 2;
739  cmp = range_cmp_bounds(typcache, &hist[middle], value);
740 
741  if (cmp < 0 || (equal && cmp == 0))
742  lower = middle;
743  else
744  upper = middle - 1;
745  }
746  return lower;
747 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3113
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:46
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:77
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1924
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:747