granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/indxpath.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * indxpath.c
   4  *        Routines to determine which indices are usable for scanning a
   5  *        given relation, and create IndexPaths accordingly.
   6  *
   7  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.153 2004/01/04 03:51:52 tgl Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17
  18 #include <math.h>
  19
  20 #include "access/nbtree.h"
  21 #include "catalog/pg_amop.h"
  22 #include "catalog/pg_namespace.h"
  23 #include "catalog/pg_opclass.h"
  24 #include "catalog/pg_operator.h"
  25 #include "catalog/pg_type.h"
  26 #include "executor/executor.h"
  27 #include "nodes/makefuncs.h"
  28 #include "optimizer/clauses.h"
  29 #include "optimizer/cost.h"
  30 #include "optimizer/pathnode.h"
  31 #include "optimizer/paths.h"
  32 #include "optimizer/restrictinfo.h"
  33 #include "optimizer/var.h"
  34 #include "parser/parse_expr.h"
  35 #include "rewrite/rewriteManip.h"
  36 #include "utils/builtins.h"
  37 #include "utils/catcache.h"
  38 #include "utils/lsyscache.h"
  39 #include "utils/pg_locale.h"
  40 #include "utils/selfuncs.h"
  41 #include "utils/syscache.h"
  42
  43
  44 /*
  45  * DoneMatchingIndexKeys() - MACRO
  46  */
  47 #define DoneMatchingIndexKeys(classes)  (classes[0] == InvalidOid)
  48
  49 #define is_indexable_operator(clause,opclass,indexkey_on_left) \
  50         (indexable_operator(clause,opclass,indexkey_on_left) != InvalidOid)
  51
  52
  53 static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index);
  54 static List *group_clauses_by_indexkey_for_join(Query *root,
  55                                                                    RelOptInfo *rel, IndexOptInfo *index,
  56                                                                    Relids outer_relids,
  57                                                                    JoinType jointype, bool isouterjoin);
  58 static bool match_clause_to_indexcol(RelOptInfo *rel, IndexOptInfo *index,
  59                                                                          int indexcol, Oid opclass,
  60                                                                          RestrictInfo *rinfo);
  61 static bool match_join_clause_to_indexcol(RelOptInfo *rel, IndexOptInfo *index,
  62                                                                                   int indexcol, Oid opclass,
  63                                                                                   RestrictInfo *rinfo);
  64 static Oid indexable_operator(Expr *clause, Oid opclass,
  65                                    bool indexkey_on_left);
  66 static bool pred_test(List *predicate_list, List *restrictinfo_list,
  67                   List *joininfo_list);
  68 static bool pred_test_restrict_list(Expr *predicate, List *restrictinfo_list);
  69 static bool pred_test_recurse_clause(Expr *predicate, Node *clause);
  70 static bool pred_test_recurse_pred(Expr *predicate, Node *clause);
  71 static bool pred_test_simple_clause(Expr *predicate, Node *clause);
  72 static Relids indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index);
  73 static Path *make_innerjoin_index_path(Query *root,
  74                                                   RelOptInfo *rel, IndexOptInfo *index,
  75                                                   List *clausegroups);
  76 static bool match_index_to_operand(Node *operand, int indexcol,
  77                                            RelOptInfo *rel, IndexOptInfo *index);
  78 static bool match_special_index_operator(Expr *clause, Oid opclass,
  79                                                          bool indexkey_on_left);
  80 static List *expand_indexqual_condition(Expr *clause, Oid opclass);
  81 static List *prefix_quals(Node *leftop, Oid opclass,
  82                          Const *prefix, Pattern_Prefix_Status pstatus);
  83 static List *network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass,
  84                                          Datum rightop);
  85 static Datum string_to_datum(const char *str, Oid datatype);
  86 static Const *string_to_const(const char *str, Oid datatype);
  87
  88
  89 /*
  90  * create_index_paths()
  91  *        Generate all interesting index paths for the given relation.
  92  *        Candidate paths are added to the rel's pathlist (using add_path).
  93  *
  94  * To be considered for an index scan, an index must match one or more
  95  * restriction clauses or join clauses from the query's qual condition,
  96  * or match the query's ORDER BY condition.
  97  *
  98  * There are two basic kinds of index scans.  A "plain" index scan uses
  99  * only restriction clauses (possibly none at all) in its indexqual,
 100  * so it can be applied in any context.  An "innerjoin" index scan uses
 101  * join clauses (plus restriction clauses, if available) in its indexqual.
 102  * Therefore it can only be used as the inner relation of a nestloop
 103  * join against an outer rel that includes all the other rels mentioned
 104  * in its join clauses.  In that context, values for the other rels'
 105  * attributes are available and fixed during any one scan of the indexpath.
 106  *
 107  * An IndexPath is generated and submitted to add_path() for each plain index
 108  * scan this routine deems potentially interesting for the current query.
 109  *
 110  * We also determine the set of other relids that participate in join
 111  * clauses that could be used with each index.  The actually best innerjoin
 112  * path will be generated for each outer relation later on, but knowing the
 113  * set of potential otherrels allows us to identify equivalent outer relations
 114  * and avoid repeated computation.
 115  *
 116  * 'rel' is the relation for which we want to generate index paths
 117  */
 118 void
 119 create_index_paths(Query *root, RelOptInfo *rel)
 120 {
 121         List       *restrictinfo_list = rel->baserestrictinfo;
 122         List       *joininfo_list = rel->joininfo;
 123         Relids          all_join_outerrelids = NULL;
 124         List       *ilist;
 125
 126         foreach(ilist, rel->indexlist)
 127         {
 128                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
 129                 List       *restrictclauses;
 130                 List       *index_pathkeys;
 131                 List       *useful_pathkeys;
 132                 bool            index_is_ordered;
 133                 Relids          join_outerrelids;
 134
 135                 /*
 136                  * If this is a partial index, we can only use it if it passes the
 137                  * predicate test.
 138                  */
 139                 if (index->indpred != NIL)
 140                 {
 141                         if (!pred_test(index->indpred, restrictinfo_list, joininfo_list))
 142                                 continue;
 143                         index->predOK = true; /* set flag for orindxpaths.c */
 144                 }
 145
 146                 /*
 147                  * 1. Match the index against non-OR restriction clauses.
 148                  * (OR clauses will be considered later by orindxpath.c.)
 149                  */
 150                 restrictclauses = group_clauses_by_indexkey(rel, index);
 151
 152                 /*
 153                  * 2. Compute pathkeys describing index's ordering, if any, then
 154                  * see how many of them are actually useful for this query.
 155                  */
 156                 index_pathkeys = build_index_pathkeys(root, rel, index,
 157                                                                                           ForwardScanDirection);
 158                 index_is_ordered = (index_pathkeys != NIL);
 159                 useful_pathkeys = truncate_useless_pathkeys(root, rel,
 160                                                                                                         index_pathkeys);
 161
 162                 /*
 163                  * 3. Generate an indexscan path if there are relevant restriction
 164                  * clauses OR the index ordering is potentially useful for later
 165                  * merging or final output ordering.
 166                  *
 167                  * If there is a predicate, consider it anyway since the index
 168                  * predicate has already been found to match the query.  The
 169                  * selectivity of the predicate might alone make the index useful.
 170                  */
 171                 if (restrictclauses != NIL ||
 172                         useful_pathkeys != NIL ||
 173                         index->indpred != NIL)
 174                         add_path(rel, (Path *)
 175                                          create_index_path(root, rel, index,
 176                                                                            restrictclauses,
 177                                                                            useful_pathkeys,
 178                                                                            index_is_ordered ?
 179                                                                            ForwardScanDirection :
 180                                                                            NoMovementScanDirection));
 181
 182                 /*
 183                  * 4. If the index is ordered, a backwards scan might be
 184                  * interesting. Currently this is only possible for a DESC query
 185                  * result ordering.
 186                  */
 187                 if (index_is_ordered)
 188                 {
 189                         index_pathkeys = build_index_pathkeys(root, rel, index,
 190                                                                                                   BackwardScanDirection);
 191                         useful_pathkeys = truncate_useless_pathkeys(root, rel,
 192                                                                                                                 index_pathkeys);
 193                         if (useful_pathkeys != NIL)
 194                                 add_path(rel, (Path *)
 195                                                  create_index_path(root, rel, index,
 196                                                                                    restrictclauses,
 197                                                                                    useful_pathkeys,
 198                                                                                    BackwardScanDirection));
 199                 }
 200
 201                 /*
 202                  * 5. Examine join clauses to see which ones are potentially
 203                  * usable with this index, and generate the set of all other
 204                  * relids that participate in such join clauses.  We'll use this
 205                  * set later to recognize outer rels that are equivalent for
 206                  * joining purposes. We compute both per-index and
 207                  * overall-for-relation sets.
 208                  */
 209                 join_outerrelids = indexable_outerrelids(rel, index);
 210                 index->outer_relids = join_outerrelids;
 211                 all_join_outerrelids = bms_add_members(all_join_outerrelids,
 212                                                                                            join_outerrelids);
 213         }
 214
 215         rel->index_outer_relids = all_join_outerrelids;
 216 }
 217
 218
 219 /****************************************************************************
 220  *                              ----  ROUTINES TO CHECK RESTRICTIONS  ----
 221  ****************************************************************************/
 222
 223
 224 /*
 225  * group_clauses_by_indexkey
 226  *        Find restriction clauses that can be used with an index.
 227  *
 228  * 'rel' is the node of the relation itself.
 229  * 'index' is a index on 'rel'.
 230  *
 231  * Returns a list of sublists of RestrictInfo nodes for clauses that can be
 232  * used with this index.  Each sublist contains clauses that can be used
 233  * with one index key (in no particular order); the top list is ordered by
 234  * index key.  (This is depended on by expand_indexqual_conditions().)
 235  *
 236  * Note that in a multi-key index, we stop if we find a key that cannot be
 237  * used with any clause.  For example, given an index on (A,B,C), we might
 238  * return ((C1 C2) (C3 C4)) if we find that clauses C1 and C2 use column A,
 239  * clauses C3 and C4 use column B, and no clauses use column C.  But if
 240  * no clauses match B we will return ((C1 C2)), whether or not there are
 241  * clauses matching column C, because the executor couldn't use them anyway.
 242  * Therefore, there are no empty sublists in the result.
 243  */
 244 static List *
 245 group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index)
 246 {
 247         FastList        clausegroup_list;
 248         List       *restrictinfo_list = rel->baserestrictinfo;
 249         int                     indexcol = 0;
 250         Oid                *classes = index->classlist;
 251
 252         if (restrictinfo_list == NIL)
 253                 return NIL;
 254
 255         FastListInit(&clausegroup_list);
 256         do
 257         {
 258                 Oid                     curClass = classes[0];
 259                 FastList        clausegroup;
 260                 List       *i;
 261
 262                 FastListInit(&clausegroup);
 263                 foreach(i, restrictinfo_list)
 264                 {
 265                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
 266
 267                         if (match_clause_to_indexcol(rel,
 268                                                                                  index,
 269                                                                                  indexcol,
 270                                                                                  curClass,
 271                                                                                  rinfo))
 272                                 FastAppend(&clausegroup, rinfo);
 273                 }
 274
 275                 /*
 276                  * If no clauses match this key, we're done; we don't want to look
 277                  * at keys to its right.
 278                  */
 279                 if (FastListValue(&clausegroup) == NIL)
 280                         break;
 281
 282                 FastAppend(&clausegroup_list, FastListValue(&clausegroup));
 283
 284                 indexcol++;
 285                 classes++;
 286
 287         } while (!DoneMatchingIndexKeys(classes));
 288
 289         return FastListValue(&clausegroup_list);
 290 }
 291
 292 /*
 293  * group_clauses_by_indexkey_for_join
 294  *        Generate a list of sublists of clauses that can be used with an index
 295  *        to scan the inner side of a nestloop join.
 296  *
 297  * This is much like group_clauses_by_indexkey(), but we consider both
 298  * join and restriction clauses.  Any joinclause that uses only otherrels
 299  * in the specified outer_relids is fair game.  But there must be at least
 300  * one such joinclause in the final list, otherwise we return NIL indicating
 301  * that this index isn't interesting as an inner indexscan.  (A scan using
 302  * only restriction clauses shouldn't be created here, because a regular Path
 303  * will already have been generated for it.)
 304  */
 305 static List *
 306 group_clauses_by_indexkey_for_join(Query *root,
 307                                                                    RelOptInfo *rel, IndexOptInfo *index,
 308                                                                    Relids outer_relids,
 309                                                                    JoinType jointype, bool isouterjoin)
 310 {
 311         FastList        clausegroup_list;
 312         bool            jfound = false;
 313         int                     indexcol = 0;
 314         Oid                *classes = index->classlist;
 315
 316         FastListInit(&clausegroup_list);
 317         do
 318         {
 319                 Oid                     curClass = classes[0];
 320                 FastList        clausegroup;
 321                 int                     numsources;
 322                 List       *i;
 323
 324                 FastListInit(&clausegroup);
 325
 326                 /*
 327                  * We can always use plain restriction clauses for the rel.  We scan
 328                  * these first because we want them first in the clausegroup list
 329                  * for the convenience of remove_redundant_join_clauses, which can
 330                  * never remove non-join clauses and hence won't be able to get rid
 331                  * of a non-join clause if it appears after a join clause it is
 332                  * redundant with.
 333                  */
 334                 foreach(i, rel->baserestrictinfo)
 335                 {
 336                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
 337
 338                         /* Can't use pushed-down clauses in outer join */
 339                         if (isouterjoin && rinfo->ispusheddown)
 340                                 continue;
 341
 342                         if (match_clause_to_indexcol(rel,
 343                                                                                  index,
 344                                                                                  indexcol,
 345                                                                                  curClass,
 346                                                                                  rinfo))
 347                                 FastAppend(&clausegroup, rinfo);
 348                 }
 349
 350                 /* found anything in base restrict list? */
 351                 numsources = (FastListValue(&clausegroup) != NIL) ? 1 : 0;
 352
 353                 /* Look for joinclauses that are usable with given outer_relids */
 354                 foreach(i, rel->joininfo)
 355                 {
 356                         JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
 357                         bool            jfoundhere = false;
 358                         List       *j;
 359
 360                         if (!bms_is_subset(joininfo->unjoined_relids, outer_relids))
 361                                 continue;
 362
 363                         foreach(j, joininfo->jinfo_restrictinfo)
 364                         {
 365                                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
 366
 367                                 /* Can't use pushed-down clauses in outer join */
 368                                 if (isouterjoin && rinfo->ispusheddown)
 369                                         continue;
 370
 371                                 if (match_join_clause_to_indexcol(rel,
 372                                                                                                   index,
 373                                                                                                   indexcol,
 374                                                                                                   curClass,
 375                                                                                                   rinfo))
 376                                 {
 377                                         FastAppend(&clausegroup, rinfo);
 378                                         if (!jfoundhere)
 379                                         {
 380                                                 jfoundhere = true;
 381                                                 jfound = true;
 382                                                 numsources++;
 383                                         }
 384                                 }
 385                         }
 386                 }
 387
 388                 /*
 389                  * If we found clauses in more than one list, we may now have clauses
 390                  * that are known redundant.  Get rid of 'em.
 391                  */
 392                 if (numsources > 1)
 393                 {
 394                         List       *nl;
 395
 396                         nl = remove_redundant_join_clauses(root,
 397                                                                                          FastListValue(&clausegroup),
 398                                                                                            jointype);
 399                         FastListFromList(&clausegroup, nl);
 400                 }
 401
 402                 /*
 403                  * If no clauses match this key, we're done; we don't want to look
 404                  * at keys to its right.
 405                  */
 406                 if (FastListValue(&clausegroup) == NIL)
 407                         break;
 408
 409                 FastAppend(&clausegroup_list, FastListValue(&clausegroup));
 410
 411                 indexcol++;
 412                 classes++;
 413
 414         } while (!DoneMatchingIndexKeys(classes));
 415
 416         /* if no join clause was matched then forget it, per comments above */
 417         if (!jfound)
 418                 return NIL;
 419
 420         return FastListValue(&clausegroup_list);
 421 }
 422
 423
 424 /*
 425  * group_clauses_by_indexkey_for_or
 426  *        Generate a list of sublists of clauses that can be used with an index
 427  *        to find rows matching an OR subclause.
 428  *
 429  * This is essentially just like group_clauses_by_indexkey() except that
 430  * we can use the given clause (or any AND subclauses of it) as well as
 431  * top-level restriction clauses of the relation.  Furthermore, we demand
 432  * that at least one such use be made, otherwise we fail and return NIL.
 433  * (Any path we made without such a use would be redundant with non-OR
 434  * indexscans.  Compare also group_clauses_by_indexkey_for_join.)
 435  *
 436  * XXX When we generate an indexqual list that uses both the OR subclause
 437  * and top-level restriction clauses, we end up with a slightly inefficient
 438  * plan because create_indexscan_plan is not very bright about figuring out
 439  * which restriction clauses are implied by the generated indexqual condition.
 440  * Currently we'll end up rechecking both the OR clause and the top-level
 441  * restriction clause as qpquals.  FIXME someday.
 442  */
 443 List *
 444 group_clauses_by_indexkey_for_or(RelOptInfo *rel,
 445                                                                  IndexOptInfo *index,
 446                                                                  Expr *orsubclause)
 447 {
 448         FastList        clausegroup_list;
 449         bool            matched = false;
 450         int                     indexcol = 0;
 451         Oid                *classes = index->classlist;
 452
 453         FastListInit(&clausegroup_list);
 454         do
 455         {
 456                 Oid                     curClass = classes[0];
 457                 FastList        clausegroup;
 458                 List       *item;
 459
 460                 FastListInit(&clausegroup);
 461
 462                 /* Try to match the OR subclause to the index key */
 463                 if (IsA(orsubclause, RestrictInfo))
 464                 {
 465                         if (match_clause_to_indexcol(rel, index,
 466                                                                                  indexcol, curClass,
 467                                                                                  (RestrictInfo *) orsubclause))
 468                         {
 469                                 FastAppend(&clausegroup, orsubclause);
 470                                 matched = true;
 471                         }
 472                 }
 473                 else if (and_clause((Node *) orsubclause))
 474                 {
 475                         foreach(item, ((BoolExpr *) orsubclause)->args)
 476                         {
 477                                 RestrictInfo *subsubclause = (RestrictInfo *) lfirst(item);
 478
 479                                 if (IsA(subsubclause, RestrictInfo) &&
 480                                         match_clause_to_indexcol(rel, index,
 481                                                                                          indexcol, curClass,
 482                                                                                          subsubclause))
 483                                 {
 484                                         FastAppend(&clausegroup, subsubclause);
 485                                         matched = true;
 486                                 }
 487                         }
 488                 }
 489
 490                 /*
 491                  * If we found no clauses for this indexkey in the OR subclause
 492                  * itself, try looking in the rel's top-level restriction list.
 493                  *
 494                  * XXX should we always search the top-level list?  Slower but
 495                  * could sometimes yield a better plan.
 496                  */
 497                 if (FastListValue(&clausegroup) == NIL)
 498                 {
 499                         foreach(item, rel->baserestrictinfo)
 500                         {
 501                                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
 502
 503                                 if (match_clause_to_indexcol(rel, index,
 504                                                                                          indexcol, curClass,
 505                                                                                          rinfo))
 506                                         FastAppend(&clausegroup, rinfo);
 507                         }
 508                 }
 509
 510                 /*
 511                  * If still no clauses match this key, we're done; we don't want
 512                  * to look at keys to its right.
 513                  */
 514                 if (FastListValue(&clausegroup) == NIL)
 515                         break;
 516
 517                 FastAppend(&clausegroup_list, FastListValue(&clausegroup));
 518
 519                 indexcol++;
 520                 classes++;
 521
 522         } while (!DoneMatchingIndexKeys(classes));
 523
 524         /* if OR clause was not used then forget it, per comments above */
 525         if (!matched)
 526                 return NIL;
 527
 528         return FastListValue(&clausegroup_list);
 529 }
 530
 531
 532 /*
 533  * match_clause_to_indexcol()
 534  *        Determines whether a restriction clause matches a column of an index.
 535  *
 536  *        To match, the clause:
 537  *
 538  *        (1)  must be in the form (indexkey op const) or (const op indexkey);
 539  *                 and
 540  *        (2)  must contain an operator which is in the same class as the index
 541  *                 operator for this column, or is a "special" operator as recognized
 542  *                 by match_special_index_operator().
 543  *
 544  *        Presently, the executor can only deal with indexquals that have the
 545  *        indexkey on the left, so we can only use clauses that have the indexkey
 546  *        on the right if we can commute the clause to put the key on the left.
 547  *        We do not actually do the commuting here, but we check whether a
 548  *        suitable commutator operator is available.
 549  *
 550  * 'rel' is the relation of interest.
 551  * 'index' is an index on 'rel'.
 552  * 'indexcol' is a column number of 'index' (counting from 0).
 553  * 'opclass' is the corresponding operator class.
 554  * 'rinfo' is the clause to be tested (as a RestrictInfo node).
 555  *
 556  * Returns true if the clause can be used with this index key.
 557  *
 558  * NOTE:  returns false if clause is an OR or AND clause; it is the
 559  * responsibility of higher-level routines to cope with those.
 560  */
 561 static bool
 562 match_clause_to_indexcol(RelOptInfo *rel,
 563                                                  IndexOptInfo *index,
 564                                                  int indexcol,
 565                                                  Oid opclass,
 566                                                  RestrictInfo *rinfo)
 567 {
 568         Expr       *clause = rinfo->clause;
 569         Node       *leftop,
 570                            *rightop;
 571
 572         /* Clause must be a binary opclause. */
 573         if (!is_opclause(clause))
 574                 return false;
 575         leftop = get_leftop(clause);
 576         rightop = get_rightop(clause);
 577         if (!leftop || !rightop)
 578                 return false;
 579
 580         /*
 581          * Check for clauses of the form: (indexkey operator constant) or
 582          * (constant operator indexkey). Anything that is a "pseudo constant"
 583          * expression will do.
 584          */
 585         if (match_index_to_operand(leftop, indexcol, rel, index) &&
 586                 is_pseudo_constant_clause_relids(rightop, rinfo->right_relids))
 587         {
 588                 if (is_indexable_operator(clause, opclass, true))
 589                         return true;
 590
 591                 /*
 592                  * If we didn't find a member of the index's opclass, see whether
 593                  * it is a "special" indexable operator.
 594                  */
 595                 if (match_special_index_operator(clause, opclass, true))
 596                         return true;
 597                 return false;
 598         }
 599
 600         if (match_index_to_operand(rightop, indexcol, rel, index) &&
 601                 is_pseudo_constant_clause_relids(leftop, rinfo->left_relids))
 602         {
 603                 if (is_indexable_operator(clause, opclass, false))
 604                         return true;
 605
 606                 /*
 607                  * If we didn't find a member of the index's opclass, see whether
 608                  * it is a "special" indexable operator.
 609                  */
 610                 if (match_special_index_operator(clause, opclass, false))
 611                         return true;
 612                 return false;
 613         }
 614
 615         return false;
 616 }
 617
 618 /*
 619  * match_join_clause_to_indexcol()
 620  *        Determines whether a join clause matches a column of an index.
 621  *
 622  *        To match, the clause:
 623  *
 624  *        (1)  must be in the form (indexkey op others) or (others op indexkey),
 625  *                 where others is an expression involving only vars of the other
 626  *                 relation(s); and
 627  *        (2)  must contain an operator which is in the same class as the index
 628  *                 operator for this column, or is a "special" operator as recognized
 629  *                 by match_special_index_operator().
 630  *
 631  *        As above, we must be able to commute the clause to put the indexkey
 632  *        on the left.
 633  *
 634  *        Note that we already know that the clause as a whole uses vars from
 635  *        the interesting set of relations.  But we need to defend against
 636  *        expressions like (a.f1 OP (b.f2 OP a.f3)); that's not processable by
 637  *        an indexscan nestloop join, whereas (a.f1 OP (b.f2 OP c.f3)) is.
 638  *
 639  * 'rel' is the relation of interest.
 640  * 'index' is an index on 'rel'.
 641  * 'indexcol' is a column number of 'index' (counting from 0).
 642  * 'opclass' is the corresponding operator class.
 643  * 'rinfo' is the clause to be tested (as a RestrictInfo node).
 644  *
 645  * Returns true if the clause can be used with this index key.
 646  *
 647  * NOTE:  returns false if clause is an OR or AND clause; it is the
 648  * responsibility of higher-level routines to cope with those.
 649  */
 650 static bool
 651 match_join_clause_to_indexcol(RelOptInfo *rel,
 652                                                           IndexOptInfo *index,
 653                                                           int indexcol,
 654                                                           Oid opclass,
 655                                                           RestrictInfo *rinfo)
 656 {
 657         Expr       *clause = rinfo->clause;
 658         Node       *leftop,
 659                            *rightop;
 660
 661         /* Clause must be a binary opclause. */
 662         if (!is_opclause(clause))
 663                 return false;
 664         leftop = get_leftop(clause);
 665         rightop = get_rightop(clause);
 666         if (!leftop || !rightop)
 667                 return false;
 668
 669         /*
 670          * Check for an indexqual that could be handled by a nestloop join. We
 671          * need the index key to be compared against an expression that uses
 672          * none of the indexed relation's vars and contains no volatile
 673          * functions.
 674          */
 675         if (match_index_to_operand(leftop, indexcol, rel, index))
 676         {
 677                 Relids          othervarnos = rinfo->right_relids;
 678                 bool            isIndexable;
 679
 680                 isIndexable =
 681                         !bms_overlap(rel->relids, othervarnos) &&
 682                         !contain_volatile_functions(rightop) &&
 683                         is_indexable_operator(clause, opclass, true);
 684                 return isIndexable;
 685         }
 686
 687         if (match_index_to_operand(rightop, indexcol, rel, index))
 688         {
 689                 Relids          othervarnos = rinfo->left_relids;
 690                 bool            isIndexable;
 691
 692                 isIndexable =
 693                         !bms_overlap(rel->relids, othervarnos) &&
 694                         !contain_volatile_functions(leftop) &&
 695                         is_indexable_operator(clause, opclass, false);
 696                 return isIndexable;
 697         }
 698
 699         return false;
 700 }
 701
 702 /*
 703  * indexable_operator
 704  *        Does a binary opclause contain an operator matching the index opclass?
 705  *
 706  * If the indexkey is on the right, what we actually want to know
 707  * is whether the operator has a commutator operator that matches
 708  * the index's opclass.
 709  *
 710  * Returns the OID of the matching operator, or InvalidOid if no match.
 711  * (Formerly, this routine might return a binary-compatible operator
 712  * rather than the original one, but that kluge is history.)
 713  */
 714 static Oid
 715 indexable_operator(Expr *clause, Oid opclass, bool indexkey_on_left)
 716 {
 717         Oid                     expr_op = ((OpExpr *) clause)->opno;
 718         Oid                     commuted_op;
 719
 720         /* Get the commuted operator if necessary */
 721         if (indexkey_on_left)
 722                 commuted_op = expr_op;
 723         else
 724                 commuted_op = get_commutator(expr_op);
 725         if (commuted_op == InvalidOid)
 726                 return InvalidOid;
 727
 728         /* OK if the (commuted) operator is a member of the index's opclass */
 729         if (op_in_opclass(commuted_op, opclass))
 730                 return expr_op;
 731
 732         return InvalidOid;
 733 }
 734
 735 /****************************************************************************
 736  *                              ----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS      ----
 737  ****************************************************************************/
 738
 739 /*
 740  * pred_test
 741  *        Does the "predicate inclusion test" for partial indexes.
 742  *
 743  *        Recursively checks whether the clauses in restrictinfo_list imply
 744  *        that the given predicate is true.
 745  *
 746  *        This routine (together with the routines it calls) iterates over
 747  *        ANDs in the predicate first, then reduces the qualification
 748  *        clauses down to their constituent terms, and iterates over ORs
 749  *        in the predicate last.  This order is important to make the test
 750  *        succeed whenever possible (assuming the predicate has been converted
 751  *        to CNF format). --Nels, Jan '93
 752  */
 753 static bool
 754 pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list)
 755 {
 756         List       *pred;
 757
 758         /*
 759          * Note: if Postgres tried to optimize queries by forming equivalence
 760          * classes over equi-joined attributes (i.e., if it recognized that a
 761          * qualification such as "where a.b=c.d and a.b=5" could make use of
 762          * an index on c.d), then we could use that equivalence class info
 763          * here with joininfo_list to do more complete tests for the usability
 764          * of a partial index.  For now, the test only uses restriction
 765          * clauses (those in restrictinfo_list). --Nels, Dec '92
 766          *
 767          * XXX as of 7.1, equivalence class info *is* available.  Consider
 768          * improving this code as foreseen by Nels.
 769          */
 770
 771         if (predicate_list == NIL)
 772                 return true;                    /* no predicate: the index is usable */
 773         if (restrictinfo_list == NIL)
 774                 return false;                   /* no restriction clauses: the test must
 775                                                                  * fail */
 776
 777         foreach(pred, predicate_list)
 778         {
 779                 /*
 780                  * if any clause is not implied, the whole predicate is not
 781                  * implied.  Note we assume that any sub-ANDs have been flattened
 782                  * when the predicate was fed through canonicalize_qual().
 783                  */
 784                 if (!pred_test_restrict_list(lfirst(pred), restrictinfo_list))
 785                         return false;
 786         }
 787         return true;
 788 }
 789
 790
 791 /*
 792  * pred_test_restrict_list
 793  *        Does the "predicate inclusion test" for one conjunct of a predicate
 794  *        expression.
 795  */
 796 static bool
 797 pred_test_restrict_list(Expr *predicate, List *restrictinfo_list)
 798 {
 799         List       *item;
 800
 801         foreach(item, restrictinfo_list)
 802         {
 803                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(item);
 804
 805                 /* if any clause implies the predicate, return true */
 806                 if (pred_test_recurse_clause(predicate,
 807                                                                          (Node *) restrictinfo->clause))
 808                         return true;
 809         }
 810         return false;
 811 }
 812
 813
 814 /*
 815  * pred_test_recurse_clause
 816  *        Does the "predicate inclusion test" for a general restriction-clause
 817  *        expression.  Here we recursively deal with the possibility that the
 818  *        restriction clause is itself an AND or OR structure.
 819  */
 820 static bool
 821 pred_test_recurse_clause(Expr *predicate, Node *clause)
 822 {
 823         List       *items,
 824                            *item;
 825
 826         Assert(clause != NULL);
 827         if (or_clause(clause))
 828         {
 829                 items = ((BoolExpr *) clause)->args;
 830                 foreach(item, items)
 831                 {
 832                         /* if any OR item doesn't imply the predicate, clause doesn't */
 833                         if (!pred_test_recurse_clause(predicate, lfirst(item)))
 834                                 return false;
 835                 }
 836                 return true;
 837         }
 838         else if (and_clause(clause))
 839         {
 840                 items = ((BoolExpr *) clause)->args;
 841                 foreach(item, items)
 842                 {
 843                         /*
 844                          * if any AND item implies the predicate, the whole clause
 845                          * does
 846                          */
 847                         if (pred_test_recurse_clause(predicate, lfirst(item)))
 848                                 return true;
 849                 }
 850                 return false;
 851         }
 852         else
 853                 return pred_test_recurse_pred(predicate, clause);
 854 }
 855
 856
 857 /*
 858  * pred_test_recurse_pred
 859  *        Does the "predicate inclusion test" for one conjunct of a predicate
 860  *        expression for a simple restriction clause.  Here we recursively deal
 861  *        with the possibility that the predicate conjunct is itself an AND or
 862  *        OR structure.
 863  */
 864 static bool
 865 pred_test_recurse_pred(Expr *predicate, Node *clause)
 866 {
 867         List       *items,
 868                            *item;
 869
 870         Assert(predicate != NULL);
 871         if (or_clause((Node *) predicate))
 872         {
 873                 items = ((BoolExpr *) predicate)->args;
 874                 foreach(item, items)
 875                 {
 876                         /* if any item is implied, the whole predicate is implied */
 877                         if (pred_test_recurse_pred(lfirst(item), clause))
 878                                 return true;
 879                 }
 880                 return false;
 881         }
 882         else if (and_clause((Node *) predicate))
 883         {
 884                 items = ((BoolExpr *) predicate)->args;
 885                 foreach(item, items)
 886                 {
 887                         /*
 888                          * if any item is not implied, the whole predicate is not
 889                          * implied
 890                          */
 891                         if (!pred_test_recurse_pred(lfirst(item), clause))
 892                                 return false;
 893                 }
 894                 return true;
 895         }
 896         else
 897                 return pred_test_simple_clause(predicate, clause);
 898 }
 899
 900
 901 /*
 902  * Define an "operator implication table" for btree operators ("strategies").
 903  * The "strategy numbers" are:  (1) <   (2) <=   (3) =   (4) >=   (5) >
 904  *
 905  * The interpretation of:
 906  *
 907  *              test_op = BT_implic_table[given_op-1][target_op-1]
 908  *
 909  * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
 910  * of btree operators, is as follows:
 911  *
 912  *       If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
 913  *       want to determine whether "ATTR target_op CONST2" must also be true, then
 914  *       you can use "CONST2 test_op CONST1" as a test.  If this test returns true,
 915  *       then the target expression must be true; if the test returns false, then
 916  *       the target expression may be false.
 917  *
 918  * An entry where test_op==0 means the implication cannot be determined, i.e.,
 919  * this test should always be considered false.
 920  */
 921
 922 static const StrategyNumber
 923                         BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
 924         {4, 4, 0, 0, 0},
 925         {5, 4, 0, 0, 0},
 926         {5, 4, 3, 2, 1},
 927         {0, 0, 0, 2, 1},
 928         {0, 0, 0, 2, 2}
 929 };
 930
 931
 932 /*
 933  * pred_test_simple_clause
 934  *        Does the "predicate inclusion test" for a "simple clause" predicate
 935  *        and a "simple clause" restriction.
 936  *
 937  *        We have two strategies for determining whether one simple clause
 938  *        implies another.      A simple and general way is to see if they are
 939  *        equal(); this works for any kind of expression.  (Actually, there
 940  *        is an implied assumption that the functions in the expression are
 941  *        immutable, ie dependent only on their input arguments --- but this
 942  *        was checked for the predicate by CheckPredicate().)
 943  *
 944  *        Our other way works only for (binary boolean) operators that are
 945  *        in some btree operator class.  We use the above operator implication
 946  *        table to be able to derive implications between nonidentical clauses.
 947  *
 948  *        Eventually, rtree operators could also be handled by defining an
 949  *        appropriate "RT_implic_table" array.
 950  */
 951 static bool
 952 pred_test_simple_clause(Expr *predicate, Node *clause)
 953 {
 954         Var                *pred_var,
 955                            *clause_var;
 956         Const      *pred_const,
 957                            *clause_const;
 958         Oid                     pred_op,
 959                                 clause_op,
 960                                 test_op = InvalidOid;
 961         Oid                     opclass_id;
 962         bool            found = false;
 963         StrategyNumber pred_strategy,
 964                                 clause_strategy,
 965                                 test_strategy;
 966         Oid                     clause_subtype;
 967         Expr       *test_expr;
 968         ExprState  *test_exprstate;
 969         Datum           test_result;
 970         bool            isNull;
 971         CatCList   *catlist;
 972         int                     i;
 973         EState     *estate;
 974         MemoryContext oldcontext;
 975
 976         /* First try the equal() test */
 977         if (equal((Node *) predicate, clause))
 978                 return true;
 979
 980         /*
 981          * Can't do anything more unless they are both binary opclauses with a
 982          * Var on the left and a Const on the right.  (XXX someday try to
 983          * commute Const/Var cases?)  Note we don't have to think about binary
 984          * relabeling of the Const node, since that would have been folded right
 985          * into the Const.
 986          */
 987         if (!is_opclause(predicate))
 988                 return false;
 989         pred_var = (Var *) get_leftop(predicate);
 990         pred_const = (Const *) get_rightop(predicate);
 991
 992         if (!is_opclause(clause))
 993                 return false;
 994         clause_var = (Var *) get_leftop((Expr *) clause);
 995         clause_const = (Const *) get_rightop((Expr *) clause);
 996
 997         if (!IsA(clause_var, Var) ||
 998                 clause_const == NULL ||
 999                 !IsA(clause_const, Const) ||
1000                 !IsA(pred_var, Var) ||
1001                 pred_const == NULL ||
1002                 !IsA(pred_const, Const))
1003                 return false;
1004
1005         /*
1006          * The implication can't be determined unless the predicate and the
1007          * clause refer to the same attribute.
1008          */
1009         if (clause_var->varno != pred_var->varno ||
1010                 clause_var->varattno != pred_var->varattno)
1011                 return false;
1012
1013         /* Get the operators for the two clauses we're comparing */
1014         pred_op = ((OpExpr *) predicate)->opno;
1015         clause_op = ((OpExpr *) clause)->opno;
1016
1017         /*
1018          * Try to find a btree opclass containing the needed operators.
1019          *
1020          * We must find a btree opclass that contains both operators, else the
1021          * implication can't be determined.  Also, the pred_op has to be of
1022          * default subtype (implying left and right input datatypes are the same);
1023          * otherwise it's unsafe to put the pred_const on the left side of the
1024          * test.  Also, the opclass must contain a suitable test operator
1025          * matching the clause_const's type (which we take to mean that it has
1026          * the same subtype as the original clause_operator).
1027          *
1028          * If there are multiple matching opclasses, assume we can use any one to
1029          * determine the logical relationship of the two operators and the correct
1030          * corresponding test operator.  This should work for any logically
1031          * consistent opclasses.
1032          */
1033         catlist = SearchSysCacheList(AMOPOPID, 1,
1034                                                                  ObjectIdGetDatum(pred_op),
1035                                                                  0, 0, 0);
1036
1037         for (i = 0; i < catlist->n_members; i++)
1038         {
1039                 HeapTuple       pred_tuple = &catlist->members[i]->tuple;
1040                 Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
1041                 HeapTuple       clause_tuple;
1042
1043                 opclass_id = pred_form->amopclaid;
1044
1045                 /* must be btree */
1046                 if (!opclass_is_btree(opclass_id))
1047                         continue;
1048                 /* predicate operator must be default within this opclass */
1049                 if (pred_form->amopsubtype != InvalidOid)
1050                         continue;
1051
1052                 /* Get the predicate operator's btree strategy number */
1053                 pred_strategy = (StrategyNumber) pred_form->amopstrategy;
1054                 Assert(pred_strategy >= 1 && pred_strategy <= 5);
1055
1056                 /*
1057                  * From the same opclass, find a strategy number for the clause_op,
1058                  * if possible
1059                  */
1060                 clause_tuple = SearchSysCache(AMOPOPID,
1061                                                                           ObjectIdGetDatum(clause_op),
1062                                                                           ObjectIdGetDatum(opclass_id),
1063                                                                           0, 0);
1064                 if (HeapTupleIsValid(clause_tuple))
1065                 {
1066                         Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
1067
1068                         /* Get the restriction clause operator's strategy/subtype */
1069                         clause_strategy = (StrategyNumber) clause_form->amopstrategy;
1070                         Assert(clause_strategy >= 1 && clause_strategy <= 5);
1071                         clause_subtype = clause_form->amopsubtype;
1072
1073                         /* done with clause_tuple */
1074                         ReleaseSysCache(clause_tuple);
1075
1076                         /*
1077                          * Look up the "test" strategy number in the implication table
1078                          */
1079                         test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1080                         if (test_strategy == 0)
1081                         {
1082                                 /* Can't determine implication using this interpretation */
1083                                 continue;
1084                         }
1085
1086                         /*
1087                          * See if opclass has an operator for the test strategy and the
1088                          * clause datatype.
1089                          */
1090                         test_op = get_opclass_member(opclass_id, clause_subtype,
1091                                                                                  test_strategy);
1092                         if (OidIsValid(test_op))
1093                         {
1094                                 found = true;
1095                                 break;
1096                         }
1097                 }
1098         }
1099
1100         ReleaseSysCacheList(catlist);
1101
1102         if (!found)
1103         {
1104                 /* couldn't find a btree opclass to interpret the operators */
1105                 return false;
1106         }
1107
1108         /*
1109          * Evaluate the test.  For this we need an EState.
1110          */
1111         estate = CreateExecutorState();
1112
1113         /* We can use the estate's working context to avoid memory leaks. */
1114         oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
1115
1116         /* Build expression tree */
1117         test_expr = make_opclause(test_op,
1118                                                           BOOLOID,
1119                                                           false,
1120                                                           (Expr *) pred_const,
1121                                                           (Expr *) clause_const);
1122
1123         /* Prepare it for execution */
1124         test_exprstate = ExecPrepareExpr(test_expr, estate);
1125
1126         /* And execute it. */
1127         test_result = ExecEvalExprSwitchContext(test_exprstate,
1128                                                                                   GetPerTupleExprContext(estate),
1129                                                                                         &isNull, NULL);
1130
1131         /* Get back to outer memory context */
1132         MemoryContextSwitchTo(oldcontext);
1133
1134         /* Release all the junk we just created */
1135         FreeExecutorState(estate);
1136
1137         if (isNull)
1138         {
1139                 /* Treat a null result as false ... but it's a tad fishy ... */
1140                 elog(DEBUG2, "null predicate test result");
1141                 return false;
1142         }
1143         return DatumGetBool(test_result);
1144 }
1145
1146
1147 /****************************************************************************
1148  *                              ----  ROUTINES TO CHECK JOIN CLAUSES  ----
1149  ****************************************************************************/
1150
1151 /*
1152  * indexable_outerrelids
1153  *        Finds all other relids that participate in any indexable join clause
1154  *        for the specified index.      Returns a set of relids.
1155  *
1156  * 'rel' is the relation for which 'index' is defined
1157  */
1158 static Relids
1159 indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index)
1160 {
1161         Relids          outer_relids = NULL;
1162         List       *i;
1163
1164         foreach(i, rel->joininfo)
1165         {
1166                 JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
1167                 bool            match_found = false;
1168                 List       *j;
1169
1170                 /*
1171                  * Examine each joinclause in the JoinInfo node's list to see if
1172                  * it matches any key of the index.  If so, add the JoinInfo's
1173                  * otherrels to the result.  We can skip examining other
1174                  * joinclauses in the same list as soon as we find a match (since
1175                  * by definition they all have the same otherrels).
1176                  */
1177                 foreach(j, joininfo->jinfo_restrictinfo)
1178                 {
1179                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1180                         int                     indexcol = 0;
1181                         Oid                *classes = index->classlist;
1182
1183                         do
1184                         {
1185                                 Oid                     curClass = classes[0];
1186
1187                                 if (match_join_clause_to_indexcol(rel,
1188                                                                                                   index,
1189                                                                                                   indexcol,
1190                                                                                                   curClass,
1191                                                                                                   rinfo))
1192                                 {
1193                                         match_found = true;
1194                                         break;
1195                                 }
1196
1197                                 indexcol++;
1198                                 classes++;
1199
1200                         } while (!DoneMatchingIndexKeys(classes));
1201
1202                         if (match_found)
1203                                 break;
1204                 }
1205
1206                 if (match_found)
1207                 {
1208                         outer_relids = bms_add_members(outer_relids,
1209                                                                                    joininfo->unjoined_relids);
1210                 }
1211         }
1212
1213         return outer_relids;
1214 }
1215
1216 /*
1217  * best_inner_indexscan
1218  *        Finds the best available inner indexscan for a nestloop join
1219  *        with the given rel on the inside and the given outer_relids outside.
1220  *        May return NULL if there are no possible inner indexscans.
1221  *
1222  * We ignore ordering considerations (since a nestloop's inner scan's order
1223  * is uninteresting).  Also, we consider only total cost when deciding which
1224  * of two possible paths is better --- this assumes that all indexpaths have
1225  * negligible startup cost.  (True today, but someday we might have to think
1226  * harder.)  Therefore, there is only one dimension of comparison and so it's
1227  * sufficient to return a single "best" path.
1228  */
1229 Path *
1230 best_inner_indexscan(Query *root, RelOptInfo *rel,
1231                                          Relids outer_relids, JoinType jointype)
1232 {
1233         Path       *cheapest = NULL;
1234         bool            isouterjoin;
1235         List       *ilist;
1236         List       *jlist;
1237         InnerIndexscanInfo *info;
1238         MemoryContext oldcontext;
1239
1240         /*
1241          * Nestloop only supports inner, left, and IN joins.
1242          */
1243         switch (jointype)
1244         {
1245                 case JOIN_INNER:
1246                 case JOIN_IN:
1247                 case JOIN_UNIQUE_OUTER:
1248                         isouterjoin = false;
1249                         break;
1250                 case JOIN_LEFT:
1251                         isouterjoin = true;
1252                         break;
1253                 default:
1254                         return NULL;
1255         }
1256
1257         /*
1258          * If there are no indexable joinclauses for this rel, exit quickly.
1259          */
1260         if (bms_is_empty(rel->index_outer_relids))
1261                 return NULL;
1262
1263         /*
1264          * Otherwise, we have to do path selection in the memory context of
1265          * the given rel, so that any created path can be safely attached to
1266          * the rel's cache of best inner paths.  (This is not currently an
1267          * issue for normal planning, but it is an issue for GEQO planning.)
1268          */
1269         oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1270
1271         /*
1272          * Intersect the given outer_relids with index_outer_relids to find
1273          * the set of outer relids actually relevant for this index. If there
1274          * are none, again we can fail immediately.
1275          */
1276         outer_relids = bms_intersect(rel->index_outer_relids, outer_relids);
1277         if (bms_is_empty(outer_relids))
1278         {
1279                 bms_free(outer_relids);
1280                 MemoryContextSwitchTo(oldcontext);
1281                 return NULL;
1282         }
1283
1284         /*
1285          * Look to see if we already computed the result for this set of
1286          * relevant outerrels.  (We include the isouterjoin status in the
1287          * cache lookup key for safety.  In practice I suspect this is not
1288          * necessary because it should always be the same for a given
1289          * innerrel.)
1290          */
1291         foreach(jlist, rel->index_inner_paths)
1292         {
1293                 info = (InnerIndexscanInfo *) lfirst(jlist);
1294                 if (bms_equal(info->other_relids, outer_relids) &&
1295                         info->isouterjoin == isouterjoin)
1296                 {
1297                         bms_free(outer_relids);
1298                         MemoryContextSwitchTo(oldcontext);
1299                         return info->best_innerpath;
1300                 }
1301         }
1302
1303         /*
1304          * For each index of the rel, find the best path; then choose the best
1305          * overall.  We cache the per-index results as well as the overall
1306          * result.      (This is useful because different indexes may have
1307          * different relevant outerrel sets, so different overall outerrel
1308          * sets might still map to the same computation for a given index.)
1309          */
1310         foreach(ilist, rel->indexlist)
1311         {
1312                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
1313                 Relids          index_outer_relids;
1314                 Path       *path = NULL;
1315
1316                 /* identify set of relevant outer relids for this index */
1317                 index_outer_relids = bms_intersect(index->outer_relids, outer_relids);
1318                 /* skip if none */
1319                 if (bms_is_empty(index_outer_relids))
1320                 {
1321                         bms_free(index_outer_relids);
1322                         continue;
1323                 }
1324
1325                 /*
1326                  * Look to see if we already computed the result for this index.
1327                  */
1328                 foreach(jlist, index->inner_paths)
1329                 {
1330                         info = (InnerIndexscanInfo *) lfirst(jlist);
1331                         if (bms_equal(info->other_relids, index_outer_relids) &&
1332                                 info->isouterjoin == isouterjoin)
1333                         {
1334                                 path = info->best_innerpath;
1335                                 bms_free(index_outer_relids);   /* not needed anymore */
1336                                 break;
1337                         }
1338                 }
1339
1340                 if (jlist == NIL)               /* failed to find a match? */
1341                 {
1342                         List       *clausegroups;
1343
1344                         /* find useful clauses for this index and outerjoin set */
1345                         clausegroups = group_clauses_by_indexkey_for_join(root,
1346                                                                                                                           rel,
1347                                                                                                                           index,
1348                                                                                                           index_outer_relids,
1349                                                                                                                           jointype,
1350                                                                                                                         isouterjoin);
1351                         if (clausegroups)
1352                         {
1353                                 /* make the path */
1354                                 path = make_innerjoin_index_path(root, rel, index,
1355                                                                                                  clausegroups);
1356                         }
1357
1358                         /* Cache the result --- whether positive or negative */
1359                         info = makeNode(InnerIndexscanInfo);
1360                         info->other_relids = index_outer_relids;
1361                         info->isouterjoin = isouterjoin;
1362                         info->best_innerpath = path;
1363                         index->inner_paths = lcons(info, index->inner_paths);
1364                 }
1365
1366                 if (path != NULL &&
1367                         (cheapest == NULL ||
1368                          compare_path_costs(path, cheapest, TOTAL_COST) < 0))
1369                         cheapest = path;
1370         }
1371
1372         /* Cache the result --- whether positive or negative */
1373         info = makeNode(InnerIndexscanInfo);
1374         info->other_relids = outer_relids;
1375         info->isouterjoin = isouterjoin;
1376         info->best_innerpath = cheapest;
1377         rel->index_inner_paths = lcons(info, rel->index_inner_paths);
1378
1379         MemoryContextSwitchTo(oldcontext);
1380
1381         return cheapest;
1382 }
1383
1384 /****************************************************************************
1385  *                              ----  PATH CREATION UTILITIES  ----
1386  ****************************************************************************/
1387
1388 /*
1389  * make_innerjoin_index_path
1390  *        Create an index path node for a path to be used as an inner
1391  *        relation in a nestloop join.
1392  *
1393  * 'rel' is the relation for which 'index' is defined
1394  * 'clausegroups' is a list of lists of RestrictInfos that can use 'index'
1395  */
1396 static Path *
1397 make_innerjoin_index_path(Query *root,
1398                                                   RelOptInfo *rel, IndexOptInfo *index,
1399                                                   List *clausegroups)
1400 {
1401         IndexPath  *pathnode = makeNode(IndexPath);
1402         List       *indexquals,
1403                            *allclauses,
1404                            *l;
1405
1406         /* XXX perhaps this code should be merged with create_index_path? */
1407
1408         pathnode->path.pathtype = T_IndexScan;
1409         pathnode->path.parent = rel;
1410
1411         /*
1412          * There's no point in marking the path with any pathkeys, since it
1413          * will only ever be used as the inner path of a nestloop, and so its
1414          * ordering does not matter.
1415          */
1416         pathnode->path.pathkeys = NIL;
1417
1418         /* Convert RestrictInfo nodes to indexquals the executor can handle */
1419         indexquals = expand_indexqual_conditions(index, clausegroups);
1420
1421         /*
1422          * Also make a flattened list of the RestrictInfo nodes; createplan.c
1423          * will need this later.  We assume here that we can destructively
1424          * modify the passed-in clausegroups list structure.
1425          */
1426         allclauses = NIL;
1427         foreach(l, clausegroups)
1428         {
1429                 /* nconc okay here since same clause couldn't be in two sublists */
1430                 allclauses = nconc(allclauses, (List *) lfirst(l));
1431         }
1432
1433         /*
1434          * Note that we are making a pathnode for a single-scan indexscan;
1435          * therefore, indexinfo and indexqual should be single-element lists.
1436          */
1437         pathnode->indexinfo = makeList1(index);
1438         pathnode->indexqual = makeList1(indexquals);
1439         pathnode->indexjoinclauses = makeList1(allclauses);
1440
1441         /* We don't actually care what order the index scans in ... */
1442         pathnode->indexscandir = NoMovementScanDirection;
1443
1444         /*
1445          * We must compute the estimated number of output rows for the
1446          * indexscan.  This is less than rel->rows because of the additional
1447          * selectivity of the join clauses.  Since clausegroups may contain
1448          * both restriction and join clauses, we have to do a set union to get
1449          * the full set of clauses that must be considered to compute the
1450          * correct selectivity.  (Without the union operation, we might have
1451          * some restriction clauses appearing twice, which'd mislead
1452          * clauselist_selectivity into double-counting their selectivity.
1453          * However, since RestrictInfo nodes aren't copied when linking them
1454          * into different lists, it should be sufficient to use pointer
1455          * comparison to remove duplicates.)
1456          *
1457          * Always assume the join type is JOIN_INNER; even if some of the join
1458          * clauses come from other contexts, that's not our problem.
1459          */
1460         allclauses = set_ptrUnion(rel->baserestrictinfo, allclauses);
1461         pathnode->rows = rel->tuples *
1462                 clauselist_selectivity(root,
1463                                                            allclauses,
1464                                                            rel->relid,          /* do not use 0! */
1465                                                            JOIN_INNER);
1466         /* Like costsize.c, force estimate to be at least one row */
1467         if (pathnode->rows < 1.0)
1468                 pathnode->rows = 1.0;
1469
1470         cost_index(&pathnode->path, root, rel, index, indexquals, true);
1471
1472         return (Path *) pathnode;
1473 }
1474
1475 /****************************************************************************
1476  *                              ----  ROUTINES TO CHECK OPERANDS  ----
1477  ****************************************************************************/
1478
1479 /*
1480  * match_index_to_operand()
1481  *        Generalized test for a match between an index's key
1482  *        and the operand on one side of a restriction or join clause.
1483  *
1484  * operand: the nodetree to be compared to the index
1485  * indexcol: the column number of the index (counting from 0)
1486  * rel: the parent relation
1487  * index: the index of interest
1488  */
1489 static bool
1490 match_index_to_operand(Node *operand,
1491                                            int indexcol,
1492                                            RelOptInfo *rel,
1493                                            IndexOptInfo *index)
1494 {
1495         int                     indkey;
1496
1497         /*
1498          * Ignore any RelabelType node above the operand.       This is needed to
1499          * be able to apply indexscanning in binary-compatible-operator cases.
1500          * Note: we can assume there is at most one RelabelType node;
1501          * eval_const_expressions() will have simplified if more than one.
1502          */
1503         if (operand && IsA(operand, RelabelType))
1504                 operand = (Node *) ((RelabelType *) operand)->arg;
1505
1506         indkey = index->indexkeys[indexcol];
1507         if (indkey != 0)
1508         {
1509                 /*
1510                  * Simple index column; operand must be a matching Var.
1511                  */
1512                 if (operand && IsA(operand, Var) &&
1513                         rel->relid == ((Var *) operand)->varno &&
1514                         indkey == ((Var *) operand)->varattno)
1515                         return true;
1516         }
1517         else
1518         {
1519                 /*
1520                  * Index expression; find the correct expression.  (This search
1521                  * could be avoided, at the cost of complicating all the callers
1522                  * of this routine; doesn't seem worth it.)
1523                  */
1524                 List       *indexprs;
1525                 int                     i;
1526                 Node       *indexkey;
1527
1528                 indexprs = index->indexprs;
1529                 for (i = 0; i < indexcol; i++)
1530                 {
1531                         if (index->indexkeys[i] == 0)
1532                         {
1533                                 if (indexprs == NIL)
1534                                         elog(ERROR, "wrong number of index expressions");
1535                                 indexprs = lnext(indexprs);
1536                         }
1537                 }
1538                 if (indexprs == NIL)
1539                         elog(ERROR, "wrong number of index expressions");
1540                 indexkey = (Node *) lfirst(indexprs);
1541
1542                 /*
1543                  * Does it match the operand?  Again, strip any relabeling.
1544                  */
1545                 if (indexkey && IsA(indexkey, RelabelType))
1546                         indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1547
1548                 if (equal(indexkey, operand))
1549                         return true;
1550         }
1551
1552         return false;
1553 }
1554
1555 /****************************************************************************
1556  *                      ----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
1557  ****************************************************************************/
1558
1559 /*----------
1560  * These routines handle special optimization of operators that can be
1561  * used with index scans even though they are not known to the executor's
1562  * indexscan machinery.  The key idea is that these operators allow us
1563  * to derive approximate indexscan qual clauses, such that any tuples
1564  * that pass the operator clause itself must also satisfy the simpler
1565  * indexscan condition(s).      Then we can use the indexscan machinery
1566  * to avoid scanning as much of the table as we'd otherwise have to,
1567  * while applying the original operator as a qpqual condition to ensure
1568  * we deliver only the tuples we want.  (In essence, we're using a regular
1569  * index as if it were a lossy index.)
1570  *
1571  * An example of what we're doing is
1572  *                      textfield LIKE 'abc%'
1573  * from which we can generate the indexscanable conditions
1574  *                      textfield >= 'abc' AND textfield < 'abd'
1575  * which allow efficient scanning of an index on textfield.
1576  * (In reality, character set and collation issues make the transformation
1577  * from LIKE to indexscan limits rather harder than one might think ...
1578  * but that's the basic idea.)
1579  *
1580  * Two routines are provided here, match_special_index_operator() and
1581  * expand_indexqual_conditions().  match_special_index_operator() is
1582  * just an auxiliary function for match_clause_to_indexcol(); after
1583  * the latter fails to recognize a restriction opclause's operator
1584  * as a member of an index's opclass, it asks match_special_index_operator()
1585  * whether the clause should be considered an indexqual anyway.
1586  * expand_indexqual_conditions() converts a list of lists of RestrictInfo
1587  * nodes (with implicit AND semantics across list elements) into
1588  * a list of clauses that the executor can actually handle.  For operators
1589  * that are members of the index's opclass this transformation is a no-op,
1590  * but operators recognized by match_special_index_operator() must be
1591  * converted into one or more "regular" indexqual conditions.
1592  *----------
1593  */
1594
1595 /*
1596  * match_special_index_operator
1597  *        Recognize restriction clauses that can be used to generate
1598  *        additional indexscanable qualifications.
1599  *
1600  * The given clause is already known to be a binary opclause having
1601  * the form (indexkey OP pseudoconst) or (pseudoconst OP indexkey),
1602  * but the OP proved not to be one of the index's opclass operators.
1603  * Return 'true' if we can do something with it anyway.
1604  */
1605 static bool
1606 match_special_index_operator(Expr *clause, Oid opclass,
1607                                                          bool indexkey_on_left)
1608 {
1609         bool            isIndexable = false;
1610         Node       *rightop;
1611         Oid                     expr_op;
1612         Const      *patt;
1613         Const      *prefix = NULL;
1614         Const      *rest = NULL;
1615
1616         /*
1617          * Currently, all known special operators require the indexkey on the
1618          * left, but this test could be pushed into the switch statement if
1619          * some are added that do not...
1620          */
1621         if (!indexkey_on_left)
1622                 return false;
1623
1624         /* we know these will succeed */
1625         rightop = get_rightop(clause);
1626         expr_op = ((OpExpr *) clause)->opno;
1627
1628         /* again, required for all current special ops: */
1629         if (!IsA(rightop, Const) ||
1630                 ((Const *) rightop)->constisnull)
1631                 return false;
1632         patt = (Const *) rightop;
1633
1634         switch (expr_op)
1635         {
1636                 case OID_TEXT_LIKE_OP:
1637                 case OID_BPCHAR_LIKE_OP:
1638                 case OID_NAME_LIKE_OP:
1639                         /* the right-hand const is type text for all of these */
1640                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
1641                                                                   &prefix, &rest) != Pattern_Prefix_None;
1642                         break;
1643
1644                 case OID_BYTEA_LIKE_OP:
1645                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
1646                                                                   &prefix, &rest) != Pattern_Prefix_None;
1647                         break;
1648
1649                 case OID_TEXT_ICLIKE_OP:
1650                 case OID_BPCHAR_ICLIKE_OP:
1651                 case OID_NAME_ICLIKE_OP:
1652                         /* the right-hand const is type text for all of these */
1653                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
1654                                                                   &prefix, &rest) != Pattern_Prefix_None;
1655                         break;
1656
1657                 case OID_TEXT_REGEXEQ_OP:
1658                 case OID_BPCHAR_REGEXEQ_OP:
1659                 case OID_NAME_REGEXEQ_OP:
1660                         /* the right-hand const is type text for all of these */
1661                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex,
1662                                                                   &prefix, &rest) != Pattern_Prefix_None;
1663                         break;
1664
1665                 case OID_TEXT_ICREGEXEQ_OP:
1666                 case OID_BPCHAR_ICREGEXEQ_OP:
1667                 case OID_NAME_ICREGEXEQ_OP:
1668                         /* the right-hand const is type text for all of these */
1669                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
1670                                                                   &prefix, &rest) != Pattern_Prefix_None;
1671                         break;
1672
1673                 case OID_INET_SUB_OP:
1674                 case OID_INET_SUBEQ_OP:
1675                 case OID_CIDR_SUB_OP:
1676                 case OID_CIDR_SUBEQ_OP:
1677                         isIndexable = true;
1678                         break;
1679         }
1680
1681         if (prefix)
1682         {
1683                 pfree(DatumGetPointer(prefix->constvalue));
1684                 pfree(prefix);
1685         }
1686
1687         /* done if the expression doesn't look indexable */
1688         if (!isIndexable)
1689                 return false;
1690
1691         /*
1692          * Must also check that index's opclass supports the operators we will
1693          * want to apply.  (A hash index, for example, will not support ">=".)
1694          * Currently, only btree supports the operators we need.
1695          *
1696          * We insist on the opclass being the specific one we expect, else we'd
1697          * do the wrong thing if someone were to make a reverse-sort opclass
1698          * with the same operators.
1699          */
1700         switch (expr_op)
1701         {
1702                 case OID_TEXT_LIKE_OP:
1703                 case OID_TEXT_ICLIKE_OP:
1704                 case OID_TEXT_REGEXEQ_OP:
1705                 case OID_TEXT_ICREGEXEQ_OP:
1706                         /* text operators will be used for varchar inputs, too */
1707                         isIndexable =
1708                                 (opclass == TEXT_PATTERN_BTREE_OPS_OID) ||
1709                                 (opclass == TEXT_BTREE_OPS_OID && lc_collate_is_c()) ||
1710                                 (opclass == VARCHAR_PATTERN_BTREE_OPS_OID) ||
1711                                 (opclass == VARCHAR_BTREE_OPS_OID && lc_collate_is_c());
1712                         break;
1713
1714                 case OID_BPCHAR_LIKE_OP:
1715                 case OID_BPCHAR_ICLIKE_OP:
1716                 case OID_BPCHAR_REGEXEQ_OP:
1717                 case OID_BPCHAR_ICREGEXEQ_OP:
1718                         isIndexable =
1719                                 (opclass == BPCHAR_PATTERN_BTREE_OPS_OID) ||
1720                                 (opclass == BPCHAR_BTREE_OPS_OID && lc_collate_is_c());
1721                         break;
1722
1723                 case OID_NAME_LIKE_OP:
1724                 case OID_NAME_ICLIKE_OP:
1725                 case OID_NAME_REGEXEQ_OP:
1726                 case OID_NAME_ICREGEXEQ_OP:
1727                         isIndexable =
1728                                 (opclass == NAME_PATTERN_BTREE_OPS_OID) ||
1729                                 (opclass == NAME_BTREE_OPS_OID && lc_collate_is_c());
1730                         break;
1731
1732                 case OID_BYTEA_LIKE_OP:
1733                         isIndexable = (opclass == BYTEA_BTREE_OPS_OID);
1734                         break;
1735
1736                 case OID_INET_SUB_OP:
1737                 case OID_INET_SUBEQ_OP:
1738                         isIndexable = (opclass == INET_BTREE_OPS_OID);
1739                         break;
1740
1741                 case OID_CIDR_SUB_OP:
1742                 case OID_CIDR_SUBEQ_OP:
1743                         isIndexable = (opclass == CIDR_BTREE_OPS_OID);
1744                         break;
1745         }
1746
1747         return isIndexable;
1748 }
1749
1750 /*
1751  * expand_indexqual_conditions
1752  *        Given a list of sublists of RestrictInfo nodes, produce a flat list
1753  *        of index qual clauses.  Standard qual clauses (those in the index's
1754  *        opclass) are passed through unchanged.  "Special" index operators
1755  *        are expanded into clauses that the indexscan machinery will know
1756  *        what to do with.
1757  *
1758  * The input list is ordered by index key, and so the output list is too.
1759  * (The latter is not depended on by any part of the planner, so far as I can
1760  * tell; but some parts of the executor do assume that the indxqual list
1761  * ultimately delivered to the executor is so ordered.  One such place is
1762  * _bt_preprocess_keys() in the btree support.  Perhaps that ought to be fixed
1763  * someday --- tgl 7/00)
1764  */
1765 List *
1766 expand_indexqual_conditions(IndexOptInfo *index, List *clausegroups)
1767 {
1768         FastList        resultquals;
1769         Oid                *classes = index->classlist;
1770
1771         if (clausegroups == NIL)
1772                 return NIL;
1773
1774         FastListInit(&resultquals);
1775         do
1776         {
1777                 Oid                     curClass = classes[0];
1778                 List       *i;
1779
1780                 foreach(i, (List *) lfirst(clausegroups))
1781                 {
1782                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1783
1784                         FastConc(&resultquals,
1785                                          expand_indexqual_condition(rinfo->clause,
1786                                                                                                 curClass));
1787                 }
1788
1789                 clausegroups = lnext(clausegroups);
1790
1791                 classes++;
1792
1793         } while (clausegroups != NIL && !DoneMatchingIndexKeys(classes));
1794
1795         Assert(clausegroups == NIL);    /* else more groups than indexkeys... */
1796
1797         return FastListValue(&resultquals);
1798 }
1799
1800 /*
1801  * expand_indexqual_condition --- expand a single indexqual condition
1802  */
1803 static List *
1804 expand_indexqual_condition(Expr *clause, Oid opclass)
1805 {
1806         /* we know these will succeed */
1807         Node       *leftop = get_leftop(clause);
1808         Node       *rightop = get_rightop(clause);
1809         Oid                     expr_op = ((OpExpr *) clause)->opno;
1810         Const      *patt = (Const *) rightop;
1811         Const      *prefix = NULL;
1812         Const      *rest = NULL;
1813         Pattern_Prefix_Status pstatus;
1814         List       *result;
1815
1816         switch (expr_op)
1817         {
1818                         /*
1819                          * LIKE and regex operators are not members of any index
1820                          * opclass, so if we find one in an indexqual list we can
1821                          * assume that it was accepted by
1822                          * match_special_index_operator().
1823                          */
1824                 case OID_TEXT_LIKE_OP:
1825                 case OID_BPCHAR_LIKE_OP:
1826                 case OID_NAME_LIKE_OP:
1827                 case OID_BYTEA_LIKE_OP:
1828                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
1829                                                                                    &prefix, &rest);
1830                         result = prefix_quals(leftop, opclass, prefix, pstatus);
1831                         break;
1832
1833                 case OID_TEXT_ICLIKE_OP:
1834                 case OID_BPCHAR_ICLIKE_OP:
1835                 case OID_NAME_ICLIKE_OP:
1836                         /* the right-hand const is type text for all of these */
1837                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
1838                                                                                    &prefix, &rest);
1839                         result = prefix_quals(leftop, opclass, prefix, pstatus);
1840                         break;
1841
1842                 case OID_TEXT_REGEXEQ_OP:
1843                 case OID_BPCHAR_REGEXEQ_OP:
1844                 case OID_NAME_REGEXEQ_OP:
1845                         /* the right-hand const is type text for all of these */
1846                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex,
1847                                                                                    &prefix, &rest);
1848                         result = prefix_quals(leftop, opclass, prefix, pstatus);
1849                         break;
1850
1851                 case OID_TEXT_ICREGEXEQ_OP:
1852                 case OID_BPCHAR_ICREGEXEQ_OP:
1853                 case OID_NAME_ICREGEXEQ_OP:
1854                         /* the right-hand const is type text for all of these */
1855                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
1856                                                                                    &prefix, &rest);
1857                         result = prefix_quals(leftop, opclass, prefix, pstatus);
1858                         break;
1859
1860                 case OID_INET_SUB_OP:
1861                 case OID_INET_SUBEQ_OP:
1862                 case OID_CIDR_SUB_OP:
1863                 case OID_CIDR_SUBEQ_OP:
1864                         result = network_prefix_quals(leftop, expr_op, opclass,
1865                                                                                   patt->constvalue);
1866                         break;
1867
1868                 default:
1869                         result = makeList1(clause);
1870                         break;
1871         }
1872
1873         return result;
1874 }
1875
1876 /*
1877  * Given a fixed prefix that all the "leftop" values must have,
1878  * generate suitable indexqual condition(s).  opclass is the index
1879  * operator class; we use it to deduce the appropriate comparison
1880  * operators and operand datatypes.
1881  */
1882 static List *
1883 prefix_quals(Node *leftop, Oid opclass,
1884                          Const *prefix_const, Pattern_Prefix_Status pstatus)
1885 {
1886         List       *result;
1887         Oid                     datatype;
1888         Oid                     oproid;
1889         Expr       *expr;
1890         Const      *greaterstr;
1891
1892         Assert(pstatus != Pattern_Prefix_None);
1893
1894         switch (opclass)
1895         {
1896                 case TEXT_BTREE_OPS_OID:
1897                 case TEXT_PATTERN_BTREE_OPS_OID:
1898                         datatype = TEXTOID;
1899                         break;
1900
1901                 case VARCHAR_BTREE_OPS_OID:
1902                 case VARCHAR_PATTERN_BTREE_OPS_OID:
1903                         datatype = VARCHAROID;
1904                         break;
1905
1906                 case BPCHAR_BTREE_OPS_OID:
1907                 case BPCHAR_PATTERN_BTREE_OPS_OID:
1908                         datatype = BPCHAROID;
1909                         break;
1910
1911                 case NAME_BTREE_OPS_OID:
1912                 case NAME_PATTERN_BTREE_OPS_OID:
1913                         datatype = NAMEOID;
1914                         break;
1915
1916                 case BYTEA_BTREE_OPS_OID:
1917                         datatype = BYTEAOID;
1918                         break;
1919
1920                 default:
1921                         /* shouldn't get here */
1922                         elog(ERROR, "unexpected opclass: %u", opclass);
1923                         return NIL;
1924         }
1925
1926         /*
1927          * If necessary, coerce the prefix constant to the right type. The
1928          * given prefix constant is either text or bytea type.
1929          */
1930         if (prefix_const->consttype != datatype)
1931         {
1932                 char       *prefix;
1933
1934                 switch (prefix_const->consttype)
1935                 {
1936                         case TEXTOID:
1937                                 prefix = DatumGetCString(DirectFunctionCall1(textout,
1938                                                                                           prefix_const->constvalue));
1939                                 break;
1940                         case BYTEAOID:
1941                                 prefix = DatumGetCString(DirectFunctionCall1(byteaout,
1942                                                                                           prefix_const->constvalue));
1943                                 break;
1944                         default:
1945                                 elog(ERROR, "unexpected const type: %u",
1946                                          prefix_const->consttype);
1947                                 return NIL;
1948                 }
1949                 prefix_const = string_to_const(prefix, datatype);
1950                 pfree(prefix);
1951         }
1952
1953         /*
1954          * If we found an exact-match pattern, generate an "=" indexqual.
1955          */
1956         if (pstatus == Pattern_Prefix_Exact)
1957         {
1958                 oproid = get_opclass_member(opclass, InvalidOid,
1959                                                                         BTEqualStrategyNumber);
1960                 if (oproid == InvalidOid)
1961                         elog(ERROR, "no = operator for opclass %u", opclass);
1962                 expr = make_opclause(oproid, BOOLOID, false,
1963                                                          (Expr *) leftop, (Expr *) prefix_const);
1964                 result = makeList1(expr);
1965                 return result;
1966         }
1967
1968         /*
1969          * Otherwise, we have a nonempty required prefix of the values.
1970          *
1971          * We can always say "x >= prefix".
1972          */
1973         oproid = get_opclass_member(opclass, InvalidOid,
1974                                                                 BTGreaterEqualStrategyNumber);
1975         if (oproid == InvalidOid)
1976                 elog(ERROR, "no >= operator for opclass %u", opclass);
1977         expr = make_opclause(oproid, BOOLOID, false,
1978                                                  (Expr *) leftop, (Expr *) prefix_const);
1979         result = makeList1(expr);
1980
1981         /*-------
1982          * If we can create a string larger than the prefix, we can say
1983          * "x < greaterstr".
1984          *-------
1985          */
1986         greaterstr = make_greater_string(prefix_const);
1987         if (greaterstr)
1988         {
1989                 oproid = get_opclass_member(opclass, InvalidOid,
1990                                                                         BTLessStrategyNumber);
1991                 if (oproid == InvalidOid)
1992                         elog(ERROR, "no < operator for opclass %u", opclass);
1993                 expr = make_opclause(oproid, BOOLOID, false,
1994                                                          (Expr *) leftop, (Expr *) greaterstr);
1995                 result = lappend(result, expr);
1996         }
1997
1998         return result;
1999 }
2000
2001 /*
2002  * Given a leftop and a rightop, and a inet-class sup/sub operator,
2003  * generate suitable indexqual condition(s).  expr_op is the original
2004  * operator, and opclass is the index opclass.
2005  */
2006 static List *
2007 network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass, Datum rightop)
2008 {
2009         bool            is_eq;
2010         Oid                     datatype;
2011         Oid                     opr1oid;
2012         Oid                     opr2oid;
2013         Datum           opr1right;
2014         Datum           opr2right;
2015         List       *result;
2016         Expr       *expr;
2017
2018         switch (expr_op)
2019         {
2020                 case OID_INET_SUB_OP:
2021                         datatype = INETOID;
2022                         is_eq = false;
2023                         break;
2024                 case OID_INET_SUBEQ_OP:
2025                         datatype = INETOID;
2026                         is_eq = true;
2027                         break;
2028                 case OID_CIDR_SUB_OP:
2029                         datatype = CIDROID;
2030                         is_eq = false;
2031                         break;
2032                 case OID_CIDR_SUBEQ_OP:
2033                         datatype = CIDROID;
2034                         is_eq = true;
2035                         break;
2036                 default:
2037                         elog(ERROR, "unexpected operator: %u", expr_op);
2038                         return NIL;
2039         }
2040
2041         /*
2042          * create clause "key >= network_scan_first( rightop )", or ">" if the
2043          * operator disallows equality.
2044          */
2045         if (is_eq)
2046         {
2047                 opr1oid = get_opclass_member(opclass, InvalidOid,
2048                                                                          BTGreaterEqualStrategyNumber);
2049                 if (opr1oid == InvalidOid)
2050                         elog(ERROR, "no >= operator for opclass %u", opclass);
2051         }
2052         else
2053         {
2054                 opr1oid = get_opclass_member(opclass, InvalidOid,
2055                                                                          BTGreaterStrategyNumber);
2056                 if (opr1oid == InvalidOid)
2057                         elog(ERROR, "no > operator for opclass %u", opclass);
2058         }
2059
2060         opr1right = network_scan_first(rightop);
2061
2062         expr = make_opclause(opr1oid, BOOLOID, false,
2063                                                  (Expr *) leftop,
2064                                                  (Expr *) makeConst(datatype, -1, opr1right,
2065                                                                                         false, false));
2066         result = makeList1(expr);
2067
2068         /* create clause "key <= network_scan_last( rightop )" */
2069
2070         opr2oid = get_opclass_member(opclass, InvalidOid,
2071                                                                  BTLessEqualStrategyNumber);
2072         if (opr2oid == InvalidOid)
2073                 elog(ERROR, "no <= operator for opclass %u", opclass);
2074
2075         opr2right = network_scan_last(rightop);
2076
2077         expr = make_opclause(opr2oid, BOOLOID, false,
2078                                                  (Expr *) leftop,
2079                                                  (Expr *) makeConst(datatype, -1, opr2right,
2080                                                                                         false, false));
2081         result = lappend(result, expr);
2082
2083         return result;
2084 }
2085
2086 /*
2087  * Handy subroutines for match_special_index_operator() and friends.
2088  */
2089
2090 /*
2091  * Generate a Datum of the appropriate type from a C string.
2092  * Note that all of the supported types are pass-by-ref, so the
2093  * returned value should be pfree'd if no longer needed.
2094  */
2095 static Datum
2096 string_to_datum(const char *str, Oid datatype)
2097 {
2098         /*
2099          * We cheat a little by assuming that textin() will do for bpchar and
2100          * varchar constants too...
2101          */
2102         if (datatype == NAMEOID)
2103                 return DirectFunctionCall1(namein, CStringGetDatum(str));
2104         else if (datatype == BYTEAOID)
2105                 return DirectFunctionCall1(byteain, CStringGetDatum(str));
2106         else
2107                 return DirectFunctionCall1(textin, CStringGetDatum(str));
2108 }
2109
2110 /*
2111  * Generate a Const node of the appropriate type from a C string.
2112  */
2113 static Const *
2114 string_to_const(const char *str, Oid datatype)
2115 {
2116         Datum           conval = string_to_datum(str, datatype);
2117
2118         return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2119                                          conval, false, false);
2120 }