analyzejoins.c File Reference

#include "postgres.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/joininfo.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/restrictinfo.h"
#include "optimizer/tlist.h"
#include "utils/lsyscache.h"

Include dependency graph for analyzejoins.c:

Go to the source code of this file.

Functions
static bool	join_is_removable (PlannerInfo *root, SpecialJoinInfo *sjinfo)
static void	remove_rel_from_query (PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
static void	remove_rel_from_restrictinfo (RestrictInfo *rinfo, int relid, int ojrelid)
static void	remove_rel_from_eclass (EquivalenceClass *ec, int relid, int ojrelid)
static List *	remove_rel_from_joinlist (List *joinlist, int relid, int *nremoved)
static bool	rel_supports_distinctness (PlannerInfo *root, RelOptInfo *rel)
static bool	rel_is_distinct_for (PlannerInfo *root, RelOptInfo *rel, List *clause_list)
static Oid	distinct_col_search (int colno, List *colnos, List *opids)
static bool	is_innerrel_unique_for (PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist)
List *	remove_useless_joins (PlannerInfo *root, List *joinlist)
static bool	clause_sides_match_join (RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
void	reduce_unique_semijoins (PlannerInfo *root)
bool	query_supports_distinctness (Query *query)
bool	query_is_distinct_for (Query *query, List *colnos, List *opids)
bool	innerrel_is_unique (PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)

Function Documentation

clause_sides_match_join()

static bool clause_sides_match_join ( RestrictInfo *  rinfo, Relids  outerrelids, Relids  innerrelids  )

inlinestatic

Definition at line 130 of file analyzejoins.c.

{
    if (bms_is_subset(rinfo->left_relids, outerrelids) &&
        bms_is_subset(rinfo->right_relids, innerrelids))
    {
        /* lefthand side is outer */
        rinfo->outer_is_left = true;
        return true;
    }
    else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
             bms_is_subset(rinfo->right_relids, outerrelids))
    {
        /* righthand side is outer */
        rinfo->outer_is_left = false;
        return true;
    }
    return false;               /* no good for these input relations */
}

References bms_is_subset().

Referenced by is_innerrel_unique_for(), and join_is_removable().

distinct_col_search()

static Oid distinct_col_search ( int  colno, List *  colnos, List *  opids  )

static

Definition at line 1132 of file analyzejoins.c.

{
    ListCell   *lc1,
               *lc2;
 
    forboth(lc1, colnos, lc2, opids)
    {
        if (colno == lfirst_int(lc1))
            return lfirst_oid(lc2);
    }
    return InvalidOid;
}

References forboth, InvalidOid, lfirst_int, and lfirst_oid.

Referenced by query_is_distinct_for().

innerrel_is_unique()

bool innerrel_is_unique	(	PlannerInfo *	root,
		Relids	joinrelids,
		Relids	outerrelids,
		RelOptInfo *	innerrel,
		JoinType	jointype,
		List *	restrictlist,
		bool	force_cache
	)

Definition at line 1172 of file analyzejoins.c.

{
    MemoryContext old_context;
    ListCell   *lc;
 
    /* Certainly can't prove uniqueness when there are no joinclauses */
    if (restrictlist == NIL)
        return false;
 
    /*
     * Make a quick check to eliminate cases in which we will surely be unable
     * to prove uniqueness of the innerrel.
     */
    if (!rel_supports_distinctness(root, innerrel))
        return false;
 
    /*
     * Query the cache to see if we've managed to prove that innerrel is
     * unique for any subset of this outerrel.  We don't need an exact match,
     * as extra outerrels can't make the innerrel any less unique (or more
     * formally, the restrictlist for a join to a superset outerrel must be a
     * superset of the conditions we successfully used before).
     */
    foreach(lc, innerrel->unique_for_rels)
    {
        Relids      unique_for_rels = (Relids) lfirst(lc);
 
        if (bms_is_subset(unique_for_rels, outerrelids))
            return true;        /* Success! */
    }
 
    /*
     * Conversely, we may have already determined that this outerrel, or some
     * superset thereof, cannot prove this innerrel to be unique.
     */
    foreach(lc, innerrel->non_unique_for_rels)
    {
        Relids      unique_for_rels = (Relids) lfirst(lc);
 
        if (bms_is_subset(outerrelids, unique_for_rels))
            return false;
    }
 
    /* No cached information, so try to make the proof. */
    if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
                               jointype, restrictlist))
    {
        /*
         * Cache the positive result for future probes, being sure to keep it
         * in the planner_cxt even if we are working in GEQO.
         *
         * Note: one might consider trying to isolate the minimal subset of
         * the outerrels that proved the innerrel unique.  But it's not worth
         * the trouble, because the planner builds up joinrels incrementally
         * and so we'll see the minimally sufficient outerrels before any
         * supersets of them anyway.
         */
        old_context = MemoryContextSwitchTo(root->planner_cxt);
        innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
                                            bms_copy(outerrelids));
        MemoryContextSwitchTo(old_context);
 
        return true;            /* Success! */
    }
    else
    {
        /*
         * None of the join conditions for outerrel proved innerrel unique, so
         * we can safely reject this outerrel or any subset of it in future
         * checks.
         *
         * However, in normal planning mode, caching this knowledge is totally
         * pointless; it won't be queried again, because we build up joinrels
         * from smaller to larger.  It is useful in GEQO mode, where the
         * knowledge can be carried across successive planning attempts; and
         * it's likely to be useful when using join-search plugins, too. Hence
         * cache when join_search_private is non-NULL.  (Yeah, that's a hack,
         * but it seems reasonable.)
         *
         * Also, allow callers to override that heuristic and force caching;
         * that's useful for reduce_unique_semijoins, which calls here before
         * the normal join search starts.
         */
        if (force_cache || root->join_search_private)
        {
            old_context = MemoryContextSwitchTo(root->planner_cxt);
            innerrel->non_unique_for_rels =
                lappend(innerrel->non_unique_for_rels,
                        bms_copy(outerrelids));
            MemoryContextSwitchTo(old_context);
        }
 
        return false;
    }
}

