PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
array_selfuncs.c File Reference
#include "postgres.h"
#include <math.h>
#include "access/htup_details.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_statistic.h"
#include "optimizer/clauses.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
#include "utils/typcache.h"
Include dependency graph for array_selfuncs.c:

Go to the source code of this file.

Macros

#define DEFAULT_CONTAIN_SEL   0.005
 
#define DEFAULT_OVERLAP_SEL   0.01
 
#define DEFAULT_SEL(operator)
 
#define EFFORT   100
 

Functions

static Selectivity calc_arraycontsel (VariableStatData *vardata, Datum constval, Oid elemtype, Oid operator)
 
static Selectivity mcelem_array_selec (ArrayType *array, TypeCacheEntry *typentry, Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, float4 *hist, int nhist, Oid operator, FmgrInfo *cmpfunc)
 
static Selectivity mcelem_array_contain_overlap_selec (Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, Oid operator, FmgrInfo *cmpfunc)
 
static Selectivity mcelem_array_contained_selec (Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, float4 *hist, int nhist, Oid operator, FmgrInfo *cmpfunc)
 
static float * calc_hist (const float4 *hist, int nhist, int n)
 
static float * calc_distr (const float *p, int n, int m, float rest)
 
static int floor_log2 (uint32 n)
 
static bool find_next_mcelem (Datum *mcelem, int nmcelem, Datum value, int *index, FmgrInfo *cmpfunc)
 
static int element_compare (const void *key1, const void *key2, void *arg)
 
static int float_compare_desc (const void *key1, const void *key2)
 
Selectivity scalararraysel_containment (PlannerInfo *root, Node *leftop, Node *rightop, Oid elemtype, bool isEquality, bool useOr, int varRelid)
 
Datum arraycontsel (PG_FUNCTION_ARGS)
 
Datum arraycontjoinsel (PG_FUNCTION_ARGS)
 

Macro Definition Documentation

#define DEFAULT_CONTAIN_SEL   0.005
#define DEFAULT_OVERLAP_SEL   0.01

Definition at line 35 of file array_selfuncs.c.

