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

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