src/backend/optimizer/plan/initsplan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * initsplan.c
   4  *        Target list, qualification, joininfo initialization routines
   5  *
   6  * Portions Copyright (c) 1996-2004, 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.102 2004/08/29 04:12:33 momjian 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 is_pushed_down,
  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                 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(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                 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(Query *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(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                 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(Query *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 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.
 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->rowMarks, relno))
 337                                 ereport(ERROR,
 338                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 339                                                  errmsg("SELECT FOR UPDATE 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 'RestrictInfo' or 'JoinInfo' field
 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(Query *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 involved
 455                  * in lower-level outer joins (this may be an overly strong test).
 456                  */
 457                 Relids          addrelids = NULL;
 458                 Relids          tmprelids;
 459                 int                     relno;
 460
 461                 valid_everywhere = true;
 462                 tmprelids = bms_copy(relids);
 463                 while ((relno = bms_first_member(tmprelids)) >= 0)
 464                 {
 465                         RelOptInfo *rel = find_base_rel(root, relno);
 466
 467                         if (rel->outerjoinset != NULL)
 468                         {
 469                                 addrelids = bms_add_members(addrelids, rel->outerjoinset);
 470                                 valid_everywhere = false;
 471                         }
 472                 }
 473                 bms_free(tmprelids);
 474
 475                 if (bms_is_subset(addrelids, relids))
 476                 {
 477                         /* Qual is not affected by any outer-join restriction */
 478                         can_be_equijoin = true;
 479                 }
 480                 else
 481                 {
 482                         relids = bms_union(relids, addrelids);
 483                         /* Should still be a subset of current scope ... */
 484                         Assert(bms_is_subset(relids, qualscope));
 485
 486                         /*
 487                          * Because application of the qual will be delayed by outer
 488                          * join, we mustn't assume its vars are equal everywhere.
 489                          */
 490                         can_be_equijoin = false;
 491                 }
 492                 bms_free(addrelids);
 493         }
 494
 495         /*
 496          * Mark the qual as "pushed down" if it can be applied at a level
 497          * below its original syntactic level.  This allows us to distinguish
 498          * original JOIN/ON quals from higher-level quals pushed down to the
 499          * same joinrel. A qual originating from WHERE is always considered
 500          * "pushed down".
 501          */
 502         if (!is_pushed_down)
 503                 is_pushed_down = !bms_equal(relids, qualscope);
 504
 505         /*
 506          * Build the RestrictInfo node itself.
 507          */
 508         restrictinfo = make_restrictinfo((Expr *) clause,
 509                                                                          is_pushed_down,
 510                                                                          valid_everywhere);
 511
 512         /*
 513          * Figure out where to attach it.
 514          */
 515         switch (bms_membership(relids))
 516         {
 517                 case BMS_SINGLETON:
 518
 519                         /*
 520                          * There is only one relation participating in 'clause', so
 521                          * 'clause' is a restriction clause for that relation.
 522                          */
 523                         rel = find_base_rel(root, bms_singleton_member(relids));
 524
 525                         /*
 526                          * Check for a "mergejoinable" clause even though it's not a
 527                          * join clause.  This is so that we can recognize that "a.x =
 528                          * a.y" makes x and y eligible to be considered equal, even
 529                          * when they belong to the same rel.  Without this, we would
 530                          * not recognize that "a.x = a.y AND a.x = b.z AND a.y = c.q"
 531                          * allows us to consider z and q equal after their rels are
 532                          * joined.
 533                          */
 534                         if (can_be_equijoin)
 535                                 check_mergejoinable(restrictinfo);
 536
 537                         /*
 538                          * If the clause was deduced from implied equality, check to
 539                          * see whether it is redundant with restriction clauses we
 540                          * already have for this rel.  Note we cannot apply this check
 541                          * to user-written clauses, since we haven't found the
 542                          * canonical pathkey sets yet while processing user clauses.
 543                          * (NB: no comparable check is done in the join-clause case;
 544                          * redundancy will be detected when the join clause is moved
 545                          * into a join rel's restriction list.)
 546                          */
 547                         if (!isdeduced ||
 548                                 !qual_is_redundant(root, restrictinfo,
 549                                                                    rel->baserestrictinfo))
 550                         {
 551                                 /* Add clause to rel's restriction list */
 552                                 rel->baserestrictinfo = lappend(rel->baserestrictinfo,
 553                                                                                                 restrictinfo);
 554                         }
 555                         break;
 556                 case BMS_MULTIPLE:
 557
 558                         /*
 559                          * 'clause' is a join clause, since there is more than one rel
 560                          * in the relid set.
 561                          */
 562
 563                         /*
 564                          * Check for hash or mergejoinable operators.
 565                          *
 566                          * We don't bother setting the hashjoin info if we're not going
 567                          * to need it.  We do want to know about mergejoinable ops in
 568                          * all cases, however, because we use mergejoinable ops for
 569                          * other purposes such as detecting redundant clauses.
 570                          */
 571                         check_mergejoinable(restrictinfo);
 572                         if (enable_hashjoin)
 573                                 check_hashjoinable(restrictinfo);
 574
 575                         /*
 576                          * Add clause to the join lists of all the relevant relations.
 577                          */
 578                         add_join_clause_to_rels(root, restrictinfo, relids);
 579
 580                         /*
 581                          * Add vars used in the join clause to targetlists of their
 582                          * relations, so that they will be emitted by the plan nodes
 583                          * that scan those relations (else they won't be available at
 584                          * the join node!).
 585                          */
 586                         vars = pull_var_clause(clause, false);
 587                         add_vars_to_targetlist(root, vars, relids);
 588                         list_free(vars);
 589                         break;
 590                 default:
 591
 592                         /*
 593                          * 'clause' references no rels, and therefore we have no place
 594                          * to attach it.  Shouldn't get here if callers are working
 595                          * properly.
 596                          */
 597                         elog(ERROR, "cannot cope with variable-free clause");
 598                         break;
 599         }
 600
 601         /*
 602          * If the clause has a mergejoinable operator, and is not an
 603          * outer-join qualification nor bubbled up due to an outer join, then
 604          * the two sides represent equivalent PathKeyItems for path keys: any
 605          * path that is sorted by one side will also be sorted by the other
 606          * (as soon as the two rels are joined, that is).  Record the key
 607          * equivalence for future use.  (We can skip this for a deduced
 608          * clause, since the keys are already known equivalent in that case.)
 609          */
 610         if (can_be_equijoin &&
 611                 restrictinfo->mergejoinoperator != InvalidOid &&
 612                 !isdeduced)
 613                 add_equijoined_keys(root, restrictinfo);
 614 }
 615
 616 /*
 617  * process_implied_equality
 618  *        Check to see whether we already have a restrictinfo item that says
 619  *        item1 = item2, and create one if not; or if delete_it is true,
 620  *        remove any such restrictinfo item.
 621  *
 622  * This processing is a consequence of transitivity of mergejoin equality:
 623  * if we have mergejoinable clauses A = B and B = C, we can deduce A = C
 624  * (where = is an appropriate mergejoinable operator).  See path/pathkeys.c
 625  * for more details.
 626  */
 627 void
 628 process_implied_equality(Query *root,
 629                                                  Node *item1, Node *item2,
 630                                                  Oid sortop1, Oid sortop2,
 631                                                  Relids item1_relids, Relids item2_relids,
 632                                                  bool delete_it)
 633 {
 634         Relids          relids;
 635         BMS_Membership membership;
 636         RelOptInfo *rel1;
 637         List       *restrictlist;
 638         ListCell   *itm;
 639         Oid                     ltype,
 640                                 rtype;
 641         Operator        eq_operator;
 642         Form_pg_operator pgopform;
 643         Expr       *clause;
 644
 645         /* Get set of relids referenced in the two expressions */
 646         relids = bms_union(item1_relids, item2_relids);
 647         membership = bms_membership(relids);
 648
 649         /*
 650          * generate_implied_equalities() shouldn't call me on two constants.
 651          */
 652         Assert(membership != BMS_EMPTY_SET);
 653
 654         /*
 655          * If the exprs involve a single rel, we need to look at that rel's
 656          * baserestrictinfo list.  If multiple rels, any one will have a
 657          * joininfo node for the rest, and we can scan any of 'em.
 658          */
 659         if (membership == BMS_SINGLETON)
 660         {
 661                 rel1 = find_base_rel(root, bms_singleton_member(relids));
 662                 restrictlist = rel1->baserestrictinfo;
 663         }
 664         else
 665         {
 666                 Relids          other_rels;
 667                 int                     first_rel;
 668                 JoinInfo   *joininfo;
 669
 670                 /* Copy relids, find and remove one member */
 671                 other_rels = bms_copy(relids);
 672                 first_rel = bms_first_member(other_rels);
 673
 674                 rel1 = find_base_rel(root, first_rel);
 675
 676                 /* use remaining members to find join node */
 677                 joininfo = find_joininfo_node(rel1, other_rels);
 678
 679                 restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL;
 680
 681                 bms_free(other_rels);
 682         }
 683
 684         /*
 685          * Scan to see if equality is already known.  If so, we're done in the
 686          * add case, and done after removing it in the delete case.
 687          */
 688         foreach(itm, restrictlist)
 689         {
 690                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
 691                 Node       *left,
 692                                    *right;
 693
 694                 if (restrictinfo->mergejoinoperator == InvalidOid)
 695                         continue;                       /* ignore non-mergejoinable clauses */
 696                 /* We now know the restrictinfo clause is a binary opclause */
 697                 left = get_leftop(restrictinfo->clause);
 698                 right = get_rightop(restrictinfo->clause);
 699                 if ((equal(item1, left) && equal(item2, right)) ||
 700                         (equal(item2, left) && equal(item1, right)))
 701                 {
 702                         /* found a matching clause */
 703                         if (delete_it)
 704                         {
 705                                 if (membership == BMS_SINGLETON)
 706                                 {
 707                                         /* delete it from local restrictinfo list */
 708                                         rel1->baserestrictinfo = list_delete_ptr(rel1->baserestrictinfo,
 709                                                                                                                          restrictinfo);
 710                                 }
 711                                 else
 712                                 {
 713                                         /* let joininfo.c do it */
 714                                         remove_join_clause_from_rels(root, restrictinfo, relids);
 715                                 }
 716                         }
 717                         return;                         /* done */
 718                 }
 719         }
 720
 721         /* Didn't find it.  Done if deletion requested */
 722         if (delete_it)
 723                 return;
 724
 725         /*
 726          * This equality is new information, so construct a clause
 727          * representing it to add to the query data structures.
 728          */
 729         ltype = exprType(item1);
 730         rtype = exprType(item2);
 731         eq_operator = compatible_oper(list_make1(makeString("=")),
 732                                                                   ltype, rtype, true);
 733         if (!HeapTupleIsValid(eq_operator))
 734         {
 735                 /*
 736                  * Would it be safe to just not add the equality to the query if
 737                  * we have no suitable equality operator for the combination of
 738                  * datatypes?  NO, because sortkey selection may screw up anyway.
 739                  */
 740                 ereport(ERROR,
 741                                 (errcode(ERRCODE_UNDEFINED_FUNCTION),
 742                                  errmsg("could not identify an equality operator for types %s and %s",
 743                                                 format_type_be(ltype), format_type_be(rtype))));
 744         }
 745         pgopform = (Form_pg_operator) GETSTRUCT(eq_operator);
 746
 747         /*
 748          * Let's just make sure this appears to be a compatible operator.
 749          */
 750         if (pgopform->oprlsortop != sortop1 ||
 751                 pgopform->oprrsortop != sortop2 ||
 752                 pgopform->oprresult != BOOLOID)
 753                 ereport(ERROR,
 754                                 (errcode(ERRCODE_INVALID_FUNCTION_DEFINITION),
 755                                  errmsg("equality operator for types %s and %s should be merge-joinable, but isn't",
 756                                                 format_type_be(ltype), format_type_be(rtype))));
 757
 758         /*
 759          * Now we can build the new clause.  Copy to ensure it shares no
 760          * substructure with original (this is necessary in case there are
 761          * subselects in there...)
 762          */
 763         clause = make_opclause(oprid(eq_operator),      /* opno */
 764                                                    BOOLOID,             /* opresulttype */
 765                                                    false,               /* opretset */
 766                                                    (Expr *) copyObject(item1),
 767                                                    (Expr *) copyObject(item2));
 768
 769         ReleaseSysCache(eq_operator);
 770
 771         /*
 772          * Push the new clause into all the appropriate restrictinfo lists.
 773          *
 774          * Note: we mark the qual "pushed down" to ensure that it can never be
 775          * taken for an original JOIN/ON clause.
 776          */
 777         distribute_qual_to_rels(root, (Node *) clause,
 778                                                         true, true, NULL, relids);
 779 }
 780
 781 /*
 782  * qual_is_redundant
 783  *        Detect whether an implied-equality qual that turns out to be a
 784  *        restriction clause for a single base relation is redundant with
 785  *        already-known restriction clauses for that rel.  This occurs with,
 786  *        for example,
 787  *                              SELECT * FROM tab WHERE f1 = f2 AND f2 = f3;
 788  *        We need to suppress the redundant condition to avoid computing
 789  *        too-small selectivity, not to mention wasting time at execution.
 790  *
 791  * Note: quals of the form "var = const" are never considered redundant,
 792  * only those of the form "var = var".  This is needed because when we
 793  * have constants in an implied-equality set, we use a different strategy
 794  * that suppresses all "var = var" deductions.  We must therefore keep
 795  * all the "var = const" quals.
 796  */
 797 static bool
 798 qual_is_redundant(Query *root,
 799                                   RestrictInfo *restrictinfo,
 800                                   List *restrictlist)
 801 {
 802         Node       *newleft;
 803         Node       *newright;
 804         List       *oldquals;
 805         ListCell   *olditem;
 806         List       *equalexprs;
 807         bool            someadded;
 808
 809         /* Never redundant unless vars appear on both sides */
 810         if (bms_is_empty(restrictinfo->left_relids) ||
 811                 bms_is_empty(restrictinfo->right_relids))
 812                 return false;
 813
 814         newleft = get_leftop(restrictinfo->clause);
 815         newright = get_rightop(restrictinfo->clause);
 816
 817         /*
 818          * Set cached pathkeys.  NB: it is okay to do this now because this
 819          * routine is only invoked while we are generating implied equalities.
 820          * Therefore, the equi_key_list is already complete and so we can
 821          * correctly determine canonical pathkeys.
 822          */
 823         cache_mergeclause_pathkeys(root, restrictinfo);
 824         /* If different, say "not redundant" (should never happen) */
 825         if (restrictinfo->left_pathkey != restrictinfo->right_pathkey)
 826                 return false;
 827
 828         /*
 829          * Scan existing quals to find those referencing same pathkeys.
 830          * Usually there will be few, if any, so build a list of just the
 831          * interesting ones.
 832          */
 833         oldquals = NIL;
 834         foreach(olditem, restrictlist)
 835         {
 836                 RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
 837
 838                 if (oldrinfo->mergejoinoperator != InvalidOid)
 839                 {
 840                         cache_mergeclause_pathkeys(root, oldrinfo);
 841                         if (restrictinfo->left_pathkey == oldrinfo->left_pathkey &&
 842                                 restrictinfo->right_pathkey == oldrinfo->right_pathkey)
 843                                 oldquals = lcons(oldrinfo, oldquals);
 844                 }
 845         }
 846         if (oldquals == NIL)
 847                 return false;
 848
 849         /*
 850          * Now, we want to develop a list of exprs that are known equal to the
 851          * left side of the new qual.  We traverse the old-quals list
 852          * repeatedly to transitively expand the exprs list.  If at any point
 853          * we find we can reach the right-side expr of the new qual, we are
 854          * done.  We give up when we can't expand the equalexprs list any
 855          * more.
 856          */
 857         equalexprs = list_make1(newleft);
 858         do
 859         {
 860                 someadded = false;
 861                 /* cannot use foreach here because of possible list_delete */
 862                 olditem = list_head(oldquals);
 863                 while (olditem)
 864                 {
 865                         RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
 866                         Node       *oldleft = get_leftop(oldrinfo->clause);
 867                         Node       *oldright = get_rightop(oldrinfo->clause);
 868                         Node       *newguy = NULL;
 869
 870                         /* must advance olditem before list_delete possibly pfree's it */
 871                         olditem = lnext(olditem);
 872
 873                         if (list_member(equalexprs, oldleft))
 874                                 newguy = oldright;
 875                         else if (list_member(equalexprs, oldright))
 876                                 newguy = oldleft;
 877                         else
 878                                 continue;
 879                         if (equal(newguy, newright))
 880                                 return true;    /* we proved new clause is redundant */
 881                         equalexprs = lcons(newguy, equalexprs);
 882                         someadded = true;
 883
 884                         /*
 885                          * Remove this qual from list, since we don't need it anymore.
 886                          */
 887                         oldquals = list_delete_ptr(oldquals, oldrinfo);
 888                 }
 889         } while (someadded);
 890
 891         return false;                           /* it's not redundant */
 892 }
 893
 894
 895 /*****************************************************************************
 896  *
 897  *       CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
 898  *
 899  *****************************************************************************/
 900
 901 /*
 902  * check_mergejoinable
 903  *        If the restrictinfo's clause is mergejoinable, set the mergejoin
 904  *        info fields in the restrictinfo.
 905  *
 906  *        Currently, we support mergejoin for binary opclauses where
 907  *        the operator is a mergejoinable operator.  The arguments can be
 908  *        anything --- as long as there are no volatile functions in them.
 909  */
 910 static void
 911 check_mergejoinable(RestrictInfo *restrictinfo)
 912 {
 913         Expr       *clause = restrictinfo->clause;
 914         Oid                     opno,
 915                                 leftOp,
 916                                 rightOp;
 917
 918         if (!is_opclause(clause))
 919                 return;
 920         if (list_length(((OpExpr *) clause)->args) != 2)
 921                 return;
 922
 923         opno = ((OpExpr *) clause)->opno;
 924
 925         if (op_mergejoinable(opno,
 926                                                  &leftOp,
 927                                                  &rightOp) &&
 928                 !contain_volatile_functions((Node *) clause))
 929         {
 930                 restrictinfo->mergejoinoperator = opno;
 931                 restrictinfo->left_sortop = leftOp;
 932                 restrictinfo->right_sortop = rightOp;
 933         }
 934 }
 935
 936 /*
 937  * check_hashjoinable
 938  *        If the restrictinfo's clause is hashjoinable, set the hashjoin
 939  *        info fields in the restrictinfo.
 940  *
 941  *        Currently, we support hashjoin for binary opclauses where
 942  *        the operator is a hashjoinable operator.      The arguments can be
 943  *        anything --- as long as there are no volatile functions in them.
 944  */
 945 static void
 946 check_hashjoinable(RestrictInfo *restrictinfo)
 947 {
 948         Expr       *clause = restrictinfo->clause;
 949         Oid                     opno;
 950
 951         if (!is_opclause(clause))
 952                 return;
 953         if (list_length(((OpExpr *) clause)->args) != 2)
 954                 return;
 955
 956         opno = ((OpExpr *) clause)->opno;
 957
 958         if (op_hashjoinable(opno) &&
 959                 !contain_volatile_functions((Node *) clause))
 960                 restrictinfo->hashjoinoperator = opno;
 961 }