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.97 2004/01/05 05:07:35 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 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                 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  * 'is_pushed_down': if TRUE, force the clause to be marked 'is_pushed_down'
 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  * 'is_pushed_down' will be TRUE.
 369  */
 370 static void
 371 distribute_qual_to_rels(Query *root, Node *clause,
 372                                                 bool is_pushed_down,
 373                                                 bool isdeduced,
 374                                                 Relids outerjoin_nonnullable,
 375                                                 Relids qualscope)
 376 {
 377         Relids          relids;
 378         bool            valid_everywhere;
 379         bool            can_be_equijoin;
 380         RestrictInfo *restrictinfo;
 381         RelOptInfo *rel;
 382         List       *vars;
 383
 384         /*
 385          * Retrieve all relids mentioned within the clause.
 386          */
 387         relids = pull_varnos(clause);
 388
 389         /*
 390          * Cross-check: clause should contain no relids not within its scope.
 391          * Otherwise the parser messed up.
 392          */
 393         if (!bms_is_subset(relids, qualscope))
 394                 elog(ERROR, "JOIN qualification may not refer to other relations");
 395
 396         /*
 397          * If the clause is variable-free, we force it to be evaluated at its
 398          * original syntactic level.  Note that this should not happen for
 399          * top-level clauses, because query_planner() special-cases them.  But
 400          * it will happen for variable-free JOIN/ON clauses.  We don't have to
 401          * be real smart about such a case, we just have to be correct.
 402          */
 403         if (bms_is_empty(relids))
 404                 relids = qualscope;
 405
 406         /*
 407          * Check to see if clause application must be delayed by outer-join
 408          * considerations.
 409          */
 410         if (isdeduced)
 411         {
 412                 /*
 413                  * If the qual came from implied-equality deduction, we can
 414                  * evaluate the qual at its natural semantic level.  It is not
 415                  * affected by any outer-join rules (else we'd not have decided
 416                  * the vars were equal).
 417                  */
 418                 Assert(bms_equal(relids, qualscope));
 419                 valid_everywhere = true;
 420                 can_be_equijoin = true;
 421         }
 422         else if (bms_overlap(relids, outerjoin_nonnullable))
 423         {
 424                 /*
 425                  * The qual is attached to an outer join and mentions (some of
 426                  * the) rels on the nonnullable side.  Force the qual to be
 427                  * evaluated exactly at the level of joining corresponding to the
 428                  * outer join. We cannot let it get pushed down into the
 429                  * nonnullable side, since then we'd produce no output rows,
 430                  * rather than the intended single null-extended row, for any
 431                  * nonnullable-side rows failing the qual.
 432                  *
 433                  * Note: an outer-join qual that mentions only nullable-side rels can
 434                  * be pushed down into the nullable side without changing the join
 435                  * result, so we treat it the same as an ordinary inner-join qual.
 436                  */
 437                 relids = qualscope;
 438                 valid_everywhere = false;
 439                 can_be_equijoin = false;
 440         }
 441         else
 442         {
 443                 /*
 444                  * For a non-outer-join qual, we can evaluate the qual as soon as
 445                  * (1) we have all the rels it mentions, and (2) we are at or
 446                  * above any outer joins that can null any of these rels and are
 447                  * below the syntactic location of the given qual. To enforce the
 448                  * latter, scan the base rels listed in relids, and merge their
 449                  * outer-join sets into the clause's own reference list.  At the
 450                  * time we are called, the outerjoinset of each baserel will show
 451                  * exactly those outer joins that are below the qual in the join
 452                  * tree.
 453                  *
 454                  * We also need to determine whether the qual is "valid everywhere",
 455                  * which is true if the qual mentions no variables that are involved
 456                  * in lower-level outer joins (this may be an overly 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
 513         /*
 514          * Figure out where to attach it.
 515          */
 516         switch (bms_membership(relids))
 517         {
 518                 case BMS_SINGLETON:
 519
 520                         /*
 521                          * There is only one relation participating in 'clause', so
 522                          * 'clause' is a restriction clause for that relation.
 523                          */
 524                         rel = find_base_rel(root, bms_singleton_member(relids));
 525
 526                         /*
 527                          * Check for a "mergejoinable" clause even though it's not a
 528                          * join clause.  This is so that we can recognize that "a.x =
 529                          * a.y" makes x and y eligible to be considered equal, even
 530                          * when they belong to the same rel.  Without this, we would
 531                          * not recognize that "a.x = a.y AND a.x = b.z AND a.y = c.q"
 532                          * allows us to consider z and q equal after their rels are
 533                          * joined.
 534                          */
 535                         if (can_be_equijoin)
 536                                 check_mergejoinable(restrictinfo);
 537
 538                         /*
 539                          * If the clause was deduced from implied equality, check to
 540                          * see whether it is redundant with restriction clauses we
 541                          * already have for this rel.  Note we cannot apply this check
 542                          * to user-written clauses, since we haven't found the
 543                          * canonical pathkey sets yet while processing user clauses.
 544                          * (NB: no comparable check is done in the join-clause case;
 545                          * redundancy will be detected when the join clause is moved
 546                          * into a join rel's restriction list.)
 547                          */
 548                         if (!isdeduced ||
 549                                 !qual_is_redundant(root, restrictinfo,
 550                                                                    rel->baserestrictinfo))
 551                         {
 552                                 /* Add clause to rel's restriction list */
 553                                 rel->baserestrictinfo = lappend(rel->baserestrictinfo,
 554                                                                                                 restrictinfo);
 555                         }
 556                         break;
 557                 case BMS_MULTIPLE:
 558
 559                         /*
 560                          * 'clause' is a join clause, since there is more than one rel
 561                          * in the relid set.
 562                          */
 563
 564                         /*
 565                          * Check for hash or mergejoinable operators.
 566                          *
 567                          * We don't bother setting the hashjoin info if we're not going
 568                          * to need it.  We do want to know about mergejoinable ops in
 569                          * all cases, however, because we use mergejoinable ops for
 570                          * other purposes such as detecting redundant clauses.
 571                          */
 572                         check_mergejoinable(restrictinfo);
 573                         if (enable_hashjoin)
 574                                 check_hashjoinable(restrictinfo);
 575
 576                         /*
 577                          * Add clause to the join lists of all the relevant relations.
 578                          */
 579                         add_join_clause_to_rels(root, restrictinfo, relids);
 580
 581                         /*
 582                          * Add vars used in the join clause to targetlists of their
 583                          * relations, so that they will be emitted by the plan nodes
 584                          * that scan those relations (else they won't be available at
 585                          * the join node!).
 586                          */
 587                         vars = pull_var_clause(clause, false);
 588                         add_vars_to_targetlist(root, vars, relids);
 589                         freeList(vars);
 590                         break;
 591                 default:
 592
 593                         /*
 594                          * 'clause' references no rels, and therefore we have no place
 595                          * to attach it.  Shouldn't get here if callers are working
 596                          * properly.
 597                          */
 598                         elog(ERROR, "cannot cope with variable-free clause");
 599                         break;
 600         }
 601
 602         /*
 603          * If the clause has a mergejoinable operator, and is not an
 604          * outer-join qualification nor bubbled up due to an outer join, then
 605          * the two sides represent equivalent PathKeyItems for path keys: any
 606          * path that is sorted by one side will also be sorted by the other
 607          * (as soon as the two rels are joined, that is).  Record the key
 608          * equivalence for future use.  (We can skip this for a deduced
 609          * clause, since the keys are already known equivalent in that case.)
 610          */
 611         if (can_be_equijoin &&
 612                 restrictinfo->mergejoinoperator != InvalidOid &&
 613                 !isdeduced)
 614                 add_equijoined_keys(root, restrictinfo);
 615 }
 616
 617 /*
 618  * process_implied_equality
 619  *        Check to see whether we already have a restrictinfo item that says
 620  *        item1 = item2, and create one if not; or if delete_it is true,
 621  *        remove any such restrictinfo item.
 622  *
 623  * This processing is a consequence of transitivity of mergejoin equality:
 624  * if we have mergejoinable clauses A = B and B = C, we can deduce A = C
 625  * (where = is an appropriate mergejoinable operator).  See path/pathkeys.c
 626  * for more details.
 627  */
 628 void
 629 process_implied_equality(Query *root,
 630                                                  Node *item1, Node *item2,
 631                                                  Oid sortop1, Oid sortop2,
 632                                                  Relids item1_relids, Relids item2_relids,
 633                                                  bool delete_it)
 634 {
 635         Relids          relids;
 636         BMS_Membership membership;
 637         RelOptInfo *rel1;
 638         List       *restrictlist;
 639         List       *itm;
 640         Oid                     ltype,
 641                                 rtype;
 642         Operator        eq_operator;
 643         Form_pg_operator pgopform;
 644         Expr       *clause;
 645
 646         /* Get set of relids referenced in the two expressions */
 647         relids = bms_union(item1_relids, item2_relids);
 648         membership = bms_membership(relids);
 649
 650         /*
 651          * generate_implied_equalities() shouldn't call me on two constants.
 652          */
 653         Assert(membership != BMS_EMPTY_SET);
 654
 655         /*
 656          * If the exprs involve a single rel, we need to look at that rel's
 657          * baserestrictinfo list.  If multiple rels, any one will have a
 658          * joininfo node for the rest, and we can scan any of 'em.
 659          */
 660         if (membership == BMS_SINGLETON)
 661         {
 662                 rel1 = find_base_rel(root, bms_singleton_member(relids));
 663                 restrictlist = rel1->baserestrictinfo;
 664         }
 665         else
 666         {
 667                 Relids          other_rels;
 668                 int                     first_rel;
 669                 JoinInfo   *joininfo;
 670
 671                 /* Copy relids, find and remove one member */
 672                 other_rels = bms_copy(relids);
 673                 first_rel = bms_first_member(other_rels);
 674
 675                 rel1 = find_base_rel(root, first_rel);
 676
 677                 /* use remaining members to find join node */
 678                 joininfo = find_joininfo_node(rel1, other_rels);
 679
 680                 restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL;
 681
 682                 bms_free(other_rels);
 683         }
 684
 685         /*
 686          * Scan to see if equality is already known.  If so, we're done in the
 687          * add case, and done after removing it in the delete case.
 688          */
 689         foreach(itm, restrictlist)
 690         {
 691                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
 692                 Node       *left,
 693                                    *right;
 694
 695                 if (restrictinfo->mergejoinoperator == InvalidOid)
 696                         continue;                       /* ignore non-mergejoinable clauses */
 697                 /* We now know the restrictinfo clause is a binary opclause */
 698                 left = get_leftop(restrictinfo->clause);
 699                 right = get_rightop(restrictinfo->clause);
 700                 if ((equal(item1, left) && equal(item2, right)) ||
 701                         (equal(item2, left) && equal(item1, right)))
 702                 {
 703                         /* found a matching clause */
 704                         if (delete_it)
 705                         {
 706                                 if (membership == BMS_SINGLETON)
 707                                 {
 708                                         /* delete it from local restrictinfo list */
 709                                         rel1->baserestrictinfo = lremove(restrictinfo,
 710                                                                                                  rel1->baserestrictinfo);
 711                                 }
 712                                 else
 713                                 {
 714                                         /* let joininfo.c do it */
 715                                         remove_join_clause_from_rels(root, restrictinfo, relids);
 716                                 }
 717                         }
 718                         return;                         /* done */
 719                 }
 720         }
 721
 722         /* Didn't find it.  Done if deletion requested */
 723         if (delete_it)
 724                 return;
 725
 726         /*
 727          * This equality is new information, so construct a clause
 728          * representing it to add to the query data structures.
 729          */
 730         ltype = exprType(item1);
 731         rtype = exprType(item2);
 732         eq_operator = compatible_oper(makeList1(makeString("=")),
 733                                                                   ltype, rtype, true);
 734         if (!HeapTupleIsValid(eq_operator))
 735         {
 736                 /*
 737                  * Would it be safe to just not add the equality to the query if
 738                  * we have no suitable equality operator for the combination of
 739                  * datatypes?  NO, because sortkey selection may screw up anyway.
 740                  */
 741                 ereport(ERROR,
 742                                 (errcode(ERRCODE_UNDEFINED_FUNCTION),
 743                                  errmsg("could not identify an equality operator for types %s and %s",
 744                                                 format_type_be(ltype), format_type_be(rtype))));
 745         }
 746         pgopform = (Form_pg_operator) GETSTRUCT(eq_operator);
 747
 748         /*
 749          * Let's just make sure this appears to be a compatible operator.
 750          */
 751         if (pgopform->oprlsortop != sortop1 ||
 752                 pgopform->oprrsortop != sortop2 ||
 753                 pgopform->oprresult != BOOLOID)
 754                 ereport(ERROR,
 755                                 (errcode(ERRCODE_INVALID_FUNCTION_DEFINITION),
 756                                  errmsg("equality operator for types %s and %s should be merge-joinable, but isn't",
 757                                                 format_type_be(ltype), format_type_be(rtype))));
 758
 759         clause = make_opclause(oprid(eq_operator),      /* opno */
 760                                                    BOOLOID,             /* opresulttype */
 761                                                    false,               /* opretset */
 762                                                    (Expr *) item1,
 763                                                    (Expr *) 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(Query *root,
 795                                   RestrictInfo *restrictinfo,
 796                                   List *restrictlist)
 797 {
 798         Node       *newleft;
 799         Node       *newright;
 800         List       *oldquals;
 801         List       *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 = makeList1(newleft);
 854         do
 855         {
 856                 someadded = false;
 857                 /* cannot use foreach here because of possible lremove */
 858                 olditem = 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 lremove possibly pfree's it */
 867                         olditem = lnext(olditem);
 868
 869                         if (member(oldleft, equalexprs))
 870                                 newguy = oldright;
 871                         else if (member(oldright, equalexprs))
 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 = lremove(oldrinfo, oldquals);
 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 (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 (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 }