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