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