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

Include dependency graph for analyzejoins.c:

Functions
static bool	join_is_removable (PlannerInfo root, SpecialJoinInfo sjinfo)

static void	remove_rel_from_query (PlannerInfo *root, int relid, Relids joinrelids)

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 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 outerrelids, RelOptInfo innerrel, JoinType jointype, List *restrictlist, bool force_cache)

Function Documentation

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

inlinestatic

Definition at line 127 of file analyzejoins.c.

References bms_is_subset(), RestrictInfo::left_relids, RestrictInfo::outer_is_left, and RestrictInfo::right_relids.

Referenced by is_innerrel_unique_for(), and join_is_removable().

 {
     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 */
 }

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

static

Definition at line 923 of file analyzejoins.c.

References forboth, InvalidOid, lfirst_int, and lfirst_oid.

Referenced by query_is_distinct_for().

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

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

Definition at line 962 of file analyzejoins.c.

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

Referenced by add_paths_to_joinrel(), and reduce_unique_semijoins().

 {
     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, 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;
     }
 }

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

static

Definition at line 1069 of file analyzejoins.c.

References RestrictInfo::can_join, clause_sides_match_join(), IS_OUTER_JOIN, RestrictInfo::is_pushed_down, lappend(), lfirst, RestrictInfo::mergeopfamilies, NIL, rel_is_distinct_for(), and RelOptInfo::relids.

Referenced by innerrel_is_unique().

 {
     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 (restrictinfo->is_pushed_down && IS_OUTER_JOIN(jointype))
             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);
 }

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

static

Definition at line 159 of file analyzejoins.c.

References RelOptInfo::attr_needed, bms_equal(), bms_get_singleton_member(), bms_is_member(), bms_is_subset(), bms_overlap(), bms_union(), RestrictInfo::can_join, RestrictInfo::clause_relids, clause_sides_match_join(), SpecialJoinInfo::delay_upper_joins, find_base_rel(), RestrictInfo::is_pushed_down, JOIN_LEFT, RelOptInfo::joininfo, SpecialJoinInfo::jointype, lappend(), lfirst, RelOptInfo::max_attr, RestrictInfo::mergeopfamilies, RelOptInfo::min_attr, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_lateral, PlaceHolderInfo::ph_needed, PlaceHolderInfo::ph_var, PlaceHolderVar::phexpr, PlannerInfo::placeholder_list, pull_varnos(), rel_is_distinct_for(), rel_supports_distinctness(), RelOptInfo::relids, and RestrictInfo::required_relids.

