PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
analyzejoins.c File Reference
#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:

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, Relids joinrelids)
 
static Listremove_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)
 
Listremove_useless_joins (PlannerInfo *root, List *joinlist)
 
static bool clause_sides_match_join (RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
 
bool query_supports_distinctness (Query *query)
 
bool query_is_distinct_for (Query *query, List *colnos, List *opids)
 

Function Documentation

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

Definition at line 122 of file analyzejoins.c.

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

Referenced by join_is_removable().

124 {
125  if (bms_is_subset(rinfo->left_relids, outerrelids) &&
126  bms_is_subset(rinfo->right_relids, innerrelids))
127  {
128  /* lefthand side is outer */
129  rinfo->outer_is_left = true;
130  return true;
131  }
132  else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
133  bms_is_subset(rinfo->right_relids, outerrelids))
134  {
135  /* righthand side is outer */
136  rinfo->outer_is_left = false;
137  return true;
138  }
139  return false; /* no good for these input relations */
140 }
Relids left_relids
Definition: relation.h:1664
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
bool outer_is_left
Definition: relation.h:1692
Relids right_relids
Definition: relation.h:1665
static Oid distinct_col_search ( int  colno,
List colnos,
List opids 
)
static

Definition at line 838 of file analyzejoins.c.

References forboth, InvalidOid, lfirst_int, and lfirst_oid.

Referenced by query_is_distinct_for().

839 {
840  ListCell *lc1,
841  *lc2;
842 
843  forboth(lc1, colnos, lc2, opids)
844  {
845  if (colno == lfirst_int(lc1))
846  return lfirst_oid(lc2);
847  }
848  return InvalidOid;
849 }
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:174
#define lfirst_int(lc)
Definition: pg_list.h:107
#define InvalidOid
Definition: postgres_ext.h:36
#define lfirst_oid(lc)
Definition: pg_list.h:108
static bool join_is_removable ( PlannerInfo root,
SpecialJoinInfo sjinfo 
)
static

Definition at line 154 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().

