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.76 2000/01/09 00:26:31 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                 long            npages;
1397                 Selectivity     selec;
1398
1399                 indexquals = get_actual_clauses(clausegroup);
1400                 /* expand special operators to indexquals the executor can handle */
1401                 indexquals = expand_indexqual_conditions(indexquals);
1402
1403                 index_selectivity(root,
1404                                                   rel,
1405                                                   index,
1406                                                   indexquals,
1407                                                   &npages,
1408                                                   &selec);
1409
1410                 /* XXX this code ought to be merged with create_index_path? */
1411
1412                 pathnode->path.pathtype = T_IndexScan;
1413                 pathnode->path.parent = rel;
1414                 pathnode->path.pathkeys = build_index_pathkeys(root, rel, index);
1415
1416                 /* Note that we are making a pathnode for a single-scan indexscan;
1417                  * therefore, both indexid and indexqual should be single-element
1418                  * lists.
1419                  */
1420                 pathnode->indexid = lconsi(index->indexoid, NIL);
1421                 pathnode->indexqual = lcons(indexquals, NIL);
1422
1423                 /* joinrelids saves the rels needed on the outer side of the join */
1424                 pathnode->joinrelids = lfirst(outerrelids_list);
1425
1426                 pathnode->path.path_cost = cost_index(rel, index,
1427                                                                                           npages, selec,
1428                                                                                           true);
1429
1430                 path_list = lappend(path_list, pathnode);
1431                 outerrelids_list = lnext(outerrelids_list);
1432         }
1433         return path_list;
1434 }
1435
1436 /****************************************************************************
1437  *                              ----  ROUTINES TO CHECK OPERANDS  ----
1438  ****************************************************************************/
1439
1440 /*
1441  * match_index_to_operand()
1442  *        Generalized test for a match between an index's key
1443  *        and the operand on one side of a restriction or join clause.
1444  *    Now check for functional indices as well.
1445  */
1446 static bool
1447 match_index_to_operand(int indexkey,
1448                                            Var *operand,
1449                                            RelOptInfo *rel,
1450                                            IndexOptInfo *index)
1451 {
1452         if (index->indproc == InvalidOid)
1453         {
1454                 /*
1455                  * Normal index.
1456                  */
1457                 if (IsA(operand, Var) &&
1458                         lfirsti(rel->relids) == operand->varno &&
1459                         indexkey == operand->varattno)
1460                         return true;
1461                 else
1462                         return false;
1463         }
1464
1465         /*
1466          * functional index check
1467          */
1468         return function_index_operand((Expr *) operand, rel, index);
1469 }
1470
1471 static bool
1472 function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index)
1473 {
1474         int                     relvarno = lfirsti(rel->relids);
1475         Func       *function;
1476         List       *funcargs;
1477         int                *indexKeys = index->indexkeys;
1478         List       *arg;
1479         int                     i;
1480
1481         /*
1482          * sanity check, make sure we know what we're dealing with here.
1483          */
1484         if (funcOpnd == NULL || ! IsA(funcOpnd, Expr) ||
1485                 funcOpnd->opType != FUNC_EXPR ||
1486                 funcOpnd->oper == NULL || indexKeys == NULL)
1487                 return false;
1488
1489         function = (Func *) funcOpnd->oper;
1490         funcargs = funcOpnd->args;
1491
1492         if (function->funcid != index->indproc)
1493                 return false;
1494
1495         /*
1496          * Check that the arguments correspond to the same arguments used to
1497          * create the functional index.  To do this we must check that 1.
1498          * refer to the right relation. 2. the args have the right attr.
1499          * numbers in the right order.
1500          */
1501         i = 0;
1502         foreach(arg, funcargs)
1503         {
1504                 Var        *var = (Var *) lfirst(arg);
1505
1506                 if (! IsA(var, Var))
1507                         return false;
1508                 if (indexKeys[i] == 0)
1509                         return false;
1510                 if (var->varno != relvarno || var->varattno != indexKeys[i])
1511                         return false;
1512
1513                 i++;
1514         }
1515
1516         if (indexKeys[i] != 0)
1517                 return false;                   /* not enough arguments */
1518
1519         return true;
1520 }
1521
1522 /****************************************************************************
1523  *                      ----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
1524  ****************************************************************************/
1525
1526 /*----------
1527  * These routines handle special optimization of operators that can be
1528  * used with index scans even though they are not known to the executor's
1529  * indexscan machinery.  The key idea is that these operators allow us
1530  * to derive approximate indexscan qual clauses, such that any tuples
1531  * that pass the operator clause itself must also satisfy the simpler
1532  * indexscan condition(s).  Then we can use the indexscan machinery
1533  * to avoid scanning as much of the table as we'd otherwise have to,
1534  * while applying the original operator as a qpqual condition to ensure
1535  * we deliver only the tuples we want.  (In essence, we're using a regular
1536  * index as if it were a lossy index.)
1537  *
1538  * An example of what we're doing is
1539  *                      textfield LIKE 'abc%'
1540  * from which we can generate the indexscanable conditions
1541  *                      textfield >= 'abc' AND textfield < 'abd'
1542  * which allow efficient scanning of an index on textfield.
1543  * (In reality, character set and collation issues make the transformation
1544  * from LIKE to indexscan limits rather harder than one might think ...
1545  * but that's the basic idea.)
1546  *
1547  * Two routines are provided here, match_special_index_operator() and
1548  * expand_indexqual_conditions().  match_special_index_operator() is
1549  * just an auxiliary function for match_clause_to_indexkey(); after
1550  * the latter fails to recognize a restriction opclause's operator
1551  * as a member of an index's opclass, it asks match_special_index_operator()
1552  * whether the clause should be considered an indexqual anyway.
1553  * expand_indexqual_conditions() converts a list of "raw" indexqual
1554  * conditions (with implicit AND semantics across list elements) into
1555  * a list that the executor can actually handle.  For operators that
1556  * are members of the index's opclass this transformation is a no-op,
1557  * but operators recognized by match_special_index_operator() must be
1558  * converted into one or more "regular" indexqual conditions.
1559  *----------
1560  */
1561
1562 /*
1563  * match_special_index_operator
1564  *        Recognize restriction clauses that can be used to generate
1565  *        additional indexscanable qualifications.
1566  *
1567  * The given clause is already known to be a binary opclause having
1568  * the form (indexkey OP const/param) or (const/param OP indexkey),
1569  * but the OP proved not to be one of the index's opclass operators.
1570  * Return 'true' if we can do something with it anyway.
1571  */
1572 static bool
1573 match_special_index_operator(Expr *clause, Oid opclass, Oid relam,
1574                                                          bool indexkey_on_left)
1575 {
1576         bool            isIndexable = false;
1577         Var                *leftop,
1578                            *rightop;
1579         Oid                     expr_op;
1580         Datum           constvalue;
1581         char       *patt;
1582         char       *prefix;
1583
1584         /* Currently, all known special operators require the indexkey
1585          * on the left, but this test could be pushed into the switch statement
1586          * if some are added that do not...
1587          */
1588         if (! indexkey_on_left)
1589                 return false;
1590
1591         /* we know these will succeed */
1592         leftop = get_leftop(clause);
1593         rightop = get_rightop(clause);
1594         expr_op = ((Oper *) clause->oper)->opno;
1595
1596         /* again, required for all current special ops: */
1597         if (! IsA(rightop, Const) ||
1598                 ((Const *) rightop)->constisnull)
1599                 return false;
1600         constvalue = ((Const *) rightop)->constvalue;
1601
1602         switch (expr_op)
1603         {
1604                 case OID_TEXT_LIKE_OP:
1605                 case OID_BPCHAR_LIKE_OP:
1606                 case OID_VARCHAR_LIKE_OP:
1607                 case OID_NAME_LIKE_OP:
1608                         /* the right-hand const is type text for all of these */
1609                         patt = textout((text *) DatumGetPointer(constvalue));
1610                         isIndexable = like_fixed_prefix(patt, &prefix) != Prefix_None;
1611                         if (prefix) pfree(prefix);
1612                         pfree(patt);
1613                         break;
1614
1615                 case OID_TEXT_REGEXEQ_OP:
1616                 case OID_BPCHAR_REGEXEQ_OP:
1617                 case OID_VARCHAR_REGEXEQ_OP:
1618                 case OID_NAME_REGEXEQ_OP:
1619                         /* the right-hand const is type text for all of these */
1620                         patt = textout((text *) DatumGetPointer(constvalue));
1621                         isIndexable = regex_fixed_prefix(patt, false, &prefix) != Prefix_None;
1622                         if (prefix) pfree(prefix);
1623                         pfree(patt);
1624                         break;
1625
1626                 case OID_TEXT_ICREGEXEQ_OP:
1627                 case OID_BPCHAR_ICREGEXEQ_OP:
1628                 case OID_VARCHAR_ICREGEXEQ_OP:
1629                 case OID_NAME_ICREGEXEQ_OP:
1630                         /* the right-hand const is type text for all of these */
1631                         patt = textout((text *) DatumGetPointer(constvalue));
1632                         isIndexable = regex_fixed_prefix(patt, true, &prefix) != Prefix_None;
1633                         if (prefix) pfree(prefix);
1634                         pfree(patt);
1635                         break;
1636         }
1637
1638         /* done if the expression doesn't look indexable */
1639         if (! isIndexable)
1640                 return false;
1641
1642         /*
1643          * Must also check that index's opclass supports the operators we will
1644          * want to apply.  (A hash index, for example, will not support ">=".)
1645          * We cheat a little by not checking for availability of "=" ... any
1646          * index type should support "=", methinks.
1647          */
1648         switch (expr_op)
1649         {
1650                 case OID_TEXT_LIKE_OP:
1651                 case OID_TEXT_REGEXEQ_OP:
1652                 case OID_TEXT_ICREGEXEQ_OP:
1653                         if (! op_class(find_operator(">=", TEXTOID), opclass, relam) ||
1654                                 ! op_class(find_operator("<", TEXTOID), opclass, relam))
1655                                 isIndexable = false;
1656                         break;
1657
1658                 case OID_BPCHAR_LIKE_OP:
1659                 case OID_BPCHAR_REGEXEQ_OP:
1660                 case OID_BPCHAR_ICREGEXEQ_OP:
1661                         if (! op_class(find_operator(">=", BPCHAROID), opclass, relam) ||
1662                                 ! op_class(find_operator("<", BPCHAROID), opclass, relam))
1663                                 isIndexable = false;
1664                         break;
1665
1666                 case OID_VARCHAR_LIKE_OP:
1667                 case OID_VARCHAR_REGEXEQ_OP:
1668                 case OID_VARCHAR_ICREGEXEQ_OP:
1669                         if (! op_class(find_operator(">=", VARCHAROID), opclass, relam) ||
1670                                 ! op_class(find_operator("<", VARCHAROID), opclass, relam))
1671                                 isIndexable = false;
1672                         break;
1673
1674                 case OID_NAME_LIKE_OP:
1675                 case OID_NAME_REGEXEQ_OP:
1676                 case OID_NAME_ICREGEXEQ_OP:
1677                         if (! op_class(find_operator(">=", NAMEOID), opclass, relam) ||
1678                                 ! op_class(find_operator("<", NAMEOID), opclass, relam))
1679                                 isIndexable = false;
1680                         break;
1681         }
1682
1683         return isIndexable;
1684 }
1685
1686 /*
1687  * expand_indexqual_conditions
1688  *        Given a list of (implicitly ANDed) indexqual clauses,
1689  *        expand any "special" index operators into clauses that the indexscan
1690  *        machinery will know what to do with.  Clauses that were not
1691  *        recognized by match_special_index_operator() must be passed through
1692  *        unchanged.
1693  */
1694 List *
1695 expand_indexqual_conditions(List *indexquals)
1696 {
1697         List       *resultquals = NIL;
1698         List       *q;
1699
1700         foreach(q, indexquals)
1701         {
1702                 Expr       *clause = (Expr *) lfirst(q);
1703                 /* we know these will succeed */
1704                 Var                *leftop = get_leftop(clause);
1705                 Var                *rightop = get_rightop(clause);
1706                 Oid                     expr_op = ((Oper *) clause->oper)->opno;
1707                 Datum           constvalue;
1708                 char       *patt;
1709                 char       *prefix;
1710                 Prefix_Status pstatus;
1711
1712                 switch (expr_op)
1713                 {
1714                         /*
1715                          * LIKE and regex operators are not members of any index opclass,
1716                          * so if we find one in an indexqual list we can assume that
1717                          * it was accepted by match_special_index_operator().
1718                          */
1719                         case OID_TEXT_LIKE_OP:
1720                         case OID_BPCHAR_LIKE_OP:
1721                         case OID_VARCHAR_LIKE_OP:
1722                         case OID_NAME_LIKE_OP:
1723                                 /* the right-hand const is type text for all of these */
1724                                 constvalue = ((Const *) rightop)->constvalue;
1725                                 patt = textout((text *) DatumGetPointer(constvalue));
1726                                 pstatus = like_fixed_prefix(patt, &prefix);
1727                                 resultquals = nconc(resultquals,
1728                                                                         prefix_quals(leftop, expr_op,
1729                                                                                                  prefix, pstatus));
1730                                 if (prefix) pfree(prefix);
1731                                 pfree(patt);
1732                                 break;
1733
1734                         case OID_TEXT_REGEXEQ_OP:
1735                         case OID_BPCHAR_REGEXEQ_OP:
1736                         case OID_VARCHAR_REGEXEQ_OP:
1737                         case OID_NAME_REGEXEQ_OP:
1738                                 /* the right-hand const is type text for all of these */
1739                                 constvalue = ((Const *) rightop)->constvalue;
1740                                 patt = textout((text *) DatumGetPointer(constvalue));
1741                                 pstatus = regex_fixed_prefix(patt, false, &prefix);
1742                                 resultquals = nconc(resultquals,
1743                                                                         prefix_quals(leftop, expr_op,
1744                                                                                                  prefix, pstatus));
1745                                 if (prefix) pfree(prefix);
1746                                 pfree(patt);
1747                                 break;
1748
1749                         case OID_TEXT_ICREGEXEQ_OP:
1750                         case OID_BPCHAR_ICREGEXEQ_OP:
1751                         case OID_VARCHAR_ICREGEXEQ_OP:
1752                         case OID_NAME_ICREGEXEQ_OP:
1753                                 /* the right-hand const is type text for all of these */
1754                                 constvalue = ((Const *) rightop)->constvalue;
1755                                 patt = textout((text *) DatumGetPointer(constvalue));
1756                                 pstatus = regex_fixed_prefix(patt, true, &prefix);
1757                                 resultquals = nconc(resultquals,
1758                                                                         prefix_quals(leftop, expr_op,
1759                                                                                                  prefix, pstatus));
1760                                 if (prefix) pfree(prefix);
1761                                 pfree(patt);
1762                                 break;
1763
1764                         default:
1765                                 resultquals = lappend(resultquals, clause);
1766                                 break;
1767                 }
1768         }
1769
1770         return resultquals;
1771 }
1772
1773 /*
1774  * Extract the fixed prefix, if any, for a LIKE pattern.
1775  * *prefix is set to a palloc'd prefix string,
1776  * or to NULL if no fixed prefix exists for the pattern.
1777  * The return value distinguishes no fixed prefix, a partial prefix,
1778  * or an exact-match-only pattern.
1779  */
1780 static Prefix_Status
1781 like_fixed_prefix(char *patt, char **prefix)
1782 {
1783         char       *match;
1784         int                     pos,
1785                                 match_pos;
1786
1787         *prefix = match = palloc(strlen(patt)+1);
1788         match_pos = 0;
1789
1790         for (pos = 0; patt[pos]; pos++)
1791         {
1792                 /* % and _ are wildcard characters in LIKE */
1793                 if (patt[pos] == '%' ||
1794                         patt[pos] == '_')
1795                         break;
1796                 /* Backslash quotes the next character */
1797                 if (patt[pos] == '\\')
1798                 {
1799                         pos++;
1800                         if (patt[pos] == '\0')
1801                                 break;
1802                 }
1803                 /*
1804                  * NOTE: this code used to think that %% meant a literal %,
1805                  * but textlike() itself does not think that, and the SQL92
1806                  * spec doesn't say any such thing either.
1807                  */
1808                 match[match_pos++] = patt[pos];
1809         }
1810
1811         match[match_pos] = '\0';
1812
1813         /* in LIKE, an empty pattern is an exact match! */
1814         if (patt[pos] == '\0')
1815                 return Prefix_Exact;    /* reached end of pattern, so exact */
1816
1817         if (match_pos > 0)
1818                 return Prefix_Partial;
1819         return Prefix_None;
1820 }
1821
1822 /*
1823  * Extract the fixed prefix, if any, for a regex pattern.
1824  * *prefix is set to a palloc'd prefix string,
1825  * or to NULL if no fixed prefix exists for the pattern.
1826  * The return value distinguishes no fixed prefix, a partial prefix,
1827  * or an exact-match-only pattern.
1828  */
1829 static Prefix_Status
1830 regex_fixed_prefix(char *patt, bool case_insensitive,
1831                                    char **prefix)
1832 {
1833         char       *match;
1834         int                     pos,
1835                                 match_pos;
1836
1837         *prefix = NULL;
1838
1839         /* Pattern must be anchored left */
1840         if (patt[0] != '^')
1841                 return Prefix_None;
1842
1843         /* Cannot optimize if unquoted | { } is present in pattern */
1844         for (pos = 1; patt[pos]; pos++)
1845         {
1846                 if (patt[pos] == '|' ||
1847                         patt[pos] == '{' ||
1848                         patt[pos] == '}')
1849                         return Prefix_None;
1850                 if (patt[pos] == '\\')
1851                 {
1852                         pos++;
1853                         if (patt[pos] == '\0')
1854                                 break;
1855                 }
1856         }
1857
1858         /* OK, allocate space for pattern */
1859         *prefix = match = palloc(strlen(patt)+1);
1860         match_pos = 0;
1861
1862         /* note start at pos 1 to skip leading ^ */
1863         for (pos = 1; patt[pos]; pos++)
1864         {
1865                 if (patt[pos] == '.' ||
1866                         patt[pos] == '?' ||
1867                         patt[pos] == '*' ||
1868                         patt[pos] == '[' ||
1869                         patt[pos] == '$' ||
1870                         /* XXX I suspect isalpha() is not an adequately locale-sensitive
1871                          * test for characters that can vary under case folding?
1872                          */
1873                         (case_insensitive && isalpha(patt[pos])))
1874                         break;
1875                 if (patt[pos] == '\\')
1876                 {
1877                         pos++;
1878                         if (patt[pos] == '\0')
1879                                 break;
1880                 }
1881                 match[match_pos++] = patt[pos];
1882         }
1883
1884         match[match_pos] = '\0';
1885
1886         if (patt[pos] == '$' && patt[pos+1] == '\0')
1887                 return Prefix_Exact;    /* pattern specifies exact match */
1888
1889         if (match_pos > 0)
1890                 return Prefix_Partial;
1891         return Prefix_None;
1892 }
1893
1894 /*
1895  * Given a fixed prefix that all the "leftop" values must have,
1896  * generate suitable indexqual condition(s).  expr_op is the original
1897  * LIKE or regex operator; we use it to deduce the appropriate comparison
1898  * operators.
1899  */
1900 static List *
1901 prefix_quals(Var *leftop, Oid expr_op,
1902                          char *prefix, Prefix_Status pstatus)
1903 {
1904         List       *result;
1905         Oid                     datatype;
1906         Oid                     oproid;
1907         Const      *con;
1908         Oper       *op;
1909         Expr       *expr;
1910         char       *greaterstr;
1911
1912         Assert(pstatus != Prefix_None);
1913
1914         switch (expr_op)
1915         {
1916                 case OID_TEXT_LIKE_OP:
1917                 case OID_TEXT_REGEXEQ_OP:
1918                 case OID_TEXT_ICREGEXEQ_OP:
1919                         datatype = TEXTOID;
1920                         break;
1921
1922                 case OID_BPCHAR_LIKE_OP:
1923                 case OID_BPCHAR_REGEXEQ_OP:
1924                 case OID_BPCHAR_ICREGEXEQ_OP:
1925                         datatype = BPCHAROID;
1926                         break;
1927
1928                 case OID_VARCHAR_LIKE_OP:
1929                 case OID_VARCHAR_REGEXEQ_OP:
1930                 case OID_VARCHAR_ICREGEXEQ_OP:
1931                         datatype = VARCHAROID;
1932                         break;
1933
1934                 case OID_NAME_LIKE_OP:
1935                 case OID_NAME_REGEXEQ_OP:
1936                 case OID_NAME_ICREGEXEQ_OP:
1937                         datatype = NAMEOID;
1938                         break;
1939
1940                 default:
1941                         elog(ERROR, "prefix_quals: unexpected operator %u", expr_op);
1942                         return NIL;
1943         }
1944
1945         /*
1946          * If we found an exact-match pattern, generate an "=" indexqual.
1947          */
1948         if (pstatus == Prefix_Exact)
1949         {
1950                 oproid = find_operator("=", datatype);
1951                 if (oproid == InvalidOid)
1952                         elog(ERROR, "prefix_quals: no = operator for type %u", datatype);
1953                 con = string_to_const(prefix, datatype);
1954                 op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1955                 expr = make_opclause(op, leftop, (Var *) con);
1956                 result = lcons(expr, NIL);
1957                 return result;
1958         }
1959
1960         /*
1961          * Otherwise, we have a nonempty required prefix of the values.
1962          *
1963          * We can always say "x >= prefix".
1964          */
1965         oproid = find_operator(">=", datatype);
1966         if (oproid == InvalidOid)
1967                 elog(ERROR, "prefix_quals: no >= operator for type %u", datatype);
1968         con = string_to_const(prefix, datatype);
1969         op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1970         expr = make_opclause(op, leftop, (Var *) con);
1971         result = lcons(expr, NIL);
1972
1973         /*
1974          * If we can create a string larger than the prefix, say "x < greaterstr".
1975          */
1976         greaterstr = make_greater_string(prefix, datatype);
1977         if (greaterstr)
1978         {
1979                 oproid = find_operator("<", datatype);
1980                 if (oproid == InvalidOid)
1981                         elog(ERROR, "prefix_quals: no < operator for type %u", datatype);
1982                 con = string_to_const(greaterstr, datatype);
1983                 op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1984                 expr = make_opclause(op, leftop, (Var *) con);
1985                 result = lappend(result, expr);
1986                 pfree(greaterstr);
1987         }
1988
1989         return result;
1990 }
1991
1992 /*
1993  * Try to generate a string greater than the given string or any string it is
1994  * a prefix of.  If successful, return a palloc'd string; else return NULL.
1995  *
1996  * To work correctly in non-ASCII locales with weird collation orders,
1997  * we cannot simply increment "foo" to "fop" --- we have to check whether
1998  * we actually produced a string greater than the given one.  If not,
1999  * increment the righthand byte again and repeat.  If we max out the righthand
2000  * byte, truncate off the last character and start incrementing the next.
2001  * For example, if "z" were the last character in the sort order, then we
2002  * could produce "foo" as a string greater than "fonz".
2003  *
2004  * This could be rather slow in the worst case, but in most cases we won't
2005  * have to try more than one or two strings before succeeding.
2006  *
2007  * XXX in a sufficiently weird locale, this might produce incorrect results?
2008  * For example, in German I believe "ss" is treated specially --- if we are
2009  * given "foos" and return "foot", will this actually be greater than "fooss"?
2010  */
2011 static char *
2012 make_greater_string(const char * str, Oid datatype)
2013 {
2014         char       *workstr;
2015         int                     len;
2016
2017         /* Make a modifiable copy, which will be our return value if successful */
2018         workstr = pstrdup((char *) str);
2019
2020         while ((len = strlen(workstr)) > 0)
2021         {
2022                 unsigned char  *lastchar = (unsigned char *) (workstr + len - 1);
2023
2024                 /*
2025                  * Try to generate a larger string by incrementing the last byte.
2026                  */
2027                 while (*lastchar < (unsigned char) 255)
2028                 {
2029                         (*lastchar)++;
2030                         if (string_lessthan(str, workstr, datatype))
2031                                 return workstr;                 /* Success! */
2032                 }
2033                 /*
2034                  * Truncate off the last character, which might be more than 1 byte
2035                  * in MULTIBYTE case.
2036                  */
2037 #ifdef MULTIBYTE
2038                 len = pg_mbcliplen((const unsigned char *) workstr, len, len-1);
2039                 workstr[len] = '\0';
2040 #else
2041                 *lastchar = '\0';
2042 #endif
2043         }
2044
2045         /* Failed... */
2046         pfree(workstr);
2047         return NULL;
2048 }
2049
2050 /*
2051  * Handy subroutines for match_special_index_operator() and friends.
2052  */
2053
2054 /* See if there is a binary op of the given name for the given datatype */
2055 static Oid
2056 find_operator(const char * opname, Oid datatype)
2057 {
2058         HeapTuple       optup;
2059
2060         optup = SearchSysCacheTuple(OPERNAME,
2061                                                                 PointerGetDatum(opname),
2062                                                                 ObjectIdGetDatum(datatype),
2063                                                                 ObjectIdGetDatum(datatype),
2064                                                                 CharGetDatum('b'));
2065         if (!HeapTupleIsValid(optup))
2066                 return InvalidOid;
2067         return optup->t_data->t_oid;
2068 }
2069
2070 /*
2071  * Generate a Datum of the appropriate type from a C string.
2072  * Note that all of the supported types are pass-by-ref, so the
2073  * returned value should be pfree'd if no longer needed.
2074  */
2075 static Datum
2076 string_to_datum(const char * str, Oid datatype)
2077 {
2078         /* We cheat a little by assuming that textin() will do for
2079          * bpchar and varchar constants too...
2080          */
2081         if (datatype == NAMEOID)
2082                 return PointerGetDatum(namein((char *) str));
2083         else
2084                 return PointerGetDatum(textin((char *) str));
2085 }
2086
2087 /*
2088  * Generate a Const node of the appropriate type from a C string.
2089  */
2090 static Const *
2091 string_to_const(const char * str, Oid datatype)
2092 {
2093         Datum           conval = string_to_datum(str, datatype);
2094
2095         return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2096                                          conval, false, false, false, false);
2097 }
2098
2099 /*
2100  * Test whether two strings are "<" according to the rules of the given
2101  * datatype.  We do this the hard way, ie, actually calling the type's
2102  * "<" operator function, to ensure we get the right result...
2103  */
2104 static bool
2105 string_lessthan(const char * str1, const char * str2, Oid datatype)
2106 {
2107         Datum           datum1 = string_to_datum(str1, datatype);
2108         Datum           datum2 = string_to_datum(str2, datatype);
2109         bool            result;
2110
2111         switch (datatype)
2112         {
2113                 case TEXTOID:
2114                         result = text_lt((text *) datum1, (text *) datum2);
2115                         break;
2116
2117                 case BPCHAROID:
2118                         result = bpcharlt((char *) datum1, (char *) datum2);
2119                         break;
2120
2121                 case VARCHAROID:
2122                         result = varcharlt((char *) datum1, (char *) datum2);
2123                         break;
2124
2125                 case NAMEOID:
2126                         result = namelt((NameData *) datum1, (NameData *) datum2);
2127                         break;
2128
2129                 default:
2130                         elog(ERROR, "string_lessthan: unexpected datatype %u", datatype);
2131                         result = false;
2132                         break;
2133         }
2134
2135         pfree(DatumGetPointer(datum1));
2136         pfree(DatumGetPointer(datum2));
2137
2138         return result;
2139 }