src/backend/optimizer/util/restrictinfo.c

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