References bms_copy(), bms_is_subset(), is_innerrel_unique_for(), lappend(), lfirst, MemoryContextSwitchTo(), NIL, RelOptInfo::non_unique_for_rels, rel_supports_distinctness(), and RelOptInfo::unique_for_rels.

Referenced by add_paths_to_joinrel(), and reduce_unique_semijoins().

is_innerrel_unique_for()

static bool is_innerrel_unique_for ( PlannerInfo *  root, Relids  joinrelids, Relids  outerrelids, RelOptInfo *  innerrel, JoinType  jointype, List *  restrictlist  )

static

Definition at line 1280 of file analyzejoins.c.

{
    List       *clause_list = NIL;
    ListCell   *lc;
 
    /*
     * Search for mergejoinable clauses that constrain the inner rel against
     * the outer rel.  If an operator is mergejoinable then it behaves like
     * equality for some btree opclass, so it's what we want.  The
     * mergejoinability test also eliminates clauses containing volatile
     * functions, which we couldn't depend on.
     */
    foreach(lc, restrictlist)
    {
        RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
 
        /*
         * As noted above, if it's a pushed-down clause and we're at an outer
         * join, we can't use it.
         */
        if (IS_OUTER_JOIN(jointype) &&
            RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
            continue;
 
        /* Ignore if it's not a mergejoinable clause */
        if (!restrictinfo->can_join ||
            restrictinfo->mergeopfamilies == NIL)
            continue;           /* not mergejoinable */
 
        /*
         * Check if clause has the form "outer op inner" or "inner op outer",
         * and if so mark which side is inner.
         */
        if (!clause_sides_match_join(restrictinfo, outerrelids,
                                     innerrel->relids))
            continue;           /* no good for these input relations */
 
        /* OK, add to list */
        clause_list = lappend(clause_list, restrictinfo);
    }
 
    /* Let rel_is_distinct_for() do the hard work */
    return rel_is_distinct_for(root, innerrel, clause_list);
}

References clause_sides_match_join(), IS_OUTER_JOIN, lappend(), lfirst, NIL, rel_is_distinct_for(), RelOptInfo::relids, and RINFO_IS_PUSHED_DOWN.

Referenced by innerrel_is_unique().

join_is_removable()

static bool join_is_removable ( PlannerInfo *  root, SpecialJoinInfo *  sjinfo  )

static

Definition at line 162 of file analyzejoins.c.

{
    int         innerrelid;
    RelOptInfo *innerrel;
    Relids      inputrelids;
    Relids      joinrelids;
    List       *clause_list = NIL;
    ListCell   *l;
    int         attroff;
 
    /*
     * Must be a left join to a single baserel, else we aren't going to be
     * able to do anything with it.
     */
    if (sjinfo->jointype != JOIN_LEFT)
        return false;
 
    if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
        return false;
 
    /*
     * Never try to eliminate a left join to the query result rel.  Although
     * the case is syntactically impossible in standard SQL, MERGE will build
     * a join tree that looks exactly like that.
     */
    if (innerrelid == root->parse->resultRelation)
        return false;
 
    innerrel = find_base_rel(root, innerrelid);
 
    /*
     * Before we go to the effort of checking whether any innerrel variables
     * are needed above the join, make a quick check to eliminate cases in
     * which we will surely be unable to prove uniqueness of the innerrel.
     */
    if (!rel_supports_distinctness(root, innerrel))
        return false;
 
    /* Compute the relid set for the join we are considering */
    inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
    Assert(sjinfo->ojrelid != 0);
    joinrelids = bms_copy(inputrelids);
    joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
 
    /*
     * We can't remove the join if any inner-rel attributes are used above the
     * join.  Here, "above" the join includes pushed-down conditions, so we
     * should reject if attr_needed includes the OJ's own relid; therefore,
     * compare to inputrelids not joinrelids.
     *
     * As a micro-optimization, it seems better to start with max_attr and
     * count down rather than starting with min_attr and counting up, on the
     * theory that the system attributes are somewhat less likely to be wanted
     * and should be tested last.
     */
    for (attroff = innerrel->max_attr - innerrel->min_attr;
         attroff >= 0;
         attroff--)
    {
        if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
            return false;
    }
 
    /*
     * Similarly check that the inner rel isn't needed by any PlaceHolderVars
     * that will be used above the join.  The PHV case is a little bit more
     * complicated, because PHVs may have been assigned a ph_eval_at location
     * that includes the innerrel, yet their contained expression might not
     * actually reference the innerrel (it could be just a constant, for
     * instance).  If such a PHV is due to be evaluated above the join then it
     * needn't prevent join removal.
     */
    foreach(l, root->placeholder_list)
    {
        PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
 
        if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
            return false;       /* it references innerrel laterally */
        if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
            continue;           /* it definitely doesn't reference innerrel */
        if (bms_is_subset(phinfo->ph_needed, inputrelids))
            continue;           /* PHV is not used above the join */
        if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
            return false;       /* it has to be evaluated below the join */
 
        /*
         * We need to be sure there will still be a place to evaluate the PHV
         * if we remove the join, ie that ph_eval_at wouldn't become empty.
         */
        if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
            return false;       /* there isn't any other place to eval PHV */
        /* Check contained expression last, since this is a bit expensive */
        if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
                        innerrel->relids))
            return false;       /* contained expression references innerrel */
    }
 
    /*
     * Search for mergejoinable clauses that constrain the inner rel against
     * either the outer rel or a pseudoconstant.  If an operator is
     * mergejoinable then it behaves like equality for some btree opclass, so
     * it's what we want.  The mergejoinability test also eliminates clauses
     * containing volatile functions, which we couldn't depend on.
     */
    foreach(l, innerrel->joininfo)
    {
        RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
 
        /*
         * If the current join commutes with some other outer join(s) via
         * outer join identity 3, there will be multiple clones of its join
         * clauses in the joininfo list.  We want to consider only the
         * has_clone form of such clauses.  Processing more than one form
         * would be wasteful, and also some of the others would confuse the
         * RINFO_IS_PUSHED_DOWN test below.
         */
        if (restrictinfo->is_clone)
            continue;           /* ignore it */
 
        /*
         * If it's not a join clause for this outer join, we can't use it.
         * Note that if the clause is pushed-down, then it is logically from
         * above the outer join, even if it references no other rels (it might
         * be from WHERE, for example).
         */
        if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
            continue;           /* ignore; not useful here */
 
        /* Ignore if it's not a mergejoinable clause */
        if (!restrictinfo->can_join ||
            restrictinfo->mergeopfamilies == NIL)
            continue;           /* not mergejoinable */
 
        /*
         * Check if clause has the form "outer op inner" or "inner op outer",
         * and if so mark which side is inner.
         */
        if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
                                     innerrel->relids))
            continue;           /* no good for these input relations */
 
        /* OK, add to list */
        clause_list = lappend(clause_list, restrictinfo);
    }
 
    /*
     * Now that we have the relevant equality join clauses, try to prove the
     * innerrel distinct.
     */
    if (rel_is_distinct_for(root, innerrel, clause_list))
        return true;
 
    /*
     * Some day it would be nice to check for other methods of establishing
     * distinctness.
     */
    return false;
}