Referenced by remove_useless_joins().

 {
     int         innerrelid;
     RelOptInfo *innerrel;
     Relids      joinrelids;
     List       *clause_list = NIL;
     ListCell   *l;
     int         attroff;
 
     /*
      * Must be a non-delaying left join to a single baserel, else we aren't
      * going to be able to do anything with it.
      */
     if (sjinfo->jointype != JOIN_LEFT ||
         sjinfo->delay_upper_joins)
         return false;
 
     if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
         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 */
     joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
 
     /*
      * We can't remove the join if any inner-rel attributes are used above the
      * join.
      *
      * Note that this test only detects use of inner-rel attributes in higher
      * join conditions and the target list.  There might be such attributes in
      * pushed-down conditions at this join, too.  We check that case below.
      *
      * 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], joinrelids))
             return false;
     }
 
     /*
      * Similarly check that the inner rel isn't needed by any PlaceHolderVars
      * that will be used above the join.  We only need to fail if such a PHV
      * actually references some inner-rel attributes; but the correct check
      * for that is relatively expensive, so we first check against ph_eval_at,
      * which must mention the inner rel if the PHV uses any inner-rel attrs as
      * non-lateral references.  Note that if the PHV's syntactic scope is just
      * the inner rel, we can't drop the rel even if the PHV is variable-free.
      */
     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_is_subset(phinfo->ph_needed, joinrelids))
             continue;           /* PHV is not used above the join */
         if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
             continue;           /* it definitely doesn't reference innerrel */
         if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids))
             return false;       /* there isn't any other place to eval PHV */
         if (bms_overlap(pull_varnos((Node *) phinfo->ph_var->phexpr),
                         innerrel->relids))
             return false;       /* it does reference 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 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 (restrictinfo->is_pushed_down ||
             !bms_equal(restrictinfo->required_relids, joinrelids))
         {
             /*
              * If such a clause actually references the inner rel then join
              * removal has to be disallowed.  We have to check this despite
              * the previous attr_needed checks because of the possibility of
              * pushed-down clauses referencing the rel.
              */
             if (bms_is_member(innerrelid, restrictinfo->clause_relids))
                 return false;
             continue;           /* else, 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;
 }

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

Definition at line 774 of file analyzejoins.c.

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

Referenced by create_unique_path(), and rel_is_distinct_for().

 {
     ListCell   *l;
     Oid         opid;
 
     Assert(list_length(colnos) == list_length(opids));
 
     /*
      * A set-returning function in the query's targetlist can result in
      * returning duplicate rows, if the SRF is evaluated after the
      * de-duplication step; so we play it safe and say "no" if there are any
      * SRFs.  (We could be certain that it's okay if SRFs appear only in the
      * specified columns, since those must be evaluated before de-duplication;
      * but it doesn't presently seem worth the complication to check that.)
      */
     if (query->hasTargetSRFs)
         return false;
 
     /*
      * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
      * columns in the DISTINCT clause appear in colnos and operator semantics
      * match.
      */
     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;
     }
 
     /*
      * 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(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;
 }

bool query_supports_distinctness ( Query * query )

Definition at line 737 of file analyzejoins.c.

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

Referenced by create_unique_path(), and rel_supports_distinctness().

 {
     /* we don't cope with SRFs, see comment below */
     if (query->hasTargetSRFs)
         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;
 }

void reduce_unique_semijoins ( PlannerInfo * root )

Definition at line 512 of file analyzejoins.c.

References bms_get_singleton_member(), bms_union(), SpecialJoinInfo::delay_upper_joins, find_base_rel(), generate_join_implied_equalities(), innerrel_is_unique(), PlannerInfo::join_info_list, JOIN_SEMI, RelOptInfo::joininfo, SpecialJoinInfo::jointype, lfirst, list_concat(), list_delete_ptr(), list_head(), lnext, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, next, NULL, and rel_supports_distinctness().

Referenced by query_planner().

 {
     ListCell   *lc;
     ListCell   *next;
 
     /*
      * Scan the join_info_list to find semijoins.  We can't use foreach
      * because we may delete the current cell.
      */
     for (lc = list_head(root->join_info_list); lc != NULL; lc = next)
     {
         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
         int         innerrelid;
         RelOptInfo *innerrel;
         Relids      joinrelids;
         List       *restrictlist;
 
         next = lnext(lc);
 
         /*
          * Must be a non-delaying semijoin to a single baserel, else we aren't
          * going to be able to do anything with it.  (It's probably not
          * possible for delay_upper_joins to be set on a semijoin, but we
          * might as well check.)
          */
         if (sjinfo->jointype != JOIN_SEMI ||
             sjinfo->delay_upper_joins)
             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);
 
         /*
          * 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),
                         innerrel->joininfo);
 
         /* Test whether the innerrel is unique for those clauses. */
         if (!innerrel_is_unique(root, sjinfo->min_lefthand, innerrel,
                                 JOIN_SEMI, restrictlist, true))
             continue;
 
         /* OK, remove the SpecialJoinInfo from the list. */
         root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
     }
 }

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

static

Definition at line 648 of file analyzejoins.c.

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

