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