PostgreSQL Source Code  git master
selfuncs.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * selfuncs.c
4  * Selectivity functions and index cost estimation functions for
5  * standard operators and index access methods.
6  *
7  * Selectivity routines are registered in the pg_operator catalog
8  * in the "oprrest" and "oprjoin" attributes.
9  *
10  * Index cost functions are located via the index AM's API struct,
11  * which is obtained from the handler function registered in pg_am.
12  *
13  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
14  * Portions Copyright (c) 1994, Regents of the University of California
15  *
16  *
17  * IDENTIFICATION
18  * src/backend/utils/adt/selfuncs.c
19  *
20  *-------------------------------------------------------------------------
21  */
22 
23 /*----------
24  * Operator selectivity estimation functions are called to estimate the
25  * selectivity of WHERE clauses whose top-level operator is their operator.
26  * We divide the problem into two cases:
27  * Restriction clause estimation: the clause involves vars of just
28  * one relation.
29  * Join clause estimation: the clause involves vars of multiple rels.
30  * Join selectivity estimation is far more difficult and usually less accurate
31  * than restriction estimation.
32  *
33  * When dealing with the inner scan of a nestloop join, we consider the
34  * join's joinclauses as restriction clauses for the inner relation, and
35  * treat vars of the outer relation as parameters (a/k/a constants of unknown
36  * values). So, restriction estimators need to be able to accept an argument
37  * telling which relation is to be treated as the variable.
38  *
39  * The call convention for a restriction estimator (oprrest function) is
40  *
41  * Selectivity oprrest (PlannerInfo *root,
42  * Oid operator,
43  * List *args,
44  * int varRelid);
45  *
46  * root: general information about the query (rtable and RelOptInfo lists
47  * are particularly important for the estimator).
48  * operator: OID of the specific operator in question.
49  * args: argument list from the operator clause.
50  * varRelid: if not zero, the relid (rtable index) of the relation to
51  * be treated as the variable relation. May be zero if the args list
52  * is known to contain vars of only one relation.
53  *
54  * This is represented at the SQL level (in pg_proc) as
55  *
56  * float8 oprrest (internal, oid, internal, int4);
57  *
58  * The result is a selectivity, that is, a fraction (0 to 1) of the rows
59  * of the relation that are expected to produce a TRUE result for the
60  * given operator.
61  *
62  * The call convention for a join estimator (oprjoin function) is similar
63  * except that varRelid is not needed, and instead join information is
64  * supplied:
65  *
66  * Selectivity oprjoin (PlannerInfo *root,
67  * Oid operator,
68  * List *args,
69  * JoinType jointype,
70  * SpecialJoinInfo *sjinfo);
71  *
72  * float8 oprjoin (internal, oid, internal, int2, internal);
73  *
74  * (Before Postgres 8.4, join estimators had only the first four of these
75  * parameters. That signature is still allowed, but deprecated.) The
76  * relationship between jointype and sjinfo is explained in the comments for
77  * clause_selectivity() --- the short version is that jointype is usually
78  * best ignored in favor of examining sjinfo.
79  *
80  * Join selectivity for regular inner and outer joins is defined as the
81  * fraction (0 to 1) of the cross product of the relations that is expected
82  * to produce a TRUE result for the given operator. For both semi and anti
83  * joins, however, the selectivity is defined as the fraction of the left-hand
84  * side relation's rows that are expected to have a match (ie, at least one
85  * row with a TRUE result) in the right-hand side.
86  *
87  * For both oprrest and oprjoin functions, the operator's input collation OID
88  * (if any) is passed using the standard fmgr mechanism, so that the estimator
89  * function can fetch it with PG_GET_COLLATION(). Note, however, that all
90  * statistics in pg_statistic are currently built using the database's default
91  * collation. Thus, in most cases where we are looking at statistics, we
92  * should ignore the actual operator collation and use DEFAULT_COLLATION_OID.
93  * We expect that the error induced by doing this is usually not large enough
94  * to justify complicating matters.
95  *----------
96  */
97 
98 #include "postgres.h"
99 
100 #include <ctype.h>
101 #include <float.h>
102 #include <math.h>
103 
104 #include "access/brin.h"
105 #include "access/gin.h"
106 #include "access/htup_details.h"
107 #include "access/sysattr.h"
108 #include "catalog/index.h"
109 #include "catalog/pg_am.h"
110 #include "catalog/pg_collation.h"
111 #include "catalog/pg_operator.h"
112 #include "catalog/pg_opfamily.h"
113 #include "catalog/pg_statistic.h"
115 #include "catalog/pg_type.h"
116 #include "executor/executor.h"
117 #include "mb/pg_wchar.h"
118 #include "miscadmin.h"
119 #include "nodes/makefuncs.h"
120 #include "nodes/nodeFuncs.h"
121 #include "optimizer/clauses.h"
122 #include "optimizer/cost.h"
123 #include "optimizer/pathnode.h"
124 #include "optimizer/paths.h"
125 #include "optimizer/plancat.h"
126 #include "optimizer/predtest.h"
127 #include "optimizer/restrictinfo.h"
128 #include "optimizer/var.h"
129 #include "parser/parse_clause.h"
130 #include "parser/parse_coerce.h"
131 #include "parser/parsetree.h"
132 #include "statistics/statistics.h"
133 #include "utils/acl.h"
134 #include "utils/builtins.h"
135 #include "utils/bytea.h"
136 #include "utils/date.h"
137 #include "utils/datum.h"
138 #include "utils/fmgroids.h"
139 #include "utils/index_selfuncs.h"
140 #include "utils/lsyscache.h"
141 #include "utils/nabstime.h"
142 #include "utils/pg_locale.h"
143 #include "utils/rel.h"
144 #include "utils/selfuncs.h"
145 #include "utils/snapmgr.h"
146 #include "utils/spccache.h"
147 #include "utils/syscache.h"
148 #include "utils/timestamp.h"
149 #include "utils/tqual.h"
150 #include "utils/typcache.h"
151 #include "utils/varlena.h"
152 
153 
154 /* Hooks for plugins to get control when we ask for stats */
157 
158 static double eqsel_internal(PG_FUNCTION_ARGS, bool negate);
159 static double var_eq_const(VariableStatData *vardata, Oid operator,
160  Datum constval, bool constisnull,
161  bool varonleft, bool negate);
162 static double var_eq_non_const(VariableStatData *vardata, Oid operator,
163  Node *other,
164  bool varonleft, bool negate);
165 static double ineq_histogram_selectivity(PlannerInfo *root,
166  VariableStatData *vardata,
167  FmgrInfo *opproc, bool isgt, bool iseq,
168  Datum constval, Oid consttype);
169 static double eqjoinsel_inner(Oid operator,
170  VariableStatData *vardata1, VariableStatData *vardata2);
171 static double eqjoinsel_semi(Oid operator,
172  VariableStatData *vardata1, VariableStatData *vardata2,
173  RelOptInfo *inner_rel);
175  RelOptInfo *rel, List **varinfos, double *ndistinct);
176 static bool convert_to_scalar(Datum value, Oid valuetypid, double *scaledvalue,
177  Datum lobound, Datum hibound, Oid boundstypid,
178  double *scaledlobound, double *scaledhibound);
179 static double convert_numeric_to_scalar(Datum value, Oid typid, bool *failure);
180 static void convert_string_to_scalar(char *value,
181  double *scaledvalue,
182  char *lobound,
183  double *scaledlobound,
184  char *hibound,
185  double *scaledhibound);
187  double *scaledvalue,
188  Datum lobound,
189  double *scaledlobound,
190  Datum hibound,
191  double *scaledhibound);
192 static double convert_one_string_to_scalar(char *value,
193  int rangelo, int rangehi);
194 static double convert_one_bytea_to_scalar(unsigned char *value, int valuelen,
195  int rangelo, int rangehi);
196 static char *convert_string_datum(Datum value, Oid typid, bool *failure);
197 static double convert_timevalue_to_scalar(Datum value, Oid typid,
198  bool *failure);
199 static void examine_simple_variable(PlannerInfo *root, Var *var,
200  VariableStatData *vardata);
201 static bool get_variable_range(PlannerInfo *root, VariableStatData *vardata,
202  Oid sortop, Datum *min, Datum *max);
203 static bool get_actual_variable_range(PlannerInfo *root,
204  VariableStatData *vardata,
205  Oid sortop,
206  Datum *min, Datum *max);
207 static RelOptInfo *find_join_input_rel(PlannerInfo *root, Relids relids);
209  VariableStatData *vardata,
210  Oid vartype, Oid opfamily, Const *prefixcon);
211 static Selectivity like_selectivity(const char *patt, int pattlen,
212  bool case_insensitive);
213 static Selectivity regex_selectivity(const char *patt, int pattlen,
214  bool case_insensitive,
215  int fixed_prefix_len);
216 static Datum string_to_datum(const char *str, Oid datatype);
217 static Const *string_to_const(const char *str, Oid datatype);
218 static Const *string_to_bytea_const(const char *str, size_t str_len);
219 static List *add_predicate_to_quals(IndexOptInfo *index, List *indexQuals);
220 
221 
222 /*
223  * eqsel - Selectivity of "=" for any data types.
224  *
225  * Note: this routine is also used to estimate selectivity for some
226  * operators that are not "=" but have comparable selectivity behavior,
227  * such as "~=" (geometric approximate-match). Even for "=", we must
228  * keep in mind that the left and right datatypes may differ.
229  */
230 Datum
232 {
233  PG_RETURN_FLOAT8((float8) eqsel_internal(fcinfo, false));
234 }
235 
236 /*
237  * Common code for eqsel() and neqsel()
238  */
239 static double
241 {
243  Oid operator = PG_GETARG_OID(1);
244  List *args = (List *) PG_GETARG_POINTER(2);
245  int varRelid = PG_GETARG_INT32(3);
246  VariableStatData vardata;
247  Node *other;
248  bool varonleft;
249  double selec;
250 
251  /*
252  * When asked about <>, we do the estimation using the corresponding =
253  * operator, then convert to <> via "1.0 - eq_selectivity - nullfrac".
254  */
255  if (negate)
256  {
257  operator = get_negator(operator);
258  if (!OidIsValid(operator))
259  {
260  /* Use default selectivity (should we raise an error instead?) */
261  return 1.0 - DEFAULT_EQ_SEL;
262  }
263  }
264 
265  /*
266  * If expression is not variable = something or something = variable, then
267  * punt and return a default estimate.
268  */
269  if (!get_restriction_variable(root, args, varRelid,
270  &vardata, &other, &varonleft))
271  return negate ? (1.0 - DEFAULT_EQ_SEL) : DEFAULT_EQ_SEL;
272 
273  /*
274  * We can do a lot better if the something is a constant. (Note: the
275  * Const might result from estimation rather than being a simple constant
276  * in the query.)
277  */
278  if (IsA(other, Const))
279  selec = var_eq_const(&vardata, operator,
280  ((Const *) other)->constvalue,
281  ((Const *) other)->constisnull,
282  varonleft, negate);
283  else
284  selec = var_eq_non_const(&vardata, operator, other,
285  varonleft, negate);
286 
287  ReleaseVariableStats(vardata);
288 
289  return selec;
290 }
291 
292 /*
293  * var_eq_const --- eqsel for var = const case
294  *
295  * This is split out so that some other estimation functions can use it.
296  */
297 static double
298 var_eq_const(VariableStatData *vardata, Oid operator,
299  Datum constval, bool constisnull,
300  bool varonleft, bool negate)
301 {
302  double selec;
303  double nullfrac = 0.0;
304  bool isdefault;
305  Oid opfuncoid;
306 
307  /*
308  * If the constant is NULL, assume operator is strict and return zero, ie,
309  * operator will never return TRUE. (It's zero even for a negator op.)
310  */
311  if (constisnull)
312  return 0.0;
313 
314  /*
315  * Grab the nullfrac for use below. Note we allow use of nullfrac
316  * regardless of security check.
317  */
318  if (HeapTupleIsValid(vardata->statsTuple))
319  {
320  Form_pg_statistic stats;
321 
322  stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
323  nullfrac = stats->stanullfrac;
324  }
325 
326  /*
327  * If we matched the var to a unique index or DISTINCT clause, assume
328  * there is exactly one match regardless of anything else. (This is
329  * slightly bogus, since the index or clause's equality operator might be
330  * different from ours, but it's much more likely to be right than
331  * ignoring the information.)
332  */
333  if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1.0)
334  {
335  selec = 1.0 / vardata->rel->tuples;
336  }
337  else if (HeapTupleIsValid(vardata->statsTuple) &&
339  (opfuncoid = get_opcode(operator))))
340  {
341  AttStatsSlot sslot;
342  bool match = false;
343  int i;
344 
345  /*
346  * Is the constant "=" to any of the column's most common values?
347  * (Although the given operator may not really be "=", we will assume
348  * that seeing whether it returns TRUE is an appropriate test. If you
349  * don't like this, maybe you shouldn't be using eqsel for your
350  * operator...)
351  */
352  if (get_attstatsslot(&sslot, vardata->statsTuple,
353  STATISTIC_KIND_MCV, InvalidOid,
355  {
356  FmgrInfo eqproc;
357 
358  fmgr_info(opfuncoid, &eqproc);
359 
360  for (i = 0; i < sslot.nvalues; i++)
361  {
362  /* be careful to apply operator right way 'round */
363  if (varonleft)
364  match = DatumGetBool(FunctionCall2Coll(&eqproc,
365  DEFAULT_COLLATION_OID,
366  sslot.values[i],
367  constval));
368  else
369  match = DatumGetBool(FunctionCall2Coll(&eqproc,
370  DEFAULT_COLLATION_OID,
371  constval,
372  sslot.values[i]));
373  if (match)
374  break;
375  }
376  }
377  else
378  {
379  /* no most-common-value info available */
380  i = 0; /* keep compiler quiet */
381  }
382 
383  if (match)
384  {
385  /*
386  * Constant is "=" to this common value. We know selectivity
387  * exactly (or as exactly as ANALYZE could calculate it, anyway).
388  */
389  selec = sslot.numbers[i];
390  }
391  else
392  {
393  /*
394  * Comparison is against a constant that is neither NULL nor any
395  * of the common values. Its selectivity cannot be more than
396  * this:
397  */
398  double sumcommon = 0.0;
399  double otherdistinct;
400 
401  for (i = 0; i < sslot.nnumbers; i++)
402  sumcommon += sslot.numbers[i];
403  selec = 1.0 - sumcommon - nullfrac;
404  CLAMP_PROBABILITY(selec);
405 
406  /*
407  * and in fact it's probably a good deal less. We approximate that
408  * all the not-common values share this remaining fraction
409  * equally, so we divide by the number of other distinct values.
410  */
411  otherdistinct = get_variable_numdistinct(vardata, &isdefault) -
412  sslot.nnumbers;
413  if (otherdistinct > 1)
414  selec /= otherdistinct;
415 
416  /*
417  * Another cross-check: selectivity shouldn't be estimated as more
418  * than the least common "most common value".
419  */
420  if (sslot.nnumbers > 0 && selec > sslot.numbers[sslot.nnumbers - 1])
421  selec = sslot.numbers[sslot.nnumbers - 1];
422  }
423 
424  free_attstatsslot(&sslot);
425  }
426  else
427  {
428  /*
429  * No ANALYZE stats available, so make a guess using estimated number
430  * of distinct values and assuming they are equally common. (The guess
431  * is unlikely to be very good, but we do know a few special cases.)
432  */
433  selec = 1.0 / get_variable_numdistinct(vardata, &isdefault);
434  }
435 
436  /* now adjust if we wanted <> rather than = */
437  if (negate)
438  selec = 1.0 - selec - nullfrac;
439 
440  /* result should be in range, but make sure... */
441  CLAMP_PROBABILITY(selec);
442 
443  return selec;
444 }
445 
446 /*
447  * var_eq_non_const --- eqsel for var = something-other-than-const case
448  */
449 static double
451  Node *other,
452  bool varonleft, bool negate)
453 {
454  double selec;
455  double nullfrac = 0.0;
456  bool isdefault;
457 
458  /*
459  * Grab the nullfrac for use below.
460  */
461  if (HeapTupleIsValid(vardata->statsTuple))
462  {
463  Form_pg_statistic stats;
464 
465  stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
466  nullfrac = stats->stanullfrac;
467  }
468 
469  /*
470  * If we matched the var to a unique index or DISTINCT clause, assume
471  * there is exactly one match regardless of anything else. (This is
472  * slightly bogus, since the index or clause's equality operator might be
473  * different from ours, but it's much more likely to be right than
474  * ignoring the information.)
475  */
476  if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1.0)
477  {
478  selec = 1.0 / vardata->rel->tuples;
479  }
480  else if (HeapTupleIsValid(vardata->statsTuple))
481  {
482  double ndistinct;
483  AttStatsSlot sslot;
484 
485  /*
486  * Search is for a value that we do not know a priori, but we will
487  * assume it is not NULL. Estimate the selectivity as non-null
488  * fraction divided by number of distinct values, so that we get a
489  * result averaged over all possible values whether common or
490  * uncommon. (Essentially, we are assuming that the not-yet-known
491  * comparison value is equally likely to be any of the possible
492  * values, regardless of their frequency in the table. Is that a good
493  * idea?)
494  */
495  selec = 1.0 - nullfrac;
496  ndistinct = get_variable_numdistinct(vardata, &isdefault);
497  if (ndistinct > 1)
498  selec /= ndistinct;
499 
500  /*
501  * Cross-check: selectivity should never be estimated as more than the
502  * most common value's.
503  */
504  if (get_attstatsslot(&sslot, vardata->statsTuple,
505  STATISTIC_KIND_MCV, InvalidOid,
507  {
508  if (sslot.nnumbers > 0 && selec > sslot.numbers[0])
509  selec = sslot.numbers[0];
510  free_attstatsslot(&sslot);
511  }
512  }
513  else
514  {
515  /*
516  * No ANALYZE stats available, so make a guess using estimated number
517  * of distinct values and assuming they are equally common. (The guess
518  * is unlikely to be very good, but we do know a few special cases.)
519  */
520  selec = 1.0 / get_variable_numdistinct(vardata, &isdefault);
521  }
522 
523  /* now adjust if we wanted <> rather than = */
524  if (negate)
525  selec = 1.0 - selec - nullfrac;
526 
527  /* result should be in range, but make sure... */
528  CLAMP_PROBABILITY(selec);
529 
530  return selec;
531 }
532 
533 /*
534  * neqsel - Selectivity of "!=" for any data types.
535  *
536  * This routine is also used for some operators that are not "!="
537  * but have comparable selectivity behavior. See above comments
538  * for eqsel().
539  */
540 Datum
542 {
543  PG_RETURN_FLOAT8((float8) eqsel_internal(fcinfo, true));
544 }
545 
546 /*
547  * scalarineqsel - Selectivity of "<", "<=", ">", ">=" for scalars.
548  *
549  * This is the guts of scalarltsel/scalarlesel/scalargtsel/scalargesel.
550  * The isgt and iseq flags distinguish which of the four cases apply.
551  *
552  * The caller has commuted the clause, if necessary, so that we can treat
553  * the variable as being on the left. The caller must also make sure that
554  * the other side of the clause is a non-null Const, and dissect that into
555  * a value and datatype. (This definition simplifies some callers that
556  * want to estimate against a computed value instead of a Const node.)
557  *
558  * This routine works for any datatype (or pair of datatypes) known to
559  * convert_to_scalar(). If it is applied to some other datatype,
560  * it will return an approximate estimate based on assuming that the constant
561  * value falls in the middle of the bin identified by binary search.
562  */
563 static double
564 scalarineqsel(PlannerInfo *root, Oid operator, bool isgt, bool iseq,
565  VariableStatData *vardata, Datum constval, Oid consttype)
566 {
567  Form_pg_statistic stats;
568  FmgrInfo opproc;
569  double mcv_selec,
570  hist_selec,
571  sumcommon;
572  double selec;
573 
574  if (!HeapTupleIsValid(vardata->statsTuple))
575  {
576  /* no stats available, so default result */
577  return DEFAULT_INEQ_SEL;
578  }
579  stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
580 
581  fmgr_info(get_opcode(operator), &opproc);
582 
583  /*
584  * If we have most-common-values info, add up the fractions of the MCV
585  * entries that satisfy MCV OP CONST. These fractions contribute directly
586  * to the result selectivity. Also add up the total fraction represented
587  * by MCV entries.
588  */
589  mcv_selec = mcv_selectivity(vardata, &opproc, constval, true,
590  &sumcommon);
591 
592  /*
593  * If there is a histogram, determine which bin the constant falls in, and
594  * compute the resulting contribution to selectivity.
595  */
596  hist_selec = ineq_histogram_selectivity(root, vardata,
597  &opproc, isgt, iseq,
598  constval, consttype);
599 
600  /*
601  * Now merge the results from the MCV and histogram calculations,
602  * realizing that the histogram covers only the non-null values that are
603  * not listed in MCV.
604  */
605  selec = 1.0 - stats->stanullfrac - sumcommon;
606 
607  if (hist_selec >= 0.0)
608  selec *= hist_selec;
609  else
610  {
611  /*
612  * If no histogram but there are values not accounted for by MCV,
613  * arbitrarily assume half of them will match.
614  */
615  selec *= 0.5;
616  }
617 
618  selec += mcv_selec;
619 
620  /* result should be in range, but make sure... */
621  CLAMP_PROBABILITY(selec);
622 
623  return selec;
624 }
625 
626 /*
627  * mcv_selectivity - Examine the MCV list for selectivity estimates
628  *
629  * Determine the fraction of the variable's MCV population that satisfies
630  * the predicate (VAR OP CONST), or (CONST OP VAR) if !varonleft. Also
631  * compute the fraction of the total column population represented by the MCV
632  * list. This code will work for any boolean-returning predicate operator.
633  *
634  * The function result is the MCV selectivity, and the fraction of the
635  * total population is returned into *sumcommonp. Zeroes are returned
636  * if there is no MCV list.
637  */
638 double
640  Datum constval, bool varonleft,
641  double *sumcommonp)
642 {
643  double mcv_selec,
644  sumcommon;
645  AttStatsSlot sslot;
646  int i;
647 
648  mcv_selec = 0.0;
649  sumcommon = 0.0;
650 
651  if (HeapTupleIsValid(vardata->statsTuple) &&
652  statistic_proc_security_check(vardata, opproc->fn_oid) &&
653  get_attstatsslot(&sslot, vardata->statsTuple,
654  STATISTIC_KIND_MCV, InvalidOid,
656  {
657  for (i = 0; i < sslot.nvalues; i++)
658  {
659  if (varonleft ?
661  DEFAULT_COLLATION_OID,
662  sslot.values[i],
663  constval)) :
665  DEFAULT_COLLATION_OID,
666  constval,
667  sslot.values[i])))
668  mcv_selec += sslot.numbers[i];
669  sumcommon += sslot.numbers[i];
670  }
671  free_attstatsslot(&sslot);
672  }
673 
674  *sumcommonp = sumcommon;
675  return mcv_selec;
676 }
677 
678 /*
679  * histogram_selectivity - Examine the histogram for selectivity estimates
680  *
681  * Determine the fraction of the variable's histogram entries that satisfy
682  * the predicate (VAR OP CONST), or (CONST OP VAR) if !varonleft.
683  *
684  * This code will work for any boolean-returning predicate operator, whether
685  * or not it has anything to do with the histogram sort operator. We are
686  * essentially using the histogram just as a representative sample. However,
687  * small histograms are unlikely to be all that representative, so the caller
688  * should be prepared to fall back on some other estimation approach when the
689  * histogram is missing or very small. It may also be prudent to combine this
690  * approach with another one when the histogram is small.
691  *
692  * If the actual histogram size is not at least min_hist_size, we won't bother
693  * to do the calculation at all. Also, if the n_skip parameter is > 0, we
694  * ignore the first and last n_skip histogram elements, on the grounds that
695  * they are outliers and hence not very representative. Typical values for
696  * these parameters are 10 and 1.
697  *
698  * The function result is the selectivity, or -1 if there is no histogram
699  * or it's smaller than min_hist_size.
700  *
701  * The output parameter *hist_size receives the actual histogram size,
702  * or zero if no histogram. Callers may use this number to decide how
703  * much faith to put in the function result.
704  *
705  * Note that the result disregards both the most-common-values (if any) and
706  * null entries. The caller is expected to combine this result with
707  * statistics for those portions of the column population. It may also be
708  * prudent to clamp the result range, ie, disbelieve exact 0 or 1 outputs.
709  */
710 double
712  Datum constval, bool varonleft,
713  int min_hist_size, int n_skip,
714  int *hist_size)
715 {
716  double result;
717  AttStatsSlot sslot;
718 
719  /* check sanity of parameters */
720  Assert(n_skip >= 0);
721  Assert(min_hist_size > 2 * n_skip);
722 
723  if (HeapTupleIsValid(vardata->statsTuple) &&
724  statistic_proc_security_check(vardata, opproc->fn_oid) &&
725  get_attstatsslot(&sslot, vardata->statsTuple,
726  STATISTIC_KIND_HISTOGRAM, InvalidOid,
728  {
729  *hist_size = sslot.nvalues;
730  if (sslot.nvalues >= min_hist_size)
731  {
732  int nmatch = 0;
733  int i;
734 
735  for (i = n_skip; i < sslot.nvalues - n_skip; i++)
736  {
737  if (varonleft ?
739  DEFAULT_COLLATION_OID,
740  sslot.values[i],
741  constval)) :
743  DEFAULT_COLLATION_OID,
744  constval,
745  sslot.values[i])))
746  nmatch++;
747  }
748  result = ((double) nmatch) / ((double) (sslot.nvalues - 2 * n_skip));
749  }
750  else
751  result = -1;
752  free_attstatsslot(&sslot);
753  }
754  else
755  {
756  *hist_size = 0;
757  result = -1;
758  }
759 
760  return result;
761 }
762 
763 /*
764  * ineq_histogram_selectivity - Examine the histogram for scalarineqsel
765  *
766  * Determine the fraction of the variable's histogram population that
767  * satisfies the inequality condition, ie, VAR < (or <=, >, >=) CONST.
768  * The isgt and iseq flags distinguish which of the four cases apply.
769  *
770  * Returns -1 if there is no histogram (valid results will always be >= 0).
771  *
772  * Note that the result disregards both the most-common-values (if any) and
773  * null entries. The caller is expected to combine this result with
774  * statistics for those portions of the column population.
775  */
776 static double
778  VariableStatData *vardata,
779  FmgrInfo *opproc, bool isgt, bool iseq,
780  Datum constval, Oid consttype)
781 {
782  double hist_selec;
783  AttStatsSlot sslot;
784 
785  hist_selec = -1.0;
786 
787  /*
788  * Someday, ANALYZE might store more than one histogram per rel/att,
789  * corresponding to more than one possible sort ordering defined for the
790  * column type. However, to make that work we will need to figure out
791  * which staop to search for --- it's not necessarily the one we have at
792  * hand! (For example, we might have a '<=' operator rather than the '<'
793  * operator that will appear in staop.) For now, assume that whatever
794  * appears in pg_statistic is sorted the same way our operator sorts, or
795  * the reverse way if isgt is true.
796  */
797  if (HeapTupleIsValid(vardata->statsTuple) &&
798  statistic_proc_security_check(vardata, opproc->fn_oid) &&
799  get_attstatsslot(&sslot, vardata->statsTuple,
800  STATISTIC_KIND_HISTOGRAM, InvalidOid,
802  {
803  if (sslot.nvalues > 1)
804  {
805  /*
806  * Use binary search to find the desired location, namely the
807  * right end of the histogram bin containing the comparison value,
808  * which is the leftmost entry for which the comparison operator
809  * succeeds (if isgt) or fails (if !isgt). (If the given operator
810  * isn't actually sort-compatible with the histogram, you'll get
811  * garbage results ... but probably not any more garbage-y than
812  * you would have from the old linear search.)
813  *
814  * In this loop, we pay no attention to whether the operator iseq
815  * or not; that detail will be mopped up below. (We cannot tell,
816  * anyway, whether the operator thinks the values are equal.)
817  *
818  * If the binary search accesses the first or last histogram
819  * entry, we try to replace that endpoint with the true column min
820  * or max as found by get_actual_variable_range(). This
821  * ameliorates misestimates when the min or max is moving as a
822  * result of changes since the last ANALYZE. Note that this could
823  * result in effectively including MCVs into the histogram that
824  * weren't there before, but we don't try to correct for that.
825  */
826  double histfrac;
827  int lobound = 0; /* first possible slot to search */
828  int hibound = sslot.nvalues; /* last+1 slot to search */
829  bool have_end = false;
830 
831  /*
832  * If there are only two histogram entries, we'll want up-to-date
833  * values for both. (If there are more than two, we need at most
834  * one of them to be updated, so we deal with that within the
835  * loop.)
836  */
837  if (sslot.nvalues == 2)
838  have_end = get_actual_variable_range(root,
839  vardata,
840  sslot.staop,
841  &sslot.values[0],
842  &sslot.values[1]);
843 
844  while (lobound < hibound)
845  {
846  int probe = (lobound + hibound) / 2;
847  bool ltcmp;
848 
849  /*
850  * If we find ourselves about to compare to the first or last
851  * histogram entry, first try to replace it with the actual
852  * current min or max (unless we already did so above).
853  */
854  if (probe == 0 && sslot.nvalues > 2)
855  have_end = get_actual_variable_range(root,
856  vardata,
857  sslot.staop,
858  &sslot.values[0],
859  NULL);
860  else if (probe == sslot.nvalues - 1 && sslot.nvalues > 2)
861  have_end = get_actual_variable_range(root,
862  vardata,
863  sslot.staop,
864  NULL,
865  &sslot.values[probe]);
866 
867  ltcmp = DatumGetBool(FunctionCall2Coll(opproc,
868  DEFAULT_COLLATION_OID,
869  sslot.values[probe],
870  constval));
871  if (isgt)
872  ltcmp = !ltcmp;
873  if (ltcmp)
874  lobound = probe + 1;
875  else
876  hibound = probe;
877  }
878 
879  if (lobound <= 0)
880  {
881  /*
882  * Constant is below lower histogram boundary. More
883  * precisely, we have found that no entry in the histogram
884  * satisfies the inequality clause (if !isgt) or they all do
885  * (if isgt). We estimate that that's true of the entire
886  * table, so set histfrac to 0.0 (which we'll flip to 1.0
887  * below, if isgt).
888  */
889  histfrac = 0.0;
890  }
891  else if (lobound >= sslot.nvalues)
892  {
893  /*
894  * Inverse case: constant is above upper histogram boundary.
895  */
896  histfrac = 1.0;
897  }
898  else
899  {
900  /* We have values[i-1] <= constant <= values[i]. */
901  int i = lobound;
902  double eq_selec = 0;
903  double val,
904  high,
905  low;
906  double binfrac;
907 
908  /*
909  * In the cases where we'll need it below, obtain an estimate
910  * of the selectivity of "x = constval". We use a calculation
911  * similar to what var_eq_const() does for a non-MCV constant,
912  * ie, estimate that all distinct non-MCV values occur equally
913  * often. But multiplication by "1.0 - sumcommon - nullfrac"
914  * will be done by our caller, so we shouldn't do that here.
915  * Therefore we can't try to clamp the estimate by reference
916  * to the least common MCV; the result would be too small.
917  *
918  * Note: since this is effectively assuming that constval
919  * isn't an MCV, it's logically dubious if constval in fact is
920  * one. But we have to apply *some* correction for equality,
921  * and anyway we cannot tell if constval is an MCV, since we
922  * don't have a suitable equality operator at hand.
923  */
924  if (i == 1 || isgt == iseq)
925  {
926  double otherdistinct;
927  bool isdefault;
928  AttStatsSlot mcvslot;
929 
930  /* Get estimated number of distinct values */
931  otherdistinct = get_variable_numdistinct(vardata,
932  &isdefault);
933 
934  /* Subtract off the number of known MCVs */
935  if (get_attstatsslot(&mcvslot, vardata->statsTuple,
936  STATISTIC_KIND_MCV, InvalidOid,
938  {
939  otherdistinct -= mcvslot.nnumbers;
940  free_attstatsslot(&mcvslot);
941  }
942 
943  /* If result doesn't seem sane, leave eq_selec at 0 */
944  if (otherdistinct > 1)
945  eq_selec = 1.0 / otherdistinct;
946  }
947 
948  /*
949  * Convert the constant and the two nearest bin boundary
950  * values to a uniform comparison scale, and do a linear
951  * interpolation within this bin.
952  */
953  if (convert_to_scalar(constval, consttype, &val,
954  sslot.values[i - 1], sslot.values[i],
955  vardata->vartype,
956  &low, &high))
957  {
958  if (high <= low)
959  {
960  /* cope if bin boundaries appear identical */
961  binfrac = 0.5;
962  }
963  else if (val <= low)
964  binfrac = 0.0;
965  else if (val >= high)
966  binfrac = 1.0;
967  else
968  {
969  binfrac = (val - low) / (high - low);
970 
971  /*
972  * Watch out for the possibility that we got a NaN or
973  * Infinity from the division. This can happen
974  * despite the previous checks, if for example "low"
975  * is -Infinity.
976  */
977  if (isnan(binfrac) ||
978  binfrac < 0.0 || binfrac > 1.0)
979  binfrac = 0.5;
980  }
981  }
982  else
983  {
984  /*
985  * Ideally we'd produce an error here, on the grounds that
986  * the given operator shouldn't have scalarXXsel
987  * registered as its selectivity func unless we can deal
988  * with its operand types. But currently, all manner of
989  * stuff is invoking scalarXXsel, so give a default
990  * estimate until that can be fixed.
991  */
992  binfrac = 0.5;
993  }
994 
995  /*
996  * Now, compute the overall selectivity across the values
997  * represented by the histogram. We have i-1 full bins and
998  * binfrac partial bin below the constant.
999  */
1000  histfrac = (double) (i - 1) + binfrac;
1001  histfrac /= (double) (sslot.nvalues - 1);
1002 
1003  /*
1004  * At this point, histfrac is an estimate of the fraction of
1005  * the population represented by the histogram that satisfies
1006  * "x <= constval". Somewhat remarkably, this statement is
1007  * true regardless of which operator we were doing the probes
1008  * with, so long as convert_to_scalar() delivers reasonable
1009  * results. If the probe constant is equal to some histogram
1010  * entry, we would have considered the bin to the left of that
1011  * entry if probing with "<" or ">=", or the bin to the right
1012  * if probing with "<=" or ">"; but binfrac would have come
1013  * out as 1.0 in the first case and 0.0 in the second, leading
1014  * to the same histfrac in either case. For probe constants
1015  * between histogram entries, we find the same bin and get the
1016  * same estimate with any operator.
1017  *
1018  * The fact that the estimate corresponds to "x <= constval"
1019  * and not "x < constval" is because of the way that ANALYZE
1020  * constructs the histogram: each entry is, effectively, the
1021  * rightmost value in its sample bucket. So selectivity
1022  * values that are exact multiples of 1/(histogram_size-1)
1023  * should be understood as estimates including a histogram
1024  * entry plus everything to its left.
1025  *
1026  * However, that breaks down for the first histogram entry,
1027  * which necessarily is the leftmost value in its sample
1028  * bucket. That means the first histogram bin is slightly
1029  * narrower than the rest, by an amount equal to eq_selec.
1030  * Another way to say that is that we want "x <= leftmost" to
1031  * be estimated as eq_selec not zero. So, if we're dealing
1032  * with the first bin (i==1), rescale to make that true while
1033  * adjusting the rest of that bin linearly.
1034  */
1035  if (i == 1)
1036  histfrac += eq_selec * (1.0 - binfrac);
1037 
1038  /*
1039  * "x <= constval" is good if we want an estimate for "<=" or
1040  * ">", but if we are estimating for "<" or ">=", we now need
1041  * to decrease the estimate by eq_selec.
1042  */
1043  if (isgt == iseq)
1044  histfrac -= eq_selec;
1045  }
1046 
1047  /*
1048  * Now the estimate is finished for "<" and "<=" cases. If we are
1049  * estimating for ">" or ">=", flip it.
1050  */
1051  hist_selec = isgt ? (1.0 - histfrac) : histfrac;
1052 
1053  /*
1054  * The histogram boundaries are only approximate to begin with,
1055  * and may well be out of date anyway. Therefore, don't believe
1056  * extremely small or large selectivity estimates --- unless we
1057  * got actual current endpoint values from the table, in which
1058  * case just do the usual sanity clamp. Somewhat arbitrarily, we
1059  * set the cutoff for other cases at a hundredth of the histogram
1060  * resolution.
1061  */
1062  if (have_end)
1063  CLAMP_PROBABILITY(hist_selec);
1064  else
1065  {
1066  double cutoff = 0.01 / (double) (sslot.nvalues - 1);
1067 
1068  if (hist_selec < cutoff)
1069  hist_selec = cutoff;
1070  else if (hist_selec > 1.0 - cutoff)
1071  hist_selec = 1.0 - cutoff;
1072  }
1073  }
1074 
1075  free_attstatsslot(&sslot);
1076  }
1077 
1078  return hist_selec;
1079 }
1080 
1081 /*
1082  * Common wrapper function for the selectivity estimators that simply
1083  * invoke scalarineqsel().
1084  */
1085 static Datum
1087 {
1088  PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
1089  Oid operator = PG_GETARG_OID(1);
1090  List *args = (List *) PG_GETARG_POINTER(2);
1091  int varRelid = PG_GETARG_INT32(3);
1092  VariableStatData vardata;
1093  Node *other;
1094  bool varonleft;
1095  Datum constval;
1096  Oid consttype;
1097  double selec;
1098 
1099  /*
1100  * If expression is not variable op something or something op variable,
1101  * then punt and return a default estimate.
1102  */
1103  if (!get_restriction_variable(root, args, varRelid,
1104  &vardata, &other, &varonleft))
1106 
1107  /*
1108  * Can't do anything useful if the something is not a constant, either.
1109  */
1110  if (!IsA(other, Const))
1111  {
1112  ReleaseVariableStats(vardata);
1114  }
1115 
1116  /*
1117  * If the constant is NULL, assume operator is strict and return zero, ie,
1118  * operator will never return TRUE.
1119  */
1120  if (((Const *) other)->constisnull)
1121  {
1122  ReleaseVariableStats(vardata);
1123  PG_RETURN_FLOAT8(0.0);
1124  }
1125  constval = ((Const *) other)->constvalue;
1126  consttype = ((Const *) other)->consttype;
1127 
1128  /*
1129  * Force the var to be on the left to simplify logic in scalarineqsel.
1130  */
1131  if (!varonleft)
1132  {
1133  operator = get_commutator(operator);
1134  if (!operator)
1135  {
1136  /* Use default selectivity (should we raise an error instead?) */
1137  ReleaseVariableStats(vardata);
1139  }
1140  isgt = !isgt;
1141  }
1142 
1143  /* The rest of the work is done by scalarineqsel(). */
1144  selec = scalarineqsel(root, operator, isgt, iseq,
1145  &vardata, constval, consttype);
1146 
1147  ReleaseVariableStats(vardata);
1148 
1149  PG_RETURN_FLOAT8((float8) selec);
1150 }
1151 
1152 /*
1153  * scalarltsel - Selectivity of "<" for scalars.
1154  */
1155 Datum
1157 {
1158  return scalarineqsel_wrapper(fcinfo, false, false);
1159 }
1160 
1161 /*
1162  * scalarlesel - Selectivity of "<=" for scalars.
1163  */
1164 Datum
1166 {
1167  return scalarineqsel_wrapper(fcinfo, false, true);
1168 }
1169 
1170 /*
1171  * scalargtsel - Selectivity of ">" for scalars.
1172  */
1173 Datum
1175 {
1176  return scalarineqsel_wrapper(fcinfo, true, false);
1177 }
1178 
1179 /*
1180  * scalargesel - Selectivity of ">=" for scalars.
1181  */
1182 Datum
1184 {
1185  return scalarineqsel_wrapper(fcinfo, true, true);
1186 }
1187 
1188 /*
1189  * patternsel - Generic code for pattern-match selectivity.
1190  */
1191 static double
1193 {
1194  PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
1195  Oid operator = PG_GETARG_OID(1);
1196  List *args = (List *) PG_GETARG_POINTER(2);
1197  int varRelid = PG_GETARG_INT32(3);
1198  Oid collation = PG_GET_COLLATION();
1199  VariableStatData vardata;
1200  Node *other;
1201  bool varonleft;
1202  Datum constval;
1203  Oid consttype;
1204  Oid vartype;
1205  Oid opfamily;
1206  Pattern_Prefix_Status pstatus;
1207  Const *patt;
1208  Const *prefix = NULL;
1209  Selectivity rest_selec = 0;
1210  double nullfrac = 0.0;
1211  double result;
1212 
1213  /*
1214  * If this is for a NOT LIKE or similar operator, get the corresponding
1215  * positive-match operator and work with that. Set result to the correct
1216  * default estimate, too.
1217  */
1218  if (negate)
1219  {
1220  operator = get_negator(operator);
1221  if (!OidIsValid(operator))
1222  elog(ERROR, "patternsel called for operator without a negator");
1223  result = 1.0 - DEFAULT_MATCH_SEL;
1224  }
1225  else
1226  {
1227  result = DEFAULT_MATCH_SEL;
1228  }
1229 
1230  /*
1231  * If expression is not variable op constant, then punt and return a
1232  * default estimate.
1233  */
1234  if (!get_restriction_variable(root, args, varRelid,
1235  &vardata, &other, &varonleft))
1236  return result;
1237  if (!varonleft || !IsA(other, Const))
1238  {
1239  ReleaseVariableStats(vardata);
1240  return result;
1241  }
1242 
1243  /*
1244  * If the constant is NULL, assume operator is strict and return zero, ie,
1245  * operator will never return TRUE. (It's zero even for a negator op.)
1246  */
1247  if (((Const *) other)->constisnull)
1248  {
1249  ReleaseVariableStats(vardata);
1250  return 0.0;
1251  }
1252  constval = ((Const *) other)->constvalue;
1253  consttype = ((Const *) other)->consttype;
1254 
1255  /*
1256  * The right-hand const is type text or bytea for all supported operators.
1257  * We do not expect to see binary-compatible types here, since
1258  * const-folding should have relabeled the const to exactly match the
1259  * operator's declared type.
1260  */
1261  if (consttype != TEXTOID && consttype != BYTEAOID)
1262  {
1263  ReleaseVariableStats(vardata);
1264  return result;
1265  }
1266 
1267  /*
1268  * Similarly, the exposed type of the left-hand side should be one of
1269  * those we know. (Do not look at vardata.atttype, which might be
1270  * something binary-compatible but different.) We can use it to choose
1271  * the index opfamily from which we must draw the comparison operators.
1272  *
1273  * NOTE: It would be more correct to use the PATTERN opfamilies than the
1274  * simple ones, but at the moment ANALYZE will not generate statistics for
1275  * the PATTERN operators. But our results are so approximate anyway that
1276  * it probably hardly matters.
1277  */
1278  vartype = vardata.vartype;
1279 
1280  switch (vartype)
1281  {
1282  case TEXTOID:
1283  opfamily = TEXT_BTREE_FAM_OID;
1284  break;
1285  case BPCHAROID:
1286  opfamily = BPCHAR_BTREE_FAM_OID;
1287  break;
1288  case NAMEOID:
1289  opfamily = NAME_BTREE_FAM_OID;
1290  break;
1291  case BYTEAOID:
1292  opfamily = BYTEA_BTREE_FAM_OID;
1293  break;
1294  default:
1295  ReleaseVariableStats(vardata);
1296  return result;
1297  }
1298 
1299  /*
1300  * Grab the nullfrac for use below.
1301  */
1302  if (HeapTupleIsValid(vardata.statsTuple))
1303  {
1304  Form_pg_statistic stats;
1305 
1306  stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
1307  nullfrac = stats->stanullfrac;
1308  }
1309 
1310  /*
1311  * Pull out any fixed prefix implied by the pattern, and estimate the
1312  * fractional selectivity of the remainder of the pattern. Unlike many of
1313  * the other functions in this file, we use the pattern operator's actual
1314  * collation for this step. This is not because we expect the collation
1315  * to make a big difference in the selectivity estimate (it seldom would),
1316  * but because we want to be sure we cache compiled regexps under the
1317  * right cache key, so that they can be re-used at runtime.
1318  */
1319  patt = (Const *) other;
1320  pstatus = pattern_fixed_prefix(patt, ptype, collation,
1321  &prefix, &rest_selec);
1322 
1323  /*
1324  * If necessary, coerce the prefix constant to the right type.
1325  */
1326  if (prefix && prefix->consttype != vartype)
1327  {
1328  char *prefixstr;
1329 
1330  switch (prefix->consttype)
1331  {
1332  case TEXTOID:
1333  prefixstr = TextDatumGetCString(prefix->constvalue);
1334  break;
1335  case BYTEAOID:
1337  prefix->constvalue));
1338  break;
1339  default:
1340  elog(ERROR, "unrecognized consttype: %u",
1341  prefix->consttype);
1342  ReleaseVariableStats(vardata);
1343  return result;
1344  }
1345  prefix = string_to_const(prefixstr, vartype);
1346  pfree(prefixstr);
1347  }
1348 
1349  if (pstatus == Pattern_Prefix_Exact)
1350  {
1351  /*
1352  * Pattern specifies an exact match, so pretend operator is '='
1353  */
1354  Oid eqopr = get_opfamily_member(opfamily, vartype, vartype,
1356 
1357  if (eqopr == InvalidOid)
1358  elog(ERROR, "no = operator for opfamily %u", opfamily);
1359  result = var_eq_const(&vardata, eqopr, prefix->constvalue,
1360  false, true, false);
1361  }
1362  else
1363  {
1364  /*
1365  * Not exact-match pattern. If we have a sufficiently large
1366  * histogram, estimate selectivity for the histogram part of the
1367  * population by counting matches in the histogram. If not, estimate
1368  * selectivity of the fixed prefix and remainder of pattern
1369  * separately, then combine the two to get an estimate of the
1370  * selectivity for the part of the column population represented by
1371  * the histogram. (For small histograms, we combine these
1372  * approaches.)
1373  *
1374  * We then add up data for any most-common-values values; these are
1375  * not in the histogram population, and we can get exact answers for
1376  * them by applying the pattern operator, so there's no reason to
1377  * approximate. (If the MCVs cover a significant part of the total
1378  * population, this gives us a big leg up in accuracy.)
1379  */
1380  Selectivity selec;
1381  int hist_size;
1382  FmgrInfo opproc;
1383  double mcv_selec,
1384  sumcommon;
1385 
1386  /* Try to use the histogram entries to get selectivity */
1387  fmgr_info(get_opcode(operator), &opproc);
1388 
1389  selec = histogram_selectivity(&vardata, &opproc, constval, true,
1390  10, 1, &hist_size);
1391 
1392  /* If not at least 100 entries, use the heuristic method */
1393  if (hist_size < 100)
1394  {
1395  Selectivity heursel;
1397 
1398  if (pstatus == Pattern_Prefix_Partial)
1399  prefixsel = prefix_selectivity(root, &vardata, vartype,
1400  opfamily, prefix);
1401  else
1402  prefixsel = 1.0;
1403  heursel = prefixsel * rest_selec;
1404 
1405  if (selec < 0) /* fewer than 10 histogram entries? */
1406  selec = heursel;
1407  else
1408  {
1409  /*
1410  * For histogram sizes from 10 to 100, we combine the
1411  * histogram and heuristic selectivities, putting increasingly
1412  * more trust in the histogram for larger sizes.
1413  */
1414  double hist_weight = hist_size / 100.0;
1415 
1416  selec = selec * hist_weight + heursel * (1.0 - hist_weight);
1417  }
1418  }
1419 
1420  /* In any case, don't believe extremely small or large estimates. */
1421  if (selec < 0.0001)
1422  selec = 0.0001;
1423  else if (selec > 0.9999)
1424  selec = 0.9999;
1425 
1426  /*
1427  * If we have most-common-values info, add up the fractions of the MCV
1428  * entries that satisfy MCV OP PATTERN. These fractions contribute
1429  * directly to the result selectivity. Also add up the total fraction
1430  * represented by MCV entries.
1431  */
1432  mcv_selec = mcv_selectivity(&vardata, &opproc, constval, true,
1433  &sumcommon);
1434 
1435  /*
1436  * Now merge the results from the MCV and histogram calculations,
1437  * realizing that the histogram covers only the non-null values that
1438  * are not listed in MCV.
1439  */
1440  selec *= 1.0 - nullfrac - sumcommon;
1441  selec += mcv_selec;
1442  result = selec;
1443  }
1444 
1445  /* now adjust if we wanted not-match rather than match */
1446  if (negate)
1447  result = 1.0 - result - nullfrac;
1448 
1449  /* result should be in range, but make sure... */
1450  CLAMP_PROBABILITY(result);
1451 
1452  if (prefix)
1453  {
1454  pfree(DatumGetPointer(prefix->constvalue));
1455  pfree(prefix);
1456  }
1457 
1458  ReleaseVariableStats(vardata);
1459 
1460  return result;
1461 }
1462 
1463 /*
1464  * regexeqsel - Selectivity of regular-expression pattern match.
1465  */
1466 Datum
1468 {
1470 }
1471 
1472 /*
1473  * icregexeqsel - Selectivity of case-insensitive regex match.
1474  */
1475 Datum
1477 {
1479 }
1480 
1481 /*
1482  * likesel - Selectivity of LIKE pattern match.
1483  */
1484 Datum
1486 {
1488 }
1489 
1490 /*
1491  * prefixsel - selectivity of prefix operator
1492  */
1493 Datum
1495 {
1497 }
1498 
1499 /*
1500  *
1501  * iclikesel - Selectivity of ILIKE pattern match.
1502  */
1503 Datum
1505 {
1507 }
1508 
1509 /*
1510  * regexnesel - Selectivity of regular-expression pattern non-match.
1511  */
1512 Datum
1514 {
1516 }
1517 
1518 /*
1519  * icregexnesel - Selectivity of case-insensitive regex non-match.
1520  */
1521 Datum
1523 {
1525 }
1526 
1527 /*
1528  * nlikesel - Selectivity of LIKE pattern non-match.
1529  */
1530 Datum
1532 {
1534 }
1535 
1536 /*
1537  * icnlikesel - Selectivity of ILIKE pattern non-match.
1538  */
1539 Datum
1541 {
1543 }
1544 
1545 /*
1546  * boolvarsel - Selectivity of Boolean variable.
1547  *
1548  * This can actually be called on any boolean-valued expression. If it
1549  * involves only Vars of the specified relation, and if there are statistics
1550  * about the Var or expression (the latter is possible if it's indexed) then
1551  * we'll produce a real estimate; otherwise it's just a default.
1552  */
1554 boolvarsel(PlannerInfo *root, Node *arg, int varRelid)
1555 {
1556  VariableStatData vardata;
1557  double selec;
1558 
1559  examine_variable(root, arg, varRelid, &vardata);
1560  if (HeapTupleIsValid(vardata.statsTuple))
1561  {
1562  /*
1563  * A boolean variable V is equivalent to the clause V = 't', so we
1564  * compute the selectivity as if that is what we have.
1565  */
1566  selec = var_eq_const(&vardata, BooleanEqualOperator,
1567  BoolGetDatum(true), false, true, false);
1568  }
1569  else if (is_funcclause(arg))
1570  {
1571  /*
1572  * If we have no stats and it's a function call, estimate 0.3333333.
1573  * This seems a pretty unprincipled choice, but Postgres has been
1574  * using that estimate for function calls since 1992. The hoariness
1575  * of this behavior suggests that we should not be in too much hurry
1576  * to use another value.
1577  */
1578  selec = 0.3333333;
1579  }
1580  else
1581  {
1582  /* Otherwise, the default estimate is 0.5 */
1583  selec = 0.5;
1584  }
1585  ReleaseVariableStats(vardata);
1586  return selec;
1587 }
1588 
1589 /*
1590  * booltestsel - Selectivity of BooleanTest Node.
1591  */
1594  int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
1595 {
1596  VariableStatData vardata;
1597  double selec;
1598 
1599  examine_variable(root, arg, varRelid, &vardata);
1600 
1601  if (HeapTupleIsValid(vardata.statsTuple))
1602  {
1603  Form_pg_statistic stats;
1604  double freq_null;
1605  AttStatsSlot sslot;
1606 
1607  stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
1608  freq_null = stats->stanullfrac;
1609 
1610  if (get_attstatsslot(&sslot, vardata.statsTuple,
1611  STATISTIC_KIND_MCV, InvalidOid,
1613  && sslot.nnumbers > 0)
1614  {
1615  double freq_true;
1616  double freq_false;
1617 
1618  /*
1619  * Get first MCV frequency and derive frequency for true.
1620  */
1621  if (DatumGetBool(sslot.values[0]))
1622  freq_true = sslot.numbers[0];
1623  else
1624  freq_true = 1.0 - sslot.numbers[0] - freq_null;
1625 
1626  /*
1627  * Next derive frequency for false. Then use these as appropriate
1628  * to derive frequency for each case.
1629  */
1630  freq_false = 1.0 - freq_true - freq_null;
1631 
1632  switch (booltesttype)
1633  {
1634  case IS_UNKNOWN:
1635  /* select only NULL values */
1636  selec = freq_null;
1637  break;
1638  case IS_NOT_UNKNOWN:
1639  /* select non-NULL values */
1640  selec = 1.0 - freq_null;
1641  break;
1642  case IS_TRUE:
1643  /* select only TRUE values */
1644  selec = freq_true;
1645  break;
1646  case IS_NOT_TRUE:
1647  /* select non-TRUE values */
1648  selec = 1.0 - freq_true;
1649  break;
1650  case IS_FALSE:
1651  /* select only FALSE values */
1652  selec = freq_false;
1653  break;
1654  case IS_NOT_FALSE:
1655  /* select non-FALSE values */
1656  selec = 1.0 - freq_false;
1657  break;
1658  default:
1659  elog(ERROR, "unrecognized booltesttype: %d",
1660  (int) booltesttype);
1661  selec = 0.0; /* Keep compiler quiet */
1662  break;
1663  }
1664 
1665  free_attstatsslot(&sslot);
1666  }
1667  else
1668  {
1669  /*
1670  * No most-common-value info available. Still have null fraction
1671  * information, so use it for IS [NOT] UNKNOWN. Otherwise adjust
1672  * for null fraction and assume a 50-50 split of TRUE and FALSE.
1673  */
1674  switch (booltesttype)
1675  {
1676  case IS_UNKNOWN:
1677  /* select only NULL values */
1678  selec = freq_null;
1679  break;
1680  case IS_NOT_UNKNOWN:
1681  /* select non-NULL values */
1682  selec = 1.0 - freq_null;
1683  break;
1684  case IS_TRUE:
1685  case IS_FALSE:
1686  /* Assume we select half of the non-NULL values */
1687  selec = (1.0 - freq_null) / 2.0;
1688  break;
1689  case IS_NOT_TRUE:
1690  case IS_NOT_FALSE:
1691  /* Assume we select NULLs plus half of the non-NULLs */
1692  /* equiv. to freq_null + (1.0 - freq_null) / 2.0 */
1693  selec = (freq_null + 1.0) / 2.0;
1694  break;
1695  default:
1696  elog(ERROR, "unrecognized booltesttype: %d",
1697  (int) booltesttype);
1698  selec = 0.0; /* Keep compiler quiet */
1699  break;
1700  }
1701  }
1702  }
1703  else
1704  {
1705  /*
1706  * If we can't get variable statistics for the argument, perhaps
1707  * clause_selectivity can do something with it. We ignore the
1708  * possibility of a NULL value when using clause_selectivity, and just
1709  * assume the value is either TRUE or FALSE.
1710  */
1711  switch (booltesttype)
1712  {
1713  case IS_UNKNOWN:
1714  selec = DEFAULT_UNK_SEL;
1715  break;
1716  case IS_NOT_UNKNOWN:
1717  selec = DEFAULT_NOT_UNK_SEL;
1718  break;
1719  case IS_TRUE:
1720  case IS_NOT_FALSE:
1721  selec = (double) clause_selectivity(root, arg,
1722  varRelid,
1723  jointype, sjinfo);
1724  break;
1725  case IS_FALSE:
1726  case IS_NOT_TRUE:
1727  selec = 1.0 - (double) clause_selectivity(root, arg,
1728  varRelid,
1729  jointype, sjinfo);
1730  break;
1731  default:
1732  elog(ERROR, "unrecognized booltesttype: %d",
1733  (int) booltesttype);
1734  selec = 0.0; /* Keep compiler quiet */
1735  break;
1736  }
1737  }
1738 
1739  ReleaseVariableStats(vardata);
1740 
1741  /* result should be in range, but make sure... */
1742  CLAMP_PROBABILITY(selec);
1743 
1744  return (Selectivity) selec;
1745 }
1746 
1747 /*
1748  * nulltestsel - Selectivity of NullTest Node.
1749  */
1752  int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
1753 {
1754  VariableStatData vardata;
1755  double selec;
1756 
1757  examine_variable(root, arg, varRelid, &vardata);
1758 
1759  if (HeapTupleIsValid(vardata.statsTuple))
1760  {
1761  Form_pg_statistic stats;
1762  double freq_null;
1763 
1764  stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
1765  freq_null = stats->stanullfrac;
1766 
1767  switch (nulltesttype)
1768  {
1769  case IS_NULL:
1770 
1771  /*
1772  * Use freq_null directly.
1773  */
1774  selec = freq_null;
1775  break;
1776  case IS_NOT_NULL:
1777 
1778  /*
1779  * Select not unknown (not null) values. Calculate from
1780  * freq_null.
1781  */
1782  selec = 1.0 - freq_null;
1783  break;
1784  default:
1785  elog(ERROR, "unrecognized nulltesttype: %d",
1786  (int) nulltesttype);
1787  return (Selectivity) 0; /* keep compiler quiet */
1788  }
1789  }
1790  else
1791  {
1792  /*
1793  * No ANALYZE stats available, so make a guess
1794  */
1795  switch (nulltesttype)
1796  {
1797  case IS_NULL:
1798  selec = DEFAULT_UNK_SEL;
1799  break;
1800  case IS_NOT_NULL:
1801  selec = DEFAULT_NOT_UNK_SEL;
1802  break;
1803  default:
1804  elog(ERROR, "unrecognized nulltesttype: %d",
1805  (int) nulltesttype);
1806  return (Selectivity) 0; /* keep compiler quiet */
1807  }
1808  }
1809 
1810  ReleaseVariableStats(vardata);
1811 
1812  /* result should be in range, but make sure... */
1813  CLAMP_PROBABILITY(selec);
1814 
1815  return (Selectivity) selec;
1816 }
1817 
1818 /*
1819  * strip_array_coercion - strip binary-compatible relabeling from an array expr
1820  *
1821  * For array values, the parser normally generates ArrayCoerceExpr conversions,
1822  * but it seems possible that RelabelType might show up. Also, the planner
1823  * is not currently tense about collapsing stacked ArrayCoerceExpr nodes,
1824  * so we need to be ready to deal with more than one level.
1825  */
1826 static Node *
1828 {
1829  for (;;)
1830  {
1831  if (node && IsA(node, ArrayCoerceExpr))
1832  {
1833  ArrayCoerceExpr *acoerce = (ArrayCoerceExpr *) node;
1834 
1835  /*
1836  * If the per-element expression is just a RelabelType on top of
1837  * CaseTestExpr, then we know it's a binary-compatible relabeling.
1838  */
1839  if (IsA(acoerce->elemexpr, RelabelType) &&
1840  IsA(((RelabelType *) acoerce->elemexpr)->arg, CaseTestExpr))
1841  node = (Node *) acoerce->arg;
1842  else
1843  break;
1844  }
1845  else if (node && IsA(node, RelabelType))
1846  {
1847  /* We don't really expect this case, but may as well cope */
1848  node = (Node *) ((RelabelType *) node)->arg;
1849  }
1850  else
1851  break;
1852  }
1853  return node;
1854 }
1855 
1856 /*
1857  * scalararraysel - Selectivity of ScalarArrayOpExpr Node.
1858  */
1861  ScalarArrayOpExpr *clause,
1862  bool is_join_clause,
1863  int varRelid,
1864  JoinType jointype,
1865  SpecialJoinInfo *sjinfo)
1866 {
1867  Oid operator = clause->opno;
1868  bool useOr = clause->useOr;
1869  bool isEquality = false;
1870  bool isInequality = false;
1871  Node *leftop;
1872  Node *rightop;
1873  Oid nominal_element_type;
1874  Oid nominal_element_collation;
1875  TypeCacheEntry *typentry;
1876  RegProcedure oprsel;
1877  FmgrInfo oprselproc;
1878  Selectivity s1;
1879  Selectivity s1disjoint;
1880 
1881  /* First, deconstruct the expression */
1882  Assert(list_length(clause->args) == 2);
1883  leftop = (Node *) linitial(clause->args);
1884  rightop = (Node *) lsecond(clause->args);
1885 
1886  /* aggressively reduce both sides to constants */
1887  leftop = estimate_expression_value(root, leftop);
1888  rightop = estimate_expression_value(root, rightop);
1889 
1890  /* get nominal (after relabeling) element type of rightop */
1891  nominal_element_type = get_base_element_type(exprType(rightop));
1892  if (!OidIsValid(nominal_element_type))
1893  return (Selectivity) 0.5; /* probably shouldn't happen */
1894  /* get nominal collation, too, for generating constants */
1895  nominal_element_collation = exprCollation(rightop);
1896 
1897  /* look through any binary-compatible relabeling of rightop */
1898  rightop = strip_array_coercion(rightop);
1899 
1900  /*
1901  * Detect whether the operator is the default equality or inequality
1902  * operator of the array element type.
1903  */
1904  typentry = lookup_type_cache(nominal_element_type, TYPECACHE_EQ_OPR);
1905  if (OidIsValid(typentry->eq_opr))
1906  {
1907  if (operator == typentry->eq_opr)
1908  isEquality = true;
1909  else if (get_negator(operator) == typentry->eq_opr)
1910  isInequality = true;
1911  }
1912 
1913  /*
1914  * If it is equality or inequality, we might be able to estimate this as a
1915  * form of array containment; for instance "const = ANY(column)" can be
1916  * treated as "ARRAY[const] <@ column". scalararraysel_containment tries
1917  * that, and returns the selectivity estimate if successful, or -1 if not.
1918  */
1919  if ((isEquality || isInequality) && !is_join_clause)
1920  {
1921  s1 = scalararraysel_containment(root, leftop, rightop,
1922  nominal_element_type,
1923  isEquality, useOr, varRelid);
1924  if (s1 >= 0.0)
1925  return s1;
1926  }
1927 
1928  /*
1929  * Look up the underlying operator's selectivity estimator. Punt if it
1930  * hasn't got one.
1931  */
1932  if (is_join_clause)
1933  oprsel = get_oprjoin(operator);
1934  else
1935  oprsel = get_oprrest(operator);
1936  if (!oprsel)
1937  return (Selectivity) 0.5;
1938  fmgr_info(oprsel, &oprselproc);
1939 
1940  /*
1941  * In the array-containment check above, we must only believe that an
1942  * operator is equality or inequality if it is the default btree equality
1943  * operator (or its negator) for the element type, since those are the
1944  * operators that array containment will use. But in what follows, we can
1945  * be a little laxer, and also believe that any operators using eqsel() or
1946  * neqsel() as selectivity estimator act like equality or inequality.
1947  */
1948  if (oprsel == F_EQSEL || oprsel == F_EQJOINSEL)
1949  isEquality = true;
1950  else if (oprsel == F_NEQSEL || oprsel == F_NEQJOINSEL)
1951  isInequality = true;
1952 
1953  /*
1954  * We consider three cases:
1955  *
1956  * 1. rightop is an Array constant: deconstruct the array, apply the
1957  * operator's selectivity function for each array element, and merge the
1958  * results in the same way that clausesel.c does for AND/OR combinations.
1959  *
1960  * 2. rightop is an ARRAY[] construct: apply the operator's selectivity
1961  * function for each element of the ARRAY[] construct, and merge.
1962  *
1963  * 3. otherwise, make a guess ...
1964  */
1965  if (rightop && IsA(rightop, Const))
1966  {
1967  Datum arraydatum = ((Const *) rightop)->constvalue;
1968  bool arrayisnull = ((Const *) rightop)->constisnull;
1969  ArrayType *arrayval;
1970  int16 elmlen;
1971  bool elmbyval;
1972  char elmalign;
1973  int num_elems;
1974  Datum *elem_values;
1975  bool *elem_nulls;
1976  int i;
1977 
1978  if (arrayisnull) /* qual can't succeed if null array */
1979  return (Selectivity) 0.0;
1980  arrayval = DatumGetArrayTypeP(arraydatum);
1982  &elmlen, &elmbyval, &elmalign);
1983  deconstruct_array(arrayval,
1984  ARR_ELEMTYPE(arrayval),
1985  elmlen, elmbyval, elmalign,
1986  &elem_values, &elem_nulls, &num_elems);
1987 
1988  /*
1989  * For generic operators, we assume the probability of success is
1990  * independent for each array element. But for "= ANY" or "<> ALL",
1991  * if the array elements are distinct (which'd typically be the case)
1992  * then the probabilities are disjoint, and we should just sum them.
1993  *
1994  * If we were being really tense we would try to confirm that the
1995  * elements are all distinct, but that would be expensive and it
1996  * doesn't seem to be worth the cycles; it would amount to penalizing
1997  * well-written queries in favor of poorly-written ones. However, we
1998  * do protect ourselves a little bit by checking whether the
1999  * disjointness assumption leads to an impossible (out of range)
2000  * probability; if so, we fall back to the normal calculation.
2001  */
2002  s1 = s1disjoint = (useOr ? 0.0 : 1.0);
2003 
2004  for (i = 0; i < num_elems; i++)
2005  {
2006  List *args;
2007  Selectivity s2;
2008 
2009  args = list_make2(leftop,
2010  makeConst(nominal_element_type,
2011  -1,
2012  nominal_element_collation,
2013  elmlen,
2014  elem_values[i],
2015  elem_nulls[i],
2016  elmbyval));
2017  if (is_join_clause)
2018  s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
2019  clause->inputcollid,
2020  PointerGetDatum(root),
2021  ObjectIdGetDatum(operator),
2022  PointerGetDatum(args),
2023  Int16GetDatum(jointype),
2024  PointerGetDatum(sjinfo)));
2025  else
2026  s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
2027  clause->inputcollid,
2028  PointerGetDatum(root),
2029  ObjectIdGetDatum(operator),
2030  PointerGetDatum(args),
2031  Int32GetDatum(varRelid)));
2032 
2033  if (useOr)
2034  {
2035  s1 = s1 + s2 - s1 * s2;
2036  if (isEquality)
2037  s1disjoint += s2;
2038  }
2039  else
2040  {
2041  s1 = s1 * s2;
2042  if (isInequality)
2043  s1disjoint += s2 - 1.0;
2044  }
2045  }
2046 
2047  /* accept disjoint-probability estimate if in range */
2048  if ((useOr ? isEquality : isInequality) &&
2049  s1disjoint >= 0.0 && s1disjoint <= 1.0)
2050  s1 = s1disjoint;
2051  }
2052  else if (rightop && IsA(rightop, ArrayExpr) &&
2053  !((ArrayExpr *) rightop)->multidims)
2054  {
2055  ArrayExpr *arrayexpr = (ArrayExpr *) rightop;
2056  int16 elmlen;
2057  bool elmbyval;
2058  ListCell *l;
2059 
2060  get_typlenbyval(arrayexpr->element_typeid,
2061  &elmlen, &elmbyval);
2062 
2063  /*
2064  * We use the assumption of disjoint probabilities here too, although
2065  * the odds of equal array elements are rather higher if the elements
2066  * are not all constants (which they won't be, else constant folding
2067  * would have reduced the ArrayExpr to a Const). In this path it's
2068  * critical to have the sanity check on the s1disjoint estimate.
2069  */
2070  s1 = s1disjoint = (useOr ? 0.0 : 1.0);
2071 
2072  foreach(l, arrayexpr->elements)
2073  {
2074  Node *elem = (Node *) lfirst(l);
2075  List *args;
2076  Selectivity s2;
2077 
2078  /*
2079  * Theoretically, if elem isn't of nominal_element_type we should
2080  * insert a RelabelType, but it seems unlikely that any operator
2081  * estimation function would really care ...
2082  */
2083  args = list_make2(leftop, elem);
2084  if (is_join_clause)
2085  s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
2086  clause->inputcollid,
2087  PointerGetDatum(root),
2088  ObjectIdGetDatum(operator),
2089  PointerGetDatum(args),
2090  Int16GetDatum(jointype),
2091  PointerGetDatum(sjinfo)));
2092  else
2093  s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
2094  clause->inputcollid,
2095  PointerGetDatum(root),
2096  ObjectIdGetDatum(operator),
2097  PointerGetDatum(args),
2098  Int32GetDatum(varRelid)));
2099 
2100  if (useOr)
2101  {
2102  s1 = s1 + s2 - s1 * s2;
2103  if (isEquality)
2104  s1disjoint += s2;
2105  }
2106  else
2107  {
2108  s1 = s1 * s2;
2109  if (isInequality)
2110  s1disjoint += s2 - 1.0;
2111  }
2112  }
2113 
2114  /* accept disjoint-probability estimate if in range */
2115  if ((useOr ? isEquality : isInequality) &&
2116  s1disjoint >= 0.0 && s1disjoint <= 1.0)
2117  s1 = s1disjoint;
2118  }
2119  else
2120  {
2121  CaseTestExpr *dummyexpr;
2122  List *args;
2123  Selectivity s2;
2124  int i;
2125 
2126  /*
2127  * We need a dummy rightop to pass to the operator selectivity
2128  * routine. It can be pretty much anything that doesn't look like a
2129  * constant; CaseTestExpr is a convenient choice.
2130  */
2131  dummyexpr = makeNode(CaseTestExpr);
2132  dummyexpr->typeId = nominal_element_type;
2133  dummyexpr->typeMod = -1;
2134  dummyexpr->collation = clause->inputcollid;
2135  args = list_make2(leftop, dummyexpr);
2136  if (is_join_clause)
2137  s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
2138  clause->inputcollid,
2139  PointerGetDatum(root),
2140  ObjectIdGetDatum(operator),
2141  PointerGetDatum(args),
2142  Int16GetDatum(jointype),
2143  PointerGetDatum(sjinfo)));
2144  else
2145  s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
2146  clause->inputcollid,
2147  PointerGetDatum(root),
2148  ObjectIdGetDatum(operator),
2149  PointerGetDatum(args),
2150  Int32GetDatum(varRelid)));
2151  s1 = useOr ? 0.0 : 1.0;
2152 
2153  /*
2154  * Arbitrarily assume 10 elements in the eventual array value (see
2155  * also estimate_array_length). We don't risk an assumption of
2156  * disjoint probabilities here.
2157  */
2158  for (i = 0; i < 10; i++)
2159  {
2160  if (useOr)
2161  s1 = s1 + s2 - s1 * s2;
2162  else
2163  s1 = s1 * s2;
2164  }
2165  }
2166 
2167  /* result should be in range, but make sure... */
2168  CLAMP_PROBABILITY(s1);
2169 
2170  return s1;
2171 }
2172 
2173 /*
2174  * Estimate number of elements in the array yielded by an expression.
2175  *
2176  * It's important that this agree with scalararraysel.
2177  */
2178 int
2180 {
2181  /* look through any binary-compatible relabeling of arrayexpr */
2182  arrayexpr = strip_array_coercion(arrayexpr);
2183 
2184  if (arrayexpr && IsA(arrayexpr, Const))
2185  {
2186  Datum arraydatum = ((Const *) arrayexpr)->constvalue;
2187  bool arrayisnull = ((Const *) arrayexpr)->constisnull;
2188  ArrayType *arrayval;
2189 
2190  if (arrayisnull)
2191  return 0;
2192  arrayval = DatumGetArrayTypeP(arraydatum);
2193  return ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
2194  }
2195  else if (arrayexpr && IsA(arrayexpr, ArrayExpr) &&
2196  !((ArrayExpr *) arrayexpr)->multidims)
2197  {
2198  return list_length(((ArrayExpr *) arrayexpr)->elements);
2199  }
2200  else
2201  {
2202  /* default guess --- see also scalararraysel */
2203  return 10;
2204  }
2205 }
2206 
2207 /*
2208  * rowcomparesel - Selectivity of RowCompareExpr Node.
2209  *
2210  * We estimate RowCompare selectivity by considering just the first (high
2211  * order) columns, which makes it equivalent to an ordinary OpExpr. While
2212  * this estimate could be refined by considering additional columns, it
2213  * seems unlikely that we could do a lot better without multi-column
2214  * statistics.
2215  */
2218  RowCompareExpr *clause,
2219  int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
2220 {
2221  Selectivity s1;
2222  Oid opno = linitial_oid(clause->opnos);
2223  Oid inputcollid = linitial_oid(clause->inputcollids);
2224  List *opargs;
2225  bool is_join_clause;
2226 
2227  /* Build equivalent arg list for single operator */
2228  opargs = list_make2(linitial(clause->largs), linitial(clause->rargs));
2229 
2230  /*
2231  * Decide if it's a join clause. This should match clausesel.c's
2232  * treat_as_join_clause(), except that we intentionally consider only the
2233  * leading columns and not the rest of the clause.
2234  */
2235  if (varRelid != 0)
2236  {
2237  /*
2238  * Caller is forcing restriction mode (eg, because we are examining an
2239  * inner indexscan qual).
2240  */
2241  is_join_clause = false;
2242  }
2243  else if (sjinfo == NULL)
2244  {
2245  /*
2246  * It must be a restriction clause, since it's being evaluated at a
2247  * scan node.
2248  */
2249  is_join_clause = false;
2250  }
2251  else
2252  {
2253  /*
2254  * Otherwise, it's a join if there's more than one relation used.
2255  */
2256  is_join_clause = (NumRelids((Node *) opargs) > 1);
2257  }
2258 
2259  if (is_join_clause)
2260  {
2261  /* Estimate selectivity for a join clause. */
2262  s1 = join_selectivity(root, opno,
2263  opargs,
2264  inputcollid,
2265  jointype,
2266  sjinfo);
2267  }
2268  else
2269  {
2270  /* Estimate selectivity for a restriction clause. */
2271  s1 = restriction_selectivity(root, opno,
2272  opargs,
2273  inputcollid,
2274  varRelid);
2275  }
2276 
2277  return s1;
2278 }
2279 
2280 /*
2281  * eqjoinsel - Join selectivity of "="
2282  */
2283 Datum
2285 {
2286  PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
2287  Oid operator = PG_GETARG_OID(1);
2288  List *args = (List *) PG_GETARG_POINTER(2);
2289 
2290 #ifdef NOT_USED
2291  JoinType jointype = (JoinType) PG_GETARG_INT16(3);
2292 #endif
2294  double selec;
2295  VariableStatData vardata1;
2296  VariableStatData vardata2;
2297  bool join_is_reversed;
2298  RelOptInfo *inner_rel;
2299 
2300  get_join_variables(root, args, sjinfo,
2301  &vardata1, &vardata2, &join_is_reversed);
2302 
2303  switch (sjinfo->jointype)
2304  {
2305  case JOIN_INNER:
2306  case JOIN_LEFT:
2307  case JOIN_FULL:
2308  selec = eqjoinsel_inner(operator, &vardata1, &vardata2);
2309  break;
2310  case JOIN_SEMI:
2311  case JOIN_ANTI:
2312 
2313  /*
2314  * Look up the join's inner relation. min_righthand is sufficient
2315  * information because neither SEMI nor ANTI joins permit any
2316  * reassociation into or out of their RHS, so the righthand will
2317  * always be exactly that set of rels.
2318  */
2319  inner_rel = find_join_input_rel(root, sjinfo->min_righthand);
2320 
2321  if (!join_is_reversed)
2322  selec = eqjoinsel_semi(operator, &vardata1, &vardata2,
2323  inner_rel);
2324  else
2325  selec = eqjoinsel_semi(get_commutator(operator),
2326  &vardata2, &vardata1,
2327  inner_rel);
2328  break;
2329  default:
2330  /* other values not expected here */
2331  elog(ERROR, "unrecognized join type: %d",
2332  (int) sjinfo->jointype);
2333  selec = 0; /* keep compiler quiet */
2334  break;
2335  }
2336 
2337  ReleaseVariableStats(vardata1);
2338  ReleaseVariableStats(vardata2);
2339 
2340  CLAMP_PROBABILITY(selec);
2341 
2342  PG_RETURN_FLOAT8((float8) selec);
2343 }
2344 
2345 /*
2346  * eqjoinsel_inner --- eqjoinsel for normal inner join
2347  *
2348  * We also use this for LEFT/FULL outer joins; it's not presently clear
2349  * that it's worth trying to distinguish them here.
2350  */
2351 static double
2353  VariableStatData *vardata1, VariableStatData *vardata2)
2354 {
2355  double selec;
2356  double nd1;
2357  double nd2;
2358  bool isdefault1;
2359  bool isdefault2;
2360  Oid opfuncoid;
2361  Form_pg_statistic stats1 = NULL;
2362  Form_pg_statistic stats2 = NULL;
2363  bool have_mcvs1 = false;
2364  bool have_mcvs2 = false;
2365  AttStatsSlot sslot1;
2366  AttStatsSlot sslot2;
2367 
2368  nd1 = get_variable_numdistinct(vardata1, &isdefault1);
2369  nd2 = get_variable_numdistinct(vardata2, &isdefault2);
2370 
2371  opfuncoid = get_opcode(operator);
2372 
2373  memset(&sslot1, 0, sizeof(sslot1));
2374  memset(&sslot2, 0, sizeof(sslot2));
2375 
2376  if (HeapTupleIsValid(vardata1->statsTuple))
2377  {
2378  /* note we allow use of nullfrac regardless of security check */
2379  stats1 = (Form_pg_statistic) GETSTRUCT(vardata1->statsTuple);
2380  if (statistic_proc_security_check(vardata1, opfuncoid))
2381  have_mcvs1 = get_attstatsslot(&sslot1, vardata1->statsTuple,
2382  STATISTIC_KIND_MCV, InvalidOid,
2384  }
2385 
2386  if (HeapTupleIsValid(vardata2->statsTuple))
2387  {
2388  /* note we allow use of nullfrac regardless of security check */
2389  stats2 = (Form_pg_statistic) GETSTRUCT(vardata2->statsTuple);
2390  if (statistic_proc_security_check(vardata2, opfuncoid))
2391  have_mcvs2 = get_attstatsslot(&sslot2, vardata2->statsTuple,
2392  STATISTIC_KIND_MCV, InvalidOid,
2394  }
2395 
2396  if (have_mcvs1 && have_mcvs2)
2397  {
2398  /*
2399  * We have most-common-value lists for both relations. Run through
2400  * the lists to see which MCVs actually join to each other with the
2401  * given operator. This allows us to determine the exact join
2402  * selectivity for the portion of the relations represented by the MCV
2403  * lists. We still have to estimate for the remaining population, but
2404  * in a skewed distribution this gives us a big leg up in accuracy.
2405  * For motivation see the analysis in Y. Ioannidis and S.
2406  * Christodoulakis, "On the propagation of errors in the size of join
2407  * results", Technical Report 1018, Computer Science Dept., University
2408  * of Wisconsin, Madison, March 1991 (available from ftp.cs.wisc.edu).
2409  */
2410  FmgrInfo eqproc;
2411  bool *hasmatch1;
2412  bool *hasmatch2;
2413  double nullfrac1 = stats1->stanullfrac;
2414  double nullfrac2 = stats2->stanullfrac;
2415  double matchprodfreq,
2416  matchfreq1,
2417  matchfreq2,
2418  unmatchfreq1,
2419  unmatchfreq2,
2420  otherfreq1,
2421  otherfreq2,
2422  totalsel1,
2423  totalsel2;
2424  int i,
2425  nmatches;
2426 
2427  fmgr_info(opfuncoid, &eqproc);
2428  hasmatch1 = (bool *) palloc0(sslot1.nvalues * sizeof(bool));
2429  hasmatch2 = (bool *) palloc0(sslot2.nvalues * sizeof(bool));
2430 
2431  /*
2432  * Note we assume that each MCV will match at most one member of the
2433  * other MCV list. If the operator isn't really equality, there could
2434  * be multiple matches --- but we don't look for them, both for speed
2435  * and because the math wouldn't add up...
2436  */
2437  matchprodfreq = 0.0;
2438  nmatches = 0;
2439  for (i = 0; i < sslot1.nvalues; i++)
2440  {
2441  int j;
2442 
2443  for (j = 0; j < sslot2.nvalues; j++)
2444  {
2445  if (hasmatch2[j])
2446  continue;
2447  if (DatumGetBool(FunctionCall2Coll(&eqproc,
2448  DEFAULT_COLLATION_OID,
2449  sslot1.values[i],
2450  sslot2.values[j])))
2451  {
2452  hasmatch1[i] = hasmatch2[j] = true;
2453  matchprodfreq += sslot1.numbers[i] * sslot2.numbers[j];
2454  nmatches++;
2455  break;
2456  }
2457  }
2458  }
2459  CLAMP_PROBABILITY(matchprodfreq);
2460  /* Sum up frequencies of matched and unmatched MCVs */
2461  matchfreq1 = unmatchfreq1 = 0.0;
2462  for (i = 0; i < sslot1.nvalues; i++)
2463  {
2464  if (hasmatch1[i])
2465  matchfreq1 += sslot1.numbers[i];
2466  else
2467  unmatchfreq1 += sslot1.numbers[i];
2468  }
2469  CLAMP_PROBABILITY(matchfreq1);
2470  CLAMP_PROBABILITY(unmatchfreq1);
2471  matchfreq2 = unmatchfreq2 = 0.0;
2472  for (i = 0; i < sslot2.nvalues; i++)
2473  {
2474  if (hasmatch2[i])
2475  matchfreq2 += sslot2.numbers[i];
2476  else
2477  unmatchfreq2 += sslot2.numbers[i];
2478  }
2479  CLAMP_PROBABILITY(matchfreq2);
2480  CLAMP_PROBABILITY(unmatchfreq2);
2481  pfree(hasmatch1);
2482  pfree(hasmatch2);
2483 
2484  /*
2485  * Compute total frequency of non-null values that are not in the MCV
2486  * lists.
2487  */
2488  otherfreq1 = 1.0 - nullfrac1 - matchfreq1 - unmatchfreq1;
2489  otherfreq2 = 1.0 - nullfrac2 - matchfreq2 - unmatchfreq2;
2490  CLAMP_PROBABILITY(otherfreq1);
2491  CLAMP_PROBABILITY(otherfreq2);
2492 
2493  /*
2494  * We can estimate the total selectivity from the point of view of
2495  * relation 1 as: the known selectivity for matched MCVs, plus
2496  * unmatched MCVs that are assumed to match against random members of
2497  * relation 2's non-MCV population, plus non-MCV values that are
2498  * assumed to match against random members of relation 2's unmatched
2499  * MCVs plus non-MCV values.
2500  */
2501  totalsel1 = matchprodfreq;
2502  if (nd2 > sslot2.nvalues)
2503  totalsel1 += unmatchfreq1 * otherfreq2 / (nd2 - sslot2.nvalues);
2504  if (nd2 > nmatches)
2505  totalsel1 += otherfreq1 * (otherfreq2 + unmatchfreq2) /
2506  (nd2 - nmatches);
2507  /* Same estimate from the point of view of relation 2. */
2508  totalsel2 = matchprodfreq;
2509  if (nd1 > sslot1.nvalues)
2510  totalsel2 += unmatchfreq2 * otherfreq1 / (nd1 - sslot1.nvalues);
2511  if (nd1 > nmatches)
2512  totalsel2 += otherfreq2 * (otherfreq1 + unmatchfreq1) /
2513  (nd1 - nmatches);
2514 
2515  /*
2516  * Use the smaller of the two estimates. This can be justified in
2517  * essentially the same terms as given below for the no-stats case: to
2518  * a first approximation, we are estimating from the point of view of
2519  * the relation with smaller nd.
2520  */
2521  selec = (totalsel1 < totalsel2) ? totalsel1 : totalsel2;
2522  }
2523  else
2524  {
2525  /*
2526  * We do not have MCV lists for both sides. Estimate the join
2527  * selectivity as MIN(1/nd1,1/nd2)*(1-nullfrac1)*(1-nullfrac2). This
2528  * is plausible if we assume that the join operator is strict and the
2529  * non-null values are about equally distributed: a given non-null
2530  * tuple of rel1 will join to either zero or N2*(1-nullfrac2)/nd2 rows
2531  * of rel2, so total join rows are at most
2532  * N1*(1-nullfrac1)*N2*(1-nullfrac2)/nd2 giving a join selectivity of
2533  * not more than (1-nullfrac1)*(1-nullfrac2)/nd2. By the same logic it
2534  * is not more than (1-nullfrac1)*(1-nullfrac2)/nd1, so the expression
2535  * with MIN() is an upper bound. Using the MIN() means we estimate
2536  * from the point of view of the relation with smaller nd (since the
2537  * larger nd is determining the MIN). It is reasonable to assume that
2538  * most tuples in this rel will have join partners, so the bound is
2539  * probably reasonably tight and should be taken as-is.
2540  *
2541  * XXX Can we be smarter if we have an MCV list for just one side? It
2542  * seems that if we assume equal distribution for the other side, we
2543  * end up with the same answer anyway.
2544  */
2545  double nullfrac1 = stats1 ? stats1->stanullfrac : 0.0;
2546  double nullfrac2 = stats2 ? stats2->stanullfrac : 0.0;
2547 
2548  selec = (1.0 - nullfrac1) * (1.0 - nullfrac2);
2549  if (nd1 > nd2)
2550  selec /= nd1;
2551  else
2552  selec /= nd2;
2553  }
2554 
2555  free_attstatsslot(&sslot1);
2556  free_attstatsslot(&sslot2);
2557 
2558  return selec;
2559 }
2560 
2561 /*
2562  * eqjoinsel_semi --- eqjoinsel for semi join
2563  *
2564  * (Also used for anti join, which we are supposed to estimate the same way.)
2565  * Caller has ensured that vardata1 is the LHS variable.
2566  * Unlike eqjoinsel_inner, we have to cope with operator being InvalidOid.
2567  */
2568 static double
2570  VariableStatData *vardata1, VariableStatData *vardata2,
2571  RelOptInfo *inner_rel)
2572 {
2573  double selec;
2574  double nd1;
2575  double nd2;
2576  bool isdefault1;
2577  bool isdefault2;
2578  Oid opfuncoid;
2579  Form_pg_statistic stats1 = NULL;
2580  bool have_mcvs1 = false;
2581  bool have_mcvs2 = false;
2582  AttStatsSlot sslot1;
2583  AttStatsSlot sslot2;
2584 
2585  nd1 = get_variable_numdistinct(vardata1, &isdefault1);
2586  nd2 = get_variable_numdistinct(vardata2, &isdefault2);
2587 
2588  opfuncoid = OidIsValid(operator) ? get_opcode(operator) : InvalidOid;
2589 
2590  memset(&sslot1, 0, sizeof(sslot1));
2591  memset(&sslot2, 0, sizeof(sslot2));
2592 
2593  /*
2594  * We clamp nd2 to be not more than what we estimate the inner relation's
2595  * size to be. This is intuitively somewhat reasonable since obviously
2596  * there can't be more than that many distinct values coming from the
2597  * inner rel. The reason for the asymmetry (ie, that we don't clamp nd1
2598  * likewise) is that this is the only pathway by which restriction clauses
2599  * applied to the inner rel will affect the join result size estimate,
2600  * since set_joinrel_size_estimates will multiply SEMI/ANTI selectivity by
2601  * only the outer rel's size. If we clamped nd1 we'd be double-counting
2602  * the selectivity of outer-rel restrictions.
2603  *
2604  * We can apply this clamping both with respect to the base relation from
2605  * which the join variable comes (if there is just one), and to the
2606  * immediate inner input relation of the current join.
2607  *
2608  * If we clamp, we can treat nd2 as being a non-default estimate; it's not
2609  * great, maybe, but it didn't come out of nowhere either. This is most
2610  * helpful when the inner relation is empty and consequently has no stats.
2611  */
2612  if (vardata2->rel)
2613  {
2614  if (nd2 >= vardata2->rel->rows)
2615  {
2616  nd2 = vardata2->rel->rows;
2617  isdefault2 = false;
2618  }
2619  }
2620  if (nd2 >= inner_rel->rows)
2621  {
2622  nd2 = inner_rel->rows;
2623  isdefault2 = false;
2624  }
2625 
2626  if (HeapTupleIsValid(vardata1->statsTuple))
2627  {
2628  /* note we allow use of nullfrac regardless of security check */
2629  stats1 = (Form_pg_statistic) GETSTRUCT(vardata1->statsTuple);
2630  if (statistic_proc_security_check(vardata1, opfuncoid))
2631  have_mcvs1 = get_attstatsslot(&sslot1, vardata1->statsTuple,
2632  STATISTIC_KIND_MCV, InvalidOid,
2634  }
2635 
2636  if (HeapTupleIsValid(vardata2->statsTuple) &&
2637  statistic_proc_security_check(vardata2, opfuncoid))
2638  {
2639  have_mcvs2 = get_attstatsslot(&sslot2, vardata2->statsTuple,
2640  STATISTIC_KIND_MCV, InvalidOid,
2642  /* note: currently don't need stanumbers from RHS */
2643  }
2644 
2645  if (have_mcvs1 && have_mcvs2 && OidIsValid(operator))
2646  {
2647  /*
2648  * We have most-common-value lists for both relations. Run through
2649  * the lists to see which MCVs actually join to each other with the
2650  * given operator. This allows us to determine the exact join
2651  * selectivity for the portion of the relations represented by the MCV
2652  * lists. We still have to estimate for the remaining population, but
2653  * in a skewed distribution this gives us a big leg up in accuracy.
2654  */
2655  FmgrInfo eqproc;
2656  bool *hasmatch1;
2657  bool *hasmatch2;
2658  double nullfrac1 = stats1->stanullfrac;
2659  double matchfreq1,
2660  uncertainfrac,
2661  uncertain;
2662  int i,
2663  nmatches,
2664  clamped_nvalues2;
2665 
2666  /*
2667  * The clamping above could have resulted in nd2 being less than
2668  * sslot2.nvalues; in which case, we assume that precisely the nd2
2669  * most common values in the relation will appear in the join input,
2670  * and so compare to only the first nd2 members of the MCV list. Of
2671  * course this is frequently wrong, but it's the best bet we can make.
2672  */
2673  clamped_nvalues2 = Min(sslot2.nvalues, nd2);
2674 
2675  fmgr_info(opfuncoid, &eqproc);
2676  hasmatch1 = (bool *) palloc0(sslot1.nvalues * sizeof(bool));
2677  hasmatch2 = (bool *) palloc0(clamped_nvalues2 * sizeof(bool));
2678 
2679  /*
2680  * Note we assume that each MCV will match at most one member of the
2681  * other MCV list. If the operator isn't really equality, there could
2682  * be multiple matches --- but we don't look for them, both for speed
2683  * and because the math wouldn't add up...
2684  */
2685  nmatches = 0;
2686  for (i = 0; i < sslot1.nvalues; i++)
2687  {
2688  int j;
2689 
2690  for (j = 0; j < clamped_nvalues2; j++)
2691  {
2692  if (hasmatch2[j])
2693  continue;
2694  if (DatumGetBool(FunctionCall2Coll(&eqproc,
2695  DEFAULT_COLLATION_OID,
2696  sslot1.values[i],
2697  sslot2.values[j])))
2698  {
2699  hasmatch1[i] = hasmatch2[j] = true;
2700  nmatches++;
2701  break;
2702  }
2703  }
2704  }
2705  /* Sum up frequencies of matched MCVs */
2706  matchfreq1 = 0.0;
2707  for (i = 0; i < sslot1.nvalues; i++)
2708  {
2709  if (hasmatch1[i])
2710  matchfreq1 += sslot1.numbers[i];
2711  }
2712  CLAMP_PROBABILITY(matchfreq1);
2713  pfree(hasmatch1);
2714  pfree(hasmatch2);
2715 
2716  /*
2717  * Now we need to estimate the fraction of relation 1 that has at
2718  * least one join partner. We know for certain that the matched MCVs
2719  * do, so that gives us a lower bound, but we're really in the dark
2720  * about everything else. Our crude approach is: if nd1 <= nd2 then
2721  * assume all non-null rel1 rows have join partners, else assume for
2722  * the uncertain rows that a fraction nd2/nd1 have join partners. We
2723  * can discount the known-matched MCVs from the distinct-values counts
2724  * before doing the division.
2725  *
2726  * Crude as the above is, it's completely useless if we don't have
2727  * reliable ndistinct values for both sides. Hence, if either nd1 or
2728  * nd2 is default, punt and assume half of the uncertain rows have
2729  * join partners.
2730  */
2731  if (!isdefault1 && !isdefault2)
2732  {
2733  nd1 -= nmatches;
2734  nd2 -= nmatches;
2735  if (nd1 <= nd2 || nd2 < 0)
2736  uncertainfrac = 1.0;
2737  else
2738  uncertainfrac = nd2 / nd1;
2739  }
2740  else
2741  uncertainfrac = 0.5;
2742  uncertain = 1.0 - matchfreq1 - nullfrac1;
2743  CLAMP_PROBABILITY(uncertain);
2744  selec = matchfreq1 + uncertainfrac * uncertain;
2745  }
2746  else
2747  {
2748  /*
2749  * Without MCV lists for both sides, we can only use the heuristic
2750  * about nd1 vs nd2.
2751  */
2752  double nullfrac1 = stats1 ? stats1->stanullfrac : 0.0;
2753 
2754  if (!isdefault1 && !isdefault2)
2755  {
2756  if (nd1 <= nd2 || nd2 < 0)
2757  selec = 1.0 - nullfrac1;
2758  else
2759  selec = (nd2 / nd1) * (1.0 - nullfrac1);
2760  }
2761  else
2762  selec = 0.5 * (1.0 - nullfrac1);
2763  }
2764 
2765  free_attstatsslot(&sslot1);
2766  free_attstatsslot(&sslot2);
2767 
2768  return selec;
2769 }
2770 
2771 /*
2772  * neqjoinsel - Join selectivity of "!="
2773  */
2774 Datum
2776 {
2777  PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
2778  Oid operator = PG_GETARG_OID(1);
2779  List *args = (List *) PG_GETARG_POINTER(2);
2780  JoinType jointype = (JoinType) PG_GETARG_INT16(3);
2782  float8 result;
2783 
2784  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
2785  {
2786  /*
2787  * For semi-joins, if there is more than one distinct value in the RHS
2788  * relation then every non-null LHS row must find a row to join since
2789  * it can only be equal to one of them. We'll assume that there is
2790  * always more than one distinct RHS value for the sake of stability,
2791  * though in theory we could have special cases for empty RHS
2792  * (selectivity = 0) and single-distinct-value RHS (selectivity =
2793  * fraction of LHS that has the same value as the single RHS value).
2794  *
2795  * For anti-joins, if we use the same assumption that there is more
2796  * than one distinct key in the RHS relation, then every non-null LHS
2797  * row must be suppressed by the anti-join.
2798  *
2799  * So either way, the selectivity estimate should be 1 - nullfrac.
2800  */
2801  VariableStatData leftvar;
2802  VariableStatData rightvar;
2803  bool reversed;
2804  HeapTuple statsTuple;
2805  double nullfrac;
2806 
2807  get_join_variables(root, args, sjinfo, &leftvar, &rightvar, &reversed);
2808  statsTuple = reversed ? rightvar.statsTuple : leftvar.statsTuple;
2809  if (HeapTupleIsValid(statsTuple))
2810  nullfrac = ((Form_pg_statistic) GETSTRUCT(statsTuple))->stanullfrac;
2811  else
2812  nullfrac = 0.0;
2813  ReleaseVariableStats(leftvar);
2814  ReleaseVariableStats(rightvar);
2815 
2816  result = 1.0 - nullfrac;
2817  }
2818  else
2819  {
2820  /*
2821  * We want 1 - eqjoinsel() where the equality operator is the one
2822  * associated with this != operator, that is, its negator.
2823  */
2824  Oid eqop = get_negator(operator);
2825 
2826  if (eqop)
2827  {
2829  PointerGetDatum(root),
2830  ObjectIdGetDatum(eqop),
2831  PointerGetDatum(args),
2832  Int16GetDatum(jointype),
2833  PointerGetDatum(sjinfo)));
2834  }
2835  else
2836  {
2837  /* Use default selectivity (should we raise an error instead?) */
2838  result = DEFAULT_EQ_SEL;
2839  }
2840  result = 1.0 - result;
2841  }
2842 
2843  PG_RETURN_FLOAT8(result);
2844 }
2845 
2846 /*
2847  * scalarltjoinsel - Join selectivity of "<" for scalars
2848  */
2849 Datum
2851 {
2853 }
2854 
2855 /*
2856  * scalarlejoinsel - Join selectivity of "<=" for scalars
2857  */
2858 Datum
2860 {
2862 }
2863 
2864 /*
2865  * scalargtjoinsel - Join selectivity of ">" for scalars
2866  */
2867 Datum
2869 {
2871 }
2872 
2873 /*
2874  * scalargejoinsel - Join selectivity of ">=" for scalars
2875  */
2876 Datum
2878 {
2880 }
2881 
2882 /*
2883  * patternjoinsel - Generic code for pattern-match join selectivity.
2884  */
2885 static double
2887 {
2888  /* For the moment we just punt. */
2889  return negate ? (1.0 - DEFAULT_MATCH_SEL) : DEFAULT_MATCH_SEL;
2890 }
2891 
2892 /*
2893  * regexeqjoinsel - Join selectivity of regular-expression pattern match.
2894  */
2895 Datum
2897 {
2899 }
2900 
2901 /*
2902  * icregexeqjoinsel - Join selectivity of case-insensitive regex match.
2903  */
2904 Datum
2906 {
2908 }
2909 
2910 /*
2911  * likejoinsel - Join selectivity of LIKE pattern match.
2912  */
2913 Datum
2915 {
2917 }
2918 
2919 /*
2920  * prefixjoinsel - Join selectivity of prefix operator
2921  */
2922 Datum
2924 {
2926 }
2927 
2928 /*
2929  * iclikejoinsel - Join selectivity of ILIKE pattern match.
2930  */
2931 Datum
2933 {
2935 }
2936 
2937 /*
2938  * regexnejoinsel - Join selectivity of regex non-match.
2939  */
2940 Datum
2942 {
2944 }
2945 
2946 /*
2947  * icregexnejoinsel - Join selectivity of case-insensitive regex non-match.
2948  */
2949 Datum
2951 {
2953 }
2954 
2955 /*
2956  * nlikejoinsel - Join selectivity of LIKE pattern non-match.
2957  */
2958 Datum
2960 {
2962 }
2963 
2964 /*
2965  * icnlikejoinsel - Join selectivity of ILIKE pattern non-match.
2966  */
2967 Datum
2969 {
2971 }
2972 
2973 /*
2974  * mergejoinscansel - Scan selectivity of merge join.
2975  *
2976  * A merge join will stop as soon as it exhausts either input stream.
2977  * Therefore, if we can estimate the ranges of both input variables,
2978  * we can estimate how much of the input will actually be read. This
2979  * can have a considerable impact on the cost when using indexscans.
2980  *
2981  * Also, we can estimate how much of each input has to be read before the
2982  * first join pair is found, which will affect the join's startup time.
2983  *
2984  * clause should be a clause already known to be mergejoinable. opfamily,
2985  * strategy, and nulls_first specify the sort ordering being used.
2986  *
2987  * The outputs are:
2988  * *leftstart is set to the fraction of the left-hand variable expected
2989  * to be scanned before the first join pair is found (0 to 1).
2990  * *leftend is set to the fraction of the left-hand variable expected
2991  * to be scanned before the join terminates (0 to 1).
2992  * *rightstart, *rightend similarly for the right-hand variable.
2993  */
2994 void
2996  Oid opfamily, int strategy, bool nulls_first,
2997  Selectivity *leftstart, Selectivity *leftend,
2998  Selectivity *rightstart, Selectivity *rightend)
2999 {
3000  Node *left,
3001  *right;
3002  VariableStatData leftvar,
3003  rightvar;
3004  int op_strategy;
3005  Oid op_lefttype;
3006  Oid op_righttype;
3007  Oid opno,
3008  lsortop,
3009  rsortop,
3010  lstatop,
3011  rstatop,
3012  ltop,
3013  leop,
3014  revltop,
3015  revleop;
3016  bool isgt;
3017  Datum leftmin,
3018  leftmax,
3019  rightmin,
3020  rightmax;
3021  double selec;
3022 
3023  /* Set default results if we can't figure anything out. */
3024  /* XXX should default "start" fraction be a bit more than 0? */
3025  *leftstart = *rightstart = 0.0;
3026  *leftend = *rightend = 1.0;
3027 
3028  /* Deconstruct the merge clause */
3029  if (!is_opclause(clause))
3030  return; /* shouldn't happen */
3031  opno = ((OpExpr *) clause)->opno;
3032  left = get_leftop((Expr *) clause);
3033  right = get_rightop((Expr *) clause);
3034  if (!right)
3035  return; /* shouldn't happen */
3036 
3037  /* Look for stats for the inputs */
3038  examine_variable(root, left, 0, &leftvar);
3039  examine_variable(root, right, 0, &rightvar);
3040 
3041  /* Extract the operator's declared left/right datatypes */
3042  get_op_opfamily_properties(opno, opfamily, false,
3043  &op_strategy,
3044  &op_lefttype,
3045  &op_righttype);
3046  Assert(op_strategy == BTEqualStrategyNumber);
3047 
3048  /*
3049  * Look up the various operators we need. If we don't find them all, it
3050  * probably means the opfamily is broken, but we just fail silently.
3051  *
3052  * Note: we expect that pg_statistic histograms will be sorted by the '<'
3053  * operator, regardless of which sort direction we are considering.
3054  */
3055  switch (strategy)
3056  {
3057  case BTLessStrategyNumber:
3058  isgt = false;
3059  if (op_lefttype == op_righttype)
3060  {
3061  /* easy case */
3062  ltop = get_opfamily_member(opfamily,
3063  op_lefttype, op_righttype,
3065  leop = get_opfamily_member(opfamily,
3066  op_lefttype, op_righttype,
3068  lsortop = ltop;
3069  rsortop = ltop;
3070  lstatop = lsortop;
3071  rstatop = rsortop;
3072  revltop = ltop;
3073  revleop = leop;
3074  }
3075  else
3076  {
3077  ltop = get_opfamily_member(opfamily,
3078  op_lefttype, op_righttype,
3080  leop = get_opfamily_member(opfamily,
3081  op_lefttype, op_righttype,
3083  lsortop = get_opfamily_member(opfamily,
3084  op_lefttype, op_lefttype,
3086  rsortop = get_opfamily_member(opfamily,
3087  op_righttype, op_righttype,
3089  lstatop = lsortop;
3090  rstatop = rsortop;
3091  revltop = get_opfamily_member(opfamily,
3092  op_righttype, op_lefttype,
3094  revleop = get_opfamily_member(opfamily,
3095  op_righttype, op_lefttype,
3097  }
3098  break;
3100  /* descending-order case */
3101  isgt = true;
3102  if (op_lefttype == op_righttype)
3103  {
3104  /* easy case */
3105  ltop = get_opfamily_member(opfamily,
3106  op_lefttype, op_righttype,
3108  leop = get_opfamily_member(opfamily,
3109  op_lefttype, op_righttype,
3111  lsortop = ltop;
3112  rsortop = ltop;
3113  lstatop = get_opfamily_member(opfamily,
3114  op_lefttype, op_lefttype,
3116  rstatop = lstatop;
3117  revltop = ltop;
3118  revleop = leop;
3119  }
3120  else
3121  {
3122  ltop = get_opfamily_member(opfamily,
3123  op_lefttype, op_righttype,
3125  leop = get_opfamily_member(opfamily,
3126  op_lefttype, op_righttype,
3128  lsortop = get_opfamily_member(opfamily,
3129  op_lefttype, op_lefttype,
3131  rsortop = get_opfamily_member(opfamily,
3132  op_righttype, op_righttype,
3134  lstatop = get_opfamily_member(opfamily,
3135  op_lefttype, op_lefttype,
3137  rstatop = get_opfamily_member(opfamily,
3138  op_righttype, op_righttype,
3140  revltop = get_opfamily_member(opfamily,
3141  op_righttype, op_lefttype,
3143  revleop = get_opfamily_member(opfamily,
3144  op_righttype, op_lefttype,
3146  }
3147  break;
3148  default:
3149  goto fail; /* shouldn't get here */
3150  }
3151 
3152  if (!OidIsValid(lsortop) ||
3153  !OidIsValid(rsortop) ||
3154  !OidIsValid(lstatop) ||
3155  !OidIsValid(rstatop) ||
3156  !OidIsValid(ltop) ||
3157  !OidIsValid(leop) ||
3158  !OidIsValid(revltop) ||
3159  !OidIsValid(revleop))
3160  goto fail; /* insufficient info in catalogs */
3161 
3162  /* Try to get ranges of both inputs */
3163  if (!isgt)
3164  {
3165  if (!get_variable_range(root, &leftvar, lstatop,
3166  &leftmin, &leftmax))
3167  goto fail; /* no range available from stats */
3168  if (!get_variable_range(root, &rightvar, rstatop,
3169  &rightmin, &rightmax))
3170  goto fail; /* no range available from stats */
3171  }
3172  else
3173  {
3174  /* need to swap the max and min */
3175  if (!get_variable_range(root, &leftvar, lstatop,
3176  &leftmax, &leftmin))
3177  goto fail; /* no range available from stats */
3178  if (!get_variable_range(root, &rightvar, rstatop,
3179  &rightmax, &rightmin))
3180  goto fail; /* no range available from stats */
3181  }
3182 
3183  /*
3184  * Now, the fraction of the left variable that will be scanned is the
3185  * fraction that's <= the right-side maximum value. But only believe
3186  * non-default estimates, else stick with our 1.0.
3187  */
3188  selec = scalarineqsel(root, leop, isgt, true, &leftvar,
3189  rightmax, op_righttype);
3190  if (selec != DEFAULT_INEQ_SEL)
3191  *leftend = selec;
3192 
3193  /* And similarly for the right variable. */
3194  selec = scalarineqsel(root, revleop, isgt, true, &rightvar,
3195  leftmax, op_lefttype);
3196  if (selec != DEFAULT_INEQ_SEL)
3197  *rightend = selec;
3198 
3199  /*
3200  * Only one of the two "end" fractions can really be less than 1.0;
3201  * believe the smaller estimate and reset the other one to exactly 1.0. If
3202  * we get exactly equal estimates (as can easily happen with self-joins),
3203  * believe neither.
3204  */
3205  if (*leftend > *rightend)
3206  *leftend = 1.0;
3207  else if (*leftend < *rightend)
3208  *rightend = 1.0;
3209  else
3210  *leftend = *rightend = 1.0;
3211 
3212  /*
3213  * Also, the fraction of the left variable that will be scanned before the
3214  * first join pair is found is the fraction that's < the right-side
3215  * minimum value. But only believe non-default estimates, else stick with
3216  * our own default.
3217  */
3218  selec = scalarineqsel(root, ltop, isgt, false, &leftvar,
3219  rightmin, op_righttype);
3220  if (selec != DEFAULT_INEQ_SEL)
3221  *leftstart = selec;
3222 
3223  /* And similarly for the right variable. */
3224  selec = scalarineqsel(root, revltop, isgt, false, &rightvar,
3225  leftmin, op_lefttype);
3226  if (selec != DEFAULT_INEQ_SEL)
3227  *rightstart = selec;
3228 
3229  /*
3230  * Only one of the two "start" fractions can really be more than zero;
3231  * believe the larger estimate and reset the other one to exactly 0.0. If
3232  * we get exactly equal estimates (as can easily happen with self-joins),
3233  * believe neither.
3234  */
3235  if (*leftstart < *rightstart)
3236  *leftstart = 0.0;
3237  else if (*leftstart > *rightstart)
3238  *rightstart = 0.0;
3239  else
3240  *leftstart = *rightstart = 0.0;
3241 
3242  /*
3243  * If the sort order is nulls-first, we're going to have to skip over any
3244  * nulls too. These would not have been counted by scalarineqsel, and we
3245  * can safely add in this fraction regardless of whether we believe
3246  * scalarineqsel's results or not. But be sure to clamp the sum to 1.0!
3247  */
3248  if (nulls_first)
3249  {
3250  Form_pg_statistic stats;
3251 
3252  if (HeapTupleIsValid(leftvar.statsTuple))
3253  {
3254  stats = (Form_pg_statistic) GETSTRUCT(leftvar.statsTuple);
3255  *leftstart += stats->stanullfrac;
3256  CLAMP_PROBABILITY(*leftstart);
3257  *leftend += stats->stanullfrac;
3258  CLAMP_PROBABILITY(*leftend);
3259  }
3260  if (HeapTupleIsValid(rightvar.statsTuple))
3261  {
3262  stats = (Form_pg_statistic) GETSTRUCT(rightvar.statsTuple);
3263  *rightstart += stats->stanullfrac;
3264  CLAMP_PROBABILITY(*rightstart);
3265  *rightend += stats->stanullfrac;
3266  CLAMP_PROBABILITY(*rightend);
3267  }
3268  }
3269 
3270  /* Disbelieve start >= end, just in case that can happen */
3271  if (*leftstart >= *leftend)
3272  {
3273  *leftstart = 0.0;
3274  *leftend = 1.0;
3275  }
3276  if (*rightstart >= *rightend)
3277  {
3278  *rightstart = 0.0;
3279  *rightend = 1.0;
3280  }
3281 
3282 fail:
3283  ReleaseVariableStats(leftvar);
3284  ReleaseVariableStats(rightvar);
3285 }
3286 
3287 
3288 /*
3289  * Helper routine for estimate_num_groups: add an item to a list of
3290  * GroupVarInfos, but only if it's not known equal to any of the existing
3291  * entries.
3292  */
3293 typedef struct
3294 {
3295  Node *var; /* might be an expression, not just a Var */
3296  RelOptInfo *rel; /* relation it belongs to */
3297  double ndistinct; /* # distinct values */
3298 } GroupVarInfo;
3299 
3300 static List *
3302  Node *var, VariableStatData *vardata)
3303 {
3304  GroupVarInfo *varinfo;
3305  double ndistinct;
3306  bool isdefault;
3307  ListCell *lc;
3308 
3309  ndistinct = get_variable_numdistinct(vardata, &isdefault);
3310 
3311  /* cannot use foreach here because of possible list_delete */
3312  lc = list_head(varinfos);
3313  while (lc)
3314  {
3315  varinfo = (GroupVarInfo *) lfirst(lc);
3316 
3317  /* must advance lc before list_delete possibly pfree's it */
3318  lc = lnext(lc);
3319 
3320  /* Drop exact duplicates */
3321  if (equal(var, varinfo->var))
3322  return varinfos;
3323 
3324  /*
3325  * Drop known-equal vars, but only if they belong to different
3326  * relations (see comments for estimate_num_groups)
3327  */
3328  if (vardata->rel != varinfo->rel &&
3329  exprs_known_equal(root, var, varinfo->var))
3330  {
3331  if (varinfo->ndistinct <= ndistinct)
3332  {
3333  /* Keep older item, forget new one */
3334  return varinfos;
3335  }
3336  else
3337  {
3338  /* Delete the older item */
3339  varinfos = list_delete_ptr(varinfos, varinfo);
3340  }
3341  }
3342  }
3343 
3344  varinfo = (GroupVarInfo *) palloc(sizeof(GroupVarInfo));
3345 
3346  varinfo->var = var;
3347  varinfo->rel = vardata->rel;
3348  varinfo->ndistinct = ndistinct;
3349  varinfos = lappend(varinfos, varinfo);
3350  return varinfos;
3351 }
3352 
3353 /*
3354  * estimate_num_groups - Estimate number of groups in a grouped query
3355  *
3356  * Given a query having a GROUP BY clause, estimate how many groups there
3357  * will be --- ie, the number of distinct combinations of the GROUP BY
3358  * expressions.
3359  *
3360  * This routine is also used to estimate the number of rows emitted by
3361  * a DISTINCT filtering step; that is an isomorphic problem. (Note:
3362  * actually, we only use it for DISTINCT when there's no grouping or
3363  * aggregation ahead of the DISTINCT.)
3364  *
3365  * Inputs:
3366  * root - the query
3367  * groupExprs - list of expressions being grouped by
3368  * input_rows - number of rows estimated to arrive at the group/unique
3369  * filter step
3370  * pgset - NULL, or a List** pointing to a grouping set to filter the
3371  * groupExprs against
3372  *
3373  * Given the lack of any cross-correlation statistics in the system, it's
3374  * impossible to do anything really trustworthy with GROUP BY conditions
3375  * involving multiple Vars. We should however avoid assuming the worst
3376  * case (all possible cross-product terms actually appear as groups) since
3377  * very often the grouped-by Vars are highly correlated. Our current approach
3378  * is as follows:
3379  * 1. Expressions yielding boolean are assumed to contribute two groups,
3380  * independently of their content, and are ignored in the subsequent
3381  * steps. This is mainly because tests like "col IS NULL" break the
3382  * heuristic used in step 2 especially badly.
3383  * 2. Reduce the given expressions to a list of unique Vars used. For
3384  * example, GROUP BY a, a + b is treated the same as GROUP BY a, b.
3385  * It is clearly correct not to count the same Var more than once.
3386  * It is also reasonable to treat f(x) the same as x: f() cannot
3387  * increase the number of distinct values (unless it is volatile,
3388  * which we consider unlikely for grouping), but it probably won't
3389  * reduce the number of distinct values much either.
3390  * As a special case, if a GROUP BY expression can be matched to an
3391  * expressional index for which we have statistics, then we treat the
3392  * whole expression as though it were just a Var.
3393  * 3. If the list contains Vars of different relations that are known equal
3394  * due to equivalence classes, then drop all but one of the Vars from each
3395  * known-equal set, keeping the one with smallest estimated # of values
3396  * (since the extra values of the others can't appear in joined rows).
3397  * Note the reason we only consider Vars of different relations is that
3398  * if we considered ones of the same rel, we'd be double-counting the
3399  * restriction selectivity of the equality in the next step.
3400  * 4. For Vars within a single source rel, we multiply together the numbers
3401  * of values, clamp to the number of rows in the rel (divided by 10 if
3402  * more than one Var), and then multiply by a factor based on the
3403  * selectivity of the restriction clauses for that rel. When there's
3404  * more than one Var, the initial product is probably too high (it's the
3405  * worst case) but clamping to a fraction of the rel's rows seems to be a
3406  * helpful heuristic for not letting the estimate get out of hand. (The
3407  * factor of 10 is derived from pre-Postgres-7.4 practice.) The factor
3408  * we multiply by to adjust for the restriction selectivity assumes that
3409  * the restriction clauses are independent of the grouping, which may not
3410  * be a valid assumption, but it's hard to do better.
3411  * 5. If there are Vars from multiple rels, we repeat step 4 for each such
3412  * rel, and multiply the results together.
3413  * Note that rels not containing grouped Vars are ignored completely, as are
3414  * join clauses. Such rels cannot increase the number of groups, and we
3415  * assume such clauses do not reduce the number either (somewhat bogus,
3416  * but we don't have the info to do better).
3417  */
3418 double
3419 estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
3420  List **pgset)
3421 {
3422  List *varinfos = NIL;
3423  double srf_multiplier = 1.0;
3424  double numdistinct;
3425  ListCell *l;
3426  int i;
3427 
3428  /*
3429  * We don't ever want to return an estimate of zero groups, as that tends
3430  * to lead to division-by-zero and other unpleasantness. The input_rows
3431  * estimate is usually already at least 1, but clamp it just in case it
3432  * isn't.
3433  */
3434  input_rows = clamp_row_est(input_rows);
3435 
3436  /*
3437  * If no grouping columns, there's exactly one group. (This can't happen
3438  * for normal cases with GROUP BY or DISTINCT, but it is possible for
3439  * corner cases with set operations.)
3440  */
3441  if (groupExprs == NIL || (pgset && list_length(*pgset) < 1))
3442  return 1.0;
3443 
3444  /*
3445  * Count groups derived from boolean grouping expressions. For other
3446  * expressions, find the unique Vars used, treating an expression as a Var
3447  * if we can find stats for it. For each one, record the statistical
3448  * estimate of number of distinct values (total in its table, without
3449  * regard for filtering).
3450  */
3451  numdistinct = 1.0;
3452 
3453  i = 0;
3454  foreach(l, groupExprs)
3455  {
3456  Node *groupexpr = (Node *) lfirst(l);
3457  double this_srf_multiplier;
3458  VariableStatData vardata;
3459  List *varshere;
3460  ListCell *l2;
3461 
3462  /* is expression in this grouping set? */
3463  if (pgset && !list_member_int(*pgset, i++))
3464  continue;
3465 
3466  /*
3467  * Set-returning functions in grouping columns are a bit problematic.
3468  * The code below will effectively ignore their SRF nature and come up
3469  * with a numdistinct estimate as though they were scalar functions.
3470  * We compensate by scaling up the end result by the largest SRF
3471  * rowcount estimate. (This will be an overestimate if the SRF
3472  * produces multiple copies of any output value, but it seems best to
3473  * assume the SRF's outputs are distinct. In any case, it's probably
3474  * pointless to worry too much about this without much better
3475  * estimates for SRF output rowcounts than we have today.)
3476  */
3477  this_srf_multiplier = expression_returns_set_rows(groupexpr);
3478  if (srf_multiplier < this_srf_multiplier)
3479  srf_multiplier = this_srf_multiplier;
3480 
3481  /* Short-circuit for expressions returning boolean */
3482  if (exprType(groupexpr) == BOOLOID)
3483  {
3484  numdistinct *= 2.0;
3485  continue;
3486  }
3487 
3488  /*
3489  * If examine_variable is able to deduce anything about the GROUP BY
3490  * expression, treat it as a single variable even if it's really more
3491  * complicated.
3492  */
3493  examine_variable(root, groupexpr, 0, &vardata);
3494  if (HeapTupleIsValid(vardata.statsTuple) || vardata.isunique)
3495  {
3496  varinfos = add_unique_group_var(root, varinfos,
3497  groupexpr, &vardata);
3498  ReleaseVariableStats(vardata);
3499  continue;
3500  }
3501  ReleaseVariableStats(vardata);
3502 
3503  /*
3504  * Else pull out the component Vars. Handle PlaceHolderVars by
3505  * recursing into their arguments (effectively assuming that the
3506  * PlaceHolderVar doesn't change the number of groups, which boils
3507  * down to ignoring the possible addition of nulls to the result set).
3508  */
3509  varshere = pull_var_clause(groupexpr,
3513 
3514  /*
3515  * If we find any variable-free GROUP BY item, then either it is a
3516  * constant (and we can ignore it) or it contains a volatile function;
3517  * in the latter case we punt and assume that each input row will
3518  * yield a distinct group.
3519  */
3520  if (varshere == NIL)
3521  {
3522  if (contain_volatile_functions(groupexpr))
3523  return input_rows;
3524  continue;
3525  }
3526 
3527  /*
3528  * Else add variables to varinfos list
3529  */
3530  foreach(l2, varshere)
3531  {
3532  Node *var = (Node *) lfirst(l2);
3533 
3534  examine_variable(root, var, 0, &vardata);
3535  varinfos = add_unique_group_var(root, varinfos, var, &vardata);
3536  ReleaseVariableStats(vardata);
3537  }
3538  }
3539 
3540  /*
3541  * If now no Vars, we must have an all-constant or all-boolean GROUP BY
3542  * list.
3543  */
3544  if (varinfos == NIL)
3545  {
3546  /* Apply SRF multiplier as we would do in the long path */
3547  numdistinct *= srf_multiplier;
3548  /* Round off */
3549  numdistinct = ceil(numdistinct);
3550  /* Guard against out-of-range answers */
3551  if (numdistinct > input_rows)
3552  numdistinct = input_rows;
3553  if (numdistinct < 1.0)
3554  numdistinct = 1.0;
3555  return numdistinct;
3556  }
3557 
3558  /*
3559  * Group Vars by relation and estimate total numdistinct.
3560  *
3561  * For each iteration of the outer loop, we process the frontmost Var in
3562  * varinfos, plus all other Vars in the same relation. We remove these
3563  * Vars from the newvarinfos list for the next iteration. This is the
3564  * easiest way to group Vars of same rel together.
3565  */
3566  do
3567  {
3568  GroupVarInfo *varinfo1 = (GroupVarInfo *) linitial(varinfos);
3569  RelOptInfo *rel = varinfo1->rel;
3570  double reldistinct = 1;
3571  double relmaxndistinct = reldistinct;
3572  int relvarcount = 0;
3573  List *newvarinfos = NIL;
3574  List *relvarinfos = NIL;
3575 
3576  /*
3577  * Split the list of varinfos in two - one for the current rel, one
3578  * for remaining Vars on other rels.
3579  */
3580  relvarinfos = lcons(varinfo1, relvarinfos);
3581  for_each_cell(l, lnext(list_head(varinfos)))
3582  {
3583  GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(l);
3584 
3585  if (varinfo2->rel == varinfo1->rel)
3586  {
3587  /* varinfos on current rel */
3588  relvarinfos = lcons(varinfo2, relvarinfos);
3589  }
3590  else
3591  {
3592  /* not time to process varinfo2 yet */
3593  newvarinfos = lcons(varinfo2, newvarinfos);
3594  }
3595  }
3596 
3597  /*
3598  * Get the numdistinct estimate for the Vars of this rel. We
3599  * iteratively search for multivariate n-distinct with maximum number
3600  * of vars; assuming that each var group is independent of the others,
3601  * we multiply them together. Any remaining relvarinfos after no more
3602  * multivariate matches are found are assumed independent too, so
3603  * their individual ndistinct estimates are multiplied also.
3604  *
3605  * While iterating, count how many separate numdistinct values we
3606  * apply. We apply a fudge factor below, but only if we multiplied
3607  * more than one such values.
3608  */
3609  while (relvarinfos)
3610  {
3611  double mvndistinct;
3612 
3613  if (estimate_multivariate_ndistinct(root, rel, &relvarinfos,
3614  &mvndistinct))
3615  {
3616  reldistinct *= mvndistinct;
3617  if (relmaxndistinct < mvndistinct)
3618  relmaxndistinct = mvndistinct;
3619  relvarcount++;
3620  }
3621  else
3622  {
3623  foreach(l, relvarinfos)
3624  {
3625  GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(l);
3626 
3627  reldistinct *= varinfo2->ndistinct;
3628  if (relmaxndistinct < varinfo2->ndistinct)
3629  relmaxndistinct = varinfo2->ndistinct;
3630  relvarcount++;
3631  }
3632 
3633  /* we're done with this relation */
3634  relvarinfos = NIL;
3635  }
3636  }
3637 
3638  /*
3639  * Sanity check --- don't divide by zero if empty relation.
3640  */
3641  Assert(IS_SIMPLE_REL(rel));
3642  if (rel->tuples > 0)
3643  {
3644  /*
3645  * Clamp to size of rel, or size of rel / 10 if multiple Vars. The
3646  * fudge factor is because the Vars are probably correlated but we
3647  * don't know by how much. We should never clamp to less than the
3648  * largest ndistinct value for any of the Vars, though, since
3649  * there will surely be at least that many groups.
3650  */
3651  double clamp = rel->tuples;
3652 
3653  if (relvarcount > 1)
3654  {
3655  clamp *= 0.1;
3656  if (clamp < relmaxndistinct)
3657  {
3658  clamp = relmaxndistinct;
3659  /* for sanity in case some ndistinct is too large: */
3660  if (clamp > rel->tuples)
3661  clamp = rel->tuples;
3662  }
3663  }
3664  if (reldistinct > clamp)
3665  reldistinct = clamp;
3666 
3667  /*
3668  * Update the estimate based on the restriction selectivity,
3669  * guarding against division by zero when reldistinct is zero.
3670  * Also skip this if we know that we are returning all rows.
3671  */
3672  if (reldistinct > 0 && rel->rows < rel->tuples)
3673  {
3674  /*
3675  * Given a table containing N rows with n distinct values in a
3676  * uniform distribution, if we select p rows at random then
3677  * the expected number of distinct values selected is
3678  *
3679  * n * (1 - product((N-N/n-i)/(N-i), i=0..p-1))
3680  *
3681  * = n * (1 - (N-N/n)! / (N-N/n-p)! * (N-p)! / N!)
3682  *
3683  * See "Approximating block accesses in database
3684  * organizations", S. B. Yao, Communications of the ACM,
3685  * Volume 20 Issue 4, April 1977 Pages 260-261.
3686  *
3687  * Alternatively, re-arranging the terms from the factorials,
3688  * this may be written as
3689  *
3690  * n * (1 - product((N-p-i)/(N-i), i=0..N/n-1))
3691  *
3692  * This form of the formula is more efficient to compute in
3693  * the common case where p is larger than N/n. Additionally,
3694  * as pointed out by Dell'Era, if i << N for all terms in the
3695  * product, it can be approximated by
3696  *
3697  * n * (1 - ((N-p)/N)^(N/n))
3698  *
3699  * See "Expected distinct values when selecting from a bag
3700  * without replacement", Alberto Dell'Era,
3701  * http://www.adellera.it/investigations/distinct_balls/.
3702  *
3703  * The condition i << N is equivalent to n >> 1, so this is a
3704  * good approximation when the number of distinct values in
3705  * the table is large. It turns out that this formula also
3706  * works well even when n is small.
3707  */
3708  reldistinct *=
3709  (1 - pow((rel->tuples - rel->rows) / rel->tuples,
3710  rel->tuples / reldistinct));
3711  }
3712  reldistinct = clamp_row_est(reldistinct);
3713 
3714  /*
3715  * Update estimate of total distinct groups.
3716  */
3717  numdistinct *= reldistinct;
3718  }
3719 
3720  varinfos = newvarinfos;
3721  } while (varinfos != NIL);
3722 
3723  /* Now we can account for the effects of any SRFs */
3724  numdistinct *= srf_multiplier;
3725 
3726  /* Round off */
3727  numdistinct = ceil(numdistinct);
3728 
3729  /* Guard against out-of-range answers */
3730  if (numdistinct > input_rows)
3731  numdistinct = input_rows;
3732  if (numdistinct < 1.0)
3733  numdistinct = 1.0;
3734 
3735  return numdistinct;
3736 }
3737 
3738 /*
3739  * Estimate hash bucket statistics when the specified expression is used
3740  * as a hash key for the given number of buckets.
3741  *
3742  * This attempts to determine two values:
3743  *
3744  * 1. The frequency of the most common value of the expression (returns
3745  * zero into *mcv_freq if we can't get that).
3746  *
3747  * 2. The "bucketsize fraction", ie, average number of entries in a bucket
3748  * divided by total tuples in relation.
3749  *
3750  * XXX This is really pretty bogus since we're effectively assuming that the
3751  * distribution of hash keys will be the same after applying restriction
3752  * clauses as it was in the underlying relation. However, we are not nearly
3753  * smart enough to figure out how the restrict clauses might change the
3754  * distribution, so this will have to do for now.
3755  *
3756  * We are passed the number of buckets the executor will use for the given
3757  * input relation. If the data were perfectly distributed, with the same
3758  * number of tuples going into each available bucket, then the bucketsize
3759  * fraction would be 1/nbuckets. But this happy state of affairs will occur
3760  * only if (a) there are at least nbuckets distinct data values, and (b)
3761  * we have a not-too-skewed data distribution. Otherwise the buckets will
3762  * be nonuniformly occupied. If the other relation in the join has a key
3763  * distribution similar to this one's, then the most-loaded buckets are
3764  * exactly those that will be probed most often. Therefore, the "average"
3765  * bucket size for costing purposes should really be taken as something close
3766  * to the "worst case" bucket size. We try to estimate this by adjusting the
3767  * fraction if there are too few distinct data values, and then scaling up
3768  * by the ratio of the most common value's frequency to the average frequency.
3769  *
3770  * If no statistics are available, use a default estimate of 0.1. This will
3771  * discourage use of a hash rather strongly if the inner relation is large,
3772  * which is what we want. We do not want to hash unless we know that the
3773  * inner rel is well-dispersed (or the alternatives seem much worse).
3774  *
3775  * The caller should also check that the mcv_freq is not so large that the
3776  * most common value would by itself require an impractically large bucket.
3777  * In a hash join, the executor can split buckets if they get too big, but
3778  * obviously that doesn't help for a bucket that contains many duplicates of
3779  * the same value.
3780  */
3781 void
3782 estimate_hash_bucket_stats(PlannerInfo *root, Node *hashkey, double nbuckets,
3783  Selectivity *mcv_freq,
3784  Selectivity *bucketsize_frac)
3785 {
3786  VariableStatData vardata;
3787  double estfract,
3788  ndistinct,
3789  stanullfrac,
3790  avgfreq;
3791  bool isdefault;
3792  AttStatsSlot sslot;
3793 
3794  examine_variable(root, hashkey, 0, &vardata);
3795 
3796  /* Look up the frequency of the most common value, if available */
3797  *mcv_freq = 0.0;
3798 
3799  if (HeapTupleIsValid(vardata.statsTuple))
3800  {
3801  if (get_attstatsslot(&sslot, vardata.statsTuple,
3802  STATISTIC_KIND_MCV, InvalidOid,
3804  {
3805  /*
3806  * The first MCV stat is for the most common value.
3807  */
3808  if (sslot.nnumbers > 0)
3809  *mcv_freq = sslot.numbers[0];
3810  free_attstatsslot(&sslot);
3811  }
3812  }
3813 
3814  /* Get number of distinct values */
3815  ndistinct = get_variable_numdistinct(&vardata, &isdefault);
3816 
3817  /*
3818  * If ndistinct isn't real, punt. We normally return 0.1, but if the
3819  * mcv_freq is known to be even higher than that, use it instead.
3820  */
3821  if (isdefault)
3822  {
3823  *bucketsize_frac = (Selectivity) Max(0.1, *mcv_freq);
3824  ReleaseVariableStats(vardata);
3825  return;
3826  }
3827 
3828  /* Get fraction that are null */
3829  if (HeapTupleIsValid(vardata.statsTuple))
3830  {
3831  Form_pg_statistic stats;
3832 
3833  stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
3834  stanullfrac = stats->stanullfrac;
3835  }
3836  else
3837  stanullfrac = 0.0;
3838 
3839  /* Compute avg freq of all distinct data values in raw relation */
3840  avgfreq = (1.0 - stanullfrac) / ndistinct;
3841 
3842  /*
3843  * Adjust ndistinct to account for restriction clauses. Observe we are
3844  * assuming that the data distribution is affected uniformly by the
3845  * restriction clauses!
3846  *
3847  * XXX Possibly better way, but much more expensive: multiply by
3848  * selectivity of rel's restriction clauses that mention the target Var.
3849  */
3850  if (vardata.rel && vardata.rel->tuples > 0)
3851  {
3852  ndistinct *= vardata.rel->rows / vardata.rel->tuples;
3853  ndistinct = clamp_row_est(ndistinct);
3854  }
3855 
3856  /*
3857  * Initial estimate of bucketsize fraction is 1/nbuckets as long as the
3858  * number of buckets is less than the expected number of distinct values;
3859  * otherwise it is 1/ndistinct.
3860  */
3861  if (ndistinct > nbuckets)
3862  estfract = 1.0 / nbuckets;
3863  else
3864  estfract = 1.0 / ndistinct;
3865 
3866  /*
3867  * Adjust estimated bucketsize upward to account for skewed distribution.
3868  */
3869  if (avgfreq > 0.0 && *mcv_freq > avgfreq)
3870  estfract *= *mcv_freq / avgfreq;
3871 
3872  /*
3873  * Clamp bucketsize to sane range (the above adjustment could easily
3874  * produce an out-of-range result). We set the lower bound a little above
3875  * zero, since zero isn't a very sane result.
3876  */
3877  if (estfract < 1.0e-6)
3878  estfract = 1.0e-6;
3879  else if (estfract > 1.0)
3880  estfract = 1.0;
3881 
3882  *bucketsize_frac = (Selectivity) estfract;
3883 
3884  ReleaseVariableStats(vardata);
3885 }
3886 
3887 
3888 /*-------------------------------------------------------------------------
3889  *
3890  * Support routines
3891  *
3892  *-------------------------------------------------------------------------
3893  */
3894 
3895 /*
3896  * Find applicable ndistinct statistics for the given list of VarInfos (which
3897  * must all belong to the given rel), and update *ndistinct to the estimate of
3898  * the MVNDistinctItem that best matches. If a match it found, *varinfos is
3899  * updated to remove the list of matched varinfos.
3900  *
3901  * Varinfos that aren't for simple Vars are ignored.
3902  *
3903  * Return true if we're able to find a match, false otherwise.
3904  */
3905 static bool
3907  List **varinfos, double *ndistinct)
3908 {
3909  ListCell *lc;
3910  Bitmapset *attnums = NULL;
3911  int nmatches;
3912  Oid statOid = InvalidOid;
3913  MVNDistinct *stats;
3914  Bitmapset *matched = NULL;
3915 
3916  /* bail out immediately if the table has no extended statistics */
3917  if (!rel->statlist)
3918  return false;
3919 
3920  /* Determine the attnums we're looking for */
3921  foreach(lc, *varinfos)
3922  {
3923  GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc);
3924 
3925  Assert(varinfo->rel == rel);
3926 
3927  if (IsA(varinfo->var, Var))
3928  {
3929  attnums = bms_add_member(attnums,
3930  ((Var *) varinfo->var)->varattno);
3931  }
3932  }
3933 
3934  /* look for the ndistinct statistics matching the most vars */
3935  nmatches = 1; /* we require at least two matches */
3936  foreach(lc, rel->statlist)
3937  {
3938  StatisticExtInfo *info = (StatisticExtInfo *) lfirst(lc);
3939  Bitmapset *shared;
3940  int nshared;
3941 
3942  /* skip statistics of other kinds */
3943  if (info->kind != STATS_EXT_NDISTINCT)
3944  continue;
3945 
3946  /* compute attnums shared by the vars and the statistics object */
3947  shared = bms_intersect(info->keys, attnums);
3948  nshared = bms_num_members(shared);
3949 
3950  /*
3951  * Does this statistics object match more columns than the currently
3952  * best object? If so, use this one instead.
3953  *
3954  * XXX This should break ties using name of the object, or something
3955  * like that, to make the outcome stable.
3956  */
3957  if (nshared > nmatches)
3958  {
3959  statOid = info->statOid;
3960  nmatches = nshared;
3961  matched = shared;
3962  }
3963  }
3964 
3965  /* No match? */
3966  if (statOid == InvalidOid)
3967  return false;
3968  Assert(nmatches > 1 && matched != NULL);
3969 
3970  stats = statext_ndistinct_load(statOid);
3971 
3972  /*
3973  * If we have a match, search it for the specific item that matches (there
3974  * must be one), and construct the output values.
3975  */
3976  if (stats)
3977  {
3978  int i;
3979  List *newlist = NIL;
3980  MVNDistinctItem *item = NULL;
3981 
3982  /* Find the specific item that exactly matches the combination */
3983  for (i = 0; i < stats->nitems; i++)
3984  {
3985  MVNDistinctItem *tmpitem = &stats->items[i];
3986 
3987  if (bms_subset_compare(tmpitem->attrs, matched) == BMS_EQUAL)
3988  {
3989  item = tmpitem;
3990  break;
3991  }
3992  }
3993 
3994  /* make sure we found an item */
3995  if (!item)
3996  elog(ERROR, "corrupt MVNDistinct entry");
3997 
3998  /* Form the output varinfo list, keeping only unmatched ones */
3999  foreach(lc, *varinfos)
4000  {
4001  GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc);
4003 
4004  if (!IsA(varinfo->var, Var))
4005  {
4006  newlist = lappend(newlist, varinfo);
4007  continue;
4008  }
4009 
4010  attnum = ((Var *) varinfo->var)->varattno;
4011  if (!bms_is_member(attnum, matched))
4012  newlist = lappend(newlist, varinfo);
4013  }
4014 
4015  *varinfos = newlist;
4016  *ndistinct = item->ndistinct;
4017  return true;
4018  }
4019 
4020  return false;
4021 }
4022 
4023 /*
4024  * convert_to_scalar
4025  * Convert non-NULL values of the indicated types to the comparison
4026  * scale needed by scalarineqsel().
4027  * Returns "true" if successful.
4028  *
4029  * XXX this routine is a hack: ideally we should look up the conversion
4030  * subroutines in pg_type.
4031  *
4032  * All numeric datatypes are simply converted to their equivalent
4033  * "double" values. (NUMERIC values that are outside the range of "double"
4034  * are clamped to +/- HUGE_VAL.)
4035  *
4036  * String datatypes are converted by convert_string_to_scalar(),
4037  * which is explained below. The reason why this routine deals with
4038  * three values at a time, not just one, is that we need it for strings.
4039  *
4040  * The bytea datatype is just enough different from strings that it has
4041  * to be treated separately.
4042  *
4043  * The several datatypes representing absolute times are all converted
4044  * to Timestamp, which is actually a double, and then we just use that
4045  * double value. Note this will give correct results even for the "special"
4046  * values of Timestamp, since those are chosen to compare correctly;
4047  * see timestamp_cmp.
4048  *
4049  * The several datatypes representing relative times (intervals) are all
4050  * converted to measurements expressed in seconds.
4051  */
4052 static bool
4053 convert_to_scalar(Datum value, Oid valuetypid, double *scaledvalue,
4054  Datum lobound, Datum hibound, Oid boundstypid,
4055  double *scaledlobound, double *scaledhibound)
4056 {
4057  bool failure = false;
4058 
4059  /*
4060  * Both the valuetypid and the boundstypid should exactly match the
4061  * declared input type(s) of the operator we are invoked for. However,
4062  * extensions might try to use scalarineqsel as estimator for operators
4063  * with input type(s) we don't handle here; in such cases, we want to
4064  * return false, not fail. In any case, we mustn't assume that valuetypid
4065  * and boundstypid are identical.
4066  *
4067  * XXX The histogram we are interpolating between points of could belong
4068  * to a column that's only binary-compatible with the declared type. In
4069  * essence we are assuming that the semantics of binary-compatible types
4070  * are enough alike that we can use a histogram generated with one type's
4071  * operators to estimate selectivity for the other's. This is outright
4072  * wrong in some cases --- in particular signed versus unsigned
4073  * interpretation could trip us up. But it's useful enough in the
4074  * majority of cases that we do it anyway. Should think about more
4075  * rigorous ways to do it.
4076  */
4077  switch (valuetypid)
4078  {
4079  /*
4080  * Built-in numeric types
4081  */
4082  case BOOLOID:
4083  case INT2OID:
4084  case INT4OID:
4085  case INT8OID:
4086  case FLOAT4OID:
4087  case FLOAT8OID:
4088  case NUMERICOID:
4089  case OIDOID:
4090  case REGPROCOID:
4091  case REGPROCEDUREOID:
4092  case REGOPEROID:
4093  case REGOPERATOROID:
4094  case REGCLASSOID:
4095  case REGTYPEOID:
4096  case REGCONFIGOID:
4097  case REGDICTIONARYOID:
4098  case REGROLEOID:
4099  case REGNAMESPACEOID:
4100  *scaledvalue = convert_numeric_to_scalar(value, valuetypid,
4101  &failure);
4102  *scaledlobound = convert_numeric_to_scalar(lobound, boundstypid,
4103  &failure);
4104  *scaledhibound = convert_numeric_to_scalar(hibound, boundstypid,
4105  &failure);
4106  return !failure;
4107 
4108  /*
4109  * Built-in string types
4110  */
4111  case CHAROID:
4112  case BPCHAROID:
4113  case VARCHAROID:
4114  case TEXTOID:
4115  case NAMEOID:
4116  {
4117  char *valstr = convert_string_datum(value, valuetypid,
4118  &failure);
4119  char *lostr = convert_string_datum(lobound, boundstypid,
4120  &failure);
4121  char *histr = convert_string_datum(hibound, boundstypid,
4122  &failure);
4123 
4124  /*
4125  * Bail out if any of the values is not of string type. We
4126  * might leak converted strings for the other value(s), but
4127  * that's not worth troubling over.
4128  */
4129  if (failure)
4130  return false;
4131 
4132  convert_string_to_scalar(valstr, scaledvalue,
4133  lostr, scaledlobound,
4134  histr, scaledhibound);
4135  pfree(valstr);
4136  pfree(lostr);
4137  pfree(histr);
4138  return true;
4139  }
4140 
4141  /*
4142  * Built-in bytea type
4143  */
4144  case BYTEAOID:
4145  {
4146  /* We only support bytea vs bytea comparison */
4147  if (boundstypid != BYTEAOID)
4148  return false;
4149  convert_bytea_to_scalar(value, scaledvalue,
4150  lobound, scaledlobound,
4151  hibound, scaledhibound);
4152  return true;
4153  }
4154 
4155  /*
4156  * Built-in time types
4157  */
4158  case TIMESTAMPOID:
4159  case TIMESTAMPTZOID:
4160  case ABSTIMEOID:
4161  case DATEOID:
4162  case INTERVALOID:
4163  case RELTIMEOID:
4164  case TINTERVALOID:
4165  case TIMEOID:
4166  case TIMETZOID:
4167  *scaledvalue = convert_timevalue_to_scalar(value, valuetypid,
4168  &failure);
4169  *scaledlobound = convert_timevalue_to_scalar(lobound, boundstypid,
4170  &failure);
4171  *scaledhibound = convert_timevalue_to_scalar(hibound, boundstypid,
4172  &failure);
4173  return !failure;
4174 
4175  /*
4176  * Built-in network types
4177  */
4178  case INETOID:
4179  case CIDROID:
4180  case MACADDROID:
4181  case MACADDR8OID:
4182  *scaledvalue = convert_network_to_scalar(value, valuetypid,
4183  &failure);
4184  *scaledlobound = convert_network_to_scalar(lobound, boundstypid,
4185  &failure);
4186  *scaledhibound = convert_network_to_scalar(hibound, boundstypid,
4187  &failure);
4188  return !failure;
4189  }
4190  /* Don't know how to convert */
4191  *scaledvalue = *scaledlobound = *scaledhibound = 0;
4192  return false;
4193 }
4194 
4195 /*
4196  * Do convert_to_scalar()'s work for any numeric data type.
4197  *
4198  * On failure (e.g., unsupported typid), set *failure to true;
4199  * otherwise, that variable is not changed.
4200  */
4201 static double
4203 {
4204  switch (typid)
4205  {
4206  case BOOLOID:
4207  return (double) DatumGetBool(value);
4208  case INT2OID:
4209  return (double) DatumGetInt16(value);
4210  case INT4OID:
4211  return (double) DatumGetInt32(value);
4212  case INT8OID:
4213  return (double) DatumGetInt64(value);
4214  case FLOAT4OID:
4215  return (double) DatumGetFloat4(value);
4216  case FLOAT8OID:
4217  return (double) DatumGetFloat8(value);
4218  case NUMERICOID:
4219  /* Note: out-of-range values will be clamped to +-HUGE_VAL */
4220  return (double)
4222  value));
4223  case OIDOID:
4224  case REGPROCOID:
4225  case REGPROCEDUREOID:
4226  case REGOPEROID:
4227  case REGOPERATOROID:
4228  case REGCLASSOID:
4229  case REGTYPEOID:
4230  case REGCONFIGOID:
4231  case REGDICTIONARYOID:
4232  case REGROLEOID:
4233  case REGNAMESPACEOID:
4234  /* we can treat OIDs as integers... */
4235  return (double) DatumGetObjectId(value);
4236  }
4237 
4238  *failure = true;
4239  return 0;
4240 }
4241 
4242 /*
4243  * Do convert_to_scalar()'s work for any character-string data type.
4244  *
4245  * String datatypes are converted to a scale that ranges from 0 to 1,
4246  * where we visualize the bytes of the string as fractional digits.
4247  *
4248  * We do not want the base to be 256, however, since that tends to
4249  * generate inflated selectivity estimates; few databases will have
4250  * occurrences of all 256 possible byte values at each position.
4251  * Instead, use the smallest and largest byte values seen in the bounds
4252  * as the estimated range for each byte, after some fudging to deal with
4253  * the fact that we probably aren't going to see the full range that way.
4254  *
4255  * An additional refinement is that we discard any common prefix of the
4256  * three strings before computing the scaled values. This allows us to
4257  * "zoom in" when we encounter a narrow data range. An example is a phone
4258  * number database where all the values begin with the same area code.
4259  * (Actually, the bounds will be adjacent histogram-bin-boundary values,
4260  * so this is more likely to happen than you might think.)
4261  */
4262 static void
4264  double *scaledvalue,
4265  char *lobound,
4266  double *scaledlobound,
4267  char *hibound,
4268  double *scaledhibound)
4269 {
4270  int rangelo,
4271  rangehi;
4272  char *sptr;
4273 
4274  rangelo = rangehi = (unsigned char) hibound[0];
4275  for (sptr = lobound; *sptr; sptr++)
4276  {
4277  if (rangelo > (unsigned char) *sptr)
4278  rangelo = (unsigned char) *sptr;
4279  if (rangehi < (unsigned char) *sptr)
4280  rangehi = (unsigned char) *sptr;
4281  }
4282  for (sptr = hibound; *sptr; sptr++)
4283  {
4284  if (rangelo > (unsigned char) *sptr)
4285  rangelo = (unsigned char) *sptr;
4286  if (rangehi < (unsigned char) *sptr)
4287  rangehi = (unsigned char) *sptr;
4288  }
4289  /* If range includes any upper-case ASCII chars, make it include all */
4290  if (rangelo <= 'Z' && rangehi >= 'A')
4291  {
4292  if (rangelo > 'A')
4293  rangelo = 'A';
4294  if (rangehi < 'Z')
4295  rangehi = 'Z';
4296  }
4297  /* Ditto lower-case */
4298  if (rangelo <= 'z' && rangehi >= 'a')
4299  {
4300  if (rangelo > 'a')
4301  rangelo = 'a';
4302  if (rangehi < 'z')
4303  rangehi = 'z';
4304  }
4305  /* Ditto digits */
4306  if (rangelo <= '9' && rangehi >= '0')
4307  {
4308  if (rangelo > '0')
4309  rangelo = '0';
4310  if (rangehi < '9')
4311  rangehi = '9';
4312  }
4313 
4314  /*
4315  * If range includes less than 10 chars, assume we have not got enough
4316  * data, and make it include regular ASCII set.
4317  */
4318  if (rangehi - rangelo < 9)
4319  {
4320  rangelo = ' ';
4321  rangehi = 127;
4322  }
4323 
4324  /*
4325  * Now strip any common prefix of the three strings.
4326  */
4327  while (*lobound)
4328  {
4329  if (*lobound != *hibound || *lobound != *value)
4330  break;
4331  lobound++, hibound++, value++;
4332  }
4333 
4334  /*
4335  * Now we can do the conversions.
4336  */
4337  *scaledvalue = convert_one_string_to_scalar(value, rangelo, rangehi);
4338  *scaledlobound = convert_one_string_to_scalar(lobound, rangelo, rangehi);
4339  *scaledhibound = convert_one_string_to_scalar(hibound, rangelo, rangehi);
4340 }
4341 
4342 static double
4343 convert_one_string_to_scalar(char *value, int rangelo, int rangehi)
4344 {
4345  int slen = strlen(value);
4346  double num,
4347  denom,
4348  base;
4349 
4350  if (slen <= 0)
4351  return 0.0; /* empty string has scalar value 0 */
4352 
4353  /*
4354  * There seems little point in considering more than a dozen bytes from
4355  * the string. Since base is at least 10, that will give us nominal
4356  * resolution of at least 12 decimal digits, which is surely far more
4357  * precision than this estimation technique has got anyway (especially in
4358  * non-C locales). Also, even with the maximum possible base of 256, this
4359  * ensures denom cannot grow larger than 256^13 = 2.03e31, which will not
4360  * overflow on any known machine.
4361  */
4362  if (slen > 12)
4363  slen = 12;
4364 
4365  /* Convert initial characters to fraction */
4366  base = rangehi - rangelo + 1;
4367  num = 0.0;
4368  denom = base;
4369  while (slen-- > 0)
4370  {
4371  int ch = (unsigned char) *value++;
4372 
4373  if (ch < rangelo)
4374  ch = rangelo - 1;
4375  else if (ch > rangehi)
4376  ch = rangehi + 1;
4377  num += ((double) (ch - rangelo)) / denom;
4378  denom *= base;
4379  }
4380 
4381  return num;
4382 }
4383 
4384 /*
4385  * Convert a string-type Datum into a palloc'd, null-terminated string.
4386  *
4387  * On failure (e.g., unsupported typid), set *failure to true;
4388  * otherwise, that variable is not changed. (We'll return NULL on failure.)
4389  *
4390  * When using a non-C locale, we must pass the string through strxfrm()
4391  * before continuing, so as to generate correct locale-specific results.
4392  */
4393 static char *
4394 convert_string_datum(Datum value, Oid typid, bool *failure)
4395 {
4396  char *val;
4397 
4398  switch (typid)
4399  {
4400  case CHAROID:
4401  val = (char *) palloc(2);
4402  val[0] = DatumGetChar(value);
4403  val[1] = '\0';
4404  break;
4405  case BPCHAROID:
4406  case VARCHAROID:
4407  case TEXTOID:
4408  val = TextDatumGetCString(value);
4409  break;
4410  case NAMEOID:
4411  {
4412  NameData *nm = (NameData *) DatumGetPointer(value);
4413 
4414  val = pstrdup(NameStr(*nm));
4415  break;
4416  }
4417  default:
4418  *failure = true;
4419  return NULL;
4420  }
4421 
4422  if (!lc_collate_is_c(DEFAULT_COLLATION_OID))
4423  {
4424  char *xfrmstr;
4425  size_t xfrmlen;
4426  size_t xfrmlen2 PG_USED_FOR_ASSERTS_ONLY;
4427 
4428  /*
4429  * XXX: We could guess at a suitable output buffer size and only call
4430  * strxfrm twice if our guess is too small.
4431  *
4432  * XXX: strxfrm doesn't support UTF-8 encoding on Win32, it can return
4433  * bogus data or set an error. This is not really a problem unless it
4434  * crashes since it will only give an estimation error and nothing
4435  * fatal.
4436  */
4437 #if _MSC_VER == 1400 /* VS.Net 2005 */
4438 
4439  /*
4440  *
4441  * http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=99694
4442  */
4443  {
4444  char x[1];
4445 
4446  xfrmlen = strxfrm(x, val, 0);
4447  }
4448 #else
4449  xfrmlen = strxfrm(NULL, val, 0);
4450 #endif
4451 #ifdef WIN32
4452 
4453  /*
4454  * On Windows, strxfrm returns INT_MAX when an error occurs. Instead
4455  * of trying to allocate this much memory (and fail), just return the
4456  * original string unmodified as if we were in the C locale.
4457  */
4458  if (xfrmlen == INT_MAX)
4459  return val;
4460 #endif
4461  xfrmstr = (char *) palloc(xfrmlen + 1);
4462  xfrmlen2 = strxfrm(xfrmstr, val, xfrmlen + 1);
4463 
4464  /*
4465  * Some systems (e.g., glibc) can return a smaller value from the
4466  * second call than the first; thus the Assert must be <= not ==.
4467  */
4468  Assert(xfrmlen2 <= xfrmlen);
4469  pfree(val);
4470  val = xfrmstr;
4471  }
4472 
4473  return val;
4474 }
4475 
4476 /*
4477  * Do convert_to_scalar()'s work for any bytea data type.
4478  *
4479  * Very similar to convert_string_to_scalar except we can't assume
4480  * null-termination and therefore pass explicit lengths around.
4481  *
4482  * Also, assumptions about likely "normal" ranges of characters have been
4483  * removed - a data range of 0..255 is always used, for now. (Perhaps
4484  * someday we will add information about actual byte data range to
4485  * pg_statistic.)
4486  */
4487 static void
4489  double *scaledvalue,
4490  Datum lobound,
4491  double *scaledlobound,
4492  Datum hibound,
4493  double *scaledhibound)
4494 {
4495  bytea *valuep = DatumGetByteaPP(value);
4496  bytea *loboundp = DatumGetByteaPP(lobound);
4497  bytea *hiboundp = DatumGetByteaPP(hibound);
4498  int rangelo,
4499  rangehi,
4500  valuelen = VARSIZE_ANY_EXHDR(valuep),
4501  loboundlen = VARSIZE_ANY_EXHDR(loboundp),
4502  hiboundlen = VARSIZE_ANY_EXHDR(hiboundp),
4503  i,
4504  minlen;
4505  unsigned char *valstr = (unsigned char *) VARDATA_ANY(valuep);
4506  unsigned char *lostr = (unsigned char *) VARDATA_ANY(loboundp);
4507  unsigned char *histr = (unsigned char *) VARDATA_ANY(hiboundp);
4508 
4509  /*
4510  * Assume bytea data is uniformly distributed across all byte values.
4511  */
4512  rangelo = 0;
4513  rangehi = 255;
4514 
4515  /*
4516  * Now strip any common prefix of the three strings.
4517  */
4518  minlen = Min(Min(valuelen, loboundlen), hiboundlen);
4519  for (i = 0; i < minlen; i++)
4520  {
4521  if (*lostr != *histr || *lostr != *valstr)
4522  break;
4523  lostr++, histr++, valstr++;
4524  loboundlen--, hiboundlen--, valuelen--;
4525  }
4526 
4527  /*
4528  * Now we can do the conversions.
4529  */
4530  *scaledvalue = convert_one_bytea_to_scalar(valstr, valuelen, rangelo, rangehi);
4531  *scaledlobound = convert_one_bytea_to_scalar(lostr, loboundlen, rangelo, rangehi);
4532  *scaledhibound = convert_one_bytea_to_scalar(histr, hiboundlen, rangelo, rangehi);
4533 }
4534 
4535 static double
4536 convert_one_bytea_to_scalar(unsigned char *value, int valuelen,
4537  int rangelo, int rangehi)
4538 {
4539  double num,
4540  denom,
4541  base;
4542 
4543  if (valuelen <= 0)
4544  return 0.0; /* empty string has scalar value 0 */
4545 
4546  /*
4547  * Since base is 256, need not consider more than about 10 chars (even
4548  * this many seems like overkill)
4549  */
4550  if (valuelen > 10)
4551  valuelen = 10;
4552 
4553  /* Convert initial characters to fraction */
4554  base = rangehi - rangelo + 1;
4555  num = 0.0;
4556  denom = base;
4557  while (valuelen-- > 0)
4558  {
4559  int ch = *value++;
4560 
4561  if (ch < rangelo)
4562  ch = rangelo - 1;
4563  else if (ch > rangehi)
4564  ch = rangehi + 1;
4565  num += ((double) (ch - rangelo)) / denom;
4566  denom *= base;
4567  }
4568 
4569  return num;
4570 }
4571 
4572 /*
4573  * Do convert_to_scalar()'s work for any timevalue data type.
4574  *
4575  * On failure (e.g., unsupported typid), set *failure to true;
4576  * otherwise, that variable is not changed.
4577  */
4578 static double
4580 {
4581  switch (typid)
4582  {
4583  case TIMESTAMPOID:
4584  return DatumGetTimestamp(value);
4585  case TIMESTAMPTZOID:
4586  return DatumGetTimestampTz(value);
4587  case ABSTIMEOID:
4589  value));
4590  case DATEOID:
4592  case INTERVALOID:
4593  {
4595 
4596  /*
4597  * Convert the month part of Interval to days using assumed
4598  * average month length of 365.25/12.0 days. Not too
4599  * accurate, but plenty good enough for our purposes.
4600  */
4601  return interval->time + interval->day * (double) USECS_PER_DAY +
4602  interval->month * ((DAYS_PER_YEAR / (double) MONTHS_PER_YEAR) * USECS_PER_DAY);
4603  }
4604  case RELTIMEOID:
4605  return (DatumGetRelativeTime(value) * 1000000.0);
4606  case TINTERVALOID:
4607  {
4608  TimeInterval tinterval = DatumGetTimeInterval(value);
4609 
4610  if (tinterval->status != 0)
4611  return ((tinterval->data[1] - tinterval->data[0]) * 1000000.0);
4612  return 0; /* for lack of a better idea */
4613  }
4614  case TIMEOID:
4615  return DatumGetTimeADT(value);
4616  case TIMETZOID:
4617  {
4618  TimeTzADT *timetz = DatumGetTimeTzADTP(value);
4619 
4620  /* use GMT-equivalent time */
4621  return (double) (timetz->time + (timetz->zone * 1000000.0));
4622  }
4623  }
4624 
4625  *failure = true;
4626  return 0;
4627 }
4628 
4629 
4630 /*
4631  * get_restriction_variable
4632  * Examine the args of a restriction clause to see if it's of the
4633  * form (variable op pseudoconstant) or (pseudoconstant op variable),
4634  * where "variable" could be either a Var or an expression in vars of a
4635  * single relation. If so, extract information about the variable,
4636  * and also indicate which side it was on and the other argument.
4637  *
4638  * Inputs:
4639  * root: the planner info
4640  * args: clause argument list
4641  * varRelid: see specs for restriction selectivity functions
4642  *
4643  * Outputs: (these are valid only if true is returned)
4644  * *vardata: gets information about variable (see examine_variable)
4645  * *other: gets other clause argument, aggressively reduced to a constant
4646  * *varonleft: set true if variable is on the left, false if on the right
4647  *
4648  * Returns true if a variable is identified, otherwise false.
4649  *
4650  * Note: if there are Vars on both sides of the clause, we must fail, because
4651  * callers are expecting that the other side will act like a pseudoconstant.
4652  */
4653 bool
4655  VariableStatData *vardata, Node **other,
4656  bool *varonleft)
4657 {
4658  Node *left,
4659  *right;
4660  VariableStatData rdata;
4661 
4662  /* Fail if not a binary opclause (probably shouldn't happen) */
4663  if (list_length(args) != 2)
4664  return false;
4665 
4666  left = (Node *) linitial(args);
4667  right = (Node *) lsecond(args);
4668 
4669  /*
4670  * Examine both sides. Note that when varRelid is nonzero, Vars of other
4671  * relations will be treated as pseudoconstants.
4672  */
4673  examine_variable(root, left, varRelid, vardata);
4674  examine_variable(root, right, varRelid, &rdata);
4675 
4676  /*
4677  * If one side is a variable and the other not, we win.
4678  */
4679  if (vardata->rel && rdata.rel == NULL)
4680  {
4681  *varonleft = true;
4682  *other = estimate_expression_value(root, rdata.var);
4683  /* Assume we need no ReleaseVariableStats(rdata) here */
4684  return true;
4685  }
4686 
4687  if (vardata->rel == NULL && rdata.rel)
4688  {
4689  *varonleft = false;
4690  *other = estimate_expression_value(root, vardata->var);
4691  /* Assume we need no ReleaseVariableStats(*vardata) here */
4692  *vardata = rdata;
4693  return true;
4694  }
4695 
4696  /* Oops, clause has wrong structure (probably var op var) */
4697  ReleaseVariableStats(*vardata);
4698  ReleaseVariableStats(rdata);
4699 
4700  return false;
4701 }
4702 
4703 /*
4704  * get_join_variables
4705  * Apply examine_variable() to each side of a join clause.
4706  * Also, attempt to identify whether the join clause has the same
4707  * or reversed sense compared to the SpecialJoinInfo.
4708  *
4709  * We consider the join clause "normal" if it is "lhs_var OP rhs_var",
4710  * or "reversed" if it is "rhs_var OP lhs_var". In complicated cases
4711  * where we can't tell for sure, we default to assuming it's normal.
4712  */
4713 void
4715  VariableStatData *vardata1, VariableStatData *vardata2,
4716  bool *join_is_reversed)
4717 {
4718  Node *left,
4719  *right;
4720 
4721  if (list_length(args) != 2)
4722  elog(ERROR, "join operator should take two arguments");
4723 
4724  left = (Node *) linitial(args);
4725  right = (Node *) lsecond(args);
4726 
4727  examine_variable(root, left, 0, vardata1);
4728  examine_variable(root, right, 0, vardata2);
4729 
4730  if (vardata1->rel &&
4731  bms_is_subset(vardata1->rel->relids, sjinfo->syn_righthand))
4732  *join_is_reversed = true; /* var1 is on RHS */
4733  else if (vardata2->rel &&
4734  bms_is_subset(vardata2->rel->relids, sjinfo->syn_lefthand))
4735  *join_is_reversed = true; /* var2 is on LHS */
4736  else
4737  *join_is_reversed = false;
4738 }
4739 
4740 /*
4741  * examine_variable
4742  * Try to look up statistical data about an expression.
4743  * Fill in a VariableStatData struct to describe the expression.
4744  *
4745  * Inputs:
4746  * root: the planner info
4747  * node: the expression tree to examine
4748  * varRelid: see specs for restriction selectivity functions
4749  *
4750  * Outputs: *vardata is filled as follows:
4751  * var: the input expression (with any binary relabeling stripped, if
4752  * it is or contains a variable; but otherwise the type is preserved)
4753  * rel: RelOptInfo for relation containing variable; NULL if expression
4754  * contains no Vars (NOTE this could point to a RelOptInfo of a
4755  * subquery, not one in the current query).
4756  * statsTuple: the pg_statistic entry for the variable, if one exists;
4757  * otherwise NULL.
4758  * freefunc: pointer to a function to release statsTuple with.
4759  * vartype: exposed type of the expression; this should always match
4760  * the declared input type of the operator we are estimating for.
4761  * atttype, atttypmod: actual type/typmod of the "var" expression. This is
4762  * commonly the same as the exposed type of the variable argument,
4763  * but can be different in binary-compatible-type cases.
4764  * isunique: true if we were able to match the var to a unique index or a
4765  * single-column DISTINCT clause, implying its values are unique for
4766  * this query. (Caution: this should be trusted for statistical
4767  * purposes only, since we do not check indimmediate nor verify that
4768  * the exact same definition of equality applies.)
4769  * acl_ok: true if current user has permission to read the column(s)
4770  * underlying the pg_statistic entry. This is consulted by
4771  * statistic_proc_security_check().
4772  *
4773  * Caller is responsible for doing ReleaseVariableStats() before exiting.
4774  */
4775 void
4776 examine_variable(PlannerInfo *root, Node *node, int varRelid,
4777  VariableStatData *vardata)
4778 {
4779  Node *basenode;
4780  Relids varnos;
4781  RelOptInfo *onerel;
4782 
4783  /* Make sure we don't return dangling pointers in vardata */
4784  MemSet(vardata, 0, sizeof(VariableStatData));
4785 
4786  /* Save the exposed type of the expression */
4787  vardata->vartype = exprType(node);
4788 
4789  /* Look inside any binary-compatible relabeling */
4790 
4791  if (IsA(node, RelabelType))
4792  basenode = (Node *) ((RelabelType *) node)->arg;
4793  else
4794  basenode = node;
4795 
4796  /* Fast path for a simple Var */
4797 
4798  if (IsA(basenode, Var) &&
4799  (varRelid == 0 || varRelid == ((Var *) basenode)->varno))
4800  {
4801  Var *var = (Var *) basenode;
4802 
4803  /* Set up result fields other than the stats tuple */
4804  vardata->var = basenode; /* return Var without relabeling */
4805  vardata->rel = find_base_rel(root, var->varno);
4806  vardata->atttype = var->vartype;
4807  vardata->atttypmod = var->vartypmod;
4808  vardata->isunique = has_unique_index(vardata->rel, var->varattno);
4809 
4810  /* Try to locate some stats */
4811  examine_simple_variable(root, var, vardata);
4812 
4813  return;
4814  }
4815 
4816  /*
4817  * Okay, it's a more complicated expression. Determine variable
4818  * membership. Note that when varRelid isn't zero, only vars of that
4819  * relation are considered "real" vars.
4820  */
4821  varnos = pull_varnos(basenode);
4822 
4823  onerel = NULL;
4824 
4825  switch (bms_membership(varnos))
4826  {
4827  case BMS_EMPTY_SET:
4828  /* No Vars at all ... must be pseudo-constant clause */
4829  break;
4830  case BMS_SINGLETON:
4831  if (varRelid == 0 || bms_is_member(varRelid, varnos))
4832  {
4833  onerel = find_base_rel(root,
4834  (varRelid ? varRelid : bms_singleton_member(varnos)));
4835  vardata->rel = onerel;
4836  node = basenode; /* strip any relabeling */
4837  }
4838  /* else treat it as a constant */
4839  break;
4840  case BMS_MULTIPLE:
4841  if (varRelid == 0)
4842  {
4843  /* treat it as a variable of a join relation */
4844  vardata->rel = find_join_rel(root, varnos);
4845  node = basenode; /* strip any relabeling */
4846  }
4847  else if (bms_is_member(varRelid, varnos))
4848  {
4849  /* ignore the vars belonging to other relations */
4850  vardata->rel = find_base_rel(root, varRelid);
4851  node = basenode; /* strip any relabeling */
4852  /* note: no point in expressional-index search here */
4853  }
4854  /* else treat it as a constant */
4855  break;
4856  }
4857 
4858  bms_free(varnos);
4859 
4860  vardata->var = node;
4861  vardata->atttype = exprType(node);
4862  vardata->atttypmod = exprTypmod(node);
4863 
4864  if (onerel)
4865  {
4866  /*
4867  * We have an expression in vars of a single relation. Try to match
4868  * it to expressional index columns, in hopes of finding some
4869  * statistics.
4870  *
4871  * XXX it's conceivable that there are multiple matches with different
4872  * index opfamilies; if so, we need to pick one that matches the
4873  * operator we are estimating for. FIXME later.
4874  */
4875  ListCell *ilist;
4876 
4877  foreach(ilist, onerel->indexlist)
4878  {
4879  IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
4880  ListCell *indexpr_item;
4881  int pos;
4882 
4883  indexpr_item = list_head(index->indexprs);
4884  if (indexpr_item == NULL)
4885  continue; /* no expressions here... */
4886 
4887  for (pos = 0; pos < index->ncolumns; pos++)
4888  {
4889  if (index->indexkeys[pos] == 0)
4890  {
4891  Node *indexkey;
4892 
4893  if (indexpr_item == NULL)
4894  elog(ERROR, "too few entries in indexprs list");
4895  indexkey = (Node *) lfirst(indexpr_item);
4896  if (indexkey && IsA(indexkey, RelabelType))
4897  indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4898  if (equal(node, indexkey))
4899  {
4900  /*
4901  * Found a match ... is it a unique index? Tests here
4902  * should match has_unique_index().
4903  */
4904  if (index->unique &&
4905  index->nkeycolumns == 1 &&
4906  (index->indpred == NIL || index->predOK))
4907  vardata->isunique = true;
4908 
4909  /*
4910  * Has it got stats? We only consider stats for
4911  * non-partial indexes, since partial indexes probably
4912  * don't reflect whole-relation statistics; the above
4913  * check for uniqueness is the only info we take from
4914  * a partial index.
4915  *
4916  * An index stats hook, however, must make its own
4917  * decisions about what to do with partial indexes.
4918  */
4919  if (get_index_stats_hook &&
4920  (*get_index_stats_hook) (root, index->indexoid,
4921  pos + 1, vardata))
4922  {
4923  /*
4924  * The hook took control of acquiring a stats
4925  * tuple. If it did supply a tuple, it'd better
4926  * have supplied a freefunc.
4927  */
4928  if (HeapTupleIsValid(vardata->statsTuple) &&
4929  !vardata->freefunc)
4930  elog(ERROR, "no function provided to release variable stats with");
4931  }
4932  else if (index->indpred == NIL)
4933  {
4934  vardata->statsTuple =
4936  ObjectIdGetDatum(index->indexoid),
4937  Int16GetDatum(pos + 1),
4938  BoolGetDatum(false));
4939  vardata->freefunc = ReleaseSysCache;
4940 
4941  if (HeapTupleIsValid(vardata->statsTuple))
4942  {
4943  /* Get index's table for permission check */
4944  RangeTblEntry *rte;
4945 
4946  rte = planner_rt_fetch(index->rel->relid, root);
4947  Assert(rte->rtekind == RTE_RELATION);
4948 
4949  /*
4950  * For simplicity, we insist on the whole
4951  * table being selectable, rather than trying
4952  * to identify which column(s) the index
4953  * depends on.
4954  */
4955  vardata->acl_ok =
4957  ACL_SELECT) == ACLCHECK_OK);
4958  }
4959  else
4960  {
4961  /* suppress leakproofness checks later */
4962  vardata->acl_ok = true;
4963  }
4964  }
4965  if (vardata->statsTuple)
4966  break;
4967  }
4968  indexpr_item = lnext(indexpr_item);
4969  }
4970  }
4971  if (vardata->statsTuple)
4972  break;
4973  }
4974  }
4975 }
4976 
4977 /*
4978  * examine_simple_variable
4979  * Handle a simple Var for examine_variable
4980  *
4981  * This is split out as a subroutine so that we can recurse to deal with
4982  * Vars referencing subqueries.
4983  *
4984  * We already filled in all the fields of *vardata except for the stats tuple.
4985  */
4986 static void
4988  VariableStatData *vardata)
4989 {
4990  RangeTblEntry *rte = root->simple_rte_array[var->varno];
4991 
4992  Assert(IsA(rte, RangeTblEntry));
4993 
4995  (*get_relation_stats_hook) (root, rte, var->varattno, vardata))
4996  {
4997  /*
4998  * The hook took control of acquiring a stats tuple. If it did supply
4999  * a tuple, it'd better have supplied a freefunc.
5000  */
5001  if (HeapTupleIsValid(vardata->statsTuple) &&
5002  !vardata->freefunc)
5003  elog(ERROR, "no function provided to release variable stats with");
5004  }
5005  else if (rte->rtekind == RTE_RELATION)
5006  {
5007  /*
5008  * Plain table or parent of an inheritance appendrel, so look up the
5009  * column in pg_statistic
5010  */
5012  ObjectIdGetDatum(rte->relid),
5013  Int16GetDatum(var->varattno),
5014  BoolGetDatum(rte->inh));
5015  vardata->freefunc = ReleaseSysCache;
5016 
5017  if (HeapTupleIsValid(vardata->statsTuple))
5018  {
5019  /* check if user has permission to read this column */
5020  vardata->acl_ok =
5022  ACL_SELECT) == ACLCHECK_OK) ||
5024  ACL_SELECT) == ACLCHECK_OK);
5025  }
5026  else
5027  {
5028  /* suppress any possible leakproofness checks later */
5029  vardata->acl_ok = true;
5030  }
5031  }
5032  else if (rte->rtekind == RTE_SUBQUERY && !rte->inh)
5033  {
5034  /*
5035  * Plain subquery (not one that was converted to an appendrel).
5036  */
5037  Query *subquery = rte->subquery;
5038  RelOptInfo *rel;
5039  TargetEntry *ste;
5040 
5041  /*
5042  * Punt if it's a whole-row var rather than a plain column reference.
5043  */
5044  if (var->varattno == InvalidAttrNumber)
5045  return;
5046 
5047  /*
5048  * Punt if subquery uses set operations or GROUP BY, as these will
5049  * mash underlying columns' stats beyond recognition. (Set ops are
5050  * particularly nasty; if we forged ahead, we would return stats
5051  * relevant to only the leftmost subselect...) DISTINCT is also
5052  * problematic, but we check that later because there is a possibility
5053  * of learning something even with it.
5054  */
5055  if (subquery->setOperations ||
5056  subquery->groupClause)
5057  return;
5058 
5059  /*
5060  * OK, fetch RelOptInfo for subquery. Note that we don't change the
5061  * rel returned in vardata, since caller expects it to be a rel of the
5062  * caller's query level. Because we might already be recursing, we
5063  * can't use that rel pointer either, but have to look up the Var's
5064  * rel afresh.
5065  */
5066  rel = find_base_rel(root, var->varno);
5067 
5068  /* If the subquery hasn't been planned yet, we have to punt */
5069  if (rel->subroot == NULL)
5070  return;
5071  Assert(IsA(rel->subroot, PlannerInfo));
5072 
5073  /*
5074  * Switch our attention to the subquery as mangled by the planner. It
5075  * was okay to look at the pre-planning version for the tests above,
5076  * but now we need a Var that will refer to the subroot's live
5077  * RelOptInfos. For instance, if any subquery pullup happened during
5078  * planning, Vars in the targetlist might have gotten replaced, and we
5079  * need to see the replacement expressions.
5080  */
5081  subquery = rel->subroot->parse;
5082  Assert(IsA(subquery, Query));
5083 
5084  /* Get the subquery output expression referenced by the upper Var */
5085  ste = get_tle_by_resno(subquery->targetList, var->varattno);
5086  if (ste == NULL || ste->resjunk)
5087  elog(ERROR, "subquery %s does not have attribute %d",
5088  rte->eref->aliasname, var->varattno);
5089  var = (Var *) ste->expr;
5090 
5091  /*
5092  * If subquery uses DISTINCT, we can't make use of any stats for the
5093  * variable ... but, if it's the only DISTINCT column, we are entitled
5094  * to consider it unique. We do the test this way so that it works
5095  * for cases involving DISTINCT ON.
5096  */
5097  if (subquery->distinctClause)
5098  {
5099  if (list_length(subquery->distinctClause) == 1 &&
5100  targetIsInSortList(ste, InvalidOid, subquery->distinctClause))
5101  vardata->isunique = true;
5102  /* cannot go further */
5103  return;
5104  }
5105 
5106  /*
5107  * If the sub-query originated from a view with the security_barrier
5108  * attribute, we must not look at the variable's statistics, though it
5109  * seems all right to notice the existence of a DISTINCT clause. So
5110  * stop here.
5111  *
5112  * This is probably a harsher restriction than necessary; it's
5113  * certainly OK for the selectivity estimator (which is a C function,
5114  * and therefore omnipotent anyway) to look at the statistics. But
5115  * many selectivity estimators will happily *invoke the operator
5116  * function* to try to work out a good estimate - and that's not OK.
5117  * So for now, don't dig down for stats.
5118  */
5119  if (rte->security_barrier)
5120  return;
5121 
5122  /* Can only handle a simple Var of subquery's query level */
5123  if (var && IsA(var, Var) &&
5124  var->varlevelsup == 0)
5125  {
5126  /*
5127  * OK, recurse into the subquery. Note that the original setting
5128  * of vardata->isunique (which will surely be false) is left
5129  * unchanged in this situation. That's what we want, since even
5130  * if the underlying column is unique, the subquery may have
5131  * joined to other tables in a way that creates duplicates.
5132  */
5133  examine_simple_variable(rel->subroot, var, vardata);
5134  }
5135  }
5136  else
5137  {
5138  /*
5139  * Otherwise, the Var comes from a FUNCTION, VALUES, or CTE RTE. (We
5140  * won't see RTE_JOIN here because join alias Vars have already been
5141  * flattened.) There's not much we can do with function outputs, but
5142  * maybe someday try to be smarter about VALUES and/or CTEs.
5143  */
5144  }
5145 }
5146 
5147 /*
5148  * Check whether it is permitted to call func_oid passing some of the
5149  * pg_statistic data in vardata. We allow this either if the user has SELECT
5150  * privileges on the table or column underlying the pg_statistic data or if
5151  * the function is marked leak-proof.
5152  */
5153 bool
5155 {
5156  if (vardata->acl_ok)
5157  return true;
5158 
5159  if (!OidIsValid(func_oid))
5160  return false;
5161 
5162  if (get_func_leakproof(func_oid))
5163  return true;
5164 
5165  ereport(DEBUG2,
5166  (errmsg_internal("not using statistics because function \"%s\" is not leak-proof",
5167  get_func_name(func_oid))));
5168  return false;
5169 }
5170 
5171 /*
5172  * get_variable_numdistinct
5173  * Estimate the number of distinct values of a variable.
5174  *
5175  * vardata: results of examine_variable
5176  * *isdefault: set to true if the result is a default rather than based on
5177  * anything meaningful.
5178  *
5179  * NB: be careful to produce a positive integral result, since callers may
5180  * compare the result to exact integer counts, or might divide by it.
5181  */
5182 double
5183 get_variable_numdistinct(VariableStatData *vardata, bool *isdefault)
5184 {
5185  double stadistinct;
5186  double stanullfrac = 0.0;
5187  double ntuples;
5188 
5189  *isdefault = false;
5190 
5191  /*
5192  * Determine the stadistinct value to use. There are cases where we can
5193  * get an estimate even without a pg_statistic entry, or can get a better
5194  * value than is in pg_statistic. Grab stanullfrac too if we can find it
5195  * (otherwise, assume no nulls, for lack of any better idea).
5196  */
5197  if (HeapTupleIsValid(vardata->statsTuple))
5198  {
5199  /* Use the pg_statistic entry */
5200  Form_pg_statistic stats;
5201 
5202  stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
5203  stadistinct = stats->stadistinct;
5204  stanullfrac = stats->stanullfrac;
5205  }
5206  else if (vardata->vartype == BOOLOID)
5207  {
5208  /*
5209  * Special-case boolean columns: presumably, two distinct values.
5210  *
5211  * Are there any other datatypes we should wire in special estimates
5212  * for?
5213  */
5214  stadistinct = 2.0;
5215  }
5216  else if (vardata->rel && vardata->rel->rtekind == RTE_VALUES)
5217  {
5218  /*
5219  * If the Var represents a column of a VALUES RTE, assume it's unique.
5220  * This could of course be very wrong, but it should tend to be true
5221  * in well-written queries. We could consider examining the VALUES'
5222  * contents to get some real statistics; but that only works if the
5223  * entries are all constants, and it would be pretty expensive anyway.
5224  */
5225  stadistinct = -1.0; /* unique (and all non null) */
5226  }
5227  else
5228  {
5229  /*
5230  * We don't keep statistics for system columns, but in some cases we
5231  * can infer distinctness anyway.
5232  */
5233  if (vardata->var && IsA(vardata->var, Var))
5234  {
5235  switch (((Var *) vardata->var)->varattno)
5236  {
5239  stadistinct = -1.0; /* unique (and all non null) */
5240  break;
5242  stadistinct = 1.0; /* only 1 value */
5243  break;
5244  default:
5245  stadistinct = 0.0; /* means "unknown" */
5246  break;
5247  }
5248  }
5249  else
5250  stadistinct = 0.0; /* means "unknown" */
5251 
5252  /*
5253  * XXX consider using estimate_num_groups on expressions?
5254  */
5255  }
5256 
5257  /*
5258  * If there is a unique index or DISTINCT clause for the variable, assume
5259  * it is unique no matter what pg_statistic says; the statistics could be
5260  * out of date, or we might have found a partial unique index that proves
5261  * the var is unique for this query. However, we'd better still believe
5262  * the null-fraction statistic.
5263  */
5264  if (vardata->isunique)
5265  stadistinct = -1.0 * (1.0 - stanullfrac);
5266 
5267  /*
5268  * If we had an absolute estimate, use that.
5269  */
5270  if (stadistinct > 0.0)
5271  return clamp_row_est(stadistinct);
5272 
5273  /*
5274  * Otherwise we need to get the relation size; punt if not available.
5275  */
5276  if (vardata->rel == NULL)
5277  {
5278  *isdefault = true;
5279  return DEFAULT_NUM_DISTINCT;
5280  }
5281  ntuples = vardata->rel->tuples;
5282  if (ntuples <= 0.0)
5283  {
5284  *isdefault = true;
5285  return DEFAULT_NUM_DISTINCT;
5286  }
5287 
5288  /*
5289  * If we had a relative estimate, use that.
5290  */
5291  if (stadistinct < 0.0)
5292  return clamp_row_est(-stadistinct * ntuples);
5293 
5294  /*
5295  * With no data, estimate ndistinct = ntuples if the table is small, else
5296  * use default. We use DEFAULT_NUM_DISTINCT as the cutoff for "small" so
5297  * that the behavior isn't discontinuous.
5298  */
5299  if (ntuples < DEFAULT_NUM_DISTINCT)
5300  return clamp_row_est(ntuples);
5301 
5302  *isdefault = true;
5303  return DEFAULT_NUM_DISTINCT;
5304 }
5305 
5306 /*
5307  * get_variable_range
5308  * Estimate the minimum and maximum value of the specified variable.
5309  * If successful, store values in *min and *max, and return true.
5310  * If no data available, return false.
5311  *
5312  * sortop is the "<" comparison operator to use. This should generally
5313  * be "<" not ">", as only the former is likely to be found in pg_statistic.
5314  */
5315 static bool
5317  Datum *min, Datum *max)
5318 {
5319  Datum tmin = 0;
5320  Datum tmax = 0;
5321  bool have_data = false;
5322  int16 typLen;
5323  bool typByVal;
5324  Oid opfuncoid;
5325  AttStatsSlot sslot;
5326  int i;
5327 
5328  /*
5329  * XXX It's very tempting to try to use the actual column min and max, if
5330  * we can get them relatively-cheaply with an index probe. However, since
5331  * this function is called many times during join planning, that could
5332  * have unpleasant effects on planning speed. Need more investigation
5333  * before enabling this.
5334  */
5335 #ifdef NOT_USED
5336  if (get_actual_variable_range(root, vardata, sortop, min, max))
5337  return true;
5338 #endif
5339 
5340  if (!HeapTupleIsValid(vardata->statsTuple))
5341  {
5342  /* no stats available, so default result */
5343  return false;
5344  }
5345 
5346  /*
5347  * If we can't apply the sortop to the stats data, just fail. In
5348  * principle, if there's a histogram and no MCVs, we could return the
5349  * histogram endpoints without ever applying the sortop ... but it's
5350  * probably not worth trying, because whatever the caller wants to do with
5351  * the endpoints would likely fail the security check too.
5352  */
5353  if (!statistic_proc_security_check(vardata,
5354  (opfuncoid = get_opcode(sortop))))
5355  return false;
5356 
5357  get_typlenbyval(vardata->atttype, &typLen, &typByVal);
5358 
5359  /*
5360  * If there is a histogram, grab the first and last values.
5361  *
5362  * If there is a histogram that is sorted with some other operator than
5363  * the one we want, fail --- this suggests that there is data we can't
5364  * use.
5365  */
5366  if (get_attstatsslot(&sslot, vardata->statsTuple,
5367  STATISTIC_KIND_HISTOGRAM, sortop,
5369  {
5370  if (sslot.nvalues > 0)
5371  {
5372  tmin = datumCopy(sslot.values[0], typByVal, typLen);
5373  tmax = datumCopy(sslot.values[sslot.nvalues - 1], typByVal, typLen);
5374  have_data = true;
5375  }
5376  free_attstatsslot(&sslot);
5377  }
5378  else if (get_attstatsslot(&sslot, vardata->statsTuple,
5379  STATISTIC_KIND_HISTOGRAM, InvalidOid,
5380  0))
5381  {
5382  free_attstatsslot(&sslot);
5383  return false;
5384  }
5385 
5386  /*
5387  * If we have most-common-values info, look for extreme MCVs. This is
5388  * needed even if we also have a histogram, since the histogram excludes
5389  * the MCVs. However, usually the MCVs will not be the extreme values, so
5390  * avoid unnecessary data copying.
5391  */
5392  if (get_attstatsslot(&sslot, vardata->statsTuple,
5393  STATISTIC_KIND_MCV, InvalidOid,
5395  {
5396  bool tmin_is_mcv = false;
5397  bool tmax_is_mcv = false;
5398  FmgrInfo opproc;
5399 
5400  fmgr_info(opfuncoid, &opproc);
5401 
5402  for (i = 0; i < sslot.nvalues; i++)
5403  {
5404  if (!have_data)
5405  {
5406  tmin = tmax = sslot.values[i];
5407  tmin_is_mcv = tmax_is_mcv = have_data = true;
5408  continue;
5409  }
5410  if (DatumGetBool(FunctionCall2Coll(&opproc,
5411  DEFAULT_COLLATION_OID,
5412  sslot.values[i], tmin)))
5413  {
5414  tmin = sslot.values[i];
5415  tmin_is_mcv = true;
5416  }
5417  if (DatumGetBool(FunctionCall2Coll(&opproc,
5418  DEFAULT_COLLATION_OID,
5419  tmax, sslot.values[i])))
5420  {
5421  tmax = sslot.values[i];
5422  tmax_is_mcv = true;
5423  }
5424  }
5425  if (tmin_is_mcv)
5426  tmin = datumCopy(tmin, typByVal, typLen);
5427  if (tmax_is_mcv)
5428  tmax = datumCopy(tmax, typByVal, typLen);
5429  free_attstatsslot(&sslot);
5430  }
5431 
5432  *min = tmin;
5433  *max = tmax;
5434  return have_data;
5435 }
5436 
5437 
5438 /*
5439  * get_actual_variable_range
5440  * Attempt to identify the current *actual* minimum and/or maximum
5441  * of the specified variable, by looking for a suitable btree index
5442  * and fetching its low and/or high values.
5443  * If successful, store values in *min and *max, and return true.
5444  * (Either pointer can be NULL if that endpoint isn't needed.)
5445  * If no data available, return false.
5446  *
5447  * sortop is the "<" comparison operator to use.
5448  */
5449 static bool
5451  Oid sortop,
5452  Datum *min, Datum *max)
5453 {
5454  bool have_data = false;
5455  RelOptInfo *rel = vardata->rel;
5456  RangeTblEntry *rte;
5457  ListCell *lc;
5458 
5459  /* No hope if no relation or it doesn't have indexes */
5460  if (rel == NULL || rel->indexlist == NIL)
5461  return false;
5462  /* If it has indexes it must be a plain relation */
5463  rte = root->simple_rte_array[rel->relid];
5464  Assert(rte->rtekind == RTE_RELATION);
5465 
5466  /* Search through the indexes to see if any match our problem */
5467  foreach(lc, rel->indexlist)
5468  {
5470  ScanDirection indexscandir;
5471 
5472  /* Ignore non-btree indexes */
5473  if (index->relam != BTREE_AM_OID)
5474  continue;
5475 
5476  /*
5477  * Ignore partial indexes --- we only want stats that cover the entire
5478  * relation.
5479  */
5480  if (index->indpred != NIL)
5481  continue;
5482 
5483  /*
5484  * The index list might include hypothetical indexes inserted by a
5485  * get_relation_info hook --- don't try to access them.
5486  */
5487  if (index->hypothetical)
5488  continue;
5489 
5490  /*
5491  * The first index column must match the desired variable and sort
5492  * operator --- but we can use a descending-order index.
5493  */
5494  if (!match_index_to_operand(vardata->var, 0, index))
5495  continue;
5496  switch (get_op_opfamily_strategy(sortop, index->sortopfamily[0]))
5497  {
5498  case BTLessStrategyNumber:
5499  if (index->reverse_sort[0])
5500  indexscandir = BackwardScanDirection;
5501  else
5502  indexscandir = ForwardScanDirection;
5503  break;
5505  if (index->reverse_sort[0])
5506  indexscandir = ForwardScanDirection;
5507  else
5508  indexscandir = BackwardScanDirection;
5509  break;
5510  default:
5511  /* index doesn't match the sortop */
5512  continue;
5513  }
5514 
5515  /*
5516  * Found a suitable index to extract data from. We'll need an EState
5517  * and a bunch of other infrastructure.
5518  */
5519  {
5520  EState *estate;
5521  ExprContext *econtext;
5522  MemoryContext tmpcontext;
5523  MemoryContext oldcontext;
5524  Relation heapRel;
5525  Relation indexRel;
5526  IndexInfo *indexInfo;
5527  TupleTableSlot *slot;
5528  int16 typLen;
5529  bool typByVal;
5530  ScanKeyData scankeys[1];
5531  IndexScanDesc index_scan;
5532  HeapTuple tup;
5534  bool isnull[INDEX_MAX_KEYS];
5535  SnapshotData SnapshotNonVacuumable;
5536 
5537  estate = CreateExecutorState();
5538  econtext = GetPerTupleExprContext(estate);
5539  /* Make sure any cruft is generated in the econtext's memory */
5540  tmpcontext = econtext->ecxt_per_tuple_memory;
5541  oldcontext = MemoryContextSwitchTo(tmpcontext);
5542 
5543  /*
5544  * Open the table and index so we can read from them. We should
5545  * already have at least AccessShareLock on the table, but not
5546  * necessarily on the index.
5547  */
5548  heapRel = heap_open(rte->relid, NoLock);
5549  indexRel = index_open(index->indexoid, AccessShareLock);
5550 
5551  /* extract index key information from the index's pg_index info */
5552  indexInfo = BuildIndexInfo(indexRel);
5553 
5554  /* some other stuff */
5555  slot = MakeSingleTupleTableSlot(RelationGetDescr(heapRel));
5556  econtext->ecxt_scantuple = slot;
5557  get_typlenbyval(vardata->atttype, &typLen, &typByVal);
5558  InitNonVacuumableSnapshot(SnapshotNonVacuumable, RecentGlobalXmin);
5559 
5560  /* set up an IS NOT NULL scan key so that we ignore nulls */
5561  ScanKeyEntryInitialize(&scankeys[0],
5563  1, /* index col to scan */
5564  InvalidStrategy, /* no strategy */
5565  InvalidOid, /* no strategy subtype */
5566  InvalidOid, /* no collation */
5567  InvalidOid, /* no reg proc for this */
5568  (Datum) 0); /* constant */
5569 
5570  have_data = true;
5571 
5572  /* If min is requested ... */
5573  if (min)
5574  {
5575  /*
5576  * In principle, we should scan the index with our current
5577  * active snapshot, which is the best approximation we've got
5578  * to what the query will see when executed. But that won't
5579  * be exact if a new snap is taken before running the query,
5580  * and it can be very expensive if a lot of recently-dead or
5581  * uncommitted rows exist at the beginning or end of the index
5582  * (because we'll laboriously fetch each one and reject it).
5583  * Instead, we use SnapshotNonVacuumable. That will accept
5584  * recently-dead and uncommitted rows as well as normal
5585  * visible rows. On the other hand, it will reject known-dead
5586  * rows, and thus not give a bogus answer when the extreme
5587  * value has been deleted (unless the deletion was quite
5588  * recent); that case motivates not using SnapshotAny here.
5589  *
5590  * A crucial point here is that SnapshotNonVacuumable, with
5591  * RecentGlobalXmin as horizon, yields the inverse of the
5592  * condition that the indexscan will use to decide that index
5593  * entries are killable (see heap_hot_search_buffer()).
5594  * Therefore, if the snapshot rejects a tuple and we have to
5595  * continue scanning past it, we know that the indexscan will
5596  * mark that index entry killed. That means that the next
5597  * get_actual_variable_range() call will not have to visit
5598  * that heap entry. In this way we avoid repetitive work when
5599  * this function is used a lot during planning.
5600  */
5601  index_scan = index_beginscan(heapRel, indexRel,
5602  &SnapshotNonVacuumable,
5603  1, 0);
5604  index_rescan(index_scan, scankeys, 1, NULL, 0);
5605 
5606  /* Fetch first tuple in sortop's direction */
5607  if ((tup = index_getnext(index_scan,
5608  indexscandir)) != NULL)
5609  {
5610  /* Extract the index column values from the heap tuple */
5611  ExecStoreTuple(tup, slot, InvalidBuffer, false);
5612  FormIndexDatum(indexInfo, slot, estate,
5613  values, isnull);
5614 
5615  /* Shouldn't have got a null, but be careful */
5616  if (isnull[0])
5617  elog(ERROR, "found unexpected null value in index \"%s\"",
5618  RelationGetRelationName(indexRel));
5619 
5620  /* Copy the index column value out to caller's context */
5621  MemoryContextSwitchTo(oldcontext);
5622  *min = datumCopy(values[0], typByVal, typLen);
5623  MemoryContextSwitchTo(tmpcontext);
5624  }
5625  else
5626  have_data = false;
5627 
5628  index_endscan(index_scan);
5629  }
5630 
5631  /* If max is requested, and we didn't find the index is empty */
5632  if (max && have_data)
5633  {
5634  index_scan = index_beginscan(heapRel, indexRel,
5635  &SnapshotNonVacuumable,
5636  1, 0);
5637  index_rescan(index_scan, scankeys, 1, NULL, 0);
5638 
5639  /* Fetch first tuple in reverse direction */
5640  if ((tup = index_getnext(index_scan,
5641  -indexscandir)) != NULL)
5642  {
5643  /* Extract the index column values from the heap tuple */
5644  ExecStoreTuple(tup, slot, InvalidBuffer, false);
5645  FormIndexDatum(indexInfo, slot, estate,
5646  values, isnull);
5647 
5648  /* Shouldn't have got a null, but be careful */
5649  if (isnull[0])
5650  elog(ERROR, "found unexpected null value in index \"%s\"",
5651  RelationGetRelationName(indexRel));
5652 
5653  /* Copy the index column value out to caller's context */
5654  MemoryContextSwitchTo(oldcontext);
5655  *max = datumCopy(values[0], typByVal, typLen);
5656  MemoryContextSwitchTo(tmpcontext);
5657  }
5658  else
5659  have_data = false;
5660 
5661  index_endscan(index_scan);
5662  }
5663 
5664  /* Clean everything up */
5666 
5667  index_close(indexRel, AccessShareLock);
5668  heap_close(heapRel, NoLock);
5669 
5670  MemoryContextSwitchTo(oldcontext);
5671  FreeExecutorState(estate);
5672 
5673  /* And we're done */
5674  break;
5675  }
5676  }
5677 
5678  return have_data;
5679 }
5680 
5681 /*
5682  * find_join_input_rel
5683  * Look up the input relation for a join.
5684  *
5685  * We assume that the input relation's RelOptInfo must have been constructed
5686  * already.
5687  */
5688 static RelOptInfo *
5690 {
5691  RelOptInfo *rel = NULL;
5692 
5693  switch (bms_membership(relids))
5694  {
5695  case BMS_EMPTY_SET:
5696  /* should not happen */
5697  break;
5698  case BMS_SINGLETON:
5699  rel = find_base_rel(root, bms_singleton_member(relids));
5700  break;
5701  case BMS_MULTIPLE:
5702  rel = find_join_rel(root, relids);
5703  break;
5704  }
5705 
5706  if (rel == NULL)
5707  elog(ERROR, "could not find RelOptInfo for given relids");
5708 
5709  return rel;
5710 }
5711 
5712 
5713 /*-------------------------------------------------------------------------
5714  *
5715  * Pattern analysis functions
5716  *
5717  * These routines support analysis of LIKE and regular-expression patterns
5718  * by the planner/optimizer. It's important that they agree with the
5719  * regular-expression code in backend/regex/ and the LIKE code in
5720  * backend/utils/adt/like.c. Also, the computation of the fixed prefix
5721  * must be conservative: if we report a string longer than the true fixed
5722  * prefix, the query may produce actually wrong answers, rather than just
5723  * getting a bad selectivity estimate!
5724  *
5725  * Note that the prefix-analysis functions are called from
5726  * backend/optimizer/path/indxpath.c as well as from routines in this file.
5727  *
5728  *-------------------------------------------------------------------------
5729  */
5730 
5731 /*
5732  * Check whether char is a letter (and, hence, subject to case-folding)
5733  *
5734  * In multibyte character sets or with ICU, we can't use isalpha, and it does not seem
5735  * worth trying to convert to wchar_t to use iswalpha. Instead, just assume
5736  * any multibyte char is potentially case-varying.
5737  */
5738 static int
5739 pattern_char_isalpha(char c, bool is_multibyte,
5740  pg_locale_t locale, bool locale_is_c)
5741 {
5742  if (locale_is_c)
5743  return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
5744  else if (is_multibyte && IS_HIGHBIT_SET(c))
5745  return true;
5746  else if (locale && locale->provider == COLLPROVIDER_ICU)
5747  return IS_HIGHBIT_SET(c) ? true : false;
5748 #ifdef HAVE_LOCALE_T
5749  else if (locale && locale->provider == COLLPROVIDER_LIBC)
5750  return isalpha_l((unsigned char) c, locale->info.lt);
5751 #endif
5752  else
5753  return isalpha((unsigned char) c);
5754 }
5755 
5756 /*
5757  * Extract the fixed prefix, if any, for a pattern.
5758  *
5759  * *prefix is set to a palloc'd prefix string (in the form of a Const node),
5760  * or to NULL if no fixed prefix exists for the pattern.
5761  * If rest_selec is not NULL, *rest_selec is set to an estimate of the
5762  * selectivity of the remainder of the pattern (without any fixed prefix).
5763  * The prefix Const has the same type (TEXT or BYTEA) as the input pattern.
5764  *
5765  * The return value distinguishes no fixed prefix, a partial prefix,
5766  * or an exact-match-only pattern.
5767  */
5768 
5769 static Pattern_Prefix_Status
5770 like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
5771  Const **prefix_const, Selectivity *rest_selec)
5772 {
5773  char *match;
5774  char *patt;
5775  int pattlen;
5776  Oid typeid = patt_const->consttype;
5777  int pos,
5778  match_pos;
5779  bool is_multibyte = (pg_database_encoding_max_length() > 1);
5780  pg_locale_t locale = 0;
5781  bool locale_is_c = false;
5782 
5783  /* the right-hand const is type text or bytea */
5784  Assert(typeid == BYTEAOID || typeid == TEXTOID);
5785 
5786  if (case_insensitive)
5787  {
5788  if (typeid == BYTEAOID)
5789  ereport(ERROR,
5790  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5791  errmsg("case insensitive matching not supported on type bytea")));
5792 
5793  /* If case-insensitive, we need locale info */
5794  if (lc_ctype_is_c(collation))
5795  locale_is_c = true;
5796  else if (collation != DEFAULT_COLLATION_OID)
5797  {
5798  if (!OidIsValid(collation))
5799  {
5800  /*
5801  * This typically means that the parser could not resolve a
5802  * conflict of implicit collations, so report it that way.
5803  */
5804  ereport(ERROR,
5805  (errcode(ERRCODE_INDETERMINATE_COLLATION),
5806  errmsg("could not determine which collation to use for ILIKE"),
5807  errhint("Use the COLLATE clause to set the collation explicitly.")));
5808  }
5809  locale = pg_newlocale_from_collation(collation);
5810  }
5811  }
5812 
5813  if (typeid != BYTEAOID)
5814  {
5815  patt = TextDatumGetCString(patt_const->constvalue);
5816  pattlen = strlen(patt);
5817  }
5818  else
5819  {
5820  bytea *bstr = DatumGetByteaPP(patt_const->constvalue);
5821 
5822  pattlen = VARSIZE_ANY_EXHDR(bstr);
5823  patt = (char *) palloc(pattlen);
5824  memcpy(patt, VARDATA_ANY(bstr), pattlen);
5825  Assert((Pointer) bstr == DatumGetPointer(patt_const->constvalue));
5826  }
5827 
5828  match = palloc(pattlen + 1);
5829  match_pos = 0;
5830  for (pos = 0; pos < pattlen; pos++)
5831  {
5832  /* % and _ are wildcard characters in LIKE */
5833  if (patt[pos] == '%' ||
5834  patt[pos] == '_')
5835  break;
5836 
5837  /* Backslash escapes the next character */
5838  if (patt[pos] == '\\')
5839  {
5840  pos++;
5841  if (pos >= pattlen)
5842  break;
5843  }
5844 
5845  /* Stop if case-varying character (it's sort of a wildcard) */
5846  if (case_insensitive &&
5847  pattern_char_isalpha(patt[pos], is_multibyte, locale, locale_is_c))
5848  break;
5849 
5850  match[match_pos++] = patt[pos];
5851  }
5852 
5853  match[match_pos] = '\0';
5854 
5855  if (typeid != BYTEAOID)
5856  *prefix_const = string_to_const(match, typeid);
5857  else
5858  *prefix_const = string_to_bytea_const(match, match_pos);
5859 
5860  if (rest_selec != NULL)
5861  *rest_selec = like_selectivity(&patt[pos], pattlen - pos,
5862  case_insensitive);
5863 
5864  pfree(patt);
5865  pfree(match);
5866 
5867  /* in LIKE, an empty pattern is an exact match! */
5868  if (pos == pattlen)
5869  return Pattern_Prefix_Exact; /* reached end of pattern, so exact */
5870 
5871  if (match_pos > 0)
5872  return Pattern_Prefix_Partial;
5873 
5874  return Pattern_Prefix_None;
5875 }
5876 
5877 static Pattern_Prefix_Status
5878 regex_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
5879  Const **prefix_const, Selectivity *rest_selec)
5880 {
5881  Oid typeid = patt_const->consttype;
5882  char *prefix;
5883  bool exact;
5884 
5885  /*
5886  * Should be unnecessary, there are no bytea regex operators defined. As
5887  * such, it should be noted that the rest of this function has *not* been
5888  * made safe for binary (possibly NULL containing) strings.
5889  */
5890  if (typeid == BYTEAOID)
5891  ereport(ERROR,
5892  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5893  errmsg("regular-expression matching not supported on type bytea")));
5894 
5895  /* Use the regexp machinery to extract the prefix, if any */
5896  prefix = regexp_fixed_prefix(DatumGetTextPP(patt_const->constvalue),
5897  case_insensitive, collation,
5898  &exact);
5899 
5900  if (prefix == NULL)
5901  {
5902  *prefix_const = NULL;
5903 
5904  if (rest_selec != NULL)
5905  {
5906  char *patt = TextDatumGetCString(patt_const->constvalue);
5907 
5908  *rest_selec = regex_selectivity(patt, strlen(patt),
5909  case_insensitive,
5910  0);
5911  pfree(patt);
5912  }
5913 
5914  return Pattern_Prefix_None;
5915  }
5916 
5917  *prefix_const = string_to_const(prefix, typeid);
5918 
5919  if (rest_selec != NULL)
5920  {
5921  if (exact)
5922  {
5923  /* Exact match, so there's no additional selectivity */
5924  *rest_selec = 1.0;
5925  }
5926  else
5927  {
5928  char *patt = TextDatumGetCString(patt_const->constvalue);
5929 
5930  *rest_selec = regex_selectivity(patt, strlen(patt),
5931  case_insensitive,
5932  strlen(prefix));
5933  pfree(patt);
5934  }
5935  }
5936 
5937  pfree(prefix);
5938 
5939  if (exact)
5940  return Pattern_Prefix_Exact; /* pattern specifies exact match */
5941  else
5942  return Pattern_Prefix_Partial;
5943 }
5944 
5946 pattern_fixed_prefix(Const *patt, Pattern_Type ptype, Oid collation,
5947  Const **prefix, Selectivity *rest_selec)
5948 {
5949  Pattern_Prefix_Status result;
5950 
5951  switch (ptype)
5952  {
5953  case Pattern_Type_Like:
5954  result = like_fixed_prefix(patt, false, collation,
5955  prefix, rest_selec);
5956  break;
5957  case Pattern_Type_Like_IC:
5958  result = like_fixed_prefix(patt, true, collation,
5959  prefix, rest_selec);
5960  break;
5961  case Pattern_Type_Regex:
5962  result = regex_fixed_prefix(patt, false, collation,
5963  prefix, rest_selec);
5964  break;
5965  case Pattern_Type_Regex_IC:
5966  result = regex_fixed_prefix(patt, true, collation,
5967  prefix, rest_selec);
5968  break;
5969  case Pattern_Type_Prefix:
5970  /* Prefix type work is trivial. */
5971  result = Pattern_Prefix_Partial;
5972  *rest_selec = 1.0; /* all */
5973  *prefix = makeConst(patt->consttype,
5974  patt->consttypmod,
5975  patt->constcollid,
5976  patt->constlen,
5977  datumCopy(patt->constvalue,
5978  patt->constbyval,
5979  patt->constlen),
5980  patt->constisnull,
5981  patt->constbyval);
5982  break;
5983  default:
5984  elog(ERROR, "unrecognized ptype: %d", (int) ptype);
5985  result = Pattern_Prefix_None; /* keep compiler quiet */
5986  break;
5987  }
5988  return result;
5989 }
5990 
5991 /*
5992  * Estimate the selectivity of a fixed prefix for a pattern match.
5993  *
5994  * A fixed prefix "foo" is estimated as the selectivity of the expression
5995  * "variable >= 'foo' AND variable < 'fop'" (see also indxpath.c).
5996  *
5997  * The selectivity estimate is with respect to the portion of the column
5998  * population represented by the histogram --- the caller must fold this
5999  * together with info about MCVs and NULLs.
6000  *
6001  * We use the >= and < operators from the specified btree opfamily to do the
6002  * estimation. The given variable and Const must be of the associated
6003  * datatype.
6004  *
6005  * XXX Note: we make use of the upper bound to estimate operator selectivity
6006  * even if the locale is such that we cannot rely on the upper-bound string.
6007  * The selectivity only needs to be approximately right anyway, so it seems
6008  * more useful to use the upper-bound code than not.
6009  */
6010 static Selectivity
6012  Oid vartype, Oid opfamily, Const *prefixcon)
6013 {
6015  Oid cmpopr;
6016  FmgrInfo opproc;
6017  Const *greaterstrcon;
6018  Selectivity eq_sel;
6019 
6020  cmpopr = get_opfamily_member(opfamily, vartype, vartype,
6022  if (cmpopr == InvalidOid)
6023  elog(ERROR, "no >= operator for opfamily %u", opfamily);
6024  fmgr_info(get_opcode(cmpopr), &opproc);
6025 
6026  prefixsel = ineq_histogram_selectivity(root, vardata,
6027  &opproc, true, true,
6028  prefixcon->constvalue,
6029  prefixcon->consttype);
6030 
6031  if (prefixsel < 0.0)
6032  {
6033  /* No histogram is present ... return a suitable default estimate */
6034  return DEFAULT_MATCH_SEL;
6035  }
6036 
6037  /*-------
6038  * If we can create a string larger than the prefix, say
6039  * "x < greaterstr".
6040  *-------
6041  */
6042  cmpopr = get_opfamily_member(opfamily, vartype, vartype,
6044  if (cmpopr == InvalidOid)
6045  elog(ERROR, "no < operator for opfamily %u", opfamily);
6046  fmgr_info(get_opcode(cmpopr), &opproc);
6047  greaterstrcon = make_greater_string(prefixcon, &opproc,
6048  DEFAULT_COLLATION_OID);
6049  if (greaterstrcon)
6050  {
6051  Selectivity topsel;
6052 
6053  topsel = ineq_histogram_selectivity(root, vardata,
6054  &opproc, false, false,
6055  greaterstrcon->constvalue,
6056  greaterstrcon->consttype);
6057 
6058  /* ineq_histogram_selectivity worked before, it shouldn't fail now */
6059  Assert(topsel >= 0.0);
6060 
6061  /*
6062  * Merge the two selectivities in the same way as for a range query
6063  * (see clauselist_selectivity()). Note that we don't need to worry
6064  * about double-exclusion of nulls, since ineq_histogram_selectivity
6065  * doesn't count those anyway.
6066  */
6067  prefixsel = topsel + prefixsel - 1.0;
6068  }
6069 
6070  /*
6071  * If the prefix is long then the two bounding values might be too close
6072  * together for the histogram to distinguish them usefully, resulting in a
6073  * zero estimate (plus or minus roundoff error). To avoid returning a
6074  * ridiculously small estimate, compute the estimated selectivity for
6075  * "variable = 'foo'", and clamp to that. (Obviously, the resultant
6076  * estimate should be at least that.)
6077  *
6078  * We apply this even if we couldn't make a greater string. That case
6079  * suggests that the prefix is near the maximum possible, and thus
6080  * probably off the end of the histogram, and thus we probably got a very
6081  * small estimate from the >= condition; so we still need to clamp.
6082  */
6083  cmpopr = get_opfamily_member(opfamily, vartype, vartype,
6085  if (cmpopr == InvalidOid)
6086  elog(ERROR, "no = operator for opfamily %u", opfamily);
6087  eq_sel = var_eq_const(vardata, cmpopr, prefixcon->constvalue,
6088  false, true, false);
6089 
6090  prefixsel = Max(prefixsel, eq_sel);
6091 
6092  return prefixsel;
6093 }
6094 
6095 
6096 /*
6097  * Estimate the selectivity of a pattern of the specified type.
6098  * Note that any fixed prefix of the pattern will have been removed already,
6099  * so actually we may be looking at just a fragment of the pattern.
6100  *
6101  * For now, we use a very simplistic approach: fixed characters reduce the
6102  * selectivity a good deal, character ranges reduce it a little,
6103  * wildcards (such as % for LIKE or .* for regex) increase it.
6104  */
6105 
6106 #define FIXED_CHAR_SEL 0.20 /* about 1/5 */
6107 #define CHAR_RANGE_SEL 0.25
6108 #define ANY_CHAR_SEL 0.9 /* not 1, since it won't match end-of-string */
6109 #define FULL_WILDCARD_SEL 5.0
6110 #define PARTIAL_WILDCARD_SEL 2.0
6111 
6112 static Selectivity
6113 like_selectivity(const char *patt, int pattlen, bool case_insensitive)
6114 {
6115  Selectivity sel = 1.0;
6116  int pos;
6117 
6118  /* Skip any leading wildcard; it's already factored into initial sel */
6119  for (pos = 0; pos < pattlen; pos++)
6120  {
6121  if (patt[pos] != '%' && patt[pos] != '_')
6122  break;
6123  }
6124 
6125  for (; pos < pattlen; pos++)
6126  {
6127  /* % and _ are wildcard characters in LIKE */
6128  if (patt[pos] == '%')
6129  sel *= FULL_WILDCARD_SEL;
6130  else if (patt[pos] == '_')
6131  sel *= ANY_CHAR_SEL;
6132  else if (patt[pos] == '\\')
6133  {
6134  /* Backslash quotes the next character */
6135  pos++;
6136  if (pos >= pattlen)
6137  break;
6138  sel *= FIXED_CHAR_SEL;
6139  }
6140  else
6141  sel *= FIXED_CHAR_SEL;
6142  }
6143  /* Could get sel > 1 if multiple wildcards */
6144  if (sel > 1.0)
6145  sel = 1.0;
6146  return sel;
6147 }
6148 
6149 static Selectivity
6150 regex_selectivity_sub(const char *patt, int pattlen, bool case_insensitive)
6151 {
6152  Selectivity sel = 1.0;
6153  int paren_depth = 0;
6154  int paren_pos = 0; /* dummy init to keep compiler quiet */
6155  int pos;
6156 
6157  for (pos = 0; pos < pattlen; pos++)
6158  {
6159  if (patt[pos] == '(')
6160  {
6161  if (paren_depth == 0)
6162  paren_pos = pos; /* remember start of parenthesized item */
6163  paren_depth++;
6164  }
6165  else if (patt[pos] == ')' && paren_depth > 0)
6166  {
6167  paren_depth--;
6168  if (paren_depth == 0)
6169  sel *= regex_selectivity_sub(patt + (paren_pos + 1),
6170  pos - (paren_pos + 1),
6171  case_insensitive);
6172  }
6173  else if (patt[pos] == '|' && paren_depth == 0)
6174  {
6175  /*
6176  * If unquoted | is present at paren level 0 in pattern, we have
6177  * multiple alternatives; sum their probabilities.
6178  */
6179  sel += regex_selectivity_sub(patt + (pos + 1),
6180  pattlen - (pos + 1),
6181  case_insensitive);
6182  break; /* rest of pattern is now processed */
6183  }
6184