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.4 1996/11/08 05:56:55 momjian 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 #ifdef INDEXSCAN_PATCH
 497             /* Handle also function parameters.  DZ - 27-8-1996 */
 498             if ((rightop && IsA(rightop,Const)) ||
 499                 (rightop && IsA(rightop,Param)))
 500 #else
 501             if (rightop && IsA(rightop,Const))
 502 #endif
 503                 {
 504                     restrict_op = ((Oper*)((Expr*)clause)->oper)->opno;
 505                     isIndexable =
 506                         ( op_class(restrict_op, xclass, index->relam) &&
 507                          IndexScanableOperand(leftop,
 508                                               indexkey,
 509                                               rel,
 510                                               index) );
 511                 }
 512
 513             /*
 514              * Must try to commute the clause to standard s-arg format.
 515              */
 516             else if (leftop && IsA(leftop,Const))
 517                 {
 518                     restrict_op =
 519                         get_commutator(((Oper*)((Expr*)clause)->oper)->opno);
 520
 521                     if ( (restrict_op != InvalidOid) &&
 522                         op_class(restrict_op, xclass, index->relam) &&
 523                         IndexScanableOperand(rightop,
 524                                              indexkey,rel,index) )
 525                         {
 526                             isIndexable = true;
 527                             /*
 528                              * In place list modification.
 529                              * (op const var/func) -> (op var/func const)
 530                              */
 531                             /* BUG!  Old version:
 532                                CommuteClause(clause, restrict_op);
 533                                */
 534                             CommuteClause((Node*)clause);
 535                         }
 536                 }
 537         }
 538     /*
 539      * Check for an indexable scan on one of the join relations.
 540      * clause is of the form (operator var/func var/func)
 541      */
 542     else
 543         {
 544             if (rightop
 545                 && match_index_to_operand(indexkey,(Expr*)rightop,rel,index)) {
 546
 547                 join_op = get_commutator(((Oper*)((Expr*)clause)->oper)->opno);
 548
 549             } else if (leftop
 550                        && match_index_to_operand(indexkey,
 551                                                  (Expr*)leftop,rel,index)) {
 552                 join_op = ((Oper*)((Expr*)clause)->oper)->opno;
 553             }
 554
 555             if ( join_op && op_class(join_op,xclass,index->relam) &&
 556                 join_clause_p((Node*)clause))
 557                 {
 558                     isIndexable = true;
 559
 560                     /*
 561                      * If we're using the operand's commutator we must
 562                      * commute the clause.
 563                      */
 564                     if (join_op != ((Oper*)((Expr*)clause)->oper)->opno)
 565                         CommuteClause((Node*)clause);
 566                 }
 567         }
 568
 569     if (isIndexable)
 570         return(clauseInfo);
 571
 572     return(NULL);
 573 }
 574
 575 /****************************************************************************
 576  *              ----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS  ----
 577  ****************************************************************************/
 578
 579 /*
 580  * pred_test--
 581  *    Does the "predicate inclusion test" for partial indexes.
 582  *
 583  *    Recursively checks whether the clauses in clauseinfo_list imply
 584  *    that the given predicate is true.
 585  *
 586  *    This routine (together with the routines it calls) iterates over
 587  *    ANDs in the predicate first, then reduces the qualification
 588  *    clauses down to their constituent terms, and iterates over ORs
 589  *    in the predicate last.  This order is important to make the test
 590  *    succeed whenever possible (assuming the predicate has been
 591  *    successfully cnfify()-ed). --Nels, Jan '93
 592  */
 593 static bool
 594 pred_test(List *predicate_list, List *clauseinfo_list, List *joininfo_list)
 595 {
 596     List *pred, *items, *item;
 597
 598     /*
 599      * Note: if Postgres tried to optimize queries by forming equivalence
 600      * classes over equi-joined attributes (i.e., if it recognized that a
 601      * qualification such as "where a.b=c.d and a.b=5" could make use of
 602      * an index on c.d), then we could use that equivalence class info
 603      * here with joininfo_list to do more complete tests for the usability
 604      * of a partial index.  For now, the test only uses restriction
 605      * clauses (those in clauseinfo_list). --Nels, Dec '92
 606      */
 607
 608     if (predicate_list == NULL)
 609         return true;    /* no predicate: the index is usable */
 610     if (clauseinfo_list == NULL)
 611         return false;   /* no restriction clauses: the test must fail */
 612
 613     foreach (pred, predicate_list) {
 614         /* if any clause is not implied, the whole predicate is not implied */
 615         if (and_clause(lfirst(pred))) {
 616             items = ((Expr*)lfirst(pred))->args;
 617             foreach (item, items) {
 618                 if (!one_pred_test(lfirst(item), clauseinfo_list))
 619                     return false;
 620             }
 621         }
 622         else if (!one_pred_test(lfirst(pred), clauseinfo_list))
 623             return false;
 624     }
 625     return true;
 626 }
 627
 628
 629 /*
 630  * one_pred_test--
 631  *    Does the "predicate inclusion test" for one conjunct of a predicate
 632  *    expression.
 633  */
 634 static bool
 635 one_pred_test(Expr *predicate, List *clauseinfo_list)
 636 {
 637     CInfo *clauseinfo;
 638     List *item;
 639
 640     Assert(predicate != NULL);
 641     foreach (item, clauseinfo_list) {
 642         clauseinfo = (CInfo *)lfirst(item);
 643         /* if any clause implies the predicate, return true */
 644         if (one_pred_clause_expr_test(predicate, (Node*)clauseinfo->clause))
 645             return true;
 646     }
 647     return false;
 648 }
 649
 650
 651 /*
 652  * one_pred_clause_expr_test--
 653  *    Does the "predicate inclusion test" for a general restriction-clause
 654  *    expression.
 655  */
 656 static bool
 657 one_pred_clause_expr_test(Expr *predicate, Node *clause)
 658 {
 659     List *items, *item;
 660
 661     if (is_opclause(clause))
 662         return one_pred_clause_test(predicate, clause);
 663     else if (or_clause(clause)) {
 664         items = ((Expr*)clause)->args;
 665         foreach (item, items) {
 666             /* if any OR item doesn't imply the predicate, clause doesn't */
 667             if (!one_pred_clause_expr_test(predicate, lfirst(item)))
 668                 return false;
 669         }
 670         return true;
 671     }else if (and_clause(clause)) {
 672         items = ((Expr*)clause)->args;
 673         foreach (item, items) {
 674             /* if any AND item implies the predicate, the whole clause does */
 675             if (one_pred_clause_expr_test(predicate, lfirst(item)))
 676                 return true;
 677         }
 678         return false;
 679     }else {
 680         /* unknown clause type never implies the predicate */
 681         return false;
 682     }
 683 }
 684
 685
 686 /*
 687  * one_pred_clause_test--
 688  *    Does the "predicate inclusion test" for one conjunct of a predicate
 689  *    expression for a simple restriction clause.
 690  */
 691 static bool
 692 one_pred_clause_test(Expr *predicate, Node *clause)
 693 {
 694     List *items, *item;
 695
 696     if (is_opclause((Node*)predicate))
 697         return clause_pred_clause_test(predicate, clause);
 698     else if (or_clause((Node*)predicate)) {
 699         items = predicate->args;
 700         foreach (item, items) {
 701             /* if any item is implied, the whole predicate is implied */
 702             if (one_pred_clause_test(lfirst(item), clause))
 703                 return true;
 704         }
 705         return false;
 706     }else if (and_clause((Node*)predicate)) {
 707         items = predicate->args;
 708         foreach (item, items) {
 709             /*
 710              * if any item is not implied, the whole predicate is not
 711              * implied
 712              */
 713             if (!one_pred_clause_test(lfirst(item), clause))
 714                 return false;
 715         }
 716         return true;
 717     }
 718     else {
 719         elog(DEBUG, "Unsupported predicate type, index will not be used");
 720         return false;
 721     }
 722 }
 723
 724
 725 /*
 726  * Define an "operator implication table" for btree operators ("strategies").
 727  * The "strategy numbers" are:  (1) <   (2) <=   (3) =   (4) >=   (5) >
 728  *
 729  * The interpretation of:
 730  *
 731  *      test_op = BT_implic_table[given_op-1][target_op-1]
 732  *
 733  * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
 734  * of btree operators, is as follows:
 735  *
 736  *   If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
 737  *   want to determine whether "ATTR target_op CONST2" must also be true, then
 738  *   you can use "CONST1 test_op CONST2" as a test.  If this test returns true,
 739  *   then the target expression must be true; if the test returns false, then
 740  *   the target expression may be false.
 741  *
 742  * An entry where test_op==0 means the implication cannot be determined, i.e.,
 743  * this test should always be considered false.
 744  */
 745
 746 StrategyNumber BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
 747     {2, 2, 0, 0, 0},
 748     {1, 2, 0, 0, 0},
 749     {1, 2, 3, 4, 5},
 750     {0, 0, 0, 4, 5},
 751     {0, 0, 0, 4, 4}
 752 };
 753
 754
 755 /*
 756  * clause_pred_clause_test--
 757  *    Use operator class info to check whether clause implies predicate.
 758  *
 759  *    Does the "predicate inclusion test" for a "simple clause" predicate
 760  *    for a single "simple clause" restriction.  Currently, this only handles
 761  *    (binary boolean) operators that are in some btree operator class.
 762  *    Eventually, rtree operators could also be handled by defining an
 763  *    appropriate "RT_implic_table" array.
 764  */
 765 static bool
 766 clause_pred_clause_test(Expr *predicate, Node *clause)
 767 {
 768     Var         *pred_var, *clause_var;
 769     Const       *pred_const, *clause_const;
 770     Oid         pred_op, clause_op, test_op;
 771     Oid         opclass_id;
 772     StrategyNumber      pred_strategy, clause_strategy, test_strategy;
 773     Oper        *test_oper;
 774     Expr        *test_expr;
 775     bool        test_result, isNull;
 776     Relation    relation;
 777     HeapScanDesc  scan;
 778     HeapTuple   tuple;
 779     ScanKeyData entry[3];
 780     Form_pg_amop form;
 781
 782     pred_var = (Var*)get_leftop(predicate);
 783     pred_const = (Const*)get_rightop(predicate);
 784     clause_var = (Var*)get_leftop((Expr*)clause);
 785     clause_const = (Const*)get_rightop((Expr*)clause);
 786
 787     /* Check the basic form; for now, only allow the simplest case */
 788     if (!is_opclause(clause) ||
 789         !IsA(clause_var,Var) ||
 790         !IsA(clause_const,Const) ||
 791         !IsA(predicate->oper,Oper) ||
 792         !IsA(pred_var,Var) ||
 793         !IsA(pred_const,Const)) {
 794         return false;
 795     }
 796
 797     /*
 798      * The implication can't be determined unless the predicate and the clause
 799      * refer to the same attribute.
 800      */
 801     if (clause_var->varattno != pred_var->varattno)
 802         return false;
 803
 804     /* Get the operators for the two clauses we're comparing */
 805     pred_op = ((Oper*)((Expr*)predicate)->oper)->opno;
 806     clause_op = ((Oper*)((Expr*)clause)->oper)->opno;
 807
 808
 809     /*
 810      * 1. Find a "btree" strategy number for the pred_op
 811      */
 812     /* XXX - hardcoded amopid value 403 to find "btree" operator classes */
 813     ScanKeyEntryInitialize(&entry[0], 0,
 814                            Anum_pg_amop_amopid,
 815                            ObjectIdEqualRegProcedure,
 816                            ObjectIdGetDatum(403));
 817
 818     ScanKeyEntryInitialize(&entry[1], 0,
 819                            Anum_pg_amop_amopopr,
 820                            ObjectIdEqualRegProcedure,
 821                            ObjectIdGetDatum(pred_op));
 822
 823     relation = heap_openr(AccessMethodOperatorRelationName);
 824
 825     /*
 826      * The following assumes that any given operator will only be in a single
 827      * btree operator class.  This is true at least for all the pre-defined
 828      * operator classes.  If it isn't true, then whichever operator class
 829      * happens to be returned first for the given operator will be used to
 830      * find the associated strategy numbers for the test. --Nels, Jan '93
 831      */
 832     scan = heap_beginscan(relation, false, NowTimeQual, 2, entry);
 833     tuple = heap_getnext(scan, false, (Buffer *)NULL);
 834     if (! HeapTupleIsValid(tuple)) {
 835         elog(DEBUG, "clause_pred_clause_test: unknown pred_op");
 836         return false;
 837     }
 838     form = (Form_pg_amop) GETSTRUCT(tuple);
 839
 840     /* Get the predicate operator's strategy number (1 to 5) */
 841     pred_strategy = (StrategyNumber)form->amopstrategy;
 842
 843     /* Remember which operator class this strategy number came from */
 844     opclass_id = form->amopclaid;
 845
 846     heap_endscan(scan);
 847
 848
 849     /*
 850      * 2. From the same opclass, find a strategy num for the clause_op
 851      */
 852     ScanKeyEntryInitialize(&entry[1], 0,
 853                            Anum_pg_amop_amopclaid,
 854                            ObjectIdEqualRegProcedure,
 855                            ObjectIdGetDatum(opclass_id));
 856
 857     ScanKeyEntryInitialize(&entry[2], 0,
 858                            Anum_pg_amop_amopopr,
 859                            ObjectIdEqualRegProcedure,
 860                            ObjectIdGetDatum(clause_op));
 861
 862     scan = heap_beginscan(relation, false, NowTimeQual, 3, entry);
 863     tuple = heap_getnext(scan, false, (Buffer *)NULL);
 864     if (! HeapTupleIsValid(tuple)) {
 865         elog(DEBUG, "clause_pred_clause_test: unknown clause_op");
 866         return false;
 867     }
 868     form = (Form_pg_amop) GETSTRUCT(tuple);
 869
 870     /* Get the restriction clause operator's strategy number (1 to 5) */
 871     clause_strategy = (StrategyNumber)form->amopstrategy;
 872     heap_endscan(scan);
 873
 874
 875     /*
 876      * 3. Look up the "test" strategy number in the implication table
 877      */
 878
 879     test_strategy = BT_implic_table[clause_strategy-1][pred_strategy-1];
 880     if (test_strategy == 0)
 881         return false;           /* the implication cannot be determined */
 882
 883
 884     /*
 885      * 4. From the same opclass, find the operator for the test strategy
 886      */
 887
 888     ScanKeyEntryInitialize(&entry[2], 0,
 889                            Anum_pg_amop_amopstrategy,
 890                            Integer16EqualRegProcedure,
 891                            Int16GetDatum(test_strategy));
 892
 893     scan = heap_beginscan(relation, false, NowTimeQual, 3, entry);
 894     tuple = heap_getnext(scan, false, (Buffer *)NULL);
 895     if (! HeapTupleIsValid(tuple)) {
 896         elog(DEBUG, "clause_pred_clause_test: unknown test_op");
 897         return false;
 898     }
 899     form = (Form_pg_amop) GETSTRUCT(tuple);
 900
 901     /* Get the test operator */
 902     test_op = form->amopopr;
 903     heap_endscan(scan);
 904
 905
 906     /*
 907      * 5. Evaluate the test
 908      */
 909     test_oper = makeOper(test_op, /* opno */
 910                          InvalidOid, /* opid */
 911                          BOOL_TYPEID, /* opresulttype */
 912                          0,     /* opsize */
 913                          NULL); /* op_fcache */
 914     (void) replace_opid(test_oper);
 915
 916     test_expr = make_opclause(test_oper,
 917                               copyObject(clause_const),
 918                               copyObject(pred_const));
 919
 920 #ifndef OMIT_PARTIAL_INDEX
 921     test_result = ExecEvalExpr((Node*)test_expr, NULL, &isNull, NULL);
 922 #endif /* OMIT_PARTIAL_INDEX */
 923     if (isNull) {
 924         elog(DEBUG, "clause_pred_clause_test: null test result");
 925         return false;
 926     }
 927     return test_result;
 928 }
 929
 930
 931 /****************************************************************************
 932  *              ----  ROUTINES TO CHECK JOIN CLAUSES  ----
 933  ****************************************************************************/
 934
 935 /*
 936  * indexable-joinclauses--
 937  *    Finds all groups of join clauses from among 'joininfo-list' that can
 938  *    be used in conjunction with 'index'.
 939  *
 940  *    The first clause in the group is marked as having the other relation
 941  *    in the join clause as its outer join relation.
 942  *
 943  * Returns a list of these clause groups.
 944  *
 945  */
 946 static List *
 947 indexable_joinclauses(Rel *rel, Rel *index, List *joininfo_list)
 948 {
 949     JInfo *joininfo = (JInfo*)NULL;
 950     List *cg_list = NIL;
 951     List *i = NIL;
 952     List *clausegroups = NIL;
 953
 954     foreach(i,joininfo_list) {
 955         joininfo = (JInfo*)lfirst(i);
 956         clausegroups =
 957             group_clauses_by_indexkey (rel,
 958                                        index,
 959                                        index->indexkeys,
 960                                        index->classlist,
 961                                        joininfo->jinfoclauseinfo,
 962                                        true);
 963
 964         if (clausegroups != NIL) {
 965             List *clauses = lfirst(clausegroups);
 966
 967             ((CInfo*)lfirst(clauses))->cinfojoinid =
 968                 joininfo->otherrels;
 969         }
 970         cg_list = nconc(cg_list,clausegroups);
 971     }
 972     return(cg_list);
 973 }
 974
 975 /****************************************************************************
 976  *              ----  PATH CREATION UTILITIES  ----
 977  ****************************************************************************/
 978
 979 /*
 980  * extract_restrict_clauses -
 981  *    the list of clause info contains join clauses and restriction clauses.
 982  *    This routine returns the restriction clauses only.
 983  */
 984 #ifdef NOT_USED
 985 static List *
 986 extract_restrict_clauses(List *clausegroup)
 987 {
 988     List *restrict_cls = NIL;
 989     List *l;
 990
 991     foreach (l, clausegroup) {
 992         CInfo *cinfo = lfirst(l);
 993
 994         if (!join_clause_p((Node*)cinfo->clause)) {
 995             restrict_cls = lappend(restrict_cls, cinfo);
 996         }
 997     }
 998     return restrict_cls;
 999 }
