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