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-2005, 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.107 2005/06/09 04:18:59 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(PlannerInfo *root, Relids rels,
  38                                                          Relids outerrels);
  39 static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
  40                                                 bool is_pushed_down,
  41                                                 bool isdeduced,
  42                                                 Relids outerjoin_nonnullable,
  43                                                 Relids qualscope);
  44 static void add_vars_to_targetlist(PlannerInfo *root, List *vars,
  45                                            Relids where_needed);
  46 static bool qual_is_redundant(PlannerInfo *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(PlannerInfo *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                 ListCell   *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(PlannerInfo *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                 list_free(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(PlannerInfo *root, List *vars, Relids where_needed)
 137 {
 138         ListCell   *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                         rel->reltargetlist = lappend(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(PlannerInfo *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                 ListCell   *l;
 209
 210                 /*
 211                  * First, recurse to handle child joins.
 212                  */
 213                 foreach(l, f->fromlist)
 214                 {
 215                         result = bms_add_members(result,
 216                                                                          distribute_quals_to_rels(root,
 217                                                                                                                           lfirst(l)));
 218                 }
 219
 220                 /*
 221                  * Now process the top-level quals.  These are always marked as
 222                  * "pushed down", since they clearly didn't come from a JOIN expr.
 223                  */
 224                 foreach(l, (List *) f->quals)
 225                         distribute_qual_to_rels(root, (Node *) lfirst(l),
 226                                                                         true, false, NULL, result);
 227         }
 228         else if (IsA(jtnode, JoinExpr))
 229         {
 230                 JoinExpr   *j = (JoinExpr *) jtnode;
 231                 Relids          leftids,
 232                                         rightids,
 233                                         nonnullable_rels,
 234                                         nullable_rels;
 235                 ListCell   *qual;
 236
 237                 /*
 238                  * Order of operations here is subtle and critical.  First we
 239                  * recurse to handle sub-JOINs.  Their join quals will be placed
 240                  * without regard for whether this level is an outer join, which
 241                  * is correct.  Then we place our own join quals, which are
 242                  * restricted by lower outer joins in any case, and are forced to
 243                  * this level if this is an outer join and they mention the outer
 244                  * side.  Finally, if this is an outer join, we mark baserels
 245                  * contained within the inner side(s) with our own rel set; this
 246                  * will prevent quals above us in the join tree that use those
 247                  * rels from being pushed down below this level.  (It's okay for
 248                  * upper quals to be pushed down to the outer side, however.)
 249                  */
 250                 leftids = distribute_quals_to_rels(root, j->larg);
 251                 rightids = distribute_quals_to_rels(root, j->rarg);
 252
 253                 result = bms_union(leftids, rightids);
 254
 255                 nonnullable_rels = nullable_rels = NULL;
 256                 switch (j->jointype)
 257                 {
 258                         case JOIN_INNER:
 259                                 /* Inner join adds no restrictions for quals */
 260                                 break;
 261                         case JOIN_LEFT:
 262                                 nonnullable_rels = leftids;
 263                                 nullable_rels = rightids;
 264                                 break;
 265                         case JOIN_FULL:
 266                                 /* each side is both outer and inner */
 267                                 nonnullable_rels = result;
 268                                 nullable_rels = result;
 269                                 break;
 270                         case JOIN_RIGHT:
 271                                 nonnullable_rels = rightids;
 272                                 nullable_rels = leftids;
 273                                 break;
 274                         case JOIN_UNION:
 275
 276                                 /*
 277                                  * This is where we fail if upper levels of planner
 278                                  * haven't rewritten UNION JOIN as an Append ...
 279                                  */
 280                                 ereport(ERROR,
 281                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 282                                                  errmsg("UNION JOIN is not implemented")));
 283                                 break;
 284                         default:
 285                                 elog(ERROR, "unrecognized join type: %d",
 286                                          (int) j->jointype);
 287                                 break;
 288                 }
 289
 290                 foreach(qual, (List *) j->quals)
 291                         distribute_qual_to_rels(root, (Node *) lfirst(qual),
 292                                                                         false, false,
 293                                                                         nonnullable_rels, result);
 294
 295                 if (nullable_rels != NULL)
 296                         mark_baserels_for_outer_join(root, nullable_rels, result);
 297         }
 298         else
 299                 elog(ERROR, "unrecognized node type: %d",
 300                          (int) nodeTag(jtnode));
 301         return result;
 302 }
 303
 304 /*
 305  * mark_baserels_for_outer_join
 306  *        Mark all base rels listed in 'rels' as having the given outerjoinset.
 307  */
 308 static void
 309 mark_baserels_for_outer_join(PlannerInfo *root, Relids rels, Relids outerrels)
 310 {
 311         Relids          tmprelids;
 312         int                     relno;
 313
 314         tmprelids = bms_copy(rels);
 315         while ((relno = bms_first_member(tmprelids)) >= 0)
 316         {
 317                 RelOptInfo *rel = find_base_rel(root, relno);
 318
 319                 /*
 320                  * Since we do this bottom-up, any outer-rels previously marked
 321                  * should be within the new outer join set.
 322                  */
 323                 Assert(bms_is_subset(rel->outerjoinset, outerrels));
 324
 325                 /*
 326                  * Presently the executor cannot support FOR UPDATE/SHARE marking of
 327                  * rels appearing on the nullable side of an outer join. (It's
 328                  * somewhat unclear what that would mean, anyway: what should we
 329                  * mark when a result row is generated from no element of the
 330                  * nullable relation?)  So, complain if target rel is FOR UPDATE/SHARE.
 331                  * It's sufficient to make this check once per rel, so do it only
 332                  * if rel wasn't already known nullable.
 333                  */
 334                 if (rel->outerjoinset == NULL)
 335                 {
 336                         if (list_member_int(root->parse->rowMarks, relno))
 337                                 ereport(ERROR,
 338                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 339                                                  errmsg("SELECT FOR UPDATE/SHARE cannot be applied to the nullable side of an outer join")));
 340                 }
 341
 342                 rel->outerjoinset = outerrels;
 343         }
 344         bms_free(tmprelids);
 345 }
 346
 347 /*
 348  * distribute_qual_to_rels
 349  *        Add clause information to either the baserestrictinfo or joininfo list
 350  *        (depending on whether the clause is a join) of each base relation
 351  *        mentioned in the clause.      A RestrictInfo node is created and added to
 352  *        the appropriate list for each rel.  Also, if the clause uses a
 353  *        mergejoinable operator and is not delayed by outer-join rules, enter
 354  *        the left- and right-side expressions into the query's lists of
 355  *        equijoined vars.
 356  *
 357  * 'clause': the qual clause to be distributed
 358  * 'is_pushed_down': if TRUE, force the clause to be marked 'is_pushed_down'
 359  *              (this indicates the clause came from a FromExpr, not a JoinExpr)
 360  * 'isdeduced': TRUE if the qual came from implied-equality deduction
 361  * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
 362  *              baserels appearing on the outer (nonnullable) side of the join
 363  * 'qualscope': set of baserels the qual's syntactic scope covers
 364  *
 365  * 'qualscope' identifies what level of JOIN the qual came from.  For a top
 366  * level qual (WHERE qual), qualscope lists all baserel ids and in addition
 367  * 'is_pushed_down' will be TRUE.
 368  */
 369 static void
 370 distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 371                                                 bool is_pushed_down,
 372                                                 bool isdeduced,
 373                                                 Relids outerjoin_nonnullable,
 374                                                 Relids qualscope)
 375 {
 376         Relids          relids;
 377         bool            valid_everywhere;
 378         bool            can_be_equijoin;
 379         RestrictInfo *restrictinfo;
 380         RelOptInfo *rel;
 381         List       *vars;
 382
 383         /*
 384          * Retrieve all relids mentioned within the clause.
 385          */
 386         relids = pull_varnos(clause);
 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                 valid_everywhere = true;
 419                 can_be_equijoin = true;
 420         }
 421         else if (bms_overlap(relids, outerjoin_nonnullable))
 422         {
 423                 /*
 424                  * The qual is attached to an outer join and mentions (some of
 425                  * the) rels on the nonnullable side.  Force the qual to be
 426                  * evaluated exactly at the level of joining corresponding to the
 427                  * outer join. We cannot let it get pushed down into the
 428                  * nonnullable side, since then we'd produce no output rows,
 429                  * rather than the intended single null-extended row, for any
 430                  * nonnullable-side rows failing the qual.
 431                  *
 432                  * Note: an outer-join qual that mentions only nullable-side rels can
 433                  * be pushed down into the nullable side without changing the join
 434                  * result, so we treat it the same as an ordinary inner-join qual.
 435                  */
 436                 relids = qualscope;
 437                 valid_everywhere = false;
 438                 can_be_equijoin = false;
 439         }
 440         else
 441         {
 442                 /*
 443                  * For a non-outer-join qual, we can evaluate the qual as soon as
 444                  * (1) we have all the rels it mentions, and (2) we are at or
 445                  * above any outer joins that can null any of these rels and are
 446                  * below the syntactic location of the given qual. To enforce the
 447                  * latter, scan the base rels listed in relids, and merge their
 448                  * outer-join sets into the clause's own reference list.  At the
 449                  * time we are called, the outerjoinset of each baserel will show
 450                  * exactly those outer joins that are below the qual in the join
 451                  * tree.
 452                  *
 453                  * We also need to determine whether the qual is "valid everywhere",
 454                  * which is true if the qual mentions no variables that are
 455                  * involved in lower-level outer joins (this may be an overly
 456                  * strong test).
 457                  */
 458                 Relids          addrelids = NULL;
 459                 Relids          tmprelids;
 460                 int                     relno;
 461
 462                 valid_everywhere = true;
 463                 tmprelids = bms_copy(relids);
 464                 while ((relno = bms_first_member(tmprelids)) >= 0)
 465                 {
 466                         RelOptInfo *rel = find_base_rel(root, relno);
 467
 468                         if (rel->outerjoinset != NULL)
 469                         {
 470                                 addrelids = bms_add_members(addrelids, rel->outerjoinset);
 471                                 valid_everywhere = false;
 472                         }
 473                 }
 474                 bms_free(tmprelids);
 475
 476                 if (bms_is_subset(addrelids, relids))
 477                 {
 478                         /* Qual is not affected by any outer-join restriction */
 479                         can_be_equijoin = true;
 480                 }
 481                 else
 482                 {
 483                         relids = bms_union(relids, addrelids);
 484                         /* Should still be a subset of current scope ... */
 485                         Assert(bms_is_subset(relids, qualscope));
 486
 487                         /*
 488                          * Because application of the qual will be delayed by outer
 489                          * join, we mustn't assume its vars are equal everywhere.
 490                          */
 491                         can_be_equijoin = false;
 492                 }
 493                 bms_free(addrelids);
 494         }
 495
 496         /*
 497          * Mark the qual as "pushed down" if it can be applied at a level
 498          * below its original syntactic level.  This allows us to distinguish
 499          * original JOIN/ON quals from higher-level quals pushed down to the
 500          * same joinrel. A qual originating from WHERE is always considered
 501          * "pushed down".
 502          */
 503         if (!is_pushed_down)
 504                 is_pushed_down = !bms_equal(relids, qualscope);
 505
 506         /*
 507          * Build the RestrictInfo node itself.
 508          */
 509         restrictinfo = make_restrictinfo((Expr *) clause,
 510                                                                          is_pushed_down,
 511                                                                          valid_everywhere,
 512                                                                          relids);
 513
 514         /*
 515          * Figure out where to attach it.
 516          */
 517         switch (bms_membership(relids))
 518         {
 519                 case BMS_SINGLETON:
 520
 521                         /*
 522                          * There is only one relation participating in 'clause', so
 523                          * 'clause' is a restriction clause for that relation.
 524                          */
 525                         rel = find_base_rel(root, bms_singleton_member(relids));
 526
 527                         /*
 528                          * Check for a "mergejoinable" clause even though it's not a
 529                          * join clause.  This is so that we can recognize that "a.x =
 530                          * a.y" makes x and y eligible to be considered equal, even
 531                          * when they belong to the same rel.  Without this, we would
 532                          * not recognize that "a.x = a.y AND a.x = b.z AND a.y = c.q"
 533                          * allows us to consider z and q equal after their rels are
 534                          * joined.
 535                          */
 536                         if (can_be_equijoin)
 537                                 check_mergejoinable(restrictinfo);
 538
 539                         /*
 540                          * If the clause was deduced from implied equality, check to
 541                          * see whether it is redundant with restriction clauses we
 542                          * already have for this rel.  Note we cannot apply this check
 543                          * to user-written clauses, since we haven't found the
 544                          * canonical pathkey sets yet while processing user clauses.
 545                          * (NB: no comparable check is done in the join-clause case;
 546                          * redundancy will be detected when the join clause is moved
 547                          * into a join rel's restriction list.)
 548                          */
 549                         if (!isdeduced ||
 550                                 !qual_is_redundant(root, restrictinfo,
 551                                                                    rel->baserestrictinfo))
 552                         {
 553                                 /* Add clause to rel's restriction list */
 554                                 rel->baserestrictinfo = lappend(rel->baserestrictinfo,
 555                                                                                                 restrictinfo);
 556                         }
 557                         break;
 558                 case BMS_MULTIPLE:
 559
 560                         /*
 561                          * 'clause' is a join clause, since there is more than one rel
 562                          * in the relid set.
 563                          */
 564
 565                         /*
 566                          * Check for hash or mergejoinable operators.
 567                          *
 568                          * We don't bother setting the hashjoin info if we're not going
 569                          * to need it.  We do want to know about mergejoinable ops in
 570                          * all cases, however, because we use mergejoinable ops for
 571                          * other purposes such as detecting redundant clauses.
 572                          */
 573                         check_mergejoinable(restrictinfo);
 574                         if (enable_hashjoin)
 575                                 check_hashjoinable(restrictinfo);
 576
 577                         /*
 578                          * Add clause to the join lists of all the relevant relations.
 579                          */
 580                         add_join_clause_to_rels(root, restrictinfo, relids);
 581
 582                         /*
 583                          * Add vars used in the join clause to targetlists of their
 584                          * relations, so that they will be emitted by the plan nodes
 585                          * that scan those relations (else they won't be available at
 586                          * the join node!).
 587                          */
 588                         vars = pull_var_clause(clause, false);
 589                         add_vars_to_targetlist(root, vars, relids);
 590                         list_free(vars);
 591                         break;
 592                 default:
 593
 594                         /*
 595                          * 'clause' references no rels, and therefore we have no place
 596                          * to attach it.  Shouldn't get here if callers are working
 597                          * properly.
 598                          */
 599                         elog(ERROR, "cannot cope with variable-free clause");
 600                         break;
 601         }
 602
 603         /*
 604          * If the clause has a mergejoinable operator, and is not an
 605          * outer-join qualification nor bubbled up due to an outer join, then
 606          * the two sides represent equivalent PathKeyItems for path keys: any
 607          * path that is sorted by one side will also be sorted by the other
 608          * (as soon as the two rels are joined, that is).  Record the key
 609          * equivalence for future use.  (We can skip this for a deduced
 610          * clause, since the keys are already known equivalent in that case.)
 611          */
 612         if (can_be_equijoin &&
 613                 restrictinfo->mergejoinoperator != InvalidOid &&
 614                 !isdeduced)
 615                 add_equijoined_keys(root, restrictinfo);
 616 }
 617
 618 /*
 619  * process_implied_equality
 620  *        Check to see whether we already have a restrictinfo item that says
 621  *        item1 = item2, and create one if not; or if delete_it is true,
 622  *        remove any such restrictinfo item.
 623  *
 624  * This processing is a consequence of transitivity of mergejoin equality:
 625  * if we have mergejoinable clauses A = B and B = C, we can deduce A = C
 626  * (where = is an appropriate mergejoinable operator).  See path/pathkeys.c
 627  * for more details.
 628  */
 629 void
 630 process_implied_equality(PlannerInfo *root,
 631                                                  Node *item1, Node *item2,
 632                                                  Oid sortop1, Oid sortop2,
 633                                                  Relids item1_relids, Relids item2_relids,
 634                                                  bool delete_it)
 635 {
 636         Relids          relids;
 637         BMS_Membership membership;
 638         RelOptInfo *rel1;
 639         List       *restrictlist;
 640         ListCell   *itm;
 641         Oid                     ltype,
 642                                 rtype;
 643         Operator        eq_operator;
 644         Form_pg_operator pgopform;
 645         Expr       *clause;
 646
 647         /* Get set of relids referenced in the two expressions */
 648         relids = bms_union(item1_relids, item2_relids);
 649         membership = bms_membership(relids);
 650
 651         /*
 652          * generate_implied_equalities() shouldn't call me on two constants.
 653          */
 654         Assert(membership != BMS_EMPTY_SET);
 655
 656         /*
 657          * If the exprs involve a single rel, we need to look at that rel's
 658          * baserestrictinfo list.  If multiple rels, we can scan the joininfo
 659          * list of any of 'em.
 660          */
 661         if (membership == BMS_SINGLETON)
 662         {
 663                 rel1 = find_base_rel(root, bms_singleton_member(relids));
 664                 restrictlist = rel1->baserestrictinfo;
 665         }
 666         else
 667         {
 668                 Relids          other_rels;
 669                 int                     first_rel;
 670
 671                 /* Copy relids, find and remove one member */
 672                 other_rels = bms_copy(relids);
 673                 first_rel = bms_first_member(other_rels);
 674                 bms_free(other_rels);
 675
 676                 rel1 = find_base_rel(root, first_rel);
 677                 restrictlist = rel1->joininfo;
 678         }
 679
 680         /*
 681          * Scan to see if equality is already known.  If so, we're done in the
 682          * add case, and done after removing it in the delete case.
 683          */
 684         foreach(itm, restrictlist)
 685         {
 686                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
 687                 Node       *left,
 688                                    *right;
 689
 690                 if (restrictinfo->mergejoinoperator == InvalidOid)
 691                         continue;                       /* ignore non-mergejoinable clauses */
 692                 /* We now know the restrictinfo clause is a binary opclause */
 693                 left = get_leftop(restrictinfo->clause);
 694                 right = get_rightop(restrictinfo->clause);
 695                 if ((equal(item1, left) && equal(item2, right)) ||
 696                         (equal(item2, left) && equal(item1, right)))
 697                 {
 698                         /* found a matching clause */
 699                         if (delete_it)
 700                         {
 701                                 if (membership == BMS_SINGLETON)
 702                                 {
 703                                         /* delete it from local restrictinfo list */
 704                                         rel1->baserestrictinfo = list_delete_ptr(rel1->baserestrictinfo,
 705                                                                                                                    restrictinfo);
 706                                 }
 707                                 else
 708                                 {
 709                                         /* let joininfo.c do it */
 710                                         remove_join_clause_from_rels(root, restrictinfo, relids);
 711                                 }
 712                         }
 713                         return;                         /* done */
 714                 }
 715         }
 716
 717         /* Didn't find it.  Done if deletion requested */
 718         if (delete_it)
 719                 return;
 720
 721         /*
 722          * This equality is new information, so construct a clause
 723          * representing it to add to the query data structures.
 724          */
 725         ltype = exprType(item1);
 726         rtype = exprType(item2);
 727         eq_operator = compatible_oper(list_make1(makeString("=")),
 728                                                                   ltype, rtype, true);
 729         if (!HeapTupleIsValid(eq_operator))
 730         {
 731                 /*
 732                  * Would it be safe to just not add the equality to the query if
 733                  * we have no suitable equality operator for the combination of
 734                  * datatypes?  NO, because sortkey selection may screw up anyway.
 735                  */
 736                 ereport(ERROR,
 737                                 (errcode(ERRCODE_UNDEFINED_FUNCTION),
 738                                  errmsg("could not identify an equality operator for types %s and %s",
 739                                                 format_type_be(ltype), format_type_be(rtype))));
 740         }
 741         pgopform = (Form_pg_operator) GETSTRUCT(eq_operator);
 742
 743         /*
 744          * Let's just make sure this appears to be a compatible operator.
 745          */
 746         if (pgopform->oprlsortop != sortop1 ||
 747                 pgopform->oprrsortop != sortop2 ||
 748                 pgopform->oprresult != BOOLOID)
 749                 ereport(ERROR,
 750                                 (errcode(ERRCODE_INVALID_FUNCTION_DEFINITION),
 751                                  errmsg("equality operator for types %s and %s should be merge-joinable, but isn't",
 752                                                 format_type_be(ltype), format_type_be(rtype))));
 753
 754         /*
 755          * Now we can build the new clause.  Copy to ensure it shares no
 756          * substructure with original (this is necessary in case there are
 757          * subselects in there...)
 758          */
 759         clause = make_opclause(oprid(eq_operator),      /* opno */
 760                                                    BOOLOID,             /* opresulttype */
 761                                                    false,               /* opretset */
 762                                                    (Expr *) copyObject(item1),
 763                                                    (Expr *) copyObject(item2));
 764
 765         ReleaseSysCache(eq_operator);
 766
 767         /*
 768          * Push the new clause into all the appropriate restrictinfo lists.
 769          *
 770          * Note: we mark the qual "pushed down" to ensure that it can never be
 771          * taken for an original JOIN/ON clause.
 772          */
 773         distribute_qual_to_rels(root, (Node *) clause,
 774                                                         true, true, NULL, relids);
 775 }
 776
 777 /*
 778  * qual_is_redundant
 779  *        Detect whether an implied-equality qual that turns out to be a
 780  *        restriction clause for a single base relation is redundant with
 781  *        already-known restriction clauses for that rel.  This occurs with,
 782  *        for example,
 783  *                              SELECT * FROM tab WHERE f1 = f2 AND f2 = f3;
 784  *        We need to suppress the redundant condition to avoid computing
 785  *        too-small selectivity, not to mention wasting time at execution.
 786  *
 787  * Note: quals of the form "var = const" are never considered redundant,
 788  * only those of the form "var = var".  This is needed because when we
 789  * have constants in an implied-equality set, we use a different strategy
 790  * that suppresses all "var = var" deductions.  We must therefore keep
 791  * all the "var = const" quals.
 792  */
 793 static bool
 794 qual_is_redundant(PlannerInfo *root,
 795                                   RestrictInfo *restrictinfo,
 796                                   List *restrictlist)
 797 {
 798         Node       *newleft;
 799         Node       *newright;
 800         List       *oldquals;
 801         ListCell   *olditem;
 802         List       *equalexprs;
 803         bool            someadded;
 804
 805         /* Never redundant unless vars appear on both sides */
 806         if (bms_is_empty(restrictinfo->left_relids) ||
 807                 bms_is_empty(restrictinfo->right_relids))
 808                 return false;
 809
 810         newleft = get_leftop(restrictinfo->clause);
 811         newright = get_rightop(restrictinfo->clause);
 812
 813         /*
 814          * Set cached pathkeys.  NB: it is okay to do this now because this
 815          * routine is only invoked while we are generating implied equalities.
 816          * Therefore, the equi_key_list is already complete and so we can
 817          * correctly determine canonical pathkeys.
 818          */
 819         cache_mergeclause_pathkeys(root, restrictinfo);
 820         /* If different, say "not redundant" (should never happen) */
 821         if (restrictinfo->left_pathkey != restrictinfo->right_pathkey)
 822                 return false;
 823
 824         /*
 825          * Scan existing quals to find those referencing same pathkeys.
 826          * Usually there will be few, if any, so build a list of just the
 827          * interesting ones.
 828          */
 829         oldquals = NIL;
 830         foreach(olditem, restrictlist)
 831         {
 832                 RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
 833
 834                 if (oldrinfo->mergejoinoperator != InvalidOid)
 835                 {
 836                         cache_mergeclause_pathkeys(root, oldrinfo);
 837                         if (restrictinfo->left_pathkey == oldrinfo->left_pathkey &&
 838                                 restrictinfo->right_pathkey == oldrinfo->right_pathkey)
 839                                 oldquals = lcons(oldrinfo, oldquals);
 840                 }
 841         }
 842         if (oldquals == NIL)
 843                 return false;
 844
 845         /*
 846          * Now, we want to develop a list of exprs that are known equal to the
 847          * left side of the new qual.  We traverse the old-quals list
 848          * repeatedly to transitively expand the exprs list.  If at any point
 849          * we find we can reach the right-side expr of the new qual, we are
 850          * done.  We give up when we can't expand the equalexprs list any
 851          * more.
 852          */
 853         equalexprs = list_make1(newleft);
 854         do
 855         {
 856                 someadded = false;
 857                 /* cannot use foreach here because of possible list_delete */
 858                 olditem = list_head(oldquals);
 859                 while (olditem)
 860                 {
 861                         RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
 862                         Node       *oldleft = get_leftop(oldrinfo->clause);
 863                         Node       *oldright = get_rightop(oldrinfo->clause);
 864                         Node       *newguy = NULL;
 865
 866                         /* must advance olditem before list_delete possibly pfree's it */
 867                         olditem = lnext(olditem);
 868
 869                         if (list_member(equalexprs, oldleft))
 870                                 newguy = oldright;
 871                         else if (list_member(equalexprs, oldright))
 872                                 newguy = oldleft;
 873                         else
 874                                 continue;
 875                         if (equal(newguy, newright))
 876                                 return true;    /* we proved new clause is redundant */
 877                         equalexprs = lcons(newguy, equalexprs);
 878                         someadded = true;
 879
 880                         /*
 881                          * Remove this qual from list, since we don't need it anymore.
 882                          */
 883                         oldquals = list_delete_ptr(oldquals, oldrinfo);
 884                 }
 885         } while (someadded);
 886
 887         return false;                           /* it's not redundant */
 888 }
 889
 890
 891 /*****************************************************************************
 892  *
 893  *       CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
 894  *
 895  *****************************************************************************/
 896
 897 /*
 898  * check_mergejoinable
 899  *        If the restrictinfo's clause is mergejoinable, set the mergejoin
 900  *        info fields in the restrictinfo.
 901  *
 902  *        Currently, we support mergejoin for binary opclauses where
 903  *        the operator is a mergejoinable operator.  The arguments can be
 904  *        anything --- as long as there are no volatile functions in them.
 905  */
 906 static void
 907 check_mergejoinable(RestrictInfo *restrictinfo)
 908 {
 909         Expr       *clause = restrictinfo->clause;
 910         Oid                     opno,
 911                                 leftOp,
 912                                 rightOp;
 913
 914         if (!is_opclause(clause))
 915                 return;
 916         if (list_length(((OpExpr *) clause)->args) != 2)
 917                 return;
 918
 919         opno = ((OpExpr *) clause)->opno;
 920
 921         if (op_mergejoinable(opno,
 922                                                  &leftOp,
 923                                                  &rightOp) &&
 924                 !contain_volatile_functions((Node *) clause))
 925         {
 926                 restrictinfo->mergejoinoperator = opno;
 927                 restrictinfo->left_sortop = leftOp;
 928                 restrictinfo->right_sortop = rightOp;
 929         }
 930 }
 931
 932 /*
 933  * check_hashjoinable
 934  *        If the restrictinfo's clause is hashjoinable, set the hashjoin
 935  *        info fields in the restrictinfo.
 936  *
 937  *        Currently, we support hashjoin for binary opclauses where
 938  *        the operator is a hashjoinable operator.      The arguments can be
 939  *        anything --- as long as there are no volatile functions in them.
 940  */
 941 static void
 942 check_hashjoinable(RestrictInfo *restrictinfo)
 943 {
 944         Expr       *clause = restrictinfo->clause;
 945         Oid                     opno;
 946
 947         if (!is_opclause(clause))
 948                 return;
 949         if (list_length(((OpExpr *) clause)->args) != 2)
 950                 return;
 951
 952         opno = ((OpExpr *) clause)->opno;
 953
 954         if (op_hashjoinable(opno) &&
 955                 !contain_volatile_functions((Node *) clause))
 956                 restrictinfo->hashjoinoperator = opno;
 957 }