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

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