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