* initsplan.c
* Target list, qualification, joininfo initialization routines
*
- * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.94 2003/12/30 23:53:14 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.142 2008/08/17 01:19:59 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
-#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
-#include "optimizer/tlist.h"
+#include "optimizer/prep.h"
+#include "optimizer/restrictinfo.h"
#include "optimizer/var.h"
-#include "parser/parsetree.h"
#include "parser/parse_expr.h"
#include "parser/parse_oper.h"
#include "utils/builtins.h"
#include "utils/syscache.h"
-static void mark_baserels_for_outer_join(Query *root, Relids rels,
- Relids outerrels);
-static void distribute_qual_to_rels(Query *root, Node *clause,
- bool ispusheddown,
- bool isdeduced,
- Relids outerjoin_nonnullable,
- Relids qualscope);
-static void add_vars_to_targetlist(Query *root, List *vars,
- Relids where_needed);
-static bool qual_is_redundant(Query *root, RestrictInfo *restrictinfo,
- List *restrictlist);
+/* These parameters are set by GUC */
+int from_collapse_limit;
+int join_collapse_limit;
+
+
+static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
+ bool below_outer_join,
+ Relids *qualscope, Relids *inner_join_rels);
+static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
+ Relids left_rels, Relids right_rels,
+ Relids inner_join_rels,
+ JoinType jointype, List *clause);
+static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
+ bool is_deduced,
+ bool below_outer_join,
+ Relids qualscope,
+ Relids ojscope,
+ Relids outerjoin_nonnullable);
+static void distribute_sublink_quals_to_rels(PlannerInfo *root,
+ FlattenedSubLink *fslink,
+ bool below_outer_join);
+static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
+ bool is_pushed_down);
+static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
static void check_mergejoinable(RestrictInfo *restrictinfo);
static void check_hashjoinable(RestrictInfo *restrictinfo);
* the base relations (ie, table, subquery, and function RTEs)
* appearing in the jointree.
*
+ * The initial invocation must pass root->parse->jointree as the value of
+ * jtnode. Internally, the function recurses through 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.
+ * is the only place that should call build_simple_rel with reloptkind
+ * RELOPT_BASEREL. (Note: build_simple_rel recurses internally to build
+ * "other rel" RelOptInfos for the members of any appendrels we find here.)
*/
void
-add_base_rels_to_query(Query *root, Node *jtnode)
+add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
{
if (jtnode == NULL)
return;
{
int varno = ((RangeTblRef *) jtnode)->rtindex;
- build_base_rel(root, varno);
+ (void) build_simple_rel(root, varno, RELOPT_BASEREL);
}
else if (IsA(jtnode, FromExpr))
{
FromExpr *f = (FromExpr *) jtnode;
- List *l;
+ ListCell *l;
foreach(l, f->fromlist)
add_base_rels_to_query(root, lfirst(l));
* propagate up through all join plan steps.
*/
void
-build_base_rel_tlists(Query *root, List *final_tlist)
+build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
{
List *tlist_vars = pull_var_clause((Node *) final_tlist, false);
if (tlist_vars != NIL)
{
add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
- freeList(tlist_vars);
+ list_free(tlist_vars);
}
}
* 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, Relids where_needed)
+void
+add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
{
- List *temp;
+ ListCell *temp;
Assert(!bms_is_empty(where_needed));
{
/* Variable not yet requested, so add to reltargetlist */
/* XXX is copyObject necessary here? */
- FastAppend(&rel->reltargetlist, copyObject(var));
+ rel->reltargetlist = lappend(rel->reltargetlist, copyObject(var));
}
rel->attr_needed[attrno] = bms_add_members(rel->attr_needed[attrno],
where_needed);
/*****************************************************************************
*
- * QUALIFICATIONS
+ * JOIN TREE PROCESSING
*
*****************************************************************************/
-
/*
- * distribute_quals_to_rels
+ * deconstruct_jointree
* 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.
+ * clauses, and add these to the appropriate restrictinfo and joininfo
+ * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes
+ * to root->join_info_list for any outer joins appearing in the query tree.
+ * Return a "joinlist" data structure showing the join order decisions
+ * that need to be made by make_one_rel().
+ *
+ * The "joinlist" result is a list of items that are either RangeTblRef
+ * jointree nodes or sub-joinlists. All the items at the same level of
+ * joinlist must be joined in an order to be determined by make_one_rel()
+ * (note that legal orders may be constrained by SpecialJoinInfo nodes).
+ * A sub-joinlist represents a subproblem to be planned separately. Currently
+ * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
+ * subproblems is stopped by join_collapse_limit or from_collapse_limit.
*
* 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 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, 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.
+ * NULL row to be incorrectly emitted by the join. Therefore, we artificially
+ * OR the minimum-relids of such an outer join into the required_relids of
+ * clauses appearing above it. This forces those clauses to be delayed until
+ * application of the outer join (or maybe even higher in the join tree).
*/
-Relids
-distribute_quals_to_rels(Query *root, Node *jtnode)
+List *
+deconstruct_jointree(PlannerInfo *root)
{
- Relids result = NULL;
+ Relids qualscope;
+ Relids inner_join_rels;
+
+ /* Start recursion at top of jointree */
+ Assert(root->parse->jointree != NULL &&
+ IsA(root->parse->jointree, FromExpr));
+
+ return deconstruct_recurse(root, (Node *) root->parse->jointree, false,
+ &qualscope, &inner_join_rels);
+}
+
+/*
+ * deconstruct_recurse
+ * One recursion level of deconstruct_jointree processing.
+ *
+ * Inputs:
+ * jtnode is the jointree node to examine
+ * below_outer_join is TRUE if this node is within the nullable side of a
+ * higher-level outer join
+ * Outputs:
+ * *qualscope gets the set of base Relids syntactically included in this
+ * jointree node (do not modify or free this, as it may also be pointed
+ * to by RestrictInfo and SpecialJoinInfo nodes)
+ * *inner_join_rels gets the set of base Relids syntactically included in
+ * inner joins appearing at or below this jointree node (do not modify
+ * or free this, either)
+ * Return value is the appropriate joinlist for this jointree node
+ *
+ * In addition, entries will be added to root->join_info_list for outer joins.
+ */
+static List *
+deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
+ Relids *qualscope, Relids *inner_join_rels)
+{
+ List *joinlist;
if (jtnode == NULL)
- return result;
+ {
+ *qualscope = NULL;
+ *inner_join_rels = NULL;
+ return NIL;
+ }
if (IsA(jtnode, RangeTblRef))
{
int varno = ((RangeTblRef *) jtnode)->rtindex;
/* No quals to deal with, just return correct result */
- result = bms_make_singleton(varno);
+ *qualscope = bms_make_singleton(varno);
+ /* A single baserel does not create an inner join */
+ *inner_join_rels = NULL;
+ joinlist = list_make1(jtnode);
}
else if (IsA(jtnode, FromExpr))
{
FromExpr *f = (FromExpr *) jtnode;
- List *l;
- List *qual;
+ int remaining;
+ ListCell *l;
/*
- * First, recurse to handle child joins.
+ * First, recurse to handle child joins. We collapse subproblems into
+ * a single joinlist whenever the resulting joinlist wouldn't exceed
+ * from_collapse_limit members. Also, always collapse one-element
+ * subproblems, since that won't lengthen the joinlist anyway.
*/
+ *qualscope = NULL;
+ *inner_join_rels = NULL;
+ joinlist = NIL;
+ remaining = list_length(f->fromlist);
foreach(l, f->fromlist)
{
- result = bms_add_members(result,
- distribute_quals_to_rels(root,
- lfirst(l)));
+ Relids sub_qualscope;
+ List *sub_joinlist;
+ int sub_members;
+
+ sub_joinlist = deconstruct_recurse(root, lfirst(l),
+ below_outer_join,
+ &sub_qualscope,
+ inner_join_rels);
+ *qualscope = bms_add_members(*qualscope, sub_qualscope);
+ sub_members = list_length(sub_joinlist);
+ remaining--;
+ if (sub_members <= 1 ||
+ list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
+ joinlist = list_concat(joinlist, sub_joinlist);
+ else
+ joinlist = lappend(joinlist, sub_joinlist);
}
/*
- * Now process the top-level quals. These are always marked as
- * "pushed down", since they clearly didn't come from a JOIN expr.
+ * A FROM with more than one list element is an inner join subsuming
+ * all below it, so we should report inner_join_rels = qualscope. If
+ * there was exactly one element, we should (and already did) report
+ * whatever its inner_join_rels were. If there were no elements (is
+ * that possible?) the initialization before the loop fixed it.
+ */
+ if (list_length(f->fromlist) > 1)
+ *inner_join_rels = *qualscope;
+
+ /*
+ * Now process the top-level quals.
*/
- foreach(qual, (List *) f->quals)
- distribute_qual_to_rels(root, (Node *) lfirst(qual),
- true, false, NULL, result);
+ foreach(l, (List *) f->quals)
+ {
+ Node *qual = (Node *) lfirst(l);
+
+ /* FlattenedSubLink wrappers need special processing */
+ if (qual && IsA(qual, FlattenedSubLink))
+ distribute_sublink_quals_to_rels(root,
+ (FlattenedSubLink *) qual,
+ below_outer_join);
+ else
+ distribute_qual_to_rels(root, qual,
+ false, below_outer_join,
+ *qualscope, NULL, NULL);
+ }
}
else if (IsA(jtnode, JoinExpr))
{
JoinExpr *j = (JoinExpr *) jtnode;
Relids leftids,
rightids,
+ left_inners,
+ right_inners,
nonnullable_rels,
- nullable_rels;
- List *qual;
+ ojscope;
+ List *leftjoinlist,
+ *rightjoinlist;
+ SpecialJoinInfo *sjinfo;
+ ListCell *l;
/*
- * 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.)
+ * 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 create a join_info_list entry for the join. 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 = bms_union(leftids, rightids);
-
- nonnullable_rels = nullable_rels = NULL;
switch (j->jointype)
{
case JOIN_INNER:
+ leftjoinlist = deconstruct_recurse(root, j->larg,
+ below_outer_join,
+ &leftids, &left_inners);
+ rightjoinlist = deconstruct_recurse(root, j->rarg,
+ below_outer_join,
+ &rightids, &right_inners);
+ *qualscope = bms_union(leftids, rightids);
+ *inner_join_rels = *qualscope;
/* Inner join adds no restrictions for quals */
+ nonnullable_rels = NULL;
break;
case JOIN_LEFT:
+ case JOIN_ANTI:
+ leftjoinlist = deconstruct_recurse(root, j->larg,
+ below_outer_join,
+ &leftids, &left_inners);
+ rightjoinlist = deconstruct_recurse(root, j->rarg,
+ true,
+ &rightids, &right_inners);
+ *qualscope = bms_union(leftids, rightids);
+ *inner_join_rels = bms_union(left_inners, right_inners);
nonnullable_rels = leftids;
- nullable_rels = rightids;
break;
case JOIN_FULL:
+ leftjoinlist = deconstruct_recurse(root, j->larg,
+ true,
+ &leftids, &left_inners);
+ rightjoinlist = deconstruct_recurse(root, j->rarg,
+ true,
+ &rightids, &right_inners);
+ *qualscope = bms_union(leftids, rightids);
+ *inner_join_rels = bms_union(left_inners, right_inners);
/* each side is both outer and inner */
- nonnullable_rels = result;
- nullable_rels = result;
- break;
- case JOIN_RIGHT:
- 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 ...
- */
- ereport(ERROR,
- (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
- errmsg("UNION JOIN is not implemented")));
+ nonnullable_rels = *qualscope;
break;
default:
+ /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
elog(ERROR, "unrecognized join type: %d",
(int) j->jointype);
+ nonnullable_rels = NULL; /* keep compiler quiet */
+ leftjoinlist = rightjoinlist = NIL;
break;
}
- foreach(qual, (List *) j->quals)
- distribute_qual_to_rels(root, (Node *) lfirst(qual),
- false, false,
- nonnullable_rels, result);
+ /*
+ * For an OJ, form the SpecialJoinInfo now, because we need the OJ's
+ * semantic scope (ojscope) to pass to distribute_qual_to_rels. But
+ * we mustn't add it to join_info_list just yet, because we don't want
+ * distribute_qual_to_rels to think it is an outer join below us.
+ */
+ if (j->jointype != JOIN_INNER)
+ {
+ sjinfo = make_outerjoininfo(root,
+ leftids, rightids,
+ *inner_join_rels,
+ j->jointype,
+ (List *) j->quals);
+ ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+ }
+ else
+ {
+ sjinfo = NULL;
+ ojscope = NULL;
+ }
+
+ /* Process the qual clauses */
+ foreach(l, (List *) j->quals)
+ {
+ Node *qual = (Node *) lfirst(l);
+
+ /* FlattenedSubLink wrappers need special processing */
+ if (qual && IsA(qual, FlattenedSubLink))
+ distribute_sublink_quals_to_rels(root,
+ (FlattenedSubLink *) qual,
+ below_outer_join);
+ else
+ distribute_qual_to_rels(root, qual,
+ false, below_outer_join,
+ *qualscope,
+ ojscope, nonnullable_rels);
+ }
+
+ /* Now we can add the SpecialJoinInfo to join_info_list */
+ if (sjinfo)
+ root->join_info_list = lappend(root->join_info_list, sjinfo);
- if (nullable_rels != NULL)
- mark_baserels_for_outer_join(root, nullable_rels, result);
+ /*
+ * Finally, compute the output joinlist. We fold subproblems together
+ * except at a FULL JOIN or where join_collapse_limit would be
+ * exceeded.
+ */
+ if (j->jointype == JOIN_FULL)
+ {
+ /* force the join order exactly at this node */
+ joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
+ }
+ else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
+ join_collapse_limit)
+ {
+ /* OK to combine subproblems */
+ joinlist = list_concat(leftjoinlist, rightjoinlist);
+ }
+ else
+ {
+ /* can't combine, but needn't force join order above here */
+ Node *leftpart,
+ *rightpart;
+
+ /* avoid creating useless 1-element sublists */
+ if (list_length(leftjoinlist) == 1)
+ leftpart = (Node *) linitial(leftjoinlist);
+ else
+ leftpart = (Node *) leftjoinlist;
+ if (list_length(rightjoinlist) == 1)
+ rightpart = (Node *) linitial(rightjoinlist);
+ else
+ rightpart = (Node *) rightjoinlist;
+ joinlist = list_make2(leftpart, rightpart);
+ }
}
else
+ {
elog(ERROR, "unrecognized node type: %d",
(int) nodeTag(jtnode));
- return result;
+ joinlist = NIL; /* keep compiler quiet */
+ }
+ return joinlist;
}
/*
- * mark_baserels_for_outer_join
- * Mark all base rels listed in 'rels' as having the given outerjoinset.
+ * make_outerjoininfo
+ * Build a SpecialJoinInfo for the current outer join
+ *
+ * Inputs:
+ * left_rels: the base Relids syntactically on outer side of join
+ * right_rels: the base Relids syntactically on inner side of join
+ * inner_join_rels: base Relids participating in inner joins below this one
+ * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
+ * clause: the outer join's join condition (in implicit-AND format)
+ *
+ * The node should eventually be appended to root->join_info_list, but we
+ * do not do that here.
+ *
+ * Note: we assume that this function is invoked bottom-up, so that
+ * root->join_info_list already contains entries for all outer joins that are
+ * syntactically below this one.
*/
-static void
-mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels)
+static SpecialJoinInfo *
+make_outerjoininfo(PlannerInfo *root,
+ Relids left_rels, Relids right_rels,
+ Relids inner_join_rels,
+ JoinType jointype, List *clause)
{
- Relids tmprelids;
- int relno;
+ SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
+ Relids clause_relids;
+ Relids strict_relids;
+ Relids min_lefthand;
+ Relids min_righthand;
+ ListCell *l;
+
+ /*
+ * We should not see RIGHT JOIN here because left/right were switched
+ * earlier
+ */
+ Assert(jointype != JOIN_INNER);
+ Assert(jointype != JOIN_RIGHT);
+
+ /*
+ * 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
+ * any nullable rel is FOR UPDATE/SHARE.
+ *
+ * You might be wondering why this test isn't made far upstream in the
+ * parser. It's because the parser hasn't got enough info --- consider
+ * FOR UPDATE applied to a view. Only after rewriting and flattening do
+ * we know whether the view contains an outer join.
+ */
+ foreach(l, root->parse->rowMarks)
+ {
+ RowMarkClause *rc = (RowMarkClause *) lfirst(l);
+
+ if (bms_is_member(rc->rti, right_rels) ||
+ (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("SELECT FOR UPDATE/SHARE cannot be applied to the nullable side of an outer join")));
+ }
+
+ sjinfo->syn_lefthand = left_rels;
+ sjinfo->syn_righthand = right_rels;
+ sjinfo->jointype = jointype;
+ /* this always starts out false */
+ sjinfo->delay_upper_joins = false;
+ sjinfo->join_quals = clause;
+
+ /* If it's a full join, no need to be very smart */
+ if (jointype == JOIN_FULL)
+ {
+ sjinfo->min_lefthand = bms_copy(left_rels);
+ sjinfo->min_righthand = bms_copy(right_rels);
+ sjinfo->lhs_strict = false; /* don't care about this */
+ return sjinfo;
+ }
+
+ /*
+ * Retrieve all relids mentioned within the join clause.
+ */
+ clause_relids = pull_varnos((Node *) clause);
+
+ /*
+ * For which relids is the clause strict, ie, it cannot succeed if the
+ * rel's columns are all NULL?
+ */
+ strict_relids = find_nonnullable_rels((Node *) clause);
+
+ /* Remember whether the clause is strict for any LHS relations */
+ sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
+
+ /*
+ * Required LHS always includes the LHS rels mentioned in the clause. We
+ * may have to add more rels based on lower outer joins; see below.
+ */
+ min_lefthand = bms_intersect(clause_relids, left_rels);
+
+ /*
+ * Similarly for required RHS. But here, we must also include any lower
+ * inner joins, to ensure we don't try to commute with any of them.
+ */
+ min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
+ right_rels);
- tmprelids = bms_copy(rels);
- while ((relno = bms_first_member(tmprelids)) >= 0)
+ foreach(l, root->join_info_list)
{
- RelOptInfo *rel = find_base_rel(root, relno);
+ SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
+
+ /* ignore full joins --- other mechanisms preserve their ordering */
+ if (otherinfo->jointype == JOIN_FULL)
+ continue;
/*
- * Since we do this bottom-up, any outer-rels previously marked
- * should be within the new outer join set.
+ * For a lower OJ in our LHS, if our join condition uses the lower
+ * join's RHS and is not strict for that rel, we must preserve the
+ * ordering of the two OJs, so add lower OJ's full syntactic relset to
+ * min_lefthand. (We must use its full syntactic relset, not just its
+ * min_lefthand + min_righthand. This is because there might be other
+ * OJs below this one that this one can commute with, but we cannot
+ * commute with them if we don't with this one.)
+ *
+ * Note: I believe we have to insist on being strict for at least one
+ * rel in the lower OJ's min_righthand, not its whole syn_righthand.
*/
- Assert(bms_is_subset(rel->outerjoinset, outerrels));
+ if (bms_overlap(left_rels, otherinfo->syn_righthand) &&
+ bms_overlap(clause_relids, otherinfo->syn_righthand) &&
+ !bms_overlap(strict_relids, otherinfo->min_righthand))
+ {
+ min_lefthand = bms_add_members(min_lefthand,
+ otherinfo->syn_lefthand);
+ min_lefthand = bms_add_members(min_lefthand,
+ otherinfo->syn_righthand);
+ }
/*
- * Presently the executor cannot support FOR UPDATE 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.
- * It's sufficient to make this check once per rel, so do it only
- * if rel wasn't already known nullable.
+ * For a lower OJ in our RHS, if our join condition does not use the
+ * lower join's RHS and the lower OJ's join condition is strict, we
+ * can interchange the ordering of the two OJs; otherwise we must add
+ * lower OJ's full syntactic relset to min_righthand.
+ *
+ * Here, we have to consider that "our join condition" includes any
+ * clauses that syntactically appeared above the lower OJ and below
+ * ours; those are equivalent to degenerate clauses in our OJ and must
+ * be treated as such. Such clauses obviously can't reference our
+ * LHS, and they must be non-strict for the lower OJ's RHS (else
+ * reduce_outer_joins would have reduced the lower OJ to a plain
+ * join). Hence the other ways in which we handle clauses within our
+ * join condition are not affected by them. The net effect is
+ * therefore sufficiently represented by the delay_upper_joins flag
+ * saved for us by check_outerjoin_delay.
*/
- if (rel->outerjoinset == NULL)
+ if (bms_overlap(right_rels, otherinfo->syn_righthand))
{
- if (intMember(relno, root->rowMarks))
- ereport(ERROR,
- (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
- errmsg("SELECT FOR UPDATE cannot be applied to the nullable side of an outer join")));
+ if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
+ !otherinfo->lhs_strict || otherinfo->delay_upper_joins)
+ {
+ min_righthand = bms_add_members(min_righthand,
+ otherinfo->syn_lefthand);
+ min_righthand = bms_add_members(min_righthand,
+ otherinfo->syn_righthand);
+ }
}
-
- rel->outerjoinset = outerrels;
}
- bms_free(tmprelids);
+
+ /*
+ * If we found nothing to put in min_lefthand, punt and make it the full
+ * LHS, to avoid having an empty min_lefthand which will confuse later
+ * processing. (We don't try to be smart about such cases, just correct.)
+ * Likewise for min_righthand.
+ */
+ if (bms_is_empty(min_lefthand))
+ min_lefthand = bms_copy(left_rels);
+ if (bms_is_empty(min_righthand))
+ min_righthand = bms_copy(right_rels);
+
+ /* Now they'd better be nonempty */
+ Assert(!bms_is_empty(min_lefthand));
+ Assert(!bms_is_empty(min_righthand));
+ /* Shouldn't overlap either */
+ Assert(!bms_overlap(min_lefthand, min_righthand));
+
+ sjinfo->min_lefthand = min_lefthand;
+ sjinfo->min_righthand = min_righthand;
+
+ return sjinfo;
}
+
+/*****************************************************************************
+ *
+ * QUALIFICATIONS
+ *
+ *****************************************************************************/
+
/*
* distribute_qual_to_rels
- * Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
+ * Add clause information to either the baserestrictinfo or joininfo list
* (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
+ * the appropriate list for each rel. Alternatively, if the clause uses a
* 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.
+ * the left- and right-side expressions into the query's list of
+ * EquivalenceClasses.
*
* 'clause': the qual clause to be distributed
- * 'ispusheddown': if TRUE, force the clause to be marked 'ispusheddown'
- * (this indicates the clause came from a FromExpr, not a JoinExpr)
- * 'isdeduced': TRUE if the qual came from implied-equality deduction
+ * 'is_deduced': TRUE if the qual came from implied-equality deduction
+ * 'below_outer_join': TRUE if the qual is from a JOIN/ON that is below the
+ * nullable side of a higher-level outer join
+ * 'qualscope': set of baserels the qual's syntactic scope covers
+ * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels
+ * needed to form this join
* '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
+ * (for FULL JOIN this includes both sides of the join, and must in fact
+ * equal qualscope)
*
- * '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.
+ * 'qualscope' identifies what level of JOIN the qual came from syntactically.
+ * 'ojscope' is needed if we decide to force the qual up to the outer-join
+ * level, which will be ojscope not necessarily qualscope.
*/
static void
-distribute_qual_to_rels(Query *root, Node *clause,
- bool ispusheddown,
- bool isdeduced,
- Relids outerjoin_nonnullable,
- Relids qualscope)
+distribute_qual_to_rels(PlannerInfo *root, Node *clause,
+ bool is_deduced,
+ bool below_outer_join,
+ Relids qualscope,
+ Relids ojscope,
+ Relids outerjoin_nonnullable)
{
- RestrictInfo *restrictinfo = makeNode(RestrictInfo);
- RelOptInfo *rel;
Relids relids;
- List *vars;
- bool can_be_equijoin;
-
- restrictinfo->clause = (Expr *) clause;
- restrictinfo->canjoin = false; /* set below, if join clause */
- restrictinfo->left_relids = NULL;
- restrictinfo->right_relids = NULL;
- restrictinfo->subclauseindices = NIL;
- restrictinfo->eval_cost.startup = -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;
+ bool is_pushed_down;
+ bool outerjoin_delayed;
+ bool pseudoconstant = false;
+ bool maybe_equivalence;
+ bool maybe_outer_join;
+ RestrictInfo *restrictinfo;
/*
- * 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);
/*
* Cross-check: clause should contain no relids not within its scope.
* Otherwise the parser messed up.
*/
if (!bms_is_subset(relids, qualscope))
- elog(ERROR, "JOIN qualification may not refer to other relations");
+ elog(ERROR, "JOIN qualification cannot refer to other relations");
+ if (ojscope && !bms_is_subset(relids, ojscope))
+ elog(ERROR, "JOIN qualification cannot refer to other relations");
/*
- * 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 the clause is variable-free, our normal heuristic for pushing it
+ * down to just the mentioned rels doesn't work, because there are none.
+ *
+ * If the clause is an outer-join clause, we must force it to the OJ's
+ * semantic level to preserve semantics.
+ *
+ * Otherwise, when the clause contains volatile functions, we force it to
+ * be evaluated at its original syntactic level. This preserves the
+ * expected semantics.
+ *
+ * When the clause contains no volatile functions either, it is actually a
+ * pseudoconstant clause that will not change value during any one
+ * execution of the plan, and hence can be used as a one-time qual in a
+ * gating Result plan node. We put such a clause into the regular
+ * RestrictInfo lists for the moment, but eventually createplan.c will
+ * pull it out and make a gating Result node immediately above whatever
+ * plan node the pseudoconstant clause is assigned to. It's usually best
+ * to put a gating node as high in the plan tree as possible. If we are
+ * not below an outer join, we can actually push the pseudoconstant qual
+ * all the way to the top of the tree. If we are below an outer join, we
+ * leave the qual at its original syntactic level (we could push it up to
+ * just below the outer join, but that seems more complex than it's
+ * worth).
*/
if (bms_is_empty(relids))
- relids = qualscope;
+ {
+ if (ojscope)
+ {
+ /* clause is attached to outer join, eval it there */
+ relids = bms_copy(ojscope);
+ /* mustn't use as gating qual, so don't mark pseudoconstant */
+ }
+ else
+ {
+ /* eval at original syntactic level */
+ relids = bms_copy(qualscope);
+ if (!contain_volatile_functions(clause))
+ {
+ /* mark as gating qual */
+ pseudoconstant = true;
+ /* tell createplan.c to check for gating quals */
+ root->hasPseudoConstantQuals = true;
+ /* if not below outer join, push it to top of tree */
+ if (!below_outer_join)
+ relids =
+ get_relids_in_jointree((Node *) root->parse->jointree,
+ false);
+ }
+ }
+ }
- /*
+ /*----------
* Check to see if clause application must be delayed by outer-join
* considerations.
+ *
+ * A word about is_pushed_down: we mark the qual as "pushed down" if
+ * it is (potentially) applicable at a level different from its original
+ * syntactic level. This flag is used to distinguish OUTER JOIN ON quals
+ * from other quals pushed down to the same joinrel. The rules are:
+ * WHERE quals and INNER JOIN quals: is_pushed_down = true.
+ * Non-degenerate OUTER JOIN quals: is_pushed_down = false.
+ * Degenerate OUTER JOIN quals: is_pushed_down = true.
+ * A "degenerate" OUTER JOIN qual is one that doesn't mention the
+ * non-nullable side, and hence can be pushed down into the nullable side
+ * without changing the join result. It is correct to treat it as a
+ * regular filter condition at the level where it is evaluated.
+ *
+ * Note: it is not immediately obvious that a simple boolean is enough
+ * for this: if for some reason we were to attach a degenerate qual to
+ * its original join level, it would need to be treated as an outer join
+ * qual there. However, this cannot happen, because all the rels the
+ * clause mentions must be in the outer join's min_righthand, therefore
+ * the join it needs must be formed before the outer join; and we always
+ * attach quals to the lowest level where they can be evaluated. But
+ * if we were ever to re-introduce a mechanism for delaying evaluation
+ * of "expensive" quals, this area would need work.
+ *----------
*/
- if (isdeduced)
+ if (is_deduced)
{
/*
- * 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).
+ * If the qual came from implied-equality deduction, it should not be
+ * outerjoin-delayed, else deducer blew it. But we can't check this
+ * because the join_info_list may now contain OJs above where the qual
+ * belongs.
*/
- Assert(bms_equal(relids, qualscope));
- can_be_equijoin = true;
+ Assert(!ojscope);
+ is_pushed_down = true;
+ outerjoin_delayed = false;
+ /* Don't feed it back for more deductions */
+ maybe_equivalence = false;
+ maybe_outer_join = false;
}
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,
+ * The qual is attached to an outer join and mentions (some of the)
+ * rels on the nonnullable side, so it's not degenerate.
+ *
+ * We can't use such a clause to deduce equivalence (the left and
+ * right sides might be unequal above the join because one of them has
+ * gone to NULL) ... but we might be able to use it for more limited
+ * deductions, if it is mergejoinable. So consider adding it to the
+ * lists of set-aside outer-join clauses.
+ */
+ is_pushed_down = false;
+ maybe_equivalence = false;
+ maybe_outer_join = true;
+
+ /* Check to see if must be delayed by lower outer join */
+ outerjoin_delayed = check_outerjoin_delay(root, &relids, false);
+
+ /*
+ * Now 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.
+ * (Do this step after calling check_outerjoin_delay, because that
+ * trashes relids.)
*/
- relids = qualscope;
- can_be_equijoin = false;
+ Assert(ojscope);
+ relids = ojscope;
+ Assert(!pseudoconstant);
}
else
{
/*
- * 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.
+ * Normal qual clause or degenerate outer-join clause. Either way, we
+ * can mark it as pushed-down.
*/
- Relids addrelids = NULL;
- Relids tmprelids;
- int relno;
+ is_pushed_down = true;
- tmprelids = bms_copy(relids);
- while ((relno = bms_first_member(tmprelids)) >= 0)
+ /* Check to see if must be delayed by lower outer join */
+ outerjoin_delayed = check_outerjoin_delay(root, &relids, true);
+
+ if (outerjoin_delayed)
{
- RelOptInfo *rel = find_base_rel(root, relno);
+ /* Should still be a subset of current scope ... */
+ Assert(bms_is_subset(relids, qualscope));
- if (rel->outerjoinset != NULL)
- addrelids = bms_add_members(addrelids, rel->outerjoinset);
- }
- bms_free(tmprelids);
+ /*
+ * Because application of the qual will be delayed by outer join,
+ * we mustn't assume its vars are equal everywhere.
+ */
+ maybe_equivalence = false;
- if (bms_is_subset(addrelids, relids))
- {
- /* Qual is not affected by any outer-join restriction */
- can_be_equijoin = true;
+ /*
+ * It's possible that this is an IS NULL clause that's redundant
+ * with a lower antijoin; if so we can just discard it. We need
+ * not test in any of the other cases, because this will only
+ * be possible for pushed-down, delayed clauses.
+ */
+ if (check_redundant_nullability_qual(root, clause))
+ return;
}
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.
+ * Qual is not delayed by any lower outer-join restriction, so we
+ * can consider feeding it to the equivalence machinery. However,
+ * if it's itself within an outer-join clause, treat it as though
+ * it appeared below that outer join (note that we can only get
+ * here when the clause references only nullable-side rels).
*/
- can_be_equijoin = false;
+ maybe_equivalence = true;
+ if (outerjoin_nonnullable != NULL)
+ below_outer_join = true;
+ }
+
+ /*
+ * Since it doesn't mention the LHS, it's certainly not useful as a
+ * set-aside OJ clause, even if it's in an OJ.
+ */
+ maybe_outer_join = false;
+ }
+
+ /*
+ * Build the RestrictInfo node itself.
+ */
+ restrictinfo = make_restrictinfo((Expr *) clause,
+ is_pushed_down,
+ outerjoin_delayed,
+ pseudoconstant,
+ relids);
+
+ /*
+ * If it's a join clause (either naturally, or because delayed by
+ * outer-join rules), add vars used in the 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: if the clause gets absorbed into an EquivalenceClass then this
+ * may be unnecessary, but for now we have to do it to cover the case
+ * where the EC becomes ec_broken and we end up reinserting the original
+ * clauses into the plan.
+ */
+ if (bms_membership(relids) == BMS_MULTIPLE)
+ {
+ List *vars = pull_var_clause(clause, false);
+
+ add_vars_to_targetlist(root, vars, relids);
+ list_free(vars);
+ }
+
+ /*
+ * We check "mergejoinability" of every clause, not only join clauses,
+ * because we want to know about equivalences between vars of the same
+ * relation, or between vars and consts.
+ */
+ check_mergejoinable(restrictinfo);
+
+ /*
+ * If it is a true equivalence clause, send it to the EquivalenceClass
+ * machinery. We do *not* attach it directly to any restriction or join
+ * lists. The EC code will propagate it to the appropriate places later.
+ *
+ * If the clause has a mergejoinable operator and is not
+ * outerjoin-delayed, yet isn't an equivalence because it is an outer-join
+ * clause, the EC code may yet be able to do something with it. We add it
+ * to appropriate lists for further consideration later. Specifically:
+ *
+ * If it is a left or right outer-join qualification that relates the two
+ * sides of the outer join (no funny business like leftvar1 = leftvar2 +
+ * rightvar), we add it to root->left_join_clauses or
+ * root->right_join_clauses according to which side the nonnullable
+ * variable appears on.
+ *
+ * If it is a full outer-join qualification, we add it to
+ * root->full_join_clauses. (Ideally we'd discard cases that aren't
+ * leftvar = rightvar, as we do for left/right joins, but this routine
+ * doesn't have the info needed to do that; and the current usage of the
+ * full_join_clauses list doesn't require that, so it's not currently
+ * worth complicating this routine's API to make it possible.)
+ *
+ * If none of the above hold, pass it off to
+ * distribute_restrictinfo_to_rels().
+ */
+ if (restrictinfo->mergeopfamilies)
+ {
+ if (maybe_equivalence)
+ {
+ if (process_equivalence(root, restrictinfo, below_outer_join))
+ return;
+ /* EC rejected it, so pass to distribute_restrictinfo_to_rels */
+ }
+ else if (maybe_outer_join && restrictinfo->can_join)
+ {
+ if (bms_is_subset(restrictinfo->left_relids,
+ outerjoin_nonnullable) &&
+ !bms_overlap(restrictinfo->right_relids,
+ outerjoin_nonnullable))
+ {
+ /* we have outervar = innervar */
+ root->left_join_clauses = lappend(root->left_join_clauses,
+ restrictinfo);
+ return;
+ }
+ if (bms_is_subset(restrictinfo->right_relids,
+ outerjoin_nonnullable) &&
+ !bms_overlap(restrictinfo->left_relids,
+ outerjoin_nonnullable))
+ {
+ /* we have innervar = outervar */
+ root->right_join_clauses = lappend(root->right_join_clauses,
+ restrictinfo);
+ return;
+ }
+ if (bms_equal(outerjoin_nonnullable, qualscope))
+ {
+ /* FULL JOIN (above tests cannot match in this case) */
+ root->full_join_clauses = lappend(root->full_join_clauses,
+ restrictinfo);
+ return;
+ }
}
- bms_free(addrelids);
}
+ /* No EC special case applies, so push it into the clause lists */
+ distribute_restrictinfo_to_rels(root, restrictinfo);
+}
+
+/*
+ * distribute_sublink_quals_to_rels
+ * Pull sublink quals out of a FlattenedSubLink node and distribute
+ * them appropriately; then add a SpecialJoinInfo node to the query's
+ * join_info_list. The FlattenedSubLink node itself is no longer
+ * needed and does not propagate into further processing.
+ */
+static void
+distribute_sublink_quals_to_rels(PlannerInfo *root,
+ FlattenedSubLink *fslink,
+ bool below_outer_join)
+{
+ List *quals = make_ands_implicit(fslink->quals);
+ SpecialJoinInfo *sjinfo;
+ Relids qualscope;
+ Relids ojscope;
+ ListCell *l;
+
/*
- * 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".
+ * Build a suitable SpecialJoinInfo for the sublink. Note: using
+ * righthand as inner_join_rels is the conservative worst case;
+ * it might be possible to use a smaller set and thereby allow
+ * the sublink join to commute with others inside its RHS.
*/
- restrictinfo->ispusheddown = ispusheddown || !bms_equal(relids,
- qualscope);
+ sjinfo = make_outerjoininfo(root,
+ fslink->lefthand, fslink->righthand,
+ fslink->righthand,
+ fslink->jointype,
+ quals);
+
+ qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
+ ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+
+ /* Distribute the join quals much as for a regular LEFT JOIN */
+ foreach(l, quals)
+ {
+ Node *qual = (Node *) lfirst(l);
+
+ distribute_qual_to_rels(root, qual,
+ false, below_outer_join,
+ qualscope, ojscope,
+ fslink->lefthand);
+ }
+
+ /* Now we can add the SpecialJoinInfo to join_info_list */
+ root->join_info_list = lappend(root->join_info_list, sjinfo);
+}
+
+/*
+ * check_outerjoin_delay
+ * Detect whether a qual referencing the given relids must be delayed
+ * in application due to the presence of a lower outer join, and/or
+ * may force extra delay of higher-level outer joins.
+ *
+ * If the qual must be delayed, add relids to *relids_p to reflect the lowest
+ * safe level for evaluating the qual, and return TRUE. Any extra delay for
+ * higher-level joins is reflected by setting delay_upper_joins to TRUE in
+ * SpecialJoinInfo structs.
+ *
+ * For an is_pushed_down 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. We must enforce (2) because pushing down such a clause below
+ * the OJ might cause the OJ to emit null-extended rows that should not have
+ * been formed, or that should have been rejected by the clause. (This is
+ * only an issue for non-strict quals, since if we can prove a qual mentioning
+ * only nullable rels is strict, we'd have reduced the outer join to an inner
+ * join in reduce_outer_joins().)
+ *
+ * To enforce (2), scan the join_info_list and merge the required-relid sets of
+ * any such OJs into the clause's own reference list. At the time we are
+ * called, the join_info_list contains only outer joins below this qual. We
+ * have to repeat the scan until no new relids get added; this ensures that
+ * the qual is suitably delayed regardless of the order in which OJs get
+ * executed. As an example, if we have one OJ with LHS=A, RHS=B, and one with
+ * LHS=B, RHS=C, it is implied that these can be done in either order; if the
+ * B/C join is done first then the join to A can null C, so a qual actually
+ * mentioning only C cannot be applied below the join to A.
+ *
+ * For a non-pushed-down qual, this isn't going to determine where we place the
+ * qual, but we need to determine outerjoin_delayed anyway for possible use
+ * in reconsider_outer_join_clauses().
+ *
+ * Lastly, a pushed-down qual that references the nullable side of any current
+ * join_info_list member and has to be evaluated above that OJ (because its
+ * required relids overlap the LHS too) causes that OJ's delay_upper_joins
+ * flag to be set TRUE. This will prevent any higher-level OJs from
+ * being interchanged with that OJ, which would result in not having any
+ * correct place to evaluate the qual. (The case we care about here is a
+ * sub-select WHERE clause within the RHS of some outer join. The WHERE
+ * clause must effectively be treated as a degenerate clause of that outer
+ * join's condition. Rather than trying to match such clauses with joins
+ * directly, we set delay_upper_joins here, and when the upper outer join
+ * is processed by make_outerjoininfo, it will refrain from allowing the
+ * two OJs to commute.)
+ */
+static bool
+check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
+ bool is_pushed_down)
+{
+ Relids relids = *relids_p;
+ bool outerjoin_delayed;
+ bool found_some;
+
+ outerjoin_delayed = false;
+ do
+ {
+ ListCell *l;
+
+ found_some = false;
+ foreach(l, root->join_info_list)
+ {
+ SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
+
+ /* do we reference any nullable rels of this OJ? */
+ if (bms_overlap(relids, sjinfo->min_righthand) ||
+ (sjinfo->jointype == JOIN_FULL &&
+ bms_overlap(relids, sjinfo->min_lefthand)))
+ {
+ /* yes, so set the result flag */
+ outerjoin_delayed = true;
+ /* have we included all its rels in relids? */
+ if (!bms_is_subset(sjinfo->min_lefthand, relids) ||
+ !bms_is_subset(sjinfo->min_righthand, relids))
+ {
+ /* no, so add them in */
+ relids = bms_add_members(relids, sjinfo->min_lefthand);
+ relids = bms_add_members(relids, sjinfo->min_righthand);
+ /* we'll need another iteration */
+ found_some = true;
+ }
+ /* set delay_upper_joins if needed */
+ if (is_pushed_down && sjinfo->jointype != JOIN_FULL &&
+ bms_overlap(relids, sjinfo->min_lefthand))
+ sjinfo->delay_upper_joins = true;
+ }
+ }
+ } while (found_some);
+
+ *relids_p = relids;
+ return outerjoin_delayed;
+}
+
+/*
+ * check_redundant_nullability_qual
+ * Check to see if the qual is an IS NULL qual that is redundant with
+ * a lower JOIN_ANTI join.
+ *
+ * We want to suppress redundant IS NULL quals, not so much to save cycles
+ * as to avoid generating bogus selectivity estimates for them. So if
+ * redundancy is detected here, distribute_qual_to_rels() just throws away
+ * the qual.
+ */
+static bool
+check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
+{
+ Var *forced_null_var;
+ Index forced_null_rel;
+ SpecialJoinInfo *match_sjinfo = NULL;
+ ListCell *lc;
+
+ /* Check for IS NULL, and identify the Var forced to NULL */
+ forced_null_var = find_forced_null_var(clause);
+ if (forced_null_var == NULL)
+ return false;
+ forced_null_rel = forced_null_var->varno;
/*
- * If it's a binary opclause, set up left/right relids info.
+ * Search to see if there's a matching antijoin that is not masked by
+ * a higher outer join. Because we have to scan the join info bottom-up,
+ * we have to continue looking after finding a match to check for masking
+ * joins. This logic should agree with reduce_outer_joins's code
+ * to detect antijoins on the basis of IS NULL clauses. (It's tempting
+ * to consider adding some data structures to avoid redundant work,
+ * but in practice this code shouldn't get executed often enough to
+ * make it worth the trouble.)
*/
- if (is_opclause(clause) && length(((OpExpr *) clause)->args) == 2)
+ foreach(lc, root->join_info_list)
{
- restrictinfo->left_relids = pull_varnos(get_leftop((Expr *) clause));
- restrictinfo->right_relids = pull_varnos(get_rightop((Expr *) clause));
+ SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+
+ /* Check for match ... */
+ if (sjinfo->jointype == JOIN_ANTI &&
+ bms_is_member(forced_null_rel, sjinfo->syn_righthand))
+ {
+ List *nonnullable_vars;
+
+ nonnullable_vars = find_nonnullable_vars((Node *) sjinfo->join_quals);
+ if (list_member(nonnullable_vars, forced_null_var))
+ {
+ match_sjinfo = sjinfo;
+ continue;
+ }
+ }
+ /*
+ * Else, if we had a lower match, check to see if the target var is
+ * from the nullable side of this OJ. If so, this OJ masks the
+ * lower one and we can no longer consider the IS NULL as redundant
+ * with the lower antijoin.
+ */
+ if (!match_sjinfo)
+ continue;
+ if (bms_is_member(forced_null_rel, sjinfo->syn_righthand) ||
+ (sjinfo->jointype == JOIN_FULL &&
+ bms_is_member(forced_null_rel, sjinfo->syn_lefthand)))
+ match_sjinfo = NULL;
}
+ return (match_sjinfo != NULL);
+}
+
+/*
+ * distribute_restrictinfo_to_rels
+ * Push a completed RestrictInfo into the proper restriction or join
+ * clause list(s).
+ *
+ * This is the last step of distribute_qual_to_rels() for ordinary qual
+ * clauses. Clauses that are interesting for equivalence-class processing
+ * are diverted to the EC machinery, but may ultimately get fed back here.
+ */
+void
+distribute_restrictinfo_to_rels(PlannerInfo *root,
+ RestrictInfo *restrictinfo)
+{
+ Relids relids = restrictinfo->required_relids;
+ RelOptInfo *rel;
+
switch (bms_membership(relids))
{
case BMS_SINGLETON:
/*
- * There is only one relation participating in 'clause', so
- * 'clause' is a restriction clause for that relation.
+ * There is only one relation participating in the clause, so it
+ * 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);
- }
+ /* 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. Set additional RestrictInfo fields for
- * joining. First, does it look like a normal join clause,
- * i.e., a binary operator relating expressions that come from
- * distinct relations? If so we might be able to use it in a
- * join algorithm.
+ * The clause is a join clause, since there is more than one rel
+ * in its relid set.
*/
- if (is_opclause(clause) && length(((OpExpr *) clause)->args) == 2)
- {
- if (!bms_is_empty(restrictinfo->left_relids) &&
- !bms_is_empty(restrictinfo->right_relids) &&
- !bms_overlap(restrictinfo->left_relids,
- restrictinfo->right_relids))
- restrictinfo->canjoin = true;
- }
/*
- * Now 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 for hashjoinable operators. (We don't bother setting the
+ * hashjoin info if we're not going to need it.)
*/
- 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!).
- */
- add_vars_to_targetlist(root, vars, relids);
break;
default:
/*
- * 'clause' references no rels, and therefore we have no place
- * to attach it. Shouldn't get here if callers are working
- * properly.
+ * 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; 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.
+ * Create a restrictinfo item that says "item1 op item2", and push it
+ * into the appropriate lists. (In practice opno is always a btree
+ * equality operator.)
+ *
+ * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
+ * This must contain at least all the rels used in the expressions, but it
+ * is used only to set the qual application level when both exprs are
+ * variable-free. Otherwise the qual is applied at the lowest join level
+ * that provides all its variables.
+ *
+ * "both_const" indicates whether both items are known pseudo-constant;
+ * in this case it is worth applying eval_const_expressions() in case we
+ * can produce constant TRUE or constant FALSE. (Otherwise it's not,
+ * because the expressions went through eval_const_expressions already.)
+ *
+ * This is currently used only when an EquivalenceClass is found to
+ * contain pseudoconstants. See path/pathkeys.c for more details.
*/
void
-process_implied_equality(Query *root,
- Node *item1, Node *item2,
- Oid sortop1, Oid sortop2,
- Relids item1_relids, Relids item2_relids,
- bool delete_it)
+process_implied_equality(PlannerInfo *root,
+ Oid opno,
+ Expr *item1,
+ Expr *item2,
+ Relids qualscope,
+ bool below_outer_join,
+ bool both_const)
{
- Relids relids;
- BMS_Membership membership;
- RelOptInfo *rel1;
- List *restrictlist;
- List *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);
-
/*
- * generate_implied_equalities() shouldn't call me on two constants.
+ * Build the new clause. Copy to ensure it shares no substructure with
+ * original (this is necessary in case there are subselects in there...)
*/
- Assert(membership != BMS_EMPTY_SET);
+ clause = make_opclause(opno,
+ BOOLOID, /* opresulttype */
+ false, /* opretset */
+ (Expr *) copyObject(item1),
+ (Expr *) copyObject(item2));
- /*
- * 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.
- */
- if (membership == BMS_SINGLETON)
- {
- rel1 = find_base_rel(root, bms_singleton_member(relids));
- restrictlist = rel1->baserestrictinfo;
- }
- else
+ /* If both constant, try to reduce to a boolean constant. */
+ if (both_const)
{
- 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);
-
- /* use remaining members to find join node */
- joininfo = find_joininfo_node(rel1, other_rels);
+ clause = (Expr *) eval_const_expressions(root, (Node *) clause);
- restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL;
-
- bms_free(other_rels);
- }
-
- /*
- * 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)
- {
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
- Node *left,
- *right;
-
- if (restrictinfo->mergejoinoperator == InvalidOid)
- continue; /* ignore non-mergejoinable clauses */
- /* We now know the restrictinfo clause is a binary opclause */
- left = get_leftop(restrictinfo->clause);
- right = get_rightop(restrictinfo->clause);
- if ((equal(item1, left) && equal(item2, right)) ||
- (equal(item2, left) && equal(item1, right)))
+ /* If we produced const TRUE, just drop the clause */
+ if (clause && IsA(clause, Const))
{
- /* found a matching clause */
- if (delete_it)
- {
- if (membership == BMS_SINGLETON)
- {
- /* delete it from local restrictinfo list */
- rel1->baserestrictinfo = lremove(restrictinfo,
- rel1->baserestrictinfo);
- }
- 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;
+ Const *cclause = (Const *) clause;
- /*
- * 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("=")),
- ltype, rtype, true);
- if (!HeapTupleIsValid(eq_operator))
- {
- /*
- * Would it be safe to just not add the equality to the query if
- * we have no suitable equality operator for the combination of
- * datatypes? NO, because sortkey selection may screw up anyway.
- */
- 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))));
+ Assert(cclause->consttype == BOOLOID);
+ if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
+ return;
+ }
}
- 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)
- 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))));
-
- clause = make_opclause(oprid(eq_operator), /* opno */
- BOOLOID, /* opresulttype */
- false, /* opretset */
- (Expr *) item1,
- (Expr *) item2);
- ReleaseSysCache(eq_operator);
+ /* Make a copy of qualscope to avoid problems if source EC changes */
+ qualscope = bms_copy(qualscope);
/*
* 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);
+ true, below_outer_join,
+ qualscope, NULL, NULL);
}
/*
- * 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.
+ * build_implied_join_equality --- build a RestrictInfo for a derived equality
+ *
+ * This overlaps the functionality of process_implied_equality(), but we
+ * must return the RestrictInfo, not push it into the joininfo tree.
*/
-static bool
-qual_is_redundant(Query *root,
- RestrictInfo *restrictinfo,
- List *restrictlist)
+RestrictInfo *
+build_implied_join_equality(Oid opno,
+ Expr *item1,
+ Expr *item2,
+ Relids qualscope)
{
- Node *newleft;
- Node *newright;
- List *oldquals;
- List *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);
+ RestrictInfo *restrictinfo;
+ Expr *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.
+ * Build the new clause. Copy to ensure it shares no substructure with
+ * original (this is necessary in case there are subselects in there...)
*/
- cache_mergeclause_pathkeys(root, restrictinfo);
- /* If different, say "not redundant" (should never happen) */
- if (restrictinfo->left_pathkey != restrictinfo->right_pathkey)
- return false;
+ clause = make_opclause(opno,
+ BOOLOID, /* opresulttype */
+ false, /* opretset */
+ (Expr *) copyObject(item1),
+ (Expr *) copyObject(item2));
- /*
- * 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;
+ /* Make a copy of qualscope to avoid problems if source EC changes */
+ qualscope = bms_copy(qualscope);
/*
- * 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.
+ * Build the RestrictInfo node itself.
*/
- equalexprs = makeList1(newleft);
- do
- {
- someadded = false;
- /* cannot use foreach here because of possible lremove */
- olditem = 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 lremove possibly pfree's it */
- olditem = lnext(olditem);
-
- if (member(oldleft, equalexprs))
- newguy = oldright;
- else if (member(oldright, equalexprs))
- 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 = lremove(oldrinfo, oldquals);
- }
- } while (someadded);
-
- return false; /* it's not redundant */
+ restrictinfo = make_restrictinfo(clause,
+ true, /* is_pushed_down */
+ false, /* outerjoin_delayed */
+ false, /* pseudoconstant */
+ qualscope);
+
+ /* Set mergejoinability info always, and hashjoinability if enabled */
+ check_mergejoinable(restrictinfo);
+ if (enable_hashjoin)
+ check_hashjoinable(restrictinfo);
+
+ return restrictinfo;
}
check_mergejoinable(RestrictInfo *restrictinfo)
{
Expr *clause = restrictinfo->clause;
- Oid opno,
- leftOp,
- rightOp;
+ Oid opno;
+ if (restrictinfo->pseudoconstant)
+ return;
if (!is_opclause(clause))
return;
- if (length(((OpExpr *) clause)->args) != 2)
+ if (list_length(((OpExpr *) clause)->args) != 2)
return;
opno = ((OpExpr *) clause)->opno;
- if (op_mergejoinable(opno,
- &leftOp,
- &rightOp) &&
+ if (op_mergejoinable(opno) &&
!contain_volatile_functions((Node *) clause))
- {
- restrictinfo->mergejoinoperator = opno;
- restrictinfo->left_sortop = leftOp;
- restrictinfo->right_sortop = rightOp;
- }
+ restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
+
+ /*
+ * Note: op_mergejoinable is just a hint; if we fail to find the operator
+ * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
+ * is not treated as mergejoinable.
+ */
}
/*
Expr *clause = restrictinfo->clause;
Oid opno;
+ if (restrictinfo->pseudoconstant)
+ return;
if (!is_opclause(clause))
return;
- if (length(((OpExpr *) clause)->args) != 2)
+ if (list_length(((OpExpr *) clause)->args) != 2)
return;
opno = ((OpExpr *) clause)->opno;
projects / postgresql / blobdiff