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