* initsplan.c
* Target list, qualification, joininfo initialization routines
*
- * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.72 2002/05/18 02:25:49 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.106 2005/06/05 22:32:55 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
-#include <sys/types.h>
-
#include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "nodes/makefuncs.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
+#include "optimizer/restrictinfo.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "parser/parsetree.h"
#include "utils/syscache.h"
-static void mark_baserels_for_outer_join(Query *root, Relids rels,
+static void mark_baserels_for_outer_join(PlannerInfo *root, Relids rels,
Relids outerrels);
-static void distribute_qual_to_rels(Query *root, Node *clause,
- bool ispusheddown,
- bool isouterjoin,
+static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
+ bool is_pushed_down,
bool isdeduced,
+ Relids outerjoin_nonnullable,
Relids qualscope);
-static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
- Relids join_relids);
-static void add_vars_to_targetlist(Query *root, List *vars);
-static bool qual_is_redundant(Query *root, RestrictInfo *restrictinfo,
+static void add_vars_to_targetlist(PlannerInfo *root, List *vars,
+ Relids where_needed);
+static bool qual_is_redundant(PlannerInfo *root, RestrictInfo *restrictinfo,
List *restrictlist);
static void check_mergejoinable(RestrictInfo *restrictinfo);
static void check_hashjoinable(RestrictInfo *restrictinfo);
* add_base_rels_to_query
*
* Scan the query's jointree and create baserel RelOptInfos for all
- * the base relations (ie, table and subquery RTEs) appearing in the
- * jointree. Also, create otherrel RelOptInfos for join RTEs.
- *
- * The return value is a list of all the baserel indexes (but not join RTE
- * indexes) included in the scanned jointree. This is actually just an
- * internal convenience for marking join otherrels properly; no outside
- * caller uses the result.
+ * the base relations (ie, table, subquery, and function RTEs)
+ * appearing in the jointree.
*
* At the end of this process, there should be one baserel RelOptInfo for
* every non-join RTE that is used in the query. Therefore, this routine
* is the only place that should call build_base_rel. But build_other_rel
- * will be used again later to build rels for inheritance children.
+ * will be used later to build rels for inheritance children.
*/
-List *
-add_base_rels_to_query(Query *root, Node *jtnode)
+void
+add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
{
- List *result = NIL;
-
if (jtnode == NULL)
- return NIL;
+ return;
if (IsA(jtnode, RangeTblRef))
{
int varno = ((RangeTblRef *) jtnode)->rtindex;
build_base_rel(root, varno);
- result = makeListi1(varno);
}
else if (IsA(jtnode, FromExpr))
{
FromExpr *f = (FromExpr *) jtnode;
- List *l;
+ ListCell *l;
foreach(l, f->fromlist)
- {
- result = nconc(result,
- add_base_rels_to_query(root, lfirst(l)));
- }
+ add_base_rels_to_query(root, lfirst(l));
}
else if (IsA(jtnode, JoinExpr))
{
JoinExpr *j = (JoinExpr *) jtnode;
- RelOptInfo *jrel;
- result = add_base_rels_to_query(root, j->larg);
- result = nconc(result,
- add_base_rels_to_query(root, j->rarg));
- /* the join's own rtindex is NOT added to result */
- jrel = build_other_rel(root, j->rtindex);
- /*
- * Mark the join's otherrel with outerjoinset = list of baserel ids
- * included in the join. Note we must copy here because result list
- * is destructively modified by nconcs at higher levels.
- */
- jrel->outerjoinset = listCopy(result);
- /*
- * Safety check: join RTEs should not be SELECT FOR UPDATE targets
- */
- if (intMember(j->rtindex, root->rowMarks))
- elog(ERROR, "SELECT FOR UPDATE cannot be applied to a join");
+ add_base_rels_to_query(root, j->larg);
+ add_base_rels_to_query(root, j->rarg);
}
else
- elog(ERROR, "add_base_rels_to_query: unexpected node type %d",
- nodeTag(jtnode));
- return result;
+ elog(ERROR, "unrecognized node type: %d",
+ (int) nodeTag(jtnode));
}
/*
* build_base_rel_tlists
- * Creates targetlist entries for each var seen in 'tlist' and adds
- * them to the tlist of the appropriate rel node.
+ * Add targetlist entries for each var needed in the query's final tlist
+ * to the appropriate base relations.
+ *
+ * We mark such vars as needed by "relation 0" to ensure that they will
+ * propagate up through all join plan steps.
*/
void
-build_base_rel_tlists(Query *root, List *tlist)
+build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
{
- List *tlist_vars = pull_var_clause((Node *) tlist, false);
+ List *tlist_vars = pull_var_clause((Node *) final_tlist, false);
- add_vars_to_targetlist(root, tlist_vars);
- freeList(tlist_vars);
+ if (tlist_vars != NIL)
+ {
+ add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
+ list_free(tlist_vars);
+ }
}
/*
* add_vars_to_targetlist
* For each variable appearing in the list, add it to the owning
- * relation's targetlist if not already present.
- *
- * Note that join alias variables will be attached to the otherrel for
- * the join RTE. They will later be transferred to the tlist of
- * the corresponding joinrel. We will also cause entries to be made
- * for the Vars that the alias will eventually depend on.
+ * relation's targetlist if not already present, and mark the variable
+ * as being needed for the indicated join (or for final output if
+ * where_needed includes "relation 0").
*/
static void
-add_vars_to_targetlist(Query *root, List *vars)
+add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
{
- List *temp;
+ ListCell *temp;
+
+ Assert(!bms_is_empty(where_needed));
foreach(temp, vars)
{
Var *var = (Var *) lfirst(temp);
RelOptInfo *rel = find_base_rel(root, var->varno);
+ int attrno = var->varattno;
- add_var_to_tlist(rel, var);
-
- if (rel->reloptkind == RELOPT_OTHER_JOIN_REL)
+ Assert(attrno >= rel->min_attr && attrno <= rel->max_attr);
+ attrno -= rel->min_attr;
+ if (bms_is_empty(rel->attr_needed[attrno]))
{
- /* Var is an alias */
- Node *expansion;
- List *varsused;
-
- expansion = flatten_join_alias_vars((Node *) var,
- root->rtable, true);
- varsused = pull_var_clause(expansion, false);
- add_vars_to_targetlist(root, varsused);
- freeList(varsused);
+ /* Variable not yet requested, so add to reltargetlist */
+ /* XXX is copyObject necessary here? */
+ rel->reltargetlist = lappend(rel->reltargetlist, copyObject(var));
}
+ rel->attr_needed[attrno] = bms_add_members(rel->attr_needed[attrno],
+ where_needed);
}
}
* distribute_quals_to_rels
* Recursively scan the query's join tree for WHERE and JOIN/ON qual
* clauses, and add these to the appropriate RestrictInfo and JoinInfo
- * lists belonging to base RelOptInfos. Also, base RelOptInfos are marked
+ * lists belonging to base RelOptInfos. Also, base RelOptInfos are marked
* with outerjoinset information, to aid in proper positioning of qual
* clauses that appear above outer joins.
*
* of an outer join since the qual might eliminate matching rows and cause a
* NULL row to be incorrectly emitted by the join. Therefore, rels appearing
* within the nullable side(s) of an outer join are marked with
- * outerjoinset = list of Relids used at the outer join node.
- * This list will be added to the list of rels referenced by quals using such
+ * outerjoinset = set of Relids used at the outer join node.
+ * This set will be added to the set of rels referenced by quals using such
* a rel, thereby forcing them up the join tree to the right level.
*
* To ease the calculation of these values, distribute_quals_to_rels() returns
- * the list of base Relids involved in its own level of join. This is just an
+ * the set of base Relids involved in its own level of join. This is just an
* internal convenience; no outside callers pay attention to the result.
*/
Relids
-distribute_quals_to_rels(Query *root, Node *jtnode)
+distribute_quals_to_rels(PlannerInfo *root, Node *jtnode)
{
- Relids result = NIL;
+ Relids result = NULL;
if (jtnode == NULL)
return result;
int varno = ((RangeTblRef *) jtnode)->rtindex;
/* No quals to deal with, just return correct result */
- result = makeListi1(varno);
+ result = bms_make_singleton(varno);
}
else if (IsA(jtnode, FromExpr))
{
FromExpr *f = (FromExpr *) jtnode;
- List *l;
- List *qual;
+ ListCell *l;
/*
* First, recurse to handle child joins.
- *
- * Note: we assume it's impossible to see same RT index from more
- * than one subtree, so nconc() is OK rather than set_unioni().
*/
foreach(l, f->fromlist)
{
- result = nconc(result,
- distribute_quals_to_rels(root, lfirst(l)));
+ result = bms_add_members(result,
+ distribute_quals_to_rels(root,
+ lfirst(l)));
}
/*
* Now process the top-level quals. These are always marked as
* "pushed down", since they clearly didn't come from a JOIN expr.
*/
- foreach(qual, (List *) f->quals)
- distribute_qual_to_rels(root, (Node *) lfirst(qual),
- true, false, false, result);
+ foreach(l, (List *) f->quals)
+ distribute_qual_to_rels(root, (Node *) lfirst(l),
+ true, false, NULL, result);
}
else if (IsA(jtnode, JoinExpr))
{
JoinExpr *j = (JoinExpr *) jtnode;
Relids leftids,
- rightids;
- bool isouterjoin;
- List *qual;
+ rightids,
+ nonnullable_rels,
+ nullable_rels;
+ ListCell *qual;
/*
* Order of operations here is subtle and critical. First we
* recurse to handle sub-JOINs. Their join quals will be placed
* without regard for whether this level is an outer join, which
- * is correct. Then, if we are an outer join, we mark baserels
- * contained within the nullable side(s) with our own rel list;
- * this will restrict placement of subsequent quals using those
- * rels, including our own quals and quals above us in the join
- * tree. Finally we place our own join quals.
+ * is correct. Then we place our own join quals, which are
+ * restricted by lower outer joins in any case, and are forced to
+ * this level if this is an outer join and they mention the outer
+ * side. Finally, if this is an outer join, we mark baserels
+ * contained within the inner side(s) with our own rel set; this
+ * will prevent quals above us in the join tree that use those
+ * rels from being pushed down below this level. (It's okay for
+ * upper quals to be pushed down to the outer side, however.)
*/
leftids = distribute_quals_to_rels(root, j->larg);
rightids = distribute_quals_to_rels(root, j->rarg);
- result = nconc(listCopy(leftids), rightids);
+ result = bms_union(leftids, rightids);
- isouterjoin = false;
+ nonnullable_rels = nullable_rels = NULL;
switch (j->jointype)
{
case JOIN_INNER:
/* Inner join adds no restrictions for quals */
break;
case JOIN_LEFT:
- mark_baserels_for_outer_join(root, rightids, result);
- isouterjoin = true;
+ nonnullable_rels = leftids;
+ nullable_rels = rightids;
break;
case JOIN_FULL:
- mark_baserels_for_outer_join(root, result, result);
- isouterjoin = true;
+ /* each side is both outer and inner */
+ nonnullable_rels = result;
+ nullable_rels = result;
break;
case JOIN_RIGHT:
- mark_baserels_for_outer_join(root, leftids, result);
- isouterjoin = true;
+ nonnullable_rels = rightids;
+ nullable_rels = leftids;
break;
case JOIN_UNION:
* This is where we fail if upper levels of planner
* haven't rewritten UNION JOIN as an Append ...
*/
- elog(ERROR, "UNION JOIN is not implemented yet");
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("UNION JOIN is not implemented")));
break;
default:
- elog(ERROR,
- "distribute_quals_to_rels: unsupported join type %d",
+ elog(ERROR, "unrecognized join type: %d",
(int) j->jointype);
break;
}
foreach(qual, (List *) j->quals)
distribute_qual_to_rels(root, (Node *) lfirst(qual),
- false, isouterjoin, false, result);
+ false, false,
+ nonnullable_rels, result);
+
+ if (nullable_rels != NULL)
+ mark_baserels_for_outer_join(root, nullable_rels, result);
}
else
- elog(ERROR, "distribute_quals_to_rels: unexpected node type %d",
- nodeTag(jtnode));
+ elog(ERROR, "unrecognized node type: %d",
+ (int) nodeTag(jtnode));
return result;
}
* Mark all base rels listed in 'rels' as having the given outerjoinset.
*/
static void
-mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels)
+mark_baserels_for_outer_join(PlannerInfo *root, Relids rels, Relids outerrels)
{
- List *relid;
+ Relids tmprelids;
+ int relno;
- foreach(relid, rels)
+ tmprelids = bms_copy(rels);
+ while ((relno = bms_first_member(tmprelids)) >= 0)
{
- int relno = lfirsti(relid);
RelOptInfo *rel = find_base_rel(root, relno);
/*
* Since we do this bottom-up, any outer-rels previously marked
* should be within the new outer join set.
*/
- Assert(is_subseti(rel->outerjoinset, outerrels));
+ Assert(bms_is_subset(rel->outerjoinset, outerrels));
/*
- * Presently the executor cannot support FOR UPDATE marking of
+ * Presently the executor cannot support FOR UPDATE/SHARE marking of
* rels appearing on the nullable side of an outer join. (It's
* somewhat unclear what that would mean, anyway: what should we
* mark when a result row is generated from no element of the
- * nullable relation?) So, complain if target rel is FOR UPDATE.
+ * nullable relation?) So, complain if target rel is FOR UPDATE/SHARE.
* It's sufficient to make this check once per rel, so do it only
* if rel wasn't already known nullable.
*/
- if (rel->outerjoinset == NIL)
+ if (rel->outerjoinset == NULL)
{
- if (intMember(relno, root->rowMarks))
- elog(ERROR, "SELECT FOR UPDATE cannot be applied to the nullable side of an OUTER JOIN");
+ if (list_member_int(root->parse->rowMarks, relno))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("SELECT FOR UPDATE/SHARE cannot be applied to the nullable side of an outer join")));
}
rel->outerjoinset = outerrels;
}
+ bms_free(tmprelids);
}
/*
* (depending on whether the clause is a join) of each base relation
* mentioned in the clause. A RestrictInfo node is created and added to
* the appropriate list for each rel. Also, if the clause uses a
- * mergejoinable operator and is not an outer-join qual, enter the left-
- * and right-side expressions into the query's lists of equijoined vars.
+ * mergejoinable operator and is not delayed by outer-join rules, enter
+ * the left- and right-side expressions into the query's lists of
+ * equijoined vars.
*
* 'clause': the qual clause to be distributed
- * 'ispusheddown': if TRUE, force the clause to be marked 'ispusheddown'
+ * 'is_pushed_down': if TRUE, force the clause to be marked 'is_pushed_down'
* (this indicates the clause came from a FromExpr, not a JoinExpr)
- * 'isouterjoin': TRUE if the qual came from an OUTER JOIN's ON-clause
* 'isdeduced': TRUE if the qual came from implied-equality deduction
- * 'qualscope': list of baserels the qual's syntactic scope covers
+ * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
+ * baserels appearing on the outer (nonnullable) side of the join
+ * 'qualscope': set of baserels the qual's syntactic scope covers
*
* 'qualscope' identifies what level of JOIN the qual came from. For a top
* level qual (WHERE qual), qualscope lists all baserel ids and in addition
- * 'ispusheddown' will be TRUE.
+ * 'is_pushed_down' will be TRUE.
*/
static void
-distribute_qual_to_rels(Query *root, Node *clause,
- bool ispusheddown,
- bool isouterjoin,
+distribute_qual_to_rels(PlannerInfo *root, Node *clause,
+ bool is_pushed_down,
bool isdeduced,
+ Relids outerjoin_nonnullable,
Relids qualscope)
{
- RestrictInfo *restrictinfo = makeNode(RestrictInfo);
Relids relids;
- List *vars;
+ bool valid_everywhere;
bool can_be_equijoin;
-
- restrictinfo->clause = (Expr *) clause;
- restrictinfo->subclauseindices = NIL;
- restrictinfo->eval_cost = -1; /* not computed until needed */
- restrictinfo->this_selec = -1; /* not computed until needed */
- restrictinfo->mergejoinoperator = InvalidOid;
- restrictinfo->left_sortop = InvalidOid;
- restrictinfo->right_sortop = InvalidOid;
- restrictinfo->left_pathkey = NIL; /* not computable yet */
- restrictinfo->right_pathkey = NIL;
- restrictinfo->left_mergescansel = -1; /* not computed until needed */
- restrictinfo->right_mergescansel = -1;
- restrictinfo->hashjoinoperator = InvalidOid;
- restrictinfo->left_bucketsize = -1; /* not computed until needed */
- restrictinfo->right_bucketsize = -1;
+ RestrictInfo *restrictinfo;
+ RelOptInfo *rel;
+ List *vars;
/*
- * Retrieve all relids and vars contained within the clause.
+ * Retrieve all relids mentioned within the clause.
*/
- clause_get_relids_vars(clause, &relids, &vars);
+ relids = pull_varnos(clause);
/*
- * The clause might contain some join alias vars; if so, we want to
- * remove the join otherrelids from relids and add the referent joins'
- * scope lists instead (thus ensuring that the clause can be evaluated
- * no lower than that join node). We rely here on the marking done
- * earlier by add_base_rels_to_query.
- *
- * We can combine this step with a cross-check that the clause contains
- * no relids not within its scope. If the first crosscheck succeeds,
- * the clause contains no aliases and we needn't look more closely.
+ * Cross-check: clause should contain no relids not within its scope.
+ * Otherwise the parser messed up.
*/
- if (!is_subseti(relids, qualscope))
- {
- Relids newrelids = NIL;
- List *relid;
-
- foreach(relid, relids)
- {
- RelOptInfo *rel = find_other_rel(root, lfirsti(relid));
-
- if (rel && rel->outerjoinset)
- {
- /* this relid is for a join RTE */
- newrelids = set_unioni(newrelids, rel->outerjoinset);
- }
- else
- {
- /* this relid is for a true baserel */
- newrelids = lappendi(newrelids, lfirsti(relid));
- }
- }
- relids = newrelids;
- /* Now repeat the crosscheck */
- if (!is_subseti(relids, qualscope))
- elog(ERROR, "JOIN qualification may not refer to other relations");
- }
+ if (!bms_is_subset(relids, qualscope))
+ elog(ERROR, "JOIN qualification may not refer to other relations");
/*
* If the clause is variable-free, we force it to be evaluated at its
* it will happen for variable-free JOIN/ON clauses. We don't have to
* be real smart about such a case, we just have to be correct.
*/
- if (relids == NIL)
+ if (bms_is_empty(relids))
relids = qualscope;
/*
- * For an outer-join qual, pretend that the clause references all rels
- * appearing within its syntactic scope, even if it really doesn't.
- * This ensures that the clause will be evaluated exactly at the level
- * of joining corresponding to the outer join.
- *
- * For a non-outer-join qual, we can evaluate the qual as soon as (1) we
- * have all the rels it mentions, and (2) we are at or above any outer
- * joins that can null any of these rels and are below the syntactic
- * location of the given qual. To enforce the latter, scan the base
- * rels listed in relids, and merge their outer-join lists into the
- * clause's own reference list. At the time we are called, the
- * outerjoinset list of each baserel will show exactly those outer
- * joins that are below the qual in the join tree.
- *
- * If the qual came from implied-equality deduction, we can evaluate the
- * qual at its natural semantic level.
- *
+ * Check to see if clause application must be delayed by outer-join
+ * considerations.
*/
if (isdeduced)
{
- Assert(sameseti(relids, qualscope));
+ /*
+ * If the qual came from implied-equality deduction, we can
+ * evaluate the qual at its natural semantic level. It is not
+ * affected by any outer-join rules (else we'd not have decided
+ * the vars were equal).
+ */
+ Assert(bms_equal(relids, qualscope));
+ valid_everywhere = true;
can_be_equijoin = true;
}
- else if (isouterjoin)
+ else if (bms_overlap(relids, outerjoin_nonnullable))
{
+ /*
+ * The qual is attached to an outer join and mentions (some of
+ * the) rels on the nonnullable side. Force the qual to be
+ * evaluated exactly at the level of joining corresponding to the
+ * outer join. We cannot let it get pushed down into the
+ * nonnullable side, since then we'd produce no output rows,
+ * rather than the intended single null-extended row, for any
+ * nonnullable-side rows failing the qual.
+ *
+ * Note: an outer-join qual that mentions only nullable-side rels can
+ * be pushed down into the nullable side without changing the join
+ * result, so we treat it the same as an ordinary inner-join qual.
+ */
relids = qualscope;
+ valid_everywhere = false;
can_be_equijoin = false;
}
else
{
- Relids newrelids = relids;
- List *relid;
-
/*
- * We rely on set_unioni to be nondestructive of its input
- * lists...
+ * For a non-outer-join qual, we can evaluate the qual as soon as
+ * (1) we have all the rels it mentions, and (2) we are at or
+ * above any outer joins that can null any of these rels and are
+ * below the syntactic location of the given qual. To enforce the
+ * latter, scan the base rels listed in relids, and merge their
+ * outer-join sets into the clause's own reference list. At the
+ * time we are called, the outerjoinset of each baserel will show
+ * exactly those outer joins that are below the qual in the join
+ * tree.
+ *
+ * We also need to determine whether the qual is "valid everywhere",
+ * which is true if the qual mentions no variables that are
+ * involved in lower-level outer joins (this may be an overly
+ * strong test).
*/
- can_be_equijoin = true;
- foreach(relid, relids)
+ Relids addrelids = NULL;
+ Relids tmprelids;
+ int relno;
+
+ valid_everywhere = true;
+ tmprelids = bms_copy(relids);
+ while ((relno = bms_first_member(tmprelids)) >= 0)
{
- RelOptInfo *rel = find_base_rel(root, lfirsti(relid));
+ RelOptInfo *rel = find_base_rel(root, relno);
- if (rel->outerjoinset &&
- !is_subseti(rel->outerjoinset, relids))
+ if (rel->outerjoinset != NULL)
{
- newrelids = set_unioni(newrelids, rel->outerjoinset);
-
- /*
- * Because application of the qual will be delayed by
- * outer join, we mustn't assume its vars are equal
- * everywhere.
- */
- can_be_equijoin = false;
+ addrelids = bms_add_members(addrelids, rel->outerjoinset);
+ valid_everywhere = false;
}
}
- relids = newrelids;
- /* Should still be a subset of current scope ... */
- Assert(is_subseti(relids, qualscope));
+ bms_free(tmprelids);
+
+ if (bms_is_subset(addrelids, relids))
+ {
+ /* Qual is not affected by any outer-join restriction */
+ can_be_equijoin = true;
+ }
+ else
+ {
+ relids = bms_union(relids, addrelids);
+ /* Should still be a subset of current scope ... */
+ Assert(bms_is_subset(relids, qualscope));
+
+ /*
+ * Because application of the qual will be delayed by outer
+ * join, we mustn't assume its vars are equal everywhere.
+ */
+ can_be_equijoin = false;
+ }
+ bms_free(addrelids);
}
/*
* same joinrel. A qual originating from WHERE is always considered
* "pushed down".
*/
- restrictinfo->ispusheddown = ispusheddown || !sameseti(relids,
- qualscope);
+ if (!is_pushed_down)
+ is_pushed_down = !bms_equal(relids, qualscope);
- if (length(relids) == 1)
+ /*
+ * Build the RestrictInfo node itself.
+ */
+ restrictinfo = make_restrictinfo((Expr *) clause,
+ is_pushed_down,
+ valid_everywhere);
+
+ /*
+ * Figure out where to attach it.
+ */
+ switch (bms_membership(relids))
{
- /*
- * There is only one relation participating in 'clause', so
- * 'clause' is a restriction clause for that relation.
- */
- RelOptInfo *rel = find_base_rel(root, lfirsti(relids));
+ case BMS_SINGLETON:
- /*
- * Check for a "mergejoinable" clause even though it's not a join
- * clause. This is so that we can recognize that "a.x = a.y"
- * makes x and y eligible to be considered equal, even when they
- * belong to the same rel. Without this, we would not recognize
- * that "a.x = a.y AND a.x = b.z AND a.y = c.q" allows us to
- * consider z and q equal after their rels are joined.
- */
- if (can_be_equijoin)
- check_mergejoinable(restrictinfo);
+ /*
+ * There is only one relation participating in 'clause', so
+ * 'clause' is a restriction clause for that relation.
+ */
+ rel = find_base_rel(root, bms_singleton_member(relids));
- /*
- * If the clause was deduced from implied equality, check to see
- * whether it is redundant with restriction clauses we already
- * have for this rel. Note we cannot apply this check to
- * user-written clauses, since we haven't found the canonical
- * pathkey sets yet while processing user clauses. (NB: no
- * comparable check is done in the join-clause case; redundancy
- * will be detected when the join clause is moved into a join
- * rel's restriction list.)
- */
- if (!isdeduced ||
- !qual_is_redundant(root, restrictinfo, rel->baserestrictinfo))
- {
- /* Add clause to rel's restriction list */
- rel->baserestrictinfo = lappend(rel->baserestrictinfo,
- restrictinfo);
- }
- }
- else if (relids != NIL)
- {
- /*
- * 'clause' is a join clause, since there is more than one rel in
- * the relid list. Set additional RestrictInfo fields for
- * joining.
- *
- * We don't bother setting the merge/hashjoin info if we're not going
- * to need it. We do want to know about mergejoinable ops in any
- * potential equijoin clause (see later in this routine), and we
- * ignore enable_mergejoin if isouterjoin is true, because
- * mergejoin is the only implementation we have for full and right
- * outer joins.
- */
- if (enable_mergejoin || isouterjoin || can_be_equijoin)
+ /*
+ * Check for a "mergejoinable" clause even though it's not a
+ * join clause. This is so that we can recognize that "a.x =
+ * a.y" makes x and y eligible to be considered equal, even
+ * when they belong to the same rel. Without this, we would
+ * not recognize that "a.x = a.y AND a.x = b.z AND a.y = c.q"
+ * allows us to consider z and q equal after their rels are
+ * joined.
+ */
+ if (can_be_equijoin)
+ check_mergejoinable(restrictinfo);
+
+ /*
+ * If the clause was deduced from implied equality, check to
+ * see whether it is redundant with restriction clauses we
+ * already have for this rel. Note we cannot apply this check
+ * to user-written clauses, since we haven't found the
+ * canonical pathkey sets yet while processing user clauses.
+ * (NB: no comparable check is done in the join-clause case;
+ * redundancy will be detected when the join clause is moved
+ * into a join rel's restriction list.)
+ */
+ if (!isdeduced ||
+ !qual_is_redundant(root, restrictinfo,
+ rel->baserestrictinfo))
+ {
+ /* Add clause to rel's restriction list */
+ rel->baserestrictinfo = lappend(rel->baserestrictinfo,
+ restrictinfo);
+ }
+ break;
+ case BMS_MULTIPLE:
+
+ /*
+ * 'clause' is a join clause, since there is more than one rel
+ * in the relid set.
+ */
+
+ /*
+ * Check for hash or mergejoinable operators.
+ *
+ * We don't bother setting the hashjoin info if we're not going
+ * to need it. We do want to know about mergejoinable ops in
+ * all cases, however, because we use mergejoinable ops for
+ * other purposes such as detecting redundant clauses.
+ */
check_mergejoinable(restrictinfo);
- if (enable_hashjoin)
- check_hashjoinable(restrictinfo);
+ if (enable_hashjoin)
+ check_hashjoinable(restrictinfo);
- /*
- * Add clause to the join lists of all the relevant relations.
- */
- add_join_info_to_rels(root, restrictinfo, relids);
+ /*
+ * Add clause to the join lists of all the relevant relations.
+ */
+ add_join_clause_to_rels(root, restrictinfo, relids);
- /*
- * Add vars used in the join clause to targetlists of their
- * relations, so that they will be emitted by the plan nodes that
- * scan those relations (else they won't be available at the join
- * node!).
- */
- add_vars_to_targetlist(root, vars);
- }
- else
- {
- /*
- * 'clause' references no rels, and therefore we have no place to
- * attach it. Shouldn't get here if callers are working properly.
- */
- elog(ERROR, "distribute_qual_to_rels: can't cope with variable-free clause");
+ /*
+ * Add vars used in the join clause to targetlists of their
+ * relations, so that they will be emitted by the plan nodes
+ * that scan those relations (else they won't be available at
+ * the join node!).
+ */
+ vars = pull_var_clause(clause, false);
+ add_vars_to_targetlist(root, vars, relids);
+ list_free(vars);
+ break;
+ default:
+
+ /*
+ * 'clause' references no rels, and therefore we have no place
+ * to attach it. Shouldn't get here if callers are working
+ * properly.
+ */
+ elog(ERROR, "cannot cope with variable-free clause");
+ break;
}
/*
* equivalence for future use. (We can skip this for a deduced
* clause, since the keys are already known equivalent in that case.)
*/
- if (can_be_equijoin && restrictinfo->mergejoinoperator != InvalidOid &&
+ if (can_be_equijoin &&
+ restrictinfo->mergejoinoperator != InvalidOid &&
!isdeduced)
add_equijoined_keys(root, restrictinfo);
}
-/*
- * add_join_info_to_rels
- * For every relation participating in a join clause, add 'restrictinfo' to
- * the appropriate joininfo list (creating a new list and adding it to the
- * appropriate rel node if necessary).
- *
- * 'restrictinfo' describes the join clause
- * 'join_relids' is the list of relations participating in the join clause
- */
-static void
-add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
- Relids join_relids)
-{
- List *join_relid;
-
- /* For every relid, find the joininfo, and add the proper join entries */
- foreach(join_relid, join_relids)
- {
- int cur_relid = lfirsti(join_relid);
- Relids unjoined_relids = NIL;
- JoinInfo *joininfo;
- List *otherrel;
-
- /* Get the relids not equal to the current relid */
- foreach(otherrel, join_relids)
- {
- if (lfirsti(otherrel) != cur_relid)
- unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel));
- }
-
- /*
- * Find or make the joininfo node for this combination of rels,
- * and add the restrictinfo node to it.
- */
- joininfo = find_joininfo_node(find_base_rel(root, cur_relid),
- unjoined_relids);
- joininfo->jinfo_restrictinfo = lappend(joininfo->jinfo_restrictinfo,
- restrictinfo);
- }
-}
-
/*
* process_implied_equality
* Check to see whether we already have a restrictinfo item that says
- * item1 = item2, and create one if not. This is a consequence of
- * transitivity of mergejoin equality: if we have mergejoinable
- * clauses A = B and B = C, we can deduce A = C (where = is an
- * appropriate mergejoinable operator).
+ * item1 = item2, and create one if not; or if delete_it is true,
+ * remove any such restrictinfo item.
+ *
+ * This processing is a consequence of transitivity of mergejoin equality:
+ * if we have mergejoinable clauses A = B and B = C, we can deduce A = C
+ * (where = is an appropriate mergejoinable operator). See path/pathkeys.c
+ * for more details.
*/
void
-process_implied_equality(Query *root, Node *item1, Node *item2,
- Oid sortop1, Oid sortop2)
+process_implied_equality(PlannerInfo *root,
+ Node *item1, Node *item2,
+ Oid sortop1, Oid sortop2,
+ Relids item1_relids, Relids item2_relids,
+ bool delete_it)
{
- Index irel1;
- Index irel2;
+ Relids relids;
+ BMS_Membership membership;
RelOptInfo *rel1;
List *restrictlist;
- List *itm;
+ ListCell *itm;
Oid ltype,
rtype;
Operator eq_operator;
Form_pg_operator pgopform;
Expr *clause;
+ /* Get set of relids referenced in the two expressions */
+ relids = bms_union(item1_relids, item2_relids);
+ membership = bms_membership(relids);
+
/*
- * Currently, since check_mergejoinable only accepts Var = Var
- * clauses, we should only see Var nodes here. Would have to work a
- * little harder to locate the right rel(s) if more-general mergejoin
- * clauses were accepted.
+ * generate_implied_equalities() shouldn't call me on two constants.
*/
- Assert(IsA(item1, Var));
- irel1 = ((Var *) item1)->varno;
- Assert(IsA(item2, Var));
- irel2 = ((Var *) item2)->varno;
+ Assert(membership != BMS_EMPTY_SET);
/*
- * If both vars belong to same rel, we need to look at that rel's
- * baserestrictinfo list. If different rels, each will have a
- * joininfo node for the other, and we can scan either list.
+ * If the exprs involve a single rel, we need to look at that rel's
+ * baserestrictinfo list. If multiple rels, any one will have a
+ * joininfo node for the rest, and we can scan any of 'em.
*/
- rel1 = find_base_rel(root, irel1);
- if (irel1 == irel2)
+ if (membership == BMS_SINGLETON)
+ {
+ rel1 = find_base_rel(root, bms_singleton_member(relids));
restrictlist = rel1->baserestrictinfo;
+ }
else
{
- JoinInfo *joininfo = find_joininfo_node(rel1,
- makeListi1(irel2));
+ Relids other_rels;
+ int first_rel;
+ JoinInfo *joininfo;
+
+ /* Copy relids, find and remove one member */
+ other_rels = bms_copy(relids);
+ first_rel = bms_first_member(other_rels);
- restrictlist = joininfo->jinfo_restrictinfo;
+ rel1 = find_base_rel(root, first_rel);
+
+ /* use remaining members to find join node */
+ joininfo = find_joininfo_node(rel1, other_rels);
+
+ restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL;
+
+ bms_free(other_rels);
}
/*
- * Scan to see if equality is already known.
+ * Scan to see if equality is already known. If so, we're done in the
+ * add case, and done after removing it in the delete case.
*/
foreach(itm, restrictlist)
{
if (restrictinfo->mergejoinoperator == InvalidOid)
continue; /* ignore non-mergejoinable clauses */
/* We now know the restrictinfo clause is a binary opclause */
- left = (Node *) get_leftop(restrictinfo->clause);
- right = (Node *) get_rightop(restrictinfo->clause);
+ left = get_leftop(restrictinfo->clause);
+ right = get_rightop(restrictinfo->clause);
if ((equal(item1, left) && equal(item2, right)) ||
(equal(item2, left) && equal(item1, right)))
- return; /* found a matching clause */
+ {
+ /* found a matching clause */
+ if (delete_it)
+ {
+ if (membership == BMS_SINGLETON)
+ {
+ /* delete it from local restrictinfo list */
+ rel1->baserestrictinfo = list_delete_ptr(rel1->baserestrictinfo,
+ restrictinfo);
+ }
+ else
+ {
+ /* let joininfo.c do it */
+ remove_join_clause_from_rels(root, restrictinfo, relids);
+ }
+ }
+ return; /* done */
+ }
}
+ /* Didn't find it. Done if deletion requested */
+ if (delete_it)
+ return;
+
/*
* This equality is new information, so construct a clause
* representing it to add to the query data structures.
*/
ltype = exprType(item1);
rtype = exprType(item2);
- eq_operator = compatible_oper(makeList1(makeString("=")),
+ eq_operator = compatible_oper(list_make1(makeString("=")),
ltype, rtype, true);
if (!HeapTupleIsValid(eq_operator))
{
* we have no suitable equality operator for the combination of
* datatypes? NO, because sortkey selection may screw up anyway.
*/
- elog(ERROR, "Unable to identify an equality operator for types '%s' and '%s'",
- format_type_be(ltype), format_type_be(rtype));
+ ereport(ERROR,
+ (errcode(ERRCODE_UNDEFINED_FUNCTION),
+ errmsg("could not identify an equality operator for types %s and %s",
+ format_type_be(ltype), format_type_be(rtype))));
}
pgopform = (Form_pg_operator) GETSTRUCT(eq_operator);
if (pgopform->oprlsortop != sortop1 ||
pgopform->oprrsortop != sortop2 ||
pgopform->oprresult != BOOLOID)
- elog(ERROR, "Equality operator for types '%s' and '%s' should be mergejoinable, but isn't",
- format_type_be(ltype), format_type_be(rtype));
-
- clause = makeNode(Expr);
- clause->typeOid = BOOLOID;
- clause->opType = OP_EXPR;
- clause->oper = (Node *) makeOper(oprid(eq_operator),/* opno */
- InvalidOid, /* opid */
- BOOLOID, /* opresulttype */
- false); /* opretset */
- clause->args = makeList2(item1, item2);
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_FUNCTION_DEFINITION),
+ errmsg("equality operator for types %s and %s should be merge-joinable, but isn't",
+ format_type_be(ltype), format_type_be(rtype))));
+
+ /*
+ * Now we can build the new clause. Copy to ensure it shares no
+ * substructure with original (this is necessary in case there are
+ * subselects in there...)
+ */
+ clause = make_opclause(oprid(eq_operator), /* opno */
+ BOOLOID, /* opresulttype */
+ false, /* opretset */
+ (Expr *) copyObject(item1),
+ (Expr *) copyObject(item2));
ReleaseSysCache(eq_operator);
/*
+ * Push the new clause into all the appropriate restrictinfo lists.
+ *
* Note: we mark the qual "pushed down" to ensure that it can never be
* taken for an original JOIN/ON clause.
*/
distribute_qual_to_rels(root, (Node *) clause,
- true, false, true,
- pull_varnos((Node *) clause));
+ true, true, NULL, relids);
}
/*
* SELECT * FROM tab WHERE f1 = f2 AND f2 = f3;
* We need to suppress the redundant condition to avoid computing
* too-small selectivity, not to mention wasting time at execution.
+ *
+ * Note: quals of the form "var = const" are never considered redundant,
+ * only those of the form "var = var". This is needed because when we
+ * have constants in an implied-equality set, we use a different strategy
+ * that suppresses all "var = var" deductions. We must therefore keep
+ * all the "var = const" quals.
*/
static bool
-qual_is_redundant(Query *root,
+qual_is_redundant(PlannerInfo *root,
RestrictInfo *restrictinfo,
List *restrictlist)
{
- List *oldquals;
- List *olditem;
Node *newleft;
Node *newright;
- List *equalvars;
+ List *oldquals;
+ ListCell *olditem;
+ List *equalexprs;
bool someadded;
+ /* Never redundant unless vars appear on both sides */
+ if (bms_is_empty(restrictinfo->left_relids) ||
+ bms_is_empty(restrictinfo->right_relids))
+ return false;
+
+ newleft = get_leftop(restrictinfo->clause);
+ newright = get_rightop(restrictinfo->clause);
+
/*
* Set cached pathkeys. NB: it is okay to do this now because this
* routine is only invoked while we are generating implied equalities.
return false;
/*
- * Now, we want to develop a list of Vars that are known equal to the
+ * Now, we want to develop a list of exprs that are known equal to the
* left side of the new qual. We traverse the old-quals list
- * repeatedly to transitively expand the Vars list. If at any point
- * we find we can reach the right-side Var of the new qual, we are
- * done. We give up when we can't expand the equalvars list any more.
+ * repeatedly to transitively expand the exprs list. If at any point
+ * we find we can reach the right-side expr of the new qual, we are
+ * done. We give up when we can't expand the equalexprs list any
+ * more.
*/
- newleft = (Node *) get_leftop(restrictinfo->clause);
- newright = (Node *) get_rightop(restrictinfo->clause);
- equalvars = makeList1(newleft);
+ equalexprs = list_make1(newleft);
do
{
someadded = false;
- foreach(olditem, oldquals)
+ /* cannot use foreach here because of possible list_delete */
+ olditem = list_head(oldquals);
+ while (olditem)
{
RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
- Node *oldleft = (Node *) get_leftop(oldrinfo->clause);
- Node *oldright = (Node *) get_rightop(oldrinfo->clause);
+ Node *oldleft = get_leftop(oldrinfo->clause);
+ Node *oldright = get_rightop(oldrinfo->clause);
Node *newguy = NULL;
- if (member(oldleft, equalvars))
+ /* must advance olditem before list_delete possibly pfree's it */
+ olditem = lnext(olditem);
+
+ if (list_member(equalexprs, oldleft))
newguy = oldright;
- else if (member(oldright, equalvars))
+ else if (list_member(equalexprs, oldright))
newguy = oldleft;
else
continue;
if (equal(newguy, newright))
return true; /* we proved new clause is redundant */
- equalvars = lcons(newguy, equalvars);
+ equalexprs = lcons(newguy, equalexprs);
someadded = true;
/*
* Remove this qual from list, since we don't need it anymore.
- * Note this doesn't break the foreach() loop, since lremove
- * doesn't touch the next-link of the removed cons cell.
*/
- oldquals = lremove(oldrinfo, oldquals);
+ oldquals = list_delete_ptr(oldquals, oldrinfo);
}
} while (someadded);
* info fields in the restrictinfo.
*
* Currently, we support mergejoin for binary opclauses where
- * both operands are simple Vars and the operator is a mergejoinable
- * operator.
+ * the operator is a mergejoinable operator. The arguments can be
+ * anything --- as long as there are no volatile functions in them.
*/
static void
check_mergejoinable(RestrictInfo *restrictinfo)
{
Expr *clause = restrictinfo->clause;
- Var *left,
- *right;
Oid opno,
leftOp,
rightOp;
- if (!is_opclause((Node *) clause))
+ if (!is_opclause(clause))
return;
-
- left = get_leftop(clause);
- right = get_rightop(clause);
-
- /* caution: is_opclause accepts more than I do, so check it */
- if (!right)
- return; /* unary opclauses need not apply */
- if (!IsA(left, Var) ||!IsA(right, Var))
+ if (list_length(((OpExpr *) clause)->args) != 2)
return;
- opno = ((Oper *) clause->oper)->opno;
+ opno = ((OpExpr *) clause)->opno;
if (op_mergejoinable(opno,
- left->vartype,
- right->vartype,
&leftOp,
- &rightOp))
+ &rightOp) &&
+ !contain_volatile_functions((Node *) clause))
{
restrictinfo->mergejoinoperator = opno;
restrictinfo->left_sortop = leftOp;
* info fields in the restrictinfo.
*
* Currently, we support hashjoin for binary opclauses where
- * both operands are simple Vars and the operator is a hashjoinable
- * operator.
+ * the operator is a hashjoinable operator. The arguments can be
+ * anything --- as long as there are no volatile functions in them.
*/
static void
check_hashjoinable(RestrictInfo *restrictinfo)
{
Expr *clause = restrictinfo->clause;
- Var *left,
- *right;
Oid opno;
- if (!is_opclause((Node *) clause))
+ if (!is_opclause(clause))
return;
-
- left = get_leftop(clause);
- right = get_rightop(clause);
-
- /* caution: is_opclause accepts more than I do, so check it */
- if (!right)
- return; /* unary opclauses need not apply */
- if (!IsA(left, Var) ||!IsA(right, Var))
+ if (list_length(((OpExpr *) clause)->args) != 2)
return;
- opno = ((Oper *) clause->oper)->opno;
+ opno = ((OpExpr *) clause)->opno;
- if (op_hashjoinable(opno,
- left->vartype,
- right->vartype))
+ if (op_hashjoinable(opno) &&
+ !contain_volatile_functions((Node *) clause))
restrictinfo->hashjoinoperator = opno;
}