granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/initsplan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * initsplan.c
   4  *        Target list, qualification, joininfo initialization routines
   5  *
   6  * Portions Copyright (c) 1996-2003, 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.95 2004/01/04 00:07:32 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "catalog/pg_operator.h"
  18 #include "catalog/pg_type.h"
  19 #include "nodes/makefuncs.h"
  20 #include "optimizer/clauses.h"
  21 #include "optimizer/cost.h"
  22 #include "optimizer/joininfo.h"
  23 #include "optimizer/pathnode.h"
  24 #include "optimizer/paths.h"
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/restrictinfo.h"
  27 #include "optimizer/tlist.h"
  28 #include "optimizer/var.h"
  29 #include "parser/parsetree.h"
  30 #include "parser/parse_expr.h"
  31 #include "parser/parse_oper.h"
  32 #include "utils/builtins.h"
  33 #include "utils/lsyscache.h"
  34 #include "utils/syscache.h"
  35
  36
  37 static void mark_baserels_for_outer_join(Query *root, Relids rels,
  38                                                          Relids outerrels);
  39 static void distribute_qual_to_rels(Query *root, Node *clause,
  40                                                 bool ispusheddown,
  41                                                 bool isdeduced,
  42                                                 Relids outerjoin_nonnullable,
  43                                                 Relids qualscope);
  44 static void add_vars_to_targetlist(Query *root, List *vars,
  45                                            Relids where_needed);
  46 static bool qual_is_redundant(Query *root, RestrictInfo *restrictinfo,
  47                                   List *restrictlist);
  48 static void check_mergejoinable(RestrictInfo *restrictinfo);
  49 static void check_hashjoinable(RestrictInfo *restrictinfo);
  50
  51
  52 /*****************************************************************************
  53  *
  54  *       JOIN TREES
  55  *
  56  *****************************************************************************/
  57
  58 /*
  59  * add_base_rels_to_query
  60  *
  61  *        Scan the query's jointree and create baserel RelOptInfos for all
  62  *        the base relations (ie, table, subquery, and function RTEs)
  63  *        appearing in the jointree.
  64  *
  65  * At the end of this process, there should be one baserel RelOptInfo for
  66  * every non-join RTE that is used in the query.  Therefore, this routine
  67  * is the only place that should call build_base_rel.  But build_other_rel
  68  * will be used later to build rels for inheritance children.
  69  */
  70 void
  71 add_base_rels_to_query(Query *root, Node *jtnode)
  72 {
  73         if (jtnode == NULL)
  74                 return;
  75         if (IsA(jtnode, RangeTblRef))
  76         {
  77                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
  78
  79                 build_base_rel(root, varno);
  80         }
  81         else if (IsA(jtnode, FromExpr))
  82         {
  83                 FromExpr   *f = (FromExpr *) jtnode;
  84                 List       *l;
  85
  86                 foreach(l, f->fromlist)
  87                         add_base_rels_to_query(root, lfirst(l));
  88         }
  89         else if (IsA(jtnode, JoinExpr))
  90         {
  91                 JoinExpr   *j = (JoinExpr *) jtnode;
  92
  93                 add_base_rels_to_query(root, j->larg);
  94                 add_base_rels_to_query(root, j->rarg);
  95         }
  96         else
  97                 elog(ERROR, "unrecognized node type: %d",
  98                          (int) nodeTag(jtnode));
  99 }
 100
 101
 102 /*****************************************************************************
 103  *
 104  *       TARGET LISTS
 105  *
 106  *****************************************************************************/
 107
 108 /*
 109  * build_base_rel_tlists
 110  *        Add targetlist entries for each var needed in the query's final tlist
 111  *        to the appropriate base relations.
 112  *
 113  * We mark such vars as needed by "relation 0" to ensure that they will
 114  * propagate up through all join plan steps.
 115  */
 116 void
 117 build_base_rel_tlists(Query *root, List *final_tlist)
 118 {
 119         List       *tlist_vars = pull_var_clause((Node *) final_tlist, false);
 120
 121         if (tlist_vars != NIL)
 122         {
 123                 add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
 124                 freeList(tlist_vars);
 125         }
 126 }
 127
 128 /*
 129  * add_vars_to_targetlist
 130  *        For each variable appearing in the list, add it to the owning
 131  *        relation's targetlist if not already present, and mark the variable
 132  *        as being needed for the indicated join (or for final output if
 133  *        where_needed includes "relation 0").
 134  */
 135 static void
 136 add_vars_to_targetlist(Query *root, List *vars, Relids where_needed)
 137 {
 138         List       *temp;
 139
 140         Assert(!bms_is_empty(where_needed));
 141
 142         foreach(temp, vars)
 143         {
 144                 Var                *var = (Var *) lfirst(temp);
 145                 RelOptInfo *rel = find_base_rel(root, var->varno);
 146                 int                     attrno = var->varattno;
 147
 148                 Assert(attrno >= rel->min_attr && attrno <= rel->max_attr);
 149                 attrno -= rel->min_attr;
 150                 if (bms_is_empty(rel->attr_needed[attrno]))
 151                 {
 152                         /* Variable not yet requested, so add to reltargetlist */
 153                         /* XXX is copyObject necessary here? */
 154                         FastAppend(&rel->reltargetlist, copyObject(var));
 155                 }
 156                 rel->attr_needed[attrno] = bms_add_members(rel->attr_needed[attrno],
 157                                                                                                    where_needed);
 158         }
 159 }
 160
 161
 162 /*****************************************************************************
 163  *
 164  *        QUALIFICATIONS
 165  *
 166  *****************************************************************************/
 167
 168
 169 /*
 170  * distribute_quals_to_rels
 171  *        Recursively scan the query's join tree for WHERE and JOIN/ON qual
 172  *        clauses, and add these to the appropriate RestrictInfo and JoinInfo
 173  *        lists belonging to base RelOptInfos.  Also, base RelOptInfos are marked
 174  *        with outerjoinset information, to aid in proper positioning of qual
 175  *        clauses that appear above outer joins.
 176  *
 177  * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
 178  * be evaluated at the lowest level where all the variables it mentions are
 179  * available.  However, we cannot push a qual down into the nullable side(s)
 180  * of an outer join since the qual might eliminate matching rows and cause a
 181  * NULL row to be incorrectly emitted by the join.      Therefore, rels appearing
 182  * within the nullable side(s) of an outer join are marked with
 183  *              outerjoinset = set of Relids used at the outer join node.
 184  * This set will be added to the set of rels referenced by quals using such
 185  * a rel, thereby forcing them up the join tree to the right level.
 186  *
 187  * To ease the calculation of these values, distribute_quals_to_rels() returns
 188  * the set of base Relids involved in its own level of join.  This is just an
 189  * internal convenience; no outside callers pay attention to the result.
 190  */
 191 Relids
 192 distribute_quals_to_rels(Query *root, Node *jtnode)
 193 {
 194         Relids          result = NULL;
 195
 196         if (jtnode == NULL)
 197                 return result;
 198         if (IsA(jtnode, RangeTblRef))
 199         {
 200                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 201
 202                 /* No quals to deal with, just return correct result */
 203                 result = bms_make_singleton(varno);
 204         }
 205         else if (IsA(jtnode, FromExpr))
 206         {
 207                 FromExpr   *f = (FromExpr *) jtnode;
 208                 List       *l;
 209                 List       *qual;
 210
 211                 /*
 212                  * First, recurse to handle child joins.
 213                  */
 214                 foreach(l, f->fromlist)
 215                 {
 216                         result = bms_add_members(result,
 217                                                                          distribute_quals_to_rels(root,
 218                                                                                                                           lfirst(l)));
 219                 }
 220
 221                 /*
 222                  * Now process the top-level quals.  These are always marked as
 223                  * "pushed down", since they clearly didn't come from a JOIN expr.
 224                  */
 225                 foreach(qual, (List *) f->quals)
 226                         distribute_qual_to_rels(root, (Node *) lfirst(qual),
 227                                                                         true, false, NULL, result);
 228         }
 229         else if (IsA(jtnode, JoinExpr))
 230         {
 231                 JoinExpr   *j = (JoinExpr *) jtnode;
 232                 Relids          leftids,
 233                                         rightids,
 234                                         nonnullable_rels,
 235                                         nullable_rels;
 236                 List       *qual;
 237
 238                 /*
 239                  * Order of operations here is subtle and critical.  First we
 240                  * recurse to handle sub-JOINs.  Their join quals will be placed
 241                  * without regard for whether this level is an outer join, which
 242                  * is correct.  Then we place our own join quals, which are
 243                  * restricted by lower outer joins in any case, and are forced to
 244                  * this level if this is an outer join and they mention the outer
 245                  * side.  Finally, if this is an outer join, we mark baserels
 246                  * contained within the inner side(s) with our own rel set; this
 247                  * will prevent quals above us in the join tree that use those
 248                  * rels from being pushed down below this level.  (It's okay for
 249                  * upper quals to be pushed down to the outer side, however.)
 250                  */
 251                 leftids = distribute_quals_to_rels(root, j->larg);
 252                 rightids = distribute_quals_to_rels(root, j->rarg);
 253
 254                 result = bms_union(leftids, rightids);
 255
 256                 nonnullable_rels = nullable_rels = NULL;
 257                 switch (j->jointype)
 258                 {
 259                         case JOIN_INNER:
 260                                 /* Inner join adds no restrictions for quals */
 261                                 break;
 262                         case JOIN_LEFT:
 263                                 nonnullable_rels = leftids;
 264                                 nullable_rels = rightids;
 265                                 break;
 266                         case JOIN_FULL:
 267                                 /* each side is both outer and inner */
 268                                 nonnullable_rels = result;
 269                                 nullable_rels = result;
 270                                 break;
 271                         case JOIN_RIGHT:
 272                                 nonnullable_rels = rightids;
 273                                 nullable_rels = leftids;
 274                                 break;
 275                         case JOIN_UNION:
 276
 277                                 /*
 278                                  * This is where we fail if upper levels of planner
 279                                  * haven't rewritten UNION JOIN as an Append ...
 280                                  */
 281                                 ereport(ERROR,
 282                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 283                                                  errmsg("UNION JOIN is not implemented")));
 284                                 break;
 285                         default:
 286                                 elog(ERROR, "unrecognized join type: %d",
 287                                          (int) j->jointype);
 288                                 break;
 289                 }
 290
 291                 foreach(qual, (List *) j->quals)
 292                         distribute_qual_to_rels(root, (Node *) lfirst(qual),
 293                                                                         false, false,
 294                                                                         nonnullable_rels, result);
 295
 296                 if (nullable_rels != NULL)
 297                         mark_baserels_for_outer_join(root, nullable_rels, result);
 298         }
 299         else
 300                 elog(ERROR, "unrecognized node type: %d",
 301                          (int) nodeTag(jtnode));
 302         return result;
 303 }
 304
 305 /*
 306  * mark_baserels_for_outer_join
 307  *        Mark all base rels listed in 'rels' as having the given outerjoinset.
 308  */
 309 static void
 310 mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels)
 311 {
 312         Relids          tmprelids;
 313         int                     relno;
 314
 315         tmprelids = bms_copy(rels);
 316         while ((relno = bms_first_member(tmprelids)) >= 0)
 317         {
 318                 RelOptInfo *rel = find_base_rel(root, relno);
 319
 320                 /*
 321                  * Since we do this bottom-up, any outer-rels previously marked
 322                  * should be within the new outer join set.
 323                  */
 324                 Assert(bms_is_subset(rel->outerjoinset, outerrels));
 325
 326                 /*
 327                  * Presently the executor cannot support FOR UPDATE marking of
 328                  * rels appearing on the nullable side of an outer join. (It's
 329                  * somewhat unclear what that would mean, anyway: what should we
 330                  * mark when a result row is generated from no element of the
 331                  * nullable relation?)  So, complain if target rel is FOR UPDATE.
 332                  * It's sufficient to make this check once per rel, so do it only
 333                  * if rel wasn't already known nullable.
 334                  */
 335                 if (rel->outerjoinset == NULL)
 336                 {
 337                         if (intMember(relno, root->rowMarks))
 338                                 ereport(ERROR,
 339                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 340                                                  errmsg("SELECT FOR UPDATE cannot be applied to the nullable side of an outer join")));
 341                 }
 342
 343                 rel->outerjoinset = outerrels;
 344         }
 345         bms_free(tmprelids);
 346 }
 347
 348 /*
 349  * distribute_qual_to_rels
 350  *        Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
 351  *        (depending on whether the clause is a join) of each base relation
 352  *        mentioned in the clause.      A RestrictInfo node is created and added to
 353  *        the appropriate list for each rel.  Also, if the clause uses a
 354  *        mergejoinable operator and is not delayed by outer-join rules, enter
 355  *        the left- and right-side expressions into the query's lists of
 356  *        equijoined vars.
 357  *
 358  * 'clause': the qual clause to be distributed
 359  * 'ispusheddown': if TRUE, force the clause to be marked 'ispusheddown'
 360  *              (this indicates the clause came from a FromExpr, not a JoinExpr)
 361  * 'isdeduced': TRUE if the qual came from implied-equality deduction
 362  * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
 363  *              baserels appearing on the outer (nonnullable) side of the join
 364  * 'qualscope': set of baserels the qual's syntactic scope covers
 365  *
 366  * 'qualscope' identifies what level of JOIN the qual came from.  For a top
 367  * level qual (WHERE qual), qualscope lists all baserel ids and in addition
 368  * 'ispusheddown' will be TRUE.
 369  */
 370 static void
 371 distribute_qual_to_rels(Query *root, Node *clause,
 372                                                 bool ispusheddown,
 373                                                 bool isdeduced,
 374                                                 Relids outerjoin_nonnullable,
 375                                                 Relids qualscope)
 376 {
 377         Relids          relids;
 378         List       *vars;
 379         bool            can_be_equijoin;
 380         RestrictInfo *restrictinfo;
 381         RelOptInfo *rel;
 382
 383         /*
 384          * Retrieve all relids and vars contained within the clause.
 385          */
 386         clause_get_relids_vars(clause, &relids, &vars);
 387
 388         /*
 389          * Cross-check: clause should contain no relids not within its scope.
 390          * Otherwise the parser messed up.
 391          */
 392         if (!bms_is_subset(relids, qualscope))
 393                 elog(ERROR, "JOIN qualification may not refer to other relations");
 394
 395         /*
 396          * If the clause is variable-free, we force it to be evaluated at its
 397          * original syntactic level.  Note that this should not happen for
 398          * top-level clauses, because query_planner() special-cases them.  But
 399          * it will happen for variable-free JOIN/ON clauses.  We don't have to
 400          * be real smart about such a case, we just have to be correct.
 401          */
 402         if (bms_is_empty(relids))
 403                 relids = qualscope;
 404
 405         /*
 406          * Check to see if clause application must be delayed by outer-join
 407          * considerations.
 408          */
 409         if (isdeduced)
 410         {
 411                 /*
 412                  * If the qual came from implied-equality deduction, we can
 413                  * evaluate the qual at its natural semantic level.  It is not
 414                  * affected by any outer-join rules (else we'd not have decided
 415                  * the vars were equal).
 416                  */
 417                 Assert(bms_equal(relids, qualscope));
 418                 can_be_equijoin = true;
 419         }
 420         else if (bms_overlap(relids, outerjoin_nonnullable))
 421         {
 422                 /*
 423                  * The qual is attached to an outer join and mentions (some of
 424                  * the) rels on the nonnullable side.  Force the qual to be
 425                  * evaluated exactly at the level of joining corresponding to the
 426                  * outer join. We cannot let it get pushed down into the
 427                  * nonnullable side, since then we'd produce no output rows,
 428                  * rather than the intended single null-extended row, for any
 429                  * nonnullable-side rows failing the qual.
 430                  *
 431                  * Note: an outer-join qual that mentions only nullable-side rels can
 432                  * be pushed down into the nullable side without changing the join
 433                  * result, so we treat it the same as an ordinary inner-join qual.
 434                  */
 435                 relids = qualscope;
 436                 can_be_equijoin = false;
 437         }
 438         else
 439         {
 440                 /*
 441                  * For a non-outer-join qual, we can evaluate the qual as soon as
 442                  * (1) we have all the rels it mentions, and (2) we are at or
 443                  * above any outer joins that can null any of these rels and are
 444                  * below the syntactic location of the given qual. To enforce the
 445                  * latter, scan the base rels listed in relids, and merge their
 446                  * outer-join sets into the clause's own reference list.  At the
 447                  * time we are called, the outerjoinset of each baserel will show
 448                  * exactly those outer joins that are below the qual in the join
 449                  * tree.
 450                  */
 451                 Relids          addrelids = NULL;
 452                 Relids          tmprelids;
 453                 int                     relno;
 454
 455                 tmprelids = bms_copy(relids);
 456                 while ((relno = bms_first_member(tmprelids)) >= 0)
 457                 {
 458                         RelOptInfo *rel = find_base_rel(root, relno);
 459
 460                         if (rel->outerjoinset != NULL)
 461                                 addrelids = bms_add_members(addrelids, rel->outerjoinset);
 462                 }
 463                 bms_free(tmprelids);
 464
 465                 if (bms_is_subset(addrelids, relids))
 466                 {
 467                         /* Qual is not affected by any outer-join restriction */
 468                         can_be_equijoin = true;
 469                 }
 470                 else
 471                 {
 472                         relids = bms_union(relids, addrelids);
 473                         /* Should still be a subset of current scope ... */
 474                         Assert(bms_is_subset(relids, qualscope));
 475
 476                         /*
 477                          * Because application of the qual will be delayed by outer
 478                          * join, we mustn't assume its vars are equal everywhere.
 479                          */
 480                         can_be_equijoin = false;
 481                 }
 482                 bms_free(addrelids);
 483         }
 484
 485         /*
 486          * Mark the qual as "pushed down" if it can be applied at a level
 487          * below its original syntactic level.  This allows us to distinguish
 488          * original JOIN/ON quals from higher-level quals pushed down to the
 489          * same joinrel. A qual originating from WHERE is always considered
 490          * "pushed down".
 491          */
 492         if (!ispusheddown)
 493                 ispusheddown = !bms_equal(relids, qualscope);
 494
 495         /*
 496          * Build the RestrictInfo node itself.
 497          */
 498         restrictinfo = make_restrictinfo((Expr *) clause, ispusheddown);
 499
 500         /*
 501          * Figure out where to attach it.
 502          */
 503         switch (bms_membership(relids))
 504         {
 505                 case BMS_SINGLETON:
 506
 507                         /*
 508                          * There is only one relation participating in 'clause', so
 509                          * 'clause' is a restriction clause for that relation.
 510                          */
 511                         rel = find_base_rel(root, bms_singleton_member(relids));
 512
 513                         /*
 514                          * Check for a "mergejoinable" clause even though it's not a
 515                          * join clause.  This is so that we can recognize that "a.x =
 516                          * a.y" makes x and y eligible to be considered equal, even
 517                          * when they belong to the same rel.  Without this, we would
 518                          * not recognize that "a.x = a.y AND a.x = b.z AND a.y = c.q"
 519                          * allows us to consider z and q equal after their rels are
 520                          * joined.
 521                          */
 522                         if (can_be_equijoin)
 523                                 check_mergejoinable(restrictinfo);
 524
 525                         /*
 526                          * If the clause was deduced from implied equality, check to
 527                          * see whether it is redundant with restriction clauses we
 528                          * already have for this rel.  Note we cannot apply this check
 529                          * to user-written clauses, since we haven't found the
 530                          * canonical pathkey sets yet while processing user clauses.
 531                          * (NB: no comparable check is done in the join-clause case;
 532                          * redundancy will be detected when the join clause is moved
 533                          * into a join rel's restriction list.)
 534                          */
 535                         if (!isdeduced ||
 536                                 !qual_is_redundant(root, restrictinfo,
 537                                                                    rel->baserestrictinfo))
 538                         {
 539                                 /* Add clause to rel's restriction list */
 540                                 rel->baserestrictinfo = lappend(rel->baserestrictinfo,
 541                                                                                                 restrictinfo);
 542                         }
 543                         break;
 544                 case BMS_MULTIPLE:
 545
 546                         /*
 547                          * 'clause' is a join clause, since there is more than one rel
 548                          * in the relid set.
 549                          */
 550
 551                         /*
 552                          * Check for hash or mergejoinable operators.
 553                          *
 554                          * We don't bother setting the hashjoin info if we're not going
 555                          * to need it.  We do want to know about mergejoinable ops in
 556                          * all cases, however, because we use mergejoinable ops for
 557                          * other purposes such as detecting redundant clauses.
 558                          */
 559                         check_mergejoinable(restrictinfo);
 560                         if (enable_hashjoin)
 561                                 check_hashjoinable(restrictinfo);
 562
 563                         /*
 564                          * Add clause to the join lists of all the relevant relations.
 565                          */
 566                         add_join_clause_to_rels(root, restrictinfo, relids);
 567
 568                         /*
 569                          * Add vars used in the join clause to targetlists of their
 570                          * relations, so that they will be emitted by the plan nodes
 571                          * that scan those relations (else they won't be available at
 572                          * the join node!).
 573                          */
 574                         add_vars_to_targetlist(root, vars, relids);
 575                         break;
 576                 default:
 577
 578                         /*
 579                          * 'clause' references no rels, and therefore we have no place
 580                          * to attach it.  Shouldn't get here if callers are working
 581                          * properly.
 582                          */
 583                         elog(ERROR, "cannot cope with variable-free clause");
 584                         break;
 585         }
 586
 587         /*
 588          * If the clause has a mergejoinable operator, and is not an
 589          * outer-join qualification nor bubbled up due to an outer join, then
 590          * the two sides represent equivalent PathKeyItems for path keys: any
 591          * path that is sorted by one side will also be sorted by the other
 592          * (as soon as the two rels are joined, that is).  Record the key
 593          * equivalence for future use.  (We can skip this for a deduced
 594          * clause, since the keys are already known equivalent in that case.)
 595          */
 596         if (can_be_equijoin &&
 597                 restrictinfo->mergejoinoperator != InvalidOid &&
 598                 !isdeduced)
 599                 add_equijoined_keys(root, restrictinfo);
 600 }
 601
 602 /*
 603  * process_implied_equality
 604  *        Check to see whether we already have a restrictinfo item that says
 605  *        item1 = item2, and create one if not; or if delete_it is true,
 606  *        remove any such restrictinfo item.
 607  *
 608  * This processing is a consequence of transitivity of mergejoin equality:
 609  * if we have mergejoinable clauses A = B and B = C, we can deduce A = C
 610  * (where = is an appropriate mergejoinable operator).  See path/pathkeys.c
 611  * for more details.
 612  */
 613 void
 614 process_implied_equality(Query *root,
 615                                                  Node *item1, Node *item2,
 616                                                  Oid sortop1, Oid sortop2,
 617                                                  Relids item1_relids, Relids item2_relids,
 618                                                  bool delete_it)
 619 {
 620         Relids          relids;
 621         BMS_Membership membership;
 622         RelOptInfo *rel1;
 623         List       *restrictlist;
 624         List       *itm;
 625         Oid                     ltype,
 626                                 rtype;
 627         Operator        eq_operator;
 628         Form_pg_operator pgopform;
 629         Expr       *clause;
 630
 631         /* Get set of relids referenced in the two expressions */
 632         relids = bms_union(item1_relids, item2_relids);
 633         membership = bms_membership(relids);
 634
 635         /*
 636          * generate_implied_equalities() shouldn't call me on two constants.
 637          */
 638         Assert(membership != BMS_EMPTY_SET);
 639
 640         /*
 641          * If the exprs involve a single rel, we need to look at that rel's
 642          * baserestrictinfo list.  If multiple rels, any one will have a
 643          * joininfo node for the rest, and we can scan any of 'em.
 644          */
 645         if (membership == BMS_SINGLETON)
 646         {
 647                 rel1 = find_base_rel(root, bms_singleton_member(relids));
 648                 restrictlist = rel1->baserestrictinfo;
 649         }
 650         else
 651         {
 652                 Relids          other_rels;
 653                 int                     first_rel;
 654                 JoinInfo   *joininfo;
 655
 656                 /* Copy relids, find and remove one member */
 657                 other_rels = bms_copy(relids);
 658                 first_rel = bms_first_member(other_rels);
 659
 660                 rel1 = find_base_rel(root, first_rel);
 661
 662                 /* use remaining members to find join node */
 663                 joininfo = find_joininfo_node(rel1, other_rels);
 664
 665                 restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL;
 666
 667                 bms_free(other_rels);
 668         }
 669
 670         /*
 671          * Scan to see if equality is already known.  If so, we're done in the
 672          * add case, and done after removing it in the delete case.
 673          */
 674         foreach(itm, restrictlist)
 675         {
 676                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
 677                 Node       *left,
 678                                    *right;
 679
 680                 if (restrictinfo->mergejoinoperator == InvalidOid)
 681                         continue;                       /* ignore non-mergejoinable clauses */
 682                 /* We now know the restrictinfo clause is a binary opclause */
 683                 left = get_leftop(restrictinfo->clause);
 684                 right = get_rightop(restrictinfo->clause);
 685                 if ((equal(item1, left) && equal(item2, right)) ||
 686                         (equal(item2, left) && equal(item1, right)))
 687                 {
 688                         /* found a matching clause */
 689                         if (delete_it)
 690                         {
 691                                 if (membership == BMS_SINGLETON)
 692                                 {
 693                                         /* delete it from local restrictinfo list */
 694                                         rel1->baserestrictinfo = lremove(restrictinfo,
 695                                                                                                  rel1->baserestrictinfo);
 696                                 }
 697                                 else
 698                                 {
 699                                         /* let joininfo.c do it */
 700                                         remove_join_clause_from_rels(root, restrictinfo, relids);
 701                                 }
 702                         }
 703                         return;                         /* done */
 704                 }
 705         }
 706
 707         /* Didn't find it.  Done if deletion requested */
 708         if (delete_it)
 709                 return;
 710
 711         /*
 712          * This equality is new information, so construct a clause
 713          * representing it to add to the query data structures.
 714          */
 715         ltype = exprType(item1);
 716         rtype = exprType(item2);
 717         eq_operator = compatible_oper(makeList1(makeString("=")),
 718                                                                   ltype, rtype, true);
 719         if (!HeapTupleIsValid(eq_operator))
 720         {
 721                 /*
 722                  * Would it be safe to just not add the equality to the query if
 723                  * we have no suitable equality operator for the combination of
 724                  * datatypes?  NO, because sortkey selection may screw up anyway.
 725                  */
 726                 ereport(ERROR,
 727                                 (errcode(ERRCODE_UNDEFINED_FUNCTION),
 728                                  errmsg("could not identify an equality operator for types %s and %s",
 729                                                 format_type_be(ltype), format_type_be(rtype))));
 730         }
 731         pgopform = (Form_pg_operator) GETSTRUCT(eq_operator);
 732
 733         /*
 734          * Let's just make sure this appears to be a compatible operator.
 735          */
 736         if (pgopform->oprlsortop != sortop1 ||
 737                 pgopform->oprrsortop != sortop2 ||
 738                 pgopform->oprresult != BOOLOID)
 739                 ereport(ERROR,
 740                                 (errcode(ERRCODE_INVALID_FUNCTION_DEFINITION),
 741                                  errmsg("equality operator for types %s and %s should be merge-joinable, but isn't",
 742                                                 format_type_be(ltype), format_type_be(rtype))));
 743
 744         clause = make_opclause(oprid(eq_operator),      /* opno */
 745                                                    BOOLOID,             /* opresulttype */
 746                                                    false,               /* opretset */
 747                                                    (Expr *) item1,
 748                                                    (Expr *) item2);
 749
 750         ReleaseSysCache(eq_operator);
 751
 752         /*
 753          * Push the new clause into all the appropriate restrictinfo lists.
 754          *
 755          * Note: we mark the qual "pushed down" to ensure that it can never be
 756          * taken for an original JOIN/ON clause.
 757          */
 758         distribute_qual_to_rels(root, (Node *) clause,
 759                                                         true, true, NULL, relids);
 760 }
 761
 762 /*
 763  * qual_is_redundant
 764  *        Detect whether an implied-equality qual that turns out to be a
 765  *        restriction clause for a single base relation is redundant with
 766  *        already-known restriction clauses for that rel.  This occurs with,
 767  *        for example,
 768  *                              SELECT * FROM tab WHERE f1 = f2 AND f2 = f3;
 769  *        We need to suppress the redundant condition to avoid computing
 770  *        too-small selectivity, not to mention wasting time at execution.
 771  *
 772  * Note: quals of the form "var = const" are never considered redundant,
 773  * only those of the form "var = var".  This is needed because when we
 774  * have constants in an implied-equality set, we use a different strategy
 775  * that suppresses all "var = var" deductions.  We must therefore keep
 776  * all the "var = const" quals.
 777  */
 778 static bool
 779 qual_is_redundant(Query *root,
 780                                   RestrictInfo *restrictinfo,
 781                                   List *restrictlist)
 782 {
 783         Node       *newleft;
 784         Node       *newright;
 785         List       *oldquals;
 786         List       *olditem;
 787         List       *equalexprs;
 788         bool            someadded;
 789
 790         /* Never redundant unless vars appear on both sides */
 791         if (bms_is_empty(restrictinfo->left_relids) ||
 792                 bms_is_empty(restrictinfo->right_relids))
 793                 return false;
 794
 795         newleft = get_leftop(restrictinfo->clause);
 796         newright = get_rightop(restrictinfo->clause);
 797
 798         /*
 799          * Set cached pathkeys.  NB: it is okay to do this now because this
 800          * routine is only invoked while we are generating implied equalities.
 801          * Therefore, the equi_key_list is already complete and so we can
 802          * correctly determine canonical pathkeys.
 803          */
 804         cache_mergeclause_pathkeys(root, restrictinfo);
 805         /* If different, say "not redundant" (should never happen) */
 806         if (restrictinfo->left_pathkey != restrictinfo->right_pathkey)
 807                 return false;
 808
 809         /*
 810          * Scan existing quals to find those referencing same pathkeys.
 811          * Usually there will be few, if any, so build a list of just the
 812          * interesting ones.
 813          */
 814         oldquals = NIL;
 815         foreach(olditem, restrictlist)
 816         {
 817                 RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
 818
 819                 if (oldrinfo->mergejoinoperator != InvalidOid)
 820                 {
 821                         cache_mergeclause_pathkeys(root, oldrinfo);
 822                         if (restrictinfo->left_pathkey == oldrinfo->left_pathkey &&
 823                                 restrictinfo->right_pathkey == oldrinfo->right_pathkey)
 824                                 oldquals = lcons(oldrinfo, oldquals);
 825                 }
 826         }
 827         if (oldquals == NIL)
 828                 return false;
 829
 830         /*
 831          * Now, we want to develop a list of exprs that are known equal to the
 832          * left side of the new qual.  We traverse the old-quals list
 833          * repeatedly to transitively expand the exprs list.  If at any point
 834          * we find we can reach the right-side expr of the new qual, we are
 835          * done.  We give up when we can't expand the equalexprs list any
 836          * more.
 837          */
 838         equalexprs = makeList1(newleft);
 839         do
 840         {
 841                 someadded = false;
 842                 /* cannot use foreach here because of possible lremove */
 843                 olditem = oldquals;
 844                 while (olditem)
 845                 {
 846                         RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
 847                         Node       *oldleft = get_leftop(oldrinfo->clause);
 848                         Node       *oldright = get_rightop(oldrinfo->clause);
 849                         Node       *newguy = NULL;
 850
 851                         /* must advance olditem before lremove possibly pfree's it */
 852                         olditem = lnext(olditem);
 853
 854                         if (member(oldleft, equalexprs))
 855                                 newguy = oldright;
 856                         else if (member(oldright, equalexprs))
 857                                 newguy = oldleft;
 858                         else
 859                                 continue;
 860                         if (equal(newguy, newright))
 861                                 return true;    /* we proved new clause is redundant */
 862                         equalexprs = lcons(newguy, equalexprs);
 863                         someadded = true;
 864
 865                         /*
 866                          * Remove this qual from list, since we don't need it anymore.
 867                          */
 868                         oldquals = lremove(oldrinfo, oldquals);
 869                 }
 870         } while (someadded);
 871
 872         return false;                           /* it's not redundant */
 873 }
 874
 875
 876 /*****************************************************************************
 877  *
 878  *       CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
 879  *
 880  *****************************************************************************/
 881
 882 /*
 883  * check_mergejoinable
 884  *        If the restrictinfo's clause is mergejoinable, set the mergejoin
 885  *        info fields in the restrictinfo.
 886  *
 887  *        Currently, we support mergejoin for binary opclauses where
 888  *        the operator is a mergejoinable operator.  The arguments can be
 889  *        anything --- as long as there are no volatile functions in them.
 890  */
 891 static void
 892 check_mergejoinable(RestrictInfo *restrictinfo)
 893 {
 894         Expr       *clause = restrictinfo->clause;
 895         Oid                     opno,
 896                                 leftOp,
 897                                 rightOp;
 898
 899         if (!is_opclause(clause))
 900                 return;
 901         if (length(((OpExpr *) clause)->args) != 2)
 902                 return;
 903
 904         opno = ((OpExpr *) clause)->opno;
 905
 906         if (op_mergejoinable(opno,
 907                                                  &leftOp,
 908                                                  &rightOp) &&
 909                 !contain_volatile_functions((Node *) clause))
 910         {
 911                 restrictinfo->mergejoinoperator = opno;
 912                 restrictinfo->left_sortop = leftOp;
 913                 restrictinfo->right_sortop = rightOp;
 914         }
 915 }
 916
 917 /*
 918  * check_hashjoinable
 919  *        If the restrictinfo's clause is hashjoinable, set the hashjoin
 920  *        info fields in the restrictinfo.
 921  *
 922  *        Currently, we support hashjoin for binary opclauses where
 923  *        the operator is a hashjoinable operator.      The arguments can be
 924  *        anything --- as long as there are no volatile functions in them.
 925  */
 926 static void
 927 check_hashjoinable(RestrictInfo *restrictinfo)
 928 {
 929         Expr       *clause = restrictinfo->clause;
 930         Oid                     opno;
 931
 932         if (!is_opclause(clause))
 933                 return;
 934         if (length(((OpExpr *) clause)->args) != 2)
 935                 return;
 936
 937         opno = ((OpExpr *) clause)->opno;
 938
 939         if (op_hashjoinable(opno) &&
 940                 !contain_volatile_functions((Node *) clause))
 941                 restrictinfo->hashjoinoperator = opno;
 942 }