* relnode.c
* Relation-node lookup/construction routines
*
- * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
+ * 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.35 2001/10/25 05:49:34 momjian Exp $
+ * src/backend/optimizer/util/relnode.c
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
#include "optimizer/cost.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 RelOptInfo *make_base_rel(Query *root, int relid);
-static List *new_join_tlist(List *tlist, int first_resdomno);
-static List *build_joinrel_restrictlist(Query *root,
+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);
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);
/*
- * build_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 *
-build_base_rel(Query *root, int relid)
+build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
{
- List *rels;
RelOptInfo *rel;
+ RangeTblEntry *rte;
- /* Already made? */
- foreach(rels, root->base_rel_list)
- {
- rel = (RelOptInfo *) lfirst(rels);
-
- /* length(rel->relids) == 1 for all members of base_rel_list */
- if (lfirsti(rel->relids) == relid)
- return rel;
- }
-
- /* It should not exist as an "other" rel */
- foreach(rels, root->other_rel_list)
- {
- rel = (RelOptInfo *) lfirst(rels);
-
- if (lfirsti(rel->relids) == relid)
- elog(ERROR, "build_base_rel: rel already exists as 'other' rel");
- }
-
- /* No existing RelOptInfo for this base rel, so make a new one */
- rel = make_base_rel(root, relid);
-
- /* and add it to the list */
- root->base_rel_list = lcons(rel, root->base_rel_list);
+ /* 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);
- return rel;
-}
+ /* Fetch RTE for relation */
+ rte = root->simple_rte_array[relid];
+ Assert(rte != NULL);
-/*
- * build_other_rel
- * Returns relation entry corresponding to 'relid', creating a new one
- * if necessary. This is for 'other' relations, which are just like
- * base relations except that they live in a different list.
- */
-RelOptInfo *
-build_other_rel(Query *root, int relid)
-{
- List *rels;
- RelOptInfo *rel;
-
- /* Already made? */
- foreach(rels, root->other_rel_list)
- {
- rel = (RelOptInfo *) lfirst(rels);
-
- /* length(rel->relids) == 1 for all members of other_rel_list */
- if (lfirsti(rel->relids) == relid)
- return rel;
- }
-
- /* It should not exist as a base rel */
- foreach(rels, root->base_rel_list)
- {
- rel = (RelOptInfo *) lfirst(rels);
-
- if (lfirsti(rel->relids) == relid)
- elog(ERROR, "build_other_rel: rel already exists as base rel");
- }
-
- /* No existing RelOptInfo for this other rel, so make a new one */
- rel = make_base_rel(root, relid);
-
- /* and add it to the list */
- root->other_rel_list = lcons(rel, root->other_rel_list);
-
- return rel;
-}
-
-/*
- * make_base_rel
- * Construct a base-relation RelOptInfo for the specified rangetable index.
- *
- * Common code for build_base_rel and build_other_rel.
- */
-static RelOptInfo *
-make_base_rel(Query *root, int relid)
-{
- RelOptInfo *rel = makeNode(RelOptInfo);
- Oid relationObjectId;
-
- rel->relids = makeListi1(relid);
+ rel = makeNode(RelOptInfo);
+ 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->cheapest_startup_path = NULL;
rel->cheapest_total_path = NULL;
- rel->pruneable = true;
- rel->issubquery = false;
+ 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 = 0;
- rel->outerjoinset = NIL;
+ rel->baserestrictcost.startup = 0;
+ rel->baserestrictcost.per_tuple = 0;
rel->joininfo = NIL;
- rel->innerjoin = NIL;
-
- /* Check rtable to see if it's a plain relation or a subquery */
- relationObjectId = getrelid(relid, root->rtable);
+ rel->has_eclass_joins = false;
+ rel->index_outer_relids = NULL;
+ rel->index_inner_paths = NIL;
- if (relationObjectId != InvalidOid)
+ /* Check type of rtable entry */
+ switch (rte->rtekind)
{
- /* Plain relation --- retrieve statistics from the system catalogs */
- bool indexed;
+ 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:
- get_relation_info(relationObjectId,
- &indexed, &rel->pages, &rel->tuples);
- if (indexed)
- rel->indexlist = find_secondary_indexes(relationObjectId);
+ /*
+ * 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)
{
- /* subquery --- mark it as such for later processing */
- rel->issubquery = true;
+ ListCell *l;
+
+ 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
- * (since we'd have no idea which list to add it to).
+ * Find a base or other relation entry, which must already exist.
*/
RelOptInfo *
-find_base_rel(Query *root, int relid)
+find_base_rel(PlannerInfo *root, int relid)
{
- List *rels;
RelOptInfo *rel;
- foreach(rels, root->base_rel_list)
- {
- rel = (RelOptInfo *) lfirst(rels);
+ Assert(relid > 0);
- /* length(rel->relids) == 1 for all members of base_rel_list */
- if (lfirsti(rel->relids) == relid)
- return rel;
- }
-
- foreach(rels, root->other_rel_list)
+ if (relid < root->simple_rel_array_size)
{
- rel = (RelOptInfo *) lfirst(rels);
-
- if (lfirsti(rel->relids) == relid)
+ rel = root->simple_rel_array[relid];
+ if (rel)
return rel;
}
- elog(ERROR, "find_base_rel: no relation entry for relid %d", relid);
+ 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 build_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)
+ {
+ Relids hashkey = relids;
+ JoinHashEntry *hentry;
+
+ hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
+ &hashkey,
+ HASH_FIND,
+ NULL);
+ if (hentry)
+ return hentry->join_rel;
+ }
+ else
{
- RelOptInfo *rel = (RelOptInfo *) lfirst(joinrels);
+ 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;
* 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
- * 'jointype': type of join (inner/outer)
+ * '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.
* duplicated calculation of the restrictlist...
*/
RelOptInfo *
-build_join_rel(Query *root,
+build_join_rel(PlannerInfo *root,
+ Relids joinrelids,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel,
- JoinType jointype,
+ 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(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->cheapest_startup_path = NULL;
joinrel->cheapest_total_path = NULL;
- joinrel->pruneable = true;
- joinrel->issubquery = false;
+ 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 = 0;
- joinrel->outerjoinset = 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().)
+ * caller might or might not need the restrictlist, but I need it anyway
+ * for set_joinrel_size_estimates().)
*/
- restrictlist = build_joinrel_restrictlist(root,
- 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,
- jointype, restrictlist);
+ sjinfo, restrictlist);
/*
- * Add the joinrel to the query's joinrel list.
+ * 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;
- return t_list;
+ /*
+ * 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));
+ }
+
+ /* 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];
+ }
+ }
}
/*
*
* 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
* is not handled in the sub-relations, so it depends on which
*
* 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
* be considered further up the join tree.)
*
- * When building a restriction list, we eliminate redundant clauses.
- * We don't try to do that for join clause lists, since the join clauses
- * aren't really doing anything, just waiting to become part of higher
- * levels' restriction lists.
+ * 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
*
* 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
* the original nodes in the lists made for the join relation.
*/
static List *
-build_joinrel_restrictlist(Query *root,
+build_joinrel_restrictlist(PlannerInfo *root,
RelOptInfo *joinrel,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel)
{
- List *result = NIL;
- List *rlist;
- List *item;
+ List *result;
/*
- * Collect all the clauses that syntactically belong at this level.
+ * 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).
*/
- rlist = nconc(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);
/*
- * Eliminate duplicate and redundant clauses.
- *
- * We must eliminate duplicates, since we will see many of the same
- * clauses arriving from both input relations. Also, if a clause is a
- * mergejoinable clause, it's possible that it is redundant with
- * previous clauses (see optimizer/README for discussion). We detect
- * that case and omit the redundant clause from the result list.
- *
- * We can detect redundant mergejoinable clauses very cheaply by using
- * their left and right pathkeys, which uniquely identify the sets of
- * equijoined variables in question. All the members of a pathkey set
- * that are in the left relation have already been forced to be equal;
- * likewise for those in the right relation. So, we need to have only
- * one clause that checks equality between any set member on the left
- * and any member on the right; by transitivity, all the rest are then
- * equal.
+ * Add on any clauses derived from EquivalenceClasses. These cannot be
+ * redundant with the clauses in the joininfo lists, so don't bother
+ * checking.
*/
- foreach(item, rlist)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
-
- /* eliminate duplicates */
- if (member(rinfo, result))
- continue;
-
- /* check for redundant merge clauses */
- if (rinfo->mergejoinoperator != InvalidOid)
- {
- bool redundant = false;
- List *olditem;
-
- cache_mergeclause_pathkeys(root, rinfo);
-
- foreach(olditem, result)
- {
- RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
-
- if (oldrinfo->mergejoinoperator != InvalidOid &&
- rinfo->left_pathkey == oldrinfo->left_pathkey &&
- rinfo->right_pathkey == oldrinfo->right_pathkey)
- {
- redundant = true;
- break;
- }
- }
-
- if (redundant)
- continue;
- }
-
- /* otherwise, add it to result list */
- result = lappend(result, rinfo);
- }
-
- freeList(rlist);
+ result = list_concat(result,
+ generate_join_implied_equalities(root,
+ joinrel,
+ outer_rel,
+ inner_rel));
return result;
}
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);
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
- if (is_subseti(joininfo->unjoined_relids, joinrel->relids))
+ 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 =
- set_union(new_joininfo->jinfo_restrictinfo,
- joininfo->jinfo_restrictinfo);
+ new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
}
}
+
+ return new_joininfo;
}
projects / postgresql / blobdiff