155 {
156  int innerrelid;
157  RelOptInfo *innerrel;
158  Relids joinrelids;
159  List *clause_list = NIL;
160  ListCell *l;
161  int attroff;
162 
163  /*
164  * Must be a non-delaying left join to a single baserel, else we aren't
165  * going to be able to do anything with it.
166  */
167  if (sjinfo->jointype != JOIN_LEFT ||
168  sjinfo->delay_upper_joins)
169  return false;
170 
171  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
172  return false;
173 
174  innerrel = find_base_rel(root, innerrelid);
175 
176  /*
177  * Before we go to the effort of checking whether any innerrel variables
178  * are needed above the join, make a quick check to eliminate cases in
179  * which we will surely be unable to prove uniqueness of the innerrel.
180  */
181  if (!rel_supports_distinctness(root, innerrel))
182  return false;
183 
184  /* Compute the relid set for the join we are considering */
185  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
186 
187  /*
188  * We can't remove the join if any inner-rel attributes are used above the
189  * join.
190  *
191  * Note that this test only detects use of inner-rel attributes in higher
192  * join conditions and the target list. There might be such attributes in
193  * pushed-down conditions at this join, too. We check that case below.
194  *
195  * As a micro-optimization, it seems better to start with max_attr and
196  * count down rather than starting with min_attr and counting up, on the
197  * theory that the system attributes are somewhat less likely to be wanted
198  * and should be tested last.
199  */
200  for (attroff = innerrel->max_attr - innerrel->min_attr;
201  attroff >= 0;
202  attroff--)
203  {
204  if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
205  return false;
206  }
207 
208  /*
209  * Similarly check that the inner rel isn't needed by any PlaceHolderVars
210  * that will be used above the join. We only need to fail if such a PHV
211  * actually references some inner-rel attributes; but the correct check
212  * for that is relatively expensive, so we first check against ph_eval_at,
213  * which must mention the inner rel if the PHV uses any inner-rel attrs as
214  * non-lateral references. Note that if the PHV's syntactic scope is just
215  * the inner rel, we can't drop the rel even if the PHV is variable-free.
216  */
217  foreach(l, root->placeholder_list)
218  {
219  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
220 
221  if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
222  return false; /* it references innerrel laterally */
223  if (bms_is_subset(phinfo->ph_needed, joinrelids))
224  continue; /* PHV is not used above the join */
225  if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
226  continue; /* it definitely doesn't reference innerrel */
227  if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids))
228  return false; /* there isn't any other place to eval PHV */
229  if (bms_overlap(pull_varnos((Node *) phinfo->ph_var->phexpr),
230  innerrel->relids))
231  return false; /* it does reference innerrel */
232  }
233 
234  /*
235  * Search for mergejoinable clauses that constrain the inner rel against
236  * either the outer rel or a pseudoconstant. If an operator is
237  * mergejoinable then it behaves like equality for some btree opclass, so
238  * it's what we want. The mergejoinability test also eliminates clauses
239  * containing volatile functions, which we couldn't depend on.
240  */
241  foreach(l, innerrel->joininfo)
242  {
243  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
244 
245  /*
246  * If it's not a join clause for this outer join, we can't use it.
247  * Note that if the clause is pushed-down, then it is logically from
248  * above the outer join, even if it references no other rels (it might
249  * be from WHERE, for example).
250  */
251  if (restrictinfo->is_pushed_down ||
252  !bms_equal(restrictinfo->required_relids, joinrelids))
253  {
254  /*
255  * If such a clause actually references the inner rel then join
256  * removal has to be disallowed. We have to check this despite
257  * the previous attr_needed checks because of the possibility of
258  * pushed-down clauses referencing the rel.
259  */
260  if (bms_is_member(innerrelid, restrictinfo->clause_relids))
261  return false;
262  continue; /* else, ignore; not useful here */
263  }
264 
265  /* Ignore if it's not a mergejoinable clause */
266  if (!restrictinfo->can_join ||
267  restrictinfo->mergeopfamilies == NIL)
268  continue; /* not mergejoinable */
269 
270  /*
271  * Check if clause has the form "outer op inner" or "inner op outer",
272  * and if so mark which side is inner.
273  */
274  if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
275  innerrel->relids))
276  continue; /* no good for these input relations */
277 
278  /* OK, add to list */
279  clause_list = lappend(clause_list, restrictinfo);
280  }
281 
282  /*
283  * Now that we have the relevant equality join clauses, try to prove the
284  * innerrel distinct.
285  */
286  if (rel_is_distinct_for(root, innerrel, clause_list))
287  return true;
288 
289  /*
290  * Some day it would be nice to check for other methods of establishing
291  * distinctness.
292  */
293  return false;
294 }
#define NIL
Definition: pg_list.h:69
Relids ph_needed
Definition: relation.h:1937
Relids ph_eval_at
Definition: relation.h:1935
PlaceHolderVar * ph_var
Definition: relation.h:1934
Relids * attr_needed
Definition: relation.h:523
Relids required_relids
Definition: relation.h:1655
Relids min_righthand
Definition: relation.h:1808
Relids clause_relids
Definition: relation.h:1652
Definition: nodes.h:508
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:539
List * mergeopfamilies
Definition: relation.h:1682
Expr * phexpr
Definition: relation.h:1740
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
Definition: analyzejoins.c:561
bool can_join
Definition: relation.h:1643
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
List * joininfo
Definition: relation.h:549
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition: analyzejoins.c:122
Relids relids
Definition: relation.h:490
Relids pull_varnos(Node *node)
Definition: var.c:95
List * lappend(List *list, void *datum)
Definition: list.c:128
bool delay_upper_joins
Definition: relation.h:1813
Relids ph_lateral
Definition: relation.h:1936
bool is_pushed_down
Definition: relation.h:1639
#define lfirst(lc)
Definition: pg_list.h:106
JoinType jointype
Definition: relation.h:1811
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
AttrNumber max_attr
Definition: relation.h:522
List * placeholder_list
Definition: relation.h:253
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:219
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
Definition: analyzejoins.c:505
Definition: pg_list.h:45
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:419
Relids min_lefthand
Definition: relation.h:1807
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
AttrNumber min_attr
Definition: relation.h:521
bool query_is_distinct_for ( Query query,
List colnos,
List opids 
)

Definition at line 688 of file analyzejoins.c.

References SetOperationStmt::all, Assert, 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, IsA, 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().

