granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/equivclass.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * equivclass.c
   4  *        Routines for managing EquivalenceClasses
   5  *
   6  * See src/backend/optimizer/README for discussion of EquivalenceClasses.
   7  *
   8  *
   9  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  10  * Portions Copyright (c) 1994, Regents of the University of California
  11  *
  12  * IDENTIFICATION
  13  *        $PostgreSQL: pgsql/src/backend/optimizer/path/equivclass.c,v 1.11 2008/08/02 21:31:59 tgl Exp $
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19 #include "access/skey.h"
  20 #include "optimizer/clauses.h"
  21 #include "optimizer/cost.h"
  22 #include "optimizer/paths.h"
  23 #include "optimizer/planmain.h"
  24 #include "optimizer/prep.h"
  25 #include "optimizer/var.h"
  26 #include "utils/lsyscache.h"
  27
  28
  29 static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
  30                           Expr *expr, Relids relids,
  31                           bool is_child, Oid datatype);
  32 static void generate_base_implied_equalities_const(PlannerInfo *root,
  33                                                                            EquivalenceClass *ec);
  34 static void generate_base_implied_equalities_no_const(PlannerInfo *root,
  35                                                                                   EquivalenceClass *ec);
  36 static void generate_base_implied_equalities_broken(PlannerInfo *root,
  37                                                                                 EquivalenceClass *ec);
  38 static List *generate_join_implied_equalities_normal(PlannerInfo *root,
  39                                                                                 EquivalenceClass *ec,
  40                                                                                 RelOptInfo *joinrel,
  41                                                                                 RelOptInfo *outer_rel,
  42                                                                                 RelOptInfo *inner_rel);
  43 static List *generate_join_implied_equalities_broken(PlannerInfo *root,
  44                                                                                 EquivalenceClass *ec,
  45                                                                                 RelOptInfo *joinrel,
  46                                                                                 RelOptInfo *outer_rel,
  47                                                                                 RelOptInfo *inner_rel);
  48 static Oid select_equality_operator(EquivalenceClass *ec,
  49                                                  Oid lefttype, Oid righttype);
  50 static RestrictInfo *create_join_clause(PlannerInfo *root,
  51                                    EquivalenceClass *ec, Oid opno,
  52                                    EquivalenceMember *leftem,
  53                                    EquivalenceMember *rightem,
  54                                    EquivalenceClass *parent_ec);
  55 static bool reconsider_outer_join_clause(PlannerInfo *root,
  56                                                          RestrictInfo *rinfo,
  57                                                          bool outer_on_left);
  58 static bool reconsider_full_join_clause(PlannerInfo *root,
  59                                                         RestrictInfo *rinfo);
  60
  61
  62 /*
  63  * process_equivalence
  64  *        The given clause has a mergejoinable operator and can be applied without
  65  *        any delay by an outer join, so its two sides can be considered equal
  66  *        anywhere they are both computable; moreover that equality can be
  67  *        extended transitively.  Record this knowledge in the EquivalenceClass
  68  *        data structure.  Returns TRUE if successful, FALSE if not (in which
  69  *        case caller should treat the clause as ordinary, not an equivalence).
  70  *
  71  * If below_outer_join is true, then the clause was found below the nullable
  72  * side of an outer join, so its sides might validly be both NULL rather than
  73  * strictly equal.      We can still deduce equalities in such cases, but we take
  74  * care to mark an EquivalenceClass if it came from any such clauses.  Also,
  75  * we have to check that both sides are either pseudo-constants or strict
  76  * functions of Vars, else they might not both go to NULL above the outer
  77  * join.  (This is the reason why we need a failure return.  It's more
  78  * convenient to check this case here than at the call sites...)
  79  *
  80  * Note: constructing merged EquivalenceClasses is a standard UNION-FIND
  81  * problem, for which there exist better data structures than simple lists.
  82  * If this code ever proves to be a bottleneck then it could be sped up ---
  83  * but for now, simple is beautiful.
  84  *
  85  * Note: this is only called during planner startup, not during GEQO
  86  * exploration, so we need not worry about whether we're in the right
  87  * memory context.
  88  */
  89 bool
  90 process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
  91                                         bool below_outer_join)
  92 {
  93         Expr       *clause = restrictinfo->clause;
  94         Oid                     opno,
  95                                 item1_type,
  96                                 item2_type;
  97         Expr       *item1;
  98         Expr       *item2;
  99         Relids          item1_relids,
 100                                 item2_relids;
 101         List       *opfamilies;
 102         EquivalenceClass *ec1,
 103                            *ec2;
 104         EquivalenceMember *em1,
 105                            *em2;
 106         ListCell   *lc1;
 107
 108         /* Extract info from given clause */
 109         Assert(is_opclause(clause));
 110         opno = ((OpExpr *) clause)->opno;
 111         item1 = (Expr *) get_leftop(clause);
 112         item2 = (Expr *) get_rightop(clause);
 113         item1_relids = restrictinfo->left_relids;
 114         item2_relids = restrictinfo->right_relids;
 115
 116         /*
 117          * If below outer join, check for strictness, else reject.
 118          */
 119         if (below_outer_join)
 120         {
 121                 if (!bms_is_empty(item1_relids) &&
 122                         contain_nonstrict_functions((Node *) item1))
 123                         return false;           /* LHS is non-strict but not constant */
 124                 if (!bms_is_empty(item2_relids) &&
 125                         contain_nonstrict_functions((Node *) item2))
 126                         return false;           /* RHS is non-strict but not constant */
 127         }
 128
 129         /*
 130          * We use the declared input types of the operator, not exprType() of the
 131          * inputs, as the nominal datatypes for opfamily lookup.  This presumes
 132          * that btree operators are always registered with amoplefttype and
 133          * amoprighttype equal to their declared input types.  We will need this
 134          * info anyway to build EquivalenceMember nodes, and by extracting it now
 135          * we can use type comparisons to short-circuit some equal() tests.
 136          */
 137         op_input_types(opno, &item1_type, &item2_type);
 138
 139         opfamilies = restrictinfo->mergeopfamilies;
 140
 141         /*
 142          * Sweep through the existing EquivalenceClasses looking for matches to
 143          * item1 and item2.  These are the possible outcomes:
 144          *
 145          * 1. We find both in the same EC.      The equivalence is already known, so
 146          * there's nothing to do.
 147          *
 148          * 2. We find both in different ECs.  Merge the two ECs together.
 149          *
 150          * 3. We find just one.  Add the other to its EC.
 151          *
 152          * 4. We find neither.  Make a new, two-entry EC.
 153          *
 154          * Note: since all ECs are built through this process, it's impossible
 155          * that we'd match an item in more than one existing EC.  It is possible
 156          * to match more than once within an EC, if someone fed us something silly
 157          * like "WHERE X=X".  (However, we can't simply discard such clauses,
 158          * since they should fail when X is null; so we will build a 2-member EC
 159          * to ensure the correct restriction clause gets generated.  Hence there
 160          * is no shortcut here for item1 and item2 equal.)
 161          */
 162         ec1 = ec2 = NULL;
 163         em1 = em2 = NULL;
 164         foreach(lc1, root->eq_classes)
 165         {
 166                 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 167                 ListCell   *lc2;
 168
 169                 /* Never match to a volatile EC */
 170                 if (cur_ec->ec_has_volatile)
 171                         continue;
 172
 173                 /*
 174                  * A "match" requires matching sets of btree opfamilies.  Use of
 175                  * equal() for this test has implications discussed in the comments
 176                  * for get_mergejoin_opfamilies().
 177                  */
 178                 if (!equal(opfamilies, cur_ec->ec_opfamilies))
 179                         continue;
 180
 181                 foreach(lc2, cur_ec->ec_members)
 182                 {
 183                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 184
 185                         Assert(!cur_em->em_is_child);           /* no children yet */
 186
 187                         /*
 188                          * If below an outer join, don't match constants: they're not as
 189                          * constant as they look.
 190                          */
 191                         if ((below_outer_join || cur_ec->ec_below_outer_join) &&
 192                                 cur_em->em_is_const)
 193                                 continue;
 194
 195                         if (!ec1 &&
 196                                 item1_type == cur_em->em_datatype &&
 197                                 equal(item1, cur_em->em_expr))
 198                         {
 199                                 ec1 = cur_ec;
 200                                 em1 = cur_em;
 201                                 if (ec2)
 202                                         break;
 203                         }
 204
 205                         if (!ec2 &&
 206                                 item2_type == cur_em->em_datatype &&
 207                                 equal(item2, cur_em->em_expr))
 208                         {
 209                                 ec2 = cur_ec;
 210                                 em2 = cur_em;
 211                                 if (ec1)
 212                                         break;
 213                         }
 214                 }
 215
 216                 if (ec1 && ec2)
 217                         break;
 218         }
 219
 220         /* Sweep finished, what did we find? */
 221
 222         if (ec1 && ec2)
 223         {
 224                 /* If case 1, nothing to do, except add to sources */
 225                 if (ec1 == ec2)
 226                 {
 227                         ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 228                         ec1->ec_below_outer_join |= below_outer_join;
 229                         /* mark the RI as usable with this pair of EMs */
 230                         /* NB: can't set left_ec/right_ec until merging is finished */
 231                         restrictinfo->left_em = em1;
 232                         restrictinfo->right_em = em2;
 233                         return true;
 234                 }
 235
 236                 /*
 237                  * Case 2: need to merge ec1 and ec2.  We add ec2's items to ec1, then
 238                  * set ec2's ec_merged link to point to ec1 and remove ec2 from the
 239                  * eq_classes list.  We cannot simply delete ec2 because that could
 240                  * leave dangling pointers in existing PathKeys.  We leave it behind
 241                  * with a link so that the merged EC can be found.
 242                  */
 243                 ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
 244                 ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
 245                 ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
 246                 ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
 247                 ec1->ec_has_const |= ec2->ec_has_const;
 248                 /* can't need to set has_volatile */
 249                 ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
 250                 ec2->ec_merged = ec1;
 251                 root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
 252                 /* just to avoid debugging confusion w/ dangling pointers: */
 253                 ec2->ec_members = NIL;
 254                 ec2->ec_sources = NIL;
 255                 ec2->ec_derives = NIL;
 256                 ec2->ec_relids = NULL;
 257                 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 258                 ec1->ec_below_outer_join |= below_outer_join;
 259                 /* mark the RI as usable with this pair of EMs */
 260                 restrictinfo->left_em = em1;
 261                 restrictinfo->right_em = em2;
 262         }
 263         else if (ec1)
 264         {
 265                 /* Case 3: add item2 to ec1 */
 266                 em2 = add_eq_member(ec1, item2, item2_relids, false, item2_type);
 267                 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 268                 ec1->ec_below_outer_join |= below_outer_join;
 269                 /* mark the RI as usable with this pair of EMs */
 270                 restrictinfo->left_em = em1;
 271                 restrictinfo->right_em = em2;
 272         }
 273         else if (ec2)
 274         {
 275                 /* Case 3: add item1 to ec2 */
 276                 em1 = add_eq_member(ec2, item1, item1_relids, false, item1_type);
 277                 ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
 278                 ec2->ec_below_outer_join |= below_outer_join;
 279                 /* mark the RI as usable with this pair of EMs */
 280                 restrictinfo->left_em = em1;
 281                 restrictinfo->right_em = em2;
 282         }
 283         else
 284         {
 285                 /* Case 4: make a new, two-entry EC */
 286                 EquivalenceClass *ec = makeNode(EquivalenceClass);
 287
 288                 ec->ec_opfamilies = opfamilies;
 289                 ec->ec_members = NIL;
 290                 ec->ec_sources = list_make1(restrictinfo);
 291                 ec->ec_derives = NIL;
 292                 ec->ec_relids = NULL;
 293                 ec->ec_has_const = false;
 294                 ec->ec_has_volatile = false;
 295                 ec->ec_below_outer_join = below_outer_join;
 296                 ec->ec_broken = false;
 297                 ec->ec_sortref = 0;
 298                 ec->ec_merged = NULL;
 299                 em1 = add_eq_member(ec, item1, item1_relids, false, item1_type);
 300                 em2 = add_eq_member(ec, item2, item2_relids, false, item2_type);
 301
 302                 root->eq_classes = lappend(root->eq_classes, ec);
 303
 304                 /* mark the RI as usable with this pair of EMs */
 305                 restrictinfo->left_em = em1;
 306                 restrictinfo->right_em = em2;
 307         }
 308
 309         return true;
 310 }
 311
 312 /*
 313  * add_eq_member - build a new EquivalenceMember and add it to an EC
 314  */
 315 static EquivalenceMember *
 316 add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
 317                           bool is_child, Oid datatype)
 318 {
 319         EquivalenceMember *em = makeNode(EquivalenceMember);
 320
 321         em->em_expr = expr;
 322         em->em_relids = relids;
 323         em->em_is_const = false;
 324         em->em_is_child = is_child;
 325         em->em_datatype = datatype;
 326
 327         if (bms_is_empty(relids))
 328         {
 329                 /*
 330                  * No Vars, assume it's a pseudoconstant.  This is correct for entries
 331                  * generated from process_equivalence(), because a WHERE clause can't
 332                  * contain aggregates or SRFs, and non-volatility was checked before
 333                  * process_equivalence() ever got called.  But
 334                  * get_eclass_for_sort_expr() has to work harder.  We put the tests
 335                  * there not here to save cycles in the equivalence case.
 336                  */
 337                 Assert(!is_child);
 338                 em->em_is_const = true;
 339                 ec->ec_has_const = true;
 340                 /* it can't affect ec_relids */
 341         }
 342         else if (!is_child)                     /* child members don't add to ec_relids */
 343         {
 344                 ec->ec_relids = bms_add_members(ec->ec_relids, relids);
 345         }
 346         ec->ec_members = lappend(ec->ec_members, em);
 347
 348         return em;
 349 }
 350
 351
 352 /*
 353  * get_eclass_for_sort_expr
 354  *        Given an expression and opfamily info, find an existing equivalence
 355  *        class it is a member of; if none, build a new single-member
 356  *        EquivalenceClass for it.
 357  *
 358  * sortref is the SortGroupRef of the originating SortGroupClause, if any,
 359  * or zero if not.
 360  *
 361  * This can be used safely both before and after EquivalenceClass merging;
 362  * since it never causes merging it does not invalidate any existing ECs
 363  * or PathKeys.
 364  *
 365  * Note: opfamilies must be chosen consistently with the way
 366  * process_equivalence() would do; that is, generated from a mergejoinable
 367  * equality operator.  Else we might fail to detect valid equivalences,
 368  * generating poor (but not incorrect) plans.
 369  */
 370 EquivalenceClass *
 371 get_eclass_for_sort_expr(PlannerInfo *root,
 372                                                  Expr *expr,
 373                                                  Oid expr_datatype,
 374                                                  List *opfamilies,
 375                                                  Index sortref)
 376 {
 377         EquivalenceClass *newec;
 378         EquivalenceMember *newem;
 379         ListCell   *lc1;
 380         MemoryContext oldcontext;
 381
 382         /*
 383          * Scan through the existing EquivalenceClasses for a match
 384          */
 385         foreach(lc1, root->eq_classes)
 386         {
 387                 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 388                 ListCell   *lc2;
 389
 390                 /* Never match to a volatile EC */
 391                 if (cur_ec->ec_has_volatile)
 392                         continue;
 393
 394                 if (!equal(opfamilies, cur_ec->ec_opfamilies))
 395                         continue;
 396
 397                 foreach(lc2, cur_ec->ec_members)
 398                 {
 399                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 400
 401                         /*
 402                          * If below an outer join, don't match constants: they're not as
 403                          * constant as they look.
 404                          */
 405                         if (cur_ec->ec_below_outer_join &&
 406                                 cur_em->em_is_const)
 407                                 continue;
 408
 409                         if (expr_datatype == cur_em->em_datatype &&
 410                                 equal(expr, cur_em->em_expr))
 411                                 return cur_ec;  /* Match! */
 412                 }
 413         }
 414
 415         /*
 416          * No match, so build a new single-member EC
 417          *
 418          * Here, we must be sure that we construct the EC in the right context. We
 419          * can assume, however, that the passed expr is long-lived.
 420          */
 421         oldcontext = MemoryContextSwitchTo(root->planner_cxt);
 422
 423         newec = makeNode(EquivalenceClass);
 424         newec->ec_opfamilies = list_copy(opfamilies);
 425         newec->ec_members = NIL;
 426         newec->ec_sources = NIL;
 427         newec->ec_derives = NIL;
 428         newec->ec_relids = NULL;
 429         newec->ec_has_const = false;
 430         newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
 431         newec->ec_below_outer_join = false;
 432         newec->ec_broken = false;
 433         newec->ec_sortref = sortref;
 434         newec->ec_merged = NULL;
 435         newem = add_eq_member(newec, expr, pull_varnos((Node *) expr),
 436                                                   false, expr_datatype);
 437
 438         /*
 439          * add_eq_member doesn't check for volatile functions, set-returning
 440          * functions, or aggregates, but such could appear in sort expressions; so
 441          * we have to check whether its const-marking was correct.
 442          */
 443         if (newec->ec_has_const)
 444         {
 445                 if (newec->ec_has_volatile ||
 446                         expression_returns_set((Node *) expr) ||
 447                         contain_agg_clause((Node *) expr))
 448                 {
 449                         newec->ec_has_const = false;
 450                         newem->em_is_const = false;
 451                 }
 452         }
 453
 454         root->eq_classes = lappend(root->eq_classes, newec);
 455
 456         MemoryContextSwitchTo(oldcontext);
 457
 458         return newec;
 459 }
 460
 461
 462 /*
 463  * generate_base_implied_equalities
 464  *        Generate any restriction clauses that we can deduce from equivalence
 465  *        classes.
 466  *
 467  * When an EC contains pseudoconstants, our strategy is to generate
 468  * "member = const1" clauses where const1 is the first constant member, for
 469  * every other member (including other constants).      If we are able to do this
 470  * then we don't need any "var = var" comparisons because we've successfully
 471  * constrained all the vars at their points of creation.  If we fail to
 472  * generate any of these clauses due to lack of cross-type operators, we fall
 473  * back to the "ec_broken" strategy described below.  (XXX if there are
 474  * multiple constants of different types, it's possible that we might succeed
 475  * in forming all the required clauses if we started from a different const
 476  * member; but this seems a sufficiently hokey corner case to not be worth
 477  * spending lots of cycles on.)
 478  *
 479  * For ECs that contain no pseudoconstants, we generate derived clauses
 480  * "member1 = member2" for each pair of members belonging to the same base
 481  * relation (actually, if there are more than two for the same base relation,
 482  * we only need enough clauses to link each to each other).  This provides
 483  * the base case for the recursion: each row emitted by a base relation scan
 484  * will constrain all computable members of the EC to be equal.  As each
 485  * join path is formed, we'll add additional derived clauses on-the-fly
 486  * to maintain this invariant (see generate_join_implied_equalities).
 487  *
 488  * If the opfamilies used by the EC do not provide complete sets of cross-type
 489  * equality operators, it is possible that we will fail to generate a clause
 490  * that must be generated to maintain the invariant.  (An example: given
 491  * "WHERE a.x = b.y AND b.y = a.z", the scheme breaks down if we cannot
 492  * generate "a.x = a.z" as a restriction clause for A.)  In this case we mark
 493  * the EC "ec_broken" and fall back to regurgitating its original source
 494  * RestrictInfos at appropriate times.  We do not try to retract any derived
 495  * clauses already generated from the broken EC, so the resulting plan could
 496  * be poor due to bad selectivity estimates caused by redundant clauses.  But
 497  * the correct solution to that is to fix the opfamilies ...
 498  *
 499  * Equality clauses derived by this function are passed off to
 500  * process_implied_equality (in plan/initsplan.c) to be inserted into the
 501  * restrictinfo datastructures.  Note that this must be called after initial
 502  * scanning of the quals and before Path construction begins.
 503  *
 504  * We make no attempt to avoid generating duplicate RestrictInfos here: we
 505  * don't search ec_sources for matches, nor put the created RestrictInfos
 506  * into ec_derives.  Doing so would require some slightly ugly changes in
 507  * initsplan.c's API, and there's no real advantage, because the clauses
 508  * generated here can't duplicate anything we will generate for joins anyway.
 509  */
 510 void
 511 generate_base_implied_equalities(PlannerInfo *root)
 512 {
 513         ListCell   *lc;
 514         Index           rti;
 515
 516         foreach(lc, root->eq_classes)
 517         {
 518                 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
 519
 520                 Assert(ec->ec_merged == NULL);  /* else shouldn't be in list */
 521                 Assert(!ec->ec_broken); /* not yet anyway... */
 522
 523                 /* Single-member ECs won't generate any deductions */
 524                 if (list_length(ec->ec_members) <= 1)
 525                         continue;
 526
 527                 if (ec->ec_has_const)
 528                         generate_base_implied_equalities_const(root, ec);
 529                 else
 530                         generate_base_implied_equalities_no_const(root, ec);
 531
 532                 /* Recover if we failed to generate required derived clauses */
 533                 if (ec->ec_broken)
 534                         generate_base_implied_equalities_broken(root, ec);
 535         }
 536
 537         /*
 538          * This is also a handy place to mark base rels (which should all exist by
 539          * now) with flags showing whether they have pending eclass joins.
 540          */
 541         for (rti = 1; rti < root->simple_rel_array_size; rti++)
 542         {
 543                 RelOptInfo *brel = root->simple_rel_array[rti];
 544
 545                 if (brel == NULL)
 546                         continue;
 547
 548                 brel->has_eclass_joins = has_relevant_eclass_joinclause(root, brel);
 549         }
 550 }
 551
 552 /*
 553  * generate_base_implied_equalities when EC contains pseudoconstant(s)
 554  */
 555 static void
 556 generate_base_implied_equalities_const(PlannerInfo *root,
 557                                                                            EquivalenceClass *ec)
 558 {
 559         EquivalenceMember *const_em = NULL;
 560         ListCell   *lc;
 561
 562         /*
 563          * In the trivial case where we just had one "var = const" clause,
 564          * push the original clause back into the main planner machinery.  There
 565          * is nothing to be gained by doing it differently, and we save the
 566          * effort to re-build and re-analyze an equality clause that will be
 567          * exactly equivalent to the old one.
 568          */
 569         if (list_length(ec->ec_members) == 2 &&
 570                 list_length(ec->ec_sources) == 1)
 571         {
 572                 RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
 573
 574                 if (bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
 575                 {
 576                         distribute_restrictinfo_to_rels(root, restrictinfo);
 577                         return;
 578                 }
 579         }
 580
 581         /* Find the constant member to use */
 582         foreach(lc, ec->ec_members)
 583         {
 584                 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 585
 586                 if (cur_em->em_is_const)
 587                 {
 588                         const_em = cur_em;
 589                         break;
 590                 }
 591         }
 592         Assert(const_em != NULL);
 593
 594         /* Generate a derived equality against each other member */
 595         foreach(lc, ec->ec_members)
 596         {
 597                 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 598                 Oid                     eq_op;
 599
 600                 Assert(!cur_em->em_is_child);   /* no children yet */
 601                 if (cur_em == const_em)
 602                         continue;
 603                 eq_op = select_equality_operator(ec,
 604                                                                                  cur_em->em_datatype,
 605                                                                                  const_em->em_datatype);
 606                 if (!OidIsValid(eq_op))
 607                 {
 608                         /* failed... */
 609                         ec->ec_broken = true;
 610                         break;
 611                 }
 612                 process_implied_equality(root, eq_op,
 613                                                                  cur_em->em_expr, const_em->em_expr,
 614                                                                  ec->ec_relids,
 615                                                                  ec->ec_below_outer_join,
 616                                                                  cur_em->em_is_const);
 617         }
 618 }
 619
 620 /*
 621  * generate_base_implied_equalities when EC contains no pseudoconstants
 622  */
 623 static void
 624 generate_base_implied_equalities_no_const(PlannerInfo *root,
 625                                                                                   EquivalenceClass *ec)
 626 {
 627         EquivalenceMember **prev_ems;
 628         ListCell   *lc;
 629
 630         /*
 631          * We scan the EC members once and track the last-seen member for each
 632          * base relation.  When we see another member of the same base relation,
 633          * we generate "prev_mem = cur_mem".  This results in the minimum number
 634          * of derived clauses, but it's possible that it will fail when a
 635          * different ordering would succeed.  XXX FIXME: use a UNION-FIND
 636          * algorithm similar to the way we build merged ECs.  (Use a list-of-lists
 637          * for each rel.)
 638          */
 639         prev_ems = (EquivalenceMember **)
 640                 palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
 641
 642         foreach(lc, ec->ec_members)
 643         {
 644                 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 645                 int                     relid;
 646
 647                 Assert(!cur_em->em_is_child);   /* no children yet */
 648                 if (bms_membership(cur_em->em_relids) != BMS_SINGLETON)
 649                         continue;
 650                 relid = bms_singleton_member(cur_em->em_relids);
 651                 Assert(relid < root->simple_rel_array_size);
 652
 653                 if (prev_ems[relid] != NULL)
 654                 {
 655                         EquivalenceMember *prev_em = prev_ems[relid];
 656                         Oid                     eq_op;
 657
 658                         eq_op = select_equality_operator(ec,
 659                                                                                          prev_em->em_datatype,
 660                                                                                          cur_em->em_datatype);
 661                         if (!OidIsValid(eq_op))
 662                         {
 663                                 /* failed... */
 664                                 ec->ec_broken = true;
 665                                 break;
 666                         }
 667                         process_implied_equality(root, eq_op,
 668                                                                          prev_em->em_expr, cur_em->em_expr,
 669                                                                          ec->ec_relids,
 670                                                                          ec->ec_below_outer_join,
 671                                                                          false);
 672                 }
 673                 prev_ems[relid] = cur_em;
 674         }
 675
 676         pfree(prev_ems);
 677
 678         /*
 679          * We also have to make sure that all the Vars used in the member clauses
 680          * will be available at any join node we might try to reference them at.
 681          * For the moment we force all the Vars to be available at all join nodes
 682          * for this eclass.  Perhaps this could be improved by doing some
 683          * pre-analysis of which members we prefer to join, but it's no worse than
 684          * what happened in the pre-8.3 code.
 685          */
 686         foreach(lc, ec->ec_members)
 687         {
 688                 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 689                 List       *vars = pull_var_clause((Node *) cur_em->em_expr, false);
 690
 691                 add_vars_to_targetlist(root, vars, ec->ec_relids);
 692                 list_free(vars);
 693         }
 694 }
 695
 696 /*
 697  * generate_base_implied_equalities cleanup after failure
 698  *
 699  * What we must do here is push any zero- or one-relation source RestrictInfos
 700  * of the EC back into the main restrictinfo datastructures.  Multi-relation
 701  * clauses will be regurgitated later by generate_join_implied_equalities().
 702  * (We do it this way to maintain continuity with the case that ec_broken
 703  * becomes set only after we've gone up a join level or two.)
 704  */
 705 static void
 706 generate_base_implied_equalities_broken(PlannerInfo *root,
 707                                                                                 EquivalenceClass *ec)
 708 {
 709         ListCell   *lc;
 710
 711         foreach(lc, ec->ec_sources)
 712         {
 713                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
 714
 715                 if (bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
 716                         distribute_restrictinfo_to_rels(root, restrictinfo);
 717         }
 718 }
 719
 720
 721 /*
 722  * generate_join_implied_equalities
 723  *        Generate any join clauses that we can deduce from equivalence classes.
 724  *
 725  * At a join node, we must enforce restriction clauses sufficient to ensure
 726  * that all equivalence-class members computable at that node are equal.
 727  * Since the set of clauses to enforce can vary depending on which subset
 728  * relations are the inputs, we have to compute this afresh for each join
 729  * path pair.  Hence a fresh List of RestrictInfo nodes is built and passed
 730  * back on each call.
 731  *
 732  * The results are sufficient for use in merge, hash, and plain nestloop join
 733  * methods.  We do not worry here about selecting clauses that are optimal
 734  * for use in a nestloop-with-inner-indexscan join, however.  indxpath.c makes
 735  * its own selections of clauses to use, and if the ones we pick here are
 736  * redundant with those, the extras will be eliminated in createplan.c.
 737  *
 738  * Because the same join clauses are likely to be needed multiple times as
 739  * we consider different join paths, we avoid generating multiple copies:
 740  * whenever we select a particular pair of EquivalenceMembers to join,
 741  * we check to see if the pair matches any original clause (in ec_sources)
 742  * or previously-built clause (in ec_derives).  This saves memory and allows
 743  * re-use of information cached in RestrictInfos.
 744  */
 745 List *
 746 generate_join_implied_equalities(PlannerInfo *root,
 747                                                                  RelOptInfo *joinrel,
 748                                                                  RelOptInfo *outer_rel,
 749                                                                  RelOptInfo *inner_rel)
 750 {
 751         List       *result = NIL;
 752         ListCell   *lc;
 753
 754         foreach(lc, root->eq_classes)
 755         {
 756                 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
 757                 List       *sublist = NIL;
 758
 759                 /* ECs containing consts do not need any further enforcement */
 760                 if (ec->ec_has_const)
 761                         continue;
 762
 763                 /* Single-member ECs won't generate any deductions */
 764                 if (list_length(ec->ec_members) <= 1)
 765                         continue;
 766
 767                 /* We can quickly ignore any that don't overlap the join, too */
 768                 if (!bms_overlap(ec->ec_relids, joinrel->relids))
 769                         continue;
 770
 771                 if (!ec->ec_broken)
 772                         sublist = generate_join_implied_equalities_normal(root,
 773                                                                                                                           ec,
 774                                                                                                                           joinrel,
 775                                                                                                                           outer_rel,
 776                                                                                                                           inner_rel);
 777
 778                 /* Recover if we failed to generate required derived clauses */
 779                 if (ec->ec_broken)
 780                         sublist = generate_join_implied_equalities_broken(root,
 781                                                                                                                           ec,
 782                                                                                                                           joinrel,
 783                                                                                                                           outer_rel,
 784                                                                                                                           inner_rel);
 785
 786                 result = list_concat(result, sublist);
 787         }
 788
 789         return result;
 790 }
 791
 792 /*
 793  * generate_join_implied_equalities for a still-valid EC
 794  */
 795 static List *
 796 generate_join_implied_equalities_normal(PlannerInfo *root,
 797                                                                                 EquivalenceClass *ec,
 798                                                                                 RelOptInfo *joinrel,
 799                                                                                 RelOptInfo *outer_rel,
 800                                                                                 RelOptInfo *inner_rel)
 801 {
 802         List       *result = NIL;
 803         List       *new_members = NIL;
 804         List       *outer_members = NIL;
 805         List       *inner_members = NIL;
 806         ListCell   *lc1;
 807
 808         /*
 809          * First, scan the EC to identify member values that are computable at the
 810          * outer rel, at the inner rel, or at this relation but not in either
 811          * input rel.  The outer-rel members should already be enforced equal,
 812          * likewise for the inner-rel members.  We'll need to create clauses to
 813          * enforce that any newly computable members are all equal to each other
 814          * as well as to at least one input member, plus enforce at least one
 815          * outer-rel member equal to at least one inner-rel member.
 816          */
 817         foreach(lc1, ec->ec_members)
 818         {
 819                 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
 820
 821                 if (cur_em->em_is_child)
 822                         continue;                       /* ignore children here */
 823                 if (!bms_is_subset(cur_em->em_relids, joinrel->relids))
 824                         continue;                       /* ignore --- not computable yet */
 825
 826                 if (bms_is_subset(cur_em->em_relids, outer_rel->relids))
 827                         outer_members = lappend(outer_members, cur_em);
 828                 else if (bms_is_subset(cur_em->em_relids, inner_rel->relids))
 829                         inner_members = lappend(inner_members, cur_em);
 830                 else
 831                         new_members = lappend(new_members, cur_em);
 832         }
 833
 834         /*
 835          * First, select the joinclause if needed.      We can equate any one outer
 836          * member to any one inner member, but we have to find a datatype
 837          * combination for which an opfamily member operator exists.  If we have
 838          * choices, we prefer simple Var members (possibly with RelabelType) since
 839          * these are (a) cheapest to compute at runtime and (b) most likely to
 840          * have useful statistics.      Also, if enable_hashjoin is on, we prefer
 841          * operators that are also hashjoinable.
 842          */
 843         if (outer_members && inner_members)
 844         {
 845                 EquivalenceMember *best_outer_em = NULL;
 846                 EquivalenceMember *best_inner_em = NULL;
 847                 Oid                     best_eq_op = InvalidOid;
 848                 int                     best_score = -1;
 849                 RestrictInfo *rinfo;
 850
 851                 foreach(lc1, outer_members)
 852                 {
 853                         EquivalenceMember *outer_em = (EquivalenceMember *) lfirst(lc1);
 854                         ListCell   *lc2;
 855
 856                         foreach(lc2, inner_members)
 857                         {
 858                                 EquivalenceMember *inner_em = (EquivalenceMember *) lfirst(lc2);
 859                                 Oid                     eq_op;
 860                                 int                     score;
 861
 862                                 eq_op = select_equality_operator(ec,
 863                                                                                                  outer_em->em_datatype,
 864                                                                                                  inner_em->em_datatype);
 865                                 if (!OidIsValid(eq_op))
 866                                         continue;
 867                                 score = 0;
 868                                 if (IsA(outer_em->em_expr, Var) ||
 869                                         (IsA(outer_em->em_expr, RelabelType) &&
 870                                          IsA(((RelabelType *) outer_em->em_expr)->arg, Var)))
 871                                         score++;
 872                                 if (IsA(inner_em->em_expr, Var) ||
 873                                         (IsA(inner_em->em_expr, RelabelType) &&
 874                                          IsA(((RelabelType *) inner_em->em_expr)->arg, Var)))
 875                                         score++;
 876                                 if (!enable_hashjoin || op_hashjoinable(eq_op))
 877                                         score++;
 878                                 if (score > best_score)
 879                                 {
 880                                         best_outer_em = outer_em;
 881                                         best_inner_em = inner_em;
 882                                         best_eq_op = eq_op;
 883                                         best_score = score;
 884                                         if (best_score == 3)
 885                                                 break;  /* no need to look further */
 886                                 }
 887                         }
 888                         if (best_score == 3)
 889                                 break;                  /* no need to look further */
 890                 }
 891                 if (best_score < 0)
 892                 {
 893                         /* failed... */
 894                         ec->ec_broken = true;
 895                         return NIL;
 896                 }
 897
 898                 /*
 899                  * Create clause, setting parent_ec to mark it as redundant with other
 900                  * joinclauses
 901                  */
 902                 rinfo = create_join_clause(root, ec, best_eq_op,
 903                                                                    best_outer_em, best_inner_em,
 904                                                                    ec);
 905
 906                 result = lappend(result, rinfo);
 907         }
 908
 909         /*
 910          * Now deal with building restrictions for any expressions that involve
 911          * Vars from both sides of the join.  We have to equate all of these to
 912          * each other as well as to at least one old member (if any).
 913          *
 914          * XXX as in generate_base_implied_equalities_no_const, we could be a lot
 915          * smarter here to avoid unnecessary failures in cross-type situations.
 916          * For now, use the same left-to-right method used there.
 917          */
 918         if (new_members)
 919         {
 920                 List       *old_members = list_concat(outer_members, inner_members);
 921                 EquivalenceMember *prev_em = NULL;
 922                 RestrictInfo *rinfo;
 923
 924                 /* For now, arbitrarily take the first old_member as the one to use */
 925                 if (old_members)
 926                         new_members = lappend(new_members, linitial(old_members));
 927
 928                 foreach(lc1, new_members)
 929                 {
 930                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
 931
 932                         if (prev_em != NULL)
 933                         {
 934                                 Oid                     eq_op;
 935
 936                                 eq_op = select_equality_operator(ec,
 937                                                                                                  prev_em->em_datatype,
 938                                                                                                  cur_em->em_datatype);
 939                                 if (!OidIsValid(eq_op))
 940                                 {
 941                                         /* failed... */
 942                                         ec->ec_broken = true;
 943                                         return NIL;
 944                                 }
 945                                 /* do NOT set parent_ec, this qual is not redundant! */
 946                                 rinfo = create_join_clause(root, ec, eq_op,
 947                                                                                    prev_em, cur_em,
 948                                                                                    NULL);
 949
 950                                 result = lappend(result, rinfo);
 951                         }
 952                         prev_em = cur_em;
 953                 }
 954         }
 955
 956         return result;
 957 }
 958
 959 /*
 960  * generate_join_implied_equalities cleanup after failure
 961  *
 962  * Return any original RestrictInfos that are enforceable at this join.
 963  */
 964 static List *
 965 generate_join_implied_equalities_broken(PlannerInfo *root,
 966                                                                                 EquivalenceClass *ec,
 967                                                                                 RelOptInfo *joinrel,
 968                                                                                 RelOptInfo *outer_rel,
 969                                                                                 RelOptInfo *inner_rel)
 970 {
 971         List       *result = NIL;
 972         ListCell   *lc;
 973
 974         foreach(lc, ec->ec_sources)
 975         {
 976                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
 977
 978                 if (bms_is_subset(restrictinfo->required_relids, joinrel->relids) &&
 979                   !bms_is_subset(restrictinfo->required_relids, outer_rel->relids) &&
 980                         !bms_is_subset(restrictinfo->required_relids, inner_rel->relids))
 981                         result = lappend(result, restrictinfo);
 982         }
 983
 984         return result;
 985 }
 986
 987
 988 /*
 989  * select_equality_operator
 990  *        Select a suitable equality operator for comparing two EC members
 991  *
 992  * Returns InvalidOid if no operator can be found for this datatype combination
 993  */
 994 static Oid
 995 select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
 996 {
 997         ListCell   *lc;
 998
 999         foreach(lc, ec->ec_opfamilies)
1000         {
1001                 Oid                     opfamily = lfirst_oid(lc);
1002                 Oid                     opno;
1003
1004                 opno = get_opfamily_member(opfamily, lefttype, righttype,
1005                                                                    BTEqualStrategyNumber);
1006                 if (OidIsValid(opno))
1007                         return opno;
1008         }
1009         return InvalidOid;
1010 }
1011
1012
1013 /*
1014  * create_join_clause
1015  *        Find or make a RestrictInfo comparing the two given EC members
1016  *        with the given operator.
1017  *
1018  * parent_ec is either equal to ec (if the clause is a potentially-redundant
1019  * join clause) or NULL (if not).  We have to treat this as part of the
1020  * match requirements --- it's possible that a clause comparing the same two
1021  * EMs is a join clause in one join path and a restriction clause in another.
1022  */
1023 static RestrictInfo *
1024 create_join_clause(PlannerInfo *root,
1025                                    EquivalenceClass *ec, Oid opno,
1026                                    EquivalenceMember *leftem,
1027                                    EquivalenceMember *rightem,
1028                                    EquivalenceClass *parent_ec)
1029 {
1030         RestrictInfo *rinfo;
1031         ListCell   *lc;
1032         MemoryContext oldcontext;
1033
1034         /*
1035          * Search to see if we already built a RestrictInfo for this pair of
1036          * EquivalenceMembers.  We can use either original source clauses or
1037          * previously-derived clauses.  The check on opno is probably redundant,
1038          * but be safe ...
1039          */
1040         foreach(lc, ec->ec_sources)
1041         {
1042                 rinfo = (RestrictInfo *) lfirst(lc);
1043                 if (rinfo->left_em == leftem &&
1044                         rinfo->right_em == rightem &&
1045                         rinfo->parent_ec == parent_ec &&
1046                         opno == ((OpExpr *) rinfo->clause)->opno)
1047                         return rinfo;
1048         }
1049
1050         foreach(lc, ec->ec_derives)
1051         {
1052                 rinfo = (RestrictInfo *) lfirst(lc);
1053                 if (rinfo->left_em == leftem &&
1054                         rinfo->right_em == rightem &&
1055                         rinfo->parent_ec == parent_ec &&
1056                         opno == ((OpExpr *) rinfo->clause)->opno)
1057                         return rinfo;
1058         }
1059
1060         /*
1061          * Not there, so build it, in planner context so we can re-use it. (Not
1062          * important in normal planning, but definitely so in GEQO.)
1063          */
1064         oldcontext = MemoryContextSwitchTo(root->planner_cxt);
1065
1066         rinfo = build_implied_join_equality(opno,
1067                                                                                 leftem->em_expr,
1068                                                                                 rightem->em_expr,
1069                                                                                 bms_union(leftem->em_relids,
1070                                                                                                   rightem->em_relids));
1071
1072         /* Mark the clause as redundant, or not */
1073         rinfo->parent_ec = parent_ec;
1074
1075         /*
1076          * We can set these now, rather than letting them be looked up later,
1077          * since this is only used after EC merging is complete.
1078          */
1079         rinfo->left_ec = ec;
1080         rinfo->right_ec = ec;
1081
1082         /* Mark it as usable with these EMs */
1083         rinfo->left_em = leftem;
1084         rinfo->right_em = rightem;
1085         /* and save it for possible re-use */
1086         ec->ec_derives = lappend(ec->ec_derives, rinfo);
1087
1088         MemoryContextSwitchTo(oldcontext);
1089
1090         return rinfo;
1091 }
1092
1093
1094 /*
1095  * reconsider_outer_join_clauses
1096  *        Re-examine any outer-join clauses that were set aside by
1097  *        distribute_qual_to_rels(), and see if we can derive any
1098  *        EquivalenceClasses from them.  Then, if they were not made
1099  *        redundant, push them out into the regular join-clause lists.
1100  *
1101  * When we have mergejoinable clauses A = B that are outer-join clauses,
1102  * we can't blindly combine them with other clauses A = C to deduce B = C,
1103  * since in fact the "equality" A = B won't necessarily hold above the
1104  * outer join (one of the variables might be NULL instead).  Nonetheless
1105  * there are cases where we can add qual clauses using transitivity.
1106  *
1107  * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
1108  * for which there is also an equivalence clause OUTERVAR = CONSTANT.
1109  * It is safe and useful to push a clause INNERVAR = CONSTANT into the
1110  * evaluation of the inner (nullable) relation, because any inner rows not
1111  * meeting this condition will not contribute to the outer-join result anyway.
1112  * (Any outer rows they could join to will be eliminated by the pushed-down
1113  * equivalence clause.)
1114  *
1115  * Note that the above rule does not work for full outer joins; nor is it
1116  * very interesting to consider cases where the generated equivalence clause
1117  * would involve relations outside the outer join, since such clauses couldn't
1118  * be pushed into the inner side's scan anyway.  So the restriction to
1119  * outervar = pseudoconstant is not really giving up anything.
1120  *
1121  * For full-join cases, we can only do something useful if it's a FULL JOIN
1122  * USING and a merged column has an equivalence MERGEDVAR = CONSTANT.
1123  * By the time it gets here, the merged column will look like
1124  *              COALESCE(LEFTVAR, RIGHTVAR)
1125  * and we will have a full-join clause LEFTVAR = RIGHTVAR that we can match
1126  * the COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
1127  * and RIGHTVAR = CONSTANT into the input relations, since any rows not
1128  * meeting these conditions cannot contribute to the join result.
1129  *
1130  * Again, there isn't any traction to be gained by trying to deal with
1131  * clauses comparing a mergedvar to a non-pseudoconstant.  So we can make
1132  * use of the EquivalenceClasses to search for matching variables that were
1133  * equivalenced to constants.  The interesting outer-join clauses were
1134  * accumulated for us by distribute_qual_to_rels.
1135  *
1136  * When we find one of these cases, we implement the changes we want by
1137  * generating a new equivalence clause INNERVAR = CONSTANT (or LEFTVAR, etc)
1138  * and pushing it into the EquivalenceClass structures.  This is because we
1139  * may already know that INNERVAR is equivalenced to some other var(s), and
1140  * we'd like the constant to propagate to them too.  Note that it would be
1141  * unsafe to merge any existing EC for INNERVAR with the OUTERVAR's EC ---
1142  * that could result in propagating constant restrictions from
1143  * INNERVAR to OUTERVAR, which would be very wrong.
1144  *
1145  * It's possible that the INNERVAR is also an OUTERVAR for some other
1146  * outer-join clause, in which case the process can be repeated.  So we repeat
1147  * looping over the lists of clauses until no further deductions can be made.
1148  * Whenever we do make a deduction, we remove the generating clause from the
1149  * lists, since we don't want to make the same deduction twice.
1150  *
1151  * If we don't find any match for a set-aside outer join clause, we must
1152  * throw it back into the regular joinclause processing by passing it to
1153  * distribute_restrictinfo_to_rels().  If we do generate a derived clause,
1154  * however, the outer-join clause is redundant.  We still throw it back,
1155  * because otherwise the join will be seen as a clauseless join and avoided
1156  * during join order searching; but we mark it as redundant to keep from
1157  * messing up the joinrel's size estimate.  (This behavior means that the
1158  * API for this routine is uselessly complex: we could have just put all
1159  * the clauses into the regular processing initially.  We keep it because
1160  * someday we might want to do something else, such as inserting "dummy"
1161  * joinclauses instead of real ones.)
1162  *
1163  * Outer join clauses that are marked outerjoin_delayed are special: this
1164  * condition means that one or both VARs might go to null due to a lower
1165  * outer join.  We can still push a constant through the clause, but only
1166  * if its operator is strict; and we *have to* throw the clause back into
1167  * regular joinclause processing.  By keeping the strict join clause,
1168  * we ensure that any null-extended rows that are mistakenly generated due
1169  * to suppressing rows not matching the constant will be rejected at the
1170  * upper outer join.  (This doesn't work for full-join clauses.)
1171  */
1172 void
1173 reconsider_outer_join_clauses(PlannerInfo *root)
1174 {
1175         bool            found;
1176         ListCell   *cell;
1177         ListCell   *prev;
1178         ListCell   *next;
1179
1180         /* Outer loop repeats until we find no more deductions */
1181         do
1182         {
1183                 found = false;
1184
1185                 /* Process the LEFT JOIN clauses */
1186                 prev = NULL;
1187                 for (cell = list_head(root->left_join_clauses); cell; cell = next)
1188                 {
1189                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1190
1191                         next = lnext(cell);
1192                         if (reconsider_outer_join_clause(root, rinfo, true))
1193                         {
1194                                 found = true;
1195                                 /* remove it from the list */
1196                                 root->left_join_clauses =
1197                                         list_delete_cell(root->left_join_clauses, cell, prev);
1198                                 /* we throw it back anyway (see notes above) */
1199                                 /* but the thrown-back clause has no extra selectivity */
1200                                 rinfo->this_selec = 1.0;
1201                                 distribute_restrictinfo_to_rels(root, rinfo);
1202                         }
1203                         else
1204                                 prev = cell;
1205                 }
1206
1207                 /* Process the RIGHT JOIN clauses */
1208                 prev = NULL;
1209                 for (cell = list_head(root->right_join_clauses); cell; cell = next)
1210                 {
1211                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1212
1213                         next = lnext(cell);
1214                         if (reconsider_outer_join_clause(root, rinfo, false))
1215                         {
1216                                 found = true;
1217                                 /* remove it from the list */
1218                                 root->right_join_clauses =
1219                                         list_delete_cell(root->right_join_clauses, cell, prev);
1220                                 /* we throw it back anyway (see notes above) */
1221                                 /* but the thrown-back clause has no extra selectivity */
1222                                 rinfo->this_selec = 1.0;
1223                                 distribute_restrictinfo_to_rels(root, rinfo);
1224                         }
1225                         else
1226                                 prev = cell;
1227                 }
1228
1229                 /* Process the FULL JOIN clauses */
1230                 prev = NULL;
1231                 for (cell = list_head(root->full_join_clauses); cell; cell = next)
1232                 {
1233                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1234
1235                         next = lnext(cell);
1236                         if (reconsider_full_join_clause(root, rinfo))
1237                         {
1238                                 found = true;
1239                                 /* remove it from the list */
1240                                 root->full_join_clauses =
1241                                         list_delete_cell(root->full_join_clauses, cell, prev);
1242                                 /* we throw it back anyway (see notes above) */
1243                                 /* but the thrown-back clause has no extra selectivity */
1244                                 rinfo->this_selec = 1.0;
1245                                 distribute_restrictinfo_to_rels(root, rinfo);
1246                         }
1247                         else
1248                                 prev = cell;
1249                 }
1250         } while (found);
1251
1252         /* Now, any remaining clauses have to be thrown back */
1253         foreach(cell, root->left_join_clauses)
1254         {
1255                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1256
1257                 distribute_restrictinfo_to_rels(root, rinfo);
1258         }
1259         foreach(cell, root->right_join_clauses)
1260         {
1261                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1262
1263                 distribute_restrictinfo_to_rels(root, rinfo);
1264         }
1265         foreach(cell, root->full_join_clauses)
1266         {
1267                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1268
1269                 distribute_restrictinfo_to_rels(root, rinfo);
1270         }
1271 }
1272
1273 /*
1274  * reconsider_outer_join_clauses for a single LEFT/RIGHT JOIN clause
1275  *
1276  * Returns TRUE if we were able to propagate a constant through the clause.
1277  */
1278 static bool
1279 reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
1280                                                          bool outer_on_left)
1281 {
1282         Expr       *outervar,
1283                            *innervar;
1284         Oid                     opno,
1285                                 left_type,
1286                                 right_type,
1287                                 inner_datatype;
1288         Relids          inner_relids;
1289         ListCell   *lc1;
1290
1291         Assert(is_opclause(rinfo->clause));
1292         opno = ((OpExpr *) rinfo->clause)->opno;
1293
1294         /* If clause is outerjoin_delayed, operator must be strict */
1295         if (rinfo->outerjoin_delayed && !op_strict(opno))
1296                 return false;
1297
1298         /* Extract needed info from the clause */
1299         op_input_types(opno, &left_type, &right_type);
1300         if (outer_on_left)
1301         {
1302                 outervar = (Expr *) get_leftop(rinfo->clause);
1303                 innervar = (Expr *) get_rightop(rinfo->clause);
1304                 inner_datatype = right_type;
1305                 inner_relids = rinfo->right_relids;
1306         }
1307         else
1308         {
1309                 outervar = (Expr *) get_rightop(rinfo->clause);
1310                 innervar = (Expr *) get_leftop(rinfo->clause);
1311                 inner_datatype = left_type;
1312                 inner_relids = rinfo->left_relids;
1313         }
1314
1315         /* Scan EquivalenceClasses for a match to outervar */
1316         foreach(lc1, root->eq_classes)
1317         {
1318                 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1319                 bool            match;
1320                 ListCell   *lc2;
1321
1322                 /* Ignore EC unless it contains pseudoconstants */
1323                 if (!cur_ec->ec_has_const)
1324                         continue;
1325                 /* Never match to a volatile EC */
1326                 if (cur_ec->ec_has_volatile)
1327                         continue;
1328                 /* It has to match the outer-join clause as to opfamilies, too */
1329                 if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
1330                         continue;
1331                 /* Does it contain a match to outervar? */
1332                 match = false;
1333                 foreach(lc2, cur_ec->ec_members)
1334                 {
1335                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1336
1337                         if (equal(outervar, cur_em->em_expr))
1338                         {
1339                                 match = true;
1340                                 break;
1341                         }
1342                 }
1343                 if (!match)
1344                         continue;                       /* no match, so ignore this EC */
1345
1346                 /*
1347                  * Yes it does!  Try to generate a clause INNERVAR = CONSTANT for each
1348                  * CONSTANT in the EC.  Note that we must succeed with at least one
1349                  * constant before we can decide to throw away the outer-join clause.
1350                  */
1351                 match = false;
1352                 foreach(lc2, cur_ec->ec_members)
1353                 {
1354                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1355                         Oid                     eq_op;
1356                         RestrictInfo *newrinfo;
1357
1358                         if (!cur_em->em_is_const)
1359                                 continue;               /* ignore non-const members */
1360                         eq_op = select_equality_operator(cur_ec,
1361                                                                                          inner_datatype,
1362                                                                                          cur_em->em_datatype);
1363                         if (!OidIsValid(eq_op))
1364                                 continue;               /* can't generate equality */
1365                         newrinfo = build_implied_join_equality(eq_op,
1366                                                                                                    innervar,
1367                                                                                                    cur_em->em_expr,
1368                                                                                                    inner_relids);
1369                         if (process_equivalence(root, newrinfo, true))
1370                                 match = true;
1371                 }
1372
1373                 /*
1374                  * If we were able to equate INNERVAR to any constant, report success.
1375                  * Otherwise, fall out of the search loop, since we know the OUTERVAR
1376                  * appears in at most one EC.
1377                  */
1378                 if (match)
1379                         return true;
1380                 else
1381                         break;
1382         }
1383
1384         return false;                           /* failed to make any deduction */
1385 }
1386
1387 /*
1388  * reconsider_outer_join_clauses for a single FULL JOIN clause
1389  *
1390  * Returns TRUE if we were able to propagate a constant through the clause.
1391  */
1392 static bool
1393 reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
1394 {
1395         Expr       *leftvar;
1396         Expr       *rightvar;
1397         Oid                     opno,
1398                                 left_type,
1399                                 right_type;
1400         Relids          left_relids,
1401                                 right_relids;
1402         ListCell   *lc1;
1403
1404         /* Can't use an outerjoin_delayed clause here */
1405         if (rinfo->outerjoin_delayed)
1406                 return false;
1407
1408         /* Extract needed info from the clause */
1409         Assert(is_opclause(rinfo->clause));
1410         opno = ((OpExpr *) rinfo->clause)->opno;
1411         op_input_types(opno, &left_type, &right_type);
1412         leftvar = (Expr *) get_leftop(rinfo->clause);
1413         rightvar = (Expr *) get_rightop(rinfo->clause);
1414         left_relids = rinfo->left_relids;
1415         right_relids = rinfo->right_relids;
1416
1417         foreach(lc1, root->eq_classes)
1418         {
1419                 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1420                 EquivalenceMember *coal_em = NULL;
1421                 bool            match;
1422                 bool            matchleft;
1423                 bool            matchright;
1424                 ListCell   *lc2;
1425
1426                 /* Ignore EC unless it contains pseudoconstants */
1427                 if (!cur_ec->ec_has_const)
1428                         continue;
1429                 /* Never match to a volatile EC */
1430                 if (cur_ec->ec_has_volatile)
1431                         continue;
1432                 /* It has to match the outer-join clause as to opfamilies, too */
1433                 if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
1434                         continue;
1435
1436                 /*
1437                  * Does it contain a COALESCE(leftvar, rightvar) construct?
1438                  *
1439                  * We can assume the COALESCE() inputs are in the same order as the
1440                  * join clause, since both were automatically generated in the cases
1441                  * we care about.
1442                  *
1443                  * XXX currently this may fail to match in cross-type cases because
1444                  * the COALESCE will contain typecast operations while the join clause
1445                  * may not (if there is a cross-type mergejoin operator available for
1446                  * the two column types). Is it OK to strip implicit coercions from
1447                  * the COALESCE arguments?
1448                  */
1449                 match = false;
1450                 foreach(lc2, cur_ec->ec_members)
1451                 {
1452                         coal_em = (EquivalenceMember *) lfirst(lc2);
1453                         if (IsA(coal_em->em_expr, CoalesceExpr))
1454                         {
1455                                 CoalesceExpr *cexpr = (CoalesceExpr *) coal_em->em_expr;
1456                                 Node       *cfirst;
1457                                 Node       *csecond;
1458
1459                                 if (list_length(cexpr->args) != 2)
1460                                         continue;
1461                                 cfirst = (Node *) linitial(cexpr->args);
1462                                 csecond = (Node *) lsecond(cexpr->args);
1463
1464                                 if (equal(leftvar, cfirst) && equal(rightvar, csecond))
1465                                 {
1466                                         match = true;
1467                                         break;
1468                                 }
1469                         }
1470                 }
1471                 if (!match)
1472                         continue;                       /* no match, so ignore this EC */
1473
1474                 /*
1475                  * Yes it does!  Try to generate clauses LEFTVAR = CONSTANT and
1476                  * RIGHTVAR = CONSTANT for each CONSTANT in the EC.  Note that we must
1477                  * succeed with at least one constant for each var before we can
1478                  * decide to throw away the outer-join clause.
1479                  */
1480                 matchleft = matchright = false;
1481                 foreach(lc2, cur_ec->ec_members)
1482                 {
1483                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1484                         Oid                     eq_op;
1485                         RestrictInfo *newrinfo;
1486
1487                         if (!cur_em->em_is_const)
1488                                 continue;               /* ignore non-const members */
1489                         eq_op = select_equality_operator(cur_ec,
1490                                                                                          left_type,
1491                                                                                          cur_em->em_datatype);
1492                         if (OidIsValid(eq_op))
1493                         {
1494                                 newrinfo = build_implied_join_equality(eq_op,
1495                                                                                                            leftvar,
1496                                                                                                            cur_em->em_expr,
1497                                                                                                            left_relids);
1498                                 if (process_equivalence(root, newrinfo, true))
1499                                         matchleft = true;
1500                         }
1501                         eq_op = select_equality_operator(cur_ec,
1502                                                                                          right_type,
1503                                                                                          cur_em->em_datatype);
1504                         if (OidIsValid(eq_op))
1505                         {
1506                                 newrinfo = build_implied_join_equality(eq_op,
1507                                                                                                            rightvar,
1508                                                                                                            cur_em->em_expr,
1509                                                                                                            right_relids);
1510                                 if (process_equivalence(root, newrinfo, true))
1511                                         matchright = true;
1512                         }
1513                 }
1514
1515                 /*
1516                  * If we were able to equate both vars to constants, we're done, and
1517                  * we can throw away the full-join clause as redundant.  Moreover, we
1518                  * can remove the COALESCE entry from the EC, since the added
1519                  * restrictions ensure it will always have the expected value. (We
1520                  * don't bother trying to update ec_relids or ec_sources.)
1521                  */
1522                 if (matchleft && matchright)
1523                 {
1524                         cur_ec->ec_members = list_delete_ptr(cur_ec->ec_members, coal_em);
1525                         return true;
1526                 }
1527
1528                 /*
1529                  * Otherwise, fall out of the search loop, since we know the COALESCE
1530                  * appears in at most one EC (XXX might stop being true if we allow
1531                  * stripping of coercions above?)
1532                  */
1533                 break;
1534         }
1535
1536         return false;                           /* failed to make any deduction */
1537 }
1538
1539
1540 /*
1541  * exprs_known_equal
1542  *        Detect whether two expressions are known equal due to equivalence
1543  *        relationships.
1544  *
1545  * Actually, this only shows that the expressions are equal according
1546  * to some opfamily's notion of equality --- but we only use it for
1547  * selectivity estimation, so a fuzzy idea of equality is OK.
1548  *
1549  * Note: does not bother to check for "equal(item1, item2)"; caller must
1550  * check that case if it's possible to pass identical items.
1551  */
1552 bool
1553 exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
1554 {
1555         ListCell   *lc1;
1556
1557         foreach(lc1, root->eq_classes)
1558         {
1559                 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1560                 bool            item1member = false;
1561                 bool            item2member = false;
1562                 ListCell   *lc2;
1563
1564                 /* Never match to a volatile EC */
1565                 if (ec->ec_has_volatile)
1566                         continue;
1567
1568                 foreach(lc2, ec->ec_members)
1569                 {
1570                         EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
1571
1572                         if (equal(item1, em->em_expr))
1573                                 item1member = true;
1574                         else if (equal(item2, em->em_expr))
1575                                 item2member = true;
1576                         /* Exit as soon as equality is proven */
1577                         if (item1member && item2member)
1578                                 return true;
1579                 }
1580         }
1581         return false;
1582 }
1583
1584
1585 /*
1586  * add_child_rel_equivalences
1587  *        Search for EC members that reference (only) the parent_rel, and
1588  *        add transformed members referencing the child_rel.
1589  *
1590  * We only need to do this for ECs that could generate join conditions,
1591  * since the child members are only used for creating inner-indexscan paths.
1592  *
1593  * parent_rel and child_rel could be derived from appinfo, but since the
1594  * caller has already computed them, we might as well just pass them in.
1595  */
1596 void
1597 add_child_rel_equivalences(PlannerInfo *root,
1598                                                    AppendRelInfo *appinfo,
1599                                                    RelOptInfo *parent_rel,
1600                                                    RelOptInfo *child_rel)
1601 {
1602         ListCell   *lc1;
1603
1604         foreach(lc1, root->eq_classes)
1605         {
1606                 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1607                 ListCell   *lc2;
1608
1609                 /*
1610                  * Won't generate joinclauses if const or single-member (the latter
1611                  * test covers the volatile case too)
1612                  */
1613                 if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
1614                         continue;
1615
1616                 /* No point in searching if parent rel not mentioned in eclass */
1617                 if (!bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
1618                         continue;
1619
1620                 foreach(lc2, cur_ec->ec_members)
1621                 {
1622                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1623
1624                         /* Does it reference (only) parent_rel? */
1625                         if (bms_equal(cur_em->em_relids, parent_rel->relids))
1626                         {
1627                                 /* Yes, generate transformed child version */
1628                                 Expr       *child_expr;
1629
1630                                 child_expr = (Expr *)
1631                                         adjust_appendrel_attrs((Node *) cur_em->em_expr,
1632                                                                                    appinfo);
1633                                 (void) add_eq_member(cur_ec, child_expr, child_rel->relids,
1634                                                                          true, cur_em->em_datatype);
1635                         }
1636                 }
1637         }
1638 }
1639
1640
1641 /*
1642  * mutate_eclass_expressions
1643  *        Apply an expression tree mutator to all expressions stored in
1644  *        equivalence classes.
1645  *
1646  * This is a bit of a hack ... it's currently needed only by planagg.c,
1647  * which needs to do a global search-and-replace of MIN/MAX Aggrefs
1648  * after eclasses are already set up.  Without changing the eclasses too,
1649  * subsequent matching of ORDER BY clauses would fail.
1650  *
1651  * Note that we assume the mutation won't affect relation membership or any
1652  * other properties we keep track of (which is a bit bogus, but by the time
1653  * planagg.c runs, it no longer matters).  Also we must be called in the
1654  * main planner memory context.
1655  */
1656 void
1657 mutate_eclass_expressions(PlannerInfo *root,
1658                                                   Node *(*mutator) (),
1659                                                   void *context)
1660 {
1661         ListCell   *lc1;
1662
1663         foreach(lc1, root->eq_classes)
1664         {
1665                 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1666                 ListCell   *lc2;
1667
1668                 foreach(lc2, cur_ec->ec_members)
1669                 {
1670                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1671
1672                         cur_em->em_expr = (Expr *)
1673                                 mutator((Node *) cur_em->em_expr, context);
1674                 }
1675         }
1676 }
1677
1678
1679 /*
1680  * find_eclass_clauses_for_index_join
1681  *        Create joinclauses usable for a nestloop-with-inner-indexscan
1682  *        scanning the given inner rel with the specified set of outer rels.
1683  */
1684 List *
1685 find_eclass_clauses_for_index_join(PlannerInfo *root, RelOptInfo *rel,
1686                                                                    Relids outer_relids)
1687 {
1688         List       *result = NIL;
1689         bool            is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1690         ListCell   *lc1;
1691
1692         foreach(lc1, root->eq_classes)
1693         {
1694                 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1695                 ListCell   *lc2;
1696
1697                 /*
1698                  * Won't generate joinclauses if const or single-member (the latter
1699                  * test covers the volatile case too)
1700                  */
1701                 if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
1702                         continue;
1703
1704                 /*
1705                  * No point in searching if rel not mentioned in eclass (but we can't
1706                  * tell that for a child rel).
1707                  */
1708                 if (!is_child_rel &&
1709                         !bms_is_subset(rel->relids, cur_ec->ec_relids))
1710                         continue;
1711                 /* ... nor if no overlap with outer_relids */
1712                 if (!bms_overlap(outer_relids, cur_ec->ec_relids))
1713                         continue;
1714
1715                 /* Scan members, looking for indexable columns */
1716                 foreach(lc2, cur_ec->ec_members)
1717                 {
1718                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1719                         EquivalenceMember *best_outer_em = NULL;
1720                         Oid                     best_eq_op = InvalidOid;
1721                         ListCell   *lc3;
1722
1723                         if (!bms_equal(cur_em->em_relids, rel->relids) ||
1724                                 !eclass_matches_any_index(cur_ec, cur_em, rel))
1725                                 continue;
1726
1727                         /*
1728                          * Found one, so try to generate a join clause.  This is like
1729                          * generate_join_implied_equalities_normal, except simpler since
1730                          * our only preference item is to pick a Var on the outer side. We
1731                          * only need one join clause per index col.
1732                          */
1733                         foreach(lc3, cur_ec->ec_members)
1734                         {
1735                                 EquivalenceMember *outer_em = (EquivalenceMember *) lfirst(lc3);
1736                                 Oid                     eq_op;
1737
1738                                 if (!bms_is_subset(outer_em->em_relids, outer_relids))
1739                                         continue;
1740                                 eq_op = select_equality_operator(cur_ec,
1741                                                                                                  cur_em->em_datatype,
1742                                                                                                  outer_em->em_datatype);
1743                                 if (!OidIsValid(eq_op))
1744                                         continue;
1745                                 best_outer_em = outer_em;
1746                                 best_eq_op = eq_op;
1747                                 if (IsA(outer_em->em_expr, Var) ||
1748                                         (IsA(outer_em->em_expr, RelabelType) &&
1749                                          IsA(((RelabelType *) outer_em->em_expr)->arg, Var)))
1750                                         break;          /* no need to look further */
1751                         }
1752
1753                         if (best_outer_em)
1754                         {
1755                                 /* Found a suitable joinclause */
1756                                 RestrictInfo *rinfo;
1757
1758                                 /* set parent_ec to mark as redundant with other joinclauses */
1759                                 rinfo = create_join_clause(root, cur_ec, best_eq_op,
1760                                                                                    cur_em, best_outer_em,
1761                                                                                    cur_ec);
1762
1763                                 result = lappend(result, rinfo);
1764
1765                                 /*
1766                                  * Note: we keep scanning here because we want to provide a
1767                                  * clause for every possible indexcol.
1768                                  */
1769                         }
1770                 }
1771         }
1772
1773         return result;
1774 }
1775
1776
1777 /*
1778  * have_relevant_eclass_joinclause
1779  *              Detect whether there is an EquivalenceClass that could produce
1780  *              a joinclause between the two given relations.
1781  *
1782  * This is essentially a very cut-down version of
1783  * generate_join_implied_equalities().  Note it's OK to occasionally say "yes"
1784  * incorrectly.  Hence we don't bother with details like whether the lack of a
1785  * cross-type operator might prevent the clause from actually being generated.
1786  */
1787 bool
1788 have_relevant_eclass_joinclause(PlannerInfo *root,
1789                                                                 RelOptInfo *rel1, RelOptInfo *rel2)
1790 {
1791         ListCell   *lc1;
1792
1793         foreach(lc1, root->eq_classes)
1794         {
1795                 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1796                 bool            has_rel1;
1797                 bool            has_rel2;
1798                 ListCell   *lc2;
1799
1800                 /*
1801                  * Won't generate joinclauses if single-member (this test covers the
1802                  * volatile case too)
1803                  */
1804                 if (list_length(ec->ec_members) <= 1)
1805                         continue;
1806
1807                 /*
1808                  * Note we don't test ec_broken; if we did, we'd need a separate code
1809                  * path to look through ec_sources.  Checking the members anyway is OK
1810                  * as a possibly-overoptimistic heuristic.
1811                  *
1812                  * We don't test ec_has_const either, even though a const eclass
1813                  * won't generate real join clauses.  This is because if we had
1814                  * "WHERE a.x = b.y and a.x = 42", it is worth considering a join
1815                  * between a and b, since the join result is likely to be small even
1816                  * though it'll end up being an unqualified nestloop.
1817                  */
1818
1819                 /* Needn't scan if it couldn't contain members from each rel */
1820                 if (!bms_overlap(rel1->relids, ec->ec_relids) ||
1821                         !bms_overlap(rel2->relids, ec->ec_relids))
1822                         continue;
1823
1824                 /* Scan the EC to see if it has member(s) in each rel */
1825                 has_rel1 = has_rel2 = false;
1826                 foreach(lc2, ec->ec_members)
1827                 {
1828                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1829
1830                         if (cur_em->em_is_const || cur_em->em_is_child)
1831                                 continue;               /* ignore consts and children here */
1832                         if (bms_is_subset(cur_em->em_relids, rel1->relids))
1833                         {
1834                                 has_rel1 = true;
1835                                 if (has_rel2)
1836                                         break;
1837                         }
1838                         if (bms_is_subset(cur_em->em_relids, rel2->relids))
1839                         {
1840                                 has_rel2 = true;
1841                                 if (has_rel1)
1842                                         break;
1843                         }
1844                 }
1845
1846                 if (has_rel1 && has_rel2)
1847                         return true;
1848         }
1849
1850         return false;
1851 }
1852
1853
1854 /*
1855  * has_relevant_eclass_joinclause
1856  *              Detect whether there is an EquivalenceClass that could produce
1857  *              a joinclause between the given relation and anything else.
1858  *
1859  * This is the same as have_relevant_eclass_joinclause with the other rel
1860  * implicitly defined as "everything else in the query".
1861  */
1862 bool
1863 has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
1864 {
1865         ListCell   *lc1;
1866
1867         foreach(lc1, root->eq_classes)
1868         {
1869                 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1870                 bool            has_rel1;
1871                 bool            has_rel2;
1872                 ListCell   *lc2;
1873
1874                 /*
1875                  * Won't generate joinclauses if single-member (this test covers the
1876                  * volatile case too)
1877                  */
1878                 if (list_length(ec->ec_members) <= 1)
1879                         continue;
1880
1881                 /*
1882                  * Note we don't test ec_broken; if we did, we'd need a separate code
1883                  * path to look through ec_sources.  Checking the members anyway is OK
1884                  * as a possibly-overoptimistic heuristic.
1885                  *
1886                  * We don't test ec_has_const either, even though a const eclass
1887                  * won't generate real join clauses.  This is because if we had
1888                  * "WHERE a.x = b.y and a.x = 42", it is worth considering a join
1889                  * between a and b, since the join result is likely to be small even
1890                  * though it'll end up being an unqualified nestloop.
1891                  */
1892
1893                 /* Needn't scan if it couldn't contain members from each rel */
1894                 if (!bms_overlap(rel1->relids, ec->ec_relids) ||
1895                         bms_is_subset(ec->ec_relids, rel1->relids))
1896                         continue;
1897
1898                 /* Scan the EC to see if it has member(s) in each rel */
1899                 has_rel1 = has_rel2 = false;
1900                 foreach(lc2, ec->ec_members)
1901                 {
1902                         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1903
1904                         if (cur_em->em_is_const || cur_em->em_is_child)
1905                                 continue;               /* ignore consts and children here */
1906                         if (bms_is_subset(cur_em->em_relids, rel1->relids))
1907                         {
1908                                 has_rel1 = true;
1909                                 if (has_rel2)
1910                                         break;
1911                         }
1912                         if (!bms_overlap(cur_em->em_relids, rel1->relids))
1913                         {
1914                                 has_rel2 = true;
1915                                 if (has_rel1)
1916                                         break;
1917                         }
1918                 }
1919
1920                 if (has_rel1 && has_rel2)
1921                         return true;
1922         }
1923
1924         return false;
1925 }
1926
1927
1928 /*
1929  * eclass_useful_for_merging
1930  *        Detect whether the EC could produce any mergejoinable join clauses
1931  *        against the specified relation.
1932  *
1933  * This is just a heuristic test and doesn't have to be exact; it's better
1934  * to say "yes" incorrectly than "no".  Hence we don't bother with details
1935  * like whether the lack of a cross-type operator might prevent the clause
1936  * from actually being generated.
1937  */
1938 bool
1939 eclass_useful_for_merging(EquivalenceClass *eclass,
1940                                                   RelOptInfo *rel)
1941 {
1942         ListCell   *lc;
1943
1944         Assert(!eclass->ec_merged);
1945
1946         /*
1947          * Won't generate joinclauses if const or single-member (the latter test
1948          * covers the volatile case too)
1949          */
1950         if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
1951                 return false;
1952
1953         /*
1954          * Note we don't test ec_broken; if we did, we'd need a separate code path
1955          * to look through ec_sources.  Checking the members anyway is OK as a
1956          * possibly-overoptimistic heuristic.
1957          */
1958
1959         /* If rel already includes all members of eclass, no point in searching */
1960         if (bms_is_subset(eclass->ec_relids, rel->relids))
1961                 return false;
1962
1963         /* To join, we need a member not in the given rel */
1964         foreach(lc, eclass->ec_members)
1965         {
1966                 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
1967
1968                 if (!cur_em->em_is_child &&
1969                         !bms_overlap(cur_em->em_relids, rel->relids))
1970                         return true;
1971         }
1972
1973         return false;
1974 }