* relnode.c
* Relation-node lookup/construction routines
*
- * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2003, 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.38 2002/06/20 20:29:31 momjian Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.59 2004/06/01 03:03:02 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "optimizer/cost.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
-#include "optimizer/paths.h"
#include "optimizer/plancat.h"
+#include "optimizer/restrictinfo.h"
#include "optimizer/tlist.h"
#include "parser/parsetree.h"
static RelOptInfo *make_base_rel(Query *root, int relid);
-static List *new_join_tlist(List *tlist, int first_resdomno);
+static void build_joinrel_tlist(Query *root, RelOptInfo *joinrel);
static List *build_joinrel_restrictlist(Query *root,
RelOptInfo *joinrel,
RelOptInfo *outer_rel,
- RelOptInfo *inner_rel);
+ RelOptInfo *inner_rel,
+ JoinType jointype);
static void build_joinrel_joinlist(RelOptInfo *joinrel,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel);
void
build_base_rel(Query *root, int relid)
{
- List *rels;
+ ListCell *l;
RelOptInfo *rel;
/* Rel should not exist already */
- foreach(rels, root->base_rel_list)
+ foreach(l, root->base_rel_list)
{
- rel = (RelOptInfo *) lfirst(rels);
-
- /* length(rel->relids) == 1 for all members of base_rel_list */
- if (lfirsti(rel->relids) == relid)
- elog(ERROR, "build_base_rel: rel already exists");
+ rel = (RelOptInfo *) lfirst(l);
+ if (relid == rel->relid)
+ elog(ERROR, "rel already exists");
}
/* It should not exist as an "other" rel, either */
- foreach(rels, root->other_rel_list)
+ foreach(l, root->other_rel_list)
{
- rel = (RelOptInfo *) lfirst(rels);
-
- if (lfirsti(rel->relids) == relid)
- elog(ERROR, "build_base_rel: rel already exists as 'other' rel");
+ rel = (RelOptInfo *) lfirst(l);
+ if (relid == rel->relid)
+ elog(ERROR, "rel already exists as \"other\" rel");
}
/* No existing RelOptInfo for this base rel, so make a new one */
RelOptInfo *
build_other_rel(Query *root, int relid)
{
- List *rels;
+ ListCell *l;
RelOptInfo *rel;
/* Already made? */
- foreach(rels, root->other_rel_list)
+ foreach(l, root->other_rel_list)
{
- rel = (RelOptInfo *) lfirst(rels);
-
- /* length(rel->relids) == 1 for all members of other_rel_list */
- if (lfirsti(rel->relids) == relid)
+ rel = (RelOptInfo *) lfirst(l);
+ if (relid == rel->relid)
return rel;
}
/* It should not exist as a base rel */
- foreach(rels, root->base_rel_list)
+ foreach(l, root->base_rel_list)
{
- rel = (RelOptInfo *) lfirst(rels);
-
- if (lfirsti(rel->relids) == relid)
- elog(ERROR, "build_other_rel: rel already exists as base rel");
+ rel = (RelOptInfo *) lfirst(l);
+ if (relid == rel->relid)
+ elog(ERROR, "rel already exists as base rel");
}
/* No existing RelOptInfo for this other rel, so make a new one */
rel = make_base_rel(root, relid);
- /* if it's not a join rel, must be a child rel */
- if (rel->reloptkind == RELOPT_BASEREL)
- rel->reloptkind = RELOPT_OTHER_CHILD_REL;
+ /* presently, must be an inheritance child rel */
+ Assert(rel->reloptkind == RELOPT_BASEREL);
+ rel->reloptkind = RELOPT_OTHER_CHILD_REL;
/* and add it to the list */
root->other_rel_list = lcons(rel, root->other_rel_list);
RangeTblEntry *rte = rt_fetch(relid, root->rtable);
rel->reloptkind = RELOPT_BASEREL;
- rel->relids = makeListi1(relid);
+ 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->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->joinrti = 0;
- rel->joinrteids = NIL;
rel->baserestrictinfo = NIL;
- rel->baserestrictcost = 0;
- rel->outerjoinset = NIL;
+ rel->baserestrictcost.startup = 0;
+ rel->baserestrictcost.per_tuple = 0;
+ rel->outerjoinset = NULL;
rel->joininfo = NIL;
- rel->innerjoin = NIL;
+ rel->index_outer_relids = NULL;
+ rel->index_inner_paths = NIL;
/* Check type of rtable entry */
switch (rte->rtekind)
{
case RTE_RELATION:
- {
/* Table --- retrieve statistics from the system catalogs */
- bool indexed;
-
- get_relation_info(rte->relid,
- &indexed, &rel->pages, &rel->tuples);
- if (indexed)
- rel->indexlist = find_secondary_indexes(rte->relid);
+ get_relation_info(rte->relid, rel);
break;
- }
case RTE_SUBQUERY:
case RTE_FUNCTION:
- /* Subquery or function --- nothing to do here */
- break;
- case RTE_JOIN:
- /* Join --- must be an otherrel */
- rel->reloptkind = RELOPT_OTHER_JOIN_REL;
+ /* Subquery or function --- need only set up attr range */
+ /* Note: 0 is included in range to support whole-row Vars */
+ rel->min_attr = 0;
+ rel->max_attr = list_length(rte->eref->colnames);
break;
default:
- elog(ERROR, "make_base_rel: unsupported RTE kind %d",
+ elog(ERROR, "unrecognized RTE kind: %d",
(int) rte->rtekind);
break;
}
+ Assert(rel->max_attr >= rel->min_attr);
+ 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));
+
return rel;
}
RelOptInfo *
find_base_rel(Query *root, int relid)
{
- List *rels;
+ ListCell *l;
RelOptInfo *rel;
- foreach(rels, root->base_rel_list)
+ foreach(l, root->base_rel_list)
{
- rel = (RelOptInfo *) lfirst(rels);
-
- /* length(rel->relids) == 1 for all members of base_rel_list */
- if (lfirsti(rel->relids) == relid)
+ rel = (RelOptInfo *) lfirst(l);
+ if (relid == rel->relid)
return rel;
}
- foreach(rels, root->other_rel_list)
+ foreach(l, root->other_rel_list)
{
- rel = (RelOptInfo *) lfirst(rels);
-
- if (lfirsti(rel->relids) == relid)
+ rel = (RelOptInfo *) lfirst(l);
+ if (relid == rel->relid)
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 */
}
-/*
- * find_other_rel
- * Find an otherrel entry, if one exists for the given relid.
- * Return NULL if no entry.
- */
-RelOptInfo *
-find_other_rel(Query *root, int relid)
-{
- List *rels;
-
- foreach(rels, root->other_rel_list)
- {
- RelOptInfo *rel = (RelOptInfo *) lfirst(rels);
-
- if (lfirsti(rel->relids) == relid)
- return rel;
- }
- return NULL;
-}
-
-/*
- * find_other_rel_for_join
- * Look for an otherrel for a join RTE matching the given baserel set.
- * Return NULL if no entry.
- */
-RelOptInfo *
-find_other_rel_for_join(Query *root, List *relids)
-{
- List *rels;
-
- foreach(rels, root->other_rel_list)
- {
- RelOptInfo *rel = (RelOptInfo *) lfirst(rels);
-
- if (rel->reloptkind == RELOPT_OTHER_JOIN_REL
- && sameseti(relids, rel->outerjoinset))
- return rel;
- }
- return NULL;
-}
-
/*
* 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 *
+RelOptInfo *
find_join_rel(Query *root, Relids relids)
{
- List *joinrels;
+ ListCell *l;
- foreach(joinrels, root->join_rel_list)
+ foreach(l, root->join_rel_list)
{
- RelOptInfo *rel = (RelOptInfo *) lfirst(joinrels);
+ RelOptInfo *rel = (RelOptInfo *) lfirst(l);
- if (sameseti(rel->relids, relids))
+ if (bms_equal(rel->relids, relids))
return 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
* 'jointype': type of join (inner/outer)
*/
RelOptInfo *
build_join_rel(Query *root,
+ Relids joinrelids,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel,
JoinType jointype,
List **restrictlist_ptr)
{
- List *joinrelids;
RelOptInfo *joinrel;
- RelOptInfo *joinrterel;
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)
*restrictlist_ptr = build_joinrel_restrictlist(root,
joinrel,
outer_rel,
- inner_rel);
+ inner_rel,
+ jointype);
return joinrel;
}
*/
joinrel = makeNode(RelOptInfo);
joinrel->reloptkind = RELOPT_JOINREL;
- joinrel->relids = joinrelids;
+ 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->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->joinrti = 0;
- joinrel->joinrteids = nconc(listCopy(outer_rel->joinrteids),
- inner_rel->joinrteids);
joinrel->baserestrictinfo = NIL;
- joinrel->baserestrictcost = 0;
- joinrel->outerjoinset = NIL;
+ joinrel->baserestrictcost.startup = 0;
+ joinrel->baserestrictcost.per_tuple = 0;
+ joinrel->outerjoinset = NULL;
joinrel->joininfo = NIL;
- joinrel->innerjoin = NIL;
-
- /* Is there a join RTE matching this join? */
- joinrterel = find_other_rel_for_join(root, joinrelids);
- if (joinrterel)
- {
- /* Yes, remember its RT index */
- joinrel->joinrti = lfirsti(joinrterel->relids);
- joinrel->joinrteids = lconsi(joinrel->joinrti, joinrel->joinrteids);
- }
+ 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.
- *
- * XXX right now we don't remove any irrelevant elements, we just
- * append the two tlists together. 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.
+ * 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).
*/
- 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);
-
- /*
- * If there are any alias variables attached to the matching join RTE,
- * attach them to the tlist too, so that they will be evaluated for use
- * at higher plan levels.
- */
- if (joinrterel)
- {
- List *jrtetl;
-
- foreach(jrtetl, joinrterel->targetlist)
- {
- TargetEntry *jrtete = lfirst(jrtetl);
-
- add_var_to_tlist(joinrel, (Var *) jrtete->expr);
- }
- }
+ build_joinrel_tlist(root, joinrel);
/*
* Construct restrict and join clause lists for the new joinrel. (The
restrictlist = build_joinrel_restrictlist(root,
joinrel,
outer_rel,
- inner_rel);
+ inner_rel,
+ jointype);
if (restrictlist_ptr)
*restrictlist_ptr = restrictlist;
build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
}
/*
- * 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'.
+ * build_joinrel_tlist
+ * Builds a join relation's target list.
*
- * 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.
+ * The join's targetlist includes all Vars of its member relations that
+ * will still be needed above the join.
*
- * '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
+ * In a former lifetime, this just merged the tlists of the two member
+ * relations first presented. While we could still do that, working from
+ * lists of Vars would mean doing a find_base_rel lookup for each Var.
+ * It seems more efficient to scan the list of base rels and collect the
+ * needed vars directly from there.
*
- * 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(Query *root, RelOptInfo *joinrel)
{
- int resdomno = first_resdomno - 1;
- List *t_list = NIL;
- List *i;
+ Relids relids = joinrel->relids;
+ ListCell *rels;
+
+ joinrel->reltargetlist = NIL;
+ joinrel->width = 0;
- foreach(i, tlist)
+ foreach(rels, root->base_rel_list)
{
- TargetEntry *xtl = lfirst(i);
+ RelOptInfo *baserel = (RelOptInfo *) lfirst(rels);
+ ListCell *vars;
- resdomno += 1;
- t_list = lappend(t_list,
- create_tl_element(get_expr(xtl), resdomno));
- }
+ if (!bms_is_member(baserel->relid, relids))
+ continue;
+
+ foreach(vars, baserel->reltargetlist)
+ {
+ Var *var = (Var *) lfirst(vars);
+ int ndx = var->varattno - baserel->min_attr;
- return t_list;
+ if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
+ {
+ joinrel->reltargetlist = lappend(joinrel->reltargetlist, var);
+ Assert(baserel->attr_widths[ndx] > 0);
+ joinrel->width += baserel->attr_widths[ndx];
+ }
+ }
+ }
}
/*
* 'joinrel' is a join relation node
* 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
* to form joinrel.
+ * 'jointype' is the type of join used.
*
* build_joinrel_restrictlist() returns a list of relevant restrictinfos,
* whereas build_joinrel_joinlist() stores its results in the joinrel's
build_joinrel_restrictlist(Query *root,
RelOptInfo *joinrel,
RelOptInfo *outer_rel,
- RelOptInfo *inner_rel)
+ RelOptInfo *inner_rel,
+ JoinType jointype)
{
- List *result = NIL;
+ List *result;
List *rlist;
- List *item;
/*
* Collect all the clauses that syntactically belong at this level.
*/
- rlist = nconc(subbuild_joinrel_restrictlist(joinrel,
- outer_rel->joininfo),
- subbuild_joinrel_restrictlist(joinrel,
- inner_rel->joininfo));
+ rlist = list_concat(subbuild_joinrel_restrictlist(joinrel,
+ outer_rel->joininfo),
+ subbuild_joinrel_restrictlist(joinrel,
+ inner_rel->joininfo));
/*
* Eliminate duplicate and redundant clauses.
* 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.
*/
- 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);
- }
+ result = remove_redundant_join_clauses(root, rlist, jointype);
- freeList(rlist);
+ list_free(rlist);
return result;
}
List *joininfo_list)
{
List *restrictlist = NIL;
- List *xjoininfo;
+ ListCell *xjoininfo;
foreach(xjoininfo, joininfo_list)
{
JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo);
- if (is_subseti(joininfo->unjoined_relids, joinrel->relids))
+ if (bms_is_subset(joininfo->unjoined_relids, joinrel->relids))
{
/*
* Clauses in this JoinInfo list become restriction clauses
* We must copy the list to avoid disturbing the input relation,
* but we can use a shallow copy.
*/
- restrictlist = nconc(restrictlist,
- listCopy(joininfo->jinfo_restrictinfo));
+ restrictlist = list_concat(restrictlist,
+ list_copy(joininfo->jinfo_restrictinfo));
}
else
{
subbuild_joinrel_joinlist(RelOptInfo *joinrel,
List *joininfo_list)
{
- List *xjoininfo;
+ ListCell *xjoininfo;
foreach(xjoininfo, joininfo_list)
{
JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo);
Relids new_unjoined_relids;
- new_unjoined_relids = set_differencei(joininfo->unjoined_relids,
- joinrel->relids);
- if (new_unjoined_relids == NIL)
+ new_unjoined_relids = bms_difference(joininfo->unjoined_relids,
+ joinrel->relids);
+ if (bms_is_empty(new_unjoined_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.
*/
+ bms_free(new_unjoined_relids);
}
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).
+ * add the clauses to it, eliminating duplicates. (Since
+ * RestrictInfo nodes are normally multiply-linked rather than
+ * copied, pointer equality should be a sufficient test. If
+ * two equal() nodes should happen to sneak in, no great harm
+ * is done --- they'll be detected by redundant-clause testing
+ * when they reach a restriction list.)
*/
JoinInfo *new_joininfo;
- new_joininfo = find_joininfo_node(joinrel, new_unjoined_relids);
+ new_joininfo = make_joininfo_node(joinrel, new_unjoined_relids);
new_joininfo->jinfo_restrictinfo =
- set_union(new_joininfo->jinfo_restrictinfo,
- joininfo->jinfo_restrictinfo);
+ list_union_ptr(new_joininfo->jinfo_restrictinfo,
+ joininfo->jinfo_restrictinfo);
}
}
}