689 {
690  ListCell *l;
691  Oid opid;
692 
693  Assert(list_length(colnos) == list_length(opids));
694 
695  /*
696  * A set-returning function in the query's targetlist can result in
697  * returning duplicate rows, if the SRF is evaluated after the
698  * de-duplication step; so we play it safe and say "no" if there are any
699  * SRFs. (We could be certain that it's okay if SRFs appear only in the
700  * specified columns, since those must be evaluated before de-duplication;
701  * but it doesn't presently seem worth the complication to check that.)
702  */
703  if (query->hasTargetSRFs)
704  return false;
705 
706  /*
707  * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
708  * columns in the DISTINCT clause appear in colnos and operator semantics
709  * match.
710  */
711  if (query->distinctClause)
712  {
713  foreach(l, query->distinctClause)
714  {
715  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
717  query->targetList);
718 
719  opid = distinct_col_search(tle->resno, colnos, opids);
720  if (!OidIsValid(opid) ||
721  !equality_ops_are_compatible(opid, sgc->eqop))
722  break; /* exit early if no match */
723  }
724  if (l == NULL) /* had matches for all? */
725  return true;
726  }
727 
728  /*
729  * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
730  * the grouped columns appear in colnos and operator semantics match.
731  */
732  if (query->groupClause && !query->groupingSets)
733  {
734  foreach(l, query->groupClause)
735  {
736  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
738  query->targetList);
739 
740  opid = distinct_col_search(tle->resno, colnos, opids);
741  if (!OidIsValid(opid) ||
742  !equality_ops_are_compatible(opid, sgc->eqop))
743  break; /* exit early if no match */
744  }
745  if (l == NULL) /* had matches for all? */
746  return true;
747  }
748  else if (query->groupingSets)
749  {
750  /*
751  * If we have grouping sets with expressions, we probably don't have
752  * uniqueness and analysis would be hard. Punt.
753  */
754  if (query->groupClause)
755  return false;
756 
757  /*
758  * If we have no groupClause (therefore no grouping expressions), we
759  * might have one or many empty grouping sets. If there's just one,
760  * then we're returning only one row and are certainly unique. But
761  * otherwise, we know we're certainly not unique.
762  */
763  if (list_length(query->groupingSets) == 1 &&
764  ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
765  return true;
766  else
767  return false;
768  }
769  else
770  {
771  /*
772  * If we have no GROUP BY, but do have aggregates or HAVING, then the
773  * result is at most one row so it's surely unique, for any operators.
774  */
775  if (query->hasAggs || query->havingQual)
776  return true;
777  }
778 
779  /*
780  * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
781  * except with ALL.
782  */
783  if (query->setOperations)
784  {
785  SetOperationStmt *topop = (SetOperationStmt *) query->setOperations;
786 
787  Assert(IsA(topop, SetOperationStmt));
788  Assert(topop->op != SETOP_NONE);
789 
790  if (!topop->all)
791  {
792  ListCell *lg;
793 
794  /* We're good if all the nonjunk output columns are in colnos */
795  lg = list_head(topop->groupClauses);
796  foreach(l, query->targetList)
797  {
798  TargetEntry *tle = (TargetEntry *) lfirst(l);
799  SortGroupClause *sgc;
800 
801  if (tle->resjunk)
802  continue; /* ignore resjunk columns */
803 
804  /* non-resjunk columns should have grouping clauses */
805  Assert(lg != NULL);
806  sgc = (SortGroupClause *) lfirst(lg);
807  lg = lnext(lg);
808 
809  opid = distinct_col_search(tle->resno, colnos, opids);
810  if (!OidIsValid(opid) ||
811  !equality_ops_are_compatible(opid, sgc->eqop))
812  break; /* exit early if no match */
813  }
814  if (l == NULL) /* had matches for all? */
815  return true;
816  }
817  }
818 
819  /*
820  * XXX Are there any other cases in which we can easily see the result
821  * must be distinct?
822  *
823  * If you do add more smarts to this function, be sure to update
824  * query_supports_distinctness() to match.
825  */
826 
827  return false;
828 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:370
static Oid distinct_col_search(int colno, List *colnos, List *opids)
Definition: analyzejoins.c:838
bool hasAggs
Definition: parsenodes.h:116
List * groupingSets
Definition: parsenodes.h:139
unsigned int Oid
Definition: postgres_ext.h:31
#define OidIsValid(objectId)
Definition: c.h:533
List * targetList
Definition: parsenodes.h:131
bool resjunk
Definition: primnodes.h:1337
#define linitial(l)
Definition: pg_list.h:110
List * distinctClause
Definition: parsenodes.h:145
AttrNumber resno
Definition: primnodes.h:1331
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
#define lnext(lc)
Definition: pg_list.h:105
bool hasTargetSRFs
Definition: parsenodes.h:118
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:670
#define lfirst(lc)
Definition: pg_list.h:106
bool equality_ops_are_compatible(Oid opno1, Oid opno2)
Definition: lsyscache.c:695
static int list_length(const List *l)
Definition: pg_list.h:89
SetOperation op
Definition: parsenodes.h:1485
Node * setOperations
Definition: parsenodes.h:154
List * groupClause
Definition: parsenodes.h:137
Node * havingQual
Definition: parsenodes.h:141
bool query_supports_distinctness ( Query query)

Definition at line 651 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().

652 {
653  /* we don't cope with SRFs, see comment below */
654  if (query->hasTargetSRFs)
655  return false;
656 
657  /* check for features we can prove distinctness with */
658  if (query->distinctClause != NIL ||
659  query->groupClause != NIL ||
660  query->groupingSets != NIL ||
661  query->hasAggs ||
662  query->havingQual ||
663  query->setOperations)
664  return true;
665 
666  return false;
667 }
#define NIL
Definition: pg_list.h:69
bool hasAggs
Definition: parsenodes.h:116
List * groupingSets
Definition: parsenodes.h:139
List * distinctClause
Definition: parsenodes.h:145
bool hasTargetSRFs
Definition: parsenodes.h:118
Node * setOperations
Definition: parsenodes.h:154
List * groupClause
Definition: parsenodes.h:137
Node * havingQual
Definition: parsenodes.h:141
static bool rel_is_distinct_for ( PlannerInfo root,
RelOptInfo rel,
List clause_list 
)
static

Definition at line 561 of file analyzejoins.c.

References Assert, RestrictInfo::clause, get_leftop(), get_rightop(), IsA, lappend_int(), lappend_oid(), lfirst, 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 join_is_removable().

562 {
563  /*
564  * We could skip a couple of tests here if we assume all callers checked
565  * rel_supports_distinctness first, but it doesn't seem worth taking any
566  * risk for.
567  */
568  if (rel->reloptkind != RELOPT_BASEREL)
569  return false;
570  if (rel->rtekind == RTE_RELATION)
571  {
572  /*
573  * Examine the indexes to see if we have a matching unique index.
574  * relation_has_unique_index_for automatically adds any usable
575  * restriction clauses for the rel, so we needn't do that here.
576  */
577  if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
578  return true;
579  }
580  else if (rel->rtekind == RTE_SUBQUERY)
581  {
582  Index relid = rel->relid;
583  Query *subquery = root->simple_rte_array[relid]->subquery;
584  List *colnos = NIL;
585  List *opids = NIL;
586  ListCell *l;
587 
588  /*
589  * Build the argument lists for query_is_distinct_for: a list of
590  * output column numbers that the query needs to be distinct over, and
591  * a list of equality operators that the output columns need to be
592  * distinct according to.
593  *
594  * (XXX we are not considering restriction clauses attached to the
595  * subquery; is that worth doing?)
596  */
597  foreach(l, clause_list)
598  {
599  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
600  Oid op;
601  Var *var;
602 
603  /*
604  * Get the equality operator we need uniqueness according to.
605  * (This might be a cross-type operator and thus not exactly the
606  * same operator the subquery would consider; that's all right
607  * since query_is_distinct_for can resolve such cases.) The
608  * caller's mergejoinability test should have selected only
609  * OpExprs.
610  */
611  Assert(IsA(rinfo->clause, OpExpr));
612  op = ((OpExpr *) rinfo->clause)->opno;
613 
614  /* caller identified the inner side for us */
615  if (rinfo->outer_is_left)
616  var = (Var *) get_rightop(rinfo->clause);
617  else
618  var = (Var *) get_leftop(rinfo->clause);
619 
620  /*
621  * If inner side isn't a Var referencing a subquery output column,
622  * this clause doesn't help us.
623  */
624  if (!var || !IsA(var, Var) ||
625  var->varno != relid || var->varlevelsup != 0)
626  continue;
627 
628  colnos = lappend_int(colnos, var->varattno);
629  opids = lappend_oid(opids, op);
630  }
631 
632  if (query_is_distinct_for(subquery, colnos, opids))
633  return true;
634  }
635  return false;
636 }
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
bool query_is_distinct_for(Query *query, List *colnos, List *opids)
Definition: analyzejoins.c:688
Index varlevelsup
Definition: primnodes.h:151
RelOptKind reloptkind
Definition: relation.h:487
AttrNumber varattno
Definition: primnodes.h:146
unsigned int Oid
Definition: postgres_ext.h:31
Definition: primnodes.h:141
List * lappend_oid(List *list, Oid datum)
Definition: list.c:164
Node * get_leftop(const Expr *clause)
Definition: clauses.c:198
bool outer_is_left
Definition: relation.h:1692
List * lappend_int(List *list, int datum)
Definition: list.c:146
Index relid
Definition: relation.h:518
RangeTblEntry ** simple_rte_array
Definition: relation.h:185
Expr * clause
Definition: relation.h:1637
Index varno
Definition: primnodes.h:144
unsigned int Index
Definition: c.h:361
RTEKind rtekind
Definition: relation.h:520
#define Assert(condition)
Definition: c.h:670
#define lfirst(lc)
Definition: pg_list.h:106
Node * get_rightop(const Expr *clause)
Definition: clauses.c:215
Query * subquery
Definition: parsenodes.h:900
bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
Definition: indxpath.c:2943
Definition: pg_list.h:45
static bool rel_supports_distinctness ( PlannerInfo root,
RelOptInfo rel 
)
static

Definition at line 505 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 join_is_removable().

506 {
507  /* We only know about baserels ... */
508  if (rel->reloptkind != RELOPT_BASEREL)
509  return false;
510  if (rel->rtekind == RTE_RELATION)
511  {
512  /*
513  * For a plain relation, we only know how to prove uniqueness by
514  * reference to unique indexes. Make sure there's at least one
515  * suitable unique index. It must be immediately enforced, and if
516  * it's a partial index, it must match the query. (Keep these
517  * conditions in sync with relation_has_unique_index_for!)
518  */
519  ListCell *lc;
520 
521  foreach(lc, rel->indexlist)
522  {
523  IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
524 
525  if (ind->unique && ind->immediate &&
526  (ind->indpred == NIL || ind->predOK))
527  return true;
528  }
529  }
530  else if (rel->rtekind == RTE_SUBQUERY)
531  {
532  Query *subquery = root->simple_rte_array[rel->relid]->subquery;
533 
534  /* Check if the subquery has any qualities that support distinctness */
535  if (query_supports_distinctness(subquery))
536  return true;
537  }
538  /* We have no proof rules for any other rtekinds. */
539  return false;
540 }
#define NIL
Definition: pg_list.h:69
bool predOK
Definition: relation.h:620
RelOptKind reloptkind
Definition: relation.h:487
bool immediate
Definition: relation.h:622
bool unique
Definition: relation.h:621
Index relid
Definition: relation.h:518
RangeTblEntry ** simple_rte_array
Definition: relation.h:185
RTEKind rtekind
Definition: relation.h:520
List * indexlist
Definition: relation.h:527
#define lfirst(lc)
Definition: pg_list.h:106
bool query_supports_distinctness(Query *query)
Definition: analyzejoins.c:651
Query * subquery
Definition: parsenodes.h:900
List * indpred
Definition: relation.h:611
static List * remove_rel_from_joinlist ( List joinlist,
int  relid,
int *  nremoved 
)
static

Definition at line 453 of file analyzejoins.c.

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

Referenced by remove_useless_joins().

454 {
455  List *result = NIL;
456  ListCell *jl;
457 
458  foreach(jl, joinlist)
459  {
460  Node *jlnode = (Node *) lfirst(jl);
461 
462  if (IsA(jlnode, RangeTblRef))
463  {
464  int varno = ((RangeTblRef *) jlnode)->rtindex;
465 
466  if (varno == relid)
467  (*nremoved)++;
468  else
469  result = lappend(result, jlnode);
470  }
471  else if (IsA(jlnode, List))
472  {
473  /* Recurse to handle subproblem */
474  List *sublist;
475 
476  sublist = remove_rel_from_joinlist((List *) jlnode,
477  relid, nremoved);
478  /* Avoid including empty sub-lists in the result */
479  if (sublist)
480  result = lappend(result, sublist);
481  }
482  else
483  {
484  elog(ERROR, "unrecognized joinlist node type: %d",
485  (int) nodeTag(jlnode));
486  }
487  }
488 
489  return result;
490 }
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:559
Definition: nodes.h:508
#define ERROR
Definition: elog.h:43
List * lappend(List *list, void *datum)
Definition: list.c:128
#define lfirst(lc)
Definition: pg_list.h:106
#define nodeTag(nodeptr)
Definition: nodes.h:513
static List * remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
Definition: analyzejoins.c:453
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
static void remove_rel_from_query ( PlannerInfo root,
int  relid,
Relids  joinrelids 
)
static

Definition at line 308 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().

309 {
310  RelOptInfo *rel = find_base_rel(root, relid);
311  List *joininfos;
312  Index rti;
313  ListCell *l;
314  ListCell *nextl;
315 
316  /*
317  * Mark the rel as "dead" to show it is no longer part of the join tree.
318  * (Removing it from the baserel array altogether seems too risky.)
319  */
320  rel->reloptkind = RELOPT_DEADREL;
321 
322  /*
323  * Remove references to the rel from other baserels' attr_needed arrays.
324  */
325  for (rti = 1; rti < root->simple_rel_array_size; rti++)
326  {
327  RelOptInfo *otherrel = root->simple_rel_array[rti];
328  int attroff;
329 
330  /* there may be empty slots corresponding to non-baserel RTEs */
331  if (otherrel == NULL)
332  continue;
333 
334  Assert(otherrel->relid == rti); /* sanity check on array */
335 
336  /* no point in processing target rel itself */
337  if (otherrel == rel)
338  continue;
339 
340  for (attroff = otherrel->max_attr - otherrel->min_attr;
341  attroff >= 0;
342  attroff--)
343  {
344  otherrel->attr_needed[attroff] =
345  bms_del_member(otherrel->attr_needed[attroff], relid);
346  }
347  }
348 
349  /*
350  * Likewise remove references from SpecialJoinInfo data structures.
351  *
352  * This is relevant in case the outer join we're deleting is nested inside
353  * other outer joins: the upper joins' relid sets have to be adjusted. The
354  * RHS of the target outer join will be made empty here, but that's OK
355  * since caller will delete that SpecialJoinInfo entirely.
356  */
357  foreach(l, root->join_info_list)
358  {
359  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
360 
361  sjinfo->min_lefthand = bms_del_member(sjinfo->min_lefthand, relid);
362  sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, relid);
363  sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, relid);
364  sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, relid);
365  }
366 
367  /*
368  * Likewise remove references from PlaceHolderVar data structures,
369  * removing any no-longer-needed placeholders entirely.
370  *
371  * Removal is a bit tricker than it might seem: we can remove PHVs that
372  * are used at the target rel and/or in the join qual, but not those that
373  * are used at join partner rels or above the join. It's not that easy to
374  * distinguish PHVs used at partner rels from those used in the join qual,
375  * since they will both have ph_needed sets that are subsets of
376  * joinrelids. However, a PHV used at a partner rel could not have the
377  * target rel in ph_eval_at, so we check that while deciding whether to
378  * remove or just update the PHV. There is no corresponding test in
379  * join_is_removable because it doesn't need to distinguish those cases.
380  */
381  for (l = list_head(root->placeholder_list); l != NULL; l = nextl)
382  {
383  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
384 
385  nextl = lnext(l);
386  Assert(!bms_is_member(relid, phinfo->ph_lateral));
387  if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
388  bms_is_member(relid, phinfo->ph_eval_at))
390  phinfo);
391  else
392  {
393  phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
394  Assert(!bms_is_empty(phinfo->ph_eval_at));
395  phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
396  }
397  }
398 
399  /*
400  * Remove any joinquals referencing the rel from the joininfo lists.
401  *
402  * In some cases, a joinqual has to be put back after deleting its
403  * reference to the target rel. This can occur for pseudoconstant and
404  * outerjoin-delayed quals, which can get marked as requiring the rel in
405  * order to force them to be evaluated at or above the join. We can't
406  * just discard them, though. Only quals that logically belonged to the
407  * outer join being discarded should be removed from the query.
408  *
409  * We must make a copy of the rel's old joininfo list before starting the
410  * loop, because otherwise remove_join_clause_from_rels would destroy the
411  * list while we're scanning it.
412  */
413  joininfos = list_copy(rel->joininfo);
414  foreach(l, joininfos)
415  {
416  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
417 
418  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
419 
420  if (rinfo->is_pushed_down ||
421  !bms_equal(rinfo->required_relids, joinrelids))
422  {
423  /* Recheck that qual doesn't actually reference the target rel */
424  Assert(!bms_is_member(relid, rinfo->clause_relids));
425 
426  /*
427  * The required_relids probably aren't shared with anything else,
428  * but let's copy them just to be sure.
429  */
430  rinfo->required_relids = bms_copy(rinfo->required_relids);
432  relid);
433  distribute_restrictinfo_to_rels(root, rinfo);
434  }
435  }
436 
437  /*
438  * There may be references to the rel in root->fkey_list, but if so,
439  * match_foreign_keys_to_quals() will get rid of them.
440  */
441 }
Relids ph_needed
Definition: relation.h:1937
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:122
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:110
Relids ph_eval_at
Definition: relation.h:1935
RelOptKind reloptkind
Definition: relation.h:487
Relids * attr_needed
Definition: relation.h:523
List * join_info_list
Definition: relation.h:247
Relids required_relids
Definition: relation.h:1655
Relids min_righthand
Definition: relation.h:1808
Relids clause_relids
Definition: relation.h:1652
List * list_copy(const List *oldlist)
Definition: list.c:1160
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:590
Relids syn_lefthand
Definition: relation.h:1809
struct RelOptInfo ** simple_rel_array
Definition: relation.h:176
Relids syn_righthand
Definition: relation.h:1810
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:2203
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
List * joininfo
Definition: relation.h:549
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
int simple_rel_array_size
Definition: relation.h:177
#define lnext(lc)
Definition: pg_list.h:105
Index relid
Definition: relation.h:518
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:633
Relids ph_lateral
Definition: relation.h:1936
unsigned int Index
Definition: c.h:361
bool is_pushed_down
Definition: relation.h:1639
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:670
#define lfirst(lc)
Definition: pg_list.h:106
AttrNumber max_attr
Definition: relation.h:522
List * placeholder_list
Definition: relation.h:253
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:219
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:705
Definition: pg_list.h:45
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:419
Relids min_lefthand
Definition: relation.h:1807
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
AttrNumber min_attr
Definition: relation.h:521
List* remove_useless_joins ( PlannerInfo root,
List joinlist 
)

