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