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