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