src/backend/optimizer/plan/initsplan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * initsplan.c
   4  *        Target list, qualification, joininfo initialization 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/plan/initsplan.c,v 1.124 2006/12/07 19:33:40 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "catalog/pg_operator.h"
  18 #include "catalog/pg_type.h"
  19 #include "optimizer/clauses.h"
  20 #include "optimizer/cost.h"
  21 #include "optimizer/joininfo.h"
  22 #include "optimizer/pathnode.h"
  23 #include "optimizer/paths.h"
  24 #include "optimizer/planmain.h"
  25 #include "optimizer/prep.h"
  26 #include "optimizer/restrictinfo.h"
  27 #include "optimizer/var.h"
  28 #include "parser/parse_expr.h"
  29 #include "parser/parse_oper.h"
  30 #include "utils/builtins.h"
  31 #include "utils/lsyscache.h"
  32 #include "utils/syscache.h"
  33
  34
  35 /* These parameters are set by GUC */
  36 int                     from_collapse_limit;
  37 int                     join_collapse_limit;
  38
  39
  40 static void add_vars_to_targetlist(PlannerInfo *root, List *vars,
  41                                            Relids where_needed);
  42 static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
  43                                         bool below_outer_join, Relids *qualscope);
  44 static OuterJoinInfo *make_outerjoininfo(PlannerInfo *root,
  45                                    Relids left_rels, Relids right_rels,
  46                                    bool is_full_join, Node *clause);
  47 static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
  48                                                 bool is_pushed_down,
  49                                                 bool is_deduced,
  50                                                 bool below_outer_join,
  51                                                 Relids qualscope,
  52                                                 Relids ojscope,
  53                                                 Relids outerjoin_nonnullable);
  54 static bool qual_is_redundant(PlannerInfo *root, RestrictInfo *restrictinfo,
  55                                   List *restrictlist);
  56 static void check_mergejoinable(RestrictInfo *restrictinfo);
  57 static void check_hashjoinable(RestrictInfo *restrictinfo);
  58
  59
  60 /*****************************************************************************
  61  *
  62  *       JOIN TREES
  63  *
  64  *****************************************************************************/
  65
  66 /*
  67  * add_base_rels_to_query
  68  *
  69  *        Scan the query's jointree and create baserel RelOptInfos for all
  70  *        the base relations (ie, table, subquery, and function RTEs)
  71  *        appearing in the jointree.
  72  *
  73  * The initial invocation must pass root->parse->jointree as the value of
  74  * jtnode.      Internally, the function recurses through the jointree.
  75  *
  76  * At the end of this process, there should be one baserel RelOptInfo for
  77  * every non-join RTE that is used in the query.  Therefore, this routine
  78  * is the only place that should call build_simple_rel with reloptkind
  79  * RELOPT_BASEREL.      (Note: build_simple_rel recurses internally to build
  80  * "other rel" RelOptInfos for the members of any appendrels we find here.)
  81  */
  82 void
  83 add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
  84 {
  85         if (jtnode == NULL)
  86                 return;
  87         if (IsA(jtnode, RangeTblRef))
  88         {
  89                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
  90
  91                 (void) build_simple_rel(root, varno, RELOPT_BASEREL);
  92         }
  93         else if (IsA(jtnode, FromExpr))
  94         {
  95                 FromExpr   *f = (FromExpr *) jtnode;
  96                 ListCell   *l;
  97
  98                 foreach(l, f->fromlist)
  99                         add_base_rels_to_query(root, lfirst(l));
 100         }
 101         else if (IsA(jtnode, JoinExpr))
 102         {
 103                 JoinExpr   *j = (JoinExpr *) jtnode;
 104
 105                 add_base_rels_to_query(root, j->larg);
 106                 add_base_rels_to_query(root, j->rarg);
 107         }
 108         else
 109                 elog(ERROR, "unrecognized node type: %d",
 110                          (int) nodeTag(jtnode));
 111 }
 112
 113
 114 /*****************************************************************************
 115  *
 116  *       TARGET LISTS
 117  *
 118  *****************************************************************************/
 119
 120 /*
 121  * build_base_rel_tlists
 122  *        Add targetlist entries for each var needed in the query's final tlist
 123  *        to the appropriate base relations.
 124  *
 125  * We mark such vars as needed by "relation 0" to ensure that they will
 126  * propagate up through all join plan steps.
 127  */
 128 void
 129 build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
 130 {
 131         List       *tlist_vars = pull_var_clause((Node *) final_tlist, false);
 132
 133         if (tlist_vars != NIL)
 134         {
 135                 add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
 136                 list_free(tlist_vars);
 137         }
 138 }
 139
 140 /*
 141  * add_vars_to_targetlist
 142  *        For each variable appearing in the list, add it to the owning
 143  *        relation's targetlist if not already present, and mark the variable
 144  *        as being needed for the indicated join (or for final output if
 145  *        where_needed includes "relation 0").
 146  */
 147 static void
 148 add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
 149 {
 150         ListCell   *temp;
 151
 152         Assert(!bms_is_empty(where_needed));
 153
 154         foreach(temp, vars)
 155         {
 156                 Var                *var = (Var *) lfirst(temp);
 157                 RelOptInfo *rel = find_base_rel(root, var->varno);
 158                 int                     attrno = var->varattno;
 159
 160                 Assert(attrno >= rel->min_attr && attrno <= rel->max_attr);
 161                 attrno -= rel->min_attr;
 162                 if (bms_is_empty(rel->attr_needed[attrno]))
 163                 {
 164                         /* Variable not yet requested, so add to reltargetlist */
 165                         /* XXX is copyObject necessary here? */
 166                         rel->reltargetlist = lappend(rel->reltargetlist, copyObject(var));
 167                 }
 168                 rel->attr_needed[attrno] = bms_add_members(rel->attr_needed[attrno],
 169                                                                                                    where_needed);
 170         }
 171 }
 172
 173
 174 /*****************************************************************************
 175  *
 176  *        JOIN TREE PROCESSING
 177  *
 178  *****************************************************************************/
 179
 180 /*
 181  * deconstruct_jointree
 182  *        Recursively scan the query's join tree for WHERE and JOIN/ON qual
 183  *        clauses, and add these to the appropriate restrictinfo and joininfo
 184  *        lists belonging to base RelOptInfos.  Also, add OuterJoinInfo nodes
 185  *        to root->oj_info_list for any outer joins appearing in the query tree.
 186  *        Return a "joinlist" data structure showing the join order decisions
 187  *        that need to be made by make_one_rel().
 188  *
 189  * The "joinlist" result is a list of items that are either RangeTblRef
 190  * jointree nodes or sub-joinlists.  All the items at the same level of
 191  * joinlist must be joined in an order to be determined by make_one_rel()
 192  * (note that legal orders may be constrained by OuterJoinInfo nodes).
 193  * A sub-joinlist represents a subproblem to be planned separately. Currently
 194  * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
 195  * subproblems is stopped by join_collapse_limit or from_collapse_limit.
 196  *
 197  * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
 198  * be evaluated at the lowest level where all the variables it mentions are
 199  * available.  However, we cannot push a qual down into the nullable side(s)
 200  * of an outer join since the qual might eliminate matching rows and cause a
 201  * NULL row to be incorrectly emitted by the join.      Therefore, we artificially
 202  * OR the minimum-relids of such an outer join into the required_relids of
 203  * clauses appearing above it.  This forces those clauses to be delayed until
 204  * application of the outer join (or maybe even higher in the join tree).
 205  */
 206 List *
 207 deconstruct_jointree(PlannerInfo *root)
 208 {
 209         Relids          qualscope;
 210
 211         /* Start recursion at top of jointree */
 212         Assert(root->parse->jointree != NULL &&
 213                    IsA(root->parse->jointree, FromExpr));
 214
 215         return deconstruct_recurse(root, (Node *) root->parse->jointree, false,
 216                                                            &qualscope);
 217 }
 218
 219 /*
 220  * deconstruct_recurse
 221  *        One recursion level of deconstruct_jointree processing.
 222  *
 223  * Inputs:
 224  *      jtnode is the jointree node to examine
 225  *      below_outer_join is TRUE if this node is within the nullable side of a
 226  *              higher-level outer join
 227  * Outputs:
 228  *      *qualscope gets the set of base Relids syntactically included in this
 229  *              jointree node (do not modify or free this, as it may also be pointed
 230  *              to by RestrictInfo nodes)
 231  *      Return value is the appropriate joinlist for this jointree node
 232  *
 233  * In addition, entries will be added to root->oj_info_list for outer joins.
 234  */
 235 static List *
 236 deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 237                                         Relids *qualscope)
 238 {
 239         List       *joinlist;
 240
 241         if (jtnode == NULL)
 242         {
 243                 *qualscope = NULL;
 244                 return NIL;
 245         }
 246         if (IsA(jtnode, RangeTblRef))
 247         {
 248                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 249
 250                 /* No quals to deal with, just return correct result */
 251                 *qualscope = bms_make_singleton(varno);
 252                 joinlist = list_make1(jtnode);
 253         }
 254         else if (IsA(jtnode, FromExpr))
 255         {
 256                 FromExpr   *f = (FromExpr *) jtnode;
 257                 int                     remaining;
 258                 ListCell   *l;
 259
 260                 /*
 261                  * First, recurse to handle child joins.  We collapse subproblems into
 262                  * a single joinlist whenever the resulting joinlist wouldn't exceed
 263                  * from_collapse_limit members.  Also, always collapse one-element
 264                  * subproblems, since that won't lengthen the joinlist anyway.
 265                  */
 266                 *qualscope = NULL;
 267                 joinlist = NIL;
 268                 remaining = list_length(f->fromlist);
 269                 foreach(l, f->fromlist)
 270                 {
 271                         Relids          sub_qualscope;
 272                         List       *sub_joinlist;
 273                         int                     sub_members;
 274
 275                         sub_joinlist = deconstruct_recurse(root, lfirst(l),
 276                                                                                            below_outer_join,
 277                                                                                            &sub_qualscope);
 278                         *qualscope = bms_add_members(*qualscope, sub_qualscope);
 279                         sub_members = list_length(sub_joinlist);
 280                         remaining--;
 281                         if (sub_members <= 1 ||
 282                                 list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
 283                                 joinlist = list_concat(joinlist, sub_joinlist);
 284                         else
 285                                 joinlist = lappend(joinlist, sub_joinlist);
 286                 }
 287
 288                 /*
 289                  * Now process the top-level quals.  These are always marked as
 290                  * "pushed down", since they clearly didn't come from a JOIN expr.
 291                  */
 292                 foreach(l, (List *) f->quals)
 293                         distribute_qual_to_rels(root, (Node *) lfirst(l),
 294                                                                         true, false, below_outer_join,
 295                                                                         *qualscope, NULL, NULL);
 296         }
 297         else if (IsA(jtnode, JoinExpr))
 298         {
 299                 JoinExpr   *j = (JoinExpr *) jtnode;
 300                 Relids          leftids,
 301                                         rightids,
 302                                         nonnullable_rels,
 303                                         ojscope;
 304                 List       *leftjoinlist,
 305                                    *rightjoinlist;
 306                 OuterJoinInfo *ojinfo;
 307                 ListCell   *qual;
 308
 309                 /*
 310                  * Order of operations here is subtle and critical.  First we recurse
 311                  * to handle sub-JOINs.  Their join quals will be placed without
 312                  * regard for whether this level is an outer join, which is correct.
 313                  * Then we place our own join quals, which are restricted by lower
 314                  * outer joins in any case, and are forced to this level if this is an
 315                  * outer join and they mention the outer side.  Finally, if this is an
 316                  * outer join, we create an oj_info_list entry for the join.  This
 317                  * will prevent quals above us in the join tree that use those rels
 318                  * from being pushed down below this level.  (It's okay for upper
 319                  * quals to be pushed down to the outer side, however.)
 320                  */
 321                 switch (j->jointype)
 322                 {
 323                         case JOIN_INNER:
 324                                 leftjoinlist = deconstruct_recurse(root, j->larg,
 325                                                                                                    below_outer_join,
 326                                                                                                    &leftids);
 327                                 rightjoinlist = deconstruct_recurse(root, j->rarg,
 328                                                                                                         below_outer_join,
 329                                                                                                         &rightids);
 330                                 *qualscope = bms_union(leftids, rightids);
 331                                 /* Inner join adds no restrictions for quals */
 332                                 nonnullable_rels = NULL;
 333                                 break;
 334                         case JOIN_LEFT:
 335                                 leftjoinlist = deconstruct_recurse(root, j->larg,
 336                                                                                                    below_outer_join,
 337                                                                                                    &leftids);
 338                                 rightjoinlist = deconstruct_recurse(root, j->rarg,
 339                                                                                                         true,
 340                                                                                                         &rightids);
 341                                 *qualscope = bms_union(leftids, rightids);
 342                                 nonnullable_rels = leftids;
 343                                 break;
 344                         case JOIN_FULL:
 345                                 leftjoinlist = deconstruct_recurse(root, j->larg,
 346                                                                                                    true,
 347                                                                                                    &leftids);
 348                                 rightjoinlist = deconstruct_recurse(root, j->rarg,
 349                                                                                                         true,
 350                                                                                                         &rightids);
 351                                 *qualscope = bms_union(leftids, rightids);
 352                                 /* each side is both outer and inner */
 353                                 nonnullable_rels = *qualscope;
 354                                 break;
 355                         case JOIN_RIGHT:
 356                                 /* notice we switch leftids and rightids */
 357                                 leftjoinlist = deconstruct_recurse(root, j->larg,
 358                                                                                                    true,
 359                                                                                                    &rightids);
 360                                 rightjoinlist = deconstruct_recurse(root, j->rarg,
 361                                                                                                         below_outer_join,
 362                                                                                                         &leftids);
 363                                 *qualscope = bms_union(leftids, rightids);
 364                                 nonnullable_rels = leftids;
 365                                 break;
 366                         default:
 367                                 elog(ERROR, "unrecognized join type: %d",
 368                                          (int) j->jointype);
 369                                 nonnullable_rels = NULL;                /* keep compiler quiet */
 370                                 leftjoinlist = rightjoinlist = NIL;
 371                                 break;
 372                 }
 373
 374                 /*
 375                  * For an OJ, form the OuterJoinInfo now, because we need the OJ's
 376                  * semantic scope (ojscope) to pass to distribute_qual_to_rels.
 377                  */
 378                 if (j->jointype != JOIN_INNER)
 379                 {
 380                         ojinfo = make_outerjoininfo(root, leftids, rightids,
 381                                                                                 (j->jointype == JOIN_FULL), j->quals);
 382                         ojscope = bms_union(ojinfo->min_lefthand, ojinfo->min_righthand);
 383                 }
 384                 else
 385                 {
 386                         ojinfo = NULL;
 387                         ojscope = NULL;
 388                 }
 389
 390                 /* Process the qual clauses */
 391                 foreach(qual, (List *) j->quals)
 392                         distribute_qual_to_rels(root, (Node *) lfirst(qual),
 393                                                                         false, false, below_outer_join,
 394                                                                         *qualscope, ojscope, nonnullable_rels);
 395
 396                 /* Now we can add the OuterJoinInfo to oj_info_list */
 397                 if (ojinfo)
 398                         root->oj_info_list = lappend(root->oj_info_list, ojinfo);
 399
 400                 /*
 401                  * Finally, compute the output joinlist.  We fold subproblems together
 402                  * except at a FULL JOIN or where join_collapse_limit would be
 403                  * exceeded.
 404                  */
 405                 if (j->jointype != JOIN_FULL &&
 406                         (list_length(leftjoinlist) + list_length(rightjoinlist) <=
 407                          join_collapse_limit))
 408                         joinlist = list_concat(leftjoinlist, rightjoinlist);
 409                 else
 410                         /* force the join order at this node */
 411                         joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
 412         }
 413         else
 414         {
 415                 elog(ERROR, "unrecognized node type: %d",
 416                          (int) nodeTag(jtnode));
 417                 joinlist = NIL;                 /* keep compiler quiet */
 418         }
 419         return joinlist;
 420 }
 421
 422 /*
 423  * make_outerjoininfo
 424  *        Build an OuterJoinInfo for the current outer join
 425  *
 426  * Inputs:
 427  *      left_rels: the base Relids syntactically on outer side of join
 428  *      right_rels: the base Relids syntactically on inner side of join
 429  *      is_full_join: what it says
 430  *      clause: the outer join's join condition
 431  *
 432  * If the join is a RIGHT JOIN, left_rels and right_rels are switched by
 433  * the caller, so that left_rels is always the nonnullable side.  Hence
 434  * we need only distinguish the LEFT and FULL cases.
 435  *
 436  * The node should eventually be put into root->oj_info_list, but we
 437  * do not do that here.
 438  */
 439 static OuterJoinInfo *
 440 make_outerjoininfo(PlannerInfo *root,
 441                                    Relids left_rels, Relids right_rels,
 442                                    bool is_full_join, Node *clause)
 443 {
 444         OuterJoinInfo *ojinfo = makeNode(OuterJoinInfo);
 445         Relids          clause_relids;
 446         Relids          strict_relids;
 447         ListCell   *l;
 448
 449         /*
 450          * Presently the executor cannot support FOR UPDATE/SHARE marking of rels
 451          * appearing on the nullable side of an outer join. (It's somewhat unclear
 452          * what that would mean, anyway: what should we mark when a result row is
 453          * generated from no element of the nullable relation?)  So, complain if
 454          * any nullable rel is FOR UPDATE/SHARE.
 455          *
 456          * You might be wondering why this test isn't made far upstream in the
 457          * parser.      It's because the parser hasn't got enough info --- consider
 458          * FOR UPDATE applied to a view.  Only after rewriting and flattening do
 459          * we know whether the view contains an outer join.
 460          */
 461         foreach(l, root->parse->rowMarks)
 462         {
 463                 RowMarkClause *rc = (RowMarkClause *) lfirst(l);
 464
 465                 if (bms_is_member(rc->rti, right_rels) ||
 466                         (is_full_join && bms_is_member(rc->rti, left_rels)))
 467                         ereport(ERROR,
 468                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 469                                          errmsg("SELECT FOR UPDATE/SHARE cannot be applied to the nullable side of an outer join")));
 470         }
 471
 472         /* If it's a full join, no need to be very smart */
 473         ojinfo->is_full_join = is_full_join;
 474         if (is_full_join)
 475         {
 476                 ojinfo->min_lefthand = left_rels;
 477                 ojinfo->min_righthand = right_rels;
 478                 ojinfo->lhs_strict = false;             /* don't care about this */
 479                 return ojinfo;
 480         }
 481
 482         /*
 483          * Retrieve all relids mentioned within the join clause.
 484          */
 485         clause_relids = pull_varnos(clause);
 486
 487         /*
 488          * For which relids is the clause strict, ie, it cannot succeed if the
 489          * rel's columns are all NULL?
 490          */
 491         strict_relids = find_nonnullable_rels(clause);
 492
 493         /* Remember whether the clause is strict for any LHS relations */
 494         ojinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
 495
 496         /*
 497          * Required LHS is basically the LHS rels mentioned in the clause... but
 498          * if there aren't any, punt and make it the full LHS, to avoid having an
 499          * empty min_lefthand which will confuse later processing. (We don't try
 500          * to be smart about such cases, just correct.) We may have to add more
 501          * rels based on lower outer joins; see below.
 502          */
 503         ojinfo->min_lefthand = bms_intersect(clause_relids, left_rels);
 504         if (bms_is_empty(ojinfo->min_lefthand))
 505                 ojinfo->min_lefthand = bms_copy(left_rels);
 506
 507         /*
 508          * Required RHS is normally the full set of RHS rels.  Sometimes we can
 509          * exclude some, see below.
 510          */
 511         ojinfo->min_righthand = bms_copy(right_rels);
 512
 513         foreach(l, root->oj_info_list)
 514         {
 515                 OuterJoinInfo *otherinfo = (OuterJoinInfo *) lfirst(l);
 516
 517                 /* ignore full joins --- other mechanisms preserve their ordering */
 518                 if (otherinfo->is_full_join)
 519                         continue;
 520
 521                 /*
 522                  * For a lower OJ in our LHS, if our join condition uses the lower
 523                  * join's RHS and is not strict for that rel, we must preserve the
 524                  * ordering of the two OJs, so add lower OJ's full required relset to
 525                  * min_lefthand.
 526                  */
 527                 if (bms_overlap(ojinfo->min_lefthand, otherinfo->min_righthand) &&
 528                         !bms_overlap(strict_relids, otherinfo->min_righthand))
 529                 {
 530                         ojinfo->min_lefthand = bms_add_members(ojinfo->min_lefthand,
 531                                                                                                    otherinfo->min_lefthand);
 532                         ojinfo->min_lefthand = bms_add_members(ojinfo->min_lefthand,
 533                                                                                                    otherinfo->min_righthand);
 534                 }
 535
 536                 /*
 537                  * For a lower OJ in our RHS, if our join condition does not use the
 538                  * lower join's RHS and the lower OJ's join condition is strict, we
 539                  * can interchange the ordering of the two OJs, so exclude the lower
 540                  * RHS from our min_righthand.
 541                  */
 542                 if (bms_overlap(ojinfo->min_righthand, otherinfo->min_righthand) &&
 543                         !bms_overlap(clause_relids, otherinfo->min_righthand) &&
 544                         otherinfo->lhs_strict)
 545                 {
 546                         ojinfo->min_righthand = bms_del_members(ojinfo->min_righthand,
 547                                                                                                         otherinfo->min_righthand);
 548                 }
 549         }
 550
 551         /* Neither set should be empty, else we might get confused later */
 552         Assert(!bms_is_empty(ojinfo->min_lefthand));
 553         Assert(!bms_is_empty(ojinfo->min_righthand));
 554         /* Shouldn't overlap either */
 555         Assert(!bms_overlap(ojinfo->min_lefthand, ojinfo->min_righthand));
 556
 557         return ojinfo;
 558 }
 559
 560
 561 /*****************************************************************************
 562  *
 563  *        QUALIFICATIONS
 564  *
 565  *****************************************************************************/
 566
 567 /*
 568  * distribute_qual_to_rels
 569  *        Add clause information to either the baserestrictinfo or joininfo list
 570  *        (depending on whether the clause is a join) of each base relation
 571  *        mentioned in the clause.      A RestrictInfo node is created and added to
 572  *        the appropriate list for each rel.  Also, if the clause uses a
 573  *        mergejoinable operator and is not delayed by outer-join rules, enter
 574  *        the left- and right-side expressions into the query's lists of
 575  *        equijoined vars.
 576  *
 577  * 'clause': the qual clause to be distributed
 578  * 'is_pushed_down': if TRUE, force the clause to be marked 'is_pushed_down'
 579  *              (this indicates the clause came from a FromExpr, not a JoinExpr)
 580  * 'is_deduced': TRUE if the qual came from implied-equality deduction
 581  * 'below_outer_join': TRUE if the qual is from a JOIN/ON that is below the
 582  *              nullable side of a higher-level outer join.
 583  * 'qualscope': set of baserels the qual's syntactic scope covers
 584  * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels
 585  *              needed to form this join
 586  * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
 587  *              baserels appearing on the outer (nonnullable) side of the join
 588  *              (for FULL JOIN this includes both sides of the join, and must in fact
 589  *              equal qualscope)
 590  *
 591  * 'qualscope' identifies what level of JOIN the qual came from syntactically.
 592  * 'ojscope' is needed if we decide to force the qual up to the outer-join
 593  * level, which will be ojscope not necessarily qualscope.
 594  */
 595 static void
 596 distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 597                                                 bool is_pushed_down,
 598                                                 bool is_deduced,
 599                                                 bool below_outer_join,
 600                                                 Relids qualscope,
 601                                                 Relids ojscope,
 602                                                 Relids outerjoin_nonnullable)
 603 {
 604         Relids          relids;
 605         bool            outerjoin_delayed;
 606         bool            pseudoconstant = false;
 607         bool            maybe_equijoin;
 608         bool            maybe_outer_join;
 609         RestrictInfo *restrictinfo;
 610         RelOptInfo *rel;
 611         List       *vars;
 612
 613         /*
 614          * Retrieve all relids mentioned within the clause.
 615          */
 616         relids = pull_varnos(clause);
 617
 618         /*
 619          * Cross-check: clause should contain no relids not within its scope.
 620          * Otherwise the parser messed up.
 621          */
 622         if (!bms_is_subset(relids, qualscope))
 623                 elog(ERROR, "JOIN qualification may not refer to other relations");
 624         if (ojscope && !bms_is_subset(relids, ojscope))
 625                 elog(ERROR, "JOIN qualification may not refer to other relations");
 626
 627         /*
 628          * If the clause is variable-free, our normal heuristic for pushing it
 629          * down to just the mentioned rels doesn't work, because there are none.
 630          *
 631          * If the clause is an outer-join clause, we must force it to the OJ's
 632          * semantic level to preserve semantics.
 633          *
 634          * Otherwise, when the clause contains volatile functions, we force it to
 635          * be evaluated at its original syntactic level.  This preserves the
 636          * expected semantics.
 637          *
 638          * When the clause contains no volatile functions either, it is actually a
 639          * pseudoconstant clause that will not change value during any one
 640          * execution of the plan, and hence can be used as a one-time qual in a
 641          * gating Result plan node.  We put such a clause into the regular
 642          * RestrictInfo lists for the moment, but eventually createplan.c will
 643          * pull it out and make a gating Result node immediately above whatever
 644          * plan node the pseudoconstant clause is assigned to.  It's usually best
 645          * to put a gating node as high in the plan tree as possible. If we are
 646          * not below an outer join, we can actually push the pseudoconstant qual
 647          * all the way to the top of the tree.  If we are below an outer join, we
 648          * leave the qual at its original syntactic level (we could push it up to
 649          * just below the outer join, but that seems more complex than it's
 650          * worth).
 651          */
 652         if (bms_is_empty(relids))
 653         {
 654                 if (ojscope)
 655                 {
 656                         /* clause is attached to outer join, eval it there */
 657                         relids = ojscope;
 658                         /* mustn't use as gating qual, so don't mark pseudoconstant */
 659                 }
 660                 else
 661                 {
 662                         /* eval at original syntactic level */
 663                         relids = qualscope;
 664                         if (!contain_volatile_functions(clause))
 665                         {
 666                                 /* mark as gating qual */
 667                                 pseudoconstant = true;
 668                                 /* tell createplan.c to check for gating quals */
 669                                 root->hasPseudoConstantQuals = true;
 670                                 /* if not below outer join, push it to top of tree */
 671                                 if (!below_outer_join)
 672                                 {
 673                                         relids = get_relids_in_jointree((Node *) root->parse->jointree);
 674                                         is_pushed_down = true;
 675                                 }
 676                         }
 677                 }
 678         }
 679
 680         /*
 681          * Check to see if clause application must be delayed by outer-join
 682          * considerations.
 683          */
 684         if (is_deduced)
 685         {
 686                 /*
 687                  * If the qual came from implied-equality deduction, we always
 688                  * evaluate the qual at its natural semantic level.  It is the
 689                  * responsibility of the deducer not to create any quals that should
 690                  * be delayed by outer-join rules.
 691                  */
 692                 Assert(bms_equal(relids, qualscope));
 693                 Assert(!ojscope);
 694                 Assert(!pseudoconstant);
 695                 /* Needn't feed it back for more deductions */
 696                 outerjoin_delayed = false;
 697                 maybe_equijoin = false;
 698                 maybe_outer_join = false;
 699         }
 700         else if (bms_overlap(relids, outerjoin_nonnullable))
 701         {
 702                 /*
 703                  * The qual is attached to an outer join and mentions (some of the)
 704                  * rels on the nonnullable side.  Force the qual to be evaluated
 705                  * exactly at the level of joining corresponding to the outer join. We
 706                  * cannot let it get pushed down into the nonnullable side, since then
 707                  * we'd produce no output rows, rather than the intended single
 708                  * null-extended row, for any nonnullable-side rows failing the qual.
 709                  *
 710                  * Note: an outer-join qual that mentions only nullable-side rels can
 711                  * be pushed down into the nullable side without changing the join
 712                  * result, so we treat it the same as an ordinary inner-join qual,
 713                  * except for not setting maybe_equijoin (see below).
 714                  */
 715                 Assert(ojscope);
 716                 relids = ojscope;
 717                 outerjoin_delayed = true;
 718                 Assert(!pseudoconstant);
 719
 720                 /*
 721                  * We can't use such a clause to deduce equijoin (the left and right
 722                  * sides might be unequal above the join because one of them has gone
 723                  * to NULL) ... but we might be able to use it for more limited
 724                  * purposes.  Note: for the current uses of deductions from an
 725                  * outer-join clause, it seems safe to make the deductions even when
 726                  * the clause is below a higher-level outer join; so we do not check
 727                  * below_outer_join here.
 728                  */
 729                 maybe_equijoin = false;
 730                 maybe_outer_join = true;
 731         }
 732         else
 733         {
 734                 /*
 735                  * For a non-outer-join qual, we can evaluate the qual as soon as (1)
 736                  * we have all the rels it mentions, and (2) we are at or above any
 737                  * outer joins that can null any of these rels and are below the
 738                  * syntactic location of the given qual.  We must enforce (2) because
 739                  * pushing down such a clause below the OJ might cause the OJ to emit
 740                  * null-extended rows that should not have been formed, or that should
 741                  * have been rejected by the clause.  (This is only an issue for
 742                  * non-strict quals, since if we can prove a qual mentioning only
 743                  * nullable rels is strict, we'd have reduced the outer join to an
 744                  * inner join in reduce_outer_joins().)
 745                  *
 746                  * To enforce (2), scan the oj_info_list and merge the required-relid
 747                  * sets of any such OJs into the clause's own reference list.  At the
 748                  * time we are called, the oj_info_list contains only outer joins
 749                  * below this qual.  We have to repeat the scan until no new relids
 750                  * get added; this ensures that the qual is suitably delayed regardless
 751                  * of the order in which OJs get executed.  As an example, if we have
 752                  * one OJ with LHS=A, RHS=B, and one with LHS=B, RHS=C, it is implied
 753                  * that these can be done in either order; if the B/C join is done
 754                  * first then the join to A can null C, so a qual actually mentioning
 755                  * only C cannot be applied below the join to A.
 756                  */
 757                 bool            found_some;
 758
 759                 outerjoin_delayed = false;
 760                 do {
 761                         ListCell   *l;
 762
 763                         found_some = false;
 764                         foreach(l, root->oj_info_list)
 765                         {
 766                                 OuterJoinInfo *ojinfo = (OuterJoinInfo *) lfirst(l);
 767
 768                                 /* do we have any nullable rels of this OJ? */
 769                                 if (bms_overlap(relids, ojinfo->min_righthand) ||
 770                                         (ojinfo->is_full_join &&
 771                                          bms_overlap(relids, ojinfo->min_lefthand)))
 772                                 {
 773                                         /* yes; do we have all its rels? */
 774                                         if (!bms_is_subset(ojinfo->min_lefthand, relids) ||
 775                                                 !bms_is_subset(ojinfo->min_righthand, relids))
 776                                         {
 777                                                 /* no, so add them in */
 778                                                 relids = bms_add_members(relids,
 779                                                                                                  ojinfo->min_lefthand);
 780                                                 relids = bms_add_members(relids,
 781                                                                                                  ojinfo->min_righthand);
 782                                                 outerjoin_delayed = true;
 783                                                 /* we'll need another iteration */
 784                                                 found_some = true;
 785                                         }
 786                                 }
 787                         }
 788                 } while (found_some);
 789
 790                 if (outerjoin_delayed)
 791                 {
 792                         /* Should still be a subset of current scope ... */
 793                         Assert(bms_is_subset(relids, qualscope));
 794                         /*
 795                          * Because application of the qual will be delayed by outer join,
 796                          * we mustn't assume its vars are equal everywhere.
 797                          */
 798                         maybe_equijoin = false;
 799                 }
 800                 else
 801                 {
 802                         /*
 803                          * Qual is not delayed by any lower outer-join restriction. If it
 804                          * is not itself below or within an outer join, we can consider it
 805                          * "valid everywhere", so consider feeding it to the equijoin
 806                          * machinery.  (If it is within an outer join, we can't consider
 807                          * it "valid everywhere": once the contained variables have gone
 808                          * to NULL, we'd be asserting things like NULL = NULL, which is
 809                          * not true.)
 810                          */
 811                         if (!below_outer_join && outerjoin_nonnullable == NULL)
 812                                 maybe_equijoin = true;
 813                         else
 814                                 maybe_equijoin = false;
 815                 }
 816
 817                 /* Since it doesn't mention the LHS, it's certainly not an OJ clause */
 818                 maybe_outer_join = false;
 819         }
 820
 821         /*
 822          * Mark the qual as "pushed down" if it can be applied at a level below
 823          * its original syntactic level.  This allows us to distinguish original
 824          * JOIN/ON quals from higher-level quals pushed down to the same joinrel.
 825          * A qual originating from WHERE is always considered "pushed down". Note
 826          * that for an outer-join qual, we have to compare to ojscope not
 827          * qualscope.
 828          */
 829         if (!is_pushed_down)
 830                 is_pushed_down = !bms_equal(relids, ojscope ? ojscope : qualscope);
 831
 832         /*
 833          * Build the RestrictInfo node itself.
 834          */
 835         restrictinfo = make_restrictinfo((Expr *) clause,
 836                                                                          is_pushed_down,
 837                                                                          outerjoin_delayed,
 838                                                                          pseudoconstant,
 839                                                                          relids);
 840
 841         /*
 842          * Figure out where to attach it.
 843          */
 844         switch (bms_membership(relids))
 845         {
 846                 case BMS_SINGLETON:
 847
 848                         /*
 849                          * There is only one relation participating in 'clause', so
 850                          * 'clause' is a restriction clause for that relation.
 851                          */
 852                         rel = find_base_rel(root, bms_singleton_member(relids));
 853
 854                         /*
 855                          * Check for a "mergejoinable" clause even though it's not a join
 856                          * clause.      This is so that we can recognize that "a.x = a.y"
 857                          * makes x and y eligible to be considered equal, even when they
 858                          * belong to the same rel.      Without this, we would not recognize
 859                          * that "a.x = a.y AND a.x = b.z AND a.y = c.q" allows us to
 860                          * consider z and q equal after their rels are joined.
 861                          */
 862                         check_mergejoinable(restrictinfo);
 863
 864                         /*
 865                          * If the clause was deduced from implied equality, check to see
 866                          * whether it is redundant with restriction clauses we already
 867                          * have for this rel.  Note we cannot apply this check to
 868                          * user-written clauses, since we haven't found the canonical
 869                          * pathkey sets yet while processing user clauses. (NB: no
 870                          * comparable check is done in the join-clause case; redundancy
 871                          * will be detected when the join clause is moved into a join
 872                          * rel's restriction list.)
 873                          */
 874                         if (!is_deduced ||
 875                                 !qual_is_redundant(root, restrictinfo,
 876                                                                    rel->baserestrictinfo))
 877                         {
 878                                 /* Add clause to rel's restriction list */
 879                                 rel->baserestrictinfo = lappend(rel->baserestrictinfo,
 880                                                                                                 restrictinfo);
 881                         }
 882                         break;
 883                 case BMS_MULTIPLE:
 884
 885                         /*
 886                          * 'clause' is a join clause, since there is more than one rel in
 887                          * the relid set.
 888                          */
 889
 890                         /*
 891                          * Check for hash or mergejoinable operators.
 892                          *
 893                          * We don't bother setting the hashjoin info if we're not going to
 894                          * need it.  We do want to know about mergejoinable ops in all
 895                          * cases, however, because we use mergejoinable ops for other
 896                          * purposes such as detecting redundant clauses.
 897                          */
 898                         check_mergejoinable(restrictinfo);
 899                         if (enable_hashjoin)
 900                                 check_hashjoinable(restrictinfo);
 901
 902                         /*
 903                          * Add clause to the join lists of all the relevant relations.
 904                          */
 905                         add_join_clause_to_rels(root, restrictinfo, relids);
 906
 907                         /*
 908                          * Add vars used in the join clause to targetlists of their
 909                          * relations, so that they will be emitted by the plan nodes that
 910                          * scan those relations (else they won't be available at the join
 911                          * node!).
 912                          */
 913                         vars = pull_var_clause(clause, false);
 914                         add_vars_to_targetlist(root, vars, relids);
 915                         list_free(vars);
 916                         break;
 917                 default:
 918
 919                         /*
 920                          * 'clause' references no rels, and therefore we have no place to
 921                          * attach it.  Shouldn't get here if callers are working properly.
 922                          */
 923                         elog(ERROR, "cannot cope with variable-free clause");
 924                         break;
 925         }
 926
 927         /*
 928          * If the clause has a mergejoinable operator, we may be able to deduce
 929          * more things from it under the principle of transitivity.
 930          *
 931          * If it is not an outer-join qualification nor bubbled up due to an outer
 932          * join, then the two sides represent equivalent PathKeyItems for path
 933          * keys: any path that is sorted by one side will also be sorted by the
 934          * other (as soon as the two rels are joined, that is).  Pass such clauses
 935          * to add_equijoined_keys.
 936          *
 937          * If it is a left or right outer-join qualification that relates the two
 938          * sides of the outer join (no funny business like leftvar1 = leftvar2 +
 939          * rightvar), we add it to root->left_join_clauses or
 940          * root->right_join_clauses according to which side the nonnullable
 941          * variable appears on.
 942          *
 943          * If it is a full outer-join qualification, we add it to
 944          * root->full_join_clauses.  (Ideally we'd discard cases that aren't
 945          * leftvar = rightvar, as we do for left/right joins, but this routine
 946          * doesn't have the info needed to do that; and the current usage of the
 947          * full_join_clauses list doesn't require that, so it's not currently
 948          * worth complicating this routine's API to make it possible.)
 949          */
 950         if (restrictinfo->mergejoinoperator != InvalidOid)
 951         {
 952                 if (maybe_equijoin)
 953                         add_equijoined_keys(root, restrictinfo);
 954                 else if (maybe_outer_join && restrictinfo->can_join)
 955                 {
 956                         if (bms_is_subset(restrictinfo->left_relids,
 957                                                           outerjoin_nonnullable) &&
 958                                 !bms_overlap(restrictinfo->right_relids,
 959                                                          outerjoin_nonnullable))
 960                         {
 961                                 /* we have outervar = innervar */
 962                                 root->left_join_clauses = lappend(root->left_join_clauses,
 963                                                                                                   restrictinfo);
 964                         }
 965                         else if (bms_is_subset(restrictinfo->right_relids,
 966                                                                    outerjoin_nonnullable) &&
 967                                          !bms_overlap(restrictinfo->left_relids,
 968                                                                   outerjoin_nonnullable))
 969                         {
 970                                 /* we have innervar = outervar */
 971                                 root->right_join_clauses = lappend(root->right_join_clauses,
 972                                                                                                    restrictinfo);
 973                         }
 974                         else if (bms_equal(outerjoin_nonnullable, qualscope))
 975                         {
 976                                 /* FULL JOIN (above tests cannot match in this case) */
 977                                 root->full_join_clauses = lappend(root->full_join_clauses,
 978                                                                                                   restrictinfo);
 979                         }
 980                 }
 981         }
 982 }
 983
 984 /*
 985  * process_implied_equality
 986  *        Check to see whether we already have a restrictinfo item that says
 987  *        item1 = item2, and create one if not; or if delete_it is true,
 988  *        remove any such restrictinfo item.
 989  *
 990  * This processing is a consequence of transitivity of mergejoin equality:
 991  * if we have mergejoinable clauses A = B and B = C, we can deduce A = C
 992  * (where = is an appropriate mergejoinable operator).  See path/pathkeys.c
 993  * for more details.
 994  */
 995 void
 996 process_implied_equality(PlannerInfo *root,
 997                                                  Node *item1, Node *item2,
 998                                                  Oid sortop1, Oid sortop2,
 999                                                  Relids item1_relids, Relids item2_relids,
1000                                                  bool delete_it)
1001 {
1002         Relids          relids;
1003         BMS_Membership membership;
1004         RelOptInfo *rel1;
1005         List       *restrictlist;
1006         ListCell   *itm;
1007         Oid                     ltype,
1008                                 rtype;
1009         Operator        eq_operator;
1010         Form_pg_operator pgopform;
1011         Expr       *clause;
1012
1013         /* Get set of relids referenced in the two expressions */
1014         relids = bms_union(item1_relids, item2_relids);
1015         membership = bms_membership(relids);
1016
1017         /*
1018          * generate_implied_equalities() shouldn't call me on two constants.
1019          */
1020         Assert(membership != BMS_EMPTY_SET);
1021
1022         /*
1023          * If the exprs involve a single rel, we need to look at that rel's
1024          * baserestrictinfo list.  If multiple rels, we can scan the joininfo list
1025          * of any of 'em.
1026          */
1027         if (membership == BMS_SINGLETON)
1028         {
1029                 rel1 = find_base_rel(root, bms_singleton_member(relids));
1030                 restrictlist = rel1->baserestrictinfo;
1031         }
1032         else
1033         {
1034                 Relids          other_rels;
1035                 int                     first_rel;
1036
1037                 /* Copy relids, find and remove one member */
1038                 other_rels = bms_copy(relids);
1039                 first_rel = bms_first_member(other_rels);
1040                 bms_free(other_rels);
1041
1042                 rel1 = find_base_rel(root, first_rel);
1043                 restrictlist = rel1->joininfo;
1044         }
1045
1046         /*
1047          * Scan to see if equality is already known.  If so, we're done in the add
1048          * case, and done after removing it in the delete case.
1049          */
1050         foreach(itm, restrictlist)
1051         {
1052                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
1053                 Node       *left,
1054                                    *right;
1055
1056                 if (restrictinfo->mergejoinoperator == InvalidOid)
1057                         continue;                       /* ignore non-mergejoinable clauses */
1058                 /* We now know the restrictinfo clause is a binary opclause */
1059                 left = get_leftop(restrictinfo->clause);
1060                 right = get_rightop(restrictinfo->clause);
1061                 if ((equal(item1, left) && equal(item2, right)) ||
1062                         (equal(item2, left) && equal(item1, right)))
1063                 {
1064                         /* found a matching clause */
1065                         if (delete_it)
1066                         {
1067                                 if (membership == BMS_SINGLETON)
1068                                 {
1069                                         /* delete it from local restrictinfo list */
1070                                         rel1->baserestrictinfo = list_delete_ptr(rel1->baserestrictinfo,
1071                                                                                                                          restrictinfo);
1072                                 }
1073                                 else
1074                                 {
1075                                         /* let joininfo.c do it */
1076                                         remove_join_clause_from_rels(root, restrictinfo, relids);
1077                                 }
1078                         }
1079                         return;                         /* done */
1080                 }
1081         }
1082
1083         /* Didn't find it.  Done if deletion requested */
1084         if (delete_it)
1085                 return;
1086
1087         /*
1088          * This equality is new information, so construct a clause representing it
1089          * to add to the query data structures.
1090          */
1091         ltype = exprType(item1);
1092         rtype = exprType(item2);
1093         eq_operator = compatible_oper(NULL, list_make1(makeString("=")),
1094                                                                   ltype, rtype,
1095                                                                   true, -1);
1096         if (!HeapTupleIsValid(eq_operator))
1097         {
1098                 /*
1099                  * Would it be safe to just not add the equality to the query if we
1100                  * have no suitable equality operator for the combination of
1101                  * datatypes?  NO, because sortkey selection may screw up anyway.
1102                  */
1103                 ereport(ERROR,
1104                                 (errcode(ERRCODE_UNDEFINED_FUNCTION),
1105                 errmsg("could not identify an equality operator for types %s and %s",
1106                            format_type_be(ltype), format_type_be(rtype))));
1107         }
1108         pgopform = (Form_pg_operator) GETSTRUCT(eq_operator);
1109
1110         /*
1111          * Let's just make sure this appears to be a compatible operator.
1112          */
1113         if (pgopform->oprlsortop != sortop1 ||
1114                 pgopform->oprrsortop != sortop2 ||
1115                 pgopform->oprresult != BOOLOID)
1116                 ereport(ERROR,
1117                                 (errcode(ERRCODE_INVALID_FUNCTION_DEFINITION),
1118                                  errmsg("equality operator for types %s and %s should be merge-joinable, but isn't",
1119                                                 format_type_be(ltype), format_type_be(rtype))));
1120
1121         /*
1122          * Now we can build the new clause.  Copy to ensure it shares no
1123          * substructure with original (this is necessary in case there are
1124          * subselects in there...)
1125          */
1126         clause = make_opclause(oprid(eq_operator),      /* opno */
1127                                                    BOOLOID,             /* opresulttype */
1128                                                    false,               /* opretset */
1129                                                    (Expr *) copyObject(item1),
1130                                                    (Expr *) copyObject(item2));
1131
1132         ReleaseSysCache(eq_operator);
1133
1134         /*
1135          * Push the new clause into all the appropriate restrictinfo lists.
1136          *
1137          * Note: we mark the qual "pushed down" to ensure that it can never be
1138          * taken for an original JOIN/ON clause.
1139          */
1140         distribute_qual_to_rels(root, (Node *) clause,
1141                                                         true, true, false, relids, NULL, NULL);
1142 }
1143
1144 /*
1145  * qual_is_redundant
1146  *        Detect whether an implied-equality qual that turns out to be a
1147  *        restriction clause for a single base relation is redundant with
1148  *        already-known restriction clauses for that rel.  This occurs with,
1149  *        for example,
1150  *                              SELECT * FROM tab WHERE f1 = f2 AND f2 = f3;
1151  *        We need to suppress the redundant condition to avoid computing
1152  *        too-small selectivity, not to mention wasting time at execution.
1153  *
1154  * Note: quals of the form "var = const" are never considered redundant,
1155  * only those of the form "var = var".  This is needed because when we
1156  * have constants in an implied-equality set, we use a different strategy
1157  * that suppresses all "var = var" deductions.  We must therefore keep
1158  * all the "var = const" quals.
1159  */
1160 static bool
1161 qual_is_redundant(PlannerInfo *root,
1162                                   RestrictInfo *restrictinfo,
1163                                   List *restrictlist)
1164 {
1165         Node       *newleft;
1166         Node       *newright;
1167         List       *oldquals;
1168         ListCell   *olditem;
1169         List       *equalexprs;
1170         bool            someadded;
1171
1172         /* Never redundant unless vars appear on both sides */
1173         if (bms_is_empty(restrictinfo->left_relids) ||
1174                 bms_is_empty(restrictinfo->right_relids))
1175                 return false;
1176
1177         newleft = get_leftop(restrictinfo->clause);
1178         newright = get_rightop(restrictinfo->clause);
1179
1180         /*
1181          * Set cached pathkeys.  NB: it is okay to do this now because this
1182          * routine is only invoked while we are generating implied equalities.
1183          * Therefore, the equi_key_list is already complete and so we can
1184          * correctly determine canonical pathkeys.
1185          */
1186         cache_mergeclause_pathkeys(root, restrictinfo);
1187         /* If different, say "not redundant" (should never happen) */
1188         if (restrictinfo->left_pathkey != restrictinfo->right_pathkey)
1189                 return false;
1190
1191         /*
1192          * Scan existing quals to find those referencing same pathkeys. Usually
1193          * there will be few, if any, so build a list of just the interesting
1194          * ones.
1195          */
1196         oldquals = NIL;
1197         foreach(olditem, restrictlist)
1198         {
1199                 RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
1200
1201                 if (oldrinfo->mergejoinoperator != InvalidOid)
1202                 {
1203                         cache_mergeclause_pathkeys(root, oldrinfo);
1204                         if (restrictinfo->left_pathkey == oldrinfo->left_pathkey &&
1205                                 restrictinfo->right_pathkey == oldrinfo->right_pathkey)
1206                                 oldquals = lcons(oldrinfo, oldquals);
1207                 }
1208         }
1209         if (oldquals == NIL)
1210                 return false;
1211
1212         /*
1213          * Now, we want to develop a list of exprs that are known equal to the
1214          * left side of the new qual.  We traverse the old-quals list repeatedly
1215          * to transitively expand the exprs list.  If at any point we find we can
1216          * reach the right-side expr of the new qual, we are done.      We give up
1217          * when we can't expand the equalexprs list any more.
1218          */
1219         equalexprs = list_make1(newleft);
1220         do
1221         {
1222                 someadded = false;
1223                 /* cannot use foreach here because of possible list_delete */
1224                 olditem = list_head(oldquals);
1225                 while (olditem)
1226                 {
1227                         RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
1228                         Node       *oldleft = get_leftop(oldrinfo->clause);
1229                         Node       *oldright = get_rightop(oldrinfo->clause);
1230                         Node       *newguy = NULL;
1231
1232                         /* must advance olditem before list_delete possibly pfree's it */
1233                         olditem = lnext(olditem);
1234
1235                         if (list_member(equalexprs, oldleft))
1236                                 newguy = oldright;
1237                         else if (list_member(equalexprs, oldright))
1238                                 newguy = oldleft;
1239                         else
1240                                 continue;
1241                         if (equal(newguy, newright))
1242                                 return true;    /* we proved new clause is redundant */
1243                         equalexprs = lcons(newguy, equalexprs);
1244                         someadded = true;
1245
1246                         /*
1247                          * Remove this qual from list, since we don't need it anymore.
1248                          */
1249                         oldquals = list_delete_ptr(oldquals, oldrinfo);
1250                 }
1251         } while (someadded);
1252
1253         return false;                           /* it's not redundant */
1254 }
1255
1256
1257 /*****************************************************************************
1258  *
1259  *       CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
1260  *
1261  *****************************************************************************/
1262
1263 /*
1264  * check_mergejoinable
1265  *        If the restrictinfo's clause is mergejoinable, set the mergejoin
1266  *        info fields in the restrictinfo.
1267  *
1268  *        Currently, we support mergejoin for binary opclauses where
1269  *        the operator is a mergejoinable operator.  The arguments can be
1270  *        anything --- as long as there are no volatile functions in them.
1271  */
1272 static void
1273 check_mergejoinable(RestrictInfo *restrictinfo)
1274 {
1275         Expr       *clause = restrictinfo->clause;
1276         Oid                     opno,
1277                                 leftOp,
1278                                 rightOp;
1279
1280         if (restrictinfo->pseudoconstant)
1281                 return;
1282         if (!is_opclause(clause))
1283                 return;
1284         if (list_length(((OpExpr *) clause)->args) != 2)
1285                 return;
1286
1287         opno = ((OpExpr *) clause)->opno;
1288
1289         if (op_mergejoinable(opno,
1290                                                  &leftOp,
1291                                                  &rightOp) &&
1292                 !contain_volatile_functions((Node *) clause))
1293         {
1294                 restrictinfo->mergejoinoperator = opno;
1295                 restrictinfo->left_sortop = leftOp;
1296                 restrictinfo->right_sortop = rightOp;
1297         }
1298 }
1299
1300 /*
1301  * check_hashjoinable
1302  *        If the restrictinfo's clause is hashjoinable, set the hashjoin
1303  *        info fields in the restrictinfo.
1304  *
1305  *        Currently, we support hashjoin for binary opclauses where
1306  *        the operator is a hashjoinable operator.      The arguments can be
1307  *        anything --- as long as there are no volatile functions in them.
1308  */
1309 static void
1310 check_hashjoinable(RestrictInfo *restrictinfo)
1311 {
1312         Expr       *clause = restrictinfo->clause;
1313         Oid                     opno;
1314
1315         if (restrictinfo->pseudoconstant)
1316                 return;
1317         if (!is_opclause(clause))
1318                 return;
1319         if (list_length(((OpExpr *) clause)->args) != 2)
1320                 return;
1321
1322         opno = ((OpExpr *) clause)->opno;
1323
1324         if (op_hashjoinable(opno) &&
1325                 !contain_volatile_functions((Node *) clause))
1326                 restrictinfo->hashjoinoperator = opno;
1327 }