* initsplan.c
* Target list, qualification, joininfo initialization routines
*
- * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
+ * 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.50 2000/09/12 21:06:54 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.106 2005/06/05 22:32:55 tgl Exp $
*
*-------------------------------------------------------------------------
*/
-#include <sys/types.h>
-
#include "postgres.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 "parser/parse_expr.h"
#include "parser/parse_oper.h"
-#include "parser/parse_type.h"
+#include "utils/builtins.h"
#include "utils/lsyscache.h"
-
-
-static void mark_baserels_for_outer_join(Query *root, Relids rels,
- Relids outerrels);
-static void add_restrict_and_join_to_rel(Query *root, Node *clause,
- bool isjoinqual,
- Relids outerjoinrelids);
-static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
- Relids join_relids);
-static void add_vars_to_targetlist(Query *root, List *vars);
+#include "utils/syscache.h"
+
+
+static void mark_baserels_for_outer_join(PlannerInfo *root, Relids rels,
+ Relids outerrels);
+static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
+ bool is_pushed_down,
+ bool isdeduced,
+ Relids outerjoin_nonnullable,
+ Relids qualscope);
+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);
/*****************************************************************************
*
- * TARGET LISTS
+ * JOIN TREES
*
*****************************************************************************/
/*
- * build_base_rel_tlists
- * Creates rel nodes for every relation mentioned in the target list
- * 'tlist' (if a node hasn't already been created) and adds them to
- * root->base_rel_list. Creates targetlist entries for each var seen
- * in 'tlist' and adds them to the tlist of the appropriate rel node.
+ * add_base_rels_to_query
+ *
+ * Scan the query's jointree and create baserel RelOptInfos for all
+ * 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 later to build rels for inheritance children.
*/
void
-build_base_rel_tlists(Query *root, List *tlist)
+add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
{
- List *tlist_vars = pull_var_clause((Node *) tlist, false);
-
- add_vars_to_targetlist(root, tlist_vars);
- freeList(tlist_vars);
-}
+ if (jtnode == NULL)
+ return;
+ if (IsA(jtnode, RangeTblRef))
+ {
+ int varno = ((RangeTblRef *) jtnode)->rtindex;
-/*
- * add_vars_to_targetlist
- * For each variable appearing in the list, add it to the relation's
- * targetlist if not already present. Rel nodes will also be created
- * if not already present.
- */
-static void
-add_vars_to_targetlist(Query *root, List *vars)
-{
- List *temp;
+ build_base_rel(root, varno);
+ }
+ else if (IsA(jtnode, FromExpr))
+ {
+ FromExpr *f = (FromExpr *) jtnode;
+ ListCell *l;
- foreach(temp, vars)
+ foreach(l, f->fromlist)
+ add_base_rels_to_query(root, lfirst(l));
+ }
+ else if (IsA(jtnode, JoinExpr))
{
- Var *var = (Var *) lfirst(temp);
- RelOptInfo *rel = get_base_rel(root, var->varno);
+ JoinExpr *j = (JoinExpr *) jtnode;
- add_var_to_tlist(rel, var);
+ add_base_rels_to_query(root, j->larg);
+ add_base_rels_to_query(root, j->rarg);
}
+ else
+ elog(ERROR, "unrecognized node type: %d",
+ (int) nodeTag(jtnode));
}
-/*----------
- * add_missing_rels_to_query
+
+/*****************************************************************************
*
- * If we have a relation listed in the join tree that does not appear
- * in the target list nor qualifications, we must add it to the base
- * relation list so that it can be processed. For instance,
- * select f.x from foo f, foo f2
- * is a join of f and f2. Note that if we have
- * select foo.x from foo f
- * this also gets turned into a join (between foo as foo and foo as f).
+ * TARGET LISTS
*
- * To avoid putting useless entries into the per-relation targetlists,
- * this should only be called after all the variables in the targetlist
- * and quals have been processed by the routines above.
+ *****************************************************************************/
+
+/*
+ * build_base_rel_tlists
+ * Add targetlist entries for each var needed in the query's final tlist
+ * to the appropriate base relations.
*
- * Returns a list of all the base relations (RelOptInfo nodes) that appear
- * in the join tree. This list can be used for cross-checking in the
- * reverse direction, ie, that we have a join tree entry for every
- * relation used in the query.
- *----------
+ * We mark such vars as needed by "relation 0" to ensure that they will
+ * propagate up through all join plan steps.
*/
-List *
-add_missing_rels_to_query(Query *root, Node *jtnode)
+void
+build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
{
- List *result = NIL;
+ List *tlist_vars = pull_var_clause((Node *) final_tlist, false);
- if (jtnode == NULL)
- return NIL;
- if (IsA(jtnode, List))
+ if (tlist_vars != NIL)
{
- List *l;
-
- foreach(l, (List *) jtnode)
- {
- result = nconc(result,
- add_missing_rels_to_query(root, lfirst(l)));
- }
+ add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
+ list_free(tlist_vars);
}
- else if (IsA(jtnode, RangeTblRef))
- {
- int varno = ((RangeTblRef *) jtnode)->rtindex;
- RelOptInfo *rel = get_base_rel(root, varno);
+}
- /*
- * If the rel isn't otherwise referenced, give it a dummy
- * targetlist consisting of its own OID.
- */
- if (rel->targetlist == NIL)
- {
- Var *var = makeVar(varno, ObjectIdAttributeNumber,
- OIDOID, -1, 0);
+/*
+ * add_vars_to_targetlist
+ * For each variable appearing in the list, add it to the owning
+ * 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(PlannerInfo *root, List *vars, Relids where_needed)
+{
+ ListCell *temp;
- add_var_to_tlist(rel, var);
- }
+ Assert(!bms_is_empty(where_needed));
- result = lcons(rel, NIL);
- }
- else if (IsA(jtnode, JoinExpr))
+ foreach(temp, vars)
{
- JoinExpr *j = (JoinExpr *) jtnode;
+ Var *var = (Var *) lfirst(temp);
+ RelOptInfo *rel = find_base_rel(root, var->varno);
+ int attrno = var->varattno;
- result = add_missing_rels_to_query(root, j->larg);
- result = nconc(result,
- add_missing_rels_to_query(root, j->rarg));
+ Assert(attrno >= rel->min_attr && attrno <= rel->max_attr);
+ attrno -= rel->min_attr;
+ if (bms_is_empty(rel->attr_needed[attrno]))
+ {
+ /* 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);
}
- else
- elog(ERROR, "add_missing_rels_to_query: unexpected node type %d",
- nodeTag(jtnode));
- return result;
}
/*
- * add_join_quals_to_rels
- * Recursively scan the join tree for JOIN/ON (and JOIN/USING) qual
- * clauses, and add these to the appropriate JoinInfo lists. Also,
- * mark base RelOptInfos with outerjoinset information, which will
- * be needed for proper placement of WHERE clauses during
- * add_restrict_and_join_to_rels().
+ * 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
+ * with outerjoinset information, to aid in proper positioning of qual
+ * clauses that appear above outer joins.
*
* NOTE: when dealing with inner joins, it is appropriate to let a qual clause
* be evaluated at the lowest level where all the variables it mentions are
- * available. However, we cannot do this within an outer join since the qual
- * might eliminate matching rows and cause a NULL row to be added improperly.
- * Therefore, rels appearing within (the nullable side 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 a rel, thereby forcing them up the join tree to the right level.
+ * available. However, we cannot push a qual down into the nullable side(s)
+ * 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 = 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, add_join_quals_to_rels() returns
- * the list of Relids involved in its own level of join. This is just an
+ * To ease the calculation of these values, distribute_quals_to_rels() returns
+ * 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
-add_join_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;
- if (IsA(jtnode, List))
+ if (IsA(jtnode, RangeTblRef))
{
- List *l;
+ int varno = ((RangeTblRef *) jtnode)->rtindex;
- /*
- * Note: we assume it's impossible to see same RT index from more
- * than one subtree, so nconc() is OK rather than LispUnioni().
- */
- foreach(l, (List *) jtnode)
- result = nconc(result,
- add_join_quals_to_rels(root, lfirst(l)));
+ /* No quals to deal with, just return correct result */
+ result = bms_make_singleton(varno);
}
- else if (IsA(jtnode, RangeTblRef))
+ else if (IsA(jtnode, FromExpr))
{
- int varno = ((RangeTblRef *) jtnode)->rtindex;
+ FromExpr *f = (FromExpr *) jtnode;
+ ListCell *l;
- /* No quals to deal with, just return correct result */
- result = lconsi(varno, NIL);
+ /*
+ * First, recurse to handle child joins.
+ */
+ foreach(l, f->fromlist)
+ {
+ 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(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,
- outerjoinids;
- List *qual;
+ 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, quals above us in the join tree, and WHERE quals.
- * Finally we place our own join quals.
+ * 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 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 = add_join_quals_to_rels(root, j->larg);
- rightids = add_join_quals_to_rels(root, j->rarg);
+ 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);
- outerjoinids = NIL;
+ 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);
- outerjoinids = result;
+ nonnullable_rels = leftids;
+ nullable_rels = rightids;
break;
case JOIN_FULL:
- mark_baserels_for_outer_join(root, result, result);
- outerjoinids = result;
+ /* 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);
- outerjoinids = result;
+ 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 ...
+ * 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, "add_join_quals_to_rels: unsupported join type %d",
+ elog(ERROR, "unrecognized join type: %d",
(int) j->jointype);
break;
}
foreach(qual, (List *) j->quals)
- add_restrict_and_join_to_rel(root, (Node *) lfirst(qual),
- true, outerjoinids);
+ distribute_qual_to_rels(root, (Node *) lfirst(qual),
+ false, false,
+ nonnullable_rels, result);
+
+ if (nullable_rels != NULL)
+ mark_baserels_for_outer_join(root, nullable_rels, result);
}
else
- elog(ERROR, "add_join_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)
{
- RelOptInfo *rel = get_base_rel(root, 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/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/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 == NULL)
+ {
+ 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);
}
/*
- * add_restrict_and_join_to_rels
- * Fill RestrictInfo and JoinInfo lists of relation entries for all
- * relations appearing within clauses. Creates new relation entries if
- * necessary, adding them to root->base_rel_list.
- *
- * 'clauses': the list of clauses in the cnfify'd query qualification.
- */
-void
-add_restrict_and_join_to_rels(Query *root, List *clauses)
-{
- List *clause;
-
- foreach(clause, clauses)
- add_restrict_and_join_to_rel(root, (Node *) lfirst(clause),
- false, NIL);
-}
-
-/*
- * add_restrict_and_join_to_rel
+ * distribute_qual_to_rels
* Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
* (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
+ * '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)
+ * 'isdeduced': TRUE if the qual came from implied-equality deduction
+ * '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
*
- * isjoinqual is true if the clause came from JOIN/ON or JOIN/USING;
- * we have to mark the created RestrictInfo accordingly. If the JOIN
- * is an OUTER join, the caller must set outerjoinrelids = all relids of join,
- * which will override the joinrel identifiers extracted from the clause
- * itself. For inner join quals and WHERE clauses, set outerjoinrelids = NIL.
- * (Passing the whole list, and not just an "isouterjoin" boolean, is simply
- * a speed optimization: we could extract the same list from the base rels'
- * outerjoinsets, but since add_join_quals_to_rels() already knows what we
- * should use, might as well pass it in instead of recalculating it.)
+ * '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
+ * 'is_pushed_down' will be TRUE.
*/
static void
-add_restrict_and_join_to_rel(Query *root, Node *clause,
- bool isjoinqual,
- Relids outerjoinrelids)
+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->isjoinqual = isjoinqual;
- restrictinfo->subclauseindices = NIL;
- restrictinfo->mergejoinoperator = InvalidOid;
- restrictinfo->left_sortop = InvalidOid;
- restrictinfo->right_sortop = InvalidOid;
- restrictinfo->hashjoinoperator = InvalidOid;
+ 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);
/*
- * If caller has given us a join relid list, use it; otherwise, we must
- * scan the referenced base rels and add in any outer-join rel lists.
- * This prevents the clause from being applied at a lower level of joining
- * than any OUTER JOIN that should be evaluated before it.
+ * Cross-check: clause should contain no relids not within its scope.
+ * Otherwise the parser messed up.
*/
- if (outerjoinrelids)
- {
- /* Safety check: parser should have enforced this to start with */
- if (! is_subseti(relids, outerjoinrelids))
- elog(ERROR, "JOIN qualification may not refer to other relations");
- relids = outerjoinrelids;
- can_be_equijoin = false;
- }
- else
- {
- Relids newrelids = relids;
- List *relid;
+ if (!bms_is_subset(relids, qualscope))
+ elog(ERROR, "JOIN qualification may not refer to other relations");
- /* We rely on LispUnioni to be nondestructive of its input lists... */
- can_be_equijoin = true;
- foreach(relid, relids)
- {
- RelOptInfo *rel = get_base_rel(root, lfirsti(relid));
-
- if (rel->outerjoinset)
- {
- newrelids = LispUnioni(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;
- }
- }
- relids = newrelids;
- }
+ /*
+ * If the clause is variable-free, we force it to be evaluated at its
+ * original syntactic level. Note that this should not happen for
+ * top-level clauses, because query_planner() special-cases them. But
+ * 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 (bms_is_empty(relids))
+ relids = qualscope;
- if (length(relids) == 1)
+ /*
+ * Check to see if clause application must be delayed by outer-join
+ * considerations.
+ */
+ if (isdeduced)
{
-
/*
- * There is only one relation participating in 'clause', so
- * 'clause' is a restriction clause for that relation.
+ * 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).
*/
- RelOptInfo *rel = get_base_rel(root, lfirsti(relids));
-
- rel->baserestrictinfo = lcons(restrictinfo,
- rel->baserestrictinfo);
-
- /*
- * 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);
+ Assert(bms_equal(relids, qualscope));
+ valid_everywhere = true;
+ can_be_equijoin = true;
}
- else if (relids != NIL)
+ else if (bms_overlap(relids, outerjoin_nonnullable))
{
-
/*
- * 'clause' is a join clause, since there is more than one rel in
- * the relid list. Set additional RestrictInfo fields for
- * joining.
+ * 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.
*
- * We don't bother setting the merge/hashjoin info if we're not
- * going to need it.
- */
- if (enable_mergejoin || can_be_equijoin)
- check_mergejoinable(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 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!).
+ * 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.
*/
- add_vars_to_targetlist(root, vars);
+ relids = qualscope;
+ valid_everywhere = false;
+ can_be_equijoin = false;
}
else
{
/*
- * 'clause' references no rels, and therefore we have no place to
- * attach it. This means query_planner() screwed up --- it should
- * treat variable-less clauses separately.
+ * 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).
*/
- elog(ERROR, "add_restrict_and_join_to_rel: can't cope with variable-free clause");
+ 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, relno);
+
+ if (rel->outerjoinset != NULL)
+ {
+ addrelids = bms_add_members(addrelids, rel->outerjoinset);
+ valid_everywhere = false;
+ }
+ }
+ 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);
}
/*
- * If the clause has a mergejoinable operator, and is not an outer-join
- * qualification nor bubbled up due to an outer join, then the two sides
- * represent equivalent PathKeyItems for path keys: any path that is
- * sorted by one side will also be sorted by the other (as soon as the
- * two rels are joined, that is). Record the key equivalence for future
- * use.
+ * Mark the qual as "pushed down" if it can be applied at a level
+ * below its original syntactic level. This allows us to distinguish
+ * original JOIN/ON quals from higher-level quals pushed down to the
+ * same joinrel. A qual originating from WHERE is always considered
+ * "pushed down".
*/
- if (can_be_equijoin && restrictinfo->mergejoinoperator != InvalidOid)
- add_equijoined_keys(root, restrictinfo);
-}
+ if (!is_pushed_down)
+ is_pushed_down = !bms_equal(relids, qualscope);
-/*
- * 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;
+ /*
+ * Build the RestrictInfo node itself.
+ */
+ restrictinfo = make_restrictinfo((Expr *) clause,
+ is_pushed_down,
+ valid_everywhere);
- /* For every relid, find the joininfo, and add the proper join entries */
- foreach(join_relid, join_relids)
+ /*
+ * Figure out where to attach it.
+ */
+ switch (bms_membership(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(get_base_rel(root, cur_relid),
- unjoined_relids);
- joininfo->jinfo_restrictinfo = lcons(restrictinfo,
- joininfo->jinfo_restrictinfo);
+ case BMS_SINGLETON:
+
+ /*
+ * 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));
+
+ /*
+ * 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);
+
+ /*
+ * 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!).
+ */
+ 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;
}
+
+ /*
+ * If the clause has a mergejoinable operator, and is not an
+ * outer-join qualification nor bubbled up due to an outer join, then
+ * the two sides represent equivalent PathKeyItems for path keys: any
+ * path that is sorted by one side will also be sorted by the other
+ * (as soon as the two rels are joined, that is). Record the key
+ * 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 &&
+ !isdeduced)
+ add_equijoined_keys(root, 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 = get_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,
- lconsi(irel2, NIL));
+ 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);
+
+ rel1 = find_base_rel(root, first_rel);
- restrictlist = joininfo->jinfo_restrictinfo;
+ /* 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 = oper("=", ltype, rtype, true);
+ 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'",
- typeidTypeName(ltype), typeidTypeName(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);
+
/*
* Let's just make sure this appears to be a compatible 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",
- typeidTypeName(ltype), typeidTypeName(rtype));
-
- clause = makeNode(Expr);
- clause->typeOid = BOOLOID;
- clause->opType = OP_EXPR;
- clause->oper = (Node *) makeOper(oprid(eq_operator), /* opno */
- InvalidOid, /* opid */
- BOOLOID); /* operator result type */
- clause->args = lcons(item1, lcons(item2, NIL));
-
- add_restrict_and_join_to_rel(root, (Node *) clause,
- false, NIL);
+ 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, true, NULL, relids);
+}
+
+/*
+ * qual_is_redundant
+ * Detect whether an implied-equality qual that turns out to be a
+ * restriction clause for a single base relation is redundant with
+ * already-known restriction clauses for that rel. This occurs with,
+ * for example,
+ * 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(PlannerInfo *root,
+ RestrictInfo *restrictinfo,
+ List *restrictlist)
+{
+ Node *newleft;
+ Node *newright;
+ 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.
+ * Therefore, the equi_key_list is already complete and so we can
+ * correctly determine canonical pathkeys.
+ */
+ cache_mergeclause_pathkeys(root, restrictinfo);
+ /* If different, say "not redundant" (should never happen) */
+ if (restrictinfo->left_pathkey != restrictinfo->right_pathkey)
+ return false;
+
+ /*
+ * Scan existing quals to find those referencing same pathkeys.
+ * Usually there will be few, if any, so build a list of just the
+ * interesting ones.
+ */
+ oldquals = NIL;
+ foreach(olditem, restrictlist)
+ {
+ RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
+
+ if (oldrinfo->mergejoinoperator != InvalidOid)
+ {
+ cache_mergeclause_pathkeys(root, oldrinfo);
+ if (restrictinfo->left_pathkey == oldrinfo->left_pathkey &&
+ restrictinfo->right_pathkey == oldrinfo->right_pathkey)
+ oldquals = lcons(oldrinfo, oldquals);
+ }
+ }
+ if (oldquals == NIL)
+ return false;
+
+ /*
+ * 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 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.
+ */
+ equalexprs = list_make1(newleft);
+ do
+ {
+ someadded = false;
+ /* cannot use foreach here because of possible list_delete */
+ olditem = list_head(oldquals);
+ while (olditem)
+ {
+ RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
+ Node *oldleft = get_leftop(oldrinfo->clause);
+ Node *oldright = get_rightop(oldrinfo->clause);
+ Node *newguy = NULL;
+
+ /* must advance olditem before list_delete possibly pfree's it */
+ olditem = lnext(olditem);
+
+ if (list_member(equalexprs, oldleft))
+ newguy = oldright;
+ else if (list_member(equalexprs, oldright))
+ newguy = oldleft;
+ else
+ continue;
+ if (equal(newguy, newright))
+ return true; /* we proved new clause is redundant */
+ equalexprs = lcons(newguy, equalexprs);
+ someadded = true;
+
+ /*
+ * Remove this qual from list, since we don't need it anymore.
+ */
+ oldquals = list_delete_ptr(oldquals, oldrinfo);
+ }
+ } while (someadded);
+
+ return false; /* it's not redundant */
}
* 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;
}
projects / postgresql / blobdiff