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