]> granicus.if.org Git - postgresql/blob - src/backend/utils/adt/selfuncs.c
Make gincostestimate() cope with hypothetical GIN indexes.
[postgresql] / src / backend / utils / adt / selfuncs.c
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 registered in the pg_am catalog
11  *        in the "amcostestimate" attribute.
12  *
13  * Portions Copyright (c) 1996-2015, 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 <math.h>
102
103 #include "access/gin.h"
104 #include "access/htup_details.h"
105 #include "access/sysattr.h"
106 #include "catalog/index.h"
107 #include "catalog/pg_collation.h"
108 #include "catalog/pg_operator.h"
109 #include "catalog/pg_opfamily.h"
110 #include "catalog/pg_statistic.h"
111 #include "catalog/pg_type.h"
112 #include "executor/executor.h"
113 #include "mb/pg_wchar.h"
114 #include "nodes/makefuncs.h"
115 #include "nodes/nodeFuncs.h"
116 #include "optimizer/clauses.h"
117 #include "optimizer/cost.h"
118 #include "optimizer/pathnode.h"
119 #include "optimizer/paths.h"
120 #include "optimizer/plancat.h"
121 #include "optimizer/predtest.h"
122 #include "optimizer/restrictinfo.h"
123 #include "optimizer/var.h"
124 #include "parser/parse_clause.h"
125 #include "parser/parse_coerce.h"
126 #include "parser/parsetree.h"
127 #include "utils/builtins.h"
128 #include "utils/bytea.h"
129 #include "utils/date.h"
130 #include "utils/datum.h"
131 #include "utils/fmgroids.h"
132 #include "utils/lsyscache.h"
133 #include "utils/nabstime.h"
134 #include "utils/pg_locale.h"
135 #include "utils/rel.h"
136 #include "utils/selfuncs.h"
137 #include "utils/spccache.h"
138 #include "utils/syscache.h"
139 #include "utils/timestamp.h"
140 #include "utils/tqual.h"
141 #include "utils/typcache.h"
142
143
144 /* Hooks for plugins to get control when we ask for stats */
145 get_relation_stats_hook_type get_relation_stats_hook = NULL;
146 get_index_stats_hook_type get_index_stats_hook = NULL;
147
148 static double var_eq_const(VariableStatData *vardata, Oid operator,
149                          Datum constval, bool constisnull,
150                          bool varonleft);
151 static double var_eq_non_const(VariableStatData *vardata, Oid operator,
152                                  Node *other,
153                                  bool varonleft);
154 static double ineq_histogram_selectivity(PlannerInfo *root,
155                                                    VariableStatData *vardata,
156                                                    FmgrInfo *opproc, bool isgt,
157                                                    Datum constval, Oid consttype);
158 static double eqjoinsel_inner(Oid operator,
159                                 VariableStatData *vardata1, VariableStatData *vardata2);
160 static double eqjoinsel_semi(Oid operator,
161                            VariableStatData *vardata1, VariableStatData *vardata2,
162                            RelOptInfo *inner_rel);
163 static bool convert_to_scalar(Datum value, Oid valuetypid, double *scaledvalue,
164                                   Datum lobound, Datum hibound, Oid boundstypid,
165                                   double *scaledlobound, double *scaledhibound);
166 static double convert_numeric_to_scalar(Datum value, Oid typid);
167 static void convert_string_to_scalar(char *value,
168                                                  double *scaledvalue,
169                                                  char *lobound,
170                                                  double *scaledlobound,
171                                                  char *hibound,
172                                                  double *scaledhibound);
173 static void convert_bytea_to_scalar(Datum value,
174                                                 double *scaledvalue,
175                                                 Datum lobound,
176                                                 double *scaledlobound,
177                                                 Datum hibound,
178                                                 double *scaledhibound);
179 static double convert_one_string_to_scalar(char *value,
180                                                          int rangelo, int rangehi);
181 static double convert_one_bytea_to_scalar(unsigned char *value, int valuelen,
182                                                         int rangelo, int rangehi);
183 static char *convert_string_datum(Datum value, Oid typid);
184 static double convert_timevalue_to_scalar(Datum value, Oid typid);
185 static void examine_simple_variable(PlannerInfo *root, Var *var,
186                                                 VariableStatData *vardata);
187 static bool get_variable_range(PlannerInfo *root, VariableStatData *vardata,
188                                    Oid sortop, Datum *min, Datum *max);
189 static bool get_actual_variable_range(PlannerInfo *root,
190                                                   VariableStatData *vardata,
191                                                   Oid sortop,
192                                                   Datum *min, Datum *max);
193 static RelOptInfo *find_join_input_rel(PlannerInfo *root, Relids relids);
194 static Selectivity prefix_selectivity(PlannerInfo *root,
195                                    VariableStatData *vardata,
196                                    Oid vartype, Oid opfamily, Const *prefixcon);
197 static Selectivity like_selectivity(const char *patt, int pattlen,
198                                  bool case_insensitive);
199 static Selectivity regex_selectivity(const char *patt, int pattlen,
200                                   bool case_insensitive,
201                                   int fixed_prefix_len);
202 static Datum string_to_datum(const char *str, Oid datatype);
203 static Const *string_to_const(const char *str, Oid datatype);
204 static Const *string_to_bytea_const(const char *str, size_t str_len);
205 static List *add_predicate_to_quals(IndexOptInfo *index, List *indexQuals);
206
207
208 /*
209  *              eqsel                   - Selectivity of "=" for any data types.
210  *
211  * Note: this routine is also used to estimate selectivity for some
212  * operators that are not "=" but have comparable selectivity behavior,
213  * such as "~=" (geometric approximate-match).  Even for "=", we must
214  * keep in mind that the left and right datatypes may differ.
215  */
216 Datum
217 eqsel(PG_FUNCTION_ARGS)
218 {
219         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
220         Oid                     operator = PG_GETARG_OID(1);
221         List       *args = (List *) PG_GETARG_POINTER(2);
222         int                     varRelid = PG_GETARG_INT32(3);
223         VariableStatData vardata;
224         Node       *other;
225         bool            varonleft;
226         double          selec;
227
228         /*
229          * If expression is not variable = something or something = variable, then
230          * punt and return a default estimate.
231          */
232         if (!get_restriction_variable(root, args, varRelid,
233                                                                   &vardata, &other, &varonleft))
234                 PG_RETURN_FLOAT8(DEFAULT_EQ_SEL);
235
236         /*
237          * We can do a lot better if the something is a constant.  (Note: the
238          * Const might result from estimation rather than being a simple constant
239          * in the query.)
240          */
241         if (IsA(other, Const))
242                 selec = var_eq_const(&vardata, operator,
243                                                          ((Const *) other)->constvalue,
244                                                          ((Const *) other)->constisnull,
245                                                          varonleft);
246         else
247                 selec = var_eq_non_const(&vardata, operator, other,
248                                                                  varonleft);
249
250         ReleaseVariableStats(vardata);
251
252         PG_RETURN_FLOAT8((float8) selec);
253 }
254
255 /*
256  * var_eq_const --- eqsel for var = const case
257  *
258  * This is split out so that some other estimation functions can use it.
259  */
260 static double
261 var_eq_const(VariableStatData *vardata, Oid operator,
262                          Datum constval, bool constisnull,
263                          bool varonleft)
264 {
265         double          selec;
266         bool            isdefault;
267
268         /*
269          * If the constant is NULL, assume operator is strict and return zero, ie,
270          * operator will never return TRUE.
271          */
272         if (constisnull)
273                 return 0.0;
274
275         /*
276          * If we matched the var to a unique index or DISTINCT clause, assume
277          * there is exactly one match regardless of anything else.  (This is
278          * slightly bogus, since the index or clause's equality operator might be
279          * different from ours, but it's much more likely to be right than
280          * ignoring the information.)
281          */
282         if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1.0)
283                 return 1.0 / vardata->rel->tuples;
284
285         if (HeapTupleIsValid(vardata->statsTuple))
286         {
287                 Form_pg_statistic stats;
288                 Datum      *values;
289                 int                     nvalues;
290                 float4     *numbers;
291                 int                     nnumbers;
292                 bool            match = false;
293                 int                     i;
294
295                 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
296
297                 /*
298                  * Is the constant "=" to any of the column's most common values?
299                  * (Although the given operator may not really be "=", we will assume
300                  * that seeing whether it returns TRUE is an appropriate test.  If you
301                  * don't like this, maybe you shouldn't be using eqsel for your
302                  * operator...)
303                  */
304                 if (get_attstatsslot(vardata->statsTuple,
305                                                          vardata->atttype, vardata->atttypmod,
306                                                          STATISTIC_KIND_MCV, InvalidOid,
307                                                          NULL,
308                                                          &values, &nvalues,
309                                                          &numbers, &nnumbers))
310                 {
311                         FmgrInfo        eqproc;
312
313                         fmgr_info(get_opcode(operator), &eqproc);
314
315                         for (i = 0; i < nvalues; i++)
316                         {
317                                 /* be careful to apply operator right way 'round */
318                                 if (varonleft)
319                                         match = DatumGetBool(FunctionCall2Coll(&eqproc,
320                                                                                                            DEFAULT_COLLATION_OID,
321                                                                                                                    values[i],
322                                                                                                                    constval));
323                                 else
324                                         match = DatumGetBool(FunctionCall2Coll(&eqproc,
325                                                                                                            DEFAULT_COLLATION_OID,
326                                                                                                                    constval,
327                                                                                                                    values[i]));
328                                 if (match)
329                                         break;
330                         }
331                 }
332                 else
333                 {
334                         /* no most-common-value info available */
335                         values = NULL;
336                         numbers = NULL;
337                         i = nvalues = nnumbers = 0;
338                 }
339
340                 if (match)
341                 {
342                         /*
343                          * Constant is "=" to this common value.  We know selectivity
344                          * exactly (or as exactly as ANALYZE could calculate it, anyway).
345                          */
346                         selec = numbers[i];
347                 }
348                 else
349                 {
350                         /*
351                          * Comparison is against a constant that is neither NULL nor any
352                          * of the common values.  Its selectivity cannot be more than
353                          * this:
354                          */
355                         double          sumcommon = 0.0;
356                         double          otherdistinct;
357
358                         for (i = 0; i < nnumbers; i++)
359                                 sumcommon += numbers[i];
360                         selec = 1.0 - sumcommon - stats->stanullfrac;
361                         CLAMP_PROBABILITY(selec);
362
363                         /*
364                          * and in fact it's probably a good deal less. We approximate that
365                          * all the not-common values share this remaining fraction
366                          * equally, so we divide by the number of other distinct values.
367                          */
368                         otherdistinct = get_variable_numdistinct(vardata, &isdefault) - nnumbers;
369                         if (otherdistinct > 1)
370                                 selec /= otherdistinct;
371
372                         /*
373                          * Another cross-check: selectivity shouldn't be estimated as more
374                          * than the least common "most common value".
375                          */
376                         if (nnumbers > 0 && selec > numbers[nnumbers - 1])
377                                 selec = numbers[nnumbers - 1];
378                 }
379
380                 free_attstatsslot(vardata->atttype, values, nvalues,
381                                                   numbers, nnumbers);
382         }
383         else
384         {
385                 /*
386                  * No ANALYZE stats available, so make a guess using estimated number
387                  * of distinct values and assuming they are equally common. (The guess
388                  * is unlikely to be very good, but we do know a few special cases.)
389                  */
390                 selec = 1.0 / get_variable_numdistinct(vardata, &isdefault);
391         }
392
393         /* result should be in range, but make sure... */
394         CLAMP_PROBABILITY(selec);
395
396         return selec;
397 }
398
399 /*
400  * var_eq_non_const --- eqsel for var = something-other-than-const case
401  */
402 static double
403 var_eq_non_const(VariableStatData *vardata, Oid operator,
404                                  Node *other,
405                                  bool varonleft)
406 {
407         double          selec;
408         bool            isdefault;
409
410         /*
411          * If we matched the var to a unique index or DISTINCT clause, assume
412          * there is exactly one match regardless of anything else.  (This is
413          * slightly bogus, since the index or clause's equality operator might be
414          * different from ours, but it's much more likely to be right than
415          * ignoring the information.)
416          */
417         if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1.0)
418                 return 1.0 / vardata->rel->tuples;
419
420         if (HeapTupleIsValid(vardata->statsTuple))
421         {
422                 Form_pg_statistic stats;
423                 double          ndistinct;
424                 float4     *numbers;
425                 int                     nnumbers;
426
427                 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
428
429                 /*
430                  * Search is for a value that we do not know a priori, but we will
431                  * assume it is not NULL.  Estimate the selectivity as non-null
432                  * fraction divided by number of distinct values, so that we get a
433                  * result averaged over all possible values whether common or
434                  * uncommon.  (Essentially, we are assuming that the not-yet-known
435                  * comparison value is equally likely to be any of the possible
436                  * values, regardless of their frequency in the table.  Is that a good
437                  * idea?)
438                  */
439                 selec = 1.0 - stats->stanullfrac;
440                 ndistinct = get_variable_numdistinct(vardata, &isdefault);
441                 if (ndistinct > 1)
442                         selec /= ndistinct;
443
444                 /*
445                  * Cross-check: selectivity should never be estimated as more than the
446                  * most common value's.
447                  */
448                 if (get_attstatsslot(vardata->statsTuple,
449                                                          vardata->atttype, vardata->atttypmod,
450                                                          STATISTIC_KIND_MCV, InvalidOid,
451                                                          NULL,
452                                                          NULL, NULL,
453                                                          &numbers, &nnumbers))
454                 {
455                         if (nnumbers > 0 && selec > numbers[0])
456                                 selec = numbers[0];
457                         free_attstatsslot(vardata->atttype, NULL, 0, numbers, nnumbers);
458                 }
459         }
460         else
461         {
462                 /*
463                  * No ANALYZE stats available, so make a guess using estimated number
464                  * of distinct values and assuming they are equally common. (The guess
465                  * is unlikely to be very good, but we do know a few special cases.)
466                  */
467                 selec = 1.0 / get_variable_numdistinct(vardata, &isdefault);
468         }
469
470         /* result should be in range, but make sure... */
471         CLAMP_PROBABILITY(selec);
472
473         return selec;
474 }
475
476 /*
477  *              neqsel                  - Selectivity of "!=" for any data types.
478  *
479  * This routine is also used for some operators that are not "!="
480  * but have comparable selectivity behavior.  See above comments
481  * for eqsel().
482  */
483 Datum
484 neqsel(PG_FUNCTION_ARGS)
485 {
486         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
487         Oid                     operator = PG_GETARG_OID(1);
488         List       *args = (List *) PG_GETARG_POINTER(2);
489         int                     varRelid = PG_GETARG_INT32(3);
490         Oid                     eqop;
491         float8          result;
492
493         /*
494          * We want 1 - eqsel() where the equality operator is the one associated
495          * with this != operator, that is, its negator.
496          */
497         eqop = get_negator(operator);
498         if (eqop)
499         {
500                 result = DatumGetFloat8(DirectFunctionCall4(eqsel,
501                                                                                                         PointerGetDatum(root),
502                                                                                                         ObjectIdGetDatum(eqop),
503                                                                                                         PointerGetDatum(args),
504                                                                                                         Int32GetDatum(varRelid)));
505         }
506         else
507         {
508                 /* Use default selectivity (should we raise an error instead?) */
509                 result = DEFAULT_EQ_SEL;
510         }
511         result = 1.0 - result;
512         PG_RETURN_FLOAT8(result);
513 }
514
515 /*
516  *      scalarineqsel           - Selectivity of "<", "<=", ">", ">=" for scalars.
517  *
518  * This is the guts of both scalarltsel and scalargtsel.  The caller has
519  * commuted the clause, if necessary, so that we can treat the variable as
520  * being on the left.  The caller must also make sure that the other side
521  * of the clause is a non-null Const, and dissect same into a value and
522  * datatype.
523  *
524  * This routine works for any datatype (or pair of datatypes) known to
525  * convert_to_scalar().  If it is applied to some other datatype,
526  * it will return a default estimate.
527  */
528 static double
529 scalarineqsel(PlannerInfo *root, Oid operator, bool isgt,
530                           VariableStatData *vardata, Datum constval, Oid consttype)
531 {
532         Form_pg_statistic stats;
533         FmgrInfo        opproc;
534         double          mcv_selec,
535                                 hist_selec,
536                                 sumcommon;
537         double          selec;
538
539         if (!HeapTupleIsValid(vardata->statsTuple))
540         {
541                 /* no stats available, so default result */
542                 return DEFAULT_INEQ_SEL;
543         }
544         stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
545
546         fmgr_info(get_opcode(operator), &opproc);
547
548         /*
549          * If we have most-common-values info, add up the fractions of the MCV
550          * entries that satisfy MCV OP CONST.  These fractions contribute directly
551          * to the result selectivity.  Also add up the total fraction represented
552          * by MCV entries.
553          */
554         mcv_selec = mcv_selectivity(vardata, &opproc, constval, true,
555                                                                 &sumcommon);
556
557         /*
558          * If there is a histogram, determine which bin the constant falls in, and
559          * compute the resulting contribution to selectivity.
560          */
561         hist_selec = ineq_histogram_selectivity(root, vardata, &opproc, isgt,
562                                                                                         constval, consttype);
563
564         /*
565          * Now merge the results from the MCV and histogram calculations,
566          * realizing that the histogram covers only the non-null values that are
567          * not listed in MCV.
568          */
569         selec = 1.0 - stats->stanullfrac - sumcommon;
570
571         if (hist_selec >= 0.0)
572                 selec *= hist_selec;
573         else
574         {
575                 /*
576                  * If no histogram but there are values not accounted for by MCV,
577                  * arbitrarily assume half of them will match.
578                  */
579                 selec *= 0.5;
580         }
581
582         selec += mcv_selec;
583
584         /* result should be in range, but make sure... */
585         CLAMP_PROBABILITY(selec);
586
587         return selec;
588 }
589
590 /*
591  *      mcv_selectivity                 - Examine the MCV list for selectivity estimates
592  *
593  * Determine the fraction of the variable's MCV population that satisfies
594  * the predicate (VAR OP CONST), or (CONST OP VAR) if !varonleft.  Also
595  * compute the fraction of the total column population represented by the MCV
596  * list.  This code will work for any boolean-returning predicate operator.
597  *
598  * The function result is the MCV selectivity, and the fraction of the
599  * total population is returned into *sumcommonp.  Zeroes are returned
600  * if there is no MCV list.
601  */
602 double
603 mcv_selectivity(VariableStatData *vardata, FmgrInfo *opproc,
604                                 Datum constval, bool varonleft,
605                                 double *sumcommonp)
606 {
607         double          mcv_selec,
608                                 sumcommon;
609         Datum      *values;
610         int                     nvalues;
611         float4     *numbers;
612         int                     nnumbers;
613         int                     i;
614
615         mcv_selec = 0.0;
616         sumcommon = 0.0;
617
618         if (HeapTupleIsValid(vardata->statsTuple) &&
619                 get_attstatsslot(vardata->statsTuple,
620                                                  vardata->atttype, vardata->atttypmod,
621                                                  STATISTIC_KIND_MCV, InvalidOid,
622                                                  NULL,
623                                                  &values, &nvalues,
624                                                  &numbers, &nnumbers))
625         {
626                 for (i = 0; i < nvalues; i++)
627                 {
628                         if (varonleft ?
629                                 DatumGetBool(FunctionCall2Coll(opproc,
630                                                                                            DEFAULT_COLLATION_OID,
631                                                                                            values[i],
632                                                                                            constval)) :
633                                 DatumGetBool(FunctionCall2Coll(opproc,
634                                                                                            DEFAULT_COLLATION_OID,
635                                                                                            constval,
636                                                                                            values[i])))
637                                 mcv_selec += numbers[i];
638                         sumcommon += numbers[i];
639                 }
640                 free_attstatsslot(vardata->atttype, values, nvalues,
641                                                   numbers, nnumbers);
642         }
643
644         *sumcommonp = sumcommon;
645         return mcv_selec;
646 }
647
648 /*
649  *      histogram_selectivity   - Examine the histogram for selectivity estimates
650  *
651  * Determine the fraction of the variable's histogram entries that satisfy
652  * the predicate (VAR OP CONST), or (CONST OP VAR) if !varonleft.
653  *
654  * This code will work for any boolean-returning predicate operator, whether
655  * or not it has anything to do with the histogram sort operator.  We are
656  * essentially using the histogram just as a representative sample.  However,
657  * small histograms are unlikely to be all that representative, so the caller
658  * should be prepared to fall back on some other estimation approach when the
659  * histogram is missing or very small.  It may also be prudent to combine this
660  * approach with another one when the histogram is small.
661  *
662  * If the actual histogram size is not at least min_hist_size, we won't bother
663  * to do the calculation at all.  Also, if the n_skip parameter is > 0, we
664  * ignore the first and last n_skip histogram elements, on the grounds that
665  * they are outliers and hence not very representative.  Typical values for
666  * these parameters are 10 and 1.
667  *
668  * The function result is the selectivity, or -1 if there is no histogram
669  * or it's smaller than min_hist_size.
670  *
671  * The output parameter *hist_size receives the actual histogram size,
672  * or zero if no histogram.  Callers may use this number to decide how
673  * much faith to put in the function result.
674  *
675  * Note that the result disregards both the most-common-values (if any) and
676  * null entries.  The caller is expected to combine this result with
677  * statistics for those portions of the column population.  It may also be
678  * prudent to clamp the result range, ie, disbelieve exact 0 or 1 outputs.
679  */
680 double
681 histogram_selectivity(VariableStatData *vardata, FmgrInfo *opproc,
682                                           Datum constval, bool varonleft,
683                                           int min_hist_size, int n_skip,
684                                           int *hist_size)
685 {
686         double          result;
687         Datum      *values;
688         int                     nvalues;
689
690         /* check sanity of parameters */
691         Assert(n_skip >= 0);
692         Assert(min_hist_size > 2 * n_skip);
693
694         if (HeapTupleIsValid(vardata->statsTuple) &&
695                 get_attstatsslot(vardata->statsTuple,
696                                                  vardata->atttype, vardata->atttypmod,
697                                                  STATISTIC_KIND_HISTOGRAM, InvalidOid,
698                                                  NULL,
699                                                  &values, &nvalues,
700                                                  NULL, NULL))
701         {
702                 *hist_size = nvalues;
703                 if (nvalues >= min_hist_size)
704                 {
705                         int                     nmatch = 0;
706                         int                     i;
707
708                         for (i = n_skip; i < nvalues - n_skip; i++)
709                         {
710                                 if (varonleft ?
711                                         DatumGetBool(FunctionCall2Coll(opproc,
712                                                                                                    DEFAULT_COLLATION_OID,
713                                                                                                    values[i],
714                                                                                                    constval)) :
715                                         DatumGetBool(FunctionCall2Coll(opproc,
716                                                                                                    DEFAULT_COLLATION_OID,
717                                                                                                    constval,
718                                                                                                    values[i])))
719                                         nmatch++;
720                         }
721                         result = ((double) nmatch) / ((double) (nvalues - 2 * n_skip));
722                 }
723                 else
724                         result = -1;
725                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
726         }
727         else
728         {
729                 *hist_size = 0;
730                 result = -1;
731         }
732
733         return result;
734 }
735
736 /*
737  *      ineq_histogram_selectivity      - Examine the histogram for scalarineqsel
738  *
739  * Determine the fraction of the variable's histogram population that
740  * satisfies the inequality condition, ie, VAR < CONST or VAR > CONST.
741  *
742  * Returns -1 if there is no histogram (valid results will always be >= 0).
743  *
744  * Note that the result disregards both the most-common-values (if any) and
745  * null entries.  The caller is expected to combine this result with
746  * statistics for those portions of the column population.
747  */
748 static double
749 ineq_histogram_selectivity(PlannerInfo *root,
750                                                    VariableStatData *vardata,
751                                                    FmgrInfo *opproc, bool isgt,
752                                                    Datum constval, Oid consttype)
753 {
754         double          hist_selec;
755         Oid                     hist_op;
756         Datum      *values;
757         int                     nvalues;
758
759         hist_selec = -1.0;
760
761         /*
762          * Someday, ANALYZE might store more than one histogram per rel/att,
763          * corresponding to more than one possible sort ordering defined for the
764          * column type.  However, to make that work we will need to figure out
765          * which staop to search for --- it's not necessarily the one we have at
766          * hand!  (For example, we might have a '<=' operator rather than the '<'
767          * operator that will appear in staop.)  For now, assume that whatever
768          * appears in pg_statistic is sorted the same way our operator sorts, or
769          * the reverse way if isgt is TRUE.
770          */
771         if (HeapTupleIsValid(vardata->statsTuple) &&
772                 get_attstatsslot(vardata->statsTuple,
773                                                  vardata->atttype, vardata->atttypmod,
774                                                  STATISTIC_KIND_HISTOGRAM, InvalidOid,
775                                                  &hist_op,
776                                                  &values, &nvalues,
777                                                  NULL, NULL))
778         {
779                 if (nvalues > 1)
780                 {
781                         /*
782                          * Use binary search to find proper location, ie, the first slot
783                          * at which the comparison fails.  (If the given operator isn't
784                          * actually sort-compatible with the histogram, you'll get garbage
785                          * results ... but probably not any more garbage-y than you would
786                          * from the old linear search.)
787                          *
788                          * If the binary search accesses the first or last histogram
789                          * entry, we try to replace that endpoint with the true column min
790                          * or max as found by get_actual_variable_range().  This
791                          * ameliorates misestimates when the min or max is moving as a
792                          * result of changes since the last ANALYZE.  Note that this could
793                          * result in effectively including MCVs into the histogram that
794                          * weren't there before, but we don't try to correct for that.
795                          */
796                         double          histfrac;
797                         int                     lobound = 0;    /* first possible slot to search */
798                         int                     hibound = nvalues;              /* last+1 slot to search */
799                         bool            have_end = false;
800
801                         /*
802                          * If there are only two histogram entries, we'll want up-to-date
803                          * values for both.  (If there are more than two, we need at most
804                          * one of them to be updated, so we deal with that within the
805                          * loop.)
806                          */
807                         if (nvalues == 2)
808                                 have_end = get_actual_variable_range(root,
809                                                                                                          vardata,
810                                                                                                          hist_op,
811                                                                                                          &values[0],
812                                                                                                          &values[1]);
813
814                         while (lobound < hibound)
815                         {
816                                 int                     probe = (lobound + hibound) / 2;
817                                 bool            ltcmp;
818
819                                 /*
820                                  * If we find ourselves about to compare to the first or last
821                                  * histogram entry, first try to replace it with the actual
822                                  * current min or max (unless we already did so above).
823                                  */
824                                 if (probe == 0 && nvalues > 2)
825                                         have_end = get_actual_variable_range(root,
826                                                                                                                  vardata,
827                                                                                                                  hist_op,
828                                                                                                                  &values[0],
829                                                                                                                  NULL);
830                                 else if (probe == nvalues - 1 && nvalues > 2)
831                                         have_end = get_actual_variable_range(root,
832                                                                                                                  vardata,
833                                                                                                                  hist_op,
834                                                                                                                  NULL,
835                                                                                                                  &values[probe]);
836
837                                 ltcmp = DatumGetBool(FunctionCall2Coll(opproc,
838                                                                                                            DEFAULT_COLLATION_OID,
839                                                                                                            values[probe],
840                                                                                                            constval));
841                                 if (isgt)
842                                         ltcmp = !ltcmp;
843                                 if (ltcmp)
844                                         lobound = probe + 1;
845                                 else
846                                         hibound = probe;
847                         }
848
849                         if (lobound <= 0)
850                         {
851                                 /* Constant is below lower histogram boundary. */
852                                 histfrac = 0.0;
853                         }
854                         else if (lobound >= nvalues)
855                         {
856                                 /* Constant is above upper histogram boundary. */
857                                 histfrac = 1.0;
858                         }
859                         else
860                         {
861                                 int                     i = lobound;
862                                 double          val,
863                                                         high,
864                                                         low;
865                                 double          binfrac;
866
867                                 /*
868                                  * We have values[i-1] <= constant <= values[i].
869                                  *
870                                  * Convert the constant and the two nearest bin boundary
871                                  * values to a uniform comparison scale, and do a linear
872                                  * interpolation within this bin.
873                                  */
874                                 if (convert_to_scalar(constval, consttype, &val,
875                                                                           values[i - 1], values[i],
876                                                                           vardata->vartype,
877                                                                           &low, &high))
878                                 {
879                                         if (high <= low)
880                                         {
881                                                 /* cope if bin boundaries appear identical */
882                                                 binfrac = 0.5;
883                                         }
884                                         else if (val <= low)
885                                                 binfrac = 0.0;
886                                         else if (val >= high)
887                                                 binfrac = 1.0;
888                                         else
889                                         {
890                                                 binfrac = (val - low) / (high - low);
891
892                                                 /*
893                                                  * Watch out for the possibility that we got a NaN or
894                                                  * Infinity from the division.  This can happen
895                                                  * despite the previous checks, if for example "low"
896                                                  * is -Infinity.
897                                                  */
898                                                 if (isnan(binfrac) ||
899                                                         binfrac < 0.0 || binfrac > 1.0)
900                                                         binfrac = 0.5;
901                                         }
902                                 }
903                                 else
904                                 {
905                                         /*
906                                          * Ideally we'd produce an error here, on the grounds that
907                                          * the given operator shouldn't have scalarXXsel
908                                          * registered as its selectivity func unless we can deal
909                                          * with its operand types.  But currently, all manner of
910                                          * stuff is invoking scalarXXsel, so give a default
911                                          * estimate until that can be fixed.
912                                          */
913                                         binfrac = 0.5;
914                                 }
915
916                                 /*
917                                  * Now, compute the overall selectivity across the values
918                                  * represented by the histogram.  We have i-1 full bins and
919                                  * binfrac partial bin below the constant.
920                                  */
921                                 histfrac = (double) (i - 1) + binfrac;
922                                 histfrac /= (double) (nvalues - 1);
923                         }
924
925                         /*
926                          * Now histfrac = fraction of histogram entries below the
927                          * constant.
928                          *
929                          * Account for "<" vs ">"
930                          */
931                         hist_selec = isgt ? (1.0 - histfrac) : histfrac;
932
933                         /*
934                          * The histogram boundaries are only approximate to begin with,
935                          * and may well be out of date anyway.  Therefore, don't believe
936                          * extremely small or large selectivity estimates --- unless we
937                          * got actual current endpoint values from the table.
938                          */
939                         if (have_end)
940                                 CLAMP_PROBABILITY(hist_selec);
941                         else
942                         {
943                                 if (hist_selec < 0.0001)
944                                         hist_selec = 0.0001;
945                                 else if (hist_selec > 0.9999)
946                                         hist_selec = 0.9999;
947                         }
948                 }
949
950                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
951         }
952
953         return hist_selec;
954 }
955
956 /*
957  *              scalarltsel             - Selectivity of "<" (also "<=") for scalars.
958  */
959 Datum
960 scalarltsel(PG_FUNCTION_ARGS)
961 {
962         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
963         Oid                     operator = PG_GETARG_OID(1);
964         List       *args = (List *) PG_GETARG_POINTER(2);
965         int                     varRelid = PG_GETARG_INT32(3);
966         VariableStatData vardata;
967         Node       *other;
968         bool            varonleft;
969         Datum           constval;
970         Oid                     consttype;
971         bool            isgt;
972         double          selec;
973
974         /*
975          * If expression is not variable op something or something op variable,
976          * then punt and return a default estimate.
977          */
978         if (!get_restriction_variable(root, args, varRelid,
979                                                                   &vardata, &other, &varonleft))
980                 PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
981
982         /*
983          * Can't do anything useful if the something is not a constant, either.
984          */
985         if (!IsA(other, Const))
986         {
987                 ReleaseVariableStats(vardata);
988                 PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
989         }
990
991         /*
992          * If the constant is NULL, assume operator is strict and return zero, ie,
993          * operator will never return TRUE.
994          */
995         if (((Const *) other)->constisnull)
996         {
997                 ReleaseVariableStats(vardata);
998                 PG_RETURN_FLOAT8(0.0);
999         }
1000         constval = ((Const *) other)->constvalue;
1001         consttype = ((Const *) other)->consttype;
1002
1003         /*
1004          * Force the var to be on the left to simplify logic in scalarineqsel.
1005          */
1006         if (varonleft)
1007         {
1008                 /* we have var < other */
1009                 isgt = false;
1010         }
1011         else
1012         {
1013                 /* we have other < var, commute to make var > other */
1014                 operator = get_commutator(operator);
1015                 if (!operator)
1016                 {
1017                         /* Use default selectivity (should we raise an error instead?) */
1018                         ReleaseVariableStats(vardata);
1019                         PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
1020                 }
1021                 isgt = true;
1022         }
1023
1024         selec = scalarineqsel(root, operator, isgt, &vardata, constval, consttype);
1025
1026         ReleaseVariableStats(vardata);
1027
1028         PG_RETURN_FLOAT8((float8) selec);
1029 }
1030
1031 /*
1032  *              scalargtsel             - Selectivity of ">" (also ">=") for integers.
1033  */
1034 Datum
1035 scalargtsel(PG_FUNCTION_ARGS)
1036 {
1037         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
1038         Oid                     operator = PG_GETARG_OID(1);
1039         List       *args = (List *) PG_GETARG_POINTER(2);
1040         int                     varRelid = PG_GETARG_INT32(3);
1041         VariableStatData vardata;
1042         Node       *other;
1043         bool            varonleft;
1044         Datum           constval;
1045         Oid                     consttype;
1046         bool            isgt;
1047         double          selec;
1048
1049         /*
1050          * If expression is not variable op something or something op variable,
1051          * then punt and return a default estimate.
1052          */
1053         if (!get_restriction_variable(root, args, varRelid,
1054                                                                   &vardata, &other, &varonleft))
1055                 PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
1056
1057         /*
1058          * Can't do anything useful if the something is not a constant, either.
1059          */
1060         if (!IsA(other, Const))
1061         {
1062                 ReleaseVariableStats(vardata);
1063                 PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
1064         }
1065
1066         /*
1067          * If the constant is NULL, assume operator is strict and return zero, ie,
1068          * operator will never return TRUE.
1069          */
1070         if (((Const *) other)->constisnull)
1071         {
1072                 ReleaseVariableStats(vardata);
1073                 PG_RETURN_FLOAT8(0.0);
1074         }
1075         constval = ((Const *) other)->constvalue;
1076         consttype = ((Const *) other)->consttype;
1077
1078         /*
1079          * Force the var to be on the left to simplify logic in scalarineqsel.
1080          */
1081         if (varonleft)
1082         {
1083                 /* we have var > other */
1084                 isgt = true;
1085         }
1086         else
1087         {
1088                 /* we have other > var, commute to make var < other */
1089                 operator = get_commutator(operator);
1090                 if (!operator)
1091                 {
1092                         /* Use default selectivity (should we raise an error instead?) */
1093                         ReleaseVariableStats(vardata);
1094                         PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
1095                 }
1096                 isgt = false;
1097         }
1098
1099         selec = scalarineqsel(root, operator, isgt, &vardata, constval, consttype);
1100
1101         ReleaseVariableStats(vardata);
1102
1103         PG_RETURN_FLOAT8((float8) selec);
1104 }
1105
1106 /*
1107  * patternsel                   - Generic code for pattern-match selectivity.
1108  */
1109 static double
1110 patternsel(PG_FUNCTION_ARGS, Pattern_Type ptype, bool negate)
1111 {
1112         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
1113         Oid                     operator = PG_GETARG_OID(1);
1114         List       *args = (List *) PG_GETARG_POINTER(2);
1115         int                     varRelid = PG_GETARG_INT32(3);
1116         Oid                     collation = PG_GET_COLLATION();
1117         VariableStatData vardata;
1118         Node       *other;
1119         bool            varonleft;
1120         Datum           constval;
1121         Oid                     consttype;
1122         Oid                     vartype;
1123         Oid                     opfamily;
1124         Pattern_Prefix_Status pstatus;
1125         Const      *patt;
1126         Const      *prefix = NULL;
1127         Selectivity rest_selec = 0;
1128         double          result;
1129
1130         /*
1131          * If this is for a NOT LIKE or similar operator, get the corresponding
1132          * positive-match operator and work with that.  Set result to the correct
1133          * default estimate, too.
1134          */
1135         if (negate)
1136         {
1137                 operator = get_negator(operator);
1138                 if (!OidIsValid(operator))
1139                         elog(ERROR, "patternsel called for operator without a negator");
1140                 result = 1.0 - DEFAULT_MATCH_SEL;
1141         }
1142         else
1143         {
1144                 result = DEFAULT_MATCH_SEL;
1145         }
1146
1147         /*
1148          * If expression is not variable op constant, then punt and return a
1149          * default estimate.
1150          */
1151         if (!get_restriction_variable(root, args, varRelid,
1152                                                                   &vardata, &other, &varonleft))
1153                 return result;
1154         if (!varonleft || !IsA(other, Const))
1155         {
1156                 ReleaseVariableStats(vardata);
1157                 return result;
1158         }
1159
1160         /*
1161          * If the constant is NULL, assume operator is strict and return zero, ie,
1162          * operator will never return TRUE.  (It's zero even for a negator op.)
1163          */
1164         if (((Const *) other)->constisnull)
1165         {
1166                 ReleaseVariableStats(vardata);
1167                 return 0.0;
1168         }
1169         constval = ((Const *) other)->constvalue;
1170         consttype = ((Const *) other)->consttype;
1171
1172         /*
1173          * The right-hand const is type text or bytea for all supported operators.
1174          * We do not expect to see binary-compatible types here, since
1175          * const-folding should have relabeled the const to exactly match the
1176          * operator's declared type.
1177          */
1178         if (consttype != TEXTOID && consttype != BYTEAOID)
1179         {
1180                 ReleaseVariableStats(vardata);
1181                 return result;
1182         }
1183
1184         /*
1185          * Similarly, the exposed type of the left-hand side should be one of
1186          * those we know.  (Do not look at vardata.atttype, which might be
1187          * something binary-compatible but different.)  We can use it to choose
1188          * the index opfamily from which we must draw the comparison operators.
1189          *
1190          * NOTE: It would be more correct to use the PATTERN opfamilies than the
1191          * simple ones, but at the moment ANALYZE will not generate statistics for
1192          * the PATTERN operators.  But our results are so approximate anyway that
1193          * it probably hardly matters.
1194          */
1195         vartype = vardata.vartype;
1196
1197         switch (vartype)
1198         {
1199                 case TEXTOID:
1200                         opfamily = TEXT_BTREE_FAM_OID;
1201                         break;
1202                 case BPCHAROID:
1203                         opfamily = BPCHAR_BTREE_FAM_OID;
1204                         break;
1205                 case NAMEOID:
1206                         opfamily = NAME_BTREE_FAM_OID;
1207                         break;
1208                 case BYTEAOID:
1209                         opfamily = BYTEA_BTREE_FAM_OID;
1210                         break;
1211                 default:
1212                         ReleaseVariableStats(vardata);
1213                         return result;
1214         }
1215
1216         /*
1217          * Pull out any fixed prefix implied by the pattern, and estimate the
1218          * fractional selectivity of the remainder of the pattern.  Unlike many of
1219          * the other functions in this file, we use the pattern operator's actual
1220          * collation for this step.  This is not because we expect the collation
1221          * to make a big difference in the selectivity estimate (it seldom would),
1222          * but because we want to be sure we cache compiled regexps under the
1223          * right cache key, so that they can be re-used at runtime.
1224          */
1225         patt = (Const *) other;
1226         pstatus = pattern_fixed_prefix(patt, ptype, collation,
1227                                                                    &prefix, &rest_selec);
1228
1229         /*
1230          * If necessary, coerce the prefix constant to the right type.
1231          */
1232         if (prefix && prefix->consttype != vartype)
1233         {
1234                 char       *prefixstr;
1235
1236                 switch (prefix->consttype)
1237                 {
1238                         case TEXTOID:
1239                                 prefixstr = TextDatumGetCString(prefix->constvalue);
1240                                 break;
1241                         case BYTEAOID:
1242                                 prefixstr = DatumGetCString(DirectFunctionCall1(byteaout,
1243                                                                                                                 prefix->constvalue));
1244                                 break;
1245                         default:
1246                                 elog(ERROR, "unrecognized consttype: %u",
1247                                          prefix->consttype);
1248                                 ReleaseVariableStats(vardata);
1249                                 return result;
1250                 }
1251                 prefix = string_to_const(prefixstr, vartype);
1252                 pfree(prefixstr);
1253         }
1254
1255         if (pstatus == Pattern_Prefix_Exact)
1256         {
1257                 /*
1258                  * Pattern specifies an exact match, so pretend operator is '='
1259                  */
1260                 Oid                     eqopr = get_opfamily_member(opfamily, vartype, vartype,
1261                                                                                                 BTEqualStrategyNumber);
1262
1263                 if (eqopr == InvalidOid)
1264                         elog(ERROR, "no = operator for opfamily %u", opfamily);
1265                 result = var_eq_const(&vardata, eqopr, prefix->constvalue,
1266                                                           false, true);
1267         }
1268         else
1269         {
1270                 /*
1271                  * Not exact-match pattern.  If we have a sufficiently large
1272                  * histogram, estimate selectivity for the histogram part of the
1273                  * population by counting matches in the histogram.  If not, estimate
1274                  * selectivity of the fixed prefix and remainder of pattern
1275                  * separately, then combine the two to get an estimate of the
1276                  * selectivity for the part of the column population represented by
1277                  * the histogram.  (For small histograms, we combine these
1278                  * approaches.)
1279                  *
1280                  * We then add up data for any most-common-values values; these are
1281                  * not in the histogram population, and we can get exact answers for
1282                  * them by applying the pattern operator, so there's no reason to
1283                  * approximate.  (If the MCVs cover a significant part of the total
1284                  * population, this gives us a big leg up in accuracy.)
1285                  */
1286                 Selectivity selec;
1287                 int                     hist_size;
1288                 FmgrInfo        opproc;
1289                 double          nullfrac,
1290                                         mcv_selec,
1291                                         sumcommon;
1292
1293                 /* Try to use the histogram entries to get selectivity */
1294                 fmgr_info(get_opcode(operator), &opproc);
1295
1296                 selec = histogram_selectivity(&vardata, &opproc, constval, true,
1297                                                                           10, 1, &hist_size);
1298
1299                 /* If not at least 100 entries, use the heuristic method */
1300                 if (hist_size < 100)
1301                 {
1302                         Selectivity heursel;
1303                         Selectivity prefixsel;
1304
1305                         if (pstatus == Pattern_Prefix_Partial)
1306                                 prefixsel = prefix_selectivity(root, &vardata, vartype,
1307                                                                                            opfamily, prefix);
1308                         else
1309                                 prefixsel = 1.0;
1310                         heursel = prefixsel * rest_selec;
1311
1312                         if (selec < 0)          /* fewer than 10 histogram entries? */
1313                                 selec = heursel;
1314                         else
1315                         {
1316                                 /*
1317                                  * For histogram sizes from 10 to 100, we combine the
1318                                  * histogram and heuristic selectivities, putting increasingly
1319                                  * more trust in the histogram for larger sizes.
1320                                  */
1321                                 double          hist_weight = hist_size / 100.0;
1322
1323                                 selec = selec * hist_weight + heursel * (1.0 - hist_weight);
1324                         }
1325                 }
1326
1327                 /* In any case, don't believe extremely small or large estimates. */
1328                 if (selec < 0.0001)
1329                         selec = 0.0001;
1330                 else if (selec > 0.9999)
1331                         selec = 0.9999;
1332
1333                 /*
1334                  * If we have most-common-values info, add up the fractions of the MCV
1335                  * entries that satisfy MCV OP PATTERN.  These fractions contribute
1336                  * directly to the result selectivity.  Also add up the total fraction
1337                  * represented by MCV entries.
1338                  */
1339                 mcv_selec = mcv_selectivity(&vardata, &opproc, constval, true,
1340                                                                         &sumcommon);
1341
1342                 if (HeapTupleIsValid(vardata.statsTuple))
1343                         nullfrac = ((Form_pg_statistic) GETSTRUCT(vardata.statsTuple))->stanullfrac;
1344                 else
1345                         nullfrac = 0.0;
1346
1347                 /*
1348                  * Now merge the results from the MCV and histogram calculations,
1349                  * realizing that the histogram covers only the non-null values that
1350                  * are not listed in MCV.
1351                  */
1352                 selec *= 1.0 - nullfrac - sumcommon;
1353                 selec += mcv_selec;
1354
1355                 /* result should be in range, but make sure... */
1356                 CLAMP_PROBABILITY(selec);
1357                 result = selec;
1358         }
1359
1360         if (prefix)
1361         {
1362                 pfree(DatumGetPointer(prefix->constvalue));
1363                 pfree(prefix);
1364         }
1365
1366         ReleaseVariableStats(vardata);
1367
1368         return negate ? (1.0 - result) : result;
1369 }
1370
1371 /*
1372  *              regexeqsel              - Selectivity of regular-expression pattern match.
1373  */
1374 Datum
1375 regexeqsel(PG_FUNCTION_ARGS)
1376 {
1377         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex, false));
1378 }
1379
1380 /*
1381  *              icregexeqsel    - Selectivity of case-insensitive regex match.
1382  */
1383 Datum
1384 icregexeqsel(PG_FUNCTION_ARGS)
1385 {
1386         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex_IC, false));
1387 }
1388
1389 /*
1390  *              likesel                 - Selectivity of LIKE pattern match.
1391  */
1392 Datum
1393 likesel(PG_FUNCTION_ARGS)
1394 {
1395         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like, false));
1396 }
1397
1398 /*
1399  *              iclikesel                       - Selectivity of ILIKE pattern match.
1400  */
1401 Datum
1402 iclikesel(PG_FUNCTION_ARGS)
1403 {
1404         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like_IC, false));
1405 }
1406
1407 /*
1408  *              regexnesel              - Selectivity of regular-expression pattern non-match.
1409  */
1410 Datum
1411 regexnesel(PG_FUNCTION_ARGS)
1412 {
1413         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex, true));
1414 }
1415
1416 /*
1417  *              icregexnesel    - Selectivity of case-insensitive regex non-match.
1418  */
1419 Datum
1420 icregexnesel(PG_FUNCTION_ARGS)
1421 {
1422         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Regex_IC, true));
1423 }
1424
1425 /*
1426  *              nlikesel                - Selectivity of LIKE pattern non-match.
1427  */
1428 Datum
1429 nlikesel(PG_FUNCTION_ARGS)
1430 {
1431         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like, true));
1432 }
1433
1434 /*
1435  *              icnlikesel              - Selectivity of ILIKE pattern non-match.
1436  */
1437 Datum
1438 icnlikesel(PG_FUNCTION_ARGS)
1439 {
1440         PG_RETURN_FLOAT8(patternsel(fcinfo, Pattern_Type_Like_IC, true));
1441 }
1442
1443 /*
1444  *              boolvarsel              - Selectivity of Boolean variable.
1445  *
1446  * This can actually be called on any boolean-valued expression.  If it
1447  * involves only Vars of the specified relation, and if there are statistics
1448  * about the Var or expression (the latter is possible if it's indexed) then
1449  * we'll produce a real estimate; otherwise it's just a default.
1450  */
1451 Selectivity
1452 boolvarsel(PlannerInfo *root, Node *arg, int varRelid)
1453 {
1454         VariableStatData vardata;
1455         double          selec;
1456
1457         examine_variable(root, arg, varRelid, &vardata);
1458         if (HeapTupleIsValid(vardata.statsTuple))
1459         {
1460                 /*
1461                  * A boolean variable V is equivalent to the clause V = 't', so we
1462                  * compute the selectivity as if that is what we have.
1463                  */
1464                 selec = var_eq_const(&vardata, BooleanEqualOperator,
1465                                                          BoolGetDatum(true), false, true);
1466         }
1467         else if (is_funcclause(arg))
1468         {
1469                 /*
1470                  * If we have no stats and it's a function call, estimate 0.3333333.
1471                  * This seems a pretty unprincipled choice, but Postgres has been
1472                  * using that estimate for function calls since 1992.  The hoariness
1473                  * of this behavior suggests that we should not be in too much hurry
1474                  * to use another value.
1475                  */
1476                 selec = 0.3333333;
1477         }
1478         else
1479         {
1480                 /* Otherwise, the default estimate is 0.5 */
1481                 selec = 0.5;
1482         }
1483         ReleaseVariableStats(vardata);
1484         return selec;
1485 }
1486
1487 /*
1488  *              booltestsel             - Selectivity of BooleanTest Node.
1489  */
1490 Selectivity
1491 booltestsel(PlannerInfo *root, BoolTestType booltesttype, Node *arg,
1492                         int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
1493 {
1494         VariableStatData vardata;
1495         double          selec;
1496
1497         examine_variable(root, arg, varRelid, &vardata);
1498
1499         if (HeapTupleIsValid(vardata.statsTuple))
1500         {
1501                 Form_pg_statistic stats;
1502                 double          freq_null;
1503                 Datum      *values;
1504                 int                     nvalues;
1505                 float4     *numbers;
1506                 int                     nnumbers;
1507
1508                 stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
1509                 freq_null = stats->stanullfrac;
1510
1511                 if (get_attstatsslot(vardata.statsTuple,
1512                                                          vardata.atttype, vardata.atttypmod,
1513                                                          STATISTIC_KIND_MCV, InvalidOid,
1514                                                          NULL,
1515                                                          &values, &nvalues,
1516                                                          &numbers, &nnumbers)
1517                         && nnumbers > 0)
1518                 {
1519                         double          freq_true;
1520                         double          freq_false;
1521
1522                         /*
1523                          * Get first MCV frequency and derive frequency for true.
1524                          */
1525                         if (DatumGetBool(values[0]))
1526                                 freq_true = numbers[0];
1527                         else
1528                                 freq_true = 1.0 - numbers[0] - freq_null;
1529
1530                         /*
1531                          * Next derive frequency for false. Then use these as appropriate
1532                          * to derive frequency for each case.
1533                          */
1534                         freq_false = 1.0 - freq_true - freq_null;
1535
1536                         switch (booltesttype)
1537                         {
1538                                 case IS_UNKNOWN:
1539                                         /* select only NULL values */
1540                                         selec = freq_null;
1541                                         break;
1542                                 case IS_NOT_UNKNOWN:
1543                                         /* select non-NULL values */
1544                                         selec = 1.0 - freq_null;
1545                                         break;
1546                                 case IS_TRUE:
1547                                         /* select only TRUE values */
1548                                         selec = freq_true;
1549                                         break;
1550                                 case IS_NOT_TRUE:
1551                                         /* select non-TRUE values */
1552                                         selec = 1.0 - freq_true;
1553                                         break;
1554                                 case IS_FALSE:
1555                                         /* select only FALSE values */
1556                                         selec = freq_false;
1557                                         break;
1558                                 case IS_NOT_FALSE:
1559                                         /* select non-FALSE values */
1560                                         selec = 1.0 - freq_false;
1561                                         break;
1562                                 default:
1563                                         elog(ERROR, "unrecognized booltesttype: %d",
1564                                                  (int) booltesttype);
1565                                         selec = 0.0;    /* Keep compiler quiet */
1566                                         break;
1567                         }
1568
1569                         free_attstatsslot(vardata.atttype, values, nvalues,
1570                                                           numbers, nnumbers);
1571                 }
1572                 else
1573                 {
1574                         /*
1575                          * No most-common-value info available. Still have null fraction
1576                          * information, so use it for IS [NOT] UNKNOWN. Otherwise adjust
1577                          * for null fraction and assume a 50-50 split of TRUE and FALSE.
1578                          */
1579                         switch (booltesttype)
1580                         {
1581                                 case IS_UNKNOWN:
1582                                         /* select only NULL values */
1583                                         selec = freq_null;
1584                                         break;
1585                                 case IS_NOT_UNKNOWN:
1586                                         /* select non-NULL values */
1587                                         selec = 1.0 - freq_null;
1588                                         break;
1589                                 case IS_TRUE:
1590                                 case IS_FALSE:
1591                                         /* Assume we select half of the non-NULL values */
1592                                         selec = (1.0 - freq_null) / 2.0;
1593                                         break;
1594                                 case IS_NOT_TRUE:
1595                                 case IS_NOT_FALSE:
1596                                         /* Assume we select NULLs plus half of the non-NULLs */
1597                                         /* equiv. to freq_null + (1.0 - freq_null) / 2.0 */
1598                                         selec = (freq_null + 1.0) / 2.0;
1599                                         break;
1600                                 default:
1601                                         elog(ERROR, "unrecognized booltesttype: %d",
1602                                                  (int) booltesttype);
1603                                         selec = 0.0;    /* Keep compiler quiet */
1604                                         break;
1605                         }
1606                 }
1607         }
1608         else
1609         {
1610                 /*
1611                  * If we can't get variable statistics for the argument, perhaps
1612                  * clause_selectivity can do something with it.  We ignore the
1613                  * possibility of a NULL value when using clause_selectivity, and just
1614                  * assume the value is either TRUE or FALSE.
1615                  */
1616                 switch (booltesttype)
1617                 {
1618                         case IS_UNKNOWN:
1619                                 selec = DEFAULT_UNK_SEL;
1620                                 break;
1621                         case IS_NOT_UNKNOWN:
1622                                 selec = DEFAULT_NOT_UNK_SEL;
1623                                 break;
1624                         case IS_TRUE:
1625                         case IS_NOT_FALSE:
1626                                 selec = (double) clause_selectivity(root, arg,
1627                                                                                                         varRelid,
1628                                                                                                         jointype, sjinfo);
1629                                 break;
1630                         case IS_FALSE:
1631                         case IS_NOT_TRUE:
1632                                 selec = 1.0 - (double) clause_selectivity(root, arg,
1633                                                                                                                   varRelid,
1634                                                                                                                   jointype, sjinfo);
1635                                 break;
1636                         default:
1637                                 elog(ERROR, "unrecognized booltesttype: %d",
1638                                          (int) booltesttype);
1639                                 selec = 0.0;    /* Keep compiler quiet */
1640                                 break;
1641                 }
1642         }
1643
1644         ReleaseVariableStats(vardata);
1645
1646         /* result should be in range, but make sure... */
1647         CLAMP_PROBABILITY(selec);
1648
1649         return (Selectivity) selec;
1650 }
1651
1652 /*
1653  *              nulltestsel             - Selectivity of NullTest Node.
1654  */
1655 Selectivity
1656 nulltestsel(PlannerInfo *root, NullTestType nulltesttype, Node *arg,
1657                         int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
1658 {
1659         VariableStatData vardata;
1660         double          selec;
1661
1662         examine_variable(root, arg, varRelid, &vardata);
1663
1664         if (HeapTupleIsValid(vardata.statsTuple))
1665         {
1666                 Form_pg_statistic stats;
1667                 double          freq_null;
1668
1669                 stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
1670                 freq_null = stats->stanullfrac;
1671
1672                 switch (nulltesttype)
1673                 {
1674                         case IS_NULL:
1675
1676                                 /*
1677                                  * Use freq_null directly.
1678                                  */
1679                                 selec = freq_null;
1680                                 break;
1681                         case IS_NOT_NULL:
1682
1683                                 /*
1684                                  * Select not unknown (not null) values. Calculate from
1685                                  * freq_null.
1686                                  */
1687                                 selec = 1.0 - freq_null;
1688                                 break;
1689                         default:
1690                                 elog(ERROR, "unrecognized nulltesttype: %d",
1691                                          (int) nulltesttype);
1692                                 return (Selectivity) 0; /* keep compiler quiet */
1693                 }
1694         }
1695         else
1696         {
1697                 /*
1698                  * No ANALYZE stats available, so make a guess
1699                  */
1700                 switch (nulltesttype)
1701                 {
1702                         case IS_NULL:
1703                                 selec = DEFAULT_UNK_SEL;
1704                                 break;
1705                         case IS_NOT_NULL:
1706                                 selec = DEFAULT_NOT_UNK_SEL;
1707                                 break;
1708                         default:
1709                                 elog(ERROR, "unrecognized nulltesttype: %d",
1710                                          (int) nulltesttype);
1711                                 return (Selectivity) 0; /* keep compiler quiet */
1712                 }
1713         }
1714
1715         ReleaseVariableStats(vardata);
1716
1717         /* result should be in range, but make sure... */
1718         CLAMP_PROBABILITY(selec);
1719
1720         return (Selectivity) selec;
1721 }
1722
1723 /*
1724  * strip_array_coercion - strip binary-compatible relabeling from an array expr
1725  *
1726  * For array values, the parser normally generates ArrayCoerceExpr conversions,
1727  * but it seems possible that RelabelType might show up.  Also, the planner
1728  * is not currently tense about collapsing stacked ArrayCoerceExpr nodes,
1729  * so we need to be ready to deal with more than one level.
1730  */
1731 static Node *
1732 strip_array_coercion(Node *node)
1733 {
1734         for (;;)
1735         {
1736                 if (node && IsA(node, ArrayCoerceExpr) &&
1737                         ((ArrayCoerceExpr *) node)->elemfuncid == InvalidOid)
1738                 {
1739                         node = (Node *) ((ArrayCoerceExpr *) node)->arg;
1740                 }
1741                 else if (node && IsA(node, RelabelType))
1742                 {
1743                         /* We don't really expect this case, but may as well cope */
1744                         node = (Node *) ((RelabelType *) node)->arg;
1745                 }
1746                 else
1747                         break;
1748         }
1749         return node;
1750 }
1751
1752 /*
1753  *              scalararraysel          - Selectivity of ScalarArrayOpExpr Node.
1754  */
1755 Selectivity
1756 scalararraysel(PlannerInfo *root,
1757                            ScalarArrayOpExpr *clause,
1758                            bool is_join_clause,
1759                            int varRelid,
1760                            JoinType jointype,
1761                            SpecialJoinInfo *sjinfo)
1762 {
1763         Oid                     operator = clause->opno;
1764         bool            useOr = clause->useOr;
1765         bool            isEquality = false;
1766         bool            isInequality = false;
1767         Node       *leftop;
1768         Node       *rightop;
1769         Oid                     nominal_element_type;
1770         Oid                     nominal_element_collation;
1771         TypeCacheEntry *typentry;
1772         RegProcedure oprsel;
1773         FmgrInfo        oprselproc;
1774         Selectivity s1;
1775         Selectivity s1disjoint;
1776
1777         /* First, deconstruct the expression */
1778         Assert(list_length(clause->args) == 2);
1779         leftop = (Node *) linitial(clause->args);
1780         rightop = (Node *) lsecond(clause->args);
1781
1782         /* aggressively reduce both sides to constants */
1783         leftop = estimate_expression_value(root, leftop);
1784         rightop = estimate_expression_value(root, rightop);
1785
1786         /* get nominal (after relabeling) element type of rightop */
1787         nominal_element_type = get_base_element_type(exprType(rightop));
1788         if (!OidIsValid(nominal_element_type))
1789                 return (Selectivity) 0.5;               /* probably shouldn't happen */
1790         /* get nominal collation, too, for generating constants */
1791         nominal_element_collation = exprCollation(rightop);
1792
1793         /* look through any binary-compatible relabeling of rightop */
1794         rightop = strip_array_coercion(rightop);
1795
1796         /*
1797          * Detect whether the operator is the default equality or inequality
1798          * operator of the array element type.
1799          */
1800         typentry = lookup_type_cache(nominal_element_type, TYPECACHE_EQ_OPR);
1801         if (OidIsValid(typentry->eq_opr))
1802         {
1803                 if (operator == typentry->eq_opr)
1804                         isEquality = true;
1805                 else if (get_negator(operator) == typentry->eq_opr)
1806                         isInequality = true;
1807         }
1808
1809         /*
1810          * If it is equality or inequality, we might be able to estimate this as a
1811          * form of array containment; for instance "const = ANY(column)" can be
1812          * treated as "ARRAY[const] <@ column".  scalararraysel_containment tries
1813          * that, and returns the selectivity estimate if successful, or -1 if not.
1814          */
1815         if ((isEquality || isInequality) && !is_join_clause)
1816         {
1817                 s1 = scalararraysel_containment(root, leftop, rightop,
1818                                                                                 nominal_element_type,
1819                                                                                 isEquality, useOr, varRelid);
1820                 if (s1 >= 0.0)
1821                         return s1;
1822         }
1823
1824         /*
1825          * Look up the underlying operator's selectivity estimator. Punt if it
1826          * hasn't got one.
1827          */
1828         if (is_join_clause)
1829                 oprsel = get_oprjoin(operator);
1830         else
1831                 oprsel = get_oprrest(operator);
1832         if (!oprsel)
1833                 return (Selectivity) 0.5;
1834         fmgr_info(oprsel, &oprselproc);
1835
1836         /*
1837          * In the array-containment check above, we must only believe that an
1838          * operator is equality or inequality if it is the default btree equality
1839          * operator (or its negator) for the element type, since those are the
1840          * operators that array containment will use.  But in what follows, we can
1841          * be a little laxer, and also believe that any operators using eqsel() or
1842          * neqsel() as selectivity estimator act like equality or inequality.
1843          */
1844         if (oprsel == F_EQSEL || oprsel == F_EQJOINSEL)
1845                 isEquality = true;
1846         else if (oprsel == F_NEQSEL || oprsel == F_NEQJOINSEL)
1847                 isInequality = true;
1848
1849         /*
1850          * We consider three cases:
1851          *
1852          * 1. rightop is an Array constant: deconstruct the array, apply the
1853          * operator's selectivity function for each array element, and merge the
1854          * results in the same way that clausesel.c does for AND/OR combinations.
1855          *
1856          * 2. rightop is an ARRAY[] construct: apply the operator's selectivity
1857          * function for each element of the ARRAY[] construct, and merge.
1858          *
1859          * 3. otherwise, make a guess ...
1860          */
1861         if (rightop && IsA(rightop, Const))
1862         {
1863                 Datum           arraydatum = ((Const *) rightop)->constvalue;
1864                 bool            arrayisnull = ((Const *) rightop)->constisnull;
1865                 ArrayType  *arrayval;
1866                 int16           elmlen;
1867                 bool            elmbyval;
1868                 char            elmalign;
1869                 int                     num_elems;
1870                 Datum      *elem_values;
1871                 bool       *elem_nulls;
1872                 int                     i;
1873
1874                 if (arrayisnull)                /* qual can't succeed if null array */
1875                         return (Selectivity) 0.0;
1876                 arrayval = DatumGetArrayTypeP(arraydatum);
1877                 get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
1878                                                          &elmlen, &elmbyval, &elmalign);
1879                 deconstruct_array(arrayval,
1880                                                   ARR_ELEMTYPE(arrayval),
1881                                                   elmlen, elmbyval, elmalign,
1882                                                   &elem_values, &elem_nulls, &num_elems);
1883
1884                 /*
1885                  * For generic operators, we assume the probability of success is
1886                  * independent for each array element.  But for "= ANY" or "<> ALL",
1887                  * if the array elements are distinct (which'd typically be the case)
1888                  * then the probabilities are disjoint, and we should just sum them.
1889                  *
1890                  * If we were being really tense we would try to confirm that the
1891                  * elements are all distinct, but that would be expensive and it
1892                  * doesn't seem to be worth the cycles; it would amount to penalizing
1893                  * well-written queries in favor of poorly-written ones.  However, we
1894                  * do protect ourselves a little bit by checking whether the
1895                  * disjointness assumption leads to an impossible (out of range)
1896                  * probability; if so, we fall back to the normal calculation.
1897                  */
1898                 s1 = s1disjoint = (useOr ? 0.0 : 1.0);
1899
1900                 for (i = 0; i < num_elems; i++)
1901                 {
1902                         List       *args;
1903                         Selectivity s2;
1904
1905                         args = list_make2(leftop,
1906                                                           makeConst(nominal_element_type,
1907                                                                                 -1,
1908                                                                                 nominal_element_collation,
1909                                                                                 elmlen,
1910                                                                                 elem_values[i],
1911                                                                                 elem_nulls[i],
1912                                                                                 elmbyval));
1913                         if (is_join_clause)
1914                                 s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
1915                                                                                                           clause->inputcollid,
1916                                                                                                           PointerGetDatum(root),
1917                                                                                                   ObjectIdGetDatum(operator),
1918                                                                                                           PointerGetDatum(args),
1919                                                                                                           Int16GetDatum(jointype),
1920                                                                                                    PointerGetDatum(sjinfo)));
1921                         else
1922                                 s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
1923                                                                                                           clause->inputcollid,
1924                                                                                                           PointerGetDatum(root),
1925                                                                                                   ObjectIdGetDatum(operator),
1926                                                                                                           PointerGetDatum(args),
1927                                                                                                    Int32GetDatum(varRelid)));
1928
1929                         if (useOr)
1930                         {
1931                                 s1 = s1 + s2 - s1 * s2;
1932                                 if (isEquality)
1933                                         s1disjoint += s2;
1934                         }
1935                         else
1936                         {
1937                                 s1 = s1 * s2;
1938                                 if (isInequality)
1939                                         s1disjoint += s2 - 1.0;
1940                         }
1941                 }
1942
1943                 /* accept disjoint-probability estimate if in range */
1944                 if ((useOr ? isEquality : isInequality) &&
1945                         s1disjoint >= 0.0 && s1disjoint <= 1.0)
1946                         s1 = s1disjoint;
1947         }
1948         else if (rightop && IsA(rightop, ArrayExpr) &&
1949                          !((ArrayExpr *) rightop)->multidims)
1950         {
1951                 ArrayExpr  *arrayexpr = (ArrayExpr *) rightop;
1952                 int16           elmlen;
1953                 bool            elmbyval;
1954                 ListCell   *l;
1955
1956                 get_typlenbyval(arrayexpr->element_typeid,
1957                                                 &elmlen, &elmbyval);
1958
1959                 /*
1960                  * We use the assumption of disjoint probabilities here too, although
1961                  * the odds of equal array elements are rather higher if the elements
1962                  * are not all constants (which they won't be, else constant folding
1963                  * would have reduced the ArrayExpr to a Const).  In this path it's
1964                  * critical to have the sanity check on the s1disjoint estimate.
1965                  */
1966                 s1 = s1disjoint = (useOr ? 0.0 : 1.0);
1967
1968                 foreach(l, arrayexpr->elements)
1969                 {
1970                         Node       *elem = (Node *) lfirst(l);
1971                         List       *args;
1972                         Selectivity s2;
1973
1974                         /*
1975                          * Theoretically, if elem isn't of nominal_element_type we should
1976                          * insert a RelabelType, but it seems unlikely that any operator
1977                          * estimation function would really care ...
1978                          */
1979                         args = list_make2(leftop, elem);
1980                         if (is_join_clause)
1981                                 s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
1982                                                                                                           clause->inputcollid,
1983                                                                                                           PointerGetDatum(root),
1984                                                                                                   ObjectIdGetDatum(operator),
1985                                                                                                           PointerGetDatum(args),
1986                                                                                                           Int16GetDatum(jointype),
1987                                                                                                    PointerGetDatum(sjinfo)));
1988                         else
1989                                 s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
1990                                                                                                           clause->inputcollid,
1991                                                                                                           PointerGetDatum(root),
1992                                                                                                   ObjectIdGetDatum(operator),
1993                                                                                                           PointerGetDatum(args),
1994                                                                                                    Int32GetDatum(varRelid)));
1995
1996                         if (useOr)
1997                         {
1998                                 s1 = s1 + s2 - s1 * s2;
1999                                 if (isEquality)
2000                                         s1disjoint += s2;
2001                         }
2002                         else
2003                         {
2004                                 s1 = s1 * s2;
2005                                 if (isInequality)
2006                                         s1disjoint += s2 - 1.0;
2007                         }
2008                 }
2009
2010                 /* accept disjoint-probability estimate if in range */
2011                 if ((useOr ? isEquality : isInequality) &&
2012                         s1disjoint >= 0.0 && s1disjoint <= 1.0)
2013                         s1 = s1disjoint;
2014         }
2015         else
2016         {
2017                 CaseTestExpr *dummyexpr;
2018                 List       *args;
2019                 Selectivity s2;
2020                 int                     i;
2021
2022                 /*
2023                  * We need a dummy rightop to pass to the operator selectivity
2024                  * routine.  It can be pretty much anything that doesn't look like a
2025                  * constant; CaseTestExpr is a convenient choice.
2026                  */
2027                 dummyexpr = makeNode(CaseTestExpr);
2028                 dummyexpr->typeId = nominal_element_type;
2029                 dummyexpr->typeMod = -1;
2030                 dummyexpr->collation = clause->inputcollid;
2031                 args = list_make2(leftop, dummyexpr);
2032                 if (is_join_clause)
2033                         s2 = DatumGetFloat8(FunctionCall5Coll(&oprselproc,
2034                                                                                                   clause->inputcollid,
2035                                                                                                   PointerGetDatum(root),
2036                                                                                                   ObjectIdGetDatum(operator),
2037                                                                                                   PointerGetDatum(args),
2038                                                                                                   Int16GetDatum(jointype),
2039                                                                                                   PointerGetDatum(sjinfo)));
2040                 else
2041                         s2 = DatumGetFloat8(FunctionCall4Coll(&oprselproc,
2042                                                                                                   clause->inputcollid,
2043                                                                                                   PointerGetDatum(root),
2044                                                                                                   ObjectIdGetDatum(operator),
2045                                                                                                   PointerGetDatum(args),
2046                                                                                                   Int32GetDatum(varRelid)));
2047                 s1 = useOr ? 0.0 : 1.0;
2048
2049                 /*
2050                  * Arbitrarily assume 10 elements in the eventual array value (see
2051                  * also estimate_array_length).  We don't risk an assumption of
2052                  * disjoint probabilities here.
2053                  */
2054                 for (i = 0; i < 10; i++)
2055                 {
2056                         if (useOr)
2057                                 s1 = s1 + s2 - s1 * s2;
2058                         else
2059                                 s1 = s1 * s2;
2060                 }
2061         }
2062
2063         /* result should be in range, but make sure... */
2064         CLAMP_PROBABILITY(s1);
2065
2066         return s1;
2067 }
2068
2069 /*
2070  * Estimate number of elements in the array yielded by an expression.
2071  *
2072  * It's important that this agree with scalararraysel.
2073  */
2074 int
2075 estimate_array_length(Node *arrayexpr)
2076 {
2077         /* look through any binary-compatible relabeling of arrayexpr */
2078         arrayexpr = strip_array_coercion(arrayexpr);
2079
2080         if (arrayexpr && IsA(arrayexpr, Const))
2081         {
2082                 Datum           arraydatum = ((Const *) arrayexpr)->constvalue;
2083                 bool            arrayisnull = ((Const *) arrayexpr)->constisnull;
2084                 ArrayType  *arrayval;
2085
2086                 if (arrayisnull)
2087                         return 0;
2088                 arrayval = DatumGetArrayTypeP(arraydatum);
2089                 return ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
2090         }
2091         else if (arrayexpr && IsA(arrayexpr, ArrayExpr) &&
2092                          !((ArrayExpr *) arrayexpr)->multidims)
2093         {
2094                 return list_length(((ArrayExpr *) arrayexpr)->elements);
2095         }
2096         else
2097         {
2098                 /* default guess --- see also scalararraysel */
2099                 return 10;
2100         }
2101 }
2102
2103 /*
2104  *              rowcomparesel           - Selectivity of RowCompareExpr Node.
2105  *
2106  * We estimate RowCompare selectivity by considering just the first (high
2107  * order) columns, which makes it equivalent to an ordinary OpExpr.  While
2108  * this estimate could be refined by considering additional columns, it
2109  * seems unlikely that we could do a lot better without multi-column
2110  * statistics.
2111  */
2112 Selectivity
2113 rowcomparesel(PlannerInfo *root,
2114                           RowCompareExpr *clause,
2115                           int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
2116 {
2117         Selectivity s1;
2118         Oid                     opno = linitial_oid(clause->opnos);
2119         Oid                     inputcollid = linitial_oid(clause->inputcollids);
2120         List       *opargs;
2121         bool            is_join_clause;
2122
2123         /* Build equivalent arg list for single operator */
2124         opargs = list_make2(linitial(clause->largs), linitial(clause->rargs));
2125
2126         /*
2127          * Decide if it's a join clause.  This should match clausesel.c's
2128          * treat_as_join_clause(), except that we intentionally consider only the
2129          * leading columns and not the rest of the clause.
2130          */
2131         if (varRelid != 0)
2132         {
2133                 /*
2134                  * Caller is forcing restriction mode (eg, because we are examining an
2135                  * inner indexscan qual).
2136                  */
2137                 is_join_clause = false;
2138         }
2139         else if (sjinfo == NULL)
2140         {
2141                 /*
2142                  * It must be a restriction clause, since it's being evaluated at a
2143                  * scan node.
2144                  */
2145                 is_join_clause = false;
2146         }
2147         else
2148         {
2149                 /*
2150                  * Otherwise, it's a join if there's more than one relation used.
2151                  */
2152                 is_join_clause = (NumRelids((Node *) opargs) > 1);
2153         }
2154
2155         if (is_join_clause)
2156         {
2157                 /* Estimate selectivity for a join clause. */
2158                 s1 = join_selectivity(root, opno,
2159                                                           opargs,
2160                                                           inputcollid,
2161                                                           jointype,
2162                                                           sjinfo);
2163         }
2164         else
2165         {
2166                 /* Estimate selectivity for a restriction clause. */
2167                 s1 = restriction_selectivity(root, opno,
2168                                                                          opargs,
2169                                                                          inputcollid,
2170                                                                          varRelid);
2171         }
2172
2173         return s1;
2174 }
2175
2176 /*
2177  *              eqjoinsel               - Join selectivity of "="
2178  */
2179 Datum
2180 eqjoinsel(PG_FUNCTION_ARGS)
2181 {
2182         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
2183         Oid                     operator = PG_GETARG_OID(1);
2184         List       *args = (List *) PG_GETARG_POINTER(2);
2185
2186 #ifdef NOT_USED
2187         JoinType        jointype = (JoinType) PG_GETARG_INT16(3);
2188 #endif
2189         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) PG_GETARG_POINTER(4);
2190         double          selec;
2191         VariableStatData vardata1;
2192         VariableStatData vardata2;
2193         bool            join_is_reversed;
2194         RelOptInfo *inner_rel;
2195
2196         get_join_variables(root, args, sjinfo,
2197                                            &vardata1, &vardata2, &join_is_reversed);
2198
2199         switch (sjinfo->jointype)
2200         {
2201                 case JOIN_INNER:
2202                 case JOIN_LEFT:
2203                 case JOIN_FULL:
2204                         selec = eqjoinsel_inner(operator, &vardata1, &vardata2);
2205                         break;
2206                 case JOIN_SEMI:
2207                 case JOIN_ANTI:
2208
2209                         /*
2210                          * Look up the join's inner relation.  min_righthand is sufficient
2211                          * information because neither SEMI nor ANTI joins permit any
2212                          * reassociation into or out of their RHS, so the righthand will
2213                          * always be exactly that set of rels.
2214                          */
2215                         inner_rel = find_join_input_rel(root, sjinfo->min_righthand);
2216
2217                         if (!join_is_reversed)
2218                                 selec = eqjoinsel_semi(operator, &vardata1, &vardata2,
2219                                                                            inner_rel);
2220                         else
2221                                 selec = eqjoinsel_semi(get_commutator(operator),
2222                                                                            &vardata2, &vardata1,
2223                                                                            inner_rel);
2224                         break;
2225                 default:
2226                         /* other values not expected here */
2227                         elog(ERROR, "unrecognized join type: %d",
2228                                  (int) sjinfo->jointype);
2229                         selec = 0;                      /* keep compiler quiet */
2230                         break;
2231         }
2232
2233         ReleaseVariableStats(vardata1);
2234         ReleaseVariableStats(vardata2);
2235
2236         CLAMP_PROBABILITY(selec);
2237
2238         PG_RETURN_FLOAT8((float8) selec);
2239 }
2240
2241 /*
2242  * eqjoinsel_inner --- eqjoinsel for normal inner join
2243  *
2244  * We also use this for LEFT/FULL outer joins; it's not presently clear
2245  * that it's worth trying to distinguish them here.
2246  */
2247 static double
2248 eqjoinsel_inner(Oid operator,
2249                                 VariableStatData *vardata1, VariableStatData *vardata2)
2250 {
2251         double          selec;
2252         double          nd1;
2253         double          nd2;
2254         bool            isdefault1;
2255         bool            isdefault2;
2256         Form_pg_statistic stats1 = NULL;
2257         Form_pg_statistic stats2 = NULL;
2258         bool            have_mcvs1 = false;
2259         Datum      *values1 = NULL;
2260         int                     nvalues1 = 0;
2261         float4     *numbers1 = NULL;
2262         int                     nnumbers1 = 0;
2263         bool            have_mcvs2 = false;
2264         Datum      *values2 = NULL;
2265         int                     nvalues2 = 0;
2266         float4     *numbers2 = NULL;
2267         int                     nnumbers2 = 0;
2268
2269         nd1 = get_variable_numdistinct(vardata1, &isdefault1);
2270         nd2 = get_variable_numdistinct(vardata2, &isdefault2);
2271
2272         if (HeapTupleIsValid(vardata1->statsTuple))
2273         {
2274                 stats1 = (Form_pg_statistic) GETSTRUCT(vardata1->statsTuple);
2275                 have_mcvs1 = get_attstatsslot(vardata1->statsTuple,
2276                                                                           vardata1->atttype,
2277                                                                           vardata1->atttypmod,
2278                                                                           STATISTIC_KIND_MCV,
2279                                                                           InvalidOid,
2280                                                                           NULL,
2281                                                                           &values1, &nvalues1,
2282                                                                           &numbers1, &nnumbers1);
2283         }
2284
2285         if (HeapTupleIsValid(vardata2->statsTuple))
2286         {
2287                 stats2 = (Form_pg_statistic) GETSTRUCT(vardata2->statsTuple);
2288                 have_mcvs2 = get_attstatsslot(vardata2->statsTuple,
2289                                                                           vardata2->atttype,
2290                                                                           vardata2->atttypmod,
2291                                                                           STATISTIC_KIND_MCV,
2292                                                                           InvalidOid,
2293                                                                           NULL,
2294                                                                           &values2, &nvalues2,
2295                                                                           &numbers2, &nnumbers2);
2296         }
2297
2298         if (have_mcvs1 && have_mcvs2)
2299         {
2300                 /*
2301                  * We have most-common-value lists for both relations.  Run through
2302                  * the lists to see which MCVs actually join to each other with the
2303                  * given operator.  This allows us to determine the exact join
2304                  * selectivity for the portion of the relations represented by the MCV
2305                  * lists.  We still have to estimate for the remaining population, but
2306                  * in a skewed distribution this gives us a big leg up in accuracy.
2307                  * For motivation see the analysis in Y. Ioannidis and S.
2308                  * Christodoulakis, "On the propagation of errors in the size of join
2309                  * results", Technical Report 1018, Computer Science Dept., University
2310                  * of Wisconsin, Madison, March 1991 (available from ftp.cs.wisc.edu).
2311                  */
2312                 FmgrInfo        eqproc;
2313                 bool       *hasmatch1;
2314                 bool       *hasmatch2;
2315                 double          nullfrac1 = stats1->stanullfrac;
2316                 double          nullfrac2 = stats2->stanullfrac;
2317                 double          matchprodfreq,
2318                                         matchfreq1,
2319                                         matchfreq2,
2320                                         unmatchfreq1,
2321                                         unmatchfreq2,
2322                                         otherfreq1,
2323                                         otherfreq2,
2324                                         totalsel1,
2325                                         totalsel2;
2326                 int                     i,
2327                                         nmatches;
2328
2329                 fmgr_info(get_opcode(operator), &eqproc);
2330                 hasmatch1 = (bool *) palloc0(nvalues1 * sizeof(bool));
2331                 hasmatch2 = (bool *) palloc0(nvalues2 * sizeof(bool));
2332
2333                 /*
2334                  * Note we assume that each MCV will match at most one member of the
2335                  * other MCV list.  If the operator isn't really equality, there could
2336                  * be multiple matches --- but we don't look for them, both for speed
2337                  * and because the math wouldn't add up...
2338                  */
2339                 matchprodfreq = 0.0;
2340                 nmatches = 0;
2341                 for (i = 0; i < nvalues1; i++)
2342                 {
2343                         int                     j;
2344
2345                         for (j = 0; j < nvalues2; j++)
2346                         {
2347                                 if (hasmatch2[j])
2348                                         continue;
2349                                 if (DatumGetBool(FunctionCall2Coll(&eqproc,
2350                                                                                                    DEFAULT_COLLATION_OID,
2351                                                                                                    values1[i],
2352                                                                                                    values2[j])))
2353                                 {
2354                                         hasmatch1[i] = hasmatch2[j] = true;
2355                                         matchprodfreq += numbers1[i] * numbers2[j];
2356                                         nmatches++;
2357                                         break;
2358                                 }
2359                         }
2360                 }
2361                 CLAMP_PROBABILITY(matchprodfreq);
2362                 /* Sum up frequencies of matched and unmatched MCVs */
2363                 matchfreq1 = unmatchfreq1 = 0.0;
2364                 for (i = 0; i < nvalues1; i++)
2365                 {
2366                         if (hasmatch1[i])
2367                                 matchfreq1 += numbers1[i];
2368                         else
2369                                 unmatchfreq1 += numbers1[i];
2370                 }
2371                 CLAMP_PROBABILITY(matchfreq1);
2372                 CLAMP_PROBABILITY(unmatchfreq1);
2373                 matchfreq2 = unmatchfreq2 = 0.0;
2374                 for (i = 0; i < nvalues2; i++)
2375                 {
2376                         if (hasmatch2[i])
2377                                 matchfreq2 += numbers2[i];
2378                         else
2379                                 unmatchfreq2 += numbers2[i];
2380                 }
2381                 CLAMP_PROBABILITY(matchfreq2);
2382                 CLAMP_PROBABILITY(unmatchfreq2);
2383                 pfree(hasmatch1);
2384                 pfree(hasmatch2);
2385
2386                 /*
2387                  * Compute total frequency of non-null values that are not in the MCV
2388                  * lists.
2389                  */
2390                 otherfreq1 = 1.0 - nullfrac1 - matchfreq1 - unmatchfreq1;
2391                 otherfreq2 = 1.0 - nullfrac2 - matchfreq2 - unmatchfreq2;
2392                 CLAMP_PROBABILITY(otherfreq1);
2393                 CLAMP_PROBABILITY(otherfreq2);
2394
2395                 /*
2396                  * We can estimate the total selectivity from the point of view of
2397                  * relation 1 as: the known selectivity for matched MCVs, plus
2398                  * unmatched MCVs that are assumed to match against random members of
2399                  * relation 2's non-MCV population, plus non-MCV values that are
2400                  * assumed to match against random members of relation 2's unmatched
2401                  * MCVs plus non-MCV values.
2402                  */
2403                 totalsel1 = matchprodfreq;
2404                 if (nd2 > nvalues2)
2405                         totalsel1 += unmatchfreq1 * otherfreq2 / (nd2 - nvalues2);
2406                 if (nd2 > nmatches)
2407                         totalsel1 += otherfreq1 * (otherfreq2 + unmatchfreq2) /
2408                                 (nd2 - nmatches);
2409                 /* Same estimate from the point of view of relation 2. */
2410                 totalsel2 = matchprodfreq;
2411                 if (nd1 > nvalues1)
2412                         totalsel2 += unmatchfreq2 * otherfreq1 / (nd1 - nvalues1);
2413                 if (nd1 > nmatches)
2414                         totalsel2 += otherfreq2 * (otherfreq1 + unmatchfreq1) /
2415                                 (nd1 - nmatches);
2416
2417                 /*
2418                  * Use the smaller of the two estimates.  This can be justified in
2419                  * essentially the same terms as given below for the no-stats case: to
2420                  * a first approximation, we are estimating from the point of view of
2421                  * the relation with smaller nd.
2422                  */
2423                 selec = (totalsel1 < totalsel2) ? totalsel1 : totalsel2;
2424         }
2425         else
2426         {
2427                 /*
2428                  * We do not have MCV lists for both sides.  Estimate the join
2429                  * selectivity as MIN(1/nd1,1/nd2)*(1-nullfrac1)*(1-nullfrac2). This
2430                  * is plausible if we assume that the join operator is strict and the
2431                  * non-null values are about equally distributed: a given non-null
2432                  * tuple of rel1 will join to either zero or N2*(1-nullfrac2)/nd2 rows
2433                  * of rel2, so total join rows are at most
2434                  * N1*(1-nullfrac1)*N2*(1-nullfrac2)/nd2 giving a join selectivity of
2435                  * not more than (1-nullfrac1)*(1-nullfrac2)/nd2. By the same logic it
2436                  * is not more than (1-nullfrac1)*(1-nullfrac2)/nd1, so the expression
2437                  * with MIN() is an upper bound.  Using the MIN() means we estimate
2438                  * from the point of view of the relation with smaller nd (since the
2439                  * larger nd is determining the MIN).  It is reasonable to assume that
2440                  * most tuples in this rel will have join partners, so the bound is
2441                  * probably reasonably tight and should be taken as-is.
2442                  *
2443                  * XXX Can we be smarter if we have an MCV list for just one side? It
2444                  * seems that if we assume equal distribution for the other side, we
2445                  * end up with the same answer anyway.
2446                  */
2447                 double          nullfrac1 = stats1 ? stats1->stanullfrac : 0.0;
2448                 double          nullfrac2 = stats2 ? stats2->stanullfrac : 0.0;
2449
2450                 selec = (1.0 - nullfrac1) * (1.0 - nullfrac2);
2451                 if (nd1 > nd2)
2452                         selec /= nd1;
2453                 else
2454                         selec /= nd2;
2455         }
2456
2457         if (have_mcvs1)
2458                 free_attstatsslot(vardata1->atttype, values1, nvalues1,
2459                                                   numbers1, nnumbers1);
2460         if (have_mcvs2)
2461                 free_attstatsslot(vardata2->atttype, values2, nvalues2,
2462                                                   numbers2, nnumbers2);
2463
2464         return selec;
2465 }
2466
2467 /*
2468  * eqjoinsel_semi --- eqjoinsel for semi join
2469  *
2470  * (Also used for anti join, which we are supposed to estimate the same way.)
2471  * Caller has ensured that vardata1 is the LHS variable.
2472  */
2473 static double
2474 eqjoinsel_semi(Oid operator,
2475                            VariableStatData *vardata1, VariableStatData *vardata2,
2476                            RelOptInfo *inner_rel)
2477 {
2478         double          selec;
2479         double          nd1;
2480         double          nd2;
2481         bool            isdefault1;
2482         bool            isdefault2;
2483         Form_pg_statistic stats1 = NULL;
2484         bool            have_mcvs1 = false;
2485         Datum      *values1 = NULL;
2486         int                     nvalues1 = 0;
2487         float4     *numbers1 = NULL;
2488         int                     nnumbers1 = 0;
2489         bool            have_mcvs2 = false;
2490         Datum      *values2 = NULL;
2491         int                     nvalues2 = 0;
2492         float4     *numbers2 = NULL;
2493         int                     nnumbers2 = 0;
2494
2495         nd1 = get_variable_numdistinct(vardata1, &isdefault1);
2496         nd2 = get_variable_numdistinct(vardata2, &isdefault2);
2497
2498         /*
2499          * We clamp nd2 to be not more than what we estimate the inner relation's
2500          * size to be.  This is intuitively somewhat reasonable since obviously
2501          * there can't be more than that many distinct values coming from the
2502          * inner rel.  The reason for the asymmetry (ie, that we don't clamp nd1
2503          * likewise) is that this is the only pathway by which restriction clauses
2504          * applied to the inner rel will affect the join result size estimate,
2505          * since set_joinrel_size_estimates will multiply SEMI/ANTI selectivity by
2506          * only the outer rel's size.  If we clamped nd1 we'd be double-counting
2507          * the selectivity of outer-rel restrictions.
2508          *
2509          * We can apply this clamping both with respect to the base relation from
2510          * which the join variable comes (if there is just one), and to the
2511          * immediate inner input relation of the current join.
2512          */
2513         if (vardata2->rel)
2514                 nd2 = Min(nd2, vardata2->rel->rows);
2515         nd2 = Min(nd2, inner_rel->rows);
2516
2517         if (HeapTupleIsValid(vardata1->statsTuple))
2518         {
2519                 stats1 = (Form_pg_statistic) GETSTRUCT(vardata1->statsTuple);
2520                 have_mcvs1 = get_attstatsslot(vardata1->statsTuple,
2521                                                                           vardata1->atttype,
2522                                                                           vardata1->atttypmod,
2523                                                                           STATISTIC_KIND_MCV,
2524                                                                           InvalidOid,
2525                                                                           NULL,
2526                                                                           &values1, &nvalues1,
2527                                                                           &numbers1, &nnumbers1);
2528         }
2529
2530         if (HeapTupleIsValid(vardata2->statsTuple))
2531         {
2532                 have_mcvs2 = get_attstatsslot(vardata2->statsTuple,
2533                                                                           vardata2->atttype,
2534                                                                           vardata2->atttypmod,
2535                                                                           STATISTIC_KIND_MCV,
2536                                                                           InvalidOid,
2537                                                                           NULL,
2538                                                                           &values2, &nvalues2,
2539                                                                           &numbers2, &nnumbers2);
2540         }
2541
2542         if (have_mcvs1 && have_mcvs2 && OidIsValid(operator))
2543         {
2544                 /*
2545                  * We have most-common-value lists for both relations.  Run through
2546                  * the lists to see which MCVs actually join to each other with the
2547                  * given operator.  This allows us to determine the exact join
2548                  * selectivity for the portion of the relations represented by the MCV
2549                  * lists.  We still have to estimate for the remaining population, but
2550                  * in a skewed distribution this gives us a big leg up in accuracy.
2551                  */
2552                 FmgrInfo        eqproc;
2553                 bool       *hasmatch1;
2554                 bool       *hasmatch2;
2555                 double          nullfrac1 = stats1->stanullfrac;
2556                 double          matchfreq1,
2557                                         uncertainfrac,
2558                                         uncertain;
2559                 int                     i,
2560                                         nmatches,
2561                                         clamped_nvalues2;
2562
2563                 /*
2564                  * The clamping above could have resulted in nd2 being less than
2565                  * nvalues2; in which case, we assume that precisely the nd2 most
2566                  * common values in the relation will appear in the join input, and so
2567                  * compare to only the first nd2 members of the MCV list.  Of course
2568                  * this is frequently wrong, but it's the best bet we can make.
2569                  */
2570                 clamped_nvalues2 = Min(nvalues2, nd2);
2571
2572                 fmgr_info(get_opcode(operator), &eqproc);
2573                 hasmatch1 = (bool *) palloc0(nvalues1 * sizeof(bool));
2574                 hasmatch2 = (bool *) palloc0(clamped_nvalues2 * sizeof(bool));
2575
2576                 /*
2577                  * Note we assume that each MCV will match at most one member of the
2578                  * other MCV list.  If the operator isn't really equality, there could
2579                  * be multiple matches --- but we don't look for them, both for speed
2580                  * and because the math wouldn't add up...
2581                  */
2582                 nmatches = 0;
2583                 for (i = 0; i < nvalues1; i++)
2584                 {
2585                         int                     j;
2586
2587                         for (j = 0; j < clamped_nvalues2; j++)
2588                         {
2589                                 if (hasmatch2[j])
2590                                         continue;
2591                                 if (DatumGetBool(FunctionCall2Coll(&eqproc,
2592                                                                                                    DEFAULT_COLLATION_OID,
2593                                                                                                    values1[i],
2594                                                                                                    values2[j])))
2595                                 {
2596                                         hasmatch1[i] = hasmatch2[j] = true;
2597                                         nmatches++;
2598                                         break;
2599                                 }
2600                         }
2601                 }
2602                 /* Sum up frequencies of matched MCVs */
2603                 matchfreq1 = 0.0;
2604                 for (i = 0; i < nvalues1; i++)
2605                 {
2606                         if (hasmatch1[i])
2607                                 matchfreq1 += numbers1[i];
2608                 }
2609                 CLAMP_PROBABILITY(matchfreq1);
2610                 pfree(hasmatch1);
2611                 pfree(hasmatch2);
2612
2613                 /*
2614                  * Now we need to estimate the fraction of relation 1 that has at
2615                  * least one join partner.  We know for certain that the matched MCVs
2616                  * do, so that gives us a lower bound, but we're really in the dark
2617                  * about everything else.  Our crude approach is: if nd1 <= nd2 then
2618                  * assume all non-null rel1 rows have join partners, else assume for
2619                  * the uncertain rows that a fraction nd2/nd1 have join partners. We
2620                  * can discount the known-matched MCVs from the distinct-values counts
2621                  * before doing the division.
2622                  *
2623                  * Crude as the above is, it's completely useless if we don't have
2624                  * reliable ndistinct values for both sides.  Hence, if either nd1 or
2625                  * nd2 is default, punt and assume half of the uncertain rows have
2626                  * join partners.
2627                  */
2628                 if (!isdefault1 && !isdefault2)
2629                 {
2630                         nd1 -= nmatches;
2631                         nd2 -= nmatches;
2632                         if (nd1 <= nd2 || nd2 < 0)
2633                                 uncertainfrac = 1.0;
2634                         else
2635                                 uncertainfrac = nd2 / nd1;
2636                 }
2637                 else
2638                         uncertainfrac = 0.5;
2639                 uncertain = 1.0 - matchfreq1 - nullfrac1;
2640                 CLAMP_PROBABILITY(uncertain);
2641                 selec = matchfreq1 + uncertainfrac * uncertain;
2642         }
2643         else
2644         {
2645                 /*
2646                  * Without MCV lists for both sides, we can only use the heuristic
2647                  * about nd1 vs nd2.
2648                  */
2649                 double          nullfrac1 = stats1 ? stats1->stanullfrac : 0.0;
2650
2651                 if (!isdefault1 && !isdefault2)
2652                 {
2653                         if (nd1 <= nd2 || nd2 < 0)
2654                                 selec = 1.0 - nullfrac1;
2655                         else
2656                                 selec = (nd2 / nd1) * (1.0 - nullfrac1);
2657                 }
2658                 else
2659                         selec = 0.5 * (1.0 - nullfrac1);
2660         }
2661
2662         if (have_mcvs1)
2663                 free_attstatsslot(vardata1->atttype, values1, nvalues1,
2664                                                   numbers1, nnumbers1);
2665         if (have_mcvs2)
2666                 free_attstatsslot(vardata2->atttype, values2, nvalues2,
2667                                                   numbers2, nnumbers2);
2668
2669         return selec;
2670 }
2671
2672 /*
2673  *              neqjoinsel              - Join selectivity of "!="
2674  */
2675 Datum
2676 neqjoinsel(PG_FUNCTION_ARGS)
2677 {
2678         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
2679         Oid                     operator = PG_GETARG_OID(1);
2680         List       *args = (List *) PG_GETARG_POINTER(2);
2681         JoinType        jointype = (JoinType) PG_GETARG_INT16(3);
2682         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) PG_GETARG_POINTER(4);
2683         Oid                     eqop;
2684         float8          result;
2685
2686         /*
2687          * We want 1 - eqjoinsel() where the equality operator is the one
2688          * associated with this != operator, that is, its negator.
2689          */
2690         eqop = get_negator(operator);
2691         if (eqop)
2692         {
2693                 result = DatumGetFloat8(DirectFunctionCall5(eqjoinsel,
2694                                                                                                         PointerGetDatum(root),
2695                                                                                                         ObjectIdGetDatum(eqop),
2696                                                                                                         PointerGetDatum(args),
2697                                                                                                         Int16GetDatum(jointype),
2698                                                                                                         PointerGetDatum(sjinfo)));
2699         }
2700         else
2701         {
2702                 /* Use default selectivity (should we raise an error instead?) */
2703                 result = DEFAULT_EQ_SEL;
2704         }
2705         result = 1.0 - result;
2706         PG_RETURN_FLOAT8(result);
2707 }
2708
2709 /*
2710  *              scalarltjoinsel - Join selectivity of "<" and "<=" for scalars
2711  */
2712 Datum
2713 scalarltjoinsel(PG_FUNCTION_ARGS)
2714 {
2715         PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
2716 }
2717
2718 /*
2719  *              scalargtjoinsel - Join selectivity of ">" and ">=" for scalars
2720  */
2721 Datum
2722 scalargtjoinsel(PG_FUNCTION_ARGS)
2723 {
2724         PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
2725 }
2726
2727 /*
2728  * patternjoinsel               - Generic code for pattern-match join selectivity.
2729  */
2730 static double
2731 patternjoinsel(PG_FUNCTION_ARGS, Pattern_Type ptype, bool negate)
2732 {
2733         /* For the moment we just punt. */
2734         return negate ? (1.0 - DEFAULT_MATCH_SEL) : DEFAULT_MATCH_SEL;
2735 }
2736
2737 /*
2738  *              regexeqjoinsel  - Join selectivity of regular-expression pattern match.
2739  */
2740 Datum
2741 regexeqjoinsel(PG_FUNCTION_ARGS)
2742 {
2743         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex, false));
2744 }
2745
2746 /*
2747  *              icregexeqjoinsel        - Join selectivity of case-insensitive regex match.
2748  */
2749 Datum
2750 icregexeqjoinsel(PG_FUNCTION_ARGS)
2751 {
2752         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex_IC, false));
2753 }
2754
2755 /*
2756  *              likejoinsel                     - Join selectivity of LIKE pattern match.
2757  */
2758 Datum
2759 likejoinsel(PG_FUNCTION_ARGS)
2760 {
2761         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like, false));
2762 }
2763
2764 /*
2765  *              iclikejoinsel                   - Join selectivity of ILIKE pattern match.
2766  */
2767 Datum
2768 iclikejoinsel(PG_FUNCTION_ARGS)
2769 {
2770         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like_IC, false));
2771 }
2772
2773 /*
2774  *              regexnejoinsel  - Join selectivity of regex non-match.
2775  */
2776 Datum
2777 regexnejoinsel(PG_FUNCTION_ARGS)
2778 {
2779         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex, true));
2780 }
2781
2782 /*
2783  *              icregexnejoinsel        - Join selectivity of case-insensitive regex non-match.
2784  */
2785 Datum
2786 icregexnejoinsel(PG_FUNCTION_ARGS)
2787 {
2788         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Regex_IC, true));
2789 }
2790
2791 /*
2792  *              nlikejoinsel            - Join selectivity of LIKE pattern non-match.
2793  */
2794 Datum
2795 nlikejoinsel(PG_FUNCTION_ARGS)
2796 {
2797         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like, true));
2798 }
2799
2800 /*
2801  *              icnlikejoinsel          - Join selectivity of ILIKE pattern non-match.
2802  */
2803 Datum
2804 icnlikejoinsel(PG_FUNCTION_ARGS)
2805 {
2806         PG_RETURN_FLOAT8(patternjoinsel(fcinfo, Pattern_Type_Like_IC, true));
2807 }
2808
2809 /*
2810  * mergejoinscansel                     - Scan selectivity of merge join.
2811  *
2812  * A merge join will stop as soon as it exhausts either input stream.
2813  * Therefore, if we can estimate the ranges of both input variables,
2814  * we can estimate how much of the input will actually be read.  This
2815  * can have a considerable impact on the cost when using indexscans.
2816  *
2817  * Also, we can estimate how much of each input has to be read before the
2818  * first join pair is found, which will affect the join's startup time.
2819  *
2820  * clause should be a clause already known to be mergejoinable.  opfamily,
2821  * strategy, and nulls_first specify the sort ordering being used.
2822  *
2823  * The outputs are:
2824  *              *leftstart is set to the fraction of the left-hand variable expected
2825  *               to be scanned before the first join pair is found (0 to 1).
2826  *              *leftend is set to the fraction of the left-hand variable expected
2827  *               to be scanned before the join terminates (0 to 1).
2828  *              *rightstart, *rightend similarly for the right-hand variable.
2829  */
2830 void
2831 mergejoinscansel(PlannerInfo *root, Node *clause,
2832                                  Oid opfamily, int strategy, bool nulls_first,
2833                                  Selectivity *leftstart, Selectivity *leftend,
2834                                  Selectivity *rightstart, Selectivity *rightend)
2835 {
2836         Node       *left,
2837                            *right;
2838         VariableStatData leftvar,
2839                                 rightvar;
2840         int                     op_strategy;
2841         Oid                     op_lefttype;
2842         Oid                     op_righttype;
2843         Oid                     opno,
2844                                 lsortop,
2845                                 rsortop,
2846                                 lstatop,
2847                                 rstatop,
2848                                 ltop,
2849                                 leop,
2850                                 revltop,
2851                                 revleop;
2852         bool            isgt;
2853         Datum           leftmin,
2854                                 leftmax,
2855                                 rightmin,
2856                                 rightmax;
2857         double          selec;
2858
2859         /* Set default results if we can't figure anything out. */
2860         /* XXX should default "start" fraction be a bit more than 0? */
2861         *leftstart = *rightstart = 0.0;
2862         *leftend = *rightend = 1.0;
2863
2864         /* Deconstruct the merge clause */
2865         if (!is_opclause(clause))
2866                 return;                                 /* shouldn't happen */
2867         opno = ((OpExpr *) clause)->opno;
2868         left = get_leftop((Expr *) clause);
2869         right = get_rightop((Expr *) clause);
2870         if (!right)
2871                 return;                                 /* shouldn't happen */
2872
2873         /* Look for stats for the inputs */
2874         examine_variable(root, left, 0, &leftvar);
2875         examine_variable(root, right, 0, &rightvar);
2876
2877         /* Extract the operator's declared left/right datatypes */
2878         get_op_opfamily_properties(opno, opfamily, false,
2879                                                            &op_strategy,
2880                                                            &op_lefttype,
2881                                                            &op_righttype);
2882         Assert(op_strategy == BTEqualStrategyNumber);
2883
2884         /*
2885          * Look up the various operators we need.  If we don't find them all, it
2886          * probably means the opfamily is broken, but we just fail silently.
2887          *
2888          * Note: we expect that pg_statistic histograms will be sorted by the '<'
2889          * operator, regardless of which sort direction we are considering.
2890          */
2891         switch (strategy)
2892         {
2893                 case BTLessStrategyNumber:
2894                         isgt = false;
2895                         if (op_lefttype == op_righttype)
2896                         {
2897                                 /* easy case */
2898                                 ltop = get_opfamily_member(opfamily,
2899                                                                                    op_lefttype, op_righttype,
2900                                                                                    BTLessStrategyNumber);
2901                                 leop = get_opfamily_member(opfamily,
2902                                                                                    op_lefttype, op_righttype,
2903                                                                                    BTLessEqualStrategyNumber);
2904                                 lsortop = ltop;
2905                                 rsortop = ltop;
2906                                 lstatop = lsortop;
2907                                 rstatop = rsortop;
2908                                 revltop = ltop;
2909                                 revleop = leop;
2910                         }
2911                         else
2912                         {
2913                                 ltop = get_opfamily_member(opfamily,
2914                                                                                    op_lefttype, op_righttype,
2915                                                                                    BTLessStrategyNumber);
2916                                 leop = get_opfamily_member(opfamily,
2917                                                                                    op_lefttype, op_righttype,
2918                                                                                    BTLessEqualStrategyNumber);
2919                                 lsortop = get_opfamily_member(opfamily,
2920                                                                                           op_lefttype, op_lefttype,
2921                                                                                           BTLessStrategyNumber);
2922                                 rsortop = get_opfamily_member(opfamily,
2923                                                                                           op_righttype, op_righttype,
2924                                                                                           BTLessStrategyNumber);
2925                                 lstatop = lsortop;
2926                                 rstatop = rsortop;
2927                                 revltop = get_opfamily_member(opfamily,
2928                                                                                           op_righttype, op_lefttype,
2929                                                                                           BTLessStrategyNumber);
2930                                 revleop = get_opfamily_member(opfamily,
2931                                                                                           op_righttype, op_lefttype,
2932                                                                                           BTLessEqualStrategyNumber);
2933                         }
2934                         break;
2935                 case BTGreaterStrategyNumber:
2936                         /* descending-order case */
2937                         isgt = true;
2938                         if (op_lefttype == op_righttype)
2939                         {
2940                                 /* easy case */
2941                                 ltop = get_opfamily_member(opfamily,
2942                                                                                    op_lefttype, op_righttype,
2943                                                                                    BTGreaterStrategyNumber);
2944                                 leop = get_opfamily_member(opfamily,
2945                                                                                    op_lefttype, op_righttype,
2946                                                                                    BTGreaterEqualStrategyNumber);
2947                                 lsortop = ltop;
2948                                 rsortop = ltop;
2949                                 lstatop = get_opfamily_member(opfamily,
2950                                                                                           op_lefttype, op_lefttype,
2951                                                                                           BTLessStrategyNumber);
2952                                 rstatop = lstatop;
2953                                 revltop = ltop;
2954                                 revleop = leop;
2955                         }
2956                         else
2957                         {
2958                                 ltop = get_opfamily_member(opfamily,
2959                                                                                    op_lefttype, op_righttype,
2960                                                                                    BTGreaterStrategyNumber);
2961                                 leop = get_opfamily_member(opfamily,
2962                                                                                    op_lefttype, op_righttype,
2963                                                                                    BTGreaterEqualStrategyNumber);
2964                                 lsortop = get_opfamily_member(opfamily,
2965                                                                                           op_lefttype, op_lefttype,
2966                                                                                           BTGreaterStrategyNumber);
2967                                 rsortop = get_opfamily_member(opfamily,
2968                                                                                           op_righttype, op_righttype,
2969                                                                                           BTGreaterStrategyNumber);
2970                                 lstatop = get_opfamily_member(opfamily,
2971                                                                                           op_lefttype, op_lefttype,
2972                                                                                           BTLessStrategyNumber);
2973                                 rstatop = get_opfamily_member(opfamily,
2974                                                                                           op_righttype, op_righttype,
2975                                                                                           BTLessStrategyNumber);
2976                                 revltop = get_opfamily_member(opfamily,
2977                                                                                           op_righttype, op_lefttype,
2978                                                                                           BTGreaterStrategyNumber);
2979                                 revleop = get_opfamily_member(opfamily,
2980                                                                                           op_righttype, op_lefttype,
2981                                                                                           BTGreaterEqualStrategyNumber);
2982                         }
2983                         break;
2984                 default:
2985                         goto fail;                      /* shouldn't get here */
2986         }
2987
2988         if (!OidIsValid(lsortop) ||
2989                 !OidIsValid(rsortop) ||
2990                 !OidIsValid(lstatop) ||
2991                 !OidIsValid(rstatop) ||
2992                 !OidIsValid(ltop) ||
2993                 !OidIsValid(leop) ||
2994                 !OidIsValid(revltop) ||
2995                 !OidIsValid(revleop))
2996                 goto fail;                              /* insufficient info in catalogs */
2997
2998         /* Try to get ranges of both inputs */
2999         if (!isgt)
3000         {
3001                 if (!get_variable_range(root, &leftvar, lstatop,
3002                                                                 &leftmin, &leftmax))
3003                         goto fail;                      /* no range available from stats */
3004                 if (!get_variable_range(root, &rightvar, rstatop,
3005                                                                 &rightmin, &rightmax))
3006                         goto fail;                      /* no range available from stats */
3007         }
3008         else
3009         {
3010                 /* need to swap the max and min */
3011                 if (!get_variable_range(root, &leftvar, lstatop,
3012                                                                 &leftmax, &leftmin))
3013                         goto fail;                      /* no range available from stats */
3014                 if (!get_variable_range(root, &rightvar, rstatop,
3015                                                                 &rightmax, &rightmin))
3016                         goto fail;                      /* no range available from stats */
3017         }
3018
3019         /*
3020          * Now, the fraction of the left variable that will be scanned is the
3021          * fraction that's <= the right-side maximum value.  But only believe
3022          * non-default estimates, else stick with our 1.0.
3023          */
3024         selec = scalarineqsel(root, leop, isgt, &leftvar,
3025                                                   rightmax, op_righttype);
3026         if (selec != DEFAULT_INEQ_SEL)
3027                 *leftend = selec;
3028
3029         /* And similarly for the right variable. */
3030         selec = scalarineqsel(root, revleop, isgt, &rightvar,
3031                                                   leftmax, op_lefttype);
3032         if (selec != DEFAULT_INEQ_SEL)
3033                 *rightend = selec;
3034
3035         /*
3036          * Only one of the two "end" fractions can really be less than 1.0;
3037          * believe the smaller estimate and reset the other one to exactly 1.0. If
3038          * we get exactly equal estimates (as can easily happen with self-joins),
3039          * believe neither.
3040          */
3041         if (*leftend > *rightend)
3042                 *leftend = 1.0;
3043         else if (*leftend < *rightend)
3044                 *rightend = 1.0;
3045         else
3046                 *leftend = *rightend = 1.0;
3047
3048         /*
3049          * Also, the fraction of the left variable that will be scanned before the
3050          * first join pair is found is the fraction that's < the right-side
3051          * minimum value.  But only believe non-default estimates, else stick with
3052          * our own default.
3053          */
3054         selec = scalarineqsel(root, ltop, isgt, &leftvar,
3055                                                   rightmin, op_righttype);
3056         if (selec != DEFAULT_INEQ_SEL)
3057                 *leftstart = selec;
3058
3059         /* And similarly for the right variable. */
3060         selec = scalarineqsel(root, revltop, isgt, &rightvar,
3061                                                   leftmin, op_lefttype);
3062         if (selec != DEFAULT_INEQ_SEL)
3063                 *rightstart = selec;
3064
3065         /*
3066          * Only one of the two "start" fractions can really be more than zero;
3067          * believe the larger estimate and reset the other one to exactly 0.0. If
3068          * we get exactly equal estimates (as can easily happen with self-joins),
3069          * believe neither.
3070          */
3071         if (*leftstart < *rightstart)
3072                 *leftstart = 0.0;
3073         else if (*leftstart > *rightstart)
3074                 *rightstart = 0.0;
3075         else
3076                 *leftstart = *rightstart = 0.0;
3077
3078         /*
3079          * If the sort order is nulls-first, we're going to have to skip over any
3080          * nulls too.  These would not have been counted by scalarineqsel, and we
3081          * can safely add in this fraction regardless of whether we believe
3082          * scalarineqsel's results or not.  But be sure to clamp the sum to 1.0!
3083          */
3084         if (nulls_first)
3085         {
3086                 Form_pg_statistic stats;
3087
3088                 if (HeapTupleIsValid(leftvar.statsTuple))
3089                 {
3090                         stats = (Form_pg_statistic) GETSTRUCT(leftvar.statsTuple);
3091                         *leftstart += stats->stanullfrac;
3092                         CLAMP_PROBABILITY(*leftstart);
3093                         *leftend += stats->stanullfrac;
3094                         CLAMP_PROBABILITY(*leftend);
3095                 }
3096                 if (HeapTupleIsValid(rightvar.statsTuple))
3097                 {
3098                         stats = (Form_pg_statistic) GETSTRUCT(rightvar.statsTuple);
3099                         *rightstart += stats->stanullfrac;
3100                         CLAMP_PROBABILITY(*rightstart);
3101                         *rightend += stats->stanullfrac;
3102                         CLAMP_PROBABILITY(*rightend);
3103                 }
3104         }
3105
3106         /* Disbelieve start >= end, just in case that can happen */
3107         if (*leftstart >= *leftend)
3108         {
3109                 *leftstart = 0.0;
3110                 *leftend = 1.0;
3111         }
3112         if (*rightstart >= *rightend)
3113         {
3114                 *rightstart = 0.0;
3115                 *rightend = 1.0;
3116         }
3117
3118 fail:
3119         ReleaseVariableStats(leftvar);
3120         ReleaseVariableStats(rightvar);
3121 }
3122
3123
3124 /*
3125  * Helper routine for estimate_num_groups: add an item to a list of
3126  * GroupVarInfos, but only if it's not known equal to any of the existing
3127  * entries.
3128  */
3129 typedef struct
3130 {
3131         Node       *var;                        /* might be an expression, not just a Var */
3132         RelOptInfo *rel;                        /* relation it belongs to */
3133         double          ndistinct;              /* # distinct values */
3134 } GroupVarInfo;
3135
3136 static List *
3137 add_unique_group_var(PlannerInfo *root, List *varinfos,
3138                                          Node *var, VariableStatData *vardata)
3139 {
3140         GroupVarInfo *varinfo;
3141         double          ndistinct;
3142         bool            isdefault;
3143         ListCell   *lc;
3144
3145         ndistinct = get_variable_numdistinct(vardata, &isdefault);
3146
3147         /* cannot use foreach here because of possible list_delete */
3148         lc = list_head(varinfos);
3149         while (lc)
3150         {
3151                 varinfo = (GroupVarInfo *) lfirst(lc);
3152
3153                 /* must advance lc before list_delete possibly pfree's it */
3154                 lc = lnext(lc);
3155
3156                 /* Drop exact duplicates */
3157                 if (equal(var, varinfo->var))
3158                         return varinfos;
3159
3160                 /*
3161                  * Drop known-equal vars, but only if they belong to different
3162                  * relations (see comments for estimate_num_groups)
3163                  */
3164                 if (vardata->rel != varinfo->rel &&
3165                         exprs_known_equal(root, var, varinfo->var))
3166                 {
3167                         if (varinfo->ndistinct <= ndistinct)
3168                         {
3169                                 /* Keep older item, forget new one */
3170                                 return varinfos;
3171                         }
3172                         else
3173                         {
3174                                 /* Delete the older item */
3175                                 varinfos = list_delete_ptr(varinfos, varinfo);
3176                         }
3177                 }
3178         }
3179
3180         varinfo = (GroupVarInfo *) palloc(sizeof(GroupVarInfo));
3181
3182         varinfo->var = var;
3183         varinfo->rel = vardata->rel;
3184         varinfo->ndistinct = ndistinct;
3185         varinfos = lappend(varinfos, varinfo);
3186         return varinfos;
3187 }
3188
3189 /*
3190  * estimate_num_groups          - Estimate number of groups in a grouped query
3191  *
3192  * Given a query having a GROUP BY clause, estimate how many groups there
3193  * will be --- ie, the number of distinct combinations of the GROUP BY
3194  * expressions.
3195  *
3196  * This routine is also used to estimate the number of rows emitted by
3197  * a DISTINCT filtering step; that is an isomorphic problem.  (Note:
3198  * actually, we only use it for DISTINCT when there's no grouping or
3199  * aggregation ahead of the DISTINCT.)
3200  *
3201  * Inputs:
3202  *      root - the query
3203  *      groupExprs - list of expressions being grouped by
3204  *      input_rows - number of rows estimated to arrive at the group/unique
3205  *              filter step
3206  *      pgset - NULL, or a List** pointing to a grouping set to filter the
3207  *              groupExprs against
3208  *
3209  * Given the lack of any cross-correlation statistics in the system, it's
3210  * impossible to do anything really trustworthy with GROUP BY conditions
3211  * involving multiple Vars.  We should however avoid assuming the worst
3212  * case (all possible cross-product terms actually appear as groups) since
3213  * very often the grouped-by Vars are highly correlated.  Our current approach
3214  * is as follows:
3215  *      1.  Expressions yielding boolean are assumed to contribute two groups,
3216  *              independently of their content, and are ignored in the subsequent
3217  *              steps.  This is mainly because tests like "col IS NULL" break the
3218  *              heuristic used in step 2 especially badly.
3219  *      2.  Reduce the given expressions to a list of unique Vars used.  For
3220  *              example, GROUP BY a, a + b is treated the same as GROUP BY a, b.
3221  *              It is clearly correct not to count the same Var more than once.
3222  *              It is also reasonable to treat f(x) the same as x: f() cannot
3223  *              increase the number of distinct values (unless it is volatile,
3224  *              which we consider unlikely for grouping), but it probably won't
3225  *              reduce the number of distinct values much either.
3226  *              As a special case, if a GROUP BY expression can be matched to an
3227  *              expressional index for which we have statistics, then we treat the
3228  *              whole expression as though it were just a Var.
3229  *      3.  If the list contains Vars of different relations that are known equal
3230  *              due to equivalence classes, then drop all but one of the Vars from each
3231  *              known-equal set, keeping the one with smallest estimated # of values
3232  *              (since the extra values of the others can't appear in joined rows).
3233  *              Note the reason we only consider Vars of different relations is that
3234  *              if we considered ones of the same rel, we'd be double-counting the
3235  *              restriction selectivity of the equality in the next step.
3236  *      4.  For Vars within a single source rel, we multiply together the numbers
3237  *              of values, clamp to the number of rows in the rel (divided by 10 if
3238  *              more than one Var), and then multiply by the selectivity of the
3239  *              restriction clauses for that rel.  When there's more than one Var,
3240  *              the initial product is probably too high (it's the worst case) but
3241  *              clamping to a fraction of the rel's rows seems to be a helpful
3242  *              heuristic for not letting the estimate get out of hand.  (The factor
3243  *              of 10 is derived from pre-Postgres-7.4 practice.)  Multiplying
3244  *              by the restriction selectivity is effectively assuming that the
3245  *              restriction clauses are independent of the grouping, which is a crummy
3246  *              assumption, but it's hard to do better.
3247  *      5.  If there are Vars from multiple rels, we repeat step 4 for each such
3248  *              rel, and multiply the results together.
3249  * Note that rels not containing grouped Vars are ignored completely, as are
3250  * join clauses.  Such rels cannot increase the number of groups, and we
3251  * assume such clauses do not reduce the number either (somewhat bogus,
3252  * but we don't have the info to do better).
3253  */
3254 double
3255 estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
3256                                         List **pgset)
3257 {
3258         List       *varinfos = NIL;
3259         double          numdistinct;
3260         ListCell   *l;
3261         int                     i;
3262
3263         /*
3264          * We don't ever want to return an estimate of zero groups, as that tends
3265          * to lead to division-by-zero and other unpleasantness.  The input_rows
3266          * estimate is usually already at least 1, but clamp it just in case it
3267          * isn't.
3268          */
3269         input_rows = clamp_row_est(input_rows);
3270
3271         /*
3272          * If no grouping columns, there's exactly one group.  (This can't happen
3273          * for normal cases with GROUP BY or DISTINCT, but it is possible for
3274          * corner cases with set operations.)
3275          */
3276         if (groupExprs == NIL || (pgset && list_length(*pgset) < 1))
3277                 return 1.0;
3278
3279         /*
3280          * Count groups derived from boolean grouping expressions.  For other
3281          * expressions, find the unique Vars used, treating an expression as a Var
3282          * if we can find stats for it.  For each one, record the statistical
3283          * estimate of number of distinct values (total in its table, without
3284          * regard for filtering).
3285          */
3286         numdistinct = 1.0;
3287
3288         i = 0;
3289         foreach(l, groupExprs)
3290         {
3291                 Node       *groupexpr = (Node *) lfirst(l);
3292                 VariableStatData vardata;
3293                 List       *varshere;
3294                 ListCell   *l2;
3295
3296                 /* is expression in this grouping set? */
3297                 if (pgset && !list_member_int(*pgset, i++))
3298                         continue;
3299
3300                 /* Short-circuit for expressions returning boolean */
3301                 if (exprType(groupexpr) == BOOLOID)
3302                 {
3303                         numdistinct *= 2.0;
3304                         continue;
3305                 }
3306
3307                 /*
3308                  * If examine_variable is able to deduce anything about the GROUP BY
3309                  * expression, treat it as a single variable even if it's really more
3310                  * complicated.
3311                  */
3312                 examine_variable(root, groupexpr, 0, &vardata);
3313                 if (HeapTupleIsValid(vardata.statsTuple) || vardata.isunique)
3314                 {
3315                         varinfos = add_unique_group_var(root, varinfos,
3316                                                                                         groupexpr, &vardata);
3317                         ReleaseVariableStats(vardata);
3318                         continue;
3319                 }
3320                 ReleaseVariableStats(vardata);
3321
3322                 /*
3323                  * Else pull out the component Vars.  Handle PlaceHolderVars by
3324                  * recursing into their arguments (effectively assuming that the
3325                  * PlaceHolderVar doesn't change the number of groups, which boils
3326                  * down to ignoring the possible addition of nulls to the result set).
3327                  */
3328                 varshere = pull_var_clause(groupexpr,
3329                                                                    PVC_RECURSE_AGGREGATES,
3330                                                                    PVC_RECURSE_PLACEHOLDERS);
3331
3332                 /*
3333                  * If we find any variable-free GROUP BY item, then either it is a
3334                  * constant (and we can ignore it) or it contains a volatile function;
3335                  * in the latter case we punt and assume that each input row will
3336                  * yield a distinct group.
3337                  */
3338                 if (varshere == NIL)
3339                 {
3340                         if (contain_volatile_functions(groupexpr))
3341                                 return input_rows;
3342                         continue;
3343                 }
3344
3345                 /*
3346                  * Else add variables to varinfos list
3347                  */
3348                 foreach(l2, varshere)
3349                 {
3350                         Node       *var = (Node *) lfirst(l2);
3351
3352                         examine_variable(root, var, 0, &vardata);
3353                         varinfos = add_unique_group_var(root, varinfos, var, &vardata);
3354                         ReleaseVariableStats(vardata);
3355                 }
3356         }
3357
3358         /*
3359          * If now no Vars, we must have an all-constant or all-boolean GROUP BY
3360          * list.
3361          */
3362         if (varinfos == NIL)
3363         {
3364                 /* Guard against out-of-range answers */
3365                 if (numdistinct > input_rows)
3366                         numdistinct = input_rows;
3367                 return numdistinct;
3368         }
3369
3370         /*
3371          * Group Vars by relation and estimate total numdistinct.
3372          *
3373          * For each iteration of the outer loop, we process the frontmost Var in
3374          * varinfos, plus all other Vars in the same relation.  We remove these
3375          * Vars from the newvarinfos list for the next iteration. This is the
3376          * easiest way to group Vars of same rel together.
3377          */
3378         do
3379         {
3380                 GroupVarInfo *varinfo1 = (GroupVarInfo *) linitial(varinfos);
3381                 RelOptInfo *rel = varinfo1->rel;
3382                 double          reldistinct = varinfo1->ndistinct;
3383                 double          relmaxndistinct = reldistinct;
3384                 int                     relvarcount = 1;
3385                 List       *newvarinfos = NIL;
3386
3387                 /*
3388                  * Get the product of numdistinct estimates of the Vars for this rel.
3389                  * Also, construct new varinfos list of remaining Vars.
3390                  */
3391                 for_each_cell(l, lnext(list_head(varinfos)))
3392                 {
3393                         GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(l);
3394
3395                         if (varinfo2->rel == varinfo1->rel)
3396                         {
3397                                 reldistinct *= varinfo2->ndistinct;
3398                                 if (relmaxndistinct < varinfo2->ndistinct)
3399                                         relmaxndistinct = varinfo2->ndistinct;
3400                                 relvarcount++;
3401                         }
3402                         else
3403                         {
3404                                 /* not time to process varinfo2 yet */
3405                                 newvarinfos = lcons(varinfo2, newvarinfos);
3406                         }
3407                 }
3408
3409                 /*
3410                  * Sanity check --- don't divide by zero if empty relation.
3411                  */
3412                 Assert(rel->reloptkind == RELOPT_BASEREL);
3413                 if (rel->tuples > 0)
3414                 {
3415                         /*
3416                          * Clamp to size of rel, or size of rel / 10 if multiple Vars. The
3417                          * fudge factor is because the Vars are probably correlated but we
3418                          * don't know by how much.  We should never clamp to less than the
3419                          * largest ndistinct value for any of the Vars, though, since
3420                          * there will surely be at least that many groups.
3421                          */
3422                         double          clamp = rel->tuples;
3423
3424                         if (relvarcount > 1)
3425                         {
3426                                 clamp *= 0.1;
3427                                 if (clamp < relmaxndistinct)
3428                                 {
3429                                         clamp = relmaxndistinct;
3430                                         /* for sanity in case some ndistinct is too large: */
3431                                         if (clamp > rel->tuples)
3432                                                 clamp = rel->tuples;
3433                                 }
3434                         }
3435                         if (reldistinct > clamp)
3436                                 reldistinct = clamp;
3437
3438                         /*
3439                          * Multiply by restriction selectivity.
3440                          */
3441                         reldistinct *= rel->rows / rel->tuples;
3442
3443                         /*
3444                          * Update estimate of total distinct groups.
3445                          */
3446                         numdistinct *= reldistinct;
3447                 }
3448
3449                 varinfos = newvarinfos;
3450         } while (varinfos != NIL);
3451
3452         numdistinct = ceil(numdistinct);
3453
3454         /* Guard against out-of-range answers */
3455         if (numdistinct > input_rows)
3456                 numdistinct = input_rows;
3457         if (numdistinct < 1.0)
3458                 numdistinct = 1.0;
3459
3460         return numdistinct;
3461 }
3462
3463 /*
3464  * Estimate hash bucketsize fraction (ie, number of entries in a bucket
3465  * divided by total tuples in relation) if the specified expression is used
3466  * as a hash key.
3467  *
3468  * XXX This is really pretty bogus since we're effectively assuming that the
3469  * distribution of hash keys will be the same after applying restriction
3470  * clauses as it was in the underlying relation.  However, we are not nearly
3471  * smart enough to figure out how the restrict clauses might change the
3472  * distribution, so this will have to do for now.
3473  *
3474  * We are passed the number of buckets the executor will use for the given
3475  * input relation.  If the data were perfectly distributed, with the same
3476  * number of tuples going into each available bucket, then the bucketsize
3477  * fraction would be 1/nbuckets.  But this happy state of affairs will occur
3478  * only if (a) there are at least nbuckets distinct data values, and (b)
3479  * we have a not-too-skewed data distribution.  Otherwise the buckets will
3480  * be nonuniformly occupied.  If the other relation in the join has a key
3481  * distribution similar to this one's, then the most-loaded buckets are
3482  * exactly those that will be probed most often.  Therefore, the "average"
3483  * bucket size for costing purposes should really be taken as something close
3484  * to the "worst case" bucket size.  We try to estimate this by adjusting the
3485  * fraction if there are too few distinct data values, and then scaling up
3486  * by the ratio of the most common value's frequency to the average frequency.
3487  *
3488  * If no statistics are available, use a default estimate of 0.1.  This will
3489  * discourage use of a hash rather strongly if the inner relation is large,
3490  * which is what we want.  We do not want to hash unless we know that the
3491  * inner rel is well-dispersed (or the alternatives seem much worse).
3492  */
3493 Selectivity
3494 estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey, double nbuckets)
3495 {
3496         VariableStatData vardata;
3497         double          estfract,
3498                                 ndistinct,
3499                                 stanullfrac,
3500                                 mcvfreq,
3501                                 avgfreq;
3502         bool            isdefault;
3503         float4     *numbers;
3504         int                     nnumbers;
3505
3506         examine_variable(root, hashkey, 0, &vardata);
3507
3508         /* Get number of distinct values */
3509         ndistinct = get_variable_numdistinct(&vardata, &isdefault);
3510
3511         /* If ndistinct isn't real, punt and return 0.1, per comments above */
3512         if (isdefault)
3513         {
3514                 ReleaseVariableStats(vardata);
3515                 return (Selectivity) 0.1;
3516         }
3517
3518         /* Get fraction that are null */
3519         if (HeapTupleIsValid(vardata.statsTuple))
3520         {
3521                 Form_pg_statistic stats;
3522
3523                 stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
3524                 stanullfrac = stats->stanullfrac;
3525         }
3526         else
3527                 stanullfrac = 0.0;
3528
3529         /* Compute avg freq of all distinct data values in raw relation */
3530         avgfreq = (1.0 - stanullfrac) / ndistinct;
3531
3532         /*
3533          * Adjust ndistinct to account for restriction clauses.  Observe we are
3534          * assuming that the data distribution is affected uniformly by the
3535          * restriction clauses!
3536          *
3537          * XXX Possibly better way, but much more expensive: multiply by
3538          * selectivity of rel's restriction clauses that mention the target Var.
3539          */
3540         if (vardata.rel)
3541                 ndistinct *= vardata.rel->rows / vardata.rel->tuples;
3542
3543         /*
3544          * Initial estimate of bucketsize fraction is 1/nbuckets as long as the
3545          * number of buckets is less than the expected number of distinct values;
3546          * otherwise it is 1/ndistinct.
3547          */
3548         if (ndistinct > nbuckets)
3549                 estfract = 1.0 / nbuckets;
3550         else
3551                 estfract = 1.0 / ndistinct;
3552
3553         /*
3554          * Look up the frequency of the most common value, if available.
3555          */
3556         mcvfreq = 0.0;
3557
3558         if (HeapTupleIsValid(vardata.statsTuple))
3559         {
3560                 if (get_attstatsslot(vardata.statsTuple,
3561                                                          vardata.atttype, vardata.atttypmod,
3562                                                          STATISTIC_KIND_MCV, InvalidOid,
3563                                                          NULL,
3564                                                          NULL, NULL,
3565                                                          &numbers, &nnumbers))
3566                 {
3567                         /*
3568                          * The first MCV stat is for the most common value.
3569                          */
3570                         if (nnumbers > 0)
3571                                 mcvfreq = numbers[0];
3572                         free_attstatsslot(vardata.atttype, NULL, 0,
3573                                                           numbers, nnumbers);
3574                 }
3575         }
3576
3577         /*
3578          * Adjust estimated bucketsize upward to account for skewed distribution.
3579          */
3580         if (avgfreq > 0.0 && mcvfreq > avgfreq)
3581                 estfract *= mcvfreq / avgfreq;
3582
3583         /*
3584          * Clamp bucketsize to sane range (the above adjustment could easily
3585          * produce an out-of-range result).  We set the lower bound a little above
3586          * zero, since zero isn't a very sane result.
3587          */
3588         if (estfract < 1.0e-6)
3589                 estfract = 1.0e-6;
3590         else if (estfract > 1.0)
3591                 estfract = 1.0;
3592
3593         ReleaseVariableStats(vardata);
3594
3595         return (Selectivity) estfract;
3596 }
3597
3598
3599 /*-------------------------------------------------------------------------
3600  *
3601  * Support routines
3602  *
3603  *-------------------------------------------------------------------------
3604  */
3605
3606 /*
3607  * convert_to_scalar
3608  *        Convert non-NULL values of the indicated types to the comparison
3609  *        scale needed by scalarineqsel().
3610  *        Returns "true" if successful.
3611  *
3612  * XXX this routine is a hack: ideally we should look up the conversion
3613  * subroutines in pg_type.
3614  *
3615  * All numeric datatypes are simply converted to their equivalent
3616  * "double" values.  (NUMERIC values that are outside the range of "double"
3617  * are clamped to +/- HUGE_VAL.)
3618  *
3619  * String datatypes are converted by convert_string_to_scalar(),
3620  * which is explained below.  The reason why this routine deals with
3621  * three values at a time, not just one, is that we need it for strings.
3622  *
3623  * The bytea datatype is just enough different from strings that it has
3624  * to be treated separately.
3625  *
3626  * The several datatypes representing absolute times are all converted
3627  * to Timestamp, which is actually a double, and then we just use that
3628  * double value.  Note this will give correct results even for the "special"
3629  * values of Timestamp, since those are chosen to compare correctly;
3630  * see timestamp_cmp.
3631  *
3632  * The several datatypes representing relative times (intervals) are all
3633  * converted to measurements expressed in seconds.
3634  */
3635 static bool
3636 convert_to_scalar(Datum value, Oid valuetypid, double *scaledvalue,
3637                                   Datum lobound, Datum hibound, Oid boundstypid,
3638                                   double *scaledlobound, double *scaledhibound)
3639 {
3640         /*
3641          * Both the valuetypid and the boundstypid should exactly match the
3642          * declared input type(s) of the operator we are invoked for, so we just
3643          * error out if either is not recognized.
3644          *
3645          * XXX The histogram we are interpolating between points of could belong
3646          * to a column that's only binary-compatible with the declared type. In
3647          * essence we are assuming that the semantics of binary-compatible types
3648          * are enough alike that we can use a histogram generated with one type's
3649          * operators to estimate selectivity for the other's.  This is outright
3650          * wrong in some cases --- in particular signed versus unsigned
3651          * interpretation could trip us up.  But it's useful enough in the
3652          * majority of cases that we do it anyway.  Should think about more
3653          * rigorous ways to do it.
3654          */
3655         switch (valuetypid)
3656         {
3657                         /*
3658                          * Built-in numeric types
3659                          */
3660                 case BOOLOID:
3661                 case INT2OID:
3662                 case INT4OID:
3663                 case INT8OID:
3664                 case FLOAT4OID:
3665                 case FLOAT8OID:
3666                 case NUMERICOID:
3667                 case OIDOID:
3668                 case REGPROCOID:
3669                 case REGPROCEDUREOID:
3670                 case REGOPEROID:
3671                 case REGOPERATOROID:
3672                 case REGCLASSOID:
3673                 case REGTYPEOID:
3674                 case REGCONFIGOID:
3675                 case REGDICTIONARYOID:
3676                 case REGROLEOID:
3677                 case REGNAMESPACEOID:
3678                         *scaledvalue = convert_numeric_to_scalar(value, valuetypid);
3679                         *scaledlobound = convert_numeric_to_scalar(lobound, boundstypid);
3680                         *scaledhibound = convert_numeric_to_scalar(hibound, boundstypid);
3681                         return true;
3682
3683                         /*
3684                          * Built-in string types
3685                          */
3686                 case CHAROID:
3687                 case BPCHAROID:
3688                 case VARCHAROID:
3689                 case TEXTOID:
3690                 case NAMEOID:
3691                         {
3692                                 char       *valstr = convert_string_datum(value, valuetypid);
3693                                 char       *lostr = convert_string_datum(lobound, boundstypid);
3694                                 char       *histr = convert_string_datum(hibound, boundstypid);
3695
3696                                 convert_string_to_scalar(valstr, scaledvalue,
3697                                                                                  lostr, scaledlobound,
3698                                                                                  histr, scaledhibound);
3699                                 pfree(valstr);
3700                                 pfree(lostr);
3701                                 pfree(histr);
3702                                 return true;
3703                         }
3704
3705                         /*
3706                          * Built-in bytea type
3707                          */
3708                 case BYTEAOID:
3709                         {
3710                                 convert_bytea_to_scalar(value, scaledvalue,
3711                                                                                 lobound, scaledlobound,
3712                                                                                 hibound, scaledhibound);
3713                                 return true;
3714                         }
3715
3716                         /*
3717                          * Built-in time types
3718                          */
3719                 case TIMESTAMPOID:
3720                 case TIMESTAMPTZOID:
3721                 case ABSTIMEOID:
3722                 case DATEOID:
3723                 case INTERVALOID:
3724                 case RELTIMEOID:
3725                 case TINTERVALOID:
3726                 case TIMEOID:
3727                 case TIMETZOID:
3728                         *scaledvalue = convert_timevalue_to_scalar(value, valuetypid);
3729                         *scaledlobound = convert_timevalue_to_scalar(lobound, boundstypid);
3730                         *scaledhibound = convert_timevalue_to_scalar(hibound, boundstypid);
3731                         return true;
3732
3733                         /*
3734                          * Built-in network types
3735                          */
3736                 case INETOID:
3737                 case CIDROID:
3738                 case MACADDROID:
3739                         *scaledvalue = convert_network_to_scalar(value, valuetypid);
3740                         *scaledlobound = convert_network_to_scalar(lobound, boundstypid);
3741                         *scaledhibound = convert_network_to_scalar(hibound, boundstypid);
3742                         return true;
3743         }
3744         /* Don't know how to convert */
3745         *scaledvalue = *scaledlobound = *scaledhibound = 0;
3746         return false;
3747 }
3748
3749 /*
3750  * Do convert_to_scalar()'s work for any numeric data type.
3751  */
3752 static double
3753 convert_numeric_to_scalar(Datum value, Oid typid)
3754 {
3755         switch (typid)
3756         {
3757                 case BOOLOID:
3758                         return (double) DatumGetBool(value);
3759                 case INT2OID:
3760                         return (double) DatumGetInt16(value);
3761                 case INT4OID:
3762                         return (double) DatumGetInt32(value);
3763                 case INT8OID:
3764                         return (double) DatumGetInt64(value);
3765                 case FLOAT4OID:
3766                         return (double) DatumGetFloat4(value);
3767                 case FLOAT8OID:
3768                         return (double) DatumGetFloat8(value);
3769                 case NUMERICOID:
3770                         /* Note: out-of-range values will be clamped to +-HUGE_VAL */
3771                         return (double)
3772                                 DatumGetFloat8(DirectFunctionCall1(numeric_float8_no_overflow,
3773                                                                                                    value));
3774                 case OIDOID:
3775                 case REGPROCOID:
3776                 case REGPROCEDUREOID:
3777                 case REGOPEROID:
3778                 case REGOPERATOROID:
3779                 case REGCLASSOID:
3780                 case REGTYPEOID:
3781                 case REGCONFIGOID:
3782                 case REGDICTIONARYOID:
3783                 case REGROLEOID:
3784                 case REGNAMESPACEOID:
3785                         /* we can treat OIDs as integers... */
3786                         return (double) DatumGetObjectId(value);
3787         }
3788
3789         /*
3790          * Can't get here unless someone tries to use scalarltsel/scalargtsel on
3791          * an operator with one numeric and one non-numeric operand.
3792          */
3793         elog(ERROR, "unsupported type: %u", typid);
3794         return 0;
3795 }
3796
3797 /*
3798  * Do convert_to_scalar()'s work for any character-string data type.
3799  *
3800  * String datatypes are converted to a scale that ranges from 0 to 1,
3801  * where we visualize the bytes of the string as fractional digits.
3802  *
3803  * We do not want the base to be 256, however, since that tends to
3804  * generate inflated selectivity estimates; few databases will have
3805  * occurrences of all 256 possible byte values at each position.
3806  * Instead, use the smallest and largest byte values seen in the bounds
3807  * as the estimated range for each byte, after some fudging to deal with
3808  * the fact that we probably aren't going to see the full range that way.
3809  *
3810  * An additional refinement is that we discard any common prefix of the
3811  * three strings before computing the scaled values.  This allows us to
3812  * "zoom in" when we encounter a narrow data range.  An example is a phone
3813  * number database where all the values begin with the same area code.
3814  * (Actually, the bounds will be adjacent histogram-bin-boundary values,
3815  * so this is more likely to happen than you might think.)
3816  */
3817 static void
3818 convert_string_to_scalar(char *value,
3819                                                  double *scaledvalue,
3820                                                  char *lobound,
3821                                                  double *scaledlobound,
3822                                                  char *hibound,
3823                                                  double *scaledhibound)
3824 {
3825         int                     rangelo,
3826                                 rangehi;
3827         char       *sptr;
3828
3829         rangelo = rangehi = (unsigned char) hibound[0];
3830         for (sptr = lobound; *sptr; sptr++)
3831         {
3832                 if (rangelo > (unsigned char) *sptr)
3833                         rangelo = (unsigned char) *sptr;
3834                 if (rangehi < (unsigned char) *sptr)
3835                         rangehi = (unsigned char) *sptr;
3836         }
3837         for (sptr = hibound; *sptr; sptr++)
3838         {
3839                 if (rangelo > (unsigned char) *sptr)
3840                         rangelo = (unsigned char) *sptr;
3841                 if (rangehi < (unsigned char) *sptr)
3842                         rangehi = (unsigned char) *sptr;
3843         }
3844         /* If range includes any upper-case ASCII chars, make it include all */
3845         if (rangelo <= 'Z' && rangehi >= 'A')
3846         {
3847                 if (rangelo > 'A')
3848                         rangelo = 'A';
3849                 if (rangehi < 'Z')
3850                         rangehi = 'Z';
3851         }
3852         /* Ditto lower-case */
3853         if (rangelo <= 'z' && rangehi >= 'a')
3854         {
3855                 if (rangelo > 'a')
3856                         rangelo = 'a';
3857                 if (rangehi < 'z')
3858                         rangehi = 'z';
3859         }
3860         /* Ditto digits */
3861         if (rangelo <= '9' && rangehi >= '0')
3862         {
3863                 if (rangelo > '0')
3864                         rangelo = '0';
3865                 if (rangehi < '9')
3866                         rangehi = '9';
3867         }
3868
3869         /*
3870          * If range includes less than 10 chars, assume we have not got enough
3871          * data, and make it include regular ASCII set.
3872          */
3873         if (rangehi - rangelo < 9)
3874         {
3875                 rangelo = ' ';
3876                 rangehi = 127;
3877         }
3878
3879         /*
3880          * Now strip any common prefix of the three strings.
3881          */
3882         while (*lobound)
3883         {
3884                 if (*lobound != *hibound || *lobound != *value)
3885                         break;
3886                 lobound++, hibound++, value++;
3887         }
3888
3889         /*
3890          * Now we can do the conversions.
3891          */
3892         *scaledvalue = convert_one_string_to_scalar(value, rangelo, rangehi);
3893         *scaledlobound = convert_one_string_to_scalar(lobound, rangelo, rangehi);
3894         *scaledhibound = convert_one_string_to_scalar(hibound, rangelo, rangehi);
3895 }
3896
3897 static double
3898 convert_one_string_to_scalar(char *value, int rangelo, int rangehi)
3899 {
3900         int                     slen = strlen(value);
3901         double          num,
3902                                 denom,
3903                                 base;
3904
3905         if (slen <= 0)
3906                 return 0.0;                             /* empty string has scalar value 0 */
3907
3908         /*
3909          * There seems little point in considering more than a dozen bytes from
3910          * the string.  Since base is at least 10, that will give us nominal
3911          * resolution of at least 12 decimal digits, which is surely far more
3912          * precision than this estimation technique has got anyway (especially in
3913          * non-C locales).  Also, even with the maximum possible base of 256, this
3914          * ensures denom cannot grow larger than 256^13 = 2.03e31, which will not
3915          * overflow on any known machine.
3916          */
3917         if (slen > 12)
3918                 slen = 12;
3919
3920         /* Convert initial characters to fraction */
3921         base = rangehi - rangelo + 1;
3922         num = 0.0;
3923         denom = base;
3924         while (slen-- > 0)
3925         {
3926                 int                     ch = (unsigned char) *value++;
3927
3928                 if (ch < rangelo)
3929                         ch = rangelo - 1;
3930                 else if (ch > rangehi)
3931                         ch = rangehi + 1;
3932                 num += ((double) (ch - rangelo)) / denom;
3933                 denom *= base;
3934         }
3935
3936         return num;
3937 }
3938
3939 /*
3940  * Convert a string-type Datum into a palloc'd, null-terminated string.
3941  *
3942  * When using a non-C locale, we must pass the string through strxfrm()
3943  * before continuing, so as to generate correct locale-specific results.
3944  */
3945 static char *
3946 convert_string_datum(Datum value, Oid typid)
3947 {
3948         char       *val;
3949
3950         switch (typid)
3951         {
3952                 case CHAROID:
3953                         val = (char *) palloc(2);
3954                         val[0] = DatumGetChar(value);
3955                         val[1] = '\0';
3956                         break;
3957                 case BPCHAROID:
3958                 case VARCHAROID:
3959                 case TEXTOID:
3960                         val = TextDatumGetCString(value);
3961                         break;
3962                 case NAMEOID:
3963                         {
3964                                 NameData   *nm = (NameData *) DatumGetPointer(value);
3965
3966                                 val = pstrdup(NameStr(*nm));
3967                                 break;
3968                         }
3969                 default:
3970
3971                         /*
3972                          * Can't get here unless someone tries to use scalarltsel on an
3973                          * operator with one string and one non-string operand.
3974                          */
3975                         elog(ERROR, "unsupported type: %u", typid);
3976                         return NULL;
3977         }
3978
3979         if (!lc_collate_is_c(DEFAULT_COLLATION_OID))
3980         {
3981                 char       *xfrmstr;
3982                 size_t          xfrmlen;
3983                 size_t xfrmlen2 PG_USED_FOR_ASSERTS_ONLY;
3984
3985                 /*
3986                  * XXX: We could guess at a suitable output buffer size and only call
3987                  * strxfrm twice if our guess is too small.
3988                  *
3989                  * XXX: strxfrm doesn't support UTF-8 encoding on Win32, it can return
3990                  * bogus data or set an error. This is not really a problem unless it
3991                  * crashes since it will only give an estimation error and nothing
3992                  * fatal.
3993                  */
3994 #if _MSC_VER == 1400                    /* VS.Net 2005 */
3995
3996                 /*
3997                  *
3998                  * http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?
3999                  * FeedbackID=99694 */
4000                 {
4001                         char            x[1];
4002
4003                         xfrmlen = strxfrm(x, val, 0);
4004                 }
4005 #else
4006                 xfrmlen = strxfrm(NULL, val, 0);
4007 #endif
4008 #ifdef WIN32
4009
4010                 /*
4011                  * On Windows, strxfrm returns INT_MAX when an error occurs. Instead
4012                  * of trying to allocate this much memory (and fail), just return the
4013                  * original string unmodified as if we were in the C locale.
4014                  */
4015                 if (xfrmlen == INT_MAX)
4016                         return val;
4017 #endif
4018                 xfrmstr = (char *) palloc(xfrmlen + 1);
4019                 xfrmlen2 = strxfrm(xfrmstr, val, xfrmlen + 1);
4020
4021                 /*
4022                  * Some systems (e.g., glibc) can return a smaller value from the
4023                  * second call than the first; thus the Assert must be <= not ==.
4024                  */
4025                 Assert(xfrmlen2 <= xfrmlen);
4026                 pfree(val);
4027                 val = xfrmstr;
4028         }
4029
4030         return val;
4031 }
4032
4033 /*
4034  * Do convert_to_scalar()'s work for any bytea data type.
4035  *
4036  * Very similar to convert_string_to_scalar except we can't assume
4037  * null-termination and therefore pass explicit lengths around.
4038  *
4039  * Also, assumptions about likely "normal" ranges of characters have been
4040  * removed - a data range of 0..255 is always used, for now.  (Perhaps
4041  * someday we will add information about actual byte data range to
4042  * pg_statistic.)
4043  */
4044 static void
4045 convert_bytea_to_scalar(Datum value,
4046                                                 double *scaledvalue,
4047                                                 Datum lobound,
4048                                                 double *scaledlobound,
4049                                                 Datum hibound,
4050                                                 double *scaledhibound)
4051 {
4052         int                     rangelo,
4053                                 rangehi,
4054                                 valuelen = VARSIZE(DatumGetPointer(value)) - VARHDRSZ,
4055                                 loboundlen = VARSIZE(DatumGetPointer(lobound)) - VARHDRSZ,
4056                                 hiboundlen = VARSIZE(DatumGetPointer(hibound)) - VARHDRSZ,
4057                                 i,
4058                                 minlen;
4059         unsigned char *valstr = (unsigned char *) VARDATA(DatumGetPointer(value)),
4060                            *lostr = (unsigned char *) VARDATA(DatumGetPointer(lobound)),
4061                            *histr = (unsigned char *) VARDATA(DatumGetPointer(hibound));
4062
4063         /*
4064          * Assume bytea data is uniformly distributed across all byte values.
4065          */
4066         rangelo = 0;
4067         rangehi = 255;
4068
4069         /*
4070          * Now strip any common prefix of the three strings.
4071          */
4072         minlen = Min(Min(valuelen, loboundlen), hiboundlen);
4073         for (i = 0; i < minlen; i++)
4074         {
4075                 if (*lostr != *histr || *lostr != *valstr)
4076                         break;
4077                 lostr++, histr++, valstr++;
4078                 loboundlen--, hiboundlen--, valuelen--;
4079         }
4080
4081         /*
4082          * Now we can do the conversions.
4083          */
4084         *scaledvalue = convert_one_bytea_to_scalar(valstr, valuelen, rangelo, rangehi);
4085         *scaledlobound = convert_one_bytea_to_scalar(lostr, loboundlen, rangelo, rangehi);
4086         *scaledhibound = convert_one_bytea_to_scalar(histr, hiboundlen, rangelo, rangehi);
4087 }
4088
4089 static double
4090 convert_one_bytea_to_scalar(unsigned char *value, int valuelen,
4091                                                         int rangelo, int rangehi)
4092 {
4093         double          num,
4094                                 denom,
4095                                 base;
4096
4097         if (valuelen <= 0)
4098                 return 0.0;                             /* empty string has scalar value 0 */
4099
4100         /*
4101          * Since base is 256, need not consider more than about 10 chars (even
4102          * this many seems like overkill)
4103          */
4104         if (valuelen > 10)
4105                 valuelen = 10;
4106
4107         /* Convert initial characters to fraction */
4108         base = rangehi - rangelo + 1;
4109         num = 0.0;
4110         denom = base;
4111         while (valuelen-- > 0)
4112         {
4113                 int                     ch = *value++;
4114
4115                 if (ch < rangelo)
4116                         ch = rangelo - 1;
4117                 else if (ch > rangehi)
4118                         ch = rangehi + 1;
4119                 num += ((double) (ch - rangelo)) / denom;
4120                 denom *= base;
4121         }
4122
4123         return num;
4124 }
4125
4126 /*
4127  * Do convert_to_scalar()'s work for any timevalue data type.
4128  */
4129 static double
4130 convert_timevalue_to_scalar(Datum value, Oid typid)
4131 {
4132         switch (typid)
4133         {
4134                 case TIMESTAMPOID:
4135                         return DatumGetTimestamp(value);
4136                 case TIMESTAMPTZOID:
4137                         return DatumGetTimestampTz(value);
4138                 case ABSTIMEOID:
4139                         return DatumGetTimestamp(DirectFunctionCall1(abstime_timestamp,
4140                                                                                                                  value));
4141                 case DATEOID:
4142                         return date2timestamp_no_overflow(DatumGetDateADT(value));
4143                 case INTERVALOID:
4144                         {
4145                                 Interval   *interval = DatumGetIntervalP(value);
4146
4147                                 /*
4148                                  * Convert the month part of Interval to days using assumed
4149                                  * average month length of 365.25/12.0 days.  Not too
4150                                  * accurate, but plenty good enough for our purposes.
4151                                  */
4152 #ifdef HAVE_INT64_TIMESTAMP
4153                                 return interval->time + interval->day * (double) USECS_PER_DAY +
4154                                         interval->month * ((DAYS_PER_YEAR / (double) MONTHS_PER_YEAR) * USECS_PER_DAY);
4155 #else
4156                                 return interval->time + interval->day * SECS_PER_DAY +
4157                                         interval->month * ((DAYS_PER_YEAR / (double) MONTHS_PER_YEAR) * (double) SECS_PER_DAY);
4158 #endif
4159                         }
4160                 case RELTIMEOID:
4161 #ifdef HAVE_INT64_TIMESTAMP
4162                         return (DatumGetRelativeTime(value) * 1000000.0);
4163 #else
4164                         return DatumGetRelativeTime(value);
4165 #endif
4166                 case TINTERVALOID:
4167                         {
4168                                 TimeInterval tinterval = DatumGetTimeInterval(value);
4169
4170 #ifdef HAVE_INT64_TIMESTAMP
4171                                 if (tinterval->status != 0)
4172                                         return ((tinterval->data[1] - tinterval->data[0]) * 1000000.0);
4173 #else
4174                                 if (tinterval->status != 0)
4175                                         return tinterval->data[1] - tinterval->data[0];
4176 #endif
4177                                 return 0;               /* for lack of a better idea */
4178                         }
4179                 case TIMEOID:
4180                         return DatumGetTimeADT(value);
4181                 case TIMETZOID:
4182                         {
4183                                 TimeTzADT  *timetz = DatumGetTimeTzADTP(value);
4184
4185                                 /* use GMT-equivalent time */
4186 #ifdef HAVE_INT64_TIMESTAMP
4187                                 return (double) (timetz->time + (timetz->zone * 1000000.0));
4188 #else
4189                                 return (double) (timetz->time + timetz->zone);
4190 #endif
4191                         }
4192         }
4193
4194         /*
4195          * Can't get here unless someone tries to use scalarltsel/scalargtsel on
4196          * an operator with one timevalue and one non-timevalue operand.
4197          */
4198         elog(ERROR, "unsupported type: %u", typid);
4199         return 0;
4200 }
4201
4202
4203 /*
4204  * get_restriction_variable
4205  *              Examine the args of a restriction clause to see if it's of the
4206  *              form (variable op pseudoconstant) or (pseudoconstant op variable),
4207  *              where "variable" could be either a Var or an expression in vars of a
4208  *              single relation.  If so, extract information about the variable,
4209  *              and also indicate which side it was on and the other argument.
4210  *
4211  * Inputs:
4212  *      root: the planner info
4213  *      args: clause argument list
4214  *      varRelid: see specs for restriction selectivity functions
4215  *
4216  * Outputs: (these are valid only if TRUE is returned)
4217  *      *vardata: gets information about variable (see examine_variable)
4218  *      *other: gets other clause argument, aggressively reduced to a constant
4219  *      *varonleft: set TRUE if variable is on the left, FALSE if on the right
4220  *
4221  * Returns TRUE if a variable is identified, otherwise FALSE.
4222  *
4223  * Note: if there are Vars on both sides of the clause, we must fail, because
4224  * callers are expecting that the other side will act like a pseudoconstant.
4225  */
4226 bool
4227 get_restriction_variable(PlannerInfo *root, List *args, int varRelid,
4228                                                  VariableStatData *vardata, Node **other,
4229                                                  bool *varonleft)
4230 {
4231         Node       *left,
4232                            *right;
4233         VariableStatData rdata;
4234
4235         /* Fail if not a binary opclause (probably shouldn't happen) */
4236         if (list_length(args) != 2)
4237                 return false;
4238
4239         left = (Node *) linitial(args);
4240         right = (Node *) lsecond(args);
4241
4242         /*
4243          * Examine both sides.  Note that when varRelid is nonzero, Vars of other
4244          * relations will be treated as pseudoconstants.
4245          */
4246         examine_variable(root, left, varRelid, vardata);
4247         examine_variable(root, right, varRelid, &rdata);
4248
4249         /*
4250          * If one side is a variable and the other not, we win.
4251          */
4252         if (vardata->rel && rdata.rel == NULL)
4253         {
4254                 *varonleft = true;
4255                 *other = estimate_expression_value(root, rdata.var);
4256                 /* Assume we need no ReleaseVariableStats(rdata) here */
4257                 return true;
4258         }
4259
4260         if (vardata->rel == NULL && rdata.rel)
4261         {
4262                 *varonleft = false;
4263                 *other = estimate_expression_value(root, vardata->var);
4264                 /* Assume we need no ReleaseVariableStats(*vardata) here */
4265                 *vardata = rdata;
4266                 return true;
4267         }
4268
4269         /* Ooops, clause has wrong structure (probably var op var) */
4270         ReleaseVariableStats(*vardata);
4271         ReleaseVariableStats(rdata);
4272
4273         return false;
4274 }
4275
4276 /*
4277  * get_join_variables
4278  *              Apply examine_variable() to each side of a join clause.
4279  *              Also, attempt to identify whether the join clause has the same
4280  *              or reversed sense compared to the SpecialJoinInfo.
4281  *
4282  * We consider the join clause "normal" if it is "lhs_var OP rhs_var",
4283  * or "reversed" if it is "rhs_var OP lhs_var".  In complicated cases
4284  * where we can't tell for sure, we default to assuming it's normal.
4285  */
4286 void
4287 get_join_variables(PlannerInfo *root, List *args, SpecialJoinInfo *sjinfo,
4288                                    VariableStatData *vardata1, VariableStatData *vardata2,
4289                                    bool *join_is_reversed)
4290 {
4291         Node       *left,
4292                            *right;
4293
4294         if (list_length(args) != 2)
4295                 elog(ERROR, "join operator should take two arguments");
4296
4297         left = (Node *) linitial(args);
4298         right = (Node *) lsecond(args);
4299
4300         examine_variable(root, left, 0, vardata1);
4301         examine_variable(root, right, 0, vardata2);
4302
4303         if (vardata1->rel &&
4304                 bms_is_subset(vardata1->rel->relids, sjinfo->syn_righthand))
4305                 *join_is_reversed = true;               /* var1 is on RHS */
4306         else if (vardata2->rel &&
4307                          bms_is_subset(vardata2->rel->relids, sjinfo->syn_lefthand))
4308                 *join_is_reversed = true;               /* var2 is on LHS */
4309         else
4310                 *join_is_reversed = false;
4311 }
4312
4313 /*
4314  * examine_variable
4315  *              Try to look up statistical data about an expression.
4316  *              Fill in a VariableStatData struct to describe the expression.
4317  *
4318  * Inputs:
4319  *      root: the planner info
4320  *      node: the expression tree to examine
4321  *      varRelid: see specs for restriction selectivity functions
4322  *
4323  * Outputs: *vardata is filled as follows:
4324  *      var: the input expression (with any binary relabeling stripped, if
4325  *              it is or contains a variable; but otherwise the type is preserved)
4326  *      rel: RelOptInfo for relation containing variable; NULL if expression
4327  *              contains no Vars (NOTE this could point to a RelOptInfo of a
4328  *              subquery, not one in the current query).
4329  *      statsTuple: the pg_statistic entry for the variable, if one exists;
4330  *              otherwise NULL.
4331  *      freefunc: pointer to a function to release statsTuple with.
4332  *      vartype: exposed type of the expression; this should always match
4333  *              the declared input type of the operator we are estimating for.
4334  *      atttype, atttypmod: type data to pass to get_attstatsslot().  This is
4335  *              commonly the same as the exposed type of the variable argument,
4336  *              but can be different in binary-compatible-type cases.
4337  *      isunique: TRUE if we were able to match the var to a unique index or a
4338  *              single-column DISTINCT clause, implying its values are unique for
4339  *              this query.  (Caution: this should be trusted for statistical
4340  *              purposes only, since we do not check indimmediate nor verify that
4341  *              the exact same definition of equality applies.)
4342  *
4343  * Caller is responsible for doing ReleaseVariableStats() before exiting.
4344  */
4345 void
4346 examine_variable(PlannerInfo *root, Node *node, int varRelid,
4347                                  VariableStatData *vardata)
4348 {
4349         Node       *basenode;
4350         Relids          varnos;
4351         RelOptInfo *onerel;
4352
4353         /* Make sure we don't return dangling pointers in vardata */
4354         MemSet(vardata, 0, sizeof(VariableStatData));
4355
4356         /* Save the exposed type of the expression */
4357         vardata->vartype = exprType(node);
4358
4359         /* Look inside any binary-compatible relabeling */
4360
4361         if (IsA(node, RelabelType))
4362                 basenode = (Node *) ((RelabelType *) node)->arg;
4363         else
4364                 basenode = node;
4365
4366         /* Fast path for a simple Var */
4367
4368         if (IsA(basenode, Var) &&
4369                 (varRelid == 0 || varRelid == ((Var *) basenode)->varno))
4370         {
4371                 Var                *var = (Var *) basenode;
4372
4373                 /* Set up result fields other than the stats tuple */
4374                 vardata->var = basenode;        /* return Var without relabeling */
4375                 vardata->rel = find_base_rel(root, var->varno);
4376                 vardata->atttype = var->vartype;
4377                 vardata->atttypmod = var->vartypmod;
4378                 vardata->isunique = has_unique_index(vardata->rel, var->varattno);
4379
4380                 /* Try to locate some stats */
4381                 examine_simple_variable(root, var, vardata);
4382
4383                 return;
4384         }
4385
4386         /*
4387          * Okay, it's a more complicated expression.  Determine variable
4388          * membership.  Note that when varRelid isn't zero, only vars of that
4389          * relation are considered "real" vars.
4390          */
4391         varnos = pull_varnos(basenode);
4392
4393         onerel = NULL;
4394
4395         switch (bms_membership(varnos))
4396         {
4397                 case BMS_EMPTY_SET:
4398                         /* No Vars at all ... must be pseudo-constant clause */
4399                         break;
4400                 case BMS_SINGLETON:
4401                         if (varRelid == 0 || bms_is_member(varRelid, varnos))
4402                         {
4403                                 onerel = find_base_rel(root,
4404                                            (varRelid ? varRelid : bms_singleton_member(varnos)));
4405                                 vardata->rel = onerel;
4406                                 node = basenode;        /* strip any relabeling */
4407                         }
4408                         /* else treat it as a constant */
4409                         break;
4410                 case BMS_MULTIPLE:
4411                         if (varRelid == 0)
4412                         {
4413                                 /* treat it as a variable of a join relation */
4414                                 vardata->rel = find_join_rel(root, varnos);
4415                                 node = basenode;        /* strip any relabeling */
4416                         }
4417                         else if (bms_is_member(varRelid, varnos))
4418                         {
4419                                 /* ignore the vars belonging to other relations */
4420                                 vardata->rel = find_base_rel(root, varRelid);
4421                                 node = basenode;        /* strip any relabeling */
4422                                 /* note: no point in expressional-index search here */
4423                         }
4424                         /* else treat it as a constant */
4425                         break;
4426         }
4427
4428         bms_free(varnos);
4429
4430         vardata->var = node;
4431         vardata->atttype = exprType(node);
4432         vardata->atttypmod = exprTypmod(node);
4433
4434         if (onerel)
4435         {
4436                 /*
4437                  * We have an expression in vars of a single relation.  Try to match
4438                  * it to expressional index columns, in hopes of finding some
4439                  * statistics.
4440                  *
4441                  * XXX it's conceivable that there are multiple matches with different
4442                  * index opfamilies; if so, we need to pick one that matches the
4443                  * operator we are estimating for.  FIXME later.
4444                  */
4445                 ListCell   *ilist;
4446
4447                 foreach(ilist, onerel->indexlist)
4448                 {
4449                         IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
4450                         ListCell   *indexpr_item;
4451                         int                     pos;
4452
4453                         indexpr_item = list_head(index->indexprs);
4454                         if (indexpr_item == NULL)
4455                                 continue;               /* no expressions here... */
4456
4457                         for (pos = 0; pos < index->ncolumns; pos++)
4458                         {
4459                                 if (index->indexkeys[pos] == 0)
4460                                 {
4461                                         Node       *indexkey;
4462
4463                                         if (indexpr_item == NULL)
4464                                                 elog(ERROR, "too few entries in indexprs list");
4465                                         indexkey = (Node *) lfirst(indexpr_item);
4466                                         if (indexkey && IsA(indexkey, RelabelType))
4467                                                 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4468                                         if (equal(node, indexkey))
4469                                         {
4470                                                 /*
4471                                                  * Found a match ... is it a unique index? Tests here
4472                                                  * should match has_unique_index().
4473                                                  */
4474                                                 if (index->unique &&
4475                                                         index->ncolumns == 1 &&
4476                                                         (index->indpred == NIL || index->predOK))
4477                                                         vardata->isunique = true;
4478
4479                                                 /*
4480                                                  * Has it got stats?  We only consider stats for
4481                                                  * non-partial indexes, since partial indexes probably
4482                                                  * don't reflect whole-relation statistics; the above
4483                                                  * check for uniqueness is the only info we take from
4484                                                  * a partial index.
4485                                                  *
4486                                                  * An index stats hook, however, must make its own
4487                                                  * decisions about what to do with partial indexes.
4488                                                  */
4489                                                 if (get_index_stats_hook &&
4490                                                         (*get_index_stats_hook) (root, index->indexoid,
4491                                                                                                          pos + 1, vardata))
4492                                                 {
4493                                                         /*
4494                                                          * The hook took control of acquiring a stats
4495                                                          * tuple.  If it did supply a tuple, it'd better
4496                                                          * have supplied a freefunc.
4497                                                          */
4498                                                         if (HeapTupleIsValid(vardata->statsTuple) &&
4499                                                                 !vardata->freefunc)
4500                                                                 elog(ERROR, "no function provided to release variable stats with");
4501                                                 }
4502                                                 else if (index->indpred == NIL)
4503                                                 {
4504                                                         vardata->statsTuple =
4505                                                                 SearchSysCache3(STATRELATTINH,
4506                                                                                    ObjectIdGetDatum(index->indexoid),
4507                                                                                                 Int16GetDatum(pos + 1),
4508                                                                                                 BoolGetDatum(false));
4509                                                         vardata->freefunc = ReleaseSysCache;
4510                                                 }
4511                                                 if (vardata->statsTuple)
4512                                                         break;
4513                                         }
4514                                         indexpr_item = lnext(indexpr_item);
4515                                 }
4516                         }
4517                         if (vardata->statsTuple)
4518                                 break;
4519                 }
4520         }
4521 }
4522
4523 /*
4524  * examine_simple_variable
4525  *              Handle a simple Var for examine_variable
4526  *
4527  * This is split out as a subroutine so that we can recurse to deal with
4528  * Vars referencing subqueries.
4529  *
4530  * We already filled in all the fields of *vardata except for the stats tuple.
4531  */
4532 static void
4533 examine_simple_variable(PlannerInfo *root, Var *var,
4534                                                 VariableStatData *vardata)
4535 {
4536         RangeTblEntry *rte = root->simple_rte_array[var->varno];
4537
4538         Assert(IsA(rte, RangeTblEntry));
4539
4540         if (get_relation_stats_hook &&
4541                 (*get_relation_stats_hook) (root, rte, var->varattno, vardata))
4542         {
4543                 /*
4544                  * The hook took control of acquiring a stats tuple.  If it did supply
4545                  * a tuple, it'd better have supplied a freefunc.
4546                  */
4547                 if (HeapTupleIsValid(vardata->statsTuple) &&
4548                         !vardata->freefunc)
4549                         elog(ERROR, "no function provided to release variable stats with");
4550         }
4551         else if (rte->rtekind == RTE_RELATION)
4552         {
4553                 /*
4554                  * Plain table or parent of an inheritance appendrel, so look up the
4555                  * column in pg_statistic
4556                  */
4557                 vardata->statsTuple = SearchSysCache3(STATRELATTINH,
4558                                                                                           ObjectIdGetDatum(rte->relid),
4559                                                                                           Int16GetDatum(var->varattno),
4560                                                                                           BoolGetDatum(rte->inh));
4561                 vardata->freefunc = ReleaseSysCache;
4562         }
4563         else if (rte->rtekind == RTE_SUBQUERY && !rte->inh)
4564         {
4565                 /*
4566                  * Plain subquery (not one that was converted to an appendrel).
4567                  */
4568                 Query      *subquery = rte->subquery;
4569                 RelOptInfo *rel;
4570                 TargetEntry *ste;
4571
4572                 /*
4573                  * Punt if it's a whole-row var rather than a plain column reference.
4574                  */
4575                 if (var->varattno == InvalidAttrNumber)
4576                         return;
4577
4578                 /*
4579                  * Punt if subquery uses set operations or GROUP BY, as these will
4580                  * mash underlying columns' stats beyond recognition.  (Set ops are
4581                  * particularly nasty; if we forged ahead, we would return stats
4582                  * relevant to only the leftmost subselect...)  DISTINCT is also
4583                  * problematic, but we check that later because there is a possibility
4584                  * of learning something even with it.
4585                  */
4586                 if (subquery->setOperations ||
4587                         subquery->groupClause)
4588                         return;
4589
4590                 /*
4591                  * OK, fetch RelOptInfo for subquery.  Note that we don't change the
4592                  * rel returned in vardata, since caller expects it to be a rel of the
4593                  * caller's query level.  Because we might already be recursing, we
4594                  * can't use that rel pointer either, but have to look up the Var's
4595                  * rel afresh.
4596                  */
4597                 rel = find_base_rel(root, var->varno);
4598
4599                 /* If the subquery hasn't been planned yet, we have to punt */
4600                 if (rel->subroot == NULL)
4601                         return;
4602                 Assert(IsA(rel->subroot, PlannerInfo));
4603
4604                 /*
4605                  * Switch our attention to the subquery as mangled by the planner. It
4606                  * was okay to look at the pre-planning version for the tests above,
4607                  * but now we need a Var that will refer to the subroot's live
4608                  * RelOptInfos.  For instance, if any subquery pullup happened during
4609                  * planning, Vars in the targetlist might have gotten replaced, and we
4610                  * need to see the replacement expressions.
4611                  */
4612                 subquery = rel->subroot->parse;
4613                 Assert(IsA(subquery, Query));
4614
4615                 /* Get the subquery output expression referenced by the upper Var */
4616                 ste = get_tle_by_resno(subquery->targetList, var->varattno);
4617                 if (ste == NULL || ste->resjunk)
4618                         elog(ERROR, "subquery %s does not have attribute %d",
4619                                  rte->eref->aliasname, var->varattno);
4620                 var = (Var *) ste->expr;
4621
4622                 /*
4623                  * If subquery uses DISTINCT, we can't make use of any stats for the
4624                  * variable ... but, if it's the only DISTINCT column, we are entitled
4625                  * to consider it unique.  We do the test this way so that it works
4626                  * for cases involving DISTINCT ON.
4627                  */
4628                 if (subquery->distinctClause)
4629                 {
4630                         if (list_length(subquery->distinctClause) == 1 &&
4631                                 targetIsInSortList(ste, InvalidOid, subquery->distinctClause))
4632                                 vardata->isunique = true;
4633                         /* cannot go further */
4634                         return;
4635                 }
4636
4637                 /*
4638                  * If the sub-query originated from a view with the security_barrier
4639                  * attribute, we must not look at the variable's statistics, though it
4640                  * seems all right to notice the existence of a DISTINCT clause. So
4641                  * stop here.
4642                  *
4643                  * This is probably a harsher restriction than necessary; it's
4644                  * certainly OK for the selectivity estimator (which is a C function,
4645                  * and therefore omnipotent anyway) to look at the statistics.  But
4646                  * many selectivity estimators will happily *invoke the operator
4647                  * function* to try to work out a good estimate - and that's not OK.
4648                  * So for now, don't dig down for stats.
4649                  */
4650                 if (rte->security_barrier)
4651                         return;
4652
4653                 /* Can only handle a simple Var of subquery's query level */
4654                 if (var && IsA(var, Var) &&
4655                         var->varlevelsup == 0)
4656                 {
4657                         /*
4658                          * OK, recurse into the subquery.  Note that the original setting
4659                          * of vardata->isunique (which will surely be false) is left
4660                          * unchanged in this situation.  That's what we want, since even
4661                          * if the underlying column is unique, the subquery may have
4662                          * joined to other tables in a way that creates duplicates.
4663                          */
4664                         examine_simple_variable(rel->subroot, var, vardata);
4665                 }
4666         }
4667         else
4668         {
4669                 /*
4670                  * Otherwise, the Var comes from a FUNCTION, VALUES, or CTE RTE.  (We
4671                  * won't see RTE_JOIN here because join alias Vars have already been
4672                  * flattened.)  There's not much we can do with function outputs, but
4673                  * maybe someday try to be smarter about VALUES and/or CTEs.
4674                  */
4675         }
4676 }
4677
4678 /*
4679  * get_variable_numdistinct
4680  *        Estimate the number of distinct values of a variable.
4681  *
4682  * vardata: results of examine_variable
4683  * *isdefault: set to TRUE if the result is a default rather than based on
4684  * anything meaningful.
4685  *
4686  * NB: be careful to produce a positive integral result, since callers may
4687  * compare the result to exact integer counts, or might divide by it.
4688  */
4689 double
4690 get_variable_numdistinct(VariableStatData *vardata, bool *isdefault)
4691 {
4692         double          stadistinct;
4693         double          ntuples;
4694
4695         *isdefault = false;
4696
4697         /*
4698          * Determine the stadistinct value to use.  There are cases where we can
4699          * get an estimate even without a pg_statistic entry, or can get a better
4700          * value than is in pg_statistic.
4701          */
4702         if (HeapTupleIsValid(vardata->statsTuple))
4703         {
4704                 /* Use the pg_statistic entry */
4705                 Form_pg_statistic stats;
4706
4707                 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
4708                 stadistinct = stats->stadistinct;
4709         }
4710         else if (vardata->vartype == BOOLOID)
4711         {
4712                 /*
4713                  * Special-case boolean columns: presumably, two distinct values.
4714                  *
4715                  * Are there any other datatypes we should wire in special estimates
4716                  * for?
4717                  */
4718                 stadistinct = 2.0;
4719         }
4720         else
4721         {
4722                 /*
4723                  * We don't keep statistics for system columns, but in some cases we
4724                  * can infer distinctness anyway.
4725                  */
4726                 if (vardata->var && IsA(vardata->var, Var))
4727                 {
4728                         switch (((Var *) vardata->var)->varattno)
4729                         {
4730                                 case ObjectIdAttributeNumber:
4731                                 case SelfItemPointerAttributeNumber:
4732                                         stadistinct = -1.0; /* unique */
4733                                         break;
4734                                 case TableOidAttributeNumber:
4735                                         stadistinct = 1.0;      /* only 1 value */
4736                                         break;
4737                                 default:
4738                                         stadistinct = 0.0;      /* means "unknown" */
4739                                         break;
4740                         }
4741                 }
4742                 else
4743                         stadistinct = 0.0;      /* means "unknown" */
4744
4745                 /*
4746                  * XXX consider using estimate_num_groups on expressions?
4747                  */
4748         }
4749
4750         /*
4751          * If there is a unique index or DISTINCT clause for the variable, assume
4752          * it is unique no matter what pg_statistic says; the statistics could be
4753          * out of date, or we might have found a partial unique index that proves
4754          * the var is unique for this query.
4755          */
4756         if (vardata->isunique)
4757                 stadistinct = -1.0;
4758
4759         /*
4760          * If we had an absolute estimate, use that.
4761          */
4762         if (stadistinct > 0.0)
4763                 return clamp_row_est(stadistinct);
4764
4765         /*
4766          * Otherwise we need to get the relation size; punt if not available.
4767          */
4768         if (vardata->rel == NULL)
4769         {
4770                 *isdefault = true;
4771                 return DEFAULT_NUM_DISTINCT;
4772         }
4773         ntuples = vardata->rel->tuples;
4774         if (ntuples <= 0.0)
4775         {
4776                 *isdefault = true;
4777                 return DEFAULT_NUM_DISTINCT;
4778         }
4779
4780         /*
4781          * If we had a relative estimate, use that.
4782          */
4783         if (stadistinct < 0.0)
4784                 return clamp_row_est(-stadistinct * ntuples);
4785
4786         /*
4787          * With no data, estimate ndistinct = ntuples if the table is small, else
4788          * use default.  We use DEFAULT_NUM_DISTINCT as the cutoff for "small" so
4789          * that the behavior isn't discontinuous.
4790          */
4791         if (ntuples < DEFAULT_NUM_DISTINCT)
4792                 return clamp_row_est(ntuples);
4793
4794         *isdefault = true;
4795         return DEFAULT_NUM_DISTINCT;
4796 }
4797
4798 /*
4799  * get_variable_range
4800  *              Estimate the minimum and maximum value of the specified variable.
4801  *              If successful, store values in *min and *max, and return TRUE.
4802  *              If no data available, return FALSE.
4803  *
4804  * sortop is the "<" comparison operator to use.  This should generally
4805  * be "<" not ">", as only the former is likely to be found in pg_statistic.
4806  */
4807 static bool
4808 get_variable_range(PlannerInfo *root, VariableStatData *vardata, Oid sortop,
4809                                    Datum *min, Datum *max)
4810 {
4811         Datum           tmin = 0;
4812         Datum           tmax = 0;
4813         bool            have_data = false;
4814         int16           typLen;
4815         bool            typByVal;
4816         Datum      *values;
4817         int                     nvalues;
4818         int                     i;
4819
4820         /*
4821          * XXX It's very tempting to try to use the actual column min and max, if
4822          * we can get them relatively-cheaply with an index probe.  However, since
4823          * this function is called many times during join planning, that could
4824          * have unpleasant effects on planning speed.  Need more investigation
4825          * before enabling this.
4826          */
4827 #ifdef NOT_USED
4828         if (get_actual_variable_range(root, vardata, sortop, min, max))
4829                 return true;
4830 #endif
4831
4832         if (!HeapTupleIsValid(vardata->statsTuple))
4833         {
4834                 /* no stats available, so default result */
4835                 return false;
4836         }
4837
4838         get_typlenbyval(vardata->atttype, &typLen, &typByVal);
4839
4840         /*
4841          * If there is a histogram, grab the first and last values.
4842          *
4843          * If there is a histogram that is sorted with some other operator than
4844          * the one we want, fail --- this suggests that there is data we can't
4845          * use.
4846          */
4847         if (get_attstatsslot(vardata->statsTuple,
4848                                                  vardata->atttype, vardata->atttypmod,
4849                                                  STATISTIC_KIND_HISTOGRAM, sortop,
4850                                                  NULL,
4851                                                  &values, &nvalues,
4852                                                  NULL, NULL))
4853         {
4854                 if (nvalues > 0)
4855                 {
4856                         tmin = datumCopy(values[0], typByVal, typLen);
4857                         tmax = datumCopy(values[nvalues - 1], typByVal, typLen);
4858                         have_data = true;
4859                 }
4860                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
4861         }
4862         else if (get_attstatsslot(vardata->statsTuple,
4863                                                           vardata->atttype, vardata->atttypmod,
4864                                                           STATISTIC_KIND_HISTOGRAM, InvalidOid,
4865                                                           NULL,
4866                                                           &values, &nvalues,
4867                                                           NULL, NULL))
4868         {
4869                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
4870                 return false;
4871         }
4872
4873         /*
4874          * If we have most-common-values info, look for extreme MCVs.  This is
4875          * needed even if we also have a histogram, since the histogram excludes
4876          * the MCVs.  However, usually the MCVs will not be the extreme values, so
4877          * avoid unnecessary data copying.
4878          */
4879         if (get_attstatsslot(vardata->statsTuple,
4880                                                  vardata->atttype, vardata->atttypmod,
4881                                                  STATISTIC_KIND_MCV, InvalidOid,
4882                                                  NULL,
4883                                                  &values, &nvalues,
4884                                                  NULL, NULL))
4885         {
4886                 bool            tmin_is_mcv = false;
4887                 bool            tmax_is_mcv = false;
4888                 FmgrInfo        opproc;
4889
4890                 fmgr_info(get_opcode(sortop), &opproc);
4891
4892                 for (i = 0; i < nvalues; i++)
4893                 {
4894                         if (!have_data)
4895                         {
4896                                 tmin = tmax = values[i];
4897                                 tmin_is_mcv = tmax_is_mcv = have_data = true;
4898                                 continue;
4899                         }
4900                         if (DatumGetBool(FunctionCall2Coll(&opproc,
4901                                                                                            DEFAULT_COLLATION_OID,
4902                                                                                            values[i], tmin)))
4903                         {
4904                                 tmin = values[i];
4905                                 tmin_is_mcv = true;
4906                         }
4907                         if (DatumGetBool(FunctionCall2Coll(&opproc,
4908                                                                                            DEFAULT_COLLATION_OID,
4909                                                                                            tmax, values[i])))
4910                         {
4911                                 tmax = values[i];
4912                                 tmax_is_mcv = true;
4913                         }
4914                 }
4915                 if (tmin_is_mcv)
4916                         tmin = datumCopy(tmin, typByVal, typLen);
4917                 if (tmax_is_mcv)
4918                         tmax = datumCopy(tmax, typByVal, typLen);
4919                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
4920         }
4921
4922         *min = tmin;
4923         *max = tmax;
4924         return have_data;
4925 }
4926
4927
4928 /*
4929  * get_actual_variable_range
4930  *              Attempt to identify the current *actual* minimum and/or maximum
4931  *              of the specified variable, by looking for a suitable btree index
4932  *              and fetching its low and/or high values.
4933  *              If successful, store values in *min and *max, and return TRUE.
4934  *              (Either pointer can be NULL if that endpoint isn't needed.)
4935  *              If no data available, return FALSE.
4936  *
4937  * sortop is the "<" comparison operator to use.
4938  */
4939 static bool
4940 get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
4941                                                   Oid sortop,
4942                                                   Datum *min, Datum *max)
4943 {
4944         bool            have_data = false;
4945         RelOptInfo *rel = vardata->rel;
4946         RangeTblEntry *rte;
4947         ListCell   *lc;
4948
4949         /* No hope if no relation or it doesn't have indexes */
4950         if (rel == NULL || rel->indexlist == NIL)
4951                 return false;
4952         /* If it has indexes it must be a plain relation */
4953         rte = root->simple_rte_array[rel->relid];
4954         Assert(rte->rtekind == RTE_RELATION);
4955
4956         /* Search through the indexes to see if any match our problem */
4957         foreach(lc, rel->indexlist)
4958         {
4959                 IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
4960                 ScanDirection indexscandir;
4961
4962                 /* Ignore non-btree indexes */
4963                 if (index->relam != BTREE_AM_OID)
4964                         continue;
4965
4966                 /*
4967                  * Ignore partial indexes --- we only want stats that cover the entire
4968                  * relation.
4969                  */
4970                 if (index->indpred != NIL)
4971                         continue;
4972
4973                 /*
4974                  * The index list might include hypothetical indexes inserted by a
4975                  * get_relation_info hook --- don't try to access them.
4976                  */
4977                 if (index->hypothetical)
4978                         continue;
4979
4980                 /*
4981                  * The first index column must match the desired variable and sort
4982                  * operator --- but we can use a descending-order index.
4983                  */
4984                 if (!match_index_to_operand(vardata->var, 0, index))
4985                         continue;
4986                 switch (get_op_opfamily_strategy(sortop, index->sortopfamily[0]))
4987                 {
4988                         case BTLessStrategyNumber:
4989                                 if (index->reverse_sort[0])
4990                                         indexscandir = BackwardScanDirection;
4991                                 else
4992                                         indexscandir = ForwardScanDirection;
4993                                 break;
4994                         case BTGreaterStrategyNumber:
4995                                 if (index->reverse_sort[0])
4996                                         indexscandir = ForwardScanDirection;
4997                                 else
4998                                         indexscandir = BackwardScanDirection;
4999                                 break;
5000                         default:
5001                                 /* index doesn't match the sortop */
5002                                 continue;
5003                 }
5004
5005                 /*
5006                  * Found a suitable index to extract data from.  We'll need an EState
5007                  * and a bunch of other infrastructure.
5008                  */
5009                 {
5010                         EState     *estate;
5011                         ExprContext *econtext;
5012                         MemoryContext tmpcontext;
5013                         MemoryContext oldcontext;
5014                         Relation        heapRel;
5015                         Relation        indexRel;
5016                         IndexInfo  *indexInfo;
5017                         TupleTableSlot *slot;
5018                         int16           typLen;
5019                         bool            typByVal;
5020                         ScanKeyData scankeys[1];
5021                         IndexScanDesc index_scan;
5022                         HeapTuple       tup;
5023                         Datum           values[INDEX_MAX_KEYS];
5024                         bool            isnull[INDEX_MAX_KEYS];
5025                         SnapshotData SnapshotDirty;
5026
5027                         estate = CreateExecutorState();
5028                         econtext = GetPerTupleExprContext(estate);
5029                         /* Make sure any cruft is generated in the econtext's memory */
5030                         tmpcontext = econtext->ecxt_per_tuple_memory;
5031                         oldcontext = MemoryContextSwitchTo(tmpcontext);
5032
5033                         /*
5034                          * Open the table and index so we can read from them.  We should
5035                          * already have at least AccessShareLock on the table, but not
5036                          * necessarily on the index.
5037                          */
5038                         heapRel = heap_open(rte->relid, NoLock);
5039                         indexRel = index_open(index->indexoid, AccessShareLock);
5040
5041                         /* extract index key information from the index's pg_index info */
5042                         indexInfo = BuildIndexInfo(indexRel);
5043
5044                         /* some other stuff */
5045                         slot = MakeSingleTupleTableSlot(RelationGetDescr(heapRel));
5046                         econtext->ecxt_scantuple = slot;
5047                         get_typlenbyval(vardata->atttype, &typLen, &typByVal);
5048                         InitDirtySnapshot(SnapshotDirty);
5049
5050                         /* set up an IS NOT NULL scan key so that we ignore nulls */
5051                         ScanKeyEntryInitialize(&scankeys[0],
5052                                                                    SK_ISNULL | SK_SEARCHNOTNULL,
5053                                                                    1,   /* index col to scan */
5054                                                                    InvalidStrategy,             /* no strategy */
5055                                                                    InvalidOid,  /* no strategy subtype */
5056                                                                    InvalidOid,  /* no collation */
5057                                                                    InvalidOid,  /* no reg proc for this */
5058                                                                    (Datum) 0);  /* constant */
5059
5060                         have_data = true;
5061
5062                         /* If min is requested ... */
5063                         if (min)
5064                         {
5065                                 /*
5066                                  * In principle, we should scan the index with our current
5067                                  * active snapshot, which is the best approximation we've got
5068                                  * to what the query will see when executed.  But that won't
5069                                  * be exact if a new snap is taken before running the query,
5070                                  * and it can be very expensive if a lot of uncommitted rows
5071                                  * exist at the end of the index (because we'll laboriously
5072                                  * fetch each one and reject it).  What seems like a good
5073                                  * compromise is to use SnapshotDirty.  That will accept
5074                                  * uncommitted rows, and thus avoid fetching multiple heap
5075                                  * tuples in this scenario.  On the other hand, it will reject
5076                                  * known-dead rows, and thus not give a bogus answer when the
5077                                  * extreme value has been deleted; that case motivates not
5078                                  * using SnapshotAny here.
5079                                  */
5080                                 index_scan = index_beginscan(heapRel, indexRel, &SnapshotDirty,
5081                                                                                          1, 0);
5082                                 index_rescan(index_scan, scankeys, 1, NULL, 0);
5083
5084                                 /* Fetch first tuple in sortop's direction */
5085                                 if ((tup = index_getnext(index_scan,
5086                                                                                  indexscandir)) != NULL)
5087                                 {
5088                                         /* Extract the index column values from the heap tuple */
5089                                         ExecStoreTuple(tup, slot, InvalidBuffer, false);
5090                                         FormIndexDatum(indexInfo, slot, estate,
5091                                                                    values, isnull);
5092
5093                                         /* Shouldn't have got a null, but be careful */
5094                                         if (isnull[0])
5095                                                 elog(ERROR, "found unexpected null value in index \"%s\"",
5096                                                          RelationGetRelationName(indexRel));
5097
5098                                         /* Copy the index column value out to caller's context */
5099                                         MemoryContextSwitchTo(oldcontext);
5100                                         *min = datumCopy(values[0], typByVal, typLen);
5101                                         MemoryContextSwitchTo(tmpcontext);
5102                                 }
5103                                 else
5104                                         have_data = false;
5105
5106                                 index_endscan(index_scan);
5107                         }
5108
5109                         /* If max is requested, and we didn't find the index is empty */
5110                         if (max && have_data)
5111                         {
5112                                 index_scan = index_beginscan(heapRel, indexRel, &SnapshotDirty,
5113                                                                                          1, 0);
5114                                 index_rescan(index_scan, scankeys, 1, NULL, 0);
5115
5116                                 /* Fetch first tuple in reverse direction */
5117                                 if ((tup = index_getnext(index_scan,
5118                                                                                  -indexscandir)) != NULL)
5119                                 {
5120                                         /* Extract the index column values from the heap tuple */
5121                                         ExecStoreTuple(tup, slot, InvalidBuffer, false);
5122                                         FormIndexDatum(indexInfo, slot, estate,
5123                                                                    values, isnull);
5124
5125                                         /* Shouldn't have got a null, but be careful */
5126                                         if (isnull[0])
5127                                                 elog(ERROR, "found unexpected null value in index \"%s\"",
5128                                                          RelationGetRelationName(indexRel));
5129
5130                                         /* Copy the index column value out to caller's context */
5131                                         MemoryContextSwitchTo(oldcontext);
5132                                         *max = datumCopy(values[0], typByVal, typLen);
5133                                         MemoryContextSwitchTo(tmpcontext);
5134                                 }
5135                                 else
5136                                         have_data = false;
5137
5138                                 index_endscan(index_scan);
5139                         }
5140
5141                         /* Clean everything up */
5142                         ExecDropSingleTupleTableSlot(slot);
5143
5144                         index_close(indexRel, AccessShareLock);
5145                         heap_close(heapRel, NoLock);
5146
5147                         MemoryContextSwitchTo(oldcontext);
5148                         FreeExecutorState(estate);
5149
5150                         /* And we're done */
5151                         break;
5152                 }
5153         }
5154
5155         return have_data;
5156 }
5157
5158 /*
5159  * find_join_input_rel
5160  *              Look up the input relation for a join.
5161  *
5162  * We assume that the input relation's RelOptInfo must have been constructed
5163  * already.
5164  */
5165 static RelOptInfo *
5166 find_join_input_rel(PlannerInfo *root, Relids relids)
5167 {
5168         RelOptInfo *rel = NULL;
5169
5170         switch (bms_membership(relids))
5171         {
5172                 case BMS_EMPTY_SET:
5173                         /* should not happen */
5174                         break;
5175                 case BMS_SINGLETON:
5176                         rel = find_base_rel(root, bms_singleton_member(relids));
5177                         break;
5178                 case BMS_MULTIPLE:
5179                         rel = find_join_rel(root, relids);
5180                         break;
5181         }
5182
5183         if (rel == NULL)
5184                 elog(ERROR, "could not find RelOptInfo for given relids");
5185
5186         return rel;
5187 }
5188
5189
5190 /*-------------------------------------------------------------------------
5191  *
5192  * Pattern analysis functions
5193  *
5194  * These routines support analysis of LIKE and regular-expression patterns
5195  * by the planner/optimizer.  It's important that they agree with the
5196  * regular-expression code in backend/regex/ and the LIKE code in
5197  * backend/utils/adt/like.c.  Also, the computation of the fixed prefix
5198  * must be conservative: if we report a string longer than the true fixed
5199  * prefix, the query may produce actually wrong answers, rather than just
5200  * getting a bad selectivity estimate!
5201  *
5202  * Note that the prefix-analysis functions are called from
5203  * backend/optimizer/path/indxpath.c as well as from routines in this file.
5204  *
5205  *-------------------------------------------------------------------------
5206  */
5207
5208 /*
5209  * Check whether char is a letter (and, hence, subject to case-folding)
5210  *
5211  * In multibyte character sets, we can't use isalpha, and it does not seem
5212  * worth trying to convert to wchar_t to use iswalpha.  Instead, just assume
5213  * any multibyte char is potentially case-varying.
5214  */
5215 static int
5216 pattern_char_isalpha(char c, bool is_multibyte,
5217                                          pg_locale_t locale, bool locale_is_c)
5218 {
5219         if (locale_is_c)
5220                 return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
5221         else if (is_multibyte && IS_HIGHBIT_SET(c))
5222                 return true;
5223 #ifdef HAVE_LOCALE_T
5224         else if (locale)
5225                 return isalpha_l((unsigned char) c, locale);
5226 #endif
5227         else
5228                 return isalpha((unsigned char) c);
5229 }
5230
5231 /*
5232  * Extract the fixed prefix, if any, for a pattern.
5233  *
5234  * *prefix is set to a palloc'd prefix string (in the form of a Const node),
5235  *      or to NULL if no fixed prefix exists for the pattern.
5236  * If rest_selec is not NULL, *rest_selec is set to an estimate of the
5237  *      selectivity of the remainder of the pattern (without any fixed prefix).
5238  * The prefix Const has the same type (TEXT or BYTEA) as the input pattern.
5239  *
5240  * The return value distinguishes no fixed prefix, a partial prefix,
5241  * or an exact-match-only pattern.
5242  */
5243
5244 static Pattern_Prefix_Status
5245 like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
5246                                   Const **prefix_const, Selectivity *rest_selec)
5247 {
5248         char       *match;
5249         char       *patt;
5250         int                     pattlen;
5251         Oid                     typeid = patt_const->consttype;
5252         int                     pos,
5253                                 match_pos;
5254         bool            is_multibyte = (pg_database_encoding_max_length() > 1);
5255         pg_locale_t locale = 0;
5256         bool            locale_is_c = false;
5257
5258         /* the right-hand const is type text or bytea */
5259         Assert(typeid == BYTEAOID || typeid == TEXTOID);
5260
5261         if (case_insensitive)
5262         {
5263                 if (typeid == BYTEAOID)
5264                         ereport(ERROR,
5265                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5266                         errmsg("case insensitive matching not supported on type bytea")));
5267
5268                 /* If case-insensitive, we need locale info */
5269                 if (lc_ctype_is_c(collation))
5270                         locale_is_c = true;
5271                 else if (collation != DEFAULT_COLLATION_OID)
5272                 {
5273                         if (!OidIsValid(collation))
5274                         {
5275                                 /*
5276                                  * This typically means that the parser could not resolve a
5277                                  * conflict of implicit collations, so report it that way.
5278                                  */
5279                                 ereport(ERROR,
5280                                                 (errcode(ERRCODE_INDETERMINATE_COLLATION),
5281                                                  errmsg("could not determine which collation to use for ILIKE"),
5282                                                  errhint("Use the COLLATE clause to set the collation explicitly.")));
5283                         }
5284                         locale = pg_newlocale_from_collation(collation);
5285                 }
5286         }
5287
5288         if (typeid != BYTEAOID)
5289         {
5290                 patt = TextDatumGetCString(patt_const->constvalue);
5291                 pattlen = strlen(patt);
5292         }
5293         else
5294         {
5295                 bytea      *bstr = DatumGetByteaP(patt_const->constvalue);
5296
5297                 pattlen = VARSIZE(bstr) - VARHDRSZ;
5298                 patt = (char *) palloc(pattlen);
5299                 memcpy(patt, VARDATA(bstr), pattlen);
5300                 if ((Pointer) bstr != DatumGetPointer(patt_const->constvalue))
5301                         pfree(bstr);
5302         }
5303
5304         match = palloc(pattlen + 1);
5305         match_pos = 0;
5306         for (pos = 0; pos < pattlen; pos++)
5307         {
5308                 /* % and _ are wildcard characters in LIKE */
5309                 if (patt[pos] == '%' ||
5310                         patt[pos] == '_')
5311                         break;
5312
5313                 /* Backslash escapes the next character */
5314                 if (patt[pos] == '\\')
5315                 {
5316                         pos++;
5317                         if (pos >= pattlen)
5318                                 break;
5319                 }
5320
5321                 /* Stop if case-varying character (it's sort of a wildcard) */
5322                 if (case_insensitive &&
5323                   pattern_char_isalpha(patt[pos], is_multibyte, locale, locale_is_c))
5324                         break;
5325
5326                 match[match_pos++] = patt[pos];
5327         }
5328
5329         match[match_pos] = '\0';
5330
5331         if (typeid != BYTEAOID)
5332                 *prefix_const = string_to_const(match, typeid);
5333         else
5334                 *prefix_const = string_to_bytea_const(match, match_pos);
5335
5336         if (rest_selec != NULL)
5337                 *rest_selec = like_selectivity(&patt[pos], pattlen - pos,
5338                                                                            case_insensitive);
5339
5340         pfree(patt);
5341         pfree(match);
5342
5343         /* in LIKE, an empty pattern is an exact match! */
5344         if (pos == pattlen)
5345                 return Pattern_Prefix_Exact;    /* reached end of pattern, so exact */
5346
5347         if (match_pos > 0)
5348                 return Pattern_Prefix_Partial;
5349
5350         return Pattern_Prefix_None;
5351 }
5352
5353 static Pattern_Prefix_Status
5354 regex_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
5355                                    Const **prefix_const, Selectivity *rest_selec)
5356 {
5357         Oid                     typeid = patt_const->consttype;
5358         char       *prefix;
5359         bool            exact;
5360
5361         /*
5362          * Should be unnecessary, there are no bytea regex operators defined. As
5363          * such, it should be noted that the rest of this function has *not* been
5364          * made safe for binary (possibly NULL containing) strings.
5365          */
5366         if (typeid == BYTEAOID)
5367                 ereport(ERROR,
5368                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5369                  errmsg("regular-expression matching not supported on type bytea")));
5370
5371         /* Use the regexp machinery to extract the prefix, if any */
5372         prefix = regexp_fixed_prefix(DatumGetTextPP(patt_const->constvalue),
5373                                                                  case_insensitive, collation,
5374                                                                  &exact);
5375
5376         if (prefix == NULL)
5377         {
5378                 *prefix_const = NULL;
5379
5380                 if (rest_selec != NULL)
5381                 {
5382                         char       *patt = TextDatumGetCString(patt_const->constvalue);
5383
5384                         *rest_selec = regex_selectivity(patt, strlen(patt),
5385                                                                                         case_insensitive,
5386                                                                                         0);
5387                         pfree(patt);
5388                 }
5389
5390                 return Pattern_Prefix_None;
5391         }
5392
5393         *prefix_const = string_to_const(prefix, typeid);
5394
5395         if (rest_selec != NULL)
5396         {
5397                 if (exact)
5398                 {
5399                         /* Exact match, so there's no additional selectivity */
5400                         *rest_selec = 1.0;
5401                 }
5402                 else
5403                 {
5404                         char       *patt = TextDatumGetCString(patt_const->constvalue);
5405
5406                         *rest_selec = regex_selectivity(patt, strlen(patt),
5407                                                                                         case_insensitive,
5408                                                                                         strlen(prefix));
5409                         pfree(patt);
5410                 }
5411         }
5412
5413         pfree(prefix);
5414
5415         if (exact)
5416                 return Pattern_Prefix_Exact;    /* pattern specifies exact match */
5417         else
5418                 return Pattern_Prefix_Partial;
5419 }
5420
5421 Pattern_Prefix_Status
5422 pattern_fixed_prefix(Const *patt, Pattern_Type ptype, Oid collation,
5423                                          Const **prefix, Selectivity *rest_selec)
5424 {
5425         Pattern_Prefix_Status result;
5426
5427         switch (ptype)
5428         {
5429                 case Pattern_Type_Like:
5430                         result = like_fixed_prefix(patt, false, collation,
5431                                                                            prefix, rest_selec);
5432                         break;
5433                 case Pattern_Type_Like_IC:
5434                         result = like_fixed_prefix(patt, true, collation,
5435                                                                            prefix, rest_selec);
5436                         break;
5437                 case Pattern_Type_Regex:
5438                         result = regex_fixed_prefix(patt, false, collation,
5439                                                                                 prefix, rest_selec);
5440                         break;
5441                 case Pattern_Type_Regex_IC:
5442                         result = regex_fixed_prefix(patt, true, collation,
5443                                                                                 prefix, rest_selec);
5444                         break;
5445                 default:
5446                         elog(ERROR, "unrecognized ptype: %d", (int) ptype);
5447                         result = Pattern_Prefix_None;           /* keep compiler quiet */
5448                         break;
5449         }
5450         return result;
5451 }
5452
5453 /*
5454  * Estimate the selectivity of a fixed prefix for a pattern match.
5455  *
5456  * A fixed prefix "foo" is estimated as the selectivity of the expression
5457  * "variable >= 'foo' AND variable < 'fop'" (see also indxpath.c).
5458  *
5459  * The selectivity estimate is with respect to the portion of the column
5460  * population represented by the histogram --- the caller must fold this
5461  * together with info about MCVs and NULLs.
5462  *
5463  * We use the >= and < operators from the specified btree opfamily to do the
5464  * estimation.  The given variable and Const must be of the associated
5465  * datatype.
5466  *
5467  * XXX Note: we make use of the upper bound to estimate operator selectivity
5468  * even if the locale is such that we cannot rely on the upper-bound string.
5469  * The selectivity only needs to be approximately right anyway, so it seems
5470  * more useful to use the upper-bound code than not.
5471  */
5472 static Selectivity
5473 prefix_selectivity(PlannerInfo *root, VariableStatData *vardata,
5474                                    Oid vartype, Oid opfamily, Const *prefixcon)
5475 {
5476         Selectivity prefixsel;
5477         Oid                     cmpopr;
5478         FmgrInfo        opproc;
5479         Const      *greaterstrcon;
5480         Selectivity eq_sel;
5481
5482         cmpopr = get_opfamily_member(opfamily, vartype, vartype,
5483                                                                  BTGreaterEqualStrategyNumber);
5484         if (cmpopr == InvalidOid)
5485                 elog(ERROR, "no >= operator for opfamily %u", opfamily);
5486         fmgr_info(get_opcode(cmpopr), &opproc);
5487
5488         prefixsel = ineq_histogram_selectivity(root, vardata, &opproc, true,
5489                                                                                    prefixcon->constvalue,
5490                                                                                    prefixcon->consttype);
5491
5492         if (prefixsel < 0.0)
5493         {
5494                 /* No histogram is present ... return a suitable default estimate */
5495                 return DEFAULT_MATCH_SEL;
5496         }
5497
5498         /*-------
5499          * If we can create a string larger than the prefix, say
5500          *      "x < greaterstr".
5501          *-------
5502          */
5503         cmpopr = get_opfamily_member(opfamily, vartype, vartype,
5504                                                                  BTLessStrategyNumber);
5505         if (cmpopr == InvalidOid)
5506                 elog(ERROR, "no < operator for opfamily %u", opfamily);
5507         fmgr_info(get_opcode(cmpopr), &opproc);
5508         greaterstrcon = make_greater_string(prefixcon, &opproc,
5509                                                                                 DEFAULT_COLLATION_OID);
5510         if (greaterstrcon)
5511         {
5512                 Selectivity topsel;
5513
5514                 topsel = ineq_histogram_selectivity(root, vardata, &opproc, false,
5515                                                                                         greaterstrcon->constvalue,
5516                                                                                         greaterstrcon->consttype);
5517
5518                 /* ineq_histogram_selectivity worked before, it shouldn't fail now */
5519                 Assert(topsel >= 0.0);
5520
5521                 /*
5522                  * Merge the two selectivities in the same way as for a range query
5523                  * (see clauselist_selectivity()).  Note that we don't need to worry
5524                  * about double-exclusion of nulls, since ineq_histogram_selectivity
5525                  * doesn't count those anyway.
5526                  */
5527                 prefixsel = topsel + prefixsel - 1.0;
5528         }
5529
5530         /*
5531          * If the prefix is long then the two bounding values might be too close
5532          * together for the histogram to distinguish them usefully, resulting in a
5533          * zero estimate (plus or minus roundoff error). To avoid returning a
5534          * ridiculously small estimate, compute the estimated selectivity for
5535          * "variable = 'foo'", and clamp to that. (Obviously, the resultant
5536          * estimate should be at least that.)
5537          *
5538          * We apply this even if we couldn't make a greater string.  That case
5539          * suggests that the prefix is near the maximum possible, and thus
5540          * probably off the end of the histogram, and thus we probably got a very
5541          * small estimate from the >= condition; so we still need to clamp.
5542          */
5543         cmpopr = get_opfamily_member(opfamily, vartype, vartype,
5544                                                                  BTEqualStrategyNumber);
5545         if (cmpopr == InvalidOid)
5546                 elog(ERROR, "no = operator for opfamily %u", opfamily);
5547         eq_sel = var_eq_const(vardata, cmpopr, prefixcon->constvalue,
5548                                                   false, true);
5549
5550         prefixsel = Max(prefixsel, eq_sel);
5551
5552         return prefixsel;
5553 }
5554
5555
5556 /*
5557  * Estimate the selectivity of a pattern of the specified type.
5558  * Note that any fixed prefix of the pattern will have been removed already,
5559  * so actually we may be looking at just a fragment of the pattern.
5560  *
5561  * For now, we use a very simplistic approach: fixed characters reduce the
5562  * selectivity a good deal, character ranges reduce it a little,
5563  * wildcards (such as % for LIKE or .* for regex) increase it.
5564  */
5565
5566 #define FIXED_CHAR_SEL  0.20    /* about 1/5 */
5567 #define CHAR_RANGE_SEL  0.25
5568 #define ANY_CHAR_SEL    0.9             /* not 1, since it won't match end-of-string */
5569 #define FULL_WILDCARD_SEL 5.0
5570 #define PARTIAL_WILDCARD_SEL 2.0
5571
5572 static Selectivity
5573 like_selectivity(const char *patt, int pattlen, bool case_insensitive)
5574 {
5575         Selectivity sel = 1.0;
5576         int                     pos;
5577
5578         /* Skip any leading wildcard; it's already factored into initial sel */
5579         for (pos = 0; pos < pattlen; pos++)
5580         {
5581                 if (patt[pos] != '%' && patt[pos] != '_')
5582                         break;
5583         }
5584
5585         for (; pos < pattlen; pos++)
5586         {
5587                 /* % and _ are wildcard characters in LIKE */
5588                 if (patt[pos] == '%')
5589                         sel *= FULL_WILDCARD_SEL;
5590                 else if (patt[pos] == '_')
5591                         sel *= ANY_CHAR_SEL;
5592                 else if (patt[pos] == '\\')
5593                 {
5594                         /* Backslash quotes the next character */
5595                         pos++;
5596                         if (pos >= pattlen)
5597                                 break;
5598                         sel *= FIXED_CHAR_SEL;
5599                 }
5600                 else
5601                         sel *= FIXED_CHAR_SEL;
5602         }
5603         /* Could get sel > 1 if multiple wildcards */
5604         if (sel > 1.0)
5605                 sel = 1.0;
5606         return sel;
5607 }
5608
5609 static Selectivity
5610 regex_selectivity_sub(const char *patt, int pattlen, bool case_insensitive)
5611 {
5612         Selectivity sel = 1.0;
5613         int                     paren_depth = 0;
5614         int                     paren_pos = 0;  /* dummy init to keep compiler quiet */
5615         int                     pos;
5616
5617         for (pos = 0; pos < pattlen; pos++)
5618         {
5619                 if (patt[pos] == '(')
5620                 {
5621                         if (paren_depth == 0)
5622                                 paren_pos = pos;        /* remember start of parenthesized item */
5623                         paren_depth++;
5624                 }
5625                 else if (patt[pos] == ')' && paren_depth > 0)
5626                 {
5627                         paren_depth--;
5628                         if (paren_depth == 0)
5629                                 sel *= regex_selectivity_sub(patt + (paren_pos + 1),
5630                                                                                          pos - (paren_pos + 1),
5631                                                                                          case_insensitive);
5632                 }
5633                 else if (patt[pos] == '|' && paren_depth == 0)
5634                 {
5635                         /*
5636                          * If unquoted | is present at paren level 0 in pattern, we have
5637                          * multiple alternatives; sum their probabilities.
5638                          */
5639                         sel += regex_selectivity_sub(patt + (pos + 1),
5640                                                                                  pattlen - (pos + 1),
5641                                                                                  case_insensitive);
5642                         break;                          /* rest of pattern is now processed */
5643                 }
5644                 else if (patt[pos] == '[')
5645                 {
5646                         bool            negclass = false;
5647
5648                         if (patt[++pos] == '^')
5649                         {
5650                                 negclass = true;
5651                                 pos++;
5652                         }
5653                         if (patt[pos] == ']')           /* ']' at start of class is not
5654                                                                                  * special */
5655                                 pos++;
5656                         while (pos < pattlen && patt[pos] != ']')
5657                                 pos++;
5658                         if (paren_depth == 0)
5659                                 sel *= (negclass ? (1.0 - CHAR_RANGE_SEL) : CHAR_RANGE_SEL);
5660                 }
5661                 else if (patt[pos] == '.')
5662                 {
5663                         if (paren_depth == 0)
5664                                 sel *= ANY_CHAR_SEL;
5665                 }
5666                 else if (patt[pos] == '*' ||
5667                                  patt[pos] == '?' ||
5668                                  patt[pos] == '+')
5669                 {
5670                         /* Ought to be smarter about quantifiers... */
5671                         if (paren_depth == 0)
5672                                 sel *= PARTIAL_WILDCARD_SEL;
5673                 }
5674                 else if (patt[pos] == '{')
5675                 {
5676                         while (pos < pattlen && patt[pos] != '}')
5677                                 pos++;
5678                         if (paren_depth == 0)
5679                                 sel *= PARTIAL_WILDCARD_SEL;
5680                 }
5681                 else if (patt[pos] == '\\')
5682                 {
5683                         /* backslash quotes the next character */
5684                         pos++;
5685                         if (pos >= pattlen)
5686                                 break;
5687                         if (paren_depth == 0)
5688                                 sel *= FIXED_CHAR_SEL;
5689                 }
5690                 else
5691                 {
5692                         if (paren_depth == 0)
5693                                 sel *= FIXED_CHAR_SEL;
5694                 }
5695         }
5696         /* Could get sel > 1 if multiple wildcards */
5697         if (sel > 1.0)
5698                 sel = 1.0;
5699         return sel;
5700 }
5701
5702 static Selectivity
5703 regex_selectivity(const char *patt, int pattlen, bool case_insensitive,
5704                                   int fixed_prefix_len)
5705 {
5706         Selectivity sel;
5707
5708         /* If patt doesn't end with $, consider it to have a trailing wildcard */
5709         if (pattlen > 0 && patt[pattlen - 1] == '$' &&
5710                 (pattlen == 1 || patt[pattlen - 2] != '\\'))
5711         {
5712                 /* has trailing $ */
5713                 sel = regex_selectivity_sub(patt, pattlen - 1, case_insensitive);
5714         }
5715         else
5716         {
5717                 /* no trailing $ */
5718                 sel = regex_selectivity_sub(patt, pattlen, case_insensitive);
5719                 sel *= FULL_WILDCARD_SEL;
5720         }
5721
5722         /* If there's a fixed prefix, discount its selectivity */
5723         if (fixed_prefix_len > 0)
5724                 sel /= pow(FIXED_CHAR_SEL, fixed_prefix_len);
5725
5726         /* Make sure result stays in range */
5727         CLAMP_PROBABILITY(sel);
5728         return sel;
5729 }
5730
5731
5732 /*
5733  * For bytea, the increment function need only increment the current byte
5734  * (there are no multibyte characters to worry about).
5735  */
5736 static bool
5737 byte_increment(unsigned char *ptr, int len)
5738 {
5739         if (*ptr >= 255)
5740                 return false;
5741         (*ptr)++;
5742         return true;
5743 }
5744
5745 /*
5746  * Try to generate a string greater than the given string or any
5747  * string it is a prefix of.  If successful, return a palloc'd string
5748  * in the form of a Const node; else return NULL.
5749  *
5750  * The caller must provide the appropriate "less than" comparison function
5751  * for testing the strings, along with the collation to use.
5752  *
5753  * The key requirement here is that given a prefix string, say "foo",
5754  * we must be able to generate another string "fop" that is greater than
5755  * all strings "foobar" starting with "foo".  We can test that we have
5756  * generated a string greater than the prefix string, but in non-C collations
5757  * that is not a bulletproof guarantee that an extension of the string might
5758  * not sort after it; an example is that "foo " is less than "foo!", but it
5759  * is not clear that a "dictionary" sort ordering will consider "foo!" less
5760  * than "foo bar".  CAUTION: Therefore, this function should be used only for
5761  * estimation purposes when working in a non-C collation.
5762  *
5763  * To try to catch most cases where an extended string might otherwise sort
5764  * before the result value, we determine which of the strings "Z", "z", "y",
5765  * and "9" is seen as largest by the collation, and append that to the given
5766  * prefix before trying to find a string that compares as larger.
5767  *
5768  * To search for a greater string, we repeatedly "increment" the rightmost
5769  * character, using an encoding-specific character incrementer function.
5770  * When it's no longer possible to increment the last character, we truncate
5771  * off that character and start incrementing the next-to-rightmost.
5772  * For example, if "z" were the last character in the sort order, then we
5773  * could produce "foo" as a string greater than "fonz".
5774  *
5775  * This could be rather slow in the worst case, but in most cases we
5776  * won't have to try more than one or two strings before succeeding.
5777  *
5778  * Note that it's important for the character incrementer not to be too anal
5779  * about producing every possible character code, since in some cases the only
5780  * way to get a larger string is to increment a previous character position.
5781  * So we don't want to spend too much time trying every possible character
5782  * code at the last position.  A good rule of thumb is to be sure that we
5783  * don't try more than 256*K values for a K-byte character (and definitely
5784  * not 256^K, which is what an exhaustive search would approach).
5785  */
5786 Const *
5787 make_greater_string(const Const *str_const, FmgrInfo *ltproc, Oid collation)
5788 {
5789         Oid                     datatype = str_const->consttype;
5790         char       *workstr;
5791         int                     len;
5792         Datum           cmpstr;
5793         text       *cmptxt = NULL;
5794         mbcharacter_incrementer charinc;
5795
5796         /*
5797          * Get a modifiable copy of the prefix string in C-string format, and set
5798          * up the string we will compare to as a Datum.  In C locale this can just
5799          * be the given prefix string, otherwise we need to add a suffix.  Types
5800          * NAME and BYTEA sort bytewise so they don't need a suffix either.
5801          */
5802         if (datatype == NAMEOID)
5803         {
5804                 workstr = DatumGetCString(DirectFunctionCall1(nameout,
5805                                                                                                           str_const->constvalue));
5806                 len = strlen(workstr);
5807                 cmpstr = str_const->constvalue;
5808         }
5809         else if (datatype == BYTEAOID)
5810         {
5811                 bytea      *bstr = DatumGetByteaP(str_const->constvalue);
5812
5813                 len = VARSIZE(bstr) - VARHDRSZ;
5814                 workstr = (char *) palloc(len);
5815                 memcpy(workstr, VARDATA(bstr), len);
5816                 if ((Pointer) bstr != DatumGetPointer(str_const->constvalue))
5817                         pfree(bstr);
5818                 cmpstr = str_const->constvalue;
5819         }
5820         else
5821         {
5822                 workstr = TextDatumGetCString(str_const->constvalue);
5823                 len = strlen(workstr);
5824                 if (lc_collate_is_c(collation) || len == 0)
5825                         cmpstr = str_const->constvalue;
5826                 else
5827                 {
5828                         /* If first time through, determine the suffix to use */
5829                         static char suffixchar = 0;
5830                         static Oid      suffixcollation = 0;
5831
5832                         if (!suffixchar || suffixcollation != collation)
5833                         {
5834                                 char       *best;
5835
5836                                 best = "Z";
5837                                 if (varstr_cmp(best, 1, "z", 1, collation) < 0)
5838                                         best = "z";
5839                                 if (varstr_cmp(best, 1, "y", 1, collation) < 0)
5840                                         best = "y";
5841                                 if (varstr_cmp(best, 1, "9", 1, collation) < 0)
5842                                         best = "9";
5843                                 suffixchar = *best;
5844                                 suffixcollation = collation;
5845                         }
5846
5847                         /* And build the string to compare to */
5848                         cmptxt = (text *) palloc(VARHDRSZ + len + 1);
5849                         SET_VARSIZE(cmptxt, VARHDRSZ + len + 1);
5850                         memcpy(VARDATA(cmptxt), workstr, len);
5851                         *(VARDATA(cmptxt) + len) = suffixchar;
5852                         cmpstr = PointerGetDatum(cmptxt);
5853                 }
5854         }
5855
5856         /* Select appropriate character-incrementer function */
5857         if (datatype == BYTEAOID)
5858                 charinc = byte_increment;
5859         else
5860                 charinc = pg_database_encoding_character_incrementer();
5861
5862         /* And search ... */
5863         while (len > 0)
5864         {
5865                 int                     charlen;
5866                 unsigned char *lastchar;
5867
5868                 /* Identify the last character --- for bytea, just the last byte */
5869                 if (datatype == BYTEAOID)
5870                         charlen = 1;
5871                 else
5872                         charlen = len - pg_mbcliplen(workstr, len, len - 1);
5873                 lastchar = (unsigned char *) (workstr + len - charlen);
5874
5875                 /*
5876                  * Try to generate a larger string by incrementing the last character
5877                  * (for BYTEA, we treat each byte as a character).
5878                  *
5879                  * Note: the incrementer function is expected to return true if it's
5880                  * generated a valid-per-the-encoding new character, otherwise false.
5881                  * The contents of the character on false return are unspecified.
5882                  */
5883                 while (charinc(lastchar, charlen))
5884                 {
5885                         Const      *workstr_const;
5886
5887                         if (datatype == BYTEAOID)
5888                                 workstr_const = string_to_bytea_const(workstr, len);
5889                         else
5890                                 workstr_const = string_to_const(workstr, datatype);
5891
5892                         if (DatumGetBool(FunctionCall2Coll(ltproc,
5893                                                                                            collation,
5894                                                                                            cmpstr,
5895                                                                                            workstr_const->constvalue)))
5896                         {
5897                                 /* Successfully made a string larger than cmpstr */
5898                                 if (cmptxt)
5899                                         pfree(cmptxt);
5900                                 pfree(workstr);
5901                                 return workstr_const;
5902                         }
5903
5904                         /* No good, release unusable value and try again */
5905                         pfree(DatumGetPointer(workstr_const->constvalue));
5906                         pfree(workstr_const);
5907                 }
5908
5909                 /*
5910                  * No luck here, so truncate off the last character and try to
5911                  * increment the next one.
5912                  */
5913                 len -= charlen;
5914                 workstr[len] = '\0';
5915         }
5916
5917         /* Failed... */
5918         if (cmptxt)
5919                 pfree(cmptxt);
5920         pfree(workstr);
5921
5922         return NULL;
5923 }
5924
5925 /*
5926  * Generate a Datum of the appropriate type from a C string.
5927  * Note that all of the supported types are pass-by-ref, so the
5928  * returned value should be pfree'd if no longer needed.
5929  */
5930 static Datum
5931 string_to_datum(const char *str, Oid datatype)
5932 {
5933         Assert(str != NULL);
5934
5935         /*
5936          * We cheat a little by assuming that CStringGetTextDatum() will do for
5937          * bpchar and varchar constants too...
5938          */
5939         if (datatype == NAMEOID)
5940                 return DirectFunctionCall1(namein, CStringGetDatum(str));
5941         else if (datatype == BYTEAOID)
5942                 return DirectFunctionCall1(byteain, CStringGetDatum(str));
5943         else
5944                 return CStringGetTextDatum(str);
5945 }
5946
5947 /*
5948  * Generate a Const node of the appropriate type from a C string.
5949  */
5950 static Const *
5951 string_to_const(const char *str, Oid datatype)
5952 {
5953         Datum           conval = string_to_datum(str, datatype);
5954         Oid                     collation;
5955         int                     constlen;
5956
5957         /*
5958          * We only need to support a few datatypes here, so hard-wire properties
5959          * instead of incurring the expense of catalog lookups.
5960          */
5961         switch (datatype)
5962         {
5963                 case TEXTOID:
5964                 case VARCHAROID:
5965                 case BPCHAROID:
5966                         collation = DEFAULT_COLLATION_OID;
5967                         constlen = -1;
5968                         break;
5969
5970                 case NAMEOID:
5971                         collation = InvalidOid;
5972                         constlen = NAMEDATALEN;
5973                         break;
5974
5975                 case BYTEAOID:
5976                         collation = InvalidOid;
5977                         constlen = -1;
5978                         break;
5979
5980                 default:
5981                         elog(ERROR, "unexpected datatype in string_to_const: %u",
5982                                  datatype);
5983                         return NULL;
5984         }
5985
5986         return makeConst(datatype, -1, collation, constlen,
5987                                          conval, false, false);
5988 }
5989
5990 /*
5991  * Generate a Const node of bytea type from a binary C string and a length.
5992  */
5993 static Const *
5994 string_to_bytea_const(const char *str, size_t str_len)
5995 {
5996         bytea      *bstr = palloc(VARHDRSZ + str_len);
5997         Datum           conval;
5998
5999         memcpy(VARDATA(bstr), str, str_len);
6000         SET_VARSIZE(bstr, VARHDRSZ + str_len);
6001         conval = PointerGetDatum(bstr);
6002
6003         return makeConst(BYTEAOID, -1, InvalidOid, -1, conval, false, false);
6004 }
6005
6006 /*-------------------------------------------------------------------------
6007  *
6008  * Index cost estimation functions
6009  *
6010  *-------------------------------------------------------------------------
6011  */
6012
6013 /*
6014  * deconstruct_indexquals is a simple function to examine the indexquals
6015  * attached to a proposed IndexPath.  It returns a list of IndexQualInfo
6016  * structs, one per qual expression.
6017  */
6018 typedef struct
6019 {
6020         RestrictInfo *rinfo;            /* the indexqual itself */
6021         int                     indexcol;               /* zero-based index column number */
6022         bool            varonleft;              /* true if index column is on left of qual */
6023         Oid                     clause_op;              /* qual's operator OID, if relevant */
6024         Node       *other_operand;      /* non-index operand of qual's operator */
6025 } IndexQualInfo;
6026
6027 static List *
6028 deconstruct_indexquals(IndexPath *path)
6029 {
6030         List       *result = NIL;
6031         IndexOptInfo *index = path->indexinfo;
6032         ListCell   *lcc,
6033                            *lci;
6034
6035         forboth(lcc, path->indexquals, lci, path->indexqualcols)
6036         {
6037                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
6038                 int                     indexcol = lfirst_int(lci);
6039                 Expr       *clause;
6040                 Node       *leftop,
6041                                    *rightop;
6042                 IndexQualInfo *qinfo;
6043
6044                 Assert(IsA(rinfo, RestrictInfo));
6045                 clause = rinfo->clause;
6046
6047                 qinfo = (IndexQualInfo *) palloc(sizeof(IndexQualInfo));
6048                 qinfo->rinfo = rinfo;
6049                 qinfo->indexcol = indexcol;
6050
6051                 if (IsA(clause, OpExpr))
6052                 {
6053                         qinfo->clause_op = ((OpExpr *) clause)->opno;
6054                         leftop = get_leftop(clause);
6055                         rightop = get_rightop(clause);
6056                         if (match_index_to_operand(leftop, indexcol, index))
6057                         {
6058                                 qinfo->varonleft = true;
6059                                 qinfo->other_operand = rightop;
6060                         }
6061                         else
6062                         {
6063                                 Assert(match_index_to_operand(rightop, indexcol, index));
6064                                 qinfo->varonleft = false;
6065                                 qinfo->other_operand = leftop;
6066                         }
6067                 }
6068                 else if (IsA(clause, RowCompareExpr))
6069                 {
6070                         RowCompareExpr *rc = (RowCompareExpr *) clause;
6071
6072                         qinfo->clause_op = linitial_oid(rc->opnos);
6073                         /* Examine only first columns to determine left/right sides */
6074                         if (match_index_to_operand((Node *) linitial(rc->largs),
6075                                                                            indexcol, index))
6076                         {
6077                                 qinfo->varonleft = true;
6078                                 qinfo->other_operand = (Node *) rc->rargs;
6079                         }
6080                         else
6081                         {
6082                                 Assert(match_index_to_operand((Node *) linitial(rc->rargs),
6083                                                                                           indexcol, index));
6084                                 qinfo->varonleft = false;
6085                                 qinfo->other_operand = (Node *) rc->largs;
6086                         }
6087                 }
6088                 else if (IsA(clause, ScalarArrayOpExpr))
6089                 {
6090                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6091
6092                         qinfo->clause_op = saop->opno;
6093                         /* index column is always on the left in this case */
6094                         Assert(match_index_to_operand((Node *) linitial(saop->args),
6095                                                                                   indexcol, index));
6096                         qinfo->varonleft = true;
6097                         qinfo->other_operand = (Node *) lsecond(saop->args);
6098                 }
6099                 else if (IsA(clause, NullTest))
6100                 {
6101                         qinfo->clause_op = InvalidOid;
6102                         Assert(match_index_to_operand((Node *) ((NullTest *) clause)->arg,
6103                                                                                   indexcol, index));
6104                         qinfo->varonleft = true;
6105                         qinfo->other_operand = NULL;
6106                 }
6107                 else
6108                 {
6109                         elog(ERROR, "unsupported indexqual type: %d",
6110                                  (int) nodeTag(clause));
6111                 }
6112
6113                 result = lappend(result, qinfo);
6114         }
6115         return result;
6116 }
6117
6118 /*
6119  * Simple function to compute the total eval cost of the "other operands"
6120  * in an IndexQualInfo list.  Since we know these will be evaluated just
6121  * once per scan, there's no need to distinguish startup from per-row cost.
6122  */
6123 static Cost
6124 other_operands_eval_cost(PlannerInfo *root, List *qinfos)
6125 {
6126         Cost            qual_arg_cost = 0;
6127         ListCell   *lc;
6128
6129         foreach(lc, qinfos)
6130         {
6131                 IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
6132                 QualCost        index_qual_cost;
6133
6134                 cost_qual_eval_node(&index_qual_cost, qinfo->other_operand, root);
6135                 qual_arg_cost += index_qual_cost.startup + index_qual_cost.per_tuple;
6136         }
6137         return qual_arg_cost;
6138 }
6139
6140 /*
6141  * Get other-operand eval cost for an index orderby list.
6142  *
6143  * Index orderby expressions aren't represented as RestrictInfos (since they
6144  * aren't boolean, usually).  So we can't apply deconstruct_indexquals to
6145  * them.  However, they are much simpler to deal with since they are always
6146  * OpExprs and the index column is always on the left.
6147  */
6148 static Cost
6149 orderby_operands_eval_cost(PlannerInfo *root, IndexPath *path)
6150 {
6151         Cost            qual_arg_cost = 0;
6152         ListCell   *lc;
6153
6154         foreach(lc, path->indexorderbys)
6155         {
6156                 Expr       *clause = (Expr *) lfirst(lc);
6157                 Node       *other_operand;
6158                 QualCost        index_qual_cost;
6159
6160                 if (IsA(clause, OpExpr))
6161                 {
6162                         other_operand = get_rightop(clause);
6163                 }
6164                 else
6165                 {
6166                         elog(ERROR, "unsupported indexorderby type: %d",
6167                                  (int) nodeTag(clause));
6168                         other_operand = NULL;           /* keep compiler quiet */
6169                 }
6170
6171                 cost_qual_eval_node(&index_qual_cost, other_operand, root);
6172                 qual_arg_cost += index_qual_cost.startup + index_qual_cost.per_tuple;
6173         }
6174         return qual_arg_cost;
6175 }
6176
6177 /*
6178  * genericcostestimate is a general-purpose estimator that can be used for
6179  * most index types.  In some cases we use genericcostestimate as the base
6180  * code and then incorporate additional index-type-specific knowledge in
6181  * the type-specific calling function.  To avoid code duplication, we make
6182  * genericcostestimate return a number of intermediate values as well as
6183  * its preliminary estimates of the output cost values.  The GenericCosts
6184  * struct includes all these values.
6185  *
6186  * Callers should initialize all fields of GenericCosts to zero.  In addition,
6187  * they can set numIndexTuples to some positive value if they have a better
6188  * than default way of estimating the number of leaf index tuples visited.
6189  */
6190 typedef struct
6191 {
6192         /* These are the values the cost estimator must return to the planner */
6193         Cost            indexStartupCost;               /* index-related startup cost */
6194         Cost            indexTotalCost; /* total index-related scan cost */
6195         Selectivity indexSelectivity;           /* selectivity of index */
6196         double          indexCorrelation;               /* order correlation of index */
6197
6198         /* Intermediate values we obtain along the way */
6199         double          numIndexPages;  /* number of leaf pages visited */
6200         double          numIndexTuples; /* number of leaf tuples visited */
6201         double          spc_random_page_cost;   /* relevant random_page_cost value */
6202         double          num_sa_scans;   /* # indexscans from ScalarArrayOps */
6203 } GenericCosts;
6204
6205 static void
6206 genericcostestimate(PlannerInfo *root,
6207                                         IndexPath *path,
6208                                         double loop_count,
6209                                         List *qinfos,
6210                                         GenericCosts *costs)
6211 {
6212         IndexOptInfo *index = path->indexinfo;
6213         List       *indexQuals = path->indexquals;
6214         List       *indexOrderBys = path->indexorderbys;
6215         Cost            indexStartupCost;
6216         Cost            indexTotalCost;
6217         Selectivity indexSelectivity;
6218         double          indexCorrelation;
6219         double          numIndexPages;
6220         double          numIndexTuples;
6221         double          spc_random_page_cost;
6222         double          num_sa_scans;
6223         double          num_outer_scans;
6224         double          num_scans;
6225         double          qual_op_cost;
6226         double          qual_arg_cost;
6227         List       *selectivityQuals;
6228         ListCell   *l;
6229
6230         /*
6231          * If the index is partial, AND the index predicate with the explicitly
6232          * given indexquals to produce a more accurate idea of the index
6233          * selectivity.
6234          */
6235         selectivityQuals = add_predicate_to_quals(index, indexQuals);
6236
6237         /*
6238          * Check for ScalarArrayOpExpr index quals, and estimate the number of
6239          * index scans that will be performed.
6240          */
6241         num_sa_scans = 1;
6242         foreach(l, indexQuals)
6243         {
6244                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
6245
6246                 if (IsA(rinfo->clause, ScalarArrayOpExpr))
6247                 {
6248                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) rinfo->clause;
6249                         int                     alength = estimate_array_length(lsecond(saop->args));
6250
6251                         if (alength > 1)
6252                                 num_sa_scans *= alength;
6253                 }
6254         }
6255
6256         /* Estimate the fraction of main-table tuples that will be visited */
6257         indexSelectivity = clauselist_selectivity(root, selectivityQuals,
6258                                                                                           index->rel->relid,
6259                                                                                           JOIN_INNER,
6260                                                                                           NULL);
6261
6262         /*
6263          * If caller didn't give us an estimate, estimate the number of index
6264          * tuples that will be visited.  We do it in this rather peculiar-looking
6265          * way in order to get the right answer for partial indexes.
6266          */
6267         numIndexTuples = costs->numIndexTuples;
6268         if (numIndexTuples <= 0.0)
6269         {
6270                 numIndexTuples = indexSelectivity * index->rel->tuples;
6271
6272                 /*
6273                  * The above calculation counts all the tuples visited across all
6274                  * scans induced by ScalarArrayOpExpr nodes.  We want to consider the
6275                  * average per-indexscan number, so adjust.  This is a handy place to
6276                  * round to integer, too.  (If caller supplied tuple estimate, it's
6277                  * responsible for handling these considerations.)
6278                  */
6279                 numIndexTuples = rint(numIndexTuples / num_sa_scans);
6280         }
6281
6282         /*
6283          * We can bound the number of tuples by the index size in any case. Also,
6284          * always estimate at least one tuple is touched, even when
6285          * indexSelectivity estimate is tiny.
6286          */
6287         if (numIndexTuples > index->tuples)
6288                 numIndexTuples = index->tuples;
6289         if (numIndexTuples < 1.0)
6290                 numIndexTuples = 1.0;
6291
6292         /*
6293          * Estimate the number of index pages that will be retrieved.
6294          *
6295          * We use the simplistic method of taking a pro-rata fraction of the total
6296          * number of index pages.  In effect, this counts only leaf pages and not
6297          * any overhead such as index metapage or upper tree levels.
6298          *
6299          * In practice access to upper index levels is often nearly free because
6300          * those tend to stay in cache under load; moreover, the cost involved is
6301          * highly dependent on index type.  We therefore ignore such costs here
6302          * and leave it to the caller to add a suitable charge if needed.
6303          */
6304         if (index->pages > 1 && index->tuples > 1)
6305                 numIndexPages = ceil(numIndexTuples * index->pages / index->tuples);
6306         else
6307                 numIndexPages = 1.0;
6308
6309         /* fetch estimated page cost for tablespace containing index */
6310         get_tablespace_page_costs(index->reltablespace,
6311                                                           &spc_random_page_cost,
6312                                                           NULL);
6313
6314         /*
6315          * Now compute the disk access costs.
6316          *
6317          * The above calculations are all per-index-scan.  However, if we are in a
6318          * nestloop inner scan, we can expect the scan to be repeated (with
6319          * different search keys) for each row of the outer relation.  Likewise,
6320          * ScalarArrayOpExpr quals result in multiple index scans.  This creates
6321          * the potential for cache effects to reduce the number of disk page
6322          * fetches needed.  We want to estimate the average per-scan I/O cost in
6323          * the presence of caching.
6324          *
6325          * We use the Mackert-Lohman formula (see costsize.c for details) to
6326          * estimate the total number of page fetches that occur.  While this
6327          * wasn't what it was designed for, it seems a reasonable model anyway.
6328          * Note that we are counting pages not tuples anymore, so we take N = T =
6329          * index size, as if there were one "tuple" per page.
6330          */
6331         num_outer_scans = loop_count;
6332         num_scans = num_sa_scans * num_outer_scans;
6333
6334         if (num_scans > 1)
6335         {
6336                 double          pages_fetched;
6337
6338                 /* total page fetches ignoring cache effects */
6339                 pages_fetched = numIndexPages * num_scans;
6340
6341                 /* use Mackert and Lohman formula to adjust for cache effects */
6342                 pages_fetched = index_pages_fetched(pages_fetched,
6343                                                                                         index->pages,
6344                                                                                         (double) index->pages,
6345                                                                                         root);
6346
6347                 /*
6348                  * Now compute the total disk access cost, and then report a pro-rated
6349                  * share for each outer scan.  (Don't pro-rate for ScalarArrayOpExpr,
6350                  * since that's internal to the indexscan.)
6351                  */
6352                 indexTotalCost = (pages_fetched * spc_random_page_cost)
6353                         / num_outer_scans;
6354         }
6355         else
6356         {
6357                 /*
6358                  * For a single index scan, we just charge spc_random_page_cost per
6359                  * page touched.
6360                  */
6361                 indexTotalCost = numIndexPages * spc_random_page_cost;
6362         }
6363
6364         /*
6365          * CPU cost: any complex expressions in the indexquals will need to be
6366          * evaluated once at the start of the scan to reduce them to runtime keys
6367          * to pass to the index AM (see nodeIndexscan.c).  We model the per-tuple
6368          * CPU costs as cpu_index_tuple_cost plus one cpu_operator_cost per
6369          * indexqual operator.  Because we have numIndexTuples as a per-scan
6370          * number, we have to multiply by num_sa_scans to get the correct result
6371          * for ScalarArrayOpExpr cases.  Similarly add in costs for any index
6372          * ORDER BY expressions.
6373          *
6374          * Note: this neglects the possible costs of rechecking lossy operators.
6375          * Detecting that that might be needed seems more expensive than it's
6376          * worth, though, considering all the other inaccuracies here ...
6377          */
6378         qual_arg_cost = other_operands_eval_cost(root, qinfos) +
6379                 orderby_operands_eval_cost(root, path);
6380         qual_op_cost = cpu_operator_cost *
6381                 (list_length(indexQuals) + list_length(indexOrderBys));
6382
6383         indexStartupCost = qual_arg_cost;
6384         indexTotalCost += qual_arg_cost;
6385         indexTotalCost += numIndexTuples * num_sa_scans * (cpu_index_tuple_cost + qual_op_cost);
6386
6387         /*
6388          * Generic assumption about index correlation: there isn't any.
6389          */
6390         indexCorrelation = 0.0;
6391
6392         /*
6393          * Return everything to caller.
6394          */
6395         costs->indexStartupCost = indexStartupCost;
6396         costs->indexTotalCost = indexTotalCost;
6397         costs->indexSelectivity = indexSelectivity;
6398         costs->indexCorrelation = indexCorrelation;
6399         costs->numIndexPages = numIndexPages;
6400         costs->numIndexTuples = numIndexTuples;
6401         costs->spc_random_page_cost = spc_random_page_cost;
6402         costs->num_sa_scans = num_sa_scans;
6403 }
6404
6405 /*
6406  * If the index is partial, add its predicate to the given qual list.
6407  *
6408  * ANDing the index predicate with the explicitly given indexquals produces
6409  * a more accurate idea of the index's selectivity.  However, we need to be
6410  * careful not to insert redundant clauses, because clauselist_selectivity()
6411  * is easily fooled into computing a too-low selectivity estimate.  Our
6412  * approach is to add only the predicate clause(s) that cannot be proven to
6413  * be implied by the given indexquals.  This successfully handles cases such
6414  * as a qual "x = 42" used with a partial index "WHERE x >= 40 AND x < 50".
6415  * There are many other cases where we won't detect redundancy, leading to a
6416  * too-low selectivity estimate, which will bias the system in favor of using
6417  * partial indexes where possible.  That is not necessarily bad though.
6418  *
6419  * Note that indexQuals contains RestrictInfo nodes while the indpred
6420  * does not, so the output list will be mixed.  This is OK for both
6421  * predicate_implied_by() and clauselist_selectivity(), but might be
6422  * problematic if the result were passed to other things.
6423  */
6424 static List *
6425 add_predicate_to_quals(IndexOptInfo *index, List *indexQuals)
6426 {
6427         List       *predExtraQuals = NIL;
6428         ListCell   *lc;
6429
6430         if (index->indpred == NIL)
6431                 return indexQuals;
6432
6433         foreach(lc, index->indpred)
6434         {
6435                 Node       *predQual = (Node *) lfirst(lc);
6436                 List       *oneQual = list_make1(predQual);
6437
6438                 if (!predicate_implied_by(oneQual, indexQuals))
6439                         predExtraQuals = list_concat(predExtraQuals, oneQual);
6440         }
6441         /* list_concat avoids modifying the passed-in indexQuals list */
6442         return list_concat(predExtraQuals, indexQuals);
6443 }
6444
6445
6446 Datum
6447 btcostestimate(PG_FUNCTION_ARGS)
6448 {
6449         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6450         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6451         double          loop_count = PG_GETARG_FLOAT8(2);
6452         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6453         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6454         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6455         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6456         IndexOptInfo *index = path->indexinfo;
6457         List       *qinfos;
6458         GenericCosts costs;
6459         Oid                     relid;
6460         AttrNumber      colnum;
6461         VariableStatData vardata;
6462         double          numIndexTuples;
6463         Cost            descentCost;
6464         List       *indexBoundQuals;
6465         int                     indexcol;
6466         bool            eqQualHere;
6467         bool            found_saop;
6468         bool            found_is_null_op;
6469         double          num_sa_scans;
6470         ListCell   *lc;
6471
6472         /* Do preliminary analysis of indexquals */
6473         qinfos = deconstruct_indexquals(path);
6474
6475         /*
6476          * For a btree scan, only leading '=' quals plus inequality quals for the
6477          * immediately next attribute contribute to index selectivity (these are
6478          * the "boundary quals" that determine the starting and stopping points of
6479          * the index scan).  Additional quals can suppress visits to the heap, so
6480          * it's OK to count them in indexSelectivity, but they should not count
6481          * for estimating numIndexTuples.  So we must examine the given indexquals
6482          * to find out which ones count as boundary quals.  We rely on the
6483          * knowledge that they are given in index column order.
6484          *
6485          * For a RowCompareExpr, we consider only the first column, just as
6486          * rowcomparesel() does.
6487          *
6488          * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6489          * index scans not one, but the ScalarArrayOpExpr's operator can be
6490          * considered to act the same as it normally does.
6491          */
6492         indexBoundQuals = NIL;
6493         indexcol = 0;
6494         eqQualHere = false;
6495         found_saop = false;
6496         found_is_null_op = false;
6497         num_sa_scans = 1;
6498         foreach(lc, qinfos)
6499         {
6500                 IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(lc);
6501                 RestrictInfo *rinfo = qinfo->rinfo;
6502                 Expr       *clause = rinfo->clause;
6503                 Oid                     clause_op;
6504                 int                     op_strategy;
6505
6506                 if (indexcol != qinfo->indexcol)
6507                 {
6508                         /* Beginning of a new column's quals */
6509                         if (!eqQualHere)
6510                                 break;                  /* done if no '=' qual for indexcol */
6511                         eqQualHere = false;
6512                         indexcol++;
6513                         if (indexcol != qinfo->indexcol)
6514                                 break;                  /* no quals at all for indexcol */
6515                 }
6516
6517                 if (IsA(clause, ScalarArrayOpExpr))
6518                 {
6519                         int                     alength = estimate_array_length(qinfo->other_operand);
6520
6521                         found_saop = true;
6522                         /* count up number of SA scans induced by indexBoundQuals only */
6523                         if (alength > 1)
6524                                 num_sa_scans *= alength;
6525                 }
6526                 else if (IsA(clause, NullTest))
6527                 {
6528                         NullTest   *nt = (NullTest *) clause;
6529
6530                         if (nt->nulltesttype == IS_NULL)
6531                         {
6532                                 found_is_null_op = true;
6533                                 /* IS NULL is like = for selectivity determination purposes */
6534                                 eqQualHere = true;
6535                         }
6536                 }
6537
6538                 /*
6539                  * We would need to commute the clause_op if not varonleft, except
6540                  * that we only care if it's equality or not, so that refinement is
6541                  * unnecessary.
6542                  */
6543                 clause_op = qinfo->clause_op;
6544
6545                 /* check for equality operator */
6546                 if (OidIsValid(clause_op))
6547                 {
6548                         op_strategy = get_op_opfamily_strategy(clause_op,
6549                                                                                                    index->opfamily[indexcol]);
6550                         Assert(op_strategy != 0);       /* not a member of opfamily?? */
6551                         if (op_strategy == BTEqualStrategyNumber)
6552                                 eqQualHere = true;
6553                 }
6554
6555                 indexBoundQuals = lappend(indexBoundQuals, rinfo);
6556         }
6557
6558         /*
6559          * If index is unique and we found an '=' clause for each column, we can
6560          * just assume numIndexTuples = 1 and skip the expensive
6561          * clauselist_selectivity calculations.  However, a ScalarArrayOp or
6562          * NullTest invalidates that theory, even though it sets eqQualHere.
6563          */
6564         if (index->unique &&
6565                 indexcol == index->ncolumns - 1 &&
6566                 eqQualHere &&
6567                 !found_saop &&
6568                 !found_is_null_op)
6569                 numIndexTuples = 1.0;
6570         else
6571         {
6572                 List       *selectivityQuals;
6573                 Selectivity btreeSelectivity;
6574
6575                 /*
6576                  * If the index is partial, AND the index predicate with the
6577                  * index-bound quals to produce a more accurate idea of the number of
6578                  * rows covered by the bound conditions.
6579                  */
6580                 selectivityQuals = add_predicate_to_quals(index, indexBoundQuals);
6581
6582                 btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6583                                                                                                   index->rel->relid,
6584                                                                                                   JOIN_INNER,
6585                                                                                                   NULL);
6586                 numIndexTuples = btreeSelectivity * index->rel->tuples;
6587
6588                 /*
6589                  * As in genericcostestimate(), we have to adjust for any
6590                  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6591                  * to integer.
6592                  */
6593                 numIndexTuples = rint(numIndexTuples / num_sa_scans);
6594         }
6595
6596         /*
6597          * Now do generic index cost estimation.
6598          */
6599         MemSet(&costs, 0, sizeof(costs));
6600         costs.numIndexTuples = numIndexTuples;
6601
6602         genericcostestimate(root, path, loop_count, qinfos, &costs);
6603
6604         /*
6605          * Add a CPU-cost component to represent the costs of initial btree
6606          * descent.  We don't charge any I/O cost for touching upper btree levels,
6607          * since they tend to stay in cache, but we still have to do about log2(N)
6608          * comparisons to descend a btree of N leaf tuples.  We charge one
6609          * cpu_operator_cost per comparison.
6610          *
6611          * If there are ScalarArrayOpExprs, charge this once per SA scan.  The
6612          * ones after the first one are not startup cost so far as the overall
6613          * plan is concerned, so add them only to "total" cost.
6614          */
6615         if (index->tuples > 1)          /* avoid computing log(0) */
6616         {
6617                 descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6618                 costs.indexStartupCost += descentCost;
6619                 costs.indexTotalCost += costs.num_sa_scans * descentCost;
6620         }
6621
6622         /*
6623          * Even though we're not charging I/O cost for touching upper btree pages,
6624          * it's still reasonable to charge some CPU cost per page descended
6625          * through.  Moreover, if we had no such charge at all, bloated indexes
6626          * would appear to have the same search cost as unbloated ones, at least
6627          * in cases where only a single leaf page is expected to be visited.  This
6628          * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6629          * touched.  The number of such pages is btree tree height plus one (ie,
6630          * we charge for the leaf page too).  As above, charge once per SA scan.
6631          */
6632         descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6633         costs.indexStartupCost += descentCost;
6634         costs.indexTotalCost += costs.num_sa_scans * descentCost;
6635
6636         /*
6637          * If we can get an estimate of the first column's ordering correlation C
6638          * from pg_statistic, estimate the index correlation as C for a
6639          * single-column index, or C * 0.75 for multiple columns. (The idea here
6640          * is that multiple columns dilute the importance of the first column's
6641          * ordering, but don't negate it entirely.  Before 8.0 we divided the
6642          * correlation by the number of columns, but that seems too strong.)
6643          */
6644         MemSet(&vardata, 0, sizeof(vardata));
6645
6646         if (index->indexkeys[0] != 0)
6647         {
6648                 /* Simple variable --- look to stats for the underlying table */
6649                 RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6650
6651                 Assert(rte->rtekind == RTE_RELATION);
6652                 relid = rte->relid;
6653                 Assert(relid != InvalidOid);
6654                 colnum = index->indexkeys[0];
6655
6656                 if (get_relation_stats_hook &&
6657                         (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6658                 {
6659                         /*
6660                          * The hook took control of acquiring a stats tuple.  If it did
6661                          * supply a tuple, it'd better have supplied a freefunc.
6662                          */
6663                         if (HeapTupleIsValid(vardata.statsTuple) &&
6664                                 !vardata.freefunc)
6665                                 elog(ERROR, "no function provided to release variable stats with");
6666                 }
6667                 else
6668                 {
6669                         vardata.statsTuple = SearchSysCache3(STATRELATTINH,
6670                                                                                                  ObjectIdGetDatum(relid),
6671                                                                                                  Int16GetDatum(colnum),
6672                                                                                                  BoolGetDatum(rte->inh));
6673                         vardata.freefunc = ReleaseSysCache;
6674                 }
6675         }
6676         else
6677         {
6678                 /* Expression --- maybe there are stats for the index itself */
6679                 relid = index->indexoid;
6680                 colnum = 1;
6681
6682                 if (get_index_stats_hook &&
6683                         (*get_index_stats_hook) (root, relid, colnum, &vardata))
6684                 {
6685                         /*
6686                          * The hook took control of acquiring a stats tuple.  If it did
6687                          * supply a tuple, it'd better have supplied a freefunc.
6688                          */
6689                         if (HeapTupleIsValid(vardata.statsTuple) &&
6690                                 !vardata.freefunc)
6691                                 elog(ERROR, "no function provided to release variable stats with");
6692                 }
6693                 else
6694                 {
6695                         vardata.statsTuple = SearchSysCache3(STATRELATTINH,
6696                                                                                                  ObjectIdGetDatum(relid),
6697                                                                                                  Int16GetDatum(colnum),
6698                                                                                                  BoolGetDatum(false));
6699                         vardata.freefunc = ReleaseSysCache;
6700                 }
6701         }
6702
6703         if (HeapTupleIsValid(vardata.statsTuple))
6704         {
6705                 Oid                     sortop;
6706                 float4     *numbers;
6707                 int                     nnumbers;
6708
6709                 sortop = get_opfamily_member(index->opfamily[0],
6710                                                                          index->opcintype[0],
6711                                                                          index->opcintype[0],
6712                                                                          BTLessStrategyNumber);
6713                 if (OidIsValid(sortop) &&
6714                         get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
6715                                                          STATISTIC_KIND_CORRELATION,
6716                                                          sortop,
6717                                                          NULL,
6718                                                          NULL, NULL,
6719                                                          &numbers, &nnumbers))
6720                 {
6721                         double          varCorrelation;
6722
6723                         Assert(nnumbers == 1);
6724                         varCorrelation = numbers[0];
6725
6726                         if (index->reverse_sort[0])
6727                                 varCorrelation = -varCorrelation;
6728
6729                         if (index->ncolumns > 1)
6730                                 costs.indexCorrelation = varCorrelation * 0.75;
6731                         else
6732                                 costs.indexCorrelation = varCorrelation;
6733
6734                         free_attstatsslot(InvalidOid, NULL, 0, numbers, nnumbers);
6735                 }
6736         }
6737
6738         ReleaseVariableStats(vardata);
6739
6740         *indexStartupCost = costs.indexStartupCost;
6741         *indexTotalCost = costs.indexTotalCost;
6742         *indexSelectivity = costs.indexSelectivity;
6743         *indexCorrelation = costs.indexCorrelation;
6744
6745         PG_RETURN_VOID();
6746 }
6747
6748 Datum
6749 hashcostestimate(PG_FUNCTION_ARGS)
6750 {
6751         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6752         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6753         double          loop_count = PG_GETARG_FLOAT8(2);
6754         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6755         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6756         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6757         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6758         List       *qinfos;
6759         GenericCosts costs;
6760
6761         /* Do preliminary analysis of indexquals */
6762         qinfos = deconstruct_indexquals(path);
6763
6764         MemSet(&costs, 0, sizeof(costs));
6765
6766         genericcostestimate(root, path, loop_count, qinfos, &costs);
6767
6768         /*
6769          * A hash index has no descent costs as such, since the index AM can go
6770          * directly to the target bucket after computing the hash value.  There
6771          * are a couple of other hash-specific costs that we could conceivably add
6772          * here, though:
6773          *
6774          * Ideally we'd charge spc_random_page_cost for each page in the target
6775          * bucket, not just the numIndexPages pages that genericcostestimate
6776          * thought we'd visit.  However in most cases we don't know which bucket
6777          * that will be.  There's no point in considering the average bucket size
6778          * because the hash AM makes sure that's always one page.
6779          *
6780          * Likewise, we could consider charging some CPU for each index tuple in
6781          * the bucket, if we knew how many there were.  But the per-tuple cost is
6782          * just a hash value comparison, not a general datatype-dependent
6783          * comparison, so any such charge ought to be quite a bit less than
6784          * cpu_operator_cost; which makes it probably not worth worrying about.
6785          *
6786          * A bigger issue is that chance hash-value collisions will result in
6787          * wasted probes into the heap.  We don't currently attempt to model this
6788          * cost on the grounds that it's rare, but maybe it's not rare enough.
6789          * (Any fix for this ought to consider the generic lossy-operator problem,
6790          * though; it's not entirely hash-specific.)
6791          */
6792
6793         *indexStartupCost = costs.indexStartupCost;
6794         *indexTotalCost = costs.indexTotalCost;
6795         *indexSelectivity = costs.indexSelectivity;
6796         *indexCorrelation = costs.indexCorrelation;
6797
6798         PG_RETURN_VOID();
6799 }
6800
6801 Datum
6802 gistcostestimate(PG_FUNCTION_ARGS)
6803 {
6804         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6805         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6806         double          loop_count = PG_GETARG_FLOAT8(2);
6807         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6808         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6809         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6810         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6811         IndexOptInfo *index = path->indexinfo;
6812         List       *qinfos;
6813         GenericCosts costs;
6814         Cost            descentCost;
6815
6816         /* Do preliminary analysis of indexquals */
6817         qinfos = deconstruct_indexquals(path);
6818
6819         MemSet(&costs, 0, sizeof(costs));
6820
6821         genericcostestimate(root, path, loop_count, qinfos, &costs);
6822
6823         /*
6824          * We model index descent costs similarly to those for btree, but to do
6825          * that we first need an idea of the tree height.  We somewhat arbitrarily
6826          * assume that the fanout is 100, meaning the tree height is at most
6827          * log100(index->pages).
6828          *
6829          * Although this computation isn't really expensive enough to require
6830          * caching, we might as well use index->tree_height to cache it.
6831          */
6832         if (index->tree_height < 0) /* unknown? */
6833         {
6834                 if (index->pages > 1)   /* avoid computing log(0) */
6835                         index->tree_height = (int) (log(index->pages) / log(100.0));
6836                 else
6837                         index->tree_height = 0;
6838         }
6839
6840         /*
6841          * Add a CPU-cost component to represent the costs of initial descent. We
6842          * just use log(N) here not log2(N) since the branching factor isn't
6843          * necessarily two anyway.  As for btree, charge once per SA scan.
6844          */
6845         if (index->tuples > 1)          /* avoid computing log(0) */
6846         {
6847                 descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6848                 costs.indexStartupCost += descentCost;
6849                 costs.indexTotalCost += costs.num_sa_scans * descentCost;
6850         }
6851
6852         /*
6853          * Likewise add a per-page charge, calculated the same as for btrees.
6854          */
6855         descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6856         costs.indexStartupCost += descentCost;
6857         costs.indexTotalCost += costs.num_sa_scans * descentCost;
6858
6859         *indexStartupCost = costs.indexStartupCost;
6860         *indexTotalCost = costs.indexTotalCost;
6861         *indexSelectivity = costs.indexSelectivity;
6862         *indexCorrelation = costs.indexCorrelation;
6863
6864         PG_RETURN_VOID();
6865 }
6866
6867 Datum
6868 spgcostestimate(PG_FUNCTION_ARGS)
6869 {
6870         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6871         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6872         double          loop_count = PG_GETARG_FLOAT8(2);
6873         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6874         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6875         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6876         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6877         IndexOptInfo *index = path->indexinfo;
6878         List       *qinfos;
6879         GenericCosts costs;
6880         Cost            descentCost;
6881
6882         /* Do preliminary analysis of indexquals */
6883         qinfos = deconstruct_indexquals(path);
6884
6885         MemSet(&costs, 0, sizeof(costs));
6886
6887         genericcostestimate(root, path, loop_count, qinfos, &costs);
6888
6889         /*
6890          * We model index descent costs similarly to those for btree, but to do
6891          * that we first need an idea of the tree height.  We somewhat arbitrarily
6892          * assume that the fanout is 100, meaning the tree height is at most
6893          * log100(index->pages).
6894          *
6895          * Although this computation isn't really expensive enough to require
6896          * caching, we might as well use index->tree_height to cache it.
6897          */
6898         if (index->tree_height < 0) /* unknown? */
6899         {
6900                 if (index->pages > 1)   /* avoid computing log(0) */
6901                         index->tree_height = (int) (log(index->pages) / log(100.0));
6902                 else
6903                         index->tree_height = 0;
6904         }
6905
6906         /*
6907          * Add a CPU-cost component to represent the costs of initial descent. We
6908          * just use log(N) here not log2(N) since the branching factor isn't
6909          * necessarily two anyway.  As for btree, charge once per SA scan.
6910          */
6911         if (index->tuples > 1)          /* avoid computing log(0) */
6912         {
6913                 descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6914                 costs.indexStartupCost += descentCost;
6915                 costs.indexTotalCost += costs.num_sa_scans * descentCost;
6916         }
6917
6918         /*
6919          * Likewise add a per-page charge, calculated the same as for btrees.
6920          */
6921         descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6922         costs.indexStartupCost += descentCost;
6923         costs.indexTotalCost += costs.num_sa_scans * descentCost;
6924
6925         *indexStartupCost = costs.indexStartupCost;
6926         *indexTotalCost = costs.indexTotalCost;
6927         *indexSelectivity = costs.indexSelectivity;
6928         *indexCorrelation = costs.indexCorrelation;
6929
6930         PG_RETURN_VOID();
6931 }
6932
6933
6934 /*
6935  * Support routines for gincostestimate
6936  */
6937
6938 typedef struct
6939 {
6940         bool            haveFullScan;
6941         double          partialEntries;
6942         double          exactEntries;
6943         double          searchEntries;
6944         double          arrayScans;
6945 } GinQualCounts;
6946
6947 /*
6948  * Estimate the number of index terms that need to be searched for while
6949  * testing the given GIN query, and increment the counts in *counts
6950  * appropriately.  If the query is unsatisfiable, return false.
6951  */
6952 static bool
6953 gincost_pattern(IndexOptInfo *index, int indexcol,
6954                                 Oid clause_op, Datum query,
6955                                 GinQualCounts *counts)
6956 {
6957         Oid                     extractProcOid;
6958         Oid                     collation;
6959         int                     strategy_op;
6960         Oid                     lefttype,
6961                                 righttype;
6962         int32           nentries = 0;
6963         bool       *partial_matches = NULL;
6964         Pointer    *extra_data = NULL;
6965         bool       *nullFlags = NULL;
6966         int32           searchMode = GIN_SEARCH_MODE_DEFAULT;
6967         int32           i;
6968
6969         /*
6970          * Get the operator's strategy number and declared input data types within
6971          * the index opfamily.  (We don't need the latter, but we use
6972          * get_op_opfamily_properties because it will throw error if it fails to
6973          * find a matching pg_amop entry.)
6974          */
6975         get_op_opfamily_properties(clause_op, index->opfamily[indexcol], false,
6976                                                            &strategy_op, &lefttype, &righttype);
6977
6978         /*
6979          * GIN always uses the "default" support functions, which are those with
6980          * lefttype == righttype == the opclass' opcintype (see
6981          * IndexSupportInitialize in relcache.c).
6982          */
6983         extractProcOid = get_opfamily_proc(index->opfamily[indexcol],
6984                                                                            index->opcintype[indexcol],
6985                                                                            index->opcintype[indexcol],
6986                                                                            GIN_EXTRACTQUERY_PROC);
6987
6988         if (!OidIsValid(extractProcOid))
6989         {
6990                 /* should not happen; throw same error as index_getprocinfo */
6991                 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
6992                          GIN_EXTRACTQUERY_PROC, indexcol + 1,
6993                          get_rel_name(index->indexoid));
6994         }
6995
6996         /*
6997          * Choose collation to pass to extractProc (should match initGinState).
6998          */
6999         if (OidIsValid(index->indexcollations[indexcol]))
7000                 collation = index->indexcollations[indexcol];
7001         else
7002                 collation = DEFAULT_COLLATION_OID;
7003
7004         OidFunctionCall7Coll(extractProcOid,
7005                                                  collation,
7006                                                  query,
7007                                                  PointerGetDatum(&nentries),
7008                                                  UInt16GetDatum(strategy_op),
7009                                                  PointerGetDatum(&partial_matches),
7010                                                  PointerGetDatum(&extra_data),
7011                                                  PointerGetDatum(&nullFlags),
7012                                                  PointerGetDatum(&searchMode));
7013
7014         if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)
7015         {
7016                 /* No match is possible */
7017                 return false;
7018         }
7019
7020         for (i = 0; i < nentries; i++)
7021         {
7022                 /*
7023                  * For partial match we haven't any information to estimate number of
7024                  * matched entries in index, so, we just estimate it as 100
7025                  */
7026                 if (partial_matches && partial_matches[i])
7027                         counts->partialEntries += 100;
7028                 else
7029                         counts->exactEntries++;
7030
7031                 counts->searchEntries++;
7032         }
7033
7034         if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
7035         {
7036                 /* Treat "include empty" like an exact-match item */
7037                 counts->exactEntries++;
7038                 counts->searchEntries++;
7039         }
7040         else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
7041         {
7042                 /* It's GIN_SEARCH_MODE_ALL */
7043                 counts->haveFullScan = true;
7044         }
7045
7046         return true;
7047 }
7048
7049 /*
7050  * Estimate the number of index terms that need to be searched for while
7051  * testing the given GIN index clause, and increment the counts in *counts
7052  * appropriately.  If the query is unsatisfiable, return false.
7053  */
7054 static bool
7055 gincost_opexpr(PlannerInfo *root,
7056                            IndexOptInfo *index,
7057                            IndexQualInfo *qinfo,
7058                            GinQualCounts *counts)
7059 {
7060         int                     indexcol = qinfo->indexcol;
7061         Oid                     clause_op = qinfo->clause_op;
7062         Node       *operand = qinfo->other_operand;
7063
7064         if (!qinfo->varonleft)
7065         {
7066                 /* must commute the operator */
7067                 clause_op = get_commutator(clause_op);
7068         }
7069
7070         /* aggressively reduce to a constant, and look through relabeling */
7071         operand = estimate_expression_value(root, operand);
7072
7073         if (IsA(operand, RelabelType))
7074                 operand = (Node *) ((RelabelType *) operand)->arg;
7075
7076         /*
7077          * It's impossible to call extractQuery method for unknown operand. So
7078          * unless operand is a Const we can't do much; just assume there will be
7079          * one ordinary search entry from the operand at runtime.
7080          */
7081         if (!IsA(operand, Const))
7082         {
7083                 counts->exactEntries++;
7084                 counts->searchEntries++;
7085                 return true;
7086         }
7087
7088         /* If Const is null, there can be no matches */
7089         if (((Const *) operand)->constisnull)
7090                 return false;
7091
7092         /* Otherwise, apply extractQuery and get the actual term counts */
7093         return gincost_pattern(index, indexcol, clause_op,
7094                                                    ((Const *) operand)->constvalue,
7095                                                    counts);
7096 }
7097
7098 /*
7099  * Estimate the number of index terms that need to be searched for while
7100  * testing the given GIN index clause, and increment the counts in *counts
7101  * appropriately.  If the query is unsatisfiable, return false.
7102  *
7103  * A ScalarArrayOpExpr will give rise to N separate indexscans at runtime,
7104  * each of which involves one value from the RHS array, plus all the
7105  * non-array quals (if any).  To model this, we average the counts across
7106  * the RHS elements, and add the averages to the counts in *counts (which
7107  * correspond to per-indexscan costs).  We also multiply counts->arrayScans
7108  * by N, causing gincostestimate to scale up its estimates accordingly.
7109  */
7110 static bool
7111 gincost_scalararrayopexpr(PlannerInfo *root,
7112                                                   IndexOptInfo *index,
7113                                                   IndexQualInfo *qinfo,
7114                                                   double numIndexEntries,
7115                                                   GinQualCounts *counts)
7116 {
7117         int                     indexcol = qinfo->indexcol;
7118         Oid                     clause_op = qinfo->clause_op;
7119         Node       *rightop = qinfo->other_operand;
7120         ArrayType  *arrayval;
7121         int16           elmlen;
7122         bool            elmbyval;
7123         char            elmalign;
7124         int                     numElems;
7125         Datum      *elemValues;
7126         bool       *elemNulls;
7127         GinQualCounts arraycounts;
7128         int                     numPossible = 0;
7129         int                     i;
7130
7131         Assert(((ScalarArrayOpExpr *) qinfo->rinfo->clause)->useOr);
7132
7133         /* aggressively reduce to a constant, and look through relabeling */
7134         rightop = estimate_expression_value(root, rightop);
7135
7136         if (IsA(rightop, RelabelType))
7137                 rightop = (Node *) ((RelabelType *) rightop)->arg;
7138
7139         /*
7140          * It's impossible to call extractQuery method for unknown operand. So
7141          * unless operand is a Const we can't do much; just assume there will be
7142          * one ordinary search entry from each array entry at runtime, and fall
7143          * back on a probably-bad estimate of the number of array entries.
7144          */
7145         if (!IsA(rightop, Const))
7146         {
7147                 counts->exactEntries++;
7148                 counts->searchEntries++;
7149                 counts->arrayScans *= estimate_array_length(rightop);
7150                 return true;
7151         }
7152
7153         /* If Const is null, there can be no matches */
7154         if (((Const *) rightop)->constisnull)
7155                 return false;
7156
7157         /* Otherwise, extract the array elements and iterate over them */
7158         arrayval = DatumGetArrayTypeP(((Const *) rightop)->constvalue);
7159         get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
7160                                                  &elmlen, &elmbyval, &elmalign);
7161         deconstruct_array(arrayval,
7162                                           ARR_ELEMTYPE(arrayval),
7163                                           elmlen, elmbyval, elmalign,
7164                                           &elemValues, &elemNulls, &numElems);
7165
7166         memset(&arraycounts, 0, sizeof(arraycounts));
7167
7168         for (i = 0; i < numElems; i++)
7169         {
7170                 GinQualCounts elemcounts;
7171
7172                 /* NULL can't match anything, so ignore, as the executor will */
7173                 if (elemNulls[i])
7174                         continue;
7175
7176                 /* Otherwise, apply extractQuery and get the actual term counts */
7177                 memset(&elemcounts, 0, sizeof(elemcounts));
7178
7179                 if (gincost_pattern(index, indexcol, clause_op, elemValues[i],
7180                                                         &elemcounts))
7181                 {
7182                         /* We ignore array elements that are unsatisfiable patterns */
7183                         numPossible++;
7184
7185                         if (elemcounts.haveFullScan)
7186                         {
7187                                 /*
7188                                  * Full index scan will be required.  We treat this as if
7189                                  * every key in the index had been listed in the query; is
7190                                  * that reasonable?
7191                                  */
7192                                 elemcounts.partialEntries = 0;
7193                                 elemcounts.exactEntries = numIndexEntries;
7194                                 elemcounts.searchEntries = numIndexEntries;
7195                         }
7196                         arraycounts.partialEntries += elemcounts.partialEntries;
7197                         arraycounts.exactEntries += elemcounts.exactEntries;
7198                         arraycounts.searchEntries += elemcounts.searchEntries;
7199                 }
7200         }
7201
7202         if (numPossible == 0)
7203         {
7204                 /* No satisfiable patterns in the array */
7205                 return false;
7206         }
7207
7208         /*
7209          * Now add the averages to the global counts.  This will give us an
7210          * estimate of the average number of terms searched for in each indexscan,
7211          * including contributions from both array and non-array quals.
7212          */
7213         counts->partialEntries += arraycounts.partialEntries / numPossible;
7214         counts->exactEntries += arraycounts.exactEntries / numPossible;
7215         counts->searchEntries += arraycounts.searchEntries / numPossible;
7216
7217         counts->arrayScans *= numPossible;
7218
7219         return true;
7220 }
7221
7222 /*
7223  * GIN has search behavior completely different from other index types
7224  */
7225 Datum
7226 gincostestimate(PG_FUNCTION_ARGS)
7227 {
7228         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
7229         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
7230         double          loop_count = PG_GETARG_FLOAT8(2);
7231         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
7232         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
7233         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
7234         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
7235         IndexOptInfo *index = path->indexinfo;
7236         List       *indexQuals = path->indexquals;
7237         List       *indexOrderBys = path->indexorderbys;
7238         List       *qinfos;
7239         ListCell   *l;
7240         List       *selectivityQuals;
7241         double          numPages = index->pages,
7242                                 numTuples = index->tuples;
7243         double          numEntryPages,
7244                                 numDataPages,
7245                                 numPendingPages,
7246                                 numEntries;
7247         GinQualCounts counts;
7248         bool            matchPossible;
7249         double          entryPagesFetched,
7250                                 dataPagesFetched,
7251                                 dataPagesFetchedBySel;
7252         double          qual_op_cost,
7253                                 qual_arg_cost,
7254                                 spc_random_page_cost,
7255                                 outer_scans;
7256         Relation        indexRel;
7257         GinStatsData ginStats;
7258
7259         /* Do preliminary analysis of indexquals */
7260         qinfos = deconstruct_indexquals(path);
7261
7262         /*
7263          * Obtain statistical information from the meta page, if possible.  Else
7264          * set ginStats to zeroes, and we'll cope below.
7265          */
7266         if (!index->hypothetical)
7267         {
7268                 indexRel = index_open(index->indexoid, AccessShareLock);
7269                 ginGetStats(indexRel, &ginStats);
7270                 index_close(indexRel, AccessShareLock);
7271         }
7272         else
7273         {
7274                 memset(&ginStats, 0, sizeof(ginStats));
7275         }
7276
7277         if (ginStats.nTotalPages > 0 && ginStats.nEntryPages > 0 && numPages > 0)
7278         {
7279                 /*
7280                  * We got valid stats.  nPendingPages can be trusted, but the other
7281                  * fields are data as of the last VACUUM.  Scale them by the ratio
7282                  * numPages / nTotalPages to account for growth since then.
7283                  */
7284                 double          scale = numPages / ginStats.nTotalPages;
7285
7286                 numEntryPages = ginStats.nEntryPages;
7287                 numDataPages = ginStats.nDataPages;
7288                 numPendingPages = ginStats.nPendingPages;
7289                 numEntries = ginStats.nEntries;
7290
7291                 numEntryPages = ceil(numEntryPages * scale);
7292                 numDataPages = ceil(numDataPages * scale);
7293                 numEntries = ceil(numEntries * scale);
7294                 /* ensure we didn't round up too much */
7295                 numEntryPages = Min(numEntryPages, numPages);
7296                 numDataPages = Min(numDataPages, numPages - numEntryPages);
7297         }
7298         else
7299         {
7300                 /*
7301                  * It's a hypothetical index, or perhaps an index created pre-9.1 and
7302                  * never vacuumed since upgrading.  Invent some plausible internal
7303                  * statistics based on the index page count.  We estimate that 90% of
7304                  * the index is entry pages, and the rest is data pages.  Estimate 100
7305                  * entries per entry page; this is rather bogus since it'll depend on
7306                  * the size of the keys, but it's more robust than trying to predict
7307                  * the number of entries per heap tuple.
7308                  */
7309                 numPages = Max(numPages, 10);
7310                 numEntryPages = floor(numPages * 0.90);
7311                 numDataPages = numPages - numEntryPages;
7312                 numPendingPages = 0;
7313                 numEntries = floor(numEntryPages * 100);
7314         }
7315
7316         /* In an empty index, numEntries could be zero.  Avoid divide-by-zero */
7317         if (numEntries < 1)
7318                 numEntries = 1;
7319
7320         /*
7321          * Include predicate in selectivityQuals (should match
7322          * genericcostestimate)
7323          */
7324         if (index->indpred != NIL)
7325         {
7326                 List       *predExtraQuals = NIL;
7327
7328                 foreach(l, index->indpred)
7329                 {
7330                         Node       *predQual = (Node *) lfirst(l);
7331                         List       *oneQual = list_make1(predQual);
7332
7333                         if (!predicate_implied_by(oneQual, indexQuals))
7334                                 predExtraQuals = list_concat(predExtraQuals, oneQual);
7335                 }
7336                 /* list_concat avoids modifying the passed-in indexQuals list */
7337                 selectivityQuals = list_concat(predExtraQuals, indexQuals);
7338         }
7339         else
7340                 selectivityQuals = indexQuals;
7341
7342         /* Estimate the fraction of main-table tuples that will be visited */
7343         *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7344                                                                                            index->rel->relid,
7345                                                                                            JOIN_INNER,
7346                                                                                            NULL);
7347
7348         /* fetch estimated page cost for tablespace containing index */
7349         get_tablespace_page_costs(index->reltablespace,
7350                                                           &spc_random_page_cost,
7351                                                           NULL);
7352
7353         /*
7354          * Generic assumption about index correlation: there isn't any.
7355          */
7356         *indexCorrelation = 0.0;
7357
7358         /*
7359          * Examine quals to estimate number of search entries & partial matches
7360          */
7361         memset(&counts, 0, sizeof(counts));
7362         counts.arrayScans = 1;
7363         matchPossible = true;
7364
7365         foreach(l, qinfos)
7366         {
7367                 IndexQualInfo *qinfo = (IndexQualInfo *) lfirst(l);
7368                 Expr       *clause = qinfo->rinfo->clause;
7369
7370                 if (IsA(clause, OpExpr))
7371                 {
7372                         matchPossible = gincost_opexpr(root,
7373                                                                                    index,
7374                                                                                    qinfo,
7375                                                                                    &counts);
7376                         if (!matchPossible)
7377                                 break;
7378                 }
7379                 else if (IsA(clause, ScalarArrayOpExpr))
7380                 {
7381                         matchPossible = gincost_scalararrayopexpr(root,
7382                                                                                                           index,
7383                                                                                                           qinfo,
7384                                                                                                           numEntries,
7385                                                                                                           &counts);
7386                         if (!matchPossible)
7387                                 break;
7388                 }
7389                 else
7390                 {
7391                         /* shouldn't be anything else for a GIN index */
7392                         elog(ERROR, "unsupported GIN indexqual type: %d",
7393                                  (int) nodeTag(clause));
7394                 }
7395         }
7396
7397         /* Fall out if there were any provably-unsatisfiable quals */
7398         if (!matchPossible)
7399         {
7400                 *indexStartupCost = 0;
7401                 *indexTotalCost = 0;
7402                 *indexSelectivity = 0;
7403                 PG_RETURN_VOID();
7404         }
7405
7406         if (counts.haveFullScan || indexQuals == NIL)
7407         {
7408                 /*
7409                  * Full index scan will be required.  We treat this as if every key in
7410                  * the index had been listed in the query; is that reasonable?
7411                  */
7412                 counts.partialEntries = 0;
7413                 counts.exactEntries = numEntries;
7414                 counts.searchEntries = numEntries;
7415         }
7416
7417         /* Will we have more than one iteration of a nestloop scan? */
7418         outer_scans = loop_count;
7419
7420         /*
7421          * Compute cost to begin scan, first of all, pay attention to pending
7422          * list.
7423          */
7424         entryPagesFetched = numPendingPages;
7425
7426         /*
7427          * Estimate number of entry pages read.  We need to do
7428          * counts.searchEntries searches.  Use a power function as it should be,
7429          * but tuples on leaf pages usually is much greater. Here we include all
7430          * searches in entry tree, including search of first entry in partial
7431          * match algorithm
7432          */
7433         entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7434
7435         /*
7436          * Add an estimate of entry pages read by partial match algorithm. It's a
7437          * scan over leaf pages in entry tree.  We haven't any useful stats here,
7438          * so estimate it as proportion.
7439          */
7440         entryPagesFetched += ceil(numEntryPages * counts.partialEntries / numEntries);
7441
7442         /*
7443          * Partial match algorithm reads all data pages before doing actual scan,
7444          * so it's a startup cost. Again, we haven't any useful stats here, so,
7445          * estimate it as proportion
7446          */
7447         dataPagesFetched = ceil(numDataPages * counts.partialEntries / numEntries);
7448
7449         /*
7450          * Calculate cache effects if more than one scan due to nestloops or array
7451          * quals.  The result is pro-rated per nestloop scan, but the array qual
7452          * factor shouldn't be pro-rated (compare genericcostestimate).
7453          */
7454         if (outer_scans > 1 || counts.arrayScans > 1)
7455         {
7456                 entryPagesFetched *= outer_scans * counts.arrayScans;
7457                 entryPagesFetched = index_pages_fetched(entryPagesFetched,
7458                                                                                                 (BlockNumber) numEntryPages,
7459                                                                                                 numEntryPages, root);
7460                 entryPagesFetched /= outer_scans;
7461                 dataPagesFetched *= outer_scans * counts.arrayScans;
7462                 dataPagesFetched = index_pages_fetched(dataPagesFetched,
7463                                                                                            (BlockNumber) numDataPages,
7464                                                                                            numDataPages, root);
7465                 dataPagesFetched /= outer_scans;
7466         }
7467
7468         /*
7469          * Here we use random page cost because logically-close pages could be far
7470          * apart on disk.
7471          */
7472         *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7473
7474         /*
7475          * Now compute the number of data pages fetched during the scan.
7476          *
7477          * We assume every entry to have the same number of items, and that there
7478          * is no overlap between them. (XXX: tsvector and array opclasses collect
7479          * statistics on the frequency of individual keys; it would be nice to use
7480          * those here.)
7481          */
7482         dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7483
7484         /*
7485          * If there is a lot of overlap among the entries, in particular if one of
7486          * the entries is very frequent, the above calculation can grossly
7487          * under-estimate.  As a simple cross-check, calculate a lower bound based
7488          * on the overall selectivity of the quals.  At a minimum, we must read
7489          * one item pointer for each matching entry.
7490          *
7491          * The width of each item pointer varies, based on the level of
7492          * compression.  We don't have statistics on that, but an average of
7493          * around 3 bytes per item is fairly typical.
7494          */
7495         dataPagesFetchedBySel = ceil(*indexSelectivity *
7496                                                                  (numTuples / (BLCKSZ / 3)));
7497         if (dataPagesFetchedBySel > dataPagesFetched)
7498                 dataPagesFetched = dataPagesFetchedBySel;
7499
7500         /* Account for cache effects, the same as above */
7501         if (outer_scans > 1 || counts.arrayScans > 1)
7502         {
7503                 dataPagesFetched *= outer_scans * counts.arrayScans;
7504                 dataPagesFetched = index_pages_fetched(dataPagesFetched,
7505                                                                                            (BlockNumber) numDataPages,
7506                                                                                            numDataPages, root);
7507                 dataPagesFetched /= outer_scans;
7508         }
7509
7510         /* And apply random_page_cost as the cost per page */
7511         *indexTotalCost = *indexStartupCost +
7512                 dataPagesFetched * spc_random_page_cost;
7513
7514         /*
7515          * Add on index qual eval costs, much as in genericcostestimate
7516          */
7517         qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7518                 orderby_operands_eval_cost(root, path);
7519         qual_op_cost = cpu_operator_cost *
7520                 (list_length(indexQuals) + list_length(indexOrderBys));
7521
7522         *indexStartupCost += qual_arg_cost;
7523         *indexTotalCost += qual_arg_cost;
7524         *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7525
7526         PG_RETURN_VOID();
7527 }
7528
7529 /*
7530  * BRIN has search behavior completely different from other index types
7531  */
7532 Datum
7533 brincostestimate(PG_FUNCTION_ARGS)
7534 {
7535         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
7536         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
7537         double          loop_count = PG_GETARG_FLOAT8(2);
7538         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
7539         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
7540         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
7541         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
7542         IndexOptInfo *index = path->indexinfo;
7543         List       *indexQuals = path->indexquals;
7544         List       *indexOrderBys = path->indexorderbys;
7545         double          numPages = index->pages;
7546         double          numTuples = index->tuples;
7547         List       *qinfos;
7548         Cost            spc_seq_page_cost;
7549         Cost            spc_random_page_cost;
7550         double          qual_op_cost;
7551         double          qual_arg_cost;
7552
7553         /* Do preliminary analysis of indexquals */
7554         qinfos = deconstruct_indexquals(path);
7555
7556         /* fetch estimated page cost for tablespace containing index */
7557         get_tablespace_page_costs(index->reltablespace,
7558                                                           &spc_random_page_cost,
7559                                                           &spc_seq_page_cost);
7560
7561         /*
7562          * BRIN indexes are always read in full; use that as startup cost.
7563          *
7564          * XXX maybe only include revmap pages here?
7565          */
7566         *indexStartupCost = spc_seq_page_cost * numPages * loop_count;
7567
7568         /*
7569          * To read a BRIN index there might be a bit of back and forth over
7570          * regular pages, as revmap might point to them out of sequential order;
7571          * calculate this as reading the whole index in random order.
7572          */
7573         *indexTotalCost = spc_random_page_cost * numPages * loop_count;
7574
7575         *indexSelectivity =
7576                 clauselist_selectivity(root, indexQuals,
7577                                                            path->indexinfo->rel->relid,
7578                                                            JOIN_INNER, NULL);
7579         *indexCorrelation = 1;
7580
7581         /*
7582          * Add on index qual eval costs, much as in genericcostestimate.
7583          */
7584         qual_arg_cost = other_operands_eval_cost(root, qinfos) +
7585                 orderby_operands_eval_cost(root, path);
7586         qual_op_cost = cpu_operator_cost *
7587                 (list_length(indexQuals) + list_length(indexOrderBys));
7588
7589         *indexStartupCost += qual_arg_cost;
7590         *indexTotalCost += qual_arg_cost;
7591         *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7592
7593         /* XXX what about pages_per_range? */
7594
7595         PG_RETURN_VOID();
7596 }