1000 #endif
1001
1002 /*
1003  * index-innerjoin--
1004  *    Creates index path nodes corresponding to paths to be used as inner
1005  *    relations in nestloop joins.
1006  *
1007  * 'clausegroup-list' is a list of list of clauseinfo nodes which can use
1008  * 'index' on their inner relation.
1009  *
1010  * Returns a list of index pathnodes.
1011  *
1012  */
1013 static List *
1014 index_innerjoin(Query *root, Rel *rel, List *clausegroup_list, Rel *index)
1015 {
1016     List *clausegroup = NIL;
1017     List *cg_list = NIL;
1018     List *i = NIL;
1019     IndexPath *pathnode = (IndexPath*)NULL;
1020     Cost        temp_selec;
1021     float       temp_pages;
1022
1023     foreach(i,clausegroup_list) {
1024         List *attnos, *values, *flags;
1025
1026         clausegroup = lfirst(i);
1027         pathnode = makeNode(IndexPath);
1028
1029         get_joinvars(lfirsti(rel->relids),clausegroup,
1030                      &attnos, &values, &flags);
1031         index_selectivity(lfirsti(index->relids),
1032                           index->classlist,
1033                           get_opnos(clausegroup),
1034                           getrelid((int)lfirst(rel->relids),
1035                                    root->rtable),
1036                           attnos,
1037                           values,
1038                           flags,
1039                           length(clausegroup),
1040                           &temp_pages,
1041                           &temp_selec);
1042         pathnode->path.pathtype = T_IndexScan;
1043         pathnode->path.parent = rel;
1044         pathnode->indexid = index->relids;
1045         pathnode->indexqual = clausegroup;
1046
1047         pathnode->path.joinid = ((CInfo*)lfirst(clausegroup))->cinfojoinid;
1048
1049         pathnode->path.path_cost =
1050             cost_index((Oid)lfirst(index->relids),
1051                        (int)temp_pages,
1052                        temp_selec,
1053                        rel->pages,
1054                        rel->tuples,
1055                        index->pages,
1056                        index->tuples,
1057                        true);
1058
1059         /* copy clauseinfo list into path for expensive function processing
1060            -- JMH, 7/7/92 */
1061         pathnode->path.locclauseinfo =
1062             set_difference(copyObject((Node*)rel->clauseinfo),
1063                            clausegroup);
1064
1065 #if 0 /* fix xfunc */
1066         /* add in cost for expensive functions!  -- JMH, 7/7/92 */
1067         if (XfuncMode != XFUNC_OFF) {
1068             ((Path*)pathnode)->path_cost +=
1069                 xfunc_get_path_cost((Path*)pathnode);
1070         }
1071 #endif
1072         cg_list = lappend(cg_list,pathnode);
1073     }
1074     return(cg_list);
1075 }
1076
1077 /*
1078  * create-index-paths--
1079  *    Creates a list of index path nodes for each group of clauses
1080  *    (restriction or join) that can be used in conjunction with an index.
1081  *
1082  * 'rel' is the relation for which 'index' is defined
1083  * 'clausegroup-list' is the list of clause groups (lists of clauseinfo
1084  *              nodes) grouped by mergesortorder
1085  * 'join' is a flag indicating whether or not the clauses are join
1086  *              clauses
1087  *
1088  * Returns a list of new index path nodes.
1089  *
1090  */
1091 static List *
1092 create_index_paths(Query *root,
1093                    Rel *rel,
1094                    Rel *index,
1095                    List *clausegroup_list,
1096                    bool join)
1097 {
1098     List *clausegroup = NIL;
1099     List *ip_list = NIL;
1100     List *i = NIL;
1101     List *j = NIL;
1102     IndexPath  *temp_path;
1103
1104     foreach(i, clausegroup_list) {
1105         CInfo *clauseinfo;
1106         List *temp_node = NIL;
1107         bool temp = true;
1108
1109         clausegroup = lfirst(i);
1110
1111         foreach (j,clausegroup) {
1112             clauseinfo = (CInfo*)lfirst(j);
1113             if (!(join_clause_p((Node*)clauseinfo->clause) &&
1114                   equal_path_merge_ordering(index->ordering,
1115                                             clauseinfo->mergesortorder))) {
1116                 temp = false;
1117             }
1118         }
1119
1120         if (!join || temp) {    /* restriction, ordering scan */
1121             temp_path = create_index_path (root, rel,index,clausegroup,join);
1122             temp_node =
1123                 lcons(temp_path, NIL);
1124             ip_list = nconc(ip_list,temp_node);
1125         }
1126     }
1127     return(ip_list);
1128 }
1129
1130 static List *
1131 add_index_paths(List *indexpaths, List *new_indexpaths)
1132 {
1133     return append(indexpaths, new_indexpaths);
1134 }
1135
1136 static bool
1137 function_index_operand(Expr *funcOpnd, Rel *rel, Rel *index)
1138 {
1139     Oid heapRelid       = (Oid)lfirst(rel->relids);
1140     Func *function;
1141     List *funcargs;
1142     int *indexKeys      = index->indexkeys;
1143     List *arg;
1144     int i;
1145
1146     /*
1147      * sanity check, make sure we know what we're dealing with here.
1148      */
1149     if (funcOpnd==NULL ||
1150         nodeTag(funcOpnd)!=T_Expr || funcOpnd->opType!=FUNC_EXPR ||
1151         funcOpnd->oper==NULL || indexKeys==NULL)
1152         return false;
1153
1154     function = (Func*)funcOpnd->oper;
1155     funcargs = funcOpnd->args;
1156
1157     if (function->funcid != index->indproc)
1158         return false;
1159
1160     /*
1161      * Check that the arguments correspond to the same arguments used
1162      * to create the functional index.  To do this we must check that
1163      * 1. refer to the right relatiion.
1164      * 2. the args have the right attr. numbers in the right order.
1165      *
1166      *
1167      * Check all args refer to the correct relation (i.e. the one with
1168      * the functional index defined on it (rel).  To do this we can
1169      * simply compare range table entry numbers, they must be the same.
1170      */
1171     foreach (arg, funcargs) {
1172         if (heapRelid != ((Var*)lfirst(arg))->varno)
1173             return false;
1174     }
1175
1176     /*
1177      * check attr numbers and order.
1178      */
1179     i = 0;
1180     foreach (arg, funcargs) {
1181
1182         if (indexKeys[i]==0)
1183             return (false);
1184
1185         if (((Var*)lfirst(arg))->varattno != indexKeys[i])
1186             return (false);
1187
1188         i++;
1189     }
1190
1191     return true;
1192 }
1193
1194 static bool
1195 SingleAttributeIndex(Rel *index)
1196 {
1197     /*
1198      * return false for now as I don't know if we support index scans
1199      * on disjunction and the code doesn't work
1200      */
1201     return (false);
1202
1203 #if 0
1204     /*
1205      * Non-functional indices.
1206      */
1207     if (index->indproc == InvalidOid)
1208         return (index->indexkeys[0] != 0 &&
1209                 index->indexkeys[1] == 0);
1210
1211     /*
1212      * We have a functional index which is a single attr index
1213      */
1214     return true;
1215 #endif
1216 }