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