X-Git-Url: https://granicus.if.org/sourcecode?a=blobdiff_plain;f=src%2Fbackend%2Foptimizer%2Futil%2Frelnode.c;h=bffd705f183a7beb17c2081defc8676992455365;hb=9f2e211386931f7aee48ffbc2fcaef1632d8329f;hp=d22daa0f638c7677abe51fa0ffebd12c69c5fe4a;hpb=d8733ce674f62f0e13cfc97d0340b43e1906f458;p=postgresql diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index d22daa0f63..bffd705f18 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -3,130 +3,280 @@ * relnode.c * Relation-node lookup/construction routines * - * Portions Copyright (c) 1996-2000, PostgreSQL, Inc + * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.23 2000/02/07 04:41:02 tgl Exp $ + * src/backend/optimizer/util/relnode.c * *------------------------------------------------------------------------- */ #include "postgres.h" #include "optimizer/cost.h" -#include "optimizer/internal.h" -#include "optimizer/joininfo.h" #include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "optimizer/placeholder.h" #include "optimizer/plancat.h" -#include "optimizer/tlist.h" +#include "optimizer/restrictinfo.h" +#include "parser/parsetree.h" +#include "utils/hsearch.h" -static List *new_join_tlist(List *tlist, int first_resdomno); -static List *build_joinrel_restrictlist(RelOptInfo *joinrel, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel); +typedef struct JoinHashEntry +{ + Relids join_relids; /* hash key --- MUST BE FIRST */ + RelOptInfo *join_rel; +} JoinHashEntry; + +static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, + RelOptInfo *input_rel); +static List *build_joinrel_restrictlist(PlannerInfo *root, + RelOptInfo *joinrel, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel); static void build_joinrel_joinlist(RelOptInfo *joinrel, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel); + RelOptInfo *outer_rel, + RelOptInfo *inner_rel); static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list); -static void subbuild_joinrel_joinlist(RelOptInfo *joinrel, - List *joininfo_list); + List *joininfo_list, + List *new_restrictlist); +static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel, + List *joininfo_list, + List *new_joininfo); /* - * get_base_rel - * Returns relation entry corresponding to 'relid', creating a new one - * if necessary. This is for base relations. + * build_simple_rel + * Construct a new RelOptInfo for a base relation or 'other' relation. */ RelOptInfo * -get_base_rel(Query *root, int relid) +build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind) { - List *baserels; RelOptInfo *rel; + RangeTblEntry *rte; - foreach(baserels, root->base_rel_list) - { - rel = (RelOptInfo *) lfirst(baserels); + /* Rel should not exist already */ + Assert(relid > 0 && relid < root->simple_rel_array_size); + if (root->simple_rel_array[relid] != NULL) + elog(ERROR, "rel %d already exists", relid); - /* We know length(rel->relids) == 1 for all members of base_rel_list */ - if (lfirsti(rel->relids) == relid) - return rel; - } + /* Fetch RTE for relation */ + rte = root->simple_rte_array[relid]; + Assert(rte != NULL); - /* No existing RelOptInfo for this base rel, so make a new one */ rel = makeNode(RelOptInfo); - rel->relids = lconsi(relid, NIL); + rel->reloptkind = reloptkind; + rel->relids = bms_make_singleton(relid); rel->rows = 0; rel->width = 0; - rel->targetlist = NIL; + rel->reltargetlist = NIL; rel->pathlist = NIL; - rel->cheapestpath = (Path *) NULL; - rel->pruneable = true; - rel->indexed = false; + rel->cheapest_startup_path = NULL; + rel->cheapest_total_path = NULL; + rel->cheapest_unique_path = NULL; + rel->relid = relid; + rel->rtekind = rte->rtekind; + /* min_attr, max_attr, attr_needed, attr_widths are set below */ + rel->indexlist = NIL; rel->pages = 0; rel->tuples = 0; + rel->subplan = NULL; + rel->subrtable = NIL; + rel->subrowmark = NIL; rel->baserestrictinfo = NIL; + rel->baserestrictcost.startup = 0; + rel->baserestrictcost.per_tuple = 0; rel->joininfo = NIL; - rel->innerjoin = NIL; + rel->has_eclass_joins = false; + rel->index_outer_relids = NULL; + rel->index_inner_paths = NIL; - if (relid < 0) + /* Check type of rtable entry */ + switch (rte->rtekind) { - /* - * If the relation is a materialized relation, assume - * constants for sizes. - */ - rel->pages = _NONAME_RELATION_PAGES_; - rel->tuples = _NONAME_RELATION_TUPLES_; + case RTE_RELATION: + /* Table --- retrieve statistics from the system catalogs */ + get_relation_info(root, rte->relid, rte->inh, rel); + break; + case RTE_SUBQUERY: + case RTE_FUNCTION: + case RTE_VALUES: + case RTE_CTE: + + /* + * Subquery, function, or values list --- set up attr range and + * arrays + * + * Note: 0 is included in range to support whole-row Vars + */ + rel->min_attr = 0; + rel->max_attr = list_length(rte->eref->colnames); + rel->attr_needed = (Relids *) + palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids)); + rel->attr_widths = (int32 *) + palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32)); + break; + default: + elog(ERROR, "unrecognized RTE kind: %d", + (int) rte->rtekind); + break; } - else + + /* Save the finished struct in the query's simple_rel_array */ + root->simple_rel_array[relid] = rel; + + /* + * If this rel is an appendrel parent, recurse to build "other rel" + * RelOptInfos for its children. They are "other rels" because they are + * not in the main join tree, but we will need RelOptInfos to plan access + * to them. + */ + if (rte->inh) { - /* - * Otherwise, retrieve relation statistics from the - * system catalogs. - */ - relation_info(root, relid, - &rel->indexed, &rel->pages, &rel->tuples); - } + ListCell *l; - root->base_rel_list = lcons(rel, root->base_rel_list); + foreach(l, root->append_rel_list) + { + AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l); + + /* append_rel_list contains all append rels; ignore others */ + if (appinfo->parent_relid != relid) + continue; + + (void) build_simple_rel(root, appinfo->child_relid, + RELOPT_OTHER_MEMBER_REL); + } + } return rel; } +/* + * find_base_rel + * Find a base or other relation entry, which must already exist. + */ +RelOptInfo * +find_base_rel(PlannerInfo *root, int relid) +{ + RelOptInfo *rel; + + Assert(relid > 0); + + if (relid < root->simple_rel_array_size) + { + rel = root->simple_rel_array[relid]; + if (rel) + return rel; + } + + elog(ERROR, "no relation entry for relid %d", relid); + + return NULL; /* keep compiler quiet */ +} + +/* + * build_join_rel_hash + * Construct the auxiliary hash table for join relations. + */ +static void +build_join_rel_hash(PlannerInfo *root) +{ + HTAB *hashtab; + HASHCTL hash_ctl; + ListCell *l; + + /* Create the hash table */ + MemSet(&hash_ctl, 0, sizeof(hash_ctl)); + hash_ctl.keysize = sizeof(Relids); + hash_ctl.entrysize = sizeof(JoinHashEntry); + hash_ctl.hash = bitmap_hash; + hash_ctl.match = bitmap_match; + hash_ctl.hcxt = CurrentMemoryContext; + hashtab = hash_create("JoinRelHashTable", + 256L, + &hash_ctl, + HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); + + /* Insert all the already-existing joinrels */ + foreach(l, root->join_rel_list) + { + RelOptInfo *rel = (RelOptInfo *) lfirst(l); + JoinHashEntry *hentry; + bool found; + + hentry = (JoinHashEntry *) hash_search(hashtab, + &(rel->relids), + HASH_ENTER, + &found); + Assert(!found); + hentry->join_rel = rel; + } + + root->join_rel_hash = hashtab; +} + /* * find_join_rel - * Returns relation entry corresponding to 'relids' (a list of RT indexes), + * Returns relation entry corresponding to 'relids' (a set of RT indexes), * or NULL if none exists. This is for join relations. - * - * Note: there is probably no good reason for this to be called from - * anywhere except get_join_rel, but keep it as a separate routine - * just in case. */ -static RelOptInfo * -find_join_rel(Query *root, Relids relids) +RelOptInfo * +find_join_rel(PlannerInfo *root, Relids relids) { - List *joinrels; + /* + * Switch to using hash lookup when list grows "too long". The threshold + * is arbitrary and is known only here. + */ + if (!root->join_rel_hash && list_length(root->join_rel_list) > 32) + build_join_rel_hash(root); - foreach(joinrels, root->join_rel_list) + /* + * Use either hashtable lookup or linear search, as appropriate. + * + * Note: the seemingly redundant hashkey variable is used to avoid taking + * the address of relids; unless the compiler is exceedingly smart, doing + * so would force relids out of a register and thus probably slow down the + * list-search case. + */ + if (root->join_rel_hash) { - RelOptInfo *rel = (RelOptInfo *) lfirst(joinrels); + Relids hashkey = relids; + JoinHashEntry *hentry; + + hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, + &hashkey, + HASH_FIND, + NULL); + if (hentry) + return hentry->join_rel; + } + else + { + ListCell *l; - if (sameseti(rel->relids, relids)) - return rel; + foreach(l, root->join_rel_list) + { + RelOptInfo *rel = (RelOptInfo *) lfirst(l); + + if (bms_equal(rel->relids, relids)) + return rel; + } } return NULL; } /* - * get_join_rel + * build_join_rel * Returns relation entry corresponding to the union of two given rels, * creating a new relation entry if none already exists. * + * 'joinrelids' is the Relids set that uniquely identifies the join * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be * joined + * 'sjinfo': join context info * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr * receives the list of RestrictInfo nodes that apply to this * particular pair of joinable relations. @@ -135,37 +285,30 @@ find_join_rel(Query *root, Relids relids) * duplicated calculation of the restrictlist... */ RelOptInfo * -get_join_rel(Query *root, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel, - List **restrictlist_ptr) +build_join_rel(PlannerInfo *root, + Relids joinrelids, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + SpecialJoinInfo *sjinfo, + List **restrictlist_ptr) { - List *joinrelids; RelOptInfo *joinrel; List *restrictlist; - List *new_outer_tlist; - List *new_inner_tlist; - - /* We should never try to join two overlapping sets of rels. */ - Assert(nonoverlap_setsi(outer_rel->relids, inner_rel->relids)); /* * See if we already have a joinrel for this set of base rels. - * - * nconc(listCopy(x), y) is an idiom for making a new list without - * changing either input list. */ - joinrelids = nconc(listCopy(outer_rel->relids), inner_rel->relids); joinrel = find_join_rel(root, joinrelids); if (joinrel) { /* - * Yes, so we only need to figure the restrictlist for this - * particular pair of component relations. + * Yes, so we only need to figure the restrictlist for this particular + * pair of component relations. */ if (restrictlist_ptr) - *restrictlist_ptr = build_joinrel_restrictlist(joinrel, + *restrictlist_ptr = build_joinrel_restrictlist(root, + joinrel, outer_rel, inner_rel); return joinrel; @@ -175,100 +318,166 @@ get_join_rel(Query *root, * Nope, so make one. */ joinrel = makeNode(RelOptInfo); - joinrel->relids = joinrelids; + joinrel->reloptkind = RELOPT_JOINREL; + joinrel->relids = bms_copy(joinrelids); joinrel->rows = 0; joinrel->width = 0; - joinrel->targetlist = NIL; + joinrel->reltargetlist = NIL; joinrel->pathlist = NIL; - joinrel->cheapestpath = (Path *) NULL; - joinrel->pruneable = true; - joinrel->indexed = false; + joinrel->cheapest_startup_path = NULL; + joinrel->cheapest_total_path = NULL; + joinrel->cheapest_unique_path = NULL; + joinrel->relid = 0; /* indicates not a baserel */ + joinrel->rtekind = RTE_JOIN; + joinrel->min_attr = 0; + joinrel->max_attr = 0; + joinrel->attr_needed = NULL; + joinrel->attr_widths = NULL; + joinrel->indexlist = NIL; joinrel->pages = 0; joinrel->tuples = 0; + joinrel->subplan = NULL; + joinrel->subrtable = NIL; + joinrel->subrowmark = NIL; joinrel->baserestrictinfo = NIL; + joinrel->baserestrictcost.startup = 0; + joinrel->baserestrictcost.per_tuple = 0; joinrel->joininfo = NIL; - joinrel->innerjoin = NIL; + joinrel->has_eclass_joins = false; + joinrel->index_outer_relids = NULL; + joinrel->index_inner_paths = NIL; /* - * Create a new tlist by removing irrelevant elements from both tlists - * of the outer and inner join relations and then merging the results - * together. + * Create a new tlist containing just the vars that need to be output from + * this join (ie, are needed for higher joinclauses or final output). * - * NOTE: the tlist order for a join rel will depend on which pair - * of outer and inner rels we first try to build it from. But the - * contents should be the same regardless. - * - * XXX someday: consider pruning vars from the join's targetlist - * if they are needed only to evaluate restriction clauses of this - * join, and will never be accessed at higher levels of the plantree. + * NOTE: the tlist order for a join rel will depend on which pair of outer + * and inner rels we first try to build it from. But the contents should + * be the same regardless. */ - new_outer_tlist = new_join_tlist(outer_rel->targetlist, 1); - new_inner_tlist = new_join_tlist(inner_rel->targetlist, - length(new_outer_tlist) + 1); - joinrel->targetlist = nconc(new_outer_tlist, new_inner_tlist); + build_joinrel_tlist(root, joinrel, outer_rel); + build_joinrel_tlist(root, joinrel, inner_rel); + add_placeholders_to_joinrel(root, joinrel); /* - * Construct restrict and join clause lists for the new joinrel. - * (The caller might or might not need the restrictlist, but - * I need it anyway for set_joinrel_size_estimates().) + * Construct restrict and join clause lists for the new joinrel. (The + * caller might or might not need the restrictlist, but I need it anyway + * for set_joinrel_size_estimates().) */ - restrictlist = build_joinrel_restrictlist(joinrel, outer_rel, inner_rel); + restrictlist = build_joinrel_restrictlist(root, joinrel, + outer_rel, inner_rel); if (restrictlist_ptr) *restrictlist_ptr = restrictlist; build_joinrel_joinlist(joinrel, outer_rel, inner_rel); + /* + * This is also the right place to check whether the joinrel has any + * pending EquivalenceClass joins. + */ + joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel); + /* * Set estimates of the joinrel's size. */ set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, - restrictlist); + sjinfo, restrictlist); /* - * Add the joinrel to the front of the query's joinrel list. - * (allpaths.c depends on this ordering!) + * Add the joinrel to the query's joinrel list, and store it into the + * auxiliary hashtable if there is one. NB: GEQO requires us to append + * the new joinrel to the end of the list! */ - root->join_rel_list = lcons(joinrel, root->join_rel_list); + root->join_rel_list = lappend(root->join_rel_list, joinrel); + + if (root->join_rel_hash) + { + JoinHashEntry *hentry; + bool found; + + hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, + &(joinrel->relids), + HASH_ENTER, + &found); + Assert(!found); + hentry->join_rel = joinrel; + } + + /* + * Also, if dynamic-programming join search is active, add the new joinrel + * to the appropriate sublist. Note: you might think the Assert on number + * of members should be for equality, but some of the level 1 rels might + * have been joinrels already, so we can only assert <=. + */ + if (root->join_rel_level) + { + Assert(root->join_cur_level > 0); + Assert(root->join_cur_level <= bms_num_members(joinrel->relids)); + root->join_rel_level[root->join_cur_level] = + lappend(root->join_rel_level[root->join_cur_level], joinrel); + } return joinrel; } /* - * new_join_tlist - * Builds a join relation's target list by keeping those elements that - * will be in the final target list and any other elements that are still - * needed for future joins. For a target list entry to still be needed - * for future joins, its 'joinlist' field must not be empty after removal - * of all relids in 'other_relids'. - * - * XXX the above comment refers to code that is long dead and gone; - * we don't keep track of joinlists for individual targetlist entries - * anymore. For now, all vars present in either input tlist will be - * emitted in the join's tlist. + * build_joinrel_tlist + * Builds a join relation's target list from an input relation. + * (This is invoked twice to handle the two input relations.) * - * 'tlist' is the target list of one of the join relations - * 'first_resdomno' is the resdom number to use for the first created - * target list entry + * The join's targetlist includes all Vars of its member relations that + * will still be needed above the join. This subroutine adds all such + * Vars from the specified input rel's tlist to the join rel's tlist. * - * Returns the new target list. + * We also compute the expected width of the join's output, making use + * of data that was cached at the baserel level by set_rel_width(). */ -static List * -new_join_tlist(List *tlist, - int first_resdomno) +static void +build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, + RelOptInfo *input_rel) { - int resdomno = first_resdomno - 1; - List *t_list = NIL; - List *i; + Relids relids = joinrel->relids; + ListCell *vars; - foreach(i, tlist) + foreach(vars, input_rel->reltargetlist) { - TargetEntry *xtl = lfirst(i); + Node *origvar = (Node *) lfirst(vars); + Var *var; + RelOptInfo *baserel; + int ndx; - resdomno += 1; - t_list = lappend(t_list, - create_tl_element(get_expr(xtl), resdomno)); - } + /* + * Ignore PlaceHolderVars in the input tlists; we'll make our own + * decisions about whether to copy them. + */ + if (IsA(origvar, PlaceHolderVar)) + continue; + + /* + * We can't run into any child RowExprs here, but we could find a + * whole-row Var with a ConvertRowtypeExpr atop it. + */ + var = (Var *) origvar; + while (!IsA(var, Var)) + { + if (IsA(var, ConvertRowtypeExpr)) + var = (Var *) ((ConvertRowtypeExpr *) var)->arg; + else + elog(ERROR, "unexpected node type in reltargetlist: %d", + (int) nodeTag(var)); + } - return t_list; + /* Get the Var's original base rel */ + baserel = find_base_rel(root, var->varno); + + /* Is it still needed above this joinrel? */ + ndx = var->varattno - baserel->min_attr; + if (bms_nonempty_difference(baserel->attr_needed[ndx], relids)) + { + /* Yup, add it to the output */ + joinrel->reltargetlist = lappend(joinrel->reltargetlist, origvar); + joinrel->width += baserel->attr_widths[ndx]; + } + } } /* @@ -279,47 +488,68 @@ new_join_tlist(List *tlist, * * These routines are separate because the restriction list must be * built afresh for each pair of input sub-relations we consider, whereas - * the join lists need only be computed once for any join RelOptInfo. - * The join lists are fully determined by the set of rels making up the + * the join list need only be computed once for any join RelOptInfo. + * The join list is fully determined by the set of rels making up the * joinrel, so we should get the same results (up to ordering) from any - * candidate pair of sub-relations. But the restriction list is whatever + * candidate pair of sub-relations. But the restriction list is whatever * is not handled in the sub-relations, so it depends on which * sub-relations are considered. * * If a join clause from an input relation refers to base rels still not * present in the joinrel, then it is still a join clause for the joinrel; - * we put it into an appropriate JoinInfo list for the joinrel. Otherwise, + * we put it into the joininfo list for the joinrel. Otherwise, * the clause is now a restrict clause for the joined relation, and we * return it to the caller of build_joinrel_restrictlist() to be stored in - * join paths made from this pair of sub-relations. (It will not need to + * join paths made from this pair of sub-relations. (It will not need to * be considered further up the join tree.) * + * In many case we will find the same RestrictInfos in both input + * relations' joinlists, so be careful to eliminate duplicates. + * Pointer equality should be a sufficient test for dups, since all + * the various joinlist entries ultimately refer to RestrictInfos + * pushed into them by distribute_restrictinfo_to_rels(). + * * 'joinrel' is a join relation node * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined * to form joinrel. * * build_joinrel_restrictlist() returns a list of relevant restrictinfos, * whereas build_joinrel_joinlist() stores its results in the joinrel's - * joininfo lists. One or the other must accept each given clause! + * joininfo list. One or the other must accept each given clause! * * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass * up to the join relation. I believe this is no longer necessary, because - * RestrictInfo nodes are no longer context-dependent. Instead, just include + * RestrictInfo nodes are no longer context-dependent. Instead, just include * the original nodes in the lists made for the join relation. */ static List * -build_joinrel_restrictlist(RelOptInfo *joinrel, +build_joinrel_restrictlist(PlannerInfo *root, + RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel) { + List *result; + /* - * We must eliminate duplicates, since we will see the - * same clauses arriving from both input relations... + * Collect all the clauses that syntactically belong at this level, + * eliminating any duplicates (important since we will see many of the + * same clauses arriving from both input relations). */ - return LispUnion(subbuild_joinrel_restrictlist(joinrel, - outer_rel->joininfo), - subbuild_joinrel_restrictlist(joinrel, - inner_rel->joininfo)); + result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL); + result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result); + + /* + * Add on any clauses derived from EquivalenceClasses. These cannot be + * redundant with the clauses in the joininfo lists, so don't bother + * checking. + */ + result = list_concat(result, + generate_join_implied_equalities(root, + joinrel, + outer_rel, + inner_rel)); + + return result; } static void @@ -327,82 +557,84 @@ build_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel) { - subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo); - subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo); + List *result; + + /* + * Collect all the clauses that syntactically belong above this level, + * eliminating any duplicates (important since we will see many of the + * same clauses arriving from both input relations). + */ + result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL); + result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result); + + joinrel->joininfo = result; } static List * subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list) + List *joininfo_list, + List *new_restrictlist) { - List *restrictlist = NIL; - List *xjoininfo; + ListCell *l; - foreach(xjoininfo, joininfo_list) + foreach(l, joininfo_list) { - JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); - Relids new_unjoined_relids; + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - new_unjoined_relids = set_differencei(joininfo->unjoined_relids, - joinrel->relids); - if (new_unjoined_relids == NIL) + if (bms_is_subset(rinfo->required_relids, joinrel->relids)) { /* - * Clauses in this JoinInfo list become restriction clauses - * for the joinrel, since they refer to no outside rels. - * - * We must copy the list to avoid disturbing the input relation, - * but we can use a shallow copy. + * This clause becomes a restriction clause for the joinrel, since + * it refers to no outside rels. Add it to the list, being + * careful to eliminate duplicates. (Since RestrictInfo nodes in + * different joinlists will have been multiply-linked rather than + * copied, pointer equality should be a sufficient test.) */ - restrictlist = nconc(restrictlist, - listCopy(joininfo->jinfo_restrictinfo)); + new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo); } else { /* - * These clauses are still join clauses at this level, - * so we ignore them in this routine. + * This clause is still a join clause at this level, so we ignore + * it in this routine. */ } } - return restrictlist; + return new_restrictlist; } -static void +static List * subbuild_joinrel_joinlist(RelOptInfo *joinrel, - List *joininfo_list) + List *joininfo_list, + List *new_joininfo) { - List *xjoininfo; + ListCell *l; - foreach(xjoininfo, joininfo_list) + foreach(l, joininfo_list) { - JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); - Relids new_unjoined_relids; + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - new_unjoined_relids = set_differencei(joininfo->unjoined_relids, - joinrel->relids); - if (new_unjoined_relids == NIL) + if (bms_is_subset(rinfo->required_relids, joinrel->relids)) { /* - * Clauses in this JoinInfo list become restriction clauses - * for the joinrel, since they refer to no outside rels. - * So we can ignore them in this routine. + * This clause becomes a restriction clause for the joinrel, since + * it refers to no outside rels. So we can ignore it in this + * routine. */ } else { /* - * These clauses are still join clauses at this level, - * so find or make the appropriate JoinInfo item for the joinrel, - * and add the clauses to it (eliminating duplicates). + * This clause is still a join clause at this level, so add it to + * the new joininfo list, being careful to eliminate duplicates. + * (Since RestrictInfo nodes in different joinlists will have been + * multiply-linked rather than copied, pointer equality should be + * a sufficient test.) */ - JoinInfo *new_joininfo; - - new_joininfo = find_joininfo_node(joinrel, new_unjoined_relids); - new_joininfo->jinfo_restrictinfo = - LispUnion(new_joininfo->jinfo_restrictinfo, - joininfo->jinfo_restrictinfo); + new_joininfo = list_append_unique_ptr(new_joininfo, rinfo); } } + + return new_joininfo; }