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.51 1999/02/18 00:49:18 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_path_group(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 create_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_path_group(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                         joinpaths = create_index_path_group(root, rel,
 174                                                                                    index,
 175                                                                                    joinclausegroups,
 176                                                                                    true);
 177                         rel->innerjoin = nconc(rel->innerjoin,
 178                                                                    index_innerjoin(root, rel,
 179                                                                                                    joinclausegroups, index));
 180                 }
 181
 182                 /*
 183                  * Some sanity checks to make sure that the indexpath is valid.
 184                  */
 185                 if (joinpaths != NULL)
 186                         retval = add_index_paths(joinpaths, retval);
 187                 if (scanpaths != NULL)
 188                         retval = add_index_paths(scanpaths, retval);
 189         }
 190
 191         return retval;
 192
 193 }
 194
 195
 196 /****************************************************************************
 197  *              ----  ROUTINES TO MATCH 'OR' CLAUSES  ----
 198  ****************************************************************************/
 199
 200
 201 /*
 202  * match_index_orclauses
 203  *        Attempt to match an index against subclauses within 'or' clauses.
 204  *        If the index does match, then the clause is marked with information
 205  *        about the index.
 206  *
 207  *        Essentially, this adds 'index' to the list of indices in the
 208  *        RestrictInfo field of each of the clauses which it matches.
 209  *
 210  * 'rel' is the node of the relation on which the index is defined.
 211  * 'index' is the index node.
 212  * 'indexkey' is the (single) key of the index
 213  * 'class' is the class of the operator corresponding to 'indexkey'.
 214  * 'restrictinfo_list' is the list of available restriction clauses.
 215  *
 216  * Returns nothing.
 217  *
 218  */
 219 static void
 220 match_index_orclauses(RelOptInfo *rel,
 221                                           RelOptInfo *index,
 222                                           int indexkey,
 223                                           int xclass,
 224                                           List *restrictinfo_list)
 225 {
 226         RestrictInfo *restrictinfo = (RestrictInfo *) NULL;
 227         List       *i = NIL;
 228
 229         foreach(i, restrictinfo_list)
 230         {
 231                 restrictinfo = (RestrictInfo *) lfirst(i);
 232                 if (valid_or_clause(restrictinfo))
 233                 {
 234
 235                         /*
 236                          * Mark the 'or' clause with a list of indices which match
 237                          * each of its subclauses.      The list is generated by adding
 238                          * 'index' to the existing list where appropriate.
 239                          */
 240                         restrictinfo->indexids = match_index_orclause(rel, index, indexkey,
 241                                                                          xclass,
 242                                                                          restrictinfo->clause->args,
 243                                                                          restrictinfo->indexids);
 244                 }
 245         }
 246 }
 247
 248 /* match_index_to_operand()
 249  *        Generalize test for a match between an existing index's key
 250  *        and the operand on the rhs of a restriction clause.  Now check
 251  *        for functional indices as well.
 252  */
 253 static bool
 254 match_index_to_operand(int indexkey,
 255                                            Expr *operand,
 256                                            RelOptInfo *rel,
 257                                            RelOptInfo *index)
 258 {
 259         bool            result;
 260
 261         /*
 262          * Normal index.
 263          */
 264         if (index->indproc == InvalidOid)
 265         {
 266                 result = match_indexkey_operand(indexkey, (Var *) operand, rel);
 267                 return result;
 268         }
 269
 270         /*
 271          * functional index check
 272          */
 273         result = function_index_operand(operand, rel, index);
 274         return result;
 275 }
 276
 277 /*
 278  * match_index_orclause
 279  *        Attempts to match an index against the subclauses of an 'or' clause.
 280  *
 281  *        A match means that:
 282  *        (1) the operator within the subclause can be used with one
 283  *                              of the index's operator classes, and
 284  *        (2) there is a usable key that matches the variable within a
 285  *                              searchable clause.
 286  *
 287  * 'or_clauses' are the remaining subclauses within the 'or' clause
 288  * 'other_matching_indices' is the list of information on other indices
 289  *              that have already been matched to subclauses within this
 290  *              particular 'or' clause (i.e., a list previously generated by
 291  *              this routine)
 292  *
 293  * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where
 294  * a,b,c are nodes of indices that match the first subclause in
 295  * 'or-clauses', d,e,f match the second subclause, no indices
 296  * match the third, g,h match the fourth, etc.
 297  */
 298 static List *
 299 match_index_orclause(RelOptInfo *rel,
 300                                          RelOptInfo *index,
 301                                          int indexkey,
 302                                          int xclass,
 303                                          List *or_clauses,
 304                                          List *other_matching_indices)
 305 {
 306         Node       *clause = NULL;
 307         List       *matching_indices = other_matching_indices;
 308         List       *index_list = NIL;
 309         List       *clist;
 310
 311         /* first time through, we create index list */
 312         if (!other_matching_indices)
 313         {
 314                 foreach(clist, or_clauses)
 315                         matching_indices = lcons(NIL, matching_indices);
 316         }
 317         else
 318                 matching_indices = other_matching_indices;
 319
 320         index_list = matching_indices;
 321
 322         foreach(clist, or_clauses)
 323         {
 324                 clause = lfirst(clist);
 325
 326                 if (is_opclause(clause))
 327                 {
 328                         Expr   *left = (Expr *) get_leftop((Expr *) clause);
 329                         Expr   *right = (Expr *) get_rightop((Expr *) clause);
 330                         if (left && right &&
 331                                 op_class(((Oper *) ((Expr *) clause)->oper)->opno,
 332                                                  xclass, index->relam) &&
 333                                 ((IsA(right, Const) &&
 334                                   match_index_to_operand(indexkey, left, rel, index)) ||
 335                                  (IsA(left, Const) &&
 336                                   match_index_to_operand(indexkey, right, rel, index))))
 337                                 lfirst(matching_indices) = lcons(index,
 338                                                                                                  lfirst(matching_indices));
 339                 }
 340
 341                 matching_indices = lnext(matching_indices);
 342         }
 343
 344         return index_list;
 345 }
 346
 347 /****************************************************************************
 348  *                              ----  ROUTINES TO CHECK RESTRICTIONS  ----
 349  ****************************************************************************/
 350
 351
 352 /*
 353  * DoneMatchingIndexKeys() - MACRO
 354  *
 355  * Determine whether we should continue matching index keys in a clause.
 356  * Depends on if there are more to match or if this is a functional index.
 357  * In the latter case we stop after the first match since the there can
 358  * be only key (i.e. the function's return value) and the attributes in
 359  * keys list represent the arguments to the function.  -mer 3 Oct. 1991
 360  */
 361 #define DoneMatchingIndexKeys(indexkeys, index) \
 362                 (indexkeys[0] == 0 || \
 363                  (index->indproc != InvalidOid))
 364
 365 /*
 366  * group_clauses_by_indexkey
 367  *        Determines whether there are clauses which will match each and every
 368  *        one of the remaining keys of an index.
 369  *
 370  * 'rel' is the node of the relation corresponding to the index.
 371  * 'indexkeys' are the remaining index keys to be matched.
 372  * 'classes' are the classes of the index operators on those keys.
 373  * 'clauses' is either:
 374  *              (1) the list of available restriction clauses on a single
 375  *                              relation, or
 376  *              (2) a list of join clauses between 'rel' and a fixed set of
 377  *                              relations,
 378  *              depending on the value of 'join'.
 379  *
 380  *              NOTE: it works now for restriction clauses only. - vadim 03/18/97
 381  *
 382  * Returns all possible groups of clauses that will match (given that
 383  * one or more clauses can match any of the remaining keys).
 384  * E.g., if you have clauses A, B, and C, ((A B) (A C)) might be
 385  * returned for an index with 2 keys.
 386  *
 387  */
 388 static List *
 389 group_clauses_by_indexkey(RelOptInfo *rel,
 390                                                   RelOptInfo *index,
 391                                                   int *indexkeys,
 392                                                   Oid *classes,
 393                                                   List *restrictinfo_list)
 394 {
 395         List       *curCinfo = NIL;
 396         RestrictInfo *matched_clause = (RestrictInfo *) NULL;
 397         List       *clausegroup = NIL;
 398         int                     curIndxKey;
 399         Oid                     curClass;
 400
 401         if (restrictinfo_list == NIL || indexkeys[0] == 0)
 402                 return NIL;
 403
 404         do
 405         {
 406                 List       *tempgroup = NIL;
 407
 408                 curIndxKey = indexkeys[0];
 409                 curClass = classes[0];
 410
 411                 foreach(curCinfo, restrictinfo_list)
 412                 {
 413                         RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo);
 414
 415                         matched_clause = match_clause_to_indexkey(rel,
 416                                                                                                           index,
 417                                                                                                           curIndxKey,
 418                                                                                                           curClass,
 419                                                                                                           temp,
 420                                                                                                           false);
 421                         if (!matched_clause)
 422                                 continue;
 423
 424                         tempgroup = lappend(tempgroup, matched_clause);
 425                 }
 426                 if (tempgroup == NIL)
 427                         break;
 428
 429                 clausegroup = nconc(clausegroup, tempgroup);
 430
 431                 indexkeys++;
 432                 classes++;
 433
 434         } while (!DoneMatchingIndexKeys(indexkeys, index));
 435
 436         /* clausegroup holds all matched clauses ordered by indexkeys */
 437
 438         if (clausegroup != NIL)
 439                 return lcons(clausegroup, NIL);
 440         return NIL;
 441 }
 442
 443 /*
 444  * group_clauses_by_ikey_for_joins
 445  *        special edition of group_clauses_by_indexkey - will
 446  *        match join & restriction clauses. See comment in indexable_joinclauses.
 447  *              - vadim 03/18/97
 448  *
 449  */
 450 static List *
 451 group_clauses_by_ikey_for_joins(RelOptInfo *rel,
 452                                                                 RelOptInfo *index,
 453                                                                 int *indexkeys,
 454                                                                 Oid *classes,
 455                                                                 List *join_cinfo_list,
 456                                                                 List *restr_cinfo_list)
 457 {
 458         List       *curCinfo = NIL;
 459         RestrictInfo *matched_clause = (RestrictInfo *) NULL;
 460         List       *clausegroup = NIL;
 461         int                     curIndxKey;
 462         Oid                     curClass;
 463         bool            jfound = false;
 464
 465         if (join_cinfo_list == NIL || indexkeys[0] == 0)
 466                 return NIL;
 467
 468         do
 469         {
 470                 List       *tempgroup = NIL;
 471
 472                 curIndxKey = indexkeys[0];
 473                 curClass = classes[0];
 474
 475                 foreach(curCinfo, join_cinfo_list)
 476                 {
 477                         RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo);
 478
 479                         matched_clause = match_clause_to_indexkey(rel,
 480                                                                                                           index,
 481                                                                                                           curIndxKey,
 482                                                                                                           curClass,
 483                                                                                                           temp,
 484                                                                                                           true);
 485                         if (!matched_clause)
 486                                 continue;
 487
 488                         tempgroup = lappend(tempgroup, matched_clause);
 489                         jfound = true;
 490                 }
 491                 foreach(curCinfo, restr_cinfo_list)
 492                 {
 493                         RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo);
 494
 495                         matched_clause = match_clause_to_indexkey(rel,
 496                                                                                                           index,
 497                                                                                                           curIndxKey,
 498                                                                                                           curClass,
 499                                                                                                           temp,
 500                                                                                                           false);
 501                         if (!matched_clause)
 502                                 continue;
 503
 504                         tempgroup = lappend(tempgroup, matched_clause);
 505                 }
 506                 if (tempgroup == NIL)
 507                         break;
 508
 509                 clausegroup = nconc(clausegroup, tempgroup);
 510
 511                 indexkeys++;
 512                 classes++;
 513
 514         } while (!DoneMatchingIndexKeys(indexkeys, index));
 515
 516         /* clausegroup holds all matched clauses ordered by indexkeys */
 517
 518         if (clausegroup != NIL)
 519         {
 520
 521                 /*
 522                  * if no one join clause was matched then there ain't clauses for
 523                  * joins at all.
 524                  */
 525                 if (!jfound)
 526                 {
 527                         freeList(clausegroup);
 528                         return NIL;
 529                 }
 530                 return lcons(clausegroup, NIL);
 531         }
 532         return NIL;
 533 }
 534
 535 /*
 536  * IndexScanableClause ()  MACRO
 537  *
 538  * Generalize condition on which we match a clause with an index.
 539  * Now we can match with functional indices.
 540  */
 541 #define IndexScanableOperand(opnd, indkeys, rel, index) \
 542         ((index->indproc == InvalidOid) ? \
 543                 match_indexkey_operand(indkeys, opnd, rel) : \
 544                 function_index_operand((Expr*)opnd,rel,index))
 545
 546 /*
 547  * There was
 548  *              equal_indexkey_var(indkeys,opnd) : \
 549  * above, and now
 550  *              match_indexkey_operand(indkeys, opnd, rel) : \
 551  * - vadim 01/22/97
 552  */
 553
 554 /* match_clause_to_indexkey()
 555  *        Finds the first of a relation's available restriction clauses that
 556  *        matches a key of an index.
 557  *
 558  *        To match, the clause must:
 559  *        (1) be in the form (op var const) if the clause is a single-
 560  *                              relation clause, and
 561  *        (2) contain an operator which is in the same class as the index
 562  *                              operator for this key.
 563  *
 564  *        If the clause being matched is a join clause, then 'join' is t.
 565  *
 566  * Returns a single restrictinfo node corresponding to the matching
 567  * clause.
 568  *
 569  * NOTE:  returns nil if clause is an or_clause.
 570  *
 571  */
 572 static RestrictInfo *
 573 match_clause_to_indexkey(RelOptInfo *rel,
 574                                                  RelOptInfo *index,
 575                                                  int indexkey,
 576                                                  int xclass,
 577                                                  RestrictInfo *restrictInfo,
 578                                                  bool join)
 579 {
 580         Expr       *clause = restrictInfo->clause;
 581         Var                *leftop,
 582                            *rightop;
 583         Oid                     join_op = InvalidOid;
 584         Oid                     restrict_op = InvalidOid;
 585         bool            isIndexable = false;
 586
 587         if (or_clause((Node *) clause) ||
 588                 not_clause((Node *) clause) || single_node((Node *) clause))
 589                 return (RestrictInfo *) NULL;
 590
 591         leftop = get_leftop(clause);
 592         rightop = get_rightop(clause);
 593
 594         /*
 595          * If this is not a join clause, check for clauses of the form:
 596          * (operator var/func constant) and (operator constant var/func)
 597          */
 598         if (!join)
 599         {
 600
 601                 /*
 602                  * Check for standard s-argable clause
 603                  */
 604                 if ((rightop && IsA(rightop, Const)) ||
 605                         (rightop && IsA(rightop, Param)))
 606                 {
 607                         restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno;
 608
 609                         isIndexable = (op_class(restrict_op, xclass, index->relam) &&
 610                                                    IndexScanableOperand(leftop,
 611                                                                                                 indexkey,
 612                                                                                                 rel,
 613                                                                                                 index));
 614
 615 #ifndef IGNORE_BINARY_COMPATIBLE_INDICES
 616
 617                         /*
 618                          * Didn't find an index? Then maybe we can find another
 619                          * binary-compatible index instead... thomas 1998-08-14
 620                          */
 621                         if (!isIndexable)
 622                         {
 623                                 Oid                     ltype;
 624                                 Oid                     rtype;
 625
 626                                 ltype = exprType((Node *) leftop);
 627                                 rtype = exprType((Node *) rightop);
 628
 629                                 /*
 630                                  * make sure we have two different binary-compatible
 631                                  * types...
 632                                  */
 633                                 if ((ltype != rtype)
 634                                         && IS_BINARY_COMPATIBLE(ltype, rtype))
 635                                 {
 636                                         char       *opname;
 637                                         Operator        newop;
 638
 639                                         opname = get_opname(restrict_op);
 640                                         if (opname != NULL)
 641                                                 newop = oper(opname, ltype, ltype, TRUE);
 642                                         else
 643                                                 newop = NULL;
 644
 645                                         /* actually have a different operator to try? */
 646                                         if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op))
 647                                         {
 648                                                 restrict_op = oprid(newop);
 649
 650                                                 isIndexable = (op_class(restrict_op, xclass, index->relam) &&
 651                                                          IndexScanableOperand(leftop,
 652                                                                                                   indexkey,
 653                                                                                                   rel,
 654                                                                                                   index));
 655
 656                                                 if (isIndexable)
 657                                                         ((Oper *) ((Expr *) clause)->oper)->opno = restrict_op;
 658                                         }
 659                                 }
 660                         }
 661 #endif
 662                 }
 663
 664                 /*
 665                  * Must try to commute the clause to standard s-arg format.
 666                  */
 667                 else if ((leftop && IsA(leftop, Const)) ||
 668                                  (leftop && IsA(leftop, Param)))
 669                 {
 670                         restrict_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno);
 671
 672                         isIndexable = ((restrict_op != InvalidOid) &&
 673                                                    op_class(restrict_op, xclass, index->relam) &&
 674                                                    IndexScanableOperand(rightop,
 675                                                                                                 indexkey, rel, index));
 676
 677 #ifndef IGNORE_BINARY_COMPATIBLE_INDICES
 678                         if (!isIndexable)
 679                         {
 680                                 Oid                     ltype;
 681                                 Oid                     rtype;
 682
 683                                 ltype = exprType((Node *) leftop);
 684                                 rtype = exprType((Node *) rightop);
 685
 686                                 if ((ltype != rtype)
 687                                         && IS_BINARY_COMPATIBLE(ltype, rtype))
 688                                 {
 689                                         char       *opname;
 690                                         Operator        newop;
 691
 692                                         restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno;
 693
 694                                         opname = get_opname(restrict_op);
 695                                         if (opname != NULL)
 696                                                 newop = oper(opname, rtype, rtype, TRUE);
 697                                         else
 698                                                 newop = NULL;
 699
 700                                         if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op))
 701                                         {
 702                                                 restrict_op = get_commutator(oprid(newop));
 703
 704                                                 isIndexable = ((restrict_op != InvalidOid) &&
 705                                                    op_class(restrict_op, xclass, index->relam) &&
 706                                                                            IndexScanableOperand(rightop,
 707                                                                                                                         indexkey,
 708                                                                                                                         rel,
 709                                                                                                                         index));
 710
 711                                                 if (isIndexable)
 712                                                         ((Oper *) ((Expr *) clause)->oper)->opno = oprid(newop);
 713                                         }
 714                                 }
 715                         }
 716 #endif
 717
 718                         if (isIndexable)
 719                         {
 720
 721                                 /*
 722                                  * In place list modification. (op const var/func) -> (op
 723                                  * var/func const)
 724                                  */
 725                                 CommuteClause((Node *) clause);
 726                         }
 727                 }
 728         }
 729
 730         /*
 731          * Check for an indexable scan on one of the join relations. clause is
 732          * of the form (operator var/func var/func)
 733          */
 734         else
 735         {
 736                 if (rightop
 737                 && match_index_to_operand(indexkey, (Expr *) rightop, rel, index))
 738                 {
 739
 740                         join_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno);
 741
 742                 }
 743                 else if (leftop
 744                                  && match_index_to_operand(indexkey,
 745                                                                                    (Expr *) leftop, rel, index))
 746                         join_op = ((Oper *) ((Expr *) clause)->oper)->opno;
 747
 748                 if (join_op && op_class(join_op, xclass, index->relam) &&
 749                         is_joinable((Node *) clause))
 750                 {
 751                         isIndexable = true;
 752
 753                         /*
 754                          * If we're using the operand's commutator we must commute the
 755                          * clause.
 756                          */
 757                         if (join_op != ((Oper *) ((Expr *) clause)->oper)->opno)
 758                                 CommuteClause((Node *) clause);
 759                 }
 760         }
 761
 762         if (isIndexable)
 763                 return restrictInfo;
 764
 765         return NULL;
 766 }
 767
 768 /****************************************************************************
 769  *                              ----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS      ----
 770  ****************************************************************************/
 771
 772 /*
 773  * pred_test
 774  *        Does the "predicate inclusion test" for partial indexes.
 775  *
 776  *        Recursively checks whether the clauses in restrictinfo_list imply
 777  *        that the given predicate is true.
 778  *
 779  *        This routine (together with the routines it calls) iterates over
 780  *        ANDs in the predicate first, then reduces the qualification
 781  *        clauses down to their constituent terms, and iterates over ORs
 782  *        in the predicate last.  This order is important to make the test
 783  *        succeed whenever possible (assuming the predicate has been
 784  *        successfully cnfify()-ed). --Nels, Jan '93
 785  */
 786 static bool
 787 pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list)
 788 {
 789         List       *pred,
 790                            *items,
 791                            *item;
 792
 793         /*
 794          * Note: if Postgres tried to optimize queries by forming equivalence
 795          * classes over equi-joined attributes (i.e., if it recognized that a
 796          * qualification such as "where a.b=c.d and a.b=5" could make use of
 797          * an index on c.d), then we could use that equivalence class info
 798          * here with joininfo_list to do more complete tests for the usability
 799          * of a partial index.  For now, the test only uses restriction
 800          * clauses (those in restrictinfo_list). --Nels, Dec '92
 801          */
 802
 803         if (predicate_list == NULL)
 804                 return true;                    /* no predicate: the index is usable */
 805         if (restrictinfo_list == NULL)
 806                 return false;                   /* no restriction clauses: the test must
 807                                                                  * fail */
 808
 809         foreach(pred, predicate_list)
 810         {
 811
 812                 /*
 813                  * if any clause is not implied, the whole predicate is not
 814                  * implied
 815                  */
 816                 if (and_clause(lfirst(pred)))
 817                 {
 818                         items = ((Expr *) lfirst(pred))->args;
 819                         foreach(item, items)
 820                         {
 821                                 if (!one_pred_test(lfirst(item), restrictinfo_list))
 822                                         return false;
 823                         }
 824                 }
 825                 else if (!one_pred_test(lfirst(pred), restrictinfo_list))
 826                         return false;
 827         }
 828         return true;
 829 }
 830
 831
 832 /*
 833  * one_pred_test
 834  *        Does the "predicate inclusion test" for one conjunct of a predicate
 835  *        expression.
 836  */
 837 static bool
 838 one_pred_test(Expr *predicate, List *restrictinfo_list)
 839 {
 840         RestrictInfo *restrictinfo;
 841         List       *item;
 842
 843         Assert(predicate != NULL);
 844         foreach(item, restrictinfo_list)
 845         {
 846                 restrictinfo = (RestrictInfo *) lfirst(item);
 847                 /* if any clause implies the predicate, return true */
 848                 if (one_pred_clause_expr_test(predicate, (Node *) restrictinfo->clause))
 849                         return true;
 850         }
 851         return false;
 852 }
 853
 854
 855 /*
 856  * one_pred_clause_expr_test
 857  *        Does the "predicate inclusion test" for a general restriction-clause
 858  *        expression.
 859  */
 860 static bool
 861 one_pred_clause_expr_test(Expr *predicate, Node *clause)
 862 {
 863         List       *items,
 864                            *item;
 865
 866         if (is_opclause(clause))
 867                 return one_pred_clause_test(predicate, clause);
 868         else if (or_clause(clause))
 869         {
 870                 items = ((Expr *) clause)->args;
 871                 foreach(item, items)
 872                 {
 873                         /* if any OR item doesn't imply the predicate, clause doesn't */
 874                         if (!one_pred_clause_expr_test(predicate, lfirst(item)))
 875                                 return false;
 876                 }
 877                 return true;
 878         }
 879         else if (and_clause(clause))
 880         {
 881                 items = ((Expr *) clause)->args;
 882                 foreach(item, items)
 883                 {
 884
 885                         /*
 886                          * if any AND item implies the predicate, the whole clause
 887                          * does
 888                          */
 889                         if (one_pred_clause_expr_test(predicate, lfirst(item)))
 890                                 return true;
 891                 }
 892                 return false;
 893         }
 894         else
 895         {
 896                 /* unknown clause type never implies the predicate */
 897                 return false;
 898         }
 899 }
 900
 901
 902 /*
 903  * one_pred_clause_test
 904  *        Does the "predicate inclusion test" for one conjunct of a predicate
 905  *        expression for a simple restriction clause.
 906  */
 907 static bool
 908 one_pred_clause_test(Expr *predicate, Node *clause)
 909 {
 910         List       *items,
 911                            *item;
 912
 913         if (is_opclause((Node *) predicate))
 914                 return clause_pred_clause_test(predicate, clause);
 915         else if (or_clause((Node *) predicate))
 916         {
 917                 items = predicate->args;
 918                 foreach(item, items)
 919                 {
 920                         /* if any item is implied, the whole predicate is implied */
 921                         if (one_pred_clause_test(lfirst(item), clause))
 922                                 return true;
 923                 }
 924                 return false;
 925         }
 926         else if (and_clause((Node *) predicate))
 927         {
 928                 items = predicate->args;
 929                 foreach(item, items)
 930                 {
 931
 932                         /*
 933                          * if any item is not implied, the whole predicate is not
 934                          * implied
 935                          */
 936                         if (!one_pred_clause_test(lfirst(item), clause))
 937                                 return false;
 938                 }
 939                 return true;
 940         }
 941         else
 942         {
 943                 elog(DEBUG, "Unsupported predicate type, index will not be used");
 944                 return false;
 945         }
 946 }
 947
 948
 949 /*
 950  * Define an "operator implication table" for btree operators ("strategies").
 951  * The "strategy numbers" are:  (1) <   (2) <=   (3) =   (4) >=   (5) >
 952  *
 953  * The interpretation of:
 954  *
 955  *              test_op = BT_implic_table[given_op-1][target_op-1]
 956  *
 957  * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
 958  * of btree operators, is as follows:
 959  *
 960  *       If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
 961  *       want to determine whether "ATTR target_op CONST2" must also be true, then
 962  *       you can use "CONST1 test_op CONST2" as a test.  If this test returns true,
 963  *       then the target expression must be true; if the test returns false, then
 964  *       the target expression may be false.
 965  *
 966  * An entry where test_op==0 means the implication cannot be determined, i.e.,
 967  * this test should always be considered false.
 968  */
 969
 970 StrategyNumber BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
 971         {2, 2, 0, 0, 0},
 972         {1, 2, 0, 0, 0},
 973         {1, 2, 3, 4, 5},
 974         {0, 0, 0, 4, 5},
 975         {0, 0, 0, 4, 4}
 976 };
 977
 978
 979 /*
 980  * clause_pred_clause_test
 981  *        Use operator class info to check whether clause implies predicate.
 982  *
 983  *        Does the "predicate inclusion test" for a "simple clause" predicate
 984  *        for a single "simple clause" restriction.  Currently, this only handles
 985  *        (binary boolean) operators that are in some btree operator class.
 986  *        Eventually, rtree operators could also be handled by defining an
 987  *        appropriate "RT_implic_table" array.
 988  */
 989 static bool
 990 clause_pred_clause_test(Expr *predicate, Node *clause)
 991 {
 992         Var                *pred_var,
 993                            *clause_var;
 994         Const      *pred_const,
 995                            *clause_const;
 996         Oid                     pred_op,
 997                                 clause_op,
 998                                 test_op;
 999         Oid                     opclass_id;
1000         StrategyNumber pred_strategy,
1001                                 clause_strategy,
1002                                 test_strategy;
1003         Oper       *test_oper;
1004         Expr       *test_expr;
1005         bool            test_result,
1006                                 isNull;
1007         Relation        relation;
1008         HeapScanDesc scan;
1009         HeapTuple       tuple;
1010         ScanKeyData entry[3];
1011         Form_pg_amop form;
1012
1013         pred_var = (Var *) get_leftop(predicate);
1014         pred_const = (Const *) get_rightop(predicate);
1015         clause_var = (Var *) get_leftop((Expr *) clause);
1016         clause_const = (Const *) get_rightop((Expr *) clause);
1017
1018         /* Check the basic form; for now, only allow the simplest case */
1019         if (!is_opclause(clause) ||
1020                 !IsA(clause_var, Var) ||
1021                 clause_const == NULL ||
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->unjoined_relids;
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.pathorder = makeNode(PathOrder);
1294             pathnode->path.pathorder->ordtype = SORTOP_ORDER;
1295             pathnode->path.pathorder->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_path_group
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_path_group(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                 bool            temp = true;
1363
1364                 clausegroup = lfirst(i);
1365
1366                 foreach(j, clausegroup)
1367                 {
1368                         restrictinfo = (RestrictInfo *) lfirst(j);
1369                         if (!(is_joinable((Node *) restrictinfo->clause) &&
1370                                   equal_path_merge_ordering(index->ordering,
1371                                                                                         restrictinfo->mergejoinorder)))
1372                                 temp = false;
1373                 }
1374
1375                 if (!join || temp)
1376                 {                                               /* restriction, ordering scan */
1377                         temp_path = create_index_path(root, rel, index, clausegroup, join);
1378                         ip_list = lappend(ip_list, temp_path);
1379                 }
1380         }
1381         return ip_list;
1382 }
1383
1384 static List *
1385 add_index_paths(List *indexpaths, List *new_indexpaths)
1386 {
1387         return append(indexpaths, new_indexpaths);
1388 }
1389
1390 static bool
1391 function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index)
1392 {
1393         Oid                     heapRelid = (Oid) lfirsti(rel->relids);
1394         Func       *function;
1395         List       *funcargs;
1396         int                *indexKeys = index->indexkeys;
1397         List       *arg;
1398         int                     i;
1399
1400         /*
1401          * sanity check, make sure we know what we're dealing with here.
1402          */
1403         if (funcOpnd == NULL ||
1404                 nodeTag(funcOpnd) != T_Expr || funcOpnd->opType != FUNC_EXPR ||
1405                 funcOpnd->oper == NULL || indexKeys == NULL)
1406                 return false;
1407
1408         function = (Func *) funcOpnd->oper;
1409         funcargs = funcOpnd->args;
1410
1411         if (function->funcid != index->indproc)
1412                 return false;
1413
1414         /*
1415          * Check that the arguments correspond to the same arguments used to
1416          * create the functional index.  To do this we must check that 1.
1417          * refer to the right relatiion. 2. the args have the right attr.
1418          * numbers in the right order.
1419          *
1420          *
1421          * Check all args refer to the correct relation (i.e. the one with the
1422          * functional index defined on it (rel).  To do this we can simply
1423          * compare range table entry numbers, they must be the same.
1424          */
1425         foreach(arg, funcargs)
1426         {
1427                 if (heapRelid != ((Var *) lfirst(arg))->varno)
1428                         return false;
1429         }
1430
1431         /*
1432          * check attr numbers and order.
1433          */
1434         i = 0;
1435         foreach(arg, funcargs)
1436         {
1437
1438                 if (indexKeys[i] == 0)
1439                         return false;
1440
1441                 if (((Var *) lfirst(arg))->varattno != indexKeys[i])
1442                         return false;
1443
1444                 i++;
1445         }
1446
1447         return true;
1448 }