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