References Assert(), bms_add_member(), bms_copy(), bms_get_singleton_member(), bms_is_member(), bms_is_subset(), bms_overlap(), bms_union(), clause_sides_match_join(), find_base_rel(), RestrictInfo::is_clone, JOIN_LEFT, RelOptInfo::joininfo, SpecialJoinInfo::jointype, lappend(), lfirst, RelOptInfo::max_attr, RelOptInfo::min_attr, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, PlannerInfo::parse, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_lateral, PlaceHolderInfo::ph_needed, PlaceHolderInfo::ph_var, PlannerInfo::placeholder_list, pull_varnos(), rel_is_distinct_for(), rel_supports_distinctness(), RelOptInfo::relids, and RINFO_IS_PUSHED_DOWN.

Referenced by remove_useless_joins().

query_is_distinct_for()

bool query_is_distinct_for	(	Query *	query,
		List *	colnos,
		List *	opids
	)

Definition at line 983 of file analyzejoins.c.

{
    ListCell   *l;
    Oid         opid;
 
    Assert(list_length(colnos) == list_length(opids));
 
    /*
     * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
     * columns in the DISTINCT clause appear in colnos and operator semantics
     * match.  This is true even if there are SRFs in the DISTINCT columns or
     * elsewhere in the tlist.
     */
    if (query->distinctClause)
    {
        foreach(l, query->distinctClause)
        {
            SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
            TargetEntry *tle = get_sortgroupclause_tle(sgc,
                                                       query->targetList);
 
            opid = distinct_col_search(tle->resno, colnos, opids);
            if (!OidIsValid(opid) ||
                !equality_ops_are_compatible(opid, sgc->eqop))
                break;          /* exit early if no match */
        }
        if (l == NULL)          /* had matches for all? */
            return true;
    }
 
    /*
     * Otherwise, a set-returning function in the query's targetlist can
     * result in returning duplicate rows, despite any grouping that might
     * occur before tlist evaluation.  (If all tlist SRFs are within GROUP BY
     * columns, it would be safe because they'd be expanded before grouping.
     * But it doesn't currently seem worth the effort to check for that.)
     */
    if (query->hasTargetSRFs)
        return false;
 
    /*
     * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
     * the grouped columns appear in colnos and operator semantics match.
     */
    if (query->groupClause && !query->groupingSets)
    {
        foreach(l, query->groupClause)
        {
            SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
            TargetEntry *tle = get_sortgroupclause_tle(sgc,
                                                       query->targetList);
 
            opid = distinct_col_search(tle->resno, colnos, opids);
            if (!OidIsValid(opid) ||
                !equality_ops_are_compatible(opid, sgc->eqop))
                break;          /* exit early if no match */
        }
        if (l == NULL)          /* had matches for all? */
            return true;
    }
    else if (query->groupingSets)
    {
        /*
         * If we have grouping sets with expressions, we probably don't have
         * uniqueness and analysis would be hard. Punt.
         */
        if (query->groupClause)
            return false;
 
        /*
         * If we have no groupClause (therefore no grouping expressions), we
         * might have one or many empty grouping sets. If there's just one,
         * then we're returning only one row and are certainly unique. But
         * otherwise, we know we're certainly not unique.
         */
        if (list_length(query->groupingSets) == 1 &&
            ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
            return true;
        else
            return false;
    }
    else
    {
        /*
         * If we have no GROUP BY, but do have aggregates or HAVING, then the
         * result is at most one row so it's surely unique, for any operators.
         */
        if (query->hasAggs || query->havingQual)
            return true;
    }
 
    /*
     * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
     * except with ALL.
     */
    if (query->setOperations)
    {
        SetOperationStmt *topop = castNode(SetOperationStmt, query->setOperations);
 
        Assert(topop->op != SETOP_NONE);
 
        if (!topop->all)
        {
            ListCell   *lg;
 
            /* We're good if all the nonjunk output columns are in colnos */
            lg = list_head(topop->groupClauses);
            foreach(l, query->targetList)
            {
                TargetEntry *tle = (TargetEntry *) lfirst(l);
                SortGroupClause *sgc;
 
                if (tle->resjunk)
                    continue;   /* ignore resjunk columns */
 
                /* non-resjunk columns should have grouping clauses */
                Assert(lg != NULL);
                sgc = (SortGroupClause *) lfirst(lg);
                lg = lnext(topop->groupClauses, lg);
 
                opid = distinct_col_search(tle->resno, colnos, opids);
                if (!OidIsValid(opid) ||
                    !equality_ops_are_compatible(opid, sgc->eqop))
                    break;      /* exit early if no match */
            }
            if (l == NULL)      /* had matches for all? */
                return true;
        }
    }
 
    /*
     * XXX Are there any other cases in which we can easily see the result
     * must be distinct?
     *
     * If you do add more smarts to this function, be sure to update
     * query_supports_distinctness() to match.
     */
 
    return false;
}

References SetOperationStmt::all, Assert(), castNode, distinct_col_search(), Query::distinctClause, SortGroupClause::eqop, equality_ops_are_compatible(), get_sortgroupclause_tle(), Query::groupClause, GROUPING_SET_EMPTY, Query::groupingSets, Query::havingQual, lfirst, linitial, list_head(), list_length(), lnext(), OidIsValid, SetOperationStmt::op, TargetEntry::resno, SETOP_NONE, Query::setOperations, and Query::targetList.

Referenced by create_unique_path(), and rel_is_distinct_for().

query_supports_distinctness()

bool query_supports_distinctness

(

Query *

query

)

Definition at line 946 of file analyzejoins.c.

{
    /* SRFs break distinctness except with DISTINCT, see below */
    if (query->hasTargetSRFs && query->distinctClause == NIL)
        return false;
 
    /* check for features we can prove distinctness with */
    if (query->distinctClause != NIL ||
        query->groupClause != NIL ||
        query->groupingSets != NIL ||
        query->hasAggs ||
        query->havingQual ||
        query->setOperations)
        return true;
 
    return false;
}

References Query::distinctClause, Query::groupClause, Query::groupingSets, Query::havingQual, NIL, and Query::setOperations.

Referenced by create_unique_path(), and rel_supports_distinctness().

reduce_unique_semijoins()

void reduce_unique_semijoins

(

PlannerInfo *

root

)

Definition at line 718 of file analyzejoins.c.

{
    ListCell   *lc;
 
    /*
     * Scan the join_info_list to find semijoins.
     */
    foreach(lc, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
        int         innerrelid;
        RelOptInfo *innerrel;
        Relids      joinrelids;
        List       *restrictlist;
 
        /*
         * Must be a semijoin to a single baserel, else we aren't going to be
         * able to do anything with it.
         */
        if (sjinfo->jointype != JOIN_SEMI)
            continue;
 
        if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
            continue;
 
        innerrel = find_base_rel(root, innerrelid);
 
        /*
         * Before we trouble to run generate_join_implied_equalities, make a
         * quick check to eliminate cases in which we will surely be unable to
         * prove uniqueness of the innerrel.
         */
        if (!rel_supports_distinctness(root, innerrel))
            continue;
 
        /* Compute the relid set for the join we are considering */
        joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
        Assert(sjinfo->ojrelid == 0);   /* SEMI joins don't have RT indexes */
 
        /*
         * Since we're only considering a single-rel RHS, any join clauses it
         * has must be clauses linking it to the semijoin's min_lefthand.  We
         * can also consider EC-derived join clauses.
         */
        restrictlist =
            list_concat(generate_join_implied_equalities(root,
                                                         joinrelids,
                                                         sjinfo->min_lefthand,
                                                         innerrel,
                                                         NULL),
                        innerrel->joininfo);
 
        /* Test whether the innerrel is unique for those clauses. */
        if (!innerrel_is_unique(root,
                                joinrelids, sjinfo->min_lefthand, innerrel,
                                JOIN_SEMI, restrictlist, true))
            continue;
 
        /* OK, remove the SpecialJoinInfo from the list. */
        root->join_info_list = foreach_delete_current(root->join_info_list, lc);
    }
}

References Assert(), bms_get_singleton_member(), bms_union(), find_base_rel(), foreach_delete_current, generate_join_implied_equalities(), innerrel_is_unique(), PlannerInfo::join_info_list, JOIN_SEMI, RelOptInfo::joininfo, SpecialJoinInfo::jointype, lfirst, list_concat(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, SpecialJoinInfo::ojrelid, and rel_supports_distinctness().

Referenced by query_planner().

rel_is_distinct_for()

static bool rel_is_distinct_for ( PlannerInfo *  root, RelOptInfo *  rel, List *  clause_list  )

static

Definition at line 849 of file analyzejoins.c.

{
    /*
     * We could skip a couple of tests here if we assume all callers checked
     * rel_supports_distinctness first, but it doesn't seem worth taking any
     * risk for.
     */
    if (rel->reloptkind != RELOPT_BASEREL)
        return false;
    if (rel->rtekind == RTE_RELATION)
    {
        /*
         * Examine the indexes to see if we have a matching unique index.
         * relation_has_unique_index_for automatically adds any usable
         * restriction clauses for the rel, so we needn't do that here.
         */
        if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
            return true;
    }
    else if (rel->rtekind == RTE_SUBQUERY)
    {
        Index       relid = rel->relid;
        Query      *subquery = root->simple_rte_array[relid]->subquery;
        List       *colnos = NIL;
        List       *opids = NIL;
        ListCell   *l;
 
        /*
         * Build the argument lists for query_is_distinct_for: a list of
         * output column numbers that the query needs to be distinct over, and
         * a list of equality operators that the output columns need to be
         * distinct according to.
         *
         * (XXX we are not considering restriction clauses attached to the
         * subquery; is that worth doing?)
         */
        foreach(l, clause_list)
        {
            RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
            Oid         op;
            Var        *var;
 
            /*
             * Get the equality operator we need uniqueness according to.
             * (This might be a cross-type operator and thus not exactly the
             * same operator the subquery would consider; that's all right
             * since query_is_distinct_for can resolve such cases.)  The
             * caller's mergejoinability test should have selected only
             * OpExprs.
             */
            op = castNode(OpExpr, rinfo->clause)->opno;
 
            /* caller identified the inner side for us */
            if (rinfo->outer_is_left)
                var = (Var *) get_rightop(rinfo->clause);
            else
                var = (Var *) get_leftop(rinfo->clause);
 
            /*
             * We may ignore any RelabelType node above the operand.  (There
             * won't be more than one, since eval_const_expressions() has been
             * applied already.)
             */
            if (var && IsA(var, RelabelType))
                var = (Var *) ((RelabelType *) var)->arg;
 
            /*
             * If inner side isn't a Var referencing a subquery output column,
             * this clause doesn't help us.
             */
            if (!var || !IsA(var, Var) ||
                var->varno != relid || var->varlevelsup != 0)
                continue;
 
            colnos = lappend_int(colnos, var->varattno);
            opids = lappend_oid(opids, op);
        }
 
        if (query_is_distinct_for(subquery, colnos, opids))
            return true;
    }
    return false;
}

References castNode, RestrictInfo::clause, get_leftop(), get_rightop(), IsA, lappend_int(), lappend_oid(), lfirst_node, NIL, query_is_distinct_for(), relation_has_unique_index_for(), RelOptInfo::relid, RELOPT_BASEREL, RelOptInfo::reloptkind, RTE_RELATION, RTE_SUBQUERY, RelOptInfo::rtekind, Var::varattno, Var::varlevelsup, and Var::varno.

Referenced by is_innerrel_unique_for(), and join_is_removable().

rel_supports_distinctness()

static bool rel_supports_distinctness ( PlannerInfo *  root, RelOptInfo *  rel  )

static

Definition at line 794 of file analyzejoins.c.

{
    /* We only know about baserels ... */
    if (rel->reloptkind != RELOPT_BASEREL)
        return false;
    if (rel->rtekind == RTE_RELATION)
    {
        /*
         * For a plain relation, we only know how to prove uniqueness by
         * reference to unique indexes.  Make sure there's at least one
         * suitable unique index.  It must be immediately enforced, and not a
         * partial index. (Keep these conditions in sync with
         * relation_has_unique_index_for!)
         */
        ListCell   *lc;
 
        foreach(lc, rel->indexlist)
        {
            IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
 
            if (ind->unique && ind->immediate && ind->indpred == NIL)
                return true;
        }
    }
    else if (rel->rtekind == RTE_SUBQUERY)
    {
        Query      *subquery = root->simple_rte_array[rel->relid]->subquery;
 
        /* Check if the subquery has any qualities that support distinctness */
        if (query_supports_distinctness(subquery))
            return true;
    }
    /* We have no proof rules for any other rtekinds. */
    return false;
}

References RelOptInfo::indexlist, lfirst, NIL, query_supports_distinctness(), RelOptInfo::relid, RELOPT_BASEREL, RelOptInfo::reloptkind, RTE_RELATION, RTE_SUBQUERY, and RelOptInfo::rtekind.

Referenced by innerrel_is_unique(), join_is_removable(), and reduce_unique_semijoins().

remove_rel_from_eclass()

static void remove_rel_from_eclass ( EquivalenceClass *  ec, int  relid, int  ojrelid  )

static

Definition at line 610 of file analyzejoins.c.

{
    ListCell   *lc;
 
    /* Fix up the EC's overall relids */
    ec->ec_relids = bms_del_member(ec->ec_relids, relid);
    ec->ec_relids = bms_del_member(ec->ec_relids, ojrelid);
 
    /*
     * Fix up the member expressions.  Any non-const member that ends with
     * empty em_relids must be a Var or PHV of the removed relation.  We don't
     * need it anymore, so we can drop it.
     */
    foreach(lc, ec->ec_members)
    {
        EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 
        if (bms_is_member(relid, cur_em->em_relids) ||
            bms_is_member(ojrelid, cur_em->em_relids))
        {
            Assert(!cur_em->em_is_const);
            cur_em->em_relids = bms_del_member(cur_em->em_relids, relid);
            cur_em->em_relids = bms_del_member(cur_em->em_relids, ojrelid);
            if (bms_is_empty(cur_em->em_relids))
                ec->ec_members = foreach_delete_current(ec->ec_members, lc);
        }
    }
 
    /* Fix up the source clauses, in case we can re-use them later */
    foreach(lc, ec->ec_sources)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
 
        remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
    }
 
    /*
     * Rather than expend code on fixing up any already-derived clauses, just
     * drop them.  (At this point, any such clauses would be base restriction
     * clauses, which we'd not need anymore anyway.)
     */
    ec->ec_derives = NIL;
}

References Assert(), bms_del_member(), bms_is_empty, bms_is_member(), EquivalenceClass::ec_derives, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceClass::ec_sources, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, foreach_delete_current, lfirst, NIL, and remove_rel_from_restrictinfo().

Referenced by remove_rel_from_query().

remove_rel_from_joinlist()

static List * remove_rel_from_joinlist ( List *  joinlist, int  relid, int *  nremoved  )

static

Definition at line 664 of file analyzejoins.c.

{
    List       *result = NIL;
    ListCell   *jl;
 
    foreach(jl, joinlist)
    {
        Node       *jlnode = (Node *) lfirst(jl);
 
        if (IsA(jlnode, RangeTblRef))
        {
            int         varno = ((RangeTblRef *) jlnode)->rtindex;
 
            if (varno == relid)
                (*nremoved)++;
            else
                result = lappend(result, jlnode);
        }
        else if (IsA(jlnode, List))
        {
            /* Recurse to handle subproblem */
            List       *sublist;
 
            sublist = remove_rel_from_joinlist((List *) jlnode,
                                               relid, nremoved);
            /* Avoid including empty sub-lists in the result */
            if (sublist)
                result = lappend(result, sublist);
        }
        else
        {
            elog(ERROR, "unrecognized joinlist node type: %d",
                 (int) nodeTag(jlnode));
        }
    }
 
    return result;
}

References elog(), ERROR, IsA, lappend(), lfirst, NIL, and nodeTag.

Referenced by remove_useless_joins().

remove_rel_from_query()

static void remove_rel_from_query ( PlannerInfo *  root, int  relid, SpecialJoinInfo *  sjinfo  )

static

Definition at line 331 of file analyzejoins.c.

{
    RelOptInfo *rel = find_base_rel(root, relid);
    int         ojrelid = sjinfo->ojrelid;
    Relids      joinrelids;
    Relids      join_plus_commute;
    List       *joininfos;
    Index       rti;
    ListCell   *l;
 
    /* Compute the relid set for the join we are considering */
    joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
    Assert(ojrelid != 0);
    joinrelids = bms_add_member(joinrelids, ojrelid);
 
    /*
     * Remove references to the rel from other baserels' attr_needed arrays.
     */
    for (rti = 1; rti < root->simple_rel_array_size; rti++)
    {
        RelOptInfo *otherrel = root->simple_rel_array[rti];
        int         attroff;
 
        /* there may be empty slots corresponding to non-baserel RTEs */
        if (otherrel == NULL)
            continue;
 
        Assert(otherrel->relid == rti); /* sanity check on array */
 
        /* no point in processing target rel itself */
        if (otherrel == rel)
            continue;
 
        for (attroff = otherrel->max_attr - otherrel->min_attr;
             attroff >= 0;
             attroff--)
        {
            otherrel->attr_needed[attroff] =
                bms_del_member(otherrel->attr_needed[attroff], relid);
            otherrel->attr_needed[attroff] =
                bms_del_member(otherrel->attr_needed[attroff], ojrelid);
        }
    }
 
    /*
     * Update all_baserels and related relid sets.
     */
    root->all_baserels = bms_del_member(root->all_baserels, relid);
    root->outer_join_rels = bms_del_member(root->outer_join_rels, ojrelid);
    root->all_query_rels = bms_del_member(root->all_query_rels, relid);
    root->all_query_rels = bms_del_member(root->all_query_rels, ojrelid);
 
    /*
     * Likewise remove references from SpecialJoinInfo data structures.
     *
     * This is relevant in case the outer join we're deleting is nested inside
     * other outer joins: the upper joins' relid sets have to be adjusted. The
     * RHS of the target outer join will be made empty here, but that's OK
     * since caller will delete that SpecialJoinInfo entirely.
     */
    foreach(l, root->join_info_list)
    {
        SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);
 
        sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand, relid);
        sjinf->min_righthand = bms_del_member(sjinf->min_righthand, relid);
        sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand, relid);
        sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand, relid);
        sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand, ojrelid);
        sjinf->min_righthand = bms_del_member(sjinf->min_righthand, ojrelid);
        sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand, ojrelid);
        sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand, ojrelid);
        /* relid cannot appear in these fields, but ojrelid can: */
        sjinf->commute_above_l = bms_del_member(sjinf->commute_above_l, ojrelid);
        sjinf->commute_above_r = bms_del_member(sjinf->commute_above_r, ojrelid);
        sjinf->commute_below_l = bms_del_member(sjinf->commute_below_l, ojrelid);
        sjinf->commute_below_r = bms_del_member(sjinf->commute_below_r, ojrelid);
    }
 
    /*
     * Likewise remove references from PlaceHolderVar data structures,
     * removing any no-longer-needed placeholders entirely.
     *
     * Removal is a bit trickier than it might seem: we can remove PHVs that
     * are used at the target rel and/or in the join qual, but not those that
     * are used at join partner rels or above the join.  It's not that easy to
     * distinguish PHVs used at partner rels from those used in the join qual,
     * since they will both have ph_needed sets that are subsets of
     * joinrelids.  However, a PHV used at a partner rel could not have the
     * target rel in ph_eval_at, so we check that while deciding whether to
     * remove or just update the PHV.  There is no corresponding test in
     * join_is_removable because it doesn't need to distinguish those cases.
     */
    foreach(l, root->placeholder_list)
    {
        PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
 
        Assert(!bms_is_member(relid, phinfo->ph_lateral));
        if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
            bms_is_member(relid, phinfo->ph_eval_at) &&
            !bms_is_member(ojrelid, phinfo->ph_eval_at))
        {
            root->placeholder_list = foreach_delete_current(root->placeholder_list,
                                                            l);
            root->placeholder_array[phinfo->phid] = NULL;
        }
        else
        {
            PlaceHolderVar *phv = phinfo->ph_var;
 
            phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
            phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, ojrelid);
            Assert(!bms_is_empty(phinfo->ph_eval_at));  /* checked previously */
            phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
            phinfo->ph_needed = bms_del_member(phinfo->ph_needed, ojrelid);
            /* ph_needed might or might not become empty */
            phv->phrels = bms_del_member(phv->phrels, relid);
            phv->phrels = bms_del_member(phv->phrels, ojrelid);
            Assert(!bms_is_empty(phv->phrels));
            Assert(phv->phnullingrels == NULL); /* no need to adjust */
        }
    }
 
    /*
     * Remove any joinquals referencing the rel from the joininfo lists.
     *
     * In some cases, a joinqual has to be put back after deleting its
     * reference to the target rel.  This can occur for pseudoconstant and
     * outerjoin-delayed quals, which can get marked as requiring the rel in
     * order to force them to be evaluated at or above the join.  We can't
     * just discard them, though.  Only quals that logically belonged to the
     * outer join being discarded should be removed from the query.
     *
     * We might encounter a qual that is a clone of a deletable qual with some
     * outer-join relids added (see deconstruct_distribute_oj_quals).  To
     * ensure we get rid of such clones as well, add the relids of all OJs
     * commutable with this one to the set we test against for
     * pushed-down-ness.
     */
    join_plus_commute = bms_union(joinrelids,
                                  sjinfo->commute_above_r);
    join_plus_commute = bms_add_members(join_plus_commute,
                                        sjinfo->commute_below_l);
 
    /*
     * We must make a copy of the rel's old joininfo list before starting the
     * loop, because otherwise remove_join_clause_from_rels would destroy the
     * list while we're scanning it.
     */
    joininfos = list_copy(rel->joininfo);
    foreach(l, joininfos)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 
        remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
 
        if (RINFO_IS_PUSHED_DOWN(rinfo, join_plus_commute))
        {
            /*
             * There might be references to relid or ojrelid in the
             * RestrictInfo's relid sets, as a consequence of PHVs having had
             * ph_eval_at sets that include those.  We already checked above
             * that any such PHV is safe (and updated its ph_eval_at), so we
             * can just drop those references.
             */
            remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
 
            /*
             * Cross-check that the clause itself does not reference the
             * target rel or join.
             */
#ifdef USE_ASSERT_CHECKING
            {
                Relids      clause_varnos = pull_varnos(root,
                                                        (Node *) rinfo->clause);
 
                Assert(!bms_is_member(relid, clause_varnos));
                Assert(!bms_is_member(ojrelid, clause_varnos));
            }
#endif
            /* Now throw it back into the joininfo lists */
            distribute_restrictinfo_to_rels(root, rinfo);
        }
    }
 
    /*
     * Likewise remove references from EquivalenceClasses.
     */
    foreach(l, root->eq_classes)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(l);
 
        if (bms_is_member(relid, ec->ec_relids) ||
            bms_is_member(ojrelid, ec->ec_relids))
            remove_rel_from_eclass(ec, relid, ojrelid);
    }
 
    /*
     * There may be references to the rel in root->fkey_list, but if so,
     * match_foreign_keys_to_quals() will get rid of them.
     */
 
    /*
     * Finally, remove the rel from the baserel array to prevent it from being
     * referenced again.  (We can't do this earlier because
     * remove_join_clause_from_rels will touch it.)
     */
    root->simple_rel_array[relid] = NULL;
 
    /* And nuke the RelOptInfo, just in case there's another access path */
    pfree(rel);
}

