1 /*-------------------------------------------------------------------------
4 * Routines for managing EquivalenceClasses
6 * See src/backend/optimizer/README for discussion of EquivalenceClasses.
9 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
10 * Portions Copyright (c) 1994, Regents of the University of California
13 * src/backend/optimizer/path/equivclass.c
15 *-------------------------------------------------------------------------
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"
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,
46 static List *generate_join_implied_equalities_broken(PlannerInfo *root,
48 Relids nominal_join_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,
62 static bool reconsider_full_join_clause(PlannerInfo *root,
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).
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...)
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
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.
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
98 process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
99 bool below_outer_join)
101 Expr *clause = restrictinfo->clause;
110 item1_nullable_relids,
111 item2_nullable_relids;
113 EquivalenceClass *ec1,
115 EquivalenceMember *em1,
119 /* Should not already be marked as having generated an eclass */
120 Assert(restrictinfo->left_ec == NULL);
121 Assert(restrictinfo->right_ec == NULL);
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;
133 * Ensure both input expressions expose the desired collation (their types
134 * should be OK already); see comments for canonicalize_ec_expression.
136 item1 = canonicalize_ec_expression(item1,
137 exprType((Node *) item1),
139 item2 = canonicalize_ec_expression(item2,
140 exprType((Node *) item2),
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.
152 if (equal(item1, item2))
153 return false; /* X=X is not a useful equivalence */
156 * If below outer join, check for strictness, else reject.
158 if (below_outer_join)
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 */
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);
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.
182 op_input_types(opno, &item1_type, &item2_type);
184 opfamilies = restrictinfo->mergeopfamilies;
187 * Sweep through the existing EquivalenceClasses looking for matches to
188 * item1 and item2. These are the possible outcomes:
190 * 1. We find both in the same EC. The equivalence is already known, so
191 * there's nothing to do.
193 * 2. We find both in different ECs. Merge the two ECs together.
195 * 3. We find just one. Add the other to its EC.
197 * 4. We find neither. Make a new, two-entry EC.
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.
206 foreach(lc1, root->eq_classes)
208 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
211 /* Never match to a volatile EC */
212 if (cur_ec->ec_has_volatile)
216 * The collation has to match; check this first since it's cheaper
217 * than the opfamily comparison.
219 if (collation != cur_ec->ec_collation)
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().
227 if (!equal(opfamilies, cur_ec->ec_opfamilies))
230 foreach(lc2, cur_ec->ec_members)
232 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
234 Assert(!cur_em->em_is_child); /* no children yet */
237 * If below an outer join, don't match constants: they're not as
238 * constant as they look.
240 if ((below_outer_join || cur_ec->ec_below_outer_join) &&
245 item1_type == cur_em->em_datatype &&
246 equal(item1, cur_em->em_expr))
255 item2_type == cur_em->em_datatype &&
256 equal(item2, cur_em->em_expr))
269 /* Sweep finished, what did we find? */
273 /* If case 1, nothing to do, except add to sources */
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;
288 * Case 2: need to merge ec1 and ec2. This should never happen after
289 * we've built any canonical pathkeys; if it did, those pathkeys might
290 * be rendered non-canonical by the merge.
292 if (root->canon_pathkeys != NIL)
293 elog(ERROR, "too late to merge equivalence classes");
296 * We add ec2's items to ec1, then set ec2's ec_merged link to point
297 * to ec1 and remove ec2 from the eq_classes list. We cannot simply
298 * delete ec2 because that could leave dangling pointers in existing
299 * PathKeys. We leave it behind with a link so that the merged EC can
302 ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
303 ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
304 ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
305 ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
306 ec1->ec_has_const |= ec2->ec_has_const;
307 /* can't need to set has_volatile */
308 ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
309 ec2->ec_merged = ec1;
310 root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
311 /* just to avoid debugging confusion w/ dangling pointers: */
312 ec2->ec_members = NIL;
313 ec2->ec_sources = NIL;
314 ec2->ec_derives = NIL;
315 ec2->ec_relids = NULL;
316 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
317 ec1->ec_below_outer_join |= below_outer_join;
318 /* mark the RI as associated with this eclass */
319 restrictinfo->left_ec = ec1;
320 restrictinfo->right_ec = ec1;
321 /* mark the RI as usable with this pair of EMs */
322 restrictinfo->left_em = em1;
323 restrictinfo->right_em = em2;
327 /* Case 3: add item2 to ec1 */
328 em2 = add_eq_member(ec1, item2, item2_relids, item2_nullable_relids,
330 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
331 ec1->ec_below_outer_join |= below_outer_join;
332 /* mark the RI as associated with this eclass */
333 restrictinfo->left_ec = ec1;
334 restrictinfo->right_ec = ec1;
335 /* mark the RI as usable with this pair of EMs */
336 restrictinfo->left_em = em1;
337 restrictinfo->right_em = em2;
341 /* Case 3: add item1 to ec2 */
342 em1 = add_eq_member(ec2, item1, item1_relids, item1_nullable_relids,
344 ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
345 ec2->ec_below_outer_join |= below_outer_join;
346 /* mark the RI as associated with this eclass */
347 restrictinfo->left_ec = ec2;
348 restrictinfo->right_ec = ec2;
349 /* mark the RI as usable with this pair of EMs */
350 restrictinfo->left_em = em1;
351 restrictinfo->right_em = em2;
355 /* Case 4: make a new, two-entry EC */
356 EquivalenceClass *ec = makeNode(EquivalenceClass);
358 ec->ec_opfamilies = opfamilies;
359 ec->ec_collation = collation;
360 ec->ec_members = NIL;
361 ec->ec_sources = list_make1(restrictinfo);
362 ec->ec_derives = NIL;
363 ec->ec_relids = NULL;
364 ec->ec_has_const = false;
365 ec->ec_has_volatile = false;
366 ec->ec_below_outer_join = below_outer_join;
367 ec->ec_broken = false;
369 ec->ec_merged = NULL;
370 em1 = add_eq_member(ec, item1, item1_relids, item1_nullable_relids,
372 em2 = add_eq_member(ec, item2, item2_relids, item2_nullable_relids,
375 root->eq_classes = lappend(root->eq_classes, ec);
377 /* mark the RI as associated with this eclass */
378 restrictinfo->left_ec = ec;
379 restrictinfo->right_ec = ec;
380 /* mark the RI as usable with this pair of EMs */
381 restrictinfo->left_em = em1;
382 restrictinfo->right_em = em2;
389 * canonicalize_ec_expression
391 * This function ensures that the expression exposes the expected type and
392 * collation, so that it will be equal() to other equivalence-class expressions
393 * that it ought to be equal() to.
395 * The rule for datatypes is that the exposed type should match what it would
396 * be for an input to an operator of the EC's opfamilies; which is usually
397 * the declared input type of the operator, but in the case of polymorphic
398 * operators no relabeling is wanted (compare the behavior of parse_coerce.c).
399 * Expressions coming in from quals will generally have the right type
400 * already, but expressions coming from indexkeys may not (because they are
401 * represented without any explicit relabel in pg_index), and the same problem
402 * occurs for sort expressions (because the parser is likewise cavalier about
403 * putting relabels on them). Such cases will be binary-compatible with the
404 * real operators, so adding a RelabelType is sufficient.
406 * Also, the expression's exposed collation must match the EC's collation.
407 * This is important because in comparisons like "foo < bar COLLATE baz",
408 * only one of the expressions has the correct exposed collation as we receive
409 * it from the parser. Forcing both of them to have it ensures that all
410 * variant spellings of such a construct behave the same. Again, we can
411 * stick on a RelabelType to force the right exposed collation. (It might
412 * work to not label the collation at all in EC members, but this is risky
413 * since some parts of the system expect exprCollation() to deliver the
414 * right answer for a sort key.)
416 * Note this code assumes that the expression has already been through
417 * eval_const_expressions, so there are no CollateExprs and no redundant
421 canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
423 Oid expr_type = exprType((Node *) expr);
426 * For a polymorphic-input-type opclass, just keep the same exposed type.
428 if (IsPolymorphicType(req_type))
429 req_type = expr_type;
432 * No work if the expression exposes the right type/collation already.
434 if (expr_type != req_type ||
435 exprCollation((Node *) expr) != req_collation)
438 * Strip any existing RelabelType, then add a new one if needed. This
439 * is to preserve the invariant of no redundant RelabelTypes.
441 * If we have to change the exposed type of the stripped expression,
442 * set typmod to -1 (since the new type may not have the same typmod
443 * interpretation). If we only have to change collation, preserve the
446 while (expr && IsA(expr, RelabelType))
447 expr = (Expr *) ((RelabelType *) expr)->arg;
449 if (exprType((Node *) expr) != req_type)
450 expr = (Expr *) makeRelabelType(expr,
454 COERCE_IMPLICIT_CAST);
455 else if (exprCollation((Node *) expr) != req_collation)
456 expr = (Expr *) makeRelabelType(expr,
458 exprTypmod((Node *) expr),
460 COERCE_IMPLICIT_CAST);
467 * add_eq_member - build a new EquivalenceMember and add it to an EC
469 static EquivalenceMember *
470 add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
471 Relids nullable_relids, bool is_child, Oid datatype)
473 EquivalenceMember *em = makeNode(EquivalenceMember);
476 em->em_relids = relids;
477 em->em_nullable_relids = nullable_relids;
478 em->em_is_const = false;
479 em->em_is_child = is_child;
480 em->em_datatype = datatype;
482 if (bms_is_empty(relids))
485 * No Vars, assume it's a pseudoconstant. This is correct for entries
486 * generated from process_equivalence(), because a WHERE clause can't
487 * contain aggregates or SRFs, and non-volatility was checked before
488 * process_equivalence() ever got called. But
489 * get_eclass_for_sort_expr() has to work harder. We put the tests
490 * there not here to save cycles in the equivalence case.
493 em->em_is_const = true;
494 ec->ec_has_const = true;
495 /* it can't affect ec_relids */
497 else if (!is_child) /* child members don't add to ec_relids */
499 ec->ec_relids = bms_add_members(ec->ec_relids, relids);
501 ec->ec_members = lappend(ec->ec_members, em);
508 * get_eclass_for_sort_expr
509 * Given an expression and opfamily/collation info, find an existing
510 * equivalence class it is a member of; if none, optionally build a new
511 * single-member EquivalenceClass for it.
513 * sortref is the SortGroupRef of the originating SortGroupClause, if any,
514 * or zero if not. (It should never be zero if the expression is volatile!)
516 * If rel is not NULL, it identifies a specific relation we're considering
517 * a path for, and indicates that child EC members for that relation can be
518 * considered. Otherwise child members are ignored. (Note: since child EC
519 * members aren't guaranteed unique, a non-NULL value means that there could
520 * be more than one EC that matches the expression; if so it's order-dependent
521 * which one you get. This is annoying but it only happens in corner cases,
522 * so for now we live with just reporting the first match. See also
523 * generate_implied_equalities_for_column and match_pathkeys_to_index.)
525 * If create_it is TRUE, we'll build a new EquivalenceClass when there is no
526 * match. If create_it is FALSE, we just return NULL when no match.
528 * This can be used safely both before and after EquivalenceClass merging;
529 * since it never causes merging it does not invalidate any existing ECs
530 * or PathKeys. However, ECs added after path generation has begun are
531 * of limited usefulness, so usually it's best to create them beforehand.
533 * Note: opfamilies must be chosen consistently with the way
534 * process_equivalence() would do; that is, generated from a mergejoinable
535 * equality operator. Else we might fail to detect valid equivalences,
536 * generating poor (but not incorrect) plans.
539 get_eclass_for_sort_expr(PlannerInfo *root,
548 EquivalenceClass *newec;
549 EquivalenceMember *newem;
551 MemoryContext oldcontext;
554 * Ensure the expression exposes the correct type and collation.
556 expr = canonicalize_ec_expression(expr, opcintype, collation);
559 * Scan through the existing EquivalenceClasses for a match
561 foreach(lc1, root->eq_classes)
563 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
567 * Never match to a volatile EC, except when we are looking at another
568 * reference to the same volatile SortGroupClause.
570 if (cur_ec->ec_has_volatile &&
571 (sortref == 0 || sortref != cur_ec->ec_sortref))
574 if (collation != cur_ec->ec_collation)
576 if (!equal(opfamilies, cur_ec->ec_opfamilies))
579 foreach(lc2, cur_ec->ec_members)
581 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
584 * Ignore child members unless they match the request.
586 if (cur_em->em_is_child &&
587 !bms_equal(cur_em->em_relids, rel))
591 * If below an outer join, don't match constants: they're not as
592 * constant as they look.
594 if (cur_ec->ec_below_outer_join &&
598 if (opcintype == cur_em->em_datatype &&
599 equal(expr, cur_em->em_expr))
600 return cur_ec; /* Match! */
604 /* No match; does caller want a NULL result? */
609 * OK, build a new single-member EC
611 * Here, we must be sure that we construct the EC in the right context.
613 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
615 newec = makeNode(EquivalenceClass);
616 newec->ec_opfamilies = list_copy(opfamilies);
617 newec->ec_collation = collation;
618 newec->ec_members = NIL;
619 newec->ec_sources = NIL;
620 newec->ec_derives = NIL;
621 newec->ec_relids = NULL;
622 newec->ec_has_const = false;
623 newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
624 newec->ec_below_outer_join = false;
625 newec->ec_broken = false;
626 newec->ec_sortref = sortref;
627 newec->ec_merged = NULL;
629 if (newec->ec_has_volatile && sortref == 0) /* should not happen */
630 elog(ERROR, "volatile EquivalenceClass has no sortref");
632 newem = add_eq_member(newec, copyObject(expr), pull_varnos((Node *) expr),
633 NULL, false, opcintype);
636 * add_eq_member doesn't check for volatile functions, set-returning
637 * functions, aggregates, or window functions, but such could appear in
638 * sort expressions; so we have to check whether its const-marking was
641 if (newec->ec_has_const)
643 if (newec->ec_has_volatile ||
644 expression_returns_set((Node *) expr) ||
645 contain_agg_clause((Node *) expr) ||
646 contain_window_function((Node *) expr))
648 newec->ec_has_const = false;
649 newem->em_is_const = false;
653 root->eq_classes = lappend(root->eq_classes, newec);
655 MemoryContextSwitchTo(oldcontext);
662 * generate_base_implied_equalities
663 * Generate any restriction clauses that we can deduce from equivalence
666 * When an EC contains pseudoconstants, our strategy is to generate
667 * "member = const1" clauses where const1 is the first constant member, for
668 * every other member (including other constants). If we are able to do this
669 * then we don't need any "var = var" comparisons because we've successfully
670 * constrained all the vars at their points of creation. If we fail to
671 * generate any of these clauses due to lack of cross-type operators, we fall
672 * back to the "ec_broken" strategy described below. (XXX if there are
673 * multiple constants of different types, it's possible that we might succeed
674 * in forming all the required clauses if we started from a different const
675 * member; but this seems a sufficiently hokey corner case to not be worth
676 * spending lots of cycles on.)
678 * For ECs that contain no pseudoconstants, we generate derived clauses
679 * "member1 = member2" for each pair of members belonging to the same base
680 * relation (actually, if there are more than two for the same base relation,
681 * we only need enough clauses to link each to each other). This provides
682 * the base case for the recursion: each row emitted by a base relation scan
683 * will constrain all computable members of the EC to be equal. As each
684 * join path is formed, we'll add additional derived clauses on-the-fly
685 * to maintain this invariant (see generate_join_implied_equalities).
687 * If the opfamilies used by the EC do not provide complete sets of cross-type
688 * equality operators, it is possible that we will fail to generate a clause
689 * that must be generated to maintain the invariant. (An example: given
690 * "WHERE a.x = b.y AND b.y = a.z", the scheme breaks down if we cannot
691 * generate "a.x = a.z" as a restriction clause for A.) In this case we mark
692 * the EC "ec_broken" and fall back to regurgitating its original source
693 * RestrictInfos at appropriate times. We do not try to retract any derived
694 * clauses already generated from the broken EC, so the resulting plan could
695 * be poor due to bad selectivity estimates caused by redundant clauses. But
696 * the correct solution to that is to fix the opfamilies ...
698 * Equality clauses derived by this function are passed off to
699 * process_implied_equality (in plan/initsplan.c) to be inserted into the
700 * restrictinfo datastructures. Note that this must be called after initial
701 * scanning of the quals and before Path construction begins.
703 * We make no attempt to avoid generating duplicate RestrictInfos here: we
704 * don't search ec_sources for matches, nor put the created RestrictInfos
705 * into ec_derives. Doing so would require some slightly ugly changes in
706 * initsplan.c's API, and there's no real advantage, because the clauses
707 * generated here can't duplicate anything we will generate for joins anyway.
710 generate_base_implied_equalities(PlannerInfo *root)
715 foreach(lc, root->eq_classes)
717 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
719 Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
720 Assert(!ec->ec_broken); /* not yet anyway... */
722 /* Single-member ECs won't generate any deductions */
723 if (list_length(ec->ec_members) <= 1)
726 if (ec->ec_has_const)
727 generate_base_implied_equalities_const(root, ec);
729 generate_base_implied_equalities_no_const(root, ec);
731 /* Recover if we failed to generate required derived clauses */
733 generate_base_implied_equalities_broken(root, ec);
737 * This is also a handy place to mark base rels (which should all exist by
738 * now) with flags showing whether they have pending eclass joins.
740 for (rti = 1; rti < root->simple_rel_array_size; rti++)
742 RelOptInfo *brel = root->simple_rel_array[rti];
747 brel->has_eclass_joins = has_relevant_eclass_joinclause(root, brel);
752 * generate_base_implied_equalities when EC contains pseudoconstant(s)
755 generate_base_implied_equalities_const(PlannerInfo *root,
756 EquivalenceClass *ec)
758 EquivalenceMember *const_em = NULL;
762 * In the trivial case where we just had one "var = const" clause, push
763 * the original clause back into the main planner machinery. There is
764 * nothing to be gained by doing it differently, and we save the effort to
765 * re-build and re-analyze an equality clause that will be exactly
766 * equivalent to the old one.
768 if (list_length(ec->ec_members) == 2 &&
769 list_length(ec->ec_sources) == 1)
771 RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
773 if (bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
775 distribute_restrictinfo_to_rels(root, restrictinfo);
781 * Find the constant member to use. We prefer an actual constant to
782 * pseudo-constants (such as Params), because the constraint exclusion
783 * machinery might be able to exclude relations on the basis of generated
784 * "var = const" equalities, but "var = param" won't work for that.
786 foreach(lc, ec->ec_members)
788 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
790 if (cur_em->em_is_const)
793 if (IsA(cur_em->em_expr, Const))
797 Assert(const_em != NULL);
799 /* Generate a derived equality against each other member */
800 foreach(lc, ec->ec_members)
802 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
805 Assert(!cur_em->em_is_child); /* no children yet */
806 if (cur_em == const_em)
808 eq_op = select_equality_operator(ec,
810 const_em->em_datatype);
811 if (!OidIsValid(eq_op))
814 ec->ec_broken = true;
817 process_implied_equality(root, eq_op, ec->ec_collation,
818 cur_em->em_expr, const_em->em_expr,
819 bms_copy(ec->ec_relids),
820 bms_union(cur_em->em_nullable_relids,
821 const_em->em_nullable_relids),
822 ec->ec_below_outer_join,
823 cur_em->em_is_const);
828 * generate_base_implied_equalities when EC contains no pseudoconstants
831 generate_base_implied_equalities_no_const(PlannerInfo *root,
832 EquivalenceClass *ec)
834 EquivalenceMember **prev_ems;
838 * We scan the EC members once and track the last-seen member for each
839 * base relation. When we see another member of the same base relation,
840 * we generate "prev_mem = cur_mem". This results in the minimum number
841 * of derived clauses, but it's possible that it will fail when a
842 * different ordering would succeed. XXX FIXME: use a UNION-FIND
843 * algorithm similar to the way we build merged ECs. (Use a list-of-lists
846 prev_ems = (EquivalenceMember **)
847 palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
849 foreach(lc, ec->ec_members)
851 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
854 Assert(!cur_em->em_is_child); /* no children yet */
855 if (bms_membership(cur_em->em_relids) != BMS_SINGLETON)
857 relid = bms_singleton_member(cur_em->em_relids);
858 Assert(relid < root->simple_rel_array_size);
860 if (prev_ems[relid] != NULL)
862 EquivalenceMember *prev_em = prev_ems[relid];
865 eq_op = select_equality_operator(ec,
866 prev_em->em_datatype,
867 cur_em->em_datatype);
868 if (!OidIsValid(eq_op))
871 ec->ec_broken = true;
874 process_implied_equality(root, eq_op, ec->ec_collation,
875 prev_em->em_expr, cur_em->em_expr,
876 bms_copy(ec->ec_relids),
877 bms_union(prev_em->em_nullable_relids,
878 cur_em->em_nullable_relids),
879 ec->ec_below_outer_join,
882 prev_ems[relid] = cur_em;
888 * We also have to make sure that all the Vars used in the member clauses
889 * will be available at any join node we might try to reference them at.
890 * For the moment we force all the Vars to be available at all join nodes
891 * for this eclass. Perhaps this could be improved by doing some
892 * pre-analysis of which members we prefer to join, but it's no worse than
893 * what happened in the pre-8.3 code.
895 foreach(lc, ec->ec_members)
897 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
898 List *vars = pull_var_clause((Node *) cur_em->em_expr,
899 PVC_RECURSE_AGGREGATES,
900 PVC_INCLUDE_PLACEHOLDERS);
902 add_vars_to_targetlist(root, vars, ec->ec_relids, false);
908 * generate_base_implied_equalities cleanup after failure
910 * What we must do here is push any zero- or one-relation source RestrictInfos
911 * of the EC back into the main restrictinfo datastructures. Multi-relation
912 * clauses will be regurgitated later by generate_join_implied_equalities().
913 * (We do it this way to maintain continuity with the case that ec_broken
914 * becomes set only after we've gone up a join level or two.) However, for
915 * an EC that contains constants, we can adopt a simpler strategy and just
916 * throw back all the source RestrictInfos immediately; that works because
917 * we know that such an EC can't become broken later. (This rule justifies
918 * ignoring ec_has_const ECs in generate_join_implied_equalities, even when
922 generate_base_implied_equalities_broken(PlannerInfo *root,
923 EquivalenceClass *ec)
927 foreach(lc, ec->ec_sources)
929 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
931 if (ec->ec_has_const ||
932 bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
933 distribute_restrictinfo_to_rels(root, restrictinfo);
939 * generate_join_implied_equalities
940 * Generate any join clauses that we can deduce from equivalence classes.
942 * At a join node, we must enforce restriction clauses sufficient to ensure
943 * that all equivalence-class members computable at that node are equal.
944 * Since the set of clauses to enforce can vary depending on which subset
945 * relations are the inputs, we have to compute this afresh for each join
946 * relation pair. Hence a fresh List of RestrictInfo nodes is built and
947 * passed back on each call.
949 * In addition to its use at join nodes, this can be applied to generate
950 * eclass-based join clauses for use in a parameterized scan of a base rel.
951 * The reason for the asymmetry of specifying the inner rel as a RelOptInfo
952 * and the outer rel by Relids is that this usage occurs before we have
953 * built any join RelOptInfos.
955 * An annoying special case for parameterized scans is that the inner rel can
956 * be an appendrel child (an "other rel"). In this case we must generate
957 * appropriate clauses using child EC members. add_child_rel_equivalences
958 * must already have been done for the child rel.
960 * The results are sufficient for use in merge, hash, and plain nestloop join
961 * methods. We do not worry here about selecting clauses that are optimal
962 * for use in a parameterized indexscan. indxpath.c makes its own selections
963 * of clauses to use, and if the ones we pick here are redundant with those,
964 * the extras will be eliminated at createplan time, using the parent_ec
965 * markers that we provide (see is_redundant_derived_clause()).
967 * Because the same join clauses are likely to be needed multiple times as
968 * we consider different join paths, we avoid generating multiple copies:
969 * whenever we select a particular pair of EquivalenceMembers to join,
970 * we check to see if the pair matches any original clause (in ec_sources)
971 * or previously-built clause (in ec_derives). This saves memory and allows
972 * re-use of information cached in RestrictInfos.
974 * join_relids should always equal bms_union(outer_relids, inner_rel->relids).
975 * We could simplify this function's API by computing it internally, but in
976 * all current uses, the caller has the value at hand anyway.
979 generate_join_implied_equalities(PlannerInfo *root,
982 RelOptInfo *inner_rel)
985 Relids inner_relids = inner_rel->relids;
986 Relids nominal_inner_relids;
987 Relids nominal_join_relids;
988 AppendRelInfo *inner_appinfo;
991 /* If inner rel is a child, extra setup work is needed */
992 if (inner_rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
994 /* Lookup parent->child translation data */
995 inner_appinfo = find_childrel_appendrelinfo(root, inner_rel);
996 /* Construct relids for the parent rel */
997 nominal_inner_relids = bms_make_singleton(inner_appinfo->parent_relid);
998 /* ECs will be marked with the parent's relid, not the child's */
999 nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1003 inner_appinfo = NULL;
1004 nominal_inner_relids = inner_relids;
1005 nominal_join_relids = join_relids;
1008 foreach(lc, root->eq_classes)
1010 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
1011 List *sublist = NIL;
1013 /* ECs containing consts do not need any further enforcement */
1014 if (ec->ec_has_const)
1017 /* Single-member ECs won't generate any deductions */
1018 if (list_length(ec->ec_members) <= 1)
1021 /* We can quickly ignore any that don't overlap the join, too */
1022 if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1026 sublist = generate_join_implied_equalities_normal(root,
1032 /* Recover if we failed to generate required derived clauses */
1034 sublist = generate_join_implied_equalities_broken(root,
1036 nominal_join_relids,
1038 nominal_inner_relids,
1041 result = list_concat(result, sublist);
1048 * generate_join_implied_equalities for a still-valid EC
1051 generate_join_implied_equalities_normal(PlannerInfo *root,
1052 EquivalenceClass *ec,
1054 Relids outer_relids,
1055 Relids inner_relids)
1058 List *new_members = NIL;
1059 List *outer_members = NIL;
1060 List *inner_members = NIL;
1064 * First, scan the EC to identify member values that are computable at the
1065 * outer rel, at the inner rel, or at this relation but not in either
1066 * input rel. The outer-rel members should already be enforced equal,
1067 * likewise for the inner-rel members. We'll need to create clauses to
1068 * enforce that any newly computable members are all equal to each other
1069 * as well as to at least one input member, plus enforce at least one
1070 * outer-rel member equal to at least one inner-rel member.
1072 foreach(lc1, ec->ec_members)
1074 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
1077 * We don't need to check explicitly for child EC members. This test
1078 * against join_relids will cause them to be ignored except when
1079 * considering a child inner rel, which is what we want.
1081 if (!bms_is_subset(cur_em->em_relids, join_relids))
1082 continue; /* not computable yet, or wrong child */
1084 if (bms_is_subset(cur_em->em_relids, outer_relids))
1085 outer_members = lappend(outer_members, cur_em);
1086 else if (bms_is_subset(cur_em->em_relids, inner_relids))
1087 inner_members = lappend(inner_members, cur_em);
1089 new_members = lappend(new_members, cur_em);
1093 * First, select the joinclause if needed. We can equate any one outer
1094 * member to any one inner member, but we have to find a datatype
1095 * combination for which an opfamily member operator exists. If we have
1096 * choices, we prefer simple Var members (possibly with RelabelType) since
1097 * these are (a) cheapest to compute at runtime and (b) most likely to
1098 * have useful statistics. Also, prefer operators that are also
1101 if (outer_members && inner_members)
1103 EquivalenceMember *best_outer_em = NULL;
1104 EquivalenceMember *best_inner_em = NULL;
1105 Oid best_eq_op = InvalidOid;
1106 int best_score = -1;
1107 RestrictInfo *rinfo;
1109 foreach(lc1, outer_members)
1111 EquivalenceMember *outer_em = (EquivalenceMember *) lfirst(lc1);
1114 foreach(lc2, inner_members)
1116 EquivalenceMember *inner_em = (EquivalenceMember *) lfirst(lc2);
1120 eq_op = select_equality_operator(ec,
1121 outer_em->em_datatype,
1122 inner_em->em_datatype);
1123 if (!OidIsValid(eq_op))
1126 if (IsA(outer_em->em_expr, Var) ||
1127 (IsA(outer_em->em_expr, RelabelType) &&
1128 IsA(((RelabelType *) outer_em->em_expr)->arg, Var)))
1130 if (IsA(inner_em->em_expr, Var) ||
1131 (IsA(inner_em->em_expr, RelabelType) &&
1132 IsA(((RelabelType *) inner_em->em_expr)->arg, Var)))
1134 if (op_hashjoinable(eq_op,
1135 exprType((Node *) outer_em->em_expr)))
1137 if (score > best_score)
1139 best_outer_em = outer_em;
1140 best_inner_em = inner_em;
1143 if (best_score == 3)
1144 break; /* no need to look further */
1147 if (best_score == 3)
1148 break; /* no need to look further */
1153 ec->ec_broken = true;
1158 * Create clause, setting parent_ec to mark it as redundant with other
1161 rinfo = create_join_clause(root, ec, best_eq_op,
1162 best_outer_em, best_inner_em,
1165 result = lappend(result, rinfo);
1169 * Now deal with building restrictions for any expressions that involve
1170 * Vars from both sides of the join. We have to equate all of these to
1171 * each other as well as to at least one old member (if any).
1173 * XXX as in generate_base_implied_equalities_no_const, we could be a lot
1174 * smarter here to avoid unnecessary failures in cross-type situations.
1175 * For now, use the same left-to-right method used there.
1179 List *old_members = list_concat(outer_members, inner_members);
1180 EquivalenceMember *prev_em = NULL;
1181 RestrictInfo *rinfo;
1183 /* For now, arbitrarily take the first old_member as the one to use */
1185 new_members = lappend(new_members, linitial(old_members));
1187 foreach(lc1, new_members)
1189 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
1191 if (prev_em != NULL)
1195 eq_op = select_equality_operator(ec,
1196 prev_em->em_datatype,
1197 cur_em->em_datatype);
1198 if (!OidIsValid(eq_op))
1201 ec->ec_broken = true;
1204 /* do NOT set parent_ec, this qual is not redundant! */
1205 rinfo = create_join_clause(root, ec, eq_op,
1209 result = lappend(result, rinfo);
1219 * generate_join_implied_equalities cleanup after failure
1221 * Return any original RestrictInfos that are enforceable at this join.
1223 * In the case of a child inner relation, we have to translate the
1224 * original RestrictInfos from parent to child Vars.
1227 generate_join_implied_equalities_broken(PlannerInfo *root,
1228 EquivalenceClass *ec,
1229 Relids nominal_join_relids,
1230 Relids outer_relids,
1231 Relids nominal_inner_relids,
1232 AppendRelInfo *inner_appinfo)
1237 foreach(lc, ec->ec_sources)
1239 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1240 Relids clause_relids = restrictinfo->required_relids;
1242 if (bms_is_subset(clause_relids, nominal_join_relids) &&
1243 !bms_is_subset(clause_relids, outer_relids) &&
1244 !bms_is_subset(clause_relids, nominal_inner_relids))
1245 result = lappend(result, restrictinfo);
1249 * If we have to translate, just brute-force apply adjust_appendrel_attrs
1250 * to all the RestrictInfos at once. This will result in returning
1251 * RestrictInfos that are not listed in ec_derives, but there shouldn't be
1252 * any duplication, and it's a sufficiently narrow corner case that we
1253 * shouldn't sweat too much over it anyway.
1256 result = (List *) adjust_appendrel_attrs(root, (Node *) result,
1264 * select_equality_operator
1265 * Select a suitable equality operator for comparing two EC members
1267 * Returns InvalidOid if no operator can be found for this datatype combination
1270 select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
1274 foreach(lc, ec->ec_opfamilies)
1276 Oid opfamily = lfirst_oid(lc);
1279 opno = get_opfamily_member(opfamily, lefttype, righttype,
1280 BTEqualStrategyNumber);
1281 if (OidIsValid(opno))
1289 * create_join_clause
1290 * Find or make a RestrictInfo comparing the two given EC members
1291 * with the given operator.
1293 * parent_ec is either equal to ec (if the clause is a potentially-redundant
1294 * join clause) or NULL (if not). We have to treat this as part of the
1295 * match requirements --- it's possible that a clause comparing the same two
1296 * EMs is a join clause in one join path and a restriction clause in another.
1298 static RestrictInfo *
1299 create_join_clause(PlannerInfo *root,
1300 EquivalenceClass *ec, Oid opno,
1301 EquivalenceMember *leftem,
1302 EquivalenceMember *rightem,
1303 EquivalenceClass *parent_ec)
1305 RestrictInfo *rinfo;
1307 MemoryContext oldcontext;
1310 * Search to see if we already built a RestrictInfo for this pair of
1311 * EquivalenceMembers. We can use either original source clauses or
1312 * previously-derived clauses. The check on opno is probably redundant,
1315 foreach(lc, ec->ec_sources)
1317 rinfo = (RestrictInfo *) lfirst(lc);
1318 if (rinfo->left_em == leftem &&
1319 rinfo->right_em == rightem &&
1320 rinfo->parent_ec == parent_ec &&
1321 opno == ((OpExpr *) rinfo->clause)->opno)
1325 foreach(lc, ec->ec_derives)
1327 rinfo = (RestrictInfo *) lfirst(lc);
1328 if (rinfo->left_em == leftem &&
1329 rinfo->right_em == rightem &&
1330 rinfo->parent_ec == parent_ec &&
1331 opno == ((OpExpr *) rinfo->clause)->opno)
1336 * Not there, so build it, in planner context so we can re-use it. (Not
1337 * important in normal planning, but definitely so in GEQO.)
1339 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
1341 rinfo = build_implied_join_equality(opno,
1345 bms_union(leftem->em_relids,
1346 rightem->em_relids),
1347 bms_union(leftem->em_nullable_relids,
1348 rightem->em_nullable_relids));
1350 /* Mark the clause as redundant, or not */
1351 rinfo->parent_ec = parent_ec;
1354 * We know the correct values for left_ec/right_ec, ie this particular EC,
1355 * so we can just set them directly instead of forcing another lookup.
1357 rinfo->left_ec = ec;
1358 rinfo->right_ec = ec;
1360 /* Mark it as usable with these EMs */
1361 rinfo->left_em = leftem;
1362 rinfo->right_em = rightem;
1363 /* and save it for possible re-use */
1364 ec->ec_derives = lappend(ec->ec_derives, rinfo);
1366 MemoryContextSwitchTo(oldcontext);
1373 * reconsider_outer_join_clauses
1374 * Re-examine any outer-join clauses that were set aside by
1375 * distribute_qual_to_rels(), and see if we can derive any
1376 * EquivalenceClasses from them. Then, if they were not made
1377 * redundant, push them out into the regular join-clause lists.
1379 * When we have mergejoinable clauses A = B that are outer-join clauses,
1380 * we can't blindly combine them with other clauses A = C to deduce B = C,
1381 * since in fact the "equality" A = B won't necessarily hold above the
1382 * outer join (one of the variables might be NULL instead). Nonetheless
1383 * there are cases where we can add qual clauses using transitivity.
1385 * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
1386 * for which there is also an equivalence clause OUTERVAR = CONSTANT.
1387 * It is safe and useful to push a clause INNERVAR = CONSTANT into the
1388 * evaluation of the inner (nullable) relation, because any inner rows not
1389 * meeting this condition will not contribute to the outer-join result anyway.
1390 * (Any outer rows they could join to will be eliminated by the pushed-down
1391 * equivalence clause.)
1393 * Note that the above rule does not work for full outer joins; nor is it
1394 * very interesting to consider cases where the generated equivalence clause
1395 * would involve relations outside the outer join, since such clauses couldn't
1396 * be pushed into the inner side's scan anyway. So the restriction to
1397 * outervar = pseudoconstant is not really giving up anything.
1399 * For full-join cases, we can only do something useful if it's a FULL JOIN
1400 * USING and a merged column has an equivalence MERGEDVAR = CONSTANT.
1401 * By the time it gets here, the merged column will look like
1402 * COALESCE(LEFTVAR, RIGHTVAR)
1403 * and we will have a full-join clause LEFTVAR = RIGHTVAR that we can match
1404 * the COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
1405 * and RIGHTVAR = CONSTANT into the input relations, since any rows not
1406 * meeting these conditions cannot contribute to the join result.
1408 * Again, there isn't any traction to be gained by trying to deal with
1409 * clauses comparing a mergedvar to a non-pseudoconstant. So we can make
1410 * use of the EquivalenceClasses to search for matching variables that were
1411 * equivalenced to constants. The interesting outer-join clauses were
1412 * accumulated for us by distribute_qual_to_rels.
1414 * When we find one of these cases, we implement the changes we want by
1415 * generating a new equivalence clause INNERVAR = CONSTANT (or LEFTVAR, etc)
1416 * and pushing it into the EquivalenceClass structures. This is because we
1417 * may already know that INNERVAR is equivalenced to some other var(s), and
1418 * we'd like the constant to propagate to them too. Note that it would be
1419 * unsafe to merge any existing EC for INNERVAR with the OUTERVAR's EC ---
1420 * that could result in propagating constant restrictions from
1421 * INNERVAR to OUTERVAR, which would be very wrong.
1423 * It's possible that the INNERVAR is also an OUTERVAR for some other
1424 * outer-join clause, in which case the process can be repeated. So we repeat
1425 * looping over the lists of clauses until no further deductions can be made.
1426 * Whenever we do make a deduction, we remove the generating clause from the
1427 * lists, since we don't want to make the same deduction twice.
1429 * If we don't find any match for a set-aside outer join clause, we must
1430 * throw it back into the regular joinclause processing by passing it to
1431 * distribute_restrictinfo_to_rels(). If we do generate a derived clause,
1432 * however, the outer-join clause is redundant. We still throw it back,
1433 * because otherwise the join will be seen as a clauseless join and avoided
1434 * during join order searching; but we mark it as redundant to keep from
1435 * messing up the joinrel's size estimate. (This behavior means that the
1436 * API for this routine is uselessly complex: we could have just put all
1437 * the clauses into the regular processing initially. We keep it because
1438 * someday we might want to do something else, such as inserting "dummy"
1439 * joinclauses instead of real ones.)
1441 * Outer join clauses that are marked outerjoin_delayed are special: this
1442 * condition means that one or both VARs might go to null due to a lower
1443 * outer join. We can still push a constant through the clause, but only
1444 * if its operator is strict; and we *have to* throw the clause back into
1445 * regular joinclause processing. By keeping the strict join clause,
1446 * we ensure that any null-extended rows that are mistakenly generated due
1447 * to suppressing rows not matching the constant will be rejected at the
1448 * upper outer join. (This doesn't work for full-join clauses.)
1451 reconsider_outer_join_clauses(PlannerInfo *root)
1458 /* Outer loop repeats until we find no more deductions */
1463 /* Process the LEFT JOIN clauses */
1465 for (cell = list_head(root->left_join_clauses); cell; cell = next)
1467 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1470 if (reconsider_outer_join_clause(root, rinfo, true))
1473 /* remove it from the list */
1474 root->left_join_clauses =
1475 list_delete_cell(root->left_join_clauses, cell, prev);
1476 /* we throw it back anyway (see notes above) */
1477 /* but the thrown-back clause has no extra selectivity */
1478 rinfo->norm_selec = 2.0;
1479 rinfo->outer_selec = 1.0;
1480 distribute_restrictinfo_to_rels(root, rinfo);
1486 /* Process the RIGHT JOIN clauses */
1488 for (cell = list_head(root->right_join_clauses); cell; cell = next)
1490 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1493 if (reconsider_outer_join_clause(root, rinfo, false))
1496 /* remove it from the list */
1497 root->right_join_clauses =
1498 list_delete_cell(root->right_join_clauses, cell, prev);
1499 /* we throw it back anyway (see notes above) */
1500 /* but the thrown-back clause has no extra selectivity */
1501 rinfo->norm_selec = 2.0;
1502 rinfo->outer_selec = 1.0;
1503 distribute_restrictinfo_to_rels(root, rinfo);
1509 /* Process the FULL JOIN clauses */
1511 for (cell = list_head(root->full_join_clauses); cell; cell = next)
1513 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1516 if (reconsider_full_join_clause(root, rinfo))
1519 /* remove it from the list */
1520 root->full_join_clauses =
1521 list_delete_cell(root->full_join_clauses, cell, prev);
1522 /* we throw it back anyway (see notes above) */
1523 /* but the thrown-back clause has no extra selectivity */
1524 rinfo->norm_selec = 2.0;
1525 rinfo->outer_selec = 1.0;
1526 distribute_restrictinfo_to_rels(root, rinfo);
1533 /* Now, any remaining clauses have to be thrown back */
1534 foreach(cell, root->left_join_clauses)
1536 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1538 distribute_restrictinfo_to_rels(root, rinfo);
1540 foreach(cell, root->right_join_clauses)
1542 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1544 distribute_restrictinfo_to_rels(root, rinfo);
1546 foreach(cell, root->full_join_clauses)
1548 RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
1550 distribute_restrictinfo_to_rels(root, rinfo);
1555 * reconsider_outer_join_clauses for a single LEFT/RIGHT JOIN clause
1557 * Returns TRUE if we were able to propagate a constant through the clause.
1560 reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
1570 Relids inner_relids,
1571 inner_nullable_relids;
1574 Assert(is_opclause(rinfo->clause));
1575 opno = ((OpExpr *) rinfo->clause)->opno;
1576 collation = ((OpExpr *) rinfo->clause)->inputcollid;
1578 /* If clause is outerjoin_delayed, operator must be strict */
1579 if (rinfo->outerjoin_delayed && !op_strict(opno))
1582 /* Extract needed info from the clause */
1583 op_input_types(opno, &left_type, &right_type);
1586 outervar = (Expr *) get_leftop(rinfo->clause);
1587 innervar = (Expr *) get_rightop(rinfo->clause);
1588 inner_datatype = right_type;
1589 inner_relids = rinfo->right_relids;
1593 outervar = (Expr *) get_rightop(rinfo->clause);
1594 innervar = (Expr *) get_leftop(rinfo->clause);
1595 inner_datatype = left_type;
1596 inner_relids = rinfo->left_relids;
1598 inner_nullable_relids = bms_intersect(inner_relids,
1599 rinfo->nullable_relids);
1601 /* Scan EquivalenceClasses for a match to outervar */
1602 foreach(lc1, root->eq_classes)
1604 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1608 /* Ignore EC unless it contains pseudoconstants */
1609 if (!cur_ec->ec_has_const)
1611 /* Never match to a volatile EC */
1612 if (cur_ec->ec_has_volatile)
1614 /* It has to match the outer-join clause as to semantics, too */
1615 if (collation != cur_ec->ec_collation)
1617 if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
1619 /* Does it contain a match to outervar? */
1621 foreach(lc2, cur_ec->ec_members)
1623 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1625 Assert(!cur_em->em_is_child); /* no children yet */
1626 if (equal(outervar, cur_em->em_expr))
1633 continue; /* no match, so ignore this EC */
1636 * Yes it does! Try to generate a clause INNERVAR = CONSTANT for each
1637 * CONSTANT in the EC. Note that we must succeed with at least one
1638 * constant before we can decide to throw away the outer-join clause.
1641 foreach(lc2, cur_ec->ec_members)
1643 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1645 RestrictInfo *newrinfo;
1647 if (!cur_em->em_is_const)
1648 continue; /* ignore non-const members */
1649 eq_op = select_equality_operator(cur_ec,
1651 cur_em->em_datatype);
1652 if (!OidIsValid(eq_op))
1653 continue; /* can't generate equality */
1654 newrinfo = build_implied_join_equality(eq_op,
1655 cur_ec->ec_collation,
1658 bms_copy(inner_relids),
1659 bms_copy(inner_nullable_relids));
1660 if (process_equivalence(root, newrinfo, true))
1665 * If we were able to equate INNERVAR to any constant, report success.
1666 * Otherwise, fall out of the search loop, since we know the OUTERVAR
1667 * appears in at most one EC.
1675 return false; /* failed to make any deduction */
1679 * reconsider_outer_join_clauses for a single FULL JOIN clause
1681 * Returns TRUE if we were able to propagate a constant through the clause.
1684 reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
1694 left_nullable_relids,
1695 right_nullable_relids;
1698 /* Can't use an outerjoin_delayed clause here */
1699 if (rinfo->outerjoin_delayed)
1702 /* Extract needed info from the clause */
1703 Assert(is_opclause(rinfo->clause));
1704 opno = ((OpExpr *) rinfo->clause)->opno;
1705 collation = ((OpExpr *) rinfo->clause)->inputcollid;
1706 op_input_types(opno, &left_type, &right_type);
1707 leftvar = (Expr *) get_leftop(rinfo->clause);
1708 rightvar = (Expr *) get_rightop(rinfo->clause);
1709 left_relids = rinfo->left_relids;
1710 right_relids = rinfo->right_relids;
1711 left_nullable_relids = bms_intersect(left_relids,
1712 rinfo->nullable_relids);
1713 right_nullable_relids = bms_intersect(right_relids,
1714 rinfo->nullable_relids);
1716 foreach(lc1, root->eq_classes)
1718 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1719 EquivalenceMember *coal_em = NULL;
1725 /* Ignore EC unless it contains pseudoconstants */
1726 if (!cur_ec->ec_has_const)
1728 /* Never match to a volatile EC */
1729 if (cur_ec->ec_has_volatile)
1731 /* It has to match the outer-join clause as to semantics, too */
1732 if (collation != cur_ec->ec_collation)
1734 if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
1738 * Does it contain a COALESCE(leftvar, rightvar) construct?
1740 * We can assume the COALESCE() inputs are in the same order as the
1741 * join clause, since both were automatically generated in the cases
1744 * XXX currently this may fail to match in cross-type cases because
1745 * the COALESCE will contain typecast operations while the join clause
1746 * may not (if there is a cross-type mergejoin operator available for
1747 * the two column types). Is it OK to strip implicit coercions from
1748 * the COALESCE arguments?
1751 foreach(lc2, cur_ec->ec_members)
1753 coal_em = (EquivalenceMember *) lfirst(lc2);
1754 Assert(!coal_em->em_is_child); /* no children yet */
1755 if (IsA(coal_em->em_expr, CoalesceExpr))
1757 CoalesceExpr *cexpr = (CoalesceExpr *) coal_em->em_expr;
1761 if (list_length(cexpr->args) != 2)
1763 cfirst = (Node *) linitial(cexpr->args);
1764 csecond = (Node *) lsecond(cexpr->args);
1766 if (equal(leftvar, cfirst) && equal(rightvar, csecond))
1774 continue; /* no match, so ignore this EC */
1777 * Yes it does! Try to generate clauses LEFTVAR = CONSTANT and
1778 * RIGHTVAR = CONSTANT for each CONSTANT in the EC. Note that we must
1779 * succeed with at least one constant for each var before we can
1780 * decide to throw away the outer-join clause.
1782 matchleft = matchright = false;
1783 foreach(lc2, cur_ec->ec_members)
1785 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1787 RestrictInfo *newrinfo;
1789 if (!cur_em->em_is_const)
1790 continue; /* ignore non-const members */
1791 eq_op = select_equality_operator(cur_ec,
1793 cur_em->em_datatype);
1794 if (OidIsValid(eq_op))
1796 newrinfo = build_implied_join_equality(eq_op,
1797 cur_ec->ec_collation,
1800 bms_copy(left_relids),
1801 bms_copy(left_nullable_relids));
1802 if (process_equivalence(root, newrinfo, true))
1805 eq_op = select_equality_operator(cur_ec,
1807 cur_em->em_datatype);
1808 if (OidIsValid(eq_op))
1810 newrinfo = build_implied_join_equality(eq_op,
1811 cur_ec->ec_collation,
1814 bms_copy(right_relids),
1815 bms_copy(right_nullable_relids));
1816 if (process_equivalence(root, newrinfo, true))
1822 * If we were able to equate both vars to constants, we're done, and
1823 * we can throw away the full-join clause as redundant. Moreover, we
1824 * can remove the COALESCE entry from the EC, since the added
1825 * restrictions ensure it will always have the expected value. (We
1826 * don't bother trying to update ec_relids or ec_sources.)
1828 if (matchleft && matchright)
1830 cur_ec->ec_members = list_delete_ptr(cur_ec->ec_members, coal_em);
1835 * Otherwise, fall out of the search loop, since we know the COALESCE
1836 * appears in at most one EC (XXX might stop being true if we allow
1837 * stripping of coercions above?)
1842 return false; /* failed to make any deduction */
1848 * Detect whether two expressions are known equal due to equivalence
1851 * Actually, this only shows that the expressions are equal according
1852 * to some opfamily's notion of equality --- but we only use it for
1853 * selectivity estimation, so a fuzzy idea of equality is OK.
1855 * Note: does not bother to check for "equal(item1, item2)"; caller must
1856 * check that case if it's possible to pass identical items.
1859 exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
1863 foreach(lc1, root->eq_classes)
1865 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
1866 bool item1member = false;
1867 bool item2member = false;
1870 /* Never match to a volatile EC */
1871 if (ec->ec_has_volatile)
1874 foreach(lc2, ec->ec_members)
1876 EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
1878 if (em->em_is_child)
1879 continue; /* ignore children here */
1880 if (equal(item1, em->em_expr))
1882 else if (equal(item2, em->em_expr))
1884 /* Exit as soon as equality is proven */
1885 if (item1member && item2member)
1894 * add_child_rel_equivalences
1895 * Search for EC members that reference the parent_rel, and
1896 * add transformed members referencing the child_rel.
1898 * Note that this function won't be called at all unless we have at least some
1899 * reason to believe that the EC members it generates will be useful.
1901 * parent_rel and child_rel could be derived from appinfo, but since the
1902 * caller has already computed them, we might as well just pass them in.
1905 add_child_rel_equivalences(PlannerInfo *root,
1906 AppendRelInfo *appinfo,
1907 RelOptInfo *parent_rel,
1908 RelOptInfo *child_rel)
1912 foreach(lc1, root->eq_classes)
1914 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
1918 * If this EC contains a volatile expression, then generating child
1919 * EMs would be downright dangerous, so skip it. We rely on a
1920 * volatile EC having only one EM.
1922 if (cur_ec->ec_has_volatile)
1925 /* No point in searching if parent rel not mentioned in eclass */
1926 if (!bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
1929 foreach(lc2, cur_ec->ec_members)
1931 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
1933 if (cur_em->em_is_const || cur_em->em_is_child)
1934 continue; /* ignore consts and children here */
1936 /* Does it reference parent_rel? */
1937 if (bms_overlap(cur_em->em_relids, parent_rel->relids))
1939 /* Yes, generate transformed child version */
1942 Relids new_nullable_relids;
1944 child_expr = (Expr *)
1945 adjust_appendrel_attrs(root,
1946 (Node *) cur_em->em_expr,
1950 * Transform em_relids to match. Note we do *not* do
1951 * pull_varnos(child_expr) here, as for example the
1952 * transformation might have substituted a constant, but we
1953 * don't want the child member to be marked as constant.
1955 new_relids = bms_difference(cur_em->em_relids,
1956 parent_rel->relids);
1957 new_relids = bms_add_members(new_relids, child_rel->relids);
1960 * And likewise for nullable_relids. Note this code assumes
1961 * parent and child relids are singletons.
1963 new_nullable_relids = cur_em->em_nullable_relids;
1964 if (bms_overlap(new_nullable_relids, parent_rel->relids))
1966 new_nullable_relids = bms_difference(new_nullable_relids,
1967 parent_rel->relids);
1968 new_nullable_relids = bms_add_members(new_nullable_relids,
1972 (void) add_eq_member(cur_ec, child_expr,
1973 new_relids, new_nullable_relids,
1974 true, cur_em->em_datatype);
1982 * mutate_eclass_expressions
1983 * Apply an expression tree mutator to all expressions stored in
1984 * equivalence classes (but ignore child exprs unless include_child_exprs).
1986 * This is a bit of a hack ... it's currently needed only by planagg.c,
1987 * which needs to do a global search-and-replace of MIN/MAX Aggrefs
1988 * after eclasses are already set up. Without changing the eclasses too,
1989 * subsequent matching of ORDER BY and DISTINCT clauses would fail.
1991 * Note that we assume the mutation won't affect relation membership or any
1992 * other properties we keep track of (which is a bit bogus, but by the time
1993 * planagg.c runs, it no longer matters). Also we must be called in the
1994 * main planner memory context.
1997 mutate_eclass_expressions(PlannerInfo *root,
1998 Node *(*mutator) (),
2000 bool include_child_exprs)
2004 foreach(lc1, root->eq_classes)
2006 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2009 foreach(lc2, cur_ec->ec_members)
2011 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2013 if (cur_em->em_is_child && !include_child_exprs)
2014 continue; /* ignore children unless requested */
2016 cur_em->em_expr = (Expr *)
2017 mutator((Node *) cur_em->em_expr, context);
2024 * generate_implied_equalities_for_column
2025 * Create EC-derived joinclauses usable with a specific column.
2027 * This is used by indxpath.c to extract potentially indexable joinclauses
2028 * from ECs, and can be used by foreign data wrappers for similar purposes.
2029 * We assume that only expressions in Vars of a single table are of interest,
2030 * but the caller provides a callback function to identify exactly which
2031 * such expressions it would like to know about.
2033 * We assume that any given table/index column could appear in only one EC.
2034 * (This should be true in all but the most pathological cases, and if it
2035 * isn't, we stop on the first match anyway.) Therefore, what we return
2036 * is a redundant list of clauses equating the table/index column to each of
2037 * the other-relation values it is known to be equal to. Any one of
2038 * these clauses can be used to create a parameterized path, and there
2039 * is no value in using more than one. (But it *is* worthwhile to create
2040 * a separate parameterized path for each one, since that leads to different
2043 * The caller can pass a Relids set of rels we aren't interested in joining
2044 * to, so as to save the work of creating useless clauses.
2047 generate_implied_equalities_for_column(PlannerInfo *root,
2049 ec_matches_callback_type callback,
2051 Relids prohibited_rels)
2054 bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2058 /* If it's a child rel, we'll need to know what its parent is */
2060 parent_relid = find_childrel_appendrelinfo(root, rel)->parent_relid;
2062 parent_relid = 0; /* not used, but keep compiler quiet */
2064 foreach(lc1, root->eq_classes)
2066 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
2067 EquivalenceMember *cur_em;
2071 * Won't generate joinclauses if const or single-member (the latter
2072 * test covers the volatile case too)
2074 if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2078 * No point in searching if rel not mentioned in eclass (but we can't
2079 * tell that for a child rel).
2081 if (!is_child_rel &&
2082 !bms_is_subset(rel->relids, cur_ec->ec_relids))
2086 * Scan members, looking for a match to the target column. Note that
2087 * child EC members are considered, but only when they belong to the
2088 * target relation. (Unlike regular members, the same expression
2089 * could be a child member of more than one EC. Therefore, it's
2090 * potentially order-dependent which EC a child relation's target
2091 * column gets matched to. This is annoying but it only happens in
2092 * corner cases, so for now we live with just reporting the first
2093 * match. See also get_eclass_for_sort_expr.)
2096 foreach(lc2, cur_ec->ec_members)
2098 cur_em = (EquivalenceMember *) lfirst(lc2);
2099 if (bms_equal(cur_em->em_relids, rel->relids) &&
2100 callback(root, rel, cur_ec, cur_em, callback_arg))
2109 * Found our match. Scan the other EC members and attempt to generate
2112 foreach(lc2, cur_ec->ec_members)
2114 EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2116 RestrictInfo *rinfo;
2118 if (other_em->em_is_child)
2119 continue; /* ignore children here */
2121 /* Make sure it'll be a join to a different rel */
2122 if (other_em == cur_em ||
2123 bms_overlap(other_em->em_relids, rel->relids))
2126 /* Forget it if caller doesn't want joins to this rel */
2127 if (bms_overlap(other_em->em_relids, prohibited_rels))
2131 * Also, if this is a child rel, avoid generating a useless join
2132 * to its parent rel.
2135 bms_is_member(parent_relid, other_em->em_relids))
2138 eq_op = select_equality_operator(cur_ec,
2139 cur_em->em_datatype,
2140 other_em->em_datatype);
2141 if (!OidIsValid(eq_op))
2144 /* set parent_ec to mark as redundant with other joinclauses */
2145 rinfo = create_join_clause(root, cur_ec, eq_op,
2149 result = lappend(result, rinfo);
2153 * If somehow we failed to create any join clauses, we might as well
2154 * keep scanning the ECs for another match. But if we did make any,
2155 * we're done, because we don't want to return non-redundant clauses.
2165 * have_relevant_eclass_joinclause
2166 * Detect whether there is an EquivalenceClass that could produce
2167 * a joinclause involving the two given relations.
2169 * This is essentially a very cut-down version of
2170 * generate_join_implied_equalities(). Note it's OK to occasionally say "yes"
2171 * incorrectly. Hence we don't bother with details like whether the lack of a
2172 * cross-type operator might prevent the clause from actually being generated.
2175 have_relevant_eclass_joinclause(PlannerInfo *root,
2176 RelOptInfo *rel1, RelOptInfo *rel2)
2180 foreach(lc1, root->eq_classes)
2182 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2185 * Won't generate joinclauses if single-member (this test covers the
2186 * volatile case too)
2188 if (list_length(ec->ec_members) <= 1)
2192 * We do not need to examine the individual members of the EC, because
2193 * all that we care about is whether each rel overlaps the relids of
2194 * at least one member, and a test on ec_relids is sufficient to prove
2195 * that. (As with have_relevant_joinclause(), it is not necessary
2196 * that the EC be able to form a joinclause relating exactly the two
2197 * given rels, only that it be able to form a joinclause mentioning
2198 * both, and this will surely be true if both of them overlap
2201 * Note we don't test ec_broken; if we did, we'd need a separate code
2202 * path to look through ec_sources. Checking the membership anyway is
2203 * OK as a possibly-overoptimistic heuristic.
2205 * We don't test ec_has_const either, even though a const eclass won't
2206 * generate real join clauses. This is because if we had "WHERE a.x =
2207 * b.y and a.x = 42", it is worth considering a join between a and b,
2208 * since the join result is likely to be small even though it'll end
2209 * up being an unqualified nestloop.
2211 if (bms_overlap(rel1->relids, ec->ec_relids) &&
2212 bms_overlap(rel2->relids, ec->ec_relids))
2221 * has_relevant_eclass_joinclause
2222 * Detect whether there is an EquivalenceClass that could produce
2223 * a joinclause involving the given relation and anything else.
2225 * This is the same as have_relevant_eclass_joinclause with the other rel
2226 * implicitly defined as "everything else in the query".
2229 has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
2233 foreach(lc1, root->eq_classes)
2235 EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2238 * Won't generate joinclauses if single-member (this test covers the
2239 * volatile case too)
2241 if (list_length(ec->ec_members) <= 1)
2245 * Per the comment in have_relevant_eclass_joinclause, it's sufficient
2246 * to find an EC that mentions both this rel and some other rel.
2248 if (bms_overlap(rel1->relids, ec->ec_relids) &&
2249 !bms_is_subset(ec->ec_relids, rel1->relids))
2258 * eclass_useful_for_merging
2259 * Detect whether the EC could produce any mergejoinable join clauses
2260 * against the specified relation.
2262 * This is just a heuristic test and doesn't have to be exact; it's better
2263 * to say "yes" incorrectly than "no". Hence we don't bother with details
2264 * like whether the lack of a cross-type operator might prevent the clause
2265 * from actually being generated.
2268 eclass_useful_for_merging(EquivalenceClass *eclass,
2273 Assert(!eclass->ec_merged);
2276 * Won't generate joinclauses if const or single-member (the latter test
2277 * covers the volatile case too)
2279 if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
2283 * Note we don't test ec_broken; if we did, we'd need a separate code path
2284 * to look through ec_sources. Checking the members anyway is OK as a
2285 * possibly-overoptimistic heuristic.
2288 /* If rel already includes all members of eclass, no point in searching */
2289 if (bms_is_subset(eclass->ec_relids, rel->relids))
2292 /* To join, we need a member not in the given rel */
2293 foreach(lc, eclass->ec_members)
2295 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
2297 if (cur_em->em_is_child)
2298 continue; /* ignore children here */
2300 if (!bms_overlap(cur_em->em_relids, rel->relids))
2309 * is_redundant_derived_clause
2310 * Test whether rinfo is derived from same EC as any clause in clauselist;
2311 * if so, it can be presumed to represent a condition that's redundant
2312 * with that member of the list.
2315 is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist)
2317 EquivalenceClass *parent_ec = rinfo->parent_ec;
2320 /* Fail if it's not a potentially-redundant clause from some EC */
2321 if (parent_ec == NULL)
2324 foreach(lc, clauselist)
2326 RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
2328 if (otherrinfo->parent_ec == parent_ec)