/*------------------------------------------------------------------------- * * equivclass . c * Routines for managing EquivalenceClasses * * See src / backend / optimizer / README for discussion of EquivalenceClasses . * * * Portions Copyright ( c ) 1996 - 2025 , PostgreSQL Global Development Group * Portions Copyright ( c ) 1994 , Regents of the University of California * * IDENTIFICATION * src / backend / optimizer / path / equivclass . c * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #include "postgres.h" #include <limits.h>#include "access/stratnum.h" #include "catalog/pg_type.h" #include "common/hashfn.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" #include "optimizer/appendinfo.h" #include "optimizer/clauses.h" #include "optimizer/optimizer.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/planmain.h" #include "optimizer/restrictinfo.h" #include "rewrite/rewriteManip.h" #include "utils/lsyscache.h" static EquivalenceMember *make_eq_member(EquivalenceClass *ec,static EquivalenceMember *add_eq_member(EquivalenceClass *ec,static EquivalenceMember *add_child_eq_member(PlannerInfo *root,int ec_index, Expr *expr,static void generate_base_implied_equalities_const(PlannerInfo *root,static void generate_base_implied_equalities_no_const(PlannerInfo *root,static void generate_base_implied_equalities_broken(PlannerInfo *root,static List *generate_join_implied_equalities_normal(PlannerInfo *root,static List *generate_join_implied_equalities_broken(PlannerInfo *root,static Oid select_equality_operator(EquivalenceClass *ec,static RestrictInfo *create_join_clause(PlannerInfo *root,static bool reconsider_outer_join_clause(PlannerInfo *root,bool outer_on_left);static bool reconsider_full_join_clause(PlannerInfo *root,static JoinDomain *find_join_domain(PlannerInfo *root, Relids relids);static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1,static void ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec);static void ec_add_derived_clauses(EquivalenceClass *ec, List *clauses);static void ec_add_derived_clause(EquivalenceClass *ec, RestrictInfo *clause);static void ec_add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo);static RestrictInfo *ec_search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,static RestrictInfo *ec_search_derived_clause_for_ems(PlannerInfo *root,/* * Hash key identifying a derived clause . * * This structure should not be filled manually . Use fill_ec_derives_key ( ) to * set it up in canonical form . typedef struct /* Hash table entry in ec_derives_hash. */ typedef struct /* Threshold for switching from list to hash table */ #define EC_DERIVES_HASH_THRESHOLD 32 #define SH_PREFIX derives#define SH_ELEMENT_TYPE ECDerivesEntry#define SH_KEY_TYPE ECDerivesKey#define SH_KEY key#define SH_HASH_KEY(tb, key) \const unsigned char *) &(key), sizeof (ECDerivesKey))#define SH_EQUAL(tb, a, b) \#define SH_SCOPE static inline #define SH_DECLARE#define SH_DEFINE#include "lib/simplehash.h" /* * process_equivalence * The given clause has a mergejoinable operator and is not an outer - join * qualification , so its two sides can be considered equal * anywhere they are both computable ; moreover that equality can be * extended transitively . Record this knowledge in the EquivalenceClass * data structure , if applicable . Returns true if successful , false if not * ( in which case caller should treat the clause as ordinary , not an * equivalence ) . * * In some cases , although we cannot convert a clause into EquivalenceClass * knowledge , we can still modify it to a more useful form than the original . * Then , * p_restrictinfo will be replaced by a new RestrictInfo , which is what * the caller should use for further processing . * * jdomain is the join domain within which the given clause was found . * This limits the applicability of deductions from the EquivalenceClass , * as described in optimizer / README . * * We reject proposed equivalence clauses if they contain leaky functions * and have security_level above zero . The EC evaluation rules require us to * apply certain tests at certain joining levels , and we can ' t tolerate * delaying any test on security_level grounds . By rejecting candidate clauses * that might require security delays , we ensure it ' s safe to apply an EC * clause as soon as it ' s supposed to be applied . * * On success return , we have also initialized the clause ' s left_ec / right_ec * fields to point to the EquivalenceClass representing it . This saves lookup * effort later . * * Note : constructing merged EquivalenceClasses is a standard UNION - FIND * problem , for which there exist better data structures than simple lists . * If this code ever proves to be a bottleneck then it could be sped up - - - * but for now , simple is beautiful . * * Note : this is only called during planner startup , not during GEQO * exploration , so we need not worry about whether we ' re in the right * memory context . bool int ec2_idx;/* Should not already be marked as having generated an eclass */ /* Reject if it is potentially postponable by security considerations */ if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)return false ;/* Extract info from given clause */ /* * Ensure both input expressions expose the desired collation ( their types * should be OK already ) ; see comments for canonicalize_ec_expression . /* * Clauses of the form X = X cannot be translated into EquivalenceClasses . * We ' d either end up with a single - entry EC , losing the knowledge that * the clause was present at all , or else make an EC with duplicate * entries , causing other issues . if (equal(item1, item2))/* * If the operator is strict , then the clause can be treated as just * " X IS NOT NULL " . ( Since we know we are considering a top - level * qual , we can ignore the difference between FALSE and NULL results . ) * It ' s worth making the conversion because we ' ll typically get a much * better selectivity estimate than we would for X = X . * * If the operator is not strict , we can ' t be sure what it will do * with NULLs , so don ' t attempt to optimize it . if (func_strict(((OpExpr *) clause)->opfuncid))false ; /* correct even if composite arg */ 1 ;return false ;/* * We use the declared input types of the operator , not exprType ( ) of the * inputs , as the nominal datatypes for opfamily lookup . This presumes * that btree operators are always registered with amoplefttype and * amoprighttype equal to their declared input types . We will need this * info anyway to build EquivalenceMember nodes , and by extracting it now * we can use type comparisons to short - circuit some equal ( ) tests . /* * Sweep through the existing EquivalenceClasses looking for matches to * item1 and item2 . These are the possible outcomes : * * 1 . We find both in the same EC . The equivalence is already known , so * there ' s nothing to do . * * 2 . We find both in different ECs . Merge the two ECs together . * * 3 . We find just one . Add the other to its EC . * * 4 . We find neither . Make a new , two - entry EC . * * Note : since all ECs are built through this process or the similar * search in get_eclass_for_sort_expr ( ) , it ' s impossible that we ' d match * an item in more than one existing nonvolatile EC . So it ' s okay to stop * at the first match . 1 ;/* Never match to a volatile EC */ if (cur_ec->ec_has_volatile)continue ;/* * The collation has to match ; check this first since it ' s cheaper * than the opfamily comparison . if (collation != cur_ec->ec_collation)continue ;/* * A " match " requires matching sets of btree opfamilies . Use of * equal ( ) for this test has implications discussed in the comments * for get_mergejoin_opfamilies ( ) . if (!equal(opfamilies, cur_ec->ec_opfamilies))continue ;/* We don't expect any children yet */ /* Child members should not exist in ec_members */ /* * Match constants only within the same JoinDomain ( see * optimizer / README ) . if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)continue ;if (!ec1 &&if (ec2)break ;if (!ec2 &&if (ec1)break ;if (ec1 && ec2)break ;/* Sweep finished, what did we find? */ if (ec1 && ec2)/* If case 1, nothing to do, except add to sources */ if (ec1 == ec2)/* mark the RI as associated with this eclass */ /* mark the RI as usable with this pair of EMs */ return true ;/* * Case 2 : need to merge ec1 and ec2 . This should never happen after * the ECs have reached canonical state ; otherwise , pathkeys could be * rendered non - canonical by the merge , and relation eclass indexes * would get broken by removal of an eq_classes list entry . if (root->ec_merging_done)"too late to merge equivalence classes" );/* * We add ec2 ' s items to ec1 , then set ec2 ' s ec_merged link to point * to ec1 and remove ec2 from the eq_classes list . We cannot simply * delete ec2 because that could leave dangling pointers in existing * PathKeys . We leave it behind with a link so that the merged EC can * be found . /* * Appends ec2 ' s derived clauses to ec1 - > ec_derives_list and adds them * to ec1 - > ec_derives_hash if present . /* can't need to set has_volatile */ /* just to avoid debugging confusion w/ dangling pointers: */ /* mark the RI as associated with this eclass */ /* mark the RI as usable with this pair of EMs */ else if (ec1)/* Case 3: add item2 to ec1 */ /* mark the RI as associated with this eclass */ /* mark the RI as usable with this pair of EMs */ else if (ec2)/* Case 3: add item1 to ec2 */ /* mark the RI as associated with this eclass */ /* mark the RI as usable with this pair of EMs */ else /* Case 4: make a new, two-entry EC */ 0 ;false ;false ;false ;0 ;/* mark the RI as associated with this eclass */ /* mark the RI as usable with this pair of EMs */ return true ;/* * canonicalize_ec_expression * * This function ensures that the expression exposes the expected type and * collation , so that it will be equal ( ) to other equivalence - class expressions * that it ought to be equal ( ) to . * * The rule for datatypes is that the exposed type should match what it would * be for an input to an operator of the EC ' s opfamilies ; which is usually * the declared input type of the operator , but in the case of polymorphic * operators no relabeling is wanted ( compare the behavior of parse_coerce . c ) . * Expressions coming in from quals will generally have the right type * already , but expressions coming from indexkeys may not ( because they are * represented without any explicit relabel in pg_index ) , and the same problem * occurs for sort expressions ( because the parser is likewise cavalier about * putting relabels on them ) . Such cases will be binary - compatible with the * real operators , so adding a RelabelType is sufficient . * * Also , the expression ' s exposed collation must match the EC ' s collation . * This is important because in comparisons like " foo < bar COLLATE baz " , * only one of the expressions has the correct exposed collation as we receive * it from the parser . Forcing both of them to have it ensures that all * variant spellings of such a construct behave the same . Again , we can * stick on a RelabelType to force the right exposed collation . ( It might * work to not label the collation at all in EC members , but this is risky * since some parts of the system expect exprCollation ( ) to deliver the * right answer for a sort key . ) /* * For a polymorphic - input - type opclass , just keep the same exposed type . * RECORD opclasses work like polymorphic - type ones for this purpose . if (IsPolymorphicType(req_type) || req_type == RECORDOID)/* * No work if the expression exposes the right type / collation already . if (expr_type != req_type ||/* * If we have to change the type of the expression , set typmod to - 1 , * since the new type may not have the same typmod interpretation . * When we only have to change collation , preserve the exposed typmod . if (expr_type != req_type)1 ;else /* * Use applyRelabelType so that we preserve const - flatness . This is * important since eval_const_expressions has already been applied . 1 , false );return expr;/* * make_eq_member * Build a new EquivalenceMember without adding it to an EC . If ' parent ' * is NULL , the result will be a parent member , otherwise a child member . static EquivalenceMember *false ;if (bms_is_empty(relids))/* * No Vars , assume it ' s a pseudoconstant . This is correct for entries * generated from process_equivalence ( ) , because a WHERE clause can ' t * contain aggregates or SRFs , and non - volatility was checked before * process_equivalence ( ) ever got called . But * get_eclass_for_sort_expr ( ) has to work harder . We put the tests * there not here to save cycles in the equivalence case . true ;true ;/* it can't affect ec_relids */ return em;/* * add_eq_member - build a new non - child EquivalenceMember and add it to ' ec ' . static EquivalenceMember */* add to the members list */ /* record the relids for parent members */ return em;/* * add_child_eq_member * Create an em_is_child = true EquivalenceMember and add it to ' ec ' . * * ' root ' is the PlannerInfo that ' ec ' belongs to . * ' ec ' is the EquivalenceClass to add the child member to . * ' ec_index ' the index of ' ec ' within root - > eq_classes , or - 1 if maintaining * the RelOptInfo . eclass_indexes isn ' t needed . * ' expr ' is the em_expr for the new member . * ' relids ' is the ' em_relids ' for the new member . * ' jdomain ' is the ' em_jdomain ' for the new member . * ' parent_em ' is the parent member of the child to create . * ' datatype ' is the em_datatype of the new member . * ' child_relid ' defines which element of ec_childmembers to add this member * to . This is generally a RELOPT_OTHER_MEMBER_REL , but for set operations * can be a RELOPT_BASEREL representing the set - op children . static EquivalenceMember *int ec_index,/* * Allocate the array to store child members ; an array of Lists indexed by * relid , or expand the existing one , if necessary . if (unlikely(ec->ec_childmembers_size < root->simple_rel_array_size))if (ec->ec_childmembers == NULL)else /* add member to the ec_childmembers List for the given child_relid */ /* Record this EC index for the child rel */ if (ec_index >= 0 )return em;/* * get_eclass_for_sort_expr * Given an expression and opfamily / collation info , find an existing * equivalence class it is a member of ; if none , optionally build a new * single - member EquivalenceClass for it . * * sortref is the SortGroupRef of the originating SortGroupClause , if any , * or zero if not . ( It should never be zero if the expression is volatile ! ) * * If rel is not NULL , it identifies a specific relation we ' re considering * a path for , and indicates that child EC members for that relation can be * considered . Otherwise child members are ignored . ( Note : since child EC * members aren ' t guaranteed unique , a non - NULL value means that there could * be more than one EC that matches the expression ; if so it ' s order - dependent * which one you get . This is annoying but it only happens in corner cases , * so for now we live with just reporting the first match . See also * generate_implied_equalities_for_column and match_pathkeys_to_index . ) * * If create_it is true , we ' ll build a new EquivalenceClass when there is no * match . If create_it is false , we just return NULL when no match . * * This can be used safely both before and after EquivalenceClass merging ; * since it never causes merging it does not invalidate any existing ECs * or PathKeys . However , ECs added after path generation has begun are * of limited usefulness , so usually it ' s best to create them beforehand . * * Note : opfamilies must be chosen consistently with the way * process_equivalence ( ) would do ; that is , generated from a mergejoinable * equality operator . Else we might fail to detect valid equivalences , * generating poor ( but not incorrect ) plans . bool create_it)/* * Ensure the expression exposes the correct type and collation . /* * Since SortGroupClause nodes are top - level expressions ( GROUP BY , ORDER * BY , etc ) , they can be presumed to belong to the top JoinDomain . /* * Scan through the existing EquivalenceClasses for a match /* * Never match to a volatile EC , except when we are looking at another * reference to the same volatile SortGroupClause . if (cur_ec->ec_has_volatile &&0 || sortref != cur_ec->ec_sortref))continue ;if (collation != cur_ec->ec_collation)continue ;if (!equal(opfamilies, cur_ec->ec_opfamilies))continue ;while ((cur_em = eclass_member_iterator_next(&it)) != NULL)/* * Ignore child members unless they match the request . if (cur_em->em_is_child &&continue ;/* * Match constants only within the same JoinDomain ( see * optimizer / README ) . if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)continue ;if (opcintype == cur_em->em_datatype &&return cur_ec; /* Match! */ /* No match; does caller want a NULL result? */ if (!create_it)return NULL;/* * OK , build a new single - member EC * * Here , we must be sure that we construct the EC in the right context . 0 ;false ;false ;0 ;if (newec->ec_has_volatile && sortref == 0 ) /* should not happen */ "volatile EquivalenceClass has no sortref" );/* * Get the precise set of relids appearing in the expression . /* * add_eq_member doesn ' t check for volatile functions , set - returning * functions , aggregates , or window functions , but such could appear in * sort expressions ; so we have to check whether its const - marking was * correct . if (newec->ec_has_const)if (newec->ec_has_volatile ||false ;false ;/* * If EC merging is already complete , we have to mop up by adding the new * EC to the eclass_indexes of the relation ( s ) mentioned in it . if (root->ec_merging_done)int ec_index = list_length(root->eq_classes) - 1 ;int i = -1 ;while ((i = bms_next_member(newec->ec_relids, i)) > 0 )/* ignore the RTE_GROUP RTE */ if (i == root->group_rtindex)continue ;if (rel == NULL) /* must be an outer join */ continue ;return newec;/* * find_ec_member_matching_expr * Locate an EquivalenceClass member matching the given expr , if any ; * return NULL if no match . * * " Matching " is defined as " equal after stripping RelabelTypes " . * This is used for identifying sort expressions , and we need to allow * binary - compatible relabeling for some cases involving binary - compatible * sort operators . * * Child EC members are ignored unless they belong to given ' relids ' . /* We ignore binary-compatible relabeling on both ends */ while (expr && IsA(expr, RelabelType))while ((em = eclass_member_iterator_next(&it)) != NULL)/* * We shouldn ' t be trying to sort by an equivalence class that * contains a constant , so no need to consider such cases any further . if (em->em_is_const)continue ;/* * Ignore child members unless they belong to the requested rel . if (em->em_is_child &&continue ;/* * Match if same expression ( after stripping relabel ) . while (emexpr && IsA(emexpr, RelabelType))if (equal(emexpr, expr))return em;return NULL;/* * find_computable_ec_member * Locate an EquivalenceClass member that can be computed from the * expressions appearing in " exprs " ; return NULL if no match . * * " exprs " can be either a list of bare expression trees , or a list of * TargetEntry nodes . Typically it will contain Vars and possibly Aggrefs * and WindowFuncs ; however , when considering an appendrel member the list * could contain arbitrary expressions . We consider an EC member to be * computable if all the Vars , PlaceHolderVars , Aggrefs , and WindowFuncs * it needs are present in " exprs " . * * There is some subtlety in that definition : for example , if an EC member is * Var_A + 1 while what is in " exprs " is Var_A + 2 , it ' s still computable . * This works because in the final plan tree , the EC member ' s expression will * be computed as part of the same plan node targetlist that is currently * represented by " exprs " . So if we have Var_A available for the existing * tlist member , it must be OK to use it in the EC expression too . * * Unlike find_ec_member_matching_expr , there ' s no special provision here * for binary - compatible relabeling . This is intentional : if we have to * compute an expression in this way , setrefs . c is going to insist on exact * matches of Vars to the source tlist . * * Child EC members are ignored unless they belong to given ' relids ' . * Also , non - parallel - safe expressions are ignored if ' require_parallel_safe ' . * * Note : some callers pass root = = NULL for notational reasons . This is OK * when require_parallel_safe is false . bool require_parallel_safe)/* * Pull out the Vars and quasi - Vars present in " exprs " . In the typical * non - appendrel case , this is just another representation of the same * list . However , it does remove the distinction between the case of a * list of plain expressions and a list of TargetEntrys . while ((em = eclass_member_iterator_next(&it)) != NULL)/* * We shouldn ' t be trying to sort by an equivalence class that * contains a constant , so no need to consider such cases any further . if (em->em_is_const)continue ;/* * Ignore child members unless they belong to the requested rel . if (em->em_is_child &&continue ;/* * Match if all Vars and quasi - Vars are present in " exprs " . if (!list_member(exprvars, lfirst(lc2)))break ;if (lc2)continue ; /* we hit a non-available Var */ /* * If requested , reject expressions that are not parallel - safe . We * check this last because it ' s a rather expensive test . if (require_parallel_safe &&continue ;return em; /* found usable expression */ return NULL;/* * relation_can_be_sorted_early * Can this relation be sorted on this EC before the final output step ? * * To succeed , we must find an EC member that prepare_sort_from_pathkeys knows * how to sort on , given the rel ' s reltarget as input . There are also a few * additional constraints based on the fact that the desired sort will be done * " early " , within the scan / join part of the plan . Also , non - parallel - safe * expressions are ignored if ' require_parallel_safe ' . * * At some point we might want to return the identified EquivalenceMember , * but for now , callers only want to know if there is one . bool bool require_parallel_safe)/* * Reject volatile ECs immediately ; such sorts must always be postponed . if (ec->ec_has_volatile)return false ;/* * Try to find an EM directly matching some reltarget member . if (!em)continue ;/* * Reject expressions involving set - returning functions , as those * can ' t be computed early either . ( Note : this test and the following * one are effectively checking properties of targetexpr , so there ' s * no point in asking whether some other EC member would be better . ) if (expression_returns_set((Node *) em->em_expr))continue ;/* * If requested , reject expressions that are not parallel - safe . We * check this last because it ' s a rather expensive test . if (require_parallel_safe &&continue ;return true ;/* * Try to find an expression computable from the reltarget . if (!em)return false ;/* * Reject expressions involving set - returning functions , as those can ' t be * computed early either . ( There ' s no point in looking for another EC * member in this case ; since SRFs can ' t appear in WHERE , they cannot * belong to multi - member ECs . ) if (expression_returns_set((Node *) em->em_expr))return false ;return true ;/* * generate_base_implied_equalities * Generate any restriction clauses that we can deduce from equivalence * classes . * * When an EC contains pseudoconstants , our strategy is to generate * " member = const1 " clauses where const1 is the first constant member , for * every other member ( including other constants ) . If we are able to do this * then we don ' t need any " var = var " comparisons because we ' ve successfully * constrained all the vars at their points of creation . If we fail to * generate any of these clauses due to lack of cross - type operators , we fall * back to the " ec_broken " strategy described below . ( XXX if there are * multiple constants of different types , it ' s possible that we might succeed * in forming all the required clauses if we started from a different const * member ; but this seems a sufficiently hokey corner case to not be worth * spending lots of cycles on . ) * * For ECs that contain no pseudoconstants , we generate derived clauses * " member1 = member2 " for each pair of members belonging to the same base * relation ( actually , if there are more than two for the same base relation , * we only need enough clauses to link each to each other ) . This provides * the base case for the recursion : each row emitted by a base relation scan * will constrain all computable members of the EC to be equal . As each * join path is formed , we ' ll add additional derived clauses on - the - fly * to maintain this invariant ( see generate_join_implied_equalities ) . * * If the opfamilies used by the EC do not provide complete sets of cross - type * equality operators , it is possible that we will fail to generate a clause * that must be generated to maintain the invariant . ( An example : given * " WHERE a . x = b . y AND b . y = a . z " , the scheme breaks down if we cannot * generate " a . x = a . z " as a restriction clause for A . ) In this case we mark * the EC " ec_broken " and fall back to regurgitating its original source * RestrictInfos at appropriate times . We do not try to retract any derived * clauses already generated from the broken EC , so the resulting plan could * be poor due to bad selectivity estimates caused by redundant clauses . But * the correct solution to that is to fix the opfamilies . . . * * Equality clauses derived by this function are passed off to * process_implied_equality ( in plan / initsplan . c ) to be inserted into the * restrictinfo datastructures . Note that this must be called after initial * scanning of the quals and before Path construction begins . * * We make no attempt to avoid generating duplicate RestrictInfos here : we * don ' t search existing source or derived clauses in the EC for matches . It * doesn ' t really seem worth the trouble to do so . void int ec_index;/* * At this point , we ' re done absorbing knowledge of equivalences in the * query , so no further EC merging should happen , and ECs remaining in the * eq_classes list can be considered canonical . ( But note that it ' s still * possible for new single - member ECs to be added through * get_eclass_for_sort_expr ( ) . ) true ;0 ;bool can_generate_joinclause = false ;int i;/* else shouldn't be in list */ /* not yet anyway... */ /* * Generate implied equalities that are restriction clauses . * Single - member ECs won ' t generate any deductions , either here or at * the join level . if (list_length(ec->ec_members) > 1 )if (ec->ec_has_const)else /* Recover if we failed to generate required derived clauses */ if (ec->ec_broken)/* Detect whether this EC might generate join clauses */ /* * Mark the base rels cited in each eclass ( which should all exist by * now ) with the eq_classes indexes of all eclasses mentioning them . * This will let us avoid searching in subsequent lookups . While * we ' re at it , we can mark base rels that have pending eclass joins ; * this is a cheap version of has_relevant_eclass_joinclause ( ) . 1 ;while ((i = bms_next_member(ec->ec_relids, i)) > 0 )/* ignore the RTE_GROUP RTE */ if (i == root->group_rtindex)continue ;if (rel == NULL) /* must be an outer join */ continue ;if (can_generate_joinclause)true ;/* * generate_base_implied_equalities when EC contains pseudoconstant ( s ) static void /* * In the trivial case where we just had one " var = const " clause , push * the original clause back into the main planner machinery . There is * nothing to be gained by doing it differently , and we save the effort to * re - build and re - analyze an equality clause that will be exactly * equivalent to the old one . if (list_length(ec->ec_members) == 2 &&1 )return ;/* We don't expect any children yet */ /* * Find the constant member to use . We prefer an actual constant to * pseudo - constants ( such as Params ) , because the constraint exclusion * machinery might be able to exclude relations on the basis of generated * " var = const " equalities , but " var = param " won ' t work for that . if (cur_em->em_is_const)if (IsA(cur_em->em_expr, Const ))break ;/* Generate a derived equality against each other member */ /* Child members should not exist in ec_members */ if (cur_em == const_em)continue ;if (!OidIsValid(eq_op))/* failed... */ true ;break ;/* * We use the constant ' s em_jdomain as qualscope , so that if the * generated clause is variable - free ( i . e , both EMs are consts ) it * will be enforced at the join domain level . /* * If the clause didn ' t degenerate to a constant , fill in the correct * markings for a mergejoinable clause , and save it as a derived * clause . ( We will not re - use such clauses directly , but selectivity * estimation may consult those later . Note that this use of derived * clauses does not overlap with its use for join clauses , since we * never generate join clauses from an ec_has_const eclass . ) if (rinfo && rinfo->mergeopfamilies)/* it's not redundant, so don't set parent_ec */ /* * generate_base_implied_equalities when EC contains no pseudoconstants static void /* * We scan the EC members once and track the last - seen member for each * base relation . When we see another member of the same base relation , * we generate " prev_em = cur_em " . This results in the minimum number of * derived clauses , but it ' s possible that it will fail when a different * ordering would succeed . XXX FIXME : use a UNION - FIND algorithm similar * to the way we build merged ECs . ( Use a list - of - lists for each rel . ) sizeof (EquivalenceMember *));/* We don't expect any children yet */ int relid;/* Child members should not exist in ec_members */ if (!bms_get_singleton_member(cur_em->em_relids, &relid))continue ;if (prev_ems[relid] != NULL)if (!OidIsValid(eq_op))/* failed... */ true ;break ;/* * The expressions aren ' t constants , so the passed qualscope will * never be used to place the generated clause . We just need to * be sure it covers both expressions , which em_relids should do . false );/* * If the clause didn ' t degenerate to a constant , fill in the * correct markings for a mergejoinable clause . We don ' t record * it as a derived clause , since we don ' t currently need to * re - find such clauses , and don ' t want to clutter the * derived - clause set with non - join clauses . if (rinfo && rinfo->mergeopfamilies)/* it's not redundant, so don't set parent_ec */ /* * We also have to make sure that all the Vars used in the member clauses * will be available at any join node we might try to reference them at . * For the moment we force all the Vars to be available at all join nodes * for this eclass . Perhaps this could be improved by doing some * pre - analysis of which members we prefer to join , but it ' s no worse than * what happened in the pre - 8 . 3 code . ( Note : rebuild_eclass_attr_needed * needs to match this code . ) /* * generate_base_implied_equalities cleanup after failure * * What we must do here is push any zero - or one - relation source RestrictInfos * of the EC back into the main restrictinfo datastructures . Multi - relation * clauses will be regurgitated later by generate_join_implied_equalities ( ) . * ( We do it this way to maintain continuity with the case that ec_broken * becomes set only after we ' ve gone up a join level or two . ) However , for * an EC that contains constants , we can adopt a simpler strategy and just * throw back all the source RestrictInfos immediately ; that works because * we know that such an EC can ' t become broken later . ( This rule justifies * ignoring ec_has_const ECs in generate_join_implied_equalities , even when * they are broken . ) static void if (ec->ec_has_const ||/* * generate_join_implied_equalities * Generate any join clauses that we can deduce from equivalence classes . * * At a join node , we must enforce restriction clauses sufficient to ensure * that all equivalence - class members computable at that node are equal . * Since the set of clauses to enforce can vary depending on which subset * relations are the inputs , we have to compute this afresh for each join * relation pair . Hence a fresh List of RestrictInfo nodes is built and * passed back on each call . * * In addition to its use at join nodes , this can be applied to generate * eclass - based join clauses for use in a parameterized scan of a base rel . * The reason for the asymmetry of specifying the inner rel as a RelOptInfo * and the outer rel by Relids is that this usage occurs before we have * built any join RelOptInfos . * * An annoying special case for parameterized scans is that the inner rel can * be an appendrel child ( an " other rel " ) . In this case we must generate * appropriate clauses using child EC members . add_child_rel_equivalences * must already have been done for the child rel . * * The results are sufficient for use in merge , hash , and plain nestloop join * methods . We do not worry here about selecting clauses that are optimal * for use in a parameterized indexscan . indxpath . c makes its own selections * of clauses to use , and if the ones we pick here are redundant with those , * the extras will be eliminated at createplan time , using the parent_ec * markers that we provide ( see is_redundant_derived_clause ( ) ) . * * Because the same join clauses are likely to be needed multiple times as * we consider different join paths , we avoid generating multiple copies : * whenever we select a particular pair of EquivalenceMembers to join , * we check to see if the pair matches any original clause ( in ec_sources ) * or previously - built derived clause . This saves memory and allows * re - use of information cached in RestrictInfos . We also avoid generating * commutative duplicates , i . e . if the algorithm selects " a . x = b . y " but * we already have " b . y = a . x " , we return the existing clause . * * If we are considering an outer join , sjinfo is the associated OJ info , * otherwise it can be NULL . * * join_relids should always equal bms_union ( outer_relids , inner_rel - > relids ) * plus whatever add_outer_joins_to_relids ( ) would add . We could simplify * this function ' s API by computing it internally , but most callers have the * value at hand anyway . int i;/* If inner rel is a child, extra setup work is needed */ if (IS_OTHER_REL(inner_rel))/* Fetch relid set for the topmost parent rel */ /* ECs will be marked with the parent's relid, not the child's */ else /* * Examine all potentially - relevant eclasses . * * If we are considering an outer join , we must include " join " clauses * that mention either input rel plus the outer join ' s relid ; these * represent post - join filter clauses that have to be applied at this * join . We don ' t have infrastructure that would let us identify such * eclasses cheaply , so just fall back to considering all eclasses * mentioning anything in nominal_join_relids . * * At inner joins , we can be smarter : only consider eclasses mentioning * both input rels . if (sjinfo && sjinfo->ojrelid != 0 )else 1 ;while ((i = bms_next_member(matching_ecs, i)) >= 0 )/* ECs containing consts do not need any further enforcement */ if (ec->ec_has_const)continue ;/* Single-member ECs won't generate any deductions */ if (list_length(ec->ec_members) <= 1 )continue ;/* Sanity check that this eclass overlaps the join */ if (!ec->ec_broken)/* Recover if we failed to generate required derived clauses */ if (ec->ec_broken)return result;/* * generate_join_implied_equalities_for_ecs * As above , but consider only the listed ECs . * * For the sole current caller , we can assume sjinfo = = NULL , that is we are * not interested in outer - join filter clauses . This might need to change * in future . /* If inner rel is a child, extra setup work is needed */ if (IS_OTHER_REL(inner_rel))/* Fetch relid set for the topmost parent rel */ /* ECs will be marked with the parent's relid, not the child's */ else /* ECs containing consts do not need any further enforcement */ if (ec->ec_has_const)continue ;/* Single-member ECs won't generate any deductions */ if (list_length(ec->ec_members) <= 1 )continue ;/* We can quickly ignore any that don't overlap the join, too */ if (!bms_overlap(ec->ec_relids, nominal_join_relids))continue ;if (!ec->ec_broken)/* Recover if we failed to generate required derived clauses */ if (ec->ec_broken)return result;/* * generate_join_implied_equalities for a still - valid EC static List */* * First , scan the EC to identify member values that are computable at the * outer rel , at the inner rel , or at this relation but not in either * input rel . The outer - rel members should already be enforced equal , * likewise for the inner - rel members . We ' ll need to create clauses to * enforce that any newly computable members are all equal to each other * as well as to at least one input member , plus enforce at least one * outer - rel member equal to at least one inner - rel member . while ((cur_em = eclass_member_iterator_next(&it)) != NULL)/* * We don ' t need to check explicitly for child EC members . This test * against join_relids will cause them to be ignored except when * considering a child inner rel , which is what we want . if (!bms_is_subset(cur_em->em_relids, join_relids))continue ; /* not computable yet, or wrong child */ if (bms_is_subset(cur_em->em_relids, outer_relids))else if (bms_is_subset(cur_em->em_relids, inner_relids))else /* * First , select the joinclause if needed . We can equate any one outer * member to any one inner member , but we have to find a datatype * combination for which an opfamily member operator exists . If we have * choices , we prefer simple Var members ( possibly with RelabelType ) since * these are ( a ) cheapest to compute at runtime and ( b ) most likely to * have useful statistics . Also , prefer operators that are also * hashjoinable . if (outer_members && inner_members)int best_score = -1 ;int score;if (!OidIsValid(eq_op))continue ;0 ;if (IsA(outer_em->em_expr, Var) ||if (IsA(inner_em->em_expr, Var) ||if (op_hashjoinable(eq_op,if (score > best_score)if (best_score == 3 )break ; /* no need to look further */ if (best_score == 3 )break ; /* no need to look further */ if (best_score < 0 )/* failed... */ true ;return NIL;/* * Create clause , setting parent_ec to mark it as redundant with other * joinclauses /* * Now deal with building restrictions for any expressions that involve * Vars from both sides of the join . We have to equate all of these to * each other as well as to at least one old member ( if any ) . * * XXX as in generate_base_implied_equalities_no_const , we could be a lot * smarter here to avoid unnecessary failures in cross - type situations . * For now , use the same left - to - right method used there . if (new_members)/* For now, arbitrarily take the first old_member as the one to use */ if (old_members)if (prev_em != NULL)if (!OidIsValid(eq_op))/* failed... */ true ;return NIL;/* do NOT set parent_ec, this qual is not redundant! */ return result;/* * generate_join_implied_equalities cleanup after failure * * Return any original RestrictInfos that are enforceable at this join . * * In the case of a child inner relation , we have to translate the * original RestrictInfos from parent to child Vars . static List *if (bms_is_subset(clause_relids, nominal_join_relids) &&/* * If we have to translate , just brute - force apply adjust_appendrel_attrs * to all the RestrictInfos at once . This will result in returning * RestrictInfos that are not included in EC ' s derived clauses , but there * shouldn ' t be any duplication , and it ' s a sufficiently narrow corner * case that we shouldn ' t sweat too much over it anyway . * * Since inner_rel might be an indirect descendant of the baserel * mentioned in the ec_sources clauses , we have to be prepared to apply * multiple levels of Var translation . if (IS_OTHER_REL(inner_rel) && result != NIL)return result;/* * select_equality_operator * Select a suitable equality operator for comparing two EC members * * Returns InvalidOid if no operator can be found for this datatype combination static Oidif (!OidIsValid(opno))continue ;/* If no barrier quals in query, don't worry about leaky operators */ if (ec->ec_max_security == 0 )return opno;/* Otherwise, insist that selected operators be leakproof */ if (get_func_leakproof(get_opcode(opno)))return opno;return InvalidOid;/* * create_join_clause * Find or make a RestrictInfo comparing the two given EC members * with the given operator ( or , possibly , its commutator , because * the ordering of the operands in the result is not guaranteed ) . * * parent_ec is either equal to ec ( if the clause is a potentially - redundant * join clause ) or NULL ( if not ) . We have to treat this as part of the * match requirements - - - it ' s possible that a clause comparing the same two * EMs is a join clause in one join path and a restriction clause in another . static RestrictInfo *if (rinfo)return rinfo;/* * Not there , so build it , in planner context so we can re - use it . ( Not * important in normal planning , but definitely so in GEQO . ) /* * If either EM is a child , recursively create the corresponding * parent - to - parent clause , so that we can duplicate its rinfo_serial . if (leftem->em_is_child || rightem->em_is_child)/* * If either EM is a child , force the clause ' s clause_relids to include * the relid ( s ) of the child rel . In normal cases it would already , but * not if we are considering appendrel child relations with pseudoconstant * translated variables ( i . e . , UNION ALL sub - selects with constant output * items ) . We must do this so that join_clause_is_movable_into ( ) will * think that the clause should be evaluated at the correct place . if (leftem->em_is_child)if (rightem->em_is_child)/* If it's a child clause, copy the parent's rinfo_serial */ if (parent_rinfo)/* Mark the clause as redundant, or not */ /* * We know the correct values for left_ec / right_ec , ie this particular EC , * so we can just set them directly instead of forcing another lookup . /* Mark it as usable with these EMs */ /* and save it for possible re-use */ return rinfo;/* * reconsider_outer_join_clauses * Re - examine any outer - join clauses that were set aside by * distribute_qual_to_rels ( ) , and see if we can derive any * EquivalenceClasses from them . Then , if they were not made * redundant , push them out into the regular join - clause lists . * * When we have mergejoinable clauses A = B that are outer - join clauses , * we can ' t blindly combine them with other clauses A = C to deduce B = C , * since in fact the " equality " A = B won ' t necessarily hold above the * outer join ( one of the variables might be NULL instead ) . Nonetheless * there are cases where we can add qual clauses using transitivity . * * One case that we look for here is an outer - join clause OUTERVAR = INNERVAR * for which there is also an equivalence clause OUTERVAR = CONSTANT . * It is safe and useful to push a clause INNERVAR = CONSTANT into the * evaluation of the inner ( nullable ) relation , because any inner rows not * meeting this condition will not contribute to the outer - join result anyway . * ( Any outer rows they could join to will be eliminated by the pushed - down * equivalence clause . ) * * Note that the above rule does not work for full outer joins ; nor is it * very interesting to consider cases where the generated equivalence clause * would involve relations outside the outer join , since such clauses couldn ' t * be pushed into the inner side ' s scan anyway . So the restriction to * outervar = pseudoconstant is not really giving up anything . * * For full - join cases , we can only do something useful if it ' s a FULL JOIN * USING and a merged column has an equivalence MERGEDVAR = CONSTANT . * By the time it gets here , the merged column will look like * COALESCE ( LEFTVAR , RIGHTVAR ) * and we will have a full - join clause LEFTVAR = RIGHTVAR that we can match * the COALESCE expression to . In this situation we can push LEFTVAR = CONSTANT * and RIGHTVAR = CONSTANT into the input relations , since any rows not * meeting these conditions cannot contribute to the join result . * * Again , there isn ' t any traction to be gained by trying to deal with * clauses comparing a mergedvar to a non - pseudoconstant . So we can make * use of the EquivalenceClasses to search for matching variables that were * equivalenced to constants . The interesting outer - join clauses were * accumulated for us by distribute_qual_to_rels . * * When we find one of these cases , we implement the changes we want by * generating a new equivalence clause INNERVAR = CONSTANT ( or LEFTVAR , etc ) * and pushing it into the EquivalenceClass structures . This is because we * may already know that INNERVAR is equivalenced to some other var ( s ) , and * we ' d like the constant to propagate to them too . Note that it would be * unsafe to merge any existing EC for INNERVAR with the OUTERVAR ' s EC - - - * that could result in propagating constant restrictions from * INNERVAR to OUTERVAR , which would be very wrong . * * It ' s possible that the INNERVAR is also an OUTERVAR for some other * outer - join clause , in which case the process can be repeated . So we repeat * looping over the lists of clauses until no further deductions can be made . * Whenever we do make a deduction , we remove the generating clause from the * lists , since we don ' t want to make the same deduction twice . * * If we don ' t find any match for a set - aside outer join clause , we must * throw it back into the regular joinclause processing by passing it to * distribute_restrictinfo_to_rels ( ) . If we do generate a derived clause , * however , the outer - join clause is redundant . We must still put some * clause into the regular processing , because otherwise the join will be * seen as a clauseless join and avoided during join order searching . * We handle this by generating a constant - TRUE clause that is marked with * the same required_relids etc as the removed outer - join clause , thus * making it a join clause between the correct relations . void bool found;/* Outer loop repeats until we find no more deductions */ do false ;/* Process the LEFT JOIN clauses */ if (reconsider_outer_join_clause(root, ojcinfo, true ))true ;/* remove it from the list */ /* throw back a dummy replacement clause (see notes above) */ true , false ),false , /* pseudoconstant */ 0 , /* security_level */ /* Process the RIGHT JOIN clauses */ if (reconsider_outer_join_clause(root, ojcinfo, false ))true ;/* remove it from the list */ /* throw back a dummy replacement clause (see notes above) */ true , false ),false , /* pseudoconstant */ 0 , /* security_level */ /* Process the FULL JOIN clauses */ if (reconsider_full_join_clause(root, ojcinfo))true ;/* remove it from the list */ /* throw back a dummy replacement clause (see notes above) */ true , false ),false , /* pseudoconstant */ 0 , /* security_level */ while (found);/* Now, any remaining clauses have to be thrown back */ /* * reconsider_outer_join_clauses for a single LEFT / RIGHT JOIN clause * * Returns true if we were able to propagate a constant through the clause . static bool bool outer_on_left)/* Extract needed info from the clause */ if (outer_on_left)else /* Scan EquivalenceClasses for a match to outervar */ bool match;/* We don't expect any children yet */ /* Ignore EC unless it contains pseudoconstants */ if (!cur_ec->ec_has_const)continue ;/* Never match to a volatile EC */ if (cur_ec->ec_has_volatile)continue ;/* It has to match the outer-join clause as to semantics, too */ if (collation != cur_ec->ec_collation)continue ;if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))continue ;/* Does it contain a match to outervar? */ false ;/* Child members should not exist in ec_members */ if (equal(outervar, cur_em->em_expr))true ;break ;if (!match)continue ; /* no match, so ignore this EC */ /* * Yes it does ! Try to generate a clause INNERVAR = CONSTANT for each * CONSTANT in the EC . Note that we must succeed with at least one * constant before we can decide to throw away the outer - join clause . false ;if (!cur_em->em_is_const)continue ; /* ignore non-const members */ if (!OidIsValid(eq_op))continue ; /* can't generate equality */ /* This equality holds within the OJ's child JoinDomain */ if (process_equivalence(root, &newrinfo, jdomain))true ;/* * If we were able to equate INNERVAR to any constant , report success . * Otherwise , fall out of the search loop , since we know the OUTERVAR * appears in at most one EC . if (match)return true ;else break ;return false ; /* failed to make any deduction */ /* * reconsider_outer_join_clauses for a single FULL JOIN clause * * Returns true if we were able to propagate a constant through the clause . static bool /* Extract needed info from the clause */ bool match;bool matchleft;bool matchright;int coal_idx = -1 ;/* We don't expect any children yet */ /* Ignore EC unless it contains pseudoconstants */ if (!cur_ec->ec_has_const)continue ;/* Never match to a volatile EC */ if (cur_ec->ec_has_volatile)continue ;/* It has to match the outer-join clause as to semantics, too */ if (collation != cur_ec->ec_collation)continue ;if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))continue ;/* * Does it contain a COALESCE ( leftvar , rightvar ) construct ? * * We can assume the COALESCE ( ) inputs are in the same order as the * join clause , since both were automatically generated in the cases * we care about . * * XXX currently this may fail to match in cross - type cases because * the COALESCE will contain typecast operations while the join clause * may not ( if there is a cross - type mergejoin operator available for * the two column types ) . Is it OK to strip implicit coercions from * the COALESCE arguments ? false ;/* Child members should not exist in ec_members */ if (IsA(coal_em->em_expr, CoalesceExpr))if (list_length(cexpr->args) != 2 )continue ;/* * The COALESCE arguments will be marked as possibly nulled by * the full join , while we wish to generate clauses that apply * to the join ' s inputs . So we must strip the join from the * nullingrels fields of cfirst / csecond before comparing them * to leftvar / rightvar . ( Perhaps with a less hokey * representation for FULL JOIN USING output columns , this * wouldn ' t be needed ? ) if (equal(leftvar, cfirst) && equal(rightvar, csecond))true ;break ;if (!match)continue ; /* no match, so ignore this EC */ /* * Yes it does ! Try to generate clauses LEFTVAR = CONSTANT and * RIGHTVAR = CONSTANT for each CONSTANT in the EC . Note that we must * succeed with at least one constant for each var before we can * decide to throw away the outer - join clause . false ;if (!cur_em->em_is_const)continue ; /* ignore non-const members */ if (OidIsValid(eq_op))/* This equality holds within the lefthand child JoinDomain */ if (process_equivalence(root, &newrinfo, jdomain))true ;if (OidIsValid(eq_op))/* This equality holds within the righthand child JoinDomain */ if (process_equivalence(root, &newrinfo, jdomain))true ;/* * If we were able to equate both vars to constants , we ' re done , and * we can throw away the full - join clause as redundant . Moreover , we * can remove the COALESCE entry from the EC , since the added * restrictions ensure it will always have the expected value . ( We * don ' t bother trying to update ec_relids or ec_sources . ) if (matchleft && matchright)return true ;/* * Otherwise , fall out of the search loop , since we know the COALESCE * appears in at most one EC ( XXX might stop being true if we allow * stripping of coercions above ? ) break ;return false ; /* failed to make any deduction */ /* * rebuild_eclass_attr_needed * Put back attr_needed bits for Vars / PHVs needed for join eclasses . * * This is used to rebuild attr_needed / ph_needed sets after removal of a * useless outer join . It should match what * generate_base_implied_equalities_no_const did , except that we call * add_vars_to_attr_needed not add_vars_to_targetlist . void /* * We don ' t expect any EC child members to exist at this point . Ensure * that ' s the case , otherwise , we might be getting asked to do * something this function hasn ' t been coded for . /* Need do anything only for a multi-member, no-const EC. */ if (list_length(ec->ec_members) > 1 && !ec->ec_has_const)/* * find_join_domain * Find the highest JoinDomain enclosed within the given relid set . * * ( We could avoid this search at the cost of complicating APIs elsewhere , * which doesn ' t seem worth it . ) static JoinDomain *if (bms_is_subset(jdomain->jd_relids, relids))return jdomain;"failed to find appropriate JoinDomain" );return NULL; /* keep compiler quiet */ /* * exprs_known_equal * Detect whether two expressions are known equal due to equivalence * relationships . * * If opfamily is given , the expressions must be known equal per the semantics * of that opfamily ( note it has to be a btree opfamily , since those are the * only opfamilies equivclass . c deals with ) . If opfamily is InvalidOid , we ' ll * return true if they ' re equal according to any opfamily , which is fuzzy but * OK for estimation purposes . * * Note : does not bother to check for " equal ( item1 , item2 ) " ; caller must * check that case if it ' s possible to pass identical items . bool bool item1member = false ;bool item2member = false ;/* Never match to a volatile EC */ if (ec->ec_has_volatile)continue ;/* * It ' s okay to consider ec_broken ECs here . Brokenness just means we * couldn ' t derive all the implied clauses we ' d have liked to ; it does * not invalidate our knowledge that the members are equal . /* Ignore if this EC doesn't use specified opfamily */ if (OidIsValid(opfamily) &&continue ;/* Ignore children here */ /* Child members should not exist in ec_members */ if (equal(item1, em->em_expr))true ;else if (equal(item2, em->em_expr))true ;/* Exit as soon as equality is proven */ if (item1member && item2member)return true ;return false ;/* * match_eclasses_to_foreign_key_col * See whether a foreign key column match is proven by any eclass . * * If the referenced and referencing Vars of the fkey ' s colno ' th column are * known equal due to any eclass , return that eclass ; otherwise return NULL . * ( In principle there might be more than one matching eclass if multiple * collations are involved , but since collation doesn ' t matter for equality , * we ignore that fine point here . ) This is much like exprs_known_equal , * except for the format of the input . * * On success , we also set fkinfo - > eclass [ colno ] to the matching eclass , * and set fkinfo - > fk_eclass_member [ colno ] to the eclass member for the * referencing Var . int colno)/* compute only if needed */ int i;/* Consider only eclasses mentioning both relations */ 1 ;while ((i = bms_next_member(matching_ecs, i)) >= 0 )/* Never match to a volatile EC */ if (ec->ec_has_volatile)continue ;/* * It ' s okay to consider " broken " ECs here , see exprs_known_equal . * Ignore children here . /* Child members should not exist in ec_members */ /* EM must be a Var, possibly with RelabelType */ while (var && IsA(var, RelabelType))if (!(var && IsA(var, Var)))continue ;/* Match? */ if (var->varno == var1varno && var->varattno == var1attno)else if (var->varno == var2varno && var->varattno == var2attno)/* Have we found both PK and FK column in this EC? */ if (item1_em && item2_em)/* * Succeed if eqop matches EC ' s opfamilies . We could test * this before scanning the members , but it ' s probably cheaper * to test for member matches first . if (opfamilies == NIL) /* compute if we didn't already */ if (equal(opfamilies, ec->ec_opfamilies))return ec;/* Otherwise, done with this EC, move on to the next */ break ;return NULL;/* * find_derived_clause_for_ec_member * Search for a previously - derived clause mentioning the given EM . * * The eclass should be an ec_has_const EC , of which the EM is a non - const * member . This should ensure there is just one derived clause mentioning * the EM ( and equating it to a constant ) . * Returns NULL if no such clause can be found . return ec_search_derived_clause_for_ems(root, ec, em, NULL, NULL);/* * add_child_rel_equivalences * Search for EC members that reference the root parent of child_rel , and * add transformed members referencing the child_rel . * * Note that this function won ' t be called at all unless we have at least some * reason to believe that the EC members it generates will be useful . * * parent_rel and child_rel could be derived from appinfo , but since the * caller has already computed them , we might as well just pass them in . * * The passed - in AppendRelInfo is not used when the parent_rel is not a * top - level baserel , since it shows the mapping from the parent_rel but * we need to translate EC expressions that refer to the top - level parent . * Using it is faster than using adjust_appendrel_attrs_multilevel ( ) , though , * so we prefer it when we can . void int i;/* * EC merging should be complete already , so we can use the parent rel ' s * eclass_indexes to avoid searching all of root - > eq_classes . 1 ;while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0 )/* * If this EC contains a volatile expression , then generating child * EMs would be downright dangerous , so skip it . We rely on a * volatile EC having only one EM . if (cur_ec->ec_has_volatile)continue ;/* Sanity check eclass_indexes only contain ECs for parent_rel */ if (cur_em->em_is_const)continue ; /* ignore consts here */ /* Child members should not exist in ec_members */ /* * Consider only members that reference and can be computed at * child ' s topmost parent rel . In particular we want to exclude * parent - rel Vars that have nonempty varnullingrels . Translating * those might fail , if the transformed expression wouldn ' t be a * simple Var ; and in any case it wouldn ' t produce a member that * has any use in creating plans for the child rel . if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&/* OK, generate transformed child version */ if (parent_rel->reloptkind == RELOPT_BASEREL)/* Simple single-level transformation */ 1 , &appinfo);else /* Must do multi-level transformation */ /* * Transform em_relids to match . Note we do * not * do * pull_varnos ( child_expr ) here , as for example the * transformation might have substituted a constant , but we * don ' t want the child member to be marked as constant . /* * add_child_join_rel_equivalences * Like add_child_rel_equivalences ( ) , but for joinrels * * Here we find the ECs relevant to the top parent joinrel and add transformed * member expressions that refer to this child joinrel . * * Note that this function won ' t be called at all unless we have at least some * reason to believe that the EC members it generates will be useful . void int nappinfos, AppendRelInfo **appinfos,int i;/* We need consider only ECs that mention the parent joinrel */ /* * If we ' re being called during GEQO join planning , we still have to * create any new EC members in the main planner context , to avoid having * a corrupt EC data structure after the GEQO context is reset . This is * problematic since we ' ll leak memory across repeated GEQO cycles . For * now , though , bloat is better than crash . If it becomes a real issue * we ' ll have to do something to avoid generating duplicate EC members . 1 ;while ((i = bms_next_member(matching_ecs, i)) >= 0 )/* * If this EC contains a volatile expression , then generating child * EMs would be downright dangerous , so skip it . We rely on a * volatile EC having only one EM . if (cur_ec->ec_has_volatile)continue ;/* Sanity check on get_eclass_indexes_for_relids result */ if (cur_em->em_is_const)continue ; /* ignore consts here */ /* Child members should not exist in ec_members */ /* * We may ignore expressions that reference a single baserel , * because add_child_rel_equivalences should have handled them . if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)continue ;/* Does this member reference child's topmost parent rel? */ if (bms_overlap(cur_em->em_relids, top_parent_relids))/* Yes, generate transformed child version */ if (parent_joinrel->reloptkind == RELOPT_JOINREL)/* Simple single-level transformation */ else /* Must do multi-level transformation */ /* * Transform em_relids to match . Note we do * not * do * pull_varnos ( child_expr ) here , as for example the * transformation might have substituted a constant , but we * don ' t want the child member to be marked as constant . /* * Add new child member to the EquivalenceClass . Because this * is a RELOPT_OTHER_JOINREL which has multiple component * relids , there is no ideal place to store these members in * the class . Ordinarily , child members are stored in the * ec_childmembers [ ] array element corresponding to their * relid , however , here we have multiple component relids , so * there ' s no single ec_childmembers [ ] array element to store * this member . So that we still correctly find this member * in loops iterating over an EquivalenceMemberIterator , we * opt to store the member in the ec_childmembers array in * only the first component relid slot of the array . This * allows the member to be found , providing callers of * setup_eclass_member_iterator ( ) specify all the component * relids for the RELOPT_OTHER_JOINREL , which they do . If we * opted to store the member in each ec_childmembers [ ] element * for all the component relids , then that would just result * in eclass_member_iterator_next ( ) finding the member * multiple times , which is a waste of effort . 1 ,1 ));/* * add_setop_child_rel_equivalences * Add equivalence members for each non - resjunk target in ' child_tlist ' * to the EquivalenceClass in the corresponding setop_pathkey ' s pk_eclass . * * ' root ' is the PlannerInfo belonging to the top - level set operation . * ' child_rel ' is the RelOptInfo of the child relation we ' re adding * EquivalenceMembers for . * ' child_tlist ' is the target list for the setop child relation . The target * list expressions are what we add as EquivalenceMembers . * ' setop_pathkeys ' is a list of PathKeys which must contain an entry for each * non - resjunk target in ' child_tlist ' . void if (tle->resjunk)continue ;if (lc2 == NULL)"too few pathkeys for set operation" );/* * We can safely pass the parent member as the first member in the * ec_members list as this is added first in generate_union_paths , * likewise , the JoinDomain can be that of the initial member of the * Pathkey ' s EquivalenceClass . We pass - 1 for ec_index since we * maintain the eclass_indexes for the child_rel after the loop . 1 ,/* * transformSetOperationStmt ( ) ensures that the targetlist never contains * any resjunk columns , so all eclasses that exist in ' root ' must have * received a new member in the loop above . Add them to the child_rel ' s * eclass_indexes . 0 ,1 );/* * setup_eclass_member_iterator * Setup an EquivalenceMemberIterator ' it ' to iterate over all parent * EquivalenceMembers and child members belonging to the given ' ec ' . * * This iterator returns : * - All parent members stored directly in ec_members for ' ec ' , and ; * - Any child member added to the given ec by add_child_eq_member ( ) where * the child_relid specified in the add_child_eq_member ( ) call is a member * of the ' child_relids ' parameter . * * Note : * The given ' child_relids ' must remain allocated and not be changed for the * lifetime of the iterator . * * Parameters : * ' it ' is a pointer to the iterator to set up . Normally stack allocated . * ' ec ' is the EquivalenceClass from which to iterate members for . * ' child_relids ' is the relids to return child members for . void /* no need to set this if the class has no child members array set */ 1 ;/* * eclass_member_iterator_next * Get the next EquivalenceMember from the EquivalenceMemberIterator ' it ' , * as setup by setup_eclass_member_iterator ( ) . NULL is returned if there * are no members left , after which callers must not call * eclass_member_iterator_next ( ) again for the given iterator . while (it->current_list != NULL)while (it->current_cell != NULL)return em;/* Search for the next list to return members from */ while ((it->current_relid = bms_next_member(it->child_relids, it->current_relid)) > 0 )/* * Be paranoid in case we ' re given relids above what we ' ve sized * the ec_childmembers array to . if (it->current_relid >= it->ec->ec_childmembers_size)return NULL;/* If there are members in this list, use it. */ if (it->current_list != NIL)/* point current_cell to the head of this list */ goto nextcell;return NULL;return NULL;/* * generate_implied_equalities_for_column * Create EC - derived joinclauses usable with a specific column . * * This is used by indxpath . c to extract potentially indexable joinclauses * from ECs , and can be used by foreign data wrappers for similar purposes . * We assume that only expressions in Vars of a single table are of interest , * but the caller provides a callback function to identify exactly which * such expressions it would like to know about . * * We assume that any given table / index column could appear in only one EC . * ( This should be true in all but the most pathological cases , and if it * isn ' t , we stop on the first match anyway . ) Therefore , what we return * is a redundant list of clauses equating the table / index column to each of * the other - relation values it is known to be equal to . Any one of * these clauses can be used to create a parameterized path , and there * is no value in using more than one . ( But it * is * worthwhile to create * a separate parameterized path for each one , since that leads to different * join orders . ) * * The caller can pass a Relids set of rels we aren ' t interested in joining * to , so as to save the work of creating useless clauses . void *callback_arg,bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);int i;/* Should be OK to rely on eclass_indexes */ /* Indexes are available only on base or "other" member relations. */ /* If it's a child rel, we'll need to know what its parent(s) are */ if (is_child_rel)else /* not used, but keep compiler quiet */ 1 ;while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0 )/* Sanity check eclass_indexes only contain ECs for rel */ /* * Won ' t generate joinclauses if const or single - member ( the latter * test covers the volatile case too ) if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1 )continue ;/* * Scan members , looking for a match to the target column . Note that * child EC members are considered , but only when they belong to the * target relation . ( Unlike regular members , the same expression * could be a child member of more than one EC . Therefore , it ' s * potentially order - dependent which EC a child relation ' s target * column gets matched to . This is annoying but it only happens in * corner cases , so for now we live with just reporting the first * match . See also get_eclass_for_sort_expr . ) while ((cur_em = eclass_member_iterator_next(&it)) != NULL)if (bms_equal(cur_em->em_relids, rel->relids) &&break ;if (!cur_em)continue ;/* * Found our match . Scan the other EC members and attempt to generate * joinclauses . Ignore children here . /* Child members should not exist in ec_members */ /* Make sure it'll be a join to a different rel */ if (other_em == cur_em ||continue ;/* Forget it if caller doesn't want joins to this rel */ if (bms_overlap(other_em->em_relids, prohibited_rels))continue ;/* * Also , if this is a child rel , avoid generating a useless join * to its parent rel ( s ) . if (is_child_rel &&continue ;if (!OidIsValid(eq_op))continue ;/* set parent_ec to mark as redundant with other joinclauses */ /* * If somehow we failed to create any join clauses , we might as well * keep scanning the ECs for another match . But if we did make any , * we ' re done , because we don ' t want to return non - redundant clauses . if (result)break ;return result;/* * have_relevant_eclass_joinclause * Detect whether there is an EquivalenceClass that could produce * a joinclause involving the two given relations . * * This is essentially a very cut - down version of * generate_join_implied_equalities ( ) . Note it ' s OK to occasionally say " yes " * incorrectly . Hence we don ' t bother with details like whether the lack of a * cross - type operator might prevent the clause from actually being generated . * False negatives are not always fatal either : they will discourage , but not * completely prevent , investigation of particular join pathways . bool int i;/* * Examine only eclasses mentioning both rel1 and rel2 . * * Note that we do not consider the possibility of an eclass generating * " join " clauses that mention just one of the rels plus an outer join * that could be formed from them . Although such clauses must be * correctly enforced when we form the outer join , they don ' t seem like * sufficient reason to prioritize this join over other ones . The join * ordering rules will force the join to be made when necessary . 1 ;while ((i = bms_next_member(matching_ecs, i)) >= 0 )/* * Sanity check that get_common_eclass_indexes gave only ECs * containing both rels . /* * Won ' t generate joinclauses if single - member ( this test covers the * volatile case too ) if (list_length(ec->ec_members) <= 1 )continue ;/* * We do not need to examine the individual members of the EC , because * all that we care about is whether each rel overlaps the relids of * at least one member , and get_common_eclass_indexes ( ) and the single * member check above are sufficient to prove that . ( As with * have_relevant_joinclause ( ) , it is not necessary that the EC be able * to form a joinclause relating exactly the two given rels , only that * it be able to form a joinclause mentioning both , and this will * surely be true if both of them overlap ec_relids . ) * * Note we don ' t test ec_broken ; if we did , we ' d need a separate code * path to look through ec_sources . Checking the membership anyway is * OK as a possibly - overoptimistic heuristic . * * We don ' t test ec_has_const either , even though a const eclass won ' t * generate real join clauses . This is because if we had " WHERE a . x = * b . y and a . x = 42 " , it is worth considering a join between a and b , * since the join result is likely to be small even though it ' ll end * up being an unqualified nestloop . return true ;return false ;/* * has_relevant_eclass_joinclause * Detect whether there is an EquivalenceClass that could produce * a joinclause involving the given relation and anything else . * * This is the same as have_relevant_eclass_joinclause with the other rel * implicitly defined as " everything else in the query " . bool int i;/* Examine only eclasses mentioning rel1 */ 1 ;while ((i = bms_next_member(matched_ecs, i)) >= 0 )/* * Won ' t generate joinclauses if single - member ( this test covers the * volatile case too ) if (list_length(ec->ec_members) <= 1 )continue ;/* * Per the comment in have_relevant_eclass_joinclause , it ' s sufficient * to find an EC that mentions both this rel and some other rel . if (!bms_is_subset(ec->ec_relids, rel1->relids))return true ;return false ;/* * eclass_useful_for_merging * Detect whether the EC could produce any mergejoinable join clauses * against the specified relation . * * This is just a heuristic test and doesn ' t have to be exact ; it ' s better * to say " yes " incorrectly than " no " . Hence we don ' t bother with details * like whether the lack of a cross - type operator might prevent the clause * from actually being generated . bool /* * Won ' t generate joinclauses if const or single - member ( the latter test * covers the volatile case too ) if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1 )return false ;/* * Note we don ' t test ec_broken ; if we did , we ' d need a separate code path * to look through ec_sources . Checking the members anyway is OK as a * possibly - overoptimistic heuristic . /* If specified rel is a child, we must consider the topmost parent rel */ if (IS_OTHER_REL(rel))else /* If rel already includes all members of eclass, no point in searching */ if (bms_is_subset(eclass->ec_relids, relids))return false ;/* * To join , we need a member not in the given rel . Ignore children here . /* Child members should not exist in ec_members */ if (!bms_overlap(cur_em->em_relids, relids))return true ;return false ;/* * is_redundant_derived_clause * Test whether rinfo is derived from same EC as any clause in clauselist ; * if so , it can be presumed to represent a condition that ' s redundant * with that member of the list . bool /* Fail if it's not a potentially-redundant clause from some EC */ if (parent_ec == NULL)return false ;if (otherrinfo->parent_ec == parent_ec)return true ;return false ;/* * is_redundant_with_indexclauses * Test whether rinfo is redundant with any clause in the IndexClause * list . Here , for convenience , we test both simple identity and * whether it is derived from the same EC as any member of the list . bool /* If indexclause is lossy, it won't enforce the condition exactly */ if (iclause->lossy)continue ;/* Match if it's same clause (pointer equality should be enough) */ if (rinfo == otherrinfo)return true ;/* Match if derived from same EC */ if (parent_ec && otherrinfo->parent_ec == parent_ec)return true ;/* * No need to look at the derived clauses in iclause - > indexquals ; they * couldn ' t match if the parent clause didn ' t . return false ;/* * get_eclass_indexes_for_relids * Build and return a Bitmapset containing the indexes into root ' s * eq_classes list for all eclasses that mention any of these relids static Bitmapset *int i = -1 ;/* Should be OK to rely on eclass_indexes */ while ((i = bms_next_member(relids, i)) > 0 )/* ignore the RTE_GROUP RTE */ if (i == root->group_rtindex)continue ;if (rel == NULL) /* must be an outer join */ continue ;return ec_indexes;/* * get_common_eclass_indexes * Build and return a Bitmapset containing the indexes into root ' s * eq_classes list for all eclasses that mention rels in both * relids1 and relids2 . static Bitmapset *int relid;/* * We can get away with just using the relation ' s eclass_indexes directly * when relids2 is a singleton set . if (bms_get_singleton_member(relids2, &relid))else /* Calculate and return the common EC indexes, recycling the left input. */ return bms_int_members(rel1ecs, rel2ecs);/* * ec_build_derives_hash * Construct the auxiliary hash table for derived clause lookups . static void /* * Create the hash table . * * We pass list_length ( ec - > ec_derives_list ) as the initial size . * Simplehash will divide this by the fillfactor ( typically 0 . 9 ) and round * up to the next power of two , so this will usually give us at least 64 * buckets around the threshold . That avoids immediate resizing without * hardcoding a specific size . /* * ec_add_derived_clause * Add a clause to the set of derived clauses for the given * EquivalenceClass . Always appends to ec_derives_list ; also adds * to ec_derives_hash if it exists . * * Also asserts expected invariants of derived clauses . static void /* * Constant , if present , is always placed on the RHS ; see * generate_base_implied_equalities_const ( ) . LHS is never a constant . /* * Clauses containing a constant are never considered redundant , so * parent_ec is not set . if (ec->ec_derives_hash)/* * ec_add_derived_clauses * Add a list of clauses to the set of clauses derived from the given * EquivalenceClass ; adding to the list and hash table if needed . * * This function is similar to ec_add_derived_clause ( ) but optimized for adding * multiple clauses at a time to the ec_derives_list . The assertions from * ec_add_derived_clause ( ) are not repeated here , as the input clauses are * assumed to have already been validated . static void if (ec->ec_derives_hash)/* * fill_ec_derives_key * Compute a canonical key for ec_derives_hash lookup or insertion . * * Derived clauses are looked up using a pair of EquivalenceMembers and a * parent EquivalenceClass . To avoid storing or searching for both EM orderings , * we canonicalize the key : * * - For clauses involving two non - constant EMs , em1 is set to the EM with lower * memory address and em2 is set to the other one . * - For clauses involving a constant EM , the caller must pass the non - constant * EM as leftem and NULL as rightem ; we then set em1 = NULL and em2 = leftem . static inline void /* Always required for lookup or insertion */ if (rightem == NULL)else if (leftem < rightem)else /* * ec_add_clause_to_derives_hash * Add a derived clause to ec_derives_hash in the given EquivalenceClass . * * Each clause is associated with a canonicalized key . For constant - containing * clauses , only the non - constant EM is used for lookup ; see comments in * fill_ec_derives_key ( ) . static void bool found;/* * Constants are always placed on the RHS ; see * generate_base_implied_equalities_const ( ) . /* * Clauses containing a constant are never considered redundant , so * parent_ec is not set . /* * See fill_ec_derives_key ( ) for details : we use a canonicalized key to * avoid storing both EM orderings . For constant EMs , only the * non - constant EM is included in the key . /* * ec_clear_derived_clauses * Reset ec_derives_list and ec_derives_hash . * * We destroy the hash table explicitly , since it may consume significant * space . The list holds the same set of entries and can become equally large * when thousands of partitions are involved , so we free it as well - - even * though we do not typically free lists . void if (ec->ec_derives_hash)/* * ec_search_clause_for_ems * Search for an existing RestrictInfo that equates the given pair * of EquivalenceMembers , either from ec_sources or ec_derives . * * Returns a clause with matching operands in either given order or commuted * order . We used to require matching operator OIDs , but dropped that since any * semantically different operator here would indicate a broken operator family . * * Returns NULL if no matching clause is found . static RestrictInfo */* Check original source clauses */ if (rinfo->left_em == leftem &&return rinfo;if (rinfo->left_em == rightem &&return rinfo;/* Not found in ec_sources; search derived clauses */ return ec_search_derived_clause_for_ems(root, ec, leftem, rightem,/* * ec_search_derived_clause_for_ems * Search for an existing derived clause between two EquivalenceMembers . * * If the number of derived clauses exceeds a threshold , switch to hash table * lookup ; otherwise , scan ec_derives_list linearly . * * Clauses involving constants are looked up by passing the non - constant EM * as leftem and setting rightem to NULL . In that case , we expect to find a * clause with a constant on the RHS . * * While searching the list , we compare each given EM with both sides of each * clause . But for hash table lookups , we construct a canonicalized key and * perform a single lookup . static RestrictInfo */* Switch to using hash lookup when list grows "too long". */ if (!ec->ec_derives_hash &&/* Perform hash table lookup if available */ if (ec->ec_derives_hash)if (entry)return rinfo;else /* Fallback to linear search over ec_derives_list */ /* Handle special case: lookup by non-const EM alone */ if (!rightem &&return rinfo;if (rinfo->left_em == leftem &&return rinfo;if (rinfo->left_em == rightem &&return rinfo;return NULL;
Messung V0.5 in Prozent C=97 H=94 G=95
¤ Dauer der Verarbeitung: 0.190 Sekunden
(vorverarbeitet am 2026-08-08)
¤ *© Formatika GbR, Deutschland
