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

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