Definition at line 55 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().

56 {
57  ListCell *lc;
58 
59  /*
60  * We are only interested in relations that are left-joined to, so we can
61  * scan the join_info_list to find them easily.
62  */
63 restart:
64  foreach(lc, root->join_info_list)
65  {
66  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
67  int innerrelid;
68  int nremoved;
69 
70  /* Skip if not removable */
71  if (!join_is_removable(root, sjinfo))
72  continue;
73 
74  /*
75  * Currently, join_is_removable can only succeed when the sjinfo's
76  * righthand is a single baserel. Remove that rel from the query and
77  * joinlist.
78  */
79  innerrelid = bms_singleton_member(sjinfo->min_righthand);
80 
81  remove_rel_from_query(root, innerrelid,
82  bms_union(sjinfo->min_lefthand,
83  sjinfo->min_righthand));
84 
85  /* We verify that exactly one reference gets removed from joinlist */
86  nremoved = 0;
87  joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
88  if (nremoved != 1)
89  elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
90 
91  /*
92  * We can delete this SpecialJoinInfo from the list too, since it's no
93  * longer of interest.
94  */
95  root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
96 
97  /*
98  * Restart the scan. This is necessary to ensure we find all
99  * removable joins independently of ordering of the join_info_list
100  * (note that removal of attr_needed bits may make a join appear
101  * removable that did not before). Also, since we just deleted the
102  * current list cell, we'd have to have some kluge to continue the
103  * list scan anyway.
104  */
105  goto restart;
106  }
107 
108  return joinlist;
109 }
List * join_info_list
Definition: relation.h:247
Relids min_righthand
Definition: relation.h:1808
static void remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
Definition: analyzejoins.c:308
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:590
#define ERROR
Definition: elog.h:43
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:154
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:496
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
static List * remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
Definition: analyzejoins.c:453
#define elog
Definition: elog.h:219
Relids min_lefthand
Definition: relation.h:1807