granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/indxpath.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * indxpath.c
   4  *        Routines to determine which indexes are usable for scanning a
   5  *        given relation, and create Paths accordingly.
   6  *
   7  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.179 2005/04/25 03:58:29 tgl Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17
  18 #include <math.h>
  19
  20 #include "access/nbtree.h"
  21 #include "catalog/pg_amop.h"
  22 #include "catalog/pg_namespace.h"
  23 #include "catalog/pg_opclass.h"
  24 #include "catalog/pg_operator.h"
  25 #include "catalog/pg_proc.h"
  26 #include "catalog/pg_type.h"
  27 #include "executor/executor.h"
  28 #include "nodes/makefuncs.h"
  29 #include "optimizer/clauses.h"
  30 #include "optimizer/cost.h"
  31 #include "optimizer/pathnode.h"
  32 #include "optimizer/paths.h"
  33 #include "optimizer/restrictinfo.h"
  34 #include "optimizer/var.h"
  35 #include "parser/parse_expr.h"
  36 #include "rewrite/rewriteManip.h"
  37 #include "utils/builtins.h"
  38 #include "utils/catcache.h"
  39 #include "utils/lsyscache.h"
  40 #include "utils/pg_locale.h"
  41 #include "utils/selfuncs.h"
  42 #include "utils/syscache.h"
  43
  44
  45 /*
  46  * DoneMatchingIndexKeys() - MACRO
  47  */
  48 #define DoneMatchingIndexKeys(classes)  (classes[0] == InvalidOid)
  49
  50 #define is_indexable_operator(clause,opclass,indexkey_on_left) \
  51         (indexable_operator(clause,opclass,indexkey_on_left) != InvalidOid)
  52
  53 #define IsBooleanOpclass(opclass) \
  54         ((opclass) == BOOL_BTREE_OPS_OID || (opclass) == BOOL_HASH_OPS_OID)
  55
  56
  57 static List *find_usable_indexes(Query *root, RelOptInfo *rel,
  58                                                                  List *clauses, List *outer_clauses,
  59                                                                  bool istoplevel, bool isjoininner,
  60                                                                  Relids outer_relids);
  61 static Path *choose_bitmap_and(Query *root, RelOptInfo *rel, List *paths);
  62 static int      bitmap_path_comparator(const void *a, const void *b);
  63 static Cost bitmap_and_cost_est(Query *root, RelOptInfo *rel, List *paths);
  64 static bool match_clause_to_indexcol(IndexOptInfo *index,
  65                                                  int indexcol, Oid opclass,
  66                                                  RestrictInfo *rinfo,
  67                                                  Relids outer_relids);
  68 static Oid indexable_operator(Expr *clause, Oid opclass,
  69                                    bool indexkey_on_left);
  70 static bool pred_test_recurse(Node *clause, Node *predicate);
  71 static bool pred_test_simple_clause(Expr *predicate, Node *clause);
  72 static Relids indexable_outerrelids(RelOptInfo *rel);
  73 static bool list_matches_any_index(List *clauses, RelOptInfo *rel,
  74                                                                    Relids outer_relids);
  75 static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
  76                                                           Relids outer_relids);
  77 static List *find_clauses_for_join(Query *root, RelOptInfo *rel,
  78                                                                    Relids outer_relids, bool isouterjoin);
  79 static bool match_boolean_index_clause(Node *clause, int indexcol,
  80                                                                            IndexOptInfo *index);
  81 static bool match_special_index_operator(Expr *clause, Oid opclass,
  82                                                          bool indexkey_on_left);
  83 static Expr *expand_boolean_index_clause(Node *clause, int indexcol,
  84                                                                                  IndexOptInfo *index);
  85 static List *expand_indexqual_condition(RestrictInfo *rinfo, Oid opclass);
  86 static List *prefix_quals(Node *leftop, Oid opclass,
  87                          Const *prefix, Pattern_Prefix_Status pstatus);
  88 static List *network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass,
  89                                          Datum rightop);
  90 static Datum string_to_datum(const char *str, Oid datatype);
  91 static Const *string_to_const(const char *str, Oid datatype);
  92
  93
  94 /*
  95  * create_index_paths()
  96  *        Generate all interesting index paths for the given relation.
  97  *        Candidate paths are added to the rel's pathlist (using add_path).
  98  *
  99  * To be considered for an index scan, an index must match one or more
 100  * restriction clauses or join clauses from the query's qual condition,
 101  * or match the query's ORDER BY condition.
 102  *
 103  * There are two basic kinds of index scans.  A "plain" index scan uses
 104  * only restriction clauses (possibly none at all) in its indexqual,
 105  * so it can be applied in any context.  An "innerjoin" index scan uses
 106  * join clauses (plus restriction clauses, if available) in its indexqual.
 107  * Therefore it can only be used as the inner relation of a nestloop
 108  * join against an outer rel that includes all the other rels mentioned
 109  * in its join clauses.  In that context, values for the other rels'
 110  * attributes are available and fixed during any one scan of the indexpath.
 111  *
 112  * An IndexPath is generated and submitted to add_path() for each plain index
 113  * scan this routine deems potentially interesting for the current query.
 114  *
 115  * We also determine the set of other relids that participate in join
 116  * clauses that could be used with each index.  The actually best innerjoin
 117  * path will be generated for each outer relation later on, but knowing the
 118  * set of potential otherrels allows us to identify equivalent outer relations
 119  * and avoid repeated computation.
 120  *
 121  * 'rel' is the relation for which we want to generate index paths
 122  *
 123  * Note: check_partial_indexes() must have been run previously.
 124  */
 125 void
 126 create_index_paths(Query *root, RelOptInfo *rel)
 127 {
 128         List       *indexpaths;
 129         List       *bitindexpaths;
 130         ListCell   *l;
 131
 132         /* Skip the whole mess if no indexes */
 133         if (rel->indexlist == NIL)
 134         {
 135                 rel->index_outer_relids = NULL;
 136                 return;
 137         }
 138
 139         /*
 140          * Examine join clauses to see which ones are potentially usable with
 141          * indexes of this rel, and generate the set of all other relids that
 142          * participate in such join clauses.  We'll use this set later to
 143          * recognize outer rels that are equivalent for joining purposes.
 144          */
 145         rel->index_outer_relids = indexable_outerrelids(rel);
 146
 147         /*
 148          * Find all the index paths that are directly usable for this relation
 149          * (ie, are valid without considering OR or JOIN clauses).
 150          */
 151         indexpaths = find_usable_indexes(root, rel,
 152                                                                          rel->baserestrictinfo, NIL,
 153                                                                          true, false, NULL);
 154
 155         /*
 156          * We can submit them all to add_path.  (This generates access paths for
 157          * plain IndexScan plans.)  However, for the next step we will only want
 158          * the ones that have some selectivity; we must discard anything that was
 159          * generated solely for ordering purposes.
 160          */
 161         bitindexpaths = NIL;
 162         foreach(l, indexpaths)
 163         {
 164                 IndexPath  *ipath = (IndexPath *) lfirst(l);
 165
 166                 add_path(rel, (Path *) ipath);
 167
 168                 if (ipath->indexselectivity < 1.0 &&
 169                         !ScanDirectionIsBackward(ipath->indexscandir))
 170                         bitindexpaths = lappend(bitindexpaths, ipath);
 171         }
 172
 173         /*
 174          * Generate BitmapOrPaths for any suitable OR-clauses present in the
 175          * restriction list.  Add these to bitindexpaths.
 176          */
 177         indexpaths = generate_bitmap_or_paths(root, rel,
 178                                                                                   rel->baserestrictinfo, NIL,
 179                                                                                   false, NULL);
 180         bitindexpaths = list_concat(bitindexpaths, indexpaths);
 181
 182         /*
 183          * If we found anything usable, generate a BitmapHeapPath for the
 184          * most promising combination of bitmap index paths.
 185          */
 186         if (bitindexpaths != NIL)
 187         {
 188                 Path       *bitmapqual;
 189                 BitmapHeapPath *bpath;
 190
 191                 bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
 192                 bpath = create_bitmap_heap_path(root, rel, bitmapqual, false);
 193                 add_path(rel, (Path *) bpath);
 194         }
 195 }
 196
 197
 198 /*----------
 199  * find_usable_indexes
 200  *        Given a list of restriction clauses, find all the potentially usable
 201  *        indexes for the given relation, and return a list of IndexPaths.
 202  *
 203  * The caller actually supplies two lists of restriction clauses: some
 204  * "current" ones and some "outer" ones.  Both lists can be used freely
 205  * to match keys of the index, but an index must use at least one of the
 206  * "current" clauses to be considered usable.  The motivation for this is
 207  * examples like
 208  *              WHERE (x = 42) AND (... OR (y = 52 AND z = 77) OR ....)
 209  * While we are considering the y/z subclause of the OR, we can use "x = 42"
 210  * as one of the available index conditions; but we shouldn't match the
 211  * subclause to any index on x alone, because such a Path would already have
 212  * been generated at the upper level.  So we could use an index on x,y,z
 213  * or an index on x,y for the OR subclause, but not an index on just x.
 214  *
 215  * If istoplevel is true (indicating we are considering the top level of a
 216  * rel's restriction clauses), we will include indexes in the result that
 217  * have an interesting sort order, even if they have no matching restriction
 218  * clauses.
 219  *
 220  * 'rel' is the relation for which we want to generate index paths
 221  * 'clauses' is the current list of clauses (RestrictInfo nodes)
 222  * 'outer_clauses' is the list of additional upper-level clauses
 223  * 'istoplevel' is true if clauses are the rel's top-level restriction list
 224  * 'isjoininner' is true if forming an inner indexscan (so some of the
 225  *              given clauses are join clauses)
 226  * 'outer_relids' identifies the outer side of the join (pass NULL
 227  *              if not isjoininner)
 228  *
 229  * Note: check_partial_indexes() must have been run previously.
 230  *----------
 231  */
 232 static List *
 233 find_usable_indexes(Query *root, RelOptInfo *rel,
 234                                         List *clauses, List *outer_clauses,
 235                                         bool istoplevel, bool isjoininner,
 236                                         Relids outer_relids)
 237 {
 238         List       *result = NIL;
 239         List       *all_clauses = NIL;          /* not computed till needed */
 240         ListCell   *ilist;
 241
 242         foreach(ilist, rel->indexlist)
 243         {
 244                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
 245                 IndexPath  *ipath;
 246                 List       *restrictclauses;
 247                 List       *index_pathkeys;
 248                 List       *useful_pathkeys;
 249                 bool            index_is_ordered;
 250
 251                 /*
 252                  * Ignore partial indexes that do not match the query.  If a partial
 253                  * index is marked predOK then we know it's OK; otherwise, if we
 254                  * are at top level we know it's not OK (since predOK is exactly
 255                  * whether its predicate could be proven from the toplevel clauses).
 256                  * Otherwise, we have to test whether the added clauses are
 257                  * sufficient to imply the predicate.  If so, we could use
 258                  * the index in the current context.
 259                  */
 260                 if (index->indpred != NIL && !index->predOK)
 261                 {
 262                         if (istoplevel)
 263                                 continue;               /* no point in trying to prove it */
 264
 265                         /* Form all_clauses if not done already */
 266                         if (all_clauses == NIL)
 267                                 all_clauses = list_concat(list_copy(clauses),
 268                                                                                   outer_clauses);
 269
 270                         if (!pred_test(index->indpred, all_clauses) ||
 271                                 pred_test(index->indpred, outer_clauses))
 272                                 continue;
 273                 }
 274
 275                 /*
 276                  * 1. Match the index against the available restriction clauses.
 277                  */
 278                 restrictclauses = group_clauses_by_indexkey(index,
 279                                                                                                         clauses,
 280                                                                                                         outer_clauses,
 281                                                                                                         outer_relids);
 282
 283                 /*
 284                  * 2. Compute pathkeys describing index's ordering, if any, then
 285                  * see how many of them are actually useful for this query.  This
 286                  * is not relevant unless we are at top level.
 287                  */
 288                 index_is_ordered = OidIsValid(index->ordering[0]);
 289                 if (istoplevel && index_is_ordered && !isjoininner)
 290                 {
 291                         index_pathkeys = build_index_pathkeys(root, index,
 292                                                                                                   ForwardScanDirection);
 293                         useful_pathkeys = truncate_useless_pathkeys(root, rel,
 294                                                                                                                 index_pathkeys);
 295                 }
 296                 else
 297                         useful_pathkeys = NIL;
 298
 299                 /*
 300                  * 3. Generate an indexscan path if there are relevant restriction
 301                  * clauses OR the index ordering is potentially useful for later
 302                  * merging or final output ordering.
 303                  *
 304                  * If there is a predicate, consider it anyway since the index
 305                  * predicate has already been found to match the query.  The
 306                  * selectivity of the predicate might alone make the index useful.
 307                  *
 308                  * Note: not all index AMs support scans with no restriction clauses.
 309                  * We assume here that the AM does so if and only if it supports
 310                  * ordered scans.  (It would probably be better if there were a
 311                  * specific flag for this in pg_am, but there's not.)
 312                  */
 313                 if (restrictclauses != NIL ||
 314                         useful_pathkeys != NIL ||
 315                         (index->indpred != NIL && index_is_ordered))
 316                 {
 317                         ipath = create_index_path(root, index,
 318                                                                           restrictclauses,
 319                                                                           useful_pathkeys,
 320                                                                           index_is_ordered ?
 321                                                                           ForwardScanDirection :
 322                                                                           NoMovementScanDirection,
 323                                                                           isjoininner);
 324                         result = lappend(result, ipath);
 325                 }
 326
 327                 /*
 328                  * 4. If the index is ordered, a backwards scan might be
 329                  * interesting. Currently this is only possible for a DESC query
 330                  * result ordering.
 331                  */
 332                 if (istoplevel && index_is_ordered && !isjoininner)
 333                 {
 334                         index_pathkeys = build_index_pathkeys(root, index,
 335                                                                                                   BackwardScanDirection);
 336                         useful_pathkeys = truncate_useless_pathkeys(root, rel,
 337                                                                                                                 index_pathkeys);
 338                         if (useful_pathkeys != NIL)
 339                         {
 340                                 ipath = create_index_path(root, index,
 341                                                                                   restrictclauses,
 342                                                                                   useful_pathkeys,
 343                                                                                   BackwardScanDirection,
 344                                                                                   false);
 345                                 result = lappend(result, ipath);
 346                         }
 347                 }
 348         }
 349
 350         return result;
 351 }
 352
 353
 354 /*
 355  * generate_bitmap_or_paths
 356  *              Look through the list of clauses to find OR clauses, and generate
 357  *              a BitmapOrPath for each one we can handle that way.  Return a list
 358  *              of the generated BitmapOrPaths.
 359  *
 360  * outer_clauses is a list of additional clauses that can be assumed true
 361  * for the purpose of generating indexquals, but are not to be searched for
 362  * ORs.  (See find_usable_indexes() for motivation.)
 363  */
 364 List *
 365 generate_bitmap_or_paths(Query *root, RelOptInfo *rel,
 366                                                  List *clauses, List *outer_clauses,
 367                                                  bool isjoininner,
 368                                                  Relids outer_relids)
 369 {
 370         List       *result = NIL;
 371         List       *all_clauses;
 372         ListCell   *l;
 373
 374         /*
 375          * We can use both the current and outer clauses as context for
 376          * find_usable_indexes
 377          */
 378         all_clauses = list_concat(list_copy(clauses), outer_clauses);
 379
 380         foreach(l, clauses)
 381         {
 382                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 383                 List   *pathlist;
 384                 Path   *bitmapqual;
 385                 ListCell *j;
 386
 387                 Assert(IsA(rinfo, RestrictInfo));
 388                 /* Ignore RestrictInfos that aren't ORs */
 389                 if (!restriction_is_or_clause(rinfo))
 390                         continue;
 391
 392                 /*
 393                  * We must be able to match at least one index to each of the arms
 394                  * of the OR, else we can't use it.
 395                  */
 396                 pathlist = NIL;
 397                 foreach(j, ((BoolExpr *) rinfo->orclause)->args)
 398                 {
 399                         Node   *orarg = (Node *) lfirst(j);
 400                         List   *indlist;
 401
 402                         /* OR arguments should be ANDs or sub-RestrictInfos */
 403                         if (and_clause(orarg))
 404                         {
 405                                 List   *andargs = ((BoolExpr *) orarg)->args;
 406
 407                                 indlist = find_usable_indexes(root, rel,
 408                                                                                           andargs,
 409                                                                                           all_clauses,
 410                                                                                           false,
 411                                                                                           isjoininner,
 412                                                                                           outer_relids);
 413                                 /* Recurse in case there are sub-ORs */
 414                                 indlist = list_concat(indlist,
 415                                                                           generate_bitmap_or_paths(root, rel,
 416                                                                                                                            andargs,
 417                                                                                                                            all_clauses,
 418                                                                                                                            isjoininner,
 419                                                                                                                            outer_relids));
 420                         }
 421                         else
 422                         {
 423                                 Assert(IsA(orarg, RestrictInfo));
 424                                 Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
 425                                 indlist = find_usable_indexes(root, rel,
 426                                                                                           list_make1(orarg),
 427                                                                                           all_clauses,
 428                                                                                           false,
 429                                                                                           isjoininner,
 430                                                                                           outer_relids);
 431                         }
 432                         /*
 433                          * If nothing matched this arm, we can't do anything
 434                          * with this OR clause.
 435                          */
 436                         if (indlist == NIL)
 437                         {
 438                                 pathlist = NIL;
 439                                 break;
 440                         }
 441                         /*
 442                          * OK, pick the most promising AND combination,
 443                          * and add it to pathlist.
 444                          */
 445                         bitmapqual = choose_bitmap_and(root, rel, indlist);
 446                         pathlist = lappend(pathlist, bitmapqual);
 447                 }
 448                 /*
 449                  * If we have a match for every arm, then turn them
 450                  * into a BitmapOrPath, and add to result list.
 451                  */
 452                 if (pathlist != NIL)
 453                 {
 454                         bitmapqual = (Path *) create_bitmap_or_path(root, rel, pathlist);
 455                         result = lappend(result, bitmapqual);
 456                 }
 457         }
 458
 459         return result;
 460 }
 461
 462
 463 /*
 464  * choose_bitmap_and
 465  *              Given a nonempty list of bitmap paths, AND them into one path.
 466  *
 467  * This is a nontrivial decision since we can legally use any subset of the
 468  * given path set.  We want to choose a good tradeoff between selectivity
 469  * and cost of computing the bitmap.
 470  *
 471  * The result is either a single one of the inputs, or a BitmapAndPath
 472  * combining multiple inputs.
 473  */
 474 static Path *
 475 choose_bitmap_and(Query *root, RelOptInfo *rel, List *paths)
 476 {
 477         int                     npaths = list_length(paths);
 478         Path      **patharray;
 479         Cost            costsofar;
 480         List       *qualsofar;
 481         ListCell   *lastcell;
 482         int                     i;
 483         ListCell   *l;
 484
 485         Assert(npaths > 0);                                                     /* else caller error */
 486         if (npaths == 1)
 487                 return (Path *) linitial(paths);                /* easy case */
 488
 489         /*
 490          * In theory we should consider every nonempty subset of the given paths.
 491          * In practice that seems like overkill, given the crude nature of the
 492          * estimates, not to mention the possible effects of higher-level AND and
 493          * OR clauses.  As a compromise, we sort the paths by selectivity.
 494          * We always take the first, and sequentially add on paths that result
 495          * in a lower estimated cost.
 496          *
 497          * We also make some effort to detect directly redundant input paths,
 498          * as can happen if there are multiple possibly usable indexes.  For
 499          * this we look only at plain IndexPath inputs, not at sub-OR clauses.
 500          * And we consider an index redundant if all its index conditions were
 501          * already used by earlier indexes.  (We could use pred_test() to have
 502          * a more intelligent, but much more expensive, check --- but in most
 503          * cases simple pointer equality should suffice, since after all the
 504          * index conditions are all coming from the same RestrictInfo lists.)
 505          *
 506          * XXX is there any risk of throwing away a useful partial index here
 507          * because we don't explicitly look at indpred?  At least in simple
 508          * cases, the partial index will sort before competing non-partial
 509          * indexes and so it makes the right choice, but perhaps we need to
 510          * work harder.
 511          */
 512
 513         /* Convert list to array so we can apply qsort */
 514         patharray = (Path **) palloc(npaths * sizeof(Path *));
 515         i = 0;
 516         foreach(l, paths)
 517         {
 518                 patharray[i++] = (Path *) lfirst(l);
 519         }
 520         qsort(patharray, npaths, sizeof(Path *), bitmap_path_comparator);
 521
 522         paths = list_make1(patharray[0]);
 523         costsofar = bitmap_and_cost_est(root, rel, paths);
 524         if (IsA(patharray[0], IndexPath))
 525                 qualsofar = list_copy(((IndexPath *) patharray[0])->indexclauses);
 526         else
 527                 qualsofar = NIL;
 528         lastcell = list_head(paths);            /* for quick deletions */
 529
 530         for (i = 1; i < npaths; i++)
 531         {
 532                 Path   *newpath = patharray[i];
 533                 List   *newqual = NIL;
 534                 Cost    newcost;
 535
 536                 if (IsA(newpath, IndexPath))
 537                 {
 538                         newqual = ((IndexPath *) newpath)->indexclauses;
 539                         if (list_difference_ptr(newqual, qualsofar) == NIL)
 540                                 continue;               /* redundant */
 541                 }
 542
 543                 paths = lappend(paths, newpath);
 544                 newcost = bitmap_and_cost_est(root, rel, paths);
 545                 if (newcost < costsofar)
 546                 {
 547                         costsofar = newcost;
 548                         if (newqual)
 549                                 qualsofar = list_concat(qualsofar, list_copy(newqual));
 550                         lastcell = lnext(lastcell);
 551                 }
 552                 else
 553                 {
 554                         paths = list_delete_cell(paths, lnext(lastcell), lastcell);
 555                 }
 556                 Assert(lnext(lastcell) == NULL);
 557         }
 558
 559         if (list_length(paths) == 1)
 560                 return (Path *) linitial(paths);                /* no need for AND */
 561         return (Path *) create_bitmap_and_path(root, rel, paths);
 562 }
 563
 564 /* qsort comparator to sort in increasing selectivity order */
 565 static int
 566 bitmap_path_comparator(const void *a, const void *b)
 567 {
 568         Path       *pa = *(Path * const *) a;
 569         Path       *pb = *(Path * const *) b;
 570         Cost            acost;
 571         Cost            bcost;
 572         Selectivity     aselec;
 573         Selectivity     bselec;
 574
 575         cost_bitmap_tree_node(pa, &acost, &aselec);
 576         cost_bitmap_tree_node(pb, &bcost, &bselec);
 577
 578         if (aselec < bselec)
 579                 return -1;
 580         if (aselec > bselec)
 581                 return 1;
 582         /* if identical selectivity, sort by cost */
 583         if (acost < bcost)
 584                 return -1;
 585         if (acost > bcost)
 586                 return 1;
 587         return 0;
 588 }
 589
 590 /*
 591  * Estimate the cost of actually executing a BitmapAnd with the given
 592  * inputs.
 593  */
 594 static Cost
 595 bitmap_and_cost_est(Query *root, RelOptInfo *rel, List *paths)
 596 {
 597         BitmapAndPath apath;
 598         Path            bpath;
 599
 600         /* Set up a dummy BitmapAndPath */
 601         apath.path.type = T_BitmapAndPath;
 602         apath.path.parent = rel;
 603         apath.bitmapquals = paths;
 604         cost_bitmap_and_node(&apath, root);
 605
 606         /* Now we can do cost_bitmap_heap_scan */
 607         cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, false);
 608
 609         return bpath.total_cost;
 610 }
 611
 612
 613 /****************************************************************************
 614  *                              ----  ROUTINES TO CHECK RESTRICTIONS  ----
 615  ****************************************************************************/
 616
 617
 618 /*
 619  * group_clauses_by_indexkey
 620  *        Find restriction clauses that can be used with an index.
 621  *
 622  * As explained in the comments for find_usable_indexes(), we can use
 623  * clauses from either of the given lists, but the result is required to
 624  * use at least one clause from the "current clauses" list.  We return
 625  * NIL if we don't find any such clause.
 626  *
 627  * outer_relids determines what Vars will be allowed on the other side
 628  * of a possible index qual; see match_clause_to_indexcol().
 629  *
 630  * Returns a list of sublists of RestrictInfo nodes for clauses that can be
 631  * used with this index.  Each sublist contains clauses that can be used
 632  * with one index key (in no particular order); the top list is ordered by
 633  * index key.  (This is depended on by expand_indexqual_conditions().)
 634  *
 635  * Note that in a multi-key index, we stop if we find a key that cannot be
 636  * used with any clause.  For example, given an index on (A,B,C), we might
 637  * return ((C1 C2) (C3 C4)) if we find that clauses C1 and C2 use column A,
 638  * clauses C3 and C4 use column B, and no clauses use column C.  But if
 639  * no clauses match B we will return ((C1 C2)), whether or not there are
 640  * clauses matching column C, because the executor couldn't use them anyway.
 641  * Therefore, there are no empty sublists in the result.
 642  */
 643 List *
 644 group_clauses_by_indexkey(IndexOptInfo *index,
 645                                                   List *clauses, List *outer_clauses,
 646                                                   Relids outer_relids)
 647 {
 648         List       *clausegroup_list = NIL;
 649         bool            found_clause = false;
 650         int                     indexcol = 0;
 651         Oid                *classes = index->classlist;
 652
 653         if (clauses == NIL)
 654                 return NIL;                             /* cannot succeed */
 655
 656         do
 657         {
 658                 Oid                     curClass = classes[0];
 659                 List       *clausegroup = NIL;
 660                 ListCell   *l;
 661
 662                 /* check the current clauses */
 663                 foreach(l, clauses)
 664                 {
 665                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 666
 667                         Assert(IsA(rinfo, RestrictInfo));
 668                         if (match_clause_to_indexcol(index,
 669                                                                                  indexcol,
 670                                                                                  curClass,
 671                                                                                  rinfo,
 672                                                                                  outer_relids))
 673                         {
 674                                 clausegroup = lappend(clausegroup, rinfo);
 675                                 found_clause = true;
 676                         }
 677                 }
 678
 679                 /* check the outer clauses */
 680                 foreach(l, outer_clauses)
 681                 {
 682                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 683
 684                         Assert(IsA(rinfo, RestrictInfo));
 685                         if (match_clause_to_indexcol(index,
 686                                                                                  indexcol,
 687                                                                                  curClass,
 688                                                                                  rinfo,
 689                                                                                  outer_relids))
 690                                 clausegroup = lappend(clausegroup, rinfo);
 691                 }
 692
 693                 /*
 694                  * If no clauses match this key, we're done; we don't want to look
 695                  * at keys to its right.
 696                  */
 697                 if (clausegroup == NIL)
 698                         break;
 699
 700                 clausegroup_list = lappend(clausegroup_list, clausegroup);
 701
 702                 indexcol++;
 703                 classes++;
 704
 705         } while (!DoneMatchingIndexKeys(classes));
 706
 707         if (!found_clause)
 708                 return NIL;
 709
 710         return clausegroup_list;
 711 }
 712
 713
 714 /*
 715  * match_clause_to_indexcol()
 716  *        Determines whether a restriction clause matches a column of an index.
 717  *
 718  *        To match a normal index, the clause:
 719  *
 720  *        (1)  must be in the form (indexkey op const) or (const op indexkey);
 721  *                 and
 722  *        (2)  must contain an operator which is in the same class as the index
 723  *                 operator for this column, or is a "special" operator as recognized
 724  *                 by match_special_index_operator().
 725  *
 726  *        Our definition of "const" is pretty liberal: we allow Vars belonging
 727  *        to the caller-specified outer_relids relations (which had better not
 728  *        include the relation whose index is being tested).  outer_relids should
 729  *        be NULL when checking simple restriction clauses, and the outer side
 730  *        of the join when building a join inner scan.  Other than that, the
 731  *        only thing we don't like is volatile functions.
 732  *
 733  *        Note: in most cases we already know that the clause as a whole uses
 734  *        vars from the interesting set of relations.  The reason for the
 735  *        outer_relids test is to reject clauses like (a.f1 OP (b.f2 OP a.f3));
 736  *        that's not processable by an indexscan nestloop join on A, whereas
 737  *        (a.f1 OP (b.f2 OP c.f3)) is.
 738  *
 739  *        Presently, the executor can only deal with indexquals that have the
 740  *        indexkey on the left, so we can only use clauses that have the indexkey
 741  *        on the right if we can commute the clause to put the key on the left.
 742  *        We do not actually do the commuting here, but we check whether a
 743  *        suitable commutator operator is available.
 744  *
 745  *        For boolean indexes, it is also possible to match the clause directly
 746  *        to the indexkey; or perhaps the clause is (NOT indexkey).
 747  *
 748  * 'index' is the index of interest.
 749  * 'indexcol' is a column number of 'index' (counting from 0).
 750  * 'opclass' is the corresponding operator class.
 751  * 'rinfo' is the clause to be tested (as a RestrictInfo node).
 752  *
 753  * Returns true if the clause can be used with this index key.
 754  *
 755  * NOTE:  returns false if clause is an OR or AND clause; it is the
 756  * responsibility of higher-level routines to cope with those.
 757  */
 758 static bool
 759 match_clause_to_indexcol(IndexOptInfo *index,
 760                                                  int indexcol,
 761                                                  Oid opclass,
 762                                                  RestrictInfo *rinfo,
 763                                                  Relids outer_relids)
 764 {
 765         Expr       *clause = rinfo->clause;
 766         Node       *leftop,
 767                            *rightop;
 768
 769         /* First check for boolean-index cases. */
 770         if (IsBooleanOpclass(opclass))
 771         {
 772                 if (match_boolean_index_clause((Node *) clause, indexcol, index))
 773                         return true;
 774         }
 775
 776         /* Else clause must be a binary opclause. */
 777         if (!is_opclause(clause))
 778                 return false;
 779         leftop = get_leftop(clause);
 780         rightop = get_rightop(clause);
 781         if (!leftop || !rightop)
 782                 return false;
 783
 784         /*
 785          * Check for clauses of the form: (indexkey operator constant) or
 786          * (constant operator indexkey).  See above notes about const-ness.
 787          */
 788         if (match_index_to_operand(leftop, indexcol, index) &&
 789                 bms_is_subset(rinfo->right_relids, outer_relids) &&
 790                 !contain_volatile_functions(rightop))
 791         {
 792                 if (is_indexable_operator(clause, opclass, true))
 793                         return true;
 794
 795                 /*
 796                  * If we didn't find a member of the index's opclass, see whether
 797                  * it is a "special" indexable operator.
 798                  */
 799                 if (match_special_index_operator(clause, opclass, true))
 800                         return true;
 801                 return false;
 802         }
 803
 804         if (match_index_to_operand(rightop, indexcol, index) &&
 805                 bms_is_subset(rinfo->left_relids, outer_relids) &&
 806                 !contain_volatile_functions(leftop))
 807         {
 808                 if (is_indexable_operator(clause, opclass, false))
 809                         return true;
 810
 811                 /*
 812                  * If we didn't find a member of the index's opclass, see whether
 813                  * it is a "special" indexable operator.
 814                  */
 815                 if (match_special_index_operator(clause, opclass, false))
 816                         return true;
 817                 return false;
 818         }
 819
 820         return false;
 821 }
 822
 823 /*
 824  * indexable_operator
 825  *        Does a binary opclause contain an operator matching the index opclass?
 826  *
 827  * If the indexkey is on the right, what we actually want to know
 828  * is whether the operator has a commutator operator that matches
 829  * the index's opclass.
 830  *
 831  * Returns the OID of the matching operator, or InvalidOid if no match.
 832  * (Formerly, this routine might return a binary-compatible operator
 833  * rather than the original one, but that kluge is history.)
 834  */
 835 static Oid
 836 indexable_operator(Expr *clause, Oid opclass, bool indexkey_on_left)
 837 {
 838         Oid                     expr_op = ((OpExpr *) clause)->opno;
 839         Oid                     commuted_op;
 840
 841         /* Get the commuted operator if necessary */
 842         if (indexkey_on_left)
 843                 commuted_op = expr_op;
 844         else
 845                 commuted_op = get_commutator(expr_op);
 846         if (commuted_op == InvalidOid)
 847                 return InvalidOid;
 848
 849         /* OK if the (commuted) operator is a member of the index's opclass */
 850         if (op_in_opclass(commuted_op, opclass))
 851                 return expr_op;
 852
 853         return InvalidOid;
 854 }
 855
 856 /****************************************************************************
 857  *                              ----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS      ----
 858  ****************************************************************************/
 859
 860 /*
 861  * check_partial_indexes
 862  *              Check each partial index of the relation, and mark it predOK or not
 863  *              depending on whether the predicate is satisfied for this query.
 864  */
 865 void
 866 check_partial_indexes(Query *root, RelOptInfo *rel)
 867 {
 868         List       *restrictinfo_list = rel->baserestrictinfo;
 869         ListCell   *ilist;
 870
 871         foreach(ilist, rel->indexlist)
 872         {
 873                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
 874
 875                 /*
 876                  * If this is a partial index, we can only use it if it passes the
 877                  * predicate test.
 878                  */
 879                 if (index->indpred == NIL)
 880                         continue;                       /* ignore non-partial indexes */
 881
 882                 index->predOK = pred_test(index->indpred, restrictinfo_list);
 883         }
 884 }
 885
 886 /*
 887  * pred_test
 888  *        Does the "predicate inclusion test" for partial indexes.
 889  *
 890  *        Recursively checks whether the clauses in restrictinfo_list imply
 891  *        that the given predicate is true.
 892  *
 893  *        The top-level List structure of each list corresponds to an AND list.
 894  *        We assume that eval_const_expressions() has been applied and so there
 895  *        are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
 896  *        including AND just below the top-level List structure).
 897  *        If this is not true we might fail to prove an implication that is
 898  *        valid, but no worse consequences will ensue.
 899  */
 900 bool
 901 pred_test(List *predicate_list, List *restrictinfo_list)
 902 {
 903         ListCell   *item;
 904
 905         /*
 906          * Note: if Postgres tried to optimize queries by forming equivalence
 907          * classes over equi-joined attributes (i.e., if it recognized that a
 908          * qualification such as "where a.b=c.d and a.b=5" could make use of
 909          * an index on c.d), then we could use that equivalence class info
 910          * here with joininfo_list to do more complete tests for the usability
 911          * of a partial index.  For now, the test only uses restriction
 912          * clauses (those in restrictinfo_list). --Nels, Dec '92
 913          *
 914          * XXX as of 7.1, equivalence class info *is* available.  Consider
 915          * improving this code as foreseen by Nels.
 916          */
 917
 918         if (predicate_list == NIL)
 919                 return true;                    /* no predicate: the index is usable */
 920         if (restrictinfo_list == NIL)
 921                 return false;                   /* no restriction clauses: the test must
 922                                                                  * fail */
 923
 924         /*
 925          * In all cases where the predicate is an AND-clause, pred_test_recurse()
 926          * will prefer to iterate over the predicate's components.  So we can
 927          * just do that to start with here, and eliminate the need for
 928          * pred_test_recurse() to handle a bare List on the predicate side.
 929          *
 930          * Logic is: restriction must imply each of the AND'ed predicate items.
 931          */
 932         foreach(item, predicate_list)
 933         {
 934                 if (!pred_test_recurse((Node *) restrictinfo_list, lfirst(item)))
 935                         return false;
 936         }
 937         return true;
 938 }
 939
 940
 941 /*----------
 942  * pred_test_recurse
 943  *        Does the "predicate inclusion test" for non-NULL restriction and
 944  *        predicate clauses.
 945  *
 946  * The logic followed here is ("=>" means "implies"):
 947  *      atom A => atom B iff:                   pred_test_simple_clause says so
 948  *      atom A => AND-expr B iff:               A => each of B's components
 949  *      atom A => OR-expr B iff:                A => any of B's components
 950  *      AND-expr A => atom B iff:               any of A's components => B
 951  *      AND-expr A => AND-expr B iff:   A => each of B's components
 952  *      AND-expr A => OR-expr B iff:    A => any of B's components,
 953  *                                                                      *or* any of A's components => B
 954  *      OR-expr A => atom B iff:                each of A's components => B
 955  *      OR-expr A => AND-expr B iff:    A => each of B's components
 956  *      OR-expr A => OR-expr B iff:             each of A's components => any of B's
 957  *
 958  * An "atom" is anything other than an AND or OR node.  Notice that we don't
 959  * have any special logic to handle NOT nodes; these should have been pushed
 960  * down or eliminated where feasible by prepqual.c.
 961  *
 962  * We can't recursively expand either side first, but have to interleave
 963  * the expansions per the above rules, to be sure we handle all of these
 964  * examples:
 965  *              (x OR y) => (x OR y OR z)
 966  *              (x AND y AND z) => (x AND y)
 967  *              (x AND y) => ((x AND y) OR z)
 968  *              ((x OR y) AND z) => (x OR y)
 969  * This is still not an exhaustive test, but it handles most normal cases
 970  * under the assumption that both inputs have been AND/OR flattened.
 971  *
 972  * A bare List node on the restriction side is interpreted as an AND clause,
 973  * in order to handle the top-level restriction List properly.  However we
 974  * need not consider a List on the predicate side since pred_test() already
 975  * expanded it.
 976  *
 977  * We have to be prepared to handle RestrictInfo nodes in the restrictinfo
 978  * tree, though not in the predicate tree.
 979  *----------
 980  */
 981 static bool
 982 pred_test_recurse(Node *clause, Node *predicate)
 983 {
 984         ListCell   *item;
 985
 986         Assert(clause != NULL);
 987         /* skip through RestrictInfo */
 988         if (IsA(clause, RestrictInfo))
 989         {
 990                 clause = (Node *) ((RestrictInfo *) clause)->clause;
 991                 Assert(clause != NULL);
 992                 Assert(!IsA(clause, RestrictInfo));
 993         }
 994         Assert(predicate != NULL);
 995
 996         /*
 997          * Since a restriction List clause is handled the same as an AND clause,
 998          * we can avoid duplicate code like this:
 999          */
1000         if (and_clause(clause))
1001                 clause = (Node *) ((BoolExpr *) clause)->args;
1002
1003         if (IsA(clause, List))
1004         {
1005                 if (and_clause(predicate))
1006                 {
1007                         /* AND-clause => AND-clause if A implies each of B's items */
1008                         foreach(item, ((BoolExpr *) predicate)->args)
1009                         {
1010                                 if (!pred_test_recurse(clause, lfirst(item)))
1011                                         return false;
1012                         }
1013                         return true;
1014                 }
1015                 else if (or_clause(predicate))
1016                 {
1017                         /* AND-clause => OR-clause if A implies any of B's items */
1018                         /* Needed to handle (x AND y) => ((x AND y) OR z) */
1019                         foreach(item, ((BoolExpr *) predicate)->args)
1020                         {
1021                                 if (pred_test_recurse(clause, lfirst(item)))
1022                                         return true;
1023                         }
1024                         /* Also check if any of A's items implies B */
1025                         /* Needed to handle ((x OR y) AND z) => (x OR y) */
1026                         foreach(item, (List *) clause)
1027                         {
1028                                 if (pred_test_recurse(lfirst(item), predicate))
1029                                         return true;
1030                         }
1031                         return false;
1032                 }
1033                 else
1034                 {
1035                         /* AND-clause => atom if any of A's items implies B */
1036                         foreach(item, (List *) clause)
1037                         {
1038                                 if (pred_test_recurse(lfirst(item), predicate))
1039                                         return true;
1040                         }
1041                         return false;
1042                 }
1043         }
1044         else if (or_clause(clause))
1045         {
1046                 if (or_clause(predicate))
1047                 {
1048                         /*
1049                          * OR-clause => OR-clause if each of A's items implies any of
1050                          * B's items.  Messy but can't do it any more simply.
1051                          */
1052                         foreach(item, ((BoolExpr *) clause)->args)
1053                         {
1054                                 Node       *citem = lfirst(item);
1055                                 ListCell   *item2;
1056
1057                                 foreach(item2, ((BoolExpr *) predicate)->args)
1058                                 {
1059                                         if (pred_test_recurse(citem, lfirst(item2)))
1060                                                 break;
1061                                 }
1062                                 if (item2 == NULL)
1063                                         return false; /* doesn't imply any of B's */
1064                         }
1065                         return true;
1066                 }
1067                 else
1068                 {
1069                         /* OR-clause => AND-clause if each of A's items implies B */
1070                         /* OR-clause => atom if each of A's items implies B */
1071                         foreach(item, ((BoolExpr *) clause)->args)
1072                         {
1073                                 if (!pred_test_recurse(lfirst(item), predicate))
1074                                         return false;
1075                         }
1076                         return true;
1077                 }
1078         }
1079         else
1080         {
1081                 if (and_clause(predicate))
1082                 {
1083                         /* atom => AND-clause if A implies each of B's items */
1084                         foreach(item, ((BoolExpr *) predicate)->args)
1085                         {
1086                                 if (!pred_test_recurse(clause, lfirst(item)))
1087                                         return false;
1088                         }
1089                         return true;
1090                 }
1091                 else if (or_clause(predicate))
1092                 {
1093                         /* atom => OR-clause if A implies any of B's items */
1094                         foreach(item, ((BoolExpr *) predicate)->args)
1095                         {
1096                                 if (pred_test_recurse(clause, lfirst(item)))
1097                                         return true;
1098                         }
1099                         return false;
1100                 }
1101                 else
1102                 {
1103                         /* atom => atom is the base case */
1104                         return pred_test_simple_clause((Expr *) predicate, clause);
1105                 }
1106         }
1107 }
1108
1109
1110 /*
1111  * Define an "operator implication table" for btree operators ("strategies").
1112  *
1113  * The strategy numbers defined by btree indexes (see access/skey.h) are:
1114  *              (1) <   (2) <=   (3) =   (4) >=   (5) >
1115  * and in addition we use (6) to represent <>.  <> is not a btree-indexable
1116  * operator, but we assume here that if the equality operator of a btree
1117  * opclass has a negator operator, the negator behaves as <> for the opclass.
1118  *
1119  * The interpretation of:
1120  *
1121  *              test_op = BT_implic_table[given_op-1][target_op-1]
1122  *
1123  * where test_op, given_op and target_op are strategy numbers (from 1 to 6)
1124  * of btree operators, is as follows:
1125  *
1126  *       If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
1127  *       want to determine whether "ATTR target_op CONST2" must also be true, then
1128  *       you can use "CONST2 test_op CONST1" as a test.  If this test returns true,
1129  *       then the target expression must be true; if the test returns false, then
1130  *       the target expression may be false.
1131  *
1132  * An entry where test_op == 0 means the implication cannot be determined,
1133  * i.e., this test should always be considered false.
1134  */
1135
1136 #define BTLT BTLessStrategyNumber
1137 #define BTLE BTLessEqualStrategyNumber
1138 #define BTEQ BTEqualStrategyNumber
1139 #define BTGE BTGreaterEqualStrategyNumber
1140 #define BTGT BTGreaterStrategyNumber
1141 #define BTNE 6
1142
1143 static const StrategyNumber
1144                         BT_implic_table[6][6] = {
1145 /*
1146  *                      The target operator:
1147  *
1148  *         LT   LE         EQ    GE    GT        NE
1149  */
1150         {BTGE, BTGE, 0, 0, 0, BTGE},    /* LT */
1151         {BTGT, BTGE, 0, 0, 0, BTGT},    /* LE */
1152         {BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE},           /* EQ */
1153         {0, 0, 0, BTLE, BTLT, BTLT},    /* GE */
1154         {0, 0, 0, BTLE, BTLE, BTLE},    /* GT */
1155         {0, 0, 0, 0, 0, BTEQ}           /* NE */
1156 };
1157
1158
1159 /*----------
1160  * pred_test_simple_clause
1161  *        Does the "predicate inclusion test" for a "simple clause" predicate
1162  *        and a "simple clause" restriction.
1163  *
1164  * We have three strategies for determining whether one simple clause
1165  * implies another:
1166  *
1167  * A simple and general way is to see if they are equal(); this works for any
1168  * kind of expression.  (Actually, there is an implied assumption that the
1169  * functions in the expression are immutable, ie dependent only on their input
1170  * arguments --- but this was checked for the predicate by CheckPredicate().)
1171  *
1172  * When the predicate is of the form "foo IS NOT NULL", we can conclude that
1173  * the predicate is implied if the clause is a strict operator or function
1174  * that has "foo" as an input.  In this case the clause must yield NULL when
1175  * "foo" is NULL, which we can take as equivalent to FALSE because we know
1176  * we are within an AND/OR subtree of a WHERE clause.  (Again, "foo" is
1177  * already known immutable, so the clause will certainly always fail.)
1178  *
1179  * Our other way works only for binary boolean opclauses of the form
1180  * "foo op constant", where "foo" is the same in both clauses.  The operators
1181  * and constants can be different but the operators must be in the same btree
1182  * operator class.      We use the above operator implication table to be able to
1183  * derive implications between nonidentical clauses.  (Note: "foo" is known
1184  * immutable, and constants are surely immutable, but we have to check that
1185  * the operators are too.  As of 8.0 it's possible for opclasses to contain
1186  * operators that are merely stable, and we dare not make deductions with
1187  * these.)
1188  *
1189  * Eventually, rtree operators could also be handled by defining an
1190  * appropriate "RT_implic_table" array.
1191  *----------
1192  */
1193 static bool
1194 pred_test_simple_clause(Expr *predicate, Node *clause)
1195 {
1196         Node       *leftop,
1197                            *rightop;
1198         Node       *pred_var,
1199                            *clause_var;
1200         Const      *pred_const,
1201                            *clause_const;
1202         bool            pred_var_on_left,
1203                                 clause_var_on_left,
1204                                 pred_op_negated;
1205         Oid                     pred_op,
1206                                 clause_op,
1207                                 pred_op_negator,
1208                                 clause_op_negator,
1209                                 test_op = InvalidOid;
1210         Oid                     opclass_id;
1211         bool            found = false;
1212         StrategyNumber pred_strategy,
1213                                 clause_strategy,
1214                                 test_strategy;
1215         Oid                     clause_subtype;
1216         Expr       *test_expr;
1217         ExprState  *test_exprstate;
1218         Datum           test_result;
1219         bool            isNull;
1220         CatCList   *catlist;
1221         int                     i;
1222         EState     *estate;
1223         MemoryContext oldcontext;
1224
1225         /* First try the equal() test */
1226         if (equal((Node *) predicate, clause))
1227                 return true;
1228
1229         /* Next try the IS NOT NULL case */
1230         if (predicate && IsA(predicate, NullTest) &&
1231                 ((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
1232         {
1233                 Expr       *nonnullarg = ((NullTest *) predicate)->arg;
1234
1235                 if (is_opclause(clause) &&
1236                         list_member(((OpExpr *) clause)->args, nonnullarg) &&
1237                         op_strict(((OpExpr *) clause)->opno))
1238                         return true;
1239                 if (is_funcclause(clause) &&
1240                         list_member(((FuncExpr *) clause)->args, nonnullarg) &&
1241                         func_strict(((FuncExpr *) clause)->funcid))
1242                         return true;
1243                 return false;                   /* we can't succeed below... */
1244         }
1245
1246         /*
1247          * Can't do anything more unless they are both binary opclauses with a
1248          * Const on one side, and identical subexpressions on the other sides.
1249          * Note we don't have to think about binary relabeling of the Const
1250          * node, since that would have been folded right into the Const.
1251          *
1252          * If either Const is null, we also fail right away; this assumes that
1253          * the test operator will always be strict.
1254          */
1255         if (!is_opclause(predicate))
1256                 return false;
1257         leftop = get_leftop(predicate);
1258         rightop = get_rightop(predicate);
1259         if (rightop == NULL)
1260                 return false;                   /* not a binary opclause */
1261         if (IsA(rightop, Const))
1262         {
1263                 pred_var = leftop;
1264                 pred_const = (Const *) rightop;
1265                 pred_var_on_left = true;
1266         }
1267         else if (IsA(leftop, Const))
1268         {
1269                 pred_var = rightop;
1270                 pred_const = (Const *) leftop;
1271                 pred_var_on_left = false;
1272         }
1273         else
1274                 return false;                   /* no Const to be found */
1275         if (pred_const->constisnull)
1276                 return false;
1277
1278         if (!is_opclause(clause))
1279                 return false;
1280         leftop = get_leftop((Expr *) clause);
1281         rightop = get_rightop((Expr *) clause);
1282         if (rightop == NULL)
1283                 return false;                   /* not a binary opclause */
1284         if (IsA(rightop, Const))
1285         {
1286                 clause_var = leftop;
1287                 clause_const = (Const *) rightop;
1288                 clause_var_on_left = true;
1289         }
1290         else if (IsA(leftop, Const))
1291         {
1292                 clause_var = rightop;
1293                 clause_const = (Const *) leftop;
1294                 clause_var_on_left = false;
1295         }
1296         else
1297                 return false;                   /* no Const to be found */
1298         if (clause_const->constisnull)
1299                 return false;
1300
1301         /*
1302          * Check for matching subexpressions on the non-Const sides.  We used
1303          * to only allow a simple Var, but it's about as easy to allow any
1304          * expression.  Remember we already know that the pred expression does
1305          * not contain any non-immutable functions, so identical expressions
1306          * should yield identical results.
1307          */
1308         if (!equal(pred_var, clause_var))
1309                 return false;
1310
1311         /*
1312          * Okay, get the operators in the two clauses we're comparing. Commute
1313          * them if needed so that we can assume the variables are on the left.
1314          */
1315         pred_op = ((OpExpr *) predicate)->opno;
1316         if (!pred_var_on_left)
1317         {
1318                 pred_op = get_commutator(pred_op);
1319                 if (!OidIsValid(pred_op))
1320                         return false;
1321         }
1322
1323         clause_op = ((OpExpr *) clause)->opno;
1324         if (!clause_var_on_left)
1325         {
1326                 clause_op = get_commutator(clause_op);
1327                 if (!OidIsValid(clause_op))
1328                         return false;
1329         }
1330
1331         /*
1332          * Try to find a btree opclass containing the needed operators.
1333          *
1334          * We must find a btree opclass that contains both operators, else the
1335          * implication can't be determined.  Also, the pred_op has to be of
1336          * default subtype (implying left and right input datatypes are the
1337          * same); otherwise it's unsafe to put the pred_const on the left side
1338          * of the test.  Also, the opclass must contain a suitable test
1339          * operator matching the clause_const's type (which we take to mean
1340          * that it has the same subtype as the original clause_operator).
1341          *
1342          * If there are multiple matching opclasses, assume we can use any one to
1343          * determine the logical relationship of the two operators and the
1344          * correct corresponding test operator.  This should work for any
1345          * logically consistent opclasses.
1346          */
1347         catlist = SearchSysCacheList(AMOPOPID, 1,
1348                                                                  ObjectIdGetDatum(pred_op),
1349                                                                  0, 0, 0);
1350
1351         /*
1352          * If we couldn't find any opclass containing the pred_op, perhaps it
1353          * is a <> operator.  See if it has a negator that is in an opclass.
1354          */
1355         pred_op_negated = false;
1356         if (catlist->n_members == 0)
1357         {
1358                 pred_op_negator = get_negator(pred_op);
1359                 if (OidIsValid(pred_op_negator))
1360                 {
1361                         pred_op_negated = true;
1362                         ReleaseSysCacheList(catlist);
1363                         catlist = SearchSysCacheList(AMOPOPID, 1,
1364                                                                            ObjectIdGetDatum(pred_op_negator),
1365                                                                                  0, 0, 0);
1366                 }
1367         }
1368
1369         /* Also may need the clause_op's negator */
1370         clause_op_negator = get_negator(clause_op);
1371
1372         /* Now search the opclasses */
1373         for (i = 0; i < catlist->n_members; i++)
1374         {
1375                 HeapTuple       pred_tuple = &catlist->members[i]->tuple;
1376                 Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
1377                 HeapTuple       clause_tuple;
1378
1379                 opclass_id = pred_form->amopclaid;
1380
1381                 /* must be btree */
1382                 if (!opclass_is_btree(opclass_id))
1383                         continue;
1384                 /* predicate operator must be default within this opclass */
1385                 if (pred_form->amopsubtype != InvalidOid)
1386                         continue;
1387
1388                 /* Get the predicate operator's btree strategy number */
1389                 pred_strategy = (StrategyNumber) pred_form->amopstrategy;
1390                 Assert(pred_strategy >= 1 && pred_strategy <= 5);
1391
1392                 if (pred_op_negated)
1393                 {
1394                         /* Only consider negators that are = */
1395                         if (pred_strategy != BTEqualStrategyNumber)
1396                                 continue;
1397                         pred_strategy = BTNE;
1398                 }
1399
1400                 /*
1401                  * From the same opclass, find a strategy number for the
1402                  * clause_op, if possible
1403                  */
1404                 clause_tuple = SearchSysCache(AMOPOPID,
1405                                                                           ObjectIdGetDatum(clause_op),
1406                                                                           ObjectIdGetDatum(opclass_id),
1407                                                                           0, 0);
1408                 if (HeapTupleIsValid(clause_tuple))
1409                 {
1410                         Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
1411
1412                         /* Get the restriction clause operator's strategy/subtype */
1413                         clause_strategy = (StrategyNumber) clause_form->amopstrategy;
1414                         Assert(clause_strategy >= 1 && clause_strategy <= 5);
1415                         clause_subtype = clause_form->amopsubtype;
1416                         ReleaseSysCache(clause_tuple);
1417                 }
1418                 else if (OidIsValid(clause_op_negator))
1419                 {
1420                         clause_tuple = SearchSysCache(AMOPOPID,
1421                                                                          ObjectIdGetDatum(clause_op_negator),
1422                                                                                   ObjectIdGetDatum(opclass_id),
1423                                                                                   0, 0);
1424                         if (HeapTupleIsValid(clause_tuple))
1425                         {
1426                                 Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
1427
1428                                 /* Get the restriction clause operator's strategy/subtype */
1429                                 clause_strategy = (StrategyNumber) clause_form->amopstrategy;
1430                                 Assert(clause_strategy >= 1 && clause_strategy <= 5);
1431                                 clause_subtype = clause_form->amopsubtype;
1432                                 ReleaseSysCache(clause_tuple);
1433
1434                                 /* Only consider negators that are = */
1435                                 if (clause_strategy != BTEqualStrategyNumber)
1436                                         continue;
1437                                 clause_strategy = BTNE;
1438                         }
1439                         else
1440                                 continue;
1441                 }
1442                 else
1443                         continue;
1444
1445                 /*
1446                  * Look up the "test" strategy number in the implication table
1447                  */
1448                 test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1449                 if (test_strategy == 0)
1450                 {
1451                         /* Can't determine implication using this interpretation */
1452                         continue;
1453                 }
1454
1455                 /*
1456                  * See if opclass has an operator for the test strategy and the
1457                  * clause datatype.
1458                  */
1459                 if (test_strategy == BTNE)
1460                 {
1461                         test_op = get_opclass_member(opclass_id, clause_subtype,
1462                                                                                  BTEqualStrategyNumber);
1463                         if (OidIsValid(test_op))
1464                                 test_op = get_negator(test_op);
1465                 }
1466                 else
1467                 {
1468                         test_op = get_opclass_member(opclass_id, clause_subtype,
1469                                                                                  test_strategy);
1470                 }
1471                 if (OidIsValid(test_op))
1472                 {
1473                         /*
1474                          * Last check: test_op must be immutable.
1475                          *
1476                          * Note that we require only the test_op to be immutable, not the
1477                          * original clause_op.  (pred_op must be immutable, else it
1478                          * would not be allowed in an index predicate.)  Essentially
1479                          * we are assuming that the opclass is consistent even if it
1480                          * contains operators that are merely stable.
1481                          */
1482                         if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
1483                         {
1484                                 found = true;
1485                                 break;
1486                         }
1487                 }
1488         }
1489
1490         ReleaseSysCacheList(catlist);
1491
1492         if (!found)
1493         {
1494                 /* couldn't find a btree opclass to interpret the operators */
1495                 return false;
1496         }
1497
1498         /*
1499          * Evaluate the test.  For this we need an EState.
1500          */
1501         estate = CreateExecutorState();
1502
1503         /* We can use the estate's working context to avoid memory leaks. */
1504         oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
1505
1506         /* Build expression tree */
1507         test_expr = make_opclause(test_op,
1508                                                           BOOLOID,
1509                                                           false,
1510                                                           (Expr *) pred_const,
1511                                                           (Expr *) clause_const);
1512
1513         /* Prepare it for execution */
1514         test_exprstate = ExecPrepareExpr(test_expr, estate);
1515
1516         /* And execute it. */
1517         test_result = ExecEvalExprSwitchContext(test_exprstate,
1518                                                                                   GetPerTupleExprContext(estate),
1519                                                                                         &isNull, NULL);
1520
1521         /* Get back to outer memory context */
1522         MemoryContextSwitchTo(oldcontext);
1523
1524         /* Release all the junk we just created */
1525         FreeExecutorState(estate);
1526
1527         if (isNull)
1528         {
1529                 /* Treat a null result as false ... but it's a tad fishy ... */
1530                 elog(DEBUG2, "null predicate test result");
1531                 return false;
1532         }
1533         return DatumGetBool(test_result);
1534 }
1535
1536
1537 /****************************************************************************
1538  *                              ----  ROUTINES TO CHECK JOIN CLAUSES  ----
1539  ****************************************************************************/
1540
1541 /*
1542  * indexable_outerrelids
1543  *        Finds all other relids that participate in any indexable join clause
1544  *        for the specified table.  Returns a set of relids.
1545  */
1546 static Relids
1547 indexable_outerrelids(RelOptInfo *rel)
1548 {
1549         Relids          outer_relids = NULL;
1550         ListCell   *l;
1551
1552         foreach(l, rel->joininfo)
1553         {
1554                 JoinInfo   *joininfo = (JoinInfo *) lfirst(l);
1555
1556                 /*
1557                  * Examine each joinclause in the JoinInfo node's list to see if
1558                  * it matches any key of any index.  If so, add the JoinInfo's
1559                  * otherrels to the result.  We can skip examining other
1560                  * joinclauses in the same list as soon as we find a match, since
1561                  * by definition they all have the same otherrels.
1562                  */
1563                 if (list_matches_any_index(joininfo->jinfo_restrictinfo,
1564                                                                    rel,
1565                                                                    joininfo->unjoined_relids))
1566                         outer_relids = bms_add_members(outer_relids,
1567                                                                                    joininfo->unjoined_relids);
1568         }
1569
1570         return outer_relids;
1571 }
1572
1573 /*
1574  * list_matches_any_index
1575  *        Workhorse for indexable_outerrelids: given a list of RestrictInfos,
1576  *        see if any of them match any index of the given rel.
1577  *
1578  * We define it like this so that we can recurse into OR subclauses.
1579  */
1580 static bool
1581 list_matches_any_index(List *clauses, RelOptInfo *rel, Relids outer_relids)
1582 {
1583         ListCell   *l;
1584
1585         foreach(l, clauses)
1586         {
1587                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1588                 ListCell *j;
1589
1590                 Assert(IsA(rinfo, RestrictInfo));
1591
1592                 /* RestrictInfos that aren't ORs are easy */
1593                 if (!restriction_is_or_clause(rinfo))
1594                 {
1595                         if (matches_any_index(rinfo, rel, outer_relids))
1596                                 return true;
1597                         continue;
1598                 }
1599
1600                 foreach(j, ((BoolExpr *) rinfo->orclause)->args)
1601                 {
1602                         Node   *orarg = (Node *) lfirst(j);
1603
1604                         /* OR arguments should be ANDs or sub-RestrictInfos */
1605                         if (and_clause(orarg))
1606                         {
1607                                 List   *andargs = ((BoolExpr *) orarg)->args;
1608
1609                                 /* Recurse to examine AND items and sub-ORs */
1610                                 if (list_matches_any_index(andargs, rel, outer_relids))
1611                                         return true;
1612                         }
1613                         else
1614                         {
1615                                 Assert(IsA(orarg, RestrictInfo));
1616                                 Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
1617                                 if (matches_any_index((RestrictInfo *) orarg, rel,
1618                                                                            outer_relids))
1619                                         return true;
1620                         }
1621                 }
1622         }
1623
1624         return false;
1625 }
1626
1627 /*
1628  * matches_any_index
1629  *        Workhorse for indexable_outerrelids: see if a simple joinclause can be
1630  *        matched to any index of the given rel.
1631  */
1632 static bool
1633 matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids)
1634 {
1635         ListCell   *l;
1636
1637         /* Normal case for a simple restriction clause */
1638         foreach(l, rel->indexlist)
1639         {
1640                 IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
1641                 int                     indexcol = 0;
1642                 Oid                *classes = index->classlist;
1643
1644                 do
1645                 {
1646                         Oid                     curClass = classes[0];
1647
1648                         if (match_clause_to_indexcol(index,
1649                                                                                  indexcol,
1650                                                                                  curClass,
1651                                                                                  rinfo,
1652                                                                                  outer_relids))
1653                                 return true;
1654
1655                         indexcol++;
1656                         classes++;
1657                 } while (!DoneMatchingIndexKeys(classes));
1658         }
1659
1660         return false;
1661 }
1662
1663 /*
1664  * best_inner_indexscan
1665  *        Finds the best available inner indexscan for a nestloop join
1666  *        with the given rel on the inside and the given outer_relids outside.
1667  *        May return NULL if there are no possible inner indexscans.
1668  *
1669  * We ignore ordering considerations (since a nestloop's inner scan's order
1670  * is uninteresting).  Also, we consider only total cost when deciding which
1671  * of two possible paths is better --- this assumes that all indexpaths have
1672  * negligible startup cost.  (True today, but someday we might have to think
1673  * harder.)  Therefore, there is only one dimension of comparison and so it's
1674  * sufficient to return a single "best" path.
1675  */
1676 Path *
1677 best_inner_indexscan(Query *root, RelOptInfo *rel,
1678                                          Relids outer_relids, JoinType jointype)
1679 {
1680         Path       *cheapest;
1681         bool            isouterjoin;
1682         List       *clause_list;
1683         List       *indexpaths;
1684         List       *bitindexpaths;
1685         ListCell   *l;
1686         InnerIndexscanInfo *info;
1687         MemoryContext oldcontext;
1688
1689         /*
1690          * Nestloop only supports inner, left, and IN joins.
1691          */
1692         switch (jointype)
1693         {
1694                 case JOIN_INNER:
1695                 case JOIN_IN:
1696                 case JOIN_UNIQUE_OUTER:
1697                         isouterjoin = false;
1698                         break;
1699                 case JOIN_LEFT:
1700                         isouterjoin = true;
1701                         break;
1702                 default:
1703                         return NULL;
1704         }
1705
1706         /*
1707          * If there are no indexable joinclauses for this rel, exit quickly.
1708          */
1709         if (bms_is_empty(rel->index_outer_relids))
1710                 return NULL;
1711
1712         /*
1713          * Otherwise, we have to do path selection in the memory context of
1714          * the given rel, so that any created path can be safely attached to
1715          * the rel's cache of best inner paths.  (This is not currently an
1716          * issue for normal planning, but it is an issue for GEQO planning.)
1717          */
1718         oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1719
1720         /*
1721          * Intersect the given outer_relids with index_outer_relids to find
1722          * the set of outer relids actually relevant for this rel. If there
1723          * are none, again we can fail immediately.
1724          */
1725         outer_relids = bms_intersect(rel->index_outer_relids, outer_relids);
1726         if (bms_is_empty(outer_relids))
1727         {
1728                 bms_free(outer_relids);
1729                 MemoryContextSwitchTo(oldcontext);
1730                 return NULL;
1731         }
1732
1733         /*
1734          * Look to see if we already computed the result for this set of
1735          * relevant outerrels.  (We include the isouterjoin status in the
1736          * cache lookup key for safety.  In practice I suspect this is not
1737          * necessary because it should always be the same for a given
1738          * innerrel.)
1739          */
1740         foreach(l, rel->index_inner_paths)
1741         {
1742                 info = (InnerIndexscanInfo *) lfirst(l);
1743                 if (bms_equal(info->other_relids, outer_relids) &&
1744                         info->isouterjoin == isouterjoin)
1745                 {
1746                         bms_free(outer_relids);
1747                         MemoryContextSwitchTo(oldcontext);
1748                         return info->best_innerpath;
1749                 }
1750         }
1751
1752         /*
1753          * Find all the relevant restriction and join clauses.
1754          */
1755         clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin);
1756
1757         /*
1758          * Find all the index paths that are usable for this join, except for
1759          * stuff involving OR clauses.
1760          */
1761         indexpaths = find_usable_indexes(root, rel,
1762                                                                          clause_list, NIL,
1763                                                                          false, true,
1764                                                                          outer_relids);
1765
1766         /*
1767          * Generate BitmapOrPaths for any suitable OR-clauses present in the
1768          * clause list.
1769          */
1770         bitindexpaths = generate_bitmap_or_paths(root, rel,
1771                                                                                          clause_list, NIL,
1772                                                                                          true,
1773                                                                                          outer_relids);
1774
1775         /*
1776          * Include the regular index paths in bitindexpaths.
1777          */
1778         bitindexpaths = list_concat(bitindexpaths, list_copy(indexpaths));
1779
1780         /*
1781          * If we found anything usable, generate a BitmapHeapPath for the
1782          * most promising combination of bitmap index paths.
1783          */
1784         if (bitindexpaths != NIL)
1785         {
1786                 Path       *bitmapqual;
1787                 BitmapHeapPath *bpath;
1788
1789                 bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
1790                 bpath = create_bitmap_heap_path(root, rel, bitmapqual, true);
1791                 indexpaths = lappend(indexpaths, bpath);
1792         }
1793
1794         /*
1795          * Now choose the cheapest member of indexpaths.
1796          */
1797         cheapest = NULL;
1798         foreach(l, indexpaths)
1799         {
1800                 Path       *path = (Path *) lfirst(l);
1801
1802                 if (cheapest == NULL ||
1803                         compare_path_costs(path, cheapest, TOTAL_COST) < 0)
1804                         cheapest = path;
1805         }
1806
1807         /* Cache the result --- whether positive or negative */
1808         info = makeNode(InnerIndexscanInfo);
1809         info->other_relids = outer_relids;
1810         info->isouterjoin = isouterjoin;
1811         info->best_innerpath = cheapest;
1812         rel->index_inner_paths = lcons(info, rel->index_inner_paths);
1813
1814         MemoryContextSwitchTo(oldcontext);
1815
1816         return cheapest;
1817 }
1818
1819 /*
1820  * find_clauses_for_join
1821  *        Generate a list of clauses that are potentially useful for
1822  *        scanning rel as the inner side of a nestloop join.
1823  *
1824  * We consider both join and restriction clauses.  Any joinclause that uses
1825  * only otherrels in the specified outer_relids is fair game.  But there must
1826  * be at least one such joinclause in the final list, otherwise we return NIL
1827  * indicating that there isn't any potential win here.
1828  */
1829 static List *
1830 find_clauses_for_join(Query *root, RelOptInfo *rel,
1831                                           Relids outer_relids, bool isouterjoin)
1832 {
1833         List       *clause_list = NIL;
1834         bool            jfound = false;
1835         int                     numsources;
1836         ListCell   *l;
1837
1838         /*
1839          * We can always use plain restriction clauses for the rel.  We
1840          * scan these first because we want them first in the clause
1841          * list for the convenience of remove_redundant_join_clauses,
1842          * which can never remove non-join clauses and hence won't be able
1843          * to get rid of a non-join clause if it appears after a join
1844          * clause it is redundant with.
1845          */
1846         foreach(l, rel->baserestrictinfo)
1847         {
1848                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1849
1850                 /* Can't use pushed-down clauses in outer join */
1851                 if (isouterjoin && rinfo->is_pushed_down)
1852                         continue;
1853                 clause_list = lappend(clause_list, rinfo);
1854         }
1855
1856         /* found anything in base restrict list? */
1857         numsources = (clause_list != NIL) ? 1 : 0;
1858
1859         /* Look for joinclauses that are usable with given outer_relids */
1860         foreach(l, rel->joininfo)
1861         {
1862                 JoinInfo   *joininfo = (JoinInfo *) lfirst(l);
1863                 bool            jfoundhere = false;
1864                 ListCell   *j;
1865
1866                 if (!bms_is_subset(joininfo->unjoined_relids, outer_relids))
1867                         continue;
1868
1869                 foreach(j, joininfo->jinfo_restrictinfo)
1870                 {
1871                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1872
1873                         /* Can't use pushed-down clauses in outer join */
1874                         if (isouterjoin && rinfo->is_pushed_down)
1875                                 continue;
1876
1877                         clause_list = lappend(clause_list, rinfo);
1878                         if (!jfoundhere)
1879                         {
1880                                 jfoundhere = true;
1881                                 jfound = true;
1882                                 numsources++;
1883                         }
1884                 }
1885         }
1886
1887         /* if no join clause was matched then forget it, per comments above */
1888         if (!jfound)
1889                 return NIL;
1890
1891         /*
1892          * If we found clauses in more than one list, we may now have
1893          * clauses that are known redundant.  Get rid of 'em.
1894          */
1895         if (numsources > 1)
1896         {
1897                 clause_list = remove_redundant_join_clauses(root,
1898                                                                                                         clause_list,
1899                                                                                                         isouterjoin);
1900         }
1901
1902         return clause_list;
1903 }
1904
1905 /****************************************************************************
1906  *                              ----  PATH CREATION UTILITIES  ----
1907  ****************************************************************************/
1908
1909 /*
1910  * flatten_clausegroups_list
1911  *        Given a list of lists of RestrictInfos, flatten it to a list
1912  *        of RestrictInfos.
1913  *
1914  * This is used to flatten out the result of group_clauses_by_indexkey()
1915  * to produce an indexclauses list.
1916  */
1917 List *
1918 flatten_clausegroups_list(List *clausegroups)
1919 {
1920         List       *allclauses = NIL;
1921         ListCell   *l;
1922
1923         foreach(l, clausegroups)
1924                 allclauses = list_concat(allclauses, list_copy((List *) lfirst(l)));
1925         return allclauses;
1926 }
1927
1928
1929 /****************************************************************************
1930  *                              ----  ROUTINES TO CHECK OPERANDS  ----
1931  ****************************************************************************/
1932
1933 /*
1934  * match_index_to_operand()
1935  *        Generalized test for a match between an index's key
1936  *        and the operand on one side of a restriction or join clause.
1937  *
1938  * operand: the nodetree to be compared to the index
1939  * indexcol: the column number of the index (counting from 0)
1940  * index: the index of interest
1941  */
1942 bool
1943 match_index_to_operand(Node *operand,
1944                                            int indexcol,
1945                                            IndexOptInfo *index)
1946 {
1947         int                     indkey;
1948
1949         /*
1950          * Ignore any RelabelType node above the operand.       This is needed to
1951          * be able to apply indexscanning in binary-compatible-operator cases.
1952          * Note: we can assume there is at most one RelabelType node;
1953          * eval_const_expressions() will have simplified if more than one.
1954          */
1955         if (operand && IsA(operand, RelabelType))
1956                 operand = (Node *) ((RelabelType *) operand)->arg;
1957
1958         indkey = index->indexkeys[indexcol];
1959         if (indkey != 0)
1960         {
1961                 /*
1962                  * Simple index column; operand must be a matching Var.
1963                  */
1964                 if (operand && IsA(operand, Var) &&
1965                         index->rel->relid == ((Var *) operand)->varno &&
1966                         indkey == ((Var *) operand)->varattno)
1967                         return true;
1968         }
1969         else
1970         {
1971                 /*
1972                  * Index expression; find the correct expression.  (This search
1973                  * could be avoided, at the cost of complicating all the callers
1974                  * of this routine; doesn't seem worth it.)
1975                  */
1976                 ListCell   *indexpr_item;
1977                 int                     i;
1978                 Node       *indexkey;
1979
1980                 indexpr_item = list_head(index->indexprs);
1981                 for (i = 0; i < indexcol; i++)
1982                 {
1983                         if (index->indexkeys[i] == 0)
1984                         {
1985                                 if (indexpr_item == NULL)
1986                                         elog(ERROR, "wrong number of index expressions");
1987                                 indexpr_item = lnext(indexpr_item);
1988                         }
1989                 }
1990                 if (indexpr_item == NULL)
1991                         elog(ERROR, "wrong number of index expressions");
1992                 indexkey = (Node *) lfirst(indexpr_item);
1993
1994                 /*
1995                  * Does it match the operand?  Again, strip any relabeling.
1996                  */
1997                 if (indexkey && IsA(indexkey, RelabelType))
1998                         indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1999
2000                 if (equal(indexkey, operand))
2001                         return true;
2002         }
2003
2004         return false;
2005 }
2006
2007 /****************************************************************************
2008  *                      ----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
2009  ****************************************************************************/
2010
2011 /*----------
2012  * These routines handle special optimization of operators that can be
2013  * used with index scans even though they are not known to the executor's
2014  * indexscan machinery.  The key idea is that these operators allow us
2015  * to derive approximate indexscan qual clauses, such that any tuples
2016  * that pass the operator clause itself must also satisfy the simpler
2017  * indexscan condition(s).      Then we can use the indexscan machinery
2018  * to avoid scanning as much of the table as we'd otherwise have to,
2019  * while applying the original operator as a qpqual condition to ensure
2020  * we deliver only the tuples we want.  (In essence, we're using a regular
2021  * index as if it were a lossy index.)
2022  *
2023  * An example of what we're doing is
2024  *                      textfield LIKE 'abc%'
2025  * from which we can generate the indexscanable conditions
2026  *                      textfield >= 'abc' AND textfield < 'abd'
2027  * which allow efficient scanning of an index on textfield.
2028  * (In reality, character set and collation issues make the transformation
2029  * from LIKE to indexscan limits rather harder than one might think ...
2030  * but that's the basic idea.)
2031  *
2032  * Another thing that we do with this machinery is to provide special
2033  * smarts for "boolean" indexes (that is, indexes on boolean columns
2034  * that support boolean equality).  We can transform a plain reference
2035  * to the indexkey into "indexkey = true", or "NOT indexkey" into
2036  * "indexkey = false", so as to make the expression indexable using the
2037  * regular index operators.  (As of Postgres 8.1, we must do this here
2038  * because constant simplification does the reverse transformation;
2039  * without this code there'd be no way to use such an index at all.)
2040  *
2041  * Three routines are provided here:
2042  *
2043  * match_special_index_operator() is just an auxiliary function for
2044  * match_clause_to_indexcol(); after the latter fails to recognize a
2045  * restriction opclause's operator as a member of an index's opclass,
2046  * it asks match_special_index_operator() whether the clause should be
2047  * considered an indexqual anyway.
2048  *
2049  * match_boolean_index_clause() similarly detects clauses that can be
2050  * converted into boolean equality operators.
2051  *
2052  * expand_indexqual_conditions() converts a list of lists of RestrictInfo
2053  * nodes (with implicit AND semantics across list elements) into
2054  * a list of clauses that the executor can actually handle.  For operators
2055  * that are members of the index's opclass this transformation is a no-op,
2056  * but clauses recognized by match_special_index_operator() or
2057  * match_boolean_index_clause() must be converted into one or more "regular"
2058  * indexqual conditions.
2059  *----------
2060  */
2061
2062 /*
2063  * match_boolean_index_clause
2064  *        Recognize restriction clauses that can be matched to a boolean index.
2065  *
2066  * This should be called only when IsBooleanOpclass() recognizes the
2067  * index's operator class.  We check to see if the clause matches the
2068  * index's key.
2069  */
2070 static bool
2071 match_boolean_index_clause(Node *clause,
2072                                                    int indexcol,
2073                                                    IndexOptInfo *index)
2074 {
2075         /* Direct match? */
2076         if (match_index_to_operand(clause, indexcol, index))
2077                 return true;
2078         /* NOT clause? */
2079         if (not_clause(clause))
2080         {
2081                 if (match_index_to_operand((Node *) get_notclausearg((Expr *) clause),
2082                                                                    indexcol, index))
2083                         return true;
2084         }
2085         /*
2086          * Since we only consider clauses at top level of WHERE, we can convert
2087          * indexkey IS TRUE and indexkey IS FALSE to index searches as well.
2088          * The different meaning for NULL isn't important.
2089          */
2090         else if (clause && IsA(clause, BooleanTest))
2091         {
2092                 BooleanTest        *btest = (BooleanTest *) clause;
2093
2094                 if (btest->booltesttype == IS_TRUE ||
2095                         btest->booltesttype == IS_FALSE)
2096                         if (match_index_to_operand((Node *) btest->arg,
2097                                                                            indexcol, index))
2098                                 return true;
2099         }
2100         return false;
2101 }
2102
2103 /*
2104  * match_special_index_operator
2105  *        Recognize restriction clauses that can be used to generate
2106  *        additional indexscanable qualifications.
2107  *
2108  * The given clause is already known to be a binary opclause having
2109  * the form (indexkey OP pseudoconst) or (pseudoconst OP indexkey),
2110  * but the OP proved not to be one of the index's opclass operators.
2111  * Return 'true' if we can do something with it anyway.
2112  */
2113 static bool
2114 match_special_index_operator(Expr *clause, Oid opclass,
2115                                                          bool indexkey_on_left)
2116 {
2117         bool            isIndexable = false;
2118         Node       *rightop;
2119         Oid                     expr_op;
2120         Const      *patt;
2121         Const      *prefix = NULL;
2122         Const      *rest = NULL;
2123
2124         /*
2125          * Currently, all known special operators require the indexkey on the
2126          * left, but this test could be pushed into the switch statement if
2127          * some are added that do not...
2128          */
2129         if (!indexkey_on_left)
2130                 return false;
2131
2132         /* we know these will succeed */
2133         rightop = get_rightop(clause);
2134         expr_op = ((OpExpr *) clause)->opno;
2135
2136         /* again, required for all current special ops: */
2137         if (!IsA(rightop, Const) ||
2138                 ((Const *) rightop)->constisnull)
2139                 return false;
2140         patt = (Const *) rightop;
2141
2142         switch (expr_op)
2143         {
2144                 case OID_TEXT_LIKE_OP:
2145                 case OID_BPCHAR_LIKE_OP:
2146                 case OID_NAME_LIKE_OP:
2147                         /* the right-hand const is type text for all of these */
2148                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
2149                                                                   &prefix, &rest) != Pattern_Prefix_None;
2150                         break;
2151
2152                 case OID_BYTEA_LIKE_OP:
2153                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
2154                                                                   &prefix, &rest) != Pattern_Prefix_None;
2155                         break;
2156
2157                 case OID_TEXT_ICLIKE_OP:
2158                 case OID_BPCHAR_ICLIKE_OP:
2159                 case OID_NAME_ICLIKE_OP:
2160                         /* the right-hand const is type text for all of these */
2161                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
2162                                                                   &prefix, &rest) != Pattern_Prefix_None;
2163                         break;
2164
2165                 case OID_TEXT_REGEXEQ_OP:
2166                 case OID_BPCHAR_REGEXEQ_OP:
2167                 case OID_NAME_REGEXEQ_OP:
2168                         /* the right-hand const is type text for all of these */
2169                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex,
2170                                                                   &prefix, &rest) != Pattern_Prefix_None;
2171                         break;
2172
2173                 case OID_TEXT_ICREGEXEQ_OP:
2174                 case OID_BPCHAR_ICREGEXEQ_OP:
2175                 case OID_NAME_ICREGEXEQ_OP:
2176                         /* the right-hand const is type text for all of these */
2177                         isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
2178                                                                   &prefix, &rest) != Pattern_Prefix_None;
2179                         break;
2180
2181                 case OID_INET_SUB_OP:
2182                 case OID_INET_SUBEQ_OP:
2183                 case OID_CIDR_SUB_OP:
2184                 case OID_CIDR_SUBEQ_OP:
2185                         isIndexable = true;
2186                         break;
2187         }
2188
2189         if (prefix)
2190         {
2191                 pfree(DatumGetPointer(prefix->constvalue));
2192                 pfree(prefix);
2193         }
2194
2195         /* done if the expression doesn't look indexable */
2196         if (!isIndexable)
2197                 return false;
2198
2199         /*
2200          * Must also check that index's opclass supports the operators we will
2201          * want to apply.  (A hash index, for example, will not support ">=".)
2202          * Currently, only btree supports the operators we need.
2203          *
2204          * We insist on the opclass being the specific one we expect, else we'd
2205          * do the wrong thing if someone were to make a reverse-sort opclass
2206          * with the same operators.
2207          */
2208         switch (expr_op)
2209         {
2210                 case OID_TEXT_LIKE_OP:
2211                 case OID_TEXT_ICLIKE_OP:
2212                 case OID_TEXT_REGEXEQ_OP:
2213                 case OID_TEXT_ICREGEXEQ_OP:
2214                         /* text operators will be used for varchar inputs, too */
2215                         isIndexable =
2216                                 (opclass == TEXT_PATTERN_BTREE_OPS_OID) ||
2217                                 (opclass == TEXT_BTREE_OPS_OID && lc_collate_is_c()) ||
2218                                 (opclass == VARCHAR_PATTERN_BTREE_OPS_OID) ||
2219                                 (opclass == VARCHAR_BTREE_OPS_OID && lc_collate_is_c());
2220                         break;
2221
2222                 case OID_BPCHAR_LIKE_OP:
2223                 case OID_BPCHAR_ICLIKE_OP:
2224                 case OID_BPCHAR_REGEXEQ_OP:
2225                 case OID_BPCHAR_ICREGEXEQ_OP:
2226                         isIndexable =
2227                                 (opclass == BPCHAR_PATTERN_BTREE_OPS_OID) ||
2228                                 (opclass == BPCHAR_BTREE_OPS_OID && lc_collate_is_c());
2229                         break;
2230
2231                 case OID_NAME_LIKE_OP:
2232                 case OID_NAME_ICLIKE_OP:
2233                 case OID_NAME_REGEXEQ_OP:
2234                 case OID_NAME_ICREGEXEQ_OP:
2235                         isIndexable =
2236                                 (opclass == NAME_PATTERN_BTREE_OPS_OID) ||
2237                                 (opclass == NAME_BTREE_OPS_OID && lc_collate_is_c());
2238                         break;
2239
2240                 case OID_BYTEA_LIKE_OP:
2241                         isIndexable = (opclass == BYTEA_BTREE_OPS_OID);
2242                         break;
2243
2244                 case OID_INET_SUB_OP:
2245                 case OID_INET_SUBEQ_OP:
2246                         isIndexable = (opclass == INET_BTREE_OPS_OID);
2247                         break;
2248
2249                 case OID_CIDR_SUB_OP:
2250                 case OID_CIDR_SUBEQ_OP:
2251                         isIndexable = (opclass == CIDR_BTREE_OPS_OID);
2252                         break;
2253         }
2254
2255         return isIndexable;
2256 }
2257
2258 /*
2259  * expand_indexqual_conditions
2260  *        Given a list of sublists of RestrictInfo nodes, produce a flat list
2261  *        of index qual clauses.  Standard qual clauses (those in the index's
2262  *        opclass) are passed through unchanged.  Boolean clauses and "special"
2263  *        index operators are expanded into clauses that the indexscan machinery
2264  *        will know what to do with.
2265  *
2266  * The input list is ordered by index key, and so the output list is too.
2267  * (The latter is not depended on by any part of the planner, so far as I can
2268  * tell; but some parts of the executor do assume that the indexqual list
2269  * ultimately delivered to the executor is so ordered.  One such place is
2270  * _bt_preprocess_keys() in the btree support.  Perhaps that ought to be fixed
2271  * someday --- tgl 7/00)
2272  */
2273 List *
2274 expand_indexqual_conditions(IndexOptInfo *index, List *clausegroups)
2275 {
2276         List       *resultquals = NIL;
2277         ListCell   *clausegroup_item;
2278         int                     indexcol = 0;
2279         Oid                *classes = index->classlist;
2280
2281         if (clausegroups == NIL)
2282                 return NIL;
2283
2284         clausegroup_item = list_head(clausegroups);
2285         do
2286         {
2287                 Oid                     curClass = classes[0];
2288                 ListCell   *l;
2289
2290                 foreach(l, (List *) lfirst(clausegroup_item))
2291                 {
2292                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
2293
2294                         /* First check for boolean cases */
2295                         if (IsBooleanOpclass(curClass))
2296                         {
2297                                 Expr   *boolqual;
2298
2299                                 boolqual = expand_boolean_index_clause((Node *) rinfo->clause,
2300                                                                                                            indexcol,
2301                                                                                                            index);
2302                                 if (boolqual)
2303                                 {
2304                                         resultquals = lappend(resultquals,
2305                                                                                   make_restrictinfo(boolqual,
2306                                                                                                                         true, true));
2307                                         continue;
2308                                 }
2309                         }
2310
2311                         resultquals = list_concat(resultquals,
2312                                                                           expand_indexqual_condition(rinfo,
2313                                                                                                                                  curClass));
2314                 }
2315
2316                 clausegroup_item = lnext(clausegroup_item);
2317
2318                 indexcol++;
2319                 classes++;
2320         } while (clausegroup_item != NULL && !DoneMatchingIndexKeys(classes));
2321
2322         Assert(clausegroup_item == NULL);       /* else more groups than indexkeys */
2323
2324         return resultquals;
2325 }
2326
2327 /*
2328  * expand_boolean_index_clause
2329  *        Convert a clause recognized by match_boolean_index_clause into
2330  *        a boolean equality operator clause.
2331  *
2332  * Returns NULL if the clause isn't a boolean index qual.
2333  */
2334 static Expr *
2335 expand_boolean_index_clause(Node *clause,
2336                                                         int indexcol,
2337                                                         IndexOptInfo *index)
2338 {
2339         /* Direct match? */
2340         if (match_index_to_operand(clause, indexcol, index))
2341         {
2342                 /* convert to indexkey = TRUE */
2343                 return make_opclause(BooleanEqualOperator, BOOLOID, false,
2344                                                          (Expr *) clause,
2345                                                          (Expr *) makeBoolConst(true, false));
2346         }
2347         /* NOT clause? */
2348         if (not_clause(clause))
2349         {
2350                 Node   *arg = (Node *) get_notclausearg((Expr *) clause);
2351
2352                 /* It must have matched the indexkey */
2353                 Assert(match_index_to_operand(arg, indexcol, index));
2354                 /* convert to indexkey = FALSE */
2355                 return make_opclause(BooleanEqualOperator, BOOLOID, false,
2356                                                          (Expr *) arg,
2357                                                          (Expr *) makeBoolConst(false, false));
2358         }
2359         if (clause && IsA(clause, BooleanTest))
2360         {
2361                 BooleanTest        *btest = (BooleanTest *) clause;
2362                 Node   *arg = (Node *) btest->arg;
2363
2364                 /* It must have matched the indexkey */
2365                 Assert(match_index_to_operand(arg, indexcol, index));
2366                 if (btest->booltesttype == IS_TRUE)
2367                 {
2368                         /* convert to indexkey = TRUE */
2369                         return make_opclause(BooleanEqualOperator, BOOLOID, false,
2370                                                                  (Expr *) arg,
2371                                                                  (Expr *) makeBoolConst(true, false));
2372                 }
2373                 if (btest->booltesttype == IS_FALSE)
2374                 {
2375                         /* convert to indexkey = FALSE */
2376                         return make_opclause(BooleanEqualOperator, BOOLOID, false,
2377                                                                  (Expr *) arg,
2378                                                                  (Expr *) makeBoolConst(false, false));
2379                 }
2380                 /* Oops */
2381                 Assert(false);
2382         }
2383
2384         return NULL;
2385 }
2386
2387 /*
2388  * expand_indexqual_condition --- expand a single indexqual condition
2389  *              (other than a boolean-qual case)
2390  *
2391  * The input is a single RestrictInfo, the output a list of RestrictInfos
2392  */
2393 static List *
2394 expand_indexqual_condition(RestrictInfo *rinfo, Oid opclass)
2395 {
2396         Expr       *clause = rinfo->clause;
2397         /* we know these will succeed */
2398         Node       *leftop = get_leftop(clause);
2399         Node       *rightop = get_rightop(clause);
2400         Oid                     expr_op = ((OpExpr *) clause)->opno;
2401         Const      *patt = (Const *) rightop;
2402         Const      *prefix = NULL;
2403         Const      *rest = NULL;
2404         Pattern_Prefix_Status pstatus;
2405         List       *result;
2406
2407         switch (expr_op)
2408         {
2409                         /*
2410                          * LIKE and regex operators are not members of any index
2411                          * opclass, so if we find one in an indexqual list we can
2412                          * assume that it was accepted by
2413                          * match_special_index_operator().
2414                          */
2415                 case OID_TEXT_LIKE_OP:
2416                 case OID_BPCHAR_LIKE_OP:
2417                 case OID_NAME_LIKE_OP:
2418                 case OID_BYTEA_LIKE_OP:
2419                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
2420                                                                                    &prefix, &rest);
2421                         result = prefix_quals(leftop, opclass, prefix, pstatus);
2422                         break;
2423
2424                 case OID_TEXT_ICLIKE_OP:
2425                 case OID_BPCHAR_ICLIKE_OP:
2426                 case OID_NAME_ICLIKE_OP:
2427                         /* the right-hand const is type text for all of these */
2428                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
2429                                                                                    &prefix, &rest);
2430                         result = prefix_quals(leftop, opclass, prefix, pstatus);
2431                         break;
2432
2433                 case OID_TEXT_REGEXEQ_OP:
2434                 case OID_BPCHAR_REGEXEQ_OP:
2435                 case OID_NAME_REGEXEQ_OP:
2436                         /* the right-hand const is type text for all of these */
2437                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex,
2438                                                                                    &prefix, &rest);
2439                         result = prefix_quals(leftop, opclass, prefix, pstatus);
2440                         break;
2441
2442                 case OID_TEXT_ICREGEXEQ_OP:
2443                 case OID_BPCHAR_ICREGEXEQ_OP:
2444                 case OID_NAME_ICREGEXEQ_OP:
2445                         /* the right-hand const is type text for all of these */
2446                         pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
2447                                                                                    &prefix, &rest);
2448                         result = prefix_quals(leftop, opclass, prefix, pstatus);
2449                         break;
2450
2451                 case OID_INET_SUB_OP:
2452                 case OID_INET_SUBEQ_OP:
2453                 case OID_CIDR_SUB_OP:
2454                 case OID_CIDR_SUBEQ_OP:
2455                         result = network_prefix_quals(leftop, expr_op, opclass,
2456                                                                                   patt->constvalue);
2457                         break;
2458
2459                 default:
2460                         result = list_make1(rinfo);
2461                         break;
2462         }
2463
2464         return result;
2465 }
2466
2467 /*
2468  * Given a fixed prefix that all the "leftop" values must have,
2469  * generate suitable indexqual condition(s).  opclass is the index
2470  * operator class; we use it to deduce the appropriate comparison
2471  * operators and operand datatypes.
2472  */
2473 static List *
2474 prefix_quals(Node *leftop, Oid opclass,
2475                          Const *prefix_const, Pattern_Prefix_Status pstatus)
2476 {
2477         List       *result;
2478         Oid                     datatype;
2479         Oid                     oproid;
2480         Expr       *expr;
2481         Const      *greaterstr;
2482
2483         Assert(pstatus != Pattern_Prefix_None);
2484
2485         switch (opclass)
2486         {
2487                 case TEXT_BTREE_OPS_OID:
2488                 case TEXT_PATTERN_BTREE_OPS_OID:
2489                         datatype = TEXTOID;
2490                         break;
2491
2492                 case VARCHAR_BTREE_OPS_OID:
2493                 case VARCHAR_PATTERN_BTREE_OPS_OID:
2494                         datatype = VARCHAROID;
2495                         break;
2496
2497                 case BPCHAR_BTREE_OPS_OID:
2498                 case BPCHAR_PATTERN_BTREE_OPS_OID:
2499                         datatype = BPCHAROID;
2500                         break;
2501
2502                 case NAME_BTREE_OPS_OID:
2503                 case NAME_PATTERN_BTREE_OPS_OID:
2504                         datatype = NAMEOID;
2505                         break;
2506
2507                 case BYTEA_BTREE_OPS_OID:
2508                         datatype = BYTEAOID;
2509                         break;
2510
2511                 default:
2512                         /* shouldn't get here */
2513                         elog(ERROR, "unexpected opclass: %u", opclass);
2514                         return NIL;
2515         }
2516
2517         /*
2518          * If necessary, coerce the prefix constant to the right type. The
2519          * given prefix constant is either text or bytea type.
2520          */
2521         if (prefix_const->consttype != datatype)
2522         {
2523                 char       *prefix;
2524
2525                 switch (prefix_const->consttype)
2526                 {
2527                         case TEXTOID:
2528                                 prefix = DatumGetCString(DirectFunctionCall1(textout,
2529                                                                                           prefix_const->constvalue));
2530                                 break;
2531                         case BYTEAOID:
2532                                 prefix = DatumGetCString(DirectFunctionCall1(byteaout,
2533                                                                                           prefix_const->constvalue));
2534                                 break;
2535                         default:
2536                                 elog(ERROR, "unexpected const type: %u",
2537                                          prefix_const->consttype);
2538                                 return NIL;
2539                 }
2540                 prefix_const = string_to_const(prefix, datatype);
2541                 pfree(prefix);
2542         }
2543
2544         /*
2545          * If we found an exact-match pattern, generate an "=" indexqual.
2546          */
2547         if (pstatus == Pattern_Prefix_Exact)
2548         {
2549                 oproid = get_opclass_member(opclass, InvalidOid,
2550                                                                         BTEqualStrategyNumber);
2551                 if (oproid == InvalidOid)
2552                         elog(ERROR, "no = operator for opclass %u", opclass);
2553                 expr = make_opclause(oproid, BOOLOID, false,
2554                                                          (Expr *) leftop, (Expr *) prefix_const);
2555                 result = list_make1(make_restrictinfo(expr, true, true));
2556                 return result;
2557         }
2558
2559         /*
2560          * Otherwise, we have a nonempty required prefix of the values.
2561          *
2562          * We can always say "x >= prefix".
2563          */
2564         oproid = get_opclass_member(opclass, InvalidOid,
2565                                                                 BTGreaterEqualStrategyNumber);
2566         if (oproid == InvalidOid)
2567                 elog(ERROR, "no >= operator for opclass %u", opclass);
2568         expr = make_opclause(oproid, BOOLOID, false,
2569                                                  (Expr *) leftop, (Expr *) prefix_const);
2570         result = list_make1(make_restrictinfo(expr, true, true));
2571
2572         /*-------
2573          * If we can create a string larger than the prefix, we can say
2574          * "x < greaterstr".
2575          *-------
2576          */
2577         greaterstr = make_greater_string(prefix_const);
2578         if (greaterstr)
2579         {
2580                 oproid = get_opclass_member(opclass, InvalidOid,
2581                                                                         BTLessStrategyNumber);
2582                 if (oproid == InvalidOid)
2583                         elog(ERROR, "no < operator for opclass %u", opclass);
2584                 expr = make_opclause(oproid, BOOLOID, false,
2585                                                          (Expr *) leftop, (Expr *) greaterstr);
2586                 result = lappend(result, make_restrictinfo(expr, true, true));
2587         }
2588
2589         return result;
2590 }
2591
2592 /*
2593  * Given a leftop and a rightop, and a inet-class sup/sub operator,
2594  * generate suitable indexqual condition(s).  expr_op is the original
2595  * operator, and opclass is the index opclass.
2596  */
2597 static List *
2598 network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass, Datum rightop)
2599 {
2600         bool            is_eq;
2601         Oid                     datatype;
2602         Oid                     opr1oid;
2603         Oid                     opr2oid;
2604         Datum           opr1right;
2605         Datum           opr2right;
2606         List       *result;
2607         Expr       *expr;
2608
2609         switch (expr_op)
2610         {
2611                 case OID_INET_SUB_OP:
2612                         datatype = INETOID;
2613                         is_eq = false;
2614                         break;
2615                 case OID_INET_SUBEQ_OP:
2616                         datatype = INETOID;
2617                         is_eq = true;
2618                         break;
2619                 case OID_CIDR_SUB_OP:
2620                         datatype = CIDROID;
2621                         is_eq = false;
2622                         break;
2623                 case OID_CIDR_SUBEQ_OP:
2624                         datatype = CIDROID;
2625                         is_eq = true;
2626                         break;
2627                 default:
2628                         elog(ERROR, "unexpected operator: %u", expr_op);
2629                         return NIL;
2630         }
2631
2632         /*
2633          * create clause "key >= network_scan_first( rightop )", or ">" if the
2634          * operator disallows equality.
2635          */
2636         if (is_eq)
2637         {
2638                 opr1oid = get_opclass_member(opclass, InvalidOid,
2639                                                                          BTGreaterEqualStrategyNumber);
2640                 if (opr1oid == InvalidOid)
2641                         elog(ERROR, "no >= operator for opclass %u", opclass);
2642         }
2643         else
2644         {
2645                 opr1oid = get_opclass_member(opclass, InvalidOid,
2646                                                                          BTGreaterStrategyNumber);
2647                 if (opr1oid == InvalidOid)
2648                         elog(ERROR, "no > operator for opclass %u", opclass);
2649         }
2650
2651         opr1right = network_scan_first(rightop);
2652
2653         expr = make_opclause(opr1oid, BOOLOID, false,
2654                                                  (Expr *) leftop,
2655                                                  (Expr *) makeConst(datatype, -1, opr1right,
2656                                                                                         false, false));
2657         result = list_make1(make_restrictinfo(expr, true, true));
2658
2659         /* create clause "key <= network_scan_last( rightop )" */
2660
2661         opr2oid = get_opclass_member(opclass, InvalidOid,
2662                                                                  BTLessEqualStrategyNumber);
2663         if (opr2oid == InvalidOid)
2664                 elog(ERROR, "no <= operator for opclass %u", opclass);
2665
2666         opr2right = network_scan_last(rightop);
2667
2668         expr = make_opclause(opr2oid, BOOLOID, false,
2669                                                  (Expr *) leftop,
2670                                                  (Expr *) makeConst(datatype, -1, opr2right,
2671                                                                                         false, false));
2672         result = lappend(result, make_restrictinfo(expr, true, true));
2673
2674         return result;
2675 }
2676
2677 /*
2678  * Handy subroutines for match_special_index_operator() and friends.
2679  */
2680
2681 /*
2682  * Generate a Datum of the appropriate type from a C string.
2683  * Note that all of the supported types are pass-by-ref, so the
2684  * returned value should be pfree'd if no longer needed.
2685  */
2686 static Datum
2687 string_to_datum(const char *str, Oid datatype)
2688 {
2689         /*
2690          * We cheat a little by assuming that textin() will do for bpchar and
2691          * varchar constants too...
2692          */
2693         if (datatype == NAMEOID)
2694                 return DirectFunctionCall1(namein, CStringGetDatum(str));
2695         else if (datatype == BYTEAOID)
2696                 return DirectFunctionCall1(byteain, CStringGetDatum(str));
2697         else
2698                 return DirectFunctionCall1(textin, CStringGetDatum(str));
2699 }
2700
2701 /*
2702  * Generate a Const node of the appropriate type from a C string.
2703  */
2704 static Const *
2705 string_to_const(const char *str, Oid datatype)
2706 {
2707         Datum           conval = string_to_datum(str, datatype);
2708
2709         return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2710                                          conval, false, false);
2711 }