src/backend/optimizer/util/restrictinfo.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * restrictinfo.c
   4  *        RestrictInfo node manipulation routines.
   5  *
   6  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL$
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "optimizer/clauses.h"
  18 #include "optimizer/cost.h"
  19 #include "optimizer/paths.h"
  20 #include "optimizer/predtest.h"
  21 #include "optimizer/restrictinfo.h"
  22 #include "optimizer/var.h"
  23
  24
  25 static RestrictInfo *make_restrictinfo_internal(Expr *clause,
  26                                                    Expr *orclause,
  27                                                    bool is_pushed_down,
  28                                                    bool outerjoin_delayed,
  29                                                    bool pseudoconstant,
  30                                                    Relids required_relids,
  31                                                    Relids nullable_relids);
  32 static Expr *make_sub_restrictinfos(Expr *clause,
  33                                            bool is_pushed_down,
  34                                            bool outerjoin_delayed,
  35                                            bool pseudoconstant,
  36                                            Relids required_relids,
  37                                            Relids nullable_relids);
  38 static List *select_nonredundant_join_list(List *restrictinfo_list,
  39                                                           List *reference_list);
  40 static bool join_clause_is_redundant(RestrictInfo *rinfo,
  41                                                  List *reference_list);
  42
  43
  44 /*
  45  * make_restrictinfo
  46  *
  47  * Build a RestrictInfo node containing the given subexpression.
  48  *
  49  * The is_pushed_down, outerjoin_delayed, and pseudoconstant flags for the
  50  * RestrictInfo must be supplied by the caller, as well as the correct value
  51  * for nullable_relids.  required_relids can be NULL, in which case it
  52  * defaults to the actual clause contents (i.e., clause_relids).
  53  *
  54  * We initialize fields that depend only on the given subexpression, leaving
  55  * others that depend on context (or may never be needed at all) to be filled
  56  * later.
  57  */
  58 RestrictInfo *
  59 make_restrictinfo(Expr *clause,
  60                                   bool is_pushed_down,
  61                                   bool outerjoin_delayed,
  62                                   bool pseudoconstant,
  63                                   Relids required_relids,
  64                                   Relids nullable_relids)
  65 {
  66         /*
  67          * If it's an OR clause, build a modified copy with RestrictInfos inserted
  68          * above each subclause of the top-level AND/OR structure.
  69          */
  70         if (or_clause((Node *) clause))
  71                 return (RestrictInfo *) make_sub_restrictinfos(clause,
  72                                                                                                            is_pushed_down,
  73                                                                                                            outerjoin_delayed,
  74                                                                                                            pseudoconstant,
  75                                                                                                            required_relids,
  76                                                                                                            nullable_relids);
  77
  78         /* Shouldn't be an AND clause, else AND/OR flattening messed up */
  79         Assert(!and_clause((Node *) clause));
  80
  81         return make_restrictinfo_internal(clause,
  82                                                                           NULL,
  83                                                                           is_pushed_down,
  84                                                                           outerjoin_delayed,
  85                                                                           pseudoconstant,
  86                                                                           required_relids,
  87                                                                           nullable_relids);
  88 }
  89
  90 /*
  91  * make_restrictinfo_from_bitmapqual
  92  *
  93  * Given the bitmapqual Path structure for a bitmap indexscan, generate
  94  * RestrictInfo node(s) equivalent to the condition represented by the
  95  * indexclauses of the Path structure.
  96  *
  97  * The result is a List (effectively, implicit-AND representation) of
  98  * RestrictInfos.
  99  *
 100  * The caller must pass is_pushed_down, but we assume outerjoin_delayed
 101  * and pseudoconstant are false and nullable_relids is NULL (no other
 102  * kind of qual should ever get into a bitmapqual).
 103  *
 104  * If include_predicates is true, we add any partial index predicates to
 105  * the explicit index quals.  When this is not true, we return a condition
 106  * that might be weaker than the actual scan represents.
 107  *
 108  * To do this through the normal make_restrictinfo() API, callers would have
 109  * to strip off the RestrictInfo nodes present in the indexclauses lists, and
 110  * then make_restrictinfo() would have to build new ones.  It's better to have
 111  * a specialized routine to allow sharing of RestrictInfos.
 112  *
 113  * The qual manipulations here are much the same as in create_bitmap_subplan;
 114  * keep the two routines in sync!
 115  */
 116 List *
 117 make_restrictinfo_from_bitmapqual(Path *bitmapqual,
 118                                                                   bool is_pushed_down,
 119                                                                   bool include_predicates)
 120 {
 121         List       *result;
 122         ListCell   *l;
 123
 124         if (IsA(bitmapqual, BitmapAndPath))
 125         {
 126                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
 127
 128                 /*
 129                  * There may well be redundant quals among the subplans, since a
 130                  * top-level WHERE qual might have gotten used to form several
 131                  * different index quals.  We don't try exceedingly hard to eliminate
 132                  * redundancies, but we do eliminate obvious duplicates by using
 133                  * list_concat_unique.
 134                  */
 135                 result = NIL;
 136                 foreach(l, apath->bitmapquals)
 137                 {
 138                         List       *sublist;
 139
 140                         sublist = make_restrictinfo_from_bitmapqual((Path *) lfirst(l),
 141                                                                                                                 is_pushed_down,
 142                                                                                                                 include_predicates);
 143                         result = list_concat_unique(result, sublist);
 144                 }
 145         }
 146         else if (IsA(bitmapqual, BitmapOrPath))
 147         {
 148                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
 149                 List       *withris = NIL;
 150                 List       *withoutris = NIL;
 151
 152                 /*
 153                  * Here, we only detect qual-free subplans.  A qual-free subplan would
 154                  * cause us to generate "... OR true ..."  which we may as well reduce
 155                  * to just "true".      We do not try to eliminate redundant subclauses
 156                  * because (a) it's not as likely as in the AND case, and (b) we might
 157                  * well be working with hundreds or even thousands of OR conditions,
 158                  * perhaps from a long IN list.  The performance of list_append_unique
 159                  * would be unacceptable.
 160                  */
 161                 foreach(l, opath->bitmapquals)
 162                 {
 163                         List       *sublist;
 164
 165                         sublist = make_restrictinfo_from_bitmapqual((Path *) lfirst(l),
 166                                                                                                                 is_pushed_down,
 167                                                                                                                 include_predicates);
 168                         if (sublist == NIL)
 169                         {
 170                                 /*
 171                                  * If we find a qual-less subscan, it represents a constant
 172                                  * TRUE, and hence the OR result is also constant TRUE, so we
 173                                  * can stop here.
 174                                  */
 175                                 return NIL;
 176                         }
 177
 178                         /*
 179                          * If the sublist contains multiple RestrictInfos, we create an
 180                          * AND subclause.  If there's just one, we have to check if it's
 181                          * an OR clause, and if so flatten it to preserve AND/OR flatness
 182                          * of our output.
 183                          *
 184                          * We construct lists with and without sub-RestrictInfos, so as
 185                          * not to have to regenerate duplicate RestrictInfos below.
 186                          */
 187                         if (list_length(sublist) > 1)
 188                         {
 189                                 withris = lappend(withris, make_andclause(sublist));
 190                                 sublist = get_actual_clauses(sublist);
 191                                 withoutris = lappend(withoutris, make_andclause(sublist));
 192                         }
 193                         else
 194                         {
 195                                 RestrictInfo *subri = (RestrictInfo *) linitial(sublist);
 196
 197                                 Assert(IsA(subri, RestrictInfo));
 198                                 if (restriction_is_or_clause(subri))
 199                                 {
 200                                         BoolExpr   *subor = (BoolExpr *) subri->orclause;
 201
 202                                         Assert(or_clause((Node *) subor));
 203                                         withris = list_concat(withris,
 204                                                                                   list_copy(subor->args));
 205                                         subor = (BoolExpr *) subri->clause;
 206                                         Assert(or_clause((Node *) subor));
 207                                         withoutris = list_concat(withoutris,
 208                                                                                          list_copy(subor->args));
 209                                 }
 210                                 else
 211                                 {
 212                                         withris = lappend(withris, subri);
 213                                         withoutris = lappend(withoutris, subri->clause);
 214                                 }
 215                         }
 216                 }
 217
 218                 /*
 219                  * Avoid generating one-element ORs, which could happen due to
 220                  * redundancy elimination or ScalarArrayOpExpr quals.
 221                  */
 222                 if (list_length(withris) <= 1)
 223                         result = withris;
 224                 else
 225                 {
 226                         /* Here's the magic part not available to outside callers */
 227                         result =
 228                                 list_make1(make_restrictinfo_internal(make_orclause(withoutris),
 229                                                                                                           make_orclause(withris),
 230                                                                                                           is_pushed_down,
 231                                                                                                           false,
 232                                                                                                           false,
 233                                                                                                           NULL,
 234                                                                                                           NULL));
 235                 }
 236         }
 237         else if (IsA(bitmapqual, IndexPath))
 238         {
 239                 IndexPath  *ipath = (IndexPath *) bitmapqual;
 240
 241                 result = list_copy(ipath->indexclauses);
 242                 if (include_predicates && ipath->indexinfo->indpred != NIL)
 243                 {
 244                         foreach(l, ipath->indexinfo->indpred)
 245                         {
 246                                 Expr       *pred = (Expr *) lfirst(l);
 247
 248                                 /*
 249                                  * We know that the index predicate must have been implied by
 250                                  * the query condition as a whole, but it may or may not be
 251                                  * implied by the conditions that got pushed into the
 252                                  * bitmapqual.  Avoid generating redundant conditions.
 253                                  */
 254                                 if (!predicate_implied_by(list_make1(pred), result))
 255                                         result = lappend(result,
 256                                                                          make_restrictinfo(pred,
 257                                                                                                            is_pushed_down,
 258                                                                                                            false,
 259                                                                                                            false,
 260                                                                                                            NULL,
 261                                                                                                            NULL));
 262                         }
 263                 }
 264         }
 265         else
 266         {
 267                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
 268                 result = NIL;                   /* keep compiler quiet */
 269         }
 270
 271         return result;
 272 }
 273
 274 /*
 275  * make_restrictinfos_from_actual_clauses
 276  *
 277  * Given a list of implicitly-ANDed restriction clauses, produce a list
 278  * of RestrictInfo nodes.  This is used to reconstitute the RestrictInfo
 279  * representation after doing transformations of a list of clauses.
 280  *
 281  * We assume that the clauses are relation-level restrictions and therefore
 282  * we don't have to worry about is_pushed_down, outerjoin_delayed, or
 283  * nullable_relids (these can be assumed true, false, and NULL, respectively).
 284  * We do take care to recognize pseudoconstant clauses properly.
 285  */
 286 List *
 287 make_restrictinfos_from_actual_clauses(PlannerInfo *root,
 288                                                                            List *clause_list)
 289 {
 290         List       *result = NIL;
 291         ListCell   *l;
 292
 293         foreach(l, clause_list)
 294         {
 295                 Expr   *clause = (Expr *) lfirst(l);
 296                 bool    pseudoconstant;
 297                 RestrictInfo *rinfo;
 298
 299                 /*
 300                  * It's pseudoconstant if it contains no Vars and no volatile
 301                  * functions.  We probably can't see any sublinks here, so
 302                  * contain_var_clause() would likely be enough, but for safety
 303                  * use contain_vars_of_level() instead.
 304                  */
 305                 pseudoconstant =
 306                         !contain_vars_of_level((Node *) clause, 0) &&
 307                         !contain_volatile_functions((Node *) clause);
 308                 if (pseudoconstant)
 309                 {
 310                         /* tell createplan.c to check for gating quals */
 311                         root->hasPseudoConstantQuals = true;
 312                 }
 313
 314                 rinfo = make_restrictinfo(clause,
 315                                                                   true,
 316                                                                   false,
 317                                                                   pseudoconstant,
 318                                                                   NULL,
 319                                                                   NULL);
 320                 result = lappend(result, rinfo);
 321         }
 322         return result;
 323 }
 324
 325 /*
 326  * make_restrictinfo_internal
 327  *
 328  * Common code for the main entry points and the recursive cases.
 329  */
 330 static RestrictInfo *
 331 make_restrictinfo_internal(Expr *clause,
 332                                                    Expr *orclause,
 333                                                    bool is_pushed_down,
 334                                                    bool outerjoin_delayed,
 335                                                    bool pseudoconstant,
 336                                                    Relids required_relids,
 337                                                    Relids nullable_relids)
 338 {
 339         RestrictInfo *restrictinfo = makeNode(RestrictInfo);
 340
 341         restrictinfo->clause = clause;
 342         restrictinfo->orclause = orclause;
 343         restrictinfo->is_pushed_down = is_pushed_down;
 344         restrictinfo->outerjoin_delayed = outerjoin_delayed;
 345         restrictinfo->pseudoconstant = pseudoconstant;
 346         restrictinfo->can_join = false;         /* may get set below */
 347         restrictinfo->nullable_relids = nullable_relids;
 348
 349         /*
 350          * If it's a binary opclause, set up left/right relids info. In any case
 351          * set up the total clause relids info.
 352          */
 353         if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
 354         {
 355                 restrictinfo->left_relids = pull_varnos(get_leftop(clause));
 356                 restrictinfo->right_relids = pull_varnos(get_rightop(clause));
 357
 358                 restrictinfo->clause_relids = bms_union(restrictinfo->left_relids,
 359                                                                                                 restrictinfo->right_relids);
 360
 361                 /*
 362                  * Does it look like a normal join clause, i.e., a binary operator
 363                  * relating expressions that come from distinct relations? If so we
 364                  * might be able to use it in a join algorithm.  Note that this is a
 365                  * purely syntactic test that is made regardless of context.
 366                  */
 367                 if (!bms_is_empty(restrictinfo->left_relids) &&
 368                         !bms_is_empty(restrictinfo->right_relids) &&
 369                         !bms_overlap(restrictinfo->left_relids,
 370                                                  restrictinfo->right_relids))
 371                 {
 372                         restrictinfo->can_join = true;
 373                         /* pseudoconstant should certainly not be true */
 374                         Assert(!restrictinfo->pseudoconstant);
 375                 }
 376         }
 377         else
 378         {
 379                 /* Not a binary opclause, so mark left/right relid sets as empty */
 380                 restrictinfo->left_relids = NULL;
 381                 restrictinfo->right_relids = NULL;
 382                 /* and get the total relid set the hard way */
 383                 restrictinfo->clause_relids = pull_varnos((Node *) clause);
 384         }
 385
 386         /* required_relids defaults to clause_relids */
 387         if (required_relids != NULL)
 388                 restrictinfo->required_relids = required_relids;
 389         else
 390                 restrictinfo->required_relids = restrictinfo->clause_relids;
 391
 392         /*
 393          * Fill in all the cacheable fields with "not yet set" markers. None of
 394          * these will be computed until/unless needed.  Note in particular that we
 395          * don't mark a binary opclause as mergejoinable or hashjoinable here;
 396          * that happens only if it appears in the right context (top level of a
 397          * joinclause list).
 398          */
 399         restrictinfo->parent_ec = NULL;
 400
 401         restrictinfo->eval_cost.startup = -1;
 402         restrictinfo->norm_selec = -1;
 403         restrictinfo->outer_selec = -1;
 404
 405         restrictinfo->mergeopfamilies = NIL;
 406
 407         restrictinfo->left_ec = NULL;
 408         restrictinfo->right_ec = NULL;
 409         restrictinfo->left_em = NULL;
 410         restrictinfo->right_em = NULL;
 411         restrictinfo->scansel_cache = NIL;
 412
 413         restrictinfo->outer_is_left = false;
 414
 415         restrictinfo->hashjoinoperator = InvalidOid;
 416
 417         restrictinfo->left_bucketsize = -1;
 418         restrictinfo->right_bucketsize = -1;
 419
 420         return restrictinfo;
 421 }
 422
 423 /*
 424  * Recursively insert sub-RestrictInfo nodes into a boolean expression.
 425  *
 426  * We put RestrictInfos above simple (non-AND/OR) clauses and above
 427  * sub-OR clauses, but not above sub-AND clauses, because there's no need.
 428  * This may seem odd but it is closely related to the fact that we use
 429  * implicit-AND lists at top level of RestrictInfo lists.  Only ORs and
 430  * simple clauses are valid RestrictInfos.
 431  *
 432  * The same is_pushed_down, outerjoin_delayed, and pseudoconstant flag
 433  * values can be applied to all RestrictInfo nodes in the result.  Likewise
 434  * for nullable_relids.
 435  *
 436  * The given required_relids are attached to our top-level output,
 437  * but any OR-clause constituents are allowed to default to just the
 438  * contained rels.
 439  */
 440 static Expr *
 441 make_sub_restrictinfos(Expr *clause,
 442                                            bool is_pushed_down,
 443                                            bool outerjoin_delayed,
 444                                            bool pseudoconstant,
 445                                            Relids required_relids,
 446                                            Relids nullable_relids)
 447 {
 448         if (or_clause((Node *) clause))
 449         {
 450                 List       *orlist = NIL;
 451                 ListCell   *temp;
 452
 453                 foreach(temp, ((BoolExpr *) clause)->args)
 454                         orlist = lappend(orlist,
 455                                                          make_sub_restrictinfos(lfirst(temp),
 456                                                                                                         is_pushed_down,
 457                                                                                                         outerjoin_delayed,
 458                                                                                                         pseudoconstant,
 459                                                                                                         NULL,
 460                                                                                                         nullable_relids));
 461                 return (Expr *) make_restrictinfo_internal(clause,
 462                                                                                                    make_orclause(orlist),
 463                                                                                                    is_pushed_down,
 464                                                                                                    outerjoin_delayed,
 465                                                                                                    pseudoconstant,
 466                                                                                                    required_relids,
 467                                                                                                    nullable_relids);
 468         }
 469         else if (and_clause((Node *) clause))
 470         {
 471                 List       *andlist = NIL;
 472                 ListCell   *temp;
 473
 474                 foreach(temp, ((BoolExpr *) clause)->args)
 475                         andlist = lappend(andlist,
 476                                                           make_sub_restrictinfos(lfirst(temp),
 477                                                                                                          is_pushed_down,
 478                                                                                                          outerjoin_delayed,
 479                                                                                                          pseudoconstant,
 480                                                                                                          required_relids,
 481                                                                                                          nullable_relids));
 482                 return make_andclause(andlist);
 483         }
 484         else
 485                 return (Expr *) make_restrictinfo_internal(clause,
 486                                                                                                    NULL,
 487                                                                                                    is_pushed_down,
 488                                                                                                    outerjoin_delayed,
 489                                                                                                    pseudoconstant,
 490                                                                                                    required_relids,
 491                                                                                                    nullable_relids);
 492 }
 493
 494 /*
 495  * restriction_is_or_clause
 496  *
 497  * Returns t iff the restrictinfo node contains an 'or' clause.
 498  */
 499 bool
 500 restriction_is_or_clause(RestrictInfo *restrictinfo)
 501 {
 502         if (restrictinfo->orclause != NULL)
 503                 return true;
 504         else
 505                 return false;
 506 }
 507
 508 /*
 509  * get_actual_clauses
 510  *
 511  * Returns a list containing the bare clauses from 'restrictinfo_list'.
 512  *
 513  * This is only to be used in cases where none of the RestrictInfos can
 514  * be pseudoconstant clauses (for instance, it's OK on indexqual lists).
 515  */
 516 List *
 517 get_actual_clauses(List *restrictinfo_list)
 518 {
 519         List       *result = NIL;
 520         ListCell   *l;
 521
 522         foreach(l, restrictinfo_list)
 523         {
 524                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 525
 526                 Assert(IsA(rinfo, RestrictInfo));
 527
 528                 Assert(!rinfo->pseudoconstant);
 529
 530                 result = lappend(result, rinfo->clause);
 531         }
 532         return result;
 533 }
 534
 535 /*
 536  * get_all_actual_clauses
 537  *
 538  * Returns a list containing the bare clauses from 'restrictinfo_list'.
 539  *
 540  * This loses the distinction between regular and pseudoconstant clauses,
 541  * so be careful what you use it for.
 542  */
 543 List *
 544 get_all_actual_clauses(List *restrictinfo_list)
 545 {
 546         List       *result = NIL;
 547         ListCell   *l;
 548
 549         foreach(l, restrictinfo_list)
 550         {
 551                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 552
 553                 Assert(IsA(rinfo, RestrictInfo));
 554
 555                 result = lappend(result, rinfo->clause);
 556         }
 557         return result;
 558 }
 559
 560 /*
 561  * extract_actual_clauses
 562  *
 563  * Extract bare clauses from 'restrictinfo_list', returning either the
 564  * regular ones or the pseudoconstant ones per 'pseudoconstant'.
 565  */
 566 List *
 567 extract_actual_clauses(List *restrictinfo_list,
 568                                            bool pseudoconstant)
 569 {
 570         List       *result = NIL;
 571         ListCell   *l;
 572
 573         foreach(l, restrictinfo_list)
 574         {
 575                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 576
 577                 Assert(IsA(rinfo, RestrictInfo));
 578
 579                 if (rinfo->pseudoconstant == pseudoconstant)
 580                         result = lappend(result, rinfo->clause);
 581         }
 582         return result;
 583 }
 584
 585 /*
 586  * extract_actual_join_clauses
 587  *
 588  * Extract bare clauses from 'restrictinfo_list', separating those that
 589  * syntactically match the join level from those that were pushed down.
 590  * Pseudoconstant clauses are excluded from the results.
 591  *
 592  * This is only used at outer joins, since for plain joins we don't care
 593  * about pushed-down-ness.
 594  */
 595 void
 596 extract_actual_join_clauses(List *restrictinfo_list,
 597                                                         List **joinquals,
 598                                                         List **otherquals)
 599 {
 600         ListCell   *l;
 601
 602         *joinquals = NIL;
 603         *otherquals = NIL;
 604
 605         foreach(l, restrictinfo_list)
 606         {
 607                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 608
 609                 Assert(IsA(rinfo, RestrictInfo));
 610
 611                 if (rinfo->is_pushed_down)
 612                 {
 613                         if (!rinfo->pseudoconstant)
 614                                 *otherquals = lappend(*otherquals, rinfo->clause);
 615                 }
 616                 else
 617                 {
 618                         /* joinquals shouldn't have been marked pseudoconstant */
 619                         Assert(!rinfo->pseudoconstant);
 620                         *joinquals = lappend(*joinquals, rinfo->clause);
 621                 }
 622         }
 623 }
 624
 625
 626 /*
 627  * select_nonredundant_join_clauses
 628  *
 629  * Given a list of RestrictInfo clauses that are to be applied in a join,
 630  * select the ones that are not redundant with any clause that's enforced
 631  * by the inner_path.  This is used for nestloop joins, wherein any clause
 632  * being used in an inner indexscan need not be checked again at the join.
 633  *
 634  * "Redundant" means either equal() or derived from the same EquivalenceClass.
 635  * We have to check the latter because indxqual.c may select different derived
 636  * clauses than were selected by generate_join_implied_equalities().
 637  *
 638  * Note that we are *not* checking for local redundancies within the given
 639  * restrictinfo_list; that should have been handled elsewhere.
 640  */
 641 List *
 642 select_nonredundant_join_clauses(PlannerInfo *root,
 643                                                                  List *restrictinfo_list,
 644                                                                  Path *inner_path)
 645 {
 646         if (IsA(inner_path, IndexPath))
 647         {
 648                 /*
 649                  * Check the index quals to see if any of them are join clauses.
 650                  *
 651                  * We can skip this if the index path is an ordinary indexpath and not
 652                  * a special innerjoin path, since it then wouldn't be using any join
 653                  * clauses.
 654                  */
 655                 IndexPath  *innerpath = (IndexPath *) inner_path;
 656
 657                 if (innerpath->isjoininner)
 658                         restrictinfo_list =
 659                                 select_nonredundant_join_list(restrictinfo_list,
 660                                                                                           innerpath->indexclauses);
 661         }
 662         else if (IsA(inner_path, BitmapHeapPath))
 663         {
 664                 /*
 665                  * Same deal for bitmapped index scans.
 666                  *
 667                  * Note: both here and above, we ignore any implicit index
 668                  * restrictions associated with the use of partial indexes.  This is
 669                  * OK because we're only trying to prove we can dispense with some
 670                  * join quals; failing to prove that doesn't result in an incorrect
 671                  * plan.  It's quite unlikely that a join qual could be proven
 672                  * redundant by an index predicate anyway.      (Also, if we did manage to
 673                  * prove it, we'd have to have a special case for update targets; see
 674                  * notes about EvalPlanQual testing in create_indexscan_plan().)
 675                  */
 676                 BitmapHeapPath *innerpath = (BitmapHeapPath *) inner_path;
 677
 678                 if (innerpath->isjoininner)
 679                 {
 680                         List       *bitmapclauses;
 681
 682                         bitmapclauses =
 683                                 make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
 684                                                                                                   true,
 685                                                                                                   false);
 686                         restrictinfo_list =
 687                                 select_nonredundant_join_list(restrictinfo_list,
 688                                                                                           bitmapclauses);
 689                 }
 690         }
 691
 692         /*
 693          * XXX the inner path of a nestloop could also be an append relation whose
 694          * elements use join quals.  However, they might each use different quals;
 695          * we could only remove join quals that are enforced by all the appendrel
 696          * members.  For the moment we don't bother to try.
 697          */
 698
 699         return restrictinfo_list;
 700 }
 701
 702 /*
 703  * select_nonredundant_join_list
 704  *              Select the members of restrictinfo_list that are not redundant with
 705  *              any member of reference_list.  See above for more info.
 706  */
 707 static List *
 708 select_nonredundant_join_list(List *restrictinfo_list,
 709                                                           List *reference_list)
 710 {
 711         List       *result = NIL;
 712         ListCell   *item;
 713
 714         foreach(item, restrictinfo_list)
 715         {
 716                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
 717
 718                 /* drop it if redundant with any reference clause */
 719                 if (join_clause_is_redundant(rinfo, reference_list))
 720                         continue;
 721
 722                 /* otherwise, add it to result list */
 723                 result = lappend(result, rinfo);
 724         }
 725
 726         return result;
 727 }
 728
 729 /*
 730  * join_clause_is_redundant
 731  *              Test whether rinfo is redundant with any clause in reference_list.
 732  */
 733 static bool
 734 join_clause_is_redundant(RestrictInfo *rinfo,
 735                                                  List *reference_list)
 736 {
 737         ListCell   *refitem;
 738
 739         foreach(refitem, reference_list)
 740         {
 741                 RestrictInfo *refrinfo = (RestrictInfo *) lfirst(refitem);
 742
 743                 /* always consider exact duplicates redundant */
 744                 if (equal(rinfo, refrinfo))
 745                         return true;
 746
 747                 /* check if derived from same EquivalenceClass */
 748                 if (rinfo->parent_ec != NULL &&
 749                         rinfo->parent_ec == refrinfo->parent_ec)
 750                         return true;
 751         }
 752
 753         return false;
 754 }