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.65 1999/07/25 23:07:24 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include <math.h>
  16
  17 #include "postgres.h"
  18
  19 #include "access/heapam.h"
  20 #include "access/nbtree.h"
  21 #include "catalog/catname.h"
  22 #include "catalog/pg_amop.h"
  23 #include "executor/executor.h"
  24 #include "nodes/makefuncs.h"
  25 #include "nodes/nodeFuncs.h"
  26 #include "optimizer/clauses.h"
  27 #include "optimizer/cost.h"
  28 #include "optimizer/keys.h"
  29 #include "optimizer/ordering.h"
  30 #include "optimizer/pathnode.h"
  31 #include "optimizer/paths.h"
  32 #include "optimizer/plancat.h"
  33 #include "optimizer/restrictinfo.h"
  34 #include "parser/parse_coerce.h"
  35 #include "parser/parse_expr.h"
  36 #include "parser/parse_oper.h"
  37 #include "parser/parsetree.h"
  38 #include "utils/lsyscache.h"
  39
  40
  41 static void match_index_orclauses(RelOptInfo *rel, RelOptInfo *index, int indexkey,
  42                                           int xclass, List *restrictinfo_list);
  43 static List *match_index_orclause(RelOptInfo *rel, RelOptInfo *index, int indexkey,
  44                          int xclass, List *or_clauses, List *other_matching_indices);
  45 static List *group_clauses_by_indexkey(RelOptInfo *rel, RelOptInfo *index,
  46                                   int *indexkeys, Oid *classes, List *restrictinfo_list);
  47 static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel, RelOptInfo *index,
  48                                                                 int *indexkeys, Oid *classes, List *join_cinfo_list, List *restr_cinfo_list);
  49 static bool match_clause_to_indexkey(RelOptInfo *rel, RelOptInfo *index,
  50                                                                          int indexkey, int xclass,
  51                                                                          Expr *clause, bool join);
  52 static bool pred_test(List *predicate_list, List *restrictinfo_list,
  53                   List *joininfo_list);
  54 static bool one_pred_test(Expr *predicate, List *restrictinfo_list);
  55 static bool one_pred_clause_expr_test(Expr *predicate, Node *clause);
  56 static bool one_pred_clause_test(Expr *predicate, Node *clause);
  57 static bool clause_pred_clause_test(Expr *predicate, Node *clause);
  58 static void indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index,
  59                                                                   List *joininfo_list, List *restrictinfo_list,
  60                                                                   List **clausegroups, List **outerrelids);
  61 static List *index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index,
  62                                                          List *clausegroup_list, List *outerrelids_list);
  63 static List *create_index_path_group(Query *root, RelOptInfo *rel, RelOptInfo *index,
  64                                                 List *clausegroup_list, bool join);
  65 static bool match_index_to_operand(int indexkey, Expr *operand,
  66                                                                    RelOptInfo *rel, RelOptInfo *index);
  67 static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index);
  68
  69
  70 /*
  71  * create_index_paths()
  72  *        Generate all interesting index paths for the given relation.
  73  *
  74  *        To be considered for an index scan, an index must match one or more
  75  *        restriction clauses or join clauses from the query's qual condition.
  76  *
  77  *        Note: an index scan might also be used simply to order the result,
  78  *        either for use in a mergejoin or to satisfy an ORDER BY request.
  79  *        That possibility is handled elsewhere.
  80  *
  81  * 'rel' is the relation for which we want to generate index paths
  82  * 'indices' is a list of available indexes for 'rel'
  83  * 'restrictinfo_list' is a list of restrictinfo nodes for 'rel'
  84  * 'joininfo_list' is a list of joininfo nodes for 'rel'
  85  *
  86  * Returns a list of IndexPath access path descriptors.
  87  */
  88 List *
  89 create_index_paths(Query *root,
  90                                    RelOptInfo *rel,
  91                                    List *indices,
  92                                    List *restrictinfo_list,
  93                                    List *joininfo_list)
  94 {
  95         List       *retval = NIL;
  96         List       *ilist;
  97
  98         foreach(ilist, indices)
  99         {
 100                 RelOptInfo *index = (RelOptInfo *) lfirst(ilist);
 101                 List       *scanclausegroups;
 102                 List       *joinclausegroups;
 103                 List       *joinouterrelids;
 104
 105                 /*
 106                  * If this is a partial index, we can only use it if it passes
 107                  * the predicate test.
 108                  */
 109                 if (index->indpred != NIL)
 110                         if (!pred_test(index->indpred, restrictinfo_list, joininfo_list))
 111                                 continue;
 112
 113                 /*
 114                  * 1. Try matching the index against subclauses of restriction 'or'
 115                  * clauses (ie, 'or' clauses that reference only this relation).
 116                  * The restrictinfo nodes for the 'or' clauses are marked with lists
 117                  * of the matching indices.  No paths are actually created now;
 118                  * that will be done in orindxpath.c after all indexes for the rel
 119                  * have been examined.  (We need to do it that way because we can
 120                  * potentially use a different index for each subclause of an 'or',
 121                  * so we can't build a path for an 'or' clause until all indexes have
 122                  * been matched against it.)
 123                  *
 124                  * We currently only look to match the first key of each index against
 125                  * 'or' subclauses.  There are cases where a later key of a multi-key
 126                  * index could be used (if other top-level clauses match earlier keys
 127                  * of the index), but our poor brains are hurting already...
 128                  *
 129                  * We don't even think about special handling of 'or' clauses that
 130                  * involve more than one relation, since they can't be processed by
 131                  * a single indexscan path anyway.  Currently, cnfify() is certain
 132                  * to have restructured any such toplevel 'or' clauses anyway.
 133                  */
 134                 match_index_orclauses(rel,
 135                                                           index,
 136                                                           index->indexkeys[0],
 137                                                           index->classlist[0],
 138                                                           restrictinfo_list);
 139
 140                 /*
 141                  * 2. If the keys of this index match any of the available non-'or'
 142                  * restriction clauses, then create a path using those clauses
 143                  * as indexquals.
 144                  */
 145                 scanclausegroups = group_clauses_by_indexkey(rel,
 146                                                                                                          index,
 147                                                                                                          index->indexkeys,
 148                                                                                                          index->classlist,
 149                                                                                                          restrictinfo_list);
 150
 151                 if (scanclausegroups != NIL)
 152                         retval = nconc(retval,
 153                                                    create_index_path_group(root,
 154                                                                                                    rel,
 155                                                                                                    index,
 156                                                                                                    scanclausegroups,
 157                                                                                                    false));
 158
 159                 /*
 160                  * 3. If this index can be used with any join clause, then create
 161                  * pathnodes for each group of usable clauses.  An index can be
 162                  * used with a join clause if its ordering is useful for a
 163                  * mergejoin, or if the index can possibly be used for scanning
 164                  * the inner relation of a nestloop join.
 165                  */
 166                 indexable_joinclauses(rel, index,
 167                                                           joininfo_list, restrictinfo_list,
 168                                                           &joinclausegroups,
 169                                                           &joinouterrelids);
 170
 171                 if (joinclausegroups != NIL)
 172                 {
 173                         retval = nconc(retval,
 174                                                    create_index_path_group(root,
 175                                                                                                    rel,
 176                                                                                                    index,
 177                                                                                                    joinclausegroups,
 178                                                                                                    true));
 179                         rel->innerjoin = nconc(rel->innerjoin,
 180                                                                    index_innerjoin(root, rel, index,
 181                                                                                                    joinclausegroups,
 182                                                                                                    joinouterrelids));
 183                 }
 184         }
 185
 186         return retval;
 187 }
 188
 189
 190 /****************************************************************************
 191  *              ----  ROUTINES TO PROCESS 'OR' CLAUSES  ----
 192  ****************************************************************************/
 193
 194
 195 /*
 196  * match_index_orclauses
 197  *        Attempt to match an index against subclauses within 'or' clauses.
 198  *        Each subclause that does match is marked with the index's node.
 199  *
 200  *        Essentially, this adds 'index' to the list of subclause indices in
 201  *        the RestrictInfo field of each of the 'or' clauses where it matches.
 202  *        NOTE: we can use storage in the RestrictInfo for this purpose because
 203  *        this processing is only done on single-relation restriction clauses.
 204  *        Therefore, we will never have indexes for more than one relation
 205  *        mentioned in the same RestrictInfo node's list.
 206  *
 207  * 'rel' is the node of the relation on which the index is defined.
 208  * 'index' is the index node.
 209  * 'indexkey' is the (single) key of the index that we will consider.
 210  * 'class' is the class of the operator corresponding to 'indexkey'.
 211  * 'restrictinfo_list' is the list of available restriction clauses.
 212  */
 213 static void
 214 match_index_orclauses(RelOptInfo *rel,
 215                                           RelOptInfo *index,
 216                                           int indexkey,
 217                                           int xclass,
 218                                           List *restrictinfo_list)
 219 {
 220         List       *i;
 221
 222         foreach(i, restrictinfo_list)
 223         {
 224                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
 225
 226                 if (restriction_is_or_clause(restrictinfo))
 227                 {
 228                         /*
 229                          * Add this index to the subclause index list for each
 230                          * subclause that it matches.
 231                          */
 232                         restrictinfo->indexids =
 233                                 match_index_orclause(rel, index,
 234                                                                          indexkey, xclass,
 235                                                                          restrictinfo->clause->args,
 236                                                                          restrictinfo->indexids);
 237                 }
 238         }
 239 }
 240
 241 /*
 242  * match_index_orclause
 243  *        Attempts to match an index against the subclauses of an 'or' clause.
 244  *
 245  *        A match means that:
 246  *        (1) the operator within the subclause can be used with the
 247  *                              index's specified operator class, and
 248  *        (2) the variable on one side of the subclause matches the index key.
 249  *
 250  * 'or_clauses' is the list of subclauses within the 'or' clause
 251  * 'other_matching_indices' is the list of information on other indices
 252  *              that have already been matched to subclauses within this
 253  *              particular 'or' clause (i.e., a list previously generated by
 254  *              this routine), or NIL if this routine has not previously been
 255  *          run for this 'or' clause.
 256  *
 257  * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where
 258  * a,b,c are nodes of indices that match the first subclause in
 259  * 'or-clauses', d,e,f match the second subclause, no indices
 260  * match the third, g,h match the fourth, etc.
 261  */
 262 static List *
 263 match_index_orclause(RelOptInfo *rel,
 264                                          RelOptInfo *index,
 265                                          int indexkey,
 266                                          int xclass,
 267                                          List *or_clauses,
 268                                          List *other_matching_indices)
 269 {
 270         List       *matching_indices;
 271         List       *index_list;
 272         List       *clist;
 273
 274         /* first time through, we create list of same length as OR clause,
 275          * containing an empty sublist for each subclause.
 276          */
 277         if (!other_matching_indices)
 278         {
 279                 matching_indices = NIL;
 280                 foreach(clist, or_clauses)
 281                         matching_indices = lcons(NIL, matching_indices);
 282         }
 283         else
 284                 matching_indices = other_matching_indices;
 285
 286         index_list = matching_indices;
 287
 288         foreach(clist, or_clauses)
 289         {
 290                 Expr       *clause = lfirst(clist);
 291
 292                 if (match_clause_to_indexkey(rel, index, indexkey, xclass,
 293                                                                          clause, false))
 294                 {
 295                         /* OK to add this index to sublist for this subclause */
 296                         lfirst(matching_indices) = lcons(index,
 297                                                                                          lfirst(matching_indices));
 298                 }
 299
 300                 matching_indices = lnext(matching_indices);
 301         }
 302
 303         return index_list;
 304 }
 305
 306 /****************************************************************************
 307  *                              ----  ROUTINES TO CHECK RESTRICTIONS  ----
 308  ****************************************************************************/
 309
 310
 311 /*
 312  * DoneMatchingIndexKeys() - MACRO
 313  *
 314  * Determine whether we should continue matching index keys in a clause.
 315  * Depends on if there are more to match or if this is a functional index.
 316  * In the latter case we stop after the first match since the there can
 317  * be only key (i.e. the function's return value) and the attributes in
 318  * keys list represent the arguments to the function.  -mer 3 Oct. 1991
 319  */
 320 #define DoneMatchingIndexKeys(indexkeys, index) \
 321                 (indexkeys[0] == 0 || \
 322                  (index->indproc != InvalidOid))
 323
 324 /*
 325  * group_clauses_by_indexkey
 326  *        Generates a list of restriction clauses that can be used with an index.
 327  *
 328  * 'rel' is the node of the relation itself.
 329  * 'index' is a index on 'rel'.
 330  * 'indexkeys' are the index keys to be matched.
 331  * 'classes' are the classes of the index operators on those keys.
 332  * 'restrictinfo_list' is the list of available restriction clauses for 'rel'.
 333  *
 334  * Returns NIL if no clauses can be used with this index.
 335  * Otherwise, a list containing a single sublist is returned (indicating
 336  * to create_index_path_group() that a single IndexPath should be created).
 337  * The sublist contains the RestrictInfo nodes for all clauses that can be
 338  * used with this index.
 339  *
 340  * The sublist is ordered by index key (but as far as I can tell, this is
 341  * an implementation artifact of this routine, and is not depended on by
 342  * any user of the returned list --- tgl 7/99).
 343  *
 344  * Note that in a multi-key index, we stop if we find a key that cannot be
 345  * used with any clause.  For example, given an index on (A,B,C), we might
 346  * return ((C1 C2 C3 C4)) if we find that clauses C1 and C2 use column A,
 347  * clauses C3 and C4 use column B, and no clauses use column C.  But if no
 348  * clauses match B we will return ((C1 C2)), whether or not there are
 349  * clauses matching column C, because the executor couldn't use them anyway.
 350  */
 351 static List *
 352 group_clauses_by_indexkey(RelOptInfo *rel,
 353                                                   RelOptInfo *index,
 354                                                   int *indexkeys,
 355                                                   Oid *classes,
 356                                                   List *restrictinfo_list)
 357 {
 358         List       *clausegroup_list = NIL;
 359
 360         if (restrictinfo_list == NIL || indexkeys[0] == 0)
 361                 return NIL;
 362
 363         do
 364         {
 365                 int                     curIndxKey = indexkeys[0];
 366                 Oid                     curClass = classes[0];
 367                 List       *clausegroup = NIL;
 368                 List       *curCinfo;
 369
 370                 foreach(curCinfo, restrictinfo_list)
 371                 {
 372                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
 373
 374                         if (match_clause_to_indexkey(rel,
 375                                                                                  index,
 376                                                                                  curIndxKey,
 377                                                                                  curClass,
 378                                                                                  rinfo->clause,
 379                                                                                  false))
 380                                 clausegroup = lappend(clausegroup, rinfo);
 381                 }
 382
 383                 /* If no clauses match this key, we're done; we don't want to
 384                  * look at keys to its right.
 385                  */
 386                 if (clausegroup == NIL)
 387                         break;
 388
 389                 clausegroup_list = nconc(clausegroup_list, clausegroup);
 390
 391                 indexkeys++;
 392                 classes++;
 393
 394         } while (!DoneMatchingIndexKeys(indexkeys, index));
 395
 396         /* clausegroup_list holds all matched clauses ordered by indexkeys */
 397         if (clausegroup_list != NIL)
 398                 return lcons(clausegroup_list, NIL);
 399         return NIL;
 400 }
 401
 402 /*
 403  * group_clauses_by_ikey_for_joins
 404  *    Generates a list of join clauses that can be used with an index.
 405  *
 406  * This is much like group_clauses_by_indexkey(), but we consider both
 407  * join and restriction clauses.  For each indexkey in the index, we
 408  * accept both join and restriction clauses that match it (since both
 409  * will make useful indexquals if the index is being used to scan the
 410  * inner side of a join).  But there must be at least one matching
 411  * join clause, or we return NIL indicating that this index isn't useful
 412  * for joining.
 413  */
 414 static List *
 415 group_clauses_by_ikey_for_joins(RelOptInfo *rel,
 416                                                                 RelOptInfo *index,
 417                                                                 int *indexkeys,
 418                                                                 Oid *classes,
 419                                                                 List *join_cinfo_list,
 420                                                                 List *restr_cinfo_list)
 421 {
 422         List       *clausegroup_list = NIL;
 423         bool            jfound = false;
 424
 425         if (join_cinfo_list == NIL || indexkeys[0] == 0)
 426                 return NIL;
 427
 428         do
 429         {
 430                 int                     curIndxKey = indexkeys[0];
 431                 Oid                     curClass = classes[0];
 432                 List       *clausegroup = NIL;
 433                 List       *curCinfo;
 434
 435                 foreach(curCinfo, join_cinfo_list)
 436                 {
 437                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
 438
 439                         if (match_clause_to_indexkey(rel,
 440                                                                                  index,
 441                                                                                  curIndxKey,
 442                                                                                  curClass,
 443                                                                                  rinfo->clause,
 444                                                                                  true))
 445                         {
 446                                 clausegroup = lappend(clausegroup, rinfo);
 447                                 jfound = true;
 448                         }
 449                 }
 450                 foreach(curCinfo, restr_cinfo_list)
 451                 {
 452                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
 453
 454                         if (match_clause_to_indexkey(rel,
 455                                                                                  index,
 456                                                                                  curIndxKey,
 457                                                                                  curClass,
 458                                                                                  rinfo->clause,
 459                                                                                  false))
 460                                 clausegroup = lappend(clausegroup, rinfo);
 461                 }
 462
 463                 /* If no clauses match this key, we're done; we don't want to
 464                  * look at keys to its right.
 465                  */
 466                 if (clausegroup == NIL)
 467                         break;
 468
 469                 clausegroup_list = nconc(clausegroup_list, clausegroup);
 470
 471                 indexkeys++;
 472                 classes++;
 473
 474         } while (!DoneMatchingIndexKeys(indexkeys, index));
 475
 476         /* clausegroup_list holds all matched clauses ordered by indexkeys */
 477
 478         if (clausegroup_list != NIL)
 479         {
 480                 /*
 481                  * if no join clause was matched then there ain't clauses for
 482                  * joins at all.
 483                  */
 484                 if (!jfound)
 485                 {
 486                         freeList(clausegroup_list);
 487                         return NIL;
 488                 }
 489                 return lcons(clausegroup_list, NIL);
 490         }
 491         return NIL;
 492 }
 493
 494
 495 /*
 496  * match_clause_to_indexkey()
 497  *    Determines whether a restriction or join clause matches
 498  *    a key of an index.
 499  *
 500  *        To match, the clause must:
 501  *        (1) be in the form (var op const) for a restriction clause,
 502  *                or (var op var) for a join clause, where the var or one
 503  *                of the vars matches the index key; and
 504  *        (2) contain an operator which is in the same class as the index
 505  *                operator for this key.
 506  *
 507  *        In the restriction case, we can cope with (const op var) by commuting
 508  *        the clause to (var op const), if there is a commutator operator.
 509  *        XXX why do we bother to commute?  The executor doesn't care!!
 510  *
 511  *        In the join case, later code will try to commute the clause if needed
 512  *        to put the inner relation's var on the right.  We have no idea here
 513  *        which relation might wind up on the inside, so we just accept
 514  *        a match for either var.
 515  *        XXX is this right?  We are making a list for this relation to
 516  *        be an inner join relation, so if there is any commuting then
 517  *        this rel must be on the right.  But again, it's not really clear
 518  *        that we have to commute at all!
 519  *
 520  * 'rel' is the relation of interest.
 521  * 'index' is an index on 'rel'.
 522  * 'indexkey' is a key of 'index'.
 523  * 'xclass' is the corresponding operator class.
 524  * 'clause' is the clause to be tested.
 525  * 'join' is true if we are considering this clause for joins.
 526  *
 527  * Returns true if the clause can be used with this index key.
 528  *
 529  * NOTE:  returns false if clause is an or_clause; that's handled elsewhere.
 530  */
 531 static bool
 532 match_clause_to_indexkey(RelOptInfo *rel,
 533                                                  RelOptInfo *index,
 534                                                  int indexkey,
 535                                                  int xclass,
 536                                                  Expr *clause,
 537                                                  bool join)
 538 {
 539         bool            isIndexable = false;
 540         Var                *leftop,
 541                            *rightop;
 542
 543         if (! is_opclause((Node *) clause))
 544                 return false;
 545         leftop = get_leftop(clause);
 546         rightop = get_rightop(clause);
 547         if (! leftop || ! rightop)
 548                 return false;
 549
 550         if (!join)
 551         {
 552                 /*
 553                  * Not considering joins, so check for clauses of the form:
 554                  * (var/func operator constant) and (constant operator var/func)
 555                  */
 556                 Oid                     restrict_op = InvalidOid;
 557
 558                 /*
 559                  * Check for standard s-argable clause
 560                  */
 561                 if (IsA(rightop, Const) || IsA(rightop, Param))
 562                 {
 563                         restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno;
 564
 565                         isIndexable = (op_class(restrict_op, xclass, index->relam) &&
 566                                                    match_index_to_operand(indexkey,
 567                                                                                                   (Expr *) leftop,
 568                                                                                                   rel,
 569                                                                                                   index));
 570
 571 #ifndef IGNORE_BINARY_COMPATIBLE_INDICES
 572
 573                         /*
 574                          * Didn't find an index? Then maybe we can find another
 575                          * binary-compatible index instead... thomas 1998-08-14
 576                          */
 577                         if (!isIndexable)
 578                         {
 579                                 Oid                     ltype = exprType((Node *) leftop);
 580                                 Oid                     rtype = exprType((Node *) rightop);
 581
 582                                 /*
 583                                  * make sure we have two different binary-compatible
 584                                  * types...
 585                                  */
 586                                 if ((ltype != rtype)
 587                                         && IS_BINARY_COMPATIBLE(ltype, rtype))
 588                                 {
 589                                         char       *opname;
 590                                         Operator        newop;
 591
 592                                         opname = get_opname(restrict_op);
 593                                         if (opname != NULL)
 594                                                 newop = oper(opname, ltype, ltype, TRUE);
 595                                         else
 596                                                 newop = NULL;
 597
 598                                         /* actually have a different operator to try? */
 599                                         if (HeapTupleIsValid(newop) &&
 600                                                 (oprid(newop) != restrict_op))
 601                                         {
 602                                                 restrict_op = oprid(newop);
 603
 604                                                 isIndexable = (op_class(restrict_op, xclass, index->relam) &&
 605                                                                            match_index_to_operand(indexkey,
 606                                                                                                                           (Expr *) leftop,
 607                                                                                                                           rel,
 608                                                                                                                           index));
 609
 610                                                 if (isIndexable)
 611                                                         ((Oper *) ((Expr *) clause)->oper)->opno = restrict_op;
 612                                         }
 613                                 }
 614                         }
 615 #endif
 616                 }
 617
 618                 /*
 619                  * Must try to commute the clause to standard s-arg format.
 620                  */
 621                 else if (IsA(leftop, Const) || IsA(leftop, Param))
 622                 {
 623                         restrict_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno);
 624
 625                         isIndexable = ((restrict_op != InvalidOid) &&
 626                                                    op_class(restrict_op, xclass, index->relam) &&
 627                                                    match_index_to_operand(indexkey,
 628                                                                                                   (Expr *) rightop,
 629                                                                                                   rel,
 630                                                                                                   index));
 631
 632 #ifndef IGNORE_BINARY_COMPATIBLE_INDICES
 633                         if (!isIndexable)
 634                         {
 635                                 Oid                     ltype;
 636                                 Oid                     rtype;
 637
 638                                 ltype = exprType((Node *) leftop);
 639                                 rtype = exprType((Node *) rightop);
 640
 641                                 if ((ltype != rtype)
 642                                         && IS_BINARY_COMPATIBLE(ltype, rtype))
 643                                 {
 644                                         char       *opname;
 645                                         Operator        newop;
 646
 647                                         restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno;
 648
 649                                         opname = get_opname(restrict_op);
 650                                         if (opname != NULL)
 651                                                 newop = oper(opname, rtype, rtype, TRUE);
 652                                         else
 653                                                 newop = NULL;
 654
 655                                         if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op))
 656                                         {
 657                                                 restrict_op = get_commutator(oprid(newop));
 658
 659                                                 isIndexable = ((restrict_op != InvalidOid) &&
 660                                                    op_class(restrict_op, xclass, index->relam) &&
 661                                                                            match_index_to_operand(indexkey,
 662                                                                                                                           (Expr *) rightop,
 663                                                                                                                           rel,
 664                                                                                                                           index));
 665
 666                                                 if (isIndexable)
 667                                                         ((Oper *) ((Expr *) clause)->oper)->opno = oprid(newop);
 668                                         }
 669                                 }
 670                         }
 671 #endif
 672
 673                         if (isIndexable)
 674                         {
 675
 676                                 /*
 677                                  * In place list modification. (op const var/func) -> (op
 678                                  * var/func const)
 679                                  */
 680                                 CommuteClause((Node *) clause);
 681                         }
 682                 }
 683         }
 684         else
 685         {
 686                 /*
 687                  * Check for an indexable scan on one of the join relations.
 688                  * clause is of the form (operator var/func var/func)
 689                  *  XXX this does not seem right.  Should check other side
 690                  * looks like var/func? do we really want to only consider
 691                  * this rel on lefthand side??
 692                  */
 693                 Oid                     join_op = InvalidOid;
 694
 695                 if (match_index_to_operand(indexkey, (Expr *) leftop,
 696                                                                    rel, index))
 697                         join_op = ((Oper *) ((Expr *) clause)->oper)->opno;
 698                 else if (match_index_to_operand(indexkey, (Expr *) rightop,
 699                                                                                 rel, index))
 700                         join_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno);
 701
 702                 if (join_op && op_class(join_op, xclass, index->relam) &&
 703                         is_joinable((Node *) clause))
 704                         isIndexable = true;
 705         }
 706
 707         return isIndexable;
 708 }
 709
 710 /****************************************************************************
 711  *                              ----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS      ----
 712  ****************************************************************************/
 713
 714 /*
 715  * pred_test
 716  *        Does the "predicate inclusion test" for partial indexes.
 717  *
 718  *        Recursively checks whether the clauses in restrictinfo_list imply
 719  *        that the given predicate is true.
 720  *
 721  *        This routine (together with the routines it calls) iterates over
 722  *        ANDs in the predicate first, then reduces the qualification
 723  *        clauses down to their constituent terms, and iterates over ORs
 724  *        in the predicate last.  This order is important to make the test
 725  *        succeed whenever possible (assuming the predicate has been
 726  *        successfully cnfify()-ed). --Nels, Jan '93
 727  */
 728 static bool
 729 pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list)
 730 {
 731         List       *pred,
 732                            *items,
 733                            *item;
 734
 735         /*
 736          * Note: if Postgres tried to optimize queries by forming equivalence
 737          * classes over equi-joined attributes (i.e., if it recognized that a
 738          * qualification such as "where a.b=c.d and a.b=5" could make use of
 739          * an index on c.d), then we could use that equivalence class info
 740          * here with joininfo_list to do more complete tests for the usability
 741          * of a partial index.  For now, the test only uses restriction
 742          * clauses (those in restrictinfo_list). --Nels, Dec '92
 743          */
 744
 745         if (predicate_list == NULL)
 746                 return true;                    /* no predicate: the index is usable */
 747         if (restrictinfo_list == NULL)
 748                 return false;                   /* no restriction clauses: the test must
 749                                                                  * fail */
 750
 751         foreach(pred, predicate_list)
 752         {
 753
 754                 /*
 755                  * if any clause is not implied, the whole predicate is not
 756                  * implied
 757                  */
 758                 if (and_clause(lfirst(pred)))
 759                 {
 760                         items = ((Expr *) lfirst(pred))->args;
 761                         foreach(item, items)
 762                         {
 763                                 if (!one_pred_test(lfirst(item), restrictinfo_list))
 764                                         return false;
 765                         }
 766                 }
 767                 else if (!one_pred_test(lfirst(pred), restrictinfo_list))
 768                         return false;
 769         }
 770         return true;
 771 }
 772
 773
 774 /*
 775  * one_pred_test
 776  *        Does the "predicate inclusion test" for one conjunct of a predicate
 777  *        expression.
 778  */
 779 static bool
 780 one_pred_test(Expr *predicate, List *restrictinfo_list)
 781 {
 782         RestrictInfo *restrictinfo;
 783         List       *item;
 784
 785         Assert(predicate != NULL);
 786         foreach(item, restrictinfo_list)
 787         {
 788                 restrictinfo = (RestrictInfo *) lfirst(item);
 789                 /* if any clause implies the predicate, return true */
 790                 if (one_pred_clause_expr_test(predicate, (Node *) restrictinfo->clause))
 791                         return true;
 792         }
 793         return false;
 794 }
 795
 796
 797 /*
 798  * one_pred_clause_expr_test
 799  *        Does the "predicate inclusion test" for a general restriction-clause
 800  *        expression.
 801  */
 802 static bool
 803 one_pred_clause_expr_test(Expr *predicate, Node *clause)
 804 {
 805         List       *items,
 806                            *item;
 807
 808         if (is_opclause(clause))
 809                 return one_pred_clause_test(predicate, clause);
 810         else if (or_clause(clause))
 811         {
 812                 items = ((Expr *) clause)->args;
 813                 foreach(item, items)
 814                 {
 815                         /* if any OR item doesn't imply the predicate, clause doesn't */
 816                         if (!one_pred_clause_expr_test(predicate, lfirst(item)))
 817                                 return false;
 818                 }
 819                 return true;
 820         }
 821         else if (and_clause(clause))
 822         {
 823                 items = ((Expr *) clause)->args;
 824                 foreach(item, items)
 825                 {
 826
 827                         /*
 828                          * if any AND item implies the predicate, the whole clause
 829                          * does
 830                          */
 831                         if (one_pred_clause_expr_test(predicate, lfirst(item)))
 832                                 return true;
 833                 }
 834                 return false;
 835         }
 836         else
 837         {
 838                 /* unknown clause type never implies the predicate */
 839                 return false;
 840         }
 841 }
 842
 843
 844 /*
 845  * one_pred_clause_test
 846  *        Does the "predicate inclusion test" for one conjunct of a predicate
 847  *        expression for a simple restriction clause.
 848  */
 849 static bool
 850 one_pred_clause_test(Expr *predicate, Node *clause)
 851 {
 852         List       *items,
 853                            *item;
 854
 855         if (is_opclause((Node *) predicate))
 856                 return clause_pred_clause_test(predicate, clause);
 857         else if (or_clause((Node *) predicate))
 858         {
 859                 items = predicate->args;
 860                 foreach(item, items)
 861                 {
 862                         /* if any item is implied, the whole predicate is implied */
 863                         if (one_pred_clause_test(lfirst(item), clause))
 864                                 return true;
 865                 }
 866                 return false;
 867         }
 868         else if (and_clause((Node *) predicate))
 869         {
 870                 items = predicate->args;
 871                 foreach(item, items)
 872                 {
 873
 874                         /*
 875                          * if any item is not implied, the whole predicate is not
 876                          * implied
 877                          */
 878                         if (!one_pred_clause_test(lfirst(item), clause))
 879                                 return false;
 880                 }
 881                 return true;
 882         }
 883         else
 884         {
 885                 elog(DEBUG, "Unsupported predicate type, index will not be used");
 886                 return false;
 887         }
 888 }
 889
 890
 891 /*
 892  * Define an "operator implication table" for btree operators ("strategies").
 893  * The "strategy numbers" are:  (1) <   (2) <=   (3) =   (4) >=   (5) >
 894  *
 895  * The interpretation of:
 896  *
 897  *              test_op = BT_implic_table[given_op-1][target_op-1]
 898  *
 899  * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
 900  * of btree operators, is as follows:
 901  *
 902  *       If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
 903  *       want to determine whether "ATTR target_op CONST2" must also be true, then
 904  *       you can use "CONST1 test_op CONST2" as a test.  If this test returns true,
 905  *       then the target expression must be true; if the test returns false, then
 906  *       the target expression may be false.
 907  *
 908  * An entry where test_op==0 means the implication cannot be determined, i.e.,
 909  * this test should always be considered false.
 910  */
 911
 912 static StrategyNumber
 913 BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
 914         {2, 2, 0, 0, 0},
 915         {1, 2, 0, 0, 0},
 916         {1, 2, 3, 4, 5},
 917         {0, 0, 0, 4, 5},
 918         {0, 0, 0, 4, 4}
 919 };
 920
 921
 922 /*
 923  * clause_pred_clause_test
 924  *        Use operator class info to check whether clause implies predicate.
 925  *
 926  *        Does the "predicate inclusion test" for a "simple clause" predicate
 927  *        for a single "simple clause" restriction.  Currently, this only handles
 928  *        (binary boolean) operators that are in some btree operator class.
 929  *        Eventually, rtree operators could also be handled by defining an
 930  *        appropriate "RT_implic_table" array.
 931  */
 932 static bool
 933 clause_pred_clause_test(Expr *predicate, Node *clause)
 934 {
 935         Var                *pred_var,
 936                            *clause_var;
 937         Const      *pred_const,
 938                            *clause_const;
 939         Oid                     pred_op,
 940                                 clause_op,
 941                                 test_op;
 942         Oid                     opclass_id;
 943         StrategyNumber pred_strategy,
 944                                 clause_strategy,
 945                                 test_strategy;
 946         Oper       *test_oper;
 947         Expr       *test_expr;
 948         bool            test_result,
 949                                 isNull;
 950         Relation        relation;
 951         HeapScanDesc scan;
 952         HeapTuple       tuple;
 953         ScanKeyData entry[3];
 954         Form_pg_amop aform;
 955
 956         pred_var = (Var *) get_leftop(predicate);
 957         pred_const = (Const *) get_rightop(predicate);
 958         clause_var = (Var *) get_leftop((Expr *) clause);
 959         clause_const = (Const *) get_rightop((Expr *) clause);
 960
 961         /* Check the basic form; for now, only allow the simplest case */
 962         if (!is_opclause(clause) ||
 963                 !IsA(clause_var, Var) ||
 964                 clause_const == NULL ||
 965                 !IsA(clause_const, Const) ||
 966                 !IsA(predicate->oper, Oper) ||
 967                 !IsA(pred_var, Var) ||
 968                 !IsA(pred_const, Const))
 969                 return false;
 970
 971         /*
 972          * The implication can't be determined unless the predicate and the
 973          * clause refer to the same attribute.
 974          */
 975         if (clause_var->varattno != pred_var->varattno)
 976                 return false;
 977
 978         /* Get the operators for the two clauses we're comparing */
 979         pred_op = ((Oper *) ((Expr *) predicate)->oper)->opno;
 980         clause_op = ((Oper *) ((Expr *) clause)->oper)->opno;
 981
 982
 983         /*
 984          * 1. Find a "btree" strategy number for the pred_op
 985          */
 986         ScanKeyEntryInitialize(&entry[0], 0,
 987                                                    Anum_pg_amop_amopid,
 988                                                    F_OIDEQ,
 989                                                    ObjectIdGetDatum(BTREE_AM_OID));
 990
 991         ScanKeyEntryInitialize(&entry[1], 0,
 992                                                    Anum_pg_amop_amopopr,
 993                                                    F_OIDEQ,
 994                                                    ObjectIdGetDatum(pred_op));
 995
 996         relation = heap_openr(AccessMethodOperatorRelationName);
 997
 998         /*
 999          * The following assumes that any given operator will only be in a
1000          * single btree operator class.  This is true at least for all the
1001          * pre-defined operator classes.  If it isn't true, then whichever
1002          * operator class happens to be returned first for the given operator
1003          * will be used to find the associated strategy numbers for the test.
1004          * --Nels, Jan '93
1005          */
1006         scan = heap_beginscan(relation, false, SnapshotNow, 2, entry);
1007         tuple = heap_getnext(scan, 0);
1008         if (!HeapTupleIsValid(tuple))
1009         {
1010                 elog(DEBUG, "clause_pred_clause_test: unknown pred_op");
1011                 return false;
1012         }
1013         aform = (Form_pg_amop) GETSTRUCT(tuple);
1014
1015         /* Get the predicate operator's strategy number (1 to 5) */
1016         pred_strategy = (StrategyNumber) aform->amopstrategy;
1017
1018         /* Remember which operator class this strategy number came from */
1019         opclass_id = aform->amopclaid;
1020
1021         heap_endscan(scan);
1022
1023
1024         /*
1025          * 2. From the same opclass, find a strategy num for the clause_op
1026          */
1027         ScanKeyEntryInitialize(&entry[1], 0,
1028                                                    Anum_pg_amop_amopclaid,
1029                                                    F_OIDEQ,
1030                                                    ObjectIdGetDatum(opclass_id));
1031
1032         ScanKeyEntryInitialize(&entry[2], 0,
1033                                                    Anum_pg_amop_amopopr,
1034                                                    F_OIDEQ,
1035                                                    ObjectIdGetDatum(clause_op));
1036
1037         scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
1038         tuple = heap_getnext(scan, 0);
1039         if (!HeapTupleIsValid(tuple))
1040         {
1041                 elog(DEBUG, "clause_pred_clause_test: unknown clause_op");
1042                 return false;
1043         }
1044         aform = (Form_pg_amop) GETSTRUCT(tuple);
1045
1046         /* Get the restriction clause operator's strategy number (1 to 5) */
1047         clause_strategy = (StrategyNumber) aform->amopstrategy;
1048         heap_endscan(scan);
1049
1050
1051         /*
1052          * 3. Look up the "test" strategy number in the implication table
1053          */
1054
1055         test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1056         if (test_strategy == 0)
1057                 return false;                   /* the implication cannot be determined */
1058
1059
1060         /*
1061          * 4. From the same opclass, find the operator for the test strategy
1062          */
1063
1064         ScanKeyEntryInitialize(&entry[2], 0,
1065                                                    Anum_pg_amop_amopstrategy,
1066                                                    F_INT2EQ,
1067                                                    Int16GetDatum(test_strategy));
1068
1069         scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
1070         tuple = heap_getnext(scan, 0);
1071         if (!HeapTupleIsValid(tuple))
1072         {
1073                 elog(DEBUG, "clause_pred_clause_test: unknown test_op");
1074                 return false;
1075         }
1076         aform = (Form_pg_amop) GETSTRUCT(tuple);
1077
1078         /* Get the test operator */
1079         test_op = aform->amopopr;
1080         heap_endscan(scan);
1081
1082
1083         /*
1084          * 5. Evaluate the test
1085          */
1086         test_oper = makeOper(test_op,           /* opno */
1087                                                  InvalidOid,    /* opid */
1088                                                  BOOLOID,               /* opresulttype */
1089                                                  0,             /* opsize */
1090                                                  NULL); /* op_fcache */
1091         replace_opid(test_oper);
1092
1093         test_expr = make_opclause(test_oper,
1094                                                           copyObject(clause_const),
1095                                                           copyObject(pred_const));
1096
1097 #ifndef OMIT_PARTIAL_INDEX
1098         test_result = ExecEvalExpr((Node *) test_expr, NULL, &isNull, NULL);
1099 #endif   /* OMIT_PARTIAL_INDEX */
1100         if (isNull)
1101         {
1102                 elog(DEBUG, "clause_pred_clause_test: null test result");
1103                 return false;
1104         }
1105         return test_result;
1106 }
1107
1108
1109 /****************************************************************************
1110  *                              ----  ROUTINES TO CHECK JOIN CLAUSES  ----
1111  ****************************************************************************/
1112
1113 /*
1114  * indexable_joinclauses
1115  *        Finds all groups of join clauses from among 'joininfo_list' that can
1116  *        be used in conjunction with 'index'.
1117  *
1118  *        Each clause group comes from a single joininfo node plus the current
1119  *        rel's restrictinfo list.  Therefore, every clause in the group references
1120  *        the current rel plus the same set of other rels (except for the restrict
1121  *        clauses, which only reference the current rel).  Therefore, this set
1122  *    of clauses could be used as an indexqual if the relation is scanned
1123  *        as the inner side of a nestloop join when the outer side contains
1124  *        (at least) all those "other rels".
1125  *
1126  *        XXX Actually, given that we are considering a join that requires an
1127  *        outer rel set (A,B,C), we should use all qual clauses that reference
1128  *        any subset of these rels, not just the full set or none.  This is
1129  *        doable with a doubly nested loop over joininfo_list; is it worth it?
1130  *
1131  * Returns two parallel lists of the same length: the clause groups,
1132  * and the required outer rel set for each one.
1133  *
1134  * 'rel' is the relation for which 'index' is defined
1135  * 'joininfo_list' is the list of JoinInfo nodes for 'rel'
1136  * 'restrictinfo_list' is the list of restriction clauses for 'rel'
1137  * '*clausegroups' receives a list of clause sublists
1138  * '*outerrelids' receives a list of relid lists
1139  */
1140 static void
1141 indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index,
1142                                           List *joininfo_list, List *restrictinfo_list,
1143                                           List **clausegroups, List **outerrelids)
1144 {
1145         List       *cg_list = NIL;
1146         List       *relid_list = NIL;
1147         List       *i;
1148
1149         foreach(i, joininfo_list)
1150         {
1151                 JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
1152                 List       *clausegroups;
1153
1154                 if (joininfo->jinfo_restrictinfo == NIL)
1155                         continue;
1156                 clausegroups = group_clauses_by_ikey_for_joins(rel,
1157                                                                                                            index,
1158                                                                                                            index->indexkeys,
1159                                                                                                            index->classlist,
1160                                                                                         joininfo->jinfo_restrictinfo,
1161                                                                                                            restrictinfo_list);
1162
1163                 /*----------
1164                  * This code knows that group_clauses_by_ikey_for_joins() returns
1165                  * either NIL or a list containing a single sublist of clauses.
1166                  * The line
1167                  *              cg_list = nconc(cg_list, clausegroups);
1168                  * is better read as
1169                  *              cg_list = lappend(cg_list, lfirst(clausegroups));
1170                  * That is, we are appending the only sublist returned by
1171                  * group_clauses_by_ikey_for_joins() to the list of clause sublists
1172                  * that this routine will return.  By using nconc() we recycle
1173                  * a cons cell that would be wasted ... whoever wrote this code
1174                  * was too clever by half...
1175                  *----------
1176                  */
1177                 if (clausegroups != NIL)
1178                 {
1179                         cg_list = nconc(cg_list, clausegroups);
1180                         relid_list = lappend(relid_list, joininfo->unjoined_relids);
1181                 }
1182         }
1183
1184         /* Make sure above clever code didn't screw up */
1185         Assert(length(cg_list) == length(relid_list));
1186
1187         *clausegroups = cg_list;
1188         *outerrelids = relid_list;
1189 }
1190
1191 /****************************************************************************
1192  *                              ----  PATH CREATION UTILITIES  ----
1193  ****************************************************************************/
1194
1195 /*
1196  * index_innerjoin
1197  *        Creates index path nodes corresponding to paths to be used as inner
1198  *        relations in nestloop joins.
1199  *
1200  * 'rel' is the relation for which 'index' is defined
1201  * 'clausegroup_list' is a list of lists of restrictinfo nodes which can use
1202  * 'index' on their inner relation.
1203  * 'outerrelids_list' is a list of the required outer rels for each group
1204  * of join clauses.
1205  *
1206  * Returns a list of index pathnodes.
1207  */
1208 static List *
1209 index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index,
1210                                 List *clausegroup_list, List *outerrelids_list)
1211 {
1212         List       *path_list = NIL;
1213         List       *i;
1214
1215         foreach(i, clausegroup_list)
1216         {
1217                 List       *clausegroup = lfirst(i);
1218                 IndexPath  *pathnode = makeNode(IndexPath);
1219                 List       *indexquals;
1220                 float           npages;
1221                 float           selec;
1222
1223                 indexquals = get_actual_clauses(clausegroup);
1224
1225                 index_selectivity(root,
1226                                                   lfirsti(rel->relids),
1227                                                   lfirsti(index->relids),
1228                                                   indexquals,
1229                                                   &npages,
1230                                                   &selec);
1231
1232                 /* XXX this code ought to be merged with create_index_path */
1233
1234                 pathnode->path.pathtype = T_IndexScan;
1235                 pathnode->path.parent = rel;
1236                 pathnode->path.pathorder = makeNode(PathOrder);
1237                 pathnode->path.pathorder->ordtype = SORTOP_ORDER;
1238                 pathnode->path.pathorder->ord.sortop = index->ordering;
1239                 pathnode->path.pathkeys = NIL;
1240
1241                 /* Note that we are making a pathnode for a single-scan indexscan;
1242                  * therefore, both indexid and indexqual should be single-element
1243                  * lists.
1244                  */
1245                 pathnode->indexid = index->relids;
1246                 pathnode->indexkeys = index->indexkeys;
1247                 pathnode->indexqual = lcons(indexquals, NIL);
1248
1249                 /* joinid saves the rels needed on the outer side of the join */
1250                 pathnode->path.joinid = lfirst(outerrelids_list);
1251
1252                 pathnode->path.path_cost = cost_index((Oid) lfirsti(index->relids),
1253                                                                                           (int) npages,
1254                                                                                           selec,
1255                                                                                           rel->pages,
1256                                                                                           rel->tuples,
1257                                                                                           index->pages,
1258                                                                                           index->tuples,
1259                                                                                           true);
1260
1261                 /*
1262                  * copy restrictinfo list into path for expensive function
1263                  * processing -- JMH, 7/7/92
1264                  */
1265                 pathnode->path.loc_restrictinfo = set_difference(copyObject((Node *) rel->restrictinfo),
1266                                                                                                                  clausegroup);
1267
1268 #ifdef NOT_USED                                 /* fix xfunc */
1269                 /* add in cost for expensive functions!  -- JMH, 7/7/92 */
1270                 if (XfuncMode != XFUNC_OFF)
1271                         ((Path *) pathnode)->path_cost += xfunc_get_path_cost((Path *) pathnode);
1272 #endif
1273                 path_list = lappend(path_list, pathnode);
1274                 outerrelids_list = lnext(outerrelids_list);
1275         }
1276         return path_list;
1277 }
1278
1279 /*
1280  * create_index_path_group
1281  *        Creates a list of index path nodes for each group of clauses
1282  *        (restriction or join) that can be used in conjunction with an index.
1283  *
1284  * 'rel' is the relation for which 'index' is defined
1285  * 'clausegroup_list' is the list of clause groups (lists of restrictinfo
1286  *                              nodes) grouped by mergejoinorder
1287  * 'join' is a flag indicating whether or not the clauses are join
1288  *                              clauses
1289  *
1290  * Returns a list of new index path nodes.
1291  *
1292  */
1293 static List *
1294 create_index_path_group(Query *root,
1295                                                 RelOptInfo *rel,
1296                                                 RelOptInfo *index,
1297                                                 List *clausegroup_list,
1298                                                 bool join)
1299 {
1300         List       *path_list = NIL;
1301         List       *i;
1302
1303         foreach(i, clausegroup_list)
1304         {
1305                 List       *clausegroup = lfirst(i);
1306                 bool            usable = true;
1307
1308                 if (join)
1309                 {
1310                         List       *j;
1311
1312                         foreach(j, clausegroup)
1313                         {
1314                                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1315                                 if (!(is_joinable((Node *) restrictinfo->clause) &&
1316                                           equal_path_merge_ordering(index->ordering,
1317                                                                                                 restrictinfo->mergejoinorder)))
1318                                 {
1319                                         usable = false;
1320                                         break;
1321                                 }
1322                         }
1323                 }
1324
1325                 if (usable)
1326                 {
1327                         path_list = lappend(path_list,
1328                                                                 create_index_path(root, rel, index,
1329                                                                                                   clausegroup, join));
1330                 }
1331         }
1332         return path_list;
1333 }
1334
1335 /****************************************************************************
1336  *                              ----  ROUTINES TO CHECK OPERANDS  ----
1337  ****************************************************************************/
1338
1339 /*
1340  * match_index_to_operand()
1341  *        Generalized test for a match between an index's key
1342  *        and the operand on one side of a restriction or join clause.
1343  *    Now check for functional indices as well.
1344  */
1345 static bool
1346 match_index_to_operand(int indexkey,
1347                                            Expr *operand,
1348                                            RelOptInfo *rel,
1349                                            RelOptInfo *index)
1350 {
1351         if (index->indproc == InvalidOid)
1352         {
1353                 /*
1354                  * Normal index.
1355                  */
1356                 return match_indexkey_operand(indexkey, (Var *) operand, rel);
1357         }
1358
1359         /*
1360          * functional index check
1361          */
1362         return function_index_operand(operand, rel, index);
1363 }
1364
1365 static bool
1366 function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index)
1367 {
1368         Oid                     heapRelid = (Oid) lfirsti(rel->relids);
1369         Func       *function;
1370         List       *funcargs;
1371         int                *indexKeys = index->indexkeys;
1372         List       *arg;
1373         int                     i;
1374
1375         /*
1376          * sanity check, make sure we know what we're dealing with here.
1377          */
1378         if (funcOpnd == NULL ||
1379                 nodeTag(funcOpnd) != T_Expr || funcOpnd->opType != FUNC_EXPR ||
1380                 funcOpnd->oper == NULL || indexKeys == NULL)
1381                 return false;
1382
1383         function = (Func *) funcOpnd->oper;
1384         funcargs = funcOpnd->args;
1385
1386         if (function->funcid != index->indproc)
1387                 return false;
1388
1389         /*
1390          * Check that the arguments correspond to the same arguments used to
1391          * create the functional index.  To do this we must check that 1.
1392          * refer to the right relatiion. 2. the args have the right attr.
1393          * numbers in the right order.
1394          *
1395          * Check all args refer to the correct relation (i.e. the one with the
1396          * functional index defined on it (rel).  To do this we can simply
1397          * compare range table entry numbers, they must be the same.
1398          */
1399         foreach(arg, funcargs)
1400         {
1401                 if (heapRelid != ((Var *) lfirst(arg))->varno)
1402                         return false;
1403         }
1404
1405         /*
1406          * check attr numbers and order.
1407          */
1408         i = 0;
1409         foreach(arg, funcargs)
1410         {
1411                 if (indexKeys[i] == 0)
1412                         return false;
1413
1414                 if (((Var *) lfirst(arg))->varattno != indexKeys[i])
1415                         return false;
1416
1417                 i++;
1418         }
1419
1420         return true;
1421 }