References PlannerInfo::all_baserels, PlannerInfo::all_query_rels, Assert(), bms_add_member(), bms_add_members(), bms_del_member(), bms_is_empty, bms_is_member(), bms_is_subset(), bms_union(), RestrictInfo::clause, SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, distribute_restrictinfo_to_rels(), EquivalenceClass::ec_relids, PlannerInfo::eq_classes, find_base_rel(), foreach_delete_current, PlannerInfo::join_info_list, RelOptInfo::joininfo, lfirst, list_copy(), RelOptInfo::max_attr, RelOptInfo::min_attr, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, SpecialJoinInfo::ojrelid, PlannerInfo::outer_join_rels, pfree(), PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_lateral, PlaceHolderInfo::ph_needed, PlaceHolderInfo::ph_var, PlaceHolderInfo::phid, PlaceHolderVar::phnullingrels, PlannerInfo::placeholder_list, pull_varnos(), RelOptInfo::relid, remove_join_clause_from_rels(), remove_rel_from_eclass(), remove_rel_from_restrictinfo(), RestrictInfo::required_relids, RINFO_IS_PUSHED_DOWN, PlannerInfo::simple_rel_array_size, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by remove_useless_joins().

remove_rel_from_restrictinfo()

static void remove_rel_from_restrictinfo ( RestrictInfo *  rinfo, int  relid, int  ojrelid  )

