| blob | 8c6770de972dad59638773e51a173d04d37c952c |
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-2022, 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>
47 Relids join_relids,
48 Relids outer_relids,
49 Relids inner_relids);
52 Relids nominal_join_relids,
53 Relids outer_relids,
54 Relids nominal_inner_relids,
69 Relids relids);
71 Relids relids2);
74 /*
75 * process_equivalence
76 * The given clause has a mergejoinable operator and can be applied without
77 * any delay by an outer join, so its two sides can be considered equal
78 * anywhere they are both computable; moreover that equality can be
79 * extended transitively. Record this knowledge in the EquivalenceClass
80 * data structure, if applicable. Returns true if successful, false if not
81 * (in which case caller should treat the clause as ordinary, not an
82 * equivalence).
83 *
84 * In some cases, although we cannot convert a clause into EquivalenceClass
85 * knowledge, we can still modify it to a more useful form than the original.
86 * Then, *p_restrictinfo will be replaced by a new RestrictInfo, which is what
87 * the caller should use for further processing.
88 *
89 * If below_outer_join is true, then the clause was found below the nullable
90 * side of an outer join, so its sides might validly be both NULL rather than
91 * strictly equal. We can still deduce equalities in such cases, but we take
92 * care to mark an EquivalenceClass if it came from any such clauses. Also,
93 * we have to check that both sides are either pseudo-constants or strict
94 * functions of Vars, else they might not both go to NULL above the outer
95 * join. (This is the main reason why we need a failure return. It's more
96 * convenient to check this case here than at the call sites...)
97 *
98 * We also reject proposed equivalence clauses if they contain leaky functions
99 * and have security_level above zero. The EC evaluation rules require us to
100 * apply certain tests at certain joining levels, and we can't tolerate
101 * delaying any test on security_level grounds. By rejecting candidate clauses
102 * that might require security delays, we ensure it's safe to apply an EC
103 * clause as soon as it's supposed to be applied.
104 *
105 * On success return, we have also initialized the clause's left_ec/right_ec
106 * fields to point to the EquivalenceClass representing it. This saves lookup
107 * effort later.
108 *
109 * Note: constructing merged EquivalenceClasses is a standard UNION-FIND
110 * problem, for which there exist better data structures than simple lists.
111 * If this code ever proves to be a bottleneck then it could be sped up ---
112 * but for now, simple is beautiful.
113 *
114 * Note: this is only called during planner startup, not during GEQO
115 * exploration, so we need not worry about whether we're in the right
116 * memory context.
117 */
118 bool
122 {
125 Oid opno,
126 collation,
127 item1_type,
128 item2_type;
131 Relids item1_relids,
132 item2_relids,
133 item1_nullable_relids,
134 item2_nullable_relids;
143 /* Should not already be marked as having generated an eclass */
147 /* Reject if it is potentially postponable by security considerations */
151 /* Extract info from given clause */
160 /*
161 * Ensure both input expressions expose the desired collation (their types
162 * should be OK already); see comments for canonicalize_ec_expression.
163 */
166 collation);
169 collation);
171 /*
172 * Clauses of the form X=X cannot be translated into EquivalenceClasses.
173 * We'd either end up with a single-entry EC, losing the knowledge that
174 * the clause was present at all, or else make an EC with duplicate
175 * entries, causing other issues.
176 */
178 {
179 /*
180 * If the operator is strict, then the clause can be treated as just
181 * "X IS NOT NULL". (Since we know we are considering a top-level
182 * qual, we can ignore the difference between FALSE and NULL results.)
183 * It's worth making the conversion because we'll typically get a much
184 * better selectivity estimate than we would for X=X.
185 *
186 * If the operator is not strict, we can't be sure what it will do
187 * with NULLs, so don't attempt to optimize it.
188 */
191 {
206 NULL,
209 }
211 }
213 /*
214 * If below outer join, check for strictness, else reject.
215 */
217 {
224 }
226 /* Calculate nullable-relid sets for each side of the clause */
232 /*
233 * We use the declared input types of the operator, not exprType() of the
234 * inputs, as the nominal datatypes for opfamily lookup. This presumes
235 * that btree operators are always registered with amoplefttype and
236 * amoprighttype equal to their declared input types. We will need this
237 * info anyway to build EquivalenceMember nodes, and by extracting it now
238 * we can use type comparisons to short-circuit some equal() tests.
239 */
244 /*
245 * Sweep through the existing EquivalenceClasses looking for matches to
246 * item1 and item2. These are the possible outcomes:
247 *
248 * 1. We find both in the same EC. The equivalence is already known, so
249 * there's nothing to do.
250 *
251 * 2. We find both in different ECs. Merge the two ECs together.
252 *
253 * 3. We find just one. Add the other to its EC.
254 *
255 * 4. We find neither. Make a new, two-entry EC.
256 *
257 * Note: since all ECs are built through this process or the similar
258 * search in get_eclass_for_sort_expr(), it's impossible that we'd match
259 * an item in more than one existing nonvolatile EC. So it's okay to stop
260 * at the first match.
261 */
266 {
270 /* Never match to a volatile EC */
274 /*
275 * The collation has to match; check this first since it's cheaper
276 * than the opfamily comparison.
277 */
281 /*
282 * A "match" requires matching sets of btree opfamilies. Use of
283 * equal() for this test has implications discussed in the comments
284 * for get_mergejoin_opfamilies().
285 */
290 {
295 /*
296 * If below an outer join, don't match constants: they're not as
297 * constant as they look.
298 */
306 {
311 }
316 {
322 }
323 }
327 }
329 /* Sweep finished, what did we find? */
332 {
333 /* If case 1, nothing to do, except add to sources */
335 {
342 /* mark the RI as associated with this eclass */
345 /* mark the RI as usable with this pair of EMs */
349 }
351 /*
352 * Case 2: need to merge ec1 and ec2. This should never happen after
353 * the ECs have reached canonical state; otherwise, pathkeys could be
354 * rendered non-canonical by the merge, and relation eclass indexes
355 * would get broken by removal of an eq_classes list entry.
356 */
360 /*
361 * We add ec2's items to ec1, then set ec2's ec_merged link to point
362 * to ec1 and remove ec2 from the eq_classes list. We cannot simply
363 * delete ec2 because that could leave dangling pointers in existing
364 * PathKeys. We leave it behind with a link so that the merged EC can
365 * be found.
366 */
372 /* can't need to set has_volatile */
380 /* just to avoid debugging confusion w/ dangling pointers: */
391 /* mark the RI as associated with this eclass */
394 /* mark the RI as usable with this pair of EMs */
397 }
399 {
400 /* Case 3: add item2 to ec1 */
409 /* mark the RI as associated with this eclass */
412 /* mark the RI as usable with this pair of EMs */
415 }
417 {
418 /* Case 3: add item1 to ec2 */
427 /* mark the RI as associated with this eclass */
430 /* mark the RI as usable with this pair of EMs */
433 }
434 else
435 {
436 /* Case 4: make a new, two-entry EC */
460 /* mark the RI as associated with this eclass */
463 /* mark the RI as usable with this pair of EMs */
466 }
469 }
471 /*
472 * canonicalize_ec_expression
473 *
474 * This function ensures that the expression exposes the expected type and
475 * collation, so that it will be equal() to other equivalence-class expressions
476 * that it ought to be equal() to.
477 *
478 * The rule for datatypes is that the exposed type should match what it would
479 * be for an input to an operator of the EC's opfamilies; which is usually
480 * the declared input type of the operator, but in the case of polymorphic
481 * operators no relabeling is wanted (compare the behavior of parse_coerce.c).
482 * Expressions coming in from quals will generally have the right type
483 * already, but expressions coming from indexkeys may not (because they are
484 * represented without any explicit relabel in pg_index), and the same problem
485 * occurs for sort expressions (because the parser is likewise cavalier about
486 * putting relabels on them). Such cases will be binary-compatible with the
487 * real operators, so adding a RelabelType is sufficient.
488 *
489 * Also, the expression's exposed collation must match the EC's collation.
490 * This is important because in comparisons like "foo < bar COLLATE baz",
491 * only one of the expressions has the correct exposed collation as we receive
492 * it from the parser. Forcing both of them to have it ensures that all
493 * variant spellings of such a construct behave the same. Again, we can
494 * stick on a RelabelType to force the right exposed collation. (It might
495 * work to not label the collation at all in EC members, but this is risky
496 * since some parts of the system expect exprCollation() to deliver the
497 * right answer for a sort key.)
498 */
499 Expr *
501 {
504 /*
505 * For a polymorphic-input-type opclass, just keep the same exposed type.
506 * RECORD opclasses work like polymorphic-type ones for this purpose.
507 */
511 /*
512 * No work if the expression exposes the right type/collation already.
513 */
516 {
517 /*
518 * If we have to change the type of the expression, set typmod to -1,
519 * since the new type may not have the same typmod interpretation.
520 * When we only have to change collation, preserve the exposed typmod.
521 */
522 int32 req_typmod;
526 else
529 /*
530 * Use applyRelabelType so that we preserve const-flatness. This is
531 * important since eval_const_expressions has already been applied.
532 */
536 }
539 }
541 /*
542 * add_eq_member - build a new EquivalenceMember and add it to an EC
543 */
547 {
558 {
559 /*
560 * No Vars, assume it's a pseudoconstant. This is correct for entries
561 * generated from process_equivalence(), because a WHERE clause can't
562 * contain aggregates or SRFs, and non-volatility was checked before
563 * process_equivalence() ever got called. But
564 * get_eclass_for_sort_expr() has to work harder. We put the tests
565 * there not here to save cycles in the equivalence case.
566 */
570 /* it can't affect ec_relids */
571 }
573 {
575 }
579 }
582 /*
583 * get_eclass_for_sort_expr
584 * Given an expression and opfamily/collation info, find an existing
585 * equivalence class it is a member of; if none, optionally build a new
586 * single-member EquivalenceClass for it.
587 *
588 * expr is the expression, and nullable_relids is the set of base relids
589 * that are potentially nullable below it. We actually only care about
590 * the set of such relids that are used in the expression; but for caller
591 * convenience, we perform that intersection step here. The caller need
592 * only be sure that nullable_relids doesn't omit any nullable rels that
593 * might appear in the expr.
594 *
595 * sortref is the SortGroupRef of the originating SortGroupClause, if any,
596 * or zero if not. (It should never be zero if the expression is volatile!)
597 *
598 * If rel is not NULL, it identifies a specific relation we're considering
599 * a path for, and indicates that child EC members for that relation can be
600 * considered. Otherwise child members are ignored. (Note: since child EC
601 * members aren't guaranteed unique, a non-NULL value means that there could
602 * be more than one EC that matches the expression; if so it's order-dependent
603 * which one you get. This is annoying but it only happens in corner cases,
604 * so for now we live with just reporting the first match. See also
605 * generate_implied_equalities_for_column and match_pathkeys_to_index.)
606 *
607 * If create_it is true, we'll build a new EquivalenceClass when there is no
608 * match. If create_it is false, we just return NULL when no match.
609 *
610 * This can be used safely both before and after EquivalenceClass merging;
611 * since it never causes merging it does not invalidate any existing ECs
612 * or PathKeys. However, ECs added after path generation has begun are
613 * of limited usefulness, so usually it's best to create them beforehand.
614 *
615 * Note: opfamilies must be chosen consistently with the way
616 * process_equivalence() would do; that is, generated from a mergejoinable
617 * equality operator. Else we might fail to detect valid equivalences,
618 * generating poor (but not incorrect) plans.
619 */
620 EquivalenceClass *
623 Relids nullable_relids,
625 Oid opcintype,
626 Oid collation,
627 Index sortref,
628 Relids rel,
630 {
631 Relids expr_relids;
635 MemoryContext oldcontext;
637 /*
638 * Ensure the expression exposes the correct type and collation.
639 */
642 /*
643 * Scan through the existing EquivalenceClasses for a match
644 */
646 {
650 /*
651 * Never match to a volatile EC, except when we are looking at another
652 * reference to the same volatile SortGroupClause.
653 */
664 {
667 /*
668 * Ignore child members unless they match the request.
669 */
674 /*
675 * If below an outer join, don't match constants: they're not as
676 * constant as they look.
677 */
685 }
686 }
688 /* No match; does caller want a NULL result? */
692 /*
693 * OK, build a new single-member EC
694 *
695 * Here, we must be sure that we construct the EC in the right context.
696 */
718 /*
719 * Get the precise set of nullable relids appearing in the expression.
720 */
727 /*
728 * add_eq_member doesn't check for volatile functions, set-returning
729 * functions, aggregates, or window functions, but such could appear in
730 * sort expressions; so we have to check whether its const-marking was
731 * correct.
732 */
734 {
739 {
742 }
743 }
747 /*
748 * If EC merging is already complete, we have to mop up by adding the new
749 * EC to the eclass_indexes of the relation(s) mentioned in it.
750 */
752 {
757 {
764 ec_index);
765 }
766 }
771 }
773 /*
774 * find_ec_member_matching_expr
775 * Locate an EquivalenceClass member matching the given expr, if any;
776 * return NULL if no match.
777 *
778 * "Matching" is defined as "equal after stripping RelabelTypes".
779 * This is used for identifying sort expressions, and we need to allow
780 * binary-compatible relabeling for some cases involving binary-compatible
781 * sort operators.
782 *
783 * Child EC members are ignored unless they belong to given 'relids'.
784 */
785 EquivalenceMember *
788 Relids relids)
789 {
792 /* We ignore binary-compatible relabeling on both ends */
797 {
801 /*
802 * We shouldn't be trying to sort by an equivalence class that
803 * contains a constant, so no need to consider such cases any further.
804 */
808 /*
809 * Ignore child members unless they belong to the requested rel.
810 */
815 /*
816 * Match if same expression (after stripping relabel).
817 */
824 }
827 }
829 /*
830 * find_computable_ec_member
831 * Locate an EquivalenceClass member that can be computed from the
832 * expressions appearing in "exprs"; return NULL if no match.
833 *
834 * "exprs" can be either a list of bare expression trees, or a list of
835 * TargetEntry nodes. Either way, it should contain Vars and possibly
836 * Aggrefs and WindowFuncs, which are matched to the corresponding elements
837 * of the EquivalenceClass's expressions.
838 *
839 * Unlike find_ec_member_matching_expr, there's no special provision here
840 * for binary-compatible relabeling. This is intentional: if we have to
841 * compute an expression in this way, setrefs.c is going to insist on exact
842 * matches of Vars to the source tlist.
843 *
844 * Child EC members are ignored unless they belong to given 'relids'.
845 * Also, non-parallel-safe expressions are ignored if 'require_parallel_safe'.
846 *
847 * Note: some callers pass root == NULL for notational reasons. This is OK
848 * when require_parallel_safe is false.
849 */
850 EquivalenceMember *
854 Relids relids,
856 {
860 {
865 /*
866 * We shouldn't be trying to sort by an equivalence class that
867 * contains a constant, so no need to consider such cases any further.
868 */
872 /*
873 * Ignore child members unless they belong to the requested rel.
874 */
879 /*
880 * Match if all Vars and quasi-Vars are available in "exprs".
881 */
883 PVC_INCLUDE_AGGREGATES |
884 PVC_INCLUDE_WINDOWFUNCS |
885 PVC_INCLUDE_PLACEHOLDERS);
887 {
890 }
895 /*
896 * If requested, reject expressions that are not parallel-safe. We
897 * check this last because it's a rather expensive test.
898 */
904 }
907 }
909 /*
910 * is_exprlist_member
911 * Subroutine for find_computable_ec_member: is "node" in "exprs"?
912 *
913 * Per the requirements of that function, "exprs" might or might not have
914 * TargetEntry superstructure.
915 */
916 static bool
918 {
922 {
930 }
932 }
934 /*
935 * Find an equivalence class member expression, all of whose Vars, come from
936 * the indicated relation.
937 */
938 Expr *
940 {
944 {
949 {
950 /*
951 * If there is more than one equivalence member whose Vars are
952 * taken entirely from this relation, we'll be content to choose
953 * any one of those.
954 */
956 }
957 }
959 /* We didn't find any suitable equivalence class expression */
961 }
963 /*
964 * relation_can_be_sorted_early
965 * Can this relation be sorted on this EC before the final output step?
966 *
967 * To succeed, we must find an EC member that prepare_sort_from_pathkeys knows
968 * how to sort on, given the rel's reltarget as input. There are also a few
969 * additional constraints based on the fact that the desired sort will be done
970 * "early", within the scan/join part of the plan. Also, non-parallel-safe
971 * expressions are ignored if 'require_parallel_safe'.
972 *
973 * At some point we might want to return the identified EquivalenceMember,
974 * but for now, callers only want to know if there is one.
975 */
976 bool
979 {
984 /*
985 * Reject volatile ECs immediately; such sorts must always be postponed.
986 */
990 /*
991 * Try to find an EM directly matching some reltarget member.
992 */
994 {
1001 /*
1002 * Reject expressions involving set-returning functions, as those
1003 * can't be computed early either. (Note: this test and the following
1004 * one are effectively checking properties of targetexpr, so there's
1005 * no point in asking whether some other EC member would be better.)
1006 */
1010 /*
1011 * If requested, reject expressions that are not parallel-safe. We
1012 * check this last because it's a rather expensive test.
1013 */
1019 }
1021 /*
1022 * Try to find a expression computable from the reltarget.
1023 */
1025 require_parallel_safe);
1029 /*
1030 * Reject expressions involving set-returning functions, as those can't be
1031 * computed early either. (There's no point in looking for another EC
1032 * member in this case; since SRFs can't appear in WHERE, they cannot
1033 * belong to multi-member ECs.)
1034 */
1039 }
1041 /*
1042 * generate_base_implied_equalities
1043 * Generate any restriction clauses that we can deduce from equivalence
1044 * classes.
1045 *
1046 * When an EC contains pseudoconstants, our strategy is to generate
1047 * "member = const1" clauses where const1 is the first constant member, for
1048 * every other member (including other constants). If we are able to do this
1049 * then we don't need any "var = var" comparisons because we've successfully
1050 * constrained all the vars at their points of creation. If we fail to
1051 * generate any of these clauses due to lack of cross-type operators, we fall
1052 * back to the "ec_broken" strategy described below. (XXX if there are
1053 * multiple constants of different types, it's possible that we might succeed
1054 * in forming all the required clauses if we started from a different const
1055 * member; but this seems a sufficiently hokey corner case to not be worth
1056 * spending lots of cycles on.)
1057 *
1058 * For ECs that contain no pseudoconstants, we generate derived clauses
1059 * "member1 = member2" for each pair of members belonging to the same base
1060 * relation (actually, if there are more than two for the same base relation,
1061 * we only need enough clauses to link each to each other). This provides
1062 * the base case for the recursion: each row emitted by a base relation scan
1063 * will constrain all computable members of the EC to be equal. As each
1064 * join path is formed, we'll add additional derived clauses on-the-fly
1065 * to maintain this invariant (see generate_join_implied_equalities).
1066 *
1067 * If the opfamilies used by the EC do not provide complete sets of cross-type
1068 * equality operators, it is possible that we will fail to generate a clause
1069 * that must be generated to maintain the invariant. (An example: given
1070 * "WHERE a.x = b.y AND b.y = a.z", the scheme breaks down if we cannot
1071 * generate "a.x = a.z" as a restriction clause for A.) In this case we mark
1072 * the EC "ec_broken" and fall back to regurgitating its original source
1073 * RestrictInfos at appropriate times. We do not try to retract any derived
1074 * clauses already generated from the broken EC, so the resulting plan could
1075 * be poor due to bad selectivity estimates caused by redundant clauses. But
1076 * the correct solution to that is to fix the opfamilies ...
1077 *
1078 * Equality clauses derived by this function are passed off to
1079 * process_implied_equality (in plan/initsplan.c) to be inserted into the
1080 * restrictinfo datastructures. Note that this must be called after initial
1081 * scanning of the quals and before Path construction begins.
1082 *
1083 * We make no attempt to avoid generating duplicate RestrictInfos here: we
1084 * don't search ec_sources or ec_derives for matches. It doesn't really
1085 * seem worth the trouble to do so.
1086 */
1087 void
1089 {
1093 /*
1094 * At this point, we're done absorbing knowledge of equivalences in the
1095 * query, so no further EC merging should happen, and ECs remaining in the
1096 * eq_classes list can be considered canonical. (But note that it's still
1097 * possible for new single-member ECs to be added through
1098 * get_eclass_for_sort_expr().)
1099 */
1104 {
1112 /*
1113 * Generate implied equalities that are restriction clauses.
1114 * Single-member ECs won't generate any deductions, either here or at
1115 * the join level.
1116 */
1118 {
1121 else
1124 /* Recover if we failed to generate required derived clauses */
1128 /* Detect whether this EC might generate join clauses */
1129 can_generate_joinclause =
1131 }
1133 /*
1134 * Mark the base rels cited in each eclass (which should all exist by
1135 * now) with the eq_classes indexes of all eclasses mentioning them.
1136 * This will let us avoid searching in subsequent lookups. While
1137 * we're at it, we can mark base rels that have pending eclass joins;
1138 * this is a cheap version of has_relevant_eclass_joinclause().
1139 */
1142 {
1148 ec_index);
1152 }
1154 ec_index++;
1155 }
1156 }
1158 /*
1159 * generate_base_implied_equalities when EC contains pseudoconstant(s)
1160 */
1161 static void
1164 {
1168 /*
1169 * In the trivial case where we just had one "var = const" clause, push
1170 * the original clause back into the main planner machinery. There is
1171 * nothing to be gained by doing it differently, and we save the effort to
1172 * re-build and re-analyze an equality clause that will be exactly
1173 * equivalent to the old one.
1174 */
1177 {
1181 {
1184 }
1185 }
1187 /*
1188 * Find the constant member to use. We prefer an actual constant to
1189 * pseudo-constants (such as Params), because the constraint exclusion
1190 * machinery might be able to exclude relations on the basis of generated
1191 * "var = const" equalities, but "var = param" won't work for that.
1192 */
1194 {
1198 {
1202 }
1203 }
1206 /* Generate a derived equality against each other member */
1208 {
1210 Oid eq_op;
1220 {
1221 /* failed... */
1224 }
1234 /*
1235 * If the clause didn't degenerate to a constant, fill in the correct
1236 * markings for a mergejoinable clause, and save it in ec_derives. (We
1237 * will not re-use such clauses directly, but selectivity estimation
1238 * may consult the list later. Note that this use of ec_derives does
1239 * not overlap with its use for join clauses, since we never generate
1240 * join clauses from an ec_has_const eclass.)
1241 */
1243 {
1244 /* it's not redundant, so don't set parent_ec */
1249 }
1250 }
1251 }
1253 /*
1254 * generate_base_implied_equalities when EC contains no pseudoconstants
1255 */
1256 static void
1259 {
1263 /*
1264 * We scan the EC members once and track the last-seen member for each
1265 * base relation. When we see another member of the same base relation,
1266 * we generate "prev_em = cur_em". This results in the minimum number of
1267 * derived clauses, but it's possible that it will fail when a different
1268 * ordering would succeed. XXX FIXME: use a UNION-FIND algorithm similar
1269 * to the way we build merged ECs. (Use a list-of-lists for each rel.)
1270 */
1275 {
1285 {
1287 Oid eq_op;
1294 {
1295 /* failed... */
1298 }
1308 /*
1309 * If the clause didn't degenerate to a constant, fill in the
1310 * correct markings for a mergejoinable clause. We don't put it
1311 * in ec_derives however; we don't currently need to re-find such
1312 * clauses, and we don't want to clutter that list with non-join
1313 * clauses.
1314 */
1316 {
1317 /* it's not redundant, so don't set parent_ec */
1321 }
1322 }
1324 }
1328 /*
1329 * We also have to make sure that all the Vars used in the member clauses
1330 * will be available at any join node we might try to reference them at.
1331 * For the moment we force all the Vars to be available at all join nodes
1332 * for this eclass. Perhaps this could be improved by doing some
1333 * pre-analysis of which members we prefer to join, but it's no worse than
1334 * what happened in the pre-8.3 code.
1335 */
1337 {
1340 PVC_RECURSE_AGGREGATES |
1341 PVC_RECURSE_WINDOWFUNCS |
1342 PVC_INCLUDE_PLACEHOLDERS);
1346 }
1347 }
1349 /*
1350 * generate_base_implied_equalities cleanup after failure
1351 *
1352 * What we must do here is push any zero- or one-relation source RestrictInfos
1353 * of the EC back into the main restrictinfo datastructures. Multi-relation
1354 * clauses will be regurgitated later by generate_join_implied_equalities().
1355 * (We do it this way to maintain continuity with the case that ec_broken
1356 * becomes set only after we've gone up a join level or two.) However, for
1357 * an EC that contains constants, we can adopt a simpler strategy and just
1358 * throw back all the source RestrictInfos immediately; that works because
1359 * we know that such an EC can't become broken later. (This rule justifies
1360 * ignoring ec_has_const ECs in generate_join_implied_equalities, even when
1361 * they are broken.)
1362 */
1363 static void
1366 {
1370 {
1376 }
1377 }
1380 /*
1381 * generate_join_implied_equalities
1382 * Generate any join clauses that we can deduce from equivalence classes.
1383 *
1384 * At a join node, we must enforce restriction clauses sufficient to ensure
1385 * that all equivalence-class members computable at that node are equal.
1386 * Since the set of clauses to enforce can vary depending on which subset
1387 * relations are the inputs, we have to compute this afresh for each join
1388 * relation pair. Hence a fresh List of RestrictInfo nodes is built and
1389 * passed back on each call.
1390 *
1391 * In addition to its use at join nodes, this can be applied to generate
1392 * eclass-based join clauses for use in a parameterized scan of a base rel.
1393 * The reason for the asymmetry of specifying the inner rel as a RelOptInfo
1394 * and the outer rel by Relids is that this usage occurs before we have
1395 * built any join RelOptInfos.
1396 *
1397 * An annoying special case for parameterized scans is that the inner rel can
1398 * be an appendrel child (an "other rel"). In this case we must generate
1399 * appropriate clauses using child EC members. add_child_rel_equivalences
1400 * must already have been done for the child rel.
1401 *
1402 * The results are sufficient for use in merge, hash, and plain nestloop join
1403 * methods. We do not worry here about selecting clauses that are optimal
1404 * for use in a parameterized indexscan. indxpath.c makes its own selections
1405 * of clauses to use, and if the ones we pick here are redundant with those,
1406 * the extras will be eliminated at createplan time, using the parent_ec
1407 * markers that we provide (see is_redundant_derived_clause()).
1408 *
1409 * Because the same join clauses are likely to be needed multiple times as
1410 * we consider different join paths, we avoid generating multiple copies:
1411 * whenever we select a particular pair of EquivalenceMembers to join,
1412 * we check to see if the pair matches any original clause (in ec_sources)
1413 * or previously-built clause (in ec_derives). This saves memory and allows
1414 * re-use of information cached in RestrictInfos.
1415 *
1416 * join_relids should always equal bms_union(outer_relids, inner_rel->relids).
1417 * We could simplify this function's API by computing it internally, but in
1418 * most current uses, the caller has the value at hand anyway.
1419 */
1420 List *
1422 Relids join_relids,
1423 Relids outer_relids,
1425 {
1428 Relids nominal_inner_relids;
1429 Relids nominal_join_relids;
1433 /* If inner rel is a child, extra setup work is needed */
1435 {
1438 /* Fetch relid set for the topmost parent rel */
1440 /* ECs will be marked with the parent's relid, not the child's */
1442 }
1443 else
1444 {
1447 }
1449 /*
1450 * Get all eclasses that mention both inner and outer sides of the join
1451 */
1453 outer_relids);
1457 {
1461 /* ECs containing consts do not need any further enforcement */
1465 /* Single-member ECs won't generate any deductions */
1469 /* Sanity check that this eclass overlaps the join */
1474 ec,
1475 join_relids,
1476 outer_relids,
1477 inner_relids);
1479 /* Recover if we failed to generate required derived clauses */
1482 ec,
1483 nominal_join_relids,
1484 outer_relids,
1485 nominal_inner_relids,
1486 inner_rel);
1489 }
1492 }
1494 /*
1495 * generate_join_implied_equalities_for_ecs
1496 * As above, but consider only the listed ECs.
1497 */
1498 List *
1501 Relids join_relids,
1502 Relids outer_relids,
1504 {
1507 Relids nominal_inner_relids;
1508 Relids nominal_join_relids;
1511 /* If inner rel is a child, extra setup work is needed */
1513 {
1516 /* Fetch relid set for the topmost parent rel */
1518 /* ECs will be marked with the parent's relid, not the child's */
1520 }
1521 else
1522 {
1525 }
1528 {
1532 /* ECs containing consts do not need any further enforcement */
1536 /* Single-member ECs won't generate any deductions */
1540 /* We can quickly ignore any that don't overlap the join, too */
1546 ec,
1547 join_relids,
1548 outer_relids,
1549 inner_relids);
1551 /* Recover if we failed to generate required derived clauses */
1554 ec,
1555 nominal_join_relids,
1556 outer_relids,
1557 nominal_inner_relids,
1558 inner_rel);
1561 }
1564 }
1566 /*
1567 * generate_join_implied_equalities for a still-valid EC
1568 */
1572 Relids join_relids,
1573 Relids outer_relids,
1574 Relids inner_relids)
1575 {
1582 /*
1583 * First, scan the EC to identify member values that are computable at the
1584 * outer rel, at the inner rel, or at this relation but not in either
1585 * input rel. The outer-rel members should already be enforced equal,
1586 * likewise for the inner-rel members. We'll need to create clauses to
1587 * enforce that any newly computable members are all equal to each other
1588 * as well as to at least one input member, plus enforce at least one
1589 * outer-rel member equal to at least one inner-rel member.
1590 */
1592 {
1595 /*
1596 * We don't need to check explicitly for child EC members. This test
1597 * against join_relids will cause them to be ignored except when
1598 * considering a child inner rel, which is what we want.
1599 */
1607 else
1609 }
1611 /*
1612 * First, select the joinclause if needed. We can equate any one outer
1613 * member to any one inner member, but we have to find a datatype
1614 * combination for which an opfamily member operator exists. If we have
1615 * choices, we prefer simple Var members (possibly with RelabelType) since
1616 * these are (a) cheapest to compute at runtime and (b) most likely to
1617 * have useful statistics. Also, prefer operators that are also
1618 * hashjoinable.
1619 */
1621 {
1629 {
1634 {
1636 Oid eq_op;
1648 score++;
1652 score++;
1655 score++;
1657 {
1664 }
1665 }
1668 }
1670 {
1671 /* failed... */
1674 }
1676 /*
1677 * Create clause, setting parent_ec to mark it as redundant with other
1678 * joinclauses
1679 */
1682 ec);
1685 }
1687 /*
1688 * Now deal with building restrictions for any expressions that involve
1689 * Vars from both sides of the join. We have to equate all of these to
1690 * each other as well as to at least one old member (if any).
1691 *
1692 * XXX as in generate_base_implied_equalities_no_const, we could be a lot
1693 * smarter here to avoid unnecessary failures in cross-type situations.
1694 * For now, use the same left-to-right method used there.
1695 */
1697 {
1702 /* For now, arbitrarily take the first old_member as the one to use */
1707 {
1711 {
1712 Oid eq_op;
1718 {
1719 /* failed... */
1722 }
1723 /* do NOT set parent_ec, this qual is not redundant! */
1726 NULL);
1729 }
1731 }
1732 }
1735 }
1737 /*
1738 * generate_join_implied_equalities cleanup after failure
1739 *
1740 * Return any original RestrictInfos that are enforceable at this join.
1741 *
1742 * In the case of a child inner relation, we have to translate the
1743 * original RestrictInfos from parent to child Vars.
1744 */
1748 Relids nominal_join_relids,
1749 Relids outer_relids,
1750 Relids nominal_inner_relids,
1752 {
1757 {
1765 }
1767 /*
1768 * If we have to translate, just brute-force apply adjust_appendrel_attrs
1769 * to all the RestrictInfos at once. This will result in returning
1770 * RestrictInfos that are not listed in ec_derives, but there shouldn't be
1771 * any duplication, and it's a sufficiently narrow corner case that we
1772 * shouldn't sweat too much over it anyway.
1773 *
1774 * Since inner_rel might be an indirect descendant of the baserel
1775 * mentioned in the ec_sources clauses, we have to be prepared to apply
1776 * multiple levels of Var translation.
1777 */
1785 }
1788 /*
1789 * select_equality_operator
1790 * Select a suitable equality operator for comparing two EC members
1791 *
1792 * Returns InvalidOid if no operator can be found for this datatype combination
1793 */
1794 static Oid
1796 {
1800 {
1802 Oid opno;
1805 BTEqualStrategyNumber);
1808 /* If no barrier quals in query, don't worry about leaky operators */
1811 /* Otherwise, insist that selected operators be leakproof */
1814 }
1816 }
1819 /*
1820 * create_join_clause
1821 * Find or make a RestrictInfo comparing the two given EC members
1822 * with the given operator.
1823 *
1824 * parent_ec is either equal to ec (if the clause is a potentially-redundant
1825 * join clause) or NULL (if not). We have to treat this as part of the
1826 * match requirements --- it's possible that a clause comparing the same two
1827 * EMs is a join clause in one join path and a restriction clause in another.
1828 */
1835 {
1838 MemoryContext oldcontext;
1840 /*
1841 * Search to see if we already built a RestrictInfo for this pair of
1842 * EquivalenceMembers. We can use either original source clauses or
1843 * previously-derived clauses. The check on opno is probably redundant,
1844 * but be safe ...
1845 */
1847 {
1854 }
1857 {
1864 }
1866 /*
1867 * Not there, so build it, in planner context so we can re-use it. (Not
1868 * important in normal planning, but definitely so in GEQO.)
1869 */
1873 opno,
1883 /* Mark the clause as redundant, or not */
1886 /*
1887 * We know the correct values for left_ec/right_ec, ie this particular EC,
1888 * so we can just set them directly instead of forcing another lookup.
1889 */
1893 /* Mark it as usable with these EMs */
1896 /* and save it for possible re-use */
1902 }
1905 /*
1906 * reconsider_outer_join_clauses
1907 * Re-examine any outer-join clauses that were set aside by
1908 * distribute_qual_to_rels(), and see if we can derive any
1909 * EquivalenceClasses from them. Then, if they were not made
1910 * redundant, push them out into the regular join-clause lists.
1911 *
1912 * When we have mergejoinable clauses A = B that are outer-join clauses,
1913 * we can't blindly combine them with other clauses A = C to deduce B = C,
1914 * since in fact the "equality" A = B won't necessarily hold above the
1915 * outer join (one of the variables might be NULL instead). Nonetheless
1916 * there are cases where we can add qual clauses using transitivity.
1917 *
1918 * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
1919 * for which there is also an equivalence clause OUTERVAR = CONSTANT.
1920 * It is safe and useful to push a clause INNERVAR = CONSTANT into the
1921 * evaluation of the inner (nullable) relation, because any inner rows not
1922 * meeting this condition will not contribute to the outer-join result anyway.
1923 * (Any outer rows they could join to will be eliminated by the pushed-down
1924 * equivalence clause.)
1925 *
1926 * Note that the above rule does not work for full outer joins; nor is it
1927 * very interesting to consider cases where the generated equivalence clause
1928 * would involve relations outside the outer join, since such clauses couldn't
1929 * be pushed into the inner side's scan anyway. So the restriction to
1930 * outervar = pseudoconstant is not really giving up anything.
1931 *
1932 * For full-join cases, we can only do something useful if it's a FULL JOIN
1933 * USING and a merged column has an equivalence MERGEDVAR = CONSTANT.
1934 * By the time it gets here, the merged column will look like
1935 * COALESCE(LEFTVAR, RIGHTVAR)
1936 * and we will have a full-join clause LEFTVAR = RIGHTVAR that we can match
1937 * the COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
1938 * and RIGHTVAR = CONSTANT into the input relations, since any rows not
1939 * meeting these conditions cannot contribute to the join result.
1940 *
1941 * Again, there isn't any traction to be gained by trying to deal with
1942 * clauses comparing a mergedvar to a non-pseudoconstant. So we can make
1943 * use of the EquivalenceClasses to search for matching variables that were
1944 * equivalenced to constants. The interesting outer-join clauses were
1945 * accumulated for us by distribute_qual_to_rels.
1946 *
1947 * When we find one of these cases, we implement the changes we want by
1948 * generating a new equivalence clause INNERVAR = CONSTANT (or LEFTVAR, etc)
1949 * and pushing it into the EquivalenceClass structures. This is because we
1950 * may already know that INNERVAR is equivalenced to some other var(s), and
1951 * we'd like the constant to propagate to them too. Note that it would be
1952 * unsafe to merge any existing EC for INNERVAR with the OUTERVAR's EC ---
1953 * that could result in propagating constant restrictions from
1954 * INNERVAR to OUTERVAR, which would be very wrong.
1955 *
1956 * It's possible that the INNERVAR is also an OUTERVAR for some other
1957 * outer-join clause, in which case the process can be repeated. So we repeat
1958 * looping over the lists of clauses until no further deductions can be made.
1959 * Whenever we do make a deduction, we remove the generating clause from the
1960 * lists, since we don't want to make the same deduction twice.
1961 *
1962 * If we don't find any match for a set-aside outer join clause, we must
1963 * throw it back into the regular joinclause processing by passing it to
1964 * distribute_restrictinfo_to_rels(). If we do generate a derived clause,
1965 * however, the outer-join clause is redundant. We still throw it back,
1966 * because otherwise the join will be seen as a clauseless join and avoided
1967 * during join order searching; but we mark it as redundant to keep from
1968 * messing up the joinrel's size estimate. (This behavior means that the
1969 * API for this routine is uselessly complex: we could have just put all
1970 * the clauses into the regular processing initially. We keep it because
1971 * someday we might want to do something else, such as inserting "dummy"
1972 * joinclauses instead of real ones.)
1973 *
1974 * Outer join clauses that are marked outerjoin_delayed are special: this
1975 * condition means that one or both VARs might go to null due to a lower
1976 * outer join. We can still push a constant through the clause, but only
1977 * if its operator is strict; and we *have to* throw the clause back into
1978 * regular joinclause processing. By keeping the strict join clause,
1979 * we ensure that any null-extended rows that are mistakenly generated due
1980 * to suppressing rows not matching the constant will be rejected at the
1981 * upper outer join. (This doesn't work for full-join clauses.)
1982 */
1983 void
1985 {
1989 /* Outer loop repeats until we find no more deductions */
1990 do
1991 {
1994 /* Process the LEFT JOIN clauses */
1996 {
2000 {
2002 /* remove it from the list */
2005 /* we throw it back anyway (see notes above) */
2006 /* but the thrown-back clause has no extra selectivity */
2010 }
2011 }
2013 /* Process the RIGHT JOIN clauses */
2015 {
2019 {
2021 /* remove it from the list */
2024 /* we throw it back anyway (see notes above) */
2025 /* but the thrown-back clause has no extra selectivity */
2029 }
2030 }
2032 /* Process the FULL JOIN clauses */
2034 {
2038 {
2040 /* remove it from the list */
2043 /* we throw it back anyway (see notes above) */
2044 /* but the thrown-back clause has no extra selectivity */
2048 }
2049 }
2052 /* Now, any remaining clauses have to be thrown back */
2054 {
2058 }
2060 {
2064 }
2066 {
2070 }
2071 }
2073 /*
2074 * reconsider_outer_join_clauses for a single LEFT/RIGHT JOIN clause
2075 *
2076 * Returns true if we were able to propagate a constant through the clause.
2077 */
2078 static bool
2081 {
2084 Oid opno,
2085 collation,
2086 left_type,
2087 right_type,
2088 inner_datatype;
2089 Relids inner_relids,
2090 inner_nullable_relids;
2097 /* If clause is outerjoin_delayed, operator must be strict */
2101 /* Extract needed info from the clause */
2104 {
2109 }
2110 else
2111 {
2116 }
2120 /* Scan EquivalenceClasses for a match to outervar */
2122 {
2127 /* Ignore EC unless it contains pseudoconstants */
2130 /* Never match to a volatile EC */
2133 /* It has to match the outer-join clause as to semantics, too */
2138 /* Does it contain a match to outervar? */
2141 {
2146 {
2149 }
2150 }
2154 /*
2155 * Yes it does! Try to generate a clause INNERVAR = CONSTANT for each
2156 * CONSTANT in the EC. Note that we must succeed with at least one
2157 * constant before we can decide to throw away the outer-join clause.
2158 */
2161 {
2163 Oid eq_op;
2169 inner_datatype,
2174 eq_op,
2176 innervar,
2183 }
2185 /*
2186 * If we were able to equate INNERVAR to any constant, report success.
2187 * Otherwise, fall out of the search loop, since we know the OUTERVAR
2188 * appears in at most one EC.
2189 */
2192 else
2194 }
2197 }
2199 /*
2200 * reconsider_outer_join_clauses for a single FULL JOIN clause
2201 *
2202 * Returns true if we were able to propagate a constant through the clause.
2203 */
2204 static bool
2206 {
2209 Oid opno,
2210 collation,
2211 left_type,
2212 right_type;
2213 Relids left_relids,
2214 right_relids,
2215 left_nullable_relids,
2216 right_nullable_relids;
2219 /* Can't use an outerjoin_delayed clause here */
2223 /* Extract needed info from the clause */
2238 {
2247 /* Ignore EC unless it contains pseudoconstants */
2250 /* Never match to a volatile EC */
2253 /* It has to match the outer-join clause as to semantics, too */
2259 /*
2260 * Does it contain a COALESCE(leftvar, rightvar) construct?
2261 *
2262 * We can assume the COALESCE() inputs are in the same order as the
2263 * join clause, since both were automatically generated in the cases
2264 * we care about.
2265 *
2266 * XXX currently this may fail to match in cross-type cases because
2267 * the COALESCE will contain typecast operations while the join clause
2268 * may not (if there is a cross-type mergejoin operator available for
2269 * the two column types). Is it OK to strip implicit coercions from
2270 * the COALESCE arguments?
2271 */
2274 {
2278 {
2289 {
2293 }
2294 }
2295 }
2299 /*
2300 * Yes it does! Try to generate clauses LEFTVAR = CONSTANT and
2301 * RIGHTVAR = CONSTANT for each CONSTANT in the EC. Note that we must
2302 * succeed with at least one constant for each var before we can
2303 * decide to throw away the outer-join clause.
2304 */
2307 {
2309 Oid eq_op;
2315 left_type,
2318 {
2320 eq_op,
2322 leftvar,
2329 }
2331 right_type,
2334 {
2336 eq_op,
2338 rightvar,
2345 }
2346 }
2348 /*
2349 * If we were able to equate both vars to constants, we're done, and
2350 * we can throw away the full-join clause as redundant. Moreover, we
2351 * can remove the COALESCE entry from the EC, since the added
2352 * restrictions ensure it will always have the expected value. (We
2353 * don't bother trying to update ec_relids or ec_sources.)
2354 */
2356 {
2359 }
2361 /*
2362 * Otherwise, fall out of the search loop, since we know the COALESCE
2363 * appears in at most one EC (XXX might stop being true if we allow
2364 * stripping of coercions above?)
2365 */
2367 }
2370 }
2373 /*
2374 * exprs_known_equal
2375 * Detect whether two expressions are known equal due to equivalence
2376 * relationships.
2377 *
2378 * Actually, this only shows that the expressions are equal according
2379 * to some opfamily's notion of equality --- but we only use it for
2380 * selectivity estimation, so a fuzzy idea of equality is OK.
2381 *
2382 * Note: does not bother to check for "equal(item1, item2)"; caller must
2383 * check that case if it's possible to pass identical items.
2384 */
2385 bool
2387 {
2391 {
2397 /* Never match to a volatile EC */
2402 {
2411 /* Exit as soon as equality is proven */
2414 }
2415 }
2417 }
2420 /*
2421 * match_eclasses_to_foreign_key_col
2422 * See whether a foreign key column match is proven by any eclass.
2423 *
2424 * If the referenced and referencing Vars of the fkey's colno'th column are
2425 * known equal due to any eclass, return that eclass; otherwise return NULL.
2426 * (In principle there might be more than one matching eclass if multiple
2427 * collations are involved, but since collation doesn't matter for equality,
2428 * we ignore that fine point here.) This is much like exprs_known_equal,
2429 * except that we insist on the comparison operator matching the eclass, so
2430 * that the result is definite not approximate.
2431 *
2432 * On success, we also set fkinfo->eclass[colno] to the matching eclass,
2433 * and set fkinfo->fk_eclass_member[colno] to the eclass member for the
2434 * referencing Var.
2435 */
2436 EquivalenceClass *
2440 {
2452 /* Consider only eclasses mentioning both relations */
2461 {
2463 i);
2468 /* Never match to a volatile EC */
2471 /* Note: it seems okay to match to "broken" eclasses here */
2474 {
2481 /* EM must be a Var, possibly with RelabelType */
2488 /* Match? */
2494 /* Have we found both PK and FK column in this EC? */
2496 {
2497 /*
2498 * Succeed if eqop matches EC's opfamilies. We could test
2499 * this before scanning the members, but it's probably cheaper
2500 * to test for member matches first.
2501 */
2505 {
2509 }
2510 /* Otherwise, done with this EC, move on to the next */
2512 }
2513 }
2514 }
2516 }
2518 /*
2519 * find_derived_clause_for_ec_member
2520 * Search for a previously-derived clause mentioning the given EM.
2521 *
2522 * The eclass should be an ec_has_const EC, of which the EM is a non-const
2523 * member. This should ensure there is just one derived clause mentioning
2524 * the EM (and equating it to a constant).
2525 * Returns NULL if no such clause can be found.
2526 */
2527 RestrictInfo *
2530 {
2536 {
2539 /*
2540 * generate_base_implied_equalities_const will have put non-const
2541 * members on the left side of derived clauses.
2542 */
2545 }
2547 }
2550 /*
2551 * add_child_rel_equivalences
2552 * Search for EC members that reference the root parent of child_rel, and
2553 * add transformed members referencing the child_rel.
2554 *
2555 * Note that this function won't be called at all unless we have at least some
2556 * reason to believe that the EC members it generates will be useful.
2557 *
2558 * parent_rel and child_rel could be derived from appinfo, but since the
2559 * caller has already computed them, we might as well just pass them in.
2560 *
2561 * The passed-in AppendRelInfo is not used when the parent_rel is not a
2562 * top-level baserel, since it shows the mapping from the parent_rel but
2563 * we need to translate EC expressions that refer to the top-level parent.
2564 * Using it is faster than using adjust_appendrel_attrs_multilevel(), though,
2565 * so we prefer it when we can.
2566 */
2567 void
2572 {
2577 /*
2578 * EC merging should be complete already, so we can use the parent rel's
2579 * eclass_indexes to avoid searching all of root->eq_classes.
2580 */
2586 {
2590 /*
2591 * If this EC contains a volatile expression, then generating child
2592 * EMs would be downright dangerous, so skip it. We rely on a
2593 * volatile EC having only one EM.
2594 */
2598 /* Sanity check eclass_indexes only contain ECs for parent_rel */
2601 /*
2602 * We don't use foreach() here because there's no point in scanning
2603 * newly-added child members, so we can stop after the last
2604 * pre-existing EC member.
2605 */
2608 {
2614 /*
2615 * We consider only original EC members here, not
2616 * already-transformed child members. Otherwise, if some original
2617 * member expression references more than one appendrel, we'd get
2618 * an O(N^2) explosion of useless derived expressions for
2619 * combinations of children. (But add_child_join_rel_equivalences
2620 * may add targeted combinations for partitionwise-join purposes.)
2621 */
2625 /* Does this member reference child's topmost parent rel? */
2627 {
2628 /* Yes, generate transformed child version */
2630 Relids new_relids;
2631 Relids new_nullable_relids;
2634 {
2635 /* Simple single-level transformation */
2640 }
2641 else
2642 {
2643 /* Must do multi-level transformation */
2647 child_relids,
2648 top_parent_relids);
2649 }
2651 /*
2652 * Transform em_relids to match. Note we do *not* do
2653 * pull_varnos(child_expr) here, as for example the
2654 * transformation might have substituted a constant, but we
2655 * don't want the child member to be marked as constant.
2656 */
2658 top_parent_relids);
2661 /*
2662 * And likewise for nullable_relids. Note this code assumes
2663 * parent and child relids are singletons.
2664 */
2667 {
2669 top_parent_relids);
2671 child_relids);
2672 }
2678 /* Record this EC index for the child rel */
2680 }
2681 }
2682 }
2683 }
2685 /*
2686 * add_child_join_rel_equivalences
2687 * Like add_child_rel_equivalences(), but for joinrels
2688 *
2689 * Here we find the ECs relevant to the top parent joinrel and add transformed
2690 * member expressions that refer to this child joinrel.
2691 *
2692 * Note that this function won't be called at all unless we have at least some
2693 * reason to believe that the EC members it generates will be useful.
2694 */
2695 void
2700 {
2704 MemoryContext oldcontext;
2709 /* We need consider only ECs that mention the parent joinrel */
2712 /*
2713 * If we're being called during GEQO join planning, we still have to
2714 * create any new EC members in the main planner context, to avoid having
2715 * a corrupt EC data structure after the GEQO context is reset. This is
2716 * problematic since we'll leak memory across repeated GEQO cycles. For
2717 * now, though, bloat is better than crash. If it becomes a real issue
2718 * we'll have to do something to avoid generating duplicate EC members.
2719 */
2724 {
2728 /*
2729 * If this EC contains a volatile expression, then generating child
2730 * EMs would be downright dangerous, so skip it. We rely on a
2731 * volatile EC having only one EM.
2732 */
2736 /* Sanity check on get_eclass_indexes_for_relids result */
2739 /*
2740 * We don't use foreach() here because there's no point in scanning
2741 * newly-added child members, so we can stop after the last
2742 * pre-existing EC member.
2743 */
2746 {
2752 /*
2753 * We consider only original EC members here, not
2754 * already-transformed child members.
2755 */
2759 /*
2760 * We may ignore expressions that reference a single baserel,
2761 * because add_child_rel_equivalences should have handled them.
2762 */
2766 /* Does this member reference child's topmost parent rel? */
2768 {
2769 /* Yes, generate transformed child version */
2771 Relids new_relids;
2772 Relids new_nullable_relids;
2775 {
2776 /* Simple single-level transformation */
2781 }
2782 else
2783 {
2784 /* Must do multi-level transformation */
2789 child_relids,
2790 top_parent_relids);
2791 }
2793 /*
2794 * Transform em_relids to match. Note we do *not* do
2795 * pull_varnos(child_expr) here, as for example the
2796 * transformation might have substituted a constant, but we
2797 * don't want the child member to be marked as constant.
2798 */
2800 top_parent_relids);
2803 /*
2804 * For nullable_relids, we must selectively replace parent
2805 * nullable relids with child ones.
2806 */
2809 new_nullable_relids =
2811 new_nullable_relids,
2812 child_relids,
2813 top_parent_relids);
2818 }
2819 }
2820 }
2823 }
2826 /*
2827 * generate_implied_equalities_for_column
2828 * Create EC-derived joinclauses usable with a specific column.
2829 *
2830 * This is used by indxpath.c to extract potentially indexable joinclauses
2831 * from ECs, and can be used by foreign data wrappers for similar purposes.
2832 * We assume that only expressions in Vars of a single table are of interest,
2833 * but the caller provides a callback function to identify exactly which
2834 * such expressions it would like to know about.
2835 *
2836 * We assume that any given table/index column could appear in only one EC.
2837 * (This should be true in all but the most pathological cases, and if it
2838 * isn't, we stop on the first match anyway.) Therefore, what we return
2839 * is a redundant list of clauses equating the table/index column to each of
2840 * the other-relation values it is known to be equal to. Any one of
2841 * these clauses can be used to create a parameterized path, and there
2842 * is no value in using more than one. (But it *is* worthwhile to create
2843 * a separate parameterized path for each one, since that leads to different
2844 * join orders.)
2845 *
2846 * The caller can pass a Relids set of rels we aren't interested in joining
2847 * to, so as to save the work of creating useless clauses.
2848 */
2849 List *
2852 ec_matches_callback_type callback,
2854 Relids prohibited_rels)
2855 {
2858 Relids parent_relids;
2861 /* Should be OK to rely on eclass_indexes */
2864 /* Indexes are available only on base or "other" member relations. */
2867 /* If it's a child rel, we'll need to know what its parent(s) are */
2870 else
2875 {
2880 /* Sanity check eclass_indexes only contain ECs for rel */
2883 /*
2884 * Won't generate joinclauses if const or single-member (the latter
2885 * test covers the volatile case too)
2886 */
2890 /*
2891 * Scan members, looking for a match to the target column. Note that
2892 * child EC members are considered, but only when they belong to the
2893 * target relation. (Unlike regular members, the same expression
2894 * could be a child member of more than one EC. Therefore, it's
2895 * potentially order-dependent which EC a child relation's target
2896 * column gets matched to. This is annoying but it only happens in
2897 * corner cases, so for now we live with just reporting the first
2898 * match. See also get_eclass_for_sort_expr.)
2899 */
2902 {
2908 }
2913 /*
2914 * Found our match. Scan the other EC members and attempt to generate
2915 * joinclauses.
2916 */
2918 {
2920 Oid eq_op;
2926 /* Make sure it'll be a join to a different rel */
2931 /* Forget it if caller doesn't want joins to this rel */
2935 /*
2936 * Also, if this is a child rel, avoid generating a useless join
2937 * to its parent rel(s).
2938 */
2949 /* set parent_ec to mark as redundant with other joinclauses */
2952 cur_ec);
2955 }
2957 /*
2958 * If somehow we failed to create any join clauses, we might as well
2959 * keep scanning the ECs for another match. But if we did make any,
2960 * we're done, because we don't want to return non-redundant clauses.
2961 */
2964 }
2967 }
2969 /*
2970 * have_relevant_eclass_joinclause
2971 * Detect whether there is an EquivalenceClass that could produce
2972 * a joinclause involving the two given relations.
2973 *
2974 * This is essentially a very cut-down version of
2975 * generate_join_implied_equalities(). Note it's OK to occasionally say "yes"
2976 * incorrectly. Hence we don't bother with details like whether the lack of a
2977 * cross-type operator might prevent the clause from actually being generated.
2978 */
2979 bool
2982 {
2986 /* Examine only eclasses mentioning both rel1 and rel2 */
2992 {
2994 i);
2996 /*
2997 * Sanity check that get_common_eclass_indexes gave only ECs
2998 * containing both rels.
2999 */
3003 /*
3004 * Won't generate joinclauses if single-member (this test covers the
3005 * volatile case too)
3006 */
3010 /*
3011 * We do not need to examine the individual members of the EC, because
3012 * all that we care about is whether each rel overlaps the relids of
3013 * at least one member, and get_common_eclass_indexes() and the single
3014 * member check above are sufficient to prove that. (As with
3015 * have_relevant_joinclause(), it is not necessary that the EC be able
3016 * to form a joinclause relating exactly the two given rels, only that
3017 * it be able to form a joinclause mentioning both, and this will
3018 * surely be true if both of them overlap ec_relids.)
3019 *
3020 * Note we don't test ec_broken; if we did, we'd need a separate code
3021 * path to look through ec_sources. Checking the membership anyway is
3022 * OK as a possibly-overoptimistic heuristic.
3023 *
3024 * We don't test ec_has_const either, even though a const eclass won't
3025 * generate real join clauses. This is because if we had "WHERE a.x =
3026 * b.y and a.x = 42", it is worth considering a join between a and b,
3027 * since the join result is likely to be small even though it'll end
3028 * up being an unqualified nestloop.
3029 */
3032 }
3035 }
3038 /*
3039 * has_relevant_eclass_joinclause
3040 * Detect whether there is an EquivalenceClass that could produce
3041 * a joinclause involving the given relation and anything else.
3042 *
3043 * This is the same as have_relevant_eclass_joinclause with the other rel
3044 * implicitly defined as "everything else in the query".
3045 */
3046 bool
3048 {
3052 /* Examine only eclasses mentioning rel1 */
3057 {
3059 i);
3061 /*
3062 * Won't generate joinclauses if single-member (this test covers the
3063 * volatile case too)
3064 */
3068 /*
3069 * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3070 * to find an EC that mentions both this rel and some other rel.
3071 */
3074 }
3077 }
3080 /*
3081 * eclass_useful_for_merging
3082 * Detect whether the EC could produce any mergejoinable join clauses
3083 * against the specified relation.
3084 *
3085 * This is just a heuristic test and doesn't have to be exact; it's better
3086 * to say "yes" incorrectly than "no". Hence we don't bother with details
3087 * like whether the lack of a cross-type operator might prevent the clause
3088 * from actually being generated.
3089 */
3090 bool
3094 {
3095 Relids relids;
3100 /*
3101 * Won't generate joinclauses if const or single-member (the latter test
3102 * covers the volatile case too)
3103 */
3107 /*
3108 * Note we don't test ec_broken; if we did, we'd need a separate code path
3109 * to look through ec_sources. Checking the members anyway is OK as a
3110 * possibly-overoptimistic heuristic.
3111 */
3113 /* If specified rel is a child, we must consider the topmost parent rel */
3115 {
3118 }
3119 else
3122 /* If rel already includes all members of eclass, no point in searching */
3126 /* To join, we need a member not in the given rel */
3128 {
3136 }
3139 }
3142 /*
3143 * is_redundant_derived_clause
3144 * Test whether rinfo is derived from same EC as any clause in clauselist;
3145 * if so, it can be presumed to represent a condition that's redundant
3146 * with that member of the list.
3147 */
3148 bool
3150 {
3154 /* Fail if it's not a potentially-redundant clause from some EC */
3159 {
3164 }
3167 }
3169 /*
3170 * is_redundant_with_indexclauses
3171 * Test whether rinfo is redundant with any clause in the IndexClause
3172 * list. Here, for convenience, we test both simple identity and
3173 * whether it is derived from the same EC as any member of the list.
3174 */
3175 bool
3177 {
3182 {
3186 /* If indexclause is lossy, it won't enforce the condition exactly */
3190 /* Match if it's same clause (pointer equality should be enough) */
3193 /* Match if derived from same EC */
3197 /*
3198 * No need to look at the derived clauses in iclause->indexquals; they
3199 * couldn't match if the parent clause didn't.
3200 */
3201 }
3204 }
3206 /*
3207 * get_eclass_indexes_for_relids
3208 * Build and return a Bitmapset containing the indexes into root's
3209 * eq_classes list for all eclasses that mention any of these relids
3210 */
3213 {
3217 /* Should be OK to rely on eclass_indexes */
3221 {
3225 }
3227 }
3229 /*
3230 * get_common_eclass_indexes
3231 * Build and return a Bitmapset containing the indexes into root's
3232 * eq_classes list for all eclasses that mention rels in both
3233 * relids1 and relids2.
3234 */
3237 {
3244 /*
3245 * We can get away with just using the relation's eclass_indexes directly
3246 * when relids2 is a singleton set.
3247 */
3250 else
3253 /* Calculate and return the common EC indexes, recycling the left input. */
3255 }