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-2000, PostgreSQL, Inc
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.90 2000/07/27 23:15:56 tgl Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17
  18 #include <math.h>
  19
  20 #include "access/heapam.h"
  21 #include "access/nbtree.h"
  22 #include "catalog/catname.h"
  23 #include "catalog/pg_amop.h"
  24 #include "catalog/pg_operator.h"
  25 #include "executor/executor.h"
  26 #include "nodes/makefuncs.h"
  27 #include "nodes/nodeFuncs.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_coerce.h"
  35 #include "parser/parse_expr.h"
  36 #include "parser/parse_oper.h"
  37 #include "utils/builtins.h"
  38 #include "utils/fmgroids.h"
  39 #include "utils/lsyscache.h"
  40 #include "utils/syscache.h"
  41
  42
  43 /*
  44  * DoneMatchingIndexKeys() - MACRO
  45  *
  46  * Determine whether we should continue matching index keys in a clause.
  47  * Depends on if there are more to match or if this is a functional index.
  48  * In the latter case we stop after the first match since the there can
  49  * be only key (i.e. the function's return value) and the attributes in
  50  * keys list represent the arguments to the function.  -mer 3 Oct. 1991
  51  */
  52 #define DoneMatchingIndexKeys(indexkeys, index) \
  53                 (indexkeys[0] == 0 || \
  54                  (index->indproc != InvalidOid))
  55
  56 #define is_indexable_operator(clause,opclass,relam,indexkey_on_left) \
  57         (indexable_operator(clause,opclass,relam,indexkey_on_left) != InvalidOid)
  58
  59
  60 static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index,
  61                                           List *restrictinfo_list);
  62 static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index,
  63                                          List *or_clauses,
  64                                          List *other_matching_indices);
  65 static bool match_or_subclause_to_indexkey(RelOptInfo *rel,
  66                                                            IndexOptInfo *index,
  67                                                            Expr *clause);
  68 static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index,
  69                                                   int *indexkeys, Oid *classes,
  70                                                   List *restrictinfo_list);
  71 static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel,
  72                                                                 IndexOptInfo *index,
  73                                                                 int *indexkeys, Oid *classes,
  74                                                                 List *join_cinfo_list,
  75                                                                 List *restr_cinfo_list);
  76 static bool match_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index,
  77                                                  int indexkey, Oid opclass,
  78                                                  Expr *clause, bool join);
  79 static bool pred_test(List *predicate_list, List *restrictinfo_list,
  80                   List *joininfo_list);
  81 static bool one_pred_test(Expr *predicate, List *restrictinfo_list);
  82 static bool one_pred_clause_expr_test(Expr *predicate, Node *clause);
  83 static bool one_pred_clause_test(Expr *predicate, Node *clause);
  84 static bool clause_pred_clause_test(Expr *predicate, Node *clause);
  85 static void indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index,
  86                                           List *joininfo_list, List *restrictinfo_list,
  87                                           List **clausegroups, List **outerrelids);
  88 static List *index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
  89                                 List *clausegroup_list, List *outerrelids_list);
  90 static bool useful_for_mergejoin(RelOptInfo *rel, IndexOptInfo *index,
  91                                          List *joininfo_list);
  92 static bool useful_for_ordering(Query *root, RelOptInfo *rel,
  93                                         IndexOptInfo *index,
  94                                         ScanDirection scandir);
  95 static bool match_index_to_operand(int indexkey, Var *operand,
  96                                            RelOptInfo *rel, IndexOptInfo *index);
  97 static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel,
  98                                            IndexOptInfo *index);
  99 static bool match_special_index_operator(Expr *clause, Oid opclass, Oid relam,
 100                                                          bool indexkey_on_left);
 101 static List *prefix_quals(Var *leftop, Oid expr_op,
 102                          char *prefix, Pattern_Prefix_Status pstatus);
 103 static Oid      find_operator(const char *opname, Oid datatype);
 104 static Datum string_to_datum(const char *str, Oid datatype);
 105 static Const *string_to_const(const char *str, Oid datatype);
 106
 107
 108 /*
 109  * create_index_paths()
 110  *        Generate all interesting index paths for the given relation.
 111  *        Candidate paths are added to the rel's pathlist (using add_path).
 112  *        Additional IndexPath nodes may also be added to rel's innerjoin list.
 113  *
 114  * To be considered for an index scan, an index must match one or more
 115  * restriction clauses or join clauses from the query's qual condition,
 116  * or match the query's ORDER BY condition.
 117  *
 118  * There are two basic kinds of index scans.  A "plain" index scan uses
 119  * only restriction clauses (possibly none at all) in its indexqual,
 120  * so it can be applied in any context.  An "innerjoin" index scan uses
 121  * join clauses (plus restriction clauses, if available) in its indexqual.
 122  * Therefore it can only be used as the inner relation of a nestloop
 123  * join against an outer rel that includes all the other rels mentioned
 124  * in its join clauses.  In that context, values for the other rels'
 125  * attributes are available and fixed during any one scan of the indexpath.
 126  *
 127  * An IndexPath is generated and submitted to add_path() for each index
 128  * this routine deems potentially interesting for the current query
 129  * (at most one IndexPath per index on the given relation).  An innerjoin
 130  * path is also generated for each interesting combination of outer join
 131  * relations.  The innerjoin paths are *not* passed to add_path(), but are
 132  * appended to the "innerjoin" list of the relation for later consideration
 133  * in nested-loop joins.
 134  *
 135  * 'rel' is the relation for which we want to generate index paths
 136  * 'indices' is a list of available indexes for 'rel'
 137  * 'restrictinfo_list' is a list of restrictinfo nodes for 'rel'
 138  * 'joininfo_list' is a list of joininfo nodes for 'rel'
 139  */
 140 void
 141 create_index_paths(Query *root,
 142                                    RelOptInfo *rel,
 143                                    List *indices,
 144                                    List *restrictinfo_list,
 145                                    List *joininfo_list)
 146 {
 147         List       *ilist;
 148
 149         foreach(ilist, indices)
 150         {
 151                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
 152                 List       *restrictclauses;
 153                 List       *joinclausegroups;
 154                 List       *joinouterrelids;
 155
 156                 /*
 157                  * If this is a partial index, we can only use it if it passes the
 158                  * predicate test.
 159                  */
 160                 if (index->indpred != NIL)
 161                         if (!pred_test(index->indpred, restrictinfo_list, joininfo_list))
 162                                 continue;
 163
 164                 /*
 165                  * 1. Try matching the index against subclauses of restriction
 166                  * 'or' clauses (ie, 'or' clauses that reference only this
 167                  * relation). The restrictinfo nodes for the 'or' clauses are
 168                  * marked with lists of the matching indices.  No paths are
 169                  * actually created now; that will be done in orindxpath.c after
 170                  * all indexes for the rel have been examined.  (We need to do it
 171                  * that way because we can potentially use a different index for
 172                  * each subclause of an 'or', so we can't build a path for an 'or'
 173                  * clause until all indexes have been matched against it.)
 174                  *
 175                  * We don't even think about special handling of 'or' clauses that
 176                  * involve more than one relation (ie, are join clauses). Can we
 177                  * do anything useful with those?
 178                  */
 179                 match_index_orclauses(rel, index, restrictinfo_list);
 180
 181                 /*
 182                  * 2. If the keys of this index match any of the available
 183                  * non-'or' restriction clauses, then create a path using those
 184                  * clauses as indexquals.
 185                  */
 186                 restrictclauses = group_clauses_by_indexkey(rel,
 187                                                                                                         index,
 188                                                                                                         index->indexkeys,
 189                                                                                                         index->classlist,
 190                                                                                                         restrictinfo_list);
 191
 192                 if (restrictclauses != NIL)
 193                         add_path(rel, (Path *) create_index_path(root, rel, index,
 194                                                                                                          restrictclauses,
 195                                                                                            NoMovementScanDirection));
 196
 197                 /*
 198                  * 3. If this index can be used for a mergejoin, then create an
 199                  * index path for it even if there were no restriction clauses.
 200                  * (If there were, there is no need to make another index path.)
 201                  * This will allow the index to be considered as a base for a
 202                  * mergejoin in later processing.  Similarly, if the index matches
 203                  * the ordering that is needed for the overall query result, make
 204                  * an index path for it even if there is no other reason to do so.
 205                  */
 206                 if (restrictclauses == NIL)
 207                 {
 208                         if (useful_for_mergejoin(rel, index, joininfo_list) ||
 209                          useful_for_ordering(root, rel, index, ForwardScanDirection))
 210                                 add_path(rel, (Path *)
 211                                                  create_index_path(root, rel, index,
 212                                                                                    restrictclauses,
 213                                                                                    ForwardScanDirection));
 214                 }
 215
 216                 /*
 217                  * Currently, backwards scan is never considered except for the
 218                  * case of matching a query result ordering.  Possibly should
 219                  * consider it in other places?
 220                  */
 221                 if (useful_for_ordering(root, rel, index, BackwardScanDirection))
 222                         add_path(rel, (Path *)
 223                                          create_index_path(root, rel, index,
 224                                                                            restrictclauses,
 225                                                                            BackwardScanDirection));
 226
 227                 /*
 228                  * 4. Create an innerjoin index path for each combination of other
 229                  * rels used in available join clauses.  These paths will be
 230                  * considered as the inner side of nestloop joins against those
 231                  * sets of other rels.  indexable_joinclauses() finds sets of
 232                  * clauses that can be used with each combination of outer rels,
 233                  * and index_innerjoin builds the paths themselves.  We add the
 234                  * paths to the rel's innerjoin list, NOT to the result list.
 235                  */
 236                 indexable_joinclauses(rel, index,
 237                                                           joininfo_list, restrictinfo_list,
 238                                                           &joinclausegroups,
 239                                                           &joinouterrelids);
 240                 if (joinclausegroups != NIL)
 241                 {
 242                         rel->innerjoin = nconc(rel->innerjoin,
 243                                                                    index_innerjoin(root, rel, index,
 244                                                                                                    joinclausegroups,
 245                                                                                                    joinouterrelids));
 246                 }
 247         }
 248 }
 249
 250
 251 /****************************************************************************
 252  *              ----  ROUTINES TO PROCESS 'OR' CLAUSES  ----
 253  ****************************************************************************/
 254
 255
 256 /*
 257  * match_index_orclauses
 258  *        Attempt to match an index against subclauses within 'or' clauses.
 259  *        Each subclause that does match is marked with the index's node.
 260  *
 261  *        Essentially, this adds 'index' to the list of subclause indices in
 262  *        the RestrictInfo field of each of the 'or' clauses where it matches.
 263  *        NOTE: we can use storage in the RestrictInfo for this purpose because
 264  *        this processing is only done on single-relation restriction clauses.
 265  *        Therefore, we will never have indexes for more than one relation
 266  *        mentioned in the same RestrictInfo node's list.
 267  *
 268  * 'rel' is the node of the relation on which the index is defined.
 269  * 'index' is the index node.
 270  * 'restrictinfo_list' is the list of available restriction clauses.
 271  */
 272 static void
 273 match_index_orclauses(RelOptInfo *rel,
 274                                           IndexOptInfo *index,
 275                                           List *restrictinfo_list)
 276 {
 277         List       *i;
 278
 279         foreach(i, restrictinfo_list)
 280         {
 281                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
 282
 283                 if (restriction_is_or_clause(restrictinfo))
 284                 {
 285
 286                         /*
 287                          * Add this index to the subclause index list for each
 288                          * subclause that it matches.
 289                          */
 290                         restrictinfo->subclauseindices =
 291                                 match_index_orclause(rel, index,
 292                                                                          restrictinfo->clause->args,
 293                                                                          restrictinfo->subclauseindices);
 294                 }
 295         }
 296 }
 297
 298 /*
 299  * match_index_orclause
 300  *        Attempts to match an index against the subclauses of an 'or' clause.
 301  *
 302  *        A match means that:
 303  *        (1) the operator within the subclause can be used with the
 304  *                index's specified operator class, and
 305  *        (2) one operand of the subclause matches the index key.
 306  *
 307  *        If a subclause is an 'and' clause, then it matches if any of its
 308  *        subclauses is an opclause that matches.
 309  *
 310  * 'or_clauses' is the list of subclauses within the 'or' clause
 311  * 'other_matching_indices' is the list of information on other indices
 312  *              that have already been matched to subclauses within this
 313  *              particular 'or' clause (i.e., a list previously generated by
 314  *              this routine), or NIL if this routine has not previously been
 315  *              run for this 'or' clause.
 316  *
 317  * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where
 318  * a,b,c are nodes of indices that match the first subclause in
 319  * 'or-clauses', d,e,f match the second subclause, no indices
 320  * match the third, g,h match the fourth, etc.
 321  */
 322 static List *
 323 match_index_orclause(RelOptInfo *rel,
 324                                          IndexOptInfo *index,
 325                                          List *or_clauses,
 326                                          List *other_matching_indices)
 327 {
 328         List       *matching_indices;
 329         List       *index_list;
 330         List       *clist;
 331
 332         /*
 333          * first time through, we create list of same length as OR clause,
 334          * containing an empty sublist for each subclause.
 335          */
 336         if (!other_matching_indices)
 337         {
 338                 matching_indices = NIL;
 339                 foreach(clist, or_clauses)
 340                         matching_indices = lcons(NIL, matching_indices);
 341         }
 342         else
 343                 matching_indices = other_matching_indices;
 344
 345         index_list = matching_indices;
 346
 347         foreach(clist, or_clauses)
 348         {
 349                 Expr       *clause = lfirst(clist);
 350
 351                 if (match_or_subclause_to_indexkey(rel, index, clause))
 352                 {
 353                         /* OK to add this index to sublist for this subclause */
 354                         lfirst(matching_indices) = lcons(index,
 355                                                                                          lfirst(matching_indices));
 356                 }
 357
 358                 matching_indices = lnext(matching_indices);
 359         }
 360
 361         return index_list;
 362 }
 363
 364 /*
 365  * See if a subclause of an OR clause matches an index.
 366  *
 367  * We accept the subclause if it is an operator clause that matches the
 368  * index, or if it is an AND clause any of whose members is an opclause
 369  * that matches the index.
 370  *
 371  * For multi-key indexes, we only look for matches to the first key;
 372  * without such a match the index is useless.  If the clause is an AND
 373  * then we may be able to extract additional subclauses to use with the
 374  * later indexkeys, but we need not worry about that until
 375  * extract_or_indexqual_conditions() is called (if it ever is).
 376  */
 377 static bool
 378 match_or_subclause_to_indexkey(RelOptInfo *rel,
 379                                                            IndexOptInfo *index,
 380                                                            Expr *clause)
 381 {
 382         int                     indexkey = index->indexkeys[0];
 383         Oid                     opclass = index->classlist[0];
 384
 385         if (and_clause((Node *) clause))
 386         {
 387                 List       *item;
 388
 389                 foreach(item, clause->args)
 390                 {
 391                         if (match_clause_to_indexkey(rel, index, indexkey, opclass,
 392                                                                                  lfirst(item), false))
 393                                 return true;
 394                 }
 395                 return false;
 396         }
 397         else
 398                 return match_clause_to_indexkey(rel, index, indexkey, opclass,
 399                                                                                 clause, false);
 400 }
 401
 402 /*
 403  * Given an OR subclause that has previously been determined to match
 404  * the specified index, extract a list of specific opclauses that can be
 405  * used as indexquals.
 406  *
 407  * In the simplest case this just means making a one-element list of the
 408  * given opclause.      However, if the OR subclause is an AND, we have to
 409  * scan it to find the opclause(s) that match the index.  (There should
 410  * be at least one, if match_or_subclause_to_indexkey succeeded, but there
 411  * could be more.)      Also, we apply expand_indexqual_conditions() to convert
 412  * any special matching opclauses to indexable operators.
 413  *
 414  * The passed-in clause is not changed.
 415  */
 416 List *
 417 extract_or_indexqual_conditions(RelOptInfo *rel,
 418                                                                 IndexOptInfo *index,
 419                                                                 Expr *orsubclause)
 420 {
 421         List       *quals = NIL;
 422
 423         if (and_clause((Node *) orsubclause))
 424         {
 425                 /*
 426                  * Extract relevant sub-subclauses in indexkey order.  This is just
 427                  * like group_clauses_by_indexkey() except that the input and output
 428                  * are lists of bare clauses, not of RestrictInfo nodes.
 429                  */
 430                 int                *indexkeys = index->indexkeys;
 431                 Oid                *classes = index->classlist;
 432
 433                 do
 434                 {
 435                         int                     curIndxKey = indexkeys[0];
 436                         Oid                     curClass = classes[0];
 437                         List       *clausegroup = NIL;
 438                         List       *item;
 439
 440                         foreach(item, orsubclause->args)
 441                         {
 442                                 if (match_clause_to_indexkey(rel, index,
 443                                                                                          curIndxKey, curClass,
 444                                                                                          lfirst(item), false))
 445                                         clausegroup = lappend(clausegroup, lfirst(item));
 446                         }
 447
 448                         /*
 449                          * If no clauses match this key, we're done; we don't want to look
 450                          * at keys to its right.
 451                          */
 452                         if (clausegroup == NIL)
 453                                 break;
 454
 455                         quals = nconc(quals, clausegroup);
 456
 457                         indexkeys++;
 458                         classes++;
 459                 } while (!DoneMatchingIndexKeys(indexkeys, index));
 460
 461                 if (quals == NIL)
 462                         elog(ERROR, "extract_or_indexqual_conditions: no matching clause");
 463         }
 464         else
 465         {
 466                 /* we assume the caller passed a valid indexable qual */
 467                 quals = lcons(orsubclause, NIL);
 468         }
 469
 470         return expand_indexqual_conditions(quals);
 471 }
 472
 473
 474 /****************************************************************************
 475  *                              ----  ROUTINES TO CHECK RESTRICTIONS  ----
 476  ****************************************************************************/
 477
 478
 479 /*
 480  * group_clauses_by_indexkey
 481  *        Generates a list of restriction clauses that can be used with an index.
 482  *
 483  * 'rel' is the node of the relation itself.
 484  * 'index' is a index on 'rel'.
 485  * 'indexkeys' are the index keys to be matched.
 486  * 'classes' are the classes of the index operators on those keys.
 487  * 'restrictinfo_list' is the list of available restriction clauses for 'rel'.
 488  *
 489  * Returns a list of all the RestrictInfo nodes for clauses that can be
 490  * used with this index.
 491  *
 492  * The list is ordered by index key.  (This is not depended on by any part
 493  * of the planner, as far as I can tell; but some parts of the executor
 494  * do assume that the indxqual list ultimately delivered to the executor
 495  * is so ordered.  One such place is _bt_orderkeys() in the btree support.
 496  * Perhaps that ought to be fixed someday --- tgl 7/00)
 497  *
 498  * Note that in a multi-key index, we stop if we find a key that cannot be
 499  * used with any clause.  For example, given an index on (A,B,C), we might
 500  * return (C1 C2 C3 C4) if we find that clauses C1 and C2 use column A,
 501  * clauses C3 and C4 use column B, and no clauses use column C.  But if
 502  * no clauses match B we will return (C1 C2), whether or not there are
 503  * clauses matching column C, because the executor couldn't use them anyway.
 504  */
 505 static List *
 506 group_clauses_by_indexkey(RelOptInfo *rel,
 507                                                   IndexOptInfo *index,
 508                                                   int *indexkeys,
 509                                                   Oid *classes,
 510                                                   List *restrictinfo_list)
 511 {
 512         List       *clausegroup_list = NIL;
 513
 514         if (restrictinfo_list == NIL || indexkeys[0] == 0)
 515                 return NIL;
 516
 517         do
 518         {
 519                 int                     curIndxKey = indexkeys[0];
 520                 Oid                     curClass = classes[0];
 521                 List       *clausegroup = NIL;
 522                 List       *curCinfo;
 523
 524                 foreach(curCinfo, restrictinfo_list)
 525                 {
 526                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
 527
 528                         if (match_clause_to_indexkey(rel,
 529                                                                                  index,
 530                                                                                  curIndxKey,
 531                                                                                  curClass,
 532                                                                                  rinfo->clause,
 533                                                                                  false))
 534                                 clausegroup = lappend(clausegroup, rinfo);
 535                 }
 536
 537                 /*
 538                  * If no clauses match this key, we're done; we don't want to look
 539                  * at keys to its right.
 540                  */
 541                 if (clausegroup == NIL)
 542                         break;
 543
 544                 clausegroup_list = nconc(clausegroup_list, clausegroup);
 545
 546                 indexkeys++;
 547                 classes++;
 548
 549         } while (!DoneMatchingIndexKeys(indexkeys, index));
 550
 551         /* clausegroup_list holds all matched clauses ordered by indexkeys */
 552         return clausegroup_list;
 553 }
 554
 555 /*
 556  * group_clauses_by_ikey_for_joins
 557  *        Generates a list of join clauses that can be used with an index
 558  *        to scan the inner side of a nestloop join.
 559  *
 560  * This is much like group_clauses_by_indexkey(), but we consider both
 561  * join and restriction clauses.  For each indexkey in the index, we
 562  * accept both join and restriction clauses that match it, since both
 563  * will make useful indexquals if the index is being used to scan the
 564  * inner side of a nestloop join.  But there must be at least one matching
 565  * join clause, or we return NIL indicating that this index isn't useful
 566  * for nestloop joining.
 567  */
 568 static List *
 569 group_clauses_by_ikey_for_joins(RelOptInfo *rel,
 570                                                                 IndexOptInfo *index,
 571                                                                 int *indexkeys,
 572                                                                 Oid *classes,
 573                                                                 List *join_cinfo_list,
 574                                                                 List *restr_cinfo_list)
 575 {
 576         List       *clausegroup_list = NIL;
 577         bool            jfound = false;
 578
 579         if (join_cinfo_list == NIL || indexkeys[0] == 0)
 580                 return NIL;
 581
 582         do
 583         {
 584                 int                     curIndxKey = indexkeys[0];
 585                 Oid                     curClass = classes[0];
 586                 List       *clausegroup = NIL;
 587                 List       *curCinfo;
 588
 589                 foreach(curCinfo, join_cinfo_list)
 590                 {
 591                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
 592
 593                         if (match_clause_to_indexkey(rel,
 594                                                                                  index,
 595                                                                                  curIndxKey,
 596                                                                                  curClass,
 597                                                                                  rinfo->clause,
 598                                                                                  true))
 599                         {
 600                                 clausegroup = lappend(clausegroup, rinfo);
 601                                 jfound = true;
 602                         }
 603                 }
 604                 foreach(curCinfo, restr_cinfo_list)
 605                 {
 606                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
 607
 608                         if (match_clause_to_indexkey(rel,
 609                                                                                  index,
 610                                                                                  curIndxKey,
 611                                                                                  curClass,
 612                                                                                  rinfo->clause,
 613                                                                                  false))
 614                                 clausegroup = lappend(clausegroup, rinfo);
 615                 }
 616
 617                 /*
 618                  * If no clauses match this key, we're done; we don't want to look
 619                  * at keys to its right.
 620                  */
 621                 if (clausegroup == NIL)
 622                         break;
 623
 624                 clausegroup_list = nconc(clausegroup_list, clausegroup);
 625
 626                 indexkeys++;
 627                 classes++;
 628
 629         } while (!DoneMatchingIndexKeys(indexkeys, index));
 630
 631         /*
 632          * if no join clause was matched then there ain't clauses for joins at
 633          * all.
 634          */
 635         if (!jfound)
 636         {
 637                 freeList(clausegroup_list);
 638                 return NIL;
 639         }
 640
 641         /* clausegroup_list holds all matched clauses ordered by indexkeys */
 642         return clausegroup_list;
 643 }
 644
 645
 646 /*
 647  * match_clause_to_indexkey()
 648  *        Determines whether a restriction or join clause matches
 649  *        a key of an index.
 650  *
 651  *        To match, the clause:
 652
 653  *        (1a) for a restriction clause: must be in the form (indexkey op const)
 654  *                 or (const op indexkey), or
 655  *        (1b) for a join clause: must be in the form (indexkey op others)
 656  *                 or (others op indexkey), where others is an expression involving
 657  *                 only vars of the other relation(s); and
 658  *        (2)  must contain an operator which is in the same class as the index
 659  *                 operator for this key, or is a "special" operator as recognized
 660  *                 by match_special_index_operator().
 661  *
 662  *        Presently, the executor can only deal with indexquals that have the
 663  *        indexkey on the left, so we can only use clauses that have the indexkey
 664  *        on the right if we can commute the clause to put the key on the left.
 665  *        We do not actually do the commuting here, but we check whether a
 666  *        suitable commutator operator is available.
 667  *
 668  *        Note that in the join case, we already know that the clause as a
 669  *        whole uses vars from the interesting set of relations.  But we need
 670  *        to defend against expressions like (a.f1 OP (b.f2 OP a.f3)); that's
 671  *        not processable by an indexscan nestloop join, whereas
 672  *        (a.f1 OP (b.f2 OP c.f3)) is.
 673  *
 674  * 'rel' is the relation of interest.
 675  * 'index' is an index on 'rel'.
 676  * 'indexkey' is a key of 'index'.
 677  * 'opclass' is the corresponding operator class.
 678  * 'clause' is the clause to be tested.
 679  * 'join' is true if we are considering this clause for joins.
 680  *
 681  * Returns true if the clause can be used with this index key.
 682  *
 683  * NOTE:  returns false if clause is an OR or AND clause; it is the
 684  * responsibility of higher-level routines to cope with those.
 685  */
 686 static bool
 687 match_clause_to_indexkey(RelOptInfo *rel,
 688                                                  IndexOptInfo *index,
 689                                                  int indexkey,
 690                                                  Oid opclass,
 691                                                  Expr *clause,
 692                                                  bool join)
 693 {
 694         Var                *leftop,
 695                            *rightop;
 696
 697         /* Clause must be a binary opclause. */
 698         if (!is_opclause((Node *) clause))
 699                 return false;
 700         leftop = get_leftop(clause);
 701         rightop = get_rightop(clause);
 702         if (!leftop || !rightop)
 703                 return false;
 704
 705         if (!join)
 706         {
 707
 708                 /*
 709                  * Not considering joins, so check for clauses of the form:
 710                  * (indexkey operator constant) or (constant operator indexkey).
 711                  * We will accept a Param as being constant.
 712                  */
 713
 714                 if ((IsA(rightop, Const) ||IsA(rightop, Param)) &&
 715                         match_index_to_operand(indexkey, leftop, rel, index))
 716                 {
 717                         if (is_indexable_operator(clause, opclass, index->relam, true))
 718                                 return true;
 719
 720                         /*
 721                          * If we didn't find a member of the index's opclass, see
 722                          * whether it is a "special" indexable operator.
 723                          */
 724                         if (match_special_index_operator(clause, opclass, index->relam,
 725                                                                                          true))
 726                                 return true;
 727                         return false;
 728                 }
 729                 if ((IsA(leftop, Const) ||IsA(leftop, Param)) &&
 730                         match_index_to_operand(indexkey, rightop, rel, index))
 731                 {
 732                         if (is_indexable_operator(clause, opclass, index->relam, false))
 733                                 return true;
 734
 735                         /*
 736                          * If we didn't find a member of the index's opclass, see
 737                          * whether it is a "special" indexable operator.
 738                          */
 739                         if (match_special_index_operator(clause, opclass, index->relam,
 740                                                                                          false))
 741                                 return true;
 742                         return false;
 743                 }
 744         }
 745         else
 746         {
 747
 748                 /*
 749                  * Check for an indexqual that could be handled by a nestloop
 750                  * join. We need the index key to be compared against an
 751                  * expression that uses none of the indexed relation's vars.
 752                  */
 753                 if (match_index_to_operand(indexkey, leftop, rel, index))
 754                 {
 755                         List       *othervarnos = pull_varnos((Node *) rightop);
 756                         bool            isIndexable;
 757
 758                         isIndexable = !intMember(lfirsti(rel->relids), othervarnos);
 759                         freeList(othervarnos);
 760                         if (isIndexable &&
 761                           is_indexable_operator(clause, opclass, index->relam, true))
 762                                 return true;
 763                 }
 764                 else if (match_index_to_operand(indexkey, rightop, rel, index))
 765                 {
 766                         List       *othervarnos = pull_varnos((Node *) leftop);
 767                         bool            isIndexable;
 768
 769                         isIndexable = !intMember(lfirsti(rel->relids), othervarnos);
 770                         freeList(othervarnos);
 771                         if (isIndexable &&
 772                          is_indexable_operator(clause, opclass, index->relam, false))
 773                                 return true;
 774                 }
 775         }
 776
 777         return false;
 778 }
 779
 780 /*
 781  * indexable_operator
 782  *        Does a binary opclause contain an operator matching the index's
 783  *        access method?
 784  *
 785  * If the indexkey is on the right, what we actually want to know
 786  * is whether the operator has a commutator operator that matches
 787  * the index's access method.
 788  *
 789  * We try both the straightforward match and matches that rely on
 790  * recognizing binary-compatible datatypes.  For example, if we have
 791  * an expression like "oid = 123", the operator will be oideqint4,
 792  * which we need to replace with oideq in order to recognize it as
 793  * matching an oid_ops index on the oid field.
 794  *
 795  * Returns the OID of the matching operator, or InvalidOid if no match.
 796  * Note that the returned OID will be different from the one in the given
 797  * expression if we used a binary-compatible substitution.      Also note that
 798  * if indexkey_on_left is FALSE (meaning we need to commute), the returned
 799  * OID is *not* commuted; it can be plugged directly into the given clause.
 800  */
 801 Oid
 802 indexable_operator(Expr *clause, Oid opclass, Oid relam,
 803                                    bool indexkey_on_left)
 804 {
 805         Oid                     expr_op = ((Oper *) clause->oper)->opno;
 806         Oid                     commuted_op;
 807         Oid                     ltype,
 808                                 rtype;
 809
 810         /* Get the commuted operator if necessary */
 811         if (indexkey_on_left)
 812                 commuted_op = expr_op;
 813         else
 814                 commuted_op = get_commutator(expr_op);
 815         if (commuted_op == InvalidOid)
 816                 return InvalidOid;
 817
 818         /* Done if the (commuted) operator is a member of the index's AM */
 819         if (op_class(commuted_op, opclass, relam))
 820                 return expr_op;
 821
 822         /*
 823          * Maybe the index uses a binary-compatible operator set.
 824          */
 825         ltype = exprType((Node *) get_leftop(clause));
 826         rtype = exprType((Node *) get_rightop(clause));
 827
 828         /*
 829          * make sure we have two different binary-compatible types...
 830          */
 831         if (ltype != rtype && IS_BINARY_COMPATIBLE(ltype, rtype))
 832         {
 833                 char       *opname = get_opname(expr_op);
 834                 Operator        newop;
 835
 836                 if (opname == NULL)
 837                         return InvalidOid;      /* probably shouldn't happen */
 838
 839                 /* Use the datatype of the index key */
 840                 if (indexkey_on_left)
 841                         newop = oper(opname, ltype, ltype, TRUE);
 842                 else
 843                         newop = oper(opname, rtype, rtype, TRUE);
 844
 845                 if (HeapTupleIsValid(newop))
 846                 {
 847                         Oid                     new_expr_op = oprid(newop);
 848
 849                         if (new_expr_op != expr_op)
 850                         {
 851
 852                                 /*
 853                                  * OK, we found a binary-compatible operator of the same
 854                                  * name; now does it match the index?
 855                                  */
 856                                 if (indexkey_on_left)
 857                                         commuted_op = new_expr_op;
 858                                 else
 859                                         commuted_op = get_commutator(new_expr_op);
 860                                 if (commuted_op == InvalidOid)
 861                                         return InvalidOid;
 862
 863                                 if (op_class(commuted_op, opclass, relam))
 864                                         return new_expr_op;
 865                         }
 866                 }
 867         }
 868
 869         return InvalidOid;
 870 }
 871
 872 /*
 873  * useful_for_mergejoin
 874  *        Determine whether the given index can support a mergejoin based
 875  *        on any available join clause.
 876  *
 877  *        We look to see whether the first indexkey of the index matches the
 878  *        left or right sides of any of the mergejoinable clauses and provides
 879  *        the ordering needed for that side.  If so, the index is useful.
 880  *        Matching a second or later indexkey is not useful unless there is
 881  *        also a mergeclause for the first indexkey, so we need not consider
 882  *        secondary indexkeys at this stage.
 883  *
 884  * 'rel' is the relation for which 'index' is defined
 885  * 'joininfo_list' is the list of JoinInfo nodes for 'rel'
 886  */
 887 static bool
 888 useful_for_mergejoin(RelOptInfo *rel,
 889                                          IndexOptInfo *index,
 890                                          List *joininfo_list)
 891 {
 892         int                *indexkeys = index->indexkeys;
 893         Oid                *ordering = index->ordering;
 894         List       *i;
 895
 896         if (!indexkeys || indexkeys[0] == 0 ||
 897                 !ordering || ordering[0] == InvalidOid)
 898                 return false;                   /* unordered index is not useful */
 899
 900         foreach(i, joininfo_list)
 901         {
 902                 JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
 903                 List       *j;
 904
 905                 foreach(j, joininfo->jinfo_restrictinfo)
 906                 {
 907                         RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
 908
 909                         if (restrictinfo->mergejoinoperator)
 910                         {
 911                                 if (restrictinfo->left_sortop == ordering[0] &&
 912                                         match_index_to_operand(indexkeys[0],
 913                                                                                 get_leftop(restrictinfo->clause),
 914                                                                                    rel, index))
 915                                         return true;
 916                                 if (restrictinfo->right_sortop == ordering[0] &&
 917                                         match_index_to_operand(indexkeys[0],
 918                                                                            get_rightop(restrictinfo->clause),
 919                                                                                    rel, index))
 920                                         return true;
 921                         }
 922                 }
 923         }
 924         return false;
 925 }
 926
 927 /*
 928  * useful_for_ordering
 929  *        Determine whether the given index can produce an ordering matching
 930  *        the order that is wanted for the query result.
 931  *
 932  * 'rel' is the relation for which 'index' is defined
 933  * 'scandir' is the contemplated scan direction
 934  */
 935 static bool
 936 useful_for_ordering(Query *root,
 937                                         RelOptInfo *rel,
 938                                         IndexOptInfo *index,
 939                                         ScanDirection scandir)
 940 {
 941         List       *index_pathkeys;
 942
 943         if (root->query_pathkeys == NIL)
 944                 return false;                   /* no special ordering requested */
 945
 946         index_pathkeys = build_index_pathkeys(root, rel, index, scandir);
 947
 948         if (index_pathkeys == NIL)
 949                 return false;                   /* unordered index */
 950
 951         return pathkeys_contained_in(root->query_pathkeys, index_pathkeys);
 952 }
 953
 954 /****************************************************************************
 955  *                              ----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS      ----
 956  ****************************************************************************/
 957
 958 /*
 959  * pred_test
 960  *        Does the "predicate inclusion test" for partial indexes.
 961  *
 962  *        Recursively checks whether the clauses in restrictinfo_list imply
 963  *        that the given predicate is true.
 964  *
 965  *        This routine (together with the routines it calls) iterates over
 966  *        ANDs in the predicate first, then reduces the qualification
 967  *        clauses down to their constituent terms, and iterates over ORs
 968  *        in the predicate last.  This order is important to make the test
 969  *        succeed whenever possible (assuming the predicate has been
 970  *        successfully cnfify()-ed). --Nels, Jan '93
 971  */
 972 static bool
 973 pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list)
 974 {
 975         List       *pred,
 976                            *items,
 977                            *item;
 978
 979         /*
 980          * Note: if Postgres tried to optimize queries by forming equivalence
 981          * classes over equi-joined attributes (i.e., if it recognized that a
 982          * qualification such as "where a.b=c.d and a.b=5" could make use of
 983          * an index on c.d), then we could use that equivalence class info
 984          * here with joininfo_list to do more complete tests for the usability
 985          * of a partial index.  For now, the test only uses restriction
 986          * clauses (those in restrictinfo_list). --Nels, Dec '92
 987          */
 988
 989         if (predicate_list == NULL)
 990                 return true;                    /* no predicate: the index is usable */
 991         if (restrictinfo_list == NULL)
 992                 return false;                   /* no restriction clauses: the test must
 993                                                                  * fail */
 994
 995         foreach(pred, predicate_list)
 996         {
 997
 998                 /*
 999                  * if any clause is not implied, the whole predicate is not
1000                  * implied
1001                  */
1002                 if (and_clause(lfirst(pred)))
1003                 {
1004                         items = ((Expr *) lfirst(pred))->args;
1005                         foreach(item, items)
1006                         {
1007                                 if (!one_pred_test(lfirst(item), restrictinfo_list))
1008                                         return false;
1009                         }
1010                 }
1011                 else if (!one_pred_test(lfirst(pred), restrictinfo_list))
1012                         return false;
1013         }
1014         return true;
1015 }
1016
1017
1018 /*
1019  * one_pred_test
1020  *        Does the "predicate inclusion test" for one conjunct of a predicate
1021  *        expression.
1022  */
1023 static bool
1024 one_pred_test(Expr *predicate, List *restrictinfo_list)
1025 {
1026         RestrictInfo *restrictinfo;
1027         List       *item;
1028
1029         Assert(predicate != NULL);
1030         foreach(item, restrictinfo_list)
1031         {
1032                 restrictinfo = (RestrictInfo *) lfirst(item);
1033                 /* if any clause implies the predicate, return true */
1034                 if (one_pred_clause_expr_test(predicate, (Node *) restrictinfo->clause))
1035                         return true;
1036         }
1037         return false;
1038 }
1039
1040
1041 /*
1042  * one_pred_clause_expr_test
1043  *        Does the "predicate inclusion test" for a general restriction-clause
1044  *        expression.
1045  */
1046 static bool
1047 one_pred_clause_expr_test(Expr *predicate, Node *clause)
1048 {
1049         List       *items,
1050                            *item;
1051
1052         if (is_opclause(clause))
1053                 return one_pred_clause_test(predicate, clause);
1054         else if (or_clause(clause))
1055         {
1056                 items = ((Expr *) clause)->args;
1057                 foreach(item, items)
1058                 {
1059                         /* if any OR item doesn't imply the predicate, clause doesn't */
1060                         if (!one_pred_clause_expr_test(predicate, lfirst(item)))
1061                                 return false;
1062                 }
1063                 return true;
1064         }
1065         else if (and_clause(clause))
1066         {
1067                 items = ((Expr *) clause)->args;
1068                 foreach(item, items)
1069                 {
1070
1071                         /*
1072                          * if any AND item implies the predicate, the whole clause
1073                          * does
1074                          */
1075                         if (one_pred_clause_expr_test(predicate, lfirst(item)))
1076                                 return true;
1077                 }
1078                 return false;
1079         }
1080         else
1081         {
1082                 /* unknown clause type never implies the predicate */
1083                 return false;
1084         }
1085 }
1086
1087
1088 /*
1089  * one_pred_clause_test
1090  *        Does the "predicate inclusion test" for one conjunct of a predicate
1091  *        expression for a simple restriction clause.
1092  */
1093 static bool
1094 one_pred_clause_test(Expr *predicate, Node *clause)
1095 {
1096         List       *items,
1097                            *item;
1098
1099         if (is_opclause((Node *) predicate))
1100                 return clause_pred_clause_test(predicate, clause);
1101         else if (or_clause((Node *) predicate))
1102         {
1103                 items = predicate->args;
1104                 foreach(item, items)
1105                 {
1106                         /* if any item is implied, the whole predicate is implied */
1107                         if (one_pred_clause_test(lfirst(item), clause))
1108                                 return true;
1109                 }
1110                 return false;
1111         }
1112         else if (and_clause((Node *) predicate))
1113         {
1114                 items = predicate->args;
1115                 foreach(item, items)
1116                 {
1117
1118                         /*
1119                          * if any item is not implied, the whole predicate is not
1120                          * implied
1121                          */
1122                         if (!one_pred_clause_test(lfirst(item), clause))
1123                                 return false;
1124                 }
1125                 return true;
1126         }
1127         else
1128         {
1129                 elog(DEBUG, "Unsupported predicate type, index will not be used");
1130                 return false;
1131         }
1132 }
1133
1134
1135 /*
1136  * Define an "operator implication table" for btree operators ("strategies").
1137  * The "strategy numbers" are:  (1) <   (2) <=   (3) =   (4) >=   (5) >
1138  *
1139  * The interpretation of:
1140  *
1141  *              test_op = BT_implic_table[given_op-1][target_op-1]
1142  *
1143  * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
1144  * of btree operators, is as follows:
1145  *
1146  *       If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
1147  *       want to determine whether "ATTR target_op CONST2" must also be true, then
1148  *       you can use "CONST1 test_op CONST2" as a test.  If this test returns true,
1149  *       then the target expression must be true; if the test returns false, then
1150  *       the target expression may be false.
1151  *
1152  * An entry where test_op==0 means the implication cannot be determined, i.e.,
1153  * this test should always be considered false.
1154  */
1155
1156 static const StrategyNumber
1157                         BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
1158         {2, 2, 0, 0, 0},
1159         {1, 2, 0, 0, 0},
1160         {1, 2, 3, 4, 5},
1161         {0, 0, 0, 4, 5},
1162         {0, 0, 0, 4, 4}
1163 };
1164
1165
1166 /*
1167  * clause_pred_clause_test
1168  *        Use operator class info to check whether clause implies predicate.
1169  *
1170  *        Does the "predicate inclusion test" for a "simple clause" predicate
1171  *        for a single "simple clause" restriction.  Currently, this only handles
1172  *        (binary boolean) operators that are in some btree operator class.
1173  *        Eventually, rtree operators could also be handled by defining an
1174  *        appropriate "RT_implic_table" array.
1175  */
1176 static bool
1177 clause_pred_clause_test(Expr *predicate, Node *clause)
1178 {
1179         Var                *pred_var,
1180                            *clause_var;
1181         Const      *pred_const,
1182                            *clause_const;
1183         Oid                     pred_op,
1184                                 clause_op,
1185                                 test_op;
1186         Oid                     opclass_id;
1187         StrategyNumber pred_strategy,
1188                                 clause_strategy,
1189                                 test_strategy;
1190         Oper       *test_oper;
1191         Expr       *test_expr;
1192         bool            test_result,
1193                                 isNull;
1194         Relation        relation;
1195         HeapScanDesc scan;
1196         HeapTuple       tuple;
1197         ScanKeyData entry[3];
1198         Form_pg_amop aform;
1199
1200         pred_var = (Var *) get_leftop(predicate);
1201         pred_const = (Const *) get_rightop(predicate);
1202         clause_var = (Var *) get_leftop((Expr *) clause);
1203         clause_const = (Const *) get_rightop((Expr *) clause);
1204
1205         /* Check the basic form; for now, only allow the simplest case */
1206         if (!is_opclause(clause) ||
1207                 !IsA(clause_var, Var) ||
1208                 clause_const == NULL ||
1209                 !IsA(clause_const, Const) ||
1210                 !IsA(predicate->oper, Oper) ||
1211                 !IsA(pred_var, Var) ||
1212                 !IsA(pred_const, Const))
1213                 return false;
1214
1215         /*
1216          * The implication can't be determined unless the predicate and the
1217          * clause refer to the same attribute.
1218          */
1219         if (clause_var->varattno != pred_var->varattno)
1220                 return false;
1221
1222         /* Get the operators for the two clauses we're comparing */
1223         pred_op = ((Oper *) ((Expr *) predicate)->oper)->opno;
1224         clause_op = ((Oper *) ((Expr *) clause)->oper)->opno;
1225
1226
1227         /*
1228          * 1. Find a "btree" strategy number for the pred_op
1229          */
1230         ScanKeyEntryInitialize(&entry[0], 0,
1231                                                    Anum_pg_amop_amopid,
1232                                                    F_OIDEQ,
1233                                                    ObjectIdGetDatum(BTREE_AM_OID));
1234
1235         ScanKeyEntryInitialize(&entry[1], 0,
1236                                                    Anum_pg_amop_amopopr,
1237                                                    F_OIDEQ,
1238                                                    ObjectIdGetDatum(pred_op));
1239
1240         relation = heap_openr(AccessMethodOperatorRelationName, AccessShareLock);
1241
1242         /*
1243          * The following assumes that any given operator will only be in a
1244          * single btree operator class.  This is true at least for all the
1245          * pre-defined operator classes.  If it isn't true, then whichever
1246          * operator class happens to be returned first for the given operator
1247          * will be used to find the associated strategy numbers for the test.
1248          * --Nels, Jan '93
1249          */
1250         scan = heap_beginscan(relation, false, SnapshotNow, 2, entry);
1251         tuple = heap_getnext(scan, 0);
1252         if (!HeapTupleIsValid(tuple))
1253         {
1254                 elog(DEBUG, "clause_pred_clause_test: unknown pred_op");
1255                 heap_endscan(scan);
1256                 heap_close(relation, AccessShareLock);
1257                 return false;
1258         }
1259         aform = (Form_pg_amop) GETSTRUCT(tuple);
1260
1261         /* Get the predicate operator's strategy number (1 to 5) */
1262         pred_strategy = (StrategyNumber) aform->amopstrategy;
1263
1264         /* Remember which operator class this strategy number came from */
1265         opclass_id = aform->amopclaid;
1266
1267         heap_endscan(scan);
1268
1269
1270         /*
1271          * 2. From the same opclass, find a strategy num for the clause_op
1272          */
1273         ScanKeyEntryInitialize(&entry[1], 0,
1274                                                    Anum_pg_amop_amopclaid,
1275                                                    F_OIDEQ,
1276                                                    ObjectIdGetDatum(opclass_id));
1277
1278         ScanKeyEntryInitialize(&entry[2], 0,
1279                                                    Anum_pg_amop_amopopr,
1280                                                    F_OIDEQ,
1281                                                    ObjectIdGetDatum(clause_op));
1282
1283         scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
1284         tuple = heap_getnext(scan, 0);
1285         if (!HeapTupleIsValid(tuple))
1286         {
1287                 elog(DEBUG, "clause_pred_clause_test: unknown clause_op");
1288                 heap_endscan(scan);
1289                 heap_close(relation, AccessShareLock);
1290                 return false;
1291         }
1292         aform = (Form_pg_amop) GETSTRUCT(tuple);
1293
1294         /* Get the restriction clause operator's strategy number (1 to 5) */
1295         clause_strategy = (StrategyNumber) aform->amopstrategy;
1296         heap_endscan(scan);
1297
1298
1299         /*
1300          * 3. Look up the "test" strategy number in the implication table
1301          */
1302
1303         test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1304         if (test_strategy == 0)
1305         {
1306                 heap_close(relation, AccessShareLock);
1307                 return false;                   /* the implication cannot be determined */
1308         }
1309
1310         /*
1311          * 4. From the same opclass, find the operator for the test strategy
1312          */
1313
1314         ScanKeyEntryInitialize(&entry[2], 0,
1315                                                    Anum_pg_amop_amopstrategy,
1316                                                    F_INT2EQ,
1317                                                    Int16GetDatum(test_strategy));
1318
1319         scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
1320         tuple = heap_getnext(scan, 0);
1321         if (!HeapTupleIsValid(tuple))
1322         {
1323                 elog(DEBUG, "clause_pred_clause_test: unknown test_op");
1324                 heap_endscan(scan);
1325                 heap_close(relation, AccessShareLock);
1326                 return false;
1327         }
1328         aform = (Form_pg_amop) GETSTRUCT(tuple);
1329
1330         /* Get the test operator */
1331         test_op = aform->amopopr;
1332
1333         heap_endscan(scan);
1334
1335         heap_close(relation, AccessShareLock);
1336
1337         /*
1338          * 5. Evaluate the test
1339          */
1340         test_oper = makeOper(test_op,           /* opno */
1341                                                  InvalidOid,    /* opid */
1342                                                  BOOLOID,               /* opresulttype */
1343                                                  0,             /* opsize */
1344                                                  NULL); /* op_fcache */
1345         replace_opid(test_oper);
1346
1347         test_expr = make_opclause(test_oper,
1348                                                           copyObject(clause_const),
1349                                                           copyObject(pred_const));
1350
1351 #ifndef OMIT_PARTIAL_INDEX
1352         test_result = ExecEvalExpr((Node *) test_expr, NULL, &isNull, NULL);
1353 #endif   /* OMIT_PARTIAL_INDEX */
1354         if (isNull)
1355         {
1356                 elog(DEBUG, "clause_pred_clause_test: null test result");
1357                 return false;
1358         }
1359         return test_result;
1360 }
1361
1362
1363 /****************************************************************************
1364  *                              ----  ROUTINES TO CHECK JOIN CLAUSES  ----
1365  ****************************************************************************/
1366
1367 /*
1368  * indexable_joinclauses
1369  *        Finds all groups of join clauses from among 'joininfo_list' that can
1370  *        be used in conjunction with 'index' for the inner scan of a nestjoin.
1371  *
1372  *        Each clause group comes from a single joininfo node plus the current
1373  *        rel's restrictinfo list.  Therefore, every clause in the group references
1374  *        the current rel plus the same set of other rels (except for the restrict
1375  *        clauses, which only reference the current rel).  Therefore, this set
1376  *        of clauses could be used as an indexqual if the relation is scanned
1377  *        as the inner side of a nestloop join when the outer side contains
1378  *        (at least) all those "other rels".
1379  *
1380  *        XXX Actually, given that we are considering a join that requires an
1381  *        outer rel set (A,B,C), we should use all qual clauses that reference
1382  *        any subset of these rels, not just the full set or none.      This is
1383  *        doable with a doubly nested loop over joininfo_list; is it worth it?
1384  *
1385  * Returns two parallel lists of the same length: the clause groups,
1386  * and the required outer rel set for each one.
1387  *
1388  * 'rel' is the relation for which 'index' is defined
1389  * 'joininfo_list' is the list of JoinInfo nodes for 'rel'
1390  * 'restrictinfo_list' is the list of restriction clauses for 'rel'
1391  * '*clausegroups' receives a list of clause sublists
1392  * '*outerrelids' receives a list of relid lists
1393  */
1394 static void
1395 indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index,
1396                                           List *joininfo_list, List *restrictinfo_list,
1397                                           List **clausegroups, List **outerrelids)
1398 {
1399         List       *cg_list = NIL;
1400         List       *relid_list = NIL;
1401         List       *i;
1402
1403         foreach(i, joininfo_list)
1404         {
1405                 JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
1406                 List       *clausegroup;
1407
1408                 clausegroup = group_clauses_by_ikey_for_joins(rel,
1409                                                                                                           index,
1410                                                                                                           index->indexkeys,
1411                                                                                                           index->classlist,
1412                                                                                         joininfo->jinfo_restrictinfo,
1413                                                                                                           restrictinfo_list);
1414
1415                 if (clausegroup != NIL)
1416                 {
1417                         cg_list = lappend(cg_list, clausegroup);
1418                         relid_list = lappend(relid_list, joininfo->unjoined_relids);
1419                 }
1420         }
1421
1422         *clausegroups = cg_list;
1423         *outerrelids = relid_list;
1424 }
1425
1426 /****************************************************************************
1427  *                              ----  PATH CREATION UTILITIES  ----
1428  ****************************************************************************/
1429
1430 /*
1431  * index_innerjoin
1432  *        Creates index path nodes corresponding to paths to be used as inner
1433  *        relations in nestloop joins.
1434  *
1435  * 'rel' is the relation for which 'index' is defined
1436  * 'clausegroup_list' is a list of lists of restrictinfo nodes which can use
1437  * 'index'.  Each sublist refers to the same set of outer rels.
1438  * 'outerrelids_list' is a list of the required outer rels for each sublist
1439  * of join clauses.
1440  *
1441  * Returns a list of index pathnodes.
1442  */
1443 static List *
1444 index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
1445                                 List *clausegroup_list, List *outerrelids_list)
1446 {
1447         List       *path_list = NIL;
1448         List       *i;
1449
1450         foreach(i, clausegroup_list)
1451         {
1452                 List       *clausegroup = lfirst(i);
1453                 IndexPath  *pathnode = makeNode(IndexPath);
1454                 List       *indexquals;
1455
1456                 /* XXX this code ought to be merged with create_index_path? */
1457
1458                 pathnode->path.pathtype = T_IndexScan;
1459                 pathnode->path.parent = rel;
1460
1461                 /*
1462                  * There's no point in marking the path with any pathkeys, since
1463                  * it will only ever be used as the inner path of a nestloop, and
1464                  * so its ordering does not matter.
1465                  */
1466                 pathnode->path.pathkeys = NIL;
1467
1468                 indexquals = get_actual_clauses(clausegroup);
1469                 /* expand special operators to indexquals the executor can handle */
1470                 indexquals = expand_indexqual_conditions(indexquals);
1471
1472                 /*
1473                  * Note that we are making a pathnode for a single-scan indexscan;
1474                  * therefore, both indexid and indexqual should be single-element
1475                  * lists.
1476                  */
1477                 pathnode->indexid = lconsi(index->indexoid, NIL);
1478                 pathnode->indexqual = lcons(indexquals, NIL);
1479
1480                 /* We don't actually care what order the index scans in ... */
1481                 pathnode->indexscandir = NoMovementScanDirection;
1482
1483                 /* joinrelids saves the rels needed on the outer side of the join */
1484                 pathnode->joinrelids = lfirst(outerrelids_list);
1485
1486                 /*
1487                  * We must compute the estimated number of output rows for the
1488                  * indexscan.  This is less than rel->rows because of the
1489                  * additional selectivity of the join clauses.  Since clausegroup
1490                  * may contain both restriction and join clauses, we have to do a
1491                  * set union to get the full set of clauses that must be
1492                  * considered to compute the correct selectivity.  (We can't just
1493                  * nconc the two lists; then we might have some restriction
1494                  * clauses appearing twice, which'd mislead
1495                  * restrictlist_selectivity into double-counting their
1496                  * selectivity.)
1497                  */
1498                 pathnode->rows = rel->tuples *
1499                         restrictlist_selectivity(root,
1500                                                                          LispUnion(rel->baserestrictinfo,
1501                                                                                            clausegroup),
1502                                                                          lfirsti(rel->relids));
1503                 /* Like costsize.c, force estimate to be at least one row */
1504                 if (pathnode->rows < 1.0)
1505                         pathnode->rows = 1.0;
1506
1507                 cost_index(&pathnode->path, root, rel, index, indexquals, true);
1508
1509                 path_list = lappend(path_list, pathnode);
1510                 outerrelids_list = lnext(outerrelids_list);
1511         }
1512         return path_list;
1513 }
1514
1515 /****************************************************************************
1516  *                              ----  ROUTINES TO CHECK OPERANDS  ----
1517  ****************************************************************************/
1518
1519 /*
1520  * match_index_to_operand()
1521  *        Generalized test for a match between an index's key
1522  *        and the operand on one side of a restriction or join clause.
1523  *        Now check for functional indices as well.
1524  */
1525 static bool
1526 match_index_to_operand(int indexkey,
1527                                            Var *operand,
1528                                            RelOptInfo *rel,
1529                                            IndexOptInfo *index)
1530 {
1531         if (index->indproc == InvalidOid)
1532         {
1533
1534                 /*
1535                  * Normal index.
1536                  */
1537                 if (IsA(operand, Var) &&
1538                         lfirsti(rel->relids) == operand->varno &&
1539                         indexkey == operand->varattno)
1540                         return true;
1541                 else
1542                         return false;
1543         }
1544
1545         /*
1546          * functional index check
1547          */
1548         return function_index_operand((Expr *) operand, rel, index);
1549 }
1550
1551 static bool
1552 function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index)
1553 {
1554         int                     relvarno = lfirsti(rel->relids);
1555         Func       *function;
1556         List       *funcargs;
1557         int                *indexKeys = index->indexkeys;
1558         List       *arg;
1559         int                     i;
1560
1561         /*
1562          * sanity check, make sure we know what we're dealing with here.
1563          */
1564         if (funcOpnd == NULL || !IsA(funcOpnd, Expr) ||
1565                 funcOpnd->opType != FUNC_EXPR ||
1566                 funcOpnd->oper == NULL || indexKeys == NULL)
1567                 return false;
1568
1569         function = (Func *) funcOpnd->oper;
1570         funcargs = funcOpnd->args;
1571
1572         if (function->funcid != index->indproc)
1573                 return false;
1574
1575         /*
1576          * Check that the arguments correspond to the same arguments used to
1577          * create the functional index.  To do this we must check that 1.
1578          * refer to the right relation. 2. the args have the right attr.
1579          * numbers in the right order.
1580          */
1581         i = 0;
1582         foreach(arg, funcargs)
1583         {
1584                 Var                *var = (Var *) lfirst(arg);
1585
1586                 if (!IsA(var, Var))
1587                         return false;
1588                 if (indexKeys[i] == 0)
1589                         return false;
1590                 if (var->varno != relvarno || var->varattno != indexKeys[i])
1591                         return false;
1592
1593                 i++;
1594         }
1595
1596         if (indexKeys[i] != 0)
1597                 return false;                   /* not enough arguments */
1598
1599         return true;
1600 }
1601
1602 /****************************************************************************
1603  *                      ----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
1604  ****************************************************************************/
1605
1606 /*----------
1607  * These routines handle special optimization of operators that can be
1608  * used with index scans even though they are not known to the executor's
1609  * indexscan machinery.  The key idea is that these operators allow us
1610  * to derive approximate indexscan qual clauses, such that any tuples
1611  * that pass the operator clause itself must also satisfy the simpler
1612  * indexscan condition(s).      Then we can use the indexscan machinery
1613  * to avoid scanning as much of the table as we'd otherwise have to,
1614  * while applying the original operator as a qpqual condition to ensure
1615  * we deliver only the tuples we want.  (In essence, we're using a regular
1616  * index as if it were a lossy index.)
1617  *
1618  * An example of what we're doing is
1619  *                      textfield LIKE 'abc%'
1620  * from which we can generate the indexscanable conditions
1621  *                      textfield >= 'abc' AND textfield < 'abd'
1622  * which allow efficient scanning of an index on textfield.
1623  * (In reality, character set and collation issues make the transformation
1624  * from LIKE to indexscan limits rather harder than one might think ...
1625  * but that's the basic idea.)
1626  *
1627  * Two routines are provided here, match_special_index_operator() and
1628  * expand_indexqual_conditions().  match_special_index_operator() is
1629  * just an auxiliary function for match_clause_to_indexkey(); after
1630  * the latter fails to recognize a restriction opclause's operator
1631  * as a member of an index's opclass, it asks match_special_index_operator()
1632  * whether the clause should be considered an indexqual anyway.
1633  * expand_indexqual_conditions() converts a list of "raw" indexqual
1634  * conditions (with implicit AND semantics across list elements) into
1635  * a list that the executor can actually handle.  For operators that
1636  * are members of the index's opclass this transformation is a no-op,
1637  * but operators recognized by match_special_index_operator() must be
1638  * converted into one or more "regular" indexqual conditions.
1639  *----------
1640  */
1641
1642 /*
1643  * match_special_index_operator
1644  *        Recognize restriction clauses that can be used to generate
1645  *        additional indexscanable qualifications.
1646  *
1647  * The given clause is already known to be a binary opclause having
1648  * the form (indexkey OP const/param) or (const/param OP indexkey),
1649  * but the OP proved not to be one of the index's opclass operators.
1650  * Return 'true' if we can do something with it anyway.
1651  */
1652 static bool
1653 match_special_index_operator(Expr *clause, Oid opclass, Oid relam,
1654                                                          bool indexkey_on_left)
1655 {
1656         bool            isIndexable = false;
1657         Var                *leftop,
1658                            *rightop;
1659         Oid                     expr_op;
1660         Datum           constvalue;
1661         char       *patt;
1662         char       *prefix;
1663         char       *rest;
1664
1665         /*
1666          * Currently, all known special operators require the indexkey on the
1667          * left, but this test could be pushed into the switch statement if
1668          * some are added that do not...
1669          */
1670         if (!indexkey_on_left)
1671                 return false;
1672
1673         /* we know these will succeed */
1674         leftop = get_leftop(clause);
1675         rightop = get_rightop(clause);
1676         expr_op = ((Oper *) clause->oper)->opno;
1677
1678         /* again, required for all current special ops: */
1679         if (!IsA(rightop, Const) ||
1680                 ((Const *) rightop)->constisnull)
1681                 return false;
1682         constvalue = ((Const *) rightop)->constvalue;
1683
1684         switch (expr_op)
1685         {
1686                 case OID_TEXT_LIKE_OP:
1687                 case OID_BPCHAR_LIKE_OP:
1688                 case OID_VARCHAR_LIKE_OP:
1689                 case OID_NAME_LIKE_OP:
1690                         /* the right-hand const is type text for all of these */
1691                         patt = DatumGetCString(DirectFunctionCall1(textout,
1692                                                                                                            constvalue));
1693                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
1694                                                                                            &prefix, &rest) != Pattern_Prefix_None;
1695                         if (prefix)
1696                                 pfree(prefix);
1697                         pfree(patt);
1698                         break;
1699
1700                 case OID_TEXT_REGEXEQ_OP:
1701                 case OID_BPCHAR_REGEXEQ_OP:
1702                 case OID_VARCHAR_REGEXEQ_OP:
1703                 case OID_NAME_REGEXEQ_OP:
1704                         /* the right-hand const is type text for all of these */
1705                         patt = DatumGetCString(DirectFunctionCall1(textout,
1706                                                                                                            constvalue));
1707                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex,
1708                                                                                            &prefix, &rest) != Pattern_Prefix_None;
1709                         if (prefix)
1710                                 pfree(prefix);
1711                         pfree(patt);
1712                         break;
1713
1714                 case OID_TEXT_ICREGEXEQ_OP:
1715                 case OID_BPCHAR_ICREGEXEQ_OP:
1716                 case OID_VARCHAR_ICREGEXEQ_OP:
1717                 case OID_NAME_ICREGEXEQ_OP:
1718                         /* the right-hand const is type text for all of these */
1719                         patt = DatumGetCString(DirectFunctionCall1(textout,
1720                                                                                                            constvalue));
1721                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
1722                                                                                            &prefix, &rest) != Pattern_Prefix_None;
1723                         if (prefix)
1724                                 pfree(prefix);
1725                         pfree(patt);
1726                         break;
1727         }
1728
1729         /* done if the expression doesn't look indexable */
1730         if (!isIndexable)
1731                 return false;
1732
1733         /*
1734          * Must also check that index's opclass supports the operators we will
1735          * want to apply.  (A hash index, for example, will not support ">=".)
1736          * We cheat a little by not checking for availability of "=" ... any
1737          * index type should support "=", methinks.
1738          */
1739         switch (expr_op)
1740         {
1741                 case OID_TEXT_LIKE_OP:
1742                 case OID_TEXT_REGEXEQ_OP:
1743                 case OID_TEXT_ICREGEXEQ_OP:
1744                         if (!op_class(find_operator(">=", TEXTOID), opclass, relam) ||
1745                                 !op_class(find_operator("<", TEXTOID), opclass, relam))
1746                                 isIndexable = false;
1747                         break;
1748
1749                 case OID_BPCHAR_LIKE_OP:
1750                 case OID_BPCHAR_REGEXEQ_OP:
1751                 case OID_BPCHAR_ICREGEXEQ_OP:
1752                         if (!op_class(find_operator(">=", BPCHAROID), opclass, relam) ||
1753                                 !op_class(find_operator("<", BPCHAROID), opclass, relam))
1754                                 isIndexable = false;
1755                         break;
1756
1757                 case OID_VARCHAR_LIKE_OP:
1758                 case OID_VARCHAR_REGEXEQ_OP:
1759                 case OID_VARCHAR_ICREGEXEQ_OP:
1760                         if (!op_class(find_operator(">=", VARCHAROID), opclass, relam) ||
1761                                 !op_class(find_operator("<", VARCHAROID), opclass, relam))
1762                                 isIndexable = false;
1763                         break;
1764
1765                 case OID_NAME_LIKE_OP:
1766                 case OID_NAME_REGEXEQ_OP:
1767                 case OID_NAME_ICREGEXEQ_OP:
1768                         if (!op_class(find_operator(">=", NAMEOID), opclass, relam) ||
1769                                 !op_class(find_operator("<", NAMEOID), opclass, relam))
1770                                 isIndexable = false;
1771                         break;
1772         }
1773
1774         return isIndexable;
1775 }
1776
1777 /*
1778  * expand_indexqual_conditions
1779  *        Given a list of (implicitly ANDed) indexqual clauses,
1780  *        expand any "special" index operators into clauses that the indexscan
1781  *        machinery will know what to do with.  Clauses that were not
1782  *        recognized by match_special_index_operator() must be passed through
1783  *        unchanged.
1784  */
1785 List *
1786 expand_indexqual_conditions(List *indexquals)
1787 {
1788         List       *resultquals = NIL;
1789         List       *q;
1790
1791         foreach(q, indexquals)
1792         {
1793                 Expr       *clause = (Expr *) lfirst(q);
1794
1795                 /* we know these will succeed */
1796                 Var                *leftop = get_leftop(clause);
1797                 Var                *rightop = get_rightop(clause);
1798                 Oid                     expr_op = ((Oper *) clause->oper)->opno;
1799                 Datum           constvalue;
1800                 char       *patt;
1801                 char       *prefix;
1802                 char       *rest;
1803                 Pattern_Prefix_Status pstatus;
1804
1805                 switch (expr_op)
1806                 {
1807
1808                                 /*
1809                                  * LIKE and regex operators are not members of any index
1810                                  * opclass, so if we find one in an indexqual list we can
1811                                  * assume that it was accepted by
1812                                  * match_special_index_operator().
1813                                  */
1814                         case OID_TEXT_LIKE_OP:
1815                         case OID_BPCHAR_LIKE_OP:
1816                         case OID_VARCHAR_LIKE_OP:
1817                         case OID_NAME_LIKE_OP:
1818                                 /* the right-hand const is type text for all of these */
1819                                 constvalue = ((Const *) rightop)->constvalue;
1820                                 patt = DatumGetCString(DirectFunctionCall1(textout,
1821                                                                                                                    constvalue));
1822                                 pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
1823                                                                                            &prefix, &rest);
1824                                 resultquals = nconc(resultquals,
1825                                                                         prefix_quals(leftop, expr_op,
1826                                                                                                  prefix, pstatus));
1827                                 if (prefix)
1828                                         pfree(prefix);
1829                                 pfree(patt);
1830                                 break;
1831
1832                         case OID_TEXT_REGEXEQ_OP:
1833                         case OID_BPCHAR_REGEXEQ_OP:
1834                         case OID_VARCHAR_REGEXEQ_OP:
1835                         case OID_NAME_REGEXEQ_OP:
1836                                 /* the right-hand const is type text for all of these */
1837                                 constvalue = ((Const *) rightop)->constvalue;
1838                                 patt = DatumGetCString(DirectFunctionCall1(textout,
1839                                                                                                                    constvalue));
1840                                 pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex,
1841                                                                                            &prefix, &rest);
1842                                 resultquals = nconc(resultquals,
1843                                                                         prefix_quals(leftop, expr_op,
1844                                                                                                  prefix, pstatus));
1845                                 if (prefix)
1846                                         pfree(prefix);
1847                                 pfree(patt);
1848                                 break;
1849
1850                         case OID_TEXT_ICREGEXEQ_OP:
1851                         case OID_BPCHAR_ICREGEXEQ_OP:
1852                         case OID_VARCHAR_ICREGEXEQ_OP:
1853                         case OID_NAME_ICREGEXEQ_OP:
1854                                 /* the right-hand const is type text for all of these */
1855                                 constvalue = ((Const *) rightop)->constvalue;
1856                                 patt = DatumGetCString(DirectFunctionCall1(textout,
1857                                                                                                                    constvalue));
1858                                 pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
1859                                                                                            &prefix, &rest);
1860                                 resultquals = nconc(resultquals,
1861                                                                         prefix_quals(leftop, expr_op,
1862                                                                                                  prefix, pstatus));
1863                                 if (prefix)
1864                                         pfree(prefix);
1865                                 pfree(patt);
1866                                 break;
1867
1868                         default:
1869                                 resultquals = lappend(resultquals, clause);
1870                                 break;
1871                 }
1872         }
1873
1874         return resultquals;
1875 }
1876
1877 /*
1878  * Given a fixed prefix that all the "leftop" values must have,
1879  * generate suitable indexqual condition(s).  expr_op is the original
1880  * LIKE or regex operator; we use it to deduce the appropriate comparison
1881  * operators.
1882  */
1883 static List *
1884 prefix_quals(Var *leftop, Oid expr_op,
1885                          char *prefix, Pattern_Prefix_Status pstatus)
1886 {
1887         List       *result;
1888         Oid                     datatype;
1889         Oid                     oproid;
1890         Const      *con;
1891         Oper       *op;
1892         Expr       *expr;
1893         char       *greaterstr;
1894
1895         Assert(pstatus != Pattern_Prefix_None);
1896
1897         switch (expr_op)
1898         {
1899                 case OID_TEXT_LIKE_OP:
1900                 case OID_TEXT_REGEXEQ_OP:
1901                 case OID_TEXT_ICREGEXEQ_OP:
1902                         datatype = TEXTOID;
1903                         break;
1904
1905                 case OID_BPCHAR_LIKE_OP:
1906                 case OID_BPCHAR_REGEXEQ_OP:
1907                 case OID_BPCHAR_ICREGEXEQ_OP:
1908                         datatype = BPCHAROID;
1909                         break;
1910
1911                 case OID_VARCHAR_LIKE_OP:
1912                 case OID_VARCHAR_REGEXEQ_OP:
1913                 case OID_VARCHAR_ICREGEXEQ_OP:
1914                         datatype = VARCHAROID;
1915                         break;
1916
1917                 case OID_NAME_LIKE_OP:
1918                 case OID_NAME_REGEXEQ_OP:
1919                 case OID_NAME_ICREGEXEQ_OP:
1920                         datatype = NAMEOID;
1921                         break;
1922
1923                 default:
1924                         elog(ERROR, "prefix_quals: unexpected operator %u", expr_op);
1925                         return NIL;
1926         }
1927
1928         /*
1929          * If we found an exact-match pattern, generate an "=" indexqual.
1930          */
1931         if (pstatus == Pattern_Prefix_Exact)
1932         {
1933                 oproid = find_operator("=", datatype);
1934                 if (oproid == InvalidOid)
1935                         elog(ERROR, "prefix_quals: no = operator for type %u", datatype);
1936                 con = string_to_const(prefix, datatype);
1937                 op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1938                 expr = make_opclause(op, leftop, (Var *) con);
1939                 result = lcons(expr, NIL);
1940                 return result;
1941         }
1942
1943         /*
1944          * Otherwise, we have a nonempty required prefix of the values.
1945          *
1946          * We can always say "x >= prefix".
1947          */
1948         oproid = find_operator(">=", datatype);
1949         if (oproid == InvalidOid)
1950                 elog(ERROR, "prefix_quals: no >= operator for type %u", datatype);
1951         con = string_to_const(prefix, datatype);
1952         op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1953         expr = make_opclause(op, leftop, (Var *) con);
1954         result = lcons(expr, NIL);
1955
1956         /*
1957          * If we can create a string larger than the prefix, say "x <
1958          * greaterstr".
1959          */
1960         greaterstr = make_greater_string(prefix, datatype);
1961         if (greaterstr)
1962         {
1963                 oproid = find_operator("<", datatype);
1964                 if (oproid == InvalidOid)
1965                         elog(ERROR, "prefix_quals: no < operator for type %u", datatype);
1966                 con = string_to_const(greaterstr, datatype);
1967                 op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1968                 expr = make_opclause(op, leftop, (Var *) con);
1969                 result = lappend(result, expr);
1970                 pfree(greaterstr);
1971         }
1972
1973         return result;
1974 }
1975
1976 /*
1977  * Handy subroutines for match_special_index_operator() and friends.
1978  */
1979
1980 /* See if there is a binary op of the given name for the given datatype */
1981 static Oid
1982 find_operator(const char *opname, Oid datatype)
1983 {
1984         HeapTuple       optup;
1985
1986         optup = SearchSysCacheTuple(OPERNAME,
1987                                                                 PointerGetDatum(opname),
1988                                                                 ObjectIdGetDatum(datatype),
1989                                                                 ObjectIdGetDatum(datatype),
1990                                                                 CharGetDatum('b'));
1991         if (!HeapTupleIsValid(optup))
1992                 return InvalidOid;
1993         return optup->t_data->t_oid;
1994 }
1995
1996 /*
1997  * Generate a Datum of the appropriate type from a C string.
1998  * Note that all of the supported types are pass-by-ref, so the
1999  * returned value should be pfree'd if no longer needed.
2000  */
2001 static Datum
2002 string_to_datum(const char *str, Oid datatype)
2003 {
2004         /*
2005          * We cheat a little by assuming that textin() will do for bpchar and
2006          * varchar constants too...
2007          */
2008         if (datatype == NAMEOID)
2009                 return PointerGetDatum(namein((char *) str));
2010         else
2011                 return DirectFunctionCall1(textin, CStringGetDatum(str));
2012 }
2013
2014 /*
2015  * Generate a Const node of the appropriate type from a C string.
2016  */
2017 static Const *
2018 string_to_const(const char *str, Oid datatype)
2019 {
2020         Datum           conval = string_to_datum(str, datatype);
2021
2022         return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2023                                          conval, false, false, false, false);
2024 }