#define DEFAULT_SEL (   operator)
Value:
((operator) == OID_ARRAY_OVERLAP_OP ? \
#define DEFAULT_CONTAIN_SEL
#define DEFAULT_OVERLAP_SEL
#define OID_ARRAY_OVERLAP_OP
Definition: pg_operator.h:1566

Definition at line 38 of file array_selfuncs.c.

Referenced by arraycontjoinsel(), arraycontsel(), and calc_arraycontsel().

#define EFFORT   100

Function Documentation

Datum arraycontjoinsel ( PG_FUNCTION_ARGS  )

Definition at line 323 of file array_selfuncs.c.

References DEFAULT_SEL, PG_GETARG_OID, and PG_RETURN_FLOAT8.

Referenced by _int_contained_joinsel(), _int_contains_joinsel(), and _int_overlap_joinsel().

324 {
325  /* For the moment this is just a stub */
326  Oid operator = PG_GETARG_OID(1);
327 
328  PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
329 }
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:326
unsigned int Oid
Definition: postgres_ext.h:31
#define PG_GETARG_OID(n)
Definition: fmgr.h:240
#define DEFAULT_SEL(operator)
Datum arraycontsel ( PG_FUNCTION_ARGS  )

Definition at line 243 of file array_selfuncs.c.

References generate_unaccent_rules::args, calc_arraycontsel(), CLAMP_PROBABILITY, DEFAULT_SEL, get_base_element_type(), get_restriction_variable(), InvalidOid, IsA, OID_ARRAY_CONTAINED_OP, OID_ARRAY_CONTAINS_OP, PG_GETARG_INT32, PG_GETARG_OID, PG_GETARG_POINTER, PG_RETURN_FLOAT8, ReleaseVariableStats, and VariableStatData::vartype.

Referenced by _int_contained_sel(), _int_contains_sel(), and _int_overlap_sel().

244 {
246  Oid operator = PG_GETARG_OID(1);
247  List *args = (List *) PG_GETARG_POINTER(2);
248  int varRelid = PG_GETARG_INT32(3);
249  VariableStatData vardata;
250  Node *other;
251  bool varonleft;
252  Selectivity selec;
253  Oid element_typeid;
254 
255  /*
256  * If expression is not (variable op something) or (something op
257  * variable), then punt and return a default estimate.
258  */
259  if (!get_restriction_variable(root, args, varRelid,
260  &vardata, &other, &varonleft))
261  PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
262 
263  /*
264  * Can't do anything useful if the something is not a constant, either.
265  */
266  if (!IsA(other, Const))
267  {
268  ReleaseVariableStats(vardata);
269  PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
270  }
271 
272  /*
273  * The "&&", "@>" and "<@" operators are strict, so we can cope with a
274  * NULL constant right away.
275  */
276  if (((Const *) other)->constisnull)
277  {
278  ReleaseVariableStats(vardata);
279  PG_RETURN_FLOAT8(0.0);
280  }
281 
282  /*
283  * If var is on the right, commute the operator, so that we can assume the
284  * var is on the left in what follows.
285  */
286  if (!varonleft)
287  {
288  if (operator == OID_ARRAY_CONTAINS_OP)
289  operator = OID_ARRAY_CONTAINED_OP;
290  else if (operator == OID_ARRAY_CONTAINED_OP)
291  operator = OID_ARRAY_CONTAINS_OP;
292  }
293 
294  /*
295  * OK, there's a Var and a Const we're dealing with here. We need the
296  * Const to be an array with same element type as column, else we can't do
297  * anything useful. (Such cases will likely fail at runtime, but here
298  * we'd rather just return a default estimate.)
299  */
300  element_typeid = get_base_element_type(((Const *) other)->consttype);
301  if (element_typeid != InvalidOid &&
302  element_typeid == get_base_element_type(vardata.vartype))
303  {
304  selec = calc_arraycontsel(&vardata, ((Const *) other)->constvalue,
305  element_typeid, operator);
306  }
307  else
308  {
309  selec = DEFAULT_SEL(operator);
310  }
311 
312  ReleaseVariableStats(vardata);
313 
314  CLAMP_PROBABILITY(selec);
315 
316  PG_RETURN_FLOAT8((float8) selec);
317 }
#define PG_GETARG_INT32(n)
Definition: fmgr.h:234
#define IsA(nodeptr, _type_)
Definition: nodes.h:561
bool get_restriction_variable(PlannerInfo *root, List *args, int varRelid, VariableStatData *vardata, Node **other, bool *varonleft)
Definition: selfuncs.c:4541
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:326
Definition: nodes.h:510
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
double Selectivity
Definition: nodes.h:640
unsigned int Oid
Definition: postgres_ext.h:31
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
#define OID_ARRAY_CONTAINS_OP
Definition: pg_operator.h:1569
double float8
Definition: c.h:375
#define PG_GETARG_OID(n)
Definition: fmgr.h:240
#define OID_ARRAY_CONTAINED_OP
Definition: pg_operator.h:1572
#define InvalidOid
Definition: postgres_ext.h:36
static Selectivity calc_arraycontsel(VariableStatData *vardata, Datum constval, Oid elemtype, Oid operator)
Oid get_base_element_type(Oid typid)
Definition: lsyscache.c:2557
#define DEFAULT_SEL(operator)
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
Definition: pg_list.h:45
static Selectivity calc_arraycontsel ( VariableStatData vardata,
Datum  constval,
Oid  elemtype,
Oid  operator 
)
static

Definition at line 339 of file array_selfuncs.c.

References ATTSTATSSLOT_NUMBERS, ATTSTATSSLOT_VALUES, TypeCacheEntry::cmp_proc_finfo, DatumGetArrayTypeP, DEFAULT_SEL, FmgrInfo::fn_oid, free_attstatsslot(), get_attstatsslot(), GETSTRUCT, HeapTupleIsValid, InvalidOid, lookup_type_cache(), mcelem_array_selec(), AttStatsSlot::nnumbers, AttStatsSlot::numbers, AttStatsSlot::nvalues, OID_ARRAY_CONTAINED_OP, OidIsValid, pfree(), PointerGetDatum, STATISTIC_KIND_DECHIST, STATISTIC_KIND_MCELEM, statistic_proc_security_check(), VariableStatData::statsTuple, TYPECACHE_CMP_PROC_FINFO, and AttStatsSlot::values.

Referenced by arraycontsel().

341 {
342  Selectivity selec;
343  TypeCacheEntry *typentry;
344  FmgrInfo *cmpfunc;
345  ArrayType *array;
346 
347  /* Get element type's default comparison function */
348  typentry = lookup_type_cache(elemtype, TYPECACHE_CMP_PROC_FINFO);
349  if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
350  return DEFAULT_SEL(operator);
351  cmpfunc = &typentry->cmp_proc_finfo;
352 
353  /*
354  * The caller made sure the const is an array with same element type, so
355  * get it now
356  */
357  array = DatumGetArrayTypeP(constval);
358 
359  if (HeapTupleIsValid(vardata->statsTuple) &&
360  statistic_proc_security_check(vardata, cmpfunc->fn_oid))
361  {
362  Form_pg_statistic stats;
363  AttStatsSlot sslot;
364  AttStatsSlot hslot;
365 
366  stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
367 
368  /* MCELEM will be an array of same type as column */
369  if (get_attstatsslot(&sslot, vardata->statsTuple,
372  {
373  /*
374  * For "array <@ const" case we also need histogram of distinct
375  * element counts.
376  */
377  if (operator != OID_ARRAY_CONTAINED_OP ||
378  !get_attstatsslot(&hslot, vardata->statsTuple,
381  memset(&hslot, 0, sizeof(hslot));
382 
383  /* Use the most-common-elements slot for the array Var. */
384  selec = mcelem_array_selec(array, typentry,
385  sslot.values, sslot.nvalues,
386  sslot.numbers, sslot.nnumbers,
387  hslot.numbers, hslot.nnumbers,
388  operator, cmpfunc);
389 
390  free_attstatsslot(&hslot);
391  free_attstatsslot(&sslot);
392  }
393  else
394  {
395  /* No most-common-elements info, so do without */
396  selec = mcelem_array_selec(array, typentry,
397  NULL, 0, NULL, 0, NULL, 0,
398  operator, cmpfunc);
399  }
400 
401  /*
402  * MCE stats count only non-null rows, so adjust for null rows.
403  */
404  selec *= (1.0 - stats->stanullfrac);
405  }
406  else
407  {
408  /* No stats at all, so do without */
409  selec = mcelem_array_selec(array, typentry,
410  NULL, 0, NULL, 0, NULL, 0,
411  operator, cmpfunc);
412  /* we assume no nulls here, so no stanullfrac correction */
413  }
414 
415  /* If constant was toasted, release the copy we made */
416  if (PointerGetDatum(array) != constval)
417  pfree(array);
418 
419  return selec;
420 }
Definition: fmgr.h:56
#define GETSTRUCT(TUP)
Definition: htup_details.h:656
#define ATTSTATSSLOT_VALUES
Definition: lsyscache.h:39
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
#define PointerGetDatum(X)
Definition: postgres.h:562
bool statistic_proc_security_check(VariableStatData *vardata, Oid func_oid)
Definition: selfuncs.c:5041
double Selectivity
Definition: nodes.h:640
FormData_pg_statistic * Form_pg_statistic
Definition: pg_statistic.h:129
#define OidIsValid(objectId)
Definition: c.h:532
FmgrInfo cmp_proc_finfo
Definition: typcache.h:71
void pfree(void *pointer)
Definition: mcxt.c:949
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define STATISTIC_KIND_DECHIST
Definition: pg_statistic.h:270
float4 * numbers
Definition: lsyscache.h:52
static Selectivity mcelem_array_selec(ArrayType *array, TypeCacheEntry *typentry, Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, float4 *hist, int nhist, Oid operator, FmgrInfo *cmpfunc)
#define OID_ARRAY_CONTAINED_OP
Definition: pg_operator.h:1572
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:310
#define InvalidOid
Definition: postgres_ext.h:36
Oid fn_oid
Definition: fmgr.h:59
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2895
Datum * values
Definition: lsyscache.h:49
#define DEFAULT_SEL(operator)
#define STATISTIC_KIND_MCELEM
Definition: pg_statistic.h:257
#define TYPECACHE_CMP_PROC_FINFO
Definition: typcache.h:120
#define DatumGetArrayTypeP(X)
Definition: array.h:246
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3011
static float * calc_distr ( const float *  p,
int  n,
int  m,
float  rest 
)
static

Definition at line 1012 of file array_selfuncs.c.

References DEFAULT_CONTAIN_SEL, i, palloc(), pfree(), and val.

Referenced by mcelem_array_contained_selec().

1013 {
1014  float *row,
1015  *prev_row,
1016  *tmp;
1017  int i,
1018  j;
1019 
1020  /*
1021  * Since we return only the last row of the matrix and need only the
1022  * current and previous row for calculations, allocate two rows.
1023  */
1024  row = (float *) palloc((m + 1) * sizeof(float));
1025  prev_row = (float *) palloc((m + 1) * sizeof(float));
1026 
1027  /* M[0,0] = 1 */
1028  row[0] = 1.0f;
1029  for (i = 1; i <= n; i++)
1030  {
1031  float t = p[i - 1];
1032 
1033  /* Swap rows */
1034  tmp = row;
1035  row = prev_row;
1036  prev_row = tmp;
1037 
1038  /* Calculate next row */
1039  for (j = 0; j <= i && j <= m; j++)
1040  {
1041  float val = 0.0f;
1042 
1043  if (j < i)
1044  val += prev_row[j] * (1.0f - t);
1045  if (j > 0)
1046  val += prev_row[j - 1] * t;
1047  row[j] = val;
1048  }
1049  }
1050 
1051  /*
1052  * The presence of many distinct rare (not in "p") elements materially
1053  * decreases selectivity. Model their collective occurrence with the
1054  * Poisson distribution.
1055  */
1056  if (rest > DEFAULT_CONTAIN_SEL)
1057  {
1058  float t;
1059 
1060  /* Swap rows */
1061  tmp = row;
1062  row = prev_row;
1063  prev_row = tmp;
1064 
1065  for (i = 0; i <= m; i++)
1066  row[i] = 0.0f;
1067 
1068  /* Value of Poisson distribution for 0 occurrences */
1069  t = exp(-rest);
1070 
1071  /*
1072  * Calculate convolution of previously computed distribution and the
1073  * Poisson distribution.
1074  */
1075  for (i = 0; i <= m; i++)
1076  {
1077  for (j = 0; j <= m - i; j++)
1078  row[j + i] += prev_row[j] * t;
1079 
1080  /* Get Poisson distribution value for (i + 1) occurrences */
1081  t *= rest / (float) (i + 1);
1082  }
1083  }
1084 
1085  pfree(prev_row);
1086  return row;
1087 }
#define DEFAULT_CONTAIN_SEL
void pfree(void *pointer)
Definition: mcxt.c:949
void * palloc(Size size)
Definition: mcxt.c:848
int i
long val
Definition: informix.c:689
static float * calc_hist ( const float4 hist,
int  nhist,
int  n 
)
static

Definition at line 923 of file array_selfuncs.c.

References i, palloc(), and val.

Referenced by mcelem_array_contained_selec().

924 {
925  float *hist_part;
926  int k,
927  i = 0;
928  float prev_interval = 0,
929  next_interval;
930  float frac;
931 
932  hist_part = (float *) palloc((n + 1) * sizeof(float));
933 
934  /*
935  * frac is a probability contribution for each interval between histogram
936  * values. We have nhist - 1 intervals, so contribution of each one will
937  * be 1 / (nhist - 1).
938  */
939  frac = 1.0f / ((float) (nhist - 1));
940 
941  for (k = 0; k <= n; k++)
942  {
943  int count = 0;
944 
945  /*
946  * Count the histogram boundaries equal to k. (Although the histogram
947  * should theoretically contain only exact integers, entries are
948  * floats so there could be roundoff error in large values. Treat any
949  * fractional value as equal to the next larger k.)
950  */
951  while (i < nhist && hist[i] <= k)
952  {
953  count++;
954  i++;
955  }
956 
957  if (count > 0)
958  {
959  /* k is an exact bound for at least one histogram box. */
960  float val;
961 
962  /* Find length between current histogram value and the next one */
963  if (i < nhist)
964  next_interval = hist[i] - hist[i - 1];
965  else
966  next_interval = 0;
967 
968  /*
969  * count - 1 histogram boxes contain k exclusively. They
970  * contribute a total of (count - 1) * frac probability. Also
971  * factor in the partial histogram boxes on either side.
972  */
973  val = (float) (count - 1);
974  if (next_interval > 0)
975  val += 0.5f / next_interval;
976  if (prev_interval > 0)
977  val += 0.5f / prev_interval;
978  hist_part[k] = frac * val;
979 
980  prev_interval = next_interval;
981  }
982  else
983  {
984  /* k does not appear as an exact histogram bound. */
985  if (prev_interval > 0)
986  hist_part[k] = frac / prev_interval;
987  else
988  hist_part[k] = 0.0f;
989  }
990  }
991 
992  return hist_part;
993 }
void * palloc(Size size)
Definition: mcxt.c:848
int i
long val
Definition: informix.c:689
static int element_compare ( const void *  key1,
const void *  key2,
void *  arg 
)
static

Definition at line 1167 of file array_selfuncs.c.

References DatumGetInt32, DEFAULT_COLLATION_OID, and FunctionCall2Coll().

Referenced by find_next_mcelem(), mcelem_array_contain_overlap_selec(), mcelem_array_contained_selec(), and mcelem_array_selec().

1168 {
1169  Datum d1 = *((const Datum *) key1);
1170  Datum d2 = *((const Datum *) key2);
1171  FmgrInfo *cmpfunc = (FmgrInfo *) arg;
1172  Datum c;
1173 
1174  c = FunctionCall2Coll(cmpfunc, DEFAULT_COLLATION_OID, d1, d2);
1175  return DatumGetInt32(c);
1176 }
Definition: fmgr.h:56
#define DatumGetInt32(X)
Definition: postgres.h:478
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1042
char * c
#define DEFAULT_COLLATION_OID
Definition: pg_collation.h:75
uintptr_t Datum
Definition: postgres.h:372
void * arg
static bool find_next_mcelem ( Datum mcelem,
int  nmcelem,
Datum  value,
int *  index,
FmgrInfo cmpfunc 
)
static

Definition at line 1132 of file array_selfuncs.c.

References element_compare(), and i.

Referenced by mcelem_array_contain_overlap_selec().

1134 {
1135  int l = *index,
1136  r = nmcelem - 1,
1137  i,
1138  res;
1139 
1140  while (l <= r)
1141  {
1142  i = (l + r) / 2;
1143  res = element_compare(&mcelem[i], &value, cmpfunc);
1144  if (res == 0)
1145  {
1146  *index = i;
1147  return true;
1148  }
1149  else if (res < 0)
1150  l = i + 1;
1151  else
1152  r = i - 1;
1153  }
1154  *index = l;
1155  return false;
1156 }
static int element_compare(const void *key1, const void *key2, void *arg)
Definition: type.h:89
static struct @121 value
int i
static int float_compare_desc ( const void *  key1,
const void *  key2 
)
static

Definition at line 1182 of file array_selfuncs.c.

Referenced by mcelem_array_contained_selec().

1183 {
1184  float d1 = *((const float *) key1);
1185  float d2 = *((const float *) key2);
1186 
1187  if (d1 > d2)
1188  return -1;
1189  else if (d1 < d2)
1190  return 1;
1191  else
1192  return 0;
1193 }
static int floor_log2 ( uint32  n)
static

Definition at line 1091 of file array_selfuncs.c.

Referenced by mcelem_array_contain_overlap_selec().

1092 {
1093  int logval = 0;
1094 
1095  if (n == 0)
1096  return -1;
1097  if (n >= (1 << 16))
1098  {
1099  n >>= 16;
1100  logval += 16;
1101  }
1102  if (n >= (1 << 8))
1103  {
1104  n >>= 8;
1105  logval += 8;
1106  }
1107  if (n >= (1 << 4))
1108  {
1109  n >>= 4;
1110  logval += 4;
1111  }
1112  if (n >= (1 << 2))
1113  {
1114  n >>= 2;
1115  logval += 2;
1116  }
1117  if (n >= (1 << 1))
1118  {
1119  logval += 1;
1120  }
1121  return logval;
1122 }
static Selectivity mcelem_array_contain_overlap_selec ( Datum mcelem,
int  nmcelem,
float4 numbers,
int  nnumbers,
Datum array_data,
int  nitems,
Oid  operator,
FmgrInfo cmpfunc 
)
static

Definition at line 523 of file array_selfuncs.c.

References CLAMP_PROBABILITY, cmp(), DEFAULT_CONTAIN_SEL, element_compare(), find_next_mcelem(), floor_log2(), i, Min, and OID_ARRAY_CONTAINS_OP.

Referenced by mcelem_array_selec(), and scalararraysel_containment().

527 {
528  Selectivity selec,
529  elem_selec;
530  int mcelem_index,
531  i;
532  bool use_bsearch;
533  float4 minfreq;
534 
535  /*
536  * There should be three more Numbers than Values, because the last three
537  * cells should hold minimal and maximal frequency among the non-null
538  * elements, and then the frequency of null elements. Ignore the Numbers
539  * if not right.
540  */
541  if (nnumbers != nmcelem + 3)
542  {
543  numbers = NULL;
544  nnumbers = 0;
545  }
546 
547  if (numbers)
548  {
549  /* Grab the lowest observed frequency */
550  minfreq = numbers[nmcelem];
551  }
552  else
553  {
554  /* Without statistics make some default assumptions */
555  minfreq = 2 * (float4) DEFAULT_CONTAIN_SEL;
556  }
557 
558  /* Decide whether it is faster to use binary search or not. */
559  if (nitems * floor_log2((uint32) nmcelem) < nmcelem + nitems)
560  use_bsearch = true;
561  else
562  use_bsearch = false;
563 
564  if (operator == OID_ARRAY_CONTAINS_OP)
565  {
566  /*
567  * Initial selectivity for "column @> const" query is 1.0, and it will
568  * be decreased with each element of constant array.
569  */
570  selec = 1.0;
571  }
572  else
573  {
574  /*
575  * Initial selectivity for "column && const" query is 0.0, and it will
576  * be increased with each element of constant array.
577  */
578  selec = 0.0;
579  }
580 
581  /* Scan mcelem and array in parallel. */
582  mcelem_index = 0;
583  for (i = 0; i < nitems; i++)
584  {
585  bool match = false;
586 
587  /* Ignore any duplicates in the array data. */
588  if (i > 0 &&
589  element_compare(&array_data[i - 1], &array_data[i], cmpfunc) == 0)
590  continue;
591 
592  /* Find the smallest MCELEM >= this array item. */
593  if (use_bsearch)
594  {
595  match = find_next_mcelem(mcelem, nmcelem, array_data[i],
596  &mcelem_index, cmpfunc);
597  }
598  else
599  {
600  while (mcelem_index < nmcelem)
601  {
602  int cmp = element_compare(&mcelem[mcelem_index],
603  &array_data[i],
604  cmpfunc);
605 
606  if (cmp < 0)
607  mcelem_index++;
608  else
609  {
610  if (cmp == 0)
611  match = true; /* mcelem is found */
612  break;
613  }
614  }
615  }
616 
617  if (match && numbers)
618  {
619  /* MCELEM matches the array item; use its frequency. */
620  elem_selec = numbers[mcelem_index];
621  mcelem_index++;
622  }
623  else
624  {
625  /*
626  * The element is not in MCELEM. Punt, but assume that the
627  * selectivity cannot be more than minfreq / 2.
628  */
629  elem_selec = Min(DEFAULT_CONTAIN_SEL, minfreq / 2);
630  }
631 
632  /*
633  * Update overall selectivity using the current element's selectivity
634  * and an assumption of element occurrence independence.
635  */
636  if (operator == OID_ARRAY_CONTAINS_OP)
637  selec *= elem_selec;
638  else
639  selec = selec + elem_selec - selec * elem_selec;
640 
641  /* Clamp intermediate results to stay sane despite roundoff error */
642  CLAMP_PROBABILITY(selec);
643  }
644 
645  return selec;
646 }
static int element_compare(const void *key1, const void *key2, void *arg)
#define DEFAULT_CONTAIN_SEL
#define Min(x, y)
Definition: c.h:812
double Selectivity
Definition: nodes.h:640
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
#define OID_ARRAY_CONTAINS_OP
Definition: pg_operator.h:1569
unsigned int uint32
Definition: c.h:258
float float4
Definition: c.h:374
static bool find_next_mcelem(Datum *mcelem, int nmcelem, Datum value, int *index, FmgrInfo *cmpfunc)
static int floor_log2(uint32 n)
int i
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
static Selectivity mcelem_array_contained_selec ( Datum mcelem,
int  nmcelem,
float4 numbers,
int  nnumbers,
Datum array_data,
int  nitems,
float4 hist,
int  nhist,
Oid  operator,
FmgrInfo cmpfunc 
)
static

Definition at line 698 of file array_selfuncs.c.

References calc_distr(), calc_hist(), CLAMP_PROBABILITY, cmp(), DEFAULT_CONTAIN_SEL, EFFORT, element_compare(), float_compare_desc(), i, Min, palloc(), pfree(), and qsort.

Referenced by mcelem_array_selec(), and scalararraysel_containment().

703 {
704  int mcelem_index,
705  i,
706  unique_nitems = 0;
707  float selec,
708  minfreq,
709  nullelem_freq;
710  float *dist,
711  *mcelem_dist,
712  *hist_part;
713  float avg_count,
714  mult,
715  rest;
716  float *elem_selec;
717 
718  /*
719  * There should be three more Numbers than Values in the MCELEM slot,
720  * because the last three cells should hold minimal and maximal frequency
721  * among the non-null elements, and then the frequency of null elements.
722  * Punt if not right, because we can't do much without the element freqs.
723  */
724  if (numbers == NULL || nnumbers != nmcelem + 3)
725  return DEFAULT_CONTAIN_SEL;
726 
727  /* Can't do much without a count histogram, either */
728  if (hist == NULL || nhist < 3)
729  return DEFAULT_CONTAIN_SEL;
730 
731  /*
732  * Grab some of the summary statistics that compute_array_stats() stores:
733  * lowest frequency, frequency of null elements, and average distinct
734  * element count.
735  */
736  minfreq = numbers[nmcelem];
737  nullelem_freq = numbers[nmcelem + 2];
738  avg_count = hist[nhist - 1];
739 
740  /*
741  * "rest" will be the sum of the frequencies of all elements not
742  * represented in MCELEM. The average distinct element count is the sum
743  * of the frequencies of *all* elements. Begin with that; we will proceed
744  * to subtract the MCELEM frequencies.
745  */
746  rest = avg_count;
747 
748  /*
749  * mult is a multiplier representing estimate of probability that each
750  * mcelem that is not present in constant doesn't occur.
751  */
752  mult = 1.0f;
753 
754  /*
755  * elem_selec is array of estimated frequencies for elements in the
756  * constant.
757  */
758  elem_selec = (float *) palloc(sizeof(float) * nitems);
759 
760  /* Scan mcelem and array in parallel. */
761  mcelem_index = 0;
762  for (i = 0; i < nitems; i++)
763  {
764  bool match = false;
765 
766  /* Ignore any duplicates in the array data. */
767  if (i > 0 &&
768  element_compare(&array_data[i - 1], &array_data[i], cmpfunc) == 0)
769  continue;
770 
771  /*
772  * Iterate over MCELEM until we find an entry greater than or equal to
773  * this element of the constant. Update "rest" and "mult" for mcelem
774  * entries skipped over.
775  */
776  while (mcelem_index < nmcelem)
777  {
778  int cmp = element_compare(&mcelem[mcelem_index],
779  &array_data[i],
780  cmpfunc);
781 
782  if (cmp < 0)
783  {
784  mult *= (1.0f - numbers[mcelem_index]);
785  rest -= numbers[mcelem_index];
786  mcelem_index++;
787  }
788  else
789  {
790  if (cmp == 0)
791  match = true; /* mcelem is found */
792  break;
793  }
794  }
795 
796  if (match)
797  {
798  /* MCELEM matches the array item. */
799  elem_selec[unique_nitems] = numbers[mcelem_index];
800  /* "rest" is decremented for all mcelems, matched or not */
801  rest -= numbers[mcelem_index];
802  mcelem_index++;
803  }
804  else
805  {
806  /*
807  * The element is not in MCELEM. Punt, but assume that the
808  * selectivity cannot be more than minfreq / 2.
809  */
810  elem_selec[unique_nitems] = Min(DEFAULT_CONTAIN_SEL,
811  minfreq / 2);
812  }
813 
814  unique_nitems++;
815  }
816 
817  /*
818  * If we handled all constant elements without exhausting the MCELEM
819  * array, finish walking it to complete calculation of "rest" and "mult".
820  */
821  while (mcelem_index < nmcelem)
822  {
823  mult *= (1.0f - numbers[mcelem_index]);
824  rest -= numbers[mcelem_index];
825  mcelem_index++;
826  }
827 
828  /*
829  * The presence of many distinct rare elements materially decreases
830  * selectivity. Use the Poisson distribution to estimate the probability
831  * of a column value having zero occurrences of such elements. See above
832  * for the definition of "rest".
833  */
834  mult *= exp(-rest);
835 
836  /*----------
837  * Using the distinct element count histogram requires
838  * O(unique_nitems * (nmcelem + unique_nitems))
839  * operations. Beyond a certain computational cost threshold, it's
840  * reasonable to sacrifice accuracy for decreased planning time. We limit
841  * the number of operations to EFFORT * nmcelem; since nmcelem is limited
842  * by the column's statistics target, the work done is user-controllable.
843  *
844  * If the number of operations would be too large, we can reduce it
845  * without losing all accuracy by reducing unique_nitems and considering
846  * only the most-common elements of the constant array. To make the
847  * results exactly match what we would have gotten with only those
848  * elements to start with, we'd have to remove any discarded elements'
849  * frequencies from "mult", but since this is only an approximation
850  * anyway, we don't bother with that. Therefore it's sufficient to qsort
851  * elem_selec[] and take the largest elements. (They will no longer match
852  * up with the elements of array_data[], but we don't care.)
853  *----------
854  */
855 #define EFFORT 100
856 
857  if ((nmcelem + unique_nitems) > 0 &&
858  unique_nitems > EFFORT * nmcelem / (nmcelem + unique_nitems))
859  {
860  /*
861  * Use the quadratic formula to solve for largest allowable N. We
862  * have A = 1, B = nmcelem, C = - EFFORT * nmcelem.
863  */
864  double b = (double) nmcelem;
865  int n;
866 
867  n = (int) ((sqrt(b * b + 4 * EFFORT * b) - b) / 2);
868 
869  /* Sort, then take just the first n elements */
870  qsort(elem_selec, unique_nitems, sizeof(float),
872  unique_nitems = n;
873  }
874 
875  /*
876  * Calculate probabilities of each distinct element count for both mcelems
877  * and constant elements. At this point, assume independent element
878  * occurrence.
879  */
880  dist = calc_distr(elem_selec, unique_nitems, unique_nitems, 0.0f);
881  mcelem_dist = calc_distr(numbers, nmcelem, unique_nitems, rest);
882 
883  /* ignore hist[nhist-1], which is the average not a histogram member */
884  hist_part = calc_hist(hist, nhist - 1, unique_nitems);
885 
886  selec = 0.0f;
887  for (i = 0; i <= unique_nitems; i++)
888  {
889  /*
890  * mult * dist[i] / mcelem_dist[i] gives us probability of qual
891  * matching from assumption of independent element occurrence with the
892  * condition that distinct element count = i.
893  */
894  if (mcelem_dist[i] > 0)
895  selec += hist_part[i] * mult * dist[i] / mcelem_dist[i];
896  }
897 
898  pfree(dist);
899  pfree(mcelem_dist);
900  pfree(hist_part);
901  pfree(elem_selec);
902 
903  /* Take into account occurrence of NULL element. */
904  selec *= (1.0f - nullelem_freq);
905 
906  CLAMP_PROBABILITY(selec);
907 
908  return selec;
909 }
static int element_compare(const void *key1, const void *key2, void *arg)
#define DEFAULT_CONTAIN_SEL
#define Min(x, y)
Definition: c.h:812
static float * calc_hist(const float4 *hist, int nhist, int n)
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
void pfree(void *pointer)
Definition: mcxt.c:949
static float * calc_distr(const float *p, int n, int m, float rest)
#define EFFORT
void * palloc(Size size)
Definition: mcxt.c:848
int i
#define qsort(a, b, c, d)
Definition: port.h:447
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
static int float_compare_desc(const void *key1, const void *key2)
static Selectivity mcelem_array_selec ( ArrayType array,
TypeCacheEntry typentry,
Datum mcelem,
int  nmcelem,
float4 numbers,
int  nnumbers,
float4 hist,
int  nhist,
Oid  operator,
FmgrInfo cmpfunc 
)
static

Definition at line 430 of file array_selfuncs.c.

References deconstruct_array(), element_compare(), elog, ERROR, i, mcelem_array_contain_overlap_selec(), mcelem_array_contained_selec(), OID_ARRAY_CONTAINED_OP, OID_ARRAY_CONTAINS_OP, OID_ARRAY_OVERLAP_OP, pfree(), qsort_arg(), TypeCacheEntry::typalign, TypeCacheEntry::typbyval, TypeCacheEntry::type_id, and TypeCacheEntry::typlen.

Referenced by calc_arraycontsel().

435 {
436  Selectivity selec;
437  int num_elems;
438  Datum *elem_values;
439  bool *elem_nulls;
440  bool null_present;
441  int nonnull_nitems;
442  int i;
443 
444  /*
445  * Prepare constant array data for sorting. Sorting lets us find unique
446  * elements and efficiently merge with the MCELEM array.
447  */
448  deconstruct_array(array,
449  typentry->type_id,
450  typentry->typlen,
451  typentry->typbyval,
452  typentry->typalign,
453  &elem_values, &elem_nulls, &num_elems);
454 
455  /* Collapse out any null elements */
456  nonnull_nitems = 0;
457  null_present = false;
458  for (i = 0; i < num_elems; i++)
459  {
460  if (elem_nulls[i])
461  null_present = true;
462  else
463  elem_values[nonnull_nitems++] = elem_values[i];
464  }
465 
466  /*
467  * Query "column @> '{anything, null}'" matches nothing. For the other
468  * two operators, presence of a null in the constant can be ignored.
469  */
470  if (null_present && operator == OID_ARRAY_CONTAINS_OP)
471  {
472  pfree(elem_values);
473  pfree(elem_nulls);
474  return (Selectivity) 0.0;
475  }
476 
477  /* Sort extracted elements using their default comparison function. */
478  qsort_arg(elem_values, nonnull_nitems, sizeof(Datum),
479  element_compare, cmpfunc);
480 
481  /* Separate cases according to operator */
482  if (operator == OID_ARRAY_CONTAINS_OP || operator == OID_ARRAY_OVERLAP_OP)
483  selec = mcelem_array_contain_overlap_selec(mcelem, nmcelem,
484  numbers, nnumbers,
485  elem_values, nonnull_nitems,
486  operator, cmpfunc);
487  else if (operator == OID_ARRAY_CONTAINED_OP)
488  selec = mcelem_array_contained_selec(mcelem, nmcelem,
489  numbers, nnumbers,
490  elem_values, nonnull_nitems,
491  hist, nhist,
492  operator, cmpfunc);
493  else
494  {
495  elog(ERROR, "arraycontsel called for unrecognized operator %u",
496  operator);
497  selec = 0.0; /* keep compiler quiet */
498  }
499 
500  pfree(elem_values);
501  pfree(elem_nulls);
502  return selec;
503 }
static int element_compare(const void *key1, const void *key2, void *arg)
double Selectivity
Definition: nodes.h:640
int16 typlen
Definition: typcache.h:37
bool typbyval
Definition: typcache.h:38
#define OID_ARRAY_CONTAINS_OP
Definition: pg_operator.h:1569
void pfree(void *pointer)
Definition: mcxt.c:949
#define ERROR
Definition: elog.h:43
#define OID_ARRAY_OVERLAP_OP
Definition: pg_operator.h:1566
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
#define OID_ARRAY_CONTAINED_OP
Definition: pg_operator.h:1572
uintptr_t Datum
Definition: postgres.h:372
static Selectivity mcelem_array_contained_selec(Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, float4 *hist, int nhist, Oid operator, FmgrInfo *cmpfunc)
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3449
char typalign
Definition: typcache.h:39
int i
#define elog
Definition: elog.h:219
static Selectivity mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, Oid operator, FmgrInfo *cmpfunc)
Selectivity scalararraysel_containment ( PlannerInfo root,
Node leftop,
Node rightop,
Oid  elemtype,
bool  isEquality,
bool  useOr,
int  varRelid 
)

Definition at line 83 of file array_selfuncs.c.

References ATTSTATSSLOT_NUMBERS, ATTSTATSSLOT_VALUES, CLAMP_PROBABILITY, TypeCacheEntry::cmp_proc_finfo, examine_variable(), FmgrInfo::fn_oid, free_attstatsslot(), get_attstatsslot(), GETSTRUCT, HeapTupleIsValid, InvalidOid, IsA, lookup_type_cache(), mcelem_array_contain_overlap_selec(), mcelem_array_contained_selec(), AttStatsSlot::nnumbers, AttStatsSlot::numbers, AttStatsSlot::nvalues, OID_ARRAY_CONTAINED_OP, OID_ARRAY_CONTAINS_OP, OidIsValid, VariableStatData::rel, ReleaseVariableStats, STATISTIC_KIND_DECHIST, STATISTIC_KIND_MCELEM, statistic_proc_security_check(), VariableStatData::statsTuple, TYPECACHE_CMP_PROC_FINFO, and AttStatsSlot::values.

Referenced by scalararraysel().

87 {
88  Selectivity selec;
89  VariableStatData vardata;
90  Datum constval;
91  TypeCacheEntry *typentry;
92  FmgrInfo *cmpfunc;
93 
94  /*
95  * rightop must be a variable, else punt.
96  */
97  examine_variable(root, rightop, varRelid, &vardata);
98  if (!vardata.rel)
99  {
100  ReleaseVariableStats(vardata);
101  return -1.0;
102  }
103 
104  /*
105  * leftop must be a constant, else punt.
106  */
107  if (!IsA(leftop, Const))
108  {
109  ReleaseVariableStats(vardata);
110  return -1.0;
111  }
112  if (((Const *) leftop)->constisnull)
113  {
114  /* qual can't succeed if null on left */
115  ReleaseVariableStats(vardata);
116  return (Selectivity) 0.0;
117  }
118  constval = ((Const *) leftop)->constvalue;
119 
120  /* Get element type's default comparison function */
121  typentry = lookup_type_cache(elemtype, TYPECACHE_CMP_PROC_FINFO);
122  if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
123  {
124  ReleaseVariableStats(vardata);
125  return -1.0;
126  }
127  cmpfunc = &typentry->cmp_proc_finfo;
128 
129  /*
130  * If the operator is <>, swap ANY/ALL, then invert the result later.
131  */
132  if (!isEquality)
133  useOr = !useOr;
134 
135  /* Get array element stats for var, if available */
136  if (HeapTupleIsValid(vardata.statsTuple) &&
137  statistic_proc_security_check(&vardata, cmpfunc->fn_oid))
138  {
139  Form_pg_statistic stats;
140  AttStatsSlot sslot;
141  AttStatsSlot hslot;
142 
143  stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
144 
145  /* MCELEM will be an array of same type as element */
146  if (get_attstatsslot(&sslot, vardata.statsTuple,
149  {
150  /* For ALL case, also get histogram of distinct-element counts */
151  if (useOr ||
152  !get_attstatsslot(&hslot, vardata.statsTuple,
155  memset(&hslot, 0, sizeof(hslot));
156 
157  /*
158  * For = ANY, estimate as var @> ARRAY[const].
159  *
160  * For = ALL, estimate as var <@ ARRAY[const].
161  */
162  if (useOr)
164  sslot.nvalues,
165  sslot.numbers,
166  sslot.nnumbers,
167  &constval, 1,
169  cmpfunc);
170  else
171  selec = mcelem_array_contained_selec(sslot.values,
172  sslot.nvalues,
173  sslot.numbers,
174  sslot.nnumbers,
175  &constval, 1,
176  hslot.numbers,
177  hslot.nnumbers,
179  cmpfunc);
180 
181  free_attstatsslot(&hslot);
182  free_attstatsslot(&sslot);
183  }
184  else
185  {
186  /* No most-common-elements info, so do without */
187  if (useOr)
188  selec = mcelem_array_contain_overlap_selec(NULL, 0,
189  NULL, 0,
190  &constval, 1,
192  cmpfunc);
193  else
194  selec = mcelem_array_contained_selec(NULL, 0,
195  NULL, 0,
196  &constval, 1,
197  NULL, 0,
199  cmpfunc);
200  }
201 
202  /*
203  * MCE stats count only non-null rows, so adjust for null rows.
204  */
205  selec *= (1.0 - stats->stanullfrac);
206  }
207  else
208  {
209  /* No stats at all, so do without */
210  if (useOr)
211  selec = mcelem_array_contain_overlap_selec(NULL, 0,
212  NULL, 0,
213  &constval, 1,
215  cmpfunc);
216  else
217  selec = mcelem_array_contained_selec(NULL, 0,
218  NULL, 0,
219  &constval, 1,
220  NULL, 0,
222  cmpfunc);
223  /* we assume no nulls here, so no stanullfrac correction */
224  }
225 
226  ReleaseVariableStats(vardata);
227 
228  /*
229  * If the operator is <>, invert the results.
230  */
231  if (!isEquality)
232  selec = 1.0 - selec;
233 
234  CLAMP_PROBABILITY(selec);
235 
236  return selec;
237 }
Definition: fmgr.h:56
#define IsA(nodeptr, _type_)
Definition: nodes.h:561
#define GETSTRUCT(TUP)
Definition: htup_details.h:656
#define ATTSTATSSLOT_VALUES
Definition: lsyscache.h:39
HeapTuple statsTuple
Definition: selfuncs.h:71
int nnumbers
Definition: lsyscache.h:53
bool statistic_proc_security_check(VariableStatData *vardata, Oid func_oid)
Definition: selfuncs.c:5041
RelOptInfo * rel
Definition: selfuncs.h:70
double Selectivity
Definition: nodes.h:640
FormData_pg_statistic * Form_pg_statistic
Definition: pg_statistic.h:129
#define OidIsValid(objectId)
Definition: c.h:532
#define CLAMP_PROBABILITY(p)
Definition: selfuncs.h:57
FmgrInfo cmp_proc_finfo
Definition: typcache.h:71
#define OID_ARRAY_CONTAINS_OP
Definition: pg_operator.h:1569
#define ATTSTATSSLOT_NUMBERS
Definition: lsyscache.h:40
#define STATISTIC_KIND_DECHIST
Definition: pg_statistic.h:270
float4 * numbers
Definition: lsyscache.h:52
#define OID_ARRAY_CONTAINED_OP
Definition: pg_operator.h:1572
uintptr_t Datum
Definition: postgres.h:372
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:310
#define InvalidOid
Definition: postgres_ext.h:36
Oid fn_oid
Definition: fmgr.h:59
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
void examine_variable(PlannerInfo *root, Node *node, int varRelid, VariableStatData *vardata)
Definition: selfuncs.c:4663
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
Definition: lsyscache.c:2895
Datum * values
Definition: lsyscache.h:49
static Selectivity mcelem_array_contained_selec(Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, float4 *hist, int nhist, Oid operator, FmgrInfo *cmpfunc)
#define ReleaseVariableStats(vardata)
Definition: selfuncs.h:81
#define STATISTIC_KIND_MCELEM
Definition: pg_statistic.h:257
#define TYPECACHE_CMP_PROC_FINFO
Definition: typcache.h:120
static Selectivity mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, Oid operator, FmgrInfo *cmpfunc)
void free_attstatsslot(AttStatsSlot *sslot)
Definition: lsyscache.c:3011