static

Definition at line 553 of file analyzejoins.c.

{
    /*
     * The clause_relids probably aren't shared with anything else, but let's
     * copy them just to be sure.
     */
    rinfo->clause_relids = bms_copy(rinfo->clause_relids);
    rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
    rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
    /* Likewise for required_relids */
    rinfo->required_relids = bms_copy(rinfo->required_relids);
    rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
    rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
 
    /* If it's an OR, recurse to clean up sub-clauses */
    if (restriction_is_or_clause(rinfo))
    {
        ListCell   *lc;
 
        Assert(is_orclause(rinfo->orclause));
        foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
        {
            Node       *orarg = (Node *) lfirst(lc);
 
            /* OR arguments should be ANDs or sub-RestrictInfos */
            if (is_andclause(orarg))
            {
                List       *andargs = ((BoolExpr *) orarg)->args;
                ListCell   *lc2;
 
                foreach(lc2, andargs)
                {
                    RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
 
                    remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
                }
            }
            else
            {
                RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
 
                remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
            }
        }
    }
}

References Assert(), bms_copy(), bms_del_member(), castNode, is_andclause(), is_orclause(), lfirst, lfirst_node, RestrictInfo::required_relids, and restriction_is_or_clause().

Referenced by remove_rel_from_eclass(), and remove_rel_from_query().