Referenced by is_innerrel_unique_for(), and join_is_removable().

 {
     /*
      * 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);
 
             /*
              * 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;
 }

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

static

Definition at line 592 of file analyzejoins.c.

References IndexOptInfo::immediate, RelOptInfo::indexlist, IndexOptInfo::indpred, lfirst, NIL, IndexOptInfo::predOK, query_supports_distinctness(), RelOptInfo::relid, RELOPT_BASEREL, RelOptInfo::reloptkind, RTE_RELATION, RTE_SUBQUERY, RelOptInfo::rtekind, PlannerInfo::simple_rte_array, RangeTblEntry::subquery, and IndexOptInfo::unique.

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

 {
     /* 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 if
          * it's a partial index, it must match the query.  (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 || ind->predOK))
                 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;
 }

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

static

Definition at line 458 of file analyzejoins.c.

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

Referenced by remove_useless_joins().

 {
     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;
 }

static void remove_rel_from_query	(	PlannerInfo *	root,
		int	relid,
		Relids	joinrelids
	)

static

Definition at line 313 of file analyzejoins.c.

References Assert, RelOptInfo::attr_needed, bms_copy(), bms_del_member(), bms_equal(), bms_is_empty(), bms_is_member(), bms_is_subset(), RestrictInfo::clause_relids, distribute_restrictinfo_to_rels(), find_base_rel(), RestrictInfo::is_pushed_down, PlannerInfo::join_info_list, RelOptInfo::joininfo, lfirst, list_copy(), list_delete_ptr(), list_head(), lnext, RelOptInfo::max_attr, RelOptInfo::min_attr, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NULL, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_lateral, PlaceHolderInfo::ph_needed, PlannerInfo::placeholder_list, RelOptInfo::relid, RELOPT_DEADREL, RelOptInfo::reloptkind, remove_join_clause_from_rels(), RestrictInfo::required_relids, PlannerInfo::simple_rel_array, PlannerInfo::simple_rel_array_size, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by remove_useless_joins().

 {
     RelOptInfo *rel = find_base_rel(root, relid);
     List       *joininfos;
     Index       rti;
     ListCell   *l;
     ListCell   *nextl;
 
     /*
      * Mark the rel as "dead" to show it is no longer part of the join tree.
      * (Removing it from the baserel array altogether seems too risky.)
      */
     rel->reloptkind = RELOPT_DEADREL;
 
     /*
      * 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);
         }
     }
 
     /*
      * 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 *sjinfo = (SpecialJoinInfo *) lfirst(l);
 
         sjinfo->min_lefthand = bms_del_member(sjinfo->min_lefthand, relid);
         sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, relid);
         sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, relid);
         sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, relid);
     }
 
     /*
      * Likewise remove references from PlaceHolderVar data structures,
      * removing any no-longer-needed placeholders entirely.
      *
      * Removal is a bit tricker 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.
      */
     for (l = list_head(root->placeholder_list); l != NULL; l = nextl)
     {
         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
 
         nextl = lnext(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))
             root->placeholder_list = list_delete_ptr(root->placeholder_list,
                                                      phinfo);
         else
         {
             phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
             Assert(!bms_is_empty(phinfo->ph_eval_at));
             phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
         }
     }
 
     /*
      * 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 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 ||
             !bms_equal(rinfo->required_relids, joinrelids))
         {
             /* Recheck that qual doesn't actually reference the target rel */
             Assert(!bms_is_member(relid, rinfo->clause_relids));
 
             /*
              * The required_relids probably aren't shared with anything else,
              * but let's copy them just to be sure.
              */
             rinfo->required_relids = bms_copy(rinfo->required_relids);
             rinfo->required_relids = bms_del_member(rinfo->required_relids,
                                                     relid);
             distribute_restrictinfo_to_rels(root, rinfo);
         }
     }
 
     /*
      * There may be references to the rel in root->fkey_list, but if so,
      * match_foreign_keys_to_quals() will get rid of them.
      */
 }

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

Definition at line 60 of file analyzejoins.c.

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

Referenced by query_planner().

 {
     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,
                               bms_union(sjinfo->min_lefthand,
                                         sjinfo->min_righthand));
 
         /* 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.
          */
         root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
 
         /*
          * 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).  Also, since we just deleted the
          * current list cell, we'd have to have some kluge to continue the
          * list scan anyway.
          */
         goto restart;
     }
 
     return joinlist;
 }

Functions

Function Documentation