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