remove_useless_joins()

List* remove_useless_joins	(	PlannerInfo *	root,
		List *	joinlist
	)

Definition at line 66 of file analyzejoins.c.

{
    ListCell   *lc;
 
    /*
     * We are only interested in relations that are left-joined to, so we can
     * scan the join_info_list to find them easily.
     */
restart:
    foreach(lc, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
        int         innerrelid;
        int         nremoved;
 
        /* Skip if not removable */
        if (!join_is_removable(root, sjinfo))
            continue;
 
        /*
         * Currently, join_is_removable can only succeed when the sjinfo's
         * righthand is a single baserel.  Remove that rel from the query and
         * joinlist.
         */
        innerrelid = bms_singleton_member(sjinfo->min_righthand);
 
        remove_rel_from_query(root, innerrelid, sjinfo);
 
        /* We verify that exactly one reference gets removed from joinlist */
        nremoved = 0;
        joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
        if (nremoved != 1)
            elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
 
        /*
         * We can delete this SpecialJoinInfo from the list too, since it's no
         * longer of interest.  (Since we'll restart the foreach loop
         * immediately, we don't bother with foreach_delete_current.)
         */
        root->join_info_list = list_delete_cell(root->join_info_list, lc);
 
        /*
         * Restart the scan.  This is necessary to ensure we find all
         * removable joins independently of ordering of the join_info_list
         * (note that removal of attr_needed bits may make a join appear
         * removable that did not before).
         */
        goto restart;
    }
 
    return joinlist;
}

References bms_singleton_member(), elog(), ERROR, PlannerInfo::join_info_list, join_is_removable(), lfirst, list_delete_cell(), SpecialJoinInfo::min_righthand, remove_rel_from_joinlist(), and remove_rel_from_query().

Referenced by query_planner().