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