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