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          * If no grouping columns, there's exactly one group.  (This can't happen
3214          * for normal cases with GROUP BY or DISTINCT, but it is possible for
3215          * corner cases with set operations.)
3216          */
3217         if (groupExprs == NIL)
3218                 return 1.0;
3219
3220         /*
3221          * Count groups derived from boolean grouping expressions.      For other
3222          * expressions, find the unique Vars used, treating an expression as a Var
3223          * if we can find stats for it.  For each one, record the statistical
3224          * estimate of number of distinct values (total in its table, without
3225          * regard for filtering).
3226          */
3227         numdistinct = 1.0;
3228
3229         foreach(l, groupExprs)
3230         {
3231                 Node       *groupexpr = (Node *) lfirst(l);
3232                 VariableStatData vardata;
3233                 List       *varshere;
3234                 ListCell   *l2;
3235
3236                 /* Short-circuit for expressions returning boolean */
3237                 if (exprType(groupexpr) == BOOLOID)
3238                 {
3239                         numdistinct *= 2.0;
3240                         continue;
3241                 }
3242
3243                 /*
3244                  * If examine_variable is able to deduce anything about the GROUP BY
3245                  * expression, treat it as a single variable even if it's really more
3246                  * complicated.
3247                  */
3248                 examine_variable(root, groupexpr, 0, &vardata);
3249                 if (HeapTupleIsValid(vardata.statsTuple) || vardata.isunique)
3250                 {
3251                         varinfos = add_unique_group_var(root, varinfos,
3252                                                                                         groupexpr, &vardata);
3253                         ReleaseVariableStats(vardata);
3254                         continue;
3255                 }
3256                 ReleaseVariableStats(vardata);
3257
3258                 /*
3259                  * Else pull out the component Vars.  Handle PlaceHolderVars by
3260                  * recursing into their arguments (effectively assuming that the
3261                  * PlaceHolderVar doesn't change the number of groups, which boils
3262                  * down to ignoring the possible addition of nulls to the result set).
3263                  */
3264                 varshere = pull_var_clause(groupexpr,
3265                                                                    PVC_RECURSE_AGGREGATES,
3266                                                                    PVC_RECURSE_PLACEHOLDERS);
3267
3268                 /*
3269                  * If we find any variable-free GROUP BY item, then either it is a
3270                  * constant (and we can ignore it) or it contains a volatile function;
3271                  * in the latter case we punt and assume that each input row will
3272                  * yield a distinct group.
3273                  */
3274                 if (varshere == NIL)
3275                 {
3276                         if (contain_volatile_functions(groupexpr))
3277                                 return input_rows;
3278                         continue;
3279                 }
3280
3281                 /*
3282                  * Else add variables to varinfos list
3283                  */
3284                 foreach(l2, varshere)
3285                 {
3286                         Node       *var = (Node *) lfirst(l2);
3287
3288                         examine_variable(root, var, 0, &vardata);
3289                         varinfos = add_unique_group_var(root, varinfos, var, &vardata);
3290                         ReleaseVariableStats(vardata);
3291                 }
3292         }
3293
3294         /*
3295          * If now no Vars, we must have an all-constant or all-boolean GROUP BY
3296          * list.
3297          */
3298         if (varinfos == NIL)
3299         {
3300                 /* Guard against out-of-range answers */
3301                 if (numdistinct > input_rows)
3302                         numdistinct = input_rows;
3303                 return numdistinct;
3304         }
3305
3306         /*
3307          * Group Vars by relation and estimate total numdistinct.
3308          *
3309          * For each iteration of the outer loop, we process the frontmost Var in
3310          * varinfos, plus all other Vars in the same relation.  We remove these
3311          * Vars from the newvarinfos list for the next iteration. This is the
3312          * easiest way to group Vars of same rel together.
3313          */
3314         do
3315         {
3316                 GroupVarInfo *varinfo1 = (GroupVarInfo *) linitial(varinfos);
3317                 RelOptInfo *rel = varinfo1->rel;
3318                 double          reldistinct = varinfo1->ndistinct;
3319                 double          relmaxndistinct = reldistinct;
3320                 int                     relvarcount = 1;
3321                 List       *newvarinfos = NIL;
3322
3323                 /*
3324                  * Get the product of numdistinct estimates of the Vars for this rel.
3325                  * Also, construct new varinfos list of remaining Vars.
3326                  */
3327                 for_each_cell(l, lnext(list_head(varinfos)))
3328                 {
3329                         GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(l);
3330
3331                         if (varinfo2->rel == varinfo1->rel)
3332                         {
3333                                 reldistinct *= varinfo2->ndistinct;
3334                                 if (relmaxndistinct < varinfo2->ndistinct)
3335                                         relmaxndistinct = varinfo2->ndistinct;
3336                                 relvarcount++;
3337                         }
3338                         else
3339                         {
3340                                 /* not time to process varinfo2 yet */
3341                                 newvarinfos = lcons(varinfo2, newvarinfos);
3342                         }
3343                 }
3344
3345                 /*
3346                  * Sanity check --- don't divide by zero if empty relation.
3347                  */
3348                 Assert(rel->reloptkind == RELOPT_BASEREL);
3349                 if (rel->tuples > 0)
3350                 {
3351                         /*
3352                          * Clamp to size of rel, or size of rel / 10 if multiple Vars. The
3353                          * fudge factor is because the Vars are probably correlated but we
3354                          * don't know by how much.  We should never clamp to less than the
3355                          * largest ndistinct value for any of the Vars, though, since
3356                          * there will surely be at least that many groups.
3357                          */
3358                         double          clamp = rel->tuples;
3359
3360                         if (relvarcount > 1)
3361                         {
3362                                 clamp *= 0.1;
3363                                 if (clamp < relmaxndistinct)
3364                                 {
3365                                         clamp = relmaxndistinct;
3366                                         /* for sanity in case some ndistinct is too large: */
3367                                         if (clamp > rel->tuples)
3368                                                 clamp = rel->tuples;
3369                                 }
3370                         }
3371                         if (reldistinct > clamp)
3372                                 reldistinct = clamp;
3373
3374                         /*
3375                          * Multiply by restriction selectivity.
3376                          */
3377                         reldistinct *= rel->rows / rel->tuples;
3378
3379                         /*
3380                          * Update estimate of total distinct groups.
3381                          */
3382                         numdistinct *= reldistinct;
3383                 }
3384
3385                 varinfos = newvarinfos;
3386         } while (varinfos != NIL);
3387
3388         numdistinct = ceil(numdistinct);
3389
3390         /* Guard against out-of-range answers */
3391         if (numdistinct > input_rows)
3392                 numdistinct = input_rows;
3393         if (numdistinct < 1.0)
3394                 numdistinct = 1.0;
3395
3396         return numdistinct;
3397 }
3398
3399 /*
3400  * Estimate hash bucketsize fraction (ie, number of entries in a bucket
3401  * divided by total tuples in relation) if the specified expression is used
3402  * as a hash key.
3403  *
3404  * XXX This is really pretty bogus since we're effectively assuming that the
3405  * distribution of hash keys will be the same after applying restriction
3406  * clauses as it was in the underlying relation.  However, we are not nearly
3407  * smart enough to figure out how the restrict clauses might change the
3408  * distribution, so this will have to do for now.
3409  *
3410  * We are passed the number of buckets the executor will use for the given
3411  * input relation.      If the data were perfectly distributed, with the same
3412  * number of tuples going into each available bucket, then the bucketsize
3413  * fraction would be 1/nbuckets.  But this happy state of affairs will occur
3414  * only if (a) there are at least nbuckets distinct data values, and (b)
3415  * we have a not-too-skewed data distribution.  Otherwise the buckets will
3416  * be nonuniformly occupied.  If the other relation in the join has a key
3417  * distribution similar to this one's, then the most-loaded buckets are
3418  * exactly those that will be probed most often.  Therefore, the "average"
3419  * bucket size for costing purposes should really be taken as something close
3420  * to the "worst case" bucket size.  We try to estimate this by adjusting the
3421  * fraction if there are too few distinct data values, and then scaling up
3422  * by the ratio of the most common value's frequency to the average frequency.
3423  *
3424  * If no statistics are available, use a default estimate of 0.1.  This will
3425  * discourage use of a hash rather strongly if the inner relation is large,
3426  * which is what we want.  We do not want to hash unless we know that the
3427  * inner rel is well-dispersed (or the alternatives seem much worse).
3428  */
3429 Selectivity
3430 estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey, double nbuckets)
3431 {
3432         VariableStatData vardata;
3433         double          estfract,
3434                                 ndistinct,
3435                                 stanullfrac,
3436                                 mcvfreq,
3437                                 avgfreq;
3438         bool            isdefault;
3439         float4     *numbers;
3440         int                     nnumbers;
3441
3442         examine_variable(root, hashkey, 0, &vardata);
3443
3444         /* Get number of distinct values */
3445         ndistinct = get_variable_numdistinct(&vardata, &isdefault);
3446
3447         /* If ndistinct isn't real, punt and return 0.1, per comments above */
3448         if (isdefault)
3449         {
3450                 ReleaseVariableStats(vardata);
3451                 return (Selectivity) 0.1;
3452         }
3453
3454         /* Get fraction that are null */
3455         if (HeapTupleIsValid(vardata.statsTuple))
3456         {
3457                 Form_pg_statistic stats;
3458
3459                 stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
3460                 stanullfrac = stats->stanullfrac;
3461         }
3462         else
3463                 stanullfrac = 0.0;
3464
3465         /* Compute avg freq of all distinct data values in raw relation */
3466         avgfreq = (1.0 - stanullfrac) / ndistinct;
3467
3468         /*
3469          * Adjust ndistinct to account for restriction clauses.  Observe we are
3470          * assuming that the data distribution is affected uniformly by the
3471          * restriction clauses!
3472          *
3473          * XXX Possibly better way, but much more expensive: multiply by
3474          * selectivity of rel's restriction clauses that mention the target Var.
3475          */
3476         if (vardata.rel)
3477                 ndistinct *= vardata.rel->rows / vardata.rel->tuples;
3478
3479         /*
3480          * Initial estimate of bucketsize fraction is 1/nbuckets as long as the
3481          * number of buckets is less than the expected number of distinct values;
3482          * otherwise it is 1/ndistinct.
3483          */
3484         if (ndistinct > nbuckets)
3485                 estfract = 1.0 / nbuckets;
3486         else
3487                 estfract = 1.0 / ndistinct;
3488
3489         /*
3490          * Look up the frequency of the most common value, if available.
3491          */
3492         mcvfreq = 0.0;
3493
3494         if (HeapTupleIsValid(vardata.statsTuple))
3495         {
3496                 if (get_attstatsslot(vardata.statsTuple,
3497                                                          vardata.atttype, vardata.atttypmod,
3498                                                          STATISTIC_KIND_MCV, InvalidOid,
3499                                                          NULL,
3500                                                          NULL, NULL,
3501                                                          &numbers, &nnumbers))
3502                 {
3503                         /*
3504                          * The first MCV stat is for the most common value.
3505                          */
3506                         if (nnumbers > 0)
3507                                 mcvfreq = numbers[0];
3508                         free_attstatsslot(vardata.atttype, NULL, 0,
3509                                                           numbers, nnumbers);
3510                 }
3511         }
3512
3513         /*
3514          * Adjust estimated bucketsize upward to account for skewed distribution.
3515          */
3516         if (avgfreq > 0.0 && mcvfreq > avgfreq)
3517                 estfract *= mcvfreq / avgfreq;
3518
3519         /*
3520          * Clamp bucketsize to sane range (the above adjustment could easily
3521          * produce an out-of-range result).  We set the lower bound a little above
3522          * zero, since zero isn't a very sane result.
3523          */
3524         if (estfract < 1.0e-6)
3525                 estfract = 1.0e-6;
3526         else if (estfract > 1.0)
3527                 estfract = 1.0;
3528
3529         ReleaseVariableStats(vardata);
3530
3531         return (Selectivity) estfract;
3532 }
3533
3534
3535 /*-------------------------------------------------------------------------
3536  *
3537  * Support routines
3538  *
3539  *-------------------------------------------------------------------------
3540  */
3541
3542 /*
3543  * convert_to_scalar
3544  *        Convert non-NULL values of the indicated types to the comparison
3545  *        scale needed by scalarineqsel().
3546  *        Returns "true" if successful.
3547  *
3548  * XXX this routine is a hack: ideally we should look up the conversion
3549  * subroutines in pg_type.
3550  *
3551  * All numeric datatypes are simply converted to their equivalent
3552  * "double" values.  (NUMERIC values that are outside the range of "double"
3553  * are clamped to +/- HUGE_VAL.)
3554  *
3555  * String datatypes are converted by convert_string_to_scalar(),
3556  * which is explained below.  The reason why this routine deals with
3557  * three values at a time, not just one, is that we need it for strings.
3558  *
3559  * The bytea datatype is just enough different from strings that it has
3560  * to be treated separately.
3561  *
3562  * The several datatypes representing absolute times are all converted
3563  * to Timestamp, which is actually a double, and then we just use that
3564  * double value.  Note this will give correct results even for the "special"
3565  * values of Timestamp, since those are chosen to compare correctly;
3566  * see timestamp_cmp.
3567  *
3568  * The several datatypes representing relative times (intervals) are all
3569  * converted to measurements expressed in seconds.
3570  */
3571 static bool
3572 convert_to_scalar(Datum value, Oid valuetypid, double *scaledvalue,
3573                                   Datum lobound, Datum hibound, Oid boundstypid,
3574                                   double *scaledlobound, double *scaledhibound)
3575 {
3576         /*
3577          * Both the valuetypid and the boundstypid should exactly match the
3578          * declared input type(s) of the operator we are invoked for, so we just
3579          * error out if either is not recognized.
3580          *
3581          * XXX The histogram we are interpolating between points of could belong
3582          * to a column that's only binary-compatible with the declared type. In
3583          * essence we are assuming that the semantics of binary-compatible types
3584          * are enough alike that we can use a histogram generated with one type's
3585          * operators to estimate selectivity for the other's.  This is outright
3586          * wrong in some cases --- in particular signed versus unsigned
3587          * interpretation could trip us up.  But it's useful enough in the
3588          * majority of cases that we do it anyway.      Should think about more
3589          * rigorous ways to do it.
3590          */
3591         switch (valuetypid)
3592         {
3593                         /*
3594                          * Built-in numeric types
3595                          */
3596                 case BOOLOID:
3597                 case INT2OID:
3598                 case INT4OID:
3599                 case INT8OID:
3600                 case FLOAT4OID:
3601                 case FLOAT8OID:
3602                 case NUMERICOID:
3603                 case OIDOID:
3604                 case REGPROCOID:
3605                 case REGPROCEDUREOID:
3606                 case REGOPEROID:
3607                 case REGOPERATOROID:
3608                 case REGCLASSOID:
3609                 case REGTYPEOID:
3610                 case REGCONFIGOID:
3611                 case REGDICTIONARYOID:
3612                         *scaledvalue = convert_numeric_to_scalar(value, valuetypid);
3613                         *scaledlobound = convert_numeric_to_scalar(lobound, boundstypid);
3614                         *scaledhibound = convert_numeric_to_scalar(hibound, boundstypid);
3615                         return true;
3616
3617                         /*
3618                          * Built-in string types
3619                          */
3620                 case CHAROID:
3621                 case BPCHAROID:
3622                 case VARCHAROID:
3623                 case TEXTOID:
3624                 case NAMEOID:
3625                         {
3626                                 char       *valstr = convert_string_datum(value, valuetypid);
3627                                 char       *lostr = convert_string_datum(lobound, boundstypid);
3628                                 char       *histr = convert_string_datum(hibound, boundstypid);
3629
3630                                 convert_string_to_scalar(valstr, scaledvalue,
3631                                                                                  lostr, scaledlobound,
3632                                                                                  histr, scaledhibound);
3633                                 pfree(valstr);
3634                                 pfree(lostr);
3635                                 pfree(histr);
3636                                 return true;
3637                         }
3638
3639                         /*
3640                          * Built-in bytea type
3641                          */
3642                 case BYTEAOID:
3643                         {
3644                                 convert_bytea_to_scalar(value, scaledvalue,
3645                                                                                 lobound, scaledlobound,
3646                                                                                 hibound, scaledhibound);
3647                                 return true;
3648                         }
3649
3650                         /*
3651                          * Built-in time types
3652                          */
3653                 case TIMESTAMPOID:
3654                 case TIMESTAMPTZOID:
3655                 case ABSTIMEOID:
3656                 case DATEOID:
3657                 case INTERVALOID:
3658                 case RELTIMEOID:
3659                 case TINTERVALOID:
3660                 case TIMEOID:
3661                 case TIMETZOID:
3662                         *scaledvalue = convert_timevalue_to_scalar(value, valuetypid);
3663                         *scaledlobound = convert_timevalue_to_scalar(lobound, boundstypid);
3664                         *scaledhibound = convert_timevalue_to_scalar(hibound, boundstypid);
3665                         return true;
3666
3667                         /*
3668                          * Built-in network types
3669                          */
3670                 case INETOID:
3671                 case CIDROID:
3672                 case MACADDROID:
3673                         *scaledvalue = convert_network_to_scalar(value, valuetypid);
3674                         *scaledlobound = convert_network_to_scalar(lobound, boundstypid);
3675                         *scaledhibound = convert_network_to_scalar(hibound, boundstypid);
3676                         return true;
3677         }
3678         /* Don't know how to convert */
3679         *scaledvalue = *scaledlobound = *scaledhibound = 0;
3680         return false;
3681 }
3682
3683 /*
3684  * Do convert_to_scalar()'s work for any numeric data type.
3685  */
3686 static double
3687 convert_numeric_to_scalar(Datum value, Oid typid)
3688 {
3689         switch (typid)
3690         {
3691                 case BOOLOID:
3692                         return (double) DatumGetBool(value);
3693                 case INT2OID:
3694                         return (double) DatumGetInt16(value);
3695                 case INT4OID:
3696                         return (double) DatumGetInt32(value);
3697                 case INT8OID:
3698                         return (double) DatumGetInt64(value);
3699                 case FLOAT4OID:
3700                         return (double) DatumGetFloat4(value);
3701                 case FLOAT8OID:
3702                         return (double) DatumGetFloat8(value);
3703                 case NUMERICOID:
3704                         /* Note: out-of-range values will be clamped to +-HUGE_VAL */
3705                         return (double)
3706                                 DatumGetFloat8(DirectFunctionCall1(numeric_float8_no_overflow,
3707                                                                                                    value));
3708                 case OIDOID:
3709                 case REGPROCOID:
3710                 case REGPROCEDUREOID:
3711                 case REGOPEROID:
3712                 case REGOPERATOROID:
3713                 case REGCLASSOID:
3714                 case REGTYPEOID:
3715                 case REGCONFIGOID:
3716                 case REGDICTIONARYOID:
3717                         /* we can treat OIDs as integers... */
3718                         return (double) DatumGetObjectId(value);
3719         }
3720
3721         /*
3722          * Can't get here unless someone tries to use scalarltsel/scalargtsel on
3723          * an operator with one numeric and one non-numeric operand.
3724          */
3725         elog(ERROR, "unsupported type: %u", typid);
3726         return 0;
3727 }
3728
3729 /*
3730  * Do convert_to_scalar()'s work for any character-string data type.
3731  *
3732  * String datatypes are converted to a scale that ranges from 0 to 1,
3733  * where we visualize the bytes of the string as fractional digits.
3734  *
3735  * We do not want the base to be 256, however, since that tends to
3736  * generate inflated selectivity estimates; few databases will have
3737  * occurrences of all 256 possible byte values at each position.
3738  * Instead, use the smallest and largest byte values seen in the bounds
3739  * as the estimated range for each byte, after some fudging to deal with
3740  * the fact that we probably aren't going to see the full range that way.
3741  *
3742  * An additional refinement is that we discard any common prefix of the
3743  * three strings before computing the scaled values.  This allows us to
3744  * "zoom in" when we encounter a narrow data range.  An example is a phone
3745  * number database where all the values begin with the same area code.
3746  * (Actually, the bounds will be adjacent histogram-bin-boundary values,
3747  * so this is more likely to happen than you might think.)
3748  */
3749 static void
3750 convert_string_to_scalar(char *value,
3751                                                  double *scaledvalue,
3752                                                  char *lobound,
3753                                                  double *scaledlobound,
3754                                                  char *hibound,
3755                                                  double *scaledhibound)
3756 {
3757         int                     rangelo,
3758                                 rangehi;
3759         char       *sptr;
3760
3761         rangelo = rangehi = (unsigned char) hibound[0];
3762         for (sptr = lobound; *sptr; sptr++)
3763         {
3764                 if (rangelo > (unsigned char) *sptr)
3765                         rangelo = (unsigned char) *sptr;
3766                 if (rangehi < (unsigned char) *sptr)
3767                         rangehi = (unsigned char) *sptr;
3768         }
3769         for (sptr = hibound; *sptr; sptr++)
3770         {
3771                 if (rangelo > (unsigned char) *sptr)
3772                         rangelo = (unsigned char) *sptr;
3773                 if (rangehi < (unsigned char) *sptr)
3774                         rangehi = (unsigned char) *sptr;
3775         }
3776         /* If range includes any upper-case ASCII chars, make it include all */
3777         if (rangelo <= 'Z' && rangehi >= 'A')
3778         {
3779                 if (rangelo > 'A')
3780                         rangelo = 'A';
3781                 if (rangehi < 'Z')
3782                         rangehi = 'Z';
3783         }
3784         /* Ditto lower-case */
3785         if (rangelo <= 'z' && rangehi >= 'a')
3786         {
3787                 if (rangelo > 'a')
3788                         rangelo = 'a';
3789                 if (rangehi < 'z')
3790                         rangehi = 'z';
3791         }
3792         /* Ditto digits */
3793         if (rangelo <= '9' && rangehi >= '0')
3794         {
3795                 if (rangelo > '0')
3796                         rangelo = '0';
3797                 if (rangehi < '9')
3798                         rangehi = '9';
3799         }
3800
3801         /*
3802          * If range includes less than 10 chars, assume we have not got enough
3803          * data, and make it include regular ASCII set.
3804          */
3805         if (rangehi - rangelo < 9)
3806         {
3807                 rangelo = ' ';
3808                 rangehi = 127;
3809         }
3810
3811         /*
3812          * Now strip any common prefix of the three strings.
3813          */
3814         while (*lobound)
3815         {
3816                 if (*lobound != *hibound || *lobound != *value)
3817                         break;
3818                 lobound++, hibound++, value++;
3819         }
3820
3821         /*
3822          * Now we can do the conversions.
3823          */
3824         *scaledvalue = convert_one_string_to_scalar(value, rangelo, rangehi);
3825         *scaledlobound = convert_one_string_to_scalar(lobound, rangelo, rangehi);
3826         *scaledhibound = convert_one_string_to_scalar(hibound, rangelo, rangehi);
3827 }
3828
3829 static double
3830 convert_one_string_to_scalar(char *value, int rangelo, int rangehi)
3831 {
3832         int                     slen = strlen(value);
3833         double          num,
3834                                 denom,
3835                                 base;
3836
3837         if (slen <= 0)
3838                 return 0.0;                             /* empty string has scalar value 0 */
3839
3840         /*
3841          * Since base is at least 10, need not consider more than about 20 chars
3842          */
3843         if (slen > 20)
3844                 slen = 20;
3845
3846         /* Convert initial characters to fraction */
3847         base = rangehi - rangelo + 1;
3848         num = 0.0;
3849         denom = base;
3850         while (slen-- > 0)
3851         {
3852                 int                     ch = (unsigned char) *value++;
3853
3854                 if (ch < rangelo)
3855                         ch = rangelo - 1;
3856                 else if (ch > rangehi)
3857                         ch = rangehi + 1;
3858                 num += ((double) (ch - rangelo)) / denom;
3859                 denom *= base;
3860         }
3861
3862         return num;
3863 }
3864
3865 /*
3866  * Convert a string-type Datum into a palloc'd, null-terminated string.
3867  *
3868  * When using a non-C locale, we must pass the string through strxfrm()
3869  * before continuing, so as to generate correct locale-specific results.
3870  */
3871 static char *
3872 convert_string_datum(Datum value, Oid typid)
3873 {
3874         char       *val;
3875
3876         switch (typid)
3877         {
3878                 case CHAROID:
3879                         val = (char *) palloc(2);
3880                         val[0] = DatumGetChar(value);
3881                         val[1] = '\0';
3882                         break;
3883                 case BPCHAROID:
3884                 case VARCHAROID:
3885                 case TEXTOID:
3886                         val = TextDatumGetCString(value);
3887                         break;
3888                 case NAMEOID:
3889                         {
3890                                 NameData   *nm = (NameData *) DatumGetPointer(value);
3891
3892                                 val = pstrdup(NameStr(*nm));
3893                                 break;
3894                         }
3895                 default:
3896
3897                         /*
3898                          * Can't get here unless someone tries to use scalarltsel on an
3899                          * operator with one string and one non-string operand.
3900                          */
3901                         elog(ERROR, "unsupported type: %u", typid);
3902                         return NULL;
3903         }
3904
3905         if (!lc_collate_is_c(DEFAULT_COLLATION_OID))
3906         {
3907                 char       *xfrmstr;
3908                 size_t          xfrmlen;
3909                 size_t xfrmlen2 PG_USED_FOR_ASSERTS_ONLY;
3910
3911                 /*
3912                  * Note: originally we guessed at a suitable output buffer size, and
3913                  * only needed to call strxfrm twice if our guess was too small.
3914                  * However, it seems that some versions of Solaris have buggy strxfrm
3915                  * that can write past the specified buffer length in that scenario.
3916                  * So, do it the dumb way for portability.
3917                  *
3918                  * Yet other systems (e.g., glibc) sometimes return a smaller value
3919                  * from the second call than the first; thus the Assert must be <= not
3920                  * == as you'd expect.  Can't any of these people program their way
3921                  * out of a paper bag?
3922                  *
3923                  * XXX: strxfrm doesn't support UTF-8 encoding on Win32, it can return
3924                  * bogus data or set an error. This is not really a problem unless it
3925                  * crashes since it will only give an estimation error and nothing
3926                  * fatal.
3927                  */
3928 #if _MSC_VER == 1400                    /* VS.Net 2005 */
3929
3930                 /*
3931                  *
3932                  * http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?
3933                  * FeedbackID=99694 */
3934                 {
3935                         char            x[1];
3936
3937                         xfrmlen = strxfrm(x, val, 0);
3938                 }
3939 #else
3940                 xfrmlen = strxfrm(NULL, val, 0);
3941 #endif
3942 #ifdef WIN32
3943
3944                 /*
3945                  * On Windows, strxfrm returns INT_MAX when an error occurs. Instead
3946                  * of trying to allocate this much memory (and fail), just return the
3947                  * original string unmodified as if we were in the C locale.
3948                  */
3949                 if (xfrmlen == INT_MAX)
3950                         return val;
3951 #endif
3952                 xfrmstr = (char *) palloc(xfrmlen + 1);
3953                 xfrmlen2 = strxfrm(xfrmstr, val, xfrmlen + 1);
3954                 Assert(xfrmlen2 <= xfrmlen);
3955                 pfree(val);
3956                 val = xfrmstr;
3957         }
3958
3959         return val;
3960 }
3961
3962 /*
3963  * Do convert_to_scalar()'s work for any bytea data type.
3964  *
3965  * Very similar to convert_string_to_scalar except we can't assume
3966  * null-termination and therefore pass explicit lengths around.
3967  *
3968  * Also, assumptions about likely "normal" ranges of characters have been
3969  * removed - a data range of 0..255 is always used, for now.  (Perhaps
3970  * someday we will add information about actual byte data range to
3971  * pg_statistic.)
3972  */
3973 static void
3974 convert_bytea_to_scalar(Datum value,
3975                                                 double *scaledvalue,
3976                                                 Datum lobound,
3977                                                 double *scaledlobound,
3978                                                 Datum hibound,
3979                                                 double *scaledhibound)
3980 {
3981         int                     rangelo,
3982                                 rangehi,
3983                                 valuelen = VARSIZE(DatumGetPointer(value)) - VARHDRSZ,
3984                                 loboundlen = VARSIZE(DatumGetPointer(lobound)) - VARHDRSZ,
3985                                 hiboundlen = VARSIZE(DatumGetPointer(hibound)) - VARHDRSZ,
3986                                 i,
3987                                 minlen;
3988         unsigned char *valstr = (unsigned char *) VARDATA(DatumGetPointer(value)),
3989                            *lostr = (unsigned char *) VARDATA(DatumGetPointer(lobound)),
3990                            *histr = (unsigned char *) VARDATA(DatumGetPointer(hibound));
3991
3992         /*
3993          * Assume bytea data is uniformly distributed across all byte values.
3994          */
3995         rangelo = 0;
3996         rangehi = 255;
3997
3998         /*
3999          * Now strip any common prefix of the three strings.
4000          */
4001         minlen = Min(Min(valuelen, loboundlen), hiboundlen);
4002         for (i = 0; i < minlen; i++)
4003         {
4004                 if (*lostr != *histr || *lostr != *valstr)
4005                         break;
4006                 lostr++, histr++, valstr++;
4007                 loboundlen--, hiboundlen--, valuelen--;
4008         }
4009
4010         /*
4011          * Now we can do the conversions.
4012          */
4013         *scaledvalue = convert_one_bytea_to_scalar(valstr, valuelen, rangelo, rangehi);
4014         *scaledlobound = convert_one_bytea_to_scalar(lostr, loboundlen, rangelo, rangehi);
4015         *scaledhibound = convert_one_bytea_to_scalar(histr, hiboundlen, rangelo, rangehi);
4016 }
4017
4018 static double
4019 convert_one_bytea_to_scalar(unsigned char *value, int valuelen,
4020                                                         int rangelo, int rangehi)
4021 {
4022         double          num,
4023                                 denom,
4024                                 base;
4025
4026         if (valuelen <= 0)
4027                 return 0.0;                             /* empty string has scalar value 0 */
4028
4029         /*
4030          * Since base is 256, need not consider more than about 10 chars (even
4031          * this many seems like overkill)
4032          */
4033         if (valuelen > 10)
4034                 valuelen = 10;
4035
4036         /* Convert initial characters to fraction */
4037         base = rangehi - rangelo + 1;
4038         num = 0.0;
4039         denom = base;
4040         while (valuelen-- > 0)
4041         {
4042                 int                     ch = *value++;
4043
4044                 if (ch < rangelo)
4045                         ch = rangelo - 1;
4046                 else if (ch > rangehi)
4047                         ch = rangehi + 1;
4048                 num += ((double) (ch - rangelo)) / denom;
4049                 denom *= base;
4050         }
4051
4052         return num;
4053 }
4054
4055 /*
4056  * Do convert_to_scalar()'s work for any timevalue data type.
4057  */
4058 static double
4059 convert_timevalue_to_scalar(Datum value, Oid typid)
4060 {
4061         switch (typid)
4062         {
4063                 case TIMESTAMPOID:
4064                         return DatumGetTimestamp(value);
4065                 case TIMESTAMPTZOID:
4066                         return DatumGetTimestampTz(value);
4067                 case ABSTIMEOID:
4068                         return DatumGetTimestamp(DirectFunctionCall1(abstime_timestamp,
4069                                                                                                                  value));
4070                 case DATEOID:
4071                         return date2timestamp_no_overflow(DatumGetDateADT(value));
4072                 case INTERVALOID:
4073                         {
4074                                 Interval   *interval = DatumGetIntervalP(value);
4075
4076                                 /*
4077                                  * Convert the month part of Interval to days using assumed
4078                                  * average month length of 365.25/12.0 days.  Not too
4079                                  * accurate, but plenty good enough for our purposes.
4080                                  */
4081 #ifdef HAVE_INT64_TIMESTAMP
4082                                 return interval->time + interval->day * (double) USECS_PER_DAY +
4083                                         interval->month * ((DAYS_PER_YEAR / (double) MONTHS_PER_YEAR) * USECS_PER_DAY);
4084 #else
4085                                 return interval->time + interval->day * SECS_PER_DAY +
4086                                         interval->month * ((DAYS_PER_YEAR / (double) MONTHS_PER_YEAR) * (double) SECS_PER_DAY);
4087 #endif
4088                         }
4089                 case RELTIMEOID:
4090 #ifdef HAVE_INT64_TIMESTAMP
4091                         return (DatumGetRelativeTime(value) * 1000000.0);
4092 #else
4093                         return DatumGetRelativeTime(value);
4094 #endif
4095                 case TINTERVALOID:
4096                         {
4097                                 TimeInterval tinterval = DatumGetTimeInterval(value);
4098
4099 #ifdef HAVE_INT64_TIMESTAMP
4100                                 if (tinterval->status != 0)
4101                                         return ((tinterval->data[1] - tinterval->data[0]) * 1000000.0);
4102 #else
4103                                 if (tinterval->status != 0)
4104                                         return tinterval->data[1] - tinterval->data[0];
4105 #endif
4106                                 return 0;               /* for lack of a better idea */
4107                         }
4108                 case TIMEOID:
4109                         return DatumGetTimeADT(value);
4110                 case TIMETZOID:
4111                         {
4112                                 TimeTzADT  *timetz = DatumGetTimeTzADTP(value);
4113
4114                                 /* use GMT-equivalent time */
4115 #ifdef HAVE_INT64_TIMESTAMP
4116                                 return (double) (timetz->time + (timetz->zone * 1000000.0));
4117 #else
4118                                 return (double) (timetz->time + timetz->zone);
4119 #endif
4120                         }
4121         }
4122
4123         /*
4124          * Can't get here unless someone tries to use scalarltsel/scalargtsel on
4125          * an operator with one timevalue and one non-timevalue operand.
4126          */
4127         elog(ERROR, "unsupported type: %u", typid);
4128         return 0;
4129 }
4130
4131
4132 /*
4133  * get_restriction_variable
4134  *              Examine the args of a restriction clause to see if it's of the
4135  *              form (variable op pseudoconstant) or (pseudoconstant op variable),
4136  *              where "variable" could be either a Var or an expression in vars of a
4137  *              single relation.  If so, extract information about the variable,
4138  *              and also indicate which side it was on and the other argument.
4139  *
4140  * Inputs:
4141  *      root: the planner info
4142  *      args: clause argument list
4143  *      varRelid: see specs for restriction selectivity functions
4144  *
4145  * Outputs: (these are valid only if TRUE is returned)
4146  *      *vardata: gets information about variable (see examine_variable)
4147  *      *other: gets other clause argument, aggressively reduced to a constant
4148  *      *varonleft: set TRUE if variable is on the left, FALSE if on the right
4149  *
4150  * Returns TRUE if a variable is identified, otherwise FALSE.
4151  *
4152  * Note: if there are Vars on both sides of the clause, we must fail, because
4153  * callers are expecting that the other side will act like a pseudoconstant.
4154  */
4155 bool
4156 get_restriction_variable(PlannerInfo *root, List *args, int varRelid,
4157                                                  VariableStatData *vardata, Node **other,
4158                                                  bool *varonleft)
4159 {
4160         Node       *left,
4161                            *right;
4162         VariableStatData rdata;
4163
4164         /* Fail if not a binary opclause (probably shouldn't happen) */
4165         if (list_length(args) != 2)
4166                 return false;
4167
4168         left = (Node *) linitial(args);
4169         right = (Node *) lsecond(args);
4170
4171         /*
4172          * Examine both sides.  Note that when varRelid is nonzero, Vars of other
4173          * relations will be treated as pseudoconstants.
4174          */
4175         examine_variable(root, left, varRelid, vardata);
4176         examine_variable(root, right, varRelid, &rdata);
4177
4178         /*
4179          * If one side is a variable and the other not, we win.
4180          */
4181         if (vardata->rel && rdata.rel == NULL)
4182         {
4183                 *varonleft = true;
4184                 *other = estimate_expression_value(root, rdata.var);
4185                 /* Assume we need no ReleaseVariableStats(rdata) here */
4186                 return true;
4187         }
4188
4189         if (vardata->rel == NULL && rdata.rel)
4190         {
4191                 *varonleft = false;
4192                 *other = estimate_expression_value(root, vardata->var);
4193                 /* Assume we need no ReleaseVariableStats(*vardata) here */
4194                 *vardata = rdata;
4195                 return true;
4196         }
4197
4198         /* Ooops, clause has wrong structure (probably var op var) */
4199         ReleaseVariableStats(*vardata);
4200         ReleaseVariableStats(rdata);
4201
4202         return false;
4203 }
4204
4205 /*
4206  * get_join_variables
4207  *              Apply examine_variable() to each side of a join clause.
4208  *              Also, attempt to identify whether the join clause has the same
4209  *              or reversed sense compared to the SpecialJoinInfo.
4210  *
4211  * We consider the join clause "normal" if it is "lhs_var OP rhs_var",
4212  * or "reversed" if it is "rhs_var OP lhs_var".  In complicated cases
4213  * where we can't tell for sure, we default to assuming it's normal.
4214  */
4215 void
4216 get_join_variables(PlannerInfo *root, List *args, SpecialJoinInfo *sjinfo,
4217                                    VariableStatData *vardata1, VariableStatData *vardata2,
4218                                    bool *join_is_reversed)
4219 {
4220         Node       *left,
4221                            *right;
4222
4223         if (list_length(args) != 2)
4224                 elog(ERROR, "join operator should take two arguments");
4225
4226         left = (Node *) linitial(args);
4227         right = (Node *) lsecond(args);
4228
4229         examine_variable(root, left, 0, vardata1);
4230         examine_variable(root, right, 0, vardata2);
4231
4232         if (vardata1->rel &&
4233                 bms_is_subset(vardata1->rel->relids, sjinfo->syn_righthand))
4234                 *join_is_reversed = true;               /* var1 is on RHS */
4235         else if (vardata2->rel &&
4236                          bms_is_subset(vardata2->rel->relids, sjinfo->syn_lefthand))
4237                 *join_is_reversed = true;               /* var2 is on LHS */
4238         else
4239                 *join_is_reversed = false;
4240 }
4241
4242 /*
4243  * examine_variable
4244  *              Try to look up statistical data about an expression.
4245  *              Fill in a VariableStatData struct to describe the expression.
4246  *
4247  * Inputs:
4248  *      root: the planner info
4249  *      node: the expression tree to examine
4250  *      varRelid: see specs for restriction selectivity functions
4251  *
4252  * Outputs: *vardata is filled as follows:
4253  *      var: the input expression (with any binary relabeling stripped, if
4254  *              it is or contains a variable; but otherwise the type is preserved)
4255  *      rel: RelOptInfo for relation containing variable; NULL if expression
4256  *              contains no Vars (NOTE this could point to a RelOptInfo of a
4257  *              subquery, not one in the current query).
4258  *      statsTuple: the pg_statistic entry for the variable, if one exists;
4259  *              otherwise NULL.
4260  *      freefunc: pointer to a function to release statsTuple with.
4261  *      vartype: exposed type of the expression; this should always match
4262  *              the declared input type of the operator we are estimating for.
4263  *      atttype, atttypmod: type data to pass to get_attstatsslot().  This is
4264  *              commonly the same as the exposed type of the variable argument,
4265  *              but can be different in binary-compatible-type cases.
4266  *      isunique: TRUE if we were able to match the var to a unique index or a
4267  *              single-column DISTINCT clause, implying its values are unique for
4268  *              this query.  (Caution: this should be trusted for statistical
4269  *              purposes only, since we do not check indimmediate nor verify that
4270  *              the exact same definition of equality applies.)
4271  *
4272  * Caller is responsible for doing ReleaseVariableStats() before exiting.
4273  */
4274 void
4275 examine_variable(PlannerInfo *root, Node *node, int varRelid,
4276                                  VariableStatData *vardata)
4277 {
4278         Node       *basenode;
4279         Relids          varnos;
4280         RelOptInfo *onerel;
4281
4282         /* Make sure we don't return dangling pointers in vardata */
4283         MemSet(vardata, 0, sizeof(VariableStatData));
4284
4285         /* Save the exposed type of the expression */
4286         vardata->vartype = exprType(node);
4287
4288         /* Look inside any binary-compatible relabeling */
4289
4290         if (IsA(node, RelabelType))
4291                 basenode = (Node *) ((RelabelType *) node)->arg;
4292         else
4293                 basenode = node;
4294
4295         /* Fast path for a simple Var */
4296
4297         if (IsA(basenode, Var) &&
4298                 (varRelid == 0 || varRelid == ((Var *) basenode)->varno))
4299         {
4300                 Var                *var = (Var *) basenode;
4301
4302                 /* Set up result fields other than the stats tuple */
4303                 vardata->var = basenode;        /* return Var without relabeling */
4304                 vardata->rel = find_base_rel(root, var->varno);
4305                 vardata->atttype = var->vartype;
4306                 vardata->atttypmod = var->vartypmod;
4307                 vardata->isunique = has_unique_index(vardata->rel, var->varattno);
4308
4309                 /* Try to locate some stats */
4310                 examine_simple_variable(root, var, vardata);
4311
4312                 return;
4313         }
4314
4315         /*
4316          * Okay, it's a more complicated expression.  Determine variable
4317          * membership.  Note that when varRelid isn't zero, only vars of that
4318          * relation are considered "real" vars.
4319          */
4320         varnos = pull_varnos(basenode);
4321
4322         onerel = NULL;
4323
4324         switch (bms_membership(varnos))
4325         {
4326                 case BMS_EMPTY_SET:
4327                         /* No Vars at all ... must be pseudo-constant clause */
4328                         break;
4329                 case BMS_SINGLETON:
4330                         if (varRelid == 0 || bms_is_member(varRelid, varnos))
4331                         {
4332                                 onerel = find_base_rel(root,
4333                                            (varRelid ? varRelid : bms_singleton_member(varnos)));
4334                                 vardata->rel = onerel;
4335                                 node = basenode;        /* strip any relabeling */
4336                         }
4337                         /* else treat it as a constant */
4338                         break;
4339                 case BMS_MULTIPLE:
4340                         if (varRelid == 0)
4341                         {
4342                                 /* treat it as a variable of a join relation */
4343                                 vardata->rel = find_join_rel(root, varnos);
4344                                 node = basenode;        /* strip any relabeling */
4345                         }
4346                         else if (bms_is_member(varRelid, varnos))
4347                         {
4348                                 /* ignore the vars belonging to other relations */
4349                                 vardata->rel = find_base_rel(root, varRelid);
4350                                 node = basenode;        /* strip any relabeling */
4351                                 /* note: no point in expressional-index search here */
4352                         }
4353                         /* else treat it as a constant */
4354                         break;
4355         }
4356
4357         bms_free(varnos);
4358
4359         vardata->var = node;
4360         vardata->atttype = exprType(node);
4361         vardata->atttypmod = exprTypmod(node);
4362
4363         if (onerel)
4364         {
4365                 /*
4366                  * We have an expression in vars of a single relation.  Try to match
4367                  * it to expressional index columns, in hopes of finding some
4368                  * statistics.
4369                  *
4370                  * XXX it's conceivable that there are multiple matches with different
4371                  * index opfamilies; if so, we need to pick one that matches the
4372                  * operator we are estimating for.      FIXME later.
4373                  */
4374                 ListCell   *ilist;
4375
4376                 foreach(ilist, onerel->indexlist)
4377                 {
4378                         IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
4379                         ListCell   *indexpr_item;
4380                         int                     pos;
4381
4382                         indexpr_item = list_head(index->indexprs);
4383                         if (indexpr_item == NULL)
4384                                 continue;               /* no expressions here... */
4385
4386                         for (pos = 0; pos < index->ncolumns; pos++)
4387                         {
4388                                 if (index->indexkeys[pos] == 0)
4389                                 {
4390                                         Node       *indexkey;
4391
4392                                         if (indexpr_item == NULL)
4393                                                 elog(ERROR, "too few entries in indexprs list");
4394                                         indexkey = (Node *) lfirst(indexpr_item);
4395                                         if (indexkey && IsA(indexkey, RelabelType))
4396                                                 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4397                                         if (equal(node, indexkey))
4398                                         {
4399                                                 /*
4400                                                  * Found a match ... is it a unique index? Tests here
4401                                                  * should match has_unique_index().
4402                                                  */
4403                                                 if (index->unique &&
4404                                                         index->ncolumns == 1 &&
4405                                                         (index->indpred == NIL || index->predOK))
4406                                                         vardata->isunique = true;
4407
4408                                                 /*
4409                                                  * Has it got stats?  We only consider stats for
4410                                                  * non-partial indexes, since partial indexes probably
4411                                                  * don't reflect whole-relation statistics; the above
4412                                                  * check for uniqueness is the only info we take from
4413                                                  * a partial index.
4414                                                  *
4415                                                  * An index stats hook, however, must make its own
4416                                                  * decisions about what to do with partial indexes.
4417                                                  */
4418                                                 if (get_index_stats_hook &&
4419                                                         (*get_index_stats_hook) (root, index->indexoid,
4420                                                                                                          pos + 1, vardata))
4421                                                 {
4422                                                         /*
4423                                                          * The hook took control of acquiring a stats
4424                                                          * tuple.  If it did supply a tuple, it'd better
4425                                                          * have supplied a freefunc.
4426                                                          */
4427                                                         if (HeapTupleIsValid(vardata->statsTuple) &&
4428                                                                 !vardata->freefunc)
4429                                                                 elog(ERROR, "no function provided to release variable stats with");
4430                                                 }
4431                                                 else if (index->indpred == NIL)
4432                                                 {
4433                                                         vardata->statsTuple =
4434                                                                 SearchSysCache3(STATRELATTINH,
4435                                                                                    ObjectIdGetDatum(index->indexoid),
4436                                                                                                 Int16GetDatum(pos + 1),
4437                                                                                                 BoolGetDatum(false));
4438                                                         vardata->freefunc = ReleaseSysCache;
4439                                                 }
4440                                                 if (vardata->statsTuple)
4441                                                         break;
4442                                         }
4443                                         indexpr_item = lnext(indexpr_item);
4444                                 }
4445                         }
4446                         if (vardata->statsTuple)
4447                                 break;
4448                 }
4449         }
4450 }
4451
4452 /*
4453  * examine_simple_variable
4454  *              Handle a simple Var for examine_variable
4455  *
4456  * This is split out as a subroutine so that we can recurse to deal with
4457  * Vars referencing subqueries.
4458  *
4459  * We already filled in all the fields of *vardata except for the stats tuple.
4460  */
4461 static void
4462 examine_simple_variable(PlannerInfo *root, Var *var,
4463                                                 VariableStatData *vardata)
4464 {
4465         RangeTblEntry *rte = root->simple_rte_array[var->varno];
4466
4467         Assert(IsA(rte, RangeTblEntry));
4468
4469         if (get_relation_stats_hook &&
4470                 (*get_relation_stats_hook) (root, rte, var->varattno, vardata))
4471         {
4472                 /*
4473                  * The hook took control of acquiring a stats tuple.  If it did supply
4474                  * a tuple, it'd better have supplied a freefunc.
4475                  */
4476                 if (HeapTupleIsValid(vardata->statsTuple) &&
4477                         !vardata->freefunc)
4478                         elog(ERROR, "no function provided to release variable stats with");
4479         }
4480         else if (rte->rtekind == RTE_RELATION)
4481         {
4482                 /*
4483                  * Plain table or parent of an inheritance appendrel, so look up the
4484                  * column in pg_statistic
4485                  */
4486                 vardata->statsTuple = SearchSysCache3(STATRELATTINH,
4487                                                                                           ObjectIdGetDatum(rte->relid),
4488                                                                                           Int16GetDatum(var->varattno),
4489                                                                                           BoolGetDatum(rte->inh));
4490                 vardata->freefunc = ReleaseSysCache;
4491         }
4492         else if (rte->rtekind == RTE_SUBQUERY && !rte->inh)
4493         {
4494                 /*
4495                  * Plain subquery (not one that was converted to an appendrel).
4496                  */
4497                 Query      *subquery = rte->subquery;
4498                 RelOptInfo *rel;
4499                 TargetEntry *ste;
4500
4501                 /*
4502                  * Punt if subquery uses set operations or GROUP BY, as these will
4503                  * mash underlying columns' stats beyond recognition.  (Set ops are
4504                  * particularly nasty; if we forged ahead, we would return stats
4505                  * relevant to only the leftmost subselect...)  DISTINCT is also
4506                  * problematic, but we check that later because there is a possibility
4507                  * of learning something even with it.
4508                  */
4509                 if (subquery->setOperations ||
4510                         subquery->groupClause)
4511                         return;
4512
4513                 /*
4514                  * OK, fetch RelOptInfo for subquery.  Note that we don't change the
4515                  * rel returned in vardata, since caller expects it to be a rel of the
4516                  * caller's query level.  Because we might already be recursing, we
4517                  * can't use that rel pointer either, but have to look up the Var's
4518                  * rel afresh.
4519                  */
4520                 rel = find_base_rel(root, var->varno);
4521
4522                 /* If the subquery hasn't been planned yet, we have to punt */
4523                 if (rel->subroot == NULL)
4524                         return;
4525                 Assert(IsA(rel->subroot, PlannerInfo));
4526
4527                 /*
4528                  * Switch our attention to the subquery as mangled by the planner. It
4529                  * was okay to look at the pre-planning version for the tests above,
4530                  * but now we need a Var that will refer to the subroot's live
4531                  * RelOptInfos.  For instance, if any subquery pullup happened during
4532                  * planning, Vars in the targetlist might have gotten replaced, and we
4533                  * need to see the replacement expressions.
4534                  */
4535                 subquery = rel->subroot->parse;
4536                 Assert(IsA(subquery, Query));
4537
4538                 /* Get the subquery output expression referenced by the upper Var */
4539                 ste = get_tle_by_resno(subquery->targetList, var->varattno);
4540                 if (ste == NULL || ste->resjunk)
4541                         elog(ERROR, "subquery %s does not have attribute %d",
4542                                  rte->eref->aliasname, var->varattno);
4543                 var = (Var *) ste->expr;
4544
4545                 /*
4546                  * If subquery uses DISTINCT, we can't make use of any stats for the
4547                  * variable ... but, if it's the only DISTINCT column, we are entitled
4548                  * to consider it unique.  We do the test this way so that it works
4549                  * for cases involving DISTINCT ON.
4550                  */
4551                 if (subquery->distinctClause)
4552                 {
4553                         if (list_length(subquery->distinctClause) == 1 &&
4554                                 targetIsInSortList(ste, InvalidOid, subquery->distinctClause))
4555                                 vardata->isunique = true;
4556                         /* cannot go further */
4557                         return;
4558                 }
4559
4560                 /*
4561                  * If the sub-query originated from a view with the security_barrier
4562                  * attribute, we must not look at the variable's statistics, though it
4563                  * seems all right to notice the existence of a DISTINCT clause. So
4564                  * stop here.
4565                  *
4566                  * This is probably a harsher restriction than necessary; it's
4567                  * certainly OK for the selectivity estimator (which is a C function,
4568                  * and therefore omnipotent anyway) to look at the statistics.  But
4569                  * many selectivity estimators will happily *invoke the operator
4570                  * function* to try to work out a good estimate - and that's not OK.
4571                  * So for now, don't dig down for stats.
4572                  */
4573                 if (rte->security_barrier)
4574                         return;
4575
4576                 /* Can only handle a simple Var of subquery's query level */
4577                 if (var && IsA(var, Var) &&
4578                         var->varlevelsup == 0)
4579                 {
4580                         /*
4581                          * OK, recurse into the subquery.  Note that the original setting
4582                          * of vardata->isunique (which will surely be false) is left
4583                          * unchanged in this situation.  That's what we want, since even
4584                          * if the underlying column is unique, the subquery may have
4585                          * joined to other tables in a way that creates duplicates.
4586                          */
4587                         examine_simple_variable(rel->subroot, var, vardata);
4588                 }
4589         }
4590         else
4591         {
4592                 /*
4593                  * Otherwise, the Var comes from a FUNCTION, VALUES, or CTE RTE.  (We
4594                  * won't see RTE_JOIN here because join alias Vars have already been
4595                  * flattened.)  There's not much we can do with function outputs, but
4596                  * maybe someday try to be smarter about VALUES and/or CTEs.
4597                  */
4598         }
4599 }
4600
4601 /*
4602  * get_variable_numdistinct
4603  *        Estimate the number of distinct values of a variable.
4604  *
4605  * vardata: results of examine_variable
4606  * *isdefault: set to TRUE if the result is a default rather than based on
4607  * anything meaningful.
4608  *
4609  * NB: be careful to produce an integral result, since callers may compare
4610  * the result to exact integer counts.
4611  */
4612 double
4613 get_variable_numdistinct(VariableStatData *vardata, bool *isdefault)
4614 {
4615         double          stadistinct;
4616         double          ntuples;
4617
4618         *isdefault = false;
4619
4620         /*
4621          * Determine the stadistinct value to use.      There are cases where we can
4622          * get an estimate even without a pg_statistic entry, or can get a better
4623          * value than is in pg_statistic.
4624          */
4625         if (HeapTupleIsValid(vardata->statsTuple))
4626         {
4627                 /* Use the pg_statistic entry */
4628                 Form_pg_statistic stats;
4629
4630                 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
4631                 stadistinct = stats->stadistinct;
4632         }
4633         else if (vardata->vartype == BOOLOID)
4634         {
4635                 /*
4636                  * Special-case boolean columns: presumably, two distinct values.
4637                  *
4638                  * Are there any other datatypes we should wire in special estimates
4639                  * for?
4640                  */
4641                 stadistinct = 2.0;
4642         }
4643         else
4644         {
4645                 /*
4646                  * We don't keep statistics for system columns, but in some cases we
4647                  * can infer distinctness anyway.
4648                  */
4649                 if (vardata->var && IsA(vardata->var, Var))
4650                 {
4651                         switch (((Var *) vardata->var)->varattno)
4652                         {
4653                                 case ObjectIdAttributeNumber:
4654                                 case SelfItemPointerAttributeNumber:
4655                                         stadistinct = -1.0; /* unique */
4656                                         break;
4657                                 case TableOidAttributeNumber:
4658                                         stadistinct = 1.0;      /* only 1 value */
4659                                         break;
4660                                 default:
4661                                         stadistinct = 0.0;      /* means "unknown" */
4662                                         break;
4663                         }
4664                 }
4665                 else
4666                         stadistinct = 0.0;      /* means "unknown" */
4667
4668                 /*
4669                  * XXX consider using estimate_num_groups on expressions?
4670                  */
4671         }
4672
4673         /*
4674          * If there is a unique index or DISTINCT clause for the variable, assume
4675          * it is unique no matter what pg_statistic says; the statistics could be
4676          * out of date, or we might have found a partial unique index that proves
4677          * the var is unique for this query.
4678          */
4679         if (vardata->isunique)
4680                 stadistinct = -1.0;
4681
4682         /*
4683          * If we had an absolute estimate, use that.
4684          */
4685         if (stadistinct > 0.0)
4686                 return stadistinct;
4687
4688         /*
4689          * Otherwise we need to get the relation size; punt if not available.
4690          */
4691         if (vardata->rel == NULL)
4692         {
4693                 *isdefault = true;
4694                 return DEFAULT_NUM_DISTINCT;
4695         }
4696         ntuples = vardata->rel->tuples;
4697         if (ntuples <= 0.0)
4698         {
4699                 *isdefault = true;
4700                 return DEFAULT_NUM_DISTINCT;
4701         }
4702
4703         /*
4704          * If we had a relative estimate, use that.
4705          */
4706         if (stadistinct < 0.0)
4707                 return floor((-stadistinct * ntuples) + 0.5);
4708
4709         /*
4710          * With no data, estimate ndistinct = ntuples if the table is small, else
4711          * use default.  We use DEFAULT_NUM_DISTINCT as the cutoff for "small" so
4712          * that the behavior isn't discontinuous.
4713          */
4714         if (ntuples < DEFAULT_NUM_DISTINCT)
4715                 return ntuples;
4716
4717         *isdefault = true;
4718         return DEFAULT_NUM_DISTINCT;
4719 }
4720
4721 /*
4722  * get_variable_range
4723  *              Estimate the minimum and maximum value of the specified variable.
4724  *              If successful, store values in *min and *max, and return TRUE.
4725  *              If no data available, return FALSE.
4726  *
4727  * sortop is the "<" comparison operator to use.  This should generally
4728  * be "<" not ">", as only the former is likely to be found in pg_statistic.
4729  */
4730 static bool
4731 get_variable_range(PlannerInfo *root, VariableStatData *vardata, Oid sortop,
4732                                    Datum *min, Datum *max)
4733 {
4734         Datum           tmin = 0;
4735         Datum           tmax = 0;
4736         bool            have_data = false;
4737         int16           typLen;
4738         bool            typByVal;
4739         Datum      *values;
4740         int                     nvalues;
4741         int                     i;
4742
4743         /*
4744          * XXX It's very tempting to try to use the actual column min and max, if
4745          * we can get them relatively-cheaply with an index probe.      However, since
4746          * this function is called many times during join planning, that could
4747          * have unpleasant effects on planning speed.  Need more investigation
4748          * before enabling this.
4749          */
4750 #ifdef NOT_USED
4751         if (get_actual_variable_range(root, vardata, sortop, min, max))
4752                 return true;
4753 #endif
4754
4755         if (!HeapTupleIsValid(vardata->statsTuple))
4756         {
4757                 /* no stats available, so default result */
4758                 return false;
4759         }
4760
4761         get_typlenbyval(vardata->atttype, &typLen, &typByVal);
4762
4763         /*
4764          * If there is a histogram, grab the first and last values.
4765          *
4766          * If there is a histogram that is sorted with some other operator than
4767          * the one we want, fail --- this suggests that there is data we can't
4768          * use.
4769          */
4770         if (get_attstatsslot(vardata->statsTuple,
4771                                                  vardata->atttype, vardata->atttypmod,
4772                                                  STATISTIC_KIND_HISTOGRAM, sortop,
4773                                                  NULL,
4774                                                  &values, &nvalues,
4775                                                  NULL, NULL))
4776         {
4777                 if (nvalues > 0)
4778                 {
4779                         tmin = datumCopy(values[0], typByVal, typLen);
4780                         tmax = datumCopy(values[nvalues - 1], typByVal, typLen);
4781                         have_data = true;
4782                 }
4783                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
4784         }
4785         else if (get_attstatsslot(vardata->statsTuple,
4786                                                           vardata->atttype, vardata->atttypmod,
4787                                                           STATISTIC_KIND_HISTOGRAM, InvalidOid,
4788                                                           NULL,
4789                                                           &values, &nvalues,
4790                                                           NULL, NULL))
4791         {
4792                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
4793                 return false;
4794         }
4795
4796         /*
4797          * If we have most-common-values info, look for extreme MCVs.  This is
4798          * needed even if we also have a histogram, since the histogram excludes
4799          * the MCVs.  However, usually the MCVs will not be the extreme values, so
4800          * avoid unnecessary data copying.
4801          */
4802         if (get_attstatsslot(vardata->statsTuple,
4803                                                  vardata->atttype, vardata->atttypmod,
4804                                                  STATISTIC_KIND_MCV, InvalidOid,
4805                                                  NULL,
4806                                                  &values, &nvalues,
4807                                                  NULL, NULL))
4808         {
4809                 bool            tmin_is_mcv = false;
4810                 bool            tmax_is_mcv = false;
4811                 FmgrInfo        opproc;
4812
4813                 fmgr_info(get_opcode(sortop), &opproc);
4814
4815                 for (i = 0; i < nvalues; i++)
4816                 {
4817                         if (!have_data)
4818                         {
4819                                 tmin = tmax = values[i];
4820                                 tmin_is_mcv = tmax_is_mcv = have_data = true;
4821                                 continue;
4822                         }
4823                         if (DatumGetBool(FunctionCall2Coll(&opproc,
4824                                                                                            DEFAULT_COLLATION_OID,
4825                                                                                            values[i], tmin)))
4826                         {
4827                                 tmin = values[i];
4828                                 tmin_is_mcv = true;
4829                         }
4830                         if (DatumGetBool(FunctionCall2Coll(&opproc,
4831                                                                                            DEFAULT_COLLATION_OID,
4832                                                                                            tmax, values[i])))
4833                         {
4834                                 tmax = values[i];
4835                                 tmax_is_mcv = true;
4836                         }
4837                 }
4838                 if (tmin_is_mcv)
4839                         tmin = datumCopy(tmin, typByVal, typLen);
4840                 if (tmax_is_mcv)
4841                         tmax = datumCopy(tmax, typByVal, typLen);
4842                 free_attstatsslot(vardata->atttype, values, nvalues, NULL, 0);
4843         }
4844
4845         *min = tmin;
4846         *max = tmax;
4847         return have_data;
4848 }
4849
4850
4851 /*
4852  * get_actual_variable_range
4853  *              Attempt to identify the current *actual* minimum and/or maximum
4854  *              of the specified variable, by looking for a suitable btree index
4855  *              and fetching its low and/or high values.
4856  *              If successful, store values in *min and *max, and return TRUE.
4857  *              (Either pointer can be NULL if that endpoint isn't needed.)
4858  *              If no data available, return FALSE.
4859  *
4860  * sortop is the "<" comparison operator to use.
4861  */
4862 static bool
4863 get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
4864                                                   Oid sortop,
4865                                                   Datum *min, Datum *max)
4866 {
4867         bool            have_data = false;
4868         RelOptInfo *rel = vardata->rel;
4869         RangeTblEntry *rte;
4870         ListCell   *lc;
4871
4872         /* No hope if no relation or it doesn't have indexes */
4873         if (rel == NULL || rel->indexlist == NIL)
4874                 return false;
4875         /* If it has indexes it must be a plain relation */
4876         rte = root->simple_rte_array[rel->relid];
4877         Assert(rte->rtekind == RTE_RELATION);
4878
4879         /* Search through the indexes to see if any match our problem */
4880         foreach(lc, rel->indexlist)
4881         {
4882                 IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
4883                 ScanDirection indexscandir;
4884
4885                 /* Ignore non-btree indexes */
4886                 if (index->relam != BTREE_AM_OID)
4887                         continue;
4888
4889                 /*
4890                  * Ignore partial indexes --- we only want stats that cover the entire
4891                  * relation.
4892                  */
4893                 if (index->indpred != NIL)
4894                         continue;
4895
4896                 /*
4897                  * The index list might include hypothetical indexes inserted by a
4898                  * get_relation_info hook --- don't try to access them.
4899                  */
4900                 if (index->hypothetical)
4901                         continue;
4902
4903                 /*
4904                  * The first index column must match the desired variable and sort
4905                  * operator --- but we can use a descending-order index.
4906                  */
4907                 if (!match_index_to_operand(vardata->var, 0, index))
4908                         continue;
4909                 switch (get_op_opfamily_strategy(sortop, index->sortopfamily[0]))
4910                 {
4911                         case BTLessStrategyNumber:
4912                                 if (index->reverse_sort[0])
4913                                         indexscandir = BackwardScanDirection;
4914                                 else
4915                                         indexscandir = ForwardScanDirection;
4916                                 break;
4917                         case BTGreaterStrategyNumber:
4918                                 if (index->reverse_sort[0])
4919                                         indexscandir = ForwardScanDirection;
4920                                 else
4921                                         indexscandir = BackwardScanDirection;
4922                                 break;
4923                         default:
4924                                 /* index doesn't match the sortop */
4925                                 continue;
4926                 }
4927
4928                 /*
4929                  * Found a suitable index to extract data from.  We'll need an EState
4930                  * and a bunch of other infrastructure.
4931                  */
4932                 {
4933                         EState     *estate;
4934                         ExprContext *econtext;
4935                         MemoryContext tmpcontext;
4936                         MemoryContext oldcontext;
4937                         Relation        heapRel;
4938                         Relation        indexRel;
4939                         IndexInfo  *indexInfo;
4940                         TupleTableSlot *slot;
4941                         int16           typLen;
4942                         bool            typByVal;
4943                         ScanKeyData scankeys[1];
4944                         IndexScanDesc index_scan;
4945                         HeapTuple       tup;
4946                         Datum           values[INDEX_MAX_KEYS];
4947                         bool            isnull[INDEX_MAX_KEYS];
4948
4949                         estate = CreateExecutorState();
4950                         econtext = GetPerTupleExprContext(estate);
4951                         /* Make sure any cruft is generated in the econtext's memory */
4952                         tmpcontext = econtext->ecxt_per_tuple_memory;
4953                         oldcontext = MemoryContextSwitchTo(tmpcontext);
4954
4955                         /*
4956                          * Open the table and index so we can read from them.  We should
4957                          * already have at least AccessShareLock on the table, but not
4958                          * necessarily on the index.
4959                          */
4960                         heapRel = heap_open(rte->relid, NoLock);
4961                         indexRel = index_open(index->indexoid, AccessShareLock);
4962
4963                         /* extract index key information from the index's pg_index info */
4964                         indexInfo = BuildIndexInfo(indexRel);
4965
4966                         /* some other stuff */
4967                         slot = MakeSingleTupleTableSlot(RelationGetDescr(heapRel));
4968                         econtext->ecxt_scantuple = slot;
4969                         get_typlenbyval(vardata->atttype, &typLen, &typByVal);
4970
4971                         /* set up an IS NOT NULL scan key so that we ignore nulls */
4972                         ScanKeyEntryInitialize(&scankeys[0],
4973                                                                    SK_ISNULL | SK_SEARCHNOTNULL,
4974                                                                    1,   /* index col to scan */
4975                                                                    InvalidStrategy,             /* no strategy */
4976                                                                    InvalidOid,  /* no strategy subtype */
4977                                                                    InvalidOid,  /* no collation */
4978                                                                    InvalidOid,  /* no reg proc for this */
4979                                                                    (Datum) 0);  /* constant */
4980
4981                         have_data = true;
4982
4983                         /* If min is requested ... */
4984                         if (min)
4985                         {
4986                                 index_scan = index_beginscan(heapRel, indexRel, SnapshotNow,
4987                                                                                          1, 0);
4988                                 index_rescan(index_scan, scankeys, 1, NULL, 0);
4989
4990                                 /* Fetch first tuple in sortop's direction */
4991                                 if ((tup = index_getnext(index_scan,
4992                                                                                  indexscandir)) != NULL)
4993                                 {
4994                                         /* Extract the index column values from the heap tuple */
4995                                         ExecStoreTuple(tup, slot, InvalidBuffer, false);
4996                                         FormIndexDatum(indexInfo, slot, estate,
4997                                                                    values, isnull);
4998
4999                                         /* Shouldn't have got a null, but be careful */
5000                                         if (isnull[0])
5001                                                 elog(ERROR, "found unexpected null value in index \"%s\"",
5002                                                          RelationGetRelationName(indexRel));
5003
5004                                         /* Copy the index column value out to caller's context */
5005                                         MemoryContextSwitchTo(oldcontext);
5006                                         *min = datumCopy(values[0], typByVal, typLen);
5007                                         MemoryContextSwitchTo(tmpcontext);
5008                                 }
5009                                 else
5010                                         have_data = false;
5011
5012                                 index_endscan(index_scan);
5013                         }
5014
5015                         /* If max is requested, and we didn't find the index is empty */
5016                         if (max && have_data)
5017                         {
5018                                 index_scan = index_beginscan(heapRel, indexRel, SnapshotNow,
5019                                                                                          1, 0);
5020                                 index_rescan(index_scan, scankeys, 1, NULL, 0);
5021
5022                                 /* Fetch first tuple in reverse direction */
5023                                 if ((tup = index_getnext(index_scan,
5024                                                                                  -indexscandir)) != NULL)
5025                                 {
5026                                         /* Extract the index column values from the heap tuple */
5027                                         ExecStoreTuple(tup, slot, InvalidBuffer, false);
5028                                         FormIndexDatum(indexInfo, slot, estate,
5029                                                                    values, isnull);
5030
5031                                         /* Shouldn't have got a null, but be careful */
5032                                         if (isnull[0])
5033                                                 elog(ERROR, "found unexpected null value in index \"%s\"",
5034                                                          RelationGetRelationName(indexRel));
5035
5036                                         /* Copy the index column value out to caller's context */
5037                                         MemoryContextSwitchTo(oldcontext);
5038                                         *max = datumCopy(values[0], typByVal, typLen);
5039                                         MemoryContextSwitchTo(tmpcontext);
5040                                 }
5041                                 else
5042                                         have_data = false;
5043
5044                                 index_endscan(index_scan);
5045                         }
5046
5047                         /* Clean everything up */
5048                         ExecDropSingleTupleTableSlot(slot);
5049
5050                         index_close(indexRel, AccessShareLock);
5051                         heap_close(heapRel, NoLock);
5052
5053                         MemoryContextSwitchTo(oldcontext);
5054                         FreeExecutorState(estate);
5055
5056                         /* And we're done */
5057                         break;
5058                 }
5059         }
5060
5061         return have_data;
5062 }
5063
5064 /*
5065  * find_join_input_rel
5066  *              Look up the input relation for a join.
5067  *
5068  * We assume that the input relation's RelOptInfo must have been constructed
5069  * already.
5070  */
5071 static RelOptInfo *
5072 find_join_input_rel(PlannerInfo *root, Relids relids)
5073 {
5074         RelOptInfo *rel = NULL;
5075
5076         switch (bms_membership(relids))
5077         {
5078                 case BMS_EMPTY_SET:
5079                         /* should not happen */
5080                         break;
5081                 case BMS_SINGLETON:
5082                         rel = find_base_rel(root, bms_singleton_member(relids));
5083                         break;
5084                 case BMS_MULTIPLE:
5085                         rel = find_join_rel(root, relids);
5086                         break;
5087         }
5088
5089         if (rel == NULL)
5090                 elog(ERROR, "could not find RelOptInfo for given relids");
5091
5092         return rel;
5093 }
5094
5095
5096 /*-------------------------------------------------------------------------
5097  *
5098  * Pattern analysis functions
5099  *
5100  * These routines support analysis of LIKE and regular-expression patterns
5101  * by the planner/optimizer.  It's important that they agree with the
5102  * regular-expression code in backend/regex/ and the LIKE code in
5103  * backend/utils/adt/like.c.  Also, the computation of the fixed prefix
5104  * must be conservative: if we report a string longer than the true fixed
5105  * prefix, the query may produce actually wrong answers, rather than just
5106  * getting a bad selectivity estimate!
5107  *
5108  * Note that the prefix-analysis functions are called from
5109  * backend/optimizer/path/indxpath.c as well as from routines in this file.
5110  *
5111  *-------------------------------------------------------------------------
5112  */
5113
5114 /*
5115  * Check whether char is a letter (and, hence, subject to case-folding)
5116  *
5117  * In multibyte character sets, we can't use isalpha, and it does not seem
5118  * worth trying to convert to wchar_t to use iswalpha.  Instead, just assume
5119  * any multibyte char is potentially case-varying.
5120  */
5121 static int
5122 pattern_char_isalpha(char c, bool is_multibyte,
5123                                          pg_locale_t locale, bool locale_is_c)
5124 {
5125         if (locale_is_c)
5126                 return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
5127         else if (is_multibyte && IS_HIGHBIT_SET(c))
5128                 return true;
5129 #ifdef HAVE_LOCALE_T
5130         else if (locale)
5131                 return isalpha_l((unsigned char) c, locale);
5132 #endif
5133         else
5134                 return isalpha((unsigned char) c);
5135 }
5136
5137 /*
5138  * Extract the fixed prefix, if any, for a pattern.
5139  *
5140  * *prefix is set to a palloc'd prefix string (in the form of a Const node),
5141  *      or to NULL if no fixed prefix exists for the pattern.
5142  * If rest_selec is not NULL, *rest_selec is set to an estimate of the
5143  *      selectivity of the remainder of the pattern (without any fixed prefix).
5144  * The prefix Const has the same type (TEXT or BYTEA) as the input pattern.
5145  *
5146  * The return value distinguishes no fixed prefix, a partial prefix,
5147  * or an exact-match-only pattern.
5148  */
5149
5150 static Pattern_Prefix_Status
5151 like_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
5152                                   Const **prefix_const, Selectivity *rest_selec)
5153 {
5154         char       *match;
5155         char       *patt;
5156         int                     pattlen;
5157         Oid                     typeid = patt_const->consttype;
5158         int                     pos,
5159                                 match_pos;
5160         bool            is_multibyte = (pg_database_encoding_max_length() > 1);
5161         pg_locale_t locale = 0;
5162         bool            locale_is_c = false;
5163
5164         /* the right-hand const is type text or bytea */
5165         Assert(typeid == BYTEAOID || typeid == TEXTOID);
5166
5167         if (case_insensitive)
5168         {
5169                 if (typeid == BYTEAOID)
5170                         ereport(ERROR,
5171                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5172                         errmsg("case insensitive matching not supported on type bytea")));
5173
5174                 /* If case-insensitive, we need locale info */
5175                 if (lc_ctype_is_c(collation))
5176                         locale_is_c = true;
5177                 else if (collation != DEFAULT_COLLATION_OID)
5178                 {
5179                         if (!OidIsValid(collation))
5180                         {
5181                                 /*
5182                                  * This typically means that the parser could not resolve a
5183                                  * conflict of implicit collations, so report it that way.
5184                                  */
5185                                 ereport(ERROR,
5186                                                 (errcode(ERRCODE_INDETERMINATE_COLLATION),
5187                                                  errmsg("could not determine which collation to use for ILIKE"),
5188                                                  errhint("Use the COLLATE clause to set the collation explicitly.")));
5189                         }
5190                         locale = pg_newlocale_from_collation(collation);
5191                 }
5192         }
5193
5194         if (typeid != BYTEAOID)
5195         {
5196                 patt = TextDatumGetCString(patt_const->constvalue);
5197                 pattlen = strlen(patt);
5198         }
5199         else
5200         {
5201                 bytea      *bstr = DatumGetByteaP(patt_const->constvalue);
5202
5203                 pattlen = VARSIZE(bstr) - VARHDRSZ;
5204                 patt = (char *) palloc(pattlen);
5205                 memcpy(patt, VARDATA(bstr), pattlen);
5206                 if ((Pointer) bstr != DatumGetPointer(patt_const->constvalue))
5207                         pfree(bstr);
5208         }
5209
5210         match = palloc(pattlen + 1);
5211         match_pos = 0;
5212         for (pos = 0; pos < pattlen; pos++)
5213         {
5214                 /* % and _ are wildcard characters in LIKE */
5215                 if (patt[pos] == '%' ||
5216                         patt[pos] == '_')
5217                         break;
5218
5219                 /* Backslash escapes the next character */
5220                 if (patt[pos] == '\\')
5221                 {
5222                         pos++;
5223                         if (pos >= pattlen)
5224                                 break;
5225                 }
5226
5227                 /* Stop if case-varying character (it's sort of a wildcard) */
5228                 if (case_insensitive &&
5229                   pattern_char_isalpha(patt[pos], is_multibyte, locale, locale_is_c))
5230                         break;
5231
5232                 match[match_pos++] = patt[pos];
5233         }
5234
5235         match[match_pos] = '\0';
5236
5237         if (typeid != BYTEAOID)
5238                 *prefix_const = string_to_const(match, typeid);
5239         else
5240                 *prefix_const = string_to_bytea_const(match, match_pos);
5241
5242         if (rest_selec != NULL)
5243                 *rest_selec = like_selectivity(&patt[pos], pattlen - pos,
5244                                                                            case_insensitive);
5245
5246         pfree(patt);
5247         pfree(match);
5248
5249         /* in LIKE, an empty pattern is an exact match! */
5250         if (pos == pattlen)
5251                 return Pattern_Prefix_Exact;    /* reached end of pattern, so exact */
5252
5253         if (match_pos > 0)
5254                 return Pattern_Prefix_Partial;
5255
5256         return Pattern_Prefix_None;
5257 }
5258
5259 static Pattern_Prefix_Status
5260 regex_fixed_prefix(Const *patt_const, bool case_insensitive, Oid collation,
5261                                    Const **prefix_const, Selectivity *rest_selec)
5262 {
5263         Oid                     typeid = patt_const->consttype;
5264         char       *prefix;
5265         bool            exact;
5266
5267         /*
5268          * Should be unnecessary, there are no bytea regex operators defined. As
5269          * such, it should be noted that the rest of this function has *not* been
5270          * made safe for binary (possibly NULL containing) strings.
5271          */
5272         if (typeid == BYTEAOID)
5273                 ereport(ERROR,
5274                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5275                  errmsg("regular-expression matching not supported on type bytea")));
5276
5277         /* Use the regexp machinery to extract the prefix, if any */
5278         prefix = regexp_fixed_prefix(DatumGetTextPP(patt_const->constvalue),
5279                                                                  case_insensitive, collation,
5280                                                                  &exact);
5281
5282         if (prefix == NULL)
5283         {
5284                 *prefix_const = NULL;
5285
5286                 if (rest_selec != NULL)
5287                 {
5288                         char   *patt = TextDatumGetCString(patt_const->constvalue);
5289
5290                         *rest_selec = regex_selectivity(patt, strlen(patt),
5291                                                                                         case_insensitive,
5292                                                                                         0);
5293                         pfree(patt);
5294                 }
5295
5296                 return Pattern_Prefix_None;
5297         }
5298
5299         *prefix_const = string_to_const(prefix, typeid);
5300
5301         if (rest_selec != NULL)
5302         {
5303                 if (exact)
5304                 {
5305                         /* Exact match, so there's no additional selectivity */
5306                         *rest_selec = 1.0;
5307                 }
5308                 else
5309                 {
5310                         char   *patt = TextDatumGetCString(patt_const->constvalue);
5311
5312                         *rest_selec = regex_selectivity(patt, strlen(patt),
5313                                                                                         case_insensitive,
5314                                                                                         strlen(prefix));
5315                         pfree(patt);
5316                 }
5317         }
5318
5319         pfree(prefix);
5320
5321         if (exact)
5322                 return Pattern_Prefix_Exact;    /* pattern specifies exact match */
5323         else
5324                 return Pattern_Prefix_Partial;
5325 }
5326
5327 Pattern_Prefix_Status
5328 pattern_fixed_prefix(Const *patt, Pattern_Type ptype, Oid collation,
5329                                          Const **prefix, Selectivity *rest_selec)
5330 {
5331         Pattern_Prefix_Status result;
5332
5333         switch (ptype)
5334         {
5335                 case Pattern_Type_Like:
5336                         result = like_fixed_prefix(patt, false, collation,
5337                                                                            prefix, rest_selec);
5338                         break;
5339                 case Pattern_Type_Like_IC:
5340                         result = like_fixed_prefix(patt, true, collation,
5341                                                                            prefix, rest_selec);
5342                         break;
5343                 case Pattern_Type_Regex:
5344                         result = regex_fixed_prefix(patt, false, collation,
5345                                                                                 prefix, rest_selec);
5346                         break;
5347                 case Pattern_Type_Regex_IC:
5348                         result = regex_fixed_prefix(patt, true, collation,
5349                                                                                 prefix, rest_selec);
5350                         break;
5351                 default:
5352                         elog(ERROR, "unrecognized ptype: %d", (int) ptype);
5353                         result = Pattern_Prefix_None;           /* keep compiler quiet */
5354                         break;
5355         }
5356         return result;
5357 }
5358
5359 /*
5360  * Estimate the selectivity of a fixed prefix for a pattern match.
5361  *
5362  * A fixed prefix "foo" is estimated as the selectivity of the expression
5363  * "variable >= 'foo' AND variable < 'fop'" (see also indxpath.c).
5364  *
5365  * The selectivity estimate is with respect to the portion of the column
5366  * population represented by the histogram --- the caller must fold this
5367  * together with info about MCVs and NULLs.
5368  *
5369  * We use the >= and < operators from the specified btree opfamily to do the
5370  * estimation.  The given variable and Const must be of the associated
5371  * datatype.
5372  *
5373  * XXX Note: we make use of the upper bound to estimate operator selectivity
5374  * even if the locale is such that we cannot rely on the upper-bound string.
5375  * The selectivity only needs to be approximately right anyway, so it seems
5376  * more useful to use the upper-bound code than not.
5377  */
5378 static Selectivity
5379 prefix_selectivity(PlannerInfo *root, VariableStatData *vardata,
5380                                    Oid vartype, Oid opfamily, Const *prefixcon)
5381 {
5382         Selectivity prefixsel;
5383         Oid                     cmpopr;
5384         FmgrInfo        opproc;
5385         Const      *greaterstrcon;
5386         Selectivity eq_sel;
5387
5388         cmpopr = get_opfamily_member(opfamily, vartype, vartype,
5389                                                                  BTGreaterEqualStrategyNumber);
5390         if (cmpopr == InvalidOid)
5391                 elog(ERROR, "no >= operator for opfamily %u", opfamily);
5392         fmgr_info(get_opcode(cmpopr), &opproc);
5393
5394         prefixsel = ineq_histogram_selectivity(root, vardata, &opproc, true,
5395                                                                                    prefixcon->constvalue,
5396                                                                                    prefixcon->consttype);
5397
5398         if (prefixsel < 0.0)
5399         {
5400                 /* No histogram is present ... return a suitable default estimate */
5401                 return DEFAULT_MATCH_SEL;
5402         }
5403
5404         /*-------
5405          * If we can create a string larger than the prefix, say
5406          *      "x < greaterstr".
5407          *-------
5408          */
5409         cmpopr = get_opfamily_member(opfamily, vartype, vartype,
5410                                                                  BTLessStrategyNumber);
5411         if (cmpopr == InvalidOid)
5412                 elog(ERROR, "no < operator for opfamily %u", opfamily);
5413         fmgr_info(get_opcode(cmpopr), &opproc);
5414         greaterstrcon = make_greater_string(prefixcon, &opproc,
5415                                                                                 DEFAULT_COLLATION_OID);
5416         if (greaterstrcon)
5417         {
5418                 Selectivity topsel;
5419
5420                 topsel = ineq_histogram_selectivity(root, vardata, &opproc, false,
5421                                                                                         greaterstrcon->constvalue,
5422                                                                                         greaterstrcon->consttype);
5423
5424                 /* ineq_histogram_selectivity worked before, it shouldn't fail now */
5425                 Assert(topsel >= 0.0);
5426
5427                 /*
5428                  * Merge the two selectivities in the same way as for a range query
5429                  * (see clauselist_selectivity()).      Note that we don't need to worry
5430                  * about double-exclusion of nulls, since ineq_histogram_selectivity
5431                  * doesn't count those anyway.
5432                  */
5433                 prefixsel = topsel + prefixsel - 1.0;
5434         }
5435
5436         /*
5437          * If the prefix is long then the two bounding values might be too close
5438          * together for the histogram to distinguish them usefully, resulting in a
5439          * zero estimate (plus or minus roundoff error). To avoid returning a
5440          * ridiculously small estimate, compute the estimated selectivity for
5441          * "variable = 'foo'", and clamp to that. (Obviously, the resultant
5442          * estimate should be at least that.)
5443          *
5444          * We apply this even if we couldn't make a greater string.  That case
5445          * suggests that the prefix is near the maximum possible, and thus
5446          * probably off the end of the histogram, and thus we probably got a very
5447          * small estimate from the >= condition; so we still need to clamp.
5448          */
5449         cmpopr = get_opfamily_member(opfamily, vartype, vartype,
5450                                                                  BTEqualStrategyNumber);
5451         if (cmpopr == InvalidOid)
5452                 elog(ERROR, "no = operator for opfamily %u", opfamily);
5453         eq_sel = var_eq_const(vardata, cmpopr, prefixcon->constvalue,
5454                                                   false, true);
5455
5456         prefixsel = Max(prefixsel, eq_sel);
5457
5458         return prefixsel;
5459 }
5460
5461
5462 /*
5463  * Estimate the selectivity of a pattern of the specified type.
5464  * Note that any fixed prefix of the pattern will have been removed already,
5465  * so actually we may be looking at just a fragment of the pattern.
5466  *
5467  * For now, we use a very simplistic approach: fixed characters reduce the
5468  * selectivity a good deal, character ranges reduce it a little,
5469  * wildcards (such as % for LIKE or .* for regex) increase it.
5470  */
5471
5472 #define FIXED_CHAR_SEL  0.20    /* about 1/5 */
5473 #define CHAR_RANGE_SEL  0.25
5474 #define ANY_CHAR_SEL    0.9             /* not 1, since it won't match end-of-string */
5475 #define FULL_WILDCARD_SEL 5.0
5476 #define PARTIAL_WILDCARD_SEL 2.0
5477
5478 static Selectivity
5479 like_selectivity(const char *patt, int pattlen, bool case_insensitive)
5480 {
5481         Selectivity sel = 1.0;
5482         int                     pos;
5483
5484         /* Skip any leading wildcard; it's already factored into initial sel */
5485         for (pos = 0; pos < pattlen; pos++)
5486         {
5487                 if (patt[pos] != '%' && patt[pos] != '_')
5488                         break;
5489         }
5490
5491         for (; pos < pattlen; pos++)
5492         {
5493                 /* % and _ are wildcard characters in LIKE */
5494                 if (patt[pos] == '%')
5495                         sel *= FULL_WILDCARD_SEL;
5496                 else if (patt[pos] == '_')
5497                         sel *= ANY_CHAR_SEL;
5498                 else if (patt[pos] == '\\')
5499                 {
5500                         /* Backslash quotes the next character */
5501                         pos++;
5502                         if (pos >= pattlen)
5503                                 break;
5504                         sel *= FIXED_CHAR_SEL;
5505                 }
5506                 else
5507                         sel *= FIXED_CHAR_SEL;
5508         }
5509         /* Could get sel > 1 if multiple wildcards */
5510         if (sel > 1.0)
5511                 sel = 1.0;
5512         return sel;
5513 }
5514
5515 static Selectivity
5516 regex_selectivity_sub(const char *patt, int pattlen, bool case_insensitive)
5517 {
5518         Selectivity sel = 1.0;
5519         int                     paren_depth = 0;
5520         int                     paren_pos = 0;  /* dummy init to keep compiler quiet */
5521         int                     pos;
5522
5523         for (pos = 0; pos < pattlen; pos++)
5524         {
5525                 if (patt[pos] == '(')
5526                 {
5527                         if (paren_depth == 0)
5528                                 paren_pos = pos;        /* remember start of parenthesized item */
5529                         paren_depth++;
5530                 }
5531                 else if (patt[pos] == ')' && paren_depth > 0)
5532                 {
5533                         paren_depth--;
5534                         if (paren_depth == 0)
5535                                 sel *= regex_selectivity_sub(patt + (paren_pos + 1),
5536                                                                                          pos - (paren_pos + 1),
5537                                                                                          case_insensitive);
5538                 }
5539                 else if (patt[pos] == '|' && paren_depth == 0)
5540                 {
5541                         /*
5542                          * If unquoted | is present at paren level 0 in pattern, we have
5543                          * multiple alternatives; sum their probabilities.
5544                          */
5545                         sel += regex_selectivity_sub(patt + (pos + 1),
5546                                                                                  pattlen - (pos + 1),
5547                                                                                  case_insensitive);
5548                         break;                          /* rest of pattern is now processed */
5549                 }
5550                 else if (patt[pos] == '[')
5551                 {
5552                         bool            negclass = false;
5553
5554                         if (patt[++pos] == '^')
5555                         {
5556                                 negclass = true;
5557                                 pos++;
5558                         }
5559                         if (patt[pos] == ']')           /* ']' at start of class is not
5560                                                                                  * special */
5561                                 pos++;
5562                         while (pos < pattlen && patt[pos] != ']')
5563                                 pos++;
5564                         if (paren_depth == 0)
5565                                 sel *= (negclass ? (1.0 - CHAR_RANGE_SEL) : CHAR_RANGE_SEL);
5566                 }
5567                 else if (patt[pos] == '.')
5568                 {
5569                         if (paren_depth == 0)
5570                                 sel *= ANY_CHAR_SEL;
5571                 }
5572                 else if (patt[pos] == '*' ||
5573                                  patt[pos] == '?' ||
5574                                  patt[pos] == '+')
5575                 {
5576                         /* Ought to be smarter about quantifiers... */
5577                         if (paren_depth == 0)
5578                                 sel *= PARTIAL_WILDCARD_SEL;
5579                 }
5580                 else if (patt[pos] == '{')
5581                 {
5582                         while (pos < pattlen && patt[pos] != '}')
5583                                 pos++;
5584                         if (paren_depth == 0)
5585                                 sel *= PARTIAL_WILDCARD_SEL;
5586                 }
5587                 else if (patt[pos] == '\\')
5588                 {
5589                         /* backslash quotes the next character */
5590                         pos++;
5591                         if (pos >= pattlen)
5592                                 break;
5593                         if (paren_depth == 0)
5594                                 sel *= FIXED_CHAR_SEL;
5595                 }
5596                 else
5597                 {
5598                         if (paren_depth == 0)
5599                                 sel *= FIXED_CHAR_SEL;
5600                 }
5601         }
5602         /* Could get sel > 1 if multiple wildcards */
5603         if (sel > 1.0)
5604                 sel = 1.0;
5605         return sel;
5606 }
5607
5608 static Selectivity
5609 regex_selectivity(const char *patt, int pattlen, bool case_insensitive,
5610                                   int fixed_prefix_len)
5611 {
5612         Selectivity sel;
5613
5614         /* If patt doesn't end with $, consider it to have a trailing wildcard */
5615         if (pattlen > 0 && patt[pattlen - 1] == '$' &&
5616                 (pattlen == 1 || patt[pattlen - 2] != '\\'))
5617         {
5618                 /* has trailing $ */
5619                 sel = regex_selectivity_sub(patt, pattlen - 1, case_insensitive);
5620         }
5621         else
5622         {
5623                 /* no trailing $ */
5624                 sel = regex_selectivity_sub(patt, pattlen, case_insensitive);
5625                 sel *= FULL_WILDCARD_SEL;
5626         }
5627
5628         /* If there's a fixed prefix, discount its selectivity */
5629         if (fixed_prefix_len > 0)
5630                 sel /= pow(FIXED_CHAR_SEL, fixed_prefix_len);
5631
5632         /* Make sure result stays in range */
5633         CLAMP_PROBABILITY(sel);
5634         return sel;
5635 }
5636
5637
5638 /*
5639  * For bytea, the increment function need only increment the current byte
5640  * (there are no multibyte characters to worry about).
5641  */
5642 static bool
5643 byte_increment(unsigned char *ptr, int len)
5644 {
5645         if (*ptr >= 255)
5646                 return false;
5647         (*ptr)++;
5648         return true;
5649 }
5650
5651 /*
5652  * Try to generate a string greater than the given string or any
5653  * string it is a prefix of.  If successful, return a palloc'd string
5654  * in the form of a Const node; else return NULL.
5655  *
5656  * The caller must provide the appropriate "less than" comparison function
5657  * for testing the strings, along with the collation to use.
5658  *
5659  * The key requirement here is that given a prefix string, say "foo",
5660  * we must be able to generate another string "fop" that is greater than
5661  * all strings "foobar" starting with "foo".  We can test that we have
5662  * generated a string greater than the prefix string, but in non-C collations
5663  * that is not a bulletproof guarantee that an extension of the string might
5664  * not sort after it; an example is that "foo " is less than "foo!", but it
5665  * is not clear that a "dictionary" sort ordering will consider "foo!" less
5666  * than "foo bar".      CAUTION: Therefore, this function should be used only for
5667  * estimation purposes when working in a non-C collation.
5668  *
5669  * To try to catch most cases where an extended string might otherwise sort
5670  * before the result value, we determine which of the strings "Z", "z", "y",
5671  * and "9" is seen as largest by the collation, and append that to the given
5672  * prefix before trying to find a string that compares as larger.
5673  *
5674  * To search for a greater string, we repeatedly "increment" the rightmost
5675  * character, using an encoding-specific character incrementer function.
5676  * When it's no longer possible to increment the last character, we truncate
5677  * off that character and start incrementing the next-to-rightmost.
5678  * For example, if "z" were the last character in the sort order, then we
5679  * could produce "foo" as a string greater than "fonz".
5680  *
5681  * This could be rather slow in the worst case, but in most cases we
5682  * won't have to try more than one or two strings before succeeding.
5683  *
5684  * Note that it's important for the character incrementer not to be too anal
5685  * about producing every possible character code, since in some cases the only
5686  * way to get a larger string is to increment a previous character position.
5687  * So we don't want to spend too much time trying every possible character
5688  * code at the last position.  A good rule of thumb is to be sure that we
5689  * don't try more than 256*K values for a K-byte character (and definitely
5690  * not 256^K, which is what an exhaustive search would approach).
5691  */
5692 Const *
5693 make_greater_string(const Const *str_const, FmgrInfo *ltproc, Oid collation)
5694 {
5695         Oid                     datatype = str_const->consttype;
5696         char       *workstr;
5697         int                     len;
5698         Datum           cmpstr;
5699         text       *cmptxt = NULL;
5700         mbcharacter_incrementer charinc;
5701
5702         /*
5703          * Get a modifiable copy of the prefix string in C-string format, and set
5704          * up the string we will compare to as a Datum.  In C locale this can just
5705          * be the given prefix string, otherwise we need to add a suffix.  Types
5706          * NAME and BYTEA sort bytewise so they don't need a suffix either.
5707          */
5708         if (datatype == NAMEOID)
5709         {
5710                 workstr = DatumGetCString(DirectFunctionCall1(nameout,
5711                                                                                                           str_const->constvalue));
5712                 len = strlen(workstr);
5713                 cmpstr = str_const->constvalue;
5714         }
5715         else if (datatype == BYTEAOID)
5716         {
5717                 bytea      *bstr = DatumGetByteaP(str_const->constvalue);
5718
5719                 len = VARSIZE(bstr) - VARHDRSZ;
5720                 workstr = (char *) palloc(len);
5721                 memcpy(workstr, VARDATA(bstr), len);
5722                 if ((Pointer) bstr != DatumGetPointer(str_const->constvalue))
5723                         pfree(bstr);
5724                 cmpstr = str_const->constvalue;
5725         }
5726         else
5727         {
5728                 workstr = TextDatumGetCString(str_const->constvalue);
5729                 len = strlen(workstr);
5730                 if (lc_collate_is_c(collation) || len == 0)
5731                         cmpstr = str_const->constvalue;
5732                 else
5733                 {
5734                         /* If first time through, determine the suffix to use */
5735                         static char suffixchar = 0;
5736                         static Oid      suffixcollation = 0;
5737
5738                         if (!suffixchar || suffixcollation != collation)
5739                         {
5740                                 char       *best;
5741
5742                                 best = "Z";
5743                                 if (varstr_cmp(best, 1, "z", 1, collation) < 0)
5744                                         best = "z";
5745                                 if (varstr_cmp(best, 1, "y", 1, collation) < 0)
5746                                         best = "y";
5747                                 if (varstr_cmp(best, 1, "9", 1, collation) < 0)
5748                                         best = "9";
5749                                 suffixchar = *best;
5750                                 suffixcollation = collation;
5751                         }
5752
5753                         /* And build the string to compare to */
5754                         cmptxt = (text *) palloc(VARHDRSZ + len + 1);
5755                         SET_VARSIZE(cmptxt, VARHDRSZ + len + 1);
5756                         memcpy(VARDATA(cmptxt), workstr, len);
5757                         *(VARDATA(cmptxt) + len) = suffixchar;
5758                         cmpstr = PointerGetDatum(cmptxt);
5759                 }
5760         }
5761
5762         /* Select appropriate character-incrementer function */
5763         if (datatype == BYTEAOID)
5764                 charinc = byte_increment;
5765         else
5766                 charinc = pg_database_encoding_character_incrementer();
5767
5768         /* And search ... */
5769         while (len > 0)
5770         {
5771                 int                     charlen;
5772                 unsigned char *lastchar;
5773
5774                 /* Identify the last character --- for bytea, just the last byte */
5775                 if (datatype == BYTEAOID)
5776                         charlen = 1;
5777                 else
5778                         charlen = len - pg_mbcliplen(workstr, len, len - 1);
5779                 lastchar = (unsigned char *) (workstr + len - charlen);
5780
5781                 /*
5782                  * Try to generate a larger string by incrementing the last character
5783                  * (for BYTEA, we treat each byte as a character).
5784                  *
5785                  * Note: the incrementer function is expected to return true if it's
5786                  * generated a valid-per-the-encoding new character, otherwise false.
5787                  * The contents of the character on false return are unspecified.
5788                  */
5789                 while (charinc(lastchar, charlen))
5790                 {
5791                         Const      *workstr_const;
5792
5793                         if (datatype == BYTEAOID)
5794                                 workstr_const = string_to_bytea_const(workstr, len);
5795                         else
5796                                 workstr_const = string_to_const(workstr, datatype);
5797
5798                         if (DatumGetBool(FunctionCall2Coll(ltproc,
5799                                                                                            collation,
5800                                                                                            cmpstr,
5801                                                                                            workstr_const->constvalue)))
5802                         {
5803                                 /* Successfully made a string larger than cmpstr */
5804                                 if (cmptxt)
5805                                         pfree(cmptxt);
5806                                 pfree(workstr);
5807                                 return workstr_const;
5808                         }
5809
5810                         /* No good, release unusable value and try again */
5811                         pfree(DatumGetPointer(workstr_const->constvalue));
5812                         pfree(workstr_const);
5813                 }
5814
5815                 /*
5816                  * No luck here, so truncate off the last character and try to
5817                  * increment the next one.
5818                  */
5819                 len -= charlen;
5820                 workstr[len] = '\0';
5821         }
5822
5823         /* Failed... */
5824         if (cmptxt)
5825                 pfree(cmptxt);
5826         pfree(workstr);
5827
5828         return NULL;
5829 }
5830
5831 /*
5832  * Generate a Datum of the appropriate type from a C string.
5833  * Note that all of the supported types are pass-by-ref, so the
5834  * returned value should be pfree'd if no longer needed.
5835  */
5836 static Datum
5837 string_to_datum(const char *str, Oid datatype)
5838 {
5839         Assert(str != NULL);
5840
5841         /*
5842          * We cheat a little by assuming that CStringGetTextDatum() will do for
5843          * bpchar and varchar constants too...
5844          */
5845         if (datatype == NAMEOID)
5846                 return DirectFunctionCall1(namein, CStringGetDatum(str));
5847         else if (datatype == BYTEAOID)
5848                 return DirectFunctionCall1(byteain, CStringGetDatum(str));
5849         else
5850                 return CStringGetTextDatum(str);
5851 }
5852
5853 /*
5854  * Generate a Const node of the appropriate type from a C string.
5855  */
5856 static Const *
5857 string_to_const(const char *str, Oid datatype)
5858 {
5859         Datum           conval = string_to_datum(str, datatype);
5860         Oid                     collation;
5861         int                     constlen;
5862
5863         /*
5864          * We only need to support a few datatypes here, so hard-wire properties
5865          * instead of incurring the expense of catalog lookups.
5866          */
5867         switch (datatype)
5868         {
5869                 case TEXTOID:
5870                 case VARCHAROID:
5871                 case BPCHAROID:
5872                         collation = DEFAULT_COLLATION_OID;
5873                         constlen = -1;
5874                         break;
5875
5876                 case NAMEOID:
5877                         collation = InvalidOid;
5878                         constlen = NAMEDATALEN;
5879                         break;
5880
5881                 case BYTEAOID:
5882                         collation = InvalidOid;
5883                         constlen = -1;
5884                         break;
5885
5886                 default:
5887                         elog(ERROR, "unexpected datatype in string_to_const: %u",
5888                                  datatype);
5889                         return NULL;
5890         }
5891
5892         return makeConst(datatype, -1, collation, constlen,
5893                                          conval, false, false);
5894 }
5895
5896 /*
5897  * Generate a Const node of bytea type from a binary C string and a length.
5898  */
5899 static Const *
5900 string_to_bytea_const(const char *str, size_t str_len)
5901 {
5902         bytea      *bstr = palloc(VARHDRSZ + str_len);
5903         Datum           conval;
5904
5905         memcpy(VARDATA(bstr), str, str_len);
5906         SET_VARSIZE(bstr, VARHDRSZ + str_len);
5907         conval = PointerGetDatum(bstr);
5908
5909         return makeConst(BYTEAOID, -1, InvalidOid, -1, conval, false, false);
5910 }
5911
5912 /*-------------------------------------------------------------------------
5913  *
5914  * Index cost estimation functions
5915  *
5916  *-------------------------------------------------------------------------
5917  */
5918
5919 /*
5920  * genericcostestimate is a general-purpose estimator that can be used for
5921  * most index types.  In some cases we use genericcostestimate as the base
5922  * code and then incorporate additional index-type-specific knowledge in
5923  * the type-specific calling function.  To avoid code duplication, we make
5924  * genericcostestimate return a number of intermediate values as well as
5925  * its preliminary estimates of the output cost values.  The GenericCosts
5926  * struct includes all these values.
5927  *
5928  * Callers should initialize all fields of GenericCosts to zero.  In addition,
5929  * they can set numIndexTuples to some positive value if they have a better
5930  * than default way of estimating the number of leaf index tuples visited.
5931  */
5932 typedef struct
5933 {
5934         /* These are the values the cost estimator must return to the planner */
5935         Cost            indexStartupCost;               /* index-related startup cost */
5936         Cost            indexTotalCost;                 /* total index-related scan cost */
5937         Selectivity     indexSelectivity;               /* selectivity of index */
5938         double          indexCorrelation;               /* order correlation of index */
5939
5940         /* Intermediate values we obtain along the way */
5941         double          numIndexPages;                  /* number of leaf pages visited */
5942         double          numIndexTuples;                 /* number of leaf tuples visited */
5943         double          spc_random_page_cost;   /* relevant random_page_cost value */
5944         double          num_sa_scans;                   /* # indexscans from ScalarArrayOps */
5945 } GenericCosts;
5946
5947 static void
5948 genericcostestimate(PlannerInfo *root,
5949                                         IndexPath *path,
5950                                         double loop_count,
5951                                         GenericCosts *costs)
5952 {
5953         IndexOptInfo *index = path->indexinfo;
5954         List       *indexQuals = path->indexquals;
5955         List       *indexOrderBys = path->indexorderbys;
5956         Cost            indexStartupCost;
5957         Cost            indexTotalCost;
5958         Selectivity     indexSelectivity;
5959         double          indexCorrelation;
5960         double          numIndexPages;
5961         double          numIndexTuples;
5962         double          spc_random_page_cost;
5963         double          num_sa_scans;
5964         double          num_outer_scans;
5965         double          num_scans;
5966         QualCost        index_qual_cost;
5967         double          qual_op_cost;
5968         double          qual_arg_cost;
5969         List       *selectivityQuals;
5970         ListCell   *l;
5971
5972         /*
5973          * If the index is partial, AND the index predicate with the explicitly
5974          * given indexquals to produce a more accurate idea of the index
5975          * selectivity.
5976          */
5977         selectivityQuals = add_predicate_to_quals(index, indexQuals);
5978
5979         /*
5980          * Check for ScalarArrayOpExpr index quals, and estimate the number of
5981          * index scans that will be performed.
5982          */
5983         num_sa_scans = 1;
5984         foreach(l, indexQuals)
5985         {
5986                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
5987
5988                 if (IsA(rinfo->clause, ScalarArrayOpExpr))
5989                 {
5990                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) rinfo->clause;
5991                         int                     alength = estimate_array_length(lsecond(saop->args));
5992
5993                         if (alength > 1)
5994                                 num_sa_scans *= alength;
5995                 }
5996         }
5997
5998         /* Estimate the fraction of main-table tuples that will be visited */
5999         indexSelectivity = clauselist_selectivity(root, selectivityQuals,
6000                                                                                           index->rel->relid,
6001                                                                                           JOIN_INNER,
6002                                                                                           NULL);
6003
6004         /*
6005          * If caller didn't give us an estimate, estimate the number of index
6006          * tuples that will be visited.  We do it in this rather peculiar-looking
6007          * way in order to get the right answer for partial indexes.
6008          */
6009         numIndexTuples = costs->numIndexTuples;
6010         if (numIndexTuples <= 0.0)
6011         {
6012                 numIndexTuples = indexSelectivity * index->rel->tuples;
6013
6014                 /*
6015                  * The above calculation counts all the tuples visited across all
6016                  * scans induced by ScalarArrayOpExpr nodes.  We want to consider the
6017                  * average per-indexscan number, so adjust.  This is a handy place to
6018                  * round to integer, too.  (If caller supplied tuple estimate, it's
6019                  * responsible for handling these considerations.)
6020                  */
6021                 numIndexTuples = rint(numIndexTuples / num_sa_scans);
6022         }
6023
6024         /*
6025          * We can bound the number of tuples by the index size in any case. Also,
6026          * always estimate at least one tuple is touched, even when
6027          * indexSelectivity estimate is tiny.
6028          */
6029         if (numIndexTuples > index->tuples)
6030                 numIndexTuples = index->tuples;
6031         if (numIndexTuples < 1.0)
6032                 numIndexTuples = 1.0;
6033
6034         /*
6035          * Estimate the number of index pages that will be retrieved.
6036          *
6037          * We use the simplistic method of taking a pro-rata fraction of the total
6038          * number of index pages.  In effect, this counts only leaf pages and not
6039          * any overhead such as index metapage or upper tree levels.
6040          *
6041          * In practice access to upper index levels is often nearly free because
6042          * those tend to stay in cache under load; moreover, the cost involved is
6043          * highly dependent on index type.  We therefore ignore such costs here
6044          * and leave it to the caller to add a suitable charge if needed.
6045          */
6046         if (index->pages > 1 && index->tuples > 1)
6047                 numIndexPages = ceil(numIndexTuples * index->pages / index->tuples);
6048         else
6049                 numIndexPages = 1.0;
6050
6051         /* fetch estimated page cost for schema containing index */
6052         get_tablespace_page_costs(index->reltablespace,
6053                                                           &spc_random_page_cost,
6054                                                           NULL);
6055
6056         /*
6057          * Now compute the disk access costs.
6058          *
6059          * The above calculations are all per-index-scan.  However, if we are in a
6060          * nestloop inner scan, we can expect the scan to be repeated (with
6061          * different search keys) for each row of the outer relation.  Likewise,
6062          * ScalarArrayOpExpr quals result in multiple index scans.      This creates
6063          * the potential for cache effects to reduce the number of disk page
6064          * fetches needed.      We want to estimate the average per-scan I/O cost in
6065          * the presence of caching.
6066          *
6067          * We use the Mackert-Lohman formula (see costsize.c for details) to
6068          * estimate the total number of page fetches that occur.  While this
6069          * wasn't what it was designed for, it seems a reasonable model anyway.
6070          * Note that we are counting pages not tuples anymore, so we take N = T =
6071          * index size, as if there were one "tuple" per page.
6072          */
6073         num_outer_scans = loop_count;
6074         num_scans = num_sa_scans * num_outer_scans;
6075
6076         if (num_scans > 1)
6077         {
6078                 double          pages_fetched;
6079
6080                 /* total page fetches ignoring cache effects */
6081                 pages_fetched = numIndexPages * num_scans;
6082
6083                 /* use Mackert and Lohman formula to adjust for cache effects */
6084                 pages_fetched = index_pages_fetched(pages_fetched,
6085                                                                                         index->pages,
6086                                                                                         (double) index->pages,
6087                                                                                         root);
6088
6089                 /*
6090                  * Now compute the total disk access cost, and then report a pro-rated
6091                  * share for each outer scan.  (Don't pro-rate for ScalarArrayOpExpr,
6092                  * since that's internal to the indexscan.)
6093                  */
6094                 indexTotalCost = (pages_fetched * spc_random_page_cost)
6095                         / num_outer_scans;
6096         }
6097         else
6098         {
6099                 /*
6100                  * For a single index scan, we just charge spc_random_page_cost per
6101                  * page touched.
6102                  */
6103                 indexTotalCost = numIndexPages * spc_random_page_cost;
6104         }
6105
6106         /*
6107          * CPU cost: any complex expressions in the indexquals will need to be
6108          * evaluated once at the start of the scan to reduce them to runtime keys
6109          * to pass to the index AM (see nodeIndexscan.c).  We model the per-tuple
6110          * CPU costs as cpu_index_tuple_cost plus one cpu_operator_cost per
6111          * indexqual operator.  Because we have numIndexTuples as a per-scan
6112          * number, we have to multiply by num_sa_scans to get the correct result
6113          * for ScalarArrayOpExpr cases.  Similarly add in costs for any index
6114          * ORDER BY expressions.
6115          *
6116          * Note: this neglects the possible costs of rechecking lossy operators.
6117          * Detecting that that might be needed seems more expensive than it's
6118          * worth, though, considering all the other inaccuracies here ...
6119          */
6120         cost_qual_eval(&index_qual_cost, indexQuals, root);
6121         qual_arg_cost = index_qual_cost.startup + index_qual_cost.per_tuple;
6122         cost_qual_eval(&index_qual_cost, indexOrderBys, root);
6123         qual_arg_cost += index_qual_cost.startup + index_qual_cost.per_tuple;
6124         qual_op_cost = cpu_operator_cost *
6125                 (list_length(indexQuals) + list_length(indexOrderBys));
6126         qual_arg_cost -= qual_op_cost;
6127         if (qual_arg_cost < 0)          /* just in case... */
6128                 qual_arg_cost = 0;
6129
6130         indexStartupCost = qual_arg_cost;
6131         indexTotalCost += qual_arg_cost;
6132         indexTotalCost += numIndexTuples * num_sa_scans * (cpu_index_tuple_cost + qual_op_cost);
6133
6134         /*
6135          * Generic assumption about index correlation: there isn't any.
6136          */
6137         indexCorrelation = 0.0;
6138
6139         /*
6140          * Return everything to caller.
6141          */
6142         costs->indexStartupCost = indexStartupCost;
6143         costs->indexTotalCost = indexTotalCost;
6144         costs->indexSelectivity = indexSelectivity;
6145         costs->indexCorrelation = indexCorrelation;
6146         costs->numIndexPages = numIndexPages;
6147         costs->numIndexTuples = numIndexTuples;
6148         costs->spc_random_page_cost = spc_random_page_cost;
6149         costs->num_sa_scans = num_sa_scans;
6150 }
6151
6152 /*
6153  * If the index is partial, add its predicate to the given qual list.
6154  *
6155  * ANDing the index predicate with the explicitly given indexquals produces
6156  * a more accurate idea of the index's selectivity.  However, we need to be
6157  * careful not to insert redundant clauses, because clauselist_selectivity()
6158  * is easily fooled into computing a too-low selectivity estimate.      Our
6159  * approach is to add only the predicate clause(s) that cannot be proven to
6160  * be implied by the given indexquals.  This successfully handles cases such
6161  * as a qual "x = 42" used with a partial index "WHERE x >= 40 AND x < 50".
6162  * There are many other cases where we won't detect redundancy, leading to a
6163  * too-low selectivity estimate, which will bias the system in favor of using
6164  * partial indexes where possible.      That is not necessarily bad though.
6165  *
6166  * Note that indexQuals contains RestrictInfo nodes while the indpred
6167  * does not, so the output list will be mixed.  This is OK for both
6168  * predicate_implied_by() and clauselist_selectivity(), but might be
6169  * problematic if the result were passed to other things.
6170  */
6171 static List *
6172 add_predicate_to_quals(IndexOptInfo *index, List *indexQuals)
6173 {
6174         List       *predExtraQuals = NIL;
6175         ListCell   *lc;
6176
6177         if (index->indpred == NIL)
6178                 return indexQuals;
6179
6180         foreach(lc, index->indpred)
6181         {
6182                 Node       *predQual = (Node *) lfirst(lc);
6183                 List       *oneQual = list_make1(predQual);
6184
6185                 if (!predicate_implied_by(oneQual, indexQuals))
6186                         predExtraQuals = list_concat(predExtraQuals, oneQual);
6187         }
6188         /* list_concat avoids modifying the passed-in indexQuals list */
6189         return list_concat(predExtraQuals, indexQuals);
6190 }
6191
6192
6193 Datum
6194 btcostestimate(PG_FUNCTION_ARGS)
6195 {
6196         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6197         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6198         double          loop_count = PG_GETARG_FLOAT8(2);
6199         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6200         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6201         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6202         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6203         IndexOptInfo *index = path->indexinfo;
6204         GenericCosts costs;
6205         Oid                     relid;
6206         AttrNumber      colnum;
6207         VariableStatData vardata;
6208         double          numIndexTuples;
6209         Cost            descentCost;
6210         List       *indexBoundQuals;
6211         int                     indexcol;
6212         bool            eqQualHere;
6213         bool            found_saop;
6214         bool            found_is_null_op;
6215         double          num_sa_scans;
6216         ListCell   *lcc,
6217                            *lci;
6218
6219         /*
6220          * For a btree scan, only leading '=' quals plus inequality quals for the
6221          * immediately next attribute contribute to index selectivity (these are
6222          * the "boundary quals" that determine the starting and stopping points of
6223          * the index scan).  Additional quals can suppress visits to the heap, so
6224          * it's OK to count them in indexSelectivity, but they should not count
6225          * for estimating numIndexTuples.  So we must examine the given indexquals
6226          * to find out which ones count as boundary quals.      We rely on the
6227          * knowledge that they are given in index column order.
6228          *
6229          * For a RowCompareExpr, we consider only the first column, just as
6230          * rowcomparesel() does.
6231          *
6232          * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
6233          * index scans not one, but the ScalarArrayOpExpr's operator can be
6234          * considered to act the same as it normally does.
6235          */
6236         indexBoundQuals = NIL;
6237         indexcol = 0;
6238         eqQualHere = false;
6239         found_saop = false;
6240         found_is_null_op = false;
6241         num_sa_scans = 1;
6242         forboth(lcc, path->indexquals, lci, path->indexqualcols)
6243         {
6244                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
6245                 Expr       *clause;
6246                 Node       *leftop,
6247                                    *rightop PG_USED_FOR_ASSERTS_ONLY;
6248                 Oid                     clause_op;
6249                 int                     op_strategy;
6250                 bool            is_null_op = false;
6251
6252                 if (indexcol != lfirst_int(lci))
6253                 {
6254                         /* Beginning of a new column's quals */
6255                         if (!eqQualHere)
6256                                 break;                  /* done if no '=' qual for indexcol */
6257                         eqQualHere = false;
6258                         indexcol++;
6259                         if (indexcol != lfirst_int(lci))
6260                                 break;                  /* no quals at all for indexcol */
6261                 }
6262
6263                 Assert(IsA(rinfo, RestrictInfo));
6264                 clause = rinfo->clause;
6265
6266                 if (IsA(clause, OpExpr))
6267                 {
6268                         leftop = get_leftop(clause);
6269                         rightop = get_rightop(clause);
6270                         clause_op = ((OpExpr *) clause)->opno;
6271                 }
6272                 else if (IsA(clause, RowCompareExpr))
6273                 {
6274                         RowCompareExpr *rc = (RowCompareExpr *) clause;
6275
6276                         leftop = (Node *) linitial(rc->largs);
6277                         rightop = (Node *) linitial(rc->rargs);
6278                         clause_op = linitial_oid(rc->opnos);
6279                 }
6280                 else if (IsA(clause, ScalarArrayOpExpr))
6281                 {
6282                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6283
6284                         leftop = (Node *) linitial(saop->args);
6285                         rightop = (Node *) lsecond(saop->args);
6286                         clause_op = saop->opno;
6287                         found_saop = true;
6288                 }
6289                 else if (IsA(clause, NullTest))
6290                 {
6291                         NullTest   *nt = (NullTest *) clause;
6292
6293                         leftop = (Node *) nt->arg;
6294                         rightop = NULL;
6295                         clause_op = InvalidOid;
6296                         if (nt->nulltesttype == IS_NULL)
6297                         {
6298                                 found_is_null_op = true;
6299                                 is_null_op = true;
6300                         }
6301                 }
6302                 else
6303                 {
6304                         elog(ERROR, "unsupported indexqual type: %d",
6305                                  (int) nodeTag(clause));
6306                         continue;                       /* keep compiler quiet */
6307                 }
6308
6309                 if (match_index_to_operand(leftop, indexcol, index))
6310                 {
6311                         /* clause_op is correct */
6312                 }
6313                 else
6314                 {
6315                         Assert(match_index_to_operand(rightop, indexcol, index));
6316                         /* Must flip operator to get the opfamily member */
6317                         clause_op = get_commutator(clause_op);
6318                 }
6319
6320                 /* check for equality operator */
6321                 if (OidIsValid(clause_op))
6322                 {
6323                         op_strategy = get_op_opfamily_strategy(clause_op,
6324                                                                                                    index->opfamily[indexcol]);
6325                         Assert(op_strategy != 0);       /* not a member of opfamily?? */
6326                         if (op_strategy == BTEqualStrategyNumber)
6327                                 eqQualHere = true;
6328                 }
6329                 else if (is_null_op)
6330                 {
6331                         /* IS NULL is like = for purposes of selectivity determination */
6332                         eqQualHere = true;
6333                 }
6334                 /* count up number of SA scans induced by indexBoundQuals only */
6335                 if (IsA(clause, ScalarArrayOpExpr))
6336                 {
6337                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6338                         int                     alength = estimate_array_length(lsecond(saop->args));
6339
6340                         if (alength > 1)
6341                                 num_sa_scans *= alength;
6342                 }
6343                 indexBoundQuals = lappend(indexBoundQuals, rinfo);
6344         }
6345
6346         /*
6347          * If index is unique and we found an '=' clause for each column, we can
6348          * just assume numIndexTuples = 1 and skip the expensive
6349          * clauselist_selectivity calculations.  However, a ScalarArrayOp or
6350          * NullTest invalidates that theory, even though it sets eqQualHere.
6351          */
6352         if (index->unique &&
6353                 indexcol == index->ncolumns - 1 &&
6354                 eqQualHere &&
6355                 !found_saop &&
6356                 !found_is_null_op)
6357                 numIndexTuples = 1.0;
6358         else
6359         {
6360                 List       *selectivityQuals;
6361                 Selectivity btreeSelectivity;
6362
6363                 /*
6364                  * If the index is partial, AND the index predicate with the
6365                  * index-bound quals to produce a more accurate idea of the number of
6366                  * rows covered by the bound conditions.
6367                  */
6368                 selectivityQuals = add_predicate_to_quals(index, indexBoundQuals);
6369
6370                 btreeSelectivity = clauselist_selectivity(root, selectivityQuals,
6371                                                                                                   index->rel->relid,
6372                                                                                                   JOIN_INNER,
6373                                                                                                   NULL);
6374                 numIndexTuples = btreeSelectivity * index->rel->tuples;
6375
6376                 /*
6377                  * As in genericcostestimate(), we have to adjust for any
6378                  * ScalarArrayOpExpr quals included in indexBoundQuals, and then round
6379                  * to integer.
6380                  */
6381                 numIndexTuples = rint(numIndexTuples / num_sa_scans);
6382         }
6383
6384         /*
6385          * Now do generic index cost estimation.
6386          */
6387         MemSet(&costs, 0, sizeof(costs));
6388         costs.numIndexTuples = numIndexTuples;
6389
6390         genericcostestimate(root, path, loop_count, &costs);
6391
6392         /*
6393          * Add a CPU-cost component to represent the costs of initial btree
6394          * descent.  We don't charge any I/O cost for touching upper btree levels,
6395          * since they tend to stay in cache, but we still have to do about log2(N)
6396          * comparisons to descend a btree of N leaf tuples.  We charge one
6397          * cpu_operator_cost per comparison.
6398          *
6399          * If there are ScalarArrayOpExprs, charge this once per SA scan.  The
6400          * ones after the first one are not startup cost so far as the overall
6401          * plan is concerned, so add them only to "total" cost.
6402          */
6403         if (index->tuples > 1)          /* avoid computing log(0) */
6404         {
6405                 descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
6406                 costs.indexStartupCost += descentCost;
6407                 costs.indexTotalCost += costs.num_sa_scans * descentCost;
6408         }
6409
6410         /*
6411          * Even though we're not charging I/O cost for touching upper btree pages,
6412          * it's still reasonable to charge some CPU cost per page descended
6413          * through.  Moreover, if we had no such charge at all, bloated indexes
6414          * would appear to have the same search cost as unbloated ones, at least
6415          * in cases where only a single leaf page is expected to be visited.  This
6416          * cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
6417          * touched.  The number of such pages is btree tree height plus one (ie,
6418          * we charge for the leaf page too).  As above, charge once per SA scan.
6419          */
6420         descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6421         costs.indexStartupCost += descentCost;
6422         costs.indexTotalCost += costs.num_sa_scans * descentCost;
6423
6424         /*
6425          * If we can get an estimate of the first column's ordering correlation C
6426          * from pg_statistic, estimate the index correlation as C for a
6427          * single-column index, or C * 0.75 for multiple columns. (The idea here
6428          * is that multiple columns dilute the importance of the first column's
6429          * ordering, but don't negate it entirely.  Before 8.0 we divided the
6430          * correlation by the number of columns, but that seems too strong.)
6431          */
6432         MemSet(&vardata, 0, sizeof(vardata));
6433
6434         if (index->indexkeys[0] != 0)
6435         {
6436                 /* Simple variable --- look to stats for the underlying table */
6437                 RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
6438
6439                 Assert(rte->rtekind == RTE_RELATION);
6440                 relid = rte->relid;
6441                 Assert(relid != InvalidOid);
6442                 colnum = index->indexkeys[0];
6443
6444                 if (get_relation_stats_hook &&
6445                         (*get_relation_stats_hook) (root, rte, colnum, &vardata))
6446                 {
6447                         /*
6448                          * The hook took control of acquiring a stats tuple.  If it did
6449                          * supply a tuple, it'd better have supplied a freefunc.
6450                          */
6451                         if (HeapTupleIsValid(vardata.statsTuple) &&
6452                                 !vardata.freefunc)
6453                                 elog(ERROR, "no function provided to release variable stats with");
6454                 }
6455                 else
6456                 {
6457                         vardata.statsTuple = SearchSysCache3(STATRELATTINH,
6458                                                                                                  ObjectIdGetDatum(relid),
6459                                                                                                  Int16GetDatum(colnum),
6460                                                                                                  BoolGetDatum(rte->inh));
6461                         vardata.freefunc = ReleaseSysCache;
6462                 }
6463         }
6464         else
6465         {
6466                 /* Expression --- maybe there are stats for the index itself */
6467                 relid = index->indexoid;
6468                 colnum = 1;
6469
6470                 if (get_index_stats_hook &&
6471                         (*get_index_stats_hook) (root, relid, colnum, &vardata))
6472                 {
6473                         /*
6474                          * The hook took control of acquiring a stats tuple.  If it did
6475                          * supply a tuple, it'd better have supplied a freefunc.
6476                          */
6477                         if (HeapTupleIsValid(vardata.statsTuple) &&
6478                                 !vardata.freefunc)
6479                                 elog(ERROR, "no function provided to release variable stats with");
6480                 }
6481                 else
6482                 {
6483                         vardata.statsTuple = SearchSysCache3(STATRELATTINH,
6484                                                                                                  ObjectIdGetDatum(relid),
6485                                                                                                  Int16GetDatum(colnum),
6486                                                                                                  BoolGetDatum(false));
6487                         vardata.freefunc = ReleaseSysCache;
6488                 }
6489         }
6490
6491         if (HeapTupleIsValid(vardata.statsTuple))
6492         {
6493                 Oid                     sortop;
6494                 float4     *numbers;
6495                 int                     nnumbers;
6496
6497                 sortop = get_opfamily_member(index->opfamily[0],
6498                                                                          index->opcintype[0],
6499                                                                          index->opcintype[0],
6500                                                                          BTLessStrategyNumber);
6501                 if (OidIsValid(sortop) &&
6502                         get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
6503                                                          STATISTIC_KIND_CORRELATION,
6504                                                          sortop,
6505                                                          NULL,
6506                                                          NULL, NULL,
6507                                                          &numbers, &nnumbers))
6508                 {
6509                         double          varCorrelation;
6510
6511                         Assert(nnumbers == 1);
6512                         varCorrelation = numbers[0];
6513
6514                         if (index->reverse_sort[0])
6515                                 varCorrelation = -varCorrelation;
6516
6517                         if (index->ncolumns > 1)
6518                                 costs.indexCorrelation = varCorrelation * 0.75;
6519                         else
6520                                 costs.indexCorrelation = varCorrelation;
6521
6522                         free_attstatsslot(InvalidOid, NULL, 0, numbers, nnumbers);
6523                 }
6524         }
6525
6526         ReleaseVariableStats(vardata);
6527
6528         *indexStartupCost = costs.indexStartupCost;
6529         *indexTotalCost = costs.indexTotalCost;
6530         *indexSelectivity = costs.indexSelectivity;
6531         *indexCorrelation = costs.indexCorrelation;
6532
6533         PG_RETURN_VOID();
6534 }
6535
6536 Datum
6537 hashcostestimate(PG_FUNCTION_ARGS)
6538 {
6539         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6540         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6541         double          loop_count = PG_GETARG_FLOAT8(2);
6542         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6543         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6544         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6545         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6546         GenericCosts costs;
6547
6548         MemSet(&costs, 0, sizeof(costs));
6549
6550         genericcostestimate(root, path, loop_count, &costs);
6551
6552         /*
6553          * A hash index has no descent costs as such, since the index AM can go
6554          * directly to the target bucket after computing the hash value.  There
6555          * are a couple of other hash-specific costs that we could conceivably add
6556          * here, though:
6557          *
6558          * Ideally we'd charge spc_random_page_cost for each page in the target
6559          * bucket, not just the numIndexPages pages that genericcostestimate
6560          * thought we'd visit.  However in most cases we don't know which bucket
6561          * that will be.  There's no point in considering the average bucket size
6562          * because the hash AM makes sure that's always one page.
6563          *
6564          * Likewise, we could consider charging some CPU for each index tuple in
6565          * the bucket, if we knew how many there were.  But the per-tuple cost is
6566          * just a hash value comparison, not a general datatype-dependent
6567          * comparison, so any such charge ought to be quite a bit less than
6568          * cpu_operator_cost; which makes it probably not worth worrying about.
6569          *
6570          * A bigger issue is that chance hash-value collisions will result in
6571          * wasted probes into the heap.  We don't currently attempt to model this
6572          * cost on the grounds that it's rare, but maybe it's not rare enough.
6573          * (Any fix for this ought to consider the generic lossy-operator problem,
6574          * though; it's not entirely hash-specific.)
6575          */
6576
6577         *indexStartupCost = costs.indexStartupCost;
6578         *indexTotalCost = costs.indexTotalCost;
6579         *indexSelectivity = costs.indexSelectivity;
6580         *indexCorrelation = costs.indexCorrelation;
6581
6582         PG_RETURN_VOID();
6583 }
6584
6585 Datum
6586 gistcostestimate(PG_FUNCTION_ARGS)
6587 {
6588         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6589         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6590         double          loop_count = PG_GETARG_FLOAT8(2);
6591         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6592         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6593         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6594         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6595         IndexOptInfo *index = path->indexinfo;
6596         GenericCosts costs;
6597         Cost            descentCost;
6598
6599         MemSet(&costs, 0, sizeof(costs));
6600
6601         genericcostestimate(root, path, loop_count, &costs);
6602
6603         /*
6604          * We model index descent costs similarly to those for btree, but to do
6605          * that we first need an idea of the tree height.  We somewhat arbitrarily
6606          * assume that the fanout is 100, meaning the tree height is at most
6607          * log100(index->pages).
6608          *
6609          * Although this computation isn't really expensive enough to require
6610          * caching, we might as well use index->tree_height to cache it.
6611          */
6612         if (index->tree_height < 0)     /* unknown? */
6613         {
6614                 if (index->pages > 1)   /* avoid computing log(0) */
6615                         index->tree_height = (int) (log(index->pages) / log(100.0));
6616                 else
6617                         index->tree_height = 0;
6618         }
6619
6620         /*
6621          * Add a CPU-cost component to represent the costs of initial descent.
6622          * We just use log(N) here not log2(N) since the branching factor isn't
6623          * necessarily two anyway.  As for btree, charge once per SA scan.
6624          */
6625         if (index->tuples > 1)          /* avoid computing log(0) */
6626         {
6627                 descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6628                 costs.indexStartupCost += descentCost;
6629                 costs.indexTotalCost += costs.num_sa_scans * descentCost;
6630         }
6631
6632         /*
6633          * Likewise add a per-page charge, calculated the same as for btrees.
6634          */
6635         descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6636         costs.indexStartupCost += descentCost;
6637         costs.indexTotalCost += costs.num_sa_scans * descentCost;
6638
6639         *indexStartupCost = costs.indexStartupCost;
6640         *indexTotalCost = costs.indexTotalCost;
6641         *indexSelectivity = costs.indexSelectivity;
6642         *indexCorrelation = costs.indexCorrelation;
6643
6644         PG_RETURN_VOID();
6645 }
6646
6647 Datum
6648 spgcostestimate(PG_FUNCTION_ARGS)
6649 {
6650         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
6651         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
6652         double          loop_count = PG_GETARG_FLOAT8(2);
6653         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
6654         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
6655         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
6656         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
6657         IndexOptInfo *index = path->indexinfo;
6658         GenericCosts costs;
6659         Cost            descentCost;
6660
6661         MemSet(&costs, 0, sizeof(costs));
6662
6663         genericcostestimate(root, path, loop_count, &costs);
6664
6665         /*
6666          * We model index descent costs similarly to those for btree, but to do
6667          * that we first need an idea of the tree height.  We somewhat arbitrarily
6668          * assume that the fanout is 100, meaning the tree height is at most
6669          * log100(index->pages).
6670          *
6671          * Although this computation isn't really expensive enough to require
6672          * caching, we might as well use index->tree_height to cache it.
6673          */
6674         if (index->tree_height < 0)     /* unknown? */
6675         {
6676                 if (index->pages > 1)   /* avoid computing log(0) */
6677                         index->tree_height = (int) (log(index->pages) / log(100.0));
6678                 else
6679                         index->tree_height = 0;
6680         }
6681
6682         /*
6683          * Add a CPU-cost component to represent the costs of initial descent.
6684          * We just use log(N) here not log2(N) since the branching factor isn't
6685          * necessarily two anyway.  As for btree, charge once per SA scan.
6686          */
6687         if (index->tuples > 1)          /* avoid computing log(0) */
6688         {
6689                 descentCost = ceil(log(index->tuples)) * cpu_operator_cost;
6690                 costs.indexStartupCost += descentCost;
6691                 costs.indexTotalCost += costs.num_sa_scans * descentCost;
6692         }
6693
6694         /*
6695          * Likewise add a per-page charge, calculated the same as for btrees.
6696          */
6697         descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
6698         costs.indexStartupCost += descentCost;
6699         costs.indexTotalCost += costs.num_sa_scans * descentCost;
6700
6701         *indexStartupCost = costs.indexStartupCost;
6702         *indexTotalCost = costs.indexTotalCost;
6703         *indexSelectivity = costs.indexSelectivity;
6704         *indexCorrelation = costs.indexCorrelation;
6705
6706         PG_RETURN_VOID();
6707 }
6708
6709
6710 /*
6711  * Support routines for gincostestimate
6712  */
6713
6714 typedef struct
6715 {
6716         bool            haveFullScan;
6717         double          partialEntries;
6718         double          exactEntries;
6719         double          searchEntries;
6720         double          arrayScans;
6721 } GinQualCounts;
6722
6723 /* Find the index column matching "op"; return its index, or -1 if no match */
6724 static int
6725 find_index_column(Node *op, IndexOptInfo *index)
6726 {
6727         int                     i;
6728
6729         for (i = 0; i < index->ncolumns; i++)
6730         {
6731                 if (match_index_to_operand(op, i, index))
6732                         return i;
6733         }
6734
6735         return -1;
6736 }
6737
6738 /*
6739  * Estimate the number of index terms that need to be searched for while
6740  * testing the given GIN query, and increment the counts in *counts
6741  * appropriately.  If the query is unsatisfiable, return false.
6742  */
6743 static bool
6744 gincost_pattern(IndexOptInfo *index, int indexcol,
6745                                 Oid clause_op, Datum query,
6746                                 GinQualCounts *counts)
6747 {
6748         Oid                     extractProcOid;
6749         int                     strategy_op;
6750         Oid                     lefttype,
6751                                 righttype;
6752         int32           nentries = 0;
6753         bool       *partial_matches = NULL;
6754         Pointer    *extra_data = NULL;
6755         bool       *nullFlags = NULL;
6756         int32           searchMode = GIN_SEARCH_MODE_DEFAULT;
6757         int32           i;
6758
6759         /*
6760          * Get the operator's strategy number and declared input data types within
6761          * the index opfamily.  (We don't need the latter, but we use
6762          * get_op_opfamily_properties because it will throw error if it fails to
6763          * find a matching pg_amop entry.)
6764          */
6765         get_op_opfamily_properties(clause_op, index->opfamily[indexcol], false,
6766                                                            &strategy_op, &lefttype, &righttype);
6767
6768         /*
6769          * GIN always uses the "default" support functions, which are those with
6770          * lefttype == righttype == the opclass' opcintype (see
6771          * IndexSupportInitialize in relcache.c).
6772          */
6773         extractProcOid = get_opfamily_proc(index->opfamily[indexcol],
6774                                                                            index->opcintype[indexcol],
6775                                                                            index->opcintype[indexcol],
6776                                                                            GIN_EXTRACTQUERY_PROC);
6777
6778         if (!OidIsValid(extractProcOid))
6779         {
6780                 /* should not happen; throw same error as index_getprocinfo */
6781                 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
6782                          GIN_EXTRACTQUERY_PROC, indexcol + 1,
6783                          get_rel_name(index->indexoid));
6784         }
6785
6786         OidFunctionCall7(extractProcOid,
6787                                          query,
6788                                          PointerGetDatum(&nentries),
6789                                          UInt16GetDatum(strategy_op),
6790                                          PointerGetDatum(&partial_matches),
6791                                          PointerGetDatum(&extra_data),
6792                                          PointerGetDatum(&nullFlags),
6793                                          PointerGetDatum(&searchMode));
6794
6795         if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)
6796         {
6797                 /* No match is possible */
6798                 return false;
6799         }
6800
6801         for (i = 0; i < nentries; i++)
6802         {
6803                 /*
6804                  * For partial match we haven't any information to estimate number of
6805                  * matched entries in index, so, we just estimate it as 100
6806                  */
6807                 if (partial_matches && partial_matches[i])
6808                         counts->partialEntries += 100;
6809                 else
6810                         counts->exactEntries++;
6811
6812                 counts->searchEntries++;
6813         }
6814
6815         if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
6816         {
6817                 /* Treat "include empty" like an exact-match item */
6818                 counts->exactEntries++;
6819                 counts->searchEntries++;
6820         }
6821         else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
6822         {
6823                 /* It's GIN_SEARCH_MODE_ALL */
6824                 counts->haveFullScan = true;
6825         }
6826
6827         return true;
6828 }
6829
6830 /*
6831  * Estimate the number of index terms that need to be searched for while
6832  * testing the given GIN index clause, and increment the counts in *counts
6833  * appropriately.  If the query is unsatisfiable, return false.
6834  */
6835 static bool
6836 gincost_opexpr(IndexOptInfo *index, OpExpr *clause, GinQualCounts *counts)
6837 {
6838         Node       *leftop = get_leftop((Expr *) clause);
6839         Node       *rightop = get_rightop((Expr *) clause);
6840         Oid                     clause_op = clause->opno;
6841         int                     indexcol;
6842         Node       *operand;
6843
6844         /* Locate the operand being compared to the index column */
6845         if ((indexcol = find_index_column(leftop, index)) >= 0)
6846         {
6847                 operand = rightop;
6848         }
6849         else if ((indexcol = find_index_column(rightop, index)) >= 0)
6850         {
6851                 operand = leftop;
6852                 clause_op = get_commutator(clause_op);
6853         }
6854         else
6855         {
6856                 elog(ERROR, "could not match index to operand");
6857                 operand = NULL;                 /* keep compiler quiet */
6858         }
6859
6860         if (IsA(operand, RelabelType))
6861                 operand = (Node *) ((RelabelType *) operand)->arg;
6862
6863         /*
6864          * It's impossible to call extractQuery method for unknown operand. So
6865          * unless operand is a Const we can't do much; just assume there will be
6866          * one ordinary search entry from the operand at runtime.
6867          */
6868         if (!IsA(operand, Const))
6869         {
6870                 counts->exactEntries++;
6871                 counts->searchEntries++;
6872                 return true;
6873         }
6874
6875         /* If Const is null, there can be no matches */
6876         if (((Const *) operand)->constisnull)
6877                 return false;
6878
6879         /* Otherwise, apply extractQuery and get the actual term counts */
6880         return gincost_pattern(index, indexcol, clause_op,
6881                                                    ((Const *) operand)->constvalue,
6882                                                    counts);
6883 }
6884
6885 /*
6886  * Estimate the number of index terms that need to be searched for while
6887  * testing the given GIN index clause, and increment the counts in *counts
6888  * appropriately.  If the query is unsatisfiable, return false.
6889  *
6890  * A ScalarArrayOpExpr will give rise to N separate indexscans at runtime,
6891  * each of which involves one value from the RHS array, plus all the
6892  * non-array quals (if any).  To model this, we average the counts across
6893  * the RHS elements, and add the averages to the counts in *counts (which
6894  * correspond to per-indexscan costs).  We also multiply counts->arrayScans
6895  * by N, causing gincostestimate to scale up its estimates accordingly.
6896  */
6897 static bool
6898 gincost_scalararrayopexpr(IndexOptInfo *index, ScalarArrayOpExpr *clause,
6899                                                   double numIndexEntries,
6900                                                   GinQualCounts *counts)
6901 {
6902         Node       *leftop = (Node *) linitial(clause->args);
6903         Node       *rightop = (Node *) lsecond(clause->args);
6904         Oid                     clause_op = clause->opno;
6905         int                     indexcol;
6906         ArrayType  *arrayval;
6907         int16           elmlen;
6908         bool            elmbyval;
6909         char            elmalign;
6910         int                     numElems;
6911         Datum      *elemValues;
6912         bool       *elemNulls;
6913         GinQualCounts arraycounts;
6914         int                     numPossible = 0;
6915         int                     i;
6916
6917         Assert(clause->useOr);
6918
6919         /* index column must be on the left */
6920         if ((indexcol = find_index_column(leftop, index)) < 0)
6921                 elog(ERROR, "could not match index to operand");
6922
6923         if (IsA(rightop, RelabelType))
6924                 rightop = (Node *) ((RelabelType *) rightop)->arg;
6925
6926         /*
6927          * It's impossible to call extractQuery method for unknown operand. So
6928          * unless operand is a Const we can't do much; just assume there will be
6929          * one ordinary search entry from each array entry at runtime, and fall
6930          * back on a probably-bad estimate of the number of array entries.
6931          */
6932         if (!IsA(rightop, Const))
6933         {
6934                 counts->exactEntries++;
6935                 counts->searchEntries++;
6936                 counts->arrayScans *= estimate_array_length(rightop);
6937                 return true;
6938         }
6939
6940         /* If Const is null, there can be no matches */
6941         if (((Const *) rightop)->constisnull)
6942                 return false;
6943
6944         /* Otherwise, extract the array elements and iterate over them */
6945         arrayval = DatumGetArrayTypeP(((Const *) rightop)->constvalue);
6946         get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
6947                                                  &elmlen, &elmbyval, &elmalign);
6948         deconstruct_array(arrayval,
6949                                           ARR_ELEMTYPE(arrayval),
6950                                           elmlen, elmbyval, elmalign,
6951                                           &elemValues, &elemNulls, &numElems);
6952
6953         memset(&arraycounts, 0, sizeof(arraycounts));
6954
6955         for (i = 0; i < numElems; i++)
6956         {
6957                 GinQualCounts elemcounts;
6958
6959                 /* NULL can't match anything, so ignore, as the executor will */
6960                 if (elemNulls[i])
6961                         continue;
6962
6963                 /* Otherwise, apply extractQuery and get the actual term counts */
6964                 memset(&elemcounts, 0, sizeof(elemcounts));
6965
6966                 if (gincost_pattern(index, indexcol, clause_op, elemValues[i],
6967                                                         &elemcounts))
6968                 {
6969                         /* We ignore array elements that are unsatisfiable patterns */
6970                         numPossible++;
6971
6972                         if (elemcounts.haveFullScan)
6973                         {
6974                                 /*
6975                                  * Full index scan will be required.  We treat this as if
6976                                  * every key in the index had been listed in the query; is
6977                                  * that reasonable?
6978                                  */
6979                                 elemcounts.partialEntries = 0;
6980                                 elemcounts.exactEntries = numIndexEntries;
6981                                 elemcounts.searchEntries = numIndexEntries;
6982                         }
6983                         arraycounts.partialEntries += elemcounts.partialEntries;
6984                         arraycounts.exactEntries += elemcounts.exactEntries;
6985                         arraycounts.searchEntries += elemcounts.searchEntries;
6986                 }
6987         }
6988
6989         if (numPossible == 0)
6990         {
6991                 /* No satisfiable patterns in the array */
6992                 return false;
6993         }
6994
6995         /*
6996          * Now add the averages to the global counts.  This will give us an
6997          * estimate of the average number of terms searched for in each indexscan,
6998          * including contributions from both array and non-array quals.
6999          */
7000         counts->partialEntries += arraycounts.partialEntries / numPossible;
7001         counts->exactEntries += arraycounts.exactEntries / numPossible;
7002         counts->searchEntries += arraycounts.searchEntries / numPossible;
7003
7004         counts->arrayScans *= numPossible;
7005
7006         return true;
7007 }
7008
7009 /*
7010  * GIN has search behavior completely different from other index types
7011  */
7012 Datum
7013 gincostestimate(PG_FUNCTION_ARGS)
7014 {
7015         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
7016         IndexPath  *path = (IndexPath *) PG_GETARG_POINTER(1);
7017         double          loop_count = PG_GETARG_FLOAT8(2);
7018         Cost       *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
7019         Cost       *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
7020         Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
7021         double     *indexCorrelation = (double *) PG_GETARG_POINTER(6);
7022         IndexOptInfo *index = path->indexinfo;
7023         List       *indexQuals = path->indexquals;
7024         List       *indexOrderBys = path->indexorderbys;
7025         ListCell   *l;
7026         List       *selectivityQuals;
7027         double          numPages = index->pages,
7028                                 numTuples = index->tuples;
7029         double          numEntryPages,
7030                                 numDataPages,
7031                                 numPendingPages,
7032                                 numEntries;
7033         GinQualCounts counts;
7034         bool            matchPossible;
7035         double          entryPagesFetched,
7036                                 dataPagesFetched,
7037                                 dataPagesFetchedBySel;
7038         double          qual_op_cost,
7039                                 qual_arg_cost,
7040                                 spc_random_page_cost,
7041                                 outer_scans;
7042         QualCost        index_qual_cost;
7043         Relation        indexRel;
7044         GinStatsData ginStats;
7045
7046         /*
7047          * Obtain statistic information from the meta page
7048          */
7049         indexRel = index_open(index->indexoid, AccessShareLock);
7050         ginGetStats(indexRel, &ginStats);
7051         index_close(indexRel, AccessShareLock);
7052
7053         numEntryPages = ginStats.nEntryPages;
7054         numDataPages = ginStats.nDataPages;
7055         numPendingPages = ginStats.nPendingPages;
7056         numEntries = ginStats.nEntries;
7057
7058         /*
7059          * nPendingPages can be trusted, but the other fields are as of the last
7060          * VACUUM.      Scale them by the ratio numPages / nTotalPages to account for
7061          * growth since then.  If the fields are zero (implying no VACUUM at all,
7062          * and an index created pre-9.1), assume all pages are entry pages.
7063          */
7064         if (ginStats.nTotalPages == 0 || ginStats.nEntryPages == 0)
7065         {
7066                 numEntryPages = numPages;
7067                 numDataPages = 0;
7068                 numEntries = numTuples; /* bogus, but no other info available */
7069         }
7070         else
7071         {
7072                 double          scale = numPages / ginStats.nTotalPages;
7073
7074                 numEntryPages = ceil(numEntryPages * scale);
7075                 numDataPages = ceil(numDataPages * scale);
7076                 numEntries = ceil(numEntries * scale);
7077                 /* ensure we didn't round up too much */
7078                 numEntryPages = Min(numEntryPages, numPages);
7079                 numDataPages = Min(numDataPages, numPages - numEntryPages);
7080         }
7081
7082         /* In an empty index, numEntries could be zero.  Avoid divide-by-zero */
7083         if (numEntries < 1)
7084                 numEntries = 1;
7085
7086         /*
7087          * Include predicate in selectivityQuals (should match
7088          * genericcostestimate)
7089          */
7090         if (index->indpred != NIL)
7091         {
7092                 List       *predExtraQuals = NIL;
7093
7094                 foreach(l, index->indpred)
7095                 {
7096                         Node       *predQual = (Node *) lfirst(l);
7097                         List       *oneQual = list_make1(predQual);
7098
7099                         if (!predicate_implied_by(oneQual, indexQuals))
7100                                 predExtraQuals = list_concat(predExtraQuals, oneQual);
7101                 }
7102                 /* list_concat avoids modifying the passed-in indexQuals list */
7103                 selectivityQuals = list_concat(predExtraQuals, indexQuals);
7104         }
7105         else
7106                 selectivityQuals = indexQuals;
7107
7108         /* Estimate the fraction of main-table tuples that will be visited */
7109         *indexSelectivity = clauselist_selectivity(root, selectivityQuals,
7110                                                                                            index->rel->relid,
7111                                                                                            JOIN_INNER,
7112                                                                                            NULL);
7113
7114         /* fetch estimated page cost for schema containing index */
7115         get_tablespace_page_costs(index->reltablespace,
7116                                                           &spc_random_page_cost,
7117                                                           NULL);
7118
7119         /*
7120          * Generic assumption about index correlation: there isn't any.
7121          */
7122         *indexCorrelation = 0.0;
7123
7124         /*
7125          * Examine quals to estimate number of search entries & partial matches
7126          */
7127         memset(&counts, 0, sizeof(counts));
7128         counts.arrayScans = 1;
7129         matchPossible = true;
7130
7131         foreach(l, indexQuals)
7132         {
7133                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
7134                 Expr       *clause;
7135
7136                 Assert(IsA(rinfo, RestrictInfo));
7137                 clause = rinfo->clause;
7138                 if (IsA(clause, OpExpr))
7139                 {
7140                         matchPossible = gincost_opexpr(index,
7141                                                                                    (OpExpr *) clause,
7142                                                                                    &counts);
7143                         if (!matchPossible)
7144                                 break;
7145                 }
7146                 else if (IsA(clause, ScalarArrayOpExpr))
7147                 {
7148                         matchPossible = gincost_scalararrayopexpr(index,
7149                                                                                                 (ScalarArrayOpExpr *) clause,
7150                                                                                                           numEntries,
7151                                                                                                           &counts);
7152                         if (!matchPossible)
7153                                 break;
7154                 }
7155                 else
7156                 {
7157                         /* shouldn't be anything else for a GIN index */
7158                         elog(ERROR, "unsupported GIN indexqual type: %d",
7159                                  (int) nodeTag(clause));
7160                 }
7161         }
7162
7163         /* Fall out if there were any provably-unsatisfiable quals */
7164         if (!matchPossible)
7165         {
7166                 *indexStartupCost = 0;
7167                 *indexTotalCost = 0;
7168                 *indexSelectivity = 0;
7169                 PG_RETURN_VOID();
7170         }
7171
7172         if (counts.haveFullScan || indexQuals == NIL)
7173         {
7174                 /*
7175                  * Full index scan will be required.  We treat this as if every key in
7176                  * the index had been listed in the query; is that reasonable?
7177                  */
7178                 counts.partialEntries = 0;
7179                 counts.exactEntries = numEntries;
7180                 counts.searchEntries = numEntries;
7181         }
7182
7183         /* Will we have more than one iteration of a nestloop scan? */
7184         outer_scans = loop_count;
7185
7186         /*
7187          * Compute cost to begin scan, first of all, pay attention to pending
7188          * list.
7189          */
7190         entryPagesFetched = numPendingPages;
7191
7192         /*
7193          * Estimate number of entry pages read.  We need to do
7194          * counts.searchEntries searches.  Use a power function as it should be,
7195          * but tuples on leaf pages usually is much greater. Here we include all
7196          * searches in entry tree, including search of first entry in partial
7197          * match algorithm
7198          */
7199         entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
7200
7201         /*
7202          * Add an estimate of entry pages read by partial match algorithm. It's a
7203          * scan over leaf pages in entry tree.  We haven't any useful stats here,
7204          * so estimate it as proportion.
7205          */
7206         entryPagesFetched += ceil(numEntryPages * counts.partialEntries / numEntries);
7207
7208         /*
7209          * Partial match algorithm reads all data pages before doing actual scan,
7210          * so it's a startup cost. Again, we haven't any useful stats here, so,
7211          * estimate it as proportion
7212          */
7213         dataPagesFetched = ceil(numDataPages * counts.partialEntries / numEntries);
7214
7215         /*
7216          * Calculate cache effects if more than one scan due to nestloops or array
7217          * quals.  The result is pro-rated per nestloop scan, but the array qual
7218          * factor shouldn't be pro-rated (compare genericcostestimate).
7219          */
7220         if (outer_scans > 1 || counts.arrayScans > 1)
7221         {
7222                 entryPagesFetched *= outer_scans * counts.arrayScans;
7223                 entryPagesFetched = index_pages_fetched(entryPagesFetched,
7224                                                                                                 (BlockNumber) numEntryPages,
7225                                                                                                 numEntryPages, root);
7226                 entryPagesFetched /= outer_scans;
7227                 dataPagesFetched *= outer_scans * counts.arrayScans;
7228                 dataPagesFetched = index_pages_fetched(dataPagesFetched,
7229                                                                                            (BlockNumber) numDataPages,
7230                                                                                            numDataPages, root);
7231                 dataPagesFetched /= outer_scans;
7232         }
7233
7234         /*
7235          * Here we use random page cost because logically-close pages could be far
7236          * apart on disk.
7237          */
7238         *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
7239
7240         /*
7241          * Now we compute the number of data pages fetched while the scan
7242          * proceeds.
7243          */
7244
7245         /* data pages scanned for each exact (non-partial) matched entry */
7246         dataPagesFetched = ceil(numDataPages * counts.exactEntries / numEntries);
7247
7248         /*
7249          * Estimate number of data pages read, using selectivity estimation and
7250          * capacity of data page.
7251          */
7252         dataPagesFetchedBySel = ceil(*indexSelectivity *
7253                                                                  (numTuples / (BLCKSZ / SizeOfIptrData)));
7254
7255         if (dataPagesFetchedBySel > dataPagesFetched)
7256         {
7257                 /*
7258                  * At least one of entries is very frequent and, unfortunately, we
7259                  * couldn't get statistic about entries (only tsvector has such
7260                  * statistics). So, we obviously have too small estimation of pages
7261                  * fetched from data tree. Re-estimate it from known capacity of data
7262                  * pages
7263                  */
7264                 dataPagesFetched = dataPagesFetchedBySel;
7265         }
7266
7267         /* Account for cache effects, the same as above */
7268         if (outer_scans > 1 || counts.arrayScans > 1)
7269         {
7270                 dataPagesFetched *= outer_scans * counts.arrayScans;
7271                 dataPagesFetched = index_pages_fetched(dataPagesFetched,
7272                                                                                            (BlockNumber) numDataPages,
7273                                                                                            numDataPages, root);
7274                 dataPagesFetched /= outer_scans;
7275         }
7276
7277         /* And apply random_page_cost as the cost per page */
7278         *indexTotalCost = *indexStartupCost +
7279                 dataPagesFetched * spc_random_page_cost;
7280
7281         /*
7282          * Add on index qual eval costs, much as in genericcostestimate
7283          */
7284         cost_qual_eval(&index_qual_cost, indexQuals, root);
7285         qual_arg_cost = index_qual_cost.startup + index_qual_cost.per_tuple;
7286         cost_qual_eval(&index_qual_cost, indexOrderBys, root);
7287         qual_arg_cost += index_qual_cost.startup + index_qual_cost.per_tuple;
7288         qual_op_cost = cpu_operator_cost *
7289                 (list_length(indexQuals) + list_length(indexOrderBys));
7290         qual_arg_cost -= qual_op_cost;
7291         if (qual_arg_cost < 0)          /* just in case... */
7292                 qual_arg_cost = 0;
7293
7294         *indexStartupCost += qual_arg_cost;
7295         *indexTotalCost += qual_arg_cost;
7296         *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
7297
7298         PG_RETURN_VOID();
7299 }