| blob | 13400af3ef53938dc6cd974046beb88c132bf263 |
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-2024, 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 */
19 #include <limits.h>
40 Oid datatype);
50 Relids join_relids,
51 Relids outer_relids,
52 Relids inner_relids);
55 Relids nominal_join_relids,
56 Relids outer_relids,
57 Relids nominal_inner_relids,
73 Relids relids);
75 Relids relids2);
78 /*
79 * process_equivalence
80 * The given clause has a mergejoinable operator and is not an outer-join
81 * qualification, so its two sides can be considered equal
82 * anywhere they are both computable; moreover that equality can be
83 * extended transitively. Record this knowledge in the EquivalenceClass
84 * data structure, if applicable. Returns true if successful, false if not
85 * (in which case caller should treat the clause as ordinary, not an
86 * equivalence).
87 *
88 * In some cases, although we cannot convert a clause into EquivalenceClass
89 * knowledge, we can still modify it to a more useful form than the original.
90 * Then, *p_restrictinfo will be replaced by a new RestrictInfo, which is what
91 * the caller should use for further processing.
92 *
93 * jdomain is the join domain within which the given clause was found.
94 * This limits the applicability of deductions from the EquivalenceClass,
95 * as described in optimizer/README.
96 *
97 * We reject proposed equivalence clauses if they contain leaky functions
98 * and have security_level above zero. The EC evaluation rules require us to
99 * apply certain tests at certain joining levels, and we can't tolerate
100 * delaying any test on security_level grounds. By rejecting candidate clauses
101 * that might require security delays, we ensure it's safe to apply an EC
102 * clause as soon as it's supposed to be applied.
103 *
104 * On success return, we have also initialized the clause's left_ec/right_ec
105 * fields to point to the EquivalenceClass representing it. This saves lookup
106 * effort later.
107 *
108 * Note: constructing merged EquivalenceClasses is a standard UNION-FIND
109 * problem, for which there exist better data structures than simple lists.
110 * If this code ever proves to be a bottleneck then it could be sped up ---
111 * but for now, simple is beautiful.
112 *
113 * Note: this is only called during planner startup, not during GEQO
114 * exploration, so we need not worry about whether we're in the right
115 * memory context.
116 */
117 bool
121 {
124 Oid opno,
125 collation,
126 item1_type,
127 item2_type;
130 Relids item1_relids,
131 item2_relids;
140 /* Should not already be marked as having generated an eclass */
144 /* Reject if it is potentially postponable by security considerations */
148 /* Extract info from given clause */
157 /*
158 * Ensure both input expressions expose the desired collation (their types
159 * should be OK already); see comments for canonicalize_ec_expression.
160 */
163 collation);
166 collation);
168 /*
169 * Clauses of the form X=X cannot be translated into EquivalenceClasses.
170 * We'd either end up with a single-entry EC, losing the knowledge that
171 * the clause was present at all, or else make an EC with duplicate
172 * entries, causing other issues.
173 */
175 {
176 /*
177 * If the operator is strict, then the clause can be treated as just
178 * "X IS NOT NULL". (Since we know we are considering a top-level
179 * qual, we can ignore the difference between FALSE and NULL results.)
180 * It's worth making the conversion because we'll typically get a much
181 * better selectivity estimate than we would for X=X.
182 *
183 * If the operator is not strict, we can't be sure what it will do
184 * with NULLs, so don't attempt to optimize it.
185 */
188 {
204 NULL,
207 }
209 }
211 /*
212 * We use the declared input types of the operator, not exprType() of the
213 * inputs, as the nominal datatypes for opfamily lookup. This presumes
214 * that btree operators are always registered with amoplefttype and
215 * amoprighttype equal to their declared input types. We will need this
216 * info anyway to build EquivalenceMember nodes, and by extracting it now
217 * we can use type comparisons to short-circuit some equal() tests.
218 */
223 /*
224 * Sweep through the existing EquivalenceClasses looking for matches to
225 * item1 and item2. These are the possible outcomes:
226 *
227 * 1. We find both in the same EC. The equivalence is already known, so
228 * there's nothing to do.
229 *
230 * 2. We find both in different ECs. Merge the two ECs together.
231 *
232 * 3. We find just one. Add the other to its EC.
233 *
234 * 4. We find neither. Make a new, two-entry EC.
235 *
236 * Note: since all ECs are built through this process or the similar
237 * search in get_eclass_for_sort_expr(), it's impossible that we'd match
238 * an item in more than one existing nonvolatile EC. So it's okay to stop
239 * at the first match.
240 */
245 {
249 /* Never match to a volatile EC */
253 /*
254 * The collation has to match; check this first since it's cheaper
255 * than the opfamily comparison.
256 */
260 /*
261 * A "match" requires matching sets of btree opfamilies. Use of
262 * equal() for this test has implications discussed in the comments
263 * for get_mergejoin_opfamilies().
264 */
269 {
274 /*
275 * Match constants only within the same JoinDomain (see
276 * optimizer/README).
277 */
284 {
289 }
294 {
300 }
301 }
305 }
307 /* Sweep finished, what did we find? */
310 {
311 /* If case 1, nothing to do, except add to sources */
313 {
319 /* mark the RI as associated with this eclass */
322 /* mark the RI as usable with this pair of EMs */
326 }
328 /*
329 * Case 2: need to merge ec1 and ec2. This should never happen after
330 * the ECs have reached canonical state; otherwise, pathkeys could be
331 * rendered non-canonical by the merge, and relation eclass indexes
332 * would get broken by removal of an eq_classes list entry.
333 */
337 /*
338 * We add ec2's items to ec1, then set ec2's ec_merged link to point
339 * to ec1 and remove ec2 from the eq_classes list. We cannot simply
340 * delete ec2 because that could leave dangling pointers in existing
341 * PathKeys. We leave it behind with a link so that the merged EC can
342 * be found.
343 */
349 /* can't need to set has_volatile */
356 /* just to avoid debugging confusion w/ dangling pointers: */
366 /* mark the RI as associated with this eclass */
369 /* mark the RI as usable with this pair of EMs */
372 }
374 {
375 /* Case 3: add item2 to ec1 */
383 /* mark the RI as associated with this eclass */
386 /* mark the RI as usable with this pair of EMs */
389 }
391 {
392 /* Case 3: add item1 to ec2 */
400 /* mark the RI as associated with this eclass */
403 /* mark the RI as usable with this pair of EMs */
406 }
407 else
408 {
409 /* Case 4: make a new, two-entry EC */
432 /* mark the RI as associated with this eclass */
435 /* mark the RI as usable with this pair of EMs */
438 }
441 }
443 /*
444 * canonicalize_ec_expression
445 *
446 * This function ensures that the expression exposes the expected type and
447 * collation, so that it will be equal() to other equivalence-class expressions
448 * that it ought to be equal() to.
449 *
450 * The rule for datatypes is that the exposed type should match what it would
451 * be for an input to an operator of the EC's opfamilies; which is usually
452 * the declared input type of the operator, but in the case of polymorphic
453 * operators no relabeling is wanted (compare the behavior of parse_coerce.c).
454 * Expressions coming in from quals will generally have the right type
455 * already, but expressions coming from indexkeys may not (because they are
456 * represented without any explicit relabel in pg_index), and the same problem
457 * occurs for sort expressions (because the parser is likewise cavalier about
458 * putting relabels on them). Such cases will be binary-compatible with the
459 * real operators, so adding a RelabelType is sufficient.
460 *
461 * Also, the expression's exposed collation must match the EC's collation.
462 * This is important because in comparisons like "foo < bar COLLATE baz",
463 * only one of the expressions has the correct exposed collation as we receive
464 * it from the parser. Forcing both of them to have it ensures that all
465 * variant spellings of such a construct behave the same. Again, we can
466 * stick on a RelabelType to force the right exposed collation. (It might
467 * work to not label the collation at all in EC members, but this is risky
468 * since some parts of the system expect exprCollation() to deliver the
469 * right answer for a sort key.)
470 */
471 Expr *
473 {
476 /*
477 * For a polymorphic-input-type opclass, just keep the same exposed type.
478 * RECORD opclasses work like polymorphic-type ones for this purpose.
479 */
483 /*
484 * No work if the expression exposes the right type/collation already.
485 */
488 {
489 /*
490 * If we have to change the type of the expression, set typmod to -1,
491 * since the new type may not have the same typmod interpretation.
492 * When we only have to change collation, preserve the exposed typmod.
493 */
494 int32 req_typmod;
498 else
501 /*
502 * Use applyRelabelType so that we preserve const-flatness. This is
503 * important since eval_const_expressions has already been applied.
504 */
508 }
511 }
513 /*
514 * add_eq_member - build a new EquivalenceMember and add it to an EC
515 */
519 {
531 {
532 /*
533 * No Vars, assume it's a pseudoconstant. This is correct for entries
534 * generated from process_equivalence(), because a WHERE clause can't
535 * contain aggregates or SRFs, and non-volatility was checked before
536 * process_equivalence() ever got called. But
537 * get_eclass_for_sort_expr() has to work harder. We put the tests
538 * there not here to save cycles in the equivalence case.
539 */
543 /* it can't affect ec_relids */
544 }
546 {
548 }
552 }
555 /*
556 * get_eclass_for_sort_expr
557 * Given an expression and opfamily/collation info, find an existing
558 * equivalence class it is a member of; if none, optionally build a new
559 * single-member EquivalenceClass for it.
560 *
561 * sortref is the SortGroupRef of the originating SortGroupClause, if any,
562 * or zero if not. (It should never be zero if the expression is volatile!)
563 *
564 * If rel is not NULL, it identifies a specific relation we're considering
565 * a path for, and indicates that child EC members for that relation can be
566 * considered. Otherwise child members are ignored. (Note: since child EC
567 * members aren't guaranteed unique, a non-NULL value means that there could
568 * be more than one EC that matches the expression; if so it's order-dependent
569 * which one you get. This is annoying but it only happens in corner cases,
570 * so for now we live with just reporting the first match. See also
571 * generate_implied_equalities_for_column and match_pathkeys_to_index.)
572 *
573 * If create_it is true, we'll build a new EquivalenceClass when there is no
574 * match. If create_it is false, we just return NULL when no match.
575 *
576 * This can be used safely both before and after EquivalenceClass merging;
577 * since it never causes merging it does not invalidate any existing ECs
578 * or PathKeys. However, ECs added after path generation has begun are
579 * of limited usefulness, so usually it's best to create them beforehand.
580 *
581 * Note: opfamilies must be chosen consistently with the way
582 * process_equivalence() would do; that is, generated from a mergejoinable
583 * equality operator. Else we might fail to detect valid equivalences,
584 * generating poor (but not incorrect) plans.
585 */
586 EquivalenceClass *
590 Oid opcintype,
591 Oid collation,
592 Index sortref,
593 Relids rel,
595 {
597 Relids expr_relids;
601 MemoryContext oldcontext;
603 /*
604 * Ensure the expression exposes the correct type and collation.
605 */
608 /*
609 * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
610 * BY, etc), they can be presumed to belong to the top JoinDomain.
611 */
614 /*
615 * Scan through the existing EquivalenceClasses for a match
616 */
618 {
622 /*
623 * Never match to a volatile EC, except when we are looking at another
624 * reference to the same volatile SortGroupClause.
625 */
636 {
639 /*
640 * Ignore child members unless they match the request.
641 */
646 /*
647 * Match constants only within the same JoinDomain (see
648 * optimizer/README).
649 */
655 {
656 /*
657 * Match!
658 *
659 * Copy the sortref if it wasn't set yet. That may happen if
660 * the ec was constructed from a WHERE clause, i.e. it doesn't
661 * have a target reference at all.
662 */
666 }
667 }
668 }
670 /* No match; does caller want a NULL result? */
674 /*
675 * OK, build a new single-member EC
676 *
677 * Here, we must be sure that we construct the EC in the right context.
678 */
699 /*
700 * Get the precise set of relids appearing in the expression.
701 */
707 /*
708 * add_eq_member doesn't check for volatile functions, set-returning
709 * functions, aggregates, or window functions, but such could appear in
710 * sort expressions; so we have to check whether its const-marking was
711 * correct.
712 */
714 {
719 {
722 }
723 }
727 /*
728 * If EC merging is already complete, we have to mop up by adding the new
729 * EC to the eclass_indexes of the relation(s) mentioned in it.
730 */
732 {
737 {
741 {
744 }
749 ec_index);
750 }
751 }
756 }
758 /*
759 * find_ec_member_matching_expr
760 * Locate an EquivalenceClass member matching the given expr, if any;
761 * return NULL if no match.
762 *
763 * "Matching" is defined as "equal after stripping RelabelTypes".
764 * This is used for identifying sort expressions, and we need to allow
765 * binary-compatible relabeling for some cases involving binary-compatible
766 * sort operators.
767 *
768 * Child EC members are ignored unless they belong to given 'relids'.
769 */
770 EquivalenceMember *
773 Relids relids)
774 {
777 /* We ignore binary-compatible relabeling on both ends */
782 {
786 /*
787 * We shouldn't be trying to sort by an equivalence class that
788 * contains a constant, so no need to consider such cases any further.
789 */
793 /*
794 * Ignore child members unless they belong to the requested rel.
795 */
800 /*
801 * Match if same expression (after stripping relabel).
802 */
809 }
812 }
814 /*
815 * find_computable_ec_member
816 * Locate an EquivalenceClass member that can be computed from the
817 * expressions appearing in "exprs"; return NULL if no match.
818 *
819 * "exprs" can be either a list of bare expression trees, or a list of
820 * TargetEntry nodes. Either way, it should contain Vars and possibly
821 * Aggrefs and WindowFuncs, which are matched to the corresponding elements
822 * of the EquivalenceClass's expressions.
823 *
824 * Unlike find_ec_member_matching_expr, there's no special provision here
825 * for binary-compatible relabeling. This is intentional: if we have to
826 * compute an expression in this way, setrefs.c is going to insist on exact
827 * matches of Vars to the source tlist.
828 *
829 * Child EC members are ignored unless they belong to given 'relids'.
830 * Also, non-parallel-safe expressions are ignored if 'require_parallel_safe'.
831 *
832 * Note: some callers pass root == NULL for notational reasons. This is OK
833 * when require_parallel_safe is false.
834 */
835 EquivalenceMember *
839 Relids relids,
841 {
845 {
850 /*
851 * We shouldn't be trying to sort by an equivalence class that
852 * contains a constant, so no need to consider such cases any further.
853 */
857 /*
858 * Ignore child members unless they belong to the requested rel.
859 */
864 /*
865 * Match if all Vars and quasi-Vars are available in "exprs".
866 */
868 PVC_INCLUDE_AGGREGATES |
869 PVC_INCLUDE_WINDOWFUNCS |
870 PVC_INCLUDE_PLACEHOLDERS);
872 {
875 }
880 /*
881 * If requested, reject expressions that are not parallel-safe. We
882 * check this last because it's a rather expensive test.
883 */
889 }
892 }
894 /*
895 * is_exprlist_member
896 * Subroutine for find_computable_ec_member: is "node" in "exprs"?
897 *
898 * Per the requirements of that function, "exprs" might or might not have
899 * TargetEntry superstructure.
900 */
901 static bool
903 {
907 {
915 }
917 }
919 /*
920 * relation_can_be_sorted_early
921 * Can this relation be sorted on this EC before the final output step?
922 *
923 * To succeed, we must find an EC member that prepare_sort_from_pathkeys knows
924 * how to sort on, given the rel's reltarget as input. There are also a few
925 * additional constraints based on the fact that the desired sort will be done
926 * "early", within the scan/join part of the plan. Also, non-parallel-safe
927 * expressions are ignored if 'require_parallel_safe'.
928 *
929 * At some point we might want to return the identified EquivalenceMember,
930 * but for now, callers only want to know if there is one.
931 */
932 bool
935 {
940 /*
941 * Reject volatile ECs immediately; such sorts must always be postponed.
942 */
946 /*
947 * Try to find an EM directly matching some reltarget member.
948 */
950 {
957 /*
958 * Reject expressions involving set-returning functions, as those
959 * can't be computed early either. (Note: this test and the following
960 * one are effectively checking properties of targetexpr, so there's
961 * no point in asking whether some other EC member would be better.)
962 */
966 /*
967 * If requested, reject expressions that are not parallel-safe. We
968 * check this last because it's a rather expensive test.
969 */
975 }
977 /*
978 * Try to find an expression computable from the reltarget.
979 */
981 require_parallel_safe);
985 /*
986 * Reject expressions involving set-returning functions, as those can't be
987 * computed early either. (There's no point in looking for another EC
988 * member in this case; since SRFs can't appear in WHERE, they cannot
989 * belong to multi-member ECs.)
990 */
995 }
997 /*
998 * generate_base_implied_equalities
999 * Generate any restriction clauses that we can deduce from equivalence
1000 * classes.
1001 *
1002 * When an EC contains pseudoconstants, our strategy is to generate
1003 * "member = const1" clauses where const1 is the first constant member, for
1004 * every other member (including other constants). If we are able to do this
1005 * then we don't need any "var = var" comparisons because we've successfully
1006 * constrained all the vars at their points of creation. If we fail to
1007 * generate any of these clauses due to lack of cross-type operators, we fall
1008 * back to the "ec_broken" strategy described below. (XXX if there are
1009 * multiple constants of different types, it's possible that we might succeed
1010 * in forming all the required clauses if we started from a different const
1011 * member; but this seems a sufficiently hokey corner case to not be worth
1012 * spending lots of cycles on.)
1013 *
1014 * For ECs that contain no pseudoconstants, we generate derived clauses
1015 * "member1 = member2" for each pair of members belonging to the same base
1016 * relation (actually, if there are more than two for the same base relation,
1017 * we only need enough clauses to link each to each other). This provides
1018 * the base case for the recursion: each row emitted by a base relation scan
1019 * will constrain all computable members of the EC to be equal. As each
1020 * join path is formed, we'll add additional derived clauses on-the-fly
1021 * to maintain this invariant (see generate_join_implied_equalities).
1022 *
1023 * If the opfamilies used by the EC do not provide complete sets of cross-type
1024 * equality operators, it is possible that we will fail to generate a clause
1025 * that must be generated to maintain the invariant. (An example: given
1026 * "WHERE a.x = b.y AND b.y = a.z", the scheme breaks down if we cannot
1027 * generate "a.x = a.z" as a restriction clause for A.) In this case we mark
1028 * the EC "ec_broken" and fall back to regurgitating its original source
1029 * RestrictInfos at appropriate times. We do not try to retract any derived
1030 * clauses already generated from the broken EC, so the resulting plan could
1031 * be poor due to bad selectivity estimates caused by redundant clauses. But
1032 * the correct solution to that is to fix the opfamilies ...
1033 *
1034 * Equality clauses derived by this function are passed off to
1035 * process_implied_equality (in plan/initsplan.c) to be inserted into the
1036 * restrictinfo datastructures. Note that this must be called after initial
1037 * scanning of the quals and before Path construction begins.
1038 *
1039 * We make no attempt to avoid generating duplicate RestrictInfos here: we
1040 * don't search ec_sources or ec_derives for matches. It doesn't really
1041 * seem worth the trouble to do so.
1042 */
1043 void
1045 {
1049 /*
1050 * At this point, we're done absorbing knowledge of equivalences in the
1051 * query, so no further EC merging should happen, and ECs remaining in the
1052 * eq_classes list can be considered canonical. (But note that it's still
1053 * possible for new single-member ECs to be added through
1054 * get_eclass_for_sort_expr().)
1055 */
1060 {
1068 /*
1069 * Generate implied equalities that are restriction clauses.
1070 * Single-member ECs won't generate any deductions, either here or at
1071 * the join level.
1072 */
1074 {
1077 else
1080 /* Recover if we failed to generate required derived clauses */
1084 /* Detect whether this EC might generate join clauses */
1085 can_generate_joinclause =
1087 }
1089 /*
1090 * Mark the base rels cited in each eclass (which should all exist by
1091 * now) with the eq_classes indexes of all eclasses mentioning them.
1092 * This will let us avoid searching in subsequent lookups. While
1093 * we're at it, we can mark base rels that have pending eclass joins;
1094 * this is a cheap version of has_relevant_eclass_joinclause().
1095 */
1098 {
1102 {
1105 }
1110 ec_index);
1114 }
1116 ec_index++;
1117 }
1118 }
1120 /*
1121 * generate_base_implied_equalities when EC contains pseudoconstant(s)
1122 */
1123 static void
1126 {
1130 /*
1131 * In the trivial case where we just had one "var = const" clause, push
1132 * the original clause back into the main planner machinery. There is
1133 * nothing to be gained by doing it differently, and we save the effort to
1134 * re-build and re-analyze an equality clause that will be exactly
1135 * equivalent to the old one.
1136 */
1139 {
1144 }
1146 /*
1147 * Find the constant member to use. We prefer an actual constant to
1148 * pseudo-constants (such as Params), because the constraint exclusion
1149 * machinery might be able to exclude relations on the basis of generated
1150 * "var = const" equalities, but "var = param" won't work for that.
1151 */
1153 {
1157 {
1161 }
1162 }
1165 /* Generate a derived equality against each other member */
1167 {
1169 Oid eq_op;
1179 {
1180 /* failed... */
1183 }
1185 /*
1186 * We use the constant's em_jdomain as qualscope, so that if the
1187 * generated clause is variable-free (i.e, both EMs are consts) it
1188 * will be enforced at the join domain level.
1189 */
1196 /*
1197 * If the clause didn't degenerate to a constant, fill in the correct
1198 * markings for a mergejoinable clause, and save it in ec_derives. (We
1199 * will not re-use such clauses directly, but selectivity estimation
1200 * may consult the list later. Note that this use of ec_derives does
1201 * not overlap with its use for join clauses, since we never generate
1202 * join clauses from an ec_has_const eclass.)
1203 */
1205 {
1206 /* it's not redundant, so don't set parent_ec */
1211 }
1212 }
1213 }
1215 /*
1216 * generate_base_implied_equalities when EC contains no pseudoconstants
1217 */
1218 static void
1221 {
1225 /*
1226 * We scan the EC members once and track the last-seen member for each
1227 * base relation. When we see another member of the same base relation,
1228 * we generate "prev_em = cur_em". This results in the minimum number of
1229 * derived clauses, but it's possible that it will fail when a different
1230 * ordering would succeed. XXX FIXME: use a UNION-FIND algorithm similar
1231 * to the way we build merged ECs. (Use a list-of-lists for each rel.)
1232 */
1237 {
1247 {
1249 Oid eq_op;
1256 {
1257 /* failed... */
1260 }
1262 /*
1263 * The expressions aren't constants, so the passed qualscope will
1264 * never be used to place the generated clause. We just need to
1265 * be sure it covers both expressions, which em_relids should do.
1266 */
1273 /*
1274 * If the clause didn't degenerate to a constant, fill in the
1275 * correct markings for a mergejoinable clause. We don't put it
1276 * in ec_derives however; we don't currently need to re-find such
1277 * clauses, and we don't want to clutter that list with non-join
1278 * clauses.
1279 */
1281 {
1282 /* it's not redundant, so don't set parent_ec */
1286 }
1287 }
1289 }
1293 /*
1294 * We also have to make sure that all the Vars used in the member clauses
1295 * will be available at any join node we might try to reference them at.
1296 * For the moment we force all the Vars to be available at all join nodes
1297 * for this eclass. Perhaps this could be improved by doing some
1298 * pre-analysis of which members we prefer to join, but it's no worse than
1299 * what happened in the pre-8.3 code.
1300 */
1302 {
1305 PVC_RECURSE_AGGREGATES |
1306 PVC_RECURSE_WINDOWFUNCS |
1307 PVC_INCLUDE_PLACEHOLDERS);
1311 }
1312 }
1314 /*
1315 * generate_base_implied_equalities cleanup after failure
1316 *
1317 * What we must do here is push any zero- or one-relation source RestrictInfos
1318 * of the EC back into the main restrictinfo datastructures. Multi-relation
1319 * clauses will be regurgitated later by generate_join_implied_equalities().
1320 * (We do it this way to maintain continuity with the case that ec_broken
1321 * becomes set only after we've gone up a join level or two.) However, for
1322 * an EC that contains constants, we can adopt a simpler strategy and just
1323 * throw back all the source RestrictInfos immediately; that works because
1324 * we know that such an EC can't become broken later. (This rule justifies
1325 * ignoring ec_has_const ECs in generate_join_implied_equalities, even when
1326 * they are broken.)
1327 */
1328 static void
1331 {
1335 {
1341 }
1342 }
1345 /*
1346 * generate_join_implied_equalities
1347 * Generate any join clauses that we can deduce from equivalence classes.
1348 *
1349 * At a join node, we must enforce restriction clauses sufficient to ensure
1350 * that all equivalence-class members computable at that node are equal.
1351 * Since the set of clauses to enforce can vary depending on which subset
1352 * relations are the inputs, we have to compute this afresh for each join
1353 * relation pair. Hence a fresh List of RestrictInfo nodes is built and
1354 * passed back on each call.
1355 *
1356 * In addition to its use at join nodes, this can be applied to generate
1357 * eclass-based join clauses for use in a parameterized scan of a base rel.
1358 * The reason for the asymmetry of specifying the inner rel as a RelOptInfo
1359 * and the outer rel by Relids is that this usage occurs before we have
1360 * built any join RelOptInfos.
1361 *
1362 * An annoying special case for parameterized scans is that the inner rel can
1363 * be an appendrel child (an "other rel"). In this case we must generate
1364 * appropriate clauses using child EC members. add_child_rel_equivalences
1365 * must already have been done for the child rel.
1366 *
1367 * The results are sufficient for use in merge, hash, and plain nestloop join
1368 * methods. We do not worry here about selecting clauses that are optimal
1369 * for use in a parameterized indexscan. indxpath.c makes its own selections
1370 * of clauses to use, and if the ones we pick here are redundant with those,
1371 * the extras will be eliminated at createplan time, using the parent_ec
1372 * markers that we provide (see is_redundant_derived_clause()).
1373 *
1374 * Because the same join clauses are likely to be needed multiple times as
1375 * we consider different join paths, we avoid generating multiple copies:
1376 * whenever we select a particular pair of EquivalenceMembers to join,
1377 * we check to see if the pair matches any original clause (in ec_sources)
1378 * or previously-built clause (in ec_derives). This saves memory and allows
1379 * re-use of information cached in RestrictInfos. We also avoid generating
1380 * commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but
1381 * we already have "b.y = a.x", we return the existing clause.
1382 *
1383 * If we are considering an outer join, sjinfo is the associated OJ info,
1384 * otherwise it can be NULL.
1385 *
1386 * join_relids should always equal bms_union(outer_relids, inner_rel->relids)
1387 * plus whatever add_outer_joins_to_relids() would add. We could simplify
1388 * this function's API by computing it internally, but most callers have the
1389 * value at hand anyway.
1390 */
1391 List *
1393 Relids join_relids,
1394 Relids outer_relids,
1397 {
1400 Relids nominal_inner_relids;
1401 Relids nominal_join_relids;
1405 /* If inner rel is a child, extra setup work is needed */
1407 {
1410 /* Fetch relid set for the topmost parent rel */
1412 /* ECs will be marked with the parent's relid, not the child's */
1415 nominal_join_relids,
1416 sjinfo,
1417 NULL);
1418 }
1419 else
1420 {
1423 }
1425 /*
1426 * Examine all potentially-relevant eclasses.
1427 *
1428 * If we are considering an outer join, we must include "join" clauses
1429 * that mention either input rel plus the outer join's relid; these
1430 * represent post-join filter clauses that have to be applied at this
1431 * join. We don't have infrastructure that would let us identify such
1432 * eclasses cheaply, so just fall back to considering all eclasses
1433 * mentioning anything in nominal_join_relids.
1434 *
1435 * At inner joins, we can be smarter: only consider eclasses mentioning
1436 * both input rels.
1437 */
1440 else
1442 outer_relids);
1446 {
1450 /* ECs containing consts do not need any further enforcement */
1454 /* Single-member ECs won't generate any deductions */
1458 /* Sanity check that this eclass overlaps the join */
1463 ec,
1464 join_relids,
1465 outer_relids,
1466 inner_relids);
1468 /* Recover if we failed to generate required derived clauses */
1471 ec,
1472 nominal_join_relids,
1473 outer_relids,
1474 nominal_inner_relids,
1475 inner_rel);
1478 }
1481 }
1483 /*
1484 * generate_join_implied_equalities_for_ecs
1485 * As above, but consider only the listed ECs.
1486 *
1487 * For the sole current caller, we can assume sjinfo == NULL, that is we are
1488 * not interested in outer-join filter clauses. This might need to change
1489 * in future.
1490 */
1491 List *
1494 Relids join_relids,
1495 Relids outer_relids,
1497 {
1500 Relids nominal_inner_relids;
1501 Relids nominal_join_relids;
1504 /* If inner rel is a child, extra setup work is needed */
1506 {
1509 /* Fetch relid set for the topmost parent rel */
1511 /* ECs will be marked with the parent's relid, not the child's */
1513 }
1514 else
1515 {
1518 }
1521 {
1525 /* ECs containing consts do not need any further enforcement */
1529 /* Single-member ECs won't generate any deductions */
1533 /* We can quickly ignore any that don't overlap the join, too */
1539 ec,
1540 join_relids,
1541 outer_relids,
1542 inner_relids);
1544 /* Recover if we failed to generate required derived clauses */
1547 ec,
1548 nominal_join_relids,
1549 outer_relids,
1550 nominal_inner_relids,
1551 inner_rel);
1554 }
1557 }
1559 /*
1560 * generate_join_implied_equalities for a still-valid EC
1561 */
1565 Relids join_relids,
1566 Relids outer_relids,
1567 Relids inner_relids)
1568 {
1575 /*
1576 * First, scan the EC to identify member values that are computable at the
1577 * outer rel, at the inner rel, or at this relation but not in either
1578 * input rel. The outer-rel members should already be enforced equal,
1579 * likewise for the inner-rel members. We'll need to create clauses to
1580 * enforce that any newly computable members are all equal to each other
1581 * as well as to at least one input member, plus enforce at least one
1582 * outer-rel member equal to at least one inner-rel member.
1583 */
1585 {
1588 /*
1589 * We don't need to check explicitly for child EC members. This test
1590 * against join_relids will cause them to be ignored except when
1591 * considering a child inner rel, which is what we want.
1592 */
1600 else
1602 }
1604 /*
1605 * First, select the joinclause if needed. We can equate any one outer
1606 * member to any one inner member, but we have to find a datatype
1607 * combination for which an opfamily member operator exists. If we have
1608 * choices, we prefer simple Var members (possibly with RelabelType) since
1609 * these are (a) cheapest to compute at runtime and (b) most likely to
1610 * have useful statistics. Also, prefer operators that are also
1611 * hashjoinable.
1612 */
1614 {
1622 {
1627 {
1629 Oid eq_op;
1641 score++;
1645 score++;
1648 score++;
1650 {
1657 }
1658 }
1661 }
1663 {
1664 /* failed... */
1667 }
1669 /*
1670 * Create clause, setting parent_ec to mark it as redundant with other
1671 * joinclauses
1672 */
1675 ec);
1678 }
1680 /*
1681 * Now deal with building restrictions for any expressions that involve
1682 * Vars from both sides of the join. We have to equate all of these to
1683 * each other as well as to at least one old member (if any).
1684 *
1685 * XXX as in generate_base_implied_equalities_no_const, we could be a lot
1686 * smarter here to avoid unnecessary failures in cross-type situations.
1687 * For now, use the same left-to-right method used there.
1688 */
1690 {
1695 /* For now, arbitrarily take the first old_member as the one to use */
1700 {
1704 {
1705 Oid eq_op;
1711 {
1712 /* failed... */
1715 }
1716 /* do NOT set parent_ec, this qual is not redundant! */
1719 NULL);
1722 }
1724 }
1725 }
1728 }
1730 /*
1731 * generate_join_implied_equalities cleanup after failure
1732 *
1733 * Return any original RestrictInfos that are enforceable at this join.
1734 *
1735 * In the case of a child inner relation, we have to translate the
1736 * original RestrictInfos from parent to child Vars.
1737 */
1741 Relids nominal_join_relids,
1742 Relids outer_relids,
1743 Relids nominal_inner_relids,
1745 {
1750 {
1758 }
1760 /*
1761 * If we have to translate, just brute-force apply adjust_appendrel_attrs
1762 * to all the RestrictInfos at once. This will result in returning
1763 * RestrictInfos that are not listed in ec_derives, but there shouldn't be
1764 * any duplication, and it's a sufficiently narrow corner case that we
1765 * shouldn't sweat too much over it anyway.
1766 *
1767 * Since inner_rel might be an indirect descendant of the baserel
1768 * mentioned in the ec_sources clauses, we have to be prepared to apply
1769 * multiple levels of Var translation.
1770 */
1774 inner_rel,
1778 }
1781 /*
1782 * select_equality_operator
1783 * Select a suitable equality operator for comparing two EC members
1784 *
1785 * Returns InvalidOid if no operator can be found for this datatype combination
1786 */
1787 static Oid
1789 {
1793 {
1795 Oid opno;
1798 BTEqualStrategyNumber);
1801 /* If no barrier quals in query, don't worry about leaky operators */
1804 /* Otherwise, insist that selected operators be leakproof */
1807 }
1809 }
1812 /*
1813 * create_join_clause
1814 * Find or make a RestrictInfo comparing the two given EC members
1815 * with the given operator (or, possibly, its commutator, because
1816 * the ordering of the operands in the result is not guaranteed).
1817 *
1818 * parent_ec is either equal to ec (if the clause is a potentially-redundant
1819 * join clause) or NULL (if not). We have to treat this as part of the
1820 * match requirements --- it's possible that a clause comparing the same two
1821 * EMs is a join clause in one join path and a restriction clause in another.
1822 */
1829 {
1833 MemoryContext oldcontext;
1835 /*
1836 * Search to see if we already built a RestrictInfo for this pair of
1837 * EquivalenceMembers. We can use either original source clauses or
1838 * previously-derived clauses, and a commutator clause is acceptable.
1839 *
1840 * We used to verify that opno matches, but that seems redundant: even if
1841 * it's not identical, it'd better have the same effects, or the operator
1842 * families we're using are broken.
1843 */
1845 {
1855 }
1858 {
1868 }
1870 /*
1871 * Not there, so build it, in planner context so we can re-use it. (Not
1872 * important in normal planning, but definitely so in GEQO.)
1873 */
1876 /*
1877 * If either EM is a child, recursively create the corresponding
1878 * parent-to-parent clause, so that we can duplicate its rinfo_serial.
1879 */
1881 {
1887 parent_ec);
1888 }
1891 opno,
1899 /*
1900 * If either EM is a child, force the clause's clause_relids to include
1901 * the relid(s) of the child rel. In normal cases it would already, but
1902 * not if we are considering appendrel child relations with pseudoconstant
1903 * translated variables (i.e., UNION ALL sub-selects with constant output
1904 * items). We must do this so that join_clause_is_movable_into() will
1905 * think that the clause should be evaluated at the correct place.
1906 */
1914 /* If it's a child clause, copy the parent's rinfo_serial */
1918 /* Mark the clause as redundant, or not */
1921 /*
1922 * We know the correct values for left_ec/right_ec, ie this particular EC,
1923 * so we can just set them directly instead of forcing another lookup.
1924 */
1928 /* Mark it as usable with these EMs */
1931 /* and save it for possible re-use */
1937 }
1940 /*
1941 * reconsider_outer_join_clauses
1942 * Re-examine any outer-join clauses that were set aside by
1943 * distribute_qual_to_rels(), and see if we can derive any
1944 * EquivalenceClasses from them. Then, if they were not made
1945 * redundant, push them out into the regular join-clause lists.
1946 *
1947 * When we have mergejoinable clauses A = B that are outer-join clauses,
1948 * we can't blindly combine them with other clauses A = C to deduce B = C,
1949 * since in fact the "equality" A = B won't necessarily hold above the
1950 * outer join (one of the variables might be NULL instead). Nonetheless
1951 * there are cases where we can add qual clauses using transitivity.
1952 *
1953 * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
1954 * for which there is also an equivalence clause OUTERVAR = CONSTANT.
1955 * It is safe and useful to push a clause INNERVAR = CONSTANT into the
1956 * evaluation of the inner (nullable) relation, because any inner rows not
1957 * meeting this condition will not contribute to the outer-join result anyway.
1958 * (Any outer rows they could join to will be eliminated by the pushed-down
1959 * equivalence clause.)
1960 *
1961 * Note that the above rule does not work for full outer joins; nor is it
1962 * very interesting to consider cases where the generated equivalence clause
1963 * would involve relations outside the outer join, since such clauses couldn't
1964 * be pushed into the inner side's scan anyway. So the restriction to
1965 * outervar = pseudoconstant is not really giving up anything.
1966 *
1967 * For full-join cases, we can only do something useful if it's a FULL JOIN
1968 * USING and a merged column has an equivalence MERGEDVAR = CONSTANT.
1969 * By the time it gets here, the merged column will look like
1970 * COALESCE(LEFTVAR, RIGHTVAR)
1971 * and we will have a full-join clause LEFTVAR = RIGHTVAR that we can match
1972 * the COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
1973 * and RIGHTVAR = CONSTANT into the input relations, since any rows not
1974 * meeting these conditions cannot contribute to the join result.
1975 *
1976 * Again, there isn't any traction to be gained by trying to deal with
1977 * clauses comparing a mergedvar to a non-pseudoconstant. So we can make
1978 * use of the EquivalenceClasses to search for matching variables that were
1979 * equivalenced to constants. The interesting outer-join clauses were
1980 * accumulated for us by distribute_qual_to_rels.
1981 *
1982 * When we find one of these cases, we implement the changes we want by
1983 * generating a new equivalence clause INNERVAR = CONSTANT (or LEFTVAR, etc)
1984 * and pushing it into the EquivalenceClass structures. This is because we
1985 * may already know that INNERVAR is equivalenced to some other var(s), and
1986 * we'd like the constant to propagate to them too. Note that it would be
1987 * unsafe to merge any existing EC for INNERVAR with the OUTERVAR's EC ---
1988 * that could result in propagating constant restrictions from
1989 * INNERVAR to OUTERVAR, which would be very wrong.
1990 *
1991 * It's possible that the INNERVAR is also an OUTERVAR for some other
1992 * outer-join clause, in which case the process can be repeated. So we repeat
1993 * looping over the lists of clauses until no further deductions can be made.
1994 * Whenever we do make a deduction, we remove the generating clause from the
1995 * lists, since we don't want to make the same deduction twice.
1996 *
1997 * If we don't find any match for a set-aside outer join clause, we must
1998 * throw it back into the regular joinclause processing by passing it to
1999 * distribute_restrictinfo_to_rels(). If we do generate a derived clause,
2000 * however, the outer-join clause is redundant. We must still put some
2001 * clause into the regular processing, because otherwise the join will be
2002 * seen as a clauseless join and avoided during join order searching.
2003 * We handle this by generating a constant-TRUE clause that is marked with
2004 * the same required_relids etc as the removed outer-join clause, thus
2005 * making it a join clause between the correct relations.
2006 */
2007 void
2009 {
2013 /* Outer loop repeats until we find no more deductions */
2014 do
2015 {
2018 /* Process the LEFT JOIN clauses */
2020 {
2024 {
2028 /* remove it from the list */
2031 /* throw back a dummy replacement clause (see notes above) */
2043 }
2044 }
2046 /* Process the RIGHT JOIN clauses */
2048 {
2052 {
2056 /* remove it from the list */
2059 /* throw back a dummy replacement clause (see notes above) */
2071 }
2072 }
2074 /* Process the FULL JOIN clauses */
2076 {
2080 {
2084 /* remove it from the list */
2087 /* throw back a dummy replacement clause (see notes above) */
2099 }
2100 }
2103 /* Now, any remaining clauses have to be thrown back */
2105 {
2109 }
2111 {
2115 }
2117 {
2121 }
2122 }
2124 /*
2125 * reconsider_outer_join_clauses for a single LEFT/RIGHT JOIN clause
2126 *
2127 * Returns true if we were able to propagate a constant through the clause.
2128 */
2129 static bool
2132 {
2137 Oid opno,
2138 collation,
2139 left_type,
2140 right_type,
2141 inner_datatype;
2142 Relids inner_relids;
2149 /* Extract needed info from the clause */
2152 {
2157 }
2158 else
2159 {
2164 }
2166 /* Scan EquivalenceClasses for a match to outervar */
2168 {
2173 /* Ignore EC unless it contains pseudoconstants */
2176 /* Never match to a volatile EC */
2179 /* It has to match the outer-join clause as to semantics, too */
2184 /* Does it contain a match to outervar? */
2187 {
2192 {
2195 }
2196 }
2200 /*
2201 * Yes it does! Try to generate a clause INNERVAR = CONSTANT for each
2202 * CONSTANT in the EC. Note that we must succeed with at least one
2203 * constant before we can decide to throw away the outer-join clause.
2204 */
2207 {
2209 Oid eq_op;
2216 inner_datatype,
2221 eq_op,
2223 innervar,
2227 /* This equality holds within the OJ's child JoinDomain */
2231 }
2233 /*
2234 * If we were able to equate INNERVAR to any constant, report success.
2235 * Otherwise, fall out of the search loop, since we know the OUTERVAR
2236 * appears in at most one EC.
2237 */
2240 else
2242 }
2245 }
2247 /*
2248 * reconsider_outer_join_clauses for a single FULL JOIN clause
2249 *
2250 * Returns true if we were able to propagate a constant through the clause.
2251 */
2252 static bool
2254 {
2260 Oid opno,
2261 collation,
2262 left_type,
2263 right_type;
2264 Relids left_relids,
2265 right_relids;
2268 /* Extract needed info from the clause */
2279 {
2288 /* Ignore EC unless it contains pseudoconstants */
2291 /* Never match to a volatile EC */
2294 /* It has to match the outer-join clause as to semantics, too */
2300 /*
2301 * Does it contain a COALESCE(leftvar, rightvar) construct?
2302 *
2303 * We can assume the COALESCE() inputs are in the same order as the
2304 * join clause, since both were automatically generated in the cases
2305 * we care about.
2306 *
2307 * XXX currently this may fail to match in cross-type cases because
2308 * the COALESCE will contain typecast operations while the join clause
2309 * may not (if there is a cross-type mergejoin operator available for
2310 * the two column types). Is it OK to strip implicit coercions from
2311 * the COALESCE arguments?
2312 */
2315 {
2319 {
2329 /*
2330 * The COALESCE arguments will be marked as possibly nulled by
2331 * the full join, while we wish to generate clauses that apply
2332 * to the join's inputs. So we must strip the join from the
2333 * nullingrels fields of cfirst/csecond before comparing them
2334 * to leftvar/rightvar. (Perhaps with a less hokey
2335 * representation for FULL JOIN USING output columns, this
2336 * wouldn't be needed?)
2337 */
2342 {
2346 }
2347 }
2348 }
2352 /*
2353 * Yes it does! Try to generate clauses LEFTVAR = CONSTANT and
2354 * RIGHTVAR = CONSTANT for each CONSTANT in the EC. Note that we must
2355 * succeed with at least one constant for each var before we can
2356 * decide to throw away the outer-join clause.
2357 */
2360 {
2362 Oid eq_op;
2369 left_type,
2372 {
2374 eq_op,
2376 leftvar,
2380 /* This equality holds within the lefthand child JoinDomain */
2384 }
2386 right_type,
2389 {
2391 eq_op,
2393 rightvar,
2397 /* This equality holds within the righthand child JoinDomain */
2401 }
2402 }
2404 /*
2405 * If we were able to equate both vars to constants, we're done, and
2406 * we can throw away the full-join clause as redundant. Moreover, we
2407 * can remove the COALESCE entry from the EC, since the added
2408 * restrictions ensure it will always have the expected value. (We
2409 * don't bother trying to update ec_relids or ec_sources.)
2410 */
2412 {
2415 }
2417 /*
2418 * Otherwise, fall out of the search loop, since we know the COALESCE
2419 * appears in at most one EC (XXX might stop being true if we allow
2420 * stripping of coercions above?)
2421 */
2423 }
2426 }
2428 /*
2429 * find_join_domain
2430 * Find the highest JoinDomain enclosed within the given relid set.
2431 *
2432 * (We could avoid this search at the cost of complicating APIs elsewhere,
2433 * which doesn't seem worth it.)
2434 */
2437 {
2441 {
2446 }
2449 }
2452 /*
2453 * exprs_known_equal
2454 * Detect whether two expressions are known equal due to equivalence
2455 * relationships.
2456 *
2457 * Actually, this only shows that the expressions are equal according
2458 * to some opfamily's notion of equality --- but we only use it for
2459 * selectivity estimation, so a fuzzy idea of equality is OK.
2460 *
2461 * Note: does not bother to check for "equal(item1, item2)"; caller must
2462 * check that case if it's possible to pass identical items.
2463 */
2464 bool
2466 {
2470 {
2476 /* Never match to a volatile EC */
2481 {
2490 /* Exit as soon as equality is proven */
2493 }
2494 }
2496 }
2499 /*
2500 * match_eclasses_to_foreign_key_col
2501 * See whether a foreign key column match is proven by any eclass.
2502 *
2503 * If the referenced and referencing Vars of the fkey's colno'th column are
2504 * known equal due to any eclass, return that eclass; otherwise return NULL.
2505 * (In principle there might be more than one matching eclass if multiple
2506 * collations are involved, but since collation doesn't matter for equality,
2507 * we ignore that fine point here.) This is much like exprs_known_equal,
2508 * except that we insist on the comparison operator matching the eclass, so
2509 * that the result is definite not approximate.
2510 *
2511 * On success, we also set fkinfo->eclass[colno] to the matching eclass,
2512 * and set fkinfo->fk_eclass_member[colno] to the eclass member for the
2513 * referencing Var.
2514 */
2515 EquivalenceClass *
2519 {
2531 /* Consider only eclasses mentioning both relations */
2540 {
2542 i);
2547 /* Never match to a volatile EC */
2550 /* Note: it seems okay to match to "broken" eclasses here */
2553 {
2560 /* EM must be a Var, possibly with RelabelType */
2567 /* Match? */
2573 /* Have we found both PK and FK column in this EC? */
2575 {
2576 /*
2577 * Succeed if eqop matches EC's opfamilies. We could test
2578 * this before scanning the members, but it's probably cheaper
2579 * to test for member matches first.
2580 */
2584 {
2588 }
2589 /* Otherwise, done with this EC, move on to the next */
2591 }
2592 }
2593 }
2595 }
2597 /*
2598 * find_derived_clause_for_ec_member
2599 * Search for a previously-derived clause mentioning the given EM.
2600 *
2601 * The eclass should be an ec_has_const EC, of which the EM is a non-const
2602 * member. This should ensure there is just one derived clause mentioning
2603 * the EM (and equating it to a constant).
2604 * Returns NULL if no such clause can be found.
2605 */
2606 RestrictInfo *
2609 {
2615 {
2618 /*
2619 * generate_base_implied_equalities_const will have put non-const
2620 * members on the left side of derived clauses.
2621 */
2624 }
2626 }
2629 /*
2630 * add_child_rel_equivalences
2631 * Search for EC members that reference the root parent of child_rel, and
2632 * add transformed members referencing the child_rel.
2633 *
2634 * Note that this function won't be called at all unless we have at least some
2635 * reason to believe that the EC members it generates will be useful.
2636 *
2637 * parent_rel and child_rel could be derived from appinfo, but since the
2638 * caller has already computed them, we might as well just pass them in.
2639 *
2640 * The passed-in AppendRelInfo is not used when the parent_rel is not a
2641 * top-level baserel, since it shows the mapping from the parent_rel but
2642 * we need to translate EC expressions that refer to the top-level parent.
2643 * Using it is faster than using adjust_appendrel_attrs_multilevel(), though,
2644 * so we prefer it when we can.
2645 */
2646 void
2651 {
2656 /*
2657 * EC merging should be complete already, so we can use the parent rel's
2658 * eclass_indexes to avoid searching all of root->eq_classes.
2659 */
2665 {
2669 /*
2670 * If this EC contains a volatile expression, then generating child
2671 * EMs would be downright dangerous, so skip it. We rely on a
2672 * volatile EC having only one EM.
2673 */
2677 /* Sanity check eclass_indexes only contain ECs for parent_rel */
2680 /*
2681 * We don't use foreach() here because there's no point in scanning
2682 * newly-added child members, so we can stop after the last
2683 * pre-existing EC member.
2684 */
2687 {
2693 /*
2694 * We consider only original EC members here, not
2695 * already-transformed child members. Otherwise, if some original
2696 * member expression references more than one appendrel, we'd get
2697 * an O(N^2) explosion of useless derived expressions for
2698 * combinations of children. (But add_child_join_rel_equivalences
2699 * may add targeted combinations for partitionwise-join purposes.)
2700 */
2704 /*
2705 * Consider only members that reference and can be computed at
2706 * child's topmost parent rel. In particular we want to exclude
2707 * parent-rel Vars that have nonempty varnullingrels. Translating
2708 * those might fail, if the transformed expression wouldn't be a
2709 * simple Var; and in any case it wouldn't produce a member that
2710 * has any use in creating plans for the child rel.
2711 */
2714 {
2715 /* OK, generate transformed child version */
2717 Relids new_relids;
2720 {
2721 /* Simple single-level transformation */
2726 }
2727 else
2728 {
2729 /* Must do multi-level transformation */
2733 child_rel,
2735 }
2737 /*
2738 * Transform em_relids to match. Note we do *not* do
2739 * pull_varnos(child_expr) here, as for example the
2740 * transformation might have substituted a constant, but we
2741 * don't want the child member to be marked as constant.
2742 */
2744 top_parent_relids);
2751 /* Record this EC index for the child rel */
2753 }
2754 }
2755 }
2756 }
2758 /*
2759 * add_child_join_rel_equivalences
2760 * Like add_child_rel_equivalences(), but for joinrels
2761 *
2762 * Here we find the ECs relevant to the top parent joinrel and add transformed
2763 * member expressions that refer to this child joinrel.
2764 *
2765 * Note that this function won't be called at all unless we have at least some
2766 * reason to believe that the EC members it generates will be useful.
2767 */
2768 void
2773 {
2777 MemoryContext oldcontext;
2782 /* We need consider only ECs that mention the parent joinrel */
2785 /*
2786 * If we're being called during GEQO join planning, we still have to
2787 * create any new EC members in the main planner context, to avoid having
2788 * a corrupt EC data structure after the GEQO context is reset. This is
2789 * problematic since we'll leak memory across repeated GEQO cycles. For
2790 * now, though, bloat is better than crash. If it becomes a real issue
2791 * we'll have to do something to avoid generating duplicate EC members.
2792 */
2797 {
2801 /*
2802 * If this EC contains a volatile expression, then generating child
2803 * EMs would be downright dangerous, so skip it. We rely on a
2804 * volatile EC having only one EM.
2805 */
2809 /* Sanity check on get_eclass_indexes_for_relids result */
2812 /*
2813 * We don't use foreach() here because there's no point in scanning
2814 * newly-added child members, so we can stop after the last
2815 * pre-existing EC member.
2816 */
2819 {
2825 /*
2826 * We consider only original EC members here, not
2827 * already-transformed child members.
2828 */
2832 /*
2833 * We may ignore expressions that reference a single baserel,
2834 * because add_child_rel_equivalences should have handled them.
2835 */
2839 /* Does this member reference child's topmost parent rel? */
2841 {
2842 /* Yes, generate transformed child version */
2844 Relids new_relids;
2847 {
2848 /* Simple single-level transformation */
2853 }
2854 else
2855 {
2856 /* Must do multi-level transformation */
2861 child_joinrel,
2863 }
2865 /*
2866 * Transform em_relids to match. Note we do *not* do
2867 * pull_varnos(child_expr) here, as for example the
2868 * transformation might have substituted a constant, but we
2869 * don't want the child member to be marked as constant.
2870 */
2872 top_parent_relids);
2878 }
2879 }
2880 }
2883 }
2886 /*
2887 * generate_implied_equalities_for_column
2888 * Create EC-derived joinclauses usable with a specific column.
2889 *
2890 * This is used by indxpath.c to extract potentially indexable joinclauses
2891 * from ECs, and can be used by foreign data wrappers for similar purposes.
2892 * We assume that only expressions in Vars of a single table are of interest,
2893 * but the caller provides a callback function to identify exactly which
2894 * such expressions it would like to know about.
2895 *
2896 * We assume that any given table/index column could appear in only one EC.
2897 * (This should be true in all but the most pathological cases, and if it
2898 * isn't, we stop on the first match anyway.) Therefore, what we return
2899 * is a redundant list of clauses equating the table/index column to each of
2900 * the other-relation values it is known to be equal to. Any one of
2901 * these clauses can be used to create a parameterized path, and there
2902 * is no value in using more than one. (But it *is* worthwhile to create
2903 * a separate parameterized path for each one, since that leads to different
2904 * join orders.)
2905 *
2906 * The caller can pass a Relids set of rels we aren't interested in joining
2907 * to, so as to save the work of creating useless clauses.
2908 */
2909 List *
2912 ec_matches_callback_type callback,
2914 Relids prohibited_rels)
2915 {
2918 Relids parent_relids;
2921 /* Should be OK to rely on eclass_indexes */
2924 /* Indexes are available only on base or "other" member relations. */
2927 /* If it's a child rel, we'll need to know what its parent(s) are */
2930 else
2935 {
2940 /* Sanity check eclass_indexes only contain ECs for rel */
2943 /*
2944 * Won't generate joinclauses if const or single-member (the latter
2945 * test covers the volatile case too)
2946 */
2950 /*
2951 * Scan members, looking for a match to the target column. Note that
2952 * child EC members are considered, but only when they belong to the
2953 * target relation. (Unlike regular members, the same expression
2954 * could be a child member of more than one EC. Therefore, it's
2955 * potentially order-dependent which EC a child relation's target
2956 * column gets matched to. This is annoying but it only happens in
2957 * corner cases, so for now we live with just reporting the first
2958 * match. See also get_eclass_for_sort_expr.)
2959 */
2962 {
2968 }
2973 /*
2974 * Found our match. Scan the other EC members and attempt to generate
2975 * joinclauses.
2976 */
2978 {
2980 Oid eq_op;
2986 /* Make sure it'll be a join to a different rel */
2991 /* Forget it if caller doesn't want joins to this rel */
2995 /*
2996 * Also, if this is a child rel, avoid generating a useless join
2997 * to its parent rel(s).
2998 */
3009 /* set parent_ec to mark as redundant with other joinclauses */
3012 cur_ec);
3015 }
3017 /*
3018 * If somehow we failed to create any join clauses, we might as well
3019 * keep scanning the ECs for another match. But if we did make any,
3020 * we're done, because we don't want to return non-redundant clauses.
3021 */
3024 }
3027 }
3029 /*
3030 * have_relevant_eclass_joinclause
3031 * Detect whether there is an EquivalenceClass that could produce
3032 * a joinclause involving the two given relations.
3033 *
3034 * This is essentially a very cut-down version of
3035 * generate_join_implied_equalities(). Note it's OK to occasionally say "yes"
3036 * incorrectly. Hence we don't bother with details like whether the lack of a
3037 * cross-type operator might prevent the clause from actually being generated.
3038 * False negatives are not always fatal either: they will discourage, but not
3039 * completely prevent, investigation of particular join pathways.
3040 */
3041 bool
3044 {
3048 /*
3049 * Examine only eclasses mentioning both rel1 and rel2.
3050 *
3051 * Note that we do not consider the possibility of an eclass generating
3052 * "join" clauses that mention just one of the rels plus an outer join
3053 * that could be formed from them. Although such clauses must be
3054 * correctly enforced when we form the outer join, they don't seem like
3055 * sufficient reason to prioritize this join over other ones. The join
3056 * ordering rules will force the join to be made when necessary.
3057 */
3063 {
3065 i);
3067 /*
3068 * Sanity check that get_common_eclass_indexes gave only ECs
3069 * containing both rels.
3070 */
3074 /*
3075 * Won't generate joinclauses if single-member (this test covers the
3076 * volatile case too)
3077 */
3081 /*
3082 * We do not need to examine the individual members of the EC, because
3083 * all that we care about is whether each rel overlaps the relids of
3084 * at least one member, and get_common_eclass_indexes() and the single
3085 * member check above are sufficient to prove that. (As with
3086 * have_relevant_joinclause(), it is not necessary that the EC be able
3087 * to form a joinclause relating exactly the two given rels, only that
3088 * it be able to form a joinclause mentioning both, and this will
3089 * surely be true if both of them overlap ec_relids.)
3090 *
3091 * Note we don't test ec_broken; if we did, we'd need a separate code
3092 * path to look through ec_sources. Checking the membership anyway is
3093 * OK as a possibly-overoptimistic heuristic.
3094 *
3095 * We don't test ec_has_const either, even though a const eclass won't
3096 * generate real join clauses. This is because if we had "WHERE a.x =
3097 * b.y and a.x = 42", it is worth considering a join between a and b,
3098 * since the join result is likely to be small even though it'll end
3099 * up being an unqualified nestloop.
3100 */
3103 }
3106 }
3109 /*
3110 * has_relevant_eclass_joinclause
3111 * Detect whether there is an EquivalenceClass that could produce
3112 * a joinclause involving the given relation and anything else.
3113 *
3114 * This is the same as have_relevant_eclass_joinclause with the other rel
3115 * implicitly defined as "everything else in the query".
3116 */
3117 bool
3119 {
3123 /* Examine only eclasses mentioning rel1 */
3128 {
3130 i);
3132 /*
3133 * Won't generate joinclauses if single-member (this test covers the
3134 * volatile case too)
3135 */
3139 /*
3140 * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3141 * to find an EC that mentions both this rel and some other rel.
3142 */
3145 }
3148 }
3151 /*
3152 * eclass_useful_for_merging
3153 * Detect whether the EC could produce any mergejoinable join clauses
3154 * against the specified relation.
3155 *
3156 * This is just a heuristic test and doesn't have to be exact; it's better
3157 * to say "yes" incorrectly than "no". Hence we don't bother with details
3158 * like whether the lack of a cross-type operator might prevent the clause
3159 * from actually being generated.
3160 */
3161 bool
3165 {
3166 Relids relids;
3171 /*
3172 * Won't generate joinclauses if const or single-member (the latter test
3173 * covers the volatile case too)
3174 */
3178 /*
3179 * Note we don't test ec_broken; if we did, we'd need a separate code path
3180 * to look through ec_sources. Checking the members anyway is OK as a
3181 * possibly-overoptimistic heuristic.
3182 */
3184 /* If specified rel is a child, we must consider the topmost parent rel */
3186 {
3189 }
3190 else
3193 /* If rel already includes all members of eclass, no point in searching */
3197 /* To join, we need a member not in the given rel */
3199 {
3207 }
3210 }
3213 /*
3214 * is_redundant_derived_clause
3215 * Test whether rinfo is derived from same EC as any clause in clauselist;
3216 * if so, it can be presumed to represent a condition that's redundant
3217 * with that member of the list.
3218 */
3219 bool
3221 {
3225 /* Fail if it's not a potentially-redundant clause from some EC */
3230 {
3235 }
3238 }
3240 /*
3241 * is_redundant_with_indexclauses
3242 * Test whether rinfo is redundant with any clause in the IndexClause
3243 * list. Here, for convenience, we test both simple identity and
3244 * whether it is derived from the same EC as any member of the list.
3245 */
3246 bool
3248 {
3253 {
3257 /* If indexclause is lossy, it won't enforce the condition exactly */
3261 /* Match if it's same clause (pointer equality should be enough) */
3264 /* Match if derived from same EC */
3268 /*
3269 * No need to look at the derived clauses in iclause->indexquals; they
3270 * couldn't match if the parent clause didn't.
3271 */
3272 }
3275 }
3277 /*
3278 * get_eclass_indexes_for_relids
3279 * Build and return a Bitmapset containing the indexes into root's
3280 * eq_classes list for all eclasses that mention any of these relids
3281 */
3284 {
3288 /* Should be OK to rely on eclass_indexes */
3292 {
3296 {
3299 }
3302 }
3304 }
3306 /*
3307 * get_common_eclass_indexes
3308 * Build and return a Bitmapset containing the indexes into root's
3309 * eq_classes list for all eclasses that mention rels in both
3310 * relids1 and relids2.
3311 */
3314 {
3321 /*
3322 * We can get away with just using the relation's eclass_indexes directly
3323 * when relids2 is a singleton set.
3324 */
3327 else
3330 /* Calculate and return the common EC indexes, recycling